从0到1打造正则表达式执行引擎

@

目录

今天是五一假期第一天，这里先给大家拜个晚 咳咳！！祝大家五一快乐，我这里给大家奉上一篇硬核教程。首先声明，这篇文章不是教你如何写正则表达式，而是教你写一个能执行正则表达式的 执行引擎

。 网上教你写正则表达式的文章、教程很多，但教你写引擎的并不多。很多人认为我就是用用而已，没必要理解那么深，但知道原理是在修炼内功，正则表达式底层原理并不单单是用在这，而是出现在计算机领域的各个角落。理解原理可以让你以后写字符串匹配时正则表达式能够信手拈来，理解原理也是触类旁通的基础。废话不多说，直接开始正式内容。

本文是我个人做的动手实践性项目，所以未完整支持所有语法，而且因为是用NFA实现的所以性能比生产级的执行引擎差好多。目前源码已开放至 https://github.com/xindoo/regex ，后续会继续更新，欢迎Star、Fork 提PR。

目前支持的正则语义如下:

• 基本语法: . ? * + () |
• 字符集合: []
• 特殊类型符号: \d \D \s \S \w \W

前置知识

声明：本文不是入门级的文章，所以如果你想看懂后文的内容，需要具备以下的基本知识。

0. 基本的编程知识，虽然这里我是用 java 写的，但并不要求懂java，懂其他语法也行，基本流程都是类似，就是语法细节不同。
1. 了解正则表达式，知道简单的正则表达式如何写。
2. 基本的数据结构知识，知道有向图的概念，知道什么是递归和回溯。

有限状态机

有限状态机(Finite-state machine)，也被称为有限状态自动机(finite-state automation)，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型(From 维基百科 状态机 ) 。 听起来晦涩难懂，我用大白话描述一遍，状态机其实就是用图把状态和状态之间的关系描述出来，状态机中的一个状态可以在某些给定条件下变成另外一种状态。举个很简单的例子你就懂了。

状态机下的正则表达式

串联匹配

并连匹配 (正则表达式中的 |)

重复匹配(正则表达式中的 ? + *)

正则表达式里有4中表示重复的方式，分别是：

1. ？重复0-1次
2. • 重复1次以上
3. • 重复0次以上
4. {n,m} 重复n到m次
   我来分别画下这4种方式如何在状态机里表示。

重复0-1次 ？

0状态可以通过E也可以依赖$\epsilon$直接跳过E到达1状态，实现E的0次匹配。

重复1次以上

0到1后可以再通过$\epsilon$跳回来，就可以实现E的1次以上匹配了。

重复0次以上

仔细看其实就是 ? + 的结合。

匹配指定次数

这种建图方式简单粗暴，但问题就是如果n和m很大的话，最后生成的状态图也会很大。其实可以把指定次数的匹配做成一条特殊的边，可以极大减小图的大小。

特殊符号(正则表达式中的 . \d \s……)

正则表达式中还支持很多某类的字符，比如 . 表示任意非换行符， \d 标识数字， [] 可以指定字符集…… ，其实这些都和图的形态无关，只是某调特殊的边而已，自己实现的时候可以选择具体的实现方式，比如后面代码中我用了策略模式来实现不同的匹配策略，简化了正则引擎的代码。

子表达式(正则表达式 () )

子表达可以Tompson算法，其实就是用递归去生成 () 中的子图，然后把子图拼接到当前图上面。（什么Tompson说的那么高大上，不就是递归吗！）

练习题

代码实现

建图

看完上文之后相信你一直知道如果将一个正则表达式转化为状态机的方法了，这里我们要将理论转化为代码。首先我们要将图转化为代码标识，我用State表示一个节点，其中用了Map<MatchStrategy, List > next表示其后继节点，next中有个key-value就是一条边，MatchStrategy用来描述边的信息。

public class State {
    private static int idCnt = 0;
    private int id;
    private int stateType;

    public State() {
        this.id = idCnt++;
    }

    Map<MatchStrategy, List<State>> next = new HashMap<>();

    public void addNext(MatchStrategy path, State state) {
        List<State> list = next.get(path);
        if (list == null) {
            list = new ArrayList<>();
            next.put(path, list);
        }
        list.add(state);
    }
    protected void setStateType() {
        stateType = 1;
    }
    protected boolean isEndState() {
        return stateType == 1;
    }
}

NFAGraph表示一个完整的图，其中封装了对图的操作，比如其中就实现了上文中图串 并连和重复的操作（注意我没有实现{}）。

public class NFAGraph {
    public State start;
    public State end;
    public NFAGraph(State start, State end) {
        this.start = start;
        this.end = end;
    }

    // |
    public void addParallelGraph(NFAGraph NFAGraph) {
        State newStart = new State();
        State newEnd = new State();
        MatchStrategy path = new EpsilonMatchStrategy();
        newStart.addNext(path, this.start);
        newStart.addNext(path, NFAGraph.start);
        this.end.addNext(path, newEnd);
        NFAGraph.end.addNext(path, newEnd);
        this.start = newStart;
        this.end = newEnd;
    }

    //
    public void addSeriesGraph(NFAGraph NFAGraph) {
        MatchStrategy path = new EpsilonMatchStrategy();
        this.end.addNext(path, NFAGraph.start);
        this.end = NFAGraph.end;
    }

    // * 重复0-n次
    public void repeatStar() {
        repeatPlus();
        addSToE(); // 重复0
    }

    // ? 重复0次哦
    public void addSToE() {
        MatchStrategy path = new EpsilonMatchStrategy();
        start.addNext(path, end);
    }

    // + 重复1-n次
    public void repeatPlus() {
        State newStart = new State();
        State newEnd = new State();
        MatchStrategy path = new EpsilonMatchStrategy();
        newStart.addNext(path, this.start);
        end.addNext(path, newEnd);
        end.addNext(path, start);
        this.start = newStart;
        this.end = newEnd;
    }

}

整个建图的过程就是依照输入的字符建立边和节点之间的关系，并完成图的拼接。

private static NFAGraph regex2nfa(String regex) {
        Reader reader = new Reader(regex);
        NFAGraph NFAGraph = null;
        while (reader.hasNext()) {
            char ch = reader.next();
            MatchStrategy matchStrategy = null;
            switch (ch) {
                // 子表达式特殊处理
                case '(' : {
                    String subRegex = reader.getSubRegex(reader);
                    NFAGraph newNFAGraph = regex2nfa(subRegex);
                    checkRepeat(reader, newNFAGraph);
                    if (NFAGraph == null) {
                        NFAGraph = newNFAGraph;
                    } else {
                        NFAGraph.addSeriesGraph(newNFAGraph);
                    }
                    break;
                }
                // 或表达式特殊处理
                case '|' : {
                    String remainRegex = reader.getRemainRegex(reader);
                    NFAGraph newNFAGraph = regex2nfa(remainRegex);
                    if (NFAGraph == null) {
                        NFAGraph = newNFAGraph;
                    } else {
                        NFAGraph.addParallelGraph(newNFAGraph);
                    }
                    break;
                }
                case '[' : {
                    matchStrategy = getCharSetMatch(reader);
                    break;
                }
                case '^' : {
                    break;
                }
                case '$' : {
                    break;
                }
                case '.' : {
                    matchStrategy = new DotMatchStrategy();
                    break;
                }
                // 处理特殊占位符
                case '\\' : {
                    char nextCh = reader.next();
                    switch (nextCh) {
                        case 'd': {
                            matchStrategy = new DigitalMatchStrategy(false);
                            break;
                        }
                        case 'D': {
                            matchStrategy = new DigitalMatchStrategy(true);
                            break;
                        }
                        case 'w': {
                            matchStrategy = new WMatchStrategy(false);
                            break;
                        }
                        case 'W': {
                            matchStrategy = new WMatchStrategy(true);
                            break;
                        }
                        case 's': {
                            matchStrategy = new SpaceMatchStrategy(false);
                            break;
                        }
                        case 'S': {
                            matchStrategy = new SpaceMatchStrategy(true);
                            break;
                        }
                        // 转义后的字符匹配
                        default:{
                            matchStrategy = new CharMatchStrategy(nextCh);
                            break;
                        }
                    }
                    break;
                }

                default : {  // 处理普通字符
                    matchStrategy = new CharMatchStrategy(ch);
                    break;
                }
            }

            // 表明有某类单字符的匹配
            if (matchStrategy != null) {
                State start = new State();
                State end = new State();
                start.addNext(matchStrategy, end);
                NFAGraph newNFAGraph = new NFAGraph(start, end);
                checkRepeat(reader, newNFAGraph);
                if (NFAGraph == null) {
                    NFAGraph = newNFAGraph;
                } else {
                    NFAGraph.addSeriesGraph(newNFAGraph);
                }
            }
        }
        return NFAGraph;
    }

    private static void checkRepeat(Reader reader, NFAGraph newNFAGraph) {
        char nextCh = reader.peak();
        switch (nextCh) {
            case '*': {
                newNFAGraph.repeatStar();
                reader.next();
                break;
            } case '+': {
                newNFAGraph.repeatPlus();
                reader.next();
                break;
            } case '?' : {
                newNFAGraph.addSToE();
                reader.next();
                break;
            } case '{' : {
                //
                break;
            }  default : {
                return;
            }
        }
    }

这里我用了 设计模式 中的策略模式将不同的匹配规则封装到不同的MatchStrategy类里，目前我实现了 . \d \D \s \S \w \w ，具体细节请参考代码。这么设计的好处就是简化了匹配策略的添加，比如如果我想加一个 \x 只匹配16进制字符，我只需要加个策略类就好了，不必改很多代码。

匹配

其实匹配的过程就出从起始态开始，用输入作为边，一直往后走，如果能走到终止态就说明可以匹配，代码主要依赖于递归和回溯，代码如下。

public boolean isMatch(String text) {
        return isMatch(text, 0, nfaGraph.start);
    }

    private boolean isMatch(String text, int pos, State curState) {
        if (pos == text.length()) {
            if (curState.isEndState()) {
                return true;
            }
            return false;
        }

        for (Map.Entry<MatchStrategy, List<State>> entry : curState.next.entrySet()) {
            MatchStrategy matchStrategy = entry.getKey();
            if (matchStrategy instanceof EpsilonMatchStrategy) {
                for (State nextState : entry.getValue()) {
                    if (isMatch(text, pos, nextState)) {
                        return true;
                    }
                }
            } else {
                if (!matchStrategy.isMatch(text.charAt(pos))) {
                    continue;
                }
                // 遍历匹配策略
                for (State nextState : entry.getValue()) {
                    if (isMatch(text, pos + 1, nextState)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

下集预告

还有下集？没错，虽然到这里已经是实现了一个基本的正则表达式引擎，但距离可用在生产环境还差很远，预告如下。

功能完善化

本身上面的引擎对正则语义支持不是很完善，后续我会继续完善代码，有兴趣可以收藏下源码 https://github.com/xindoo/regex ，但应该不会出一篇新博客了，因为原理性的东西都在这里，剩下的就是只是一些编码工作 。

DFA引擎

上文只是实现了NFA引擎，NFA的引擎建图时间复杂度是O(n)，但匹配一个长度为m的字符串时因为涉及到大量的递归和回溯，最坏时间复杂度是O(mn)。与之对比DFA引擎的建图时间复杂度O(n^2)，但匹配时没有回溯，所以匹配复杂度只有O(m)，性能差距还是挺大的。

DFA引擎实现的大体流程是先构造NFA(本文内容)，然后用 子集构造法 将NFA转化为DFA，预计未来我会出一篇博客讲解细节和具体实现。

正则引擎优化

首先DFA引擎是可以继续优化的，使用Hopcroft算法可以近一步将DFA图压缩，更少的状态节点更少的转移边可以实现更好的性能。其次，目前生产级的正则引擎很多都不是单纯用NFA或者DFA实现的，而是二者的结合，不同正则表达式下用不同的引擎可以达到更好的综合性能，简单说NFA图小但要回溯，DFA不需要回溯但有些情况图会特别大。敬请期待我后续博文。

本文由博客一文多发平台 OpenWrite 发布！