regex - NFA DFA and Regex to Transition Table

Question

I have been looking out for some algorithm that has in input a regular expression or a string and that converts it into an NFA and then a DFA, and that would actually print out the transition table of the corresponding final DFA.

I'am thus wondering if there is already an algorithm or C or Python library that does that,or if you have suggestions of algorithms to use, that I could implement.

Thank you.

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 执行。因此，如果上面的 hte 链接都不能帮助您，那么您可能会对编译器 - 编译器有所帮助，因为它们是实际使用 DFA 的那些。