编译原理湖南大学.ppt

《编译原理湖南大学.ppt》由会员分享，可在线阅读，更多相关《编译原理湖南大学.ppt（60页珍藏版）》请在三一办公上搜索。

1、2010-1-14,杨晓波湖南大学信息科学与工程学院Email:2/23/2011QQ群：81711763（编译原理）（输入学号进行验证，进入后改名为年级学号后三位+姓名，如：07101张三）,编译原理Compiler Principles,2010-1-14,教材及参考书,赵建华等译.编译原理(第2版).机械工业出版社，2009龙之书陈火旺.程序设计语言编译原理(第3版)国防工业出版社.2000,2010-1-14,学习内容及动机,课程内容编译程序构造的基本原理和实现技术.学习动机：提高学习能力、实践能力和计算思维能力编译程序是程序语言应用的基础 在早期的ACM 图灵奖中程序设计语言、编译理

2、论与方法约占1/3程序语言上千种，而其编译器的构造原理却相通其模型、理论和算法广泛应用,如：代码优化技术用于寻找软件缺陷和漏洞有穷自动机和正则表达式用于深度包检测文法用于自然语言翻译学好编译原理有助于更好地理解高级语言有助于构造一些实用的工具,万变不离其宗,2010-1-14,怎样构造编译程序,构造编译程序的前提:掌握源语言掌握目标语言掌握编译方法,2010-1-14,考核方式及要求,作业 20%+实验 30%+笔试 50%+表现-33要求DIY、按时交抄袭计0分，过期不候作业：word 2003文档，宋体5号,2010-1-14,第一章要点,语言处理器（是什么，做什么）编译器的结构（有什么）

3、编译程序的其他问题遍前端与后端编译程序的构造方法（怎么做）程序语言的发展历程程序设计语言基础,第一章 引 论,2010-1-14,1.1语言处理器,Q:我们怎么让计算机工作的？A:编程。Q:计算机能直接执行什么程序？A:机器语言程序Q:我们所书写的程序一般是面向人类的高级语言程序，它们是怎样执行的？,2010-1-14,1.1语言处理器,程序的执行方式解释型，如：BASIC编译型，如：C，C+混合型，如：JAVA其中后两种都要使用编译程序（编译器）。,2010-1-14,1.1语言处理器,编译程序(compiler)把某一种语言程序（源语言）等价地转换成另一种语言程序(目标语言)的程序,201

4、0-1-14,1.1语言处理器,解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是直接利用输入执行源程序中的指定操作。,2010-1-14,混合编译器,编译执行比解释执行快解释执行错误诊断效果更好JAVA处理器中结合了编译和解释过程，是混合编译器,源程序,编译器,中间代码,2010-1-14,JAVA语言,操作系统平台,Java虚拟机(解释器),Java编译器,javac,java,2010-1-14,.NET框架与VS.NET,.net框架类似java虚拟机,2010-1-14,.net编程工作原理,操作系统平台,CLR,各自的编译器,高级语言代码(支持CLR,符合CLS),托管代

5、码（MSIL）,即时编译JIT,操作系统平台,CLR,各自的编译器,操作系统平台,CLR,各自的编译器,操作系统平台,2010-1-14,语言处理系统,要产生可执行的文件，除了编译器外，还需要其他的一些程序。,宏扩展，加入头文件,2010-1-14,1.2 编译器结构,把英文翻译为中文的过程如下：识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。,词法分析,语法分析,中间代码产生,优化,目标代码产生,2010-1-14,编译器的结构（1）,编译器可以分为分析部分和综合部分分析部分（前端，front end）把源程序分解成组成要素，以及相应

6、的语法结构使用这个结构创建源程序的中间表示同时收集和源程序相关的信息，存放到符号表综合部分（后端，back end）根据中间表示和符号表信息构造目标程序前端部分是机器无关的，后端部分是机器相关的。,2010-1-14,编译器的结构（2）,编译器可分成顺序执行的一组步骤（phase）,前端,后端,与源语言有关,与目标机有关,2010-1-14,词法分析,词法分析/扫描（lexical analysis,scanning）读入源程序的字符流，输出成为有意义的词素(lexeme)token-name由语法分析步骤使用attribute-value指向相应的符号表条目，由语义分析/代码生成步骤使用例子

7、position=initial+rate*60,2010-1-14,语法分析,语法分析/解析（syntax analysis/parsing）根据各个词法单元的第一个分量来创建树型的中间表示形式。通常是语法树（syntax tree）中间表示形式指出了词法单元流的语法结构。,2010-1-14,语义分析,语义分析（semantic analysis）使用语法树和符号表中的信息，检查源程序是否满足语言定义的语义约束。同时收集类型信息，用于代码生成，类型检查，类型转换。,2010-1-14,中间代码生成,根据语义分析的输出，生成类机器语言的中间表示三地址代码：每个指令最多包含三个运算分量t1=i

8、nttofloat(60)；t2=id3*t1;t3=id2+t2;很容易生成机器语言指令,2010-1-14,代码优化,通过对中间代码的分析，改进中间代码的质量更快、更短、能耗更低,2010-1-14,代码生成,把中间表示形式映射到目标语言寄存器的分配指令选择内存分配,2010-1-14,1.2.7 符号表管理,符号表是编译中常用的一种数据结构，贯穿编译的各个阶段。它记录源程序中使用的名字及其属性，常见名字及其属性如下：变量 存储位置 类型 作用域过程 过程入口 参数数量和类型、每个参数的传递机制、返回值类型 每个名字对应于一个记录，其一般形式如下：,名字,信息,2010-1-14,1.2.

9、8 将多个阶段组合成遍(pass),趟（PASS）每趟读入一个输入文件，产生一个输出文件。“步骤”是逻辑组织方式“趟”和具体的实现相关，如：前端的词法分析、语法分析、语义分析以及中间代码生成可以组合在一起成为一趟代码优化可作为一个可选的趟后端可作为一趟,2010-1-14,编译区分前端与后端的好处方便移植,有些编译器集合围绕一组精心设计的中间表示形式而创建，使得可将特定语言的前端和特定目标的后端相结合一个前端和不同的目标机后端结合，可建立针对不同目标机器上的编译程序如：JAVA语言的操作平台无关性JAVA定义一种虚拟机代码Bytecode只要操作平台上实现了执行Bytecode的JAVA解释器

10、，就可以执行各种Java程序不同前端和某个目标机的后端结合起来，可生成在同一目标机器上的不同语言的编译程序如：.net平台,2010-1-14,1.2.9 编译器构造工具,Q:怎样构造编译器？A:用汇编语言和机器语言书写高级语言书写移植和自展利用现代软件开发环境和编译器构造工具,2010-1-14,编译器构造工具,语法分析程序生成器根据程序语言的语法描述自动生成语法分析器，如：YACC词法分析程序生成器根据语言语法结构的正则表达式自动生成语法分析器，如：LEX语法制导翻译引擎可生成一组用于遍历分析树并生成中间代码的例程,编译程序生成,2010-1-14,编译器构造工具,代码生成器的生成器根据一

11、组关于如何把中间语言的每个运算翻译成为目标机语言的规则，生成一个代码生成器。数据流分析引擎可帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。数据流分析是代码优化的一个重要部分编译器构造工具集提供了可用于构造编译器的不同阶段的例程的完整集合。,编译程序生成,2010-1-14,程序设计语言的发展历程,历程第一代：机器语言第二代：汇编语言（宏命令）第三代：Fortran，Cobol，Lisp，C，C+，第四代：特定应用语言：NOMAD,SQL,Postscript第五代：基于逻辑和约束的语言，Prolog、OPS5强制式语言/声明式语言前者指明如何完成，后者指明要完成哪些计算冯

12、.诺依曼语言/面向对象的语言/脚本语言,2010-1-14,语言范型及其举例,强制式语言程序说明怎么做，如：C，C+，Java，C#等声明式语言程序说明做什么，如：Prolog，ML，Haskell等面向对象语言支持面向对象编程，如：C+，Java，C#，Ruby脚本语言具有高层次运算符的解释型语言常用于把多个计算过程（脚本）“粘合”在一起如：Javascript,VBscript,PHP,Python,Ruby等特点：短,2010-1-14,最新编程语言排名（Tiobe）,33,2010-1-14,程序设计语言、计算机体系结构与编译器的关系,程序设计语言的新发展向编译器设计者提出新要求设计相

13、应的算法和表示方法来翻译和支持新的语言特征多态；动态绑定；类；类属（模板）；通过降低高级语言的执行开销，推动这些高级语言的使用编译器设计者还需要更好地利用新硬件的能力RISC技术、多核技术、大规模并行技术,2010-1-14,1.6 程序语言基础,静态与动态的区别：决策在程序运行之前还是之后静态：语言策略支持编译器静态决定某个问题动态：只允许在程序运行时刻作出决定Java类声明中的static指明了变量的存放位置可静态确定作用域x的作用域指程序文本的一个区域，其中对x的使用都指向这个声明。静态作用域：通过静态阅读程序即可决定作用域（大多数语言，如如：C和Java）动态作用域,2010-1-14

14、,环境与状态,1.6 程序语言基础,环境：从名字到存储位置的映射状态：从内存位置到它们的值的映射,2010-1-14,绑定,绑定（binding）是两个东西之间的关联如：名字与存储位置（变量）、变量与值。静态绑定：在程序运行前建立的约束如：全局变量、static变量可以在编译时确定其存储位置；常量的值始终不变。动态绑定：在程序执行过程中建立的约束如：变量的值。,2010-1-14,绑定,若C程序中有如下声明：#define ARRAYSIZE 100那么：ARRAYSIZE=10是否正确？为什么？,2010-1-14,名字、标识符和变量,标识符字母串，常由字母开头，后跟若干个字母或数字用于指称

15、一个实体，如：数据对象、过程、类等名字是助记符，如：标识符，符号（）程序语言里最基本的抽象机制用来指称变量、常量、过程/函数、结构/记录的成分、类型等。所有标识符都是名字，而名字不一定是标识符，它还可以是一个表达式，如：x.y是名字，但不是标识符！,1.6 程序语言基础,2010-1-14,名字、标识符和变量,变量指向存储中的某个特定的位置注：每次变量声明将引入一个新的变量（新存储位置）递归过程中的局部变量在每次调用时占用的存储位置不同,1.6 程序语言基础,2010-1-14,声明和定义,声明确定事物的类型如：int i是一个i的声明定义确定事物的值如：i=1是i的一个定义（定值）C+中的方

16、法：在类定义中声明，说明其参数和返回值类型在另一个地方通过代码执行该方法（定义）,1.6 程序语言基础,2010-1-14,过程、函数和方法,一般地，过程、函数和方法可统称为“过程”狭义的过程一般无返回值但具体讨论某语言程序时可能有所差异，如：C语言只有函数，无返回值的函数设为void类型Java只有方法，C+中也称方法（OO语言）方法总是和某个特定的类相关联,2010-1-14,1.6.3 静态作用域和块结构,块：一组声明和语句如：C语言的块语法：以开头、结尾，其内包含了一个声明序列，后跟一个语句序列该语法允许一个块嵌套在另一个块内，这个嵌套特性称为块结构。C族语言都具有块结构，但C语言不允

17、许在一个函数内嵌套另一个函数,2010-1-14,1.6.3 静态作用域和块结构,C语言的静态作用域策略C程序由一个顶层的变量和函数声明序列构成函数内部可以声明变量（局部变量或参数），其作用域为声明的那个函数内在顶层声明的名字x，其作用域包括其后的所有程序。但若某个函数中也声明了x，则该函数的语句不在顶层声明的x的作用域。,2010-1-14,作用域举例,1.6.3 静态作用域和块结构,2010-1-14,变量声明的静态作用域规则,若块B是包含声明D的最内层的块，则称D属于B变量声明的静态作用域规则若名字x的声明D属于B，则D的作用域包括整个B，但不包括嵌套在其内、但重新声明了x的所有块B(作

18、用域空洞）,2010-1-14,Q:B4的输出结果？,块作用域的例子,2010-1-14,1.6.4 显式访问控制,类和结构为其成员引入新的作用域若p是一个类，x是其成员，则p.x引用的是该类定义中的成员x类似块结构，类C的成员作用域可扩展到所有的子类C，除非C有对x的重新声明,2010-1-14,1.6.4 显式访问控制,OO语言通过private,public和protected等关键字，提供对超类的成员名字的显示访问控制Private:私有，作用域仅包含该类和“友类”相关方法声明和定义Protected:受保护，可从子类访问Public:公共，可从类外访问,2010-1-14,1.6.5

19、 动态作用域,如果一个作用域策略依赖于一个或多个只有程序运行时才能知道的因素，它就是动态的。动态作用域中对一个名字x的引用指向的是最近被调用但还没有终止且声明了x的过程中的这个声明，如：C预处理器的宏扩展面向对象编程中的方法解析,2010-1-14,动态作用域举例宏扩展,2010-1-14,动态作用域举例多态过程解析,多态过程：同名多定义（参数个数和类型不同）的过程有些语言可静态确定名字的类型，编译器可把过程替换为对应过程代码的引用，如：ML但其它语言中有些编译器有时不能作出这样的决定，如：Java和C+,2010-1-14,动态作用域举例多态过程解析,正常情况下，编译时不能指出x引用的是类C

20、的对象还是其子类D的对象只有运行时才能确定应调用m的哪个定义因此，编译器生成的代码必须决定对象x的类，并调用其中的x方法,2010-1-14,参数传递,问题：程序中调用过程与被调用过程之间怎样进行信息交流？答：通过以下两种方式：非局部变量参数传递,2010-1-14,参数传递方式,一传值把实在参数的值传递给相应的形式参数例：PASCAL值参数、C、Java方法：调用程序计算实参的值被调用过程开始工作时，首先把实参的值抄入相应的形参单元；被调用过程中，象引用局部数据一样引用形式单元。特点：传递实参的副本,2010-1-14,对形式参数的改变是针对本过程的形参单元进行的，对实参没有影响，在函数外不

21、起作用。例如，在C中：void inc2(int x)+x;+x;Main()int y=2;inc2(y);printf(“%d”,y);输出结果为：2,值传递的特点,未使y的值加2,2010-1-14,参数传递方式,二.传地址把实在参数的地址传递给相应的形式参数例：PASCAL变量参数，C、C+和Java数组参数、C+中的”ref”参数方法：调用程序计算实参地址程序控制转入被调用段之后，首先把实参地址抄进相应的形式单元中；过程体对形式参数的引用与赋值被处理成根据形式单元内存储的地址对实参进行访问（间接访问）。特点：可能改变实参的值,2010-1-14,procedure swap(var

22、m:integer;var n:integer);var i:integer;begin i:=m;m:=n;n:=i;end,swap(a,b),传地址举例,1,2,1,调用后a:2,b:1完成了数据交换,2010-1-14,procedure P(w,x,y,z);begin y:=y*w;z:=z+x;endbegin a:=5;b:=3;P(a+b,a-b,a,a);write(a);end,传值:传地址:,542,a:b:T1(a+b):T2(a-b):,5382,参数传递机制举例,40,42,2010-1-14,别名,即一址多名：同一个地址可以用两种以上方式访问（多个名字）如：对应于两个形式参数。这多个名字互称为别名。主要问题：修改一个变量的值，会改变另一个变量的值。所以别名分析也值得注意。,