import java.util.regex.Matcher; import java.util.regex.Pattern;最简单的使用方法：
String regex = "test";
String testString = "test";
Pattern testPattern = Pattern.compile(regex);
Matcher testMatcher = testPattern.matcher(testString);
while (testMatcher.find()) {
String tmpResult = testMatcher.group();
}
Pattern.compile(regex) 用来生成一个 Pattern 的实例。我们不能用 new Pattern 来生成一个 Pattern 对象，因为它的构建方法是 private ：
private Pattern(String p, int f) {
pattern = p;
flags = f;
// to use UNICODE_CASE if UNICODE_CHARACTER_CLASS present
if ((flags & UNICODE_CHARACTER_CLASS) != 0)
flags |= UNICODE_CASE;
// Reset group index count
capturingGroupCount = 1;
localCount = 0;
if (pattern.length() > 0) {
compile();
} else {
root = new Start(lastAccept);
matchRoot = lastAccept;
}
}
而当我们调用 Pattern.compile(regex) 的时候，实际上是执行的这段代码：
public static Pattern compile(String regex) {
return new Pattern(regex, 0);
}
Pattern(String p, int f) 的第一个参数是字符串形式的正则表达式，第二个参数是一些特殊选项的开关。它接受如下几个参数：
/**
* Enables Unix lines mode.
*/
public static final int UNIX_LINES = 0x01;
/**
* Enables case-insensitive matching.
*/
public static final int CASE_INSENSITIVE = 0x02;
/**
* Permits whitespace and comments in pattern.
*/
public static final int COMMENTS = 0x04;
/**
* Enables multiline mode.
*/
public static final int MULTILINE = 0x08;
/**
* Enables literal parsing of the pattern.
*/
public static final int LITERAL = 0x10;
/**
* Enables dotall mode.
*/
public static final int DOTALL = 0x20;
/**
* Enables Unicode-aware case folding.
*/
public static final int UNICODE_CASE = 0x40;
/**
* Enables canonical equivalence.
*/
public static final int CANON_EQ = 0x80;
/**
* Enables the Unicode version of Predefined character classes and
* POSIX character classes.
*/
public static final int UNICODE_CHARACTER_CLASS = 0x100;
一般而言我们可以用这种方法来调用：
Pattern testPattern = Pattern.compile(regex, Pattern.CASE_INSENSITIVE);
testPattern.matcher(testString) 用来获取一个 Matcher 对象的实例。它会调用如下方法：
public Matcher matcher(CharSequence input) {
if (!compiled) {
synchronized(this) {
if (!compiled)
compile();
}
}
Matcher m = new Matcher(this, input);
return m;
}
因为我们的 Pattern 已经编译 (compile) 过了，所以实际上这段代码和 new Matcher(testPattern, testString) 是相同的。不过使用这种方法可以保证 Pattern 是经过编译的。Matcher.find() 方法搜索 testString 匹配正则表达式的子字符串，Matcher.group() 会调用 Matcher.group(0) 即：
public String group(int group) {
if (first < 0)
throw new IllegalStateException("No match found");
if (group < 0 || group > groupCount())
throw new IndexOutOfBoundsException("No group " + group);
if ((groups[group*2] == -1) || (groups[group*2+1] == -1))
return null;
return getSubSequence(groups[group * 2], groups[group * 2 + 1]).toString();
}
这里的 groups 是一个数组，用于存储每次匹配时匹配的起始与结尾所在的位置。数组的大小由正则表达式中 group 的个数决定。在 Matcher 初始化时候指定：
Matcher(Pattern parent, CharSequence text) {
this.parentPattern = parent;
this.text = text;
// Allocate state storage
int parentGroupCount = Math.max(parent.capturingGroupCount, 10);
groups = new int[parentGroupCount * 2];
locals = new int[parent.localCount];
// Put fields into initial states
reset();
}
parent.capturingGroupCount 表示正则表达式中 group 的个数再加1，因为 0 表示整个匹配项。而 groups 的大小则是这个数乘以2。这里比较有意思的是 Math.max(parent.capturingGroupCount, 10)。 我弄不明白为什么要这样做，而且我做了几个简单的实验，不用这一步并没有出现 Bug。
需要注意的是，在调用 group() 之前一定要确保 find() 返回的是 true 。如果 find() 返回 false 表示在该字符串中已经找不到更多的匹配项了。这时候调用 group() 会抛出 IllegalStateException 异常。当然如果你调用 group(100) 很可能会抛出 IndexOutOfBoundsException 异常。稳妥的方法是先调用 testMatcher.groupCount() 再根据结果调用 group() 。
find() 方法如下：
public boolean find() {
int nextSearchIndex = last;
if (nextSearchIndex == first)
nextSearchIndex++;
// If next search starts before region, start it at region
if (nextSearchIndex < from)
nextSearchIndex = from;
// If next search starts beyond region then it fails
if (nextSearchIndex > to) {
for (int i = 0; i < groups.length; i++)
groups[i] = -1;
return false;
}
return search(nextSearchIndex);
}
boolean search(int from) {
this.hitEnd = false;
this.requireEnd = false;
from = from < 0 ? 0 : from;
this.first = from;
this.oldLast = oldLast < 0 ? from : oldLast;
for (int i = 0; i < groups.length; i++)
groups[i] = -1;
acceptMode = NOANCHOR;
boolean result = parentPattern.root.match(this, from, text);
if (!result)
this.first = -1;
this.oldLast = this.last;
return result;
}
由于一个字符串中可能会有多个子自字符串与正则表达式相匹配。 find() 方法就是确保我们能顺序地得到每组匹配地结果。这里的 last 记录上次匹配的末尾位置。from 和 to 默认值为 0 和整个字符串的长度，也可以通过 public Matcher region(int start, int end) 来设置。所以每次调用 search(nextSearchIndex) 的时候可以保证是从上次匹配结果的末尾开始的。这里最重要的方法就是：
boolean result = parentPattern.root.match(this, from, text);
parentPattern 是 Pattern 类的实例，在刚才讲 Matcher 的构建方法时有代码可以证明。再进入 parentPattern.root.match 的方法之后我们可以看到如下代码：
boolean match(Matcher matcher, int i, CharSequence seq) {
matcher.last = i;
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
return true;
}
看着非常简单，在这里会修改 matcher 里 groups 的内容，从而得到匹配项的起始和结束的位置。没错这就是 Pattern 类实现正则表达式的方法。但我们知道正则表达式的匹配是用有限状态机来实现的。上面这段代码只是一个名叫 Node 的类的实现。实际上 Pattern 类中一共有31个子类直接继承了 Node， 24个类间接继承了 Node， 实现了43个 match() 的方法（由于间接继承的存在）。
以下是 Node 的源代码：
static class Node extends Object {
Node next;
Node() {
next = Pattern.accept;
}
/**
* This method implements the classic accept node.
*/
boolean match(Matcher matcher, int i, CharSequence seq) {
matcher.last = i;
matcher.groups[0] = matcher.first;
matcher.groups[1] = matcher.last;
return true;
}
/**
* This method is good for all zero length assertions.
*/
boolean study(TreeInfo info) {
if (next != null) {
return next.study(info);
} else {
return info.deterministic;
}
}
}
实际上 Pattern 就是靠 compile() 来实现对正则表达式的编译：
private void compile() {
// Handle canonical equivalences
if (has(CANON_EQ) && !has(LITERAL)) {
normalize();
} else {
normalizedPattern = pattern;
}
patternLength = normalizedPattern.length();
// Copy pattern to int array for convenience
// Use double zero to terminate pattern
temp = new int[patternLength + 2];
hasSupplementary = false;
int c, count = 0;
// Convert all chars into code points
for (int x = 0; x < patternLength; x += Character.charCount(c)) {
c = normalizedPattern.codePointAt(x);
if (isSupplementary(c)) {
hasSupplementary = true;
}
temp[count++] = c;
}
patternLength = count; // patternLength now in code points
if (! has(LITERAL))
RemoveQEQuoting();
// Allocate all temporary objects here.
buffer = new int[32];
groupNodes = new GroupHead[10];
namedGroups = null;
if (has(LITERAL)) {
// Literal pattern handling
matchRoot = newSlice(temp, patternLength, hasSupplementary);
matchRoot.next = lastAccept;
} else {
// Start recursive descent parsing
matchRoot = expr(lastAccept);
// Check extra pattern characters
if (patternLength != cursor) {
if (peek() == ')') {
throw error("Unmatched closing ')'");
} else {
throw error("Unexpected internal error");
}
}
}
// Peephole optimization
if (matchRoot instanceof Slice) {
root = BnM.optimize(matchRoot);
if (root == matchRoot) {
root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
}
} else if (matchRoot instanceof Begin || matchRoot instanceof First) {
root = matchRoot;
} else {
root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
}
// Release temporary storage
temp = null;
buffer = null;
groupNodes = null;
patternLength = 0;
compiled = true;
}
不同的正则会生成不同类型的 Node 对象，不同对象的 match 方法不同。这里是根据是否开启 LITERAL 选项，分别调用 expr 和 newSlice 来构建正则表达式所对应的 Node 对象。至于 Pattern 如何构建 Node 对象，基本上就是把正则表达式转换为有限状态机的过程。并伴随着处理不同选项的琐碎细节。
可以参考：
Youtube: Convert Regular Expression to Finite-State Automaton
Implementing Regular Expressions
Regular Expressions and Finite-State Automata
Regular Languages and Finite-State Automata
No comments:
Post a Comment