3 自动机理论和词法分析器生成器

在上次课中已经能够根据模拟状态转换图完成一个词法分析器，因此解决如何将写好的正则表达式转换成状态转换图，即可完成一个自动的词法分析器生成器

本节课讲的是有限状态机，表达能力比较弱，但对于表达词法单元的规约是足够的

NFA(非确定有限状态自动机) 自动机容易理解但不容易模拟，因此将 NFA 转换成 DFA，DFA 就很好模拟了，上次课的内容就是模拟 DFA(确定有限状态自动机)

根据图的环形，DFA、NFA、RE 的表达能力是相同的，因为可以相互转化

NFA

非确定性：

1. 对于相同的字符，行为可能是不确定的，比如上面的 a，可能仍在 0 状态，也可能转换到 1 状态

2. 对于不在字母表中的字符 ε【如空字符】，也能使状态发生改变

其中 3 为接受状态

一个正则表达式和一个自动机定义的语言是相同的，那么就说这两者等价

对于 aabb 最终可以是处于 0 状态或者是 3 状态，因为可以到达 3 即终止状态，因此可以接受

注意如 1 状态没有 a 的出边则说明 1 不能接受 a 字符，根据上面的约定，即默认指向一个空状态。因此 ababab 是不能最终到 3 状态的，因此不可接受

更多的例子：

DFA

相比于 NFA，消除了不确定性的两个因素

DFA 要求在每个状态上，对于 Σ 中的每一个字符都要有下一个转移状态

但在实际画的时候，如果不画转移，那么默认转移到死状态【相当于把需要画出的很多个转移到死状态的边给省略了】

死状态是指不论什么字符，都始终在死状态，不会转移走

• 这个 DFA 描述的语言和上面 NFA 中的一样，但显然可以看出对于 DFA 想要写出它要描述的语言更难。

• 但 DFA 的好处是，给定一个字符串，可以很容易的判断是不是符合的字符串

RE 到 NFA Thompson 构造法

从 RE 到 NFA: Thompson 构造法

即按照上面对正则表达式结构的定义来归纳将正则表达式转换成 NFA

归纳

加个括号不影响语言，因此直接等价

对 s 和 t 加一个初始状态并用 ε 转移到 s 和 t的初始状态；同样的，增加终止状态，用 ε 从 s 和 t 的终止状态转移到这个终止状态

将 s 的终止状态作为 t 的初始状态

底下的 ε 表示 s 可以是 0 个；上面的 ε 表示 s 可以任意多个

复杂度

3 表示构造出的 NFA 不会太复杂，最多只是原来正则表达式复杂度的两倍（因为上面的构造中最多就是添加一个初始状态和一个终止状态）

构造的例子

完成按照上面的构造方式就能成功构造出

NFA 到 DFA 子集构造法

思想：用 DFA 来模拟 NFA

模拟就需要模拟 NFA 的所有状态和状态转移

• 上面 NFA 中的 0、1、2、4、7 都是可以通过 ε 来转移的，因此它们都是 DFA 中的初始状态

• 因为是 DFA，因此要考虑所有的输入字符即 a 和 b，对于初始状态：

  • 输入字符 a，可以转移到 3、8，而对于 3，又可以通过 ε 转移到 6、7，6 又可以通过 ε 转移到 1，进而通过 1 到 2、4，因此第二个状态包含 3、8、6、7、1、4、2
  • 同理，输入字符 b 可以到 5、4、7、1、2、4

• 一直下去，需要注意转移得到的状态是不是和已经有的状态子集相同，如果相同，则这个转移是回到自己

• 如果构造的状态子集中包含至少一个 NFA 的终止状态，那么它就是 DFA 的终止状态

公式化子集构造法

• ε 闭包也包含 s 自身，因为公式中的 ε 是 *，可以是 0 个 ε 转移

• move 是指，当前的 DFA 状态集合为 T，当看到 a 字符时，DFA 可以到达哪些状态【其实就是上面的不断找状态子集的过程】

公式化上面的构造过程

最坏情况下复杂度是指数级别的：如下例子，得到的 DFA 非常复杂

DFA 最小化

通过子集构造法得到的 DFA 不一定是最简的，如下图上面的 DFA 的状态数就比用子集构造法得到的更少

DFA 最小化算法基本思想: 等价的状态可以合并

如下反例：

采取相反的策略，先假设全部都等价，再根据不等价定义【转移的状态都不同，那肯定是不等价的】进行不等价的分裂：注意下面的不等价定义是存在 a，因此需要把每一个字母表中的都试一下，找到或者试完为止

• 先把 E 从其他状态中分裂出来，E 所在的集合只有 E 一个，因此不用再分裂，接下来对剩余状态进一步分裂

• D 通过 b 会到 E，而 ABC 通过 b 都还是到 ABCD 这个等价类，因此分裂出 D

• 然后分裂出 B

• 对于 A、C，不能分裂出来，因此 AC 就等价了，此时达到了不动点，不能再继续分裂了

合并后一定是 DFA，否则就说明分裂不完全，还需要继续分裂

合并后的初始状态是合并后包含初始状态的等价类，接受状态同理

DFA 到 词法分析器

下面展示了从 RE => NFA => DFA => 词法分析器

**注意：**如果在 DFA 中的接受状态包含 NFA 中的多个接受状态，如上面的 68，都要确定到底是要接受其中的哪个，因为我们需要最前优先匹配，所以 68 这个状态应该接受 abb

**注意：**其中 68 对于输入 a 没有状态转移，默认是转移到一个死状态的，如果加上了死状态，那么在 68 接受到 a 时就会进入死状态，并且永远停留在死状态，这是不合理的，所以要消除死状态，让状态机在 68 接收到 a 时就停止

上面的模拟过程就是手写词法分析器中的要考虑的步骤。报错会忽略第 1 个字符，从第 2 个字符开始重新识别

例子：

对于 DFA 最小化，根据之前 DFA 最小化的方法，我们把 0137 和 7 作为一类，其他 4 个终止状态为一类。

但如果这个 DFA 是用于生成词法分析器的，那么在一开始的时候不能把所有的终止状态分为一类，因为它们识别的是不同的词法单元。如下的 Π₀。其中的空就是死状态，因为在之前已经提到，要保证这是一个 DFA，所以需要补齐没有转移的线条。

最小化的结果是 Π₁，和原来一样，即原图就是一个最小化的 DFA 了。

DFA 到 RE

对于 DFA 要找到与之等价的 RE，它们表达的是一个语言

所有的路径的集合，就是这个语言，因此正则就是所有的路径的或

使用 floyed 算法找到所有的路径

上面的箭头上的是转移条件

过程：

只需要选择我们要的，即从初始状态到接受状态的结果，上面就是 R²₀₁