NFA、DFA和正则表达式转换成状态转移表

Question

NFA、DFA和正则表达式转换成状态转移表

regexdfanfa

5

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

因此，我想知道是否已经有算法或C或Python库可以做到这一点，或者您有建议要使用的算法，我可以进行实现。

谢谢。

- Anoracx

1

你的问题有点过于宽泛和主观，难以回答：你在问自己是否应该编写代码或者是否存在一种现有的库。这类形式的问题在 Stack Overflow 上并不适合。你能否更新问题，让它更具体一些，比如“我该如何使用库 X 来解决这个问题？”或者“在这里什么算法最合适？” - templatetypedef

嗯，我在询问是否有现成的库可用，或者我应该从头开始实现，或者（这就是为什么我提到了汤姆森）如果有人知道我可以实现的算法。但我稍微修改了一下问题，希望更清楚了。 - Anoracx

http://projectsgeek.com/2011/05/regular-expression-to-dfa-code-in-c-language.html - Grijesh Chauhan

http://www.sourcecodeonline.com/list?q=regular_expression_to_dfa_conversion_c_code - Grijesh Chauhan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James · Accepted Answer

我不确定这两个链接是否能帮到您。

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

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