Perl兼容的正则表达式引擎：如何实现？

Question

perl，python，java和vim等使用正则表达式进行解析的基本方法是什么？不聪明的形式语言方法（即NFA，DFA）; 解析器组合器（例如14行正则表达式引擎）也是如此。我看过Java实现perl样式正则表达式的源代码，但是其复杂的功能（例如，反向引用）和效率（例如，Boyer-Moore子字符串匹配）使得很难看到它的基本工作原理。编辑 各种消息来源说，“回溯”参与（如正则表达式匹配可以是简单，快速;形式化方法的课程），但不清除到底是什么回溯上...它来评估的方式NFA？可以直接从正则表达式的AST完成吗？java / perl / python正则表达式引擎实际上是做什么的？是否是这样的：“一种以常规语言生成所有可能单词的方法，但是一旦它与输入字符串不匹配，就放弃特定单词”。

Answer 1

正则表达式引擎中有两种通用方法。

• 正则表达式可以转换为有限自动机。这种关系在计算机科学中得到了很好的研究。这些有限的自动化然后可以有效地执行，甚至向后运行。它们提供了有力的保证，例如在线性时间和关于输入字符串的恒定空间中运行，但是从正则表达式创建有限自动机可能会很昂贵。这种方法还将引擎限制为真正的正则表达式，即排除了诸如反向引用或递归之类的高级功能。

• 正则表达式可以由回溯引擎解释。如果模式中的替代方法失败，则可以追溯到最后一个决策点，然后尝试其他方法。这是非常灵活的，并且（具有递归+命名子模式等额外功能）可以解析更大类的形式语言（形式上是LL（*）语法集）。这与PEG解析器非常相似。最大的缺点：由于回溯，运行regex会花费成倍的时间-即使没有任何其他高级功能。

最重要的是，正则表达式引擎具有额外的优化功能，例如首先在模式中搜索常量子字符串，因为它比运行任何类型的正则表达式（任何人甚至都可以使用矢量化CPU指令）更高效。如果在多个常量字符串之间有一个选择点，则可以很容易地将它们编译成trie数据结构（实际上是一个简单的有限自动机）。这样可以减少回溯的数量。

a*a*a*a*a*b字符串上的模式是证明有限自动机和回溯的区别的正则表达式aaaaaaaaaaaaaaacb。有限的自动机可以很容易地看到，由于c输入中的原因，该模式将不匹配。但是，回溯引擎现在具有许多决策点，可以在其中为每个a*子模式尝试不同的长度。re在这种情况下，像Perl或Python中的模块之类的Regex引擎呈指数级，即完成时间很长–a向输入中添加更多s会使其花费更长的时间。如果不受信任的用户可以提供任意正则表达式，则可以进行有趣的拒绝服务攻击。对于不受信任的输入，仅应使用基于有限自动机的正则表达式引擎，例如Google的RE2。

Answer 2

Perl 2中的Regex摘自Henry Spencer。

regexp.c 仅有两千行，并不比具有更多功能的更高版本难。