C语言编译器的设计.doc

《C语言编译器的设计.doc》由会员分享，可在线阅读，更多相关《C语言编译器的设计.doc（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-dateC语言编译器的设计枣 庄 学 院课程设计任务书 题目： C语言编译器的设计 学 号 姓 名 专 业 计算机科学与技术 课 程 编译原理 指导教师 职称 完成时间：20 10 年 12 月-2010 年 12 月课程设计任务书及成绩评定课程设计的任务和具体要求 1、了解编译器的基本结构，分析编译器的设计原理。2、加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握

2、；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。3、加深对语法分析器工作过程的理解；加强对递归下降法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。4、加深对中间代码生成的工作过程的理解。5、加深对代码优化的工作过程的理解。6、加深对目标代码生成的工作过程的理解指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等Windows xp vc6.0课程设计进度计划起至日期2010年12月1日-2010年12月20日2010年12月20

3、日-2010年12月26日工作内容收集资料程序分析备注 参考文献、资料索引序号文献、资料名称编著者出版单位1 汤子瀛,哲风屏,汤小丹.计算机操作系统陕西：西安电子科大出版社，19962 陈莉君. Linux操作系统内核分析人民邮电出版社，19993 庞丽萍操作系统原理华中理工大学出版社，19944 美莫里斯贝奇著 UNIX操作系统设计 陈葆钰等译 北京大学出版社，19895 吕映芝,张素琴,蒋维杜.编译原理.清华大学出版社，19976 冯博琴，傅向华等译 现代编译程序设计 人民邮电出版社，20027 李建中，姜守旭等译 编译原理 机械工业出版社，2002- 摘要编译程序是现代计算机系统的基本组

4、成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级机器语言，则这种翻译程序称作编译程序。一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁索细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代

5、尤为重要。编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、六个阶级。另外两个重要的工作：表格处理和出错处理与上述六个阶级都有联系。一 、引言（或绪论）编译器的设计涉及到编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。尽管“编译程序”是特指将高级程序设计语言翻译成低级语言的软件，但编译程序构造的基本原理和技术也广泛应用于一般的设计和实现，因此，是一门对实践性要求较高的课程。目前，世界上存在着数千种源语言，既有Fortran和Pascal这样的传统程序设计语言，也有各计算机应用领域中出现的专用语言。目标语言也同样广泛，目标语言可以是另一种程序

6、设计语言或者是从微处理机到计算机的任何计算机的机器语言。不同语言需要不同的编译器。根据编译器的构造方法或者它们要实现的功能，编译器被分为一遍编译器、多遍编译器、装入并执行编译器、调试编译器、优化编译器等多种类别。从表面上看，编译器的种类似乎千变万化，多种多样，实质上任何编译器所要完成的基本任务都是相同的。通过理解这些任务，我们可以利用同样的基本技术为各种各样的源语言和目标机器构建编译器。中间代码生成在进行了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计

7、为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。二、编译器的基础知识一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。2.1 编译器的发展背景编译程序是现代计算机系统的基本组成部

8、分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符

9、号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。 语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语。如“程序”，“语句”，“表达式”等等。一般这种语法短语也称为语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构步骤，其中包括了某种称作中间代码的抽象代码。编译器也可能

10、没有生成真正的可执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、链接器和装入器进行进一步处理。汇编器、链接器和装入器可由操心系统提供或由编译器自带。在翻译期间，中间表示或IR代表了源程序和数据结构。虽然抽象语法树是源代码完美充分的表达，即使对于代码生成也不过这样，但是它与目标代码极不相像，在控制流构造上尤为如此。在控制流构造上，目标代码使用转移语句而不是if和while语句。因此，编译器编写者可能希望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中间表示代替语法树，然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示称为中间代码。2.2编译器研发的可行性分析编

11、写编译器的原理和技术具有十分普遍的意义，以致于在每一个计算机科学家的研究生涯中，许多原理和技术都会反复用到。编译器的编写涉及到程序设计语言、计算机体系结构、语言理论、算法和软件工程等学科。简单的说，编译器是一个程序，它读入用某种语言（源语言）编写的程序并将其翻译成一个与之等价的以另一种语言（目标语言）编写的程序。作为这个翻译过程匠一个重要组成部分，编译器能够向用户报告被编译的源程序中许多操纵源程序的软件工具都首先完成某种类型的分析。下边是这类工具的示例：1结构编辑器，结构编辑器将一个命令序列作为输入一构造程序。2智能打印机，智能打印机能够对程序进行分析，打印出结构清晰的程序。3静态检查器，静态

12、检查器读入一个程序，分析这个程序，并在不运行这个程序的条件试图发现程序的潜在错误。4解释器，解释器不是通过翻译来产生目标程序，而是直接执行源程序中蕴含的操作。研究编译程序是有意义在于：1）编译程序构造是计算机科学中的一个非常成功的分支，也是最早获的成功的分支之一；2）它与文件转换程序关系密集，且不仅仅适用于编译程序；3）它包含许多在实际应用中有用的算法。23编译过程概述编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译

13、成另一种语言（称作目标语言）的等价的程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级玉器言，则这种翻译程序称作编译程序。高级语言程序的处理过程如图： 需处理的源程序 预处理程序 源程序编译程序 目标汇编程序 汇编程序 可再装配的机器代码装配/连接编辑程序 可在装配的目标文件 绝对机器代码 一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫做预处理程序的程序完成，有些预处理程序也负责宏展开，像C语言和预处理程序要完成文件合并、宏展开等任务。也就是说，一个编译程序的输入可能要一个或多个预处理程序来产

14、生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。表格管理目标代码生成代码优化中间代码生成语义分析语法分析词法分析 源程序出错处理 图1图1将编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、六个阶级。另外两个重要的工作：表格处理和出错处理与上述六个阶级都有联系。编译过程是源程序和各种信息被子保留在种种不同的表格里，编译各阶级的工作都涉及到构造、查找或更新有关的表格，因此需要有表格处理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编

15、译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单位，可表示成语法树。语法分析所依据

16、的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。语义分析阶级是审查源程序有无语义错误，为代码生成阶级收集类型信息。比如语分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象

17、，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用个数组下标的情况报告错误。又如某些语言规定运算对象可被强制，那么当二目运算一整数和一实型时，编译程序应将整型转换成实型而不能认为是源程序的错误。中间代码生成在进行了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象

18、1，运算对象2，结果）。代码优化在此阶级的任务是对前阶级产生的是间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。目标代码生成的任务是把是间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶级，它的工作与硬件系统结构和指令含义有关，这个阶的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。三、系统需求分析31词法语法分析简介词法分析的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个的单词（也称单词符号或符号）。这里所

19、谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等，即判断单词序列是否符合组成各类语法短语的组成规则，一般这种语法短语，也称为语法单位，可表示成语法树。3.2词法需求分析简介词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，

20、此外还有算符，界符等等。词法分析器的主要任务是读入输入字符，产生记号序列，提交给语法分析使用。词法分析器与语法分析器之间的交互如下图：语法分析器词法分析器源程序记号取下一个字符符号表1 剔除空白符和注释词法分析器读入输入串，将其转换成将被语法分析器分析的记号流。许多语言允许“空白符”（空格，制表符或者换行符）出现在记号之间。原程序中的注释一般都被语法分析器和翻译器忽略，所以他们也可以看成空白符。2 常数在一个表达式中，任何一个允许单个数字出现的位置都应该允许任何整型常数出现。由于翻译期间把数作为一个单元来处理，收集数字形成整数这一任务一般由词法分析器完成。3 识别标识符和关键字保留关键字的集合

21、可以通过适当地初始化符号表而得到正确的处理。4 实现词法分析器的接口在词法分析中，使用术语“记号”，“模式”，“词素”表示特定含义。记号包括：关键字、标识符、操作符、常量、文字串、和标点符号。词法分析器把与记号有关的信息收集在记号的属性中。记号影响语法分析，而属性影响记号的翻译。在实际实现时，记号通常只有一个属性，即指向符号表中一个表项的指针，与记号有关的信息保存在这个词素第一次出现的行为。这些信息存储在符号表中该标识符对应的表项内。5 记号的命名规则：正规表达式6 建立正规表达式时，可以先定义简单的正规表达式，然后用它们构造出更复杂的正规表达式。每个表达式r表示一个语言L（R）。7 记号的识

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

23、。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。语法分析的任务是语法分析器接收词法分析研究器提供的记号串，检查它们是否能由源程序的文法产生，语法分析器在编译器中的位置如图所示：词法分析器前端的其余部分源程序语法分析器记号 中间表示语法树取下一 个记号符号表典型的文法的语法分析器有三类：一类是通用的语法分析方法，如Cocke-Younger-Kasami算法和Early算法，这些方法在生成编译器时效率太低。编译器常用的是自顶向下和自底向上的方法。采用自顶向下的递归子程序法，就是对应每个非终结符语法单元，编一个独立的处理子程序。语法分析从读入第一个单词开始

24、，由非终结符即开始符出发，沿语法描述图箭头指出的方向进行分析。当遇到非终结符时，则调用相应的处理子程序，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若都不匹配时可能是进入下一非终结符语法单位或是出错。34符号表的应用在编译程序中符号表用来存放语言中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法分析过程中不断积累和更新表中的信息，并在词法分析到代

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

26、确定其在存储分配的位置。语言程序中的符号变量由它被定义的存储类别或被定义的位置来确定。首先要确定其被分配的区域。其次是根据变量出现的次序。在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法分析过程中不断积累和更新表中的信息，并在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。不论编译策略是否分趟，符号表的作用和地位是完全一致的。符号表的功能主要有：1、 收集符号属性：在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立符号的相应属性信息。2、 下文语义的合法性检查的依

27、据：同一个标识符可能在程序和不同地方出现，而有关该符号和属性是在不同情况下收集的，特别是在多趟编译及程序分段编译的情况下，更需检查标识符属性在上下文中的一致性和全法性。通过符号表中属性记录可进行这些语义检查。3、 作为目标代码生成阶段地址分配的依据：除语言中规定的临时分配存储的变量外，每个符号变量在目标代码生成时需要确定其在存储分配的位置。语言程序中的符号变量由它被定义的存储类别或被定义的位置来确定。首先要确定其被分配的区域。其次是根据变量出现的次序。语言符号可分为关键字（保留字）符号，操作符号几标识符号。他们之间的主要属性有较大的差别。因此通常为他们建立不同的符号表。四、系统设计编译程序的功

28、能图如下：编译程序 高级语言程序（源程序） 低级语言（目标语言）一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器的烦琐细节，使程序员和程序设计独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。41系统设计总体流程图启动并初始化 调用Read_File()把源程序调入到内存调用Get_Next_Token()从内存中取单词调用Programme()过程当前程序是否为结束符出错处理NY源程序是否有错误打印错误YN生成并执行目标程序结束4.2语法分析体流程图Programme()常量说明处理调用主函数部分Main_Function()Const_Declaration(

29、);N Y Var_Declaration()N测试ch是否为开始符？Sub_Function()变量说明处理 Y Y N 在TABLE表中登记过程名出错处理N递归调用Programme()返回调用列目标程序过程测试ch是否为语句后跟符出错处理生成退出数据段的指令OPR 0 0调用语句处理过程生成开辟数据段指令：int 0 A在TABLE表中返填子程序入口Y取单词Get_Next_Token()NY43语法分析概要设计语法分析是编译过程的核心部分，语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。语法分析设计采用递归下降分析法，递归下

30、降分析技术是一种无回溯的自顶向下分析技术，它的实现思想是：让一个识别符程序由一组子程序组成，其中每一个子程序对应于文法的一个非终结符；根据文法的递归定义，这些子程序往往是递归子程序。这种技术称为递归下降技术，相应的识别程序称为递归下降识别程序。在递归下降识别程序中的每一个子程序都对应于文法的一个非终结符，更确切地说为各个非终结符设计一个子程序，每一个子程序分析相对于相应非终结符短语。例如，当进入关于非终结符号语句的递归子程序时，便期待句子中出现相对于语句的短语，这时必要的是让识别程序逻辑知道句子中正期待短语的位置。递归下降分析技术是面向目标的，这个目标是子程序所相应的非终结符号，也是预测的，预

31、言能找到这个相对于该非终结符号的短语。C语言的语法分析EBNF如下： CONST，； = +|- ，； int| flaot|double|char | | = |！ | for（赋值语句；表达式；条件语句） while() dowhile() （） scanf(，&)； printf(，)； %d|%c|%s +|- |（） +|- *|/ =|=|!= ifelse a|b|A|B|Z 0|1|9用C语言实现递归下降分析程序如下：void Error()main( ) Constant（）; Variable()； Call_sentence()；Sentence();Constant（）

32、 /*常量说明部分*/ if(const) Constant_define(); Constant_define() /*常量定义*/ Identifer（）；Integer_content(); /*整型常量*/Variable() /*变量说明部分*/ if(类型说明)定义标识符；Sentence() /*语句*/ if(!Set_value_sentence() if(!Condition_sentence() if(!Circle_sentence() if(!Call_sentence() if(!printf) if(!scanf) return Error();Set_value

33、_sentence() Identifer（）； /*标识符*/Expression（）；/*表达式*/Condition () /*条件*/ Expression（）； Relation_symbol(); /*关系运算符*/ Expression（）；Circle_sentence() /*循环语句*/ for语句（）；while语句（）；do-while语句（）；Call_sentence() /*函数调用语句*/ Function_Identifer（）； /*函数名*/Expression（） /*表达式*/ if(+|-) Item(); Math_ symbol(); /*算数运

34、算符*/ Item(); Item() /*项*/ Factor();Math_ symbol(); Factor();Factor() /*因子*/ Identifer（）； Integer; If() Expression（）; If() Get_next_word(); Math_ symbol() if(Math_ symbol() Get_next_word(); Relation_symbol(); if(Relation_symbol() Get_next_word();Condition_sentence () /*条件语句*/ if(if) if() Expression（）

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

36、其他AST结点模式替换；2正确代码生成，通过树重写，所有AST结点模式被目标代码序列替换；3后处理，通过窥孔优化，有些目标代码序列被其他目标代码序列替换。l 预处理和后处理可能反复执行l 得到代码最简单的方法是为AST的每个结点生成代码段，由迭代解释程序为其执行。如果目标代码为C或C+，所有优化都可能留给C或C+编译程序。这个过程用最小的投入使解释程序变为编译程序。l 可以生成对库中简单拷贝的例程调用，而不是多次重复一个代码段，这可以相当可观地减小目标代码的长度。这个技术被称为线程代码。目标代码长度的减少对嵌入式系统可能是重要的。l 通过将库例程编号并且将程序存储为这些编号数的一个列表可以大大

37、减小目标代码长度。所有目标机依赖现在集中于库例程中。l 在其他方向，每一个重复的代码段可能在它们的上下文中被部分求值，从而导致更有效的代码。l 在简单代码生成中，为每个可能的结点类型选择了到目标代码的固定翻译。这些翻译基于共同的接口规定。l 简单代码生成只需局部判定，因此尤其适合窄编译程序。l 寄存器机的简单代码生成用机器指令重写每个表达式结点，这满足了代码选择的需要。接口规定是：一条指令的输出寄存器必要性须即用作父母指令的输入寄存器。l 寄存器机上的表达式的代码可以通过深度优先递归访问生成，这满足了指令排序的需要。递归例程携带两个额外的参数，结果必须传入其中的寄存器和空闲寄存器集，这满足了寄

38、存器分配的需要。l 因为每个没有处理的操作数都占用了一个寄存器，为需要最多寄存器的操作数首先编译代码是有利的。这要求可以在深度优先访问中计算结点的权。l 当一个表达式需要的寄存器多于可用的寄存器时，我们需要溢出一个和多个寄存器至存储器。没有最好的寄存器溢出技术，除非进行全面的研究。因此我们求助于启发式算法。l 在一个启发式算法中，我们分离出可以用可用寄存器编译的最大子表达式，编译它们，将结果存储进临时变量。变减小了原始树，我们对其重复这个过程。l 机器寄存器被编译程序设计者分为四组：为管理目的所需的、为参数传递保留的、为表达式求值保留的和用于存储局部变量的。通常情况下，每个集合的大小是固定，并且有些集合可能是空的。l 通常情况下，为局部变量保留的寄存器集比候选集要小。启发式算法包括先来先服务、来自程序员的寄存器提示以及从静态或动态简要表得的使用计数。更高级的启发算法使用图着色。l 栈上的编译用符号解释的编译有些类似于符号解释。在后者中，我们保持符号表示法，但现在我们包括栈和寄存器，更重要的是，这一次，表示法中的信息必须精确。这种表示法被称为寄变描述符。l 如果结点的效果可以精确存储于寄变描述符中，我们就这样做。没有为结点生成代码，但其语义保留在寄变描述符中：旧寄变描述+结点l 如呆结点的效果使我们不能精确地在