我的 C 有点不稳定，但我查看了 python 的源代码，看起来 python 的大部分re模块都是由状态机实现的。这并不奇怪，因为正则表达式可以简化为确定性有限状态机。
我想其他正则表达式实现是相似的。但是根据教科书的定义，很少有现代正则表达式实现是常规的。那么他们如何解释不规则性，比如反向引用？
(.*)\1 // this is not regular
问问题
59 次
1 回答
2
他们使用修正的（超越有限状态的）自动机类来解释这一点，并且比普通的汤姆森算法更复杂的匹配算法。如果您找到任何特定“RE”引擎支持的自动机类的正式表征，您将非常幸运。
根据我可以从 Pythonre源代码中弥补的内容，它将组存储在缓冲区中（无论如何它必须这样做，因为它必须将其作为匹配对象的一部分返回）并在匹配算法中进行简单的字符串匹配，消耗为组匹配缓冲区中有许多字符。
[可选咆哮：不幸的是，RE 引擎在实践中是 NFA 之上的黑客集合，破坏了它们的数学特性。许多实现者忽略了正则语言的优雅代数及其对正则关系的强大扩展，这些可以被FST有效地捕获。]
于 2011-11-20T23:17:30.840 回答