3

我的 C 有点不稳定,但我查看了 python 的源代码,看起来 python 的大部分re模块都是由状态机实现的。这并不奇怪,因为正则表达式可以简化为确定性有限状态机。

我想其他正则表达式实现是相似的。但是根据教科书的定义,很少有现代正则表达式实现是常规的。那么他们如何解释不规则性,比如反向引用?

(.*)\1   // this is not regular
4

1 回答 1

2

他们使用修正的(超越有限状态的)自动机类来解释这一点,并且比普通的汤姆森算法更复杂的匹配算法。如果您找到任何特定“RE”引擎支持的自动机类的正式表征,您将非常幸运。

根据我可以从 Pythonre源代码中弥补的内容,它将组存储在缓冲区中(无论如何它必须这样做,因为它必须将其作为匹配对象的一部分返回)并在匹配算法中进行简单的字符串匹配,消耗为组匹配缓冲区中有许多字符。

[可选咆哮:不幸的是,RE 引擎在实践中是 NFA 之上的黑客集合,破坏了它们的数学特性。许多实现者忽略了正则语言的优雅代数及其对正则关系的强大扩展,这些可以被FST有效地捕获。]

于 2011-11-20T23:17:30.840 回答