C语言编译器的设计

课程设计任务书 题目： C语言编译器的设计 学 号 姓 名 专 业 计算机科学与技术 课 程 编译原理 指导教师 职称 完成时间：20 10 年 12 月----2010 年 12 月 课程设计任务书及成绩评定 课程设计的任务和具体要求 1、了解编译器的基本结构，分析编译器的设计原理。 2、加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。 3、加深对语法分析器工作过程的理解；加强对递归下降法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。 4、加深对中间代码生成的工作过程的理解。 5、加深对代码优化的工作过程的理解。 6、加深对目标代码生成的工作过程的理解 指导教师签字： 日期： 指导教师评语 成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等 Windows xp vc6.0 课程设计进度 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 起至日期 2010年12月1日-2010年12月20日 2010年12月20日-2010年12月26日 工作内容 收集资料 程序分析 备注 参考文献、资料索引 序号 文献、资料名称 编著者 出版单位 [1] 汤子瀛,哲风屏,汤小丹.计算机操作系统．陕西：西安电子科大出版社，1996 [2] 陈莉君. Linux操作系统内核分析．人民邮电出版社，1999 [3] 庞丽萍．操作系统原理．华中理工大学出版社，1994 [4] [美]莫里斯•贝奇著 UNIX操作系统设计 陈葆钰等译 北京大学出版社，1989 [5] 吕映芝,张素琴,蒋维杜.编译原理.清华大学出版社，1997 [6] 冯博琴，傅向华等译 现代编译程序设计 人民邮电出版社，2002 [7] 李建中，姜守旭等译 编译原理 机械工业出版社，2002 　 摘要 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级机器语言，则这种翻译程序称作编译程序。一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁索细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、六个阶级。另外两个重要的工作： 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 格处理和出错处理与上述六个阶级都有联系。 一 、引言（或绪论） 编译器的设计涉及到编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。尽管“编译程序”是特指将高级程序设计语言翻译成低级语言的软件，但编译程序构造的基本原理和技术也广泛应用于一般的设计和实现，因此，是一门对实践性要求较高的课程。 目前，世界上存在着数千种源语言，既有Fortran和Pascal这样的传统程序设计语言，也有各计算机应用领域中出现的专用语言。目标语言也同样广泛，目标语言可以是另一种程序设计语言或者是从微处理机到计算机的任何计算机的机器语言。不同语言需要不同的编译器。根据编译器的构造方法或者它们要实现的功能，编译器被分为一遍编译器、多遍编译器、装入并执行编译器、调试编译器、优化编译器等多种类别。从表面上看，编译器的种类似乎千变万化，多种多样，实质上任何编译器所要完成的基本任务都是相同的。通过理解这些任务，我们可以利用同样的基本技术为各种各样的源语言和目标机器构建编译器。 中间代码生成在进行了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。 二、编译器的基础知识 一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。 2.1 编译器的发展背景 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。 词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。 语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语。如“程序”，“语句”，“表达式”等等。一般这种语法短语也称为语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构步骤，其中包括了某种称作中间代码的抽象代码。编译器也可能没有生成真正的可执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、链接器和装入器进行进一步处理。汇编器、链接器和装入器可由操心系统提供或由编译器自带。在翻译期间，中间表示或IR代表了源程序和数据结构。虽然抽象语法树是源代码完美充分的表达，即使对于代码生成也不过这样，但是它与目标代码极不相像，在控制流构造上尤为如此。在控制流构造上，目标代码使用转移语句而不是if和while语句。因此，编译器编写者可能希望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中间表示代替语法树，然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示称为中间代码。 2.2编译器研发的可行性分析 编写编译器的原理和技术具有十分普遍的意义，以致于在每一个计算机科学家的研究生涯中，许多原理和技术都会反复用到。编译器的编写涉及到程序设计语言、计算机体系结构、语言理论、算法和软件 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 等学科。简单的说，编译器是一个程序，它读入用某种语言（源语言）编写的程序并将其翻译成一个与之等价的以另一种语言（目标语言）编写的程序。作为这个翻译过程匠一个重要组成部分，编译器能够向用户报告被编译的源程序中 许多操纵源程序的软件工具都首先完成某种类型的分析。下边是这类工具的示例： 1．结构编辑器，结构编辑器将一个命令序列作为输入一构造程序。 2．智能打印机，智能打印机能够对程序进行分析，打印出结构清晰的程序。 3．静态检查器，静态检查器读入一个程序，分析这个程序，并在不运行这个程序的条件试图发现程序的潜在错误。 4．解释器，解释器不是通过翻译来产生目标程序，而是直接执行源程序中蕴含的操作。 研究编译程序是有意义在于： 1） 编译程序构造是计算机科学中的一个非常成功的分支，也是最早获的成功的分支之一； 2） 它与文件转换程序关系密集，且不仅仅适用于编译程序； 3） 它包含许多在实际应用中有用的算法。 2．3编译过程概述 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序。如果源语言是像FORTRAN，PASCAL，或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级玉器言，则这种翻译程序称作编译程序。 高级语言程序的处理过程如图： 需处理的源程序 源程序 目标汇编程序 可再装配的机器代码 可在装配的目标文件 绝对机器代码 一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫做预处理程序的程序完成，有些预处理程序也负责宏展开，像C语言和预处理程序要完成文件合并、宏展开等任务。也就是说，一个编译程序的输入可能要一个或多个预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。 源程序 图1 图1将编译过程划分了词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成、六个阶级。另外两个重要的工作：表格处理和出错处理与上述六个阶级都有联系。编译过程是源程序和各种信息被子保留在种种不同的表格里，编译各阶级的工作都涉及到构造、查找或更新有关的表格，因此需要有表格处理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。 词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。 语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此 办法 鲁班奖评选办法下载鲁班奖评选办法下载鲁班奖评选办法下载企业年金办法下载企业年金办法下载 去匹配表达式中的括号。 语义分析阶级是审查源程序有无语义错误，为代码生成阶级收集类型信息。比如语分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用个数组下标的情况报告错误。又如某些语言规定运算对象可被强制，那么当二目运算一整数和一实型时，编译程序应将整型转换成实型而不能认为是源程序的错误。 中间代码生成在进行了上述的语法分析和语义分析的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。 代码优化在此阶级的任务是对前阶级产生的是间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。 目标代码生成的任务是把是间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶级，它的工作与硬件系统结构和指令含义有关，这个阶的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。 三、系统需求分析 3．1词法语法分析简介 词法分析的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个的单词（也称单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。 语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等，即判断单词序列是否符合组成各类语法短语的组成规则，一般这种语法短语，也称为语法单位，可表示成语法树。 3.2词法需求分析简介 词法分析阶级是编译过程的第一个阶级。这个阶级的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别一个个单词（也称为单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识是由字母开头，后跟字母、数字字符序列组成的一种单词，。保留字是一种单词，此外还有算符，界符等等。 词法分析器的主要任务是读入输入字符，产生记号序列，提交给语法分析使用。词法分析器与语法分析器之间的交互如下图： 源程序 记号 取下一个字符 1． 剔除空白符和注释 词法分析器读入输入串，将其转换成将被语法分析器分析的记号流。许多语言允许“空白符”（空格，制表符或者换行符）出现在记号之间。原程序中的注释一般都被语法分析器和翻译器忽略，所以他们也可以看成空白符。 2． 常数 在一个表达式中，任何一个允许单个数字出现的位置都应该允许任何整型常数出现。由于翻译期间把数作为一个单元来处理，收集数字形成整数这一任务一般由词法分析器完成。 3． 识别标识符和关键字 保留关键字的集合可以通过适当地初始化符号表而得到正确的处理。 4． 实现词法分析器的接口 在词法分析中，使用术语“记号”，“模式”，“词素”表示特定含义。记号包括：关键字、标识符、操作符、常量、文字串、和标点符号。词法分析器把与记号有关的信息收集在记号的属性中。记号影响语法分析，而属性影响记号的翻译。在实际实现时，记号通常只有一个属性，即指向符号表中一个表项的指针，与记号有关的信息保存在这个词素第一次出现的行为。这些信息存储在符号表中该标识符对应的表项内。 5． 记号的命名规则：正规表达式 6． 建立正规表达式时，可以先定义简单的正规表达式，然后用它们构造出更复杂的正规表达式。每个表达式r表示一个语言L（R）。 7． 记号的识别：状态转换图 3.3语法需求分析简介 语法分析是编译过程的第二个阶级。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称为语法单位，可表示成语法树。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字序列，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。 语法分析的任务是语法分析器接收词法分析研究器提供的记号串，检查它们是否能由源程序的文法产生，语法分析器在编译器中的位置如图所示： 源程序 记号 中间表示 语法树 取下一 个记号 典型的文法的语法分析器有三类：一类是通用的语法分析方法，如Cocke-Younger-Kasami算法和Early算法，这些方法在生成编译器时效率太低。编译器常用的是自顶向下和自底向上的方法。 采用自顶向下的递归子程序法，就是对应每个非终结符语法单元，编一个独立的处理子程序。语法分析从读入第一个单词开始，由非终结符即开始符出发，沿语法描述图箭头指出的方向进行分析。当遇到非终结符时，则调用相应的处理子程序，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若都不匹配时可能是进入下一非终结符语法单位或是出错。 3．4符号表的应用 在编译程序中符号表用来存放语言中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法分析过程中不断积累和更新表中的信息，并在词法分析到代码生成和各阶段，按各自的需要从表中获得不同的属性信息。不论编译策略是否分趟，符号表的作用和地位是完全一致的。符号表的功能主要有： · 收集符号属性：在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立符号的相应属性信息。 · 上下文语义的合法性检查的依据：同一个标识符可能在程序和不同地方出现，而有关该符号和属性是在不同情况下收集的，特别是在多趟编译及程序分段编译的情况下，更需检查标识符属性在上下文中的一致性和全法性。通过符号表中属性记录可进行这些语义检查。 作为目标代码生成阶段地址分配的依据：除语言中规定的临时分配存储的变量外，每个符号变量在目标代码生成时需要确定其在存储分配的位置。语言程序中的符号变量由它被定义的存储类别或被定义的位置来确定。首先要确定其被分配的区域。其次是根据变量出现的次序。 在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法分析过程中不断积累和更新表中的信息，并在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。不论编译策略是否分趟，符号表的作用和地位是完全一致的。 符号表的功能主要有： 1、 收集符号属性：在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号表中建立符号的相应属性信息。 2、 下文语义的合法性检查的依据：同一个标识符可能在程序和不同地方出现，而有关该符号和属性是在不同情况下收集的，特别是在多趟编译及程序分段编译的情况下，更需检查标识符属性在上下文中的一致性和全法性。通过符号表中属性记录可进行这些语义检查。 3、 作为目标代码生成阶段地址分配的依据：除语言中规定的临时分配存储的变量外，每个符号变量在目标代码生成时需要确定其在存储分配的位置。语言程序中的符号变量由它被定义的存储类别或被定义的位置来确定。首先要确定其被分配的区域。其次是根据变量出现的次序。 语言符号可分为关键字（保留字）符号，操作符号几标识符号。他们之间的主要属性有较大的差别。因此通常为他们建立不同的符号表。 四、系统设计 编译程序的功能图如下： 高级语言程序（源程序） 低级语言（目标语言） 一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器的烦琐细节，使程序员和程序设计独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。 4．1系统设计总体流程图 N Y Y N 4.2语法分析体流程图 N Y N Y Y N N Y N Y 4．3语法分析概要设计 语法分析是编译过程的核心部分，语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。语法分析设计采用递归下降分析法，递归下降分析技术是一种无回溯的自顶向下分析技术，它的实现思想是：让一个识别符程序由一组子程序组成，其中每一个子程序对应于文法的一个非终结符；根据文法的递归定义，这些子程序往往是递归子程序。这种技术称为递归下降技术，相应的识别程序称为递归下降识别程序。在递归下降识别程序中的每一个子程序都对应于文法的一个非终结符，更确切地说为各个非终结符设计一个子程序，每一个子程序分析相对于相应非终结符短语。例如，当进入关于非终结符号〈语句〉的递归子程序时，便期待句子中出现相对于〈语句〉的短语，这时必要的是让识别程序逻辑知道句子中正期待短语的位置。递归下降分析技术是面向目标的，这个目标是子程序所相应的非终结符号，也是预测的，预言能找到这个相对于该非终结符号的短语。 C语言的语法分析EBNF如下： <程序> [<宏定义>][<头文件>]<主函数（main）>[<子函数>] <主函数(main)> [<变量说明部分>][<常量说明部分>][<子函数调用>]<语句> <常量说明部分> CONST<常量定义>{，<常量定义>}； <常量定义> <标识符>=<整型常量> <整型常量 > [+|-]<数字>{<数字>} <变量说明部分> <类型说明><标识符>{，<标识符>}； <类型说明> int| flaot|double|char <标识符> <字母>{<字母>| <数字>} <语句> <赋值语句>|<条件语句>|<循环语句>|<子函数调用语句>|<输入语句>|<输出语句> <赋值语句> <标识符>=<表达式> <条件> <表达式><关系运算符><表达式>|！<表达式> <循环语句> || for‘（’[赋值语句]‘；’[表达式]’；’[条件语句]’）‘ while’(‘<条件>’)’<语句> do’{‘<语句>’}’while’(‘<条件>’)’ <函数调用语句> <函数名>‘（’[<变量说明>]‘）’ <输入语句> scanf’(‘<输入类型声明>‘，’‘&’<标识符>’)‘’；‘ <输出语句> printf’(‘<输出类型声明>‘，’<标识符>’)‘’；‘ <输出类型声明> %d|%c|%s <表达式> [+|-]<项><加减法运算符><项> <项> <因子><乘除法运算符><因子> <因子> <标识符>|<无符号整数>|‘（‘<表达式>’）‘ <加减法运算符> +|- <乘除法运算符> *|/ <关系运算符> ==|<|<=|>|>=|!= <条件语句> if<条件><语句>else<语句> <字母> a|b|……|A|B|……|Z <数字> 0|1|……|9 用C语言实现递归下降分析程序如下： void Error(){…} main( ) { Constant（）; Variable()； Call_sentence()； Sentence(); } Constant（） /*常量说明部分*/ { 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_sentence() { Identifer（）； /*标识符*/ Expression（）；/*表达式*/ } Condition () /*条件*/ { Expression（）； Relation_symbol(); /*关系运算符*/ Expression（）； } Circle_sentence() /*循环语句*/ { for语句（）； while语句（）； do-while语句（）； } Call_sentence() /*函数调用语句*/ { Function_Identifer（）； /*函数名*/ } Expression（） /*表达式*/ { if(+|-) Item(); Math_ symbol(); /*算数运算符*/ 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（）; if(‘)’) Sentence (); } if(else) Sentence (); } 4.4目标代码的分析 代码生成概要： · 代码生成的基础是用目标代码段系统地替换AST的结点和子树，用这种方法可以保持语义紧接着是一个线性代阶段，从重写的AST产生一个线性指令序列。 · 替换过程被称为树重写。线性化由目标代码段和数据流和控制流需求控制。 · 代码生成中的三个主要问题是代码选择、寄存器分配和指令排序。 · 一般情况下，发现最优组合是NP完全的。有三个方法简化代码生成问：1每次只考虑AST的一小部分；2简化目标机；3限制代码段之间的接口。 · 代码生成分三个阶段进行：1预处理，通过程序转换，有些AST结点模式被其他AST结点模式替换；2正确代码生成，通过树重写，所有AST结点模式被目标代码序列替换；3后处理，通过窥孔优化，有些目标代码序列被其他目标代码序列替换。 · 预处理和后处理可能反复执行 · 得到代码最简单的方法是为AST的每个结点生成代码段，由迭代解释程序为其执行。如果目标代码为C或C++，所有优化都可能留给C或C++编译程序。这个过程用最小的投入使解释程序变为编译程序。 · 可以生成对库中简单拷贝的例程调用，而不是多次重复一个代码段，这可以相当可观地减小目标代码的长度。这个技术被称为线程代码。目标代码长度的减少对嵌入式系统可能是重要的。 · 通过将库例程编号并且将程序存储为这些编号数的一个列表可以大大减小目标代码长度。所有目标机依赖现在集中于库例程中。 · 在其他方向，每一个重复的代码段可能在它们的上下文中被部分求值，从而导致更有效的代码。 · 在简单代码生成中，为每个可能的结点类型选择了到目标代码的固定翻译。这些翻译基于共同的接口规定。 · 简单代码生成只需局部判定，因此尤其适合窄编译程序。 · 寄存器机的简单代码生成用机器指令重写每个表达式结点，这满足了代码选择的需要。接口规定是：一条指令的输出寄存器必要性须即用作父母指令的输入寄存器。 · 寄存器机上的表达式的代码可以通过深度优先递归访问生成，这满足了指令排序的需要。递归例程携带两个额外的参数，结果必须传入其中的寄存器和空闲寄存器集，这满足了寄存器分配的需要。 · 因为每个没有处理的操作数都占用了一个寄存器，为需要最多寄存器的操作数首先编译代码是有利的。这要求可以在深度优先访问中计算结点的权。 · 当一个表达式需要的寄存器多于可用的寄存器时，我们需要溢出一个和多个寄存器至存储器。没有最好的寄存器溢出技术，除非进行全面的研究。因此我们求助于启发式算法。 · 在一个启发式算法中，我们分离出可以用可用寄存器编译的最大子表达式，编译它们，将结果存储进临时变量。变减小了原始树，我们对其重复这个过程。 · 机器寄存器被编译程序设计者分为四组：为管理目的所需的、为参数传递保留的、为表达式求值保留的和用于存储局部变量的。通常情况下，每个集合的大小是固定，并且有些集合可能是空的。 · 通常情况下，为局部变量保留的寄存器集比候选集要小。启发式算法包括先来先服务、来自程序员的寄存器提示以及从静态或动态简要表得的使用计数。更高级的启发算法使用图着色。 · 栈上的编译用符号解释的编译有些类似于符号解释。在后者中，我们保持符号表示法，但现在我们包括栈和寄存器，更重要的是，这一次，表示法中的信息必须精确。这种表示法被称为寄变描述符。 · 如果结点的效果可以精确存储于寄变描述符中，我们就这样做。没有为结点生成代码，但其语义保留在寄变描述符中：旧寄变描述+结点 · 如呆结点的效果使我们不能精确地在寄变描述符中保留信息，我们生成代码以获得效果并且在寄变描述符中记录结果。因此语义被保留于结点的重写中。 · 如果从活跃分析中得到可用信息，当离开其活跃范围时，我们可以从寄变描述符中删除关于变量的所有信息。 · 基本块为控制图的最大部分，它不包含分裂和结合。基本块是从标号或从例程的开头开始，正好在转移或类转移结点、标号或例程的结尾结束。它只包含表达式和赋值。 · 基本块的概念从对控制流的关注中分离出对表达式和赋值的整齐序列的代码生成的关注。这种分离对窄编译程序尤其有用，因为它允许它们为表达式序列做优化代码生成。 · 基本块的代码生成分两步进行。首先将控制流图转换成依赖图，它是一“dag”，即有向非循环图。然后我们重写依赖图至代码。收益在于比起控制流图，依赖图对指令顺序限制较少。 · 基本块的依赖图由两种依赖组成：表达式中通过操作数的数据依赖以及通过变量的数据依赖，这些变量的赋值中得到它们的值并且它们的值在且 中被继续使用。最终的数据依赖是那些在基本块后仍被需要的值，这些值称为基本块的根。 · 强调这些数据依赖并且移除其他的控制流依赖产生了一个粗糙的数据依赖图，它可以通过旁路赋值并且只保留那些从根可达的结点而被简化。这个图是dag,即有向非循环图。 · 基本块的dag可以通过识别公共子表达式而进一步缩减。这个缩减可以通过不断地合并具有相同操作数、运算符和依赖的结点而得到。 · 传统地，基本块的dag作为三元式的数组而实现。 · 基本块dag中的结点被重写至相对应的机器指令，然后基于操作数求值将dag线性化。 · 用于线性化dag的晚求值的特有形式可以识别梯形序列，该梯形序列匹配寄存器，——存储器指令序列，这些指令都有公共寄存器。这种序列十分有效。 · 为发现先性化，重一个梯形开始，将第一个可用的梯形序列分离出来，以由后至前的顺序生成代码，然后从dag上离除这个梯形并且重复上述过程。 · 基本块中表达式中的指针可以用两个简单的规则处理：1.对指针所指变量的赋值使随后的表达式中使用的任何变量依赖该赋值；2.从指针检索一个值依赖于所有前面的赋值。扩展分析可能允许取消某些依赖。 · 表达式树的最优重写可以通过BURS代码生成得到，BURS代表自底向上重写系统。 · BURS技术允许将给定的任意复杂的输入树分解为许多子树，其中的每个子树是给定树集的成员，既模式树。模式树可能同样是任意复杂的。 · 应用BURS生成代码，我们将输入树看作表达式AST，将模式树看作带机器指令的AST。 · BURS在输入树上的两遍扫描中操作：一遍自底向上和一遍自顶向下。自底向上扫描参照模式树的结点注释输入树中的每个结点。在输入树中，结点I与结点N相关意味着顶部有I的树可以用顶部有N子树来重写其顶部。这暗示在重写顶部后，I以下的树的所有其他部分也可以被重写，然后自顶向下扫描可以重写整个树。 · 自底向上扫描结合模式树的片段集，特别象词法分析器结合正则表达式的项目集。 · 与词法分析器一样，BURS模式匹配的速度可以通过将其作为FSA而试销来提高（在这种情况下，它是一个树自动机），而不是采用解释的方法）。 · 与词法分析器不同，不同模式有不同代价，而我们想要最小代价的重写。在解释实现中，基于代价的判定可以用动态程序设计技术处理：在每个结点，只有在给顶寄存器类型中得到结果的代价最地的方法被保留。在树自动机实现中，常量代价可以被合并进自动机。结果转换表经常是巨大但可以被可观地压缩。 · BURS代码生成可以相对容易地为额外的需要而改写。例如，具有集中类型寄存器的机器的代码生成和方法到控制流指令的扩展。 · 两个变量都存活于程序中的一个给定位置，当涉及到寄存器分配时它们会相互干扰。如果我们知道所有变量的活跃范围，可以创建变量的寄存器相干图，其中每个结点代表一个变量并且两结点N1与N2之间的每条弧表示结点N1与N2所代表的标量的活跃范围互相重叠。 · 通过对图着色，没有相同颜色的两结点被弧连接，没种颜色代表一个寄存器，这样我们可以发现一个可能的寄存器至变量的分配》最优寄存器分配与使用最低颜色数的图着色对应。 · 最优图着色问题是ＮＰ完全的，但存在好的启发式算法，例如，从图中暂时移除度最小的结点，用相同的算法递归地对余下的图着色，重新连接移去的结点并且对其着色。 · 在超级编译中，一个小但经常使用的中间代码片段被采用并且用惯犯的研究来为它生成可能的最好的代码。结果代码在编译程序中被用做 模板 个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载 。用这种方法已经发现了惊人的代码序列。 · 在将中间代码转换成目标代码前，可能会进行预处理以提高效率。简单预处理的例子有恒定折*　和算术简化。如果原程序语义需要如此，必须注意算术溢出条件是否被预处理忠实地翻译。 · 更广泛的预处理可以在例程上进行，它们可以被内联或克隆。 · 在内联中对例程的调用被被调用的例程体替换。这节省了调用与返回序列，为进一步优化开辟了道路。必须注意保持参数转移的语义。 · 在克隆中，制作例程Ｒ的拷贝Ｃ，其中参数Ｐ的值固定为值Ｖ；对Ｒ的所有调用（其中参数Ｐ有值Ｖ）被对拷贝Ｃ的调用替换。对拷贝Ｃ经常可以产生一个比对原来的例程Ｒ更好的翻译。 · 代码生成过程产生的某些次最优符号机器代码序列可以同归窥孔优化移除，其中固定的参数化序列被其他更好的固定的参数化序列取代。大约１００种替换模式就足够解决相对简单代码生成器留下的几乎所有修正的低效问题 · 指令流中的可替换序列在窥孔优化中用基于替换模式的ＦＳＡ识别。ＦＳＡ识别器识别最长的可能序列，正如其在词法分析器中所做的。然后，序列被替换并且重新开始。 · 代码生成产生了符号奇迹指令表，其离可执行的二进制程序还有几步之遥。在大多数编译程序中，这些步骤有局部汇编程序完成。 · 汇编程序将为源代码模块生成的符号指令翻译成可重定位的二进制目标文件。连接程序将一些可重定位的二进制文件和可能的一些库目标文件结合为可执行的二进制程序文件。载入程序将可执行二景致程序文件的内容装入存储器并且开始执行程序。 · 可重定位目标文件的代码段和数据段由直接从符号指令的来的二进制代码组成。因为一些机器指令需要特殊的对齐，必须在可重定位目标代码中插入空操作指令。 · 可重定位二进制目标文件包含代码段、数据段、重定位信息以及外部连接信息。 · 计算可重定位二进制文件中的存储器地址就好象文件在位置０被装入存储器。重定位信息列出地址的位置，就象通常一样，当文件被装入不同位置时，它必须更新。 · 得到重定位信息从理论上说是一个两遍扫描过程。第二遍扫描可以通过回填重定位地址而避免。重定位信息通常作为位图实现。 · 外部入口点在可重定位二进制文件中标记一个给定单元使其可以被其他可重定位二进制文件使用。一个模块中的外部入口点可以被不同甚至相同模块中的外部访问存取。 · 外部连接信息经常作为记录数组实现 · 连接程序结合其输入文件的代码段和数据段，用重定位与外部连接信息将相对地址转换为绝对地址，在库模块中连接以满足剩余的外部访问。 · 连接产生一个可执行代码文件，它由一个代码段和一个数据段组成。重定位位图与外部符号表已经不存在了，完成了它们的使命。这就是完成了翻译过程。 从编译程序构造的极度高级的观点看，可以认为文本分析由模式匹配完成，上下文处理由数据流机完成，目标代码合成再教育次由模式匹配完成。 五、 结 论 我这次的软件设计的课题是编译器中词法分析、语法分析和目标代码的生成，在这次的设计中基本的功能模块都实现了。在这次设计中编程语言主要是用C实现的，同时要熟练掌握编译原理的知识，算法的知识和软件工程的方法论。 该系统主要功能就是对输入的C语言程序进行词法语法的分析，把输入的C语言程序分析完成后，可以识别出所输入的语言是否有语法错误，系统就会把错误的类型，行数存放到文件中。由于时间的关系，该系统只实现在编器中的一部分功能，不能真正的完成语言的分析过程，如果以后有机会和能力可以继续该系统进行更深一层的设计。 在这次软件设计中让我深切的感受到了平时所学的专业知识的用处与好处，在做设计的同时不仅要有较强的专业知识，更重要的是要有专业设计的方法论。以前我一直认为语言是第一重要的，现在我发现错了，其实在软件的设计中用户的需求分析是最重要的。一个软件，纵使你的技术在精湛、水平如何的高，如果你不使用的话，最终只能是失败，这样的例子可谓屡见不鲜，一些大的软件做了几年，最终还是以失败告终。当前存在一种情况：那就是懂计算机技术的不懂专业、懂专业的不懂计算机技术，这就在一定程度上造成了用户需求分析的困难，开发者与用户之间的交流显得至关重要。对于软件的总体设计、详细设计上也要花大的工夫，这一切当然要建立在需求分析的基础上。编码只是整个软件设计中很小的一部分，大部分时间将用在测试上，因为单元测试一般是程序员自己来测的，最后测试当然要从用户的角度来测试分析，同时用户可能会提出一些新的要求，开发者当然要对软件做相应的修改。这将是一个反复的过程。 有了这次的设计经验和知识，体会到了软件工程的重要性，我相信在以后工作中，我更好的应用软件设计的方法论。在软件设计中，不仅能体现出一个人的专业知识，也能体现出一个人在做软件时的方法以及思维方式。 预处理程序 编译程序 汇编程序 装配/连接—编辑程序 表 格 管 理 目标代码生成 代码优化 中间代码生成 语义分析 语法分析 词法分析 出 错 处 理 语法分析器 词法分析器 符号表 词法分析器 前端的其余部分 语法分析器 符号表 编译程序 启动并初始化 调用Read_File()把源程序调入到内存 调用Get_Next_Token()从内存中取单词 调用Programme()过程 当前程序是否为结束符 出错处理 源程序是否有错误 打印错误 生成并执行目标程序 结束 Programme() 常量说明处理 调用主函数部分Main_Function() Const_Declaration(); Var_Declaration() 测试ch是否为开始符？ Sub_Function() 变量说明处理 在TABLE表中登记过程名 出错 处理 递归调用Programme() 返回 调用列目标程序过程 测试ch是否为语句后跟符 出错处理 生成退出数据段的指令 OPR 0 0 调用语句处理过程 生成开辟数据段指令： int 0 A 在TABLE表中返填子程序入口 取单词Get_Next_Token()