编译原理教案

课程编码：07153008编译原理及实现技术课程教案2011～2012学年第1学期任课教师：郭德贵、张红、张睿吉林大学计算机科学与技术学院课程名称：编译原理课程英文名称：CompilerPrinciple学时：64学分：4授课对象：计算机科学与技术专业2009级教学目的：编译原理课程是计算机科学与技术专业学生的专业骨干课之一。通过学习这门课程，使学生掌握编译程序的基本原理、方法和实现技术，使学生更好的理解程序语言的内部机制，培养学生初步掌握设计大型系统软件的方法、技术以及设计大型软件的能力。教学方式：板书多媒体系统演示教材：刘磊《编译原理及实现技术》机械工业出版社2005教学参考书：1）陈火旺等《程序设计语言编译原理》国防工业出版社20012）吕映芝，张素琴，蒋维杜《编译原理》清华大学出版社19983）AlfredV.Aho,Ravi，Sethi，JeffreyD.Ullman.Compilers:Principles,Techniques,andTool.AddisonWesley,1985.4）CharlesN.Fischer,RichardJ.LeBlanc.CraftingaCompilerwithC.PearsonEducation,1991授课题目第一章编译引论授课学时2授课时间教学重点、难点：本章从总体上概要介绍编译相关的原理和技术以及典型编译器的逻辑结构，使学生对编译程序有一个初步的认识。本章重点和难点为各基本概念的理解和对整个编译程序各个阶段所承担任务的理解和掌握。教学要点：本章需要学生掌握如下内容：1．实现高级语言的编译方式和解释方式及其区别。编译方式：对整个源程序进行分析，翻译成等价的目标程序，翻译的同时做语法检查和语义检查。然后再运行目标程序。解释方式：一个语句一个语句的读入源程序，边翻译边执行，在翻译过程中不产生目标程序。解释方式特别适合于交互式语言；而且解释方式允许程序执行时改变自身，比如调试程序。这种情形编译程序不易胜任，因为它需要动态编译，而解释程序可以毫无困难的胜任；此外，解释程序不依赖于目标机，因为它不生成目标代码，可移植性优于编译程序。但是和编译程序相比，解释程序开销大，运行速度慢得多。解释方式和编译方式的最根本区别在于：在解释方式下，并不生成目标代码程序，而是直接执行源程序本身。2．典型编译器的各个组成部分以及各个部分所承担的任务。a.词法分析阶段词法分析的任务是扫描源程序的ASCII码序列，识别出一个个具有独立意义的最小语法单位，即单词.b.语法分析阶段语法分析的任务是根据程序设计语言的语法规则，把词法分析的结果分解成各种语法单位，同时检查程序中的语法错误。c.语义分析阶段这一阶段的任务是对语法分析所识别出的各类语法范畴，分析其含义，并进行静态语义检查。d.中间代码生成在进行了上述的语法分析和语义分析阶段的工作后，编译程序将源程序变成一种内部表示形式.e.中间代码优化此阶段的任务是对前阶段产生的中间代码在不改变源程序语义的前提下进行加工变换，使生成的代码更为高效，缩短运行时间或节省存储空间。f.目标代码生成这一阶段的任务是把中间代码变换成特定机器上的机器指令代码或汇编指令代码。g.表格管理编译程序在对源程序的分析过程中，需要创建和管理一系列的表格，以登记源程序的各类信息和编译各阶段的进展情况。3．遍具体实现上，受不同源语言、设计要求和计算机硬件条件的限制，往往将编译程序组织成若干遍（Pass）。所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。既可以将编译过程中的几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。例如，词法分析这一阶段可以作为单独的一遍，但更多的时候是把词法分析程序作为语法分析程序的子程序来加以调用，将词法分析阶段和语法分析阶段合并为一遍。4．前端和后端概念上，我们有时把编译程序划分为编译前端和编译后端。前端主要由与源语言有关但与目标机无关的那些部分组成。编译前端通常包括词法分析、语法分析、语义分析、中间代码生成，与目标机无关的中间代码优化部分也可包含在前端,当然前端也包括相应部分的错误处理。编译后端包括与目标机有关的中间代码优化部分和目标代码生成等。一般来说，这些部分与源语言无关而仅仅依赖于中间语言。很明显编译后端是面向目标语言的，而编译前端则不是，它几乎独立于目标语言。5．编译程序的实现一般开发编译程序有如下几种可能途径：a.转换法（预处理法）：假如我们要实现L语言的编译器，现在有L’语言的编译器，那么可以把L语言程序转换成L’语言的程序，再利用L’语言的编译器实现L语言，这种方法通常用于语言的扩充。如对于C++语言，可以把C++程序转换成C程序，再应用C语言的编译器进行编译，而不用重新设计和实现C++编译器。常见的宏定义和宏扩展都属于这种情形。b.移植法：假设在A机器上已有L语言的编译程序，想在B机器上开发一个L语言的编译程序。这里有两种实现方法：实现方法一：最直接的办法就是将A机的代码直接转换成B机代码。实现方法二：假设A机和B机上都有高级程序设计语言W的编译程序，并且A机上的L语言编译程序是用W语言写的，我们可以修改L编译程序的后端，即把从中间代码生成A机目标代码部分改为生成B机的目标代码。这种在A机上产生B机目标代码的编译程序称为交叉编译程序（CrossCompiler）。c.自展法：实现思想：先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序。通常这个过程会分成若干步，像滚雪球一样直到生成预计源语言的编译程序为止。我们把这样的实现方式称为自展技术。使用自展技术开发编译器要求这种高级语言必须是能够编译自身的。d.工具法：70年代随着诸多种类的高级程序设计语言的出现和软件开发自动化技术的提高，编译程序的构造工具陆续诞生，如70年代Bell试验室推出的LEX，YACC至今还在广泛使用。其中LEX是词法分析器的自动生成工具，YACC是语法分析器的自动生成工具。然而，这些工具大都是用于编译器的前端，即与目标机有关的代码生成和代码优化部分由于对语义和目标机形式化描述方面还存在困难，虽有不少生成工具被研制，但还没有广泛应用。e.自动生成法：如果能根据对编译程序的描述，由计算机自动生成编译程序，是最理想的方法，但需要对语言的语法、语义有较好的形式化描述工具，才能自动生成高质量的编译程序。目前，语法分析的自动生成工具比较成熟，如前面提到的YACC等，但是整个编译程序的自动生成技术还不是很成熟，虽然有基于属性文法的编译程序自动生成器和基于指称语义的编译程序自动生成器，但产生目标程序的效率很低，离实用尚有一段距离，因此，要想真正的实现自动化，必须建立形式化描述理论。授课题目第二章语言和文法授课学时1授课时间教学重点、难点：文法的定义和分类；短语和句柄；语法树和文法二义性教学要点：1．基本概念：定义1字母表字母表（alphabet）是元素的非空有穷集合,字母表中的一个元素称为该字母表的一个字母（letter）,也可叫做符号（symbol）或者字符(character).定义2符号串由字母表中的符号组成的任何有穷序列称为符号串。定义3符号串的连接设x和y均是字母表∑上的符号串，它们的连接是把y的所有符号顺序接在x的符号之后所得到的符号串。定义4符号串的方幂设x是字母表∑上的符号串，把x自身连接n次得到的符号串z,即z=xx…xx(n个x),称作符号串x的n次幂，记作z=xn。根据定义有：x0=x1=xx2=xxx3=x2x=xx2=xxx……xn=xn-1x=xxn-1=xx…xx(n个x)例1：设x=001,则有x0=εx2=001001,x3=001001001。定义5前缀和后缀设x是某一字母表上的符号串，x=yz,则y是x的前缀，z是x的后缀，特别是当z≠时，y是x的真前缀；y≠ε时，z是x的真后缀。例2设x=abc,则，a,ab,abc都是x的前缀，其中，a,ab为x的真前缀；而abc,bc,c,都是x的后缀，其中bc,c,为x的真后缀。定义6子字符串一个非空字符串x,删去它的前缀和后缀后所得到的字符串称为x的子字符串，简称子串。如果删去的前缀和后缀不同时为ε,则称该子串为真子串。定义7符号串集合若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。定义8符号串集合的乘积设A、B是两个符号串集合，AB表示A与B的乘积，则定义AB={xy|(x∈A)∧(y∈B)},运算结果仍然表示符号串的集合。例3设A={a,bc}，B={de,f},则AB={ade,af,bcde,bcf}注意有{ε}A=A{}=A,A=a=,其中为空集。符号串集合的乘积一般不满足交换律。定义9符号串集合的方幂设A是符号串集合，则称Ai是符号串集合A的方幂，其中i是非负整数。具体定义如下：A0={}A1=AA2=AA……An=AA……A(n个A)定义10符号串集合的正闭包设A是符号串集合，则称A+为符号串集合A的正闭包。其具体定义如下：A+=A1∪A2∪A3…定义11符号串集合的星闭包：设A是符号串集合，则称A+为符号串集合A的星闭包。其具体定义如下：A*=A0∪A1∪A2∪A3…星闭包又称自反闭包或克林闭包。由定义显然有A+=AA*。例4设A={ab,cd}，则A+={ab,cd,abab,abcd,cdab,cdcd,ababab,ababcd,…}A*={,ab,cd,abab,abcd,cdab,cdcd,ababab,ababcd,…}定义12文法（grammar）一个文法G是一个四元组G=(VN,VT,S,P)其中：VT是一个非空的有限集合，它的每个元素称为终极符号或终极符，一般用小写字母表示。从语法分析的角度看，终极符号是一个语言不可再分的基本符号。VN是一个非空的有限集合，它的每个元素称为非终极符号或非终极符，一般用大写字母表示。非终极符是一个语法范畴，表示一类具有某种性质的符号，它不出现在句子中。设V是文法G的符号集，则有V=VN∪VT,VN∩VT=，即VN和VT的交集为空。S是一个特殊的非终极符号，称为文法的开始符号。S∈VN。P是产生式的有限集合。所谓的产生式，也称为产生规则或简称为规则，是按照一定格式书写的定义语法范畴的文法规则。2．文法分类一个文法的核心是产生式集合，它决定了文法所产生的语言。根据产生式所受的限制不同，乔姆斯基将文法分为四类，四类文法对应四种类型的语言，通常称之为乔姆斯基体系。a.0型文法（短语型文法）如果对文法G中的任一产生式不加任何限制，则称G为0型文法或短语型文法。其中，、是符号串。b.1型文法（上下文相关文法）如果对文法G中的任一产生式均限制为形如：A其中A∈VN，，∈(VT∪VN)*，∈(VT∪VN)+，则称文法G为1型文法或上下文相关文法。c.2型文法（又称上下文无关文法）如果对文法G中的任一产生式均限制为形如：A其中A∈VN,∈(VT∪VN)*则称G为2型文法或上下文无关文法。在2型文法中，用取代非终极符A时，与A所在的上下文无关，所以称之为上下文无关文法。例2.5文法G:SaSb|ab容易验证，G为2型文法，G产生的语言为：L(G)={anbn|n≥1}例2.6文法G:SaPd|abcdPbPc|bc容易验证，G为2型文法，G产生的语言为：L(G)={anbmcmdn|m,n≥1}d.3型文法（又称线性文法、正则文法、正规文法）如果对文法G中的任一产生式均限制为形如：AB或A其中A，B∈VN,∈VT则称文法G为3型文法。上述形式的3型文法也称为右线性文法，3型文法还有另一种形式，称为左线性文法。如果对文法G中的任一产生式均限制为形如：AB或A其中A，B∈VN,∈VT这样的3型文法称为左线性文法。例2.8文法G:SS0|03．短语和句柄：定义13短语设G是一部文法，S是G的开始符号，是文法G的一