|
|
|
编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（形式为汇编语言程序或机器语言程序）。编译程序的工作过程可以分为6个阶段，如下图所示。实际的编译器中可能会将其中的某些阶段结合在一起进行处理。下面简要介绍各阶段实现的主要功能。
|
|
|
|
|
|
|
|
|
|
词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。源程序可以被看成是一个多行的字符串。“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（标点符号、左右括号）等。词法分析程序输出的“单词”常以二元组的方式输出，即单词种类和单词自身的值。
|
|
|
|
词法分析过程依据的是语言的词法规则，即描述“单词”结构的规则。例如，对于某PASCAL源程序中的一条声明语句和赋值语句：
|
|
|
|
|
|
词法分析阶段将构成这条语句的字符串分割成如下的单词序列。
|
|
|
|
|
|
|
|
|
|
（10）标识符X（11）赋值号:=（12）标识符Y
|
|
|
|
|
|
|
|
对于标识符X、Y、Z，其单词种类都是id（即标识符类），字符串“X”“Y”和“Z”都是单词的值；而对于单词60，常数是该单词的种类，60是该单词的值。这里，用id1、id2和id3分别代表X、Y和Z，强调标识符的内部标识由于组成该标识符的字符串不同而有所区别。经过词法分析后，声明语句VAR X，Y，Z：real；表示为VAR id1，id2，id3：real；，赋值语句X：=Y+Z*60；表示为id1：=id2+id3*60；。
|
|
|
|
|
|
语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”和“程序”等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树；否则就指出语法错误，并给出相应的诊断信息。
|
|
|
|
词法分析和语法分析本质上都是对源程序的结构进行分析。
|
|
|
|
对语句id1：=id2+id3*60进行语法分析后形成的语法树如下图所示。
|
|
|
|
|
|
|
|
|
|
语义分析阶段主要分析程序中各种语法结构的语义信息，包括检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。
|
|
|
|
语义分析的一个主要工作是进行类型分析和检查。程序设计语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是一种类型不匹配的错误。
|
|
|
|
在确认源程序的语法和语义之后，就可对其进行翻译，同时改变源程序的内部表示。对于声明语句，需要记录所遇到的符号的信息，因此应进行符号表的填查工作。在下图（a）所示的符号表中，每行存放一个符号的信息。第一行存放标识符X的信息，其类型为real，为它分配的逻辑地址是0；第二行存放Y的信息，其类型为real，为它分配的逻辑地址是4。对于可执行语句，则检查结构合理的语句是否有意义。对语句id1：=id2+id3*60进行语义分析后的语法树如下图（b）所示，其中增加了一个语义处理结点inttoreal，用于将一个整型数转换为浮点数。
|
|
|
|
|
|
|
|
|
|
中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。中间代码的设计原则主要有两点：一是容易生成，二是容易被翻译成目标代码。最常用的一种中间代码是与汇编语言的指令非常相似的三地址码，其实现方式常采用四元式。四元式的形式为：
|
|
|
|
|
|
例如，对语句X：=Y+Z*60，可生成以下四元式序列：
|
|
|
|
|
|
|
|
|
|
|
|
其中，t1、t2、t3是编译过程中形成的临时变量，用于存放中间运算结果。
|
|
|
|
|
|
|
|
由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在计算时间上和存储空间上有很大的浪费。当需要生成高效的目标代码时，就必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。由于中间代码是不依赖于具体机器的，此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。优化所依据的原则是程序的等价变换规则。例如，在生成语句X：=Y+Z*60的四元式后，60是编译时已知的常数，把它转换为60.0的工作可以在编译时完成，没有必要生成一个四元式，同时t3仅仅用来将其值传递给id1，也可以化简掉，因此上述的中间代码可优化成下面的等价代码：
|
|
|
|
|
|
|
|
这只是优化工作中的一个简单示例，真正的优化工作还要涉及公共子表达式的提取、循环优化等更多的内容和技术。
|
|
|
|
|
|
目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。例如，使用两个寄存器R1和R2，可对上述的四元式生成下面的目标代码：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。
|
|
|
|
|
|
用户编写的源程序不可避免地会有一些错误，这些错误大致可分为静态错误和动态错误。动态错误也称动态语义错误，它们发生在程序运行时，例如变量取零时作除数、引用数组元素下标越界等错误。静态错误是指编译时所发现的程序错误，可分为语法错误和静态语义错误，如单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误称为语法错误；而语义分析时发现的运算符与运算对象类型不匹配等错误属于静态语义错误。
|
|
|
|
在编译时发现程序中的错误后，编译程序应采用适当的策略修复它们，使得分析过程能够继续下去，以便在一次编译过程中尽可能多地找出程序中的错误。
|
|
|
|
对于编译过程的各个阶段，在逻辑上可以把它们划分为前端和后端两部分。前端包括从词法分析到中间代码生成各阶段的工作，后端包括中间代码优化和目标代码的生成及优化等阶段。以中间代码为分水岭，把编译器分成了与机器有关的部分和与机器无关的部分。如此一来，对于同一种程序设计语言的编译器，开发出一个前端之后，就可以针对不同的机器开发相应的后端，前后端有机结合后就形成了该语言的一个编译器。当语言有改动时，只会涉及前端部分的维护。对于不同的程序设计语言，分别设计出相应的前端，然后将各个语言的前端与同一个后端相结合，就可得到各个语言在某种机器上的编译器。
|
|
|
