编译原理讲义优秀课件.ppt
编译原理讲义第1页，本讲稿共19页第一章绪论4程序设计语言分低级语言和高级语言两类4低级语言:机器语言、汇编语言及其它面向机器的程序设计语言；其特点对计算机的依赖性强、直观性差、编写程序的工作量大，对程序设计人员要求较高。4高级语言：有几百种之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等，高级语言在算法描述能力、编写和调试效率上均比低级语言优越。4但高级语言与机器之间有一“鸿沟”：机器不能理解高级语言！4因此，要在计算机上实现高级语言，需使该语言能让计算机所理解。4方法：对程序进行翻译或进行解释。4翻译：在计算机中放置一能由计算机直接执行的翻译程序，它将某程序设计语言（源语言）所编写的程序（源程序）作为加工对象，将其翻译成为与之等价的另一种语言（目标语言）的程序（目标程序）4可见，计算机执行某高级语言程序，需经两个阶段，即编译阶段和运行阶段。4在执行时，一般应有一些辅助子程序配合。如：数据格式转换子程序、标准函数、动态存储分配子程序等等，由它们构成的子程序库称为运行系统。4编译系统=编译程序+运行系统第2页，本讲稿共19页计算机执行高级语言程序的步骤计算机执行高级语言程序的步骤源程序P目标程序P运行结果S编译程序数据运行程序计算机A计算机B编译阶段运行阶段第3页，本讲稿共19页编译程序与解释程序44高级语言程序高级语言程序高级语言程序高级语言程序也可通过解释程序解释程序来执行44解释程序解释程序：以源程序为输入，在执行过程中不再产生目标程序，而是边解释边执行。44解释程序解释程序运行效率不高4目前，纯粹的解释程序解释程序已不多见，通常是将编译和解释作某种程度的结合。44编译程序编译程序是现今任何计算机系统的最重要的系统程序。4本课程的目的，在于向大家介绍设计和构造编译程序的基本原理和基本方法，其中许多方法也适用于构造解释程序或汇编程序。第4页，本讲稿共19页1.1编译过程概述编译过程概述4翻译外文书刊与编译工作比较第5页，本讲稿共19页编译程序的构成4编译程序主要由八个部分构成：1.词法分析词法分析程序（扫描器 scanner）2.语法分析语法分析程序（分析器 parser）3.语义分析语义分析程序4.中间代码生成中间代码生成程序5.代码优化代码优化程序6.目标代码生成目标代码生成程序7.错误检查和处理错误检查和处理程序8.各种信息表格的管理各种信息表格的管理程序第6页，本讲稿共19页1.2 编译程序的逻辑结构词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查和处理程序源程序目标代码第7页，本讲稿共19页一个微型PASCAL语言的定义4为了便于说明，我们引入一个微型PASCAL语言（PASCAL/M）的定义。它只有如下四种语句：1）PROGRAM语句；2）说明语句；3）BEGIN-END语句；4）赋值语句；4每个PASCAL/M语句语句都以PROGRAM语句开头，后跟说明语句，再跟以一个BEGIN-END语句，在其内部可以有若干赋值语句。4右边是一个该语言程序的例子。程序1-1 一个PASCAL源程序sourcePROGRAM source;This little source program is used to illustrate compiling procedure VAR x,y,z:integer;a:integer;BEGIN This program has only 4 statement x:=23+5;z:=x DIV-3;y:=z+18*3;a:=x+(y-2)DIV 4;END.第8页，本讲稿共19页1.2.1 词法分析程序（扫描器）4词法分析程序的任务是：1）识别出源程序的各个基本语法单位（单词或语法符号）2）删除无用的空白字符及其它与输入介质相关的非实质性字符（空格、回车等）3）删除注释4）进行词法检查，报告所发现的错误4扫描器依次查看缓冲区中源程序的各字符，根据当前正查看的字符之种类，并参考扫描过程中已得到的信息，就能判断出该字符在源程序中所处地位。一般它是下述几种情况之一：1）正处理的注释中的一个字符；2）无用字符；3）下一个单词的首字符；4）正识别的单词中的一个字符；5）不合法的字符。4扫描器输出以单词为单位的单词流4例如，以特殊符号“#”分隔的单词流：#PROGRAM#source#;#VAR#x#,#y#,#z#:#integer#;#a#:#integer#;#BEGIN#x#:=#23#+#5#;#z#:=#x#DIV#-#3#;#y#:=#z#+#18#*#3#;#a#:=#x#+#(#y#-#2#)#DIV#4#;#END#.#第9页，本讲稿共19页单词流的内部表示4注意，前面的单词流形式只是我们为说明原理便于阅读而假定的形式。4为了让计算机能够方便地识别和使用，在实际中的常用方法是将单词计算机内部表示为一个有序对(Class,Value)。4Class为一整型数，用于标识该单词的类别；4Value用于存放单词的值。4例如对于source程序，可将其单词分为四类：（1）保留字（2）专用符号（3）标识符（4）整数。这样，source程序相应的单词流为：(1,PAROGRAM)(3,source)(2,;)(1,VAR)(.)(2,;)(1,END)(2,.)第10页，本讲稿共19页1.2.2 语法分析程序（分析器）44语法分析程序语法分析程序以词法分析程序输出的单词流为输入，分析源程序的结构，判断它是否为相应程序设计语言的合法程序。44方法方法：试图为源程序构造一个语法树。4分析工作是在相应程序设计语言的语法规则指导下进行的。语法规则描述了该语言的各种语成份的组成结构。4所谓语法树语法树只是逻辑概念上的，并不是在机器内真要存储一个树形结构。第11页，本讲稿共19页1.2.3 语义分析程序4一程序设计语言具有语法和语义两个特征。4语法特征描述各成份的形式或结构；4语义特征描述各语法成份的含义与功能，即规定它们的属性或在执行应进行的运算或操作。4因此，只有进行了语义分析语义分析，才能让计算机知道，应进行何操作或运算。4在进行语义分析语义分析时还应进行相应的语义检查（类型匹配、矛盾说明、参数匹配等）。4语义处理尚无公认的方法来系统地描述。当前较通用的方法是半机械化的“语法制导翻译语法制导翻译”方法。第12页，本讲稿共19页1.2.4 中间代码生成4为了处理方便和便于代码优化，在语义分析后通常并不直接产生目标代码，而是生成介于二者之间的中中间代码间代码。4常见的有：逆波兰式、三元式、四元式及树形结构等。4例如，sourcesource程序中的第四条赋值语句相应的逆波兰式可写成：a x y 2-a x y 2-div+:=div+:=44sourcesource程序相应的四元式表示为：(prologue,source)(add,23,5,T)(store,T,x)(div,x,-3,T)(store,T,z)(mult,18,3,T)(add,z,T,T)(store,T,y)(sub,y,2,T)(div,T,4,T)(add,x,T,T)(store,T,a)(epilogue)第13页，本讲稿共19页1.2.5 代码优化程序44代码优化代码优化的目的是生成质量较高的目标代码4衡量质量的标准：空间指标和时间指标4优化方法分类：与机器有关和无关两类4优化指标有时是相互矛盾的，应根据具体情况进行取舍和侧重44sourcesource程序优化后结果：(prologue,source)(store,28,x)(div,x,-3,T)(store,T,z)(add,z,54,T)(store,T,y)(sub,y,2,T)(div,T,4,T)(add,x,T,T)(store,T,a)(epilogue)第14页，本讲稿共19页1.2.6 目标代码生成程序4任务：将中间代码翻译成为目标程序4首先确定源语言各种语法成份的目标代码结构目标代码结构；4再根据需要制定中间代码到目标代码的翻译策略翻译策略4这部分程序对具体机器的依赖性很强，需具体情况具体分析4通常，目标代码的三种形式：（1）具有绝对地址绝对地址的机器指机器指令代码令代码；（2）汇编语言汇编语言形式的目标程序；（3）模块结构模块结构的机器指令（浮动地址）。44SourceSource程序对应的8038680386汇编程序见书中P9P9第15页，本讲稿共19页1.2.7 错误检查和处理程序4程序中出现错误是难免的。一完善的编译程序应具有很强的查错能力，并能准确地报告源程序中错误的种类及位置。4除报错外，编译程序还可生成一些另外的注释信息，它有助于程序设计人员调试程序。4常见的辅助手段根据请求输出“对照图”和各变量的值。44SourceSource程序的对照图，见P10P10表1-21-2第16页，本讲稿共19页1.2.8 信息表管理程序4编译过程中，需经常收集、记录或查询程序中所出现的各种量的有关属性属性属性属性（信息）。4为此，编译程序需要建立一批不同用途的表格表格表格表格（常数表、变量表、关键字表等）4除此之外，根据不同的分析方法，编译程序还保持一些专用的表格（LL分析表、LR分析表、状态矩阵等）4合理地组织各种表格，恰当地选用相应的造表和查表算法是提高编译程序工作效率的有效途径第17页，本讲稿共19页1.3 编译程序的组织语法分析程序语义分析及代码生成程序词法分析程序整理目标程序源程序目标程序停机开始第18页，本讲稿共19页本章内容结束第19页，本讲稿共19页
