12/27/2013

Regex in Java

在 java 中使用正则表达式需要用到以下两个类:
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