编译原理湖南大学.pptVIP

杨晓波 湖南大学信息科学与工程学院 Email: 248133074 2/23/2011 QQ群：81711763（编译原理） （输入学号进行验证，进入后改名为年级学号后三位+姓名，如：07101张三）,编译原理 Compiler Principles,教材及参考书,赵建华等译.编译原理(第2版).机械工业出版社，2009 龙之书 陈火旺.程序设计语言编译原理(第3版) 国防工业出版社.2000,课程内容 编译程序构造的基本原理和实现技术. 学习动机：提高学习能力、实践能力和计算思维能力 编译程序是程序语言应用的基础 在早期的ACM 图灵奖中程序设计语言、编译理论与方法约占1/3 程序语言上千种，而其编译器的构造原理却相通 其模型、理论和算法广泛应用,如： 代码优化技术用于寻找软件缺陷和漏洞 有穷自动机和正则表达式用于深度包检测 文法用于自然语言翻译 学好编译原理 有助于更好地理解高级语言 有助于构造一些实用的工具,万变不离其宗,怎样构造编译程序,构造编译程序的前提: 掌握源语言 掌握目标语言 掌握编译方法,考核方式及要求,作业 20%+实验 30%+笔试 50%+表现-33 要求 DIY、按时交 抄袭计0分，过期不候 作业：word 2003文档，宋体5号,第一章要点,语言处理器（是什么，做什么） 编译器的结构（有什么） 编译程序的其他问题 遍 前端与后端 编译程序的构造方法（怎么做） 程序语言的发展历程 程序设计语言基础,第一章 引 论,1.1语言处理器,Q:我们怎么让计算机工作的？ A: 编程。 Q:计算机能直接执行什么程序？ A:机器语言程序 Q:我们所书写的程序一般是面向人类的高级语言程序，它们是怎样执行的？,1.1语言处理器,程序的执行方式 解释型，如：BASIC 编译型，如：C，C+ 混合型，如：JAVA 其中后两种都要使用编译程序（编译器）。,1.1语言处理器,编译程序(compiler) 把某一种语言程序（源语言）等价地转换成另一种语言程序(目标语言)的程序,1.1语言处理器,解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是直接利用输入执行源程序中的指定操作。,混合编译器,编译执行比解释执行快 解释执行错误诊断效果更好 JAVA处理器中结合了编译和解释过程，是混合编译器,源程序,编译器,中间代码,JAVA语言,操作系统平台,Java虚拟机(解释器),Java编译器,javac,java,.NET框架与VS.NET,.net框架类似java虚拟机,.net编程工作原理,操作系统平台,CLR,各自的编译器,高级语言代码 (支持CLR,符合CLS),托管代码（MSIL ）,即时编译 JIT,操作系统平台,CLR,各自的编译器,操作系统平台,CLR,各自的编译器,操作系统平台,语言处理系统,要产生可执行的文件，除了编译 器外，还需要其他的一些程序。,宏扩展，加入头文件,1.2 编译器结构,把英文翻译为中文的过程如下： 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。,词法分析,语法分析,中间代码产生,优化,目标代码产生,编译器的结构（1）,编译器可以分为分析部分和综合部分 分析部分（前端，front end） 把源程序分解成组成要素，以及相应的语法结构 使用这个结构创建源程序的中间表示 同时收集和源程序相关的信息，存放到符号表 综合部分（后端，back end） 根据中间表示和符号表信息构造目标程序 前端部分是机器无关的，后端部分是机器相关的。,编译器的结构（2）,编译器可分成顺序执行的一组步骤（phase）,前端,后端,与源语言有关,与目标机有关,词法分析,词法分析/扫描（lexical analysis, scanning） 读入源程序的字符流，输出成为有意义的词素(lexeme) token-name由语法分析步骤使用 attribute-value指向相应的符号表条目，由语义分析/代码生成步骤使用 例子 position = initial + rate * 60 ,语法分析,语法分析/解析（syntax analysis/parsing） 根据各个词法单元的第一个分量来创建树型的中间表示形式。通常是语法树（syntax tree） 中间表示形式指出了词法单元流的语法结构。,语义分析,语义分析（semantic analysis） 使用语法树和符号表中的信息，检查源程序是否满足语言定义的语义约束。 同时收集类型信息，用于代码生成，类型检查，类型转换。,中间代码生成,根据语义分析的输出，生成类机器语言的中间表示 三地址代码： 每个指令最多包含三个运算分量 t1 = inttofloat(60)； t2 = id3 * t1; t3 = id2 + t2; 很容易生成机器语言指令,代码优化,通过对中间代码的分析，改进中间代码的质量 更快、更短、能耗更低,代码生成,把中间表示形式映射到目标语言 寄存器的分配 指令选择 内存分配,1.2.7 符号表管理,符号表是编译中常用的一种数据结构，贯穿编译的各个阶段。 它记录源程序中使用的名字及其属性，常见名字及其属性如下： 变量 存储位置 类型 作用域 过程 过程入口 参数数量和类型、每个参数的传递机制、返回值类型 每个名字对应于一个记录，其一般形式如下：,名字,信息,1.2.8 将多个阶段组合成遍(pass),趟（PASS） 每趟读入一个输入文件，产生一个输出文件。 “步骤”是逻辑组织方式 “趟”和具体的实现相关，如： 前端的词法分析、语法分析、语义分析以及中间代码生成可以组合在一起成为一趟 代码优化可作为一个可选的趟 后端可作为一趟,编译区分前端与后端的好处 方便移植,有些编译器集合围绕一组精心设计的中间表示形式而创建，使得可将特定语言的前端和特定目标的后端相结合 一个前端和不同的目标机后端结合，可建立针对不同目标机器上的编译程序 如：JAVA语言的操作平台无关性 JAVA定义一种虚拟机代码Bytecode 只要操作平台上实现了执行Bytecode的JAVA解释器，就可以执行各种Java程序 不同前端和某个目标机的后端结合起来，可生成在同一目标机器上的不同语言的编译程序 如：.net平台,1.2.9 编译器构造工具,Q:怎样构造编译器？ A: 用汇编语言和机器语言书写 高级语言书写 移植和自展 利用现代软件开发环境和编译器构造工具,编译器构造工具,语法分析程序生成器 根据程序语言的语法描述自动生成语法分析器，如： YACC 词法分析程序生成器 根据语言语法结构的正则表达式自动生成语法分析器，如：LEX 语法制导翻译引擎 可生成一组用于遍历分析树并生成中间代码的例程,编译程序生成,编译器构造工具,代码生成器的生成器 根据一组关于如何把中间语言的每个运算翻译成为目标机语言的规则，生成一个代码生成器。 数据流分析引擎 可帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。 数据流分析是代码优化的一个重要部分 编译器构造工具集 提供了可用于构造编译器的不同阶段的例程的完整集合。,编译程序生成,程序设计语言的发展历程,历程 第一代：机器语言 第二代：汇编语言（宏命令） 第三代：Fortran，Cobol，Lisp，C，C+， 第四代：特定应用语言：NOMAD, SQL, Postscript 第五代：基于逻辑和约束的语言，Prolog、OPS5 强制式语言/声明式语言 前者指明如何完成，后者指明要完成哪些计算 冯.诺依曼语言/面向对象的语言/脚本语言,语言范型及其举例,强制式语言 程序说明怎么做，如： C，C+，Java，C#等 声明式语言 程序说明做什么，如：Prolog ， ML ， Haskell等 面向对象语言 支持面向对象编程，如： C+，Java，C#，Ruby 脚本语言 具有高层次运算符的解释型语言 常用于把多个计算过程（脚本）“粘合”在一起 如：Javascript,VBscript,PHP,Python,Ruby等 特点：短,最新编程语言排名（Tiobe）,33,程序设计语言、计算机体系结构与编译器的关系,程序设计语言的新发展向编译器设计者提出新要求 设计相应的算法和表示方法来翻译和支持新的语言特征 多态；动态绑定；类；类属（模板）； 通过降低高级语言的执行开销，推动这些高级语言的使用 编译器设计者还需要更好地利用新硬件的能力 RISC技术、多核技术、大规模并行技术,1.6 程序语言基础,静态与动态的区别：决策在程序运行之前还是之后 静态：语言策略支持编译器静态决定某个问题 动态：只允许在程序运行时刻作出决定 Java类声明中的static指明了变量的存放位置可静态确定 作用域 x的作用域指程序文本的一个区域，其中对x的使用都指向这个声明。 静态作用域：通过静态阅读程序即可决定作用域（大多数语言，如如：C和Java） 动态作用域,环境与状态,1.6 程序语言基础,环境：从名字到存储位置的映射 状态：从内存位置到它们的值的映射,绑定,绑定（binding）是两个东西之间的关联 如：名字与存储位置（变量）、变量与值。 静态绑定：在程序运行前建立的约束 如：全局变量、static变量可以在编译时确定其存储位置；常量的值始终不变。 动态绑定：在程序执行过程中建立的约束 如：变量的值。,绑定,若C程序中有如下声明： #define ARRAYSIZE 100 那么： ARRAYSIZE=10是否正确？为什么？,名字、标识符和变量,标识符 字母串，常由字母开头，后跟若干个字母或数字 用于指称一个实体，如：数据对象、过程、类等 名字是 助记符，如：标识符，符号（） 程序语言里最基本的抽象机制 用来指称变量、常量、过程/函数、结构/记录的成分、类型等。 所有标识符都是名字，而名字不一定是标识符，它还可以是一个表达式，如： x.y是名字，但不是标识符！,1.6 程序语言基础,名字、标识符和变量,变量 指向存储中的某个特定的位置 注： 每次变量声明将引入一个新的变量（新存储位置） 递归过程中的局部变量在每次调用时占用的存储位置不同,1.6 程序语言基础,声明和定义,声明确定事物的类型 如：int i是一个i的声明 定义确定事物的值 如：i=1是i的一个定义（定值） C+中的方法： 在类定义中声明，说明其参数和返回值类型 在另一个地方通过代码执行该方法（定义）,1.6 程序语言基础,过程、函数和方法,一般地，过程、函数和方法可统称为“过程” 狭义的过程一般无返回值 但具体讨论某语言程序时可能有所差异，如： C语言只有函数，无返回值的函数设为void类型 Java只有方法，C+中也称方法 （OO语言） 方法总是和某个特定的类相关联,1.6.3 静态作用域和块结构,块：一组声明和语句 如：C语言的块语法：以开头、结尾，其内包含了一个声明序列，后跟一个语句序列 该语法允许一个块嵌套在另一个块内，这个嵌套特性称为块结构。 C族语言都具有块结构，但C语言不允许在一个函数内嵌套另一个函数,1.6.3 静态作用域和块结构,C语言的静态作用域策略 C程序由一个顶层的变量和函数声明序列构成 函数内部可以声明变量（局部变量或参数），其作用域为声明的那个函数内 在顶层声明的名字x，其作用域包括其后的所有程序。但若某个函数中也声明了x，则该函数的语句不在顶层声明的x的作用域。,作用域举例,1.6.3 静态作用域和块结构,变量声明的静态作用域规则,若块B是包含声明D的最内层的块，则称D属于B 变量声明的静态作用域规则 若名字x的声明D属于B，则D的作用域包括整个B，但不包括嵌套在其内、但重新声明了x的所有块B(作用域空洞）,Q:B4的输出结果？,块作用域的例子,1.6.4 显式访问控制,类和结构为其成员引入新的作用域 若p是一个类，x是其成员，则p.x引用的是该类定义中的成员x 类似块结构，类C的成员作用域可扩展到所有的子类C，除非C有对x的重新声明,1.6.4 显式访问控制,OO语言通过private, public和protected等关键字，提供对超类的成员名字的显示访问控制 Private:私有，作用域仅包含该类和“友类”相关方法声明和定义 Protected:受保护，可从子类访问 Public:公共，可从类外访问,1.6.5 动态作用域,如果一个作用域策略依赖于一个或多个只有程序运行时才能知道的因素，它就是动态的。 动态作用域中对一个名字x的引用指向的是最近被调用但还没有终止且声明了x的过程中的这个声明，如： C预处理器的宏扩展 面向对象编程中的方法解析,动态作用域举例宏扩展,动态作用域举例多态过程解析,多态过程：同名多定义（参数个数和类型不同）的过程 有些语言可静态确定名字的类型，编译器可把过程替换为对应过程代码的引用，如：ML 但其它语言中有些编译器有时不能作出这样的决定，如：Java和C+,动态作用域举例多态过程解析,正常情况下，编译时不能指出x引用的是类C的对象还是其子类D的对象 只有运行时才能确定应调用m的哪个定义 因此，编译器生成的代码必须决定对象x的类，并调用其中的x方法,参数传递,问题：程序中调用过程与被调用过程之间怎样进行信息交流？ 答：通过以下两种方式： 非局部变量 参数传递,参数传递方式,一传值 把实在参数的值传递给相应的形式参数 例：PASCAL值参数、C、Java 方法： 调用程序计算实参的值 被调用过程开始工作时，首先把实参的值抄入相应的形参单元； 被调用过程中，象引用局部数据一样引用形式单元。 特点：传递实参的副本,对形式参数的改变是针对本过程的形参单元进行的，对实参没有影响，在函数外不起作用。 例如，在C中： void inc2( int x) +x; +x; Mai