我正试图将正则表达式转换为NFA,但遇到了问题。如果你不知道这个主题,那么这是一个链接到我所说的here。
这里的问题是,作者解释说,给定一个字符串,您首先将其转换为后缀他提到,在实时的情况下,最好在解析R.E时绘制NFA,但是没有给出这样的方法。。。。。
我开始这件事有困难有谁能告诉我在解析字符串时应该使用什么样的算法来创建nfa,因为括号是一个大问题,因为它们应该先完成……
注:我真的不知道这里面还应该放些什么标签……这也不是家庭作业
最佳答案
这是一页Python中的a combined parser, NFA builder, and NFA interpreter我希望我不会破坏你自己解决问题的乐趣——你可能更愿意在跟踪链接之前等待并继续黑客攻击。
这有点像Deinst的建议,但“向后看”。正如deinst所说,您可以让解析器为正则表达式的每个子表达式构建一个NFA,然后在运行时将它们连接起来例如,对于(a|b)*c
首先解析(a|b)*
以获取NFA#1,然后解析c
以获取NFA#2,然后关闭NFA#1的最终状态,将其更改为#2的开始状态等等这是传统的答案。
相反,我的代码首先创建了一个简单的NFA,只有一个接受状态,没有更多。然后它解析c
,扩展NFA:现在我们有一个NFA,它检查c
,然后接受接下来,它递归地解析(a|b)*
,仍然扩展NFA给定一个字符串re
和一个NFAk
,解析器的约定是解析该字符串以生成一个结果NFA,当k
匹配时,结果NFA最终出现在re
的开头这种方法避免了需要对部分nfa的位进行重击以将它们连接在一起。
关于regex - 在解析正则表达式的同时创建自动机,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/4462650/