编译原理¶
0. 要点汇总¶
本篇文章的要点整理如下
编译器：将高级语言源程序翻译成等价的低级语言目标程序的程序
解释器：直接执行高级语言源程序，不生成目标程序
编译过程：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
词法分析：将字符流转换为单词符号流
语法分析：根据语法规则构建语法树
语义分析：检查语义错误，生成中间代码
中间代码：介于源语言和目标语言之间的代码表示
代码优化：改进中间代码，提高目标程序效率
目标代码生成：将中间代码转换为目标机器代码
上下文无关文法：描述编程语言语法的形式化工具
语法树：表示程序语法结构的数据结构
抽象语法树(AST)：简化的语法树，省略无关信息
符号表：记录标识符信息的表
运行时环境：程序运行时的存储分配和管理
虚拟机：执行中间代码的抽象计算机
JVM：Java虚拟机，执行Java字节码
链接器：将多个目标文件链接成可执行文件
加载器：将可执行文件加载到内存中执行
1. 编译器概述¶
1.1 编译器的定义¶
编译器的定义
编译器(Compiler)是将用某种高级语言编写的源程序翻译成等价的低级语言(如汇编语言或机器语言)目标程序的程序。
编译器与解释器的区别
特性 |
编译器 |
解释器 |
|---|---|---|
执行方式 |
生成目标程序 |
直接执行 |
执行速度 |
快 |
慢 |
调试 |
难 |
易 |
平台依赖 |
依赖目标平台 |
相对独立 |
编译过程
词法分析(Lexical Analysis)
语法分析(Syntax Analysis)
语义分析(Semantic Analysis)
中间代码生成(Intermediate Code Generation)
代码优化(Code Optimization)
目标代码生成(Target Code Generation)
1.2 编译器的结构¶
编译器的组成部分
分析部分
词法分析器
语法分析器
语义分析器
综合部分
中间代码生成器
代码优化器
目标代码生成器
编译器的遍
遍是指编译器从源程序到目标程序的完整过程。
单遍编译器
多遍编译器
1.3 编译器的分类¶
按用途分类
诊断编译器
优化编译器
交叉编译器
按实现技术分类
自展技术
移植技术
按目标语言分类
汇编语言编译器
机器语言编译器
2. 词法分析¶
2.1 词法分析的任务¶
词法分析的任务
将字符流转换为单词符号流
过滤空白符和注释
识别关键字、标识符、常量、运算符、界符
单词符号的类型
关键字：if, else, while, for等
标识符：变量名、函数名等
常量：整数、实数、字符串等
运算符：+ , - , * , / , = , ==等
界符：(), {}, ;, ,等
2.2 词法分析器的实现¶
有限自动机
有限自动机(Finite Automaton, FA)是识别单词的工具。
确定有限自动机(DFA)
对于每个状态和输入符号，最多有一个转移。
非确定有限自动机(NFA)
对于某个状态和输入符号，可能有多个转移。
正则表达式
正则表达式(Regular Expression)是描述单词模式的工具。
正则表达式到NFA的转换
使用Thompson构造法。
NFA到DFA的转换
使用子集构造法。
DFA的最小化
合并等价状态，得到最小DFA。
2.3 词法分析器生成器¶
Lex
Lex是词法分析器生成器，根据正则表达式规则生成词法分析器。
Lex的工作流程
编写Lex源程序
Lex将Lex源程序转换为C程序
编译C程序得到词法分析器
Lex源程序的结构
- ::
定义部分 %% 规则部分 %% 用户子程序部分
3. 语法分析¶
3.1 语法分析的任务¶
语法分析的任务
根据语法规则检查源程序的结构
构建语法树或分析树
3.2 上下文无关文法¶
上下文无关文法的定义
上下文无关文法(Context-Free Grammar, CFG)是一个四元组G = (VN, VT, P, S)
VN：非终结符集合
VT：终结符集合
P：产生式集合
S：开始符号
产生式的形式
A → β
其中A ∈ VN，β ∈ (VN ∪ VT)*
推导
推导是从开始符号出发，反复使用产生式生成终结符串的过程。
最左推导
每次替换最左边的非终结符。
最右推导
每次替换最右边的非终结符。
分析树
分析树表示推导过程。
3.3 自顶向下分析法¶
递归下降分析法
为每个非终结符编写一个递归函数。
LL(1)分析法
第一个L：从左到右扫描输入
第二个L：最左推导
1：向前看1个符号
FIRST集
FIRST(α)是α可以推导出的串的首终结符集合。
FOLLOW集
FOLLOW(A)是A的后面可能出现的终结符集合。
预测分析表
预测分析表用于确定使用哪个产生式。
3.4 自底向上分析法¶
移进-归约分析法
使用栈进行移进和归约操作。
LR分析法
L：从左到右扫描输入
R：最右推导的逆过程
LR分析表
LR分析表包括ACTION表和GOTO表。
LR分析器的类型
LR(0)：不向前看符号
SLR(1)：简单LR(1)
LR(1)：向前看1个符号
LALR(1)：向前看1个符号的LR
3.5 语法分析器生成器¶
Yacc
Yacc是语法分析器生成器，根据文法规则生成语法分析器。
Yacc的工作流程
编写Yacc源程序
Yacc将Yacc源程序转换为C程序
编译C程序得到语法分析器
Yacc源程序的结构
- ::
定义部分 %% 规则部分 %% 子程序部分
4. 语义分析¶
4.1 语义分析的任务¶
语义分析的任务
检查语义错误
收集语义信息
生成中间代码
语义错误的类型
类型不匹配
变量未声明
变量重复声明
数组下标越界
函数参数不匹配
4.2 符号表¶
符号表的定义
符号表是记录标识符信息的表。
符号表的内容
标识符名称
类型
作用域
存储位置
其他属性
符号表的操作
插入
查找
删除
修改
符号表的实现
线性表
二叉搜索树
哈希表
4.3 类型检查¶
类型系统
类型系统定义了类型和类型规则。
类型表达式
类型表达式描述数据的类型。
基本类型：int, float, char, bool
构造类型：数组、指针、函数
类型等价
名字等价：类型名相同则类型相同
结构等价：类型结构相同则类型相同
类型转换
隐式转换
显式转换
4.4 作用域分析¶
作用域的定义
作用域是标识符的有效范围。
作用域的类型
静态作用域(词法作用域)
根据程序文本确定作用域。
动态作用域
根据程序执行时的调用顺序确定作用域。
作用域的实现
作用域栈
显示表
5. 中间代码生成¶
5.1 中间代码的概念¶
中间代码的定义
中间代码是介于源语言和目标语言之间的代码表示。
中间代码的作用
独立于机器
便于优化
便于移植
中间代码的类型
后缀式
三地址码
图表示(DAG、语法树)
5.2 三地址码¶
三地址码的定义
三地址码是最多包含三个地址的指令形式。
三地址码的类型
x = y op z
x = op y
x = y
goto L
if x goto L
ifFalse x goto L
if x relop y goto L
param x
call p, n
x = call p, n
return y
x = y[i]
x[i] = y
x = &y
x = * y
x = y
三地址码的实现
四元式：(op, arg1, arg2, result)
三元式：(op, arg1, arg2)
间接三元式：三元式 + 指针表
5.3 中间代码生成¶
表达式的翻译
将表达式转换为三地址码。
控制语句的翻译
将if、while等语句转换为带跳转的三地址码。
函数调用的翻译
将函数调用转换为param和call指令。
6. 运行时环境¶
6.1 存储分配¶
存储分配策略
静态存储分配
栈式存储分配
堆式存储分配
静态存储分配
编译时确定存储空间。
- 特点：
简单
效率高
不支持递归
栈式存储分配
运行时动态分配和释放栈空间。
- 特点：
支持递归
效率高
不支持动态大小
堆式存储分配
运行时动态分配和释放堆空间。
- 特点：
灵活
支持动态大小
效率较低
6.2 活动记录¶
活动记录的定义
活动记录(Activation Record)是一次函数执行所需的信息。
活动记录的内容
参数
返回地址
动态链
静态链
局部变量
临时变量
6.3 垃圾回收¶
垃圾回收的定义
垃圾回收(Garbage Collection)是自动回收不再使用的内存的技术。
垃圾回收算法
引用计数
标记-清除
复制算法
标记-整理
分代回收
7. 代码优化¶
7.1 代码优化概述¶
代码优化的定义
代码优化是改进中间代码，提高目标程序效率的技术。
优化的原则
等价性：优化后的代码与原代码功能相同
有效性：优化后的代码效率更高
合理性：优化成本合理
优化的分类
局部优化：基本块内的优化
循环优化：针对循环的优化
全局优化：跨越基本块的优化
7.2 常见优化技术¶
常量折叠
计算常量表达式的值。
例如：x = 2 + 3 → x = 5
常量传播
用常量替换变量。
例如：x = 5; y = x + 1 → x = 5; y = 6
公共子表达式消除
避免重复计算相同的表达式。
例如：t1 = a + b; t2 = a + b → t1 = a + b; t2 = t1
死代码消除
删除不会执行的代码。
代码移动
将不变的计算移出循环。
例如：
for i = 1 to n:
x = a + b
优化为：
t = a + b
for i = 1 to n:
x = t
强度削弱
将复杂运算替换为简单运算。
例如：
x = a * 2 → x = a << 1
归纳变量删除
删除与循环变量有固定关系的变量。
7.3 数据流分析¶
数据流分析的定义
数据流分析是收集程序中数据流信息的技术。
数据流分析的应用
常量传播
复制传播
到达-定义分析
活跃变量分析
可用表达式分析
数据流方程
数据流方程描述了数据流信息的传递规则。
8. 目标代码生成¶
8.1 目标代码生成概述¶
目标代码生成的任务
将中间代码转换为目标机器代码。
目标代码生成的主要问题
指令选择
寄存器分配
指令调度
8.2 指令选择¶
指令选择的定义
指令选择是为中间代码选择合适的机器指令。
指令选择的方法
树覆盖法
图着色法
动态规划法
8.3 寄存器分配¶
寄存器分配的定义
寄存器分配是将程序中的值分配到寄存器中。
寄存器分配的重要性
寄存器是最快的存储，合理分配寄存器可以显著提高程序效率。
寄存器分配的方法
寄存器分配
寄存器分配
寄存器溢出
当寄存器不足时，将值存储到内存中。
8.4 指令调度¶
指令调度的定义
指令调度是重新排列指令顺序，以提高执行效率。
指令调度的目标
减少数据依赖
提高指令级并行
减少流水线停顿
9. 代码生成形式¶
9.1 汇编语言¶
汇编语言的特点
机器相关的符号表示
需要汇编器转换为机器代码
汇编代码的生成
将中间代码转换为汇编代码。
9.2 机器语言¶
机器语言的特点
二进制代码
可以直接执行
机器代码的生成
将中间代码直接转换为机器代码。
9.3 绝对机器代码¶
绝对机器代码的特点
包含绝对地址
可以直接加载执行
相对机器代码
包含相对地址
需要链接器处理
10. 链接与加载¶
10.1 链接¶
链接的定义
链接是将多个目标文件和库文件组合成一个可执行文件的过程。
链接的类型
静态链接
动态链接
静态链接
在编译时将库代码复制到可执行文件中。
- 优点：
独立性强
执行效率高
- 缺点：
文件大
更新困难
动态链接
在运行时加载库代码。
- 优点：
文件小
便于更新
- 缺点：
依赖性强
执行效率略低
10.2 加载¶
加载的定义
加载是将可执行文件加载到内存中并执行的过程。
加载的过程
分配内存
加载代码和数据
重定位
初始化
开始执行
重定位
将逻辑地址转换为物理地址。
11. 虚拟机¶
11.1 虚拟机的概念¶
虚拟机的定义
虚拟机是执行中间代码的抽象计算机。
虚拟机的类型
基于栈的虚拟机
基于寄存器的虚拟机
虚拟机的优点
平台独立
安全性高
易于实现
11.2 Java虚拟机(JVM)¶
JVM的结构
类加载器(ClassLoader)
运行时数据区
执行引擎
本地接口
运行时数据区
堆
方法区
栈
程序计数器
本地方法栈
执行引擎
解释器
即时编译器(JIT)
JVM的生命周期
加载
验证
准备
解析
初始化
使用
卸载
12. 编译器构造工具¶
12.1 词法分析器生成器¶
Lex/Flex
Lex/Flex是词法分析器生成器。
- 特点：
使用正则表达式
自动生成词法分析器
12.2 语法分析器生成器¶
Yacc/Bison
Yacc/Bison是语法分析器生成器。
- 特点：
使用上下文无关文法
自动生成语法分析器
12.3 其他工具¶
语法分析器生成器
ANTLR
JavaCC
代码生成器
LLVM
13. 应用领域¶
13.1 编程语言开发¶
C/C++编译器
Java编译器
Python解释器
13.2 领域特定语言¶
SQL
HTML/CSS
正则表达式
13.3 优化工具¶
性能分析器
代码优化器
13.4 安全工具¶
模糊测试
漏洞扫描
14. 总结与展望¶
编译原理是计算机科学的核心课程之一，研究如何将高级语言程序转换为低级语言程序。从词法分析到目标代码生成，从代码优化到虚拟机实现，编译技术不断发展，为编程语言的实现和优化提供了强有力的支持。
核心价值
实现高级语言
提高程序效率
保证程序正确性
支持语言创新
学习建议
理解编译原理的基本概念
掌握词法分析和语法分析
学习代码优化技术
实践编写简单编译器
关注编译技术的前沿发展
进阶方向
即时编译技术
多核并行编译
异构计算编译
自动化并行化
机器学习辅助编译
编译技术日新月异，掌握编译原理将为你的学习和工作提供强大的支持。