编译原理：词法分析
01 词法分析程序的构造
词法分析程序自动构造的典型过程：
-
使用者用正规表达式作为词法规则的形式描述，每一类词法单元都对应一个正规表达式，所有正规表达式以文本方式作为自动构造工具的输入； -
自动构造工具将每一个正规表达式转换成有限自动机的形式，比如使用 Thompson 构造法将正规表达式转换成 -NFA； -
（可选）增加一个新的开始状态，从该状态引一条 -转移边到上述每一个 -NFA 的初态，得到一个新的 -NFA； -
必要时自动构造工具会将这些 -NFA 确定化，比如使用子集构造法得到 DFA； -
必要时，自动构造工具会将有限自动机最小化，得到等价拥有状态数目最少的 DFA； -
若执行过第3步，那么就模拟单个完整的自动机；否则，自动构造工具按照一定的控制策略生成词法分析程序中扫描程序的代码，该扫描程序可以选择对每一类词法单元所对应的有限自动机依次模拟运行，并从当前输入符号序列中识别下一个单词，然后返回相应的单词记录。
上述过程中涉及到的正则表达式 RE、有限自动机 FA、文法 G 之间的转换，以及 NFA 的确定化和 FA 的最小化，是本章学习的重点。
02 正则文法和状态转换图
学习重点：
由文法构造状态转换图 由状态转化图得到文法
2.1 右线性文法
设 是一右线性文法，按以下规则构造其状态转换图：
-
对于 中的产生式 ，，，从节点 引一条有向边到节点 ，并用 标记这条边； -
对于 中的产生式 ，，，从节点 引一条有向边到终态 ，并用 标记这条边； -
对于 中的产生式 （如果有的话），，则将节点 设为状态；
-
例题：构造下列产生式的状态转换图：
转换图如下：
2.2 左线性文法
至于左线性文法，其实可以看作是倒过来的右线性文法。设 是一左线性文法，则将开始符 当作终态，另外再引入一个新节点 ， 作为初态，按以下规则构造其状态转换图：
-
对于 中的产生式 ，，，从初态节点 引一条有向边到节点 ，并用 标记这条边； -
对于 中的产生式 ，，，从节点 引一条有向边到节点 ，并用 标记这条边；
-
例题：构造下列产生式的状态转换图：
转换图如下：
2.3 句子识别
如何使用状态转换图来识别一个句子？这里以句子 00011 为例，文法及状态转换图采用上题示例，识别的步骤可以用表格呈现：
| 步骤 | 当前状态 | 余留的符号串 |
|---|---|---|
| 1 | R | 00011 |
| 2 | U | 0011 |
| 3 | U | 011 |
| 4 | U | 11 |
| 5 | S | 1 |
| 6 | S | (识别结束) |
状态转换图到文法的转换过程就是文法到状态转换图的逆过程，了解后者规则之后前者就迎刃而解，故不在此赘述。
03 有限自动机
学习重点：
自动机的概念 NFA 的确定化 具有 ε 动作的 NFA 的确定化 DFA 的最小化
状态转换图是有限自动机 FA 的图形表示，FA 是状态转换图的形式描述。FA 是一个转换函数，根据当前状态和输入，将当前状态映射到另一个状态去。
3.1 DFA 和 NFA
将有限个状态之集记作 ，有限个输入符号组成的字母表记作 ，我们用转换函数 表示若当前状态为 ，输入符号为 ，则进入下一个状态 。这就是 确定的有限自动机 DFA 的定义，其特征是对于一组特定的 和 ，对应的下一状态也是唯一确定的。
相应地，非确定的有限自动机 NFA 就是指对于一组特定的 和 ，对应的下一状态并不唯一，可以有多种选择，所以其对于的定义为 ，其中， 是 的子集。
3.2 NFA 的确定化
定理：对于字母表 上的任一 NFA ，必定存在与 等价的 DFA 。
NFA 的确定化的步骤为：
-
从初态开始，列出状态转换表，将初态接受了 中的各字符之后得到的下一状态写成一个集合记录在表中； -
将得到的各集合看作是新的状态输入，对于每一个集合，并将集合中的状态一个一个取出，将其输入了 中各字符后得到的结果写成新集合，记录在表中； -
重复第二步，直到不再有新状态产生，并将包含了终态的集合看作是新的终态。
-
例题：将下面的 NFA 转换为 DFA：
列出状态转换表：
| 当前状态 | 输入 a | 输入 b |
|---|---|---|
| S | {A,C} | ∅ |
| {A,C} | {A,C} | {A,B} |
| {A,B} | {A,C} | {A,B,C} |
| {A,B,C} | {A,C} | {A,B,C} |
在上表中，我们将状态集 {A,C}，{A,B}，{A,B,C} 看作是新状态，重新代入状态转换图得到下一时刻的状态集，并循环这个过程知道不再有新的状态集产生为止。最后，我们将状态 {A,C}，{A,B}，{A,B,C} 分别取名为 D，E，F，并且，由于状态 D 和 F 中包含了终态 C，所以 D 和 F 也是终态。画出确定化后的状态转换图为：
3.2 ε 闭包
首先来认识一下 具有 动作的 FA ：如果一个 FA 中允许对输入符号 也作状态转移 (即矢线上有 )，则这样的 FA 称为具有 动作的 FA。具有 动作的 FA 的特点是，它对要识别的字符串没有影响，但是状态却发生了改变。
具有 动作的 FA 可形式化地定义为 。
我们将由状态 经过有限数量的 矢线所能到达的所有状态 (包括 自己) 组成的集合称为状态 的 闭包，记作 。引入 闭包的目的是为了将 拓展到 ，即 ，其中 是路径上经过的字符所组成的字符串。 和 的区别在于， 指明了要接受的字符 (不包括 )，而 则指明了要接受的字符串，而字符串是可以包含 的。
可以从下面这个性质理解 和 的区别：
是指，在当前状态为 ，输入字符为 的情况下的下一个状态； 则是状态 经过若干 矢线所能达到的其他状态，由于也包括了自己，所以 ；要注意的是， 中的 是一个字符串，这意味着其等价于 ，也就意味着在走过 矢线之前，它还可以走若干个 矢线，所以它包含了 和 。
之所以要研究 ，是因为借助 矢线，我们可以将识别不同单词的 FA 连在一起，最后再确定化为一个 DFA，构造更加复杂的 FA，由此可以设计编译程序的词法分析器。
3.3 具有 ε 动作的 NFA 的确定化
具有 当作的 NFA 的确定化要把输入的单个字符当作字符串处理，即要把 也考虑在内，并且一开始就要将所有状态都当作一个新状态考虑。
为了形式化的描述这一过程，定义：。这个函数乍一看可能难以理解，但是仔细分析一下，其功能其实是很显而易见的。 的含义是，当前状态为 ，通过输入若干 ，最后输入 所能到达的所有状态的集合，到此为止它只讨论了 ，如果在外面再套一个 的话，就是指在输入了 之后，继续输入若干个 所能到达的所有状态，也就是输入字符串为 ，所能到达的所有状态。
具有 ε 动作的 NFA 的确定化步骤如下：
-
将 定义为 ，将 在接受了 中的各字符之后，通过映射 所得的状态集 记录在表中； -
将得到的各状态集看作是新的状态 输入，对于每一个集合，并将集合中的状态一个一个取出，将其输入了 中各字符后通过映射 所得的状态集 记录在表中； -
重复第二步，直到不再有新状态产生，并将包含了终态的集合看作是新的终态。
-
例题：将下面具有 动作的 NFA 确定化：
首先计算 ；接下来计算 ，根据上面的描述，我们要算的其实就是 中的状态经过路径 所能到达的全部状态，观察后得到结果 ；接下来计算 ，其实就是 中的状态经过路径 所能到达的全部状态，观察后得到结果 ，这是一个新的状态集，令它为 ；接下来计算 ，观察后得到结果 ，这是一个新的状态集，令它为 。于是得到第一排的状态转换表：
| a | b | c | |
|---|---|---|---|
| q0：{0,1,2,3} | {0,1,2,3} | {1,3} | {2,3} |
接下来则是重复上述过程，对 和 进行讨论，直到不再有新状态集产生，列出完整的状态转换表为：
| a | b | c | |
|---|---|---|---|
| q0：{0,1,2,3} | {0,1,2,3} | {1,3} | {2,3} |
| q1：{1,3} | ∅ | {1,3} | ∅ |
| q2：{2,3} | ∅ | ∅ | {2,3} |
同样，凡是包含了终态的状态集成为新的终态，故该 DFA 中所有状态均为终态，画出状态转换图：
3.4 DFA 的最小化
对于一 DFA 来说，其状态数可能并不是最小的，原因是DFA中有些状态是“等价”的，为得到效率高的 DFA，需将这些“等价”状态合并，这就是 DFA 的最小化。
如果存在一个或多个字符 ，使得状态 和 满足 ，则说明 和 可区分，即不是等价的；反之，如果 ，存在 ，则说 和 不可区分，即等价。
设某 DFA 的状态集和终态集为 和 ，显然， 和 可以被 区分，最小化算法的起点也就是这里。最小化的步骤是：
-
将 DFA 的状态集 划分为终态集和非终态集； -
对每一个子集中的状态进行检测，观察它们在接受了字符 后转换得到的下一状态是否属于当前集合，如果不属于，说明该状态与该集合的其他状态可区分，所以将该状态划分出去单独组成集合； -
重复步骤二，直到不再有新集合产生。
-
例题：将下图的 DFA 最小化：
划分状态集得 ，对于子集 ，将字符 输入，发现都进入状态 ，未区分；将字符 输入，发现 分别进入状态 ，这三个状态全部属于当前集合，而状态 接受字符 之后进入状态 ，不属于当前集合，所以状态 与其余状态可区分，将状态 单独列为一个集合，得到 。
接下来继续对 进行检测，发现 ，状态 属于当前集合，未区分；，状态 属于当前集合，而 ，状态 不属于当前集合，所以将状态 单独列为一个集合，得到 。
继续对 进行检测，发现 ，，不可区分 (为什么不可区分：虽然状态 不属于当前集合，但是由于集合中只剩下了状态 和 ，即使把 和 拿出去建立一个集合也仍然等同于现在的集合，故没必要继续区分)，不再有新集合产生，结束。
所以最终 ，状态 和状态 等价，保留其中一个即可，得到最小化后的状态转换图：
04 正则表达式与正规集
学习重点：
正规文法和正规式的转换 正规式和自动机的转换
正则表达式也称正规式。正规集就是正则表达式所表达的语言，或者说句子的集合。例如正则表达式为 ，则其对应的正规集为 。
正则表达式中的运算符 (顺序按优先级从高到低)：。 代表闭包； 代表连接，一般省略不写； 代表或。
正则表达式有几条公理，过滤掉显而易见的，有这么几条值得关注一下 (了解即可)：
4.1 正规文法 → 正规式
由正规文法求正规式的过程形如解方程，有求根公式，下面以两道例题说明：
-
例题：将下面的正规文法转换成正规式：
将 视作 ，将上面两个产生式改写成方程组得：
将 ② 式代入 ① 式得 ③ 式 。
论断：当方程形如 ，有解 。于是有 。
-
上面展示的例子是右线性文法，下面来看一个左线性文法的例子：
将 视作 ，将上面三个产生式改写成方程组得：
将 ③ 式代入 ② 式得 ④ 式 ，注意不能直接将 ④ 式代入 ① 式，否则你会发现 还未求解。遂先求解 ，发现 ④ 式形如 ，不满足上述论断的形式，解的公式需要变化一下，为 ，故有 。
将 代入 ① 式得 ，将 变为 得到该文法的正则表达式为 。
4.2 正规式 → 正规文法
将正规式转换为正规文法遵循以下三条规则：
-
若正规式形如 ：令 ， -
若正规式形如 ：令 ，；若正规式形如 ：令 ， -
若正规式形如 ：令 ，
不断利用上述规则，直到每个产生式最多含有一个非终结符为止。
-
例题：将正规式 转换为正规文法 (该题原型来自课本 P64 第 1 大题第 1 小题)。
解：
-
令 ，令 ，则有 ； -
利用规则 2，令 ，，则有 ； -
每个产生式右部的非终结符最多只有一个，结束。
故该正规式对应的正规文法为：
转换的过程中不要忘记正规文法的规则，要么化成右线性文法，要么化成左线性文法。
4.3 正规式 → FA
虽然我们可以先将正规式化为正规文法，再由文法得到 FA，但这样显然效率太低。而由一个正规式直接构造 DFA 是很困难的，所以我们一般选择先由正规式转换为 NFA，再由 NFA 转换到 DFA。
正规式到 NFA 的转换遵循下面六条规则 (这里状态转换图的形式和上面稍微有点不一样，画的时候改了，看得懂就行)：
1.
2.
3.
4.
5.
6.
-
例题：将 转换为 NFA。
首先画出初始状态转换图：
可以看到该正规式的后半部分是好分解的，利用规则 1 可得：
至于前半部分，我们可以看作是 ，其中 ，遂可利用规则 3 进行分解：
剩下的 可以利用规则 2 分解，得到最终的 NFA：
4.4 FA → 正规式
从 FA 转换为正规式的核心思想是消去除了初态和终态之外的中间状态，根据自动机的初态和终态是否为同一个，最终可能得到下面两种形式的自动机：
左图对应的正则表达式的形式为 ；右图对应的正则表达式为 。
如果一个自动机中有多个终态，则要对每个终态分开求解，即将除某个终态以为的全部状态都看作中间状态 (如果存在终态只能由该终态转换得到，则舍弃前者)，最后将每个终态对应的正则表达式用 连接起来即可。
-
例题：将下面的自动机转换为对应的正规式。
解：
首先，先求解终态 对应的正规式，将另一个终态 看作普通的中间状态，先将上图中的 都化为 ：
后三个状态可以进行合并，变成：
至此，整个自动机中除了初态 和终态 再无其它终态，遂结束。所以终态 对应的正规表达式为 。
接下来求终态 对应的正规式，由于终态 只能由终态 转换得到，遂舍弃终态 ：
合并后面的两项：
至此，整个自动机中除了初态 和终态 再无其它终态，遂结束。所以终态 对应的正规表达式为 。
将终态 和终态 对应的正规式合并，得到整个自动机的正规式为 。
4.5 正规式 → ε-NFA
从正规式转换为 可以采用 Thompson 构造法，其核心为以下三条规则：
1. 对于 ：
2. 对于 ：
3. 对于 ：
一般方法可概括为：将正规式分解为最小单位，为每个最小单位构造自动机，最后按照上面三条规则，将构造的所有自动机用 矢线连接起来。
-
例题：设正规表达式为 ，构造等价的 。
可将其拆分为两部分：，。首先构造 的自动机：
然后构造 的自动机：
最后连接起来：
发表评论