java-Thompson构造算法及其对NFA的重构
我试图创建一个方法,它将获取一个字符串(一个有效的正则表达式)并输出一个相应的非确定性有限自动机。从我所做的研究来看,Thompson's algorithm在这里最适用,因为我将只处理kleene星、并集和括号符号,语言将仅为{a,b,e},e代表空转换
此外,我面临的一个大问题是如何处理正则表达式中的嵌套括号。请在这里输入
我的问题是关于在代码中表示这一点的最佳/最直接的方法。我需要将每个节点彼此区分开来,并跟踪从节点出来的转换以及这些转换的方向。我已经研究过如何使用有向图,但是它看起来好像你只能表示一个节点,以及该节点可以通向哪里,而忽略了将你带到那个新节点的过渡。如果您对这里的建筑有任何建议,我们将不胜感激。谢谢
# 1 楼答案
不知道这是否有帮助,但我用Python为my monograph实现了这一点。遗憾的是,文本是葡萄牙语的,但实现非常简单
事实上,它将表达式编译为一个假设机器的非确定性指令序列。例如,表达式a(b | c)+d将被编译为:
只有三种类型的指令(并且
MATCH
只出现在末尾)CONSUME x
消耗输入的下一个字符,如果它是x
MATCH!
自我描述