计算机编译原理

计算机编译原理第一页，共二十八页，编辑于2023年，星期五第一章编译概述第二页，共二十八页，编辑于2023年，星期五翻译器翻译器（翻译程序）：把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的软件。翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。汇编程序：如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。第三页，共二十八页，编辑于2023年，星期五编译器与解释器编译器（编译程序）：如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。

解释器（解释程序）：这是另外一种类型的翻译程序，在翻译过程中它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。第四页，共二十八页，编辑于2023年，星期五编译器与解释器例5假设有源程序：read(x);write("x=",x);第五页，共二十八页，编辑于2023年，星期五编译器与解释器特点：1．编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译；2．解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。基本功能：二者相同；所采用的技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。第六页，共二十八页，编辑于2023年，星期五编译器根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试的编译程序称为诊断编译程序（DiagnosticCompiler）；着重于提高目标代码效率的编译程序叫优化编译程序（OptimizingCompiler）。现在很多编译程序同时提供了调试、优化等多种功能，用户可以通过“开关”进行选择。运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。如果一个编译程序产生不同于其宿主机的机器代码，则称它为交叉编译程序(CrossCompiler)。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序（RetargetableCompiler）。第七页，共二十八页，编辑于2023年，星期五编译的阶段编译器从逻辑上可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示。第八页，共二十八页，编辑于2023年，星期五编译的阶段把英文翻译为中文识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。词法分析语法分析中间代码产生优化目标代码产生第九页，共二十八页，编辑于2023年，星期五词法分析任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：正规式和有限自动机对识别出的单词符号用内部形式（内部码）表示。

对不符合词法规则的非法字符串作相应的词法出错处理。第十页，共二十八页，编辑于2023年，星期五词法分析词法分析器id,1

=

id,2

+

id,3

60position=initial+rate

60符号表

positioninitialrate.........123第十一页，共二十八页，编辑于2023年，星期五语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。如程序、语句、表达式等。依循的原则：语法规则描述工具：上下文无关文法通过语法分析确定整个输入串是否构成一个语法上正确的程序，对不符合语法规则的单词序列作相应的语法出错处理。词法分析是一种线性分析，而语法分析是一种层次结构分析。

第十二页，共二十八页，编辑于2023年，星期五语法分析表达式的语法特征：任何一个标识符都是表达式任何一个数都是表达式如果e1和e2都是表达式，那么e1+e2e1*e2(e1)也都是表达式表达式表达式表达式标识符表达式表达式(initial)标识符(rate)数(60)*+initial+rate*60分析树第十三页，共二十八页，编辑于2023年，星期五语法分析语法分析器id,1

=

id,2

+

id,3

60=+60id,1id,2id,3符号表

positioninitialrate.........123语法树第十四页，共二十八页，编辑于2023年，星期五语义分析任务：审查源程序有无语义错误，为代码生成收集类型信息（类型检查）。依循的原则：语义规则语义分析的一个重要部分是类型检查，编译器检查每个算符的运算对象，看它们的类型是否适当。如：实数作为数组下标，报错；整数和实数进行运算时，将整数转变为实数。第十五页，共二十八页，编辑于2023年，星期五语义分析语义分析器=+60id,1id,2id,3=+Inttorealid,1id,2id,360符号表

positioninitialrate.........123第十六页，共二十八页，编辑于2023年，星期五中间代码生成任务：在语义分析的同时将源程序变换成一种内部表示形式（中间代码）。“翻译”仅仅在这里才开始涉及到。中间代码：一种结构简单、含义明确的记号系统。原则：容易生成；容易将它翻译成目标代码。

中间代码：三元式，四元式，树形结构等。四元式：（运算符，运算对象1，运算对象2，结果）第十七页，共二十八页，编辑于2023年，星期五中间代码生成中间代码生成器t1=inttoreal(60)t2=id3t1t3=id2+t2id1=t3=+inttorealid,1id,2id,360符号表

positioninitialrate.........123第十八页，共二十八页，编辑于2023年，星期五中间代码生成上面的例子表示成四元式：(inttoreal 60 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1)第十九页，共二十八页，编辑于2023年，星期五代码优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等等。第二十页，共二十八页，编辑于2023年，星期五代码优化代码优化器t1=inttoreal(60)t2=id3t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t1符号表

positioninitialrate.........123第二十一页，共二十八页，编辑于2023年，星期五代码生成任务:把中间代码变换成特定机器上的目标代码。特点：与硬件系统结构和指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。

目标代码三种形式:绝对指令代码:可直接运行可重定位指令代码:需要连接装配（多数）汇编指令代码:需要进行汇编第二十二页，共二十八页，编辑于2023年，星期五代码生成代码生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t1符号表

positioninitialrate.........123第二十三页，共二十八页，编辑于2023年，星期五符号表管理符号表：用来登记源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名、变量名，还是过程名等等；若是变量名，它的类型、所占内存、地址等等。通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填入到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查证。当扫描器识别出一个名字（标识符）后，它把该名字填入到符号表中。但这时不能完全确定名字的属性，它的各种属性要在后续的各阶段才能填入。例如，名字的类型等要在语义分析时才能确定，而名字的地址可能要到目标代码生成才能确定。第二十四页，共二十八页，编辑于2023年，星期五错误诊断和报告出错处理程序：发现源程序中的错误，把有关错误信息报告给用户。语法错误语义错误好的编译程序应能最大限度地发现源程序中的各种错误，准确地指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，以便进一步发现其它可能的错误。第二十五页，共二十八页，编辑于2023年，星期五阶段的分组有关名词：前端（frontend）：主要依赖于源语言而与目标机器无关的编译阶段。如：词法分析、语法分析、语义分析、中间代码生成、部分优化工作、与前端有关的出错处理工作和符号表管理工作。后端（backend）：依赖于目标机而一般不依赖于源语言，只与中间代码有关的编译阶段。如：面向目标机器的优化，目标代码生成，以及相关出错处理和符号表操作。遍（pass趟）：对源程序或其等价的中间语言程序从头到尾扫描并完成规定任务的过程。每一遍扫描可完成上述一个阶段或多个阶段的工作。阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。第二十六页，共二十八页，编辑于2023年，星期五编译器的编写直接使用汇编语言和程序设计语言；利用编译器编写工具：词/语法、语法制导翻译、代码生成、数据流分析等