编译原理复习清华吕映芝.ppt

编译原理,清华大学计算机科学与技术系 吕映芝 2003.9.9,第1章 编译程序概论,1.1 什么是编译程序1.2 翻译和解释1.3 编译过程和编译程序的结构*1.4 编译程序的实现途径1.5 编译技术在其它软件中的应用 有关学习问题 参考书,1.1 什么是编译程序,语言和翻译：语言是人类交流思想和信息的工具。从自然语言来说，世界上存在着许多种语言，各国之间要交流信息,就要有各种语言之间的翻译。编译程序：编译程序就是一个语言的翻译程序,是把一种语言（称源语言）书写的程序翻译成另一种等价功能语言（称目标语言）的程序。换句话说，编译是指把一种用源语言表示的算法转换到另一种等价的用目标语言表示的算法。,1.1 什么是编译程序,编译程序的必要性：计算机是当代科学发展的重要工具，已渗入到各行各业乃至家庭生活中。所以如何让他为人类工作服务，就必须建立人与计算机之间的信息交流。但计算机只认识由“0”和“1”构成的机器语言，并不认识C、C+、Java、Pascal等高级程序设计语言。每台计算机都有自己独特的指令系统，即机器语言，最早的程序就是用8进制和16进制码的机器语言书写的。,1.1 什么是编译程序,用机器语言书写程序，不仅不易学，而且可调试性、可读性、可维护性和结构性都很差，开发时间也很长。因此，编译程序最初的定义是把一种高级程序设计语言的源程序（面向人的）翻译成另一种等价的低级程序设计语言（面向硬件的）即机器语言或汇编语言。所以，编译程序是人用某种语言书写的某个翻译程序。,1.1 什么是编译程序,编译程序的功能,S:源语言(程序)O:目标语言(程序)I:实现语言,用T型图 表示,1.1 什么是编译程序,随着计算机及其应用的发展，出现了各种应用更方便的高级语言，如:FORTRAN、PL/1、ALGOL 60、COBOL、PASCAL、Ada、LISP、C、C+、JAVA等。早期开发的软件需转换，因此，编译程序不仅是高级语言翻译成机器语言，广泛地讲：编译程序高级语言低级语言 高级语言 高级语言 高级语言 中间语言 中间语言 低级语言,1.1 什么是编译程序,例：高级语言 高级语言 FORTRAN PASCAL C JAVA PL/1 C+COBOL,C,Ada,JAVA,1.1 什么是编译程序,逆向工程 低级语言 高级语言例：IBM/4700（汇编语言）C交叉编译 在一个机器上对某种高级语言进行编译，产生的目标语言是另一个机器的汇编语言或机器语言。例：在WAX机上编译Ada语言，产生PC机的汇编语言，这样的目标语言只能在PC机上运行，如嵌入式系统对交叉编译的应用。当功能相同时，不同语言之间的区别，只是语言的词法、语法和语义规则形式不同。运行环境也可能不同。,例：计算园面积,C 程序：function circle();int r;float s;scanf(“%d”,Pascal 程序：procedure circle;var r:integer;s:real;begin read(r);s:=3.1416*r*r;write(s);end;,1.2 翻译和解释,翻译：按源程序的实际输入顺序，处理程 序语句，得到可执行的目标程序。解释：按源语言的定义边解释边执行。解释执行是按照被解释的源程序的逻辑流程进行处理的，不产生目标程序。,解释程序,源程序,输入,输出,解释,解释执行优点：交互方便，节省空间。缺点：效率低。因对源程序的循环语句部分要反复解释执行。共同点：都需进行词法、语法、语义分析。可比喻为：,翻译（编译）-笔译（产生目标程序）解释-口译（不产生目标程序）,1.3 编译过程和编译程序结构,编译过程编译程序结构编译的趟（遍）(pass),编译过程,词法分析语法分析语义分析中间代码生成代码优化目标代码生成,词法分析,读字符流的源程序、识别单词例：position:=initial+rate*60;（转换为内部表示，拼标识符、数和复合单词等）单词类型 单词值 标识符（1）position 算符(赋值号):=（复合单词）,词法分析,单词类型 单词值 标识符（2）initial 算符(加号)+标识符（3）rate 算符(乘号)*整数 60 界符（分号）；,语法分析,功能：层次分析，把源程序的单词组成语法短语(表示成语法树或其它内部码)。现用“巴科斯-瑙尔范式”（EBNF）描述。例:=:=:=+:=*:=“(”“)”:=:=,语法分析（语法树）,语义分析,语义审查,静态语义检查上下文相关性如：类型匹配和类型转换,例:Program p();var rate:real;procedure initial;position:=initial+rate*60;/*error*/,类型匹配错误,语义分析,类型转换,中间代码生成,源程序的内部(中间)表示结构简单、含义明确的记号系统，介于高级语言与低级语言之间,与目标机无关，便于优化、移植并容易生成目标代码。通常的中间代码有三元式、四元式、树结构或适合相应语言的中间代码。例：P-Code、C-Code、bytecode等。,中间代码生成（四元式）,例：id1:=id2+id3*60；翻译成四元式四元式：3地址（操作符，操作对象1，操作对象2，操作结果）(1)(inttoreal60t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3id1),代码优化,代码优化：是对中间代码进行等价变换，以提高目标代码的时、空效率例：上面的4条指令可变成2条，并且节省2 个工作单元。(*id360.0 t1)(+id2t1id1),目标代码生成,(*id360.0t1)(+id2t1id1),movf id3,R2mulf#60.0,R2movf id2,R1addf R2,R1movf R1,id1,R1、R2是寄存器,符号表管理,记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息,Const 常量 值：35Var变量 类型：int 层次：2 地址：dx+5,CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G,表格管理(以PL/0为例）,名字 类型 层次/值 地址 存储空间,Const（常量）无层次,出错处理,编译的任何时候都可能发现源程序中的错误。检查词法、语法和语义中的错误（静态）。编译程序的处理能力，如存储空间越界（动态）报告出错信息和位置处理和恢复,编译程序结构,词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错管理程序,出错处理,表格管理,目标代码,源程序,编译的趟（遍）(pass),从头到尾对源程序或各种形式的中间表示 进行扫描，称为一遍编译的前端（front end）中间代码生成后（代码优化后）编译的后端（back end）目标代码生成开始从源程序扫描是第一遍的输入每前一遍的输出是后一遍的输入分遍的原则按实际情况而定,1.4 编译程序的实现途径,应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性和可扩充性等。构造方式：手工构造：用机器语言、汇编语言或高级程序设计语言书写。自动构造工具：Lex,Yacc。Lex,Yacc分别 是词法和语法分析器的生成器。移植方式：目标程序用中间语言自展方式：用T型图表示,1.4 编译程序的实现途径,自展方式：步骤 1：,(1),(2),(3),实现目标,注释：PC表示PC机的机器语言或汇编语言 C1、C2是C的子集，C1 C2,自展方式,步骤 2：,步骤 3：,1.5 编译技术在其它软件中的应用,软件测试工具 如：FORTRAN，C的静态和动态测试工具（可测试程序的语句覆盖率，路径覆盖率等）高级程序设计语言的转换网络中的协议数据库系统中各种命令语言的翻译各种软件支持环境,编译程序在系统软件中的所在层,操作系统语言处理系统 应用软件层,应用软件层,复习讨论：,1.编译程序由哪些部分组成?说明每个部分的功能。2.如果在PC机上只有C语言,现在要求实现PASCAL语言，你用什么办法做更好？（最好不用汇编语言编写）3.编译的前端和后端如何划分?4.翻译(编译)和解释的区别是什么?各自的优、缺点是什么？,有关学习问题,教学内容和学习目的学习要求和学习方法,教学内容,(1)编译程序概述(2)PL/0编译程序（读懂文本，扩充功能）(3)语言和文法(4)词法分析和有限自动机(5)自顶向下语法分析方法*(6)自底向上算符优先分析法(7)自底向上LR分析法(8)语法制导翻译和中间代码生成(9)目标程序运行时的存储空间组织*(10)代码优化,学习目的,近年来，信息技术的迅猛发展，对软件技术和软件工具的需求急剧增加，编译技术已大量应用于各种各样软件工具的研制和开发中。从各种语言的结构化编辑器、分析器和语言的解释系统到嵌入式软件，交叉编译器；从传统的强制式的程序设计语言到应用式、面向对象的语言的编译；从一般的批处理环境到交互环境及分布式环境等等；技术需求越来越大，涉及面越来越广。因而，广大从事计算机系统软件和应用软件研制及开发人员对编译技术深入了解的要求越来越高。,学习要求和学习方法,目前，编译系统的构造在理论上有较成熟的体系支持，实现技术也很丰富多样。但要使学生通过该课程的学习从理解原理、掌握技术到自己设计和实现一个完整的编译程序，难度很大，因为课程内容广泛，涉及到数据结构、操作系统、离散数学及语言理论，是综合性很强的一门课程。从抽象形式语言与自动机的概念，到具体构造实现的复杂性，学生都必须理解原理掌握技术。,学习要求和学习方法,学时：课内48，课外80学好原理和构造技术（1）需做相当量作业，巩固课堂知识（2）理论联系实际，做好实验,实验要求,必做题目 65%扩充条件语句条件语句:=IF条件THEN语句ELSE语句 扩充重复语句重复语句:=REPEAT语句；语句UNTIL条件 选做题目用C语言改写PL/0编译程序；80%用Java语言改写PL/0编译程序；80%,实验要求,对PL/0语言扩充整形数组（尽量做此题）。95%讨论：分成3人一组做扩充整形数组，开展讨论、相互学习，培养团队精神。其他选做学完语法分析后可用LL（1）或LR语法分析方法改写PL/0编译程序的某些部分用LEX、YACC编写一个小型的编译器（要求见编译原理实验2）用LEX、YACC改写PL/0编译程序 适当加分,实验要求,实验报告内容:（1）对扩充部分用语法图和EBNF描述；（2）对程序变动部分的说明；（3）所用测试用例；（4）实验体会和建议。,参考书,吕映芝，张素琴，蒋维杜.编译原理.清华大学出版社.1998Tomas Pittmn,The art of Compiler Design theory and Practice,Prentice-Hall 1992Charles N.Fischer,Richard J.Leblanc,Crafting A Compiler,The Benjamin/Cummings Publishing Company 1988ALFRED V.AHO,RAVISETHI,JEFFREY D.ULLMAN,Compilers Principles,Techniques and Tools ADDISSON-WESLEY 1986教材后所列其它参考,第2章 PL/0编译程序的实现,本章目的：以PL/0语言的编译程序为实例,学习一个编译程序实现的基本步骤和相关技术,“PL/0语言的编译程序”是世界著名计算机科学家N.Wirth先生编写的。由于PL/0语言功能简单、结构清晰、可读性强，而又具备了一般高级语言的必须部分，因而PL/0语言的编译程序能充分体现一个高级语言编译程序实现的基本技术和步骤。是一个非常合适的小型编译程序的教学模型。,第2章 PL/0编译程序的实现,通过本章的学习可达到：对编译程序的构造得到一些感性认识和初步了解对编译程序的实现建立起整体概念为系统地学习本课程以下各章节打好基础 为了读者能较好地阅读PL/0语言编译程序文本。本章将对PL/0语言编译程序的实现过程作概括的分析说明。对PL/0语言文法的表示只给出语法图和扩充的巴科斯-瑙尔范式(EBNF)的描述形式，不作文法理论上的讨论。,第2章 PL/0编译程序的实现,功能,PL/0编译程序,PL/0 语言,类 pcode,源语言(PL/0)目标语言(类 pcode)实现语言（pascal),PL/0,类 pcode,pascal,类 pcode是中间代码Pcode是适合pascal的中间代码,PL/0编译程序,类 pcode解释程序,类 pcode代码,PL/0源程序,输入,输出,PL/0编译程序功能的框架,第2章 PL/0编译程序的实现,步骤1.认识源语言PL/0与目标代码类pcode 及它们之间的映射步骤2.PL/0编译程序的总体设计步骤3.PL/0编译程序词法分析的设计与实现步骤4.PL/0编译程序语法语义分析的设计与实现步骤5.PL/0编译程序代码生成的实现*步骤6.PL/0编译程序错误处理的实现步骤7.类pcode代码解释器的设计与实现,练习,见教材26-27页1.2.3.4.5.6.(2),(3),第3章文法和语言,3.1 文法和语言概述3.2 文法和语言的形式定义3.3 文法的类型（重点是二型和三型）3.4 上下文无关文法及其语法树3.5 句型的分析3.6 有关文法实用中的一些说明,3.1 语言文法概述,本章目的语言概述语言的一般描述文法的直观概念,本章目的,本章目的是为语言的语法描述寻求工具，是本课程的理论基础。通过描述工具，可以：对源语言给出精确无二义的语法描述。（严谨、简洁、易读）根据语言文法的特点来指导语法分析的过程从描述语言的文法可以自动构造出可用的分析程序(如：第13章介绍的基于LALR(1)文法的yacc和基于LL(2)文法的SD&EBNF_LL(2)制导语义翻译,语言概述,语言是由句子组成的集合，是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体 每个句子构成的规律研究语言 每个句子的含义 每个句子和使用者的关系,语言概述,语言研究的三个方面:语法（Syntax）-表示构成语言句子的各个记号之间的组合规律语义（Semantics）-表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用（Pragmatics）-表示在各个记号所出现的行为中，它们的来源、使用和影响。（本章不做进一步的介绍）,语言概述,形式语言理论（formal language theory）：是一种从语法上研究语言的理论。它是抽象的数学系统，着重研究符号串集合的表示法、结构及其特性。是程序设计语言语法分析研究的基础。（本章仅使用其与编译程序构造有关的结论，而不做证明）形式语义（formal semantics）：（本课程不介绍）。,语言的一般描述,语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。一些基本概念,文法的直观概念,句子的产生:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|,文法的直观概念,（用“”表示推导）我 我 我是 我是 我是大学生,练习,教材 4546页 5.7.9.11.13.(3)14.(1),(2)16.(2),(3),4.1 词法分析程序4.2 正规表达式、*正规文法与正规集4.3 有穷自动机4.4 正规表达式和有穷自动机*4.5 有穷自动机和正规文法,第4章 词法分析,设计词法分析程序单词的描述工具单词的识别系统,4.1 词法分析程序,词法分析（lexical analysis）词法分析是逐个读入源程序字符，并按照构词规则分割成一系列单词，再转换成词标流的过程。单词是语言中具有独立意义的最小单位，包括保留字、标识符、常量、运算符和界符等。词标是单词的机内表示，其格式由实现系统规定。例如：PL/0语言的单词 用户写的if a=2.机内表示为ifsym ident eql number。,4.1 词法分析程序,词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为单独的一遍，将源程序转换成词标流供下一遍使用。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序，获得当前词标,供语法分析程序使用。如PL/0语言编译程序的实现就是把词法分析和语法分析结合在一起作为一遍。,4.1 词法分析程序,在词法分析程序的实际实现中，首先需要描述和刻画语言中的最小单位单词，其次需要识别单词和执行某些相关的动作。程序设计语言词法的描述和识别机制是：描述机制用3型文法和正规表达式；识别机制用有穷状态自动机。在词法分析过程中，与语法分析无关的符号应预先处理。如为提高易读性增加的注释，与语法语义分析无关，无需产生相应的词标，处理时应滤掉。,4.1 词法分析程序,源程序,词法分析程序,语法分析程序,Token,get token,主要任务：读源程序(字符流)，产生单词符号（词标流）其他任务：滤掉空格、跳过注释和换行符,追踪换行标志，复制出错源程序，宏展开等。,4.1 词法分析程序,单词符号一般可分为下列五种：基本字(关键字或保留字)标识符常数（常量）运算符界符,4.1 词法分析程序,输出表示（单词种别，单词自身的值）。词法分析工作独立的原因：简化设计提高编译效率增加编译系统的可移植性,练习,教材第6667页4.7 练习 的 1.(1)3.4.(b)*5.*8.,第5章 LL(1)文法及其分析程序,5.1 语法分析（回顾）(自顶向下分析的一般过程和问题)5.2 LL(1)文法的定义 FIRST集和FOLLOW集的定义和计算 LL(1)文法的定义 非LL(1)文法的改造5.3 LL(1)分析程序的实现,5.1 语法分析（回顾）,句型、句子和语言的定义句型:有文法G s，若S x，且xV*，则称x是文法G的句型。句子:有文法Gs，若S x，且xVT*，则称x是文法G的句子。例：Gs：S0S1，S01 S 0S1 00S11 000S111 00001111,仅有00001111是句子,5.1 语法分析（回顾）,最左（最右）推导：在推导的任何一步(其中、是句型)，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。,句型的分析,句型分析 就是识别一个符号串是否为某文法的句型，也就是某文法的某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序 或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。,句型的分析,分析算法可分为：自顶向下（自上而下）分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的推导。自底向上（自下而上）分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程,自顶向下（自上而下）的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SSScAdcAd a b推导过程：S cAd cabd,自底向上（自下而上）的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,S A A c a b d c a b d c a b d 归约过程：S cAd cabd,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？在自顶向下的分析方法中，假定要被替换的最左非终结符号是V，且V为左部有n条规则：VA1|A2|An，那么如何确定用哪个右部去替换V？如：前例中 A ab|a2）如何识别可归约的串？在自底向上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到某个非终结符号，该子串称为“可归约串”，归约就是用非终结符号替换它。,练习,教材 90 页 1.3.7.（2）,（3）,第6章 自底向上的优先分析法,自底向上语法分析概述*6.1 自下而上的优先分析法概述（不介绍）*6.2 简单优先分析（不介绍）6.3 算符优先分析（本章重点）,自底向上语法分析概述,自底向上语法分析是试图将一个输入符号串反向归约至语法的开始符号，在每一步中如何选择可归约子串进行归约？常用的两种方法是：算符优先分析法LR分析（第7章详细介绍）自底向上语法分析比自上而下语法分析更有效率，特别是某些LR分析法对语法的限制更少。,6.3 算符优先分析,某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性只考虑算符之间的优先关系来确定可归约串（广义讲终结符为算符）,练习,教材116页1.(1)、（2）、（4）2.（1）,第7章 LR分析程序及其自动构造,7.1LR分析概述7.2LR(0)分析7.3SLR(1)分析*7.4LR（1）分析*7.5LALR(1)分析7.6二义性文法在LR分析中的应用7.7LR分析程序的自动生成,7.1 LR分析概述,一般移进-归约分析过程LR分析器模型和分析算法LR分析特征讨论,7.1 LR分析概述,例6.1 GS为：（1）S aAcBe（2）A b（3）A Ab（4）B d,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1）#abbcde#移进,2）#a bbcde#移进,4）#aA bcde#移进,6）#aA cde#移进,7）#aAc de#移进,9）#aAcB e#移进,11）#S#接受,符号串abbcde是否是GS的句子,对输入串abbcde#的移进-归约分析过程,7.1 LR分析概述,在步骤3中，用Ab归约在步骤5中，用AAb归约问题：何时移进？何时归约？用哪个产生式归约？,LR分析器模型,input xxx#,练习,教材151154中的1.2.6.*8.16.,第 8 章 语 法 制 导 翻 译 和 中 间 代 码 生 成,8.1概 述8.2 简单赋值语句的(四元式）翻译8.3 控制语句中布尔表达式的翻译,条件语句执行的流程图和代码结构,流程图,代码结构,注意流程图和语法图的区别,真假出口链和反填真假出口的次序。,练习,教材 188页 1.(1),(3)2.*5.补充:给出下题的四元式序列，真假出口链和反填真假出口的次序。If a0 or(b0 and b9)then s:=(a+b)*c else s:=a*b*c;,第10章 目标程序运行时的存储组织,101 概述10.2 简单的栈式存储分配方案103 嵌套过程的栈式存储分配方案*104 分程序结构的存储分配方案105 参数传递,101 概述,任务：编译程序对目标程序运行时的数据空间的组织和管理（设计运行环境和分配存储）如栈式存储分配通常可布局为：,目标代码区 静态数据区 Stack heap,运行环境和存储分配设计分析,逻辑上看，在目标代码生成前，编译程序必须进行目标程序运行环境和数据空间的分配设计，为目标代码生成作准备。实质是解决关联问题：将源程序的文本 程序与运行动作的实现所需的存储空间联系。如：源文件中用户定义的数据对象的名字N，对应运行时的存储单元S;运行管理所需空间。,运行环境和存储分配设计分析,(如pl/0的变量名对应在运行栈中一个存储单元用于存放运行时变量的值）运行时的临时工作单元及存储管理所需的存储空间等。源文本中同样的名字 可对应目标程序中不同的数据空间，因为如果一个过程允许被递归调用，这时同一个名字在不同的时间可能代表不同的存储单元。,练习,教材234页6.10.,第11章 代码优化,111 什么是代码优化112 局部优化113 控制流程分析和循环优化*114 数据流分析（不介绍）,111 什么是代码优化,宗旨：等价、高效（运行速度快、存储空间少）意图，结果，权衡阶段：source I.R target codeCode 用户 中间代码优化 目标代码优化优化分类按阶段分成:(1)与机器无关的优化,对中间代码进行(2)依赖于机器的优化,生成目标代码时进行,Frontend,code generator,111 什么是代码优化,根据优化所涉及的程序范围分成:(1)局部优化:在基本块内部进行优化(2)循环优化:对循环中的代码进行优化*(3)全局优化:大范围的优化优化工作的基础*（1）数据流的分析*（2）控制流的分析,111 什么是代码优化,优化技术简介1.删除多余运算2.代码外提（循环优化）3.强度削弱4.变换循环控制条件（循环优化）5.合并已知量与复写传播6.删除无用赋值,练习,教材267 页1.2.3.7.,