正则表达式引擎实现

每天读一篇一线开发者原创好文

需求

实现一个正则表达式的引擎，完成如下需求：

字面值：

字符：，匹配字符;

字符串：，匹配字符串;

字符集：，匹配中的任意字符;

: 匹配任意一个字符;

拼接操作：，匹配;

选择操作：，匹配，或;

量词操作：

，贪心匹配零次或多次；

，贪心匹配一次或多次；

，贪心匹配零次或一次。

断言：

: 匹配母串的末尾位置，它不消耗母串的字符。

此外，还要实现关于匹配的其他额外操作。例如，包括等，但核心算法在于模式匹配的算法实现，让我们开始尝试求解吧。

破冰

当拿到这个需求时，第一个自然反应我打开了的库实现。但是，一分钟后我便立即放弃了这个想法，因为要深入理解的设计和实现，估计并非一时能够搞定。

然后，第二个自然反应是让我想起了(一个语言大师，框架的作者，已逝的大牛)的一个实现库：

这个库实现非常简单，几乎可以秒懂。但是，它基于语言自带的实现的一套命名的正则表达式，并使用漂亮的描述。不幸的是，题目要求不允许使用编程语言(或第三方)的库实现。

纠结之后，我随即打开了搜索，无意中找到一篇博客：Regular Expression Parser in C Using Continuation Passing。这个库相对于的实现显得格外简单，也可以秒懂。在有限的时间里，要想搞定这件事情，看来这个方法是捷径哦。

入坎

众所周知，正则表达式引擎的核心领域模型是语法树。例如，从正则表达式到对象的创建过程，其实就是使用递归下降或其他算法，通过解析字符串的语法，构造出语法树的过程。

而字符串的匹配过程，常常设计状态机，用于控制诸如字符串匹配回溯等复杂的过程。

根据题目要求，不应该解析字符串的正则表达式，而是通过直接使用一些基本原语直接完成语法树的构造。

如果从字符串解析开始搞这个题目，显然已经完全入坎了，相信这次认证的结果势必“惨不忍睹”。

无状态

从字符串的正则表达式到语法树的构造，这个解析过程是相当消耗时间成本的。因此，构造出来的对象最好可以重用，而不是在匹配过程中再重复解析。此外，因为需要重用对象，对象应该是无状态的，它仅仅包含基本元数据；否则，每次匹配完一轮，则需要中间缓存状态，这相当讨厌。

例如：使用节点实现量词的语义，其中表示最小/最大迭代次数的元数据，可以由持有；而在匹配字符串过程中，记录循环的次数则不应该放在上；否则，匹配完成后，需要被，使得清为。

原子规则

在正则表达式的语法树中，诸如是叶子节点。从严格意义上讲，正则表达式的原子操作是一个字符的匹配，多个字符通过操作连接起来，从而实现了字符串的匹配规则。

在数学上，如果显式使用操作表达字符的连接，其一，显得笨拙，冗长啰嗦(即使换成的缩写)；其二，前缀表达式，在此处显得不够自然和直观。因此，数学描述常常使用隐式的空白连接的操作符：。

在编程语言实现中，如果使用内部描述正则表达式。其一，使用字符串，显然比要更直观；也可以将前者看成后者的语法糖表示。其二，如果语言支持操作符重载，那么，则可以极大改善表达力。

贪心

这是正则表达式使用量词匹配字符串的一个基本需求，而且默认情况下，实现的是贪心匹配；而实现的是非贪心匹配。例如，

在贪心模式下，匹配的子串仅包括前个，而不是前个。

回溯

正如上例，首先贪心地尝试匹配了个，直至失败而止；然后，状态机将指针迁移至，显然也是失败的。随后，开始回溯过程，将贪心匹配的个逐一吐出来，尝试匹配。

第1轮回溯：吐出一个，但是，失败；

第2轮回溯：再吐出一个, 此时，成功。

因此，不是匹配个，而仅仅两个。

栈

在图灵机模型中，常常使用栈来实现回溯。显然，回溯在正则表达式匹配中需要耗费很大的计算资源和存储资源。例如，每当一轮，需要将现场一并压栈，包括当前节点，当前母串的游标，的当前迭代次数等运行时数据。当后续节点匹配失败时，则从栈中弹出该节点，并将母串中的位置后移一位，这就是回溯。当栈为空，还是不匹配，则整个模式匹配过程失败。

CPS实现

但是，在模型中，其天然支持回溯过程，压栈过程由运行时的函数调用栈替代。以为例，探究模式匹配的规则库实现。

接口定义

对外暴露的核心编程接口。相当于后驱规则。其中，表示最后一条匹配规则，用于表示模式完全匹配。

流式接口

同时，表示拼接操作，表示选择操作，分别实现模式的串联和并联。其中，表示压栈了的后驱节点，表示剩余的、待匹配的母串，暗喻游标的移动。

使用方法实现流式接口的设计，存在两个考虑的因素。

其一，接口更加人性化，并具有更好的可读性；

其二，使用中缀表达式更加符合常规思维。

当然，完全可以分别重命名为的静态工厂方法，其实现了前缀表达式的接口风格。

原子

只有会向前移动母串的游标(可能会大量产生子串对象，效率未考虑)。

语法糖(字符)

基于的实现，可以构造诸如等语法糖。

可以看成的级联操作。

量词

为了实现自动的回溯，通过递归调用自动压栈。如果匹配失败，则匹配下一个规则，因传递，它表示压栈之前母串游标的原始位置，自动实现回溯的特性。

同理，表示匹配一次或者多次，因此可以复用。

同理，表示要么匹配一次，要么匹配零次，无需像一样递归调用。

理论上，最为抽象的应该是；感兴趣的可以实现一下，如此便彻底消除了重复设计了。

至此，大家应该明白非贪心算法的实现了吧，就是将中的两个操作数颠倒一下求值顺序，就是这么简单，留给大家自行实验。

串(并)联

如果串联多个规则，如果使用的中缀表达式，效果如下：

可以恢复使用的前缀表达式，结合变参的特性，将极大改善表达力。

此处，强制约定至少一个，或一个以上的规则才能启动级联，在编译时安全得到了保护。

断言

是一种断言操作，它不移动游标，但用于断言游标匹配至母串的末尾。

标准库

在标准库实现中，一般不会如上述实现(除函数式语言的库)，主要受限于性能的制约。例如，在的语言实现中，使用状态机实现的。

接下来，就是如何获取匹配的结果。包括是否匹配成功，子匹配结果。正如在的实现中，使用记录匹配的运行时数据，及其最终的结果。如果要匹配多个子串，则可以使用迭代器匹配子串的结果。

因此，留待下一篇文章再做分解，敬请期待。

源代码