regex - 可以将具有负前瞻的 RegEx 表示为有限自动机吗？

Question

我正在开发一种用于操作上下文无关语言的工具，语法的内部表示存储为有限自动机。进一步研究 EBNF 和 RegEx，我了解到 EBNF 有“例外”，而 RegEx 有负前瞻。我可以看到这些可能是如何通过对称差异 NFA 建模的，但我怀疑它们超出了常规 DFA 或 NFA 的能力。

但后来我遇到了这个，这很清楚地表明我错了。任何人都可以指出一个免费资源，它可能显示如何将带​​有异常的 EBNF 或带有负前瞻的 RegEx 转换为 DFA？

Answer 1

您可以在完整的可能匹配项减去负前瞻匹配时将负前瞻替换为正前瞻。例如，如果我们使用单个字符 az 作为匹配空间，/what(?!n)/则与/what(?=[a-mo-z]|$)/（$因为字符串结尾是可能的匹配项之一是必需的）相同。这在理论上是可以的，但在处理更大的匹配时实际上不是很好，比如/afraid of (?!chinese)/.

https://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto很好地处理了将前瞻转换为类似 DFA 的内容，具有最后的重要警告。