编译原理 第一部分
翻译程序（Translator）
将源程序译成逻辑上等价的目标程序的程序。翻译程序有二种工作方式：编译和解释
解释方式 ( Interpret )
以源程序作为输入，输入一句解释执行一句，不产生完整的目标程序，相应的翻译程序称为解释程序(Interpreter)
解释方式主要特点是：用户程序是消极的。用户程序运行时，控制点在解释程序，即用户程序的执行离不开解释程序。
编译方式 ( Compile )
将源程序全部译为目标程序，该目标程序可在操作系统环境下直接执行，相应的翻译程序称为编译程序(Compiler)
- 编辑程序的工作结果是ASCII码形式的源程序。
- 编译程序以ASCII码形式的源程序为输入，它的工作结果是二进制形式的目标程序，但并未包括用户程序中所使用的系统函数的目标代码。从整体上来看，程序是不完整的，程序中的部分地址尚未确定（例系统函数的调用）。
- 将二进制形式的用户程序和系统函数目标代码连接成一个程序，对未确定的地址进行定位。
由操作系统将用户程序装入内存后运行。程序在运行过程中读入数据，经处理加工后输出计算结果。
编译方式主要特点是：用户程序是积极的。用户程序执行时，控制点在用户程序自身。除操作系统外，程序运行无需其它支撑软件。
二种翻译方式比较
解释方式和编译方式的主要区别是：目标代码的执行方式不同，基本原理和方法没有本质上的区别。
1）解释方式的优点
提供一种直接的交互调试功能，容易获得较好的动态调试效果。
使用变量可不预先定义。
变量性质可动态修改。
2）解释方式的缺点在执行时需动态地对程序进行分析翻译，开销大，其执行速度相当于编译方式的1/10至1/100。
解释方式占用内存大
显然解释程序的优点就是编译程序的缺点，反之亦然，对于编译程序的优缺点不再重复叙述。
对任何一种高级语言，既可采用编译方式，也可采用解释方式，包括汇编语言在内（MASM方式和DEBUG方式）
几种程序介绍
【翻译程序】将源语言程序转换为目标语言程序的等价的程序称为翻译程序。
【编译程序】将高级语言源程序翻译为低级语言目标程序的程序称为编译程序。
编译程序的意义：使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序专家独立于机器。
【汇编程序】将汇编语言源程序翻译为机器语言目标程序的程序称为汇编程序。
【反汇编程序】将机器语言源程序翻译为汇编语言目标程序的程序称为反汇编程序。
编译程序与解释程序的异同
高级语言有两种翻译途径：==编译与解释==。
它们的主要区别在于==是否产生目标程序==。
解释程序不产生目标程序，而是边解释边执行源程序本身，是一种“会话型”语言。（如python）
高级语言程序的处理过程
编译程序的5个阶段
1、词法分析
任务：从左至右读字符流的源程序，识别(拼)单词。
【单词】单词是具有独立意义的最小语法单位。
多数程序语言中，单词符号一般包括 —各类型的常数、保留字、标识符、运算符、界符等等。
识别原则：词法规则
描述工具：正规式
正规文法
有穷自动机FA
自动生成工具：LEX
2、语法分析
任务：依据源程序的语法规则把源程序的单词序列组成更大的语法成分——“组词成句” (表示成语法树) 。
识别原则：语法规则
描述工具：上下文无关文法
下推自动机PDA
自动生成工具：YACC
3、语义分析与中间代码生成
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
语义审查(静态语义)：上下文相关性、类型匹配、类型转换
识别原则：语义规则
描述工具：属性文法
实现方法：语法制导翻译【中间代码】 是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。
许多编译程序采用了一种与“三地址指令”非常近似的“四元式”作为中间代码，其形式是：
(算符 , 运算对象1 , 运算对象2 , 结果)
常用的中间代码有：四元式，三元式，间接三元式，逆波兰记号和树形表示等等。
4、代码优化
任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
主要包括：公共子表达式的提取
循环优化
删除无用代码等等
优化所依循的原则：程序的等价变换规则。
5、目标代码生成
任务：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。
生成原则：硬件系统结构和机器指令含义。
目标代码的形式：
绝对指令代码
可重定位的指令代码
汇编指令代码
编译程序的另外两个重要的工作是==表格管理==和==出错处理==。
编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；
如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。
符号表管理
符号表
记录源程序中使用的名字
收集每个名字的各种属性信息：类型、作用域、分配存储信息
符号表是由若干记录组成的数据结构，每个标识符在表中有一条记录，每条记录有多个域，每个域记载标识符的一个属性。例如下面一条记录说明标识符aaa是整型变量及分配的内存地址
| 标识符名 | 标识符类型 | 类型 | 地址 |
|---|---|---|---|
| aaa | 1（表示变量） | 1（表示整型） | 0001 |
标识符的各种属性是在编译的不同阶段填入符号表的。词法分析阶段只能分析出标识符名，语法分析阶段只能判断标识符在语句中出现是否合法，只有到了语义分析阶段，才能将标识符的各种属性填入符号表并使用这些属性生成中间代码。
出错处理
出错处理程序的任务包括 检查错误、报告出错信息、排错、恢复编译工作。
编译程序的组成
词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序
遍（pass）
【遍】就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
Turbo C是一遍完成编译，以及预处理和后续处理。
两遍编译：
- 1.进行词法分析、语法分析、语义分析，生成中间代码作为文件保留，以及符号表文件。
- 2.优化后生成目标代码作为文件保留。
三遍编译：
- 3.对目标代码的优化。
编译程序涉及的三种语言
【源语言】要深刻理解源语言(如 FORTRAN、Pascal或 C)结构(语法)和含义(语义)；
【目标语言】最终的目标语言还是机器语言，则必须搞清楚硬件的系统结构和操作系统的功能；
【宿主语言】编写编译程序的语言。自编译程序：宿主语言是源语言。例如PASCAL
编译程序的生成
手工
- 机器语言
- 汇编
- 系统程序设计语言，自编译，移植，交叉编译等方式
自动构造工具：lex yacc