编译原理课程笔记

概论

编程语言的发展：

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

高级语言的实现

编译方式

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

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

解释方式

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

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

转换方式

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

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

编译程序的组成

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

词法分析

词法分析器

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

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

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

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

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

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

符号和符号串

字母表是元素的非空有穷集合，通常记为 $\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$ 为字母表，正则表达式递归定义如下：

$\varepsilon$ 和 $\varnothing$ 是 $\Sigma$ 上的正则表达式：
$L(\varepsilon)=\{\varepsilon\}, L(\varnothing)=\{\}$
对任意 $a\in\Sigma$ ， $a$ 是 $\Sigma$ 上的正则表达式：
$L(a)={a}$
若 $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))^*$

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

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

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

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$ 表示整数

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

保留字：

1	`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^+

特殊符号包括：

运算符： $+|-|*|\dots$
分界符： $\{\}|\;|\dots$
控制符： $\backslash \text{t}|\backslash \text{n}|\dots$

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

正则表达式的局限性

注意事项

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

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

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

例题：

可以构造成 $(y|z)*(x(y∣z)∗x(y∣z)∗)∗$
可以构造成 $(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 路径为：

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

其中状态 $3$ 是接受状态。

if 的 DFA 路径为：

1	`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)

定义如下：

若 $q\in J$ ，则 $q\in \varepsilon\text{-CLOSURE}(J)$ 。
若 $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 中应转移到的新状态集合，它也是闭包。

完整确定化流程：

求 NFA 初始状态集的 $\varepsilon$ 闭包，作为 DFA 初始状态。
对每个 DFA 状态集合 $I$ ，分别计算每个输入字符下的 $I_a$ 。
若 $I_a$ 是新的状态集合，则加入 DFA 状态集。
重复计算，直到状态集合不再增加。
若某个 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$ 等价。

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

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

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

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

状态分离法

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

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

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

\{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 的转换基于基本结构组合。

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

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

拆分结构为：

(a|b)^* aa

再继续拆为：

(a|b)^* a a

构造思路：

先构造 $a|b$ 的分支结构。
对 $a|b$ 加 $*$ ，形成 $(a|b)^*$ 的循环结构。
后面依次连接两个 $a$ 。
得到接受所有以两个 $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

这个表达式表示：

字符串以 $a$ 开始。
中间接 $ab$ 或 $ba$ 。
后面接零个或多个 $a$ 。
最后以 $b$ 结束。

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

目标正则表达式：

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

它描述的字符串结构为：

第一个字符是 $a$ 或 $b$ 。
中间可以有零个或多个 $c$ 或 $d$ 。
最后一个字符是 $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

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

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

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

例如文法：

$A \to aBcD$
$B \to b \mid \varepsilon$
$D \to BB \mid d$

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

$A \to aBcD \mid acD \mid aBc \mid ac$
$B \to b$
$D \to BB \mid B \mid d$

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

消除不可达产生式

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

算法思路：

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

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

消除特型产生式

特型产生式指形如：

A \to B

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

处理思路：

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

例如：

$A \to B \mid D \mid aB$
$B \to C \mid b$
$C \to c$
$D \to B \mid d$

消除后可整理为：

$A \to aB \mid b \mid d \mid c$
$B \to b \mid 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 \to aBd$
$B \to d$
$B \to c$
$B \to 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$ 能推出空串，还要把 $\varepsilon$ 放进去。它的作用是看当前输入符号是否可能由某个候选式右部开头，从而决定是否选择该候选式。

`Follow` 集

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

\text{Follow}(A)=\{a \in V_T \mid S \Rightarrow^+ \underbrace{...Aa...}_\text{包含 $Aa$ 的一个字串，且 $a$ 紧跟在 $A$ 后面}\} \cup (\text{若 } S \Rightarrow^* ...A \text{ ，则 } \lbrace\#\rbrace \text{ ，否则 } \varnothing)

这里 $\#$ 表示输入结束符。

Follow(A) 表示：在某个句型中，可能紧跟在 $A$ 后面的终结符集合。如果 $A$ 可能出现在句末，则 $\#$ 也属于 Follow(A)。

它的作用主要体现在空产生式上：若某个非终结符可以推出 $\varepsilon$ ，而当前输入符号属于 Follow(A)，则可以选择让 $A$ 消失。

`Predict` 集

对产生式 $A \to \beta$ ，定义：

\text{Predict}(A \to \beta)= \begin{cases} \text{First}(\beta), & \varepsilon \notin \text{First}(\beta) \\ (\text{First}(\beta)-{\varepsilon}) \cup \text{Follow}(A), & \varepsilon \in \text{First}(\beta) \end{cases}

Predict 集直接表示：当前输入符号属于哪些集合时，可以选择这条产生式。因此，在实际分析中，选择产生式时最直接的判断依据就是 Predict。

下面讲述三个集合在推导中的作用，例如文法：

$S \to aA \mid d$
$A \to bAS \mid \varepsilon$

以及输入串 $abd$ 来说明三者的作用。

用 `First` 判断

开始分析 $S$ 时，当前输入是 $a$ 。因为 $a \in \text{First}(aA)$ ，而 $a \notin \text{First}(d)$ ，所以应选择：

S \to aA

分析到 $A$ 时，当前输入是 $b$ 。因为 $b \in \text{First}(bAS)$ ，所以应选择：

A \to bAS

用 `Follow` 判断空产生式

继续分析时，当前输入变成 $d$ 。此时：

$d \notin \text{First}(bAS)$
但 $d \in \text{Follow}(A)$

所以这里可以让 $A \to \varepsilon$ ，即把 $A$ 消去，继续后面的推导。

用 `Predict` 统一判断

如果直接用 Predict，判断会更统一：

$a \in \text{Predict}(S \to aA)$ ，所以选 $S \to aA$
$b \in \text{Predict}(A \to bAS)$ ，所以选 $A \to bAS$
$d \in \text{Predict}(A \to \varepsilon)$ ，所以选 $A \to \varepsilon$

这说明 Predict 实际上把 First 和 Follow 的作用合并成了一个最终决策集合。

自顶向下分析的条件

对于某个非终结符 $A$ 的不同候选式，若要让自顶向下分析在看到当前输入符号时能唯一决定该选哪条产生式，就要求这些候选式的 Predict 集彼此不相交。

设有两个候选式：

$A \to \beta_k$
$A \to \beta_j$

则必须满足：

\text{Predict}(A \to \beta_k) \cap \text{Predict}(A \to \beta_j)=\varnothing \quad (k \ne j)

只有这样，当前输入符号才至多落入一个候选式的 Predict 集中，分析器才能唯一选择。

因此，自顶向下分析成立的核心条件就是：同一非终结符的不同候选式，其 Predict 集两两不交。

下面涉及到三个集合的求法。

`First(X)` 的求法

对任意文法符号 $X$ ，First(X) 表示：从 $X$ 出发推导时，最先可能出现的终结符集合；如果 $X$ 能推出空串，还要把 $\varepsilon$ 放进去。计算规则如下。

如果 $X$ 是终结符，即 $X \in V_T$ ，则：

\text{First}(X)={X}

如果 $X$ 是非终结符，即 $X \in V_N$ ，并且有产生式右部以终结符 $a$ 开头，例如 $X \to a\dots$ ，则：

a \in \text{First}(X)

如果 $X$ 是非终结符，且有产生式：

X \to \varepsilon

则：

\varepsilon \in \text{First}(X)

如果 $X$ 有产生式：

X \to Y_1Y_2\dots Y_n

则按从左到右的顺序处理：

把 $\text{First}(Y_1)-{\varepsilon}$ 加入 $\text{First}(X)$
若 $Y_1 \Rightarrow^* \varepsilon$ ，则继续把 $\text{First}(Y_2)-{\varepsilon}$ 加入
依次类推
若所有 $Y_i$ 都能推出 $\varepsilon$ ，则把 $\varepsilon$ 加入 $\text{First}$

核心思想是：从右部最左边开始看，谁最先能产生终结符，就把谁的首符号收进去；若前面的符号都能消失，就继续往后看。

$\text{First}(\alpha)$ 的求法

若符号串：

$\alpha = X_1X_2\dots X_n$

则 $\text{First}(\alpha)$ 的计算方法与上面相同，也是从左往右看。

若 $X_1,X_2,\dots,X_{i-1}$ 都能推出 $\varepsilon$ ，而 $X_i$ 不能推出 $\varepsilon$ ，则：

$\text{First}(\alpha)=\bigcup_{j=1}^{i-1}(\text{First}(X_j)-{\varepsilon}) \cup \text{First}(X_i)$

若所有 $X_i$ 都能推出 $\varepsilon$ ，则：

$\text{First}(\alpha)=\bigcup_{j=1}^{n}\text{First}(X_j)$

直观理解就是： $\text{First}(\alpha)$ 看的是"串 $\alpha$ 将来最先可能冒出来的终结符"。

$\text{Follow}(A)$ 的求法

Follow(A) 表示：在某个句型中，可能紧跟在非终结符 $A$ 后面的终结符集合；若 $A$ 可能出现在句末，则还要加入结束符 $\#$ 。

计算规则如下。

对所有非终结符 $B$ ，先令：

$\text{Follow}(B)=\varnothing$

对开始符号 $S$ ，加入：

$\text{Follow}(S)=\lbrace\#\rbrace$

若有产生式：

$A \to xBy$

则分两种情况：

若 $\varepsilon \notin \text{First}(y)$ ，则：

$\text{Follow}(B)\supseteq \text{First}(y)$

准确地说，应加入 $\text{First}(y)$ 中除 $\varepsilon$ 外的终结符。

若 $\varepsilon \in \text{First}(y)$ ，则：

$\text{Follow}(B)\supseteq (\text{First}(y)-{\varepsilon}) \cup \text{Follow}(A)$

也就是说，若 $y$ 能消失，则 $A$ 后面能跟的东西也能跟在 $B$ 后面。

反复应用这些规则，直到所有 Follow 集不再变化。

$\text{Predict}(A \to \beta)$ 的求法

Predict 集是最终用来选产生式的集合。定义为：

\text{Predict}(A \to \beta)= \begin{cases} \text{First}(\beta), & \varepsilon \notin \text{First}(\beta) \\ (\text{First}(\beta)-{\varepsilon}) \cup \text{Follow}(A), & \varepsilon \in \text{First}(\beta) \end{cases}

含义很直接：

若 $\beta$ 不能推出 $\varepsilon$ ，就看 $\text{First}(\beta)$
若 $\beta$ 能推出 $\varepsilon$ ，除了看 $\text{First}(\beta)$ 里非 $\varepsilon$ 的部分，还要把 $\text{Follow}(A)$ 加进来

表达式文法例子

文法为：

$E \to TE'$
$E' \to +TE' \mid \varepsilon$
$T \to FT'$
$T' \to *FT' \mid \varepsilon$
$F \to id \mid (E)$

对应各产生式的 Predict 集为：

$\text{Predict}(E \to TE') = \{id, (\}$
$\text{Predict}(E' \to +TE') = \{+\}$
$\text{Predict}(E' \to \varepsilon) = \{), \#\}$
$\text{Predict}(T \to FT') = \{id, (\}$
$\text{Predict}(T' \to *FT') = \{*\}$
$\text{Predict}(T' \to \varepsilon) = \{+, ), \#\}$
$\text{Predict}(F \to id) = \{id\}$
$\text{Predict}(F \to (E)) = \{(\}$

这一组结果后面会直接拿去构造 LL(1) 分析表。

递归下降分析方法

递归下降分析法是一种自顶向下分析方法。它的基本思想是：给每个非终结符写一个语法分析子程序，程序结构直接对应文法结构。

基本思想

若某个产生式为：

1	`Stm -> while Exp do Stm`

那么它对应的分析程序片段可以写成：

Match(while);
Exp();
Match(do);
Stm();

这里：

终结符对应匹配动作 Match(...)
非终结符对应子程序调用

因此，文法中的递归结构会自然映射成程序中的递归调用，这就是“递归下降”这个名字的来源。

一般写法

若某个非终结符有多个候选式：

$A \to \beta_1 \mid \beta_2 \mid \dots \mid \beta_n$

则对应子程序 A() 的结构是：

procedure A()
begin
    if token ∈ Predict(A -> β1) then 执行 β1
    else if token ∈ Predict(A -> β2) then 执行 β2
    ...
    else if token ∈ Predict(A -> βn) then 执行 βn
    else error()
end

其中，若：

$\beta_i = X_1X_2\dots X_n$

则执行 β_i 的动作是按顺序处理每个符号：

若 X_i 是非终结符，则调用对应过程
若 X_i 是终结符，则执行 Match(X_i)
若 X_i = \varepsilon，则执行空动作

这说明递归下降分析本质上是在代码里手工实现“按 Predict 集选产生式”。

例子

文法：

$Z \to aBa$
$B \to bB \mid c$

对应递归子程序可以写成：

procedure Z()
begin
    if token = a then Match(a); B(); Match(a)
    else error()
end

procedure B()
begin
    if token = b then Match(b); B()
    else if token = c then Match(c)
    else error()
end

对输入串 $abca$ 的分析过程是：

先调用 Z()
匹配第一个 $a$
调用 B()
在 B() 中匹配 $b$ ，再递归调用 B()
第二次 B() 匹配 $c$
返回 Z()
匹配最后一个 $a$
输入结束，分析成功

递归下降分析的特点

优点：

结构直观，文法和程序一一对应
适合手工编写小型语法分析器

限制：

文法必须适合自顶向下分析
不能直接处理左递归
若不同候选式 Predict 集相交，就无法唯一选择分支

所以递归下降分析往往要先对文法做提左因子和消左递归。

`LL(1)` 分析方法

LL(1) 是一种表驱动的自顶向下分析方法，可以看作递归下降分析的规范化、自动化版本。

LL(1) 中：

第一个 L 表示从左到右扫描输入串
第二个 L 表示构造最左推导
1 表示向前看 $1$ 个输入符号

所以 LL(1) 分析的核心就是：只看当前栈顶和当前输入符号，就决定下一步动作。

基本思想

例子文法：

$A \to aBc$
$B \to d \mid bB$

输入串： $abbdc$

分析过程本质上是在维护一个“分析栈 + 输入流”的格局，逐步把栈顶非终结符替换成右部，直到全部匹配完。

例如初始格局可写成：

1	`(A, abbdc)`

然后不断替换、匹配，最终到达空栈和空输入。

`LL(1)` 分析的动作

假设栈顶符号为 $X$ ，当前输入符号为 $a$ ，则可能有四种动作。

替换
若 $X$ 是非终结符，则根据分析表选择一个产生式 $X \to \alpha$ ，用 $\alpha$ 替换 $X$ 。
匹配
若 $X$ 是终结符，且 $X = a$ ，则弹出栈顶并读入下一个输入符号。
成功
若栈为空且输入也到达结束符 $\#$ ，则分析成功。
报错
若无法替换、也无法匹配，则报错并停止。

`LL(1)` 分析表

分析表定义为：

$T : V_N \times V_T \to P \cup \text{Error}$

其中：

$P$ 是产生式集合
$T(A,t)=A\to\alpha$ ，当 $t \in \text{Predict}(A\to\alpha)$
否则 $T(A,t)=Error$

也就是说，分析表本质上是把“某个非终结符在看到某个输入符号时该选哪条产生式”预先存成一个二维表。

`LL(1)` 驱动器算法

驱动器维护三个对象：

分析栈
输入流
LL(1) 分析表

基本流程如下：

初始化：栈中压入开始符号 $S$
读入当前输入符号 $a$
若当前格局是 (empty, #)，则成功
否则设栈顶为 $X$
若 $X$ $X$ 是终结符：
- 若 $X = a$ ，则弹栈并读下一个输入符号
- 若 $X \neq a$ ，则报错
若 $X$ $X$ 是非终结符：
- 若 $T(X,a)=X\to Y_1Y_2\dots Y_n$ ，则弹出 $X$ ，再按逆序把右部压栈
- 否则报错

这套算法和递归下降分析在逻辑上是一样的，只是把“写死在代码里的分支判断”变成了“查分析表”。

表达式文法实例

文法：

$E \to TE'$
$E' \to +TE' \mid \varepsilon$
$T \to FT'$
$T' \to *FT' \mid \varepsilon$
$F \to (E) \mid i$

对输入串 $i+i*i\#$ ，先求各产生式 Predict 集，再构造 LL(1) 分析表。

课件给出的关键结果是：

$\text{Predict}(E \to TE') = \{i, (\}$
$\text{Predict}(E' \to +TE') = \{+\}$
$\text{Predict}(E' \to \varepsilon) = \{), \#\}$
$\text{Predict}(T \to FT') = \{i, (\}$
$\text{Predict}(T' \to *FT') = \{*\}$
$\text{Predict}(T' \to \varepsilon) = \{+, ), \#\}$
$\text{Predict}(F \to (E)) = \{(\}$
$\text{Predict}(F \to i) = \{i\}$

据此可以构造分析表，然后按"栈顶 + 当前输入"一步步做替换和匹配，最终成功识别 $i+i*i\#$ 。

`LL(1)` 分析和递归下降的关系

两者本质相同，都是自顶向下分析，都是利用 Predict 集决定选哪条产生式。

区别在于：

递归下降分析：把逻辑直接写成递归子程序
LL(1) 分析：把逻辑统一写成“栈 + 分析表 + 驱动器”

因此：

递归下降更直观，适合手写
LL(1) 更规范，适合系统化实现

自底向上语法分析

自底向上语法分析是从待分析的符号串出发，自左向右扫描输入，自下而上地恢复它的语法结构。

它的核心过程是：反复在当前句型中寻找句柄，然后按照某个产生式，把这个句柄归约为相应产生式左部的非终结符，直到最终把整个输入串归约成文法的开始符。

也就是说，自底向上分析做的事情本质上是逆着推导过程走。如果顶层推导是从开始符号一步步推出句子，那么自底向上分析就是从句子一步步归约回开始符号。

例如文法：

S -> aAcBe
A -> b
A -> Ab
B -> d

对输入串 abbcde，归约过程为：

1	`abbcde => aAbcde => aAcde => aAcBe => S`

这个过程说明：

先把某个 b 归约成 A
再把 Ab 归约成 A
再把 d 归约成 B
最后把整个 aAcBe 归约成 S

语法树的构造也是自下而上的：每做一次归约，就相当于在语法树中向上合并一层结构。

规范句型

由最右推导得到的句型称为规范句型，也叫右句型。

因为自底向上分析对应的是“最右推导的逆过程”，所以它处理的中间形式主要就是规范句型。

规范前缀

若存在规范句型 αη，其中 η 是终结符串或空串，则称 α 为该规范句型的规范前缀。

直观上，规范前缀就是：在某个规范句型中，从左边截出来的一段前缀。

规范活前缀

若规范前缀 α 不含句柄，或者只含一个句柄且满足：

$\alpha=\alpha'\pi$

其中 π 是句柄，则称 α 为规范活前缀，简称活前缀。

可以把它理解成：在分析过程中，栈里暂时保留下来的那部分“还活着的合法前缀结构”。它可能还没归约完成，但它不能越过句柄的边界太多。

归约规范活前缀

若活前缀中已经包含句柄，即：

$\alpha=\alpha'\pi$

并且 π 是句柄，则称 α 为归约规范活前缀，简称归约活前缀。

归约活前缀表示：当前前缀已经到达一个可以执行归约的位置。

课件中给出了一串规范句型变化，例如：

( , abbcde )
( a, bbcde )
( ab, bcde )
( aA, bcde )
( aAb, cde )
( aA, cde )
( aAc, de )
( aAcd, e )
( aAcB, e )
( aAcBe, )
( S, )

这里左边可以理解为已经分析和归约得到的前缀，右边是剩余输入。随着分析进行，左边不断扩展、归约，最终归约到开始符 S。

派生定理

归约规范活前缀的派生定理说明这类前缀是怎么一步步生成出来的。

开始符产生式的右部是归约规范活前缀。
如果 αAβ 是归约规范活前缀，且有产生式：

$A \to \pi$

则 απ 也是归约规范活前缀。

任何归约规范活前缀都可以按上述方式派生出来。

这三个结论说明：归约规范活前缀是一个可以递归生成的集合。它们不是随意出现的，而是沿着文法产生式一步步展开得到的。

例如文法：

S -> aAc
A -> bbA
A -> b

其归约规范活前缀包括：

aAc
abA
abbA
abbbA
...
ab
abb
abbb
...

这说明：归约规范活前缀既可能停在某个非终结符位置，也可能继续展开成终结符串前缀。

有限自动机与归约规范活前缀

这一节最后一个重要结论是：归约规范活前缀可以用有限自动机识别。

这件事非常关键，因为它实际上就是后面 LR 分析方法的理论起点。

含义是：

自底向上分析的关键任务之一，是判断当前栈中前缀是否是某个合法的归约规范活前缀
这个“合法性判断”可以交给有限自动机来做
后面 LR 项目集状态机，本质上就是这种识别过程的系统化实现

语义分析

语义是程序在被赋予含义后应满足的性质。语义分析关注的不再是“程序长得像不像一种合法结构”，而是“这些结构在含义上是否合法”。

语义分析分成两类：

静态语义分析：在编译期间完成，主要检查程序结构相关的语义正确性
动态语义分析：在运行期间完成，主要检查执行过程中的语义正确性

我们主要讨论静态语义分析。静态语义分析的任务主要包括两类。

静态类型检查，例如：
- 条件表达式的类型是否为布尔型
- 运算分量类型是否相容
- 赋值左右部类型是否相容
- 函数实参与形参类型是否匹配
- 下标表达式类型是否合法
- 函数返回值类型是否与声明一致
一般语义检查，例如：
- 标识符是否先声明后使用
- 同一作用域内是否重复声明
- 数组引用中的变量是否真是数组
- 结构体域访问是否合法
- 函数调用中的函数名、参数个数与参数类型是否合法
- case 标号是否唯一
- break 是否出现在合法语句环境中

语义分析的一般过程

语义分析通常是在语法树或语法分析树基础上进行的。分析器沿着程序的结构自顶向下或按遍历顺序检查：

类型声明
变量声明
函数声明
形参声明
局部变量声明
各种语句
表达式和运算对象

因此，语义分析的核心依赖有两个：

结构信息：来自语法分析
语义信息：主要存放在符号表和类型内部表示中

符号表

符号表是记录标识符语义信息的数据结构。它的每个表项通常记录：

名字
种类
类型
存储类别
存储位置
作用域信息
其他附加属性

复杂对象还需要记录更多语义属性，例如：

数组的维数、上下界、元素类型
结构体的成员信息
函数的参数列表、返回值类型、代码地址等

符号表的总体组织

两种总体组织方式。

第一种是分表组织，把不同种类的标识符分开存：

常量表
变量表
函数表

优点是属性紧凑，不浪费空间；缺点是管理函数变多，查表和填表逻辑更复杂。

第二种是统一表组织，把所有标识符放在一张表里，每个表项带 Kind 字段区分种类。

优点是管理简单；缺点是不同种类共享表项格式，会浪费一些属性空间。

符号表表项的组织方式

表项可以按不同数据结构组织：

无序表：按扫描顺序插入
有序表：按关键字排序
散列表
二叉树

这些结构影响查找、插入和删除的效率。

各类标识符的属性表示

常量标识符

常量表项通常包含：

Name
Kind
Type
Value

例如 pai、count 这类名字，可以记录其值和类型。

类型标识符

类型标识符用于给类型命名，例如：

typedef int t1;
typedef int t2[10];

其核心属性通常是：

Name
Kind=typeKind
Type

其中 Type 指向该类型的内部表示。

变量标识符

变量表项通常包括：

Name
Kind=varKind
Type
Access
Level
Offset
Value

其中：

Access 表示直接访问还是间接访问，可记为 dir / indir
Level 表示变量所属的静态层次
Offset 表示变量在该层活动记录中的相对偏移

函数标识符

函数表项通常包括：

Name
Kind=routKind
Type：返回值类型
Class
Level
Offset
ParamList
Code
Size

其中：

Class=actual 表示有函数体的实际函数
Class=formal 表示作为参数传递的形式函数
ParamList 指向参数表
Code 指向目标代码入口
Size 表示目标代码长度

域名标识符

域名标识符是形如 s.x 的成员访问，其中 s 是结构体变量，x 是域名。

域名的特点是：

它只在所属结构体类型内部有意义
不需要像普通变量那样记录作用域层数
它的偏移量是相对于结构体起始地址的偏移量

记录方法有两种：

直接登记到总符号表中
登记到结构体类型的内部表示中

第二种更自然，因为域名本来就是类型内部组成部分。

类型的内部表示

语义分析必须有一套统一的类型内部表示，以便后续进行类型检查、空间计算和兼容性判断。

基本类型

基本类型包括：

整型
实型
布尔型
字符型

它们的内部表示至少包含：

Size
Kind

例如可用 intPtr、realPtr、boolPtr、charPtr 指向这些基本类型描述。

数组类型

数组类型内部表示通常包含：

Size
Kind=arrayTy
Low
Up
ElemTy

其中：

ElemTy 指向元素类型
Size = sizeof(ElemTy) × (Up-Low+1)

因此，多维数组本质上是“元素仍为数组类型”的嵌套结构。

结构类型

结构体类型内部表示通常包含：

Size
Kind=structTy
Body

其中 Body 是一个域定义链，每个域记录：

FieldName
FieldType
Offset
Next

结构体的总大小是所有域大小之和。

联合类型

联合类型内部表示也有：

Size
Kind=unionTy
Body

不同的是，联合体各域共享存储，所以：

Size 取所有域大小的最大值

枚举类型

枚举类型内部表示通常包含：

Size
Kind=enumTy
EList

其中 EList 是枚举项链表，每项记录：

ItemName
Value
Next

指针类型

指针类型内部表示通常包含：

Size
Kind=pointerTy
BaseType

其中 BaseType 指向被指向对象的类型。

值的内部表示

值分成两类：

简单值，例如：
- int
- float
- bool
- char
- 枚举值
复合值，例如：
- 数组
- 结构体
- 联合
- 指针

这部分的意义在于：语义分析和后续中间代码生成，既要知道“是什么类型”，也要知道“值在内部如何表达”。

标识符作用域与局部化

标识符的作用域是它有效的程序区域。一般来说，一个标识符从声明位置开始生效，到所属局部化单位结束为止。

这一章重点讨论的是：怎样让符号表正确反映这种作用域规则。

局部化符号表

一种方法是每个局部化单位单独建立一张符号表，并用 scope 栈组织这些表。

建表规则：

初始化 scope 栈为空
进入一个新局部化单位时，创建该层符号表并压栈
本层声明的标识符填入该表
退出该层时，把该表弹栈

查表规则：

从 scope 栈顶开始查
若当前层没有，再逐层向外查
直到找到或所有表都查完

这种方法最直接，能很好体现“内层遮蔽外层”的规则。

全局符号表的局部化实现

如果整个程序只维护一张总符号表，就需要额外机制实现作用域控制。课件给出三种方式。

删除法

思路是：退出作用域时，把该作用域内的符号表项直接删除。

实现要点：

给每个局部化区分配编号 num
当前分析位置用 CurrentNum 记录
插入时检查当前层是否重名
查找时按 CurrentNum, CurrentNum-1, ... , 0 的顺序查
退出作用域时删除 num=CurrentNum 的所有表项

优点是查表后留下的表项都有效；缺点是频繁删除会增加维护成本。

驻留法

思路是：退出作用域后不删表项，而是保留并插入特殊标记，使查找时跳过失效项。

本质上仍然是全局表，只是通过标记控制可见性。

优点是避免删除；缺点是查找逻辑更复杂，表会越来越大。

散列法

这是删除法的一种高效实现。基本做法：

用标识符名字做散列键
用散列表组织总符号表
当不同作用域中有重名标识符时，用外拉链处理冲突

这样既保留了全局表的统一管理，又把查找效率提高到接近散列查找。

层数与偏移量

Level 和 Offset 直接关系到存储分配和后续代码生成。

层数 `Level`

主程序层数为 0
在某层函数内部声明的变量或函数，层数为该层加 1

层数反映的是静态嵌套深度。

偏移量 `Offset`

在某一层内：

第一个声明的变量偏移量为 0
后续变量的偏移量等于前一个变量偏移量加前一个变量所占空间

偏移量反映的是该变量在本层活动记录中的相对地址。

因此，(Level, Offset) 可以唯一刻画一个变量在静态环境中的存储位置。

中间代码优化

中间代码优化的目标是提高程序质量，重点是提高运行速度。有三个基本要求：

优化必须保证程序正确性
优化后应带来明显的效率提升
优化要适度，不能为了优化引入过高代价

优化对象主要集中在循环内部，尤其是循环中频繁执行的地址计算和重复表达式。

优化可以分为两大类。

源程序阶段的优化，也就是程序员在写程序时主动选择更优算法和数据结构。它依赖对时间复杂度、空间复杂度的判断。
编译阶段的优化，又可再分成：
- 前端的中间代码级优化
- 后端的目标代码级优化

中间代码级优化又分成：

局部优化：只在基本块内部进行
非局部优化：跨基本块或涉及循环等更大范围

这一章主要讲三种典型优化：

常量表达式优化
公共表达式优化
循环不变式外提

基本块与程序流图

基本块

基本块是一组顺序执行的语句序列，具有以下特征：

只有一个入口，即第一条语句
只有一个出口，即最后一条语句
执行时只能从入口进入，从出口退出
块内语句要么全部执行，要么全部不执行
不能从中间进入，也不能从中间跳出

基本块可以基于源代码、中间代码或目标代码划分。本章主要基于四元式中间代码划分。

两类中间代码

把四元式可以分成两类。

标号性中间代码

标号性四元式只起定位作用，本身不产生跳转指令，例如：

(LABEL, -, -, L)
(ENTRY, Label, Size, Level)
(WHILE, -, -, -)
(ENDIF, -, -, -)

转移性中间代码

转移性四元式在生成目标代码时会形成跳转，例如：

(JMP, -, -, L)
(ENDPROC, -, -, -)
(ENDFUNC, -, -, -)
(THEN, E, -, -)
(ELSE, -, -, -)
(DO, E, -, -)
(ENDWHILE, -, -, -)

基于四元式的基本块划分原则

划分原则是：

初始四元式是第一个基本块入口
遇到转移性中间代码时，当前块结束，该四元式作为当前块出口，下一条作为新块入口
遇到标号性中间代码时，当前块结束，该标号性代码作为新块入口
若遇到 (ASSIG, A, -, X) 且 X 为引用型形参，则结束当前块，并把该语句作为块出口

这说明基本块划分的关键在于识别“控制流可能改变的位置”。

程序流图

在基本块划分完成后，可以构造程序流图。程序流图是以基本块为结点、以控制转移为边的有向图。

程序流图的作用是：

描述程序整体控制结构
为非局部优化提供基础
尤其用于循环识别和循环优化

常量表达式优化

常量表达式是任何时候都取固定常数值的表达式。常量表达式优化通常在基本块范围内进行。

核心思想是：如果某个四元式中的运算分量值已知，编译器就直接把结果算出来，用常数替换原表达式的结果，并删去相应计算代码。

例如：

v = a*b+c，若 a=2、b=3、c=5，则可直接改成 v = 11
若后面有 u = v+3，则可进一步改成 u = 14

这本质上就是常量折叠和常量传播。

常量定值表 `ConstDef`

用常量定值表 ConstDef 表示当前块内“已知取常数值”的变量集合。表项是二元组：

1	`(Var, Val)`

如果 ConstDef 中有 (V, c)，则表示在 V 被重新赋值之前，后续出现的 V 都可以直接替换为常数 c。

基本块上的优化算法

算法可以整理成：

基本块入口处置 ConstDef = ∅
顺序读取当前四元式
用 ConstDef 对四元式分量做值替换，得到 newtuple
若 newtuple 是运算型四元式 (ω, A, B, t)，并且 A、B 都是常数，则直接计算 A ω B = v
把 (t, v) 加入 ConstDef
删掉当前运算四元式，或把后续对 t 的使用替换成常数
若某变量被重新赋值，则更新或删除该变量对应的常量信息

例子：

a := m + 10
b := a + m
c := a + b - d

若进入基本块时已知 m = 10，则可优化为：

a := 20
b := 30
c := 50 - d

这里体现了两层作用：

常量折叠：10 + 10 = 20
常量传播：a 被替换成 20，b 又进一步成为常量

公共表达式优化

公共表达式优化的目标是消除重复计算。

例如：

t := b * c
e := b * c + b * c
c := b * c + 10
d := b * c + d

其中 b * c 被反复计算。优化后可写成：

t := b * c
e := t + t
c := t + 10
d := b * c + d

这里最后一个 d := b * c + d 没有直接替换成 t + d，因为前面的语句已经改写了变量 c，而我们关注的是“分量值是否仍然等价”，不是单纯名字相同。

四元式等价

设有两个非赋值型运算四元式：

(ω_1, A_1, B_1, t_1)
(ω_2, A_2, B_2, t_2)

若满足：

ω_1 = ω_2
A_1 与 A_2 的值相等
B_1 与 B_2 的值相等

则称这两个四元式等价。

因此，公共表达式的判断关键不只是文本相同，而是“操作和运算分量值相同”。

值编码方法

用值编码方法解决“两个分量值是否相等”的判断问题。核心思想是：给中间代码中的每个分量赋一个值编码，值编码相同则说明分量等价。

主要用到三张表：

ValueNum：值编码表，记录变量或常数及其值编码
UsableExpr：可用表达式表，记录基本块中可复用的表达式编码四元式
PAIR：临时变量等价表，记录两个临时变量等价，例如 (t_i, t_j) 表示后续可用 t_i 替换 t_j

基于值编码的优化过程

算法可以概括为：

从基本块第一条四元式开始扫描
对运算分量查 ValueNum 表，必要时生成新值编码
形成编码四元式
若当前是运算型四元式，则在 UsableExpr 中查找是否已有等价表达式
若有，则建立临时变量等价关系，删去当前重复计算
若无，则把当前表达式加入 UsableExpr
在后续代码中利用 PAIR 做替换

公共表达式优化做的是“值级别的去重计算”。它比简单的文本替换更强，因为它在乎的是值等价，而不是表面书写形式。

循环不变式外提

若一个表达式 E 在某个循环内部反复执行，但其值在整个循环过程中都不改变，则称 E 为该循环的不变表达式。

例如：

1
2
3

i := 1;
while i <= 1000 do
    a[i] := x * y;

若 x 和 y 在循环中都不改变，则 x * y 是循环不变式，可以外提为：

i := 1;
t := x * y;
while i <= 1000 do
    a[i] := t;

循环体内的代码会被执行很多次，所以把不变表达式移到循环外，只计算一次，通常能显著降低运行时间。这是循环优化中最典型、最有效的一种。

循环不变式外提的关键有三个：

识别循环结构：找到入口、循环体、出口
判断循环体中哪些变量会被改写
根据变量改写信息判断哪些表达式值不变

为此，需要建立循环变量定值表，把循环体中会被定义的变量记录下来。若某运算型四元式的两个运算分量都不出现在这个表里，则它的值不会在循环中变化，可以考虑外提。

循环识别

基于四元式的循环结构：

(WHILE, -, -, -)
条件 E 的中间代码
(DO, E.form, -, -)
循环体 S 的中间代码
(ENDWHILE, -, -, -)

循环可以基于程序文本识别，也可以基于程序流图识别。

安全性问题

课件特别强调，并不是所有不变表达式都能机械外提，必须考虑安全性。下面是两种不可以外提的问题：

除法表达式

若表达式可能因为运行时条件不同而出现除零异常，则不能简单外提。

例如在循环中：

若 a / y 看起来不变
但 y 可能为 0
外提后就会把原本只在某些路径上执行的除法提前执行

这会改变程序行为。

赋值表达式

赋值表达式不能因为右部不变就外提，因为外提会改变赋值发生的时机和次数。

外提策略

两种策略：

凡是循环不变式都外提
只外提一定会执行的循环不变式

第二种更保守，也更安全。

外提算法

分两遍扫描循环体。

第一遍：

扫描循环体四元式
建立 LoopDef 表
凡是在循环体中被定义的变量都加入 LoopDef

第二遍：

再扫描循环体
遇到运算型四元式 (ω, A, B, t)
若 A、B 都不在 LoopDef 中，则认为这是循环不变式
把它移到循环外部适当位置

两个例子。

第一个例子中，像 2*k、(2*k)*2、2*k + 2*k*2 这类只依赖 k 的表达式，在循环中不会变化，因此可以全部外提。

第二个例子是二维数组地址计算。若数组某一维下标在循环中不变，则相应的地址偏移计算可以先移到循环外，从而减少循环内的乘法和加法开销。

这说明循环优化不只针对算术表达式，也非常适合优化数组下标地址计算。

要不然没法展开。
↖

课程笔记

#编译原理

编译原理课程笔记

https://blog.kisechan.space/2026/notes-compilers/

作者

Kisechan

发布于

2026年6月17日

更新于

2026年6月25日

许可协议

我消沉的两个月里上一篇

一些精神药物的服用体验下一篇

编译原理课程笔记

概论

高级语言的实现

编译方式

解释方式

转换方式

编译程序的组成

词法分析

词法分析器

符号和符号串

长度

连接

方幂

正则表达式

正则表达式描述单词

正则表达式的局限性

注意事项

确定有限自动机 DFA

DFA 的表示方式

陷阱状态

DFA 接受的字符串

DFA 描述单词

DFA 的程序实现

NFA 的确定化

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

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

DFA 的化简

无关状态

等价状态

状态分离法

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

正则表达式到 NFA

NFA 到正则表达式

语法分析

文法

文法的分类

上下文无关文法 CFG

推导、句型、句子与语言

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

语法分析树

二义性文法

文法等价变换

增加拓广产生式

消除空产生式

消除不可达产生式

消除特型产生式

消除公共前缀

消除左递归

直接左递归

间接左递归

语法分析的功能

语法错误处理

紧急方式恢复

短语级恢复

出错产生式

全局纠正

自顶向下分析

First 集

Follow 集

Predict 集

用 First 判断

用 Follow 判断空产生式

用 Predict 统一判断

自顶向下分析的条件

First(X) 的求法

First(α)\text{First}(\alpha)First(α) 的求法

Follow(A)\text{Follow}(A)Follow(A) 的求法

Predict(A→β)\text{Predict}(A \to \beta)Predict(A→β) 的求法

表达式文法例子

递归下降分析方法

基本思想

一般写法

例子

递归下降分析的特点

LL(1) 分析方法

基本思想

LL(1) 分析的动作

LL(1) 分析表

LL(1) 驱动器算法

表达式文法实例

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

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

`First` 集

`Follow` 集

`Predict` 集

用 `First` 判断

用 `Follow` 判断空产生式

用 `Predict` 统一判断

`First(X)` 的求法

$\text{First}(\alpha)$ 的求法

$\text{Follow}(A)$ 的求法

$\text{Predict}(A \to \beta)$ 的求法

`LL(1)` 分析方法

`LL(1)` 分析的动作

`LL(1)` 分析表

`LL(1)` 驱动器算法

`LL(1)` 分析和递归下降的关系

层数 `Level`

偏移量 `Offset`

常量定值表 `ConstDef`