编译原理

引论

编译程序是现代计算机的基础组成部分之一，而且多数计算机系统都配有不止一种高级语言的编译程序。

从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把一种语言（称作源语言）数学的程序翻译成另一种语言（称作目标语言）的等价程序。比如，汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源程序是像FORTRAN，Pascal或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言。这种翻译程序称作编译程序。

一个源程序有时可能分成几个模块放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫做预处理程序的程序来完成，有些预处理程序也负责宏展开，像c语言的与处理程序要完成文合并、宏展开等任务。1.2中编译程序生成的目标程序是汇编代码形式，需要经由汇编程序翻译可再装配（或可重定位）的机器代码，再经由装配、连接编辑程序与某些库程序连接成真正能在机器码上运行的代码，编译程序的输出可能仍需要进一步的处理。

编译过程和编译程序的结构

编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体过程。从概念上来讲，一个编译程序的整个工作过程是划分阶段进行的

源程序->词法分析->语法分析->语义分析->中间代码生成->代码优化->目标代码生成->目标程序

词法分析

词法分析是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（一些场合下也称单词符号或符号）。这里所谓的单词是指逻辑上紧密连接的一组字符，这些字符具有集体含义。列如，标识符是由字母字符开头，后跟字母，数字字符的字符序列组成的一种单词。保留字（关键字或基本字）是一种单词，此外还有算符，界符等。

语法分析

语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语。如程序 语句 表达式等。

词法分析和语法分析本质上都是对源程序的结构进行分析。但语法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母大头的字母数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字的字符时，将前面所发现的所有字母和数字组合在一起构成标识单词即可。但这种线性扫描不能用于识别地柜定义的语法成分，比如不能用此办法去匹配表达式中的括号。

通过语法分析确定整个输入串是否构成一个语法上正确的程序。

可以将语法分析的结果表示为语法树的形式。

语义分析

语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。例如，语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。

• 语义分析的具体任务包括类型审查、下标检查和运算对象的类型转换等。

中间代码生成

在尽显了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示的形式，这种内部表示形式叫做中间语言或者中间代码。所谓的中间代码是一种结构简单含义明确的记号系统。需要满足两点设计原则：一是容易生成，二是容易将它翻译成目标代码。

很多编译程序采用了一种近似三地址指令的四元式中间代码，这种四元式的形式为

运算符，运算对象1，运算对象2，结果

代码优化

这一阶段的任务是对前一阶段的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。

目标代码生成

目标代码生成阶段的任务是把中间代码变换为特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。
这是编译的最后阶段，它的工作和硬件结构和指令含义等都有关，是一个非常复杂的过程。

备注：并非所有的编译程序都划分为这样几个阶段，有些编译程序并不需要生成中间代码，有些编译程序不进行优化。不过大多数编译程序都包含上述几个工作阶段。

编译程序的结构

上述的过程的6个阶段可以分别由6个模块完成，分别称作词法分析程序，语法分析程序，语义分析程序，中间代码生成程序、代码优化程序和目标代码生成程序。此外一个完成的编译程序还包括表格管理程序和出错处理程序。

表格管理和出错处理与上述6个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及构造

查找或更新有关的表格，因此需要有表格管理的工作。如果编译过程发现源程序有错误，建议程序应报告错误的性质和错误发生的地点，并将错误造成的影响尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作由出错处理程序完成。

解释程序和一些软件工具

解释程序

编译程序是一个语言处理程序，它把高级语言程序翻译成某个机器的汇编语言程序或二进制代码程序，这二进制代码程序在机器上运行产生结果。

解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个的获取分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员一交互方式工作的情况，希望在获取下一个语句之前了解每个语句的执行结果，允许程序执行时修改程序。
shell，java字节码，sql都是解释程序。

解释程序的输入包括员程序和源程序的初始数据（输入数据），它不生成目标代码，直接输出结果。编译程序和解释程序的组织也有很大不同。

经由编译程序处理时，在源程序被编译的阶段，存储区中要为源程序（中间形式）和目标代码开辟空间，要存放编译用的各种表格，如符号表。在目标代码运行阶段，存储区中主要是目标代码和数据，编译所用的任何信息都不再需要了。

解释程序一般是把源程序一个语句一个语句地进行语法分析，转换为一种内部表示形式，存放在源程序区。因为解释程序允许在执行用户程序时秀爱用户程序，这就要求在解释程序工作的整个过程中，源程序、符号表等内容始终存放在存储区中，并且存放格式要设计得易于使用和修改。

程序的解释是非常慢的，有时候高级语言解释会比运行等价的机器代码程序慢100倍。因此当程序运行速度非常重要时，是不能采用解释方式的。另外，解释程序的空间开销也是比较大的。

软件工具

为了提高了软件开发效率和质量，需要有一套软件开发过程所遵循的规范和标准。这些软件工具的开发其中很多要用到编译的原理和技术。下面是这些工具的例子

• 语言的结构化编辑器：用户可以使用这种编辑器在鱼眼的语法制导下编制出所需的源程序。结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，还会对源程序正文进行逐行分析并完成输入检查、自动提供关键字等任务。
• 语言程序的调试工具：该类工具允许用户一行一行来跟踪程序， 查看变量和数据结构的变化。调试的功能越强，实现越复杂，涉及到源程序的语法分析和语义处理技术。
• 语言程序测试工具：可以分为静态分析器和动态测试器两种。
  静态分析器：在不运行程序的情况下对源程序进行静态分析，以发现程序中潜在的错误或异常；

动态测试器：在源程序分析的基础上，将用于记录和现实程序执行轨迹的语句或函数插入到源程序的适当位置，并用测试用例来记录和显示程序运行时的路径，将运行结果与期望的结果进行比较分析，帮助编程人员找到问题。

• 程序理解工具：对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户理解程序。
• 高级语言之间的转换工具：把一种高级语言转换为另一种高级语言的工具。这与实现一个完整的编译程序相比工作量小一些。