从语法树到NFA

Question

我希望将正则表达式转换为NFA。 我知道我们需要将正则表达式转换为解析树，然后再将其转换为NFA。 我正在使用JavaScript。 是否有任何JS工具可以直接从给定的正则表达式生成解析树？

同时，我对将解析树转换为NFA部分感到困惑。

- user567879

---

这些文章可能对您有所帮助：http://swtch.com/~rsc/regexp/。 - Martin Ender

我没有完全理解你的问题：也许正则表达式转DFA可以帮助你。 - Grijesh Chauhan

Answer 1

为什么要构建解析树？将正则表达式直接转换为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（两个正则表达式的连接）：

起始状态成为R1的起始状态，在R1的接受状态和R2的起始状态之间添加epsilon转移，删除R1的接受状态。在图中，第二个状态是接受状态，但实际上不应该是。

R = R1 U R2（两个正则表达式的并）：起始状态有一个epsilon转移到R1和R2的NFA——如果可能，该机器将“猜测”进入哪一个来被接受。在图中，R1和R2由R和S代表。

R = R1*（R1的Kleene闭包）：添加一个epsilon转移，使R1可以永远循环！

现在我们已经为所有初始可能性制定了公式，它们可以组合成一个大的NFA。例如，对于（A U B）∘ C*，

1. 为A U B建立NFA“x”。 2. 为C*建立NFA“y”。 3. 构建x ∘ y的NFA 4. 完成！

可以证明，任何NFA都可以像这样归纳地构建，并且我提供的所有初始构造都是正确的。遗憾的是，我不熟悉任何js工具可以完成您要求的操作，但是有了上面的信息，如果使用一些合理的表示存储基本情况，代码应该相当简单。

如果您需要更详细的解释并且不想失眠，可以尝试访问http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser。在编码之前，您需要真正理解 Thompson 算法（我所描述的内容）。该网站似乎比我在这里提供的更深入地介绍了实现细节。

祝你好运！

- vroomfondel