着手看编译原理 2019/1/9
概述
编译程序
把某一种高级语言程序等价地转换为一种低级语言程序（如汇编语言或机器语言）的程序，称为编译程序
运行编译程序的机器称为宿主机，运行编译后的程序的机器称为目标机，经常目标机就是宿主机
- 诊断编译程序（Diagnostic Compiler）帮助开发和调试，发现程序中的错误
- 优化编译程序（Optimizing Compiler）专注于优化
- 交叉编译程序（Cross Compiler）宿主机不作为目标机
- 可变目标编译程序（Retargetable Compiler）目标机可变的编译程序
解释程序
把源语言编写的源程序作为输入，但不产生目标程序，而是边解释边执行，即每次运行都需要解释，这种程序称为解释程序
编译程序和解释程序统称为翻译程序
编译程序工作的五个阶段
- 词法分析
- 语法分析
- 中间代码产生
- 优化
- 目标代码产生
词法分析
- 目标：将源程序字符串扫描分解，识别出单词、符号等
- 规则：PL的构词规则（什么样的字符做关键字，什么样的字符可以做变量名）
- 描述工具：有限自动机
（分割字符串，为分割出的单词或符号定性）
示意如下图
语法分析
- 目标：在词法分析的基础上，根据语法规则把单词符号串分解成各类语法单位（语法范畴）
- 规则：PL的语法规则
- 描述工具：上下文无关文法
（将分割的单词、字符组织成有效形式）
示意如下图
语法分析树
中间代码产生
- 目标：进行静态语义检查，对各类语法单位按语言的语义进行初步翻译，将源程序代码翻译为中间代码
- 规则：语义规则（语义，语句的功能）
- 描述工具：属性文法
- 中间代码：三元式、四元式、树…
示意如下图
Z := X + 0.618 * Y
翻译为四元式
优化
- 目标：对前阶段产生的中间代码进行加工变换，以期产生更高效的目标代码
- 规则：程序的等价变换原则
目标代码产生
- 目标：把中间代码变换成特定机器上的目标代码（依赖于硬件系统结构和机器指令的含义）
- 目标代码的三种形式
（1）汇编指令代码：需要进行汇编（汇编器）方可运行
（2）绝对指令代码：可直接运行（机器语言）指令地址是绝对地址，变量存储单元地址已经定好，可在内存中直接运行
（3）可重新定位指令代码：需要链接（链接器）链接为可执行程序，指令中地址是相对地址，给定起始地址可以运行。
可重新定位指令代码很好支持模块化软件开发，可独立编写编译各模块，最后链接为可执行程序
编译程序的结构
编译程序总框
出错处理
遍
遍：对源程序或源程序的中间表示从头到尾扫描（分析、处理）一次
- 若干个阶段可以一遍完成
比如说词法分析，语法分析，中间代码生成，词法分析出来一个单词/符号可以交给语法分析，判断是否组成同一语法单位。完成一个语法单位的分析后即生成中间代码。这样动态地一遍就完成三个阶段的工作 - 一个阶段可以由若干遍完成
比如优化阶段，可以多遍进行多种优化，也可以多遍进行针对性的优化
编译前端与后端
可以进行区分的原因：大致以中间代码为界，词法分析、语法分析、语义分析（中间代码生成）甚至一部分的优化与目标机是无关的，仅与源语言有关，有较为明显区别与界限
- 与目标机无关的词法分析、语法分析、语义分析（中间代码生成）甚至一部分优化称为编译前端
- 与目标机有关的优化、中间代码生成、目标代码的产生称为编译后端
意义： - 程序逻辑更加清晰
- 优化分为机器无关的优化和机器相关的优化，优化更加充分
- 方便复用、移植
编译程序的生成
编译程序的开发方法
（1）以机器语言和汇编语言为工具
- 能针对具体机器，充分发挥计算机的系统功能，生成高效率的程序
- 程序编写、维护难度大
（2）高级语言开发
- 程序编写、维护难度小
在拥有L1语言的编译器的情况下，使用L1语言编写L2语言的编译器，编译该L1程序得到可运行的L2语言编译器
推广
编译程序的移植
在有A机器代码构成的L语言到A代码的编译器P1的情况下，用L语言编写编译L语言到B机器代码的编译器P2，用P1编译P2得到A机器代码版本的L语言到B机器代码的交叉编译程序，再用此程序编译P2得到B机器代码版本的编译器P3，P3作为B机器上L语言的编译器
（3）自编译方式生成编译程序
用汇编语言或者机器语言实现一个L语言的子集L1，用L1实现一个更大的子集L2，用L2……用Ln实现L
（4）编译程序的自动产生
编译程序的自动产生工具称为 编译程序-编译程序，编译程序产生器，编译程序书写系统
如LEX：词法分析程序产生器
YACC：语法分析程序产生器