从解析树到NFA

Question

我正在寻找将正则表达式转换为NFA。我知道我们需要将正则表达式转换为解析树，然后将其转换为NFA。我正在使用java脚本。有js工具直接从给定的正则表达式生成解析树吗？

另外，我对解析树到NFA部分的转换感到困惑。

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 (连接2个正则表达式)：

开始状态成为R1的开始状态，在R1的接受状态和R2的开始状态之间添加epsilon转换，从R1中删除接受状态。在图中，第二种状态是接受的，但不应该接受。

R= R1 U R2 (2个正则表达式的联合)：

对于R1和R2，带有epsilon转换到NFAs的启动状态--机器将“猜测”如果可能的话要输入哪一个。在图中，R1和R2用R和S表示。

R= R1* (R1的Kleene闭包)：

添加一个epsilon转换，这样R1就可以永远循环！

现在我们有了所有初始可能性的公式，它们可以合并成一个大的NFA。例如，对于(A )∘C*

1. 为U建立NFA 'x‘。
2. 为C*构建NFA 'y‘。
3. 构建NFA x∘y
4. 你完蛋了！

可以证明，任何NFA都可以像这样归纳地构造，并且我提供的所有初始结构都是正确的。嗯。

遗憾的是，我不太熟悉任何js工具，这些工具可以满足您的要求，但是对于上面的信息，如果您使用一些合理的表示形式存储基本案例，代码应该相当简单。

要获得更彻底和更少睡眠不足的解释，请在深入研究编码之前，尝试一下http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser，您将真正理解汤普森的算法(我已经描述过)。这个网站看起来比我在这里更深入地了解了实现。

祝好运!