程序设计语言编译原理第三版第1章.ppt
编译原理,于静洋,程序设计语言,第一章 引论,1.1 什么叫编译程序1.2 编译过程概述1.3 编译程序的结构1.4 编译程序与程序设计环境（略）1.5 编译程序的生成,1.什么是编译程序？,1.1 什么叫编译程序,翻译程序：一种语言程序-另一种语言程序,源语言,目标语言,编译程序：高级语言程序-低级语言程序,汇编程序：汇编语言程序-机器语言程序,解释程序：源语言程序-边解释边执行,（1）编译方式：先编译后执行。,（2）解释方式：以源程序作为输入，但不产生目标代码，而 是边解释边执行源程序本身。,2.“高级语言程序”的执行方式,1.1 什么叫编译程序,编译和解释的主要区别：,是否产生目标代码！,3.,“编译程序”在计算机系统中的位置较接近于“硬件”,1.1 什么叫编译程序,4.发展,20世纪50年代 第一个编译程序 FORTRAN编译程序,目前：编译原理与技术得到迅速发展，现已形成一套比较成熟的系统化的理论与方法，并开发出了一些好的编译程序的实现语言、环境与工具。,当时普遍认为设计和实现编译程序是一件十分困难、令人生畏的事情,1.1 什么叫编译程序,1.2 编译过程概述,The elephant ate an banana.,什么是语言？,for K:=1 to 100 dobeginM:=I+10*K;N:=J+10*Kend,一.类比自然语言翻译和编译过程,英汉 编译的工作过程1)识别单词词法分析2)分析句子语法结构语法分析3)根据句子含义初步翻译语义分析与中间代码产生4)修饰译文优化5)写出最后译文目标代码生成,1.2 编译过程概述,1.词法分析,for K:=1 to 100 dobeginM:=I+10*K;N:=J+10*Kend,基本字 for 标识符 K 赋值号:=常数 1 基本字 to 常数 100 基本字 do 基本字 begin.,1.2 编译过程概述,词法分析,规则：规则描述工具：任务：,依循词法规则.,正规式和有限自动机（FA）.,输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号，如基本字、标识符、常数、算符、界符等。,1.2 编译过程概述,2.语法分析,for K:=1 to 100 dobeginM:=I+10*K;N:=J+10*Kend,规则：规则描述工具：任务：,依循语法规则.,上下文无关文法.,在词法分析的基础上，根据语言的语法规则，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。,1.2 编译过程概述,3.语义分析和中间代码产生,规则：规则描述工具：任务：,语义规则,属性文法,两部分工作：1.对每种语法范畴进行静态语义检查;2.若语义正确，则进行中间代码翻译.,对语法分析器识别出的各类语法单位，分析其含义并进行初步翻译（产生中间代码）。,中间代码：一种独立于具体硬件的记号系统，更接近于机器代码,1.2 编译过程概述,for K:=1 to 100 do begin M:=I+10*K;N:=J+10*K end；,K:=1L1:if 100K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1L2:,语义分析后产生的中间代码：,三地址代码,具体实现：三元式，四元式，间接三元式,1.2 编译过程概述,K:=1L1:if 100K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1L2:,四元式序列：,1.2 编译过程概述,任务：对中间代码进行加工变换，以期在最后阶段能产生出 更为高效（省时间和空间）的目标代码。,4.优化,包括：公共子表达式的提取、循环优化、删除无用代码等,1.2 编译过程概述,优化前,优化后,1.2 编译过程概述,任务：把中间代码变换成特定机器上的低级语言代码，实现最后的翻译。,5.目标代码生成,绝对指令代码/可重定位的指令代码/汇编指令代码,有赖于硬件系统结构和机器指令含义,1.2 编译过程概述,1.3 编译程序的结构,一.编译程序总框图,1.表格管理 编译各阶段都要涉及到构造、查找或 更新有关表格。,表格的作用：登记源程序的各类信息和编译各阶段的进展状况。符号表：用来登记源程序中出现的每个名字以及名字的各种属性。,1.3 编译程序的结构,2.出错处理 每一阶段都可能检测出错误，绝大多 数错误可在前三阶段检测出来.,任务：设法发现错误，并把有关错误信息报告给用户.,语法错误：源程序中不符合语法/词法规则的错误。词法/语法分析时检测语义错误：源程序中不符合语义规则的错误。语义分析/运行时检测出来,1.3 编译程序的结构,二.遍,1.编译过程的划分：上述划分的五个阶段仅仅是逻辑功能上的一种划分,2.遍（Pass）对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。,具体实现时，受各方面（如源语言、设计要求等）限制，往往组织成若干遍,1.3 编译程序的结构,3.注意：既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍例如：词法分析+语法分析一遍语法分析+语义分析与中间代码产生一遍优化 若干遍,单遍代码不太有效。,根据系统资源的状况、运行目标的要求等，可以将一个编译程序设计形成多遍扫描的形式，在每一遍扫描中完成不同的任务。,1.3 编译程序的结构,当一遍中包含若干阶段时，各阶段的工作是穿插进行的。,例如：,识别出一个语法单位时,1.3 编译程序的结构,三.编译前端与后端,1.前端：由与源语言有关但与目标机无关的那些部分组成 包括词法分析、语法分析、语义分析与中间代码 产生、部分代码优化工作,2.后端：包括编译程序中与目标机有关的那些部分，如与 目标机有关的代码优化和目标代码生成等。,不依赖于源语言而仅仅依赖于中间语言,1.3 编译程序的结构,1.5 编译程序的生成,一.设计目标,目标程序小，执行速度快编译程序小，执行速度快诊断能力强，可靠性强可移植性，可扩充性,如何实现编译器？,直接用可运行的代码编制,太费力！,1.5 编译程序的生成,2.问题,（1）历史上第一个高级语言的编译程序是怎样构造的？-自编译技术（自展技术）（2）已有A机器上的L1语言（如：C语言）的编译程序，如何构造A机器上的L2语言（如：PASCAL语言）的编译程序？（3）已有A机器上的L语言的编译程序，如何构造B机器上的L语言的编译程序？-交叉编译/移植,源语言,编译程序实现语言,目标语言,一般采用基于T形图的方式：,表现语言翻译的T形图,1.5 编译程序的生成,问题：已知A机上有一个用A代码实现的高级语言L1的编译程序，可以用L1实现在A机上能运行一个新语言L2编写的程序。,已知条件,目标,二.多级编译程序,1.本机编译器利用,分析：,1.5 编译程序的生成,条件,目标,L1语言写成的L2语言的编译程序,A代码写成的L1语言的编译程序,得到A代码写成的L2语言的编译程序,P0,P1,P2,说明：P0L2语言的编译程序，用L1语言实现 P1L1语言的编译程序，用A代码实现 P2L2语言的编译程序，用A代码实现,1.5 编译程序的生成,问题：已知A机上有一个用A代码实现的高级语言L的编译程序（即A机上可直接运行L语言程序），是否可利用该编译程序实现在B机上运行L语言程序？,条件,目标,2.交叉编译/移植（思考）,1.5 编译程序的生成,条件,目标,说明：过程在A机上运行的产生B代码的L编译程序源程序（L语言编写）,1.5 编译程序的生成,1.5 编译程序的生成,3.自编译过程,通过一系列自展途径而形成编译程序的过程叫做自编译过程。,1.5 编译程序的生成,三.如何学习构造编译程序,要在某一台机器上为某种语言构造一个编译程序，必须掌握以下内容：,源语言：对被编译的源语言，要深刻理解其结构（语法）和 含义（语义）。目标语言：假定目标语言是机器语言，那么，就必须搞清硬 件的系统结构和OS的功能。编译方法：把一种语言程序翻译为另一种语言程序的方法很 多，但必须准确的掌握一、二。,第1章 总结,1.编译程序的概念2.编译过程（掌握）3.基本概念：遍，编译前端/后端（掌握）4.T型图（了解）,
