使用多态性对正则表达式解析器建模

Question

所以，我正在为学校做一个正则表达式解析器，它创建一个 object 的层次结构来负责匹配。我决定以 object 为导向，因为这样更容易想象语法的实现方式。因此，这些是构成正则表达式的 classes。这一切都在 Java 中，但我认为如果您精通任何 object 面向的语言，您可以继续学习。

我们需要实现的唯一运算符是 Union (+), Kleene-Star (*)，表达式的连接（ab 或可能 (a+b)c），当然还有连接示例中所示的括号.这就是我现在已经实现的，我让它像一个魅力一样工作，主要有一点开销。

parent class, Regexp.java

public abstract class Regexp {

    //Print out the regular expression it's holding
    //Used for debugging purposes
    abstract public void print();

    //Checks if the string matches the expression it's holding
    abstract public Boolean match(String text);

    //Adds a regular expression to be operated upon by the operators
    abstract public void add(Regexp regexp);

    /*
    *To help the main with the overhead to help it decide which regexp will
    *hold the other
    */
    abstract public Boolean isEmpty();

}

有最简单的正则表达式，Base.java，它包含一个字符，如果字符串与该字符匹配，returns为真。

public class Base extends Regexp{
    char c;

    public Base(char c){
        this.c = c;
    }

    public Base(){
        c = null;
    }

    @Override
    public void print() {
        System.out.println(c);
    }

    //If the string is the char, return true
    @Override
    public Boolean match(String text) {
        if(text.length() > 1) return false;
        return text.startsWith(""+c);
    }

    //Not utilized, since base is only contained and cannot contain
    @Override
    public void add(Regexp regexp) {

    }

    @Override
    public Boolean isEmpty() {
        return c == null;
    }

}

A parenthesis，Paren.java，在其中保存一个正则表达式。这里没什么特别的，但说明了匹配的工作原理。

public class Paren extends Regexp{
    //Member variables: What it's holding and if it's holding something
    private Regexp regexp;
    Boolean empty;

    //Parenthesis starts out empty
    public Paren(){
        empty = true;
    }

    //Unless you create it with something to hold
    public Paren(Regexp regexp){
        this.regexp = regexp;
        empty = false;
    }

    //Print out what it's holding
    @Override
    public void print() {
        regexp.print();
    }

    //Real simple; either what you're holding matches the string or it doesn't
    @Override
    public Boolean match(String text) {
        return regexp.match(text);
    }

    //Pass something for it to hold, then it's not empty
    @Override
    public void add(Regexp regexp) {
        this.regexp = regexp;
        empty = false;
    }

    //Return if it's holding something
    @Override
    public Boolean isEmpty() {
        return empty;
    }

}

A Union.java，这是两个可以匹配的正则表达式。如果其中一个匹配，则整个联盟都是匹配的。

public class Union extends Regexp{
    //Members
    Regexp lhs;
    Regexp rhs;

    //Indicating if there's room to push more stuff in
    private Boolean lhsEmpty;
    private Boolean rhsEmpty;

    public Union(){
        lhsEmpty = true;
        rhsEmpty = true;
    }

    //Can start out with something on the left side
    public Union(Regexp lhs){
        this.lhs = lhs;

        lhsEmpty = false;
        rhsEmpty = true;
    }

    //Or with both members set
    public Union(Regexp lhs, Regexp rhs) {
        this.lhs = lhs;
        this.rhs = rhs;

        lhsEmpty = false;
        rhsEmpty = false;
    }

    //Some stuff to help me see the unions format when I'm debugging
    @Override
    public void print() {
        System.out.println("(");
        lhs.print();
        System.out.println("union");
        rhs.print();
        System.out.println(")");

    }

    //If the string matches the left side or right side, it's a match
    @Override
    public Boolean match(String text) {
        if(lhs.match(text) || rhs.match(text)) return true;
        return false;
    }

    /*
    *If the left side is not set, add the member there first
    *If not, and right side is empty, add the member there
    *If they're both full, merge it with the right side
    *(This is a consequence of left-to-right parsing)
    */
    @Override
    public void add(Regexp regexp) {
        if(lhsEmpty){
        lhs = regexp;

        lhsEmpty = false;
        }else if(rhsEmpty){
            rhs = regexp;

            rhsEmpty = false;
        }else{
            rhs.add(regexp);
        }
    }

    //If it's not full, it's empty
    @Override
    public Boolean isEmpty() {
        return (lhsEmpty || rhsEmpty);
    }
}

一个串联，Concat.java，它基本上是一个链接在一起的正则表达式列表。这个比较复杂。

public class Concat extends Regexp{
    /*
    *The list of regexps is called product and the 
    *regexps inside called factors
    */
    List<Regexp> product;

    public Concat(){
        product = new ArrayList<Regexp>();
    }

    public Concat(Regexp regexp){
        product = new ArrayList<Regexp>();
        pushRegexp(regexp);
    }

    public Concat(List<Regexp> product) {
        this.product = product;
    }

    //Adding a new regexp pushes it into the list
    public void pushRegexp(Regexp regexp){
        product.add(regexp);
    }
    //Loops over and prints them
    @Override
    public void print() {
        for(Regexp factor: product){
            factor.print();
        }
    }

    /*
    *Builds up a substring approaching the input string.
    *When it matches, it builds another substring from where it 
    *stopped. If the entire string has been pushed, it checks if
    *there's an equal amount of matches and factors.
    */
    @Override
    public Boolean match(String text) {
        ArrayList<Boolean> bools = new ArrayList<Boolean>();

        int start = 0;
        ListIterator<Regexp> itr = product.listIterator();

        Regexp factor = itr.next();

        for(int i = 0; i <= text.length(); i++){
            String test = text.substring(start, i);

            if(factor.match(test)){
                    start = i;
                    bools.add(true);
                    if(itr.hasNext())
                        factor = itr.next();
            }
        }

        return (allTrue(bools) && (start == text.length()));
    }

    private Boolean allTrue(List<Boolean> bools){
        return product.size() == bools.size();
    }

    @Override
    public void add(Regexp regexp) {
        pushRegexp(regexp);
    }

    @Override
    public Boolean isEmpty() {
        return product.isEmpty();
    }
}

同样，我已经让这些工作让我对我的开销、标记化和所有这些好东西感到满意。现在我想介绍一下Kleene-star操作。它匹配文本中出现的任意次数，甚至 0 次。因此，ba* 将匹配 b、ba、baa、baaa 等，而 (ba)* 将匹配 ba、baba、bababa 等。是否有可能将我的正则表达式扩展到此，或者您是否看到另一种解决此问题的方法？

PS：还有getters，setter等各种支持函数我没有写出来，主要是为了让大家快速了解这些class有效。

Answer 1

您似乎在尝试使用后备算法进行解析。这可以工作——尽管使用 higher-order 函数更容易——但它远不是解析正则表达式的最佳方法（我指的是数学上正则表达式的东西，而不是一整套由 "regular expression" 库以各种语言实现的解析语言的数量）。

这不是最好的方法，因为解析时间与要匹配的字符串的大小不是线性关系；事实上，它可以是指数级的。但要了解这一点，重要的是要了解您当前的实施为何存在问题。

考虑相当简单的正则表达式 (ab+a)(bb+a)。那可以恰好匹配四个字符串：abbb、aba、abb、aa。所有这些字符串都以 a 开头，因此您的连接算法将匹配位置 1 处的第一个连接数 ((ab+a))，然后继续尝试第二个连接数 (bb+a)。这将成功匹配 abb 和 aa，但它会在 aba 和 abbb.

上失败

现在，假设您将串联函数修改为 select 最长的匹配子串而不是最短的子串。在这种情况下，第一个子表达式将匹配三个可能字符串中的 ab（除了 aa），而在 abb.

的情况下匹配将失败

简而言之，当你匹配一个连接R·S时，你需要做这样的事情：

找到一些匹配 R
查看 S 是否与文本的其余部分匹配
如果不是，则用另一个匹配 R

在完整的正则表达式匹配的情况下，我们为 R 列出匹配项的顺序并不重要，但通常我们试图找到与正则表达式匹配的最长子字符串，所以它方便从最长到最短枚举可能的匹配。

这样做意味着我们需要能够在下游故障后重新开始匹配，以找到 "next match"。这不是非常复杂，但它肯定会使界面复杂化，因为所有复合正则表达式运算符都需要 "pass through" 到它们的 children 的失败，以便找到下一个替代方案。也就是说，运算符 R+S 可能首先找到匹配 R 的内容。如果询问下一个可能性，它首先必须询问 R 是否有另一个它可以匹配的字符串，然后再转到 S。（这就是如何让 + 按长度顺序列出匹配项的问题。）

有了这样的实现，就很容易看出如何实现Kleene star(R*)，也很容易看看为什么它会花费指数时间。一种可能的实现方式：

首先，匹配尽可能多的R。
如果要求进行另一场比赛：要求最后一个 R 进行另一场比赛
如果没有更多的可能性，从列表中删除最后一个 R，并询问现在最后一个 R 是什么以进行另一场比赛
如果 none 有效，建议将空字符串作为匹配项
失败

（这可以用递归来简化：匹配一个R，然后匹配一个R*。对于下一个匹配，首先尝试下一个 R*；失败尝试下一个 R 和第一个 R*; 当所有其他方法都失败时，尝试空字符串。）

实现它是一项有趣的编程练习，因此我鼓励您继续。但请注意，还有更好的算法。您可能想阅读 Russ Cox's interesting essays on regular expression matching.

使用多态性对正则表达式解析器建模

Modelling a regular expression parser with polymorphism

java

regex

parsing

polymorphism

abstract-class