张小艳编译原理.ppt

1、编译原理 编译原理是一门非常好的课程 主讲教师：张小艳Email:QQ:1161880978,2,课程性质： 不是针对某一种语言，具有普适性、科学性、基础性 学习目的： 了解PL的基本要素、工作原理、语言翻译的基本方法； 用不同的PL进行程序设计，即自学计算机语言的能力； 具备语言翻译的基本技能。 地位： 计算机专业的一门核心课程 编译程序是计算机的重要系统软件，是高级程序设计语言的支撑基础,上课环节 “职业精神” 认真听课，认真理解书中的基本概念、基本原理与基本算法，特别是算法的思想。 勤动手、多实践、提高学习能力,学习方法,1.学到的知识是死的，总有过时的时候。只有通过学习知 识提高学习能

2、力，才是立于不败之地的保证。 2.记笔记：好记性不如烂笔头，通过动手加深理解和记忆。 3.做作业、做上机题。,主要内容,编译概述（总体结构、设计方法2 ） 语言与文法（文法、推导、归约、分类、分析树4） 词法分析（词法分析、正规式与正规文法、DFA的状态转移图6） 语法分析（自顶向下、递归子程序；自底向上：算符优先、LR-16） 语义分析（属性文法、各种语句的语法制导翻译10） 运行环境（存储分配、过程调用、符号表管理6） 代码优化（基本块的优化、控制流分析、循环优化、数据流分析2） 代码生成（目标机器模型、基本块和流图、寄存器分配2）,教材： 编译原理 （第三版），蒋立源、康慕宁主编，西工大

3、出版社。 参考书： 编译原理（第二版），张素琴、吕映芝、蒋维杜、戴桂兰，清华大学出版社。 编译原理及实践，（美）Kenneth C.Louden著，冯博琴，冯岚等译，机械工业出版社。 编译原理，（美）Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著，李建中 姜守旭译，机械工业出版社。 程序设计与语言编译原理 （第三版），陈火旺主编，国防工业出版社。,教材及参考书,南京市长江大桥欢迎您！ 乒乓球拍买完了 I am a student 我是一个学生,int LocatList (SeqList *L , datatype x) int i=0; while ( i

4、last /*返回的是存储位置*/ ,8,课前思考 什么是编译程序 编译过程和编译程序的结构 为什么要学习编译程序,学习目标 明确编译程序的功能及其在计算机系统中的作用。 了解源语言程序被编译为目标程序的整个过程，这个过程一般划分为哪些阶段。 知道编译技术可用于哪类软件的设计和开发。,第一章绪论,难重点,本章主要对编译程序的功能和结构做一综述。 通过课程的学习应掌握各个成分的功能和设计原则，以及在编译阶段的逻辑关系。理解他们怎样作为一个整体完成编译任务的。,学习指南,编译程序是现代计算机系统的基本组成部分之一。 编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码

5、生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。 通过学习应掌握各个成分的功能和设计原则，以及在编译阶段的逻辑关系。理解他们怎样作为一个整体完成编译任务的。,1.1 计算机语言的发展,机器语言(Machine Language)与汇编语言(Assemble Language) 0、1代码与助记符：更接近于计算机硬件指令系统的工作 高级语言(High Level Language) 其表示方法更接近于待解问题的表示方法 定义数据、描述运算、控制流程、传输数据 如：C、FORTRAN、PASCAL、C+、JAVA、SQL(数据定义、数据操作) 命令语言(Command Languag

6、e) 控制系统的工作以功能封装为特征 如UNIX上的shell,12,从面向机器的语言到面向人类的语言 面向机器的语言：机器指令、汇编语言 面向人类的语言：通用程序设计语言、非过程式语言，等等,计算机语言举例 例 通用程序设计语言与汇编语言（包括机器指令） Pascal语句：x := a+b； 汇编指令：十六进制代码汇编指令 A10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX,13,给出003号学生所选课程与成绩： Select 学号,姓名,课程名,成绩 from 学生,选课 where 学生.学号=“003

7、” ;,例 SQL语言 学 生： 选 课：,14,CCC2002PL： 1过程式语言、面向对象语言：通用程序设计语言，包括FORTRAN、Pascal、C/C+、Ada83/Ada95、Java等； 2函数语言：面向特点领域的、递归特性，典型代表：Lisp； 3说明性、非算法式语言：浓厚的数学特征，典型代表：LEX/YACC、SQL； 4脚本式语言：仅是一种安排，没有复杂的逻辑关系，典型代表：shell语言。, 按范型划分的程序设计语言,15, 其他面向特定应用领域的语言,a互连网应用：HTML、XML b计算机辅助设计：MATLAB c集成电路设计：VHDL、Verilog d虚拟现实：VR

8、ML ,问题： 如何将形形色色的语言翻译成可以在计算机上运行的0、1串?,16,1.2 语言之间的翻译,高级,汇编,机器,L1,L2,A1,A2,M1,M2,反汇编,从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。源语言通常是一个高级语言,目标语言通常是一个低级语言。,高级语言程序 (源程序),请注意：所谓的源和目标程序的等价是什麽含义-他们的功能一样。,编译程序,目标程序,如果从计算机系统的角度看，什么是编译程序呢？我们说编译程序是一种软件，是系统软件。通常认为系统软件是居于计算机系统中最靠近硬件的一层，其他软件

9、一般都通过系统软件发挥作用。系统软件和具体的应用领域无关，如编译系统和操作系统等。,编译程序也是一种语言处理系统，即把软件语言书写的各种程序处理成可在计算机上执行的程序。,19,语言翻译的两种基本形态 1.先翻译后执行 2. 边翻译边执行,例5 假设有源程序：read(x); write(x=, x);,1.3 编译器与解释器,20,特点： 1编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译； 2解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。 基本功能：二者相同； 所采用的技术：从翻译的

10、角度来讲，两种方式所涉及的原理、方法、技术相似。,21,1从语言抽象的演变看： 过程抽象数据类型（ADT，程序包） 类 2共同特点：两大部分组成：声明操作完整定义 3以过程式语言为例：,声明性语句： 提供操作对象的性质，如数据类型、值、作用域等； 操作性语句：确定操作的计算次序，完成实际操作。 过程头过程体过程定义,1.4 编译器的工作原理与基本组成1.4.1 通用程序设计语言的主要成份,4编译器对两类语句的翻译： 声明：生成相应的环境，一般是配置存储空间。 操作：生成可执行的代码序列。,计算机执行高级语言程序的步骤,源程序P,目标程序P,运行结果S,编译程序,数据,运行程序,计算机A,计算机

11、B,编译阶段,运行阶段,23,1自然语言的翻译过程： 识别单词 识别句子结构 理解意思 译成中文并修饰,2编译器的工作过程： 词法分析 语法分析 语义分析 目标代码生成 3编译器的阶段 （逻辑模块划分）,4中间代码的重要作用 使编译程序在逻辑上更为简单清晰； 可进行优化,1.4.2 以阶段划分编译器,编译程序的逻辑结构,词法分析程序,语法分析程序,语义分析程序,中间代码生成,代码优化程序,目标代码生成,信息表管理程序,错误检查和处理程序,源 程 序,目 标 代 码,词法分析词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分

12、解，从而识别出一个个单词(也称单词符号或符号)。,例如某源程序片断如下： begin var sum, first, count: real; sum:=first+count*10 end. 词法分析阶段将构成这段程序的字符组成了如下19个,单词序列： 1. 保留字begin2. 保留字var3. 标识符sum 4. 逗号，5. 标识符first6. 逗号，7. 标识符count8. 冒号：9. 保留字real 10. 分号；,11. 标识符sum 12. 赋值号=13. 标识符first14. 加号+15. 标识符count 16. 乘号*17. 整数1018. 保留字end19. 界符,

13、标识符用于表示变量名,可以很方便的使用id1，id2和id3分别表示sum，first和count三个标识符的内部形式，那么经过词法分析后上述程序片断中的赋值语句 sum=first+count*10 表示为: id1=id2+id3*10,词法分析阶段的任务是读字符流的源程序、从中识别并构成单词。,一个Pascal源程序片断： position := initial + rate * 60； 词法分析后可能返回：单词类型 单词值标识符 position算符(赋值) :=标识符 initial算符(加) +标识符 rate算符(乘) *整数 60界符(分号) ；,一个C源程序片断：int a;

14、a = a + 2; 词法分析后可能返回:单词类型 单词值保留字 int标识符 a界符 ;标识符 a 算符(赋值) =标识符 a算符(加) +整数 2界符 ；,有关的英文词法分析-lexical analysis 或者scanning单词-token保留字-resered word标识符-identifier(user-defined name),语法分析语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位可表示成语法树，比如上述程序段中的单词序列：id1=id2+id3*10 经语

15、法分析得知其是PASCAL语言的“赋值语句”，表示成如下页图所示的语法树,id1=id2+id3*10,id1=id2+id3*10,语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。程序的结构通常是由递归规则表示的，例如，我们可以用下面的规则来定义表达式：(1) 任何标识符是表达式。(2) 任何常数(整常数、实常数)是表达式。(3) 若表达式1和表达式2都是表达式，那么：表达式1+表达式2以及表达式1 * 表达式2都是表达式。,类似地，语句也可以递归地定义，如(1) 标识符=表达式是语句。(2) while(表达式)do语句和 i

16、f(表达式 )then语句 else语句都是语句。,词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就无法仅用线性扫描去匹配表达式中的括号。,语义分析语义分析阶段的任务是审查源程序有无语义错误。源程序中有些语法成分，按照语法规则去判断，它是正确的，但它不符合语义规则。比如使用了没有声明的变量；或者给一个过程名赋值；或者调用函数

17、时参数类型不合适或者参加运算的两个变量类型不匹配等等。比如下边的程序片段：int arr2,c;c = arr1 * 10 ; 其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。,一般，语义分析的工作还包括类型审查，类型提升以及为代码生成阶段收集类型信息. 比如审查每个算符是否实施于具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。又比如对实数用作数组下标的情况报告错误。又比如某些语言规定运算对象可被强制，那么当二目运算施于一个整型量和一个实型量时，编译程序应将整型量自动转换成实型量而不能认为是源程序的错误，或者给出警告信息后将整型量自动转换成实型量

18、。,假如在赋值语句sum=first+count*10中，算符*的两个运算对象分别是count和10,而count是实型变量，10是整型量。语义分析阶段进行类型审查之后，将整型量提升为实型量。在语法分析所得到的分析树上增加一个一目算符结点，这个结点的名称为inttoreal，表示进行将整型量变成实型量的语义处理,sum=first+count*10,count是实型变量,我们来总结一下语义分析主要的任务-完成静态语义审查和处理上下文相关性审查类型匹配审查类型转换,中间代码生成阶段在进行了上述的词法分析，语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式

19、叫做中间语言或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程序采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为： (运算符，运算对象1，运算对象2，结果)。,如源程序sum = first+count*10可生成四元式序列，如下所示，其中ti(i=1,2,3)是编译程序生成的临时名字，用于存放运算结果的。 (1) (inttoreal 10 - t1 ) (2) (* id3 t1 t2 ) (3) (+ id2 t2 t3 ) (4) ( :=

20、t3 - t4),四元式 (运算符，运算对象1，运算对象2，结果) 常写成赋值语句的形式 (结果=运算对象1 运算符 运算对象2) 如c语言的源程序a = b * c + b * d 的四元式序列为(1) t1 = b * c(2) t2 = b * d(3) t3 = t1 + t2(4) a = t3,翻译分支，循环和函数调用等语句时，四元式的生成通常要比上述例子复杂些。比如源程序：if ( a = b) a = a c;c = b * c;,翻译成的四元式: t1 = a bif t1 goto lt2 = a ca = t2 l : t3 = b * cc = t3,代码优化代码优化阶

21、段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。如: (1) (inttoreal 10 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) ( := t3 - t4) 可变换为 (1) (* id3 10.0 t1) (2) (+ id2 t1 id1),代码优化工作会降低编译程序的编译速度，因此编译优化阶段常常作为可选择阶段，编译程序具有控制机制以允许用户在编译速度和目标代码的质量间进行权衡。,目标代码生成目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指

22、令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。,例如，使用两个寄存器(R1和R2)，图1.8的中间代码可生成如下某汇编代码。,前面说过，上述编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进行优化，优化阶段即可省去;有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成，如第2章介绍的PL/0语言编译程序。,编译程序的另外两个重要的

23、工作是表格管理和出错处理最重要的一种表格是符号表。符号表中记录源程序中使用的名字和收集到的每个名字的各种属性信息，诸如类型、作用域、分配存储信息。在第二章你会看到一种符号表，在第九章你会对符号表的组织和管理了解的更深入。出错处理程序的任务包括检查错误、报告出错信息、排错、恢复编译工作。,49,例7 Pascal源程序语句如下： var x, y, z : real; x := y + z * 60;,（源程序）var x, y, z : real; x := y + z * 60;,（记号流）var id1, id2, id3 : real; id1 := id2+id3*60;,1.4.3

24、编译器各阶段的工作举例,中间代码的形式与作用： (序号)(op， arg1, arg2, result) result := arg1 op arg2,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),(1) (*, id3, 60.0, T1) (2) (+, id2, T1, id1),MOVF id3, R2 MU

25、LF#60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1,R2 := id3 R2 := R2 * 60.0 R1 := id2 R1 := R1 + R2 id1 := R1 id1 := id2 + id3 * 60.0 x := y + z * 60;,52,各阶段工作的归纳, 词法分析：识别单词，至少分以下几大类：关键字（保留字）、标识符、字面量、特殊符号； 语法分析：得到语言结构并以树的形式表示； 语义分析：考察结构正确的句子是否语义合法，可修改树结构； 中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成

26、； 中间代码优化（可选）：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但是，在占用的空间上和程序执行的时间上都更省、更有效。 目标代码生成：不同形式的目标代码汇编、可重定位、内存形式（Load-and-Go）; 符号表管理：合理组织符号，便于各阶段查找、填写等； 出错处理：错误的种类词法错、语法错、静态语义错、动态语义错。,53,1前端：语言结构的分析； 2后端：语言意义的分析与处理； 3中间代码：前端与后端的分界； 4编译器基础架构（Infrastructure） ：源代码的中间表示、一组前端、一组后端；,1.4.4 编译器的分析/综合模式,1

27、.4.5 编译器扫描的遍数,1每个阶段将程序完整分析一遍的工作模式称为一遍扫描。早期编译器的一遍定义为从外存读入内存再写到外存； 2确定扫描遍数的因素： (a) 软、硬件条件，如内存太小，或全局优化 (b) 语言结构，如规定标识符的先声明后引用, x := f(a, b, c); function f(a:integer; b:integer): integer;,(c)编译技术，如拉链回填, goto lab1; lab1: ,编译程序的组织,语法分析 程序,语义分析及 代码生成程序,词法分析 程序,整理目标程序,源程序,目标程序,停机,开始,56,1.5 编译器的编写,1直接使用汇编语言和

28、程序设计语言； 2利用编译器编写工具：词/语法、语法制导翻译、代码生成、数据流分析等； 3基于编译器基础架构的编译器构造系统（开放式编译器，如GCC、SUIF等）。,1.6 编译技术的发展和应用据说第一个编译程序的出现是在20世纪50年代早期，很难讲出确切的时间，因为当初大量的实验和实现工作是由不同的小组独立完成的，多数早期的编译工作是将算术公式翻译成机器代码。用现在的标准来衡量，当时的编译程序能完成的工作十分初步，如只允许简单的单目运算，数据元素的命名方式有很多限制。然而它们奠定了对高级语言编译系统的研究和开发的基础。随着编译技术的发展和社会对编译程序需求的不断增长，20世纪50年代末有人开始研究编译程序的自动生成工具，提出并研制编译程序的编译程序。它的功能是以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编译程序。,目前很多自动