计算机编译原理精选文档.ppt

计算机编译原理本讲稿第一页，共二十八页第一章 编译概述本讲稿第二页，共二十八页翻译器翻译器v翻译器翻译器（翻译程序）：把某一种语言程序（翻译程序）：把某一种语言程序(称为源语言程称为源语言程序序)等价地转换成另一种语言程序等价地转换成另一种语言程序(称为目标语言程序称为目标语言程序)的软件。的软件。v翻译程序根据所处理的对象和实现的途径不同又分为：翻译程序根据所处理的对象和实现的途径不同又分为：汇编程序、编译程序和解释程序。汇编程序、编译程序和解释程序。v汇编程序汇编程序：如果源语言是某种汇编语言，而目标语言是：如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。编程序。本讲稿第三页，共二十八页编译器与解释器编译器与解释器v编译器编译器（编译程序）：如果源语言是某种高级语言，而目标（编译程序）：如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。翻译程序就称为编译程序。v 解释器解释器（解释程序）：这是另外一种类型的翻译程（解释程序）：这是另外一种类型的翻译程序，在翻译过程中它按照高级语言源程序在计算机上序，在翻译过程中它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。就称为解释程序。本讲稿第四页，共二十八页编译器与解释器编译器与解释器例5 假设有源程序：read(x);write(x=,x);本讲稿第五页，共二十八页编译器与解释器编译器与解释器v特点：特点：1 1编译器：工作效率高，即时间快、空间省；交互性与编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数动态特性差、可移植性差。大多数PLPL采用此种方法翻译；采用此种方法翻译；2 2解释器：工作效率低，即时间慢、空间费；交互性与动解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的态特性好、可移植性好。早期的BasicBasic和现在的和现在的JavaJava等。等。v基本功能基本功能：二者相同；：二者相同；v所采用的技术所采用的技术：从翻译的角度来讲，两种方式所涉及：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。的原理、方法、技术相似。本讲稿第六页，共二十八页编译器编译器v根据不同的用途和侧重，编译程序还可进一步分类。专门根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试的编译程序称为用于帮助程序开发和调试的编译程序称为诊断编译程序诊断编译程序（Diagnostic CompilerDiagnostic Compiler）；着重于提高目标代码效率的编译）；着重于提高目标代码效率的编译程序叫程序叫优化编译程序优化编译程序（Optimizing CompilerOptimizing Compiler）。）。v现在很多编译程序同时提供了调试、优化等多种功能，用现在很多编译程序同时提供了调试、优化等多种功能，用户可以通过户可以通过“开关开关”进行选择。运行编译程序的计算机称进行选择。运行编译程序的计算机称宿主机宿主机，运行编译程序所产生目标代码的计算机称，运行编译程序所产生目标代码的计算机称目标目标机机。如果一个编译程序产生不同于其宿主机的机器代码，则。如果一个编译程序产生不同于其宿主机的机器代码，则称它为称它为交叉编译程序交叉编译程序(Cross Compiler)(Cross Compiler)。如果不需重写编译。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序程序中与机器无关的部分就能改变目标机，则称该编译程序为为可变目标编译程序可变目标编译程序（Retargetable CompilerRetargetable Compiler）。）。本讲稿第七页，共二十八页编译的阶段编译的阶段v编译器从逻辑上可编译器从逻辑上可以分成若干阶段，以分成若干阶段，每个阶段把源程序每个阶段把源程序从一种表示变换成从一种表示变换成另一种表示。另一种表示。本讲稿第八页，共二十八页编译的阶段编译的阶段v把英文翻译为中文把英文翻译为中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。词法分析词法分析语法分析语法分析中间代码产中间代码产生生优化优化目标代码产目标代码产生生本讲稿第九页，共二十八页词法分析词法分析v任务任务:输入源程序，对构成源程序的字符串进行扫描和分输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。解，识别出一个个单词符号。v依循的原则：构词规则依循的原则：构词规则v描述工具：正规式和有限自动机描述工具：正规式和有限自动机vv对识别出的单词符号用内部形式（内部码）表示。对识别出的单词符号用内部形式（内部码）表示。对识别出的单词符号用内部形式（内部码）表示。对识别出的单词符号用内部形式（内部码）表示。vv对不符合词法规则的非法字符串作相应的词法出错处对不符合词法规则的非法字符串作相应的词法出错处理理。本讲稿第十页，共二十八页词法分析词法分析词法分析器词法分析器 id,1 =id,2 +id,3 60 position=initial+rate 60符符 号号 表表 positioninitialrate.123本讲稿第十一页，共二十八页语法分析语法分析v任务任务:在词法分析的基础上，根据语言的语法规则把单在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。如程序、语句、表达词符号串分解成各类语法单位。如程序、语句、表达式等。式等。v依循的原则：语法规则依循的原则：语法规则v描述工具：上下文无关文法描述工具：上下文无关文法vv通过语法分析确定整个输入串是否构成一个语法上正确的通过语法分析确定整个输入串是否构成一个语法上正确的通过语法分析确定整个输入串是否构成一个语法上正确的通过语法分析确定整个输入串是否构成一个语法上正确的程序，对不符合语法规则的单词序列作相应的语法出错处程序，对不符合语法规则的单词序列作相应的语法出错处程序，对不符合语法规则的单词序列作相应的语法出错处程序，对不符合语法规则的单词序列作相应的语法出错处理。理。理。理。v词法分析是一种线性分析，而语法分析是一种层次结构分词法分析是一种线性分析，而语法分析是一种层次结构分析。析。本讲稿第十二页，共二十八页语法分析语法分析v表达式的语法特征：表达式的语法特征：任何一个标识符都任何一个标识符都是表达式是表达式任何一个数都是表任何一个数都是表达式达式如果如果e e1 1和和e e2 2都是表都是表达式，那么达式，那么ve e1+1+e e2 2ve e1*1*e e2 2 v(e e1)1)也都是表达式也都是表达式表达式表达式表达式表达式表达式表达式标识符标识符表达式表达式表达式表达式(initial)标识符标识符(rate)数数(60)*+initial+rate*60分析树分析树本讲稿第十三页，共二十八页语法分析语法分析语法分析器语法分析器 id,1 =id,2 +id,3 60 =+60 id,1 id,2 id,3 符符 号号 表表 positioninitialrate.123语法树语法树本讲稿第十四页，共二十八页语义分析语义分析v任务：任务：审查源程序有无语义错误，为代码生审查源程序有无语义错误，为代码生成收集类型信息（类型检查）。成收集类型信息（类型检查）。v依循的原则：语义规则依循的原则：语义规则v语义分析的一个重要部分是类型检查，编译语义分析的一个重要部分是类型检查，编译器检查每个算符的运算对象，看它们的类型器检查每个算符的运算对象，看它们的类型是否适当。如：实数作为数组下标，报错；是否适当。如：实数作为数组下标，报错；整数和实数进行运算时，将整数转变为实数。整数和实数进行运算时，将整数转变为实数。本讲稿第十五页，共二十八页语义分析语义分析语义分析器语义分析器=+60 id,1 id,2 id,3 =+Inttoreal id,1 id,2 id,3 60 符符 号号 表表 positioninitialrate.123本讲稿第十六页，共二十八页中间代码生成中间代码生成v任务：任务：在语义分析的同时将源程序变换成一种内部表在语义分析的同时将源程序变换成一种内部表示形式（中间代码）。示形式（中间代码）。“翻译翻译”仅仅在这里才开始涉仅仅在这里才开始涉及到。及到。vv中间代码：一种结构简单、含义明确的记号系统。原中间代码：一种结构简单、含义明确的记号系统。原则：则：容易生成；容易生成；容易将它翻译成目标代码。容易将它翻译成目标代码。v中间代码：三元式，四元式，树形结构等。中间代码：三元式，四元式，树形结构等。四元式四元式：（运算符，运算对象：（运算符，运算对象：（运算符，运算对象：（运算符，运算对象1 1 1 1，运算对象，运算对象，运算对象，运算对象2 2 2 2，结果），结果），结果），结果）本讲稿第十七页，共二十八页中间代码生成中间代码生成中间代码生成器中间代码生成器t1=inttoreal(60)t2=id3 t1t3=id2+t2id1=t3=+inttoreal id,1 id,2 id,3 60 符符 号号 表表 positioninitialrate.123本讲稿第十八页，共二十八页中间代码生成中间代码生成v上面的例子表示成四元式：上面的例子表示成四元式：(inttoreal60-t1 )(*id3t1t2 )(+id2t2t3 )(:=t3-id1)本讲稿第十九页，共二十八页代码优化代码优化v任务：对于前阶段产生的中间代码进行加工变换，以期在最任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。后阶段产生更高效的目标代码。v依循的原则：程序的等价变换规则依循的原则：程序的等价变换规则v优化的主要方面有：公共子表达式的提取、循环优化、优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等等。删除无用代码等等。本讲稿第二十页，共二十八页代码优化代码优化代码优化器代码优化器t1=inttoreal(60)t2=id3 t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t1符符 号号 表表 positioninitialrate.123本讲稿第二十一页，共二十八页代码生成代码生成v任务任务:把中间代码变换成特定机器上的目标代码。把中间代码变换成特定机器上的目标代码。v特点：特点：与硬件系统结构和指令含义有关，涉及到硬件与硬件系统结构和指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调型变量的存储空间分配以及寄存器和后缓寄存器的调度等。度等。v目标代码三种形式目标代码三种形式:绝对指令代码绝对指令代码:可直接运行可直接运行 可重定位指令代码可重定位指令代码:需要连接装配（多数）需要连接装配（多数）汇编指令代码汇编指令代码:需要进行汇编需要进行汇编本讲稿第二十二页，共二十八页代码生成代码生成代码生成器代码生成器MOVF id3,R2MULF#60.0,R2MOVF id2,R1ADDF R2,R1MOVF R1,id1t1=id3*60.0id1=id2+t1符符 号号 表表 positioninitialrate.123本讲稿第二十三页，共二十八页符号表管理符号表管理v符符号号表表：用用来来登登记记源源程程序序中中出出现现的的每每个个名名字字以以及及名名字字的的各各种种属属性性。例例如如，一一个个名名字字是是常常量量名名、变变量量名名，还还是是过过程程名名等等等等；若若是是变变量量名名，它它的的类类型型、所占内存、地址等等。所占内存、地址等等。v通通常常，编编译译程程序序在在处处理理到到名名字字的的定定义义性性出出现现时时，要要把把名名字字的的各各种种属属性性填填入入到到符符号号表表中中；当当处处理理到到名名字字的的使使用用性性出出现现时时，要要对对名名字字的的属属性性进进行行查查证。证。v当当扫扫描描器器识识别别出出一一个个名名字字（标标识识符符）后后，它它把把该该名名字字填填入入到到符符号号表表中中。但但这这时时不不能能完完全全确确定定名名字字的的属属性性，它它的的各各种种属属性性要要在在后后续续的的各各阶阶段段才才能能填填入入。例例如如，名名字字的的类类型型等等要要在在语语义义分分析析时时才才能能确确定，而名字的地址可能要到目标代码生成才能确定。定，而名字的地址可能要到目标代码生成才能确定。本讲稿第二十四页，共二十八页错误诊断和报告错误诊断和报告v出错处理程序：发现源程序中的错误，把有关错误信息出错处理程序：发现源程序中的错误，把有关错误信息报告给用户。报告给用户。语法错误语法错误语义错误语义错误v好好的的编编译译程程序序应应能能最最大大限限度度地地发发现现源源程程序序中中的的各各种种错错误误，准准确确地地指指出出错错误误的的性性质质和和发发生生错错误误的的地地点点，并并且且能能将将错错误误所所造造成成的的影影响响限限制制在在尽尽可可能能小小的的范范围围内内，使使得得源源程程序序的的其其余余部部分分能能继继续续被被编编译译下下去去，以以便便进进一一步步发发现现其其它它可可能能的的错错误。误。本讲稿第二十五页，共二十八页阶段的分组阶段的分组vv有关名词：有关名词：有关名词：有关名词：前端前端前端前端（front endfront endfront endfront end）：主要依赖于源语言而与目标机器无关的编）：主要依赖于源语言而与目标机器无关的编）：主要依赖于源语言而与目标机器无关的编）：主要依赖于源语言而与目标机器无关的编译阶段。如：词法分析、语法分析、语义分析、中间代码生成、译阶段。如：词法分析、语法分析、语义分析、中间代码生成、译阶段。如：词法分析、语法分析、语义分析、中间代码生成、译阶段。如：词法分析、语法分析、语义分析、中间代码生成、部分优化工作、与前端有关的出错处理工作和符号表管理工作。部分优化工作、与前端有关的出错处理工作和符号表管理工作。部分优化工作、与前端有关的出错处理工作和符号表管理工作。部分优化工作、与前端有关的出错处理工作和符号表管理工作。后端后端后端后端（back endback endback endback end）：依赖于目标机而一般不依赖于源语言，只与中）：依赖于目标机而一般不依赖于源语言，只与中）：依赖于目标机而一般不依赖于源语言，只与中）：依赖于目标机而一般不依赖于源语言，只与中间代码有关的编译阶段。如：面向目标机器的优化，目标代码生成，间代码有关的编译阶段。如：面向目标机器的优化，目标代码生成，间代码有关的编译阶段。如：面向目标机器的优化，目标代码生成，间代码有关的编译阶段。如：面向目标机器的优化，目标代码生成，以及相关出错处理和符号表操作。以及相关出错处理和符号表操作。以及相关出错处理和符号表操作。以及相关出错处理和符号表操作。遍遍遍遍（pass pass pass pass 趟）：对源程序或其等价的中间语言程序从头到尾扫趟）：对源程序或其等价的中间语言程序从头到尾扫趟）：对源程序或其等价的中间语言程序从头到尾扫趟）：对源程序或其等价的中间语言程序从头到尾扫描并完成规定任务的过程。每一遍扫描可完成上述一个阶段或描并完成规定任务的过程。每一遍扫描可完成上述一个阶段或描并完成规定任务的过程。每一遍扫描可完成上述一个阶段或描并完成规定任务的过程。每一遍扫描可完成上述一个阶段或多个阶段的工作。多个阶段的工作。多个阶段的工作。多个阶段的工作。阶段与遍是不同的概念。一遍可以由若干段阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。组成，一个阶段也可以分若干遍来完成。本讲稿第二十六页，共二十八页编译器的编写编译器的编写v直接使用汇编语言和程序设计语言；直接使用汇编语言和程序设计语言；v利用编译器编写工具：词利用编译器编写工具：词/语法、语法制导翻译、代语法、语法制导翻译、代码生成、数据流分析等；码生成、数据流分析等；v基于编译器基础架构的编译器构造系统（开放式编译器，基于编译器基础架构的编译器构造系统（开放式编译器，如如GCCGCC、SUIFSUIF等）。等）。GCC Home PageGCC Home Page.http:/gcc.gnu.org.http:/gcc.gnu.org.Gasta HomepageGasta Homepage.http:/.http:/SUIF Compiler System Home PageSUIF Compiler System Home Page.http:/suif.stanford.edu http:/suif.stanford.edu 本讲稿第二十七页，共二十八页习题1 1、解释下列名词：、解释下列名词：源语言源语言 目标语言目标语言 翻译器翻译器 解释器解释器 编译器编译器 2 2、典型的编译器可以分成哪几个主要的逻辑阶、典型的编译器可以分成哪几个主要的逻辑阶段，各阶段的主要功能是什么？段，各阶段的主要功能是什么？本讲稿第二十八页，共二十八页