NOTE
还未校对，部分地方有歧义基本涵盖了PPT里的重点内容与考点

编译概论#

编译程序工作的五个阶段#

\text{词法分析} \rightarrow \text{语法分析} \rightarrow \text{语义分析/中间代码产生} \rightarrow \text{中间代码优化} \rightarrow \text{目标代码产生/优化}

分析（前端）：词法分析、语法分析、语义分析、中间代码生成。
综合（后端）：中间代码优化、目标代码生成、目标代码优化

编译器由符号表进行管理，每一个阶段都可以连接错误输出

符号表#

一个表项包括：名字+属性信息（key, value）。一般通过Hash构造或线性构造，进行的操作主要是Hash查找、二分查找、线性查找。

符号表的使用时机：定义性出现（int a）与使用性出现（a = 10），词法分析器与语法分析器都会依赖符号表

编译与解释的区别#

解释：数据+源程序流入解释器生成输出
编译：源程序流入编译器先生成可执行文件，再结合数据得到输出

NOTE
几种量的区别：
标识符：函数名，结构名
常量：浮点数，整数
变量：数组元素

一、词法分析#

遵循原则：构词规则
描述工具：有限自动机

编译原理中，词法分析器是第一个把字符流变成有意义单元的组件。它的理论基础是正则语言与有限自动机。词法分析是编译原理中最优雅的部分之一是，它把一个看似工程化的任务，变成了正则表达式、NFA、DFA 三者之间的等价变换。

0. 词法分析器概述#

词法分析器的输出

输出的单词符号的表示形式（单词种类与自身值）

NOTE
单词种类通常用整数编码表示：

基本字、运算符、界符是一符一码，因为该种别只有这一个单词符号

标识符、常数，给出种别编码和自身的值，采取一类一码：

标识符单列一种，自身值表示为按机器字节划分的内部码

常数按类型分一种：值表示为标准的二进制形式

单词符号种类：

基本字符
标识符
常数
运算符
界符：逗号、分号、括号

1. 词法单元、词素与模式#

词法分析器的输入是源程序的字符流，输出是 token 流。
前置概念：

词法单元 / token：一个 token 类，例如 ID、NUM、IF。
词素 / lexeme：源程序中实际出现的字符串，例如 foo、42。
模式 / pattern：描述一个 token 类所有合法词素的规则，通常用正则表达式表示。

一个 token 可以看作二元组：

\langle \text{token class}, \text{attribute value} \rangle

例如输入 A:= B50 + 10 可能被识别为：

1
(ID, "A")
2
(OpAssign, -)
3
(ID, "B50")
4
(OpAdd, -)
5
(Integer, "10")
6
(Semicolon, -)

也就是说，Token 通常可以带一个 attribute（属性），告诉后面阶段这个 Token 对应的具体信息。

2. 正则表达式与正则定义#

正则表达式是描述词法模式的标准工具。
设 $\Sigma$ 是有限字母表（ $\Sigma *$ 表示 $\Sigma$ 上的所有字的全体）。正则表达式最基本只有三种运算：

r | s：二选一
rs：先匹配 r, 再匹配 s
r*：r 重复 0 次或多次

NOTE
这里先提一下 $\varepsilon$ ， $\varepsilon$ 表示空串，里面什么字符都没有（长度为0），但是是一个合法字符串，这里和空集 ∅ 是两回事（∅ 一个字符串都没有）

优先级为：* > 连接 > |，括号可以改变优先级。常用扩展如 +、?、字符类 [a-z] 都可以归约到上述基本运算。

3. 有限自动机#

有一个有限状态集合和一些从一个状态通向另个状态的边，每条边表示一个记号，其中一个状态是初态，某些状态是终态

3.1 NFA 与 DFA#

NFA 的非确定并非随机。其实它只是说，同一输入可能有多条路径，只要存在一条接受路径即可。NFA 是非确定的选择，不是概率。

3.2 正则表达式 → NFA：Thompson 构造#

正则表达式就是一个规则，结合识别机器DFA/NFA用来判断一个输入字符串是否可以被识别

Thompson 构造法用结构归纳把正则表达式转换为 NFA。

基本构造：

$\varepsilon$ ：一个开始状态，一个接受状态，一条 $\varepsilon$ 边。

复合构造：

并 $r|s$ ：新建开始状态，用 $\varepsilon$ 边连到两个子 NFA 的开始；两个子 NFA 的接受状态各用 $\varepsilon$ 边连到新建接受状态。
连接 $rs$ ： $r$ 的接受状态用 $\varepsilon$ 边连到 $s$ 的开始。
闭包 $r^*$ ：新建开始状态和接受状态；新开始状态用 $\varepsilon$ 边连到 $r$ 的开始和新接受状态； $r$ 的接受状态用 $\varepsilon$ 边连到 $r$ 的开始和新接受状态。

并、闭包的具体 Thompson 构造（具体画法看ppt）：

1
r|s
2

3
        ε → [a] → ε
4
      ↗             ↘
5
start                 accept
6
      ↘             ↗
7
        ε → [b] → ε

1
a*
2

3
           ε ┌──────────────┐
4
             ↓              │
5
(start) ──ε→ [ NFA(a) ] ──ε────→ (accept)
6
   │                       ↑
7
   └──────────────ε────────┘

NOTE
这里区分一下状态转换图，圆圈表示状态，其中双圆圈为终态，双圈旁加星号表示要退掉最后一个字符，单独的双圈可以用来识别ε

画画 a(b|c)* 的 NFA 结构练习一下

DFA不支持ε跳转

DFA 确定的有限自动机#

确定的有限自动机是一个五元式 $M = (S, \Sigma, f, S_0, F)$ ，其中：

S：有穷状态集
$\Sigma$ ：输入字母表（有穷）
f：状态输入函数，只会映射唯一后继状态
S0：是唯一初态
F：终态集（可空）

NFA#

与DFA的主要区别：状态转换函数，S0为非空初态集

3.3 NFA → DFA：子集构造（重要）#

NFA 便于构造，但模拟效率低；DFA 判定每个字符只需一次状态转移。因此需要把 NFA 转换为 DFA。
核心思想：DFA 的一个状态对应 NFA 的一个状态集合。

[!question] 为什么 DFA 可以把 NFA 的整个状态集合当成一个状态？
比如当前读入 a，NFA 的状态可能从 q1, q2, q3 变到 q2, q4，我们并不需要知道 NFA 到底在哪个状态，因为 NFA 本来就不要求我们做出唯一选择，我们只需要记住读到这里时，所有可能到达的状态有哪些。所以 DFA 把 {q1, q2 ,q3} 当做一个状态，然后 {q1, q2 ,q3} —a—> {q2, q4}，即 DFA 把 NFA 的多条可能路径压缩成了一个确定的集合状态，这便是子集构造

定义两个操作：

$\varepsilon\text{-closure}(s)$ ：从状态 $s$ 只经过 $\varepsilon$ 边可达的所有状态集合，包括 $s$ 自身（因为他们不消耗输入字符）
$\text{move}(T, a)$ ：从集合 $T$ 中任意状态经过输入 $a$ 可达的状态集合。（move 得到的结果不包括自身，注意别忘了每次 move 完还要看当前点有没有相关的 ε 边

子集构造算法：

先从起始位置通过 closure 得到 DFA 的初始状态，接着通过move + closure组合形式进行下去直到得到最终状态（含有NFA终态的状态），closure 每次 move 完都要做一遍。而每一次得到的集合都可以作为DFA的一次状态，分别对每一个状态分析即可。

最坏情况下，DFA 状态数可能是 NFA 状态数的指数级（ $2^n）$ 。但真实编程语言的词法模式通常不会触发最坏情况，本质就是子集构造只会生成实际从初始状态出发、沿着输入字符能够到达的那些状态集合

给一个课上的例子：

例题

由NFA绘制DFA状态图

将 DFA/NFA 不断消除中间状态的弧，只保留X指向Y的弧，那么弧上的就是正则表达式，这是DFA、NFA到正则表达式的转换

3.4 DFA 最小化（好像不重要）#

子集构造得到的 DFA 可能包含冗余状态。最小化可以让自动机更紧凑，也能暴露不同正则表达式之间的本质等价性。
DFA 最小化最核心的思想：
如果两个状态对所有可能的后续输入产生完全相同的接受结果，那么它们就是等价状态，可以合并。
最小化算法的基本步骤（不断划分集合状态）：

移除不可达状态。
初始划分为接受状态和非接受状态
反复分裂：若同一组中的状态在某个输入符号上转移到不同组，则按转移目标组分裂该组。
直到没有组可以分裂。

最终每个划分组成为最小 DFA 的一个状态。理论上，最小 DFA 在同构意义下是唯一的。这也是正则语言理论的一个漂亮结论。

4. 多规则与最长匹配（好像不重要）#

真实词法分析器需要同时识别多种 token，例如 if、id、num、<= 等。
合并方法：

为每个 token 类构造 NFA。
新建一个总开始状态，用 $\varepsilon$ 边连到所有规则 NFA 的开始状态。
对合并后的 NFA 做子集构造，得到 DFA。
每个 DFA 接受状态关联一个或多个规则及其优先级。

此时出现两个问题：

不同规则可能有公共前缀，例如 if 与 identifier。
一个字符串可能有多个可接受前缀，例如 >= 可以被识别为 > 后接 =。

实际词法分析器采用两个原则：

最长匹配：在输入上模拟 DFA，直到无法继续；然后回溯到最近经过的接受状态。
优先级：如果最近接受状态对应多个规则，选择优先级最高的规则。

最长匹配保证了 >= 不会被切分为 > 和 =；优先级保证了关键字不会被识别为标识符。

二、语法分析#

遵循原则：语法规则
描述工具：上下文无关文法

语法分析包含三个部分：文法，自上而下分析，自下而上分析

1. 文法#

NOTE
文法考点：语法树，从文法推导出语言，文法分类。

1.1 文法的分类#

0 型文法：产生式基本没有限制，只要左部至少包含一个非终结符即可，对应图灵机
1 型文法：上下文有关文法，要求左部长度小于右部长度，即不会越改越短，对应线性有界自动机
2 型文法：上下文无关文法，左边必须是一个单独非终结符，对应下推自动机
3 型文法：正规文法。具有右线性与左线性，对应有限自动机 DFA / NFA

3\text{型} \subset 2\text{型} \subset 1\text{型} \subset 0\text{型}

2. 上下文无关文法#

一个上下文无关文法 $G$ 是一个四元组：

(V, \Sigma, R, S)

$V$ ：非终结符集合
$\Sigma$ ：终结符集合（与 $V$ 不相交）
$R$ ：产生式集合，形如 $A \to \alpha$ ，其中 $A \in V$ ， $\alpha \in (V \cup \Sigma)^*$ 。产生式是一个有序对偶
$S \in V$ ：开始符号，通常就是选取的一个非终结符作为开始符号

$V^*$ 等同于闭包效果， $V^+$ 表示至少出现一次

2.1 标准CFG#

program \rightarrow stmt_list | \varepsilon

对于上式，也可以写成： $program \rightarrow \{stmt\}$ ，大括号里的部分表示重复0次或无数次

常见的推导中，stmt, while_stmt, assign_stmt, bool_expr, expr等等都属于非终结符
WHILE, ID, NUMBER等等属于终结符，这里的三者其实就是词法分析器产生的 token 类型

2.2 推导#

CFG 的核心动作便是推导（其逆过程称为归约）：就是不断用产生式，把非终结符替换掉，直到得到完整的终结符串，于是精确定义了一套合法字符串的生成规则。

推导过程中，如果每一步都替换最左边的非终结符，称为最左推导，优先生成树的左边，应用场景是自顶向下解析（LL分析法）；
替换最右边的称为最右推导。最右推导又称规范推导，优先生成树的右侧，应用场景自底向上解析（LR分析法）

最右推导（规范推导）的逆过程为最左归约（规范归约）
最左推导的逆过程称为最右归约

NOTE
如果有 $aSb \rightarrow aXYb$ ，能否替换 $xxaSbyy$ ？
不能！因为其前者 $aSb$ 压根不是产生式，CFG 里面规定产生式的左部只能有一个非终结符，标准的生产式： $A \rightarrow aXYb$

NOTE
$a^nb^n$ 可以由上下文无关文法推出，而 $a^nb^nc^n$ 不能由上下文无关文法产生，因为后者不能确定三个 n 相等

2.3 产生式#

句型与句子的辨析#

推导的过程就是从开始符号S出发，产生一系列句型，直到最终产生一个句子的过程。

即：如果 $S \to \alpha$ ，则称 $\alpha$ 是一个句型。

句子是句型的一种特殊情况，即不包含任何非终结符的句型

一些常见的产生式#

设文法 $G_1(S)：$

S \to AB \\ A \to aA | a \\ B \to bB | b

则其产生的语言是：

\bm{L(G_1) = \{a^mb^n | m, n > 0 \}}

设文法 $G_2(S)$ :

S \to aSb | ab

则其产生的语言是：

\bm{L(G_2) = \{a^nb^n | n \ge 1\}}

3. 语法树与二义性#

3.1 语法树#

语法树是推导的图形表示：根是开始符号，内部节点是非终结符，叶子是终结符。一个推导对应一棵语法树，但不同的推导顺序可能对应同一棵树。例如，最左推导和最右推导通常对应同一棵语法树。

3.2 文法二义性#

如果一个文法存在某个句子对应两棵或更多不同的语法树（二义性看树，不看推导过程），则称该文法是二义文法。经典的例子是悬空 else 问题

这里给一个详细的例子说明悬空 else 问题

S \to iCtS | iCtSeS | a \\ C \to b

把符号翻译一下就是：

1
i = if
2
t = then
3
e = else
4
a = 普通语句

如果现在我们要构造一个可能产生歧义的句子：if b then if b then a else a，那么最后的 else 到底属于哪一个 if？

第一种理解，else 属于内层 if：
```
1
if b then
2
  if b then
3
      a
4
  else
5
      a
```
对应推导： $S \to iCtS \to ibtS \to ibtiCtSeS \to ibtibtSeS \to ibtibtaea$
第二种理解，else 属于外层 if
```
1
if b then
2
  if b then
3
      a
4
else
5
  a
```
对应推导： $S \to iCtSeS \to ibtSeS \to ibtiCtSeS \to ibtibtaea$

如果你画出这两个推导的语法树会发现，虽然他们得到的是同一个字符串，但是语法树明显不同，这便是语法的二义性（同一个句子存在两个不同的语法树）

NOTE
语法分析器并不是构造一个完整的树之后才给后面的，也就是说语法分析器并不是构成一个完整的遍，它得到一个子树，就给后续部分做翻译。拿到一个单词，能够构成一个语法单位，使用这个语法单位做翻译。

4. 自顶向下分析#

自顶向下分析从开始符号出发，尝试构造一个最左推导，使得叶子序列与输入 token 流匹配。最直观的实现是递归下降，但回溯代价高。预测分析通过提前查看输入符号来消除回溯，典型代表是 LL(1) 文法。

这里记住一个点，自上而下分析面临的问题：回溯问题，文法左递归问题

回溯问题：当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的，出错时，不得不回溯

4.1 消除直接左递归与间接左递归（重要）#

直接左递归：原生产式： $E \to E\alpha|\beta$

左递归变右递归：

E \to \beta E' \\ E' \to \alpha E' | \varepsilon

扩展到多个候选，假定E的全部生产式为：

E \to E\alpha_1 | E\alpha_2|...|\beta_1|\beta_2...

则应更改为：

E \to \beta_1 E' | \beta_2 E' | ... \\ E' \to \alpha_1 E' | \alpha_2E'|...|\varepsilon

间接左递归：A -> Ba | d , B -> Ab | c ，将其展开为直接左递归 A -> Aba | ca | d，然后进行直接左递归消除：

1
A ->  ca A' | d A'
2
A' -> Aba A' | ε

例题：消除文法 $G(S)$ 的左递归

S \to Qc | c \\ Q \to Rb | b \\ R \to Sa | a

将 S 展开：

S \to Sabc| abc | bc | c \\ \text{然后按照直接左递归操作：} \\ S \to abcS' | bcS' | cS' \\ S' \to abcS' | \varepsilon

4.2 FIRST 和 FOLLOW 集合（重要）#

预测分析需要两个集合：

$\text{FIRST}(\alpha)$ ：可以从 $\alpha$ 推导出的所有串的首终结符集合。例如 $E \rightarrow +numE|\varepsilon$ 。那么 $\text{FIRST}(E)=\{+, \varepsilon \}$
$\text{FOLLOW}(A)$ ：可能在某些句型中紧跟在非终结符 $A$ 之后的终结符集合。如果 $A$ 后面跟着非终结符 $B(\text{同时}，B \rightarrow b)$ ，那么 $\text{FOLLOW}(A) = \text{FIRST}(B) = \{b\}$

计算 FIRST 的规则#

若 $X$ 是终结符，则 $\text{FIRST}(X) = \{X\}$ 。
若 $X \to \varepsilon$ 是产生式，则 $\varepsilon \in \text{FIRST}(X)$ 。
若 $X \to Y_1 Y_2 \cdots Y_k$ ，则将 $\text{FIRST}(Y_1)$ 中除 $\varepsilon$ 外的元素加入 $\text{FIRST}(X)$ ；若 $Y_1$ 能推出 $\varepsilon$ ，则继续加入 $\text{FIRST}(Y_2)$ ，依此类推；若所有 $Y_i$ 都能推出 $\varepsilon$ ，则 $\varepsilon \in \text{FIRST}(X)$ 。

这里给一个简单例子：

给定文法：

S \to AB \\ A \to aA | \varepsilon \\ B \to bB | C \\ C \to c | \varepsilon

则：

\text{FIRST}(A) = \{a, \varepsilon\}\\ \text{FIRST}(B) = \{b, c, \varepsilon\} \\ \text{FIRST}(S) = \{a, b, c, \varepsilon\} \\

总结下来：FIRST从底层开始求，比如在上面的例子里，我们先求A 和 B 的 FIRST，之后求 S 比较好求，只用代入 FIRST(B) 即可。

公共左因子#

公共左因子指的是同一个非终结符的多个产生式右部，具有相同的非空前缀符号串

很简单，例如： $A \to ab | ac | \gamma_1|\gamma_2$ ， $a$ 便是公共左因子

我们可以提取上式的公共左因子，于是得到

A \to aA'| \gamma_1 | \gamma_2 \\ A' \to b | c

这样做的目的是：经过反复提取左因子，就能够把每个非终结符(包括新引进+者)的所有候选首符集变成为两两不相交

计算 FOLLOW 的规则#

将 $（输入结束标记，也可写为 #）放入 FOLLOW(S)
若存在产生式 $A \to \alpha B \beta$ ，则 $\text{FIRST}(\beta)$ 中除 $\varepsilon$ 外的元素加入 $\text{FOLLOW}(B)$ 。
若存在产生式 $A \to \alpha B$ ，或 $A \to \alpha B \beta$ 且 $\beta \Rightarrow^* \varepsilon$ ，则 $\text{FOLLOW}(A)$ 加入 $\text{FOLLOW}(B)$ 。

FOLLOW 总结下来就是：
FOLLOW 不包含ε
看某个非终结符B时，只看它在产生式右边出现的位置

如果B后面有东西，把后面的整体的 FIRST 除 ε 外加入 FOLLOW(B)

如果B后面没有东西，或者后面有东西且整体可以推导出ε，把左边非终结符的 FOLLOW 加入 FOLLOW(B)

开始符号的 FOLLOW 放 $

典例：
有如下产生式，计算 FOLLOW 和 FIRST 集合

\begin{aligned} E &\rightarrow T E' \\ E' &\rightarrow +TE' \mid \varepsilon \\ T &\rightarrow FT' \\ T' &\rightarrow *FT' \mid \varepsilon \\ F &\rightarrow (E) \mid id \end{aligned}

计算得：

\begin{aligned} \mathrm{FIRST}(F) &= \{(,\,id\} \\ \mathrm{FIRST}(T') &= \{*,\,\varepsilon\} \\ \mathrm{FIRST}(T) &= \{(,\,id\} \\ \mathrm{FIRST}(E') &= \{+,\,\varepsilon\} \\ \mathrm{FIRST}(E) &= \{(,\,id\} \end{aligned}

\begin{aligned} \mathrm{FOLLOW}(E) &= \{\$,\,)\} \\ \mathrm{FOLLOW}(E') &= \{\$,\,)\} \\ \mathrm{FOLLOW}(T) &= \{+,\,\$,\,)\} \\ \mathrm{FOLLOW}(T') &= \{+,\,\$,\,)\} \\ \mathrm{FOLLOW}(F) &= \{*,\,+,\,\$,\,)\} \end{aligned}

4.3 预测分析表与 LL(1) 文法#

LL(1)递归下降分析法 说的是：从左往右读，使用最左推导，只向前看一个token。于是看到当前token就可以确定用哪一条生产式。

递归下降分析器#

分析程序由一组子程序组成，对每一语法单位(非终结符)构造一个相应的子程序，识别对应的语法单位。在分析过程中，当需要从某个非终结符出发进行推导时，就调用这个非终结符对应的子程序

预测分析表#

预测分析表 $M$ 是一个二维表，行是非终结符，列是终结符。

这里结合上面例子说明如何构建预测分析表：

\begin{aligned} E &\rightarrow T E' \\ E' &\rightarrow +TE' \mid \varepsilon \\ T &\rightarrow FT' \\ T' &\rightarrow *FT' \mid \varepsilon \\ F &\rightarrow (E) \mid id \end{aligned}

上式所对应的 FIRST、FOLLOW集:

\begin{aligned} \mathrm{FIRST}(F) &= \{(,\,id\} \\ \mathrm{FIRST}(T') &= \{*,\,\varepsilon\} \\ \mathrm{FIRST}(T) &= \{(,\,id\} \\ \mathrm{FIRST}(E') &= \{+,\,\varepsilon\} \\ \mathrm{FIRST}(E) &= \{(,\,id\} \end{aligned}

\begin{aligned} \mathrm{FOLLOW}(E) &= \{\$,\,)\} \\ \mathrm{FOLLOW}(E') &= \{\$,\,)\} \\ \mathrm{FOLLOW}(T) &= \{+,\,\$,\,)\} \\ \mathrm{FOLLOW}(T') &= \{+,\,\$,\,)\} \\ \mathrm{FOLLOW}(F) &= \{*,\,+,\,\$,\,)\} \end{aligned}

构造方法：

看每一个产生式左边的非终结符，然后找到其 FIRST 集元素，将产生式放入对应元素的下方
只看可以推导出 $\varepsilon$ 的非终结符，看它的 FOLLOW 集，把产生式（含 $\varepsilon$ 的那部分）放入对应元素下方

所以 M 可以构造为：

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

接下来真正模拟编译器

编译器识别输入的某个token，结合当前非终结符，查表即可预测出当前token是由哪一个产生式得出的

如果表中每个格子至多一个产生式，则该文法是 LL(1) 文法。LL(1) 文法是无二义的，且没有左递归和公共前缀。消除左递归和提取左因子是将文法改造成 LL(1) 的常用技术。

5. 自底向上分析#

算法优先分析法（LR分析法） 说的是，自底向上分析从输入串出发，反向进行最右推导（即自下而上分析=最右推导逆过程=规范归约=最左归约），边向栈压入单词符边找句柄边归约，直到归约为开始符号。

自底向上分析器的核心是移进-归约操作（采用思想便是移进-归约思想）：

维护一个栈，初始为空。
输入缓冲区存放剩余的 token 流。
每一步可以选择：
- 移进：将下一个输入符号压入栈。
- 归约：栈顶附近的某段符号串匹配某个产生式的右部，将其替换为该产生式的左部的操作被称为归约
- 接受：栈中只剩开始符号，且输入耗尽（输入 $）。
- 报错：无法继续。

归约时栈顶需要匹配的符号串称为句柄（更准确的说，在一个规范句型（由最右推导得到的句型）中，最左直接短语就是该句型的句柄）。在规范归约中，句柄总是出现在栈顶。而 LR 分析器就是在自动决定什么时候归约、什么时候移进

这里举一个例子，方便理解句柄是什么：

有文法：

S \to aAB \\ A \to b \\ B \to c

其最右推导为： $S \to aAB \to aAc \to abc$ ，最左直接短语（最后一次展开的）就是 b，所以 b 是句柄

在语法树中，句柄不等于最左端叶子，应该是在最右推导中某个非终结符最终展开的那部分，也就是说，句柄是树最下面最左边的可归约的那部分

NOTE
区分一下自上而下与自下而上分析

在自上而下的分析中，是选择唯一的产生式进行扩展

s在自下而上的分析中，是选择唯一正确的可规约串，当有多个可归约串的时候，避免回溯

5.1 短语#

语法树中某个非终结符推导出的连续符号串，即某个非终结符节点下面管辖的那一整段符号串集合

WARNING
非终结符也可以是非终结符的短语，中间的节点可以是它父节点的短语。但是ppt里的意思是只有末端叶子才是短语，这里有点歧义

短语说明图例

如图，The teacher 是 NP 的短语，praised the student 是 VP 的短语，以此类推

直接短语：只经过一步推导得到的子节点

6. LR 分析#

LR(k) 分析：L 表示从左到右扫描，R 表示最右推导的逆过程，k 表示向前看符号数。实践中 k=0 或 1。

LR分析器的核心是一张分析表：

ACTION[s, a]：当状态s面临输入终结符 a 时，应采取什么动作，是移进还是归约还是接受
GOTO[s, X]：当状态 s 面对非终结符 X 时，归约后进入哪个状态

LR 分析表具体流程

图中：s5 表示移进并进入 5 状态，r6 表示按照（6）产生式进行规约，acc 表示接受。下面按照这个表具体分析一遍流程，从栈和输入流的角度来看

初始栈：0（表示状态0）
输入：i * i + i #

看当前状态是 0，输入是 i，所以查表得到 s5，于是移进，并进入5状态，栈与输入发生变化
栈：0 i 5
输入：* i + i #

当前状态 5，输入 *，查表得 r6，于是按照（6）产生式归约，这时候栈弹出 i 和 5，把 F 压入栈
栈：0 F
输入：* i + i #

当前栈顶是非终结符 F，对应的状态是 0，查 GOTO 部分得 3，所以把 3 压栈
栈：0 F 3
输入：* i + i #

当前状态 3，输入 *，查表得 r4
栈：0 T
输入：* i + i #

当前状态 0，查 GOTO，得 2
栈：0 T 2
输入：* i + i #

查表得 s7
栈：0 T 2 * 7
输入：i + i #

就这样一步步走下去就行

LR 分析的性质#

总结下来，LR 分析的性质：

栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
一旦栈的顶部出现可归约串（句柄），则进行归约，同时保证栈中总是活前缀（活前缀后面提及）

上面 LR 分析性质来自 PPT，他默认栈内只有符号串没有状态，比如栈 0 T 2 * 7 在 PPT 看来就只有 T *，于是 T * 与剩下的输入字符串 i + i # 一起构成了 T * i + i #，这个式子便是一个规范句型，由最右推导得出的句型。在实际中，栈里是有状态的，PPT里只是简化了

LR 文法#

定义：如果一个文法能构成完全没有冲突的 LR 分析表，那么它就是 LR 文法，即表里面一个格子只能对应一个动作，这也表明 LR 文法不是二义的

LR(k) 文法：最多向前看 k 个输入符号

字的前缀、活前缀#

字的前缀：指字的任意首部，如字abc的前缀有ε，a，ab，abc（前缀别忘了ε）

活前缀：指规范句型的一个前缀，这种前缀不含句柄之后的任何符号（下面举例），并且句柄之后的符号一定是终结符，规范归约的过程中，保证分析栈中总是活前缀，就说明分析采取的移进、归约是正确的。

看一个简单的文法：

S \to aAd\\ A \to bc

我们做最右推导： $S \to aAd \to abcd$ ，最后一步是 $A \to bc$ ，所以活前缀最多走到 c 这里，即活前缀有 ε a ab abc。由于我们是最右推导，所以 c 后面一定是终结符，因为已经全部展开了。

6.1 LR(0) 项目与项目集规范族#

项目#

LR(0) 项目：在每个产生式的右部添加一个圆点

举个例子： $A \to XYZ$ 有四个项目，他们分别是：

A \to \cdot XYZ \\ A \to X \cdot YZ\\ A \to XY \cdot Z \\ Z \to XYZ \cdot

项目的分类：

归约项目：如上面的 $A \to XYZ \cdot$ ，表示 XYZ 已经看完了，可以进行归约
接受项目： $S' \to S \cdot$ ，这里 $S'$ 是人为添加的开始符号，即 $S' \to S$ ，目的是使文法的开始符号有唯一一个候选，防止原来的 S 有多个产生式。 $S' \to S \cdot$ 意思是整个输入已经分析完毕，可以接受（accept）
移进项目： $A \to \alpha \cdot a \beta$ ，其中 $a$ 是终结符，即圆点后面第一个字符是终结符，表示下一步可以把这个终结符移进来。
待约项目： $A \to \alpha \cdot B\beta$ ，其中 $B$ 是非终结符，即圆点后第一个字符是非终结符，表示下一步要处理非终结符，得先去处理/展开B

不难看出，项目点的位置表示我们在分析过程中看到了生产式的多大部分

NOTE
如果产生式是 $A \to a | b$ ，它有哪些项目？
$A \to \cdot a$ ， $A \to a \cdot$ ， $A \to \cdot b$ ， $A \to b \cdot$
分开写哦

识别活前缀的 NFA 和 DFA#

识别活前缀的DFA，就是 LR(0) 分析器的状态机，而 NFA 是构造这个 DFA 的中间形式。

我们前面提到，活前缀 = 不越过句柄的规范句型前缀，LR 分析器需要知道当前读到的这个字符属于哪个活前缀，于是我们需要一个识别活前缀的自动机。

那我们如何构造 DFA 呢？一共有两种方法，先介绍第一种。即先构造 NFA，再根据 NFA 构造 DFA

构造 NFA：

假设有 $X \to \alpha \cdot A \beta$ ，那么这个项目可以走到 $X \to \alpha A \cdot \beta$ ，于是这个过程可以画成自动机，即画一条含 A 的边，并指向下一个项目：（对应图中边 A 的那部分）

构造NFA识别活前缀

如果上式中 $A$ 是非终结符，即圆点后面是非终结符，有 $A \to \gamma$ ，那么引入 $\varepsilon$ 边，把 A 的全部产生式引进来（这里因为只有 $A \to \gamma$ ，所以一条 $\varepsilon$ 边足矣，如果有多个产生式，就要多条 $\varepsilon$ 边，每一条 $\varepsilon$ 指向一个项目）。对应上图边 $\varepsilon$ 的部分。

下面是一个完整的用于识别活前缀的 NFA 构造（建议自己对着图顺一遍）：

完整的构造NFA识别活前缀

那么如何通过 NFA 构建 DFA 呢？

构造项目集规范族，我们把 NFA 中通过 ε 能到达的一堆项目合并成一个 DFA 状态，如上图中的初始状态是： $\{S' \to \cdot E, E\to \cdot aA, E \to \cdot bB\}$ （这里多出来的 S’ 下面紧接着细说）， $\{S' \to \cdot E, E\to \cdot aA, E \to \cdot bB\}$ 就是一个 LR(0) 状态集。所以对于一个 DFA，每一个 DFA 状态 = 一个 LR(0) 状态集。下面是上图 NFA 所对应的 DFA：

完整的构造DFA识别活前缀

按照上图的红标路线，我们从开始状态识别 b 后，得到的下一个状态含有 $E \to b \cdot B$ 应该不难理解，那为什么还要包含剩下的两个关于 B 的项目呢？这里涉及到项目集的闭包closure概念

其实跟前一章词法分析中由 NFA 构造 DFA 的方法基本一样，在移动圆点结束后，要立即考虑后面是否有非终结符，然后把经过 $\varepsilon$ 边的所有项目加入当前状态。

这和前面的 LR 表联系在了一起，表左边的状态1，2……就是识别活前缀的DFA状态

上面开始状态为什么要多出 S’？
这是将文法 G(S) 拓广为 G’(S’)，拓广的目的就是使文法的开始符号有唯一一个候选，防止原来的 S 有多个产生式，比如现在拓广后只有一个开始符号了

有效项目与有效项目集#

对于当前活前缀 $\gamma$ ，如果存在一个最右推导 $S \Rightarrow^* \alpha A w \Rightarrow \alpha \beta_1 \beta_2 w$ 并且 $\gamma = \alpha \beta_1$ ，那么项目 $A \to \beta_1 \cdot \beta_2$ 就是 $\gamma$ 的有效项目。

例如： $I_3 = \{\ E \to b \cdot B, B \to \cdot cB, B \to \cdot d\}$ ，对于当前活前缀 b，这三个项目分别表示：

已经识别 b，现在准备处理 B
B 可以选择 cB
B 可以选择 d

所以他们都是针对活前缀 b 的有效项目，合起来便是一个有效项目集

不难看出，一个状态里放的是当前这个活前缀之后所有可能的解析情况（这是有效项目集的直觉），精髓

因此：

每个DFA状态 = 一个LR(0)项目集 = 针对某个活前缀的有效项目集

NOTE
按照PPT原话就是，项目A $\rightarrow$ $\beta_1 \cdot \beta_2$ 对话前缀 $\alpha \beta_1$ 是有效的，其条件是存在规范(最右)推导 ( $\omega$ 是终结符) $S' \overset{*}{\Rightarrow}_R \alpha A \omega \Rightarrow_R \alpha \beta_1 \beta_2 \omega$
有效项目的性质：
若项目 $A \rightarrow \alpha \cdot B \beta$ 对话前缀 $\eta = \delta \alpha$ 是有效的且 $B \rightarrow \gamma$ 是一个产生式，则项目 $B \rightarrow \cdot \gamma$ 对 $\eta = \delta \alpha$ 也是有效的

构造项目集的两个核心操作#

项目集通过闭包 closure 和状态转换函数 GO构造

$closure \to GO \to DFA$ 是构造 DFA 的另一种方法，该方法不用构造完整的 NFA，跟我们上面的方法有差别

为了识别活前缀，我们定义一个状态转换函数 GO是一个状态转换函数。 $I$ 是一个项目集， $X$ 是一个文法符号。函数值 $GO(I，X)$ 定义为：

GO(I, X) = CLOSURE(J)

这里怎么求 $J$ 呢？还是看上面给出的 DFA 例子图：

有 $I_0 = \{ S' \rightarrow \cdot E, E \rightarrow \cdot a A, E \rightarrow \cdot b B \}$ ，那我们从 $I_0$ 开始算 $GO$
$I_0$ 可能沿 $E,a,b$ 产生状态，这里先算 $GO(I_0, a)$ ，
识别 $a$ ，圆点跨过 $a$ ，得 $J=\{ E\to a \cdot A\}$ ，还没完！现在圆点后面是非终结符A，
继续做 $CLOSURE(J)$ ，把 A 的产生式的项目加入，
因此最终 $GO(i_0, a) = \{ E \rightarrow a \cdot A, A \rightarrow \cdot c A, A \rightarrow \cdot d \}$
其余的以此类推

于是我们可以直接手算 GO 来构造 DFA，不用写完整 NFA

NFA 与 DFA 等价性证明#

为什么我们直接用 $GO$ 算出来的，和前面用 NFA $\to$ DFA 得到的结果是一样的

因为： $I_0 = \varepsilon\text{-closure}(J)$

即，DFA 当前在状态 $I$ ，读入一个字符 $a$ 后，先找所有能通过 $a$ 走到的项目 $J$ ，然后再把这些项目通过 $ε$ 能到达的项目全部补进来。

而这恰恰就是 $GO(I, a)$ ，所以

$GO(I, a) = \varepsilon\text{-closure}(\text{move}(I, a))$

6.2 LR(0) 分析表构造#

LR(0) 要解决的是当前我处于哪个项目集状态？现在看到哪个输入符号？下一步是移进，归约，接收还是报错？

这里给出一个 LR(0) 分析表的构造示例

完整的 LR(0) 分析表构造示例

填分析表的具体做法如下：

只计算并罗列项目集（状态），比如得到 $I_0, I_1, I_2$

然后直接对着项目集填表，下面是对于每一种项目该如何填表的说明

如果项目 $A \to \alpha \cdot a B$ ，点后面是终结符，并且 $GOTO(I_i, a) = I_j$ ，填 $ACTION [i, a] = s_j$
如果项目 $A \to \alpha \cdot B \beta$ ，点后面是非终结符，并且 $GOTO(I_i, B) = I_j$ ，填 $GOTO[i, B] = j$
如果状态 $I_i$ 中有 $A \to \alpha \cdot$ ，那么填 $ACTION[I, a] = r_k$ ，k 是产生式编号
如果 $S' \to S \cdot$ ，那么 $ACTION[i, \#] = acc$

NOTE
LR(0) 项目本身没有向前看符号。导致只要状态里出现了 $A \to b \cdot$ 这样的项目，就可能在所有终结符上归约，这很容易与 Shift 冲突，因为可能我还有项目是 $A \to b \cdot a$ 。这便发生了移进-归约冲突。同时还可能发生更头疼的归约-归约冲突。于是有了后面的 SLR 等分析法。
例如一个项目集 $I = \{X \to \alpha \cdot b \beta, A \to \alpha \cdot, B \to \alpha \cdot \}$ ，当状态 $I$ 面临任何输入符号 a 时，若 a = b，则移进，若 a 都属于 A B 的FOLLOW，则进行归约，因此这个例子中，既有移进-归约冲突，又有归约-归约冲突。

6.3 SLR、LR(1) 与 LALR#

6.3.1 SLR 分析表的构造#

LR(0) 真包含于 SLR，即所有 LR(0) 都是 SLR，但存在 SLR 不是 LR(0)。如果一个文法通过 LR(0) 分析得出冲突，那么它就不是 LR(0) 文法，但可能是 SLR(1) 甚至是 LR(1) 文法，然后他们都属于无二义文法

举一个例子来看看 SLR 是如何解决 LR 的冲突的。

有如下项目集：

I_1 = \{S' \to E \cdot, E \to E \cdot +T \}, \\ I_2=\{E \to T \cdot, T \to T \cdot * F \}

对于被归约非终结符，已知

\text{FOLLOW}(S') = \{\#\} \\ \text{FOLLOW}(E) = \{+, ), \# \}

这两个项目都含有移进-归约冲突：

SLR(1) 的做法是：先看可以被归约成的非终结符的 FOLLOW 集，只在 FOLLOW 里的符号里填规约。

先看第一个情况，如果 E 后面跟着 +，如果进行了规约，变成了 S’，但是 + 并不是 S’ 的 FOLLOW 集元素，也就是说，如果归约后，S’ 在栈内，+ 在栈外，这两个组合在一起不是一个规范句型。第二种情况同理，如果 T 后面跟着 *，* 并不是 E 的 FOLLOW，所以不能对 T 进行归约，SLR 会规定：对于 $I_2$ 只有当下一个输入符号是 +，)，# 时，才允许把 T 归约成 E

按照这样的方法构造出的 ACTION 与 GOTO 表如果不含多重入口，则称该文法为 SLR(1) 文法。使用 SLR 分析表的分析器叫做 SLR 分析器

6.3.2 LR(1)、LALR(1)#

LR(1) 项目在 LR(0) 项目基础上增加一个向前看符号，形如 $[A \to \alpha \cdot \beta, a]$ ，表示只有在下一个输入符号是 $a$ 时才归约。LR(1) 能力最强，但状态数可能非常多。

LALR(1) 是 LR(1) 的实用折中：将 LR(1) 项目集中“同心”的状态（忽略向前看符号后相同的状态）合并，从而大幅减少状态数，同时保留大部分 LR(1) 的能力。Yacc/Bison 等工具默认使用 LALR(1)。

三、语义分析#

3.1 属性文法#

以上下文无关文法为基础，为每个文法符号配备若干属性；对于文法的每一个产生式都配备了一组属性的语义规则

3.1.1 综合属性#

非终结符的综合属性依赖于子节点的属性和自身的属性（自下而上传递信息）

3.1.2 继承属性#

子节点的继承属性依赖于父节点和兄弟节点的属性

铁律1（关于继承属性）：子节点的继承属性，通常由父节点的属性和左边兄弟节点的属性算出来。（这里只要没有特别指出，属性都包括继承和综合两种属性）
铁律2（关于综合属性）：节点的综合属性，只能由自身的属性和自己子节点的属性算出来。绝对不能用父节点的属性！（因为父节点的属性对子节点来说不可见，子是自下而上汇报的）。

语义分析里的一些常见符号：

符号	意义
`E.val`	E 的 val 属性
`E.type`	E 的 type 属性
`L.in`	L 的 in 属性
`digit.lexval`	数字 token 的实际数值
`id.entry`	标识符对应的符号表项
`:=`	计算并赋值
`print(...)`	调用打印函数
`addtype(...)`	调用设置类型的函数
`D`	声明的缩写，一个非终结符

3.2 抽象语法树#

3.2.1 S-属性文法#

仅使用综合属性的属性文法称 S-属性文法。与自下而上的语法分析器联合工作，一边语法分析，一边属性计算

3.2.2 L-属性文法#

S-属性文法包含于 L-属性文法，后者允许不同的属性出现，适合从左往右推导，也就是自上而下

3.3.3 建立抽象语法树#

mknode(op, left, right) 建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树：E → E1 + T 的语义规则为 E.nptr := mknode(‘+’, E1.nptr, T.nptr )
mkleaf(id, entry) 建立一个标识符结点，标号为id，一个域entry指向标识符在符号表中的入口：
mkleaf(num, val) 建立一个数结点，标号为num，一个域val用于存放数的值

赋值语句是创建一个以assign为根的节点，左子树是根据变量创建的叶子节点，右子树是赋值号右边的表达式翻译出来的抽象语法树的根

3.3 基于属性文法的处理方法#

语法制导翻译是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。由源程序的语法结构驱动的处理方法就是语法制导翻译方法。

对输入串的翻译就是根据语义规则进行计算

3.3.1 一遍扫描处理#

在语法分析的同时根据语义规则计算属性值

四、中间代码生成#

具体工作流：语法分析器，静态检查器，中间代码产生器，中间代码

4.1 中间语言#

常用中间语言：

后缀式
图表示
三地址代码

4.1.1 后缀式（逆波兰表示法）#

如果E是一个变量或常量，则E的后缀式是E自身。
如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1’E2’ op，其中E1’ 和E2’ 分别为E1 和E2的后缀式。
如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。

产生式	语义规则
E → E₁ op E₂	E.code := E₁.code \|\| E₂.code \|\| op
E → (E₁)	E.code := E₁.code
E → id	E.code := id

E.code表示E后缀形式
op表示任意二元操作符
|| 表示后缀形式的连接

后缀式计算：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到 k 目运算符就把它作用于栈顶的 k 个项，并用运算结果代替这 k 个项。

4.1.2 图表示#

有向无环图（DAG）与抽象语法树（AST）#

相较于抽象语法树，有向无环图消除了重复子树，是进行优化后的中间语言，为代码生成做准备

抽象语法树与有向无环图

4.1.3 三地址语句#

三地址代码可以看作抽象语法树或者DAG图的线性表示

三地址代码示例

四元式 一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2 及 result

a := b*(-c)+b*(-c) 的四元式形式

序号	OP	arg1	arg2	result
(0)	uminus	c	-	T₁
(1)	*	b	T₁	T₂
(2)	uminus	c	-	T₃
(3)	*	b	T₃	T₄
(4)	+	T₂	T₄	T₅
(5)	:=	T₅	-	a

三元式

序号	OP	arg1	arg2
(0)	uminus	c	-
(1)	*	b	(0)
(2)	uminus	c	-
(3)	*	b	(2)
(4)	+	(1)	(3)
(5)	:=	a	(4)

关于数组计算的三元式表示：

x[i] := y

序号	OP	arg1	arg2
(0)	[]=	x	i
(1)	:=	(0)	y

x := y[i]

序号	OP	arg1	arg2
(0)	=[]	y	i
(1)	:=	x	(0)

4.2 翻译模式#

翻译模式就是比属性文法更加明确地描述出各个语义规则在什么时候进行计算，属性文法更多的是描述属性之间计算的依赖关系，对于计算怎么去实现，什么时机去实现没有明确说明，如果把这些都说明了就是翻译模式，即得到语法指导的翻译模式

4.2.1 简单算术表达式与赋值语句#

place（综合属性）：表示“这个表达式算出来的结果，存放在哪里”。它相当于一个门牌号。
code（综合属性）：表示“为了算出这个表达式，需要执行的三地址代码序列”。它相当于一份待办清单。
newtemp()：申请一个新的临时变量（对应之前的 T1, T2, T3…），用来存放中间计算结果。
gen(…)：Generate（生成）的缩写。它的作用是把括号里的内容拼成一条具体的三地址代码指令（比如 T1 := a + b）。
id.place：标识符（变量名）自己的名字，比如 a、b。 E.place := E1.place：意思是“我的结果存在哪，取决于我子节点的结果存在哪”（透明传递）。

4.2.2 布尔表达式#

逻辑运算符的优先级：not > and > or

萘Naie_Char

编译概论#

编译程序工作的五个阶段#

符号表#

编译与解释的区别#

一、词法分析#

0. 词法分析器概述#

1. 词法单元、词素与模式#

2. 正则表达式与正则定义#

3. 有限自动机#

3.1 NFA 与 DFA#

3.2 正则表达式 → NFA：Thompson 构造#

DFA 确定的有限自动机#

NFA#

3.3 NFA → DFA：子集构造（重要）#

3.4 DFA 最小化（好像不重要）#

4. 多规则与最长匹配（好像不重要）#

二、语法分析#

1. 文法#

1.1 文法的分类#

2. 上下文无关文法#

2.1 标准CFG#

2.2 推导#

2.3 产生式#

句型与句子的辨析#

一些常见的产生式#

3. 语法树与二义性#

3.1 语法树#

3.2 文法二义性#

4. 自顶向下分析#

4.1 消除直接左递归与间接左递归（重要）#

4.2 FIRST 和 FOLLOW 集合（重要）#

计算 FIRST 的规则#

公共左因子#

计算 FOLLOW 的规则#

4.3 预测分析表与 LL(1) 文法#

递归下降分析器#

预测分析表#

5. 自底向上分析#

5.1 短语#

6. LR 分析#

LR 分析的性质#

LR 文法#

字的前缀、活前缀#

6.1 LR(0) 项目与项目集规范族#

项目#

识别活前缀的 NFA 和 DFA#

有效项目与有效项目集#

构造项目集的两个核心操作#

NFA 与 DFA 等价性证明#

6.2 LR(0) 分析表构造#

6.3 SLR、LR(1) 与 LALR#

6.3.1 SLR 分析表的构造#

6.3.2 LR(1)、LALR(1)#

三、语义分析#

3.1 属性文法#

3.1.1 综合属性#

3.1.2 继承属性#

3.2 抽象语法树#

3.2.1 S-属性文法#

3.2.2 L-属性文法#

3.3.3 建立抽象语法树#

3.3 基于属性文法的处理方法#

3.3.1 一遍扫描处理#

四、中间代码生成#

4.1 中间语言#

4.1.1 后缀式（逆波兰表示法）#

4.1.2 图表示#

有向无环图（DAG）与抽象语法树（AST）#

4.1.3 三地址语句#

4.2 翻译模式#

4.2.1 简单算术表达式与赋值语句#

4.2.2 布尔表达式#

4.2.3 条件语句的翻译#

目录