编译原理第一章ppt.ppt

1、编译原理,程序设计语言,第一章 引论,1.1 什么叫编译程序 1.2 编译过程概述 1.3 编译程序的结构 1.4 编译程序与程序设计环境（略） 1.5 编译程序的生成,1. 什么是编译程序？,1.1 什么叫编译程序,翻译程序：一种语言程序-另一种语言程序,源语言,目标语言,编译程序：高级语言程序-低级语言程序,汇编程序：汇编语言程序-机器语言程序,解释程序：源语言程序-边解释边执行,（1）编译方式：先编译后执行。,（2）解释方式：以源程序作为输入，但不产生目标代码，而 是边解释边执行源程序本身。,2.“高级语言程序”的执行方式,1.1 什么叫编译程序,编译和解释的主要区别：,是否产生目标代码

2、！,说明：很多语言处理系统组合了编译和解释两个程序 源程序先被翻译为一种中间表示形式的程序，再接受输入数据并对源程序进行解释而生成输出结果。 通常我们还是将其称为一个语言编译系统。 例如Java语言的处理系统就包括编译和解释两部分。,2.“高级语言程序”的执行方式,一个混合的语言处理系统,3.,“编译程序”在计算机系统中的位置较接近于“硬件”,1.1 什么叫编译程序,4.发展,20世纪50年代 第一个编译程序 FORTRAN编译程序,目前：编译原理与技术得到迅速发展，现已形成一套比较成熟的系统化的理论与方法，并开发出了一些好的编译程序的实现语言、环境与工具。,当时普遍认为设计和实现编译程序是一

3、件十分困难、令人生畏的事情,1.1 什么叫编译程序,编译技术是计算机科学中发展最迅速、最成熟的一个重要分支，集中体现了计算机科学发展的重要成果与精华。 通过本课程的学习，一方面要理解、掌握编译系统的结构、工作流程以及编译程序各组成部分的设计原理和实现技术；另一面，通过学习编译的理论和方法，提高对程序设计语言、操作系统、计算机原理和体系结构等课程知识的综合理解。,1.2 编译过程概述,The elephant ate an banana.,什么是语言？,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end,一.类比

4、自然语言翻译和编译过程,英汉 编译的工作过程 1)识别单词词法分析 2)分析句子语法结构语法分析 3)根据句子含义初步翻译语义分析与中间代码产生 4)修饰译文优化 5)写出最后译文目标代码生成,1.2 编译过程概述,1.词法分析,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end,基本字 for 标识符 K 赋值号 := 常数 1 基本字 to 常数 100 基本字 do 基本字 begin . .,1.2 编译过程概述,词法分析 ,规则： 规则描述工具： 任务：,依循词法规则.,正规式和有限自动机（FA）.,

5、输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号，如基本字、标识符、常数、算符、界符等。,1.2 编译过程概述,2. 语法分析,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end,规则： 规则描述工具： 任务：,依循语法规则.,上下文无关文法.,在词法分析的基础上，根据语言的语法规则，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。,1.2 编译过程概述,2 语法分析,3.语义分析和中间代码产生,规则： 规则描述工具： 任务：,语义规则,属性文法,

6、两部分工作： 1.对每种语法范畴进行静态语义检查; 2.若语义正确，则进行中间代码翻译.,对语法分析器识别出的各类语法单位，分析其含义并进行初步翻译（产生中间代码）。,中间代码：一种独立于具体硬件的记号系统，更接近于机器代码,1.2 编译过程概述,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end；,K:=1 L1:if 100K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1 L2:,语义分析后产生的中间代码：,三地址代码,具体实现：三元式，四

7、元式，间接三元式,1.2 编译过程概述,K:=1 L1:if 100K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1 L2:,四元式序列：,1.2 编译过程概述,任务：对中间代码进行加工变换，以期在最后阶段 能产生出更为高效（省时间和空间）的目标 代码。,4.优化,包括：公共子表达式的提取、循环优化、删除无用代码等,1.2 编译过程概述,优化前,优化后,1.2 编译过程概述,任务：把中间代码变换成特定机器上的低级语言代码， 实现最后的翻译。,5.目标代码生成,绝对指令代码/可重定位的指令代码/汇编指令代码,有赖于硬件系统结构和

8、机器指令含义,1.2 编译过程概述,1.3 编译程序的结构,一.编译程序总框图,1.表格管理 编译各阶段都要涉及到构造、查找或 更新有关表格 。,表格的作用： 登记源程序的各类信息和编译各阶段的进展状况。 种类：符号名表、常数表、标号表、入口名表、过程引用表 符号表： 用来登记源程序中出现的每个名字以及名字的各种属性。,1.3 编译程序的结构,2.出错处理 每一阶段都可能检测出错误，绝大多 数错误可在前三阶段检测出来 .,任务：设法发现错误，并把有关错误信息报告给用户.,语法错误：源程序中不符合语法/词法规则的错误。词法/语法分析时检测 语义错误：源程序中不符合语义规则的错误。 语义分析/运行

9、时检测出来 举例：语法错误 单词拼写错误、括号不匹配 语义错误 说明错误、作用域错误、类型不匹配,1.3 编译程序的结构,二.遍,1.编译过程的划分： 上述划分的五个阶段仅仅是逻辑功能上的一种划分,2.遍（Pass） 对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。,具体实现时，受各方面（如源语言、设计要求等）限制，往往组织成若干遍,1.3 编译程序的结构,3.注意： 既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍 例如： 词法分析+语法分析一遍 语法分析+语义分析与中间代码产生一遍 优化 若干遍,根据系统资源的状况、运行目标的要求等

10、，可以将一个编译程序设计形成多遍扫描的形式，在每一遍扫描中完成不同的任务。,1.3 编译程序的结构,当一遍中包含若干阶段时，各阶段的工作是穿插进行的 。,例如：,识别出一个语法单位时,1.3 编译程序的结构,三.编译前端与后端,1、前端： 由与源语言有关但与目标机无关的那些部分组成 包括词法分析、语法分析、语义分析与中间代码 产生、部分代码优化工作,2、后端： 包括编译程序中与目标机有关的那些部分，如与 目标机有关的代码优化和目标代码生成等。,不依赖于源语言而仅仅依赖于中间语言,1.3 编译程序的结构,1.5 编译程序的生成,一. 设计目标,目标程序小，执行速度快 编译程序小，执行速度快 诊断

11、能力强，可靠性强 可移植性，可扩充性,如何实现编译器？,直接用可运行 的代码编制,太费力！,1.5 编译程序的生成,以汇编语言或机器语言为工具 优点: 可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。 缺点: 程序难读、难写、易出错、难维护、生产的效率低。,五.编译程序生成,高级语言书写,优点: 程序易读、易理解、容易维护、生产的效率高。 缺点: 难以充分发挥计算机的系统功能，生成的程序效率低。,1.5 编译程序的生成,2、问题,（1）历史上第一个高级语言的编译程序是怎样构造的？ -自编译技术（自展技术） （2）已有A机器上的L1语言（如：C语言）的编译程序，如何构造A机器上的

12、L2语言（如：PASCAL语言）的编译程序？ （3）已有A机器上的L语言的编译程序，如何构造B机器上的L语言的编译程序？ -交叉编译 /移植,源语言,编译程序实现语言,目标语言,一般采用基于T形图的方式：,表现语言翻译的T形图,1.5 编译程序的生成,高级语言书写 利用已有的某种语言的编译程序实现另一语言的编译程序。,同一台机器 不同的语言,1.5 编译程序的生成,移植方法 把一种机器上的编译程序移植到另一种机器上。,同一种语言不同的机器,1.5 编译程序的生成,L1+L2+.+Ln,L1+L2,自展技术,L1,1.5 编译程序的生成,编译程序自动产生 编译程序-编译程序，编译程序书写系统,编译程序 自动产生器,1.5 编译程序的生成,编译程序-编译程序，编译程序书写系统,LEX 词法分析程序产生器 YACC 语法分析程序产生器 ANTLR LL(K)文法的语法分析器生成器 BISON 语法分析程序产生器,1.5 编译程序的生成,1.5 编译程序的生成,三.如何学习构造编译程序,要在某一台机器上为某种语言构造一个编译程序，必须掌握以下内容：,源语言：对被编译的源语言，要深刻理解其结构（语法）和 含义（语义）。