编译原理(西北工业大学)第1节课第一章.ppt

1 蒋立源、康慕宁.编译原理.西北工业大学出版社。 2 （美）Kenneth C.Louden著，冯博琴，冯岚等译。编译原理及实践.机械工业出版社 3 金成植.编译程序构造原理和实现技术.高等教育出版社，2000. 4 张幸儿.编译原理 编译程序构造与实践.机械工业出版社，2008. 5 陈火旺等.程序设计语言编译原理.国防工业出版社，2000.,网站资源： 1 /gjpxw/thujsj/009/ 清华同方编译原理在线学习网站 2/f?kw=%B1%E0%D2%EB%D4%AD%C0%ED 编译原理百度贴吧 3/jp2005/20/kcwz/wlkc/wlkc.html 西北工业大学编译原理网络课程 4/byyl/index.php?type=kczy 国防科技大学编译原理网络课程,第一章 绪论,1.1 编译过程概述 1.2 编译程序的逻辑结构 1.3 编译程序的组织,第一章 绪论,程序设计语言分低级语言和高级语言两类。 低级语言:机器语言、汇编语言及其它面向机器的程序设计语言；其特点为对计算机的依赖性强、直观性差、编写程序的工作量大，对程序设计人员要求较高。 高级语言：有几百种之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等，高级语言在算法描述能力、编写和调试效率上均比低级语言优越。,但高级语言与机器之间有一“鸿沟”：机器不能理解高级语言！ 因此，要在计算机上实现高级语言，需使该语言能让计算机所理解。 方法：对程序进行翻译或进行解释。 翻译：在计算机中放置一能由计算机直接执行的翻译程序，它将某程序设计语言（源语言）所编写的程序（源程序）作为加工对象，将其翻译成为与之等价的另一种语言（目标语言）的程序（目标程序）。,按编译方式执行一个高级语言程序的主要步骤,可见，计算机执行某高级语言程序，需经两个阶段，即编译阶段和运行阶段。 在执行时，一般应有一些辅助子程序配合。 如：数据格式转换子程序、标准函数、动态存储分配子程序等等，由它们构成的子程序库称为运行系统。 编译系统=编译程序+运行系统,编译程序与解释程序,高级语言程序也可通过解释程序来执行。 解释程序：以源程序为输入，在执行过程中不再产生目标程序，而是边解释边执行。 解释程序运行效率不高。 目前，纯粹的解释程序已不多见，通常是将编译和解释作某种程度的结合。,本课程的目的,编译程序是现今任何计算机系统的最重要的系统程序。 本课程的目的，在于向大家介绍设计和构造编译程序的基本原理和基本方法，其中许多方法也适用于构造解释程序或汇编程序。,1.1 编译过程概述,翻译外文书刊与编译工作比较,编译程序的构成,编译程序主要由八个部分构成： 1.词法分析程序（扫描器 scanner） 2.语法分析程序（分析器 parser） 3.语义分析程序 4.中间代码生成程序 5.代码优化程序 6.目标代码生成程序 7.错误检查和处理程序 8.各种信息表格的管理程序,1.2 编译程序的逻辑结构,一个微型PASCAL语言的定义,为了便于说明，引入一个微型PASCAL语言（PASCAL/M）的定义。它只有如下四种语句： 1）PROGRAM语句； 2）说明语句； 3）BEGIN-END语句； 4）赋值语句； 每个PASCAL/M语句都以PROGRAM语句开头，后跟说明语句，再跟以一个BEGIN-END语句，在其内部可以有若干赋值语句。,程序1-1 一个PASCAL源程序source PROGRAM 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.,1.2.1 词法分析程序（扫描器）,词法分析程序的任务是： 1）识别出源程序的各个基本语法单位（单词或语法符号）； 2）删除无用的空白字符及其它与输入介质相关的非实质性字符（空格、回车等）； 3）删除注释； 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 # . #,单词流的内部表示,注意，前面的单词流形式只是我们为说明原理便于阅读而假定的形式。 为了让计算机能够方便地识别和使用，在实际中的常用方法是将单词计算机内部表示为一个有序对( Class, Value )。 Class为一整型数，用于标识该单词的类别； Value用于存放单词的值。,单词流的内部表示,例如对于source程序，可将其单词分为四类： (1) 保留字 (2) 专用符号 (3) 标识符 (4) 整数 这样，source程序相应的单词流为： ( 1 , PAROGRAM ) ( 3 , source ) ( 2 , ;) ( 1 , VAR ) (.) ( 2 , ; ) ( 1 , END ) ( 2 , . ),图3-1 文法G的状态转换图,(a) M的状态矩阵 (b) M的状态转换图,1.2.2 语法分析程序（分析器）,语法分析程序以词法分析程序输出的单词流为输入，分析源程序的结构，判断它是否为相应程序设计语言的合法程序。 方法：试图为源程序构造一个语法树。 分析工作是在相应程序设计语言的语法规则指导下进行的。语法规则描述了该语言的各种语法成份的组成结构。 所谓语法树只是逻辑概念上的，并不是在机器内真要存储一个树形结构。,图2-3 复合if语句的两棵不同的语法树,(a)句子 i+i*i 的语法树 (b)句型 F+i*i 的语法树,(c)句子F+F*F的语法树 (d)句型F+T的语法树,图5-13 识别GS全部可归前缀的DFA,1.2.3 语义分析程序,程序设计语言具有语法和语义两个特征。 语法特征描述各成份的形式或结构； 语义特征描述各语法成份的含义与功能，即规定它们的属性或在执行时应进行的运算或操作。 因此，只有进行了语义分析，才能让计算机知道，应进行何操作或运算。,1.2.4 中间代码生成,常见的中间代码有：逆波兰式、三元式、四元式及树形结构等。 例如，与source程序中的第四条赋值语句相应的逆波兰式可写成： a x y 2 - div + := 与source程序相应的四元式表示为：,(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),赋值语句x:=a+b*c的 语法制导翻译过程,1.2.5 代码优化程序,代码优化的目的是生成质量较高的目标代码。 衡量质量的标准：空间指标和时间指标。 优化方法分类：与机器有关和无关两类。 优化指标有时是相互矛盾的，应根据具体情况进行取舍和侧重。 source程序优化后结果：,(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),(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),1.2.6 目标代码生成程序,任务：将中间代码翻译成为目标程序。 首先确定源语言各种语法成份的目标代码结构； 再根据需要制定中间代码到目标代码的翻译策略。 这部分程序对具体机器的依赖性很强，需具体情况具体分析。,1.2.6 目标代码生成程序,通常，目标代码的三种形式： （1）具有绝对地址的机器指令代码； （2）汇编语言形式的目标程序； （3）模块结构的机器指令（浮动地址）。 Source对应的80386汇编程序见书中P9,1.2.7 错误检查和处理程序,程序中出现错误是难免的。一完善的编译程序应具有很强的查错能力，并能准确地报告源程序中错误的种类及位置。 除报错外，编译程序还可生成一些另外的注释信息，它有助于程序设计人员调试程序。 常见的辅助手段根据请求输出“对照图”和各变量的值。 Source程序的对照图，见P10表1-2,1.2.8 信息表管理程序,编译过程中，需经常收集、记录或查询程序中所出现的各种量的有关属性（信息）。 为此，编译程序需要建立一批不同用途的表格（常数表、变量表、关键字表等）。 除此之外，根据不同的分析方法，编译程序还保持一些专用的表格（LL分析表、LR分析表、状态矩阵等）。 合理地组织各种表格，恰当地选用相应的造表和查表算法是提高编译程序工作效率的有效途径。,状态转换矩阵,FIRST集和FOLLOW集,LL(1)分析表,L R (1) 分 析 表,图6-10 数组的内情向量,内情向量,符号表,1.3 编译程序的组织,需要注意的是，前面所说的各部分之间的关系，是指它们之间的逻辑关系，而不一定是执行时间上的先后顺序。 事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖于编译过程中对源程序扫描的遍数，以及如何划分各遍扫描