NFA DFA和Regex转换表

Question

我一直在寻找一些输入正则表达式或字符串并将其转换为NFA然后转换为DFA的算法,这实际上会打印出相应最终DFA的转换表.

因此,我想知道是否已经有一个算法或C或Python库可以做到这一点,或者如果你有算法的建议,我可以实现.

谢谢.

Answer 1

我不确定这些链接是否对您有帮助。

第一个提供了一个非常简单的 Python 中的 NFA/DFA 实现，以及从 NFA 到 DFA 的转换。虽然它不会从正则表达式生成 NFA，但这并不难做到。第二个站点提供了有关 NFA 与 DFA 的详细讨论，包括大量代码示例（主要是 C 语言）以及我知之甚少的外部库的链接。第三和第四个链接提供了第二篇文章作者开发的两个正则引擎实现的源代码，包括从正则表达式解析到NFA，然后从NFA转换到DFA。但请注意，我还没有看过这两个项目。

• https://gist.github.com/Arachnid/491973
• http://swtch.com/~rsc/regexp/
• https://code.google.com/p/re1/source/browse/
• https://code.google.com/p/re2/source/browse/

否则，我会提到大多数现实世界的正则表达式引擎使用 NFA，而不是 DFA，因为一些扩展功能根本无法使用 DFA 执行。因此，如果上面的链接都不能帮助您，那么您可能会幸运地查看编译器-编译器，因为它们是实际使用 DFA 的编译器。