从正则表达式创建NFA的步骤

Question

从正则表达式创建NFA时,我遇到了"描述每个步骤"的问题.问题如下:

将以下正则表达式转换为非确定性有限状态自动机(NFA),清楚地描述您使用的算法的步骤:(b | a)*b(a | b)

我已经制作了一个简单的三态机器,但它非常直观.这是我的讲师在过去的考试中提出的一个问题,他也写了Thompson算法的以下解释:http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

任何人都可以清楚如何"清楚地描述每一步"吗？它看起来像是一组基本规则,而不是一个遵循步骤的算法.

也许我已经在某个地方掩饰了一个算法,但到目前为止,我只是用一个有根据的猜测创建了它们.

Answer 1

一般方法的简短版本.
有一个算法称为Thompson-McNaughton-Yamada构造算法,有时只是"Thompson Construction".一个构建中间NFA,沿着路径填充碎片,同时尊重运算符优先级:第一个括号,然后是Kleene Star(例如,a*),然后是连接(例如,ab),然后是交替(例如,a | b).

这是构建(b | a)*b(a | b)的NFA的深入演练

建立顶级

1. 处理括号.注意:在实际实现中,通过对其内容的递归调用来处理括号是有意义的.为了清楚起见,我将推迟对parens内部任何内容的评估.

2. Kleene Stars:那里只有一个*,所以我们建立一个名为P的占位符Kleene Star机器(后来将包含b | a).中间结果:
   

3. 连接:将P附加到b,并将b附加到名为Q的占位符机器(将包含(a | b).中间结果:
   

4. 括号外没有替换,所以我们跳过它.

现在我们坐在P*bQ机器上.(注意,我们的占位符P和Q只是连接机器.)我们用BFA替换P边缘用于b | a,并通过递归应用上述步骤将Q边缘替换为NFA用于a | b.

建筑P.

1. 跳跃.没有parens.

2. 跳跃.没有Kleene明星.

3. 跳跃.没有连接.

4. 为b | a构建交替机器.中间结果:
   

整合P.

接下来,我们回到那个P*bQ机器,我们撕下P边缘.我们将P边缘的源作为P机器的起始状态,P边缘的目的地作为P机器的目标状态.我们也使该州拒绝(剥夺其作为接受国的财产).结果如下:

建设Q.

1. 跳跃.没有parens.

2. 跳跃.没有Kleene明星.

3. 跳跃.没有连接.

4. 为a | b构建交替机器.顺便说一下,交替是可交换的,因此a | b在逻辑上等价于b | a.(阅读:从懒惰中跳过这个小脚注图.)

整合Q.

除了用我们构造的中间体b |机器替换Q边缘之外,我们用上面的P做了.这是结果:

田田!呃,我的意思是,QED.

想知道更多？

上面的所有图像都是使用在线工具生成的,用于自动将正则表达式转换为非确定性有限自动机.您可以在线找到Thompson-McNaughton-Yamada Construction算法的源代码.

该算法也在Aho的编译器:原理,技术和工具中得到解决,尽管其解释在实现细节上很少.您还可以通过优秀的Russ Cox 从C中的Thompson Construction实现中学习,他在一篇关于正则表达式匹配的热门文章中对其进行了详细描述.