编译原理ppt40099164

1、编译原理 Compiler Principles 彭彭 源源Email: 课件下载：课件下载： 密码：密码：bianyi课程简介课程简介u 教学方式：教学方式：理论理论(40)+实验实验(11)u 考核方式：考核方式：考试考试(70%)+平时成绩平时成绩(30%)u 课程学分：课程学分：3u 答疑答疑: 每周一中午每周一中午 信息安全实验室信息安全实验室u 参考书籍：参考书籍：p编译原理编译原理吕映芝等，清华大学出版社吕映芝等，清华大学出版社p Compiler Construction Principle and Pratice ( 编编译原理及实践译原理及实践 )， Kenneth C.L

2、ouden ， 机械工业出版社机械工业出版社pCompilers: Principles,Techniques,&Tools (编译原编译原理理 技术与工具技术与工具) ，Aho，A.V. ，人民邮电出版社，人民邮电出版社为什么要学习编译原理为什么要学习编译原理u 编译程序构造是计算机学科中一个非常成功的分支，也是最早获得成功的分支；u 编译原理蕴涵着计算机学科中解决问题的思路、抽象问题和解决问题的方法;u 编译原理课程的学习有利于加深对程序语言的理解,可以帮助你更加快速的掌握新的语言工具;u 课程中包含了很多软件技术,程序设计语言编译程序构造的基本原理和实现方法是软件的核心技术之一,

3、这对于以后从事软件设计是很有帮助的.课程要求课程要求u 上课认真听讲上课认真听讲 , 课后巩固课后巩固u 思想上重视思想上重视u 认真完成作业认真完成作业 , 保证学习时间保证学习时间第 一章 引 论本章学习内容本章学习内容内容：内容： 什么是编译程序什么是编译程序编译过程概述编译过程概述编译程序的结构编译程序的结构编译程序的构造编译程序的构造要求：要求：p 理解编译程序、解释程序和遍的概念；理解编译程序、解释程序和遍的概念；p 掌握编译过程各阶段的任务和编译程序逻辑结构掌握编译过程各阶段的任务和编译程序逻辑结构及其各部分的基本功能。及其各部分的基本功能。程序设计语言程序设计语言u 机器语言：

4、机器语言：p 能够被计算机的硬件系统直接执行的指令能够被计算机的硬件系统直接执行的指令程序。程序。p 由由二进制二进制(0、1序列序列)组成组成p 难读、难写、易出错。难读、难写、易出错。u 汇编语言：汇编语言：用用记忆符记忆符表示指令的操作表示指令的操作码。码。面向机器语面向机器语言（低级语言（低级语言）言）按机器指令的工作方式来思考问题按机器指令的工作方式来思考问题程序设计语言程序设计语言u 高级语言（面向人类的语言）：高级语言（面向人类的语言）：p 便于人类的理解和使用便于人类的理解和使用p 语言的结构符合人的思维方式：如直接使用表语言的结构符合人的思维方式：如直接使用表达式进行计算达式

5、进行计算.p 具有高抽象度：如具有高抽象度：如 类类 等机制等机制p 强调逻辑过程，事情的前因后果，不仅是做什强调逻辑过程，事情的前因后果，不仅是做什么，而且是怎么做？么，而且是怎么做？翻译程序翻译程序u 机器只能理解和执行机器语言高级语言需转换成机器只能理解和执行机器语言高级语言需转换成机器语言才能执行如何转换？机器语言才能执行如何转换？p翻译翻译p解释解释u 翻译程序：翻译程序：是指能够把某种语言的程序是指能够把某种语言的程序（源语言程（源语言程序）序）转换成另一种语言的程序转换成另一种语言的程序（目标语言程序），（目标语言程序），而后者与前者在逻辑上是等价的。而后者与前者在逻辑上是等价的

6、。u 编译程序：编译程序：源语言程序为高级语言程序，目标语言源语言程序为高级语言程序，目标语言程序是低级语言程序的翻译程序。程序是低级语言程序的翻译程序。u 汇编程序：汇编程序：源语言程序为汇编语言程序，目标语言源语言程序为汇编语言程序，目标语言程序为机器语言程序的翻译程序。程序为机器语言程序的翻译程序。如何执行一个源程序如何执行一个源程序u 先编译后执行先编译后执行-编译程序编译程序编译出目标程序，编译出目标程序，系统执行。系统执行。目标机目标机宿主机宿主机编译程序编译程序运行系统运行系统目标程序目标程序P输入数据输入数据计算结果计算结果源程序源程序P交叉编译程序：交叉编译程序：宿主机和目标

7、机的指令系统不同宿主机和目标机的指令系统不同诊断编译程序诊断编译程序：侧重于帮助程序开发和调试侧重于帮助程序开发和调试优化编译程序：优化编译程序：着重于提高目标代码的效率着重于提高目标代码的效率运行编译程序的计算机运行编译程序的计算机运行产生的目标代码的计算机运行产生的目标代码的计算机如何执行一个源程序如何执行一个源程序u 边解释边执行边解释边执行-解释程序解释程序边解释边执行源程边解释边执行源程序本身，不产生目标程序。序本身，不产生目标程序。解释程序解释程序源程序源程序输入数据输入数据计算结果计算结果编译过程编译的过程与自然语言间的翻译过程有相似之处：编译的过程与自然语言间的翻译过程有相似之

8、处：1.识别出每个单词（含义，性识别出每个单词（含义，性质等）质等）2.分析语法结构分析语法结构3.初步翻译句子的含义，得到初步翻译句子的含义，得到草稿草稿4.译文修饰译文修饰5.写出最后译文写出最后译文1.词法分析词法分析2.语法分析语法分析3.语义分析中间代码生成语义分析中间代码生成4.优化优化5.目标代码生成目标代码生成英文翻译成中文英文翻译成中文编译过程编译过程词法分析词法分析(线性分析)u 输入源程序，对构成源程序的字符串进行扫描和分解，依据词法规则(或构词规则)识别出一个个的单词(基本字、标识符、常数、运算符、基本字、标识符、常数、运算符、界限符界限符) 。u 描述词法规则的有效工

9、具是描述词法规则的有效工具是正规式正规式和和有限自有限自动机动机例：源程序 for I:=1 to 100 do经词法分析被分析成一个个的单词经词法分析被分析成一个个的单词基本字for 标识符I赋值符:=整常数1基本字to整常数100基本字do语法分析语法分析（层次分析）（层次分析）u 在词法分析的基础上，根据语言的在词法分析的基础上，根据语言的语法规则语法规则(文法规则）文法规则），把单词符号组成各类，把单词符号组成各类语法单位语法单位（语法范畴语法范畴），如），如“短语短语”、 “子句子句”、 “句子句子”、“程序段程序段” 、“程序程序” 等。等。u 通过语法分析，确定整个输入串是否构成

10、通过语法分析，确定整个输入串是否构成语语法上正确的法上正确的“程序程序”。position := initial + rate * 60 语法规则 “:=” “+” “*” “(”“)” 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*position:=initial+rate*60语法分析表达式表达式position:=initial+rate*60:=+N 60*id1 Positionid2 initialid3 rate语义分析语义分析u 对各种语法范畴进行静态语义检查对各种语法范畴进行静态语义检查p 上下文相关性上下文相关性p 类型匹配类型匹配p 类型转换类型转

11、换依据：语义规则。依据：语义规则。使用使用属性文法属性文法描述描述例:int p();double rate;position := initial + rate * 60 /* error */ /* error */ /* warning */ position := initial + rate * 6060:=+*Id1 positionId2 initialId3 rateInttoreal中间代码生成中间代码生成p 将源程序翻译成中间代码。将源程序翻译成中间代码。 所谓所谓“中间代码中间代码”是一种不依赖于机器，含是一种不依赖于机器，含义明确，便于处理的记号系统。如义明确，便于处理

12、的记号系统。如“四元式四元式”，其形式如下：其形式如下：算符算符左操作数左操作数右操作数右操作数结果结果id1:= id2 + id3 * 60(1) (inttoreal 60-t1)(2) (* id3t1t2)(3) (+ id2t2t3)(4) (:= t3-id1)60:=+*Id1 positionId2 initialId3 rateInttoreal中间代码生成中间代码生成例：例：Z=(X+0.418)*Y/W序号算符 左操作数右操作数结果(1)+X0.418T1(2)*T1YT2(3)/T2WZ 常用的中间代码出了四元式外，还有三常用的中间代码出了四元式外，还有三元式、间接三

13、元式和逆波兰记号等等。元式、间接三元式和逆波兰记号等等。1.2.4 优化优化任务：任务： 对前段产生的中间代码进行加工，以期对前段产生的中间代码进行加工，以期在最后阶段产生更为高效（省在最后阶段产生更为高效（省时间时间和和空间空间）的代码的代码依据：依据： 程序的程序的等价变换规则等价变换规则。其方法有：。其方法有：公共子表公共子表达式的提取达式的提取、循环优化循环优化、删除无用代码、并删除无用代码、并行化处理行化处理等。等。id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3 t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变

14、换变换 （1） ( *id360.0 t1) ( 2）（ + id2 t1id1)1.2.5 目标代码生成目标代码生成任务：任务： 把中间代码（或经优化处理后）变换成把中间代码（或经优化处理后）变换成特定机器上的特定机器上的低级语言代码低级语言代码（一般是（一般是机器机器代代码或码或汇编汇编代码，称为代码，称为目标代码目标代码）。它有赖于）。它有赖于硬件系统结构和机器指令含义。硬件系统结构和机器指令含义。目标代码的形式：目标代码的形式：p 绝对指令代码绝对指令代码-可以放在内存的固定地方并且立可以放在内存的固定地方并且立即执行即执行 p 可重定位的指令代码可重定位的指令代码-连接装配程序连接各

15、目标连接装配程序连接各目标模块，确定程序变量在内存中的位置，装入内存模块，确定程序变量在内存中的位置，装入内存中指定的起始地址，变成绝对指令代码程序。中指定的起始地址，变成绝对指令代码程序。p 汇编指令代码汇编指令代码-通过汇编器汇编后执行通过汇编器汇编后执行(*,id3 60.0 t1)(+,id2 t1id1 )movfid3, R2mulf #60.0, R2movfid2, R1addf R2, R1 movfR1, id1编译程序的结构编译程序的结构语义语义分析分析与中与中间代间代码生码生成器成器词词法法分分析析器器语语法法分分析析器器优优化化器器目目标标代代码码生生成成器器表格管理

16、错误处理编译程序的结构编译程序的结构源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码表格与表格管理表格与表格管理作用：作用： 登记登记源程序的各类信息源程序的各类信息和和编译各阶段的进编译各阶段的进展情况展情况。 最重要的是最重要的是符号表，符号表，它用来登记源程序中它用来登记源程序中出现的每一个名字以及名字的各种属性（类出现的每一个名字以及名字的各种属性（类型、作用域、分配存储信息等）型、作用域、分配存储信息等）如：Const1常量 值：35Var1变量 类型：实 层次：2出错处理出错处理u 错误可发生在编译的各个阶段，错误处理也是贯穿错误可发生在

17、编译的各个阶段，错误处理也是贯穿编译全过程。编译全过程。u 编译程序应设法发现源程序的错误，把有关错误报编译程序应设法发现源程序的错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫告给用户。这部分的工作是由专门的一组程序（叫做做出错处理程序出错处理程序）完成的。）完成的。错误的类型：错误的类型：p语法错误：语法错误：指源程序中不合语法（或词法）规则的错误。指源程序中不合语法（或词法）规则的错误。如：非法字符。如：非法字符。p语义错误：语义错误：指不合语义规则的错误，如：说明错误、作用指不合语义规则的错误，如：说明错误、作用域错误、类型不一致等。有些在语义分析时检测出来，有域错误、类

18、型不一致等。有些在语义分析时检测出来，有些要在运行的时候才能检测出来些要在运行的时候才能检测出来遍遍(Pass)遍：遍：对源程序对源程序(或其中间形式或其中间形式)从头至尾扫描一次并从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标进行有关加工处理，生成新的中间形式或最终目标程序，称为程序，称为一遍一遍。 即可将几个不同阶段合为一遍，也可以把各个即可将几个不同阶段合为一遍，也可以把各个阶段的工作分成若干遍。阶段的工作分成若干遍。分遍的原则：分遍的原则： 目标质量高低，机器内存大小，源语言简繁等。目标质量高低，机器内存大小，源语言简繁等。编译前端与后端编译前端与后端从概念上划分：从概念上划分： 编译程序可分为编译程序可分为编译前端编译前端和和编译后端编译后端。p 编译前端：编译前端：指与源语言有关但与目标机无关的编指与源语言有关但与目标机无关的编译程序部分。包括词法分析、语法分析、语义分译程序部分。包括词法分析、语法分析、语义分析、中间代码产生和部分优化。析、中间代码产生和部分优化。p 编译后端：编译后端：指与目标机有关的编译程序部分。包指与目标机有关的编译程序部分。包括与代目标机有关的代码优化和目标代码生成等。括与代目标机有关的代码优化和目标代码生成等。一般后端只依赖于中间语言。一般后端只依赖于中间语言。1.4 编译程序与程序设计环境编译程序与程