just for uestcer !

写在前面：

感觉不如直接去看龙书。听课无用论坚定捍卫着。

第一章是介绍相关概念，第二章拉一堆莫名其妙的概念出来串烧，但是特别乱，第三章开始才是正式内容。所以前两章差不多的了。

笔者写该死的 lr1 写的完全没时间做完考炸了，提醒后来的uu一定要注意时间安排……题目一点不难，我真的都会，就是写不完……

考试的时候一定要细心……

(emo)

第一章

解释器和编译器的区别

编译器是一个阅读一种语言，翻译成另一种语言，还能报告翻译过程中源语言错误的程序。

解释器是直接利用用户提供的输入程序与数据执行源程序中的指定操作的程序。不会通过翻译过程。

区别：

• 编译器要在运行之前先生成目标程序，解释器不会
• 编译器生成目标程序后，执行速度比解释器快
• 在生成目标程序的过程中，编译器就会检查一些错误，解释器一边执行一边检查
• 编译器生成的目标程序会依赖平台，解释程序一般只要有解释器就能执行。

共同点：

• 都是翻译程序的一种
• 都需要进行词法分析、语法分析、语义分析等前端工作
• 都会进行错误诊断

汇编器、链接器、加载器

汇编器：生成可重定位的机器代码

链接器：解决外部内存问题

加载器：把所有可执行文件放到内存中

符号表

符号表是一种数据结构（通常是哈希表、树或链表），用于存储源代码中出现的所有标识符的信息。

通常是：名字 + 属性信息（名字域 + 信息域）

标识符包括：

• 变量名
• 函数名
• 类名
• 接口名、枚举名等

表中存储的信息：

• 名称: 标识符的字符串（如 count, main）。
• 类型: 它是 int, float, 还是 void？
• 作用域 (Scope): 它是在全局定义的，还是在某个函数内部？
• 存储位置 (Memory Location): 它在内存中的相对地址（偏移量 Offset）。
• 其他属性: 数组的长度、函数的参数列表、修饰符（const, static）等。

作用：

• 用于语义检查：声明检查、重复定义检查、类型检查
• 作用域管理
• 作为目标代码生成阶段地址分配的依据

编译流程

词法分析 - 语法分析 - 语义分析 - 中间代码生成（前端结束） -（后端开始） 中间代码优化 - 目标代码生成 - 目标代码优化

每个部分做什么的：

• 对构成源程序的字符串进行扫描和分解，识别出单词符号

• 在词法分析基础上，根据语法规则，把单词符号分解成各种语法单位（语法范畴），即根据词法单元，构成语法结构进而实现（生成 ast）**。**确定输入程序在语法是否正确，生成完整的语法分析，供后续分析使用

• 类型检查、作用域检查、上下文分析（变量是否声明，是否重复定义），控制流检查，给 ast 的节点添加属性。

• 生成三地址码，用四元式、三元式的方式存储

• 进行优化（常量折叠、常量传播、公共表达式删除、死代码删除、循环优化（代码外提、强度削弱、归纳变量删除））

遍

对源程序进行从头到尾的完整扫描

现在的编译器为了解耦选择多遍。前端只需关注语言特性，后端只需关注机器特性，中间的优化Pass可以共享。

前后端划分依据：前端依赖源语言，后端依赖目标机器

词法分析器和语法分析器可以并列（先进行完全的词法分析，再语法分析），也可以前者作为后者的子程序（分析一个 token 交给语法分析器一个 token）。

第二章

什么是语言（文法）

• 文法：一套描述语言的规则
• 语法分析方法

自上而下：推导

自下而上：归约

递归下降分析

AST 构造

符号表

中间代码生成

第三章

词法分析

单词符号的种类：关键字、标识符、常数、运算符、界符

输出格式：单词种类 + 单词的值 & 属性

• 关键字/运算符：通常一符一码，值为空。
• 标识符/常数：一类一码，值为具体字符串或数值。

正则表达式

其实是三型文法。

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义(表示)一个语言，记为L(r )。 这个语言也是根据r 的子表达式所表示的语言递归定义的：

• ε是一个RE，L(ε) = {ε}
• 如果 a∈∑，则a是一个RE，L(a) = {a}
• 假设 r和 s都是 RE，表示的语言分别是 L(r)和L(s)，则
  • r|s 是一个RE，L( r|s ) = L(r)∪L(s)
  • rs 是一个RE，L( rs ) = L(r) L(s)
  • r* 是一个RE，L( r* )= (L(r))*
  • (r) 是一个RE，L( (r) ) = L(r)

DFA & NFA

DFA : $ M = (S, \Sigma ,f, S_0, F ) $

有穷状态集合、有穷的输入字母表、状态转换函数、初态、末态（可为空）

状态转换函数 $f$ 是 (s, a) -> s 的单值部分映射 ($S \times \Sigma \to S$)。$f(s, a) = s’$ 代表当前状态为 s，输入为 a 的时候状态转移到 s‘

NFA 定义与 DFA 基本一致，但是初态不唯一，且状态转换函数有区别（DFA 是对于输入的符号进行唯一跳转，但是 NFA 不是唯一跳转）：

$$f: S \times (\Sigma \cup {\epsilon}) \rightarrow 2^S$$ 是 (s, a) -> {si} 的部分映射（可以一对多）

证明 正则表达式 $\Leftrightarrow$ NFA $\Leftrightarrow$ DFA:

正则表达式 $\Rightarrow$ NFA(thompson)

基础情况 (运算符数目为0)：

• 若 $r = \epsilon$（空串），构造一个由初态直接通过 $\epsilon$ 到终态的NFA 。
• 若 $r = a$（字符），构造一个由初态通过输入 $a$ 到终态的NFA

归纳步骤 (假设运算符少于k成立，证明k也成立)：

• 并集 ($r_1 | r_2$)：引入新的初态 $q_0$ 和终态 $f_0$。从 $q_0$ 引出两条 $\epsilon$ 弧分别连接到 $NFA(r_1)$和 $NFA(r_2)$ 的初态；将 $NFA(r_1)$ 和 $NFA(r_2)$ 的终态引出 $\epsilon$ 弧连接到 $f_0$ 。
• 连接 ($r_1 \cdot r_2$)：将 $NFA(r_1)$ 的终态与 $NFA(r_2)$ 的初态重合（或用 $\epsilon$ 连接），初态为 $r_1$ 的初态，终态为 $r_2$ 的终态 。
• 闭包 ($r_1^{*}$)：引入新初态 $q_0$ 和新终态 $f_0$。
  1. $q_0$ 到 $NFA(r_1)$ 初态连 $\epsilon$ 弧。
  2. $NFA(r_1)$ 终态到 $f_0$ 连 $\epsilon$ 弧。
  3. $NFA(r_1)$ 终态反向连回其初态（实现循环）。
  4. $q_0$ 直接连 $\epsilon$ 到 $f_0$（实现0次匹配）。

NFA $\Rightarrow$ 正则表达式

预处理：对NFA $M$ 进行改造，引入新的唯一初态 $X$ 和唯一终态 $Y$。$X$ 通过 $\epsilon$ 连接原所有初态，原所有终态通过 $\epsilon$ 连接到 $Y$ 。

状态消除 (分裂与合并规则)：反复利用以下规则消除中间节点，直到只剩 $X$ 和 $Y$：

• 串联：若有 $i \xrightarrow{r1} j \xrightarrow{r2} k$，可合并为 $i \xrightarrow{r1r2} k$ 。
• 并联：若有 $i \xrightarrow{r1} j$ 和 $i \xrightarrow{r2} j$，可合并为 $i \xrightarrow{r1|r2} j$。
• 自环：若 $j$ 上有自环 $r2$，且有 $i \xrightarrow{r1} j \xrightarrow{r3} k$，则消除节点 $j$ 后变为 $i \xrightarrow{r1r2^*r3} k$。

结论：最后 $X \to Y$ 弧上的标记即为等价的正则表达式。

DFA $\Rightarrow$ NFA

由定义知可得

NFA $\Rightarrow$ DFA （子集构造法）

核心逻辑：DFA 的每一个状态对应 NFA 的一个状态子集。因为 NFA 的状态集 $S$ 是有限的，其幂集 $2^S$ 也是有限的，所以一定存在一个等价的 DFA 。

• 构造步骤：

  1. 计算 $\epsilon$-闭包 ($\epsilon$-closure)：定义 $\epsilon$-closure(I) 为状态集 I 中任意状态经过任意条 $\epsilon$ 弧能到达的所有状态的集合 。

  2. 确定DFA初态：DFA 的初态是 NFA 初态集合的 $\epsilon$-闭包 。

  3. 计算状态转换：对于 DFA 的某个状态 $I$（它实际上是 NFA 的一个状态子集）和输入符号 $a$，计算 DFA 的下一个状态 $J$：

     $$J = \epsilon\text{-closure}(\text{move}(I, a))$$

     其中 $\text{move}(I, a)$ 是从集合 $I$ 出发经过边 $a$ 能直接到达的 NFA 状态集合 。

  4. 确定DFA终态：如果 DFA 的某个状态（即 NFA 的状态子集）中包含了 NFA 的任何一个终态，则该状态被标记为 DFA 的终态 。

  5. 重复：重复上述过程直到没有新的 DFA 状态产生。

结论：通过子集构造法，我们证明了对于任何 NFA，都存在一个识别相同语言的 DFA 。

DFA 最小化

1、分成两个集合，接受状态与非接受状态

2、对于每个集合，检查里面每一个状态，进行转移的所有行为是不是一致的。例如 2 3 状态在接受 1 的时候都去到了同一个集合 A 内的元素（a，b），就认为这个行为是一致的。不一致就分裂出来，不断进行。

3、然后每个集合只选择一个作为代表

第四章

文法

概念

描述语言结构（语法）的“形式化规则系统“。形式化地描述：一个四元组：$G = (V_T, V_N, S, P)$，分别是终结符、非终结符、开始符号、产生式集合，

分类

分为四类文法：

• 0 型文法：产生式 $\alpha \to \beta$ 中，$\alpha$ 至少包含一个非终结符
• 1 型文法（上下文有关文法）：产生式 $\alpha \to \beta$ 必须满足 $|\alpha| \le |\beta|$（产生过程长度单调不减）。 特例：$S \to \epsilon$ 允许，但 $S$ 不能出现在任何产生式的右部。例如$\xi A \eta \to \xi \gamma \eta$，其中 $|A| \le |\gamma|$
• 2 型文法（上下文无关文法）：产生式 $\alpha \to \beta$ 中，$\alpha$ 必须是一个单独的非终结符。 即：$A \to \beta$，其中 $A \in V_N$，$\beta \in (V_N \cup V_T)^*$。
• 3 型文法（正则文法）：产生式必须全是右线性或左线性的。

推导与归约

• 推导：应用产生式规则，将非终结符替换为右部符号串的过程。
• 归约：应用产生式规则，将右部符号串替换为非终结符的过程。

句型、句子、语言

• 句型：从文法的开始符号 $S$ 出发，经过 $0$ 步或若干步推导，所能得到的所有字符串，都叫句型
• 句子：没有非终结符的句型。
• 语言：一套文法所能产生的所有句子的集合

最 左/右 推导

每一步都只替换字符串中最左/右边的那个非终结符

• 最左推导（最右归约） -> 递归下降分析法
• 最右推导（规范推导） -> 最左归约（规范归约） -> LR。由规范推导产生的所有句型都是规范句型

语法树 & 二义性

语法树：推导过程的形象化描述。

二义性：如果一个文法 $G$ 的某个句子，存在两棵不同的语法树（或者说存在两个不同的最左推导），那么这个文法就是二义性的。

• 缺乏优先级规定：不同的操作符混在同一个层级的规则里。例如：$E \to E + E \mid E * E \mid \textbf{id}$ 对于 id + id * id 具有二义性
• 缺乏结合性规定：规则的两边都出现了递归符号 。例如 $E \rightarrow E + E$ 对于 1 + 2 + 3 具有二义性
• if cond1 then if cond2 then S1 else S2 这个 else S2 到底属于哪个 if？

二义性消除：引入中间非终结符，用越深优先级越高进行区分。指定规则

自上而下的语法分析（图搜索）

左递归消除 & 提取公因式

提取公因式：把所有某（一个或多个）终结符开头的式子的剩余部分用新的中间非终结符代替。

左递归消除：对于规则$$A \to A\alpha \mid \beta$$（其中 $\beta$ 不以 $A$ 开头）

我们将它改写为：$$\begin{aligned} A &\to \beta A’ \ A’ &\to \alpha A’ \mid \epsilon \end{aligned}$$

LL（1）

预测分析法：无回溯的自顶向下分析。LL1 就是预测分析法

LL1 ：从左向右扫描，多看 1 个符号，推导过程是最左推导。

判定 LL（1）能不能用：

对于每一个具有多个候选式子的 $ A\to \alpha \space | \space \beta$ ，

• $\alpha \beta$ FIRST 集合不相交.
• 最多只有一个串能推导出空串。
• 若可以推导出空串，另一条路的第一个字母不能与当前这个非终结符的下一个字母重合。（若$\beta \Rightarrow^* \epsilon$，那么 $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset$。）或者看表格，每个格子里面不能有两个式子

First & Follow 集

求之前一定要先消除左递归，否则掉左递归陷阱里了

A ->Ab|a，b并不是在 FOLLOW（A）中！

FIRST（从底向上求）：

• 如果 $X$ 是终结符，则 $\text{FIRST}(X) = { X }$。

• 处理产生式 $X \to Y_1 Y_2 \dots Y_k$：

  我们要看右边第一个符号 $Y_1$。把 $\text{FIRST}(Y_1)$ 中所有的非 $\epsilon$ 元素加入 $\text{FIRST}(X)$。$Y_1$ 打头，$X$ 自然也就以 $Y_1$ 的开头打头。

• 如果 $\epsilon \in \text{FIRST}(Y_1)$（意味着 $Y_1$ 可能消失），那么必须继续看 $Y_2$。把 $\text{FIRST}(Y_2)$ 中所有非 $\epsilon$ 元素加入 $\text{FIRST}(X)$。

  如果 $Y_2$ 也能消失，继续看 $Y_3$… 以此类推。

• 只有当 $Y_1, Y_2, \dots, Y_k$ 全都能推导出 $\epsilon$ 时，才把 $\epsilon$ 加入 $\text{FIRST}(X)$。

人话：如果你发现 X 可以产生东西，那就把产生的第一个字母加进去。如果产生的是非终结符，那么就把这个非终结符的 FIRST 集合加进去。如果第一个非终结符可以玩消失，就往后看，以此类推。如果全都可以消失（或者能直接产生 $\epsilon$ ），才把 $\epsilon $ 加入 FIRST 集

FOLLOW（从顶向下求）：

• 如果在产生式中出现 $A \to \alpha B \beta$ （$B$ 后面跟着 $\beta$）。那么，把 $\text{FIRST}(\beta)$ 中除了 $\epsilon$ 以外的所有符号，加入 $\text{FOLLOW}(B)$。
• $A \to \alpha B$ （$B$ 已经在最右边了）或者 $A \to \alpha B \beta$，且 $\epsilon \in \text{FIRST}(\beta)$ （$B$ 后面的 $\beta$ 会消失），那么把左部非终结符 $\text{FOLLOW}(A)$ 中的所有内容，加入 $\text{FOLLOW}(B)$。

人话：看所有的产生式中，这个非终结符号的下一个可能是什么。终结符直接塞进去，非终结符就把非终结符的 FIRST 集加进去，如果后面这个非终结服 FIRST 集中有 $\epsilon$ ，那么就把这个丢掉，接着看下一个字符。如果当前处理的这个非终结符可以由别的产生在末尾（$A\to aNOW$），或者变相在末尾（后面的可以为空，如 $A\to NOW\space C, \epsilon \in FIRST(C)$ ），那么就继承 A 的 FOLLOW 集合。

特别注意：FOLLOW 集中永远不会有 $\epsilon$。

​ 开始符号 $S$ 的 FOLLOW 集必须包含结束符 $$$（或 #）。

LL（1）分析表

对于文法中的每一条产生式 $A \to \alpha$：

1. 直接匹配（由 FIRST 决定）：

   计算 $\text{FIRST}(\alpha)$。对于该集合中的每一个终结符 $a$，把产生式 $A \to \alpha$ 填入表格 $M[A, a]$ 中。既然 $\alpha$ 能推导出以 $a$ 开头的东西，那看到 $a$ 自然就用这条规则。

2. 处理空串（由 FOLLOW 决定）：

   如果 $\alpha$ 可以推导出 $\epsilon$（即 $\epsilon \in \text{FIRST}(\alpha)$），那么对于 $\text{FOLLOW}(A)$ 中的每一个终结符 $b$（包括 $$$），把产生式 $A \to \alpha$（实际上通常写 $A \to \epsilon$）填入表格 $M[A, b]$ 中。 $A$ 可以消失，但前提是下一个符号 $b$ 是允许接在 $A$ 后面的。

3. 错误处理：

   所有剩下的空白格子，代表语法错误 (Syntax Error)。如果程序运行到这里，说明源代码写错了。

自下而上的语法分析（移进归约）

短语、直接短语、句柄、素短语、最左素短语

• 短语：语法树中，以任意非终结符为根的子树，其所有叶子节点组成的序列。代表了程序中的一个逻辑单元（比如一个表达式、一个语句块）。

• 直接短语：高度为 2 的子树（即直接相连的父子）的叶子序列。是当前最基础的、不可再分的逻辑单元。

• 句柄：最左边的那个直接短语。

• 素短语：至少含有一个终结符的短语，且除自身外没有更小的素短语。

• 最左素短语：句型中最左边的素短语

前缀、活前缀（构造识别文法所有活前缀的NFA）

前缀：一个字符串的任意首部

活前缀：规范句型的一个前缀，并且这个前缀不包含句柄右边的任何符号。例如对于 $A \to abc$，a、ab、abc 都是活前缀

LR（0）

从左向右推导，不向前看任何符号（只要看到栈顶构成了完整句柄（即出现了 $A \to \alpha \cdot$ 这种项目），就无脑归约）构建最右推导的逆过程。

具体方法：拓广文法、构建 DFA、构建项目集。

拓广文法

0. $S’ \to\cdot S$

添加一个确切的起点

LR(0)项目集规范族、有效项目、项目集的闭包

有效项目：描述栈里面的状态可以通过某个项目还原。例如规则 $S \to aAc$。

• 如果你刚读了个 a（栈里是 a），那么 $S \to a \cdot Ac$ 是有效的。
• 如果你读了 aA（栈里是 aA），那么 $S \to aA \cdot c$ 是有效的。
• 潜台词：一个活前缀可能有多个有效项目。LR 分析器的状态，本质上就是该状态下所有有效项目的集合。

项目集的闭包：一个算法，可以计算出一个闭包集合。这个闭包集合代表当前栈内容下，所有可能应用的项目。

假设 $I$ 是一个项目集（Item Set）。$\text{CLOSURE}(I)$ 的计算规则如下：

1. 初始： $I$ 中的所有项目都在 $\text{CLOSURE}(I)$ 中。
2. 扩散：
   • 如果 $A \to \alpha \cdot B \beta$ 在集合里（意味着：我期望下一个符号是 $B$）。
   • 那么，对于文法中所有以 $B$ 为左部的产生式 $B \to \gamma$。
   • 我们要把 $B \to \cdot \gamma$ 加入集合（意味着：既然要读 $B$，我就得做好准备从 $B$ 的开头开始读）。
3. 循环： 重复步骤 2，直到集合不再增大。

文法 $G$：

0. $S’ \to S$

1. $S \to A B$

2. $A \to C d$

3. $C \to e$

4. $C \to f$

假设我们需要构建 初始状态 $I_0$ 的闭包。

第一步：放入核心项目

我们要分析整个程序，所以起点是 $S’ \to S$。初始只有这个：$$I = { S’ \to \cdot S }$$

第二步：启动 Closure 算法

1. 检查 $S’ \to \cdot S$：

• 点后面是 $S$（非终结符）。
• 动作： 找 $S$ 的定义 ($S \to A B$)，加点，放入集合。
• 新增： $S \to \cdot A B$

当前集合：

$$\begin{aligned} S’ &\to \cdot S \ S &\to \cdot A B \end{aligned}$$

2. 检查 $S \to \cdot A B$：

• 点后面是 $A$（非终结符）。
• 动作： 找 $A$ 的定义 ($A \to C d$)，加点，放入集合。
• 新增： $A \to \cdot C d$

当前集合：

$$\begin{aligned} S’ &\to \cdot S \ S &\to \cdot A B \ A &\to \cdot C d \end{aligned}$$

3. 检查 $A \to \cdot C d$：

• 点后面是 $C$（非终结符）。
• 动作： 找 $C$ 的定义。这里有两条：$C \to e$ 和 $C \to f$。
• 新增： $C \to \cdot e$ 和 $C \to \cdot f$

当前集合：

$$\begin{aligned} S’ &\to \cdot S \ S &\to \cdot A B \ A &\to \cdot C d \ C &\to \cdot e \ C &\to \cdot f \end{aligned}$$

4. 检查 $C \to \cdot e$ 和 $C \to \cdot f$：

• 点后面分别是 $e$ 和 $f$。
• 它们是终结符。
• 动作： 没法展开了，停止。

最终结果

这就是状态 $I_0$ 的完整 Closure 集合：

$$\text{CLOSURE}(I_0) = \left{ \begin{aligned} S’ &\to \cdot S \ S &\to \cdot A B \ A &\to \cdot C d \ C &\to \cdot e \ C &\to \cdot f \end{aligned} \right}$$

LR(0)项目集规范族：所有状态的集合。$C = { I_0, I_1, \dots, I_n }$，并且列出了项目之间如何流转

具体构建方式：首先计算初始状态的 CLOSURE 集合，然后利用 DFA 构建算法，把所有可能的后续都用 GOTO 计算出来，然后针对每一个集合，再依次计算自己的 CLOSURE 集合，不断循环直到集合族稳定。

LR（0）分析表 & 冲突 & 判定

长这个样子

法则 1：填“移进” (Shift)

• 看什么： 看 DFA 中从 $I_k$ 出发的边。
• 条件： 如果有一条边标记为终结符 $a$，指向状态 $I_j$（即 $I_k \xrightarrow{a} I_j$）。
• 填什么： 在 ACTION[k, a] 中填入 $s_j$ (Shift to state j)。

法则 2：填“归约” (Reduce) —— LR(0) 的核心特征

• 看什么： 看 $I_k$ 内部包含的项目。
• 条件： 如果包含一个圆点在最后的项目 $A \to \alpha \cdot$ （假设这是文法的第 $m$ 条规则）。
• 填什么： 在 ACTION[k, 所有终结符及 $] 这一整行里，全部填入 $r_m$ (Reduce by rule m)。
• 逻辑： “只要圆点到了最后，不管下一个输入是什么，闭着眼睛归约！”（这就是 LR(0) 最“莽”的地方）。

法则 3：填“接受” (Accept) 和 GOTO

• 接受： 如果 $I_k$ 包含 $S’ \to S \cdot$，则在 ACTION[k, $] 填 acc。
• GOTO： 如果 $I_k \xrightarrow{A} I_j$（边上是非终结符），在 GOTO[k, A] 填 $j$。

填的时候有两类冲突：

移进-归约冲突：某个状态 $I_k$ 里同时存在以下两种项目：

1. $A \to \alpha \cdot a \beta$ （圆点后是终结符，想移进）
2. $B \to \gamma \cdot$ （圆点在最后，想归约）

归约-归约冲突： 某个状态 $I_k$ 里同时存在两个“归约项目”：

1. $A \to \alpha \cdot$ （规则 m）
2. $B \to \beta \cdot$ （规则 n）

判定：只要构建出来的 LR(0) 分析表中，没有任何一个单元格包含“多重定义”（即没有冲突），它就是 LR(0) 文法。

SLR（1）& 分析表构建 & 冲突

SLR：只有当下一个输入符号属于 $FOLLOW(A)$ 时，才允许用 $A \to \alpha$ 进行归约。其他完全一样。因此填表的时候：

LR(0) 的填法：遇到 $A \to \alpha \cdot$，在整行填 $r$。

SLR(1) 的填法：遇到 $A \to \alpha \cdot$，只在 $FOLLOW(A)$ 对应的列 填 $r$。其他列空着（或者填移进）。

冲突：

移进-归约冲突：在某个状态 $I_k$ 中，同时存在：

1. 移进项：$B \to \beta \cdot a \gamma$ （这告诉我：看到 a 应该移进）。
2. 归约项：$A \to \alpha \cdot$ （这告诉我：该归约了）。

这时候如果 $a \in \text{FOLLOW}(A)$ 就会冲突

归约-归约冲突：在某个状态 $I_k$ 中，同时存在两个归约项：

1. 归约项 1：$A \to \alpha \cdot$
2. 归约项 2：$B \to \beta \cdot$

如果 $\text{FOLLOW}(A) \cap \text{FOLLOW}(B) \neq \emptyset$ 就会冲突

LR(1) LALR(1)

LR（1）比 LR（0） 的项目多了一个展望符。意味：当我栈内元素和我前面一样，且我的下一个元素是我的展望符的时候，我才执行归约。

LR（1）的核心区别在于 CLOSURE 集合的计算变化了，需要多一个展望符。

例如 $$[A \to \alpha \cdot B \beta, \quad a]$$，计算 [$B \to \cdot \gamma$ ] 的展望符，应该是 FIRST（B $\beta$）

算法步骤：

1. 对于项目 $[A \to \alpha \cdot B \beta, \quad a]$：
2. 对文法中每一个 $B \to \gamma$：
3. 计算 $b \in \text{FIRST}(\beta a)$。
4. 加入新项目 $[B \to \cdot \gamma, \quad b]$。

GOTO 只需要带着展望符搬家就好了。

同心集

如果两个状态中除项目的展望符以外的所有东西都一样，那么这两个状态就是同心集，可以进行合并。

合并的时候将展望符求并集。然后修正 GOTO 的箭头即可。合并了同心集的 LR（1）就是 LALR（1）

唯一弱点是可能产生 归约归约冲突：

有了 LR1 分析是不是 SLR、LALR

判断是不是 LALR1：

寻找同心状态：

在你的 LR(1) 项目集族中，找找有没有哪两个（或多个）状态，它们的产生式部分（左部、右部、圆点位置）完全一样，仅仅是展望符（Lookahead）不同？

• 情况 A： 找不到这样的状态（所有状态的核心都是独一无二的）。
  • $\rightarrow$ 结论： 它是 LALR(1) 文法。
  • (理由：没有状态需要合并，LR(1) 表本身尺寸就等于 LALR(1) 表，既然 LR(1) 没冲突，LALR(1) 自然也没冲突。)
• 情况 B： 找到了同心状态。
  • $\rightarrow$ 动作： 在脑海中（或草稿纸上）把它们的展望符取并集，检查合并后是否会产生归约-归约冲突 (Reduce/Reduce Conflict)。

判断是不是 SLR：

前置判定： 如果刚才第一步判断它不是 LALR(1)，那么直接判死刑——它肯定不是 SLR(1)。

如果它是 LALR(1)，如何进一步检查 SLR(1)？

• 检查每一个包含归约动作的状态。
• 对于产生式 $A \to \alpha\cdot$（展望符为 $L$）：
• SLR(1) 的条件： 该状态下，这一归约动作的有效范围应该是整个 $FOLLOW(A)$。
• 冲突检查： 看看 $FOLLOW(A)$ 里包含的符号，在这个状态下是否有移进 (Shift) 动作？或者是否与其他归约动作的 $FOLLOW(B)$ 有交集？
• 简易口诀： 现在的 LR(1) 表之所以没冲突，是不是因为展望符 $L$ 是 $FOLLOW(A)$ 的一个真子集，才勉强避开了冲突？如果是“靠缩小展望符范围才避开的”，那它就不是 SLR(1)。

• 状态 A：
• $[ X \to \alpha \cdot, \quad a ]$ (遇到 a 归约 X)
• $[ Y \to \beta \cdot, \quad b ]$ (遇到 b 归约 Y)
• (这里没冲突，a 和 b 不一样)
• 状态 B（核心相同，只是展望符反了）：
• $[ X \to \alpha \cdot, \quad b ]$ (遇到 b 归约 X)
• $[ Y \to \beta \cdot, \quad a ]$ (遇到 a 归约 Y)
• (这里也没冲突)

合并成 LALR(1) 状态后：

• $[ X \to \alpha \cdot, \quad a/b ]$
• $[ Y \to \beta \cdot, \quad a/b ]$

这里产生了归约-归约冲突。我到底归约哪一个呢

第五、六章

语法

字母表：语言允许使用字符的集合

词汇：由字符组成的有限串

词法规则：哪些字符串合法 / 不合法（例如针对标识符的）

语法规则：确定句子在形式上是否合法。

单词符号的形成规则和语法规则构成了一个语言的语法

使用 CFG 来描述语法规则。

语法制导（SDD）

语法制导定义：对CFG的推广，它将每个文法符号与一个语义属性集合相关联，并将每个产生式与一组语义规则相关联。这些语义规则用于计算产生式中各文法符号的属性值。语义规则的计算并不给出，

语法制导翻译是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作

两种翻译方式：

由源程序的语法结构驱动，直接生成中间代码的处理方法就是语法制导翻译方法 （不生成 AST）

生成 AST，基于 AST 进行类型检查，然后遍历 AST 中间代码生成

属性文法

没有副作用的 SDD 也称为属性文法。

综合属性

只由子节点和自身节点决定的属性。

继承属性

由父节点和兄弟节点、自身节点决定的属性。

L 属性 SDD - 自顶向下翻译

要求 SDD 中的属性要么是综合属性，要么是左兄弟决定的继承属性，且不能成环。

S 属性 SDD - 自底向上翻译

SDD 中的属性只有综合属性。

回填

回填技术：

1. 生成跳转指令时，目标地址留空（或者填入一个链表头）。
2. 生成一个列表（List），记录所有“跳向未知目标 L”的指令地址。
3. 当终于生成到标号 L 所在的位置时（知道了 L 的指令地址），回头把列表中所有指令的目标地址都填上。

语义分析过程

静态语义检查

• 类型检查（如操作数类型应相容）
• 控制流检查（保证控制语句有合法的转向点、 goto 转入循环内部、break语句的循环语句）
• 一致性检查（多次声明标识符、数组维数是否正确、在同一作用域中标识符说明次数、case常量不能相同等）
• 相关名字检查（一个名字只能表示一个对象）

名字的作用域分析

中间代码生成

数组地址计算

以二维数组为例 (R * C)

$$地址 = base + [ \underbrace{(i - low_1) \times C}{\text{跳过的整行}} + \underbrace{(j - low_2)}{\text{本行的偏移}} ] \times w$$

对公式进行变形：

$$地址 = base + (i \times C - low_1 \times C + j - low_2) \times w$$

$$地址 = \underbrace{(i \times C + j) \times w}{\text{变动部分}} + \underbrace{(base - (low_1 \times C + low_2) \times w)}{\text{固定常数部分}}$$

推广到 k 维： $$ ((((((i_1 \times n_2 + i_2)\times n_3 + i_3) ……)\times n_k + i_k)\times w + C_{offset}\ C_{offset} = base - (\dots((low_1 \times n_2 + low_2) \times n_3 + low_3) \dots \times n_k + low_k) \times w $$ 或者可以表示为： $$ \text{地址} = \underbrace{\left( w \times \sum_{d=1}^{k} (i_d \times S_d) \right)}{\text{运行时计算 (变动部分)}} + \underbrace{\left( base - w \times \sum{d=1}^{k} (low_d \times S_d) \right)}{\text{编译期计算 (常量部分)}}\ S_d = \prod{m=d+1}^{k} n_m $$

第七章

存储时内存划分

活动记录

连接数据（保存返回地址）

形式单元：放传递参数的相关信息（value or address）

局部变量

局部数组的内情向量（可变数组）

临时工作单元（表达式语句中临时单元/中间过程）

参数传递方式

非嵌套过程语言的动态存储管理

非嵌套过程语言的栈式实现

注意，这里的 sp 指的是 fp，栈帧指针，top 才是传统意义的 sp 指针

对任何局部变量X的引用可表示为变址访问: dx[SP]

dx：编译时确定的变量X相对于活动记录起点的相对地址

动态链：指向调用自己的过程的活动记录。

栈帧（活动记录）的生命周期：

过程调用的语句P(T1, T2, …, Tn )翻译成四元式序列：

par  T1	
par  T2 	
 …	
par  Tn	
call  P，n

其中再进一步翻译：

par Ti ->(二选一)
	(i+3)[TOP]:= Ti 	    (传值)
	(i+3)[TOP]:=addr(Ti)   (传地址)
call P，n ->
1[TOP]:=SP  (保护现行SP)
3[TOP]:=n   (传递参数个数)
JSR P       (转子指令)

转进过程P后，首先执行下述指令

SP:=TOP+1        	(定义新的SP)
1[SP]:=返回地址 	(保护返回地址)
TOP:=TOP+L       (设置新TOP)

过程返回时，应执行下列指令:

TOP:=SP-1  (恢复调用前TOP)
SP:=0[SP]  	(恢复调用前SP)
X:=2[TOP]  	(把返回地址取到X中)
UJ 0[X]   	(按X返回)

嵌套过程语言的动态存储管理

静态链

在活动记录中添加一个部分，指向定义该过程的直接外层过程的活动记录的栈帧。

当 Q 想找 x（属于外层 P）时：

1. 编译器知道 x 是定义在 Q 的“上一层”的。
2. Q 顺着自己的静态链，找到了 P 的活动记录。
3. 在 P 的活动记录里，加上 x 的偏移量，就找到了！

如果要找“爷爷层”的变量，就顺着静态链走两步，以此类推。

建立过程：

情况 1：父调子（P 调用 Q）

• Q 是定义在 P 里面的。所以 Q 的外层就是 P。
• 动作：Q 的静态链 = P 自己的活动记录基址（FP/SP）。

情况 2：子调子（Q 调用 Q，递归）

• Q 定义在 P 里。现在的 Q（调用者）已经有了指向 P 的静态链。
• 新的 Q（被调用者）也需要指向 P。
• 动作：新 Q 的静态链 = 老 Q 的静态链。

情况 3：兄弟调兄弟（Q 调用 R，都是 P 的子过程）

• R 也定义在 P 里。Q 有指向 P 的静态链。
• 动作：R 的静态链 = Q 的静态链（都指向同一个爹）。

display 表

在活动记录中，添加一个全局 Display 位和局部 Display 表。

调用时，传参如前一致，跳转如下：

call P，n -->
1[TOP]:=SP     	(保护现行SP)
3[TOP]:=SP+d   (传送现行display地址)
4[TOP]:=n       	(传递参数个数)
JSR            		(转子指令)

在进入程序之后，依据全局 display 地址，把整个表按需拷贝到 display 表去。

具体而言：拷贝比当前层数浅的项，将当前项改为指向自己当前的栈帧。这样，函数内部访问局部变量时，就能通过这一项找到自己。

返回的时候：

TOP:=SP-1
SP:=0[SP]
X:=2[TOP]
UJ 0[X]

SSA 中的 $ \Phi$ 函数

注：SSA 指静态单赋值，即每个变量赋值一次。

• 定义：在控制流汇合点（如 if-else 结束后的汇合处），用于合并来自不同路径的变量版本。

• 示例：

  if (cond) x = 1; else x = 2;
  y = x;
  

  转化为 SSA：

  if (cond) x1 = 1; else x2 = 2;
  x3 = Φ(x1, x2);  // 关键点：由 Φ 函数选择 x1 还是 x2
  y = x3;
  

四元式，三元式，间接三元式

• 四元式 (Quadruples)：(op, arg1, arg2, result)。最常用，类似于汇编指令。
• 三元式 (Triples)：(op, arg1, arg2)。结果由该三元式的位置（索引）隐含表示。优化较难（因为移动代码会改变索引）。
• 间接三元式 (Indirect Triples)：使用一个指针数组指向三元式，移动代码只需交换指针。

第八章

基本块划分

三条入口规则

• 第一个句子是入口
• if … goto L 或者 goto L ，这两类语句的下一句
• 跳转语句跳转到的句子（例如 goto L 中的 L）是基本块的起点

基本块优化

DAG 块内优化

DAG 表达方式

具体操作

准备操作数的结点

（注意： [] / []= 操作顺序有要求： op arg1是数组名， arg2 是索引 i ，result 是要赋的值 / 被赋的值）

合并已知量（常量传播、常量折叠）

复写传播：两个东西一样就用同一个东西

a = 10;     // 已知量
b = a;      // 复写（b 是 a 的副本）
c = b + 5;  // 使用了副本
//复写传播就是把所有的b用a换了，常量传播就是 b = 10，c=15；

删除公共子表达式

删除无用赋值

删除死代码块

循环优化

代码外提

1、求出L的所有不变运算

2 .对每个不变运算s:A:=B op C或A:=op B或A:二B检查是否满 足条件⑴或(2)

条件⑴ (i) S所在的结点是L所有出口 结点的必经结点； (ii) A在L中其他地方未再定值; (iii) L中所有A的引用点只有S 中的A的定值才能到达。

条件(2) (i) A在离开L后不再是活跃的; (ii) A在L中其他地方未再定值; (iii) L中所有A的引用点只有S 中的A的定值才能到达。

省流：必定执行/出门就忘，只有一个地方改 A 的值，所有对 A 的引用都是使用的同一个这个 A。

3.按步骤1所找出不变运算的次序，依次把符合步骤2的条件⑴ 或(2)的不变运算s外提到L的前置结点中。但是，如果s的运算 对象(B或C)是在L中定值的，那么，只有当这些定值四元式都 已外提到前置结点中时，才能把s也外提到前置结点中。

强度削弱

把计算成本高的指令换成计算成本低的指令

把乘法变成加法，除法乘法变成位运算等

删除归纳变量

把循环变量等删掉

寄存器分配

活跃变量分析

每一个块定义四个集合：use（用到的），def（定义的），out（出口处活跃的变量），in（入口处活跃的变量）

从程序出口往入口算，每一个块的 in = out - def + use。块间：前一个的 out 等于后续所有块 in 的并集。

线性扫描

把每个变量的活跃区间写出来，然后列表、写哪一段寄存器的详细分配情况。

寄存器不够溢出的时候把右端点长的先溢出

图着色

有冲突就连线。K 个寄存器，就看度数少于 K 的节点，摘出去入栈。没有就挑选度数最大的溢出（乐观着色的话就入栈）。

然后不断弹出栈的内容，重新建图，观察邻居，尝试分配寄存器。如果之前乐观着色，有可能着色成功，就不需要溢出到内存。着色失败就需要手动把它丢到内存，溢出之后重新入栈。