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