东北大学秦皇岛分校编译原理课件第一章.ppt

《东北大学秦皇岛分校编译原理课件第一章.ppt》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校编译原理课件第一章.ppt（76页珍藏版）》请在三一办公上搜索。

1、编译原理,课时：授课课时48+实验课时8课程性质：必修/考试考试方式：闭卷考试主讲：敬茂华 先修课程：离散数学、组成原理、汇编语言、数据结构、C+或其他程序设计语言,第0章 预备知识,本门课程的目的和意义 程序设计语言与程序的翻译程序设计语言的语法描述,为什么要学习编译原理？,例int fact()static int i=5;if(i=0)return(i);elsei=i-1;return(i+abs(1)*fact();/*第9行,函数abs():求绝对值.*/main()printf(“factor of 5=%d/n”,fact();,上程序的运行结果是120。但是，如果把第9行的a

2、bs(1)改成1的话，该程序结果是1。,分析 i 是静态变量，所有地方对 i 的操作都是对同一地址空间的操作，所以每次递归进入fact函数后，上一层对 i 的赋值仍然有效。由于C语言的编译机制，每次调用时，(i+abs(1)*fact()中(i+abs(1)的值都先于fact算出。所以，第1次递归时，所求值为5*fact，第2次递归时，所求值为4*fact，第3次递归时，所求值为3*fact，第4次递归时，所求值为2*fact，第5次递归时，所求值为1*fact，而此时fact为1。这样，程序相当于是求一个阶乘函数5*4*3*2*1，所以，结果为120。程序改动后结果变化，主要是和编译时代码生

3、成策略有关。对于表达式(i+abs(1)*fact()，因两个子表达式都有函数调用，因此，编译器先产生左子表达式代码，后产生右子表达式代码。当abs(1)改为1后，左子表达式就没有函数调用了，于是，编译器会先产生右子表达式代码，这样一来，每次递归调用时，(i+1)*fact()中(i+1)的值后于fact算出。第1次递归时，所求值为(i+1)*fact()，第2次递归时，所求值为(i+1)*fact()，第5次递归时，所求值为(i+1)*fact()，而此时fact为1，i为0，即实际上每次递归调用所求的实际都是1*fact，最后结果还是1。,编译原理课程关注的内容,面向机器的语言计算机的硬件

4、只能识别由0、1字符串组成的机器指令序列，即机器指令程序。特点：不易理解，编写程序既困难又容易出错。用容易记忆的符号来代替0、字符串。用符号表示的指令被称为汇编指令，汇编指令的集合被称为汇编语言，由汇编语言编写的指令序列被称为汇编语言程序。面向人类的语言通用程序设计语言，如，Java，C#；数据查询语言，如；形式化描述语言，如EBNF、。其他面向特定应用领域的语言面向互联网应用的HTML、XML；面向计算机辅助设计的MATLAB；面向集成电路设计的VHDL、Verilog；面向虚拟现实的VRML；,语言之间的翻译高级语言之间的翻译，一般被称为转换，如FORTRAN到Ada的转换等，或者被称为预

5、处理，如SQL到C/C+的预处理。高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两个翻译过程是将高级语言的源程序翻译成低级语言的目标程序，这种翻译被称为编译。将一个汇编语言汇编为可在另一平台上运行的机器指令，则称为交叉汇编，而建立在交叉汇编基础之上的编译模式称为交叉编译。把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分别称它们为反汇编和反编译。上述语言之间的翻译虽然各不相同，但基本方法，特别是对源语言的分析方法是相同的。,编译原理与编译技术,编译原理与编译技术是两类不同的过程。编译原理研究的就是语言翻译方法中所用到的基本原理，关注的是产生编译器的理论和原理。一般并不深入讨论

6、某一具体的编译器的实现和工作机制。编译技术更关注编写（实现）编译器过程中所用到的技术。编译原理是学习编译技术以及深入掌握利用高级语言进行编程的基础。,通用程序设计语言的主要成份,通用程序设计语言的典型特征之一是抽象，其抽象程度是以程序设计语言所支持的基本结构为特征的。可以大致划分为三种形式：过程、模块（抽象数据类型，ADT）和类。以过程为基本结构的程序设计语言的典型代表有C、Pascal等；以ADT为基本结构的程序设计语言的典型代表是Ada83；而以类为基本结构的程序设计语言包括当前流行的C+、Java和Ada95等。这三种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象程度得到一次

7、提高，同时也为这些程序设计语言的编译器提出了新的要求。,类概念的引入，为利用程序设计语言构造类型提供了真正的支持，也是面向对象程序设计（OOP）语言的重要特征之一。程序设计语言提供的机制与程序设计的风格有着密切关系，以过程为基本抽象的程序设计语言支持的是过程式的程序设计范型（paradigm），以类为基本抽象的程序设计语言支持的是面向对象的程序设计范型，以ADT为基本抽象的程序设计语言介于二者之间，一般被认为是面向过程的语言，但也被认为是基于对象的语言。有些面向对象的程序设计语言是由过程式的语言发展而来的，如C+、Ada95等，它们实质上是支持多范型的程序设计语言。,本课程以PL/0（面向过程

8、的语言）编译器为例，讨论把高级语言中应用最广的通用程序设计语言翻译成汇编语言程序所涉及的基本原理、技术和方法。这些原理、技术和方法也同样适用于其他各类翻译器的构造，同时有些技术和方法也可以被用于其他软件设计。内容上以最简单的、以过程为基本结构的程序设计语言为背景进行讨论。因为无论何种形式的程序设计语言，均是由声明和操作这样两个基本元素构成的，所不同的是声明和操作的范围和复杂程度不同。以过程为基本结构的程序设计语言的特征是把整个程序作为一个过程。过程的定义由两类语句组成：声明性语句和操作性语句。一般来讲，声明性语句提供所操作对象的性质，如数据类型、值、作用域等。而操作性语句确定操作的计算次序，完

9、成实际操作。,本门课程的目的和意义 计算机问题求解的基本途径:对问题进行抽象和形式化表示，然后进行处理。掌握形式语言与自动机理论。掌握编译原理及方法。了解编译程序的实现原理和技术。培养形式化描述和抽象思维能力。利用从本课程学到的知识，增强编写和调试程序的能力。,编译原理及技术在其他方面的应用,正文查找正文处理指令识别等,程序设计语言与程序的翻译一般的程序设计语言的定义都涉及语法、语义和语用三个方面。由符号（单词）构成语法成分的规则称为一般语法规则。由基本符号构成的符号（单词）书写规则特称为词法规则。,程序设计语言的语法描述 语法图 BNF范式：；:=语法成分的定义；|表示“或者”扩充的BNF范

10、式：增加了三个符号 x表示x可以出现0到多次。x表示x可能出现，也可能不出现。（x|y）表示x和y二者取一。文法口语,第一章 概述,1.1 什么是编译程序 1.2 编译的基本过程 1.3 编译程序的逻辑结构 1.4 决定编译阶段组合的因素,1.5 与编译器相关的程序 1.6编译器的翻译步骤 1.7编译器中的主要数据结构 1.8 编译器结构的其他观点,直观印象：两数之和的程序,8086/8088机器语言的程序：1010 00000000 00010000 00001000 10100010 01100000 00100000 00000000 00001110 00001010 00100000

11、 00110000 00001111 0100,IBM PC汇编语言的程序：START:MOV AX,DSEGMOV DS,AXMOV AL,DATA1MOV AH,DATA2ADD AL,AHMOV RLT,ALHLT,C语言的程序：a=b+c;,1.1什么是编译程序(compiler),编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。,功能等价,什么是编译程序,语言转(变）换系统,C+编译器,C+,C,Java,Bytecode,Java编译器,1.1.1 编译程序的功能

12、,重要性：编译程序使得程序员不必去考虑那些与机器硬件相关的细节，而专注于自己的程序设计工作。,1.1.2 翻译程序的种类,汇编程序：用于特定计算机上的汇编语言的翻 译程序。编译程序：将高级语言翻译成低级语言的翻译 程序解释程序：将会话式语言翻译成目标指令的翻 译程序,编译程序与解释程序的根本区别,从翻译的角度来讲，两种方式所涉及的基本原理、方法与技术是相似的。,1.1.3 编译程序生成的目标程序的形式,可立即执行的机器语言代码 汇编语言程序 待装配的机器语言代码模块,1.1.4 什么叫机器语言,计算机提供的基本操作称为指令。指令的全体称为指令系统。指令系统也称为机器语言。指令的基本形式：,1.

13、1.5 什么是编译系统,N,高级语言程序的处理、执行过程,语言处理过程,1.1.6 编译理论和编译器的发展史,语言文法：语言结构的规则 有穷自动机（Finite Automata）：一种识别装置 正则表达式（Regular Expression）：是3型文法的一种等价表示,0型文法1型文法2型文法3型文法,1.2 编译的基本过程,词法分析,从左至右读字符流的源程序、识别(拼)单词例：position:=initial+rate*60;,词法分析position:=initial+rate*60;,单词类型单词值 标识符1(id1)position 算符(赋值):=标识符2(id2)initia

14、l 算符(加)+标识符3(id3)rate 算符(乘)*整数 60 分号；,语法分析,功能:层次分析。依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树)。position:=initial+rate*60;规则:=“:=”:=“+”:=“*”:=“(”“)”:=:=:=,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1:=id2+id3*N,语义分析,语义审查(静态语义)上下文相关性类型匹配类型转换,例:Program p();Var rate:real;procedure initial;position:=initial+

15、rate*60/*error*/*error*/*warning*/;,语义分析,中间代码生成,源程序的内部(中间)表示三元式、四元式、P-Code、C-Code、U-Code、bytecode(*id3t1t2)t2=id3*t1t2:=id3*t1,中间代码生成,id1:=id2+id3*60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1),代码优化,id1:=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)变换（1）(*id3

16、60.0t1)(2）（+id2 t1id1),代码优化,t1=b*c t1=b*c t2=t1+0 t2=t1+t1t3=b*c a=t2t4=t2+t3a=t4,目标代码生成,(*,id360.0t1)(+,id2t1id1),movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1,符号表管理,记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息,Const1常量值：35Var1变量类型：实层次：2,出错处理,检查错误、报告出错信息、排错、恢复编译工作,1.3编译程序的逻辑结构(components),词法分析程序语法分析

17、程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序,1.4 决定编译阶段组合的因素,分析，综合(synthesis)源程序的分析线性分析层次分析语义分析目标程序的综合编译的前端（front end）编译的后端（back end）遍（趟）从头到尾扫描源程序（各种形式）一遍(pass)。,1.5 与编译器相关的程序,翻译程序 编译程序（complier）解释程序（interpretor）汇编程序（assembler）连接程序（linker）装入程序（loader）预处理程序（preprocessor）编辑器（editor）调试程序（debugger）描述器（pr

18、ofiler）项目管理程序（project manager）,1.6编译器的翻译步骤,例：a index=4+2,一、扫描程序（Scanner）,8个记号（或：单词）（Token）：a标识符左括号index标识符右括号4数字+加号2数字,二、语法分析程序（Parser）,三、语义分析程序（Semantic Analyzer）,四、源代码优化程序（Source Code Optimizer）,五、代码生成器（Code Generator）,六、目标代码优化程序（Target Code Optimizer）,1.7编译器中的主要数据结构,记号（Token）（也叫单词）语法树（Syntax Tree

19、）符号表（Symbol Table）常数表（Literal Table）中间代码（Intermediate Code）临时文件（Temporary File）,补充知识,高级语言解释系统(interpreter),功能 让计算机执行高级语言（basic,lisp,prolog)与编译程序的不同 1）不生成目标代码 2）能支持交互环境（同增量式编译系统）源 程 序 初始数据,解释程序,计算结果,解释系统,直接对源程序中的语句进行分析，执行其隐含的操作。如：b:=2;a:=b+2;编译程序 write a;解释程序直接将4的值输出（显示）,Int 2St bLd badd 2St a,生成代码,编

20、译阶段和运行阶段存储结构,编译时 运行时,名字表,目标代码缓冲区,编译用源程序中间表示各种表格,目标代码区,数据区,源程序缓冲区,解释系统存储结构,1.3 编译技术的发展和应用,功能：程序 集成环境实现方式手工机器语言汇编系统程序设计语言自动构造工具lex yacc gcc,编译程序的发展,计算模式，语言范式语言应用领域,编译程序,冯诺伊曼机体系结构并行体系结构嵌入系统,编译程序的发展,语言范型(paradigms)命令式(imperative language)应用式(applicative)基于规则的（rule-based）面向对象的（object-oriented）编译程序执行环境批处理

21、交互环境嵌入系统环境,语言范型（支持的计算模式）,命令式：程序特点：语言执行的解释：编译技术发展快：语句1；改变机器状态 系统语言语句2；内存 自动化生成技术语句3；各种寄存器 的内容 外存 与冯诺伊曼机的 体系结构一般,应用式（函数式）：程序特点：Function n(funetion2(funetion1(data)程序执行：执行一个个函数施用在数据上的变换最终得到的结果编译：语法分析容易；语义处理复杂；,基于规则的语言（prolog,yacc)：程序特点：使能条件1 动作1 使能条件2 动作2 使能条件3 动作3 面向对象语言：抽象数据类型，继承机制编译：动态绑定；,执行环境,批处理环境

22、：将源程序作为整体处理 排除程序错误不能依靠用户的外部帮助交互环境：解释 增量式编译嵌入式系统环境：交叉编译分布并行环境：并行编译程序创建和测试环境：独立编译 编译和调试同时设计考虑,编译技术的发展和应用,结构化编译器程序分析工具 静态分析 动态分析 度量工具 结构度量 模块接口复杂度 c分析工具(source insight)广泛的语言领域 数据库系统查询 脚本语言 置标语言(SGML.HTML.XML),研究领域,并行编译技术交叉编译技术硬件描述语言及其编译技术,并行化编译技术,目的：提高并行计算机体系结构的性能。超大规模计算的日益增长的需求 高性能计算机 并行软件,并行体系结构,单机速度

23、,并行体系结构,途径1,途径2,并行体系结构 编译技术支持 串行程序并行化编译技术支持 并行程序设计语言编译 依赖于目标机的优化（低层）,性能发挥,并行算法复杂，难掌握，难编程 开发并行 软件的困难 并行程序的不确定行为，难调试，验证设计新的并行算法 修改已有串行程序尽量（直接用并行程序 并行化（研究算法和设计语言和并行程 应用的人同时工作）序库实现。).HPF.Occom.PVM,途径,1,2,嵌入式,交叉编译器,由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，称为交叉编译。,O,A,B,硬件描述语言及其编译技术,电路设计依据 验证结果 如：VHD

24、L,第一章 小结,内容1 什么是编译程序2 编译过程和编译程序的结构3 为什么要学习编译程序本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要说难点的话可能是:了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的。,参考书,Tomas Pittmn,The art of Compiler Design theory and Practice,Prentice-Hall 1992ALFRED V.AHO,RAVISETHI,JEFFREY D.ULLMAN,Compilers Principles,Techniques and Tools ADDISSON-

25、WESLEY 1986陈火旺 刘春林等 程序设计语言编译原理 国防工业出版社 2000David A Watt&Deryck F Brown Programming language processors in java(in c,in c+)compilers and interpreters,Prentice-Hall 2000,参考书,Terrence W.Pratt,Marvin V.Zelkowitz Programming Languages Design and Implementation,Prentice-Hall 1996Bennett,J.P.,Introduction to Compiling techniques:a first course using ANSI C,LEX and YACC.-2nd ed-,The McGRAW-HILL Publishing Company 1996David A.Watt,Programming Language Syntax and Semantics,Prentice Hall 1991,