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