C语言编译器的设计

1、课程设计任务书题目：C语言编译器的设计学 号姓 名专 业计算机科学与技术课 程编译原理指导教师职称完成时间：2010 年12 月-2010 年12 月课程设计任务书及成绩评定课程设计的任务和具体要求1、了解编译器的基本结构，分析编译器的设计原理。2、加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一 种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进 行词法分析。3、加深对语法分析器工作过程的理解；加强对递归下降法实现语法分析程序的掌握; 能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单 的程序段进行语法翻译。4、加深对

2、中间代码生成的工作过程的理解。5、加深对代码优化的工作过程的理解。6、加深对目标代码生成的工作过程的理解指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等Win dows xp vc6.0课程设计进度计划起至日期2010 年 12 月 1 日-2010 年12月20日2010 年 12 月 20 日-2010 年12月26日工作内容收集资料程序分析备注参考文献、资料索引序号文献、资料名称编著者出版单位1 汤子瀛，哲风屏，汤小丹计算机操作系统陕西：西安电子科大出版社，19962 陈莉君.Linux操作系统内核分析人民邮电出版社，19993 庞丽萍操作系统

3、原理华中理工大学出版社，19944 美莫里斯？贝奇著UNIX操作系统设计陈葆钰等译北京大学出版社，19895 吕映芝,张素琴,蒋维杜.编译原理.清华大学出版社，19976 冯博琴，傅向华等译现代编译程序设计人民邮电出版社，20027 李建中，姜守旭等译编译原理机械工业出版社，2002摘要编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。 它把一种语（称作源语言）书写的程序翻译成另一种语言 （称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语

4、言程序翻译成机 器语言程序。如果源语言是像 FORTRAN，PASCAL,或C那样的高级语言，目标语言是像汇 编语言或机器语言那样的低级机器语言， 则这种翻译程序称作编译程序。一个编译程序的重要 性体现在它使得多数计算机用户不必考虑与机器有关的繁索细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、六个阶级。另外两 个重要的工作：表格处理和出错处理与上述六个阶级都有联系。一、引言（或绪论）编译器的设计涉及到编译程序构造的一般原理、基本设计方法、主要实现技术和一些自 动构

5、造工具。尽管“编译程序”是特指将高级程序设计语言翻译成低级语言的软件，但编译程 序构造的基本原理和技术也广泛应用于一般的设计和实现，因此，是一门对实践性要求较高的课程。目前，世界上存在着数千种源语言，既有Fortran和Pascal这样的传统程序设计语言，也 有各计算机应用领域中出现的专用语言。目标语言也同样广泛，目标语言可以是另一种程序设计语言或者是从微处理机到计算机的任何计算机的机器语言。不同语言需要不同的编译器。根据编译器的构造方法或者它们要实现的功能，编译器被分为一遍编译器、多遍编译器、装入并 执行编译器、调试编译器、优化编译器等多种类别。从表面上看，编译器的种类似乎千变万化， 多种多

6、样，实质上任何编译器所要完成的基本任务都是相同的。通过理解这些任务，我们可以利用同样的基本技术为各种各样的源语言和目标机器构建编译器。中间代码生成在进行了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则 为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程采用了一种近似“三地址 指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象1运算对象2,结 果）。二、编译器的基础知识一个编译程序就是一个语言翻译

7、程序。 它把一种语（称作源语言）书写的程序翻译成另一 种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻 译成机器语言程序。如果源语言是像 FORTRAN，PASCAL，或C那样的高级语言，目标语言 是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。2.1 编译器的发展背景编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高 级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个 编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称 作目标语言）的等价的程序。比

8、如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语 言程序。如果源语言是像FORTRAN，PASCAL,或C那样的高级语言，目标语言是像汇编语 言或机器语言那样的低级语言，则这种翻译程序称作编译程序。词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地 读入源程序，对构成源程序的字符流进行扫描和分解， 从而识别一个个单词（也称为单词符号 或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标 识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有 算符，界符等等。语法分析是编译过程的第二个阶段。语法分析的任务

9、是在词法分析的基础上将单词序列分 解成各类语法短语。如“程序”，“语句”，“表达式”等等。一般这种语法短语也称为语法单位， 可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构步骤，其中包括了某种称作中间代码的抽象代码。 编译器也可能没有生成真正的可执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、 链接器和装入器进行进一步处理。汇编器、链接器和装入器可由操心系统提供或由编译器自带。 在翻译期间，中间表示或IR代表了源程序和数据结构。虽然抽象

10、语法树是源代码完美充分的 表达，即使对于代码生成也不过这样，但是它与目标代码极不相像，在控制流构造上尤为如此。 在控制流构造上，目标代码使用转移语句而不是 if和while语句。因此，编译器编写者可能希 望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中间表示代替语法树， 然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示称为中间代码。2.2编译器研发的可行性分析编写编译器的原理和技术具有十分普遍的意义，以致于在每一个计算机科学家的研究生 涯中，许多原理和技术都会反复用到。编译器的编写涉及到程序设计语言、计算机体系结构、 语言理论、算法和软件工程等学科。简单的说，编

11、译器是一个程序，它读入用某种语言（源语 言）编写的程序并将其翻译成一个与之等价的以另一种语言（目标语言）编写的程序。作为这 个翻译过程匠一个重要组成部分，编译器能够向用户报告被编译的源程序中 许多操纵源程序的软件工具都首先完成某种类型的分析。下边是这类工具的示例： 1 结构编辑器，结构编辑器将一个命令序列作为输入一构造程序。2. 智能打印机，智能打印机能够对程序进行分析，打印出结构清晰的程序。3静态检查器，静态检查器读入一个程序，分析这个程序，并在不运行这个程序的条件试图 发现程序的潜在错误。4.解释器，解释器不是通过翻译来产生目标程序，而是直接执行源程序中蕴含的操作。研究编译程序是有意义在于

12、：1）编译程序构造是计算机科学中的一个非常成功的分支，也是最早获的成功的分支之一；2）它与文件转换程序关系密集，且不仅仅适用于编译程序；3）它包含许多在实际应用中有用的算法。2. 3编译过程概述编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高 级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称 作目标语言）的等价的程序。如果源语言是像 FORTRAN，PASCAL，或C那样的高级语言， 目标语言是像汇编语言或机器语言那样的低级玉器言，则这种翻译程序称

13、作编译程序。高级语言程序的处理过程如图：需处理的源程序可在装配的目标文件绝对机器代码一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫做预处理程序的程序完成，有些预处理程序也负责宏展开，像C语言和预处理程序要完成文件合并、宏展开等任务。也就是说，一个编译程序的输入可能要一个或多个预处 理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。图1图1将编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、 目标代码生成、六个阶级。另外两个重要的工作：表格处理和出错处理与上述六个阶级都有联系。编译过程是源程序和各种信息被

14、子保留在种种不同的表格里，编译各阶级的工作都涉及到构造、查找或更新有关的表格，因此需要有表格处理的工作；如果编译过程中发现源程序有错 误，编译程序应报告错误的性质和错误发生的地点， 并且将错误所造成的影响限制在尽可能小 的范围内，使得源程序的其余部分能继续被编译下去， 有些编译程序还能自动校正错误， 这些 工作称之为出错处理。词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地 读入源程序，对构成源程序的字符流进行扫描和分解， 从而识别一个个单词（也称为单词符号 或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标 识是由字母开头，后跟字

15、母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有 算符，界符等等。语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词序列分 解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单 位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语 法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源 程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成， 比如识别标识符， 因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又 不是数字字符时

16、，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。语义分析阶级是审查源程序有无语义错误，为代码生成阶级收集类型信息。比如语分析的 一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用个数组下标的情况报告错误。又如某些语言规定运算对象可被强制，那么当二目运算一整数和一实型时， 编译程序应将整型转换成 实型而不能认为是源程序的错误。中间代码生成在进行了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示形

17、式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则 为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程采用了一种近似“三地址 指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象1运算对象2,结 果）。代码优化在此阶级的任务是对前阶级产生的是间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。目标代码生成的任务是把是间代码变换成特定机器上的绝对指令代码或可重定位的指令 代码或汇编指令代码。这是编译的最后阶级，它的工作与硬件系统结构和指令含义有关， 这

18、个 阶的工作很复杂，涉及到硬件系统功能部件的运用、 机器指令的选择、各种数据类型变量的存 储空间分配以及寄存器和后缓寄存器的调度等。三、系统需求分析3. 1词法语法分析简介词法分析的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行 扫描和分解，从而识别出一个个的单词（也称单词符号或符号） 。这里所谓的单词是指逻辑上 紧密相连的一组字符，这些字符具有集体含义。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等，即判断单词序列是否符合组成各类语法短语的组成规则，一般这种语法 短语，也称为语法单位，可表示成语法树。3.2词法需求分

19、析简介词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地 读入源程序，对构成源程序的字符流进行扫描和分解， 从而识别一个个单词（也称为单词符号 或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标 识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有 算符，界符等等。词法分析器的主要任务是读入输入字符， 产生记号序列，提交给语法分析使用。词法分析 器与语法分析器之间的交互如下图：1 .剔除空白符和注释词法分析器读入输入串，将其转换成将被语法分析器分析的记号流。许多语言允许“空白符” （空格，制表符或者换行符

20、）出现在记号之间。原程序中的注释一般都被语法分析器和翻译器 忽略，所以他们也可以看成空白符。2. 常数在一个表达式中，任何一个允许单个数字出现的位置都应该允许任何整型常数出现。由于翻译期间把数作为一个单元来处理，收集数字形成整数这一任务一般由词法分析器完成。3. 识别标识符和关键字保留关键字的集合可以通过适当地初始化符号表而得到正确的处理。4. 实现词法分析器的接口在词法分析中，使用术语“记号”，“模式”，“词素”表示特定含义。记号包括：关键字、标识 符、操作符、常量、文字串、和标点符号。词法分析器把与记号有关的信息收集在记号的属性 中。记号影响语法分析，而属性影响记号的翻译。在实际实现时，记

21、号通常只有一个属性，艮卩 指向符号表中一个表项的指针，与记号有关的信息保存在这个词素第一次出现的行为。这些信息存储在符号表中该标识符对应的表项内。5. 记号的命名规则：正规表达式6. 建立正规表达式时，可以先定义简单的正规表达式，然后用它们构造出更复杂的正规表达式。每个表达式r表示一个语言L （ R）。7. 记号的识别：状态转换图3.3语法需求分析简介语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词序列分 解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单 位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通

22、过语 法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源 程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成， 比如识别标识符， 因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。语法分析的任务是语法分析器接收词法分析研究器提供的记号串，检查它们是否能由源程序的文法产生，语法分析器在编译器中的位置如图所示：典型的文法的语法分析器有三类：一类是通用的语法分析方

23、法，如Cocke-Younger-Kasami算法和Early算法，这些方法在生成编译器时效率太低。 编译器常用的是自顶向下和自底向上的 方法。采用自顶向下的递归子程序法，就是对应每个非终结符语法单元，编一个独立的处理子程 序。语法分析从读入第一个单词开始，由非终结符即开始符出发，沿语法描述图箭头指出的方 向进行分析。当遇到非终结符时，则调用相应的处理子程序，从语法描述图看也就进入了一个 语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到终结符时，则判断当前读入的单词是否与图中的终结符相匹配， 若匹配，则执行相应的语义程序。再读取下一个单词 继续分析。遇到分支点时将当前的单词与分支

24、点上的多个终结符逐个相比较，若都不匹配时可能是进入下一非终结符语法单位或是出错。3. 4符号表的应用在编译程序中符号表用来存放语言中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法分析过程中不断积累和更新表中的信息，并在词法分析到代码生成和各阶段，按各自的需要从表中获得不同的属性信息。 不论编译策略是否分趟， 符号表的作用和地位是完全一致的。符号表的功能主要有：收集符号属性：在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有 关标识符的属性，并在符号表中建立符号的相应属性信息。上下文语义的合法性检查的依据：同一个标识符可能在程序和不同地方出现，而有

25、关 该符号和属性是在不同情况下收集的，特别是在多趟编译及程序分段编译的情况下， 更需检查标识符属性在上下文中的一致性和全法性。通过符号表中属性记录可进行这些语义检查。作为目标代码生成阶段地址分配的依据： 除语言中规定的临时分配存储的变量外， 每个符 号变量在目标代码生成时需要确定其在存储分配的位置。 语言程序中的符号变量由它被定义的 存储类别或被定义的位置来确定。首先要确定其被分配的区域。其次是根据变量出现的次序。在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法分析过程中不断积累和更新表中的信 息，并在词法分析到代码生成的

26、各阶段，按各自的需要从表中获取不同的属性信息。不论 编译策略是否分趟，符号表的作用和地位是完全一致的。符号表的功能主要有：1收集符号属性：在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有 关标识符的属性，并在符号表中建立符号的相应属性信息。2、下文语义的合法性检查的依据：同一个标识符可能在程序和不同地方出现，而有关该 符号和属性是在不同情况下收集的，特别是在多趟编译及程序分段编译的情况下，更 需检查标识符属性在上下文中的一致性和全法性。通过符号表中属性记录可进行这些 语义检查。3、作为目标代码生成阶段地址分配的依据：除语言中规定的临时分配存储的变量外，每 个符号变量在目标代码生成时

27、需要确定其在存储分配的位置。语言程序中的符号变量 由它被定义的存储类别或被定义的位置来确定。首先要确定其被分配的区域。其次是 根据变量出现的次序。语言符号可分为关键字（保留字）符号，操作符号几标识符号。他们之间的主要属性有较 大的差别。因此通常为他们建立不同的符号表。四、系统设计编译程序的功能图如下：高级语言程序（源程序）编译程序低级语言（目标语言）一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器的烦琐细节,使程序员和程序设计独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。4. 1系统设计总体流程图结束N4. 3语法分析概要设计语法分析是编译过程的核心部分，语法

28、分析的任务是：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。语法分析设计采用递归 下降分析法，递归下降分析技术是一种无回溯的自顶向下分析技术，它的实现思想是：让一个识别符程序由一组子程序组成，其中每一个子程序对应于文法的一个非终结符；根据文法的递归定义，这些子程序往往是递归子程序。 这种技术称为递归下降技术，相应的识别程序称为递 归下降识别程序。在递归下降识别程序中的每一个子程序都对应于文法的一个非终结符，更确切地说为各个非终结符设计一个子程序，每一个子程序分析相对于相应非终结符短语。例如， 当进入关于非终结符号语句的递归子程序时，便期待句子中出现

29、相对于语句的短语， 这时必要的是让识别程序逻辑知道句子中正期待短语的位置。递归下降分析技术是面向目标 的，这个目标是子程序所相应的非终结符号，也是预测的，预言能找到这个相对于该非终结符号的短语。C语言的语法分析EBNF如下：程序 - 宏定义 头文件 主函数(ma in) 子函数主函数(main) 变量说明部分 常量说明部分 子函数调用 语句常量说明部分CONST常量定义，常量定义；常量定义 标识符 = 整型常量整型常量+|-数字数字变量说明部分 类型说明 标识符， 标识符；类型说明 int| flaot|double|char标识符 字母字母| 数字语句 赋值语句|条件语句|循环语句|子函数调

30、用语句|输入语句|输出语 句赋值语句 标识符 = 表达式条件 表达式 关系运算符 表达式| ！ 表达式循环语句 vFOR循环语句|WHILE循环语句|DO-WHILE循环语句vFOR循环语句 L for (赋值语句；表达式条件语句)vWHILE循环语句一while 条件 )语句vdo-while 循环语句do 语句 while 条件)函数调用语句 函数名 (变量说明)输入语句scanf 输入类型声明 ， 标识符);输出语句printf 输出类型声明 ， 标识符)；输出类型声明%d|%c|%s表达式+|-项加减法运算符 项项 因子乘除法运算符 因子因子 -标识符|无符号整数| (表达式 加减法运

31、算符+卜乘除法运算符一* *|/关系运算符 -=|=|=|!=条件语句if条件 语句else语句字母 一 a|b|A|B|Z数字 -0|1|9用C语言实现递归下降分析程序如下：void Error() main ()Constant ();Variable。；Call_se nten ce()； Senten ce();Constant()/*常量说明部分*/if(con st)Con sta nt_defi ne();Constant_define() /* 常量定义 */Identifer()；Integer_content(); /* 整型常量 */ _Variable() /*变量说明

32、部分*/if(类型说明) 定义标识符；Se nte nce()/* 语句 */if(!Set_value_se nten ce() if(!C on ditio n_senten ce() if(!Circle_se nte nce() if(!Call_se nte nce() if(!pri ntf) if(!sca nf) return Error();Set_value_se nten ce()Identifer ()；/*标识符*/Expression () ； /* 表达式 */Con ditio n ()/* 条件 */Expression ()；Relation_symbol(

33、); /*关系运算符 */Expression ()；Circle_sentence() /* 循环语句 */ _for语句();while 语句();do-while 语句();Call_sentence()/* 函数调用语句 */Functiondentifer () ；/*函数名 */ _Expression ()/* 表达式 */if(+|-)Item();Math_ symbol();/*算数运算符 */Item();Item() /* 项 */Factor();Math_ symbol();Factor();Factor() /* 因子 */Identifer ()；In tege

34、r;If( ( )Expression ();If( )Get_ next_word();Math_ symbol() _if(Math_ symbol()Get_n ext_word(); 一 一Relatio n_symbol(); _if(Relation_symbol()Get_ next_word();Condition_sentenee ()/* 条件语句 */ _if(if)if( ( )Expression ();if( )Sentence ();if(else)Sentence ();4.4目标代码的分析代码生成概要：代码生成的基础是用目标代码段系统地替换AST的结点和子树，

35、用这种方法可以保持语义紧接着是一个线性代阶段，从重写的 AST产生一个线性指令序列。替换过程被称为树重写。线性化由目标代码段和数据流和控制流需求控制。代码生成中的三个主要问题是代码选择、寄存器分配和指令排序。一般情况下，发现最优组合是 NP完全的。有三个方法简化代码生成问：1每次只考虑AST 的一小部分；2简化目标机；3限制代码段之间的接口。代码生成分三个阶段进行：1预处理，通过程序转换，有些 AST结点模式被其他AST结点 模式替换；2正确代码生成，通过树重写，所有 AST结点模式被目标代码序列替换；3后 处理，通过窥孔优化，有些目标代码序列被其他目标代码序列替换。预处理和后处理可能反复执行

36、得到代码最简单的方法是为AST的每个结点生成代码段，由迭代解释程序为其执行。如果 目标代码为C或C+,所有优化都可能留给 C或C+编译程序。这个过程用最小的投入使 解释程序变为编译程序。可以生成对库中简单拷贝的例程调用，而不是多次重复一个代码段，这可以相当可观地减 小目标代码的长度。这个技术被称为线程代码。目标代码长度的减少对嵌入式系统可能是 重要的。通过将库例程编号并且将程序存储为这些编号数的一个列表可以大大减小目标代码长度。 所有目标机依赖现在集中于库例程中。在其他方向，每一个重复的代码段可能在它们的上下文中被部分求值，从而导致更有效的 代码。在简单代码生成中，为每个可能的结点类型选择了到

37、目标代码的固定翻译。这些翻译基于 共同的接口规定。简单代码生成只需局部判定，因此尤其适合窄编译程序。寄存器机的简单代码生成用机器指令重写每个表达式结点，这满足了代码选择的需要。接 口规定是：一条指令的输出寄存器必要性须即用作父母指令的输入寄存器。寄存器机上的表达式的代码可以通过深度优先递归访问生成，这满足了指令排序的需要。 递归例程携带两个额外的参数，结果必须传入其中的寄存器和空闲寄存器集，这满足了寄 存器分配的需要。因为每个没有处理的操作数都占用了一个寄存器，为需要最多寄存器的操作数首先编译代码是有利的。这要求可以在深度优先访问中计算结点的权。当一个表达式需要的寄存器多于可用的寄存器时，我们

38、需要溢出一个和多个寄存器至存储器。没有最好的寄存器溢出技术，除非进行全面的研究。因此我们求助于启发式算法。在一个启发式算法中，我们分离出可以用可用寄存器编译的最大子表达式，编译它们，将 结果存储进临时变量。变减小了原始树，我们对其重复这个过程。机器寄存器被编译程序设计者分为四组：为管理目的所需的、为参数传递保留的、为表达 式求值保留的和用于存储局部变量的。通常情况下，每个集合的大小是固定，并且有些集 合可能是空的。通常情况下，为局部变量保留的寄存器集比候选集要小。启发式算法包括先来先服务、来 自程序员的寄存器提示以及从静态或动态简要表得的使用计数。更高级的启发算法使用图着色。栈上的编译用符号解

39、释的编译有些类似于符号解释。在后者中，我们保持符号表示法，但 现在我们包括栈和寄存器，更重要的是，这一次，表示法中的信息必须精确。这种表示法 被称为寄变描述符。如果结点的效果可以精确存储于寄变描述符中，我们就这样做。没有为结点生成代码，但 其语义保留在寄变描述符中：旧寄变描述 +结点如呆结点的效果使我们不能精确地在寄变描述符中保留信息，我们生成代码以获得效果并且在寄变描述符中记录结果。因此语义被保留于结点的重写中。如果从活跃分析中得到可用信息，当离开其活跃范围时，我们可以从寄变描述符中删除关 于变量的所有信息。基本块为控制图的最大部分，它不包含分裂和结合。基本块是从标号或从例程的开头开始， 正

40、好在转移或类转移结点、标号或例程的结尾结束。它只包含表达式和赋值。基本块的概念从对控制流的关注中分离出对表达式和赋值的整齐序列的代码生成的关注。 这种分离对窄编译程序尤其有用，因为它允许它们为表达式序列做优化代码生成。基本块的代码生成分两步进行。首先将控制流图转换成依赖图，它是一“dag”，即有向非循环图。然后我们重写依赖图至代码。收益在于比起控制流图，依赖图对指令顺序限制 较少。基本块的依赖图由两种依赖组成： 表达式中通过操作数的数据依赖以及通过变量的数据依 赖，这些变量的赋值中得到它们的值并且它们的值在且中被继续使用。最终的数据依赖是那些在基本块后仍被需要的值，这些值称为基本块的根。强调这

41、些数据依赖并且移除其他的控制流依赖产生了一个粗糙的数据依赖图，它可以通过旁路赋值并且只保留那些从根可达的结点而被简化。这个图是dag,即有向非循环图。基本块的dag可以通过识别公共子表达式而进一步缩减。 这个缩减可以通过不断地合并具 有相同操作数、运算符和依赖的结点而得到。传统地，基本块的dag作为三元式的数组而实现。基本块dag中的结点被重写至相对应的机器指令，然后基于操作数求值将 dag线性化。 用于线性化dag的晚求值的特有形式可以识别梯形序列，该梯形序列匹配寄存器，一一存 储器指令序列，这些指令都有公共寄存器。这种序列十分有效。为发现先性化，重一个梯形开始，将第一个可用的梯形序列分离出

42、来，以由后至前的顺序 生成代码，然后从dag上离除这个梯形并且重复上述过程。基本块中表达式中的指针可以用两个简单的规则处理： 1.对指针所指变量的赋值使随后的 表达式中使用的任何变量依赖该赋值；2.从指针检索一个值依赖于所有前面的赋值。扩展 分析可能允许取消某些依赖。表达式树的最优重写可以通过 BURS弋码生成得到，BURS弋表自底向上重写系统。BURS技术允许将给定的任意复杂的输入树分解为许多子树， 其中的每个子树是给定树集的 成员，既模式树。模式树可能同样是任意复杂的。应用BURS成代码，我们将输入树看作表达式 AST将模式树看作带机器指令的 AST BURSt输入树上的两遍扫描中操作：一

43、遍自底向上和一遍自顶向下。自底向上扫描参照模 式树的结点注释输入树中的每个结点。在输入树中，结点I与结点N相关意味着顶部有I的树可以用顶部有N子树来重写其顶部。这暗示在重写顶部后，I以下的树的所有其他部 分也可以被重写，然后自顶向下扫描可以重写整个树。自底向上扫描结合模式树的片段集，特别象词法分析器结合正则表达式的项目集。与词法分析器一样，BURSg式匹配的速度可以通过将其作为 FSA而试销来提高（在这种情 况下，它是一个树自动机），而不是采用解释的方法）。与词法分析器不同，不同模式有不同代价，而我们想要最小代价的重写。在解释实现中， 基于代价的判定可以用动态程序设计技术处理：在每个结点，只有

44、在给顶寄存器类型中得 到结果的代价最地的方法被保留。在树自动机实现中，常量代价可以被合并进自动机。结 果转换表经常是巨大但可以被可观地压缩。BURS弋码生成可以相对容易地为额外的需要而改写。例如，具有集中类型寄存器的机器的 代码生成和方法到控制流指令的扩展。两个变量都存活于程序中的一个给定位置，当涉及到寄存器分配时它们会相互干扰。如果 我们知道所有变量的活跃范围，可以创建变量的寄存器相干图，其中每个结点代表一个变 量并且两结点N1与N2之间的每条弧表示结点N1与N2所代表的标量的活跃范围互相重叠。 通过对图着色，没有相同颜色的两结点被弧连接，没种颜色代表一个寄存器，这样我们可 以发现一个可能的

45、寄存器至变量的分配最优寄存器分配与使用最低颜色数的图着色对 应。最优图着色问题是NP完全的，但存在好的启发式算法，例如，从图中暂时移除度最小的 结点，用相同的算法递归地对余下的图着色，重新连接移去的结点并且对其着色。在超级编译中，一个小但经常使用的中间代码片段被采用并且用惯犯的研究来为它生成可 能的最好的代码。结果代码在编译程序中被用做模板。用这种方法已经发现了惊人的代码 序列。在将中间代码转换成目标代码前，可能会进行预处理以提高效率。简单预处理的例子有恒 定折*和算术简化。如果原程序语义需要如此，必须注意算术溢出条件是否被预处理忠 实地翻译。更广泛的预处理可以在例程上进行，它们可以被内联或克隆。在内联中对例程的调用被被调用的例程体替换。这节省了调用与返回序列，为进一步优化 开辟了道路。必须注意保持参数转移的语义。在克隆中，制作例程R的拷贝C,其中参数P的值固定为值V;对R的所有调用（其中参 数P有值V）被对拷贝C的调用替换。对拷贝C经常可以产生一个比对原来的例程R更好 的翻译。代码生成过程产生的某些次最优符号机器代码序列可以同归窥孔优化移除，其中固定的参数化序列被其他更好的固定的参数化序列取代。大约100种替换模式就足够解决相对简 单代码生成器留下的几乎所有修正的低效问题指令流中的可替换序列在窥孔优化中用基于替