《编译原理课件chap01(陈火旺)(精品).ppt》由会员分享，可在线阅读，更多相关《编译原理课件chap01(陈火旺)(精品).ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章第一章 引论引论1.1 1.1 什么叫编译程序什么叫编译程序编译程序编译程序:是指这样的程序，它能够把某种是指这样的程序，它能够把某种语言的程序转换成另一种语言的程序，语言的程序转换成另一种语言的程序，而后者与前者在逻辑上是等价的。如果而后者与前者在逻辑上是等价的。如果源语言是诸如源语言是诸如FORTRANFORTRAN、PascalPascal、C C、AdaAda、SmalltalkSmalltalk或或JavaJava这样的这样的“高级语言高级语言”，而目标语言如汇编语言之类的而目标语言如汇编语言之类的“低级语低级语言言”这样的翻译程序则称之为编译程序。这样的翻译程序则称之为编译程
2、序。本课程主要介绍设计和构造编译程序本课程主要介绍设计和构造编译程序的基本原理和方法。的基本原理和方法。第一章 引 论编译程序又简称为“编译器”第一个编译器是20世界50年代的后期出现的FORTRAN语言编译器。同样，解释程序又简称为“解释器”，但是在概念上与编译器有明显区别：编译程序是源转换系统，而解释程序是源程序的一个执行系统。编译程序的结果是得到等价源程序的某种目标机程序，而解释程序的结果是得到源程序的执行结果，即它相当于执行源程序的抽象机。第一章 引 论 注意编译程序与解释程序的区别，一个语注意编译程序与解释程序的区别，一个语言的言的解释程序解释程序是这样的程序：它以该语言是这样的程序
3、：它以该语言写的源程序作为输入，但不产生目标程序，写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。而是边解释边执行源程序本身。术语术语“编译编译”的内涵是实现从源语言表示的内涵是实现从源语言表示的算法向目标语言表示的算法的等价变换。的算法向目标语言表示的算法的等价变换。第一章 引 论高级语言分类及其编译：过程式语言：FORTRAN Pascal Ada C（特点：面向驱动，面向语句，由系列的语句组成）函数式语言：LISP ML ASL（注重程序表示的功能，而不是一个语句接一个语句的执行）从已有的函数出发构造更复杂的函数。逻辑式语言：PROLOG（检查一定的条件，当满足时，则执
4、行适当的动作。）对象式语言：SMALLTALK C+（封装性、继承性、多态性）第一章 引 论这里主要研究过程式语言的编译高级语言分类及其编译：过程式语言：FORTRAN Pascal ADA C 函数式语言：LISP ML ASL 逻辑式语言：PROLOG 对象式语言：SMALLTALK C+函数式语言与逻辑式语言，特别是逻辑式语言，其编译技术与过程式语言的差别比较大；因对象式语言的载体基本上是过程式的，所以其编译程序也不难理解。第一章 引 论1.2 1.2 编译过程概述编译过程概述 编译程序的工作，从输入源程序开始编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非到输出目标程
5、序为止的整个过程，是非常复杂的。常复杂的。掌握编译过程的五个基本阶段，是我掌握编译过程的五个基本阶段，是我们学习编译原理课程的基本内容，把编们学习编译原理课程的基本内容，把编译的五个基本阶段与英译中的五个步骤译的五个基本阶段与英译中的五个步骤相比较，有利于对编译过程的理解：相比较，有利于对编译过程的理解：第一章 引 论英译与编译的比较1 1。识别出句子中的一个个。识别出句子中的一个个单字单字2 2。分析句子的语法结构。分析句子的语法结构3 3。初步翻译句子的含意。初步翻译句子的含意4 4。译文修饰。译文修饰5 5。写出最后译文。写出最后译文1。词法分析2。语法分析3。语义分析中间代码生成4。优
6、化5。目标代码生成第一章 引 论源程序是以文本文件方式存在注意：程序总是以字符串的方式存在。第一章 引 论1.2.1 词法分析词法分析输入源程序，对构成源程序的字符串进行输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（也称扫描和分解，识别出一个个单词（也称单词符号，或简称符号）单词符号，或简称符号）在词法分析阶段工作所依循的是语言的词在词法分析阶段工作所依循的是语言的词法规则。描述词法规则的有效工具是正法规则。描述词法规则的有效工具是正规式和有限自动机。规式和有限自动机。第一章 引 论1.2.1 词法分析词法分析什么是单词逻辑上相连的一组字符，从语法的角度来看，这些字符所具有
7、的集体含义已不能再区分了，通常包括：保留字、标识符、界符、算符和常量等第一章 引 论例.考虑下面的一段源程序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 lef
8、t to right and grouped into tokens,which are sequences of characters that have a collective meaning.单词-token保留字-reserved word标识符-identifier(user-defined name)第一章 引 论1.2.2语法分析语法分析 语法分析的任务：在词法分析的基础上，根语法分析的任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语据语言的语法规则，把单词符号分解成各类语法单位（语法范畴），如法单位（语法范畴），如“短语短语”、“句子句子”、“子句子句”、
9、“程序段程序段”等。等。语法规则通常用语法规则通常用上下文无关文法上下文无关文法描述。描述。例.对赋值语句area:3.1415926*radius*radius进行语法分析 第一章 引 论赋值语句的语法树*:*3.1415926radiusradius第一章 引 论术语语法分析(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 p
10、rogram is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.语法树(推导树)(parse tree or derivation tree)第一章 引 论1.2.3语义分析与中间代码的产生语义分析与中间代码的产生 对语法分析所识别出的各类语法范畴，对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中分析其含义，并进行初步翻译（产生中间代码）。间代码）。这一
11、阶段通常包括两方面的工作首先这一阶段通常包括两方面的工作首先对各种语法范畴进行静态语义检查（如：对各种语法范畴进行静态语义检查（如：变量是否定义，类型是否正确等），如变量是否定义，类型是否正确等），如果正确则进行另一方面的工作，即进行果正确则进行另一方面的工作，即进行中间代码的翻译。中间代码的翻译。通常使用通常使用属性文法属性文法描述语义规则描述语义规则 第一章 引 论1.2.3语义分析与中间代码的产生语义分析与中间代码的产生什么是中间代码是将源程序转变成的一种内部表现形式，是一种结构简单、含义明确的记号系统中间代码的两种性质容易生成这种中间代码容易将它翻译成目标代码主要形式四元式、三元式、间
12、接三元式、逆波兰式等 第一章 引 论中间代码生成：如：sum：firstcount10 生成四元式序列：（inttoreal 10 t1）（id3 t1 t2）（id2 t2 t3）（：t3 id1）运算符运算对象1运算对象2结果四元式的形式为：（算符，运算对象1，运算对象2，结果）id1id2id3t1，t2，t3是临时变量第一章 引 论术语语义分析(semantic analysis)The parsed program is further analyzed to determine whether it conforms to the source languages contextu
13、al constraints:scope rules,type rulese.g.To relate each applied occurrence of an identifier in the source program to the corresponding declaration.第一章 引 论1.2.4 优化优化 优化的任务在于对前段产生的中间代码优化的任务在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高进行加工，以期在最后阶段产生更为高效（省时间和空间）的代码效（省时间和空间）的代码 优化所依循的原则是程序的等价变换优化所依循的原则是程序的等价变换规则规则 其方法有：
14、公共子表达式的提取、循其方法有：公共子表达式的提取、循环优化、删除无用代码等。环优化、删除无用代码等。第一章 引 论代码优化主要任务：对中间代码进行变换，使目标代码更为高效。（节省时间和空间）id1:=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)变换变换 （1）(*id360.0t1)(2）（+id2 t1id1)例例2 2 见见P4P4第一章 引 论1.2.5 目标代码生成目标代码生成主要工作是整个编译过程的最后一个阶段，这一阶段的工作是把中间代码变换成特定目标机器上的绝对指令代码或可重定向的指令代码
15、或汇编指令代码第一章 引 论目标代码生成(*id360.0t1)(+id2t1id1)MOV id3,R2MUL#60.0,R2MOV id2,R1ADDR2,R1MOV R1,id1主要与硬件系统结构和指令含义有关。第一章 引 论1。3 编译程序的结构编译程序的结构表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理第一章 引 论 我们可以按照上页的总框图设计编译程序。从我们可以按照上页的总框图设计编译程序。从图中我们可以看到除编译的五个基本阶段外，一图中我们可以看到除编译的五个基本阶段外，一个完整的编译程序还应包括个完
16、整的编译程序还应包括“表格管理表格管理”和和“出出错处理错处理”两部分两部分 1.3.2 表格与表格管理表格与表格管理 在编译程序使用的表格中最重要的是在编译程序使用的表格中最重要的是符号表符号表它用来登记源程序中出现的每一个名字以及名子它用来登记源程序中出现的每一个名字以及名子的各种属性。如一个名字是常量名、变量名，还的各种属性。如一个名字是常量名、变量名，还是过程名等；如果是变量名它的类型又是什麽、是过程名等；如果是变量名它的类型又是什麽、所占内存是多大、地址是什么等。所占内存是多大、地址是什么等。第一章 引 论1.3.3 出错处理出错处理 一个编译程序不仅能对书写正确的程序一个编译程序不
17、仅能对书写正确的程序进行编译，而且应能对处现在源程序中进行编译，而且应能对处现在源程序中的错误进行处理。如果源程序有错，编的错误进行处理。如果源程序有错，编译程序应设法发现错误，把有关错误报译程序应设法发现错误，把有关错误报告给用户。这部分的工作是由专门的一告给用户。这部分的工作是由专门的一组程序（叫做处错处理程序）完程的。组程序（叫做处错处理程序）完程的。第一章 引 论1.3.5 编译前端与后端编译前端与后端 前端前端主要由与源语言有关但与目标机无主要由与源语言有关但与目标机无关的那些部分组成。通常包括词法分析、关的那些部分组成。通常包括词法分析、语法分析、语义分析与中间代码产生，语法分析、
18、语义分析与中间代码产生，有的代码优化工作，也可以包括在前端。有的代码优化工作，也可以包括在前端。后端后端包括编译程序中与目标代码有关的包括编译程序中与目标代码有关的部分，如与目标机有关的有关的优化，部分，如与目标机有关的有关的优化，和目标代码的生成等。和目标代码的生成等。第一章 引 论1.3.6 遍遍遍含义：对源语言或等价的中间语言程序从头到尾地扫描并完成规定的任务的过程分遍的相关因素源语言和目标机器的特征、编译程序的工作环境编译程序模块的软件接口从时间和空间角度看多遍编译 少占内存，多耗时间一遍编译 多占内存，少耗时间第一章 引 论1.4 编译程序与程序设计环境编译程序与程序设计环境 编译程
19、序无疑是实现高级语言的一个编译程序无疑是实现高级语言的一个最重要的工具。但支持程序设计人员进最重要的工具。但支持程序设计人员进行程序设计开发通常还需要其它一些工行程序设计开发通常还需要其它一些工具：如编辑程序、连接程序、调试程序具：如编辑程序、连接程序、调试程序等。编译程序与这些程序设计工具一起等。编译程序与这些程序设计工具一起构成所谓的构成所谓的程序设计环境程序设计环境。在一个程序设计环境中，编译程序起在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、着中心的作用。连接程序、调试程序、程序分析等工具直接依赖于编译程序所程序分析等工具直接依赖于编译程序所产生的结果，而其它工具的
20、构造也常常产生的结果，而其它工具的构造也常常要用到编译的原理、方法和技术。要用到编译的原理、方法和技术。第一章 引 论1.5 编译程序的生成编译程序的生成 以前构造编译程序大多是用机器语言以前构造编译程序大多是用机器语言或汇编语言作工具的。为了充分发挥各或汇编语言作工具的。为了充分发挥各种不同硬件系统的效率，为了满足各种种不同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然使用不同的具体要求，现在许多人仍然使用这种工具来构造编译程序（或编译程序这种工具来构造编译程序（或编译程序的核心部分）的核心部分）但是越来越多的人已经使用高级语言但是越来越多的人已经使用高级语言作工具来编译程序。因
21、为这样可以大大作工具来编译程序。因为这样可以大大节省程序设计的时间，并且构造出来的节省程序设计的时间，并且构造出来的编译程序易于阅读、维护和移植。编译程序易于阅读、维护和移植。第一章 引 论 我们还可以采用我们还可以采用“自编译方式自编译方式”产生产生编译程序。方法是，先对语言的核心部编译程序。方法是，先对语言的核心部分构造一个小小的编译程序（可用低级分构造一个小小的编译程序（可用低级语言实现），在以他为工具构造一个能语言实现），在以他为工具构造一个能够编译更多语言成分的较大编译程序。够编译更多语言成分的较大编译程序。如此扩展下去，就像滚雪球一样，越滚如此扩展下去，就像滚雪球一样，越滚越大，最后形成人们所期望的整个编译越大，最后形成人们所期望的整个编译程序。这种通过一系列的资占途径而形程序。这种通过一系列的资占途径而形成编译程序的过程叫做自编译过程。成编译程序的过程叫做自编译过程。第一章 引 论