java-Thompson构造算法及其对NFA的重构

1 年 Questions & Answers 2749

我试图创建一个方法，它将获取一个字符串（一个有效的正则表达式）并输出一个相应的非确定性有限自动机。从我所做的研究来看，Thompson's algorithm在这里最适用，因为我将只处理kleene星、并集和括号符号，语言将仅为{a，b，e}，e代表空转换

此外，我面临的一个大问题是如何处理正则表达式中的嵌套括号。请在这里输入

我的问题是关于在代码中表示这一点的最佳/最直接的方法。我需要将每个节点彼此区分开来，并跟踪从节点出来的转换以及这些转换的方向。我已经研究过如何使用有向图，但是它看起来好像你只能表示一个节点，以及该节点可以通向哪里，而忽略了将你带到那个新节点的过渡。如果您对这里的建筑有任何建议，我们将不胜感激。谢谢

不知道这是否有帮助，但我用Python为my monograph实现了这一点。遗憾的是，文本是葡萄牙语的，但实现非常简单

事实上，它将表达式编译为一个假设机器的非确定性指令序列。例如，表达式a（b | c）+d将被编译为：

 0000: CONSUME a
 0001: JUMP (1, 3)
 0002: CONSUME b
 0003: JUMP (2,)
 0004: CONSUME c
 0005: JUMP (1, -4)
 0006: CONSUME d
 0007: MATCH!

只有三种类型的指令（并且MATCH只出现在末尾）

Python中文网