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

从正则表达式创建NFA时，我遇到了“描述每一步”的问题。问题如下：

将以下正则表达式转换为非确定性有限状态自动机(NFA)，清楚地描述了您使用的算法的步骤：
(B | A)* B(A | B)@H_301_3@

我已经做了一个简单的3状态机，但它非常直观。
这是我的讲师撰写的过去考试的一个问题，他也写了Thompson算法的以下说明：http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html@H_301_3@

有谁能清楚如何“明确描述每一步”？它只是一个基本规则，而不是一个跟随步骤的算法。@H_301_3@

也许有一个算法我已经在某个地方，但到目前为止，我刚刚创造了他们与一个有教养的猜测。@H_301_3@

一般方法的简短版本。
有一个算法叫做汤普森麦克纳顿山田建设算法，有时只是“汤普森建筑”。一个构建中间的NFAs，沿着路径填充这些片段，同时尊重运算符优先级：第一个括号，然后是Kleene Star(例如a *)，然后连接(例如，ab)，随后交替(例如a | b)。

这是一个深入的演练(b | a)* b(a | b)的NFA@H_301_3@

建设顶级@H_301_3@

>处理括号。注意：在实际实现中，通过对其内容的递归调用来处理括号是有意义的。为了清楚起见，我将推迟对括号内的任何内容的评估。
> Kleene明星：只有一个*在那里，所以我们建立一个名为P的占位符Kleene Star机器(稍后将包含b | a)。
中间结果：@H_301_3@

>连接：将P附加到b，并将b附加到名为Q的占位符机器(将包含(a | b))中间结果：@H_301_3@

>括号外没有任何交替，所以我们跳过它。@H_301_3@

现在我们坐在一台P * bQ机上。 (请注意，我们的占位符P和Q只是级联机器。)我们将P边缘替换为b | a的NFA，并通过上述步骤的递归应用将Q边与NFA替换为| b。@H_301_3@

建筑P@H_301_3@

>跳过。没有括号。
>跳过。没有克莱恩星。
>跳过。没有混合。
>为b | a构建交替机器。中级成绩：@H_301_3@

整合P@H_301_3@

接下来，我们回到那个P * bQ机器，我们撕掉了P边。我们将P边缘的源作为P机的起始状态，P边的目的地作为P机的目的地状态。我们也使国家拒绝(剥夺其成为接受国家的财产)。结果如下：@H_301_3@

建设Q@H_301_3@

>跳过。没有括号。
>跳过。没有克莱恩星。
>跳过。没有混合。
>构建一个| b的交替机器。顺便说一下，交替是可交换的，所以a |在逻辑上等同于b | a。 (阅读：从懒惰中跳过这个小脚注图)@H_301_3@

整合Q@H_301_3@

我们用P做的，除了用我们构建的机器代替Q边。这是结果：@H_301_3@

田田！呃，我的意思是QED。@H_301_3@

该算法在Aho’s Compilers: Principles,Techniques,and Tools中也得到了解决，尽管其解释在实现细节上很少。你也可以从an implementation of the Thompson Construction in C的优秀的Russ Cox学习，他在一篇关于regular expression matching的热门文章中描述了一些细节。@H_301_3@

原文链接：https://www.f2er.com/regex/357554.html

猜你在找的正则表达式相关文章