绪论
1. 编译程序：
- 定义：一种能够把某一种语言程序（源语言程序）转换成另一种语言程序（目标语言程序）的程序。
- 诊断编译程序(Diagnostic Compiler):专门用于帮助程序开发和调试的编译程序
- 优化编译程序(Optimizing Compiler):着重于提高目标代码效率的编译程序
- 主机：编译程序的计算机
- 目标机： 产生目标程序的计算机
2. 编译器与解释器：
- 编译器：编译器是将一种语言翻译为另一种语言的计算机程序。
- 源程序：通常为高级语言（C++，JAVA…）
- 目标程序：机器代码
- 源程序 -> 编译器 -> 目标程序
- 高级语言程序除了像上面所说的先编译后执行外，有时候也可以用“解释”来执行。解释器是这样的一种程序，它以高级语言写的源程序作为输入，但不产生目标程序，而是一边解释源程序本身一边执行。
3. 编译程序的工作原理和基本结构
3.1 语言的主要成分
(1).语法：
- 定义：对于任意的程序，都可以看成字符串（属于一个有限字符集）的一个序列。语法规则就是让这些字符的组合能被人和机器看懂的一系列的规则，分为词法规则和语法规则
- 词法规则：单词符号的形成规则，各类型的常数、标志符、关键字、界符等
- 语法单位：从单词符号到语法单位的形成规则，表达式，语句，函数，过程和程序等等。
(2).语义
- 定义：用于定义一个程序的意义。（书上的定义）
- 自己的理解：就是定义每一个词语的意义和性质，让字符的堆砌有了具体的释义，用语文类比，语法就是规定怎么写成一个汉字和一个标点，语义就是规定一个词，一个符号有什么意义，能放在那里，使人能过理解。
- 程序的层次结构
- 自上而下看上述层次结构：顶端是程序本身，它是一个完整的执行单位。一个程序通常是由若干个子程序或分程序组成的，它们常常含有自己的数据。子程序或分程序是有语句组成的。而组成语句的成分则是各种类型的表达式。表达式是表述数据运算的基本结构，它通常含有数据引用、算符和函数调用。
- 自下而上看上述层次结构：我们希望通过对下层成分的理解掌握上层成分，从而掌握整个程序。
3.2 编译的基本过程
- 五步过程
- 编译程序的主要工作过程就是上面的五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。
（1） 词法分析
任务：对输入的源程序进行扫描与分解，识别出一个个单词，如if、while等，标识符，常数，界符（；左右括号等）。
这一过程依循的就是词法规则（构词规则）
有效工具：正规式，有限自动机
（2） 语法分析
任务：语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单 位（语法范畴），如“短语”、“字句”、“句子”（“语句”）、“程序段”和“程序”。
简单来说，就是把语句识别为句子
- 语法规则通常用上下文无关文法描述，理论模型是下推自动机。
（3）语义分析和中间代码产生
任务：这一阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
- 语义分析：检测结构正确的句子是否语义合法，修改树结构；
- 中间代码生成：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成（比如四元式）；
- 使用属性文法描述语义规则，模型仍是下推自动机。
（4）优化
任务：优化的任务在于对前段产生的中间代码进行加工变换，以求在最后阶段能产生出更为高效（省时间和空间）的目标代码。它包括以下几个方面：公共子表达式的提取、循环优化、删除无用代码等等。
- 优化分类：局部优化、循环优化、全局优化等
- 优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但在占用的空间上和程序执行的时间上都更省、更有效。
（5）目标代码生成
任务：这一阶段的任务是：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。
- 这个阶段实现了最后的翻译，它的工作有依赖于硬件系统结构和机器指令含义。
上述编译程序的五个阶段是一种典型的逻辑模型。事实上，并非所有编译程序都分成这五阶段。有些编译程序对优化没有要求，优化阶段就可以省去。五阶段。有些编译程序对优化没有要求，优化阶段就可以省去；在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。
3.3 编译程序的基本结构
类似于编译过程
- 词法分析器：输入源程序，进行词法分析，输出单词符号。
- 语法分析器：简称分析器，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
- 语义分析与中间代码产生器：按照语意规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把他们翻译成一定形式的中间代码。
- 优化器：对中间代码进行优化处理。
- 目标代码生成器:把中间代码翻译成目标程序。
在上述框架中还有两个重要的概念就是表格管理和出错管理
- 表格与表格管理：编译程序在工作中需要保持一系列的表格，以登记源程序中各类信息的编译各阶段的进展状况。合理的设计和使用表格是编译程序构造的一个重要问题。在编译程序使用的表格中，最重要的是符号表。它用来登记源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名、变量名，还是过程名等等，以及它的类型、内存地址等信息。
编译的各个阶段都涉及到了对这些表格的修改、查找或更新等工作。所以对于这些表格的管理也是编译程序 的主要工作之一。 - 出错处理：一个编译程序不但要能对书写正确的程序进行翻译，而且应该能对出现在源程序中的错误进行处理。如果源程序中发现错误，编译器就应该将信息发送给用户。这部分的工作是由专门的一组程序（出错处理程序）完成。
3.4 编译的前端和后端
3.5 编译的遍数（pass）
- 遍：所谓遍就是对源程序或源程序的中间结构从头到尾扫描一次，并作有关的加工处理 ，生成新的中间结果或目标程序。
- 我们可采用一遍或者多遍扫描源程序或其中间代码的处理方法来实现编译程序。如何划分遍数，与源语言、设计要求、硬件设备等诸因素有关，因此遍数的划定是由具体情况来决定的，难以统一划定。