支持递归引用的正则表达式匹配器最优时间复杂度探究

问题背景 #

你提到的这种支持+、?、*、.、|、字符类、锚点、分组，还允许通过{<regex-name>}进行递归引用的正则，本质上已经超出了传统正则语言的范畴——它等价于带正则扩展的上下文无关文法（EBNF），匹配问题其实就是上下文无关语言的成员判定问题。

现有思路与最优复杂度对比 #

你当前构思的O(m²n³)实现是可行的，但并非最优。这类匹配问题的最优最坏时间复杂度可以达到O(mn³)，下面具体解释原因：

1. 从递归正则到CFG的转化 #

首先，我们可以把递归正则等价转化为标准的上下文无关文法（CFG）：

• 每个递归的正则名称对应CFG的一个非终结符
• 正则中的运算符（比如*、+、|、字符匹配）可以转化为常数个CFG产生式，整个转化过程的规模是O(m)级别的（m是原正则的长度）。
  比如你给出的括号匹配正则brackets = (\({brackets}\))*，可以转化为：

brackets → ε | ( brackets ) brackets

这个转化后的文法大小和原正则长度m线性相关。

2. 最优的CFG成员判定算法 #

对于一般的CFG，经典的Earley算法和CYK算法的最坏时间复杂度都是O(n³|G|)，其中|G|是文法的大小（对应这里的m）：

• Earley算法可以处理任意CFG，包括左递归、相互递归的情况（比如你给出的a和b互相递归的例子），在最坏情况下是O(n³)每文法大小单位，也就是整体O(mn³)。
• 如果你直接在正则结构上做动态规划而不先转化为CFG，可能会因为重复处理正则中的嵌套结构引入额外的m系数，导致O(m²n³)的复杂度——但通过先把正则转化为紧凑的CFG，就能把这个系数降到m，得到更优的结果。

3. 有没有更低复杂度的可能？ #

对于某些特殊结构的递归正则（比如仅右递归、线性文法结构，比如单纯的括号匹配），可以做到O(mn²)的时间复杂度，但对于任意递归正则（比如相互递归、包含任意分支的情况），O(mn³)是目前已知的最坏情况下的最优复杂度——因为上下文无关语言的成员判定问题本身的下界就是Ω(n³)（对于一般CFG），加上文法大小m的线性系数，就是Ω(mn³)。

总结 #

如果你想优化你的实现，可以先把递归正则转化为等价的CFG，再用Earley或优化后的CYK算法进行匹配，这样就能把复杂度从O(m²n³)降到最优的O(mn³)。

内容的提问来源于stack exchange，提问作者Ofek