编译原理课件chap01(陈火旺).ppt

1、第二章 文法和语言,编译原理,第一章 编译程序引论 第二章 文法和语言 第三章 词法分析 第四章 自顶向下语法分析方法 第五章 自底向上优先分析方法 第六章 LR分析方法 第七章 语法制导翻译和中间代码生成 第八章 运行时存储空间分配 第九章 代码生成,第一章 引 论,第一章 引论,1.1 什么叫编译程序 编译程序:是指这样的程序，它能够把某种语言的程序转换成另一种语言的程序，而后者与前者在逻辑上是等价的。如果源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java这样的“高级语言”，而目标语言如汇编语言之类的“低级语言”这样的翻译程序则称之为编译程序。 本课程主要介

2、绍设计和构造编译程序的基本原理和方法。,第一章 引 论,编译程序又简称为“编译器”,第一个编译器是20世纪50年代的后期出现的FORTRAN语言编译器。 同样，解释程序又简称为“解释器”，但是在概念上与编译器有明显区别： 编译程序是源转换系统，而解释程序是源程序的一个执行系统。 编译程序的结果是得到等价源程序的某种目标机程序，而解释程序的结果是得到源程序的执行结果，即它相当于执行源程序的抽象机。,第一章 引 论,注意编译程序与解释程序的区别，一个语言的解释程序是这样的程序：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。 术语“编译”的内涵是实现从源语言表示的算法向

3、目标语言表示的算法的等价变换。,第一章 引 论,高级语言分类及其编译： 过程式语言：FORTRAN Pascal Ada C （特点：面向驱动，面向语句，由系列的语句组成） 函数式语言：LISP ML ASL （注重程序表示的功能，而不是一个语句接一个语句的执行） 从已有的函数出发构造更复杂的函数。 逻辑式语言：PROLOG （检查一定的条件，当满足时，则执行适当的动作。） 对象式语言：SMALLTALK C+ （封装性、继承性、多态性）,第一章 引 论,这里主要研究过程式语言的编译,高级语言分类及其编译： 过程式语言：FORTRAN Pascal ADA C 函数式语言：LISP ML AS

4、L 逻辑式语言：PROLOG 对象式语言：SMALLTALK C+ 函数式语言与逻辑式语言，特别是逻辑式语言，其编译技术与过程式语言的差别比较大；因对象式语言的载体基本上是过程式的，所以其编译程序也不难理解。,第一章 引 论,1.2 编译过程概述 编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。 掌握编译过程的五个基本阶段，是我们学习编译原理课程的基本内容，把编译的五个基本阶段与英译中的五个步骤相比较，有利于对编译过程的理解：,第一章 引 论,英译与编译的比较,1。识别出句子中的一个个单字 2。分析句子的语法结构 3。初步翻译句子的含意 4。译文修饰 5。写出最后译

5、文,1。词法分析 2。语法分析 3。语义分析中间代码生成 4。优化 5。目标代码生成,第一章 引 论,源程序是以文本文件方式存在,注意：程序总是以字符串的方式存在。,第一章 引 论,1.2.1 词法分析 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（也称单词符号，或简称符号） 在词法分析阶段工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。,1。识别出句子中的一个个单字,第一章 引 论,1.2.1 词法分析 什么是单词 逻辑上相连的一组字符，从语法的角度来看，这些字符所具有的集体含义已不能再区分了，通常包括：保留字、标识符、界符、算符和常量等,第一章

6、 引 论,例. 考虑下面的一段源程序,var area, radius:real; begin read(radius); area:3.1415926*radius*radius; end. 保留字： var， begin， end， read，real 运算符： *， : 界符：(，)，; ，. 标识符： radius， area,第一章 引 论,有关术语,词法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and

7、 grouped into tokens,which are sequences of characters that have a collective meaning. 单词-token 保留字-reserved word 标识符 -identifier(user-defined name),第一章 引 论,1.2.2语法分析 语法分析的任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（语法范畴），如“短语”、“句子”、 “子句”、“程序段”等。 语法规则通常用上下文无关文法描述。 例. 对赋值语句area:3.1415926*radius*radius进行语法分

8、析,2。分析句子的语法结构,第一章 引 论,赋值语句的语法树,*,第一章 引 论,术语,语法分析(syntax analysis or parsing) The purpose of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to constru

9、ct a suitable representation of its phrase structure. 语法树(推导树)(parse tree or derivation tree),第一章 引 论,1.2.3语义分析与中间代码的产生 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 这一阶段通常包括两方面的工作首先对各种语法范畴进行静态语义检查（如：变量是否定义，类型是否正确等），如果正确则进行另一方面的工作，即进行中间代码的翻译。 通常使用属性文法描述语义规则,3。初步翻译句子的含意,第一章 引 论,1.2.3语义分析与中间代码的产生 什么是中间代码 是将

10、源程序转变成的一种内部表现形式，是一种结构简单、含义明确的记号系统 中间代码的两种性质 容易生成这种中间代码 容易将它翻译成目标代码 主要形式 四元式、三元式、间接三元式、逆波兰式等,第一章 引 论,中间代码生成：,如：sum：firstcount10 生成四元式序列： （inttoreal 10 t1 ） （ id3 t1 t2） （ id2 t2 t3） （： t3 id1）,运算符,运算对象1,运算对象2,结果,四元式的形式为： （算符，运算对象1，运算对象2，结果）,id1,id2,id3,t1，t2，t3是临时变量,第一章 引 论,术语,语义分析(semantic analysis)

11、 The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rules e.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.,第一章 引 论,1.2.4 优化 优化的任务在于对前段产生的中间代码进行加工，以期在最后

12、阶段产生更为高效（省时间和空间）的代码 优化所依循的原则是程序的等价变换规则 其方法有：公共子表达式的提取、循环优化、删除无用代码等。,4。译文修饰,第一章 引 论,代码优化,主要任务：对中间代码进行变换，使目标代码更为高效。（节省时间和空间） id1:= id2 + id3 * 60 (1)(inttoreal60-t1) (2)( * id3t1t2) (3)( +id2t2t3) (4)( :=t3-id1) 变换 （1） ( *id360.0t1) ( 2）（ + id2 t1id1) 例2 见P4,第一章 引 论,1.2.5 目标代码生成 主要工作 是整个编译过程的最后一个阶段，这一

13、阶段的工作是把中间代码变换成特定目标机器上的绝对指令代码或可重定向的指令代码或汇编指令代码,5。写出最后译文,第一章 引 论,目标代码生成,(*id360.0t1) (+id2t1id1),MOVid3,R2 MUL#60.0,R2 MOVid2,R1 ADDR2,R1 MOVR1,id1,主要与硬件系统结构和指令含义有关。,第一章 引 论,1。3 编译程序的结构,表 格 管 理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出 错 处 理,第一章 引 论,我们可以按照上页的总框图设计编译程序。从图中我们可以看

14、到除编译的五个基本阶段外，一个完整的编译程序还应包括“表格管理”和“出错处理”两部分 1.3.2 表格与表格管理 在编译程序使用的表格中最重要的是符号表它用来登记源程序中出现的每一个名字以及名字的各种属性。如一个名字是常量名、变量名，还是过程名等；如果是变量名它的类型又是什麽、所占内存是多大、地址是什么等。,第一章 引 论,1.3.3 出错处理 一个编译程序不仅能对书写正确的程序进行编译，而且应能对出现在源程序中的错误进行处理。如果源程序有错，编译程序应设法发现错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做处错处理程序）完成的。,第一章 引 论,1.3.5 编译前端与后端 前

15、端主要由与源语言有关但与目标机无关的那些部分组成。通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作，也可以包括在前端。 后端包括编译程序中与目标代码有关的部分，如与目标机有关的有关的优化，和目标代码的生成等。,第一章 引 论,1.3.6 遍 遍 含义：对源语言或等价的中间语言程序从头到尾地扫描并完成规定的任务的过程 分遍的相关因素 源语言和目标机器的特征、编译程序的工作环境 编译程序模块的软件接口,从时间和空 间角度看,多遍编译 少占内存，多耗时间 一遍编译 多占内存，少耗时间,第一章 引 论,1.4 编译程序与程序设计环境 编译程序无疑是实现高级语言的一个最重要的工具。但支持程序设计人员进行程序设计开发通常还需要其它一些工具：如编辑程序、连接程序、调试程序等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。 在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、程序分析等工具直接依赖于编译程序所产生的结果，而其它工具的构造也常常要用到编译的原理、方法和技术。,第一章 引 论,1.5 编译程序的生成 以前构造编译程序大多是用机器语言或汇编语言作工具的。为了充分发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然使用这