SUN 编译引论
基本概念
编译程序与翻译程序
**编译程序（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）
词法分析器（扫描器）从左到右读取源程序字符流，根据语言的词法规则，识别各类单词，输出属性字流，为后续语法分析提供规范化输入。
输入：
源程序字符流输出：
Token（属性字流）例：
源程序：
a = b + 3;词法分析结果：
<id,a> <=> <id,b> <+> <num,3> <;>
任务：
- 去掉空格
- 识别关键字
- 识别标识符
- 识别常数
语法分析（Syntax Analysis）
语法分析器根据文法规则判断属性字流是否构成合法句子，并构造语法树或分析树，反映程序的层次结构。
输入：
Token流输出：
语法树（Syntax Tree）例：
= / \ a + / \ b 3作用：
检查程序是否符合语法规则。
例如：
a = + b 3语法错误。
语义分析与中间代码生成
语义分析检查程序在“形式正确”之外是否“含义正确”，例如标识符是否先声明后使用、表达式类型是否兼容。随后可进一步生成中间代码。
代码优化
优化阶段对中间表示进行等价变换，减少冗余计算，改善控制流与数据流结构，提高运行效率。
目标代码生成
目标代码生成器把优化后的中间代码翻译为汇编代码或机器代码，并处理寄存器分配、指令选择等问题。
前端与后端
前端
前端主要包含词法分析、语法分析、语义分析以及中间代码生成。它更依赖源语言特性，与目标机器关系较弱。
后端
后端主要负责优化和目标代码生成，更依赖目标机体系结构、指令系统和存储模型。设计变化最大
支撑模块
表格管理
编译过程中往往需要维护符号表、常量表、类型表、标号表等数据结构，为语义检查和代码生成提供支持。
出错处理
一个实用编译器不能在遇到首个错误时立即崩溃，而应尽量定位错误、恢复分析，并继续报告后续错误。
遍与扫描策略
一遍扫描适合结构简单、依赖少的语言；多遍扫描则更利于分阶段处理复杂语义。遍数设计需要在实现复杂度、内存占用和编译效率之间权衡。
编译程序结构的实例模型
典型结构示例
一遍编译程序
一遍编译程序边扫描边翻译，实现简单、速度快，但对语言结构限制较强，不适合复杂语义处理。
两遍与三遍编译程序
多遍结构把不同任务分散到不同阶段，更利于处理中间表示、优化和复杂语义约束。
现代编译器框架
如 Tiger 编译器和 GCC 一类系统，通常具备清晰的前端、优化器和后端分层，便于移植、扩展与复用。
编译程序的构造
构造要素
源语言
需要明确定义词法、语法和语义规则，否则编译器实现没有统一依据。
目标语言
目标语言决定生成结果的形式，可能是机器语言、汇编语言或中间语言。
编译方法与工具
常见工具包括词法分析器生成器、语法分析器生成器、优化框架和代码生成工具链。
生成方式
手工编写
直接使用某种编程语言实现编译程序，灵活性高，但工作量较大。
移植
将已有编译器迁移到新平台时，通常重点修改与机器相关的后端部分。
自编译
用某语言编写该语言自身的编译器，是编译系统成熟的重要标志。
自动生成
借助 Lex、Yacc、Bison 等工具自动生成部分编译器模块，可以显著降低开发成本。
第2章 形式语言与自动机理论基础
文法和语言
字符串与集合基础
字母表
字母表
字符串
运算与闭包
字符串和字符串集合常见运算包括连接、幂、集合乘积、正闭包和自反闭包。这些运算构成后续正规式和文法定义的基础。
文法的定义
四元组表示
文法通常写作
元语言
用于描述另一种语言的语言称为元语言。文法本身就是一种元语言工具，它帮助我们精确定义程序设计语言的结构。
推导与句型
推导
文法通过产生式不断替换非终结符形成字符串。需要区分直接推导、多步推导以及零步或多步推导。
最左推导与最右推导
最左推导每次替换最左边的非终结符，最右推导每次替换最右边的非终结符。最右推导的逆过程称为规范规约，是 LR 分析的理论基础。
句型与句子
句型是推导过程中出现的任意符号串，句子是只包含终结符的句型。规范句型与规范规约在自下而上分析中很关键。
文法递归与等价
左递归与右递归
若某非终结符能推导出以自身开头的串，则称为左递归；若推导出以自身结尾的串，则称为右递归。左递归会直接影响 LL 分析器构造。
文法等价
两个文法如果生成的语言相同，则称它们等价。实际编译中经常把不利于分析的文法改写为等价但更易处理的形式。
文法的表示方式
BNF 与扩展 BNF
BNF 适合严格定义语法结构，扩展 BNF 在此基础上加入重复、可选等简写能力，更接近工程实践。
语法图
语法图将文法规则可视化，便于直观理解语法结构与推导路径。
语法树与二义性
语法分析树
语法树展示句子的层次结构，是语义分析和代码生成的重要基础。
二义文法
如果同一个句子对应多棵不同的语法树，文法就是二义的。二义性会导致语义不唯一，通常需要通过改写文法或规定优先级与结合性解决。
文法分类
0 型文法
又称短语结构文法，对应图灵机，描述能力最强。
1 型文法
又称上下文有关文法，对应线性有界自动机。
2 型文法
又称上下文无关文法，对应非确定下推自动机，是编译原理中语法分析最核心的文法类别。
3 型文法
又称正规文法，对应有限自动机，主要用于词法分析。
有限自动机
DFA
定义
确定有限自动机记作
特点
DFA 在任一状态读入一个符号后，下一状态唯一确定，因此实现简单，适合直接构造词法分析器。
NFA
定义
非确定有限自动机与 DFA 的区别在于状态转换函数的结果是状态集合，并且允许
特点
NFA 描述灵活，构造方便，但实现时通常需要先转换为 DFA。
NFA 与 DFA 的等价性
理论结论
任何 NFA 都存在等价的 DFA，它们识别同一个正规语言。
关键概念
自动机化简
消除无关状态
先去掉不可达状态和无用状态，以减少自动机规模。
合并等价状态
通过划分法识别对所有输入串表现完全一致的状态，并将其合并，得到最小化 DFA。
正规式与有限自动机
正规式
基本运算
正规式通过并、连接和闭包三类运算描述正规语言，是词法规则最常见的形式化表示。
正规集
由正规式定义的语言称为正规集。正规集与有限自动机在表达能力上完全等价。
正规式与自动机的互换
RE 转 FA
可先根据正规式构造 NFA，再进行确定化与最小化，得到 DFA。
FA 转 RE
通常通过状态消去或拓广自动机的方法，把自动机重新转写为正规式。
第3章 词法分析器
词法分析与词法分析程序
任务定位
核心目标
词法分析要解决两个问题：如何定义单词规则，以及如何从字符流中识别出这些单词。
阶段位置
它是编译前端的第一步，直接面向源程序字符序列，输出更适合语法分析处理的记号流。
词法分析程序设计与实现
输入与输出
单词
单词是语言中具有独立意义的最小语法单位，典型类别包括关键字、标识符、常数、运算符和界限符。
属性字 Token
词法分析器通常输出二元组或多元组形式的 Token，例如类型和值的编码。它本质上是单词的内部表示。
源程序预处理
输入缓冲
双缓冲或对半互补缓冲机制能够提高字符读取效率，减少频繁 I/O 带来的开销。
预处理内容
常见预处理包括删除注释、过滤无关空白、宏替换、文件包含和条件编译展开。
词法分析器设计
状态图构造
通常为每类单词先单独设计状态图，再统一合并为总体自动机。
冲突消解
在合并状态图后，需要处理终态冲突、优先级冲突和保留字识别等问题。
词法分析器实现方式
数据中心法
通过状态转换表驱动识别过程，结构清晰，适合自动生成。
程序中心法
直接以程序逻辑描述状态变化，灵活性更高，但不如表驱动方式直观统一。
词法分析程序的自动生成
Lex 与 Flex
Lex/Flex 可以根据正规式规则自动生成词法分析器。它们将“规则描述”与“识别程序”分离，是词法分析自动化的重要工具。
第4章 语法分析：自上而下分析
语法分析综述
语法分析器的功能
语法分析器接收词法分析器输出的属性字流，根据源语言文法识别其结构，并构造语法树或其他结构化表示。
两类基本方法
自上而下分析
从开始符号出发，尝试推导出输入串，本质上是在“预测”输入应当符合什么结构。
自下而上分析
从输入串出发，通过不断规约恢复出开始符号，本质上是在“归纳”输入属于哪种结构。
自上而下分析
一般思想
自上而下分析沿着推导方向展开，但如果直接采用回溯，会带来大量重复尝试，效率较低。
不确定性的来源
公共前缀
多个候选式可能以相同前缀开头，导致分析器无法立即决定使用哪一条产生式。
左递归
若文法存在左递归，自上而下分析会陷入无限展开，必须先改写文法。
消除回溯的关键方法
提取左公因子
通过把共同前缀提出，延后分支决策时机，使分析器能够在读入更多符号后再选择候选式。
消除左递归
将左递归文法等价改写为非左递归文法，是构造 LL 分析器的前提之一。
FIRST 集
FIRST 集用于描述某个串可能推出的终结符首符号集合，是构造预测分析表的重要依据。
递归下降分析方法和递归下降分析器
递归下降分析
把每个非终结符对应为一个递归子程序，程序之间按文法规则相互调用，结构与文法非常接近。
LL(1) 分析器
含义
LL(1) 表示自左向右扫描输入、进行最左推导，并且每次最多向前查看 1 个输入符号。
组成
典型 LL(1) 分析器由总控程序、分析栈和分析表组成。
分析表构造
分析表需要结合 FIRST 集和 FOLLOW 集构造。若表中不存在冲突，则文法是 LL(1) 文法。
结论
LL(1) 分析简单、易实现，但适用文法范围相对受限，很多实际语言语法需要改写后才能使用。
第5章 语法分析：自下而上分析
基于移进规约的自下而上分析
基本思想
自下而上分析通过不断把输入串中的某些片段规约为非终结符，最终规约为开始符号。
基本概念
短语
短语是句型中符合某个非终结符推导结果的子串。
直接短语
若某短语在一次推导中直接由一个非终结符推出，则称为直接短语。
句柄
句柄是当前规范句型中最左的直接短语，对其规约恰好对应规范推导的逆过程。
LR 分析
LR 方法概述
LR 分析是一类自左向右扫描输入、按最右推导逆过程进行规范规约的语法分析方法，适用范围广，错误检测能力强。
LR(k) 的含义
其中
LR 分析器组成
分析栈
栈中同时维护状态信息和文法符号信息，是驱动移进、规约、接受与报错动作的核心结构。
分析表
分析表由 action 表和 goto 表组成。action 决定移进、规约、接受还是报错，goto 决定规约后转入哪个状态。
LR(0) 分析器
项目
LR(0) 项目是在产生式右部插入一个圆点，用于表示当前识别进度。
活前缀
活前缀是规范句型中不包含句柄后任意符号的前缀，LR 分析的状态本质上就是对活前缀信息的压缩表示。
项目分类
常见有移进项目、待约项目、规约项目和接受项目，不同项目对应不同分析动作。
构造步骤
需要完成拓广文法、求项目闭包、构造 GO 函数，并形成项目集规范族。
冲突与改进
移进-规约冲突
分析器在某状态下既可能移进又可能规约，说明仅靠当前信息无法唯一决定动作。
规约-规约冲突
分析器在某状态下可能按两个不同产生式规约，说明文法或分析能力不足。
SLR(1)
SLR(1) 在 LR(0) 基础上引入 FOLLOW 集辅助判断规约条件，能解决部分冲突。
LR(1)
LR(1) 项目在项目基础上引入 1 个展望符，分析能力更强，但状态数通常更多。
LALR(1)
LALR(1) 通过合并同心 LR(1) 项目集，在尽量保持 LR(1) 分析能力的同时减少状态数，因此工程应用广泛。
二义文法与 LR
任何二义文法都不是 LR 文法，但在实际语言处理中，可以通过人为规定优先级和结合性来消除某些二义性。
LR 分析的错误处理与恢复
错误类型
编译过程中的错误可分为词法错误、语法错误、语义错误，以及违反环境约束的错误。
恢复策略
紧急恢复
跳过部分输入符号，直到遇到同步记号再继续分析，简单但可能丢失较多上下文。
短语级恢复
在局部进行有限改正，尽量保留后续分析环境。
出错产生式
在文法中显式加入错误相关规则，使分析器能够识别某些常见错误模式。
全局纠正
从整体上寻找代价最小的修改方案，理论意义大于工程实用价值。
语法分析程序自动生成器
Yacc
Yacc 常用于生成 LALR(1) 分析器。它允许开发者描述文法规则和语义动作，从而自动生成语法分析程序。
第6章 语义分析与中间代码生成
语法制导翻译
语义分析的目标
语义分析关注程序“表达了什么”，而不仅是“写得像不像一个合法句子”。其核心任务包括名字管理、作用域处理和类型检查。
语法制导翻译的含义
语法制导翻译是在语法分析过程中同步进行语义处理的一种方法，常用属性文法来描述。
属性与语义规则
综合属性
综合属性由子结点信息向父结点汇总，适合表达自底向上的信息传递。
继承属性
继承属性由父结点或兄弟结点传入，适合表达上下文相关信息。
依赖图
依赖图描述属性之间的计算先后关系，是判断属性计算顺序是否可行的重要工具。
符号表
作用
符号表负责记录标识符的名字、类型、作用域、存储类别、地址偏移等信息，是语义分析与代码生成的重要支撑。
典型检查
声明与使用关系
需要检查标识符是否先声明后使用，是否重复声明，是否越过作用域边界访问。
作用域管理
作用域决定名字在哪些区域可见，常见实现方式包括栈式符号表、作用域链和嵌套表结构。
类型检查
类型的本质
类型既描述一类值的集合，也描述允许施加在这些值上的操作集合。
常见内容
类型分类
包括基本类型和复合类型，例如数组、记录、指针、函数等。
类型转换
需要区分显式转换与隐式转换，同时考虑类型提升与强制转换是否合法。
类型等价
类型等价可分为名字等价和结构等价，不同语言采用的规则不同。
类型检查方式
可分为静态类型检查、动态类型检查和无类型方式。编译型语言更强调静态检查能力。
中间语言
中间代码的作用
中间代码位于源语言和目标代码之间，是实现机器无关优化和分层设计的重要媒介。
常见表示形式
逆波兰式
后缀表达式形式简单，适合表达式求值。
三元式
三元式省略显式结果名，结构紧凑，但不便于代码移动。
间接三元式
通过间接码表改善三元式在优化中不便重排的问题。
四元式
四元式形式统一，表达清晰，是教材和实现中最常用的中间表示之一。
图与树
图结构更适合表达共享子表达式、控制流和依赖关系，在优化阶段尤其重要。
中间代码生成
说明类语句
说明类语句通常不直接生成可执行代码，而是用于填写符号表、分配类型信息和计算地址布局。
表达式与赋值翻译
常量与简单说明
需要记录常量值、变量类型、偏移地址等基础信息。
算术表达式
通常按运算优先级生成临时变量与四元式序列。
逻辑表达式
逻辑表达式翻译常与短路求值、真假出口和回填技术结合使用。
控制流翻译
语句标号与回填
标号常用于描述跳转目标。回填技术用于处理“先使用、后定义”的跳转地址问题。
条件语句
if 与 if-else 翻译的关键在于真假出口的组织和跳转目标的连接。
循环语句
while、for 等循环结构通常需要明确入口、循环体和出口三个位置，并配合回填维护控制流。
多分支语句
switch 翻译需要处理多个分支比较、默认分支和跳转组织。
数组与函数翻译
数组
数组翻译的重点在于地址计算，需要结合维度信息、基址和元素宽度求得偏移量。
函数调用
函数翻译涉及实参与形参匹配、活动记录建立、返回值传递和调用现场保护。
第7章 运行环境
程序运行时的存储组织与分配
基本概念
过程、活动与生存期
过程是程序中的可调用单位，活动是过程的一次具体执行，生存期描述某对象从建立到失效的时间区间。
绑定
绑定是程序实体与属性之间建立关联的过程，例如名字与类型、名字与存储位置、调用与目标代码地址之间的关联。
环境与状态
环境描述名字到存储位置的映射，状态描述存储位置到值的映射，两者结合才能完整刻画程序运行时语义。
运行时存储的保护对象
运行时需要保护目标代码、程序数据空间以及记录过程调用信息的控制栈，否则程序执行的正确性无法保证。
存储分配基本单元
过程活动记录是运行时存储分配的核心单位，通常包含参数区、返回地址、控制链、局部变量区和临时变量区。
存储分配策略
静态存储分配
在编译时确定对象地址，实现简单，但灵活性差。
栈式存储分配
适合过程调用和递归，遵循后进先出规律，是最常见的运行时管理方式。
堆式存储分配
适合生命周期不规则、大小可变的动态对象，但管理成本较高。
静态运行时存储分配
适用条件
只有当数据对象大小和位置都能在编译时确定，并且语言不支持递归和动态数据结构时，静态分配才足够使用。
局限性
一旦程序需要递归调用、动态申请对象或复杂嵌套作用域，静态分配就难以满足需求。
基于栈的运行时环境的动态存储分配
栈区内容
栈中既保存局部变量、临时变量等数据对象，也保存返回地址、控制信息等活动管理数据。
简单栈式实现
当语言不允许过程嵌套时，只需维护返回关系和局部数据即可，但通常仍允许递归调用。
嵌套过程的实现
访问链
访问链也称静态链，用于在嵌套作用域中找到外层过程的活动记录。
显示表
显示表直接保存各嵌套层最近一次活动记录的地址，访问非局部变量更快，但维护成本更高。
基于堆的运行时环境的动态存储分配
特点
堆适合管理长度可变、创建与销毁顺序不固定的数据对象，例如链表结点、树结点和对象实例。
典型问题
悬空引用
对象已释放但引用仍存在，会导致非法访问。
内存碎片
频繁分配与回收会造成大量不连续空闲块，降低内存利用率。
内存泄漏
对象不再使用却无法释放，会造成可用内存持续减少。
垃圾回收算法
引用计数
实现直观，但难以解决循环引用问题。
标记清除
先标记可达对象，再清除不可达对象，适用广泛，但会产生碎片。
复制算法
把存活对象复制到新区域，回收效率高，但空间利用率偏低。
分代回收
基于“大多数对象朝生夕死”的经验规律，把对象按年龄分代处理，是现代运行时系统的常见方案。
第8章 代码优化
代码优化概述
优化的目标
代码优化是在不改变程序语义的前提下，通过等价变换生成更高效的中间代码或目标代码。
提高效率的主要途径
算法层面改进
程序员从源程序层面修改算法，收益通常最大，但不属于编译器自动优化的范畴。
源级等价变换
对源程序结构做合理调整，也能提升性能，但依赖人工经验。
编译时优化
编译器能够系统地利用控制流、数据流和目标机信息进行自动优化，这是编译技术的重要价值之一。
优化分类
按作用范围分类
可分为局部优化、循环优化和全局优化。
按所处阶段分类
可分为中间代码级优化和目标代码级优化。
按具体技术分类
常见技术包括常量传播、公共子表达式删除、死代码删除、无用赋值删除、跳转优化、循环不变量外提、强度削弱和函数内联。
局部优化
基本块
定义
基本块是只有唯一入口和唯一出口的顺序语句序列，是局部优化的基本单位。
划分方法
通常先确定入口语句，再据此把中间代码切分成一组基本块，未被任何基本块覆盖的语句一般视为无效代码。
控制流图
控制流图描述基本块之间可能的执行转移关系，是后续循环分析、数据流分析和全局优化的基础。
DAG 优化
DAG 的作用
对基本块构造 DAG 后，可以更直观地识别公共子表达式、冗余赋值和常量合并机会。
结点类型
叶结点通常表示变量或常量，内部结点表示运算结果，一个结点上附着多个名字意味着这些名字当前值相同。
典型收益
可用于删除重复计算、压缩中间代码和识别无用赋值。
控制流分析与循环查找
必经结点
若从入口到某结点的所有路径都必须经过另一个结点，则后者是前者的必经结点。这个关系是寻找自然循环的关键。
回边
若一条边的终点是起点的必经结点，则该边为回边。回边常用于识别循环结构。
自然循环
由回边及其相关结点形成的区域构成自然循环，通常具有唯一入口，适合进行循环优化。
数据流分析
基本概念
定值点与引用点
定值点表示变量被赋值的位置，引用点表示变量值被使用的位置。
到达定值
若变量某次赋值能沿某条路径到达某点且中间未被重新赋值，则该定值到达该点。
ud 链与 du 链
ud 链从引用点出发追踪可能到达该引用的定值；du 链从定值点出发追踪该值可能到达的引用点。
活跃变量
若某变量当前值在未来某条路径上仍会被使用，则该变量在此点活跃。
数据流方程
到达定值分析
适合做常量传播、无用赋值删除和部分优化准备。
可用表达式分析
用于识别是否可以复用先前计算结果，减少重复运算。
活跃变量分析
常用于寄存器分配和死代码删除，是目标代码生成阶段的重要依据。
循环优化
循环前置结点
为了把循环内不变计算外提，往往先在循环入口之前建立前置结点，作为优化后代码的承载位置。
代码外提
把循环中每次迭代结果不变的运算移到循环外部，可以显著减少重复计算。
强度削弱
把开销较高的运算替换为低成本等价运算，例如将乘法变为加法。
归纳变量消除
通过分析循环变量之间的线性关系，删除冗余归纳变量，进一步减少计算与寄存器压力。
第9章 目标代码生成
代码生成器设计中的要点
输入与输出
代码生成器以中间表示为输入，以汇编代码或机器代码为输出，是编译器后端的最后一步。
三个核心问题
指令选择
需要决定某段中间代码应映射为哪组机器指令，既要保证正确，又要尽量高效。
寄存器分配
寄存器数量有限，必须决定哪些变量留在寄存器中、哪些变量暂存于内存，这直接影响运行效率。
指令调度
需要合理安排指令执行顺序，以减少流水线停顿和资源冲突。
简单代码生成器的构造
基本处理过程
针对每个基本块，依次读取三地址指令，决定操作数装入位置、生成相应计算指令，并在必要时把结果写回内存。
辅助数据结构
寄存器描述符
记录每个寄存器当前保存了哪些变量的值。
地址描述符
记录每个变量当前值可能位于哪些位置，例如寄存器、内存或二者同时存在。
getReg 思想
当需要寄存器时，优先复用已装载目标变量的寄存器；若无可用寄存器，再考虑空闲寄存器；最后才选择溢出某个寄存器内容到内存。
指令选择方法
树匹配
当中间表示可以组织为表达式树时，可通过树模式匹配选择更高质量的目标指令序列。
寄存器分配方法
固定分配
预留部分寄存器承担特定角色，实现简单，但资源利用率有限。
局部分配
以基本块为单位进行寄存器管理，适合简单代码生成器实现。
线性扫描
按变量活跃区间线性处理，算法效率高，广泛用于即时编译器。
图着色
把同时活跃的变量建边形成冲突图，再进行图着色，颜色数对应所需寄存器数。这种方法质量高，但实现复杂。
复习建议
建议重点
先建立整体框架
复习时建议先把“前端、优化、后端”三大部分串起来，明确每一章在编译器中的位置，再进入细节。
再抓核心链路
可以按“文法与自动机 -> 词法分析 -> 语法分析 -> 语义分析 -> 中间代码 -> 优化 -> 目标代码生成”的链路进行记忆。
最后突破高频难点
建议重点吃透以下内容：
高频必考概念
文法分类、FIRST/FOLLOW、LL(1) 条件、LR 项目集规范族、符号表、类型检查、四元式、活动记录、DAG 优化、数据流分析、寄存器分配。
容易混淆的概念
最左推导与最右推导、句型与句子、NFA 与 DFA、综合属性与继承属性、静态链与动态链、ud 链与 du 链、局部优化与全局优化。
适合结合题目练习的部分
子集法构造 DFA、LL(1) 分析表构造、LR 项目集闭包与 GO 函数、四元式生成、活跃变量分析与到达定值分析。