第1章 概述

编译引论

基本概念

编译程序与翻译程序

**编译程序（Compiler）**是将一种语言编写的程序翻译成另一种语言程序的软件。

一般形式：

源程序（Source Program）
        ↓ 编译
目标程序（Target Program）

例如：

• C 程序 → 汇编程序
• Java 程序 → JVM 字节码
• 高级语言 → 机器语言

广义上：

• 翻译程序（Translator）：把一种语言翻译成另一种语言
• 编译程序（Compiler）：一次性翻译整个程序
• 解释程序（Interpreter）：逐条翻译并执行

源程序、源语言

源程序（Source Program）

程序员编写的程序，例如：

int a = 10;
int b = a + 5;

源语言（Source Language）

源程序使用的语言，例如：

• C
• C++
• Java
• Python

目标程序、目标语言

目标程序（Target Program）

编译之后得到的程序。

例如：

mov eax,10
add eax,5

目标语言（Target Language）

目标程序所使用的语言，例如：

• 机器语言
• 汇编语言
• 中间代码

宿主机与宿主语言

宿主机（Host Machine）

运行编译器的计算机。

例如：

x86 PC

宿主语言（Implementation Language）

编译器自身用什么语言写的。

例如：

GCC 编译器：C语言实现
Rust 编译器：Rust实现

程序执行的两个阶段

程序运行一般分为两个阶段：

编译阶段

把源程序翻译成目标程序。

C程序
 ↓
编译器
 ↓
可执行文件

运行阶段

执行生成的程序。

可执行文件
 ↓
CPU执行
 ↓
程序运行

解释型语言（如 Python）没有明显的编译阶段。

编译程序的作用

语言桥梁

编译程序连接了人更易书写的高级语言与机器可直接执行的低级语言，是软件开发走向自动化和规模化的基础。

错误检查

编译程序不仅负责翻译，还承担大量静态检查任务，例如词法错误、语法错误、类型错误和部分语义错误的发现。

程序优化

现代编译器还需要在不改变程序语义的前提下，尽可能生成更高效的代码，包括更少的指令、更低的内存占用和更快的执行速度。

编译程序的表示与分类

程序设计语言的分类方式

按描述方式分类

命令式语言强调“如何做”，程序由一系列命令组成； C,Java,Python

声明式语言强调“做什么”，更关注结果的描述而不是控制过程。 SQL, 函数式语言

按类型检查时间分类

静态类型语言在编译阶段完成大部分类型检查 C,Java

动态类型语言则将更多类型判定延后到运行阶段 Python, JavaScrip

按隐式转换能力分类

强类型语言通常限制不同类型之间的隐式混用。 C,Java,Python

弱类型语言则允许更多自动转换，但也更容易引入潜在错误。 JavaScrip

按实现方式分类

编译型语言倾向于在运行前生成目标代码

解释型语言通常边读取边执行

实际系统中，这两种方式也常结合使用，例如先编译成字节码再由虚拟机解释或即时编译。

编译器的表示方法

函数表示

编译器可以表示为函数：

T = C(S)

含义：

C：编译器
S：源程序
T：目标程序

即：

目标程序 = 编译器(源程序)

T 型图表示

T 型图常用来描述编译器、解释器、汇编器等语言处理系统之间的关系，特别适合说明交叉编译、自举编译等场景。

符号表示

符号表示法更加抽象，常用于形式化描述“某个处理程序把某种语言翻译为另一种语言，并运行在某种机器上”。

如：

C语言 → 汇编语言

编译程序的结构与编译过程

整体流程

编译过程可以理解为“分析 + 综合”的连续流水线：前几步负责把源程序拆解、检查并建立中间表示，后几步负责优化和生成目标代码。

表格管理、出错处理和遍的组织贯穿整个编译过程。符号表、常量表、类型表、标号表等表格为语义检查和代码生成提供信息；出错处理保证编译器能定位并报告错误；遍数设置则体现编译器在实现复杂度、空间开销和优化能力之间的取舍。

词法分析（Lexical Analysis）

词法分析器（扫描器）从左到右读取源程序字符流，根据语言的词法规则，识别各类单词，输出属性字流，为后续语法分析提供规范化输入。

语法分析（Syntax Analysis）

语法分析器根据文法规则判断属性字流是否构成合法句子，并构造语法树或分析树，反映程序的层次结构。

例如，赋值语句 a = b + 3 的语法树可以表示为：

text复制代码

    =
  / \
 a   +
    / \
   b   3

如果输入类似 a = + b 3，虽然每个单词可能都能被词法分析器识别，但整体结构不符合表达式文法，因此会在语法分析阶段报错。

语义分析与中间代码生成

语义分析检查程序在“形式正确”之外是否“含义正确”，例如标识符是否先声明后使用、表达式类型是否兼容。随后可进一步生成中间代码。

代码优化

优化阶段对中间表示进行等价变换，减少冗余计算，改善控制流与数据流结构，提高运行效率。

目标代码生成

目标代码生成器把优化后的中间代码翻译为汇编代码或机器代码，并处理寄存器分配、指令选择等问题。

前端与后端

前端

前端主要包含词法分析、语法分析、语义分析以及中间代码生成。它更依赖源语言特性，与目标机器关系较弱。

后端

后端主要负责优化和目标代码生成，更依赖目标机体系结构、指令系统和存储模型。设计变化最大

支撑模块

表格管理

编译过程中往往需要维护符号表、常量表、类型表、标号表等数据结构，为语义检查和代码生成提供支持。

出错处理

一个实用编译器不能在遇到首个错误时立即崩溃，而应尽量定位错误、恢复分析，并继续报告后续错误。

遍与扫描策略

一遍扫描适合结构简单、依赖少的语言；多遍扫描则更利于分阶段处理复杂语义。遍数设计需要在实现复杂度、内存占用和编译效率之间权衡。

编译程序结构的实例模型

典型结构示例

一遍编译程序

一遍编译程序边扫描边翻译，实现简单、速度快，但对语言结构限制较强，不适合复杂语义处理。

两遍与三遍编译程序

多遍结构把不同任务分散到不同阶段，更利于处理中间表示、优化和复杂语义约束。

现代编译器框架

如 Tiger 编译器和 GCC 一类系统，通常具备清晰的前端、优化器和后端分层，便于移植、扩展与复用。

编译程序的构造

构造要素

源语言

需要明确定义词法、语法和语义规则，否则编译器实现没有统一依据。

目标语言

目标语言决定生成结果的形式，可能是机器语言、汇编语言或中间语言。

编译方法与工具

常见工具包括词法分析器生成器、语法分析器生成器、优化框架和代码生成工具链。

生成方式

手工编写

直接使用某种编程语言实现编译程序，灵活性高，但工作量较大。

移植

将已有编译器迁移到新平台时，通常重点修改与机器相关的后端部分。

自编译

用某语言编写该语言自身的编译器，是编译系统成熟的重要标志。

自动生成

借助 Lex、Yacc、Bison 等工具自动生成部分编译器模块，可以显著降低开发成本。

第2章 形式语言与自动机理论基础

文法和语言

形式语言研究“符号串集合”如何被精确定义。字母表或符号表 $\Sigma$ 是符号或字符元素的非空有穷集合，$\Sigma^*$ 表示该字母表上所有有限长度符号串的集合，包括空串 $\epsilon$。

符号串常见操作包括长度、子串、前缀、真前缀、后缀、真后缀、连接和方幂；符号串集合也可以做乘积、方幂和闭包运算。闭包中常见的是正闭包和自反闭包：正闭包表示出现一次或多次，自反闭包允许出现零次，也就是包含空串。

文法通常写作：

其中 $V_N$ 是非终结符号集，$V_T$ 是终结符号集，$S$ 是开始符号或公理，$P$ 是产生式集合。用于描述另一种语言的语言称为元语言，元语言中的符号称为元语言符号。

语言本质上是字符串集合，文法是语言的形式化定义。通过产生式可以描述直接推导、多步推导和零步或多步推导：

推导还可分为最左推导、最右推导。自下而上分析中常把最右推导的逆过程称为规范规约。推导过程中出现的串称为句型，只含终结符的句型称为句子；若采用规范推导得到，则称为规范句型。

文法可能出现递归推导，包括左递归和右递归；如果递归直接出现在同一个产生式中，就称为直接递归。文法也可以用 BNF、扩展 BNF 或语法图表示。若同一个句子能对应多棵语法分析树，则文法具有二义性。

Chomsky 文法分类可以概括为：

词法分析器（扫描器）从左到右读取源程序字符流，根据语言的词法规则，识别各类单词，输出属性字流，为后续语法分析提供规范化输入。

词法分析的输入是源程序字符流，输出是 Token（属性字流）。例如：

text复制代码

源程序：
a = b + 3;

词法分析结果：
<id,a>
<=>
<id,b>
<+>
<num,3>
<;>

任务：

• 去掉空格
• 识别关键字
• 识别标识符
• 识别常数

语言的词法规则由正规式设计和定义

token的识别由有限状态机来实现

正规式与正规集

• 正规集：一组满足某种规则的字符串集合
• 正规式：描述这个集合的表达式

关系可以简单表示为：

正规式  →  描述  →  正规集

例如：

正规式:  a*
正规集:  { ε, a, aa, aaa, aaaa, ... }

字母表 $\Sigma$ 是有限字母表，在 $\Sigma$ 上正规式与正规集可递归定义如下：

正规集是指： 可以用正规式描述的字符串集合。

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

text复制代码

L = {a, aa, aaa, aaaa, ...}

这个集合可以写成正规式：

text复制代码

a*

因此它是正规集。

正规式是一种用来描述字符串集合的表达式。

正规式的三种基本运算

正规式通过三种基本运算构造。

并（Union）

符号：

|

表示 或 可交换，可结合

例如：

a | b

表示集合：

{ "a", "b" }

连接（Concatenation）

表示字符串连接。 和结合

例如：

ab

表示集合：

{ "ab" }

再例如：

(a|b)c

表示：

{ "ac", "bc" }

闭包（Kleene Star）

A*（Kleene 闭包）

字母表 A={0,1,2} 表示 由字母表 A 中的符号组成的所有可能字符串（包括空串）。

• 可以使用 A 中的字符 任意次（包括 0 次）
• 因此 包含空串 ε

符号 $A^*$ = {ϵ, 0,1,2,00,01,02,10,11,12,… }

• 长度为 0：ε
• 长度为 1：0, 1, 2
• 长度为 2：00, 01, 12, 20 …
• 任意长度字符串都可以

A⁺（正闭包）

表示 由字母表 A 中的符号组成的所有非空字符串。 $A^+$ = {0,1,2,00,01,02,10,11,12,… }

• 可以使用 A 中的字符 至少 1 次
• 不包含空串 ε

有限状态自动机 FA

有限自动机（Finite Automaton，FA）是一种抽象计算模型，用来识别字符串是否属于某个语言集合。在编译原理中，它主要用于实现词法分析器：词法规则通常先写成正规式，再转成有限自动机，最后由程序或表格实现扫描过程。

基本流程：

输入字符串 → 自动机逐字符读取 → 状态不断变化 → 判断是否接受

一个有限自动机一般由五个部分组成，也就是五元组：

M = (Q, Σ, δ, q0, F)

简单理解：

• 状态：自动机当前处于的“位置”或“识别进度”；
• 输入符号：当前读取到的字符；
• 转换规则：根据当前状态和输入字符决定下一状态；
• 接受状态：表示识别成功的状态。

如果一个字符串 w 从初态 q0 出发，按字符依次转换后最终停在接受状态中，则称自动机 M 接受或识别 w；否则称 M 拒绝 w。自动机能接受的所有字符串组成的集合称为该自动机识别的语言，记为 L(M)。

有限自动机主要有两种：

• DFA（确定有限自动机）
• NFA（非确定有限自动机）

DFA 和 NFA 的核心区别在于：同一状态读入同一字符时，下一步是否唯一确定。

这里 $2^Q$ 表示状态集合 Q 的幂集，也就是“状态子集的集合”。因此 NFA 的转换结果不是单个状态，而是一个状态集合。例如：

f(q0, a) = {q1, q2}

表示 NFA 在状态 q0 读到字符 a 时，可以同时选择走向 q1 或 q2。

NFA 确定化需要两个重要概念：

正规式、正规集和有限自动机之间也可以互相转换：DFA 接受的语言是正规集；每个正规式都能构造出等价的 NFA。实践中常按“正规式 -> NFA -> DFA -> 最小化 DFA -> 扫描器代码”的路线实现词法分析器。

FA 的常见表示方法

有限自动机常见有三种表示方法：形式定义、状态转换图、状态转换表。它们描述的是同一个东西，只是表达形式不同。

例如，构造一个 DFA，识别字母表 {a,b} 上所有以 a 结尾的字符串。

形式定义可以写成：

M = (Q, Σ, δ, q0, F)
Q = {q0, q1}
Σ = {a, b}
初始状态 = q0
F = {q1}

其中 q0 表示“当前还不是以 a 结尾”，q1 表示“当前是以 a 结尾”，并且 q1 是接受状态。状态转换函数为：

δ(q0, a) = q1
δ(q0, b) = q0
δ(q1, a) = q1
δ(q1, b) = q0

状态转换图可以表示为：

stateDiagram-v2
    [*] --> q0
    q0 --> q1: a
    q0 --> q0: b
    q1 --> q1: a
    q1 --> q0: b

状态转换表可以写成：

如果输入串是 baba，运行过程为：

q0 --b--> q0 --a--> q1 --b--> q0 --a--> q1

最终停在接受状态 q1，所以 baba 被接受。若输入串是 abb，最终停在 q0，所以被拒绝。

确定有限自动机（DFA）

**DFA（Deterministic Finite Automaton）**具有以下特点：

• 每个状态对每个输入符号 只有一个转移
• 没有 ε 转移
• 计算过程是唯一确定的

即：

一个状态 + 一个输入 → 唯一下一状态

因此，DFA 的每一步都没有选择分支。对每个状态 q 和每个输入字符 a，δ(q,a) 必须是一个确定状态。DFA 很适合用二维表实现，词法分析器最终执行时通常就是“当前状态 + 当前字符 -> 查表 -> 下一状态”。

非确定有限自动机（NFA）

**NFA（Nondeterministic Finite Automaton）**允许：

• 一个状态对同一输入 有多个转移
• 一个状态对某个输入 没有转移
• 可以存在 ε 转移（不消耗输入字符）

因此：

一个状态 + 一个输入 → 多个可能状态

自动机会 同时尝试多条路径。

只要有一条路径到达接受状态，就认为字符串被接受。

例如，一个 NFA 可以写成：

f(q0, a) = {q0, q1}
f(q1, b) = {q2}
f(q0, ε) = {q2}

这表示从 q0 读到 a 时既可以留在 q0，也可以走到 q1；同时还可以不读取任何字符直接通过 $\epsilon$ 转换到 q2。

NFA 确定化 -> NFA 转换 DFA（子集构造法）

NFA 可以存在：

• 一个状态对同一输入有 多个转移
• ε 转移

而 DFA 必须满足：

• 每个状态对每个输入 只有一个转移
• 没有 ε 转移

因此需要将 NFA 转换为等价的 DFA。 使用的方法叫 子集构造法（Subset Construction）。

核心思想：

DFA 的一个状态 = NFA 的一组状态

DFA 化简

目标：
将一个 DFA 转换为状态数最少但语言等价的 DFA。

无关状态（多余状态）：从初态出发不可到达

如果 DFA M 既没有无关状态，且没有等价状态，则称 DFA M 是规约的（即最小的 DFA M）

划分法

• 基本划分：建立初始划分，终态集和非终态集 P 0 = 「Z，K-Z」 // K 是 M 的所有状态的集合
• 精细划分： 考察当前划分中的每一个状态，根据其指向的终态与否来形成新划分，每个相同的划分可以合并。

DFA → 正规式 RE （状态消除法）

这是反方向的转换。 核心思想：逐步删除状态 → 用正规式表示路径

把 DFA 转成“广义自动机”

允许边上标记为： 正规式

消除中间状态

如果有：qi --R1--> qk --R2--> qj 则替换为：qi --R1·R2--> qj

有环的情况

如果：qk 有自环 R 则：R*

最终

只剩：起点 → 终点 边上的表达式就是正规式。

DFA： q0 --a--> q1
q1 --b--> q2（终态） 正规式：ab

正规式 RE 与 FA 等价性

这是一个重要理论结论：

正规式 ⇔ NFA

• 每个正规式都可以构造 NFA（Thompson）
• 每个 NFA 都可以转成正规式（状态消除）

NFA ⇔ DFA

• NFA → DFA（子集构造）
• DFA 是 NFA 的特例

因此：正规语言 = 能被有限自动机识别的语言

text复制代码

正规式（描述 token）
   ↓
  NFA（容易构造）
   ↓
  DFA（方便执行）
   ↓
  代码实现（扫描器）

第 3 章词法分析

词法分析要解决的关键问题是：如何定义词法规则，并根据这些规则识别输入字符串中的单词。词法分析程序也称扫描器，它把源程序字符流切分为 Token 流，为语法分析提供更稳定的输入形式。

为什么需要词法分析

因为： 语法分析不适合直接处理字符

例如：

while(a<=10)

如果语法分析器直接逐字符处理：

w h i l e( a < = 1 0 )

太复杂。 所以先进行：“单词切分” 得到：

WHILE
(
ID
<=
NUM
)

语法分析会简单很多。

举例

源代码：

int a = b + 10;

词法分析器输出：

于是得到：

<KEYWORD, int>
<ID, a>
<ASSIGN, =>
<ID, b>
<PLUS, +>
<NUM, 10>
<SEMI, ;>

这些 token 会交给：语法分析器继续处理。

输入与输出

单词

单词是语言中具有独立意义的最小语法单位 单词是受词法规则制约

	例如，
	…A*B…，单词是“A”、“*”和“B”。
	…int int1…,单词是“int”和“int1”。
	…A++*B…,单词是“A”、“++”、“*”和“B”。

常见单词分类（token）：

• 关键字：==类码== 关键字一般是语言系统本身定义的，通常是由字母组成的字符串
• 标识符：==类码+符号表== 用于表示各类名字的标识。如变量名，数组名，结构名，函数名等。
• 常量：==类码+符号表== 如整型常数，实型常数，不同进制的常数，布尔常数，字符及字符串常数。
• 运算符：==类码== 表示程序中算术运算，逻辑运算，字符及位串等运算的确定字符（或串）
• 界限符：==类码== 如逗号，分号，括号，单双引号

属性字 Token

词法分析器通常输出二元组或多元组形式的 Token，例如类型和值的编码。它本质上是单词的内部表示。

源程序预处理

输入缓冲

词法分析器从源程序字符流读取字符时，用来暂存一段输入内容的内存区域。它的目的不是“让算法更聪明”，而是让读字符、回退字符、识别 token 这些操作在工程上更高效、更容易实现。

由于字符一个个从文件中读取速度太慢，双缓冲或对半互补缓冲机制能够提高字符读取效率，减少频繁 I/O 带来的开销。

• 一次读一大块到内存
• 然后在内存里扫描 提高效率。

对半互补缓冲区： 将缓冲区分成前后两边

预处理内容

源程序预处理的作用是减少内存空间占用，并减轻扫描器的实质性处理负担。常见预处理包括删除注释、过滤无关空白、宏替换、文件包含和条件编译展开。

词法分析器设计

词法分析器是编译器的第一阶段 作用是：把源程序的字符流转换成 token 流 也叫：

• 扫描器（Scanner）
• Lexer

设计过程：

• 对各类单词构造状态图
• 状态图合并
• 初态合并
• 调整冲突编号

词法分析程序的输入是源程序字符流，输出是属性字 Token。单词是语言中具有独立意义的最小语法单位，一般包括关键字、常数、标识符、运算符和界限符；属性字 Token 通常写成 (type, code) 或类似形式，是单词在编译器内部的表示。源程序输入常配合对半互补输入缓冲模式，预处理阶段则负责过滤注释、无用字符以及展开宏、文件包含和条件编译内容。

状态图构造

通常为每类单词先单独设计状态图。 再将各类状态图合并，构成一个能识别该语言所有单词的状态图。 合并时通常先将各类单词的状态图合并成为一个唯一初态，再调整冲突编号，保证同一输入在终态处能确定对应的 Token 类型。

冲突消解

在合并状态图后，需要处理终态冲突、优先级冲突和保留字识别等问题。

例题

词法分析器实现方式

数据中心法

也叫：

• 表驱动法
• 自动机驱动法

核心思想： 把词法规则“数据化”，程序只负责查表。典型结构包括主表和分表：主表记录状态及其分表地址或子程序入口，分表记录输入字符到转换状态的映射。

• 状态转移信息存在“表”里
• 程序本身几乎不变

程序只做：

当前状态 + 当前字符→ 查转换表→ 得到下一个状态

这其实就是： 将状态转换图看成一种数据结构（状态矩阵表），用总控程序控制输入的源程序串在其上运行。 通过状态转换表驱动识别过程，结构清晰，适合自动生成。 其实就是有限自动机（DFA）实现

程序中心法

也叫：

• 手工编码法
• 过程驱动法 核心思想： 用程序逻辑控制识别过程，通常通过 if、switch、while、goto 等语句直接描述状态变化。

直接以程序逻辑描述状态变化，灵活性更高，但不如表驱动方式直观统一，规则多后难以维护

适合：

• 教学
• 小型编译器
• 实验

词法分析程序的自动生成

Lex 与 Flex

是根据词法规则生成用于词法分析的词法分析器源程序。

Lex/Flex 可以根据正规式规则自动生成词法分析器。它们将“规则描述”与“识别程序”分离，是词法分析自动化的重要工具。

第4章 语法分析：自上而下分析

语法分析综述

在编译原理里，语法分析（Parsing） 的核心任务是利用源语言文法，对词法分析器输出的属性字流进行分析，判断 token 串是否符合文法，并构造语法树或分析树，从而识别出程序中的语法范畴结构。

而语法分析的方法，主要分成两大类：

• 自上而下分析（Top-Down Parsing）
• 自下而上分析（Bottom-Up Parsing）

它们本质上的区别是：

语法分析器的功能

语法分析器接收词法分析器输出的属性字流，根据源语言文法识别其结构，并构造语法树或其他结构化表示。 从左至右地扫描 Token 流，按照语言的语法规则识 别语句结构，输出语法树或者语法错误信息。

文法介绍

语言要素 语法：语言的描述规则 语义：语言的含义 语言是由单词按一定规则（文法）组成句子来表达特定意思。 故对语言的分析集中于对句子的分析。而句子的分析依据语言的文法规则。 语法是一种媒介，语义以语法为媒介来予以说明。

文法：形式化定义

文法是描述语言的语法结构的形式规则（也称为文法规则 或产生式规则）。 文法必须是准确的且是可理解的。 一部文法 G 是一个四元组：G =（ $V_N$, $V_T$, S, P）

$V_N$：非空有限的非终结符号集 (一般用大写字母表示，有时被称为 token)； $V_T$：非空有限的终结符号集（一般用小写字母表示）。 S ：文法的开始符号或识别符号，亦称公理， S ∈ $V_N$。S 代表语言最终要得到的语法范畴。 P ：有限产生式集。 设 V 是文法 G 的符号集，则有 V= $V_T$ ∪ $V_N$ ， $V_T$ ∩ $V_N$ = Ø

例：

给定一部文法G, 从G 的开始符号S 出发，反复使用产生 式对非终结符进行替换，最后所得到的终结符号串的全体，即为文法G 所描述的语言L (G)。

文法：字符与符号串

字符串/符号串 由字母表中的符号组成的任何有穷序列称为符号串 通常使用小写字母表示符号串，如 x =STR 字=句子=串 例：

1. 001110 是字母表 Σ={0, 1}上的符号串；
2. 字母表 A={a, b, c}上的一些符号串有：a，b，c，ab，ba，aaca 等。

符号串的递归定义 （1）设Σ是一个字母表，那么∀∈ Σ, 称为是Σ上的一个串。 （2）若 x 是 Σ 上的符号串，且 a∈ Σ ，则 xa 或 ax 是 Σ 上的符号串； （3）y 是 Σ 上的符号串，当且仅当 y 可由 (1) 和 (2) 产生。

符号串长度 如果某符号串 x 中有 m 个符号，则称其长度为 m，记为 | x | = m。 空串ε：不包含任何符号的符号串，长度为 0，记为 |ε| = 0。 例如： 1）字母表 Σ={0，1}，符号串： | 001110 | = 6 2）字母表 Σ={ x, y, z, =, 0, 1, +, ;, 空格 }，符号串： |x=y++; z=0;| = 11

符号串前后缀 如果存在三个字符串 xyz，如果 x=yz， 那么，则称：y 为 x 的前缀，z 为 x 的后缀。 若 s 的前缀（后缀）不是 s 自身，则将其称为 s 的真前缀（真后缀）。 从一个符号串中删去它的一个前缀和一个后缀之后剩余的部分称为该符号串的子符号串或子串。

文法：推导

推导的说明

假设文法：

S → aSb | ε

它表示：

a^n b^n

即：

εabaabbaaabbb...

现在想生成句子：

aabb

过程就是：

从开始符号 S  
不断使用产生式替换  
最终得到全终结符串

最左推导

定义：

每一步都替换当前句型中最左边的非终结符。

最右推导

定义：

每一步都替换当前句型中最右边的非终结符。

自下而上分析中的规范规约可以看作规范推导，也就是最右推导的逆过程。

语法树与二义性

对一部文法 G，如果至少存在一个句子，有两棵 ( 或两棵以上 )不同的语法树，则称该句子是二义性的。包含有二义性句子的文法称为二义文法。否则，该文法是无二义性的。 定义提供了对给定文法在某一范围内判定是否是二义性文法的充分条件。

Chomsky 文法分类

Chomsky 文法分类是诺姆·乔姆斯基（Noam Chomsky）在 1956 年提出的形式文法层次体系，它将形式文法按生成能力（expressive power）划分为四类，每一类都是下一类的特例。四类文法及其对应语言、自动机如下表概览：

注意：Type 3 ⊆ Type 2 ⊆ Type 1 ⊆ Type 0，每一级的生成能力都包含下一等级。

0 型：短语文法 / 非限制文法（Unrestricted Grammar）

定义：

• 生成规则没有限制，只要求形式为 α → β，α 不能是空串（至少包含一个符号），β 可以为空。
• 适用于描述最广泛的语言集合。

语言类：

• 可递归可枚举语言（Recursively Enumerable Language）
• 这些语言可以被图灵机识别，但不一定可判定。

特点：

• 最强的生成能力，但可能不可判定。
• 没有语法结构限制。

示例：

S → aSb | ε

这个例子虽然看起来简单，但本质上符合 Type 0 的要求。

对应自动机：图灵机。

1 型：上下文有关文法（Context-Sensitive Grammar, CSG）

定义：

• 生成规则形式为 αAβ → αγβ，其中 A 是非终结符，α, β, γ 是符号串，且 |γ| ≥ 1
• 规则左边的非终结符可以根据上下文 α 和 β 被替换为 γ
• 保证每次推导不缩短串长度（除非生成空串特例 S → ε，S 不出现在右边）

语言类：

• 上下文有关语言（CSL）

特点：

• 能描述比上下文无关文法更复杂的语言，例如需要记忆字符串长度或匹配多种结构。
• 所有 Type 1 语言都可被线性有界自动机（LBA, Linear Bounded Automaton）识别。

示例：

S → aSB | ε
AB → BA
aA → aa
bB → bb

• 这个规则可以生成语言 { a^n b^n c^n | n ≥ 1 }，这是上下文无关文法无法描述的。

对应自动机：线性有界自动机（LBA），类似图灵机但带有限带宽。

2 型：上下文无关文法（Context-Free Grammar, CFG）

定义：

• 生成规则形式为 A → γ，A 是单个非终结符，γ 可以是任意符号串（终结或非终结符）
• 不依赖于上下文（即不管 A 在句子中的位置，规则都可应用）

语言类：

• 上下文无关语言（CFL）

特点：

• 常用于程序设计语言的语法分析
• 支持嵌套结构，如括号匹配、if-else 语句块
• 可以用推导树表示句子结构
• 可被下推自动机（PDA, Pushdown Automaton）识别

示例：

S → aSb | ε

• 语言 L = { a^n b^n | n ≥ 0 }，左右括号匹配也属于此类语言。 对应自动机：下推自动机（PDA）

3 型：正则文法（Regular Grammar）

定义：

• 生成规则形式为：
  • 右线性：A → aB 或 A → a
  • 左线性：A → Ba 或 A → a
• 非终结符在右边或左边，但不能混用
• 最简单、最受限的文法类型

语言类：

• 正则语言（RL）

特点：

• 可被有限自动机（DFA/NFA）识别
• 适用于简单模式匹配，如词法分析
• 不能描述嵌套结构，例如 { a^n b^n | n ≥ 0 } 不属于正则语言

示例：

S → aA | bB
A → aS | a
B → bS | b

• 语言 L 包含所有由 a 和 b 构成的有限组合，但不能保证 a 和 b 数量相等。

对应自动机：有限自动机（DFA/NFA）

层次关系和直观理解

• Type 3 ⊆ Type 2 ⊆ Type 1 ⊆ Type 0
• 理解方法：
  • 正则文法 → 简单模式匹配
  • 上下文无关文法 → 支持嵌套结构
  • 上下文有关文法 → 支持复杂约束，如多组符号同步增长
  • 非限制文法 → 理论上能描述任意可枚举语言（图灵机可识别）
• 图示直观记忆：

┌───────────────┐
│   Type 0      │  ← 图灵机可识别
│ 非限制文法      │
└───────────────┘
        │
┌───────────────┐
│   Type 1      │  ← 线性有界自动机
│ 上下文有关文法 │
└───────────────┘
        │
┌───────────────┐
│   Type 2      │  ← 下推自动机（PDA）
│ 上下文无关文法 │
└───────────────┘
        │
┌───────────────┐
│   Type 3      │  ← 有限自动机
│ 正则文法       │
└───────────────┘

1. 右线性或左线性，一个终结符带一个非终结符跑 → 3 正则
2. 单非终结符左边，左边只能一个非终结符 → 2 上下文无关
3. 非终结符左右有上下文，长度不能减少 → 1 上下文有关
4. 没有任何限制，啥都能写 → 0 非限制文法

应用场景：

• 正则文法 → 词法分析器
• 上下文无关文法 → 语法分析器、编译器解析程序结构
• 上下文有关文法 → 更复杂语法或自然语言分析
• 非限制文法 → 理论计算能力研究

自上而下分析

一般的自上而下分析是从开始符号出发，试探性地推导输入串。若文法存在多个候选式，分析器可能先选错候选式，形成假匹配并导致回溯；可以通过提取左公因子减少这种不确定性。若文法存在左递归，自上而下分析可能不断展开自身而无法停止，因此需要先消除左递归。

FIRST 集用于判断某个候选式可能以哪些终结符开头。设 $G$ 是二型文法且不含左递归，候选式 $\alpha$ 的终结首符集为：

若 $\alpha \Rightarrow \epsilon$，则 $\epsilon \in FIRST(\alpha)$。

一般思想

从开始符号出发，尝试推导出输入串，本质上是在“预测”输入应当符合什么结构。 它是一种“产生式驱动”的方法，也可以理解为：先假设整个输入串属于开始符号代表的语法范畴，再不断把非终结符展开成更具体的结构。

自上而下分析通常对应最左推导：每一步都选择当前句型中最左边的非终结符进行替换。分析器一边读入 Token，一边判断当前应该使用哪条产生式。如果选择正确，最终可以从开始符号推出完整输入串；如果选择错误，就会出现匹配失败，需要回溯或提前通过规则改写消除这种不确定性。

直观过程：

开始符号 S
  ↓ 使用产生式展开
句型
  ↓ 继续展开最左非终结符
终结符串
  ↓ 与输入 Token 串匹配
接受或报错

所以，自上而下分析的重点不是“从输入串中找可规约片段”，而是“预测下一个语法结构应该是什么”。这也是 LL 分析、递归下降分析的基本思想。

自上而下分析沿着推导方向展开。若直接采用回溯，分析器会在多个候选式之间反复试探，匹配失败后再退回重新选择，这会带来大量重复尝试，效率较低。因此实际构造自上而下分析器时，通常会先改写文法，使分析器能够根据少量向前看符号确定要使用的产生式。

常见处理路线：

1. 消除左递归，避免递归下降程序无限调用自身。
2. 提取左公因子，避免多个候选式前缀相同导致回溯。
3. 计算 FIRST 集和 FOLLOW 集，构造预测分析表。
4. 若分析表无冲突，则可构造 LL(1) 分析器。

不确定性的来源

公共前缀

多个候选式可能以相同前缀开头，导致分析器无法立即决定使用哪一条产生式。

例如：

A → abC | abD

输入：

abx...

当看到：

ab

时，分析器还无法知道后面该走 C 分支还是 D 分支。如果采用普通回溯，就可能先选择 A → abC，失败后再回到 A 重新尝试 A → abD。

公共前缀的问题本质是：产生式选择发生得太早，而区分分支所需的信息还没有读到。解决方法是把公共部分先提出来，把分支选择延后。

左递归

左递归：推导时变回自身。

典型形式是 A -> Aα | β。它会让自上而下分析不断选择同一非终结符展开，容易陷入无穷递归。

若文法存在左递归，自上而下分析会陷入无限展开，必须先改写文法。

左递归分为两类：

• 直接左递归：A → Aα | β
• 间接左递归：A → Bα，B → Aβ

对递归下降分析器来说，左递归尤其危险。例如：

E → E + T | T

如果为 E 写一个递归函数，进入 E 后第一条候选式又要求先调用 E，于是程序会不断调用自身，而没有机会消耗输入符号：

parseE()
  → parseE()
    → parseE()
      → ...

因此，左递归文法通常适合自下而上分析，但不适合直接用于自上而下分析。

消除回溯的关键方法

提取左公因子

通过把共同前缀提出，延后分支决策时机，使分析器能够在读入更多符号后再选择候选式。

原文法：

A → abC | abD

提取：

A  → abA'
A' → C | D

这样：先读：

ab

之后再决定。

提取左公因子并不改变文法描述的语言，只是改变推导决策的时机，使分析器更容易用一个向前看符号完成选择。

消除左递归

将左递归文法等价改写为非左递归文法，是构造 LL 分析器的前提之一。

对直接左递归：

A → Aα | β

其中 β 表示不以 A 开头的候选式。可转换为：

A  → βA'
A' → αA' | ε

含义是：先产生一个基础部分 β，再通过 A' 反复追加 α。这样可以保留原来“重复出现 α”的语言结构，同时避免一开始就递归调用 A。

例如表达式文法：

E → E + T | T

转换为：

E  → T E'
E' → + T E' | ε

改写后适合递归下降：

• E 先识别一个 T
• E' 决定后面是否继续出现 + T
• 若没有加号，则用 ε 结束

注意：消除左递归后，语法树形状可能变化。对于表达式求值、结合性等语义问题，需要在语义动作中额外处理，不能只看文法形式。

FIRST 集

FIRST 集用于描述某个串可能推出的终结符首符号集合，是构造预测分析表的重要依据。 FIRST 是 LL 分析最核心概念之一。

定义：

FIRST(α)

表示： α 能推出的串中，第一个可能出现的终结符集合

更形式化地说：

FIRST(α) = { a | α =>* aβ, a ∈ VT }

如果 α 可以推出空串，则：

ε ∈ FIRST(α)

例如：

A → aB | bC | ε

则：

FIRST(A) = { a, b, ε }

计算 FIRST 集时可以按以下思路：

1. 若 X 是终结符，则 FIRST(X) = { X }。
2. 若 X → ε，则把 ε 加入 FIRST(X)。
3. 若 X → Y1Y2...Yk，先把 FIRST(Y1) 中除 ε 外的符号加入 FIRST(X)。
4. 如果 Y1 能推出 ε，继续考察 Y2；如果 Y1...Yk 都能推出 ε，则把 ε 加入 FIRST(X)。

FIRST 集回答的问题是：当前要展开某个候选式时，它可能以什么终结符开头？

FOLLOW 集

FOLLOW 集用于描述某个非终结符后面可能紧跟的终结符集合。

定义：

FOLLOW(A) = { a | S =>* αAaβ, a ∈ VT }

如果 A 可能出现在句型末尾，则把输入结束符 $ 加入 FOLLOW(A)。

FOLLOW 集在 LL(1) 分析表构造中主要用于处理 ε 候选式。例如：

A → α | ε

如果当前输入符号属于 FIRST(α)，就选择 A → α；如果当前输入符号属于 FOLLOW(A)，说明 A 可以为空，于是选择 A → ε。

常用计算规则：

1. 对开始符号 S，把 $ 加入 FOLLOW(S)。
2. 若产生式中有 A → αBβ，则把 FIRST(β) 中除 ε 外的符号加入 FOLLOW(B)。
3. 若 β =>* ε，或产生式形如 A → αB，则把 FOLLOW(A) 加入 FOLLOW(B)。

FOLLOW 集回答的问题是：如果当前非终结符可以结束，那么它后面合法出现什么符号？

LL(1) 文法的判断条件

对于同一个非终结符 A 的多个候选式：

A → α1 | α2 | ... | αn

若要成为 LL(1) 文法，需要满足：

1. 任意两个候选式的 FIRST 集不能相交：

FIRST(αi) ∩ FIRST(αj) = Ø

2. 如果某个候选式可以推出 ε，则它的 FOLLOW 集也不能和其他候选式的 FIRST 集冲突：

若 ε ∈ FIRST(αi)，则 FIRST(αj) ∩ FOLLOW(A) = Ø

这两个条件保证分析器只看 1 个输入符号时，也能唯一决定使用哪条产生式。

递归下降分析方法和递归下降分析器

LL(1) 分析器是一种典型的自上而下分析器：第一个 L 表示自左向右扫描输入，第二个 L 表示构造最左推导，1 表示最多向前看 1 个输入符号来决定使用哪个产生式。它通常由总控程序、分析栈和 LL(1) 分析表组成，分析表的构造需要结合 FIRST 集和 FOLLOW 集。

递归下降分析

把每个非终结符对应为一个递归子程序，程序之间按文法规则相互调用，结构与文法非常接近。

例如：

E  → T E'
E' → + T E' | ε
T  → id

可以理解为：

parseE()  负责识别 E
parseE'() 负责识别 E'
parseT()  负责识别 T

递归下降分析器的优点是直观、便于手写、便于在分析过程中嵌入语义动作；缺点是对文法要求较高，通常不能直接处理左递归，也不适合候选式冲突严重的文法。

典型匹配流程：

1. 如果当前符号是终结符，就与输入 Token 比较，成功则读入下一个 Token。
2. 如果当前符号是非终结符，就调用对应的分析子程序。
3. 如果候选式有多个，就根据 FIRST/FOLLOW 或预测分析表选择一条。
4. 如果没有合法选择，则报告语法错误。

LL(1) 分析器

含义

LL(1) 表示自左向右扫描输入、进行最左推导，并且每次最多向前查看 1 个输入符号。

三个部分可以这样记：

LL(1) 分析器的核心目标是：在当前栈顶非终结符和当前输入符号确定后，能唯一找到一条产生式。

组成

典型 LL(1) 分析器由总控程序、分析栈和LL (1) 分析表组成。

• 总控程序：负责循环读取栈顶符号和当前输入符号，决定匹配、展开或报错。
• 分析栈：保存尚未匹配或尚未展开的文法符号，初始通常为 $S。
• 预测分析表：行是非终结符，列是终结符或 $，表项是应使用的产生式。

分析动作可以概括为：

分析表构造

分析表需要结合 FIRST 集和 FOLLOW 集构造。若表中不存在冲突，则文法是 LL(1) 文法。

构造规则：

对每条产生式：

A → α

1. 对 FIRST(α) 中的每个终结符 a，把 A → α 填入 M[A,a]。
2. 如果 ε ∈ FIRST(α)，则对 FOLLOW(A) 中的每个符号 b，把 A → α 填入 M[A,b]。
3. 如果某个表项要填入多条产生式，则发生冲突，该文法不是 LL(1) 文法。

示例文法：

E  → T E'
E' → + T E' | ε
T  → id

当栈顶是 E'：

• 当前输入是 +，选择 E' → + T E'
• 当前输入是 $ 或表达式结束符，选择 E' → ε

这就是预测分析的含义：根据“当前输入符号”预测应该展开哪条产生式。

结论

LL(1) 分析简单、易实现，但适用文法范围相对受限，很多实际语言语法需要改写后才能使用。

适合 LL(1) 的文法通常满足：

• 没有左递归
• 候选式之间 FIRST 集不相交
• 含 ε 产生式时，FIRST 与 FOLLOW 不冲突

LL(1) 常用于教学和简单语言解析。对于完整程序设计语言，语法往往更复杂，工程中更常使用 LR、LALR 或基于 PEG/递归下降增强版的分析工具。

改写为 LL（1）

第5章 语法分析：自下而上分析

基于移进规约的自下而上分析

自下而上分析围绕“移进”和“规约”展开，基本概念包括短语、直接短语和句柄。它们用来说明当前句型中哪些部分已经可以被规约，以及应该优先规约哪一部分。

基本思想

从输入串出发，通过不断规约恢复出开始符号，本质上是在“归纳”输入属于哪种结构。

自下而上分析通过不断把输入串中的某些片段规约为非终结符，最终规约为开始符号。

如果自上而下分析是在做：

S =>* 输入串

那么自下而上分析就是反过来做：

输入串 =>* S

更准确地说，自下而上分析对应最右推导的逆过程，也称为规范规约。分析器不断在当前句型中寻找一个可以被规约的片段，把它替换成产生式左部的非终结符。

例如文法：

E → E + T | T
T → id

输入：

id + id

规约过程可以是：

id + id
T  + id      使用 T → id
E  + id      使用 E → T
E  + T       使用 T → id
E            使用 E → E + T

最终得到开始符号 E，说明输入串符合文法。

实际分析时，输入符号不会一次性全部拿来规约，而是通过移进-规约策略完成：

• 移进：把下一个输入符号压入栈中。
• 规约：当栈顶若干符号匹配某个产生式右部时，把它们替换为产生式左部。
• 接受：输入读完，栈中归约为开始符号。
• 报错：当前状态下既不能移进，也不能规约。

移进规约分析通常维护一个符号栈和一个输入缓冲区。栈中保存已经读入但尚未完全规约的符号，输入缓冲区保存尚未读入的符号。分析器每一步要解决的问题是：当前栈顶是否已经形成句柄；如果形成句柄，就规约；如果还没有形成句柄，就继续移进。

基本概念

这几个概念可以先按作用分开记：

短语

短语是句型中符合某个非终结符推导结果的子串。

更形式化地说，若存在推导：

S =>* αAβ
A =>+ γ

则 γ 是句型 αγβ 中相对于非终结符 A 的短语。

短语强调的是：这个子串可以由某个非终结符推出，所以它有可能在规约时被整体替换为该非终结符。

直接短语

若某短语在一次推导中直接由一个非终结符推出，则称为直接短语。

即：

A → γ

如果句型中出现的 γ 正好是某个产生式右部，那么它就是一个直接短语。移进规约分析每次真正执行规约时，规约对象通常就是某个直接短语。

句柄

句柄是当前规范句型中最左的直接短语，对其规约恰好对应规范推导的逆过程。

句柄是自下而上分析中最重要的概念。每一步规约都必须找到当前句型的句柄，如果规约了错误的短语，就可能走向错误的推导。

可以这样理解：

• 短语：可能由某个非终结符推出的片段。
• 直接短语：一步就能由某个非终结符推出的片段。
• 句柄：当前最应该被规约的那个直接短语。

对于规范规约，句柄对应最右推导逆序中的下一步。LR 分析器的核心能力，就是借助状态栈准确判断栈顶是否形成句柄。

例如文法：

E → E + T | T
T → i

对句型 E + i，i 是相对于 T 的直接短语，也是当前应规约的句柄，因此先用 T → i 规约为 E + T，再用 E → E + T 规约为 E。如果提前把错误片段规约掉，就不再对应某个最右推导的逆过程。

从语法树角度看会更直观。以文法：

E → E + T | T
T → i

句子 i + i 的一棵语法树可以看成：

        E
      / | \
     E  +  T
     |     |
     T     i
     |
     i

这棵树中：

• 左边的 i 是相对于左边 T 的短语，也是直接短语，因为 T -> i 一步推出；
• 右边的 i 是相对于右边 T 的短语，也是直接短语；
• 整个 i + i 是相对于根结点 E 的短语，因为它能由 E 推出；
• 在规范规约过程中，先规约哪个直接短语要看它是否是当前句柄，不能随便挑一个短语规约。

一个常用判断口诀是：

短语看“能不能推出”；
直接短语看“是不是一步推出”；
句柄看“当前该规约谁”。

LR 分析

LR 方法概述

LR 分析是一类自左向右扫描输入、按最右推导逆过程进行规范归约的语法分析方法，适用范围广，错误检测能力强。

LR 分析比 LL 分析适用范围更广，原因在于：LL 分析在展开前就要预测产生式，而 LR 分析可以先读入更多输入，把上下文信息压缩到状态中，再决定是否归约。

LR 分析器不直接构造语法树也可以判断句子是否合法；如果配合语义动作，就可以在归约时建立语法树、生成中间代码或进行语义检查。

LR(k) 中的 L 表示从左到右扫描输入，R 表示按最右推导的逆序进行归约，k 表示每一步最多向前看 k 个输入符号。LR 分析器由总控程序、分析栈和 LR 分析表组成。分析栈中通常同时保存状态符号 $q_i$ 和文法符号 $X_i$；LR 分析表由 ACTION 表和 GOTO 表构成，其中 ACTION 表决定移进、归约、接受或报错，GOTO 表决定归约后状态如何转移。

LR(0) 分析器的构造核心是项目集规范族。基本步骤为：拓广文法、构造项目集闭包、求状态转换函数 GO(I, X)，再构造文法的 LR(0) 项目集规范族。若项目集中同时出现移进和归约选择，就可能产生移进-归约冲突；若同时存在多个归约选择，就可能产生归约-归约冲突。

SLR(1) 通过考察归约符号的 FOLLOW 集缓解 LR(0) 冲突；LR(1) 在项目中携带 1 个搜索符，分析能力更强；LALR(1) 则把 LR(1) 项目集规范族中同心项目集合并，通常保持接近 LR(0) 的状态数。需要注意，二义文法本身不是 LR 文法，但工程工具中常通过规定优先级和结合性来排除特定二义性。

LR 分析的基本动作：

LR(k) 的含义

其中 $k$ 表示向前查看（这个向前是指语法分析器的前，对人阅读而言是向右）的输入符号个数。实际中最常见的是 LR(0)、SLR(1)、LR(1) 与 LALR(1)。

LR(k) 的完整含义：

• L：从左到右扫描输入。
• R：按最右推导的逆过程进行归约。
• k：归约决策时最多向前查看 k 个输入符号。

常见类型对比：

LR 分析器组成

总控程序

总控程序是 LR 分析器的驱动部分。它反复查看栈顶状态和当前输入符号，查 LR 分析表，并执行移进、归约、接受或报错动作。

可以把总控程序理解为固定算法，真正随文法变化的是分析表。只要给定不同文法对应的 ACTION/GOTO 表，同一个总控程序就可以分析不同语言。

分析栈

栈中同时维护状态信息和文法符号信息，是驱动移进、归约、接受与报错动作的核心结构。

通常可写成：

状态栈：0  s1  s2 ...
符号栈：   X1  X2 ...

也可以把状态和文法符号交替压入一个栈：

0 X1 s1 X2 s2 ...

其中状态表示“到目前为止已经识别出的活前缀信息”。LR 分析不是只看栈顶符号，而是主要通过栈顶状态和当前输入符号查表。

分析表

分析表由 action 表和 goto 表组成。action 决定移进、归约、接受还是报错，goto 决定归约后转入哪个状态。

• ACTION[s, a]：当前状态为 s，当前输入终结符为 a 时应执行的动作。
• GOTO[s, A]：在状态 s 下归约出非终结符 A 后应转入的状态。

基本运行流程：

1. 查看栈顶状态 s 和当前输入符号 a。
2. 查询 ACTION[s,a]。
3. 如果是移进 shift t，则把 a 和状态 t 入栈，输入前进。
4. 如果是归约 reduce A → β，则弹出 β 对应的符号和状态，再根据 GOTO[栈顶状态,A] 入栈新状态。
5. 如果是接受，则分析成功。
6. 如果为空表项，则报语法错误。

LR(0) 分析器

项目

LR(0) 项目是在产生式右部插入一个圆点，用于表示当前识别进度。

例如产生式：

A → XYZ

可以形成以下 LR(0) 项目：

A → ·XYZ
A → X·YZ
A → XY·Z
A → XYZ·

圆点左边表示已经识别的部分，圆点右边表示还期待识别的部分。

不同圆点位置含义：

• A → ·XYZ：准备开始识别 XYZ
• A → X·YZ：已经识别 X，接下来期待 Y
• A → XYZ·：XYZ 已经识别完，可以考虑按 A → XYZ 归约

有效项目

项目 [A → β1·β2] 对活前缀 αβ1 有效，表示在某个规范推导中可能出现：

S =>* αAω => αβ1β2ω

也就是说，当栈中已经形成活前缀 αβ1 时，分析器有理由相信自己正在识别产生式 A → β1β2，并且已经识别了圆点左边的 β1，接下来还需要识别圆点右边的 β2。

一个 LR(0) 项目集可以看成“对同一个活前缀有效的所有项目”的集合。项目集中的项目共同描述当前状态下可能处于哪些产生式、哪些识别位置。

项目分类

常见有移进项目、待约项目、归约项目和接收项目，不同项目对应不同分析动作。

常见分类：

如果一个项目集中同时出现移进项目和归约项目，就可能产生移进-归约冲突；如果同时出现多个归约项目，就可能产生归约-归约冲突。

后继项目：如 A → αB·β 是 A → α·Bβ 的后继项目

前缀

前缀是一个句型从左端开始截取的任意首部。例如句型 abc 的前缀包括 ε、a、ab、abc。

在 LR 分析中，前缀概念之所以重要，是因为分析栈保存的是已经读入并归约后的左部信息。分析器不能看到任意完整句型，只能根据当前栈中形成的前缀和剩余输入决定下一步动作。

活前缀

活前缀是规范句型中不包含句柄后任意符号的前缀，LR 分析的状态本质上就是对活前缀信息的压缩表示。

可以把活前缀理解为：在移进归约过程中，栈中可能出现的、还没有越过句柄右端的前缀。只要栈内容是活前缀，就说明它仍然可能继续发展成一个合法句子。

“活”的意思是：这个前缀还没有把归约机会错过，后面继续读入或归约仍可能成功。例如对句型：

E + T * i

如果当前句柄是 T * i，那么下面这些前缀还没有越过句柄右端，可能作为 LR 分析栈内容出现：

ε
E
E +
E + T
E + T *
E + T * i

但如果前缀已经包含了句柄右边的其他符号，就不再是这个规范句型的活前缀。LR 分析器用状态来记录“当前栈中活前缀已经识别到哪里”，因此 LR 项目里的圆点位置本质上就是在描述活前缀。

LR(0) 项目集可以看成识别活前缀的 DFA 状态：

栈中符号形成活前缀
  ↓
对应一个项目集状态
  ↓
根据下一个符号转移到新项目集

因此，构造 LR 分析表的本质，是为活前缀构造一个自动机。

构造步骤

需要完成拓广文法、求项目闭包、构造 GO 函数，并形成项目集规范族。 LR(0) 项目集规范族构造步骤：

1. 增广文法：增加新的开始符号。

S' → S

这样接受状态可以统一表示为：

S' → S·

这样可以确保分析器只有一个接受状态

2. 构造闭包 CLOSURE(I)：

若项目集中有：

A → α·Bβ

并且文法中有：

B → γ

则把：

B → ·γ

加入闭包。反复执行直到不再增加新项目。

3. 构造转移 GO(I, X)： 如果项目集中有：

A → α·Xβ

读入符号 X 后变成：

A → αX·β

再对这些项目求闭包，就得到 GO(I, X)。

4. 形成项目集规范族：

从初始项目集 CLOSURE({S' → ·S}) 出发，对所有可能的文法符号不断求 GO，直到没有新项目集出现。

得到的全部项目集称为 LR(0) 项目集规范族，通常记为：

C = { I0, I1, ..., In }

其中每个 Ii 是一个 DFA 状态，GO(Ii, X) = Ij 就是 DFA 中从状态 Ii 经符号 X 到状态 Ij 的边。这个 DFA 识别的是文法的活前缀。

5. 构造分析表：

• 若 GO(Ii, a) = Ij，其中 a 是终结符，则 ACTION[i,a] = shift j。
• 若 A → α· 在 Ii 中，则对所有终结符和 $ 填写 ACTION[i,a] = reduce A → α。这也是 LR(0) 容易产生移进-归约冲突或归约-归约冲突的原因。
• 若 S' → S· 在 Ii 中，则 ACTION[i,$] = accept。
• 若 GO(Ii, A) = Ij，其中 A 是非终结符，则 GOTO[i,A] = j。

冲突与改进

移进-归约冲突

分析器在某状态下既可能移进又可能归约，说明仅靠当前信息无法唯一决定动作。

典型场景：

E → E · + T
E → E ·

当下一个输入符号是 + （非终结符）时，分析器可能：

• 移进 +，继续识别 E + T
• 立即把 E 归约

如果没有额外信息，就无法唯一决定动作。

归约-归约冲突

分析器在某状态下可能按两个不同产生式归约，说明文法或分析能力不足。

例如项目集中同时存在：

A → α·
B → β·

若当前输入符号允许两者都归约，就不知道应该归约成 A 还是 B。归约-归约冲突通常比移进-归约冲突更严重，往往意味着文法设计存在歧义或分析方法能力不够。

SLR(1)

SLR(1) 在 LR(0) 基础上引入 FOLLOW 集辅助判断归约条件，能解决部分冲突。

LR(0) 的归约项目 A → α· 默认可能在所有输入符号下归约，这太粗糙。 SLR (1) 改进的核心是：如果已经识别出 α，准备归约成 A，那么下一个输入符号必须能合法地跟在 A 后面。

因此，SLR(1) 使用全局 FOLLOW 集来限制归约动作，可以解决一部分 LR(0) 冲突。但 FOLLOW 集只依赖非终结符，不能区分不同上下文，所以仍然可能不够精确。

SLR(1) 分析表的基本构造规则是：

1. 若 GO(Ii, a) = Ij，a 是终结符，则填 ACTION[i,a] = shift j。
2. 若 A → α· 在 Ii 中，则只对 FOLLOW(A) 中的每个终结符 a 填 ACTION[i,a] = reduce A → α。
3. 若 S' → S· 在 Ii 中，则填 ACTION[i,$] = accept。
4. 若 GO(Ii, A) = Ij，A 是非终结符，则填 GOTO[i,A] = j。

如果按这些规则填表后没有任何表项冲突，则文法是 SLR(1) 文法。

做题步骤

1. 拓广文法：S' → S
2. 构造 LR (0) 项目集规范族
3. 求 FOLLOW 集
4. 按 SLR (1) 规则填 ACTION/GOTO 表
5. 如果表中没有冲突，就是 SLR (1) 文法；否则不是

LR(1)

LR(1) 项目在项目基础上引入 1 个展望符，根据展望符的不同，把原来的 LR（0）项目分成不同的项目，分析能力更强，但状态数通常更多。

LR(1) 项目形式：

[A → α·β, a]

其中 a 是展望符，表示只有当后续输入可能是 a 时，这个项目才适用。

相比 SLR(1)，LR(1) 的归约条件不再只依赖 FOLLOW(A)，而是和具体项目上下文绑定。因此 LR(1) 能处理更多文法，冲突更少。

缺点是：不同展望符会让项目集数量显著增加，分析表可能很大。

LR(1) 的闭包计算会把上下文传递到新项目中。若项目集中有：

[A → α·Bβ, a]

并且有产生式：

B → γ

则对 FIRST(βa) 中的每个终结符 b，加入：

[B → ·γ, b]

这里的 b 就是新项目的展望符。它表示只有当后续输入可能是 b 时，才允许将 B → γ 作为候选识别路径。

LR(1) 项目的归约也只在自己的展望符上发生。例如 [A → α·, a] 只会在当前输入符号为 a 时归约，不会像 LR(0) 那样在所有终结符上归约，也不会像 SLR(1) 那样只依赖全局 FOLLOW(A)。

LALR(1)

LALR(1) 通过合并同心 LR(1) 项目集，在尽量保持 LR(1) 分析能力的同时减少状态数，因此工程应用广泛。

所谓同心项目集，指项目核心相同、只有展望符不同的 LR(1) 项目集。例如：

[A → α·β, a]
[A → α·β, b]

它们的核心都是：

A → α·β

LALR(1) 会把这类项目集合并，使状态数量接近 LR(0)，但保留 LR(1) 的展望符信息。Yacc/Bison 等工具常用 LALR(1) 或其变体。

需要注意：合并同心项目集可能引入新的归约-归约冲突，但不会凭空引入新的移进-归约冲突。

LALR(1) 的常见构造思路是：

1. 先构造规范 LR(1) 项目集族。
2. 找出核心相同、仅展望符不同的同心项目集。
3. 合并这些项目集，并把相同核心项目的展望符合并。
4. 在合并后的项目集族上构造 ACTION/GOTO 表。

LALR(1) 的状态数通常接近 LR(0)，但归约动作仍然带有展望符信息，所以分析能力一般强于 SLR(1)，弱于或等于规范 LR(1)。

LR 文法的分类

LR 文法常见按分析能力从弱到强分为：

LR(0) ⊆ SLR(1) ⊆ LALR(1) ⊆ LR(1)

含义大致是：

做题时一般判断“属于哪类 LR 文法”，通常是问它属于上述哪一档里最弱但足够用的类型。

二义文法与 LR

任何二义文法都不是 LR 文法，但在实际语言处理中，可以通过人为规定优先级和结合性来消除某些二义性。

例如表达式文法：

E → E + E | E * E | id

句子：

id + id * id

既可以先算 +，也可以先算 *，文法本身是二义的。实际语言通常规定：

• * 的优先级高于 +
• +、* 通常左结合

通过这些额外规则，分析工具可以在冲突时选择合适动作。例如在 Yacc 中，可以用优先级和结合性声明解决常见表达式冲突。

但要注意：这并不是让二义文法真正变成无二义文法，而是在分析器层面规定冲突处理策略。

LR 分析的错误处理与恢复

错误类型

编译过程中的错误可分为词法错误、语法错误、语义错误，以及违反环境约束的错误。

这些错误大致区别如下：

在语法分析阶段，常见错误包括：

• 缺少分号、括号、逗号等界符。
• 关键字或标识符位置不合法。
• 表达式结构不完整，例如 a + ;。
• 语句嵌套结构不匹配，例如 { 和 } 数量不一致。

LR 分析器发现错误的方式通常是：当前栈顶状态和当前输入符号对应的 ACTION 表项为空。也就是说，在当前上下文下，该输入符号不可能合法出现。

恢复策略

紧急恢复

跳过部分输入符号，直到遇到同步记号再继续分析，简单但可能丢失较多上下文。

同步记号通常选择语句或结构边界，例如：

;  }  end

优点是实现简单，不容易陷入死循环；缺点是可能跳过较多正确内容，导致后续错误定位不够精确。

短语级恢复

在局部进行有限改正，尽量保留后续分析环境。

例如：

• 插入一个缺失的 ;
• 删除一个多余的 )
• 把某个明显错误的符号替换成期望符号

短语级恢复比紧急恢复更精细，但实现时要避免做过度猜测，否则可能掩盖真正错误。

出错产生式

在文法中显式加入错误相关规则，使分析器能够识别某些常见错误模式。

例如可以为常见错误补充产生式：

stmt → error ;

含义是：当某条语句内部出现错误时，分析器可以跳到分号位置恢复，继续分析后续语句。Yacc/Bison 中的 error 记号就是这种思想。

全局纠正

从整体上寻找代价最小的修改方案，理论意义大于工程实用价值。

全局纠正会尝试找出对整个输入串最小的插入、删除或替换序列，使其变成合法句子。它可以得到理论上较优的修正方案，但代价很高，实际编译器很少完整采用。

工程中更常见的目标不是“自动修好程序”，而是：

• 尽早发现错误。
• 给出尽量准确的位置和提示。
• 恢复到稳定状态，继续报告后续错误。

语法分析程序自动生成器

Yacc

Yacc 常用于生成 LALR(1) 分析器。它允许开发者描述文法规则和语义动作，从而自动生成语法分析程序。

Yacc 的典型输入包括三部分：

1. 记号声明和优先级声明。
2. 文法规则及其语义动作。
3. 辅助 C 代码。

基本思想：

文法规则 + 语义动作
        ↓
      Yacc
        ↓
  LALR(1) 语法分析器

词法分析器通常由 Lex/Flex 生成，语法分析器由 Yacc/Bison 生成，两者配合时：

• Lex 负责把字符流转换成 Token。
• Yacc 负责根据 Token 串进行语法分析。
• 归约时执行语义动作，例如构建 AST 或生成中间代码。

Yacc/Bison 通常会根据文法生成 LALR(1) 分析表。如果文法产生移进-归约或归约-归约冲突，工具会报告冲突位置；对于表达式文法中常见的优先级和结合性冲突，可以通过优先级声明和结合性声明指定冲突解决规则。

第6章 语义分析与中间代码生成

语法制导翻译

语义分析的目标

语义分析是编译器前端的最后一个阶段，也是源程序从“结构正确”走向“含义可解释”的关键阶段。

词法分析得到合法单词，语法分析得到合法结构，语义分析则要找到剩余的、不能单靠上下文无关文法发现的错误。

语义分析的任务可以概括为：按照语法分析器识别出的语法范畴，根据相应语义规则进行语义检查和处理，并产生中间代码或目标代码。

例如：

int a;
a = 3 + 5;      // 语法正确，语义也正确
b = 1;          // 语法可能正确，但 b 未声明，语义错误
a = "hello";    // 语法可能正确，但类型不匹配，语义错误

上下文无关文法只能描述大部分结构关系，但很多上下文敏感问题必须交给语义处理，例如：

• 标识符未声明或重复定义；
• 数组越界访问；
• 类型不兼容的访问；
• break 语句出现位置非法；
• goto 的目标标号不存在；
• 函数重复定义、返回值类型错误、调用参数不匹配。

语义分析主要围绕两类检查展开：

可以把三个前端阶段的职责区分为：

flowchart LR
    A["词法分析<br/>字符流 -> Token流"] --> B["语法分析<br/>Token流 -> 语法树"]
    B --> C["语义分析<br/>语义检查和处理"]
    C --> D["中间代码或目标代码"]
    D --> E["优化与目标代码生成"]

语法制导翻译的含义

语法制导的翻译是指：为文法的每一个产生式配一个相应的语义子程序，或配一组由语义规则描述的语义动作，并在语法分析的同时调用它。

这些语义动作可以做很多事，例如：

• 查填符号表；
• 修改属性值；
• 打印信息；
• 输出中间语言；
• 进行类型检查或作用域检查。

课件里强调了两个概念：

语法制导翻译的常见实现方法是：先构造一棵语法分析树，然后访问树中各个结点来计算结点的属性值。

语法制导定义（Syntax-Directed Definition，SDD）可以看成一个由产生式和语义规则组成的表：

形式上也可以把属性翻译文法记作：

A = (G, V, F)

其中 G 是文法，V 是属性的有穷集，F 是用属性描述的、与产生式相关的语义动作。

例如，一个简单表达式求值的 SDD 可以写成：

其中 val 是语法树结点上的属性，lexval 通常由词法分析器提供。

属性与语义规则

属性是附着在文法符号上的语义信息。课件中用 N.t 表示属性：N 是文法符号，t 是该符号的某个属性。属性值可以是整数、字母、字符串、类型、存储空间，也可以是更复杂的数据结构。

属性和文法符号相关联，语义规则和产生式相关联。一个结点的属性值可以被赋值、修改，也可以触发副作用，例如 print(E.val) 或 addtype(id.lexeme, L.in)。

课件对终结符和非终结符的属性作了区分：

语义规则的本质是建立属性之间的依赖关系。若 E.val = E1.val + T.val，则 E.val 必须等待 E1.val 和 T.val 计算完成后才能计算。

综合属性

综合属性是指：产生式左部符号的某些属性由同一个产生式右部符号的属性和（或）自己的其他属性定义。在分析树中，一个结点的综合属性值通常通过子结点的属性值计算得到，信息方向是自底向上。

例如：

E -> E1 + T
E.val = E1.val + T.val

这里左部 E 的 val 由右部 E1 和 T 的 val 计算得到。

课件中的台式计算器例子输入 3 * 5 + 4\n，语法分析树上的属性自底向上计算：

（插图未导入）

计算顺序可以理解为：

digit.lexval = 3  -> F.val = 3  -> T.val = 3
digit.lexval = 5  -> F.val = 5  -> T.val = 3 * 5 = 15
digit.lexval = 4  -> F.val = 4  -> T.val = 4
E.val = 15 + 4 = 19
L -> E 时执行 print(E.val)

综合属性适合描述：

• 表达式的值；
• 表达式的类型；
• 生成的中间代码片段；
• 标识符列表所占存储宽度。

如果一个 SDD 只使用综合属性，称为 S-SDD 或 S-属性定义。

继承属性

继承属性是指：候选式中某个符号的属性由产生式左部的属性，和（或）候选式中它左侧兄弟符号的属性定义。在分析树中，一个结点的继承属性值通常由父结点和（或）兄弟结点的属性定义。

课件使用声明语句 float id1, id2; 说明继承属性。产生式和语义规则如下：

这里 T.type 是综合属性，L.in 是继承属性。float 先让 T.type = float，然后 D -> T L 把这个类型传给 L.in，再沿着变量列表向左侧子列表传递，最后通过 addtype 把每个标识符和类型写入符号表。

（插图未导入）

这个例子中，属性传递方向不是单纯自底向上，而是先由 T.type 传到兄弟结点 L.in，再传给更深层的 L1.in。因此它体现了继承属性的上下文传递作用。

继承属性适合描述：

• 声明中的公共类型向变量列表传递；
• 作用域信息从外层语法结构传到内层语法结构；
• 控制流语句中的入口、出口标号传递；
• 数组下标计算中维度、基址、宽度等上下文信息传递。

同时含有综合属性和继承属性的 SDD 更灵活，但属性计算顺序也更复杂，需要借助依赖图判断是否可行。

依赖图

依赖图是一个描述分析树中结点属性之间依赖关系的有向图。分析树中每个标号为 X 的结点，其每个属性值 X.a 都对应依赖图中的一个结点。若 X.a 的值依赖于 Y.b，则依赖图中有一条从 Y.b 指向 X.a 的有向边。

根据依赖图可以得到 SDD 属性值的求值顺序。一个可行求值顺序就是依赖图的拓扑排序：如果依赖图中有一条从 Ni 到 Nj 的边，那么 Ni 必须排在 Nj 前面。

课件用 float a,b,c 的属性传递例子给出了依赖图和一个拓扑排序：

（插图未导入）

依赖图的作用有两个：

1. 判断属性计算是否存在合法顺序。若依赖图无环，则可以进行拓扑排序并按顺序计算属性。
2. 发现语义规则中的循环依赖。若属性之间形成环，则无法确定先算谁。

课件中特别指出：只具有综合属性的 SDD 可以按照任意自底向上的顺序计算；但同时具有综合属性和继承属性的 SDD，不一定保证存在求值顺序。如果依赖图没有环，则至少存在一个拓扑排序。

复习时可以把 SDD 的解题步骤固定为：

先画语法树 -> 标出需要计算的属性 -> 根据语义规则画依赖关系 -> 按依赖顺序填属性值

S-SDD、L-SDD 与 SDT

从计算角度看，给定一个一般的 SDD，很难判断是否存在某棵语法分析树会让属性之间形成循环依赖。因此课件引入了两个有用子类：S-SDD 和 L-SDD。它们能够保证对每棵语法分析树都存在一个求值顺序，并且可以和语法分析过程高效结合。

L-SDD 的直观含义是：在一个产生式关联的各属性之间，依赖图的边可以从左到右，但不能从右到左。形式化地看，若有产生式：

A -> X1 X2 ... Xn

右部符号 Xi 的继承属性只能依赖：

1. A 的继承属性；
2. 产生式中 Xi 左侧符号 X1 ... Xi-1 的属性；
3. Xi 自身的属性，但 Xi 的全部属性不能在依赖图中形成环。

课件中的 L-SDD 例子把综合属性标成红色、继承属性标成蓝色：

（插图未导入）

语法制导翻译方案（Syntax-Directed Translation Scheme，SDT）是在产生式右部嵌入程序片段（语义动作）的上下文无关文法。可以把 SDT 看作 SDD 的具体实施方案：SDD 说明属性之间的关系，SDT 说明语义动作应该在分析过程中何时执行。

例如把声明语句的 SDD 改成 SDT：

D -> T { L.in = T.type } L
T -> int { T.type = integer }
T -> float { T.type = float }
L -> { L1.in = L.in } L1, id ...

（插图未导入）

记忆时可以这样区分：

SDD：更像说明书，描述属性如何依赖、如何计算。
SDT：更像执行方案，把语义动作放进产生式右部，说明什么时候执行。

符号表

作用

符号表负责把程序中的名字和它们的属性联系起来。编译器在处理声明语句时把信息填入符号表，在处理使用位置时查询符号表，从而判断该名字是否可见、类型是否正确、存储位置如何安排。

符号表中常见字段如下：

例如对程序：

int x;
float f(int a) {
    int y;
    y = a + x;
}

可以得到一个简化符号表：

符号表不仅服务于语义分析，也服务于后续中间代码生成和目标代码生成。例如代码生成时需要知道变量的类型宽度、偏移地址和函数入口位置。

典型检查

声明与使用关系

声明与使用关系检查主要回答三个问题：

1. 使用前是否已经声明；
2. 同一作用域内是否重复声明；
3. 当前使用位置是否能访问到对应声明。

例如：

int a;
int a;   // 同一作用域重复声明
b = 1;   // b 未声明

对于函数调用，还要检查函数是否声明、参数个数是否一致、实参类型是否能与形参类型匹配：

int add(int x, int y);
add(1);          // 参数个数不匹配
add(1, "abc");   // 参数类型不匹配

这些错误不一定破坏语法结构，但会破坏程序含义，因此属于语义错误。

作用域管理

作用域定义了名字的可见范围，编译器需要根据作用域把名字的声明和使用正确关联起来。常见作用域包括全局作用域、函数作用域、块作用域。

一个常见实现方式是使用栈式符号表：

进入新作用域：压入一个新表
声明名字：插入当前栈顶表
查找名字：从栈顶向下查找，找到最近声明
退出作用域：弹出栈顶表

例如：

int x;
void f() {
    int x;
    x = 1;
}

函数 f 内部的 x = 1 应该绑定到局部变量 x，而不是全局变量 x。这体现了嵌套作用域中的“就近原则”。

作用域和生存期容易混淆：

例如局部变量的作用域通常是所在代码块，而生存期通常是过程调用开始到结束。

类型检查

类型的本质

类型既描述一类值的集合，也描述允许施加在这些值上的操作集合。比如 int 表示整数集合，同时允许加减乘除、比较等操作；数组类型表示一组同类型元素构成的序列，同时允许下标访问。

类型系统的作用主要有：

• 发现无意义或危险的操作，例如整数和字符串直接相加；
• 决定表达式的结果类型，例如 int + float 的结果是否提升为 float；
• 辅助存储分配，例如 int、double、数组所需空间不同；
• 辅助代码生成，例如整数加法和浮点加法可能对应不同机器指令。

常见内容

类型分类

类型可以分为基本类型和复合类型。

复合类型通常可以看作由类型构造符构造出来的类型表达式。例如 array(10, int) 表示包含 10 个整数的数组，function(int, int -> int) 表示两个整数参数、返回整数的函数。

类型转换

类型转换用于在不同类型之间建立可用关系。常见转换包括：

类型转换必须遵循语言规则。一般来说，从小范围到大范围的转换更安全，从大范围到小范围可能丢失信息，例如 double 转 int 会丢弃小数部分。

在中间代码生成时，类型转换也可能对应专门的转换指令：

t1 = inttofloat(i)
t2 = t1 + f

类型等价

类型等价用于判断两个类型是否可以看作同一类型。常见规则有名字等价和结构等价。

例如：

typedef int A;
typedef int B;

若采用名字等价，A 和 B 可能被视为不同类型；若采用结构等价，由于二者本质结构都是 int，则可以视为等价。不同语言对类型等价的规定不同，考试中通常要先看题目给出的语言规则。

类型检查方式

类型检查可以按发生时间分为静态类型检查和动态类型检查。

编译型语言通常尽量在编译期间完成类型检查。若某些类型信息只有运行时才能确定，才需要借助动态检查。

类型检查常用语法制导方式实现。例如：

E -> E1 + E2
if E1.type == int and E2.type == int then E.type = int
else if E1.type == float or E2.type == float then E.type = float
else type_error

这说明语义规则不仅可以计算属性，也可以报告语义错误。

中间语言

中间代码的作用

中间代码又称中间表示（Intermediate Representation，IR），位于源语言和目标机器代码之间。它把源程序转换成一种更适合分析、优化和生成目标代码的形式。

引入中间代码的好处：

没有中间代码时，若有 m 种源语言和 n 种目标机器，可能需要 m * n 个编译器后端；有统一中间代码后，可以拆成 m 个前端和 n 个后端。

flowchart LR
    A["C / Java / Pascal 等源语言"] --> B["统一中间代码 IR"]
    B --> C["x86 代码"]
    B --> D["ARM 代码"]
    B --> E["RISC-V 代码"]

常见表示形式

逆波兰式

逆波兰式也叫后缀表达式，把运算符放在操作数之后。它不需要括号就能表达运算优先级，适合用栈进行求值。

例如：

对 a b c * + 的求值过程：

读 a：入栈
读 b：入栈
读 c：入栈
读 *：弹出 b、c，计算 b*c，结果入栈
读 +：弹出 a、b*c，计算 a+b*c

逆波兰式结构简单，但对复杂控制流、数组引用、函数调用等结构的表达能力不如四元式直观。

三元式

三元式的一般形式为：

NO. (OP, ARG1, ARG2)

它没有显式的结果字段，默认用该三元式的编号表示计算结果。例如表达式 a + b * c 可以表示为：

其中 (1) 表示引用第 1 条三元式的结果。三元式的优点是结构紧凑，不需要大量临时变量；缺点是结果依赖编号，代码优化时如果移动指令，编号引用可能需要随之修改。

间接三元式

间接三元式由两部分组成：

1. 三元式表：保存真正的三元式内容；
2. 间接码表：保存三元式执行顺序。

这样优化时可以只调整间接码表，而不移动三元式本身。

例如：

如果优化需要改变执行顺序，只需要改变指针顺序，不必修改三元式编号，因此间接三元式比普通三元式更适合代码重排。

四元式

四元式的一般形式为：

NO. (OP, ARG1, ARG2, RESULT)

其中 OP 是操作符，ARG1 和 ARG2 是操作数，RESULT 是结果位置。单目运算或赋值语句可以省略某些参数。

四元式也常被口头称为“四元组”。它的四个字段只是固定格式，具体含义要由 OP 决定。普通算术运算中 RESULT 是计算结果；数组赋值中 RESULT 可以表示被写入的数组基址；跳转语句中 RESULT 可以表示跳转目标地址。因此读四元式时不能只按“左边变量一定是 RESULT”机械理解。

表达式 a + b * c 的四元式为：

四元式的优点是结果位置明确，便于优化和代码生成；缺点是会引入较多临时变量。

常见四元式形式：

二目运算是指一个运算符需要两个操作数，形式通常是：

x = y op z  ->  (op, y, z, x)

常见二目运算例子：

注意：布尔表达式如果用于控制流，通常不一定生成 (&&, a, b, t) 这种“算出真假值”的四元式，而是直接生成跳转四元式，并维护 B.true、B.false 两条待回填链。

单目运算是指一个运算符只需要一个操作数，形式通常是：

x = op y  ->  (op, y, _, x)

常见单目运算例子：

如果题目没有特别规定单目负号的 OP 名字，建议写成 uminus，避免和二目减法 (-, a, b, t) 混淆。

数组相关的两个操作符最容易混淆：

(=[], a, i, x)   表示 x = a[i]
([]=, x, i, a)   表示 a[i] = x

也就是说：

=[]  : RESULT = ARG1[ARG2]
[]=  : RESULT[ARG2] = ARG1

所以 ([]=, t13, t9, a) 的含义是 a[t9] = t13，其中 t9 是数组元素的地址偏移，t13 是要写入数组的值。

跳转相关四元式中，RESULT 通常是目标四元式编号。若目标位置暂时未知，可以先写成 _ 或 0，再通过拉链-回填技术补上：

1: (j<, a, b, _)
2: (j, _, _, _)
...
backpatch(1, 5)  -> 1: (j<, a, b, 5)
backpatch(2, 9)  -> 2: (j, _, _, 9)

条件跳转有两种常见写法：

直接关系跳转：
1: (j<, x, y, L)

先计算布尔临时变量，再按真假跳转：
1: (<, x, y, t1)
2: (JT, t1, _, Ltrue)
3: (JF, t1, _, Lfalse)

第一种更短，第二种更贴合布尔表达式 SDD 中 B.true、B.false 的拉链-回填写法。做题时采用哪种，要看题目给的 SDD 规定。如果题目语义规则写的是 gen(JT E.PLACE - 0)、gen(JF E.PLACE - 0)，就使用 JT/JF 这种形式。

例如：

if (a < b)
    x = 1;
else
    x = 2;

可以写成直接关系跳转形式：

1: (j<, a, b, 3)
2: (j, _, _, 5)
3: (=, 1, _, x)
4: (j, _, _, 6)
5: (=, 2, _, x)
6: ...

也可以写成 JT/JF 形式：

1: (<, a, b, t1)
2: (JT, t1, _, 4)
3: (JF, t1, _, 6)
4: (=, 1, _, x)
5: (j, _, _, 7)
6: (=, 2, _, x)
7: ...

图与树

树形表示适合表达表达式的层次结构，图形表示则能表达共享子表达式和控制流关系。

表达式 a + b * c 的语法树可以写成：

      +
     / \
    a   *
       / \
      b   c

如果表达式中存在公共子表达式，例如：

(a + b) * (a + b)

用树表示会出现两个相同的 a + b 子树；用 DAG 表示可以共享这一个子表达式，从而帮助优化器发现重复计算。

flowchart TD
    M["*"]
    P["+<br/>a+b"]
    A["a"]
    B["b"]
    M --> P
    M --> P
    P --> A
    P --> B

控制流通常用控制流图表示。图中结点是基本块，边表示程序执行可能的跳转方向。

中间代码生成

中间代码生成把语义分析得到的信息转化为可优化、可翻译的中间表示。不同语句的翻译重点不同：说明类语句主要填写符号表，表达式和赋值语句主要生成计算四元式，控制流语句需要组织跳转，数组和函数调用则重点处理地址计算与参数传递。

说明类语句

说明类语句用于定义名字、类型和存储信息，通常不直接生成可执行目标代码。它们的主要作用是填写符号表，并为后续语义检查、存储分配和代码生成提供依据。

例如：

int a;
float b;

语义处理时可以把 a、b 插入符号表：

说明类语句的处理重点不是“生成一条运行时指令”，而是“建立编译期信息”。因此它一般服务于三件事：

1. 建立符号表项；
2. 计算变量或数组占用空间；
3. 检查重复声明、类型声明是否合法。

表达式与赋值翻译

常量与简单说明

常量说明需要记录常量名、常量值和类型。例如：

const int N = 10;

符号表中可以记录：

简单变量说明则重点记录类型、宽度和偏移。偏移地址通常按变量声明顺序递增：

offset = 0
声明 int a：a.offset = 0, offset = 4
声明 float b：b.offset = 4, offset = 8

这些信息会在翻译表达式和赋值语句时被查询。例如翻译 a = b + 1 时，需要知道 a、b 是否声明，以及它们的类型是否兼容。

算术表达式

算术表达式通常按语法树的层次自底向上生成临时变量和四元式序列。每个子表达式可以有两个常见属性：

例如表达式：

x = a + b * c;

应先翻译 b * c，再翻译 a + t1：

若用语法制导方式描述，可以写成：

E -> E1 + T
E.place = newtemp()
E.code = E1.code || T.code || gen(+, E1.place, T.place, E.place)

其中 newtemp() 用于生成新的临时变量，gen() 用于产生四元式，|| 表示代码序列连接。

逻辑表达式

逻辑表达式常用于条件语句和循环语句中。为了支持短路求值，逻辑表达式通常不直接生成 true 或 false 的数值结果，而是生成条件跳转代码。

例如：

if (a < b && c < d) S;

短路求值的含义是：如果 a < b 为假，就不必再判断 c < d，直接跳到整个条件的假出口。

一种常见翻译形式是维护两个链：

逻辑与 && 的控制流可以理解为：

flowchart LR
    A["判断 a < b"] -- 真 --> B["判断 c < d"]
    A -- 假 --> F["假出口"]
    B -- 真 --> T["真出口"]
    B -- 假 --> F

这种翻译方式把逻辑表达式和控制流直接结合起来，特别适合 if、while 等语句。

控制流翻译

语句标号与回填

控制流语句会改变程序执行顺序，因此中间代码中需要使用标号和跳转指令。标号有两种出现方式：

在翻译控制流时，经常会遇到“先生成跳转指令，但目标地址暂时不知道”的情况。回填技术就是先把这些未确定目标的跳转指令串成链，等目标标号确定后再统一填写。

例如：

100: if a < b goto _
101: goto _

当真出口和假出口地址确定后，再回填为：

100: if a < b goto 104
101: goto 110

回填技术常用操作：

条件语句

条件语句翻译的关键是组织真假出口。

对于：

if (E) S1 else S2

控制流结构为：

flowchart TD
    A["判断 E"] -- 真 --> B["S1"]
    A -- 假 --> C["S2"]
    B --> D["if 之后"]
    C --> D

示例：

if (a < b)
    x = 1;
else
    x = 2;

对应四元式可以写成：

1: (j<, a, b, 3)
2: (j, _, _, 5)
3: (=, 1, _, x)
4: (j, _, _, 6)
5: (=, 2, _, x)
6: ...

第 1 条是真条件跳转，第 2 条是假分支跳转，第 4 条用于跳过 else 分支。

循环语句

循环语句翻译需要明确三个位置：循环入口、循环体入口、循环出口。

对于：

while (E) S

控制流为：

flowchart TD
    A["循环入口<br/>判断 E"] -- 真 --> B["循环体 S"]
    A -- 假 --> C["循环出口"]
    B --> A

示例：

while (i < n) {
    i = i + 1;
}

四元式可以写成：

1: (j<, i, n, 3)
2: (j, _, _, 6)
3: (+, i, 1, t1)
4: (=, t1, _, i)
5: (j, _, _, 1)
6: ...

循环体执行结束后必须跳回条件判断位置；条件为假时跳到循环之后的位置。for 循环也可以拆成初始化、条件判断、循环体、增量更新四个部分来翻译。

多分支语句

多分支语句典型形式是 switch。它需要根据表达式值选择不同分支，并在每个分支结束时处理是否跳出。

例如：

switch (x) {
case 1: y = 10; break;
case 2: y = 20; break;
default: y = 0;
}

一种顺序比较式翻译为：

1: (j==, x, 1, 4)
2: (j==, x, 2, 7)
3: (j, _, _, 10)
4: (=, 10, _, y)
5: (j, _, _, 11)
7: (=, 20, _, y)
8: (j, _, _, 11)
10: (=, 0, _, y)
11: ...

若分支值很密集，编译器还可能生成跳转表来提高效率；若分支值稀疏，顺序比较或二分查找更合适。

数组与函数翻译

数组

数组翻译的核心是地址计算。数组声明阶段需要记录数组的维度、每一维大小、元素宽度、数组首地址等信息。

数组引用的中间代码通常分成两步：先计算下标对应的地址偏移，再用 =[] 或 []= 完成读写。

t = a[addr]      ->  (=[], a, addr, t)
a[addr] = value  ->  ([]=, value, addr, a)

一维数组 A[i] 的地址通常为：

addr(A[i]) = base(A) + i * width

若数组下标从 low 开始，则为：

addr(A[i]) = base(A) + (i - low) * width

二维数组按行优先存储时，A[i][j] 的地址为：

addr(A[i][j]) = base(A) + ((i - low1) * n2 + (j - low2)) * width

其中 n2 是第二维长度，width 是每个元素占用字节数。

教材中提到的内情向量表可以理解为数组的“描述信息表”，包含：

若地址公式整理为：

T = a - C + V

可以理解为：a 是数组首地址相关部分，V 是由下标计算出的可变偏移，C 是由下界等信息形成的不变修正项。

函数调用

函数说明和函数调用的翻译涉及语义检查与运行时组织。

函数说明阶段需要在符号表中记录：

函数调用阶段需要完成：

1. 检查函数是否声明；
2. 检查实参与形参个数是否一致；
3. 检查实参与形参类型是否兼容；
4. 生成传参代码；
5. 生成调用代码；
6. 接收返回值。

例如：

x = f(a, b);

可以翻译为：

param a
param b
t1 = call f, 2
x = t1

若使用四元式表示：

函数调用与运行环境联系很紧密。调用时通常要建立活动记录，保存返回地址、控制链、实参、局部变量和临时变量；函数结束时再恢复调用现场并把返回值传回调用者。

第7章 运行环境

程序运行时的存储组织与分配

运行环境研究程序执行时数据对象和过程活动如何占用存储空间。它要处理过程、活动、生存期、绑定、环境、状态等概念，并决定目标代码、运行时数据空间和控制栈如何组织。

名字和存储之间有两个容易混淆的对应关系：名字的声明或作用域与存储空间的对应方式偏静态，通常在编译时确定；名字的绑定或生存期与具体存储空间的对应方式偏动态，常在运行时随着过程调用和对象创建变化。

基本概念

过程、活动与生存期

过程是程序中的可调用单位，活动是过程的一次具体执行，生存期描述某对象从建立到失效的时间区间。

绑定

绑定是程序实体与属性之间建立关联的过程，例如名字与类型、名字与存储位置、调用与目标代码地址之间的关联。

环境与状态

环境描述名字到存储位置的映射，状态描述存储位置到值的映射，两者结合才能完整刻画程序运行时语义。

运行时存储的保护对象

运行时需要保护目标代码、程序数据空间以及记录过程调用信息的控制栈，否则程序执行的正确性无法保证。

存储分配基本单元

过程活动记录是运行时存储分配的核心单位，通常包含参数区、返回地址、控制链、局部变量区和临时变量区。

存储分配策略

静态存储分配

在编译时确定对象地址，实现简单，但灵活性差。

栈式存储分配

适合过程调用和递归，遵循后进先出规律，是最常见的运行时管理方式。

堆式存储分配

适合生命周期不规则、大小可变的动态对象，但管理成本较高。

静态运行时存储分配

适用条件

只有当数据对象大小和位置都能在编译时确定，并且语言不支持递归和动态数据结构时，静态分配才足够使用。

局限性

一旦程序需要递归调用、动态申请对象或复杂嵌套作用域，静态分配就难以满足需求。其主要限制包括：

• 数据对象的长度和内存位置必须在编译时可知；
• 不允许递归过程，因为一个过程的所有活动会使用同一组局部名字绑定；
• 不能动态建立数据结构，因为没有运行时存储分配机制。

基于栈的运行时环境的动态存储分配

栈式动态存储分配以过程活动记录为单位管理运行时空间。每次过程调用都会在栈上建立新的活动记录，过程返回时弹出该活动记录，因此天然适合过程调用和递归。

栈区内容

栈中既保存局部变量、临时变量等生存期在本过程本次活动中的数据对象，也保存返回地址、控制链、机器状态等管理过程活动的记录信息。

简单栈式实现

当语言不允许过程嵌套时，只需维护返回关系和局部数据即可，但通常仍允许递归调用。

嵌套过程的实现

访问链

访问链也称静态链或存取链，用于在嵌套作用域中找到外层过程的活动记录。沿访问链向外查找，就可以访问外层过程中的非局部变量。

显示表

显示表直接保存各嵌套层最近一次活动记录的地址，访问非局部变量更快，但维护成本更高。

基于堆的运行时环境的动态存储分配

特点

堆适合管理长度可变、创建与销毁顺序不固定的数据对象，例如链表结点、树结点和对象实例。

典型问题

悬空引用

对象已释放但引用仍存在，会导致非法访问。

内存碎片

频繁分配与回收会造成大量不连续空闲块，降低内存利用率。

内存泄漏

对象不再使用却无法释放，会造成可用内存持续减少。

垃圾回收算法

引用计数

实现直观，每个对象维护被引用次数，计数归零时即可回收。但它在多线程环境下要处理一致性问题，并且难以解决循环引用。

标记清除

先从根集合出发标记可达对象，再把不可达对象视为垃圾清除，通常在内存耗尽或达到阈值时触发。它适用广泛，但容易产生内存碎片。

复制算法

把存活对象复制到新区域，回收效率高且能整理碎片，但通常任何时刻只能使用一半内存，空间利用率偏低。

分代回收

基于“大多数对象朝生夕死”的经验规律，把对象按存活时间划分为新生代和旧生代，分别采用不同回收策略，是现代运行时系统的常见方案。

第8章 代码优化

代码优化概述

优化的目标

代码优化是在不改变程序语义的前提下，对程序进行等价变换，使生成的中间代码或目标代码更高效。

这里的“更高效”通常包括：

• 运行时间更短；
• 占用存储空间更少；
• 访问内存次数更少；
• 寄存器、缓存、指令流水线等硬件资源利用更充分。

例如：

原代码：t1 = 3 * 4
优化：  t1 = 12

这个变换不改变程序结果，但减少了运行时乘法运算。再如：

原代码：
t1 = a + b
t2 = a + b
x = t1 * t2

优化：
t1 = a + b
x = t1 * t1

第二次 a + b 被删除，程序语义不变，但避免了重复计算。

代码优化必须遵守一个底线：只能做等价变换，不能为了快而改变程序原本的含义。因此编译器优化往往依赖控制流分析、数据流分析、别名分析和目标机器信息来判断某个变换是否安全。

提高效率的主要途径

程序运行效率可以从多个层面改进。编译器优化很重要，但它不是唯一途径；从效果上看，算法改进往往收益最大，而编译时优化的特点是自动、系统，并且能利用源程序中不显式出现的中间代码和目标机器信息。

flowchart TD
    A["提高程序效率"] --> B["改进算法"]
    A --> C["源程序级等价变换"]
    A --> D["利用系统程序库"]
    A --> E["编译时优化"]
    B --> B1["改变解题方法<br/>通常收益最大"]
    C --> C1["程序员手工调整<br/>如减少重复计算"]
    D --> D1["调用高效库函数<br/>如排序、矩阵运算库"]
    E --> E1["编译器自动分析和变换<br/>不可完全由人工替代"]

算法层面改进

改进算法通常收益最大。例如把顺序查找改为二分查找，把朴素矩阵乘法换成更好的算法，这类优化能从根本上降低时间复杂度。

顺序查找：O(n)
二分查找：O(log n)

但是算法改进需要理解问题本身，通常由程序员完成，不属于编译器自动优化的主要范围。

源级等价变换

源程序级等价变换是在源代码层面调整写法，使程序更容易高效执行。例如：

// 变换前
for (i = 0; i < n; i++) {
    x = a * b;
    y[i] = x + i;
}

// 变换后
x = a * b;
for (i = 0; i < n; i++) {
    y[i] = x + i;
}

这里 a * b 与循环变量 i 无关，可以移到循环外。这个例子对应后面要学的“循环不变量外提”。

充分利用系统提供的程序库也属于源程序层面的重要优化方式。标准库、数学库、图形库或矩阵运算库通常经过专门优化，可能使用更好的算法、汇编实现、SIMD 指令或缓存友好的数据布局。

// 手写循环复制
for (i = 0; i < n; i++) {
    b[i] = a[i];
}

// 使用库函数，实际实现可能经过目标平台优化
memcpy(b, a, n * sizeof(int));

编译时优化

编译时优化由编译器自动完成。编译器可以系统地利用中间代码、控制流图、数据流方程和目标机器信息进行优化，这是编译技术不可替代的重要作用。

例如，程序员写出：

x = 2 + 3
y = x * 4

编译器可以在编译期间发现 2 + 3 是常量表达式，从而生成：

x = 5
y = x * 4

甚至继续传播：

y = 20

当然，编译器优化不是万能的。若优化会改变副作用、异常行为、内存访问顺序或程序可观察结果，就不能随意进行。

提高效率的几种途径可以对比如下：

优化分类

按作用范围分类

根据优化涉及的源程序范围，可分为局部优化、循环优化和全局优化。

局部优化只需要看一个基本块，分析代价较低；循环优化关注反复执行的代码，收益通常很明显；全局优化范围最大，需要控制流和数据流信息支持。

按所处阶段分类

根据优化相对于编译逻辑功能实现的阶段，可分为中间代码级优化和目标代码级优化。

中间代码级优化更关注“程序语义和计算结构”，目标代码级优化更关注“机器执行效率”。

按具体技术分类

常见优化技术如下：

常量合并与常量传播常常连在一起使用：

原代码：
x = 2
y = x + 3
z = y * 4

常量传播：
y = 2 + 3
z = y * 4

常量合并：
y = 5
z = y * 4

继续传播和合并：
z = 20

公共子表达式删除示例：

原代码：
t1 = a + b
t2 = c + d
t3 = a + b
x = t1 * t3

优化：
t1 = a + b
t2 = c + d
x = t1 * t1

前提是从 t1 = a + b 到 t3 = a + b 之间，a 和 b 的值没有被重新定值。

无用赋值删除示例：

原代码：
x = 1
x = 2
y = x

优化：
x = 2
y = x

因为第一次 x = 1 的值在被使用前就被 x = 2 覆盖了。

死代码删除示例：

原代码：
if false goto L1
goto L2
L1: x = 1
L2: y = 2

优化：
y = 2

若能确定 L1 永远不可达，则 x = 1 属于死代码。

无用转移语句删除示例：

原代码：
goto L1
L1: x = y

优化：
x = y

如果跳转目标正好是下一条语句，跳转本身没有意义，可以删除。

循环不变量外展示例：

原代码：
while (i < n) {
    t = a * b
    x[i] = t + i
    i = i + 1
}

优化：
t = a * b
while (i < n) {
    x[i] = t + i
    i = i + 1
}

只要 a 和 b 在循环中不变，a * b 就没有必要每轮重复计算。

函数内嵌示例：

int inc(int x) { return x + 1; }
y = inc(a);

可以展开为：

y = a + 1;

这样减少函数调用、传参和返回的开销，但函数体过大时会导致目标代码膨胀。

循环转换中最典型的是运算强度削弱：用开销较小的运算替代开销较大的运算。

强度削弱例子：

原代码：
i = 0
while (i < n) {
    t = 4 * i
    x = a[t]
    i = i + 1
}

优化：
i = 0
t = 0
while (i < n) {
    x = a[t]
    i = i + 1
    t = t + 4
}

这里 i 是基本归纳变量，4*i 是导出归纳变量。乘法 4*i 被替换为加法 t=t+4，循环每执行一次，t 与 i 同步更新。

这些技术之间常常组合使用：先做循环不变量外提和强度削弱，再通过基本块优化删除重复计算和无用临时变量，最后在目标代码级进一步做寄存器分配和指令优化。

局部优化

基本块

定义

局部优化以基本块为单位。基本块是一段顺序执行的中间代码序列，它只有一个入口和一个出口：

• 唯一入口：只能从基本块第一条语句进入；
• 唯一出口：控制流只从基本块最后一条语句离开；
• 基本块内部除了最后一条可能改变控制流外，一般不包含跳转到块外的语句。

因此，基本块内部语句的执行关系比较简单，适合做常量合并、公共子表达式删除、无用赋值删除等局部优化。

划分方法

基本块划分不是任意划分，而是有固定规则。通常先找入口语句，再由入口语句向后扩展形成基本块。

入口语句包括：

1. 程序的第一条语句；
2. 条件转移或无条件转移的目标语句；
3. 紧跟在条件转移语句或无条件转移语句后面的语句。

确定入口后，从每个入口语句开始，一直包含到下一入口语句之前，或者到下一条转移语句，或者到程序停止、暂停处为止。没有被任何基本块包含的语句一般是不可达代码，可以删除。

例如：

1  i = 0
2  t = a + b
3  if t > 0 goto 6
4  x = 1
5  goto 7
6  x = 2
7  y = x

入口语句为 1、4、6、7，因此可划分为：

这个例子的控制流可以画成：

flowchart TD
    B1["B1: 1-3"] -->|t > 0| B3["B3: 6"]
    B1 -->|t <= 0| B2["B2: 4-5"]
    B2 --> B4["B4: 7"]
    B3 --> B4

控制流图

程序的控制流图，也称流图，是一个具有唯一首结点的有向图，通常记为 $G=(N,E,n_0)$：

• $N$ 是结点集合，每个结点通常对应一个基本块；
• $E$ 是有向边集合，表示基本块之间可能的执行流向；
• $n_0$ 是唯一首结点，表示程序控制流的入口。

控制流图把“代码的线性顺序”转成“可能执行路径”的图结构。后面的循环查找、必经结点计算、到达定值分析、活跃变量分析都要建立在控制流图之上。

DAG 优化

DAG 的作用

DAG 是无环路的有向图。对一个基本块构造 DAG 后，可以把基本块内部的计算关系表示出来，从而更直观地识别公共子表达式、冗余赋值和常量合并机会。

结点类型

基本块的 DAG 结点一般带有标记：

若叶结点是标识符，有时会给它加下标 0，表示该变量进入基本块时的初值，例如 a0。

常见四元式与 DAG 结点的大致关系如下：

典型收益

可用于删除重复计算、压缩中间代码和识别无用赋值。基本块 DAG 的构造思路可以概括为：

1. 为变量和常量建立叶结点；
2. 遇到运算时，先查找是否已有相同运算结点；
3. 若已有相同运算结点，则复用结点，形成公共子表达式删除；
4. 若操作数是常量，则直接计算结果，形成常量合并；
5. 最后根据 DAG 重新生成中间代码，丢弃无用赋值。

例如：

原基本块：
t1 = a + b
t2 = a + b
t3 = t1 * t2
x = t3

DAG 优化后：
t1 = a + b
t3 = t1 * t1
x = t3

如果 t3 后续不需要保留为变量名，还可以继续压缩为：

t1 = a + b
x = t1 * t1

控制流分析与循环查找

控制流分析的目标是从流图中理解程序可能怎样执行。循环优化尤其依赖控制流分析，因为编译器必须先知道哪些基本块构成循环，才能判断哪些计算会被反复执行。

一个结点序列能够构成循环，通常需要满足两个核心条件：

这两个条件保证了“这是一段可反复执行、并且入口明确的代码区域”，便于后续做代码外提和强度削弱。

必经结点

在流图 $G$ 中，如果从首结点 $n_0$ 到结点 $n_j$ 的每一条路径都必须经过结点 $n_i$，则称 $n_i$ 是 $n_j$ 的必经结点，记为：

结点 $n$ 的全部必经结点构成必经结点集，记为 $D(n)$。

例如，若所有到达 B4 的路径都必须先经过 B2，那么 B2 DOM B4。必经关系是一个偏序关系，它能回答“某个结点是否一定在另一个结点之前执行”。

必经结点常用迭代公式求解：

其中 pred(n) 表示 n 的前驱结点集合。

回边

在流图中，若有一条有向边 $a \to b$，并且 $b$ 是 $a$ 的必经结点，即 $b \ DOM \ a$，则称 $a \to b$ 为回边，记为 <a,b>。

直观理解：如果执行到 a 之前一定经过 b，而现在又从 a 跳回 b，这就形成了一个“回到前面”的循环结构。

flowchart TD
    Entry["入口"] --> B1["B1"]
    B1 --> B2["B2"]
    B2 --> B3["B3"]
    B3 -->|回边| B2
    B3 --> Exit["出口"]

图中 B3 -> B2 是回边，因为到达 B3 必须经过 B2，即 B2 DOM B3。

自然循环

由回边可以求自然循环。设 <n,d> 是一条回边，其中 d 是循环入口，则自然循环由以下结点构成：

• 入口结点 d；
• 回边起点 n；
• 所有能够到达 n，且到达过程中不经过 d 的结点。

也就是说，自然循环包含“从入口 d 出发，最终能绕回 d 的那一片区域”，并且 d 是这个循环的唯一入口。

求自然循环时常用的逆向收集思路是：

1. 发现回边 <n,d>；
2. 先把 n 和 d 放入循环集合；
3. 从 n 开始沿前驱边反向搜索；
4. 遇到 d 停止，其他能反向追溯到的结点都加入循环。

自然循环是循环优化的主要对象。例如对一个自然循环做数据流分析后，才能判断某条语句是不是循环不变量，或者某个变量是不是归纳变量。

数据流分析

数据流分析研究的是：程序在不同位置上，变量的值、表达式的可用性、变量是否还会被使用等信息如何沿控制流传播。它是全局优化和循环优化的基础。

常见数据流信息包括：

基本概念

定值点与引用点

点是中间代码序列中的某个位置，可以分为入口点、出口点和相邻点。

定值点表示变量获得值的位置。常见定值方式包括赋值语句、输入语句，以及函数调用时形参与实参的结合。例如：

1  x = 3        // x 的定值点
2  y = x + 1    // x 的引用点，y 的定值点

引用点表示变量值被使用的位置。在第 2 行中，x 被读取，所以第 2 行是 x 的引用点。

到达定值

若变量 A 在点 d 获得一个定值，并且从 d 到点 p 存在一条通路，且通路上没有对 A 的重新定值，则称 A 在 d 的定值到达点 p。

例如：

1  x = 1
2  y = x + 1
3  x = 2
4  z = x + 1

第 1 行对 x 的定值可以到达第 2 行，因为中间没有重新给 x 赋值；但它不能到达第 4 行，因为第 3 行重新定义了 x。

ud 链与 du 链

ud 链是引用-定值链，从某个引用点出发，找出所有可能到达该引用点的定值点。

du 链是定值-引用链，从某个定值点出发，找出该定值可能到达的所有引用点。

两者方向相反：

例如：

1  x = 1
2  if c goto 4
3  x = 2
4  y = x

在第 4 行引用 x 时，可能来自第 1 行，也可能来自第 3 行，所以第 4 行 x 的 ud 链为 {1, 3}。

活跃变量

如果在程序中某点 P，变量 A 的当前值沿着某条路径在未来会被引用，并且在被引用之前没有被重新定义，则称 A 在点 P 是活跃的；否则称 A 在点 P 是死亡的。

例如：

1  x = 1
2  x = 2
3  y = x

第 1 行后，x=1 的值还没被使用就被第 2 行覆盖，因此第 1 行的定值是死亡的。第 2 行后，x=2 会在第 3 行被使用，因此 x 是活跃的。

数据流方程

数据流方程用集合描述信息在基本块之间的传播。常见集合包括：

不同分析问题的“信息”不同：到达定值分析传播的是定值点集合，可用表达式分析传播的是表达式集合，活跃变量分析传播的是变量集合。

到达定值分析

到达定值分析用于求解某个程序点上可能到达的定值点，适合做常量传播、无用赋值删除和 ud 链构造。

对基本块 B，方程为：

直观理解是：一个基本块出口处的到达定值，等于本块新产生的定值，加上流入本块且没有被本块杀死的旧定值。

例如：

B:
1  x = 1
2  y = 2
3  x = 3

若只看这个基本块内部，x=1 会被 x=3 杀死，所以 gen[B] 中保留第 2 行和第 3 行的定值，而不保留第 1 行对 x 的旧定值。

可用表达式分析

表达式 x + y 在点 P 可用，是指从初始结点到 P 的每条路径上都计算过 x + y，并且最后一次计算 x + y 后，x 和 y 都没有被重新定值。

可用表达式分析用于公共子表达式删除。例如：

1  t1 = a + b
2  c = a + b

如果第 1 行到第 2 行之间没有改变 a 或 b，则第 2 行的 a + b 可直接复用第 1 行结果。

常见方程为：

对于开始块：

对于其他基本块：

这里使用交集，是因为表达式必须在所有进入路径上都已经可用，才能保证复用安全。

活跃变量分析

活跃变量分析从程序后面向前传播，判断某个变量的当前值未来是否还会被使用。它常用于寄存器分配和死代码删除，是目标代码生成阶段的重要依据。

对基本块 B，定义：

• $def_L(B)$：在基本块 B 中被定值，且定值之前没有先在 B 中被引用的变量集合；
• $use_L(B)$：在基本块 B 中被引用，且引用之前没有先在 B 中被定值的变量集合。

方程为：

其中 succ(B) 表示 B 的后继基本块集合。

例如：

B:
1  t = x + y
2  x = 3
3  z = x + 1

在这个基本块中，x 和 y 在第 1 行被引用且此前未在块内定值，所以属于 use_L(B)；第 2 行对 x 定值，第 3 行对 z 定值，因此 x、z 属于 def_L(B)。如果某个变量不在出口活跃，且它的定值后没有任何引用，就可能成为死代码删除的对象。

循环优化

循环是代码优化中收益最明显的区域，因为循环体中的语句会被反复执行。一次小的优化如果发生在循环内部，可能随着迭代次数被放大很多倍。

循环优化一般需要两类准备：

1. 通过控制流分析找到循环，尤其是自然循环；
2. 对循环涉及的所有基本块做数据流分析，判断哪些变量会变化、哪些定值能到达、哪些表达式可用。

常见循环优化包括代码外提、强度削弱和归纳变量消除。

循环前置结点

循环前置结点是在循环入口点之前新建立的一个基本块，它以循环入口结点为唯一后继。它的作用是给“移出循环的代码”提供一个安全位置。

flowchart TD
    P["循环前置结点"] --> H["循环入口"]
    H --> B["循环体"]
    B --> H
    H --> Exit["循环出口"]

如果要把循环中的不变代码移出去，通常不是随便放到循环前某个地方，而是放到循环前置结点中。这样可以保证这些代码在进入循环前执行一次，并且不会影响循环外其他控制流。

代码外提

代码外提是把循环中结果不变的运算提到循环前置结点。判断一条语句是否能外提，核心看它依赖的操作数在循环内是否会改变，以及外提后是否改变异常、副作用和执行次数语义。

例如：

原代码：
while (i < n) {
    t = a * b
    x[i] = t + i
    i = i + 1
}

优化后：
t = a * b
while (i < n) {
    x[i] = t + i
    i = i + 1
}

如果 a 和 b 在循环中没有被重新赋值，那么 a * b 每轮结果都相同，放在循环外只计算一次即可。

但不是所有看起来“不变”的代码都能外提。例如可能触发异常的表达式、具有函数调用副作用的表达式，或者原本只在某些分支中执行的语句，都需要额外分析。

强度削弱

强度削弱是把循环中开销较高的运算替换为开销较低的等价运算，典型情况是把乘法换成加法。

基本归纳变量是循环中按固定步长变化的变量，例如：

i = i + 1

导出归纳变量是由基本归纳变量线性计算得到的变量，例如：

t = 4 * i

强度削弱的思路是：既然 i 每轮增加 1，那么 4*i 每轮增加 4，不必每次重新做乘法。

原代码：
i = 0
while (i < n) {
    t = 4 * i
    x = a[t]
    i = i + 1
}

优化后：
i = 0
t = 0
while (i < n) {
    x = a[t]
    i = i + 1
    t = t + 4
}

循环转换中常见的强度削弱情况如下：

归纳变量消除

强度削弱之后，循环中常常会同时存在基本归纳变量和导出归纳变量。如果某个归纳变量只用于计算另一个归纳变量，并且已经可以用导出变量替代，就可以进一步删除它，这叫归纳变量消除。

例如：

优化前：
i = 0
t = 0
while (i < n) {
    x = a[t]
    i = i + 1
    t = t + 4
}

如果循环条件也能安全改写为对 t 的判断，就可以减少对 i 的维护：

优化后：
t = 0
limit = 4 * n
while (t < limit) {
    x = a[t]
    t = t + 4
}

这个变换的核心是保持循环次数和数组访问地址不变。实际编译器会根据循环边界、步长、溢出风险和变量后续是否还被使用来判断能否删除归纳变量。

第9章 目标代码生成

代码生成器设计中的要点

输入与输出

代码生成器以中间表示为输入，以汇编代码或机器代码为输出，是编译器后端的最后一步。

三个核心问题

指令选择

需要决定某段中间代码应映射为哪组机器指令，既要保证正确，又要尽量高效。它的复杂度依赖于 IR 的层次、目标指令本身的特点，以及期望生成目标代码的质量。

寄存器分配

寄存器数量有限，必须决定哪些变量留在寄存器中、哪些变量暂存于内存，以及为变量分配哪个寄存器。这直接影响运行效率，也是一个经典的 NP 完全问题。

指令调度

需要合理安排指令执行顺序，以减少流水线停顿和资源冲突。它同样具有较高复杂度，在现代处理器上会显著影响目标代码质量。

简单代码生成器的构造

基本处理过程

简单代码生成器通常针对每个基本块完成。基本过程是依次遍历基本块中的三地址指令，确定哪些操作对象需要加载到寄存器，生成从内存加载到寄存器的指令，再生成计算指令，并在必要时把结果从寄存器写回内存。

辅助数据结构

寄存器描述符

记录每个寄存器当前保存了哪些变量的值。

地址描述符

记录每个变量当前值可能位于哪些位置，例如寄存器、内存或二者同时存在。

getReg 思想

getReg(I) 的输入是当前待翻译指令 I，输出是该指令中变量的寄存器分配情况。当需要寄存器时，优先复用已经装载目标变量的寄存器；若相关变量不在寄存器中且存在空闲寄存器，则返回空闲寄存器；否则选择一个已经占用的寄存器，根据寄存器描述符把其中仍需保留的变量写回内存，然后复用该寄存器。

指令选择方法

树匹配

当中间表示可以组织为表达式树时，可通过树模式匹配选择更高质量的目标指令序列。对树状 IR 来说，每条机器指令都可以看作覆盖 IR 树的一部分，代码生成就是选择一组合适的 tree pattern 覆盖整棵树。

寄存器分配方法

固定分配

固定分配会为局部变量、堆栈、临时计算等固定预留寄存器，其他变量保留在内存中。实现简单，但资源利用率有限。

局部分配

局部分配以基本块为单位进行寄存器管理：基本块开始时加载需要的变量，块内按需分配寄存器，结束时写回必要结果，并根据指令持续更新寄存器描述符和地址描述符。

线性扫描

线性扫描先确定变量的活跃范围和活跃区间。活跃范围是变量活跃的程序点集合，活跃区间是包含该范围的最小连续区间。画出每个变量的活跃区间时间图后，按顺序分配寄存器；若寄存器不够，就将某些变量 spill 到内存中。

图着色

图着色把同时活跃的变量之间连边，形成冲突图，然后进行点着色。颜色数对应需要的寄存器数，两个相邻变量不能使用同一个寄存器。这种方法质量高，但实现复杂。

复习建议

建议重点

先建立整体框架

复习时建议先把“前端、优化、后端”三大部分串起来，明确每一章在编译器中的位置，再进入细节。

再抓核心链路

可以按“文法与自动机 -> 词法分析 -> 语法分析 -> 语义分析 -> 中间代码 -> 优化 -> 目标代码生成”的链路进行记忆。

最后突破高频难点

建议重点吃透以下内容：

高频必考概念

文法分类、FIRST/FOLLOW、LL(1) 条件、LR 项目集规范族、符号表、类型检查、四元式、活动记录、DAG 优化、数据流分析、寄存器分配。

容易混淆的概念

最左推导与最右推导、句型与句子、NFA 与 DFA、综合属性与继承属性、静态链与动态链、ud 链与 du 链、局部优化与全局优化。

适合结合题目练习的部分

子集法构造 DFA、LL(1) 分析表构造、LR 项目集闭包与 GO 函数、四元式生成、活跃变量分析与到达定值分析。

相关笔记

• 编译原理修改版笔记 — 修改版笔记
• 编译原理与设计 — 考试复习大纲
• 编译原理 MOC