编译原理课程笔记

概论

编程语言的发展：

• 第一代 机器语言: 能够被计算机的硬件系统直接执行的指令程序, 如“0001000101”。
• 第二代 汇编语言: 将硬件指令用一些助记符表示, 即符号化的机器语言, 如“ADD, MOV”。
• 第三代 高级语言: 从程序员的角度出发, 对汇编语言进一步抽象, 使用便于理解的“自然语言”表述。

高级语言的实现

编译方式

将⾼级语⾔（源语⾔）翻译成低级语⾔（如汇编语⾔或机器语⾔）的⽬标程序的翻译⽅式。⼀次性将源程序翻译为⽬标程序，之后直接运⾏⽬标程序，⽆需重复翻译。

适⽤场景：程序需要频繁运⾏时，编译⽅式更⾼效，因为它省去了反复翻译的过程。

解释方式

逐⾏翻译并同时执⾏⾼级语⾔程序，翻译与执⾏同步完成。⽆需⽣成独⽴的⽬标程序，边翻译边运⾏。

适⽤场景：程序较简单且需要灵活修改时，例如 Excel 表格中的脚本，解释⽅式更具灵活性。

转换方式

将⼀种⾼级语⾔（A 语⾔）转换为另⼀种⾼级语⾔（B 语⾔），再利⽤ B 语⾔的编译器执⾏。不直接属于⾼级语⾔的实现⽅式，⽽是⼀种变通策略。

适⽤性：依赖已有编译器，适⽤于语⾔间转换的场景。

编译程序的组成

表处理和错误处理也可以算作编译程序的组成部分，但是主要还是中间的六个部分。

词法分析

词法分析器

词法分析器也叫 Scanner，输入是源程序的字符序列，输出是单词序列。它按顺序扫描源程序，识别出具有独立意义的单词，并检查词法错误。

词法分析的输出通常采用二元组形式：<单词类别, 单词内容>。例如：

• <保留字, void>
• <界限符, (>
• <保留字, int>
• <标识符, x1>
• <运算符, =>
• <常量, 0>

单词是具有独立含义的最小语义单位。常见单词类型包括保留字、标识符、常量、运算符、界限符、控制符。

实现词法分析器的基本步骤：

1. 明确要识别的单词类型和词法规则。
2. 使用形式化方法描述各类单词，主要工具是正则表达式和自动机。
3. 根据描述设计词法分析算法。

符号和符号串

字母表是元素的非空有穷集合，通常记为 $\Sigma$。字母表中的元素称为字母、符号或字符。

例如：

• $\Sigma={0,1,\dots,9}$
• $\Sigma={a,b,c,\dots,z,A,B,\dots,Z}$
• $\Sigma=\text{ASCII}$
• $\Sigma=\text{Unicode}$

符号串是由字母表中的符号组成的有穷序列，也称字符串或句子。常用 $\alpha,\beta,x,y,z$ 表示。

长度

符号串长度表示为 $|\beta|$。空串记为 $\varepsilon$，其长度为 $|\varepsilon|=0$。

连接

若 $\alpha$ 和 $\beta$ 都是 $\Sigma$ 上的符号串，则它们的连接记为 $\alpha\beta$。例如 $\alpha=abc$，$\beta=de$，则 $\alpha\beta=abcde$。

连接满足：

• $|\alpha\beta|=|\alpha|+|\beta|$
• $\varepsilon\alpha=\alpha\varepsilon=\alpha$

方幂

符号串的方幂表示重复连接。若 $x$ 是符号串，则：

• $x^0=\varepsilon$
• $x^1=x$
• $x^2=xx$
• $x^3=xxx$
• $x^n=x^{n-1}x=xx^{n-1}$

符号串集合是由某个字母表上的符号串组成的集合。若 $A$ 和 $B$ 是两个符号串集合，则它们的乘积定义为：

$$AB=\{xy\mid x\in A \land y\in B\}$$

例如 $A={a,bc}$，$B={de,f}$，则：

$$AB={ade,af,bcde,bcf}$$

---

符号串集合的方幂定义为：

• $A^0={\varepsilon}$
• $A^1=A$
• $A^2=AA$
• $A^n=A^{n-1}A$

若 $A=\{a,b\}$，则：

• $A^0={\varepsilon}$
• $A^1={a,b}$
• $A^2={aa,ab,ba,bb}$
• $A^3={aaa,aab,aba,abb,baa,bab,bba,bbb}$

正闭包表示一次或多次连接：

$$A^+=A^1\cup A^2\cup A^3\cup \dots$$

星闭包表示零次或多次连接：

$$A^*=A^0\cup A^1\cup A^2\cup A^3\cup \dots$$

也可写为：

$$A^*=\{\varepsilon\}\cup A^+$$

例如 letter 表示所有英文字母，则 $\text{letter}^+$ 表示所有非空英文字符串，$\text{letter}^*$ 表示包含空串在内的所有英文字符串。

正则表达式

正则表达式是描述正则集的一种代数表达式，也称正规表达式。它使用预先定义的符号和运算规则构造模式，用来描述一类字符串。

正则表达式 $r$ 所描述的符号串集合称为正则集或正规集，记为 $L(r)$，也称为由 $r$ 定义的语言。语言就是字母表上字符串的集合。

例如：

$$(1|2|\dots|9)(0|1|2|\dots|9)^*|0$$

这个表达式可描述十进制非负整数。

设 $\Sigma$ 为字母表，正则表达式递归定义如下：

1. $\varepsilon$ 和 $\varnothing$ 是 $\Sigma$ 上的正则表达式：

   $$L(\varepsilon)=\{\varepsilon\}, L(\varnothing)=\{\}$$

2. 对任意 $a\in\Sigma$，$a$ 是 $\Sigma$ 上的正则表达式：

   $$L(a)={a}$$

3. 若 $r$ 和 $s$ 是正则表达式，则以下表达式也是正则表达式：

   $$(r), r|s, r\cdot s, r^*$$

它们对应的语言为：

• $L((r))=L(r)$
• $L(r|s)=L(r)\cup L(s)$
• $L(r\cdot s)=L(r)L(s)$
• $L(r^*)=(L(r))^*$

正则表达式中的主要运算：

• 括号 ( )：确定运算优先级
• 或运算 |：表示多个模式的并集
• 连接运算 ·：表示前后相邻部分的组合，实际书写中常省略
• 闭包运算 *：表示零次或多次重复

实际应用中还常使用正闭包 +：

$$L(r^+)=(L(r))^+$$

运算优先级为：

$$( ) > * > \cdot > |$$

例如 ab* 表示先对 b 做闭包，再与 a 连接，即 $a(b^*)$。

正则表达式描述单词

正则表达式可用于化简和构造词法规则。

• 交换律：$A|B=B|A$

• 结合律：

  • $A|B|C=(A|B)|C=A|(B|C)$
  • $ABC=(AB)C=A(BC)$

• 分配律：

  • $A(B|C)=AB|AC$
  • $(A|B)C=AC|BC$

• 幂等律：

  • $A^{**}=A^*$

• 同一律：

  • $A\varepsilon=\varepsilon A=A$

例如在字母表 $\Sigma={a,b}$ 上：

ab* 表示所有以 a 开头，后面跟零个或多个 b 的字符串，即：

$$L(ab^*)={a,ab,abb,abbb,\dots}$$

a(a|b)* 表示所有以 a 开头，后面跟任意个 a 或 b 的字符串。

---

整数可用正则表达式描述。设：

$$D=0|1|2|\dots|9\\ D_1=1|2|\dots|9$$

则：

• $D^+$ 表示允许前导 0 的数字串
• $D_1D^*$ 表示无符号正整数
• $(+D_1D^*)|(-D_1D^*)|0$ 表示带符号整数和 0
• $(+|-|\varepsilon)(D_1D^*)|0$ 表示整数

---

词法分析中常见单词的正则描述：

保留字：

while|if|for|...

标识符：

$$L(L|D)^*$$

其中：

$$L=A|B|\dots|Z|a|b|\dots|z|\_\\ D=0|1|\dots|9$$

整数常量：

$$(+|-|\varepsilon)(D_1D^*)|0$$

其中：

$$D_1=1|2|\dots|9$$

实数常量：

$$(+|-|\varepsilon)(D_1D^*|0).D^+$$

特殊符号包括：

• 运算符：+|-|*|...
• 分界符：{|}|;|...
• 控制符：\t|\n|...

这几部分的核心关系是：词法分析器要识别源程序中的单词，符号串理论提供基本对象，正则表达式提供形式化描述，单词规则可用正则表达式精确表示。

正则表达式的局限性

注意事项

有大括号的是集合。正则表达式是用上面的运算得到的式子。

例题：设字母表 $\Sigma=\{0, 1\}$，求为 2 的倍数的二进制数字符串集合。

$(0|1)*$ 表示任意字串，那么答案应该是 $1(0|1)*0|0$。

---

例题：

1. 可以构造成 $(y|z)*(x(y∣z)∗x(y∣z)∗)∗$
2. 可以构造成 $(x∣z∣y(x∣z))∗(\varepsilon∣y)$

确定有限自动机 DFA

有限自动机 FA 是一种字符串识别装置，可以识别正规集。词法分析中引入 FA，是为了给词法分析程序的自动构造提供形式化工具。

有限自动机分为两类：

• 确定有限自动机 DFA：Deterministic Finite Automata
• 非确定有限自动机 NFA：Nondeterministic Finite Automata

---

DFA 定义为一个五元组：

$$M=(S,\Sigma,S_0,f,Z)$$

其中：

• $S$ 是有穷状态集，其中每个元素称为一个状态
• $\Sigma$ 是有穷字母表，其中每个元素称为输入字符
• $S_0\in S$ 是唯一初始状态，也称开始状态
• $f$ 是状态转换函数，$f:S\times\Sigma\to S$
• $Z\subseteq S$ 是终止状态集，也称可接受状态集或结束状态集

状态转换函数 $f(S_i,a)=S_k$ 表示：当前状态为 $S_i$，读入输入字符 a 时，自动机唯一转换到状态 $S_k$。$S_k$ 称为 $S_i$ 的一个后继状态。

例如：

$$M=({S_0,S_1,S_2,S_3},{a,b},f,S_0,{S_3})$$

其中转换函数为：

• $f(S_0,a)=S_1$
• $f(S_0,b)=S_2$
• $f(S_1,a)=S_3$
• $f(S_1,b)=S_2$
• $f(S_2,a)=S_1$
• $f(S_2,b)=S_3$
• $f(S_3,a)=S_3$
• $f(S_3,b)=S_3$

这个 DFA 的初始状态是 $S_0$，终止状态是 $S_3$，输入字母表是 ${a,b}$。

---

DFA 的表示方式

DFA 有两种常见表示方式。

第一种是状态转换图。状态转换图使用有向图表示自动机：

---

第二种是状态转换矩阵。矩阵中：

• 行表示状态
• 列表示输入字符
• 矩阵元素表示转换后的状态
• 初始状态常用 + 标记
• 终止状态常用 * 或 - 标记

以上面的 DFA 为例，状态转换矩阵为：

状态 \ $\Sigma$	$a$	$b$
$S_0+$	$S_1$	$S_2$
$S_1$	$S_3$	$S_2$
$S_2$	$S_1$	$S_3$
$S_3*$	$S_3$	$S_3$

陷阱状态

陷阱状态是自动机进入错误路径后的状态。进入陷阱状态后，后续任意输入通常都停留在陷阱状态中。

例如某 DFA 中：

• $f(0,a)=1$
• $f(0,b)=4$
• $f(1,a)=4$
• $f(1,b)=2$
• $f(2,a)=3$
• $f(2,b)=4$
• $f(3,a)=3$
• $f(3,b)=3$
• $f(4,a)=4$
• $f(4,b)=4$

其中状态 4 就是陷阱状态，因为读入 a 或 b 都回到 4。

DFA 的确定性体现在三个方面：

• 初始状态唯一
• 对任何状态 $s\in S$ 和输入符号 $a\in\Sigma$，$f(s,a)$ 唯一
• 状态转换依赖输入字符，DFA 中每一步都有确定的后继状态
• $\varepsilon$ 的输入为空边，也就是不接受没有任何输入就进行状态转换的情况

DFA 接受的字符串

对于字母表 $\Sigma$ 上的任意字符串 $a_1a_2\dots a_n$，若 DFA $M$ 中存在一条从初始状态到某个终止状态的路径，并且路径上所有边的标记依次连接后等于 $a_1a_2\dots a_n$，则称该字符串可被 DFA $M$ 接受或识别。

形式上说，DFA 处理字符串时，从初始状态开始，按字符顺序读取输入，每读入一个字符就根据状态转换函数移动到下一个状态。输入读完后，若当前状态属于终止状态集 $Z$，则该字符串被接受。

DFA $M$ 能接受的所有字符串构成的集合，称为 DFA $M$ 接受的语言，记为 $L(M)$。

例如某 DFA 的路径可识别形如 aba(ab)* 的字符串，则：

• aba 可被接受
• abaab 可被接受
• abaabab 可被接受
• abaa 根据最终状态判断
• $\varepsilon$ 是否被接受取决于初始状态是否为终止状态

DFA 的应用包括：

• 在语言学中，自动机可作为语言识别器
• 在计算机科学中，自动机可作为计算过程的动态数学模型
• 在自动控制领域中，自动机可处理控制信号序列

---

设计识别能被 3 整除的二进制数的 DFA 时，可用余数作为状态：

• $S_0$：当前二进制数除以 3 余 0
• $S_1$：当前二进制数除以 3 余 1
• $S_2$：当前二进制数除以 3 余 2

初始状态是 $S_0$，终止状态也是 $S_0$。因为余数为 0 表示该二进制数能被 3 整除。

读入一个新二进制位 b 后，原数 $n$ 变为 $2n+b$，新余数为：

$$(2r+b)\bmod 3$$

其中 $r$ 是原来的余数，$b\in{0,1}$。

因此转换规律为：

状态 \ $b$	$0$	$1$
$S_0$	$S_0$	$S_1$
$S_1$	$S_2$	$S_0$
$S_2$	$S_1$	$S_2$

---

这个 DFA 可以画成下面的图，其中 D 是个非法状态：

DFA 描述单词

DFA 可以用来描述词法分析中的各种单词。

标识符的描述，设：

$$L=a|b|\dots|z|A|B|\dots|Z|\_\\ D=0|1|2|\dots|9$$

标识符的正则表达式为：

$$L(L|D)^*$$

对应 DFA 的含义是：第一个字符必须是字母或下划线，后续字符可以是字母、下划线或数字。常数等的命名规则同上。

这些表达式可转成 DFA，用状态表示是否已经读入符号、整数部分、小数点和小数部分。

特殊符号也可由 DFA 描述。例如 {、+、>、= 都可以从初始状态读入单个字符后进入对应终止状态。若要识别复合运算符，例如 >=，则读入 > 后需要继续判断下一个字符是否为 =。

保留字可用字符路径描述。例如 for 的 DFA 路径为：

0 --f--> 1 --o--> 2 --r--> 3

其中状态 3 是接受状态。

if 的 DFA 路径为：

0 --i--> 4 --f--> 5

其中状态 5 是接受状态。

实际词法分析中，保留字和标识符容易冲突。常用处理方法是先按标识符规则识别完整字符串，再查保留字表。若识别到的字符串是 if、for、while 等，则输出保留字类别；否则输出标识符类别。

DFA 的程序实现

DFA 的程序实现主要有两种方法。

第一种是直接转向法。它基于状态转换图实现，每个状态对应一段 switch 判断，不同输入字符跳转到不同状态。

示意代码：

L_i:
switch (CurChar) {
    case 'a':
        goto L_j;
    case 'b':
        goto L_k;
    case '#':
        Accept();
    default:
        Error();
}

直接转向法的特点是：程序结构与状态图一一对应，理解直观；当状态图变化时，代码也要跟着变化。

第二种是基于状态转换矩阵的方法。它把 DFA 存成表，通过查表完成状态转换。

示意代码：

state = S0;
curChar = readNextChar();

while (curChar != '#' && T[state][curChar] != error) {
    state = T[state][curChar];
    curChar = readNextChar();
}

if (curChar == '#' && state in FinalState) {
    return true;
} else {
    return false;
}

其中：

• state 表示当前状态
• curChar 表示当前输入字符
• T[state][curChar] 表示状态转换矩阵
• FinalState 表示终止状态集合
• # 表示输入结束符

状态转换矩阵法的优点是程序框架固定，只需要修改状态表即可适配不同 DFA。它适合词法分析器的自动生成。状态较多、字符集较大时，矩阵可能占用较多存储空间，可使用压缩表或稀疏表优化。

NFA 的确定化

NFA，即非确定有限自动机，是一个五元组：

$$A=(S,\Sigma,f,S_0,Z)$$

其中：

• $S$：有穷状态集
• $\Sigma$：输入字母表
• $f$：状态转换函数，$f:S\times(\Sigma\cup{\varepsilon})\to 2^S$
• $S_0$：初始状态集
• $Z$：终止状态集

含义是：NFA 在某个状态读入一个字符，或通过 $\varepsilon$ 空边，可以转移到一个状态集合。它允许一个状态对同一输入有多个后继状态，也允许 $\varepsilon$ 转移。

---

自动机等价的定义：设 $A_1$ 和 $A_2$ 是同一个字母表 $\Sigma$ 上的自动机，若它们接受的语言相同，即：

$$L(A_1)=L(A_2)$$

则称 $A_1$ 和 $A_2$ 等价。

重要定理：对任意一个 NFA $A$，都存在一个 DFA $A'$，使得：$L(A)=L(A')$。

由 NFA 构造与其等价的 DFA 的过程，称为 NFA 的确定化。

NFA 确定化的核心方法是子集法。它的思想是：DFA 的一个状态记录 NFA 在读入某个输入符号后可能达到的一组状态。也就是说，NFA 中的一组状态：

$$\{s_{j1},s_{j2},\dots,s_{jn}\}$$

可以作为 DFA 中的一个状态 $s_i'$。

无 $\varepsilon$ 空边 NFA 的确定化

对于无 $\varepsilon$ 空边的 NFA，确定化时直接计算状态集合在每个输入符号下能到达的新状态集合。

设当前 DFA 状态对应 NFA 状态集合 $I$，输入字符为 $a$，则新状态集合为：

$$f(I,a)=\bigcup_{s\in I}f(s,a)$$

每得到一个新的状态集合，就把它作为 DFA 的一个新状态，继续对所有输入符号求转换，直到没有新状态集合产生。

带 $\varepsilon$ 空边 NFA 的确定化

带 $\varepsilon$ 空边时，需要先引入 $\varepsilon$ 闭包。状态集 $J$ 的 $\varepsilon$ 闭包记为：

$$\varepsilon\text{-CLOSURE}(J)$$

定义如下：

1. 若 $q\in J$，则 $q\in \varepsilon\text{-CLOSURE}(J)$。
2. 若 $q\in \varepsilon\text{-CLOSURE}(J)$，并且从 $q$ 出发经过任意条 $\varepsilon$ 边可到达 $q'$，则 $q'\in \varepsilon\text{-CLOSURE}(J)$。

设 $I=\{S_1,S_2,\dots,S_m\}$ 是 NFA 的一个状态集合，对输入字符 $a\in\Sigma$，先求：

$$J=f(S_1,a)\cup f(S_2,a)\cup\dots\cup f(S_m,a)$$

再求：

$$\begin{align*} I_a&=\varepsilon\text{-CLOSURE}(J)\\ &=\textcolor{red}{\varepsilon\text{-CLOSURE}}(\bigcup_{S_i\in I} f(S_i,a)) \end{align*}$$

其中 $I_a$ 就是状态集 $I$ 读入 a 后在 DFA 中应转移到的新状态集合，它也是闭包。

---

完整确定化流程：

1. 求 NFA 初始状态集的 $\varepsilon$ 闭包，作为 DFA 初始状态。
2. 对每个 DFA 状态集合 $I$，分别计算每个输入字符下的 $I_a$。
3. 若 $I_a$ 是新的状态集合，则加入 DFA 状态集。
4. 重复计算，直到状态集合不再增加。
5. 若某个 DFA 状态集合中包含 NFA 的终止状态，则该 DFA 状态是终止状态。

---

课件中的例子把 NFA 状态集合转换为 DFA 状态，例如：

• $S_1=\{1,2\}$
• $S_2=\{4,5,7,6,2\}$
• $S_3=\{3,8\}$
• $S_4=\{3,9,8\}$
• $S_5=\{9\}$

其中包含 NFA 终态 9 的集合，对应 DFA 的终止状态。

NFA 的终态是人为规定的，只要包含 NFA 的任意一个终态，那么 DFA 的对应状态也是终止状态。

---

另一个例题：

---

NFA 确定化的本质是把“多种可能路径同时存在”的情况压缩进 DFA 的一个集合状态中。每个集合状态代表 NFA 当前可能处于的所有状态。

DFA 的化简

DFA 化简的目标是得到最小自动机。最小自动机的定义是：DFA $M$ 中没有无关状态，也没有等价状态。

无关状态

状态 $S$ 是无关状态，通常有两种情况：

• 从开始状态没有到 $S$ 的通路。
• 从 $S$ 出发没有到任意终止状态的通路。

这类状态对识别语言没有实际贡献，可以删除。

等价状态

对 DFA 中两个状态 $S_1$ 和 $S_2$，若分别把它们看作初始状态时，能接受的符号串集合相同，则称 $S_1$ 和 $S_2$ 等价。

状态等价需要满足两个条件：

1. 一致性条件：$S_1$ 和 $S_2$ 同时为接受状态，或同时为非接受状态。
2. 蔓延性条件：对所有输入符号，$S_1$ 和 $S_2$ 都必须转换到等价状态中。

也就是说，若输入字符为 $a$，则 $f(S_1,a)$ 和 $f(S_2,a)$ 也应等价。

终止状态和非终止状态属于不同类别，二者在初始划分时分开。

状态分离法

DFA 化简常用状态分离法。步骤：

1. 初始划分：把所有终止状态分为一组，所有非终止状态分为一组。
2. 检查每一组中的状态：若它们对某个输入字符转向不同的组，则这些状态应被分离。
3. 得到新分组后继续检查。
4. 重复分离，直到没有新组产生。
5. 每个最终分组中的状态互相等价，可以合并为一个状态。

---

课件例子中的初始划分为：

$$\{1,2,3,5\}\cup\{4,6,7,8\}$$

经过输入字符 a 和 b 的转向检查后，进一步分离为：

$$\{1,3\}\cup\{2,5\}\cup\{4,6,7,8\}$$

最终化简后，这三个状态集合分别合并为三个新状态：

• $S_0=\{1,3\}$
• $S_1=\{2,5\}$
• $S_2=\{4,6,7,8\}$

DFA 化简的关键判断是：同组状态在每个输入字符下的后继状态是否仍然落在相同分组中。若转向模式相同，则这些状态保留在同组；若转向模式不同，则继续拆分。

正则表达式和有限自动机的相互转化

正则表达式和有限自动机描述能力等价。对 $\Sigma$ 上的每一个正则表达式 $R$，都存在一个 $\Sigma$ 上的 NFA $M$，使得：

$$L(M)=L(R)$$

因此，正则表达式可以转为 NFA，NFA 也可以转为等价的正则表达式。

正则表达式到 NFA

正则表达式到 NFA 的转换基于基本结构组合。

1. 单个字符 a：构造一条从开始状态到终止状态、标记为 a 的边。
2. 连接表达式 ab：先构造 a 的 NFA，再构造 b 的 NFA，把前一个片段的终止状态连接到后一个片段的开始状态。
3. 或表达式 a|b：从新开始状态通过 $\varepsilon$ 边分别进入 a 和 b 的子自动机，再通过 $\varepsilon$ 边汇合到新终止状态。
4. 闭包表达式 b*：构造 b 的子自动机，并加入 $\varepsilon$ 边，使其可以重复执行，也可以直接从开始状态到终止状态。

课件例子：为正则表达式 (a|b)*aa 构造 NFA。

拆分结构为：

(a|b)* aa

再继续拆为：

(a|b)* a a

构造思路：

1. 先构造 a|b 的分支结构。
2. 对 a|b 加 *，形成 (a|b)* 的循环结构。
3. 后面依次连接两个 a。
4. 得到接受所有以两个 a 结尾、前面由任意个 a 或 b 组成的字符串的 NFA。

该表达式对应的语言可以理解为：

$$L((a|b)^*aa)$$

即所有字母表 ${a,b}$ 上以 aa 结尾的字符串。

NFA 到正则表达式

NFA 到正则表达式的转换可通过逐步消去状态完成。基本思想是把经过中间状态的路径合并为一个正则表达式标记。

常见合并规则：

• 多条并行边合并为或表达式，例如 a 和 b 合并为 a|b
• 连续路径合并为连接表达式，例如 a 后接 b 合并为 ab
• 自环合并为闭包表达式，例如状态上有 a 自环，可形成 a*
• 经由某个中间状态的路径可合并为“进入路径 + 自环闭包 + 离开路径”

课件例子中，NFA 逐步消去中间状态后得到正则表达式：

$$a(ab|ba)a^*b$$

这个表达式表示：

1. 字符串以 a 开始。
2. 中间接 ab 或 ba。
3. 后面接零个或多个 a。
4. 最后以 b 结束。

---

例题：构造 $(a|b)(c|d)*(e|f)$ 的最简 DFA

目标正则表达式：

$$(a|b)(c|d)^*(e|f)$$

它描述的字符串结构为：

1. 第一个字符是 a 或 b。
2. 中间可以有零个或多个 c 或 d。
3. 最后一个字符是 e 或 f。

第一步：转为 NFA。

结构可分为三段：a|b、(c|d)*、e|f

NFA 中先通过 a 或 b 进入中间部分，中间部分在 c 和 d 上循环，最后通过 e 或 f 到达终止状态。

第二步：NFA 确定化。

课件给出的 DFA 状态集合包括：

• $S_0=\{0\}$
• $S_1=\{1,2,3\}$
• $S_2=\{2,3\}$
• $S_3=\{4\}$

其中 $S_0$ 是初始状态，$S_3$ 是终止状态。

对应转换表可整理为：

状态	a	b	c	d	e	f
$S_0+$	$S_1$	$S_1$
$S_1$			$S_2$	$S_2$	$S_3$	$S_3$
$S_2$			$S_2$	$S_2$	$S_3$	$S_3$
$S_3*$

第三步：DFA 最小化。

初始划分：

$$\{S_0,S_1,S_2\}\cup\{S_3\}$$

进一步判断后得到等价状态：

$$\{S_0\}\cup\{S_1,S_2\}\cup\{S_3\}$$

因此 $S_1$ 和 $S_2$ 可以合并。

最简 DFA 的结构为：

• 初始状态 $S_0$
• 中间状态 $\{S_1,S_2\}$
• 终止状态 $S_3$

转换关系：

• $S_0$ 读入 a 或 b 到达 $\{S_1,S_2\}$
• $\{S_1,S_2\}$ 读入 c 或 d 仍留在 $\{S_1,S_2\}$
• $\{S_1,S_2\}$ 读入 e 或 f 到达 $S_3$

---

第 9 到第 11 部分可以串成一条完整流程：先把 NFA 通过子集法确定化为 DFA，再用状态分离法化简 DFA；正则表达式可先转 NFA，再确定化、化简，最终得到可直接实现的最简 DFA。

语法分析

文法

文法是描述语言语法结构的形式化工具。一个文法定义为四元组：

$$G=(V_T,V_N,S,P)$$

其中：

• $V_T$ 是终结符集合
• $V_N$ 是非终结符集合
• $S$ 是开始符号，且 $S \in V_N$
• $P$ 是产生式集合

产生式的一般形式是：

$$\alpha \to \beta$$

其中 $\alpha,\beta \in (V_T \cup V_N)^*$，并且左部通常至少要包含非终结符^[1]。书写时通常只写产生式集合；若多个产生式左部相同，可以合并书写，如 $B \to \varepsilon \mid Bb$。

文法的分类

按乔姆斯基层次，文法可以分为四类：

• 0 型文法：短语文法，产生式一般写作 $ \alpha \to \beta $，左部至少包含一个非终结符
• 1 型文法：上下文有关文法，满足 $|\alpha| \le |\beta|$，也就是表达式的长度不缩短，一般的形式是 $\alpha A \beta\to\alpha \gamma\beta$，但开始符相关情况有例外
• 2 型文法：上下文无关文法 CFG，产生式左部只能是一个非终结符
• 3 型文法：正则文法，右部最多两个符号，通常形如 $A \to a$ 或 $A \to aB$

这一章后续的语法分析主要围绕 CFG 展开。

上下文无关文法 CFG

上下文无关文法仍然写作：

$$G=(V_T,V_N,S,P)$$

但其产生式必须满足：

$$A \to X_1X_2\dots X_n$$

其中 $A \in V_N$，每个 $X_i \in (V_T \cup V_N)$，右部允许为空，即可以出现 $\varepsilon$。例如：

$$S \to aSb \mid ab$$

这是一个典型的 CFG。

推导、句型、句子与语言

如果有产生式 $A \to \beta$，那么对于任意符号串 $\alpha,\gamma$，都有一步推导：

$$\alpha A \gamma \Rightarrow \alpha \beta \gamma$$

这里：

• $\alpha \Rightarrow^+ \beta$ 表示经过一步或多步推导得到
• $\alpha \Rightarrow^* \beta$ 表示经过零步或多步推导得到

若有：

$$S \Rightarrow^* \beta$$

则称 $\beta$ 是文法的句型。若 $\beta$ 只包含终结符，则称 $\beta$ 是句子。

文法定义的语言记为：

$$L(G)=\{u \mid S \Rightarrow^+ u; u \in V_T^*\}$$

也就是从开始符号出发能够推导出的所有终结符串的集合。

最左推导、最右推导与句柄

若每一步总是替换当前句型中最左边的非终结符，则称为最左推导。若总是替换最右边的非终结符，则称为最右推导。

• 最左推导得到的中间结果称为左句型
• 最右推导得到的中间结果称为右句型，也叫规范句型

一个句型中的某个子串若是由某个非终结符推导出来的，就称它为该句型的短语。若这个推导只用一步完成，则称为直接短语。一个句型中最左边的直接短语叫句柄。

句柄在自底向上分析里很关键，因为归约时通常就是在找句柄。

语法分析树

语法分析树是句型结构的树形表示。它满足：

• 根结点是开始符号 $S$
• 非叶结点标记非终结符
• 叶结点标记终结符、非终结符或 $\varepsilon$
• 若某个非叶结点标记为 $A$，其孩子从左到右为 $X_1,X_2,\dots,X_n$，则文法中必须有产生式：

$$A \to X_1X_2\dots X_n$$

语法分析树描述的是结构，线性推导描述的是推导顺序。一个句型若文法无二义性，通常对应唯一分析树；线性推导过程可能不止一种。

---

例题：

二义性文法

若一个文法的某个句型有两棵不同的语法分析树，则该文法是二义性文法。

等价地说，若某个句型存在两种不同的最左推导或两种不同的最右推导，该文法也是二义性的。

例如表达式文法：

$$E \to i \mid E+E \mid E*E \mid (E)$$

对串 i*i+i 可以构造两种不同结构的分析树，因此它是二义性文法。二义性会直接影响语法分析器如何确定结构。

---

另一个例子：

在 C 语言中，else 会和最近的 if 匹配。

---

目前没有一般性的判断二义性的方法。

常用的经验性判断：

• $S\to SS|a$ 可以推导出 $SSS$ 串，必有二义性
• $S\to S+S$ 可以推导出 $S+S+S$，必有二义性

因为递归结构没有规定结合方向。$SSS$ 可以左结合或右结合，$S+S+S$ 也可以左结合或右结合，所以会出现两棵语法树。实际写文法时，可以通过分层或固定递归方向消除这类二义性。

文法等价变换

文法等价变换的目标是：在不改变语言 $L(G)$ 的前提下，把文法改写成更适合语法分析的形式。后面的递归下降和 LL(1) 分析都依赖这一步。

增加拓广产生式

对任一文法 $G_1$，都可以构造等价文法 $G_2$，使其开始符唯一且不出现在任何产生式右部。

方法是：若原开始符号为 $S$，引入新开始符号 $Z$，增加一条产生式：

$$Z \to S$$

例如原文法 $ A \to aA \mid b $，可拓广为：

• $Z\to A$
• $ A \to aA \mid b $

这一步常用于后续构造分析器或分析表。

消除空产生式

空产生式是形如：

$$A \to \varepsilon$$

的产生式。消除空产生式的核心思路是先找出所有能推出 ε 的非终结符，再把这些符号在其他产生式右部中“可有可无”的情况补出来，最后删除空产生式。

课件中的方法可以压成三步：

1. 求出所有可空非终结符集合
2. 对含这些符号的产生式补充删去相应符号后的新产生式
3. 删除原空产生式及只能导出空串的无用部分

例如文法：

• A -> aBcD
• B -> b | ε
• D -> BB | d

其中 B 可空，D 也因此可空。补充规则后，可得到：

• A -> aBcD | acD | aBc | ac
• B -> b
• D -> BB | B | d

这样语言保持不变，但文法中已经没有空产生式。

消除不可达产生式

若某个非终结符从开始符号出发永远不会在任何句型中出现，则它是不可达的。以它为左部的产生式对语言没有贡献，可以删掉。

算法思路：

1. 从开始符号出发，放入可达集合
2. 扫描所有已可达非终结符的产生式右部，把能到达的新非终结符继续加入
3. 重复直到集合不再变化
4. 删除左部不在该集合中的所有产生式

这一步是在去掉“永远用不到”的规则。

消除特型产生式

特型产生式指形如：

$$A \to B$$

的单非终结符产生式，也就是右部只有一个非终结符。它会让推导链变长，不利于后续分析。

处理思路：

1. 对每个非终结符 $A$，求出所有能由 $A \Rightarrow^+ B$ 到达的非终结符集合
2. 若这些 $B$ 有非特型产生式 $B \to \alpha$，则把 $A \to \alpha$ 补进来
3. 删除所有特型产生式
4. 再删一遍不可达产生式

例如：

• A -> B | D | aB
• B -> C | b
• C -> c
• D -> B | d

消除后可整理为：

• A -> aB | b | d | c
• B -> b | c

消除公共前缀

若某个非终结符有多个候选式以同样的前缀开头，就存在公共前缀。例如：

• $A \to \alpha\beta$
• $A \to \alpha\gamma$

这种文法在自顶向下分析时，读到前缀 $\alpha$ 仍然无法决定选哪条产生式，所以要提取左因子。

方法是引入新非终结符 $A'$，改写为：

• $ A \to \alpha A’ \mid \gamma $
• $A' \to \beta_1 \mid \beta_2 \mid \dots \mid \beta_n$

本质上是把“共同开头”先抽出来，再延后分支选择。

消除左递归

左递归会导致递归下降分析器无限递归，因此必须消除。

若文法存在：

$A \Rightarrow^+ A\dots$

则称文法有左递归。

直接左递归

形如：

$A \to A\alpha \mid \beta$

可改写为：

• $A \to \beta A'$
• $A' \to \alpha A' \mid \varepsilon$

这个改写把“反复重复 $\alpha$”转到新非终结符 $A'$ 中。

间接左递归

例如：

• $A \to B\alpha \mid \beta$
• $B \to A\gamma \mid b$

需要先代入，把它变成直接左递归形式，再按直接左递归的方法消除。课件给出的思路是先展开成类似：

$ A \to A\gamma\alpha \mid b\alpha \mid \beta $

或对 $B$ 做同类替换，然后再套直接左递归消除公式。

---

例题：构造一个文法 $G$，使 $L(G) = \{a^nb^mc^k \mid m=n+k, n\ge1, m>1, k\ge1\}$。

构造如下：

• $S\to AB$
• $A\to aAb\mid ab$
• $B\to bBc\mid bc$

---

可以这样构建：

所以它是一个二义性的文法。

语法分析的功能

语法分析的任务是按照程序设计语言的语法规则，识别并分解程序中的各种语法成分。它要解决的核心问题是：给定文法 $G$ 和输入串 $\alpha$，判断 $\alpha$ 是否是 $G$ 所能生成的句子。

在编译过程里，语法分析位于词法分析之后、语义分析之前。词法分析把源程序切分成 token 串，语法分析根据这些 token 构造语法结构，通常产出语法树或语法分析树，供后续语义分析使用。

语法错误处理

语法分析不仅要判断“对不对”，还要在出错时尽量继续工作。要求有三个：

• 报告错误出现的位置
• 尽量修复错误并继续检查后续部分
• 处理代价不能过大

常见错误处理策略有四种。

紧急方式恢复

发现错误后，分析器不断丢弃输入符号，直到当前输入符号属于某个同步记号集合。这样可以尽快跳到一个相对安全的位置继续分析。

这种方法实现简单，代价较低，但可能跳过较多内容。

短语级恢复

发现错误后，对剩余输入串的前缀做局部修正，用一个能让分析继续进行的符号串替换掉错误部分。

这种方式更精细，但实现更复杂。

出错产生式

在文法中专门增加一些描述常见错误结构的产生式，使分析器能识别某些典型错误并给出更明确的提示。

这种方式适合处理高频、模式明显的错误。

全局纠正

在所有可能修正方式中，寻找对输入串改动最少的一种，使修改后的串能被文法接受。这里的改动通常包括插入、删除和替换。

这种方式理论上更理想，但开销通常较大。

自顶向下分析

自顶向下分析的思想是：从文法开始符号出发，尝试一步步推导出给定的输入串。

例如文法：

• Z -> aBd
• B -> d
• B -> c
• B -> bB

对输入串 abcd，可以做推导：

$$Z \Rightarrow aBd \Rightarrow abBd \Rightarrow abcd$$

这个过程说明，自顶向下分析的本质是“从目标文法出发去匹配输入”。它的关键问题是：当一个非终结符有多个候选式时，当前到底该选哪一条产生式。

---

为了解决“如何选产生式”的问题，引入三个核心集合：First、Follow 和 Predict。

First 集

设 $G=(V_T,V_N,S,P)$ 是上下文无关文法，$\beta \in (V_T \cup V_N)^*$，则：

$$\text{First}(\beta)=\{a \in V_T \mid \beta \Rightarrow^* \underbrace{a...}_\text{以 $a$ 开头的一个字串}\} \cup (\text{若 } \beta \Rightarrow^* \varepsilon \text{ ，则 } {\varepsilon} \text{ ，否则 } \varnothing)$$

也就是说，First(β) 表示：从 $\beta$ 出发，可能首先出现的终结符集合；如果 $\beta$ 能推出空串，还要把 ε 放进去。它的作用是看当前输入符号是否可能由某个候选式右部开头，从而决定是否选择该候选式。

Follow 集

对于非终结符 $A \in V_N$，若 $S$ 是开始符号，则：

<section class="footnotes"><div class="footnote-list"><ol><li><span id="fn:1" class="footnote-text"><span>要不然没法展开。 <a href="#fnref:1" rev="footnote" class="footnote-backref"> ↖</a></span></span></li></ol></div></section>