我正在寻找将正则表达式转换为 NFA 的方法。我知道我们需要将正则表达式转换为解析树，然后将其转换为 NFA。我正在使用 java 脚本。有没有js工具可以直接根据给定的正则表达式生成解析树？
此外，我对解析树到 NFA 部分的转换感到困惑。
最佳答案
为什么要构建一个解析树呢？将正则表达式直接转换为 NFA 相对简单。
基本案例的数量是有限的。知道了这些，我们就可以从这些案例的某种组合中构建完整的 NFA。  考虑可以构建某些正则表达式 R 的所有可能方式。
前三个很简单，但并集、串联和 Kleene 闭包需要一点思考。
我在这里找到了最后 3 张相当不错的照片: http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser/Thompson.jpg
R = Ø(什么都不接受):
将平凡地成为不接受状态的路径。 (令 O 为非接受状态，X 为接受状态。)
(->O)
R = ϵ(接受空字符串):
通往接受状态的路径。
(->X)
R = a(接受字符串 'a'):
一个起始状态，在字符串 'a' 上有一条通往接受状态的路径。
(->O-a>X)
R = R1 ∘ R2(2 个正则表达式的串联):
起始状态成为 R1 的起始状态，在 R1 的接受状态和 R2 的起始状态之间添加了 epsilon 转换，R1 的接受状态被移除。图中第二种状态是accepting但不应该。
R = R1 U R2(2 个正则表达式的并集):
R1 和 R2 的 epsilon 转换到 NFA 的起始状态——如果可能，机器将“猜测”进入哪个状态。图中R1和R2分别用R和S表示。
R = R1*(R1 的 Kleene 闭包):
添加一个 epsilon 转换，使 R1 可以永远循环!
现在我们有了所有初始可能性的公式，可以将它们组合成一个大型 NFA。例如，对于 (A U B) ∘ C*
- 为 A U B 构建 NFA“x”。
- 为 C* 构建 NFA“y”。
- 构建 NFA x ∘ y
- 大功告成!
可以证明任何 NFA 都可以像这样归纳构造，并且我提供的所有初始构造都是正确的。嗯。
遗憾的是，我不熟悉任何可以满足您要求的 js 工具，但根据上述信息，如果您使用某种合理的表示形式存储基本案例，代码应该相当简单。
要获得更彻底、更少 sleep 不足的解释，请尝试 http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser 在深入研究编码之前，您需要真正理解 Thompson 的算法(我所描述的)。该网站看起来比我在这里更深入地了解实现。
祝你好运!
关于javascript - 从解析树到 NFA，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17377913/