NFA DFA and Regex to Transition Table
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.
I'm not certain if either of these links might help you.
The first provide a very simple NFA/DFA implementation in Python, with conversion from NFA to DFA. It doesn't generate the NFA from a regex though, but it is not so difficult to do. The second site provides a long discussion on NFA vs DFA, including numerous code examples (mostly in C) and links to external libraries that I know little of. The third and fourth links provide the source code of two regex engines implementation developped by the second article's author, including parsing from regex to NFA, then conversion from NFA to DFA. Note however that I haven't had a look at either of these projects.
Otherwise, I would mention that most real world regex engines use NFA, not DFA, because of some extended features that simply can't be performed with a DFA. So if none of hte links above can help you, then you might have some luck looking at compiler-compilers, since they are the ones that actually use DFAs.
链接地址: http://www.djcxy.com/p/74796.html上一篇: 惰性量词在PCRE中的工作原理如何？
下一篇: NFA DFA和正则表达式到转换表