NFA DFA和正则表达式到转换表

 

我一直在寻找一些算法，它可以输入一个正则表达式或一个字符串，并将其转换为NFA然后是DFA，并且实际上会打印出相应的最终DFA的转换表。

因此，我想知道是否已经有一个算法或者C或Python库来实现这个功能，或者如果您有算法的使用建议，我可以实现。

谢谢。

我不确定这些链接是否可以帮助您。

第一个提供了Python中非常简单的NFA / DFA实现，并将NFA转换为DFA。 它不会从正则表达式生成NFA，但它不是很难做到。 第二个网站对NFA和DFA进行了长时间的讨论，其中包括大量代码示例（主要以C语言编写）以及我所知道的外部库的链接。 第三和第四个链接提供了第二篇文章作者开发的两个regex引擎实现的源代码，包括从正则表达式解析到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的。

    链接地址: http://www.djcxy.com/p/74795.html

    上一篇: NFA DFA and Regex to Transition Table

    下一篇: What's the regex corresponding to this DFA?