正则表达式引擎如何解决不规则问题？

Question

我的C有点不稳定，但是我看过python的源代码，它看起来像大多数python的re模块是由状态机实现的。这并不令人惊讶，因为正则表达式可以简化为确定性有限状态机。

我想其他正则表达式的实现是相似的。但是，根据教科书的定义，很少有（如果有的话）现代正则表达式实现是常规的。那么他们如何解决违规问题，如反向引用？

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

Answer 1

他们使用经修订的（超越有限状态）自动机类考虑到这一点，并匹配算法比vanilla Thomson algorithm更加复杂。如果您发现任何特定的“RE”引擎支持的自动机类的正式特性，那么您非常抱歉。

从Python re源代码中可以看出，它将该组存储在一个缓冲区中（无论如何，因为它必须将它作为匹配对象的一部分返回），并且可以直接在匹配算法，消耗与组匹配缓冲区中的字符数量一样多的字符。

[可选的咆哮：不幸的是，RE引擎实际上是NFA之上的黑客集合，它们破坏了它们的数学属性。许多实现者忽略了regular languages的优雅代数及其对正则关系的强大扩展，可以通过FSTs有效地捕获它。]