lexer - 构造非确定性有限自动机

Question

我做手写词法分析器。我需要绘制一个非确定性有限自动机，其中包含三个先前制作的有限自动机。我为飞机、云、跑道等关键字制作了它们。我需要帮助，如何为这三个自动机构建通用自动机。我需要一些例子如何做到这一点？如果你知道请帮帮我？？

Answer 1

画出飞机、云和跑道自动机，在开始状态之前留出一些空间。现在，删除他们的第一个状态。在他们面前画一个新的、单一的状态。将其连接到具有“a”过渡/边缘、“r”边缘到“unway”以及“c”边缘到“loud”的“irplane”自动机。而已。完毕。

对于更一般的情况，它更复杂：首先，画出你的每个自动机（例如飞机、云和跑道），在它们开始的地方留下一些空白空间。接下来，在它们开始之前绘制一个状态，并通过自由边将其连接到飞机、云和跑道自动机的旧开始状态的开始。（自由边也称为 ε 边、ε 边、λ 边或 lambda 边）。

接下来，您对它们执行子集构造算法，您可以在 youtube 上找到视频教程。还有一个在线子集构造算法工具，可为您将非确定性有限自动机转换为确定性有限自动机 (DFA)。该过程称为确定性。

拥有 DFA 后，您可以使用它来构建驱动扫描仪的状态、操作和查找表。那是它自己的蠕虫罐头。人们通常使用 Lex 或 Flex 之类的扫描仪生成器来实现自动化。您可以在线使用的类似的、用户友好的工具是Online Scanner Generator。您可以通过提供以下输入来使用它来制作图表：

airplane:airplane
cloud:cloud
runway:runway

它会给你一个 DFA，就像这样：