1. 主要内容
- 引论
- 高级语言及其文法
- 语法分析
- 自顶向下的语法分析
- 自底向上的语法分析
- 语法制导翻译与属性文法
- 语义分析与中间代码生成
- 符号表管理
- 运行时的存储组织
- 代码优化
- 代码生成
2. 程序设计语言
- 机器语言与汇编语言：01 代码与助记符，更接近于计算机硬件指令系统的工作
- 高级语言：其表示方法更接近于带解决的表示方法
- 命令语言：控制系统的工作，以功能封装为特征（如 UNIX 上的 shell）
3. 程序设计语言的分类
- 强制性（命令式）语言（Imperative Language)
- 通过指明一系列可执行的运算及运算的次序来描述计算过程的语言
- 程序的层次性和抽象性不高
- FORTRAN（段结构）、BASIC、Pascal（嵌套结构）、C ⋯cdots⋯
- 申述性语言（Declarative Language）
- 着重描述要处理什么，而非如何处理的非命令式语言
- 函数（应用）式语言（Functional Language），基本运算单位是函数（如 LISP、ML ⋯cdots⋯）
- 逻辑式（基于规则）语言（Logical Language），基本运算单位是谓词（如 Prolog、Yacc ⋯cdots⋯）
- 并发式语言（Concurrent Language），着重如何描述潜在的并行机制（如 ErLang、Fortran MPI ⋯cdots⋯）
- 面向对象语言（Object-Oriented Language）
- 以对象为核心（如 Smalltalk、C 、Java、Ada（程序包）⋯cdots⋯ ）
- 具有认识性（对象）、类别性（类）、多态性和继承性
4. 程序语言的翻译
- 翻译程序：将一种语言描述的程序（源程序）翻译成等价的另一种语言描述的程序（目标程序）
- 解释程序：一边解释一边执行的翻译程序
- 编译程序：将源程序完整地转换成机器语言程序或汇编语言程序，然后再执行翻译程序（比如汇编程序）进行处理转换为机器语言程序（高级语言程序 →rightarrow→ 汇编/机器语言程序）
【注】解释程序和编译程序都属于翻译程序。
常见翻译程序
- 汇编语言（Assembler）
- 交叉汇编程序（Cross Assembler）
- 反汇编程序（Disassembler）
- 交叉编译程序（Cross Compiler）
- 反编译程序（Decompiler）
- 可变目标编译程序（Retargetable Compiler）
- 并行编译程序（Parallelizing Compiler）
- 诊断编译程序（Diagnostic Compiler）
- 优化编译程序（Optimizing Compiler）
- 编译系统：编译系统 = 编译程序 运行系统（支撑环境、运行库等）
5. 编译程序总体结构
- 词法分析
- 词法分析由词法分析器（Lexical Analyzer）完成，词法分析器又称为扫描器（Scanner）
- 词法分析器从左到右扫描组成源程序的字符串，并将其转换为单词（token）串，同时检查词法错误，进行标记符登记（符号表管理）
- 输入 ：字符串 输出 ：序对 ——（种别码，属性值），其中，属性值为 token 的机内表示
- 语法分析
- 语法分析器由语法分析器（Syntax Analyzer）完成，语法分析器又叫 Parser
- 功能：
- Parser 实现「组词成句」（将词组成各类语法成分：表达式、因子、项、语句、子程序 ⋯cdots⋯ ）
- 构造分析树
- 指出语法错误
- 指导翻译
- 输入 ：token 序列 输出 ：语法成分
- 语义分析
- 语义分析一般和语法分析同时进行，称为语法制导翻译（Syntax-Directed Translation）
- 功能：分析由语法分析器识别出来的语法成分的语义
- 获取标识符的属性：类型、作用域等
- 语义检查：运算的合法性、取值范围等
- 子程序的静态绑定：代码的相对地址
- 变量的静态绑定：数据的相对地址
- 中间代码生成
- 中间代码表示
- 后缀表达式（逆波兰表达式）
- 前缀表达式（波兰表达式）
- 四元式表示（三地址码）
- 三元式表示
- 中间代码特点
- 简单规范
- 与机器无关
- 易于优化与转换
- 代码优化
- 代码优化是指对中间代码进行优化处理，式程序运行能够尽量节省存储空间，更有效地利用机器资源，使得程序的运行速度更快，效率更高（【注】这种优化变换必须是等价的）。代码优化包括：与机器无关的优化和与机器有关的优化
- 与机器无关的优化
局部优化：常量合并、公共子表达式的提取等 循环优化：强度削减（较快操作代替较慢操作）、代码外提（循环不变量提出循环）
- 与机器有关的优化
寄存器的利用：常用量放入寄存器，减少访存次数 体系结构：MIMD、SIMD、SPMD、向量机、流水机 存储策略：根据算法访存的要求安排（Cache、并行存储体系——减少访问冲突） 任务划分：按运行的算法及体系结构，划分子任务（MPMD）
- 目标代码生成
- 将中间代码转换成目标机上的机器指令代码或汇编代码
- 确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组）
- 制定从中间代码到目标代码的翻译策略或算法
- 目标代码的形式
- 具有绝对地址的机器指令
- 汇编语言形式的目标程序
- 模块结构的机器指令（需要链接程序）
- 表格管理
- 管理各种符号表（常数、标号、变量、过程、结构 ⋯cdots⋯ ），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息
- 辅助语法检查、语义检查
- 完成静态绑定、管理编译过程
- Hash 表、链表等各种表的查、填技术
- 「数据结构」与「算法」
- 错误处理
- 进行各种错误的检查、报告、纠正，以及相应的续编译处理（比如错误的定位与局部化）
词法：拼写 ⋯cdots⋯ 语法：语句结构、表达式结构 ⋯cdots⋯ 语义：类型不匹配、参数不匹配
6. 模块分类
8 项功能对应 8 个模块：
- 分析：词法分析、语法分析、语义分析
- 综合：中间代码生成、代码优化、目标代码生成
- 辅助：符号表管理、出错处理
7. 编译程序的组织
- 根据系统资源的状况、运行目标的要求 ⋯cdots⋯，可以将一个编译程序设计成多遍（Pass）扫描的形式，在每一遍扫描中，完成不同的任务。单遍代码不太有效；遍可以和阶段相对应，也可以和阶段无关
比如，首遍构造语法树、二遍处理中间表示、增加信息等
- 编译程序的设计目标
- 规模小、速度快、诊断能力强、可靠性高、可移植性好、可扩充性好
- 目标程序也要规模小、执行速度快
- 编译系统规模较大，可移植性很重要。为提供可移植性，将编译程序划分为前端和后端
- 前端
与源语言有关、与目标机无关的部分 词法分析、语法分析、语义分析、中间代码生成、与机器无关的代码优化
- 后端
与目标机有关的部分 与机器有关的代码优化、目标代码生成
8. 编译程序的生成
- 如何实现编译器？：自展——使用语言提供的功能来编译该语言自身
- T 形图：表示语言翻译过程
其含义为：源语言通过实现语言翻译为目标语言
- 自展
问题：如何在一个机器上实现 C 语言编译器？
- 移植
问题：如何将 A 机上的 C 语言编译器移植到 B 机上的 C 语言编译器？
- 交叉编译
问题：如何利用 A 机上的 C 语言编译器实现新语言 NEW 的编译器？
- 编译程序自动生成
- 词法分析器的自动生成程序
输入：词法（正规表达式）、识别动作（C程序段） 输出：yylex() 函数
- 语法分析器的自动生成程序
输入：语法规则（产生式）、语义动作（C程序段） 输出：yyparse() 函数
9. 编译技术的应用
将复杂数据看作一条语句：
- 数据格式的分析：利用词法、语法分析方法
- 数据处理的框架：基于语法制导的语义处理框架
自然语言的理解和翻译：句子翻译、输入法、语音合成、翻译、内容过滤 ⋯cdots⋯ 语法制导的结构化编辑器 程序格式化工具 软件测试工具 程序理解工具 高级语言的翻译程序 ⋯cdots⋯
