编译原理课件

1、编译原理课程信息n教学目的与要求：教学目的与要求： 编译程序是现代计算机系统的基本组成部分之一。本课程重点讲述编译程序的设计原理和常用实现技术。通过课程的学习和实验的完成，应该清楚的理解一个编译程序是如何工作的；如果在以后遇到了任何一个程序设计语言，应该知道如何实现这个语言的多数机制；应具有一定的使用编译构造工具开发编译程序的经验；会将所学的常用技术和算法应用于类似的软件的设计和实现中。 教材及主要参考书n教材：编译原理（第2版），张素琴、吕映芝、蒋维杜、戴桂兰，清华大学出版社 2004n参考书：Compilers: Principles, Technigues, and Tools Alfr

2、ed V.Aho, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley,1986. 影印版：人民邮电出版社，2001n参考书:程序设计语言 编译原理（第3版），陈火旺、刘春林等，国防工业出版社 2000n等等教学内容1 编译程序概述 编译程序是现代计算机系统的基本组成部分之一.编译程序一般由词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，目标代码生成程序，代码优化程序，符号表管理程序和错误处理程序等成分构成。本章概要介绍编译成分的主要功能以及编译阶段的逻辑关系。2 PL/0 编译程序剖析 给出一个简单的类Pascal语言，其编译程序用高级语言（

3、C和Pascal）实现。通过剖析该高级语言程序以理解各编译成分的功能及手工实现方法。教学内容3 高级语言的认识 要学习和构造编译程序，理解和定义程序设计语言是必不可少的。每个程序设计语言都有一定的规则用以规定合适程序的语法结构，也需要有对一个程序的含义的描述。上下文无关文法给出程序设计语言的精确的,易于理解的语法说明。尚没有公认的形式系统描述程序含义，但也有流行的描述语义规则的方法属性文法。4 词法分析程序的自动构造 词法分析程序是编译程序的一个构成部分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。正则表达式和有穷状态自动机分别作为单词的描述工具和识别机制，成为词法分析

4、程序的自动构造原理，学习Lex（Flex）工具的使用方法。教学内容5 语法分析程序的构造n自顶向下的语法分析。可以看作是为一个输入串寻找一个最左推导的过程,也等价于从根开始,按前序生成结点，为输入串构造分析树的过程。讨论一种有效的无回溯的自顶向下分析程序,这种分析程序称为预测分析程序。介绍对于一个文法类：LL（1）文法, 如何自动的构造预测分析程序。 n自底向上（自下而上）语法分析方法，也称移进-归约分析法。它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移进边分析，一旦栈顶符号串形成可归约串，就用相应非终结符代替可归约串，这称为一步归约，重复这一过程，直到归

5、约到栈中只剩文法的开始符号时，则为分析成功，并确认输入串是文法的句子。本章介绍LR分析法，分析过程中归约的是当前句型的句柄，称为规范归约。重点讲解LR类（LR（0）、SLR（1）、LALR（1）、LR（1）文法的分析表的构造原理。教学内容6 语义分析和中间代码生成 在词法分析和语法分析之后，编译程序下一个逻辑阶段的任务是语义分析和生成中间代码。引入属性文法和语法制导的翻译的概念，介绍中间代码的形式，针对一些语法成分讨论相应语义处理工作的描述。7 符号表 介绍符号表的一般组织和使用方法，讨论分程序结构语言的名字作用域分析及符号表设计方案。教学内容 8 运行时的存储组织和管理 编译的最终目标是生成

6、目标程序。在目标代码生成前，编译程序必须对目标程序运行时的数据空间进行组织和安排. 介绍目标程序运行时的数据空间的存储分配策略，说明程序设计语言本身关于名称的作用域和生存期的规则与存储分配策略的关系，重点讨论栈式动态存储方案.教学内容9 代码优化和目标代码生成 代码优化是对代码作一些等价变换，以使得最后生成的目标代码更为高效。介绍优化技术，优化分类以及优化工作的基础控制流和数据流分析问题。 编译的最后一个逻辑阶段是目标代码生成。目标代码生成程序的设计细节要考虑目标语言和操作系统的特点。讨论目标代码生成程序设计的一般问题，包括指令选择，寄存器分配和计算顺序选择。第1章 概述1.1 什么是编译程序

7、1.2 程序设计语言的实现1.3 处理源程序的软件工具1.4 编译技术的发展 1.1什么是编译程序(compiler) 编译程序是现代计算机系统的基本组成部分. 从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序. 什么是编译程序什么是编译程序功能术语术语编译程序的源语言(源程序)编译程序的目标语言(目标程序)编译程序的实现语言S OI 高级语言书写的程序 编译程序低级语言程序S TI 什么是编译程序n分类 软件 系统软件 语言处理系统操作系统编译系统裸机分类n软件：计算机系统中的程序及其文档n系统软件：居于计算机系统

8、中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。n语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。n软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。什么是编译程序n语言转(变）换系统C+编译器C+CJavaBytecodeJava编译器术语n编译程序(compiler)n编译程序的源语言(源程序) (source language)(source program)n编译程序的目标语言(目标程序) (object or target language)(object

9、 or target program) n编译程序的实现语言(implementation language)n语言处理程序(language processor)n语言转（变）换(language transformation)编译逻辑过程n词法分析n语法分析n语义分析n中间代码生成n代码优化n目标代码生成词法分析第一步识别单词 英文句子由单词构成 This line is a longer sentence.（字母组成的有集体含义的最小成分）n 句子开头的单词第一个字母要大写n 空格是单词分隔符n 句点是句子结尾 中文分词？汉语编程？语言的发展？无鸡鸭也可无鱼肉也可惟青菜豆腐不可少不得学费

10、无鸡鸭也可无鱼肉也可惟青菜豆腐不可少不得学费 词法分析从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出(拼)一个个的单词（符号） 单词符号是语言中具有独立意义的最基本结构。多数程序语言中，单词符号一般包括 各类型的常数、保留字、标识符、运算符、界符等等。例如例如 double f = sqrt(-1);词法分析double f = sqrt(-1); T D O U B L E ( “ d o u b l e ” )TIDENT (“f”)TOP (“=“)TIDENT (“sqrt”) TLPAREN (“(“) TOP (“-”)T I N T C O N S T A N T (

11、 “ 1 ” )TRPAREN (“)”)TSEP (“;”)词法分析n词法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and grouped into tokens, which are sequences of characters that have a collective meaning.n单词-tokenn保留字-reserved wordn标识符 -identifier(user-defined na

12、me)例n程序文本If x = y then z := 1 else z := 2;经词法分析，变成一个个单词nif, x, =, y, then, z, n:=, 1, else, z, :=, 2, ;n语言的单词符号是由词法规则所确定的。词法规则规定了字母表中哪样的字符串是一个单词符号。词法分析position := initial + rate * 60;单词类型单词类型单词值单词值 标识符1(id1) position 算符(赋值) := 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号 ；语法分析 Syntax An

13、alysis功能:层次分析.依据依据源程序的语法规则语法规则把源程序的单词序列组成语法短语(表示成语法树).n也称为 “parsing”n使用 context-free grammarsn结构上的合法性Structural validation（可生成语法树或推导Creates parse tree or derivation）This line is a longer sentence分析程序成分 double f = sqrt(-1); “sqrt(-1)”的推导Expression FuncCall TIDENT TLPAREN Expression TRPAREN TIDENT TLP

14、AREN UnaryExpression TRPAREN TIDENT TLPAREN TOP Expression TRPAREN TIDENT TLPAREN TOP TINTCONSTANT TRPAREN规则规则Expression - UnaryExpressionExpression - FuncCallExpression - TINTCONSTANTUnaryExpression - TOP ExpressionFuncCall - TIDENT TLPAREN Expression TRPARENdouble f = sqrt(-1);的的Parsing ？n语言的语法规则规

15、定了如何从单词符号形成更大的结构（即语法单位） 语法分析n又例：position := initial + rate * 60 ;（Pascal）规则）规则 :=“:=” :=“+” :=“*” :=“(”“)” := := := 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*id1:=id2+id3*N:=+N 60*id1 Positionid2 initialid3 rate语法分析n语法分析(syntax analysis or parsing)The purpose of syntax analysis is to determine the source pr

16、ograms phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.n语法树(推导树)(parse tree or derivation tree)语义分析n 句子的结构理解了，扑捉它的“含义” 如：杰克说杰瑞把他的作业落在了家里。 “

17、他的”是谁的？ 又：杰克说杰克把他的作业落在了家里。 几个杰克？语义分析n杰克把她的作业落在了家里。（杰克是男生）“杰克”和“她的”不一致。 “杰克”和“他的”才匹配程序设计语言靠严格的约束规则解决二义。 int jack=3; int jack=4; cout = n) j = 2 * i + 3;return aj;t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6中间代码(intermediate code) Intermediate code is

18、 a intermediate representation of the source program . We want this representation （ intermediate representation） to be easy to generate, and easy to translate into the target program. The representation can have a variety of forms, a common one is called three-address code or 4- tuple code.不同层次的中间代

19、码源语言源语言（高级语言）（高级语言）中间代码中间代码（高级）（高级）中间代码中间代码（中级）（中级）中间代码中间代码（低级）（低级）float a1020;aij+2;t1 = ai, j+2t1 = j + 2t2 = i * 20t3 = t1 + t2t4 = 4 * t3t5 = addr at6 = t5 + t4t7 = *t6r1 = fp - 4r2 = r1 + 2r3 = fp - 8r4 = r3 * 20r5 = r4 + r2r6 = 4 * r5 r7 = fp 216f1 = r7 + r6代码优化Code Optimization应用一些技术对代码进行变换以使

20、得编译产生的目标代码高效。nExample（中间代码一级）t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6t1 = 2 * ij = t1 + 1t3 = j nif t3 goto L0 j = t1 + 3L0: t6 = ajreturn t6代码优化id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360

21、.0t1) ( 2）（ + id2 t1id1)目标代码生成(*,id360.0t1)(+,id2t1id1)movid3,R2mul#60.0,R2movid2,R1addR2,R1movR1,id1编译程序的工作编译程序的工作n分析(analysis)和综合(synthesis) 源程序的分析 线性分析 层次分析 语义分析 目标程序的综合n编译阶段的划分编译阶段的划分前端（front end）和后端（back end） 编译的前端 与源语言有关但与目标机无关的那些部分组成 编译的后端 与目标机有关的那些部分组成n遍（趟）遍（趟）从头到尾扫描源程序（各种形式）一遍遍(pass)编译程序结构(

22、components)n词法分析程序n语法分析程序n语义分析程序n中间代码生成程序n代码优化程序n目标代码生成程序n符号表管理程序n出错处理程序出错处理程序语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理程序符号表n记录源程序中使用的名字n收集每个名字的各种属性信息 类型、作用域、分配存储信息 name: I kind：常量 value：35 name:object kind：变量 type：实 level：2 add: dx符号表管理(登录，查找）symbol table management出错处理(error handling ）检查错误、报告出错

23、信息、排错、恢复编译工作(error reporting and error recovery)早期的出错管理（复杂、低效）1.2程序设计语言的实现有些语言基本通过解释程序 Java的Bytecode有些环境同时提供编译程序和解释系统 Lisp 主要的途径有两个：通过编译程序和解释程序 编译程序低级语言程序高级语言程序高级语言程序 解释程序计算结果编译程序和解释系统如对源程序： b := 2 ; a := b+2 ; 编译程序编译程序 write a ; 解释程序解释程序 直接将4的值输出（显示）（直接对源程序中的语句进行分析，执行其隐含的操作。）Int 2St bLd badd 2St a生

24、成代码编译程序和解释程序编译程序是一个语言处理程序,它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序, 这个二进制代码程序在机器上运行以生成结果.因此通过编译程序使得我们可以先准备好一个在该机器上运行的程序,然后这个程序便会以机器的速度运行.但是在不把整个程序全部都翻译结束之后,这个程序是不能开始运行,也不能产生任何结果的.编译和运行是两个独立分开的阶段.但在一个交互环境中,不需要将这两个阶段分隔开,编译就不如解释的方法更方便. 另一种语言处理程序,解释程序,它不需要在运行前先把源程序翻译成目标代码,也可以让我们实现在某台机器上运行程序并生成结果.解释程序解释程序n是这样一个程序,它接

25、受某个语言的程序并立即运行这个源程序.它的工作模式是一个个的获取,分析并执行源程序语句,一旦第一个语句分析结束,源程序便开始运行并且生成结果, 它特别适合程序员交互方式的工作情况,即希望在获取下一个语句之前了解每个语句的执行结果,允许执行时修改程序.n著名的解释程序有Basic语言解释程序 ,Lisp语言解释程序,UNIX命令语言解释程序(shell),数据库查询语言SQL 解释程序以及bytecode解释程序.高级语言解释系统(interpreter)n功能 让计算机执行高级语言（basic,lisp,prolog)n与编译程序的不同 1）不生成目标代码 2）能支持交互环境 （同增量式编译系

26、统） 源 程 序 初始数据 解释程序计算结果编译程序和解释程序的存储组织也有很大不同n编译程序处理时,在源语言程序被编译阶段编译阶段,存储区中要为源程序(中间形式)和目标代码开辟空间,要存放编译用的各种各样表格,比如符号表.在目标代码运行目标代码运行阶段,存储区中主要是目标代码和数据,编译所用的任何信息都不再需要.n解释程序一般是把源程序一个语句一个语句的进行语法分析,转换为一种内部表示形式,存放在源程序区,比如BASIC解释程序,将LET和GOTO这样的关键字表示为一个字节的操作码,标识符用其在符号表的入口位置表示.因为解释程序解释程序允许在执行用户程序时修改用户程序,这就要求源程序源程序,

27、符号表等内容始终存放符号表等内容始终存放在存储区中在存储区中,并且存放格式要设计的易于使用和修改并且存放格式要设计的易于使用和修改. 编译阶段和运行阶段存储结构 编译时 运行时 名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区解释系统存储结构解释系统源程序临时工作单元名字表标号表缓冲区(输入输出)栈区语言处理过程语言处理过程C程序# include # include # define MAX_LINES 75Enum booleans (FALSE,TRUE);Main (int argc,char *argv*) n预处理器编译器汇编器装配连接编辑骨架程序 源程

28、序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库语言处理过程语言处理过程1.3 处理源程序的软件工具处理源程序的软件工具 （编译技术的应用）n结构化编缉器n程序分析工具 静态分析 动态分析 度量工具 结构度量 模块接口复杂度 c分析工具(source insight) n广泛的语言领域 数据库系统查询（SQL） 脚本语言 置标语言(SGML.HTML.XML)1.3处理源程序的软件工具处理源程序的软件工具1.语言的结构化编辑器语言的结构化编辑器2.语言程序的调试工具语言程序的调试工具3.程序格式化工具程序格式化工具4.语言程序测试工具语言程序测试工具5.程序理解工具程序理解工具

29、6.高级语言之间的转换工具高级语言之间的转换工具1.语言的结构化编辑器语言的结构化编辑器 用户可使用该编辑器在语言的语法制导下编制出所需的源程序。结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。因此，结构化编辑器能够执行一些对编制程序有用的附加的任务。例如，它能够检查用户的输入是否正确，能够自动地提供关键字,当用户敲入if后，编辑器立即显示then并将这两个关键字之间必须出现的条件留给用户输入，并能检查begin或左括号与end或右括号是否相匹配等等。由于结构化编辑器具有上述功能，既可保证编出的源程序无语法错误，并有统一的可读性好的程序格式

30、，这无疑将会提高程序的开发效率和质量。 商用产品很多如Turbo-Edit,Editplus和Ultraedit等等.很多集成开发环境中里也都包含这种类似的工具,如Jbuilder中就有JAVA程序的结构化编辑器.2.语言程序的调试工具语言程序的调试工具 调试是软件开发过程中一个重要环节，结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致，程序的执行是否实现预计的算法和功能。这种对算法的错误或程序没能反映算法的功能等错误就需用调试器来协助解决。n有一种调试器允许用户使用源程序正文和它的符号来调试,即一行一行的跟踪程序,查看变

31、量和数据结构的变化以进行调试工作.当然,这些符号的信息必须由编译程序提供.调试器的实现可以有很多途径.n其中一种是写一个解释器,以交互的方式翻译和执行每一行,它必须维护其所有的运行时的资源以保证在程序执行期间很容易的查询不同变量的当前值.n如果不想通过解释程序允许编译了的代码调试,编译程序必须在目标代码(汇编)生成时同时生成特定的调试信息,比如,关联标识符和它表示的地址的信息,用于无歧义的引用一个声明了多次的标识符的信息等等.调试功能愈强，实现愈复杂，它涉及源程序的语法分析和语义处理技术。3.程序格式化工具程序格式化工具程序格式化工具分析源程序并以使程序结构变得清晰可读的形式打印出来。例如，注

32、释可以以一种专门的字形出现，且语句的嵌套层次结构可以用缩排方式（齿形结构）表示出来。4.语言程序测试工具语言程序测试工具 语言程序的测试工具有两种：静态分析器和动态测试器。 静态分析器静态分析器是在不运行程序的情况下对源程序进行静态地分析，以发现程序中潜在的错误或异常.它对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系。如某变量未被赋值就被引用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误。 动态测试工具动态测试工具也是首先对源程序进行分析，在分析基础上将用于记录和显示程序执行轨迹的语句或函数插入到源程序的适当位置，并用测试用例记录和显示程序运行时的实际路

33、径,将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。5.程序理解工具程序理解工具对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户理解程序。6. 高级语言之间的转换工具高级语言之间的转换工具 由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好条件，然而一些已有的非常成熟的软件如何在新机器新语言情况下使用呢?为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题。这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另

34、一种高级语言而已。这与实现一个完整的编译程序相比工作量要少些。 比如：C，PASCAL，FORTRAN到Ada的翻译器 IBM 4700汇编到C的转换器 COBOL 到Java 的编译器 Human-orientedlanguageComputer-orientedlanguage计算模式，语言范式语言应用领域编译程序万诺曼机体系结构并行体系结构嵌入系统1.4 编译技术的发展S OI高级程序语言v不同的应用侧重:数值计算- Fortran 系统程序设计-C事务处理-obol VLSI设计-VHDL人工智能-rolog 其它-大型嵌入式实时处理-da 符号处理-nobolv语言范型:强制式语言-

35、C,Fortran,Pascal应用式(函数式）语言-ML，Lisp基于规则(逻辑）的语言-Prolog,Yacc面向对象语言-Ada,C+,Java强制式语言（Imperative Language）也称过程式语言。 其特点是命令驱动，面向语句，一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式； 语句1；语句2；语句3；语言执行的解释与万诺曼机的体系结构对应：改变机器状态（内存，各种寄存器和外存的内容） 应用式（函数式）：应用式语言（Applicative Language）更注重程序所表示的功能，而不是一个语句接一个语句地

36、执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。程序执行： 执行一个个函数施用在数据上的变换最终得到的结果Example: 解决八皇后问题的一段Haskell98程序：queen 0 = queen (n+1) = x :y | y - queen n, x - 1.8, safe 1 x ysafe n x = Truesafe n x (z :y) = and x/=z, x/=z +n, x/=z -n, safe (n+1) x y-test = queen 8len = length test -92 right answer! 基于规则的语言( Rule-based Language)这类语言的语法形式