编译原理教程-全套电子整本书电子教案教学教程整套课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,21,世纪高等院校规划教材,编译原理实用教程,第一章 编译程序概论,本章学习目标,编译程序是高级语言的支撑基础，是计算机系统中重要的系统软件之一，本章主要内容：,编译程序的功能,编译程序的体系结构,编译程序的工作过程,编译程序的设计,1.1,程序设计语言,程序设计语言分成两大类，一类是高级语言，一类是低级语言。低级语言又包括机器语言和汇编语言，主要是面向机器的。高级语言则是面向应用的，分成很多种，如,FORTRAN,、,Pascal,、,C,、,Ada,、,Java,等。,机器语言本身是有由,0,和,1,组成的，符合计算机的硬件特性，因此能够直接执行。但用机器语言编写程序很不方便且容易出错，因此就用助记符代替机器语言，产生了汇编语言。,汇编语言比机器语言在可读性方面有了进步，但是其依赖具体机器的特性无法改变，给程序设计语言增添了难度。,高级语言不能直接在机器上运行，它不是面向机器，而是面向应用的，因此，要想让高级语言运行必须有编译程序。编译程序就是这样的一种程序，它能将高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。,高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，源程序的运行过程如图,1-1,所示。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。如果目标程序是汇编语言的形式，则需要在编译阶段和运行阶段之间加一个汇编阶段。,源程序,目标程序,机器语言,计算结果,编译程序,汇编程序,图,1-1,源程序的编译、汇编和运行阶段,高级语言编写的程序除了可以通过编译方式外，还可以通过解释程序执行。所谓解释程序是一种语言翻译程序，读入一条语句，解释一条语句，执行一条语句，边读入边执行。,解释程序与编译程序的主要区别是：编译程序将源程序翻译成目标程序后再执行目标程序，而解释程序是逐条读出源程序中的语句并执行，即在解释程序的执行过程中并不产生目标程序。,1.2,编译程序的编译过程和结构,编译程序的功能是把高级语言源程序翻译成等价的低级语言目标程序。源程序是由一些基本符号构成的，我们在运行这个程序时，先编译，若某处有错误，就报错，无错误就运行。编译程序在编译时，先将程序中的单词一个个分离出来，登记在一个表中，这叫词法分析，然后检查语句格式，叫做语法分析。然后检查类型是否一致，计算表达式的值叫语义分析。这些功能都是由编译程序相应的程序完成的。,一般来说，整个编译过程可以划分成五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、中间代码的优化和目标代码的生成。,1.,词法分析阶段,词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词，并把单词翻译成相应的机内表示。当然，词法分析在识别单词的过程中，同时也做了词法检查。,在高级语言中，所谓单词，就是指逻辑上紧密相连的一组字符，这些字符具有集体含义。单词是语言中最小的语义单位，如语言中的关键字、标识符、运算符和界限符。词法分析的依据是词的构造。单词的构造规则在高级语言中有明确的规定，比如哪些为保留字、变量如何定义、常量如何构造、分界符有哪些等。,例如，用,C,语言编写的程序段如下：,main(),float x=2,y=3,s;,s=x+y*5;,识别出的单词序列为表,1-1,所示,表,1-1,词法分析程序,类型名,单词,类型名,单词,保留字,main,左括号,(,右括号,),花括号,保留字,float,标识符,x,等号,=,常量,2,逗号,标识符,y,等号,=,常量,3,逗号,标识符,s,分号,;,标识符,s,等号,=,标识符,x,运算符,+,标识符,y,运算符,*,常量,5,分号,;,花括号,2.,词法分析,语法分析是在词法分析的 基础上进行的，是编译过程的第二个阶段。语法分析的任务是根据语言的语法规则，把单词符号串分解成各类语法单位，如表达式、语句等。通过语法分析，可以确定整个输入符号串是否构成一个正确的程序。,3,语义分析和中间代码的生成,语义分析的任务是对各种不同语句进行翻译，包括两方面的工作：一是对每种语法范畴进行语义检查，如变量是否定义、类型是否正确等；二是在语义检查正确的情况下，进行中间代码的翻译。中间代码是介于高级语言语句和低级语言语句之间的一种独立于具体硬件的记号系统，它即有一定程度的抽象，又和低级语言十分接近，因此，转换成目标代码很容易。,中间代码的表示形式有很多种，常见的有四元式、三元式、间接三元式和逆波兰式。其中四元式的形式为（运算符，运算对象,1,，运算对象,2,，结果）,4.,中间代码优化,中间代码优化通过调整和改变中间代码中某些操作次序，以最终产生更加高效的目标代码。优化的主要手段有删除冗余运算、删除无用赋值、合并已知量、循环优化等。,5,目标代码的生成,这一阶段的任务是对前一阶段的中间代码变换成特定机器上的机器语言或汇编语言程序，实现机器的最终翻译。最后阶段的工作因为目标语言的关系而十分依赖机器的硬件系统，即如何充分利用机器现存的寄存器，合理的选择指令，生成尽可能短的目标代码，这与机器的硬件有关。,编译过程可以划分成五个阶段，这种划分是编译程序的逻辑组织形式。实际上，编译过程往往分成前端和后端。前端包括词法分析、语法分析、语义分析、中间代码生成和中间代码优化，主要依赖于源程序；后端包括目标代码生成，依赖于计算机硬件系统和机器指令系统。这种组织方式，便于编译程序的移植，若要将编译程序移植到不同类型的机器，只需要修改编译程序的后端即可。,编译程序还采用“分遍”的形式，即编译过程可以由一遍或多遍编译程序来完成。对于源程序或中间代码，从头到尾扫描一次并完成所规定的工作称为一遍。在一遍中，可以完成一个或相连几个逻辑步骤的工作。例如可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍；从而构成一个四遍扫描的编译程序。,词法分析器,语法分析器,语义分析器,中间代码生成器,中间代码的优化,目标代码生成器,源程序,表格管理,出错处理,目标程序,图,1-3,编译程序结构示意图,1.3,编译程序的设计技术,编译程序的任务是把源程序翻译成某台计算机上的目标程序。因此编程人员首先要熟悉源程序语言，对源程序语言的语法和语义要准确无误的理解，同时要确定开发方案。同时还要选择合适的语言编写编译程序，目前一般采用,PASCAL,、,C,、,ADA,等高级语言编写，不仅减少了开发的工作量，缩短了开发周期。最后，开发人员还要熟悉目标机的特点，产生质量较高的目标代码。,1,高级语言的自编译技术,用某种该高级语言书写自己的编译程序称为自编译。,2.,交叉编译,交叉编译是指用,A,机器上的编译程序来产生可在,B,机器上运行的目标代码。例如，若,A,机器上已有,C,程序可以运行，则可以在,A,机器上的,C,程序书写一个编译程序，它的源程序是,C,语言程序，而产生的目标程序则是基于,B,机器上的，即能够在,B,机器上执行的低级语言程序。,3,编译程序的自展技术,L,n,=LL,1,L,0,图,1-4,编译系统的自展过程,自展的方法是：首先确定一个非常简单的核心语言,L0,，然后用机器语言或汇编语言书写它的编译程序,T0,；再把语言,L0,扩充到,L1,此时有,L0,属于,L1,，并用,L0,编写出,L1,的编译程序,T1,，然后再把语言,L1,扩充为,L2,，此时，,L1,属于,L2,，并用,L1,编写,L2,的编译程序,T2,这样不断的扩展下去，直到完成所要求的编译程序为止。自展技术的使用如图,1-4,所示。,4,编译程序的移植技术,编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机器（目标机）上。,5,编译程序的自动化,在编译程序的自动化开发过程中，开发较早的是词法分析程序生成器和语法分析程序生成器。使用的工具是在,UNIX,操作系统下的软件工具,LEX,和,YACC,。,1.4,形式语言和编译实现技术,形式语言是一种不考虑含义的符号语言，形式语言的理论研究的是组成这种符号语言的符号串集合、它们的表示法、结构和特性。按,Chomsky,文法分类法，文法可以分成四大类，即短语结构文法、上下文有关文法、上下文无关文法和正则文法。通常的程序设计语言，其符号的定义和正则文法相关联，语法定义和上下文无关文法相关联，而语义一般需要上下文有关文法来定义。,形式语言理论采用数学那样的符号形式表示，数学那样的严格推理。采用形式语言方式讨论程序设计语言及其编译程序的构造，可以使我们不仅了解一些编译实现技术如何应用，而且还可以理解如此做的原因。,对编译程序的设计中所采用的技术，不但要知其然，而且还要知道所以然。从理论高度上去掌握编译技术。可以用下列公式来表示一种关系，即：,编译原理,=,形式语言理论,+,编译技术,小结,自,FORTRAN,语言产生后，计算机高级语言得到了迅速发展。高级语言的种类越来越多。但计算机只能执行机器语言，不能直接执行高级语言编写的程序。要执行高级语言程序，必须提供该高级语言的翻译程序。翻译有编译和解释两种方式。编译程序将源程序翻译成目标程序，然后再执行目标程序。解释方式则是边翻译边执行。,编译程序一般包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序和出错处理程序等。,编译过程可以分遍编译。编译程序的构造有多种技术。主要有自编译、移植、交叉编译、自展和自动化技术。,LEX,是一个具有代表性的词法分析程序生成器。,YACC,是一个基于,LALR,（,1,）分析法的语法分析程序生成器。,习题,1.1,完成下列选择题,(1),构造编译程序应掌握,。,a.,源程序,b.,目标语言,c.,编译方法,d.,以上三项都是,(2),编译程序绝大多数时间花在,。,a.,出错处理,b.,词法分析,c.,目标代码生成,d.,表格管理,(3),编译程序是对,。,a.,汇编语言的翻译,b.,高级语言程序的解释执行,c.,机器语言的执行,d.,高级语言的翻译,（,4,）高级语言程序设计是根据,定义的。,a.,词法规则,b.,语法规则,c.,语义规则,d.,以上三项都不是。,（,5,）编译程序的各阶段都设及到,。,a.,词法分析,b.,表格管理,c.,语法分析,d.,语义分析,（,6,）编译程序将源程序加工成目标程序是,之间的转换。,a.,词法,b.,语义,c.,语法,d.,规则,（,7,）解释程序和编译程序的区别是,之间的转换。,a.,是否生成中间代码,b.,加工的对象不同,c.,使用的实现技术不同,d.,是否生成目标代码,（）编译程序不能够检查、处理的错误是程序中的,。,a.,静态语义错误,b.,动态语义错误,c.,语法错误,d.,词法错误,（,9,）中间代码生成所依据的是语言的,。,a.,词法规则,b.,语法规则,c.,语义规则,d.,产生规则,（,10,）开发一个编译程序应掌握,。,a.,源语言,b.,目标语言,c.,编译技术,d.,以上三项都不是,1.2,判断题,（）用高级语言编写的源程序都必须通过编译，产生目标程序后才能运行。,（,2,）源程序和目标程序在功能上具有等价关系。,（,3,）高级语言程序到低级语言程序的转换是结构上的变换。,（,4,）解释程序虽然不产生目标代码，但是它可能产生中间代码。,（,5,）目标程序一定是机器语言程序。,1.3,问答题,（,1,）,.,计算机执行用高级语言编写的程序有那些途径,?,它们之间的区别是什么,?,（,2,）,.,画出编译程序的构造图,.,（,3,）,.,什么是编译程序的前端？什么是编译程序的后端？,第二章形式语言概述,本章学习目标,形式语言由,Chomsky,于,1956,年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言 的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是,:,文法和语言的形式定义,文法的分类,句型的分析和语法树,2.1,字母表和符号串,任何一种语言都是由基本符号构成的。计算机高级语言作为计算机的语言，程序有语句构成，语句有一些基本符号构成，这些基本符号是保留字如,main,，,if,，,then,等、字母、数字和专用符号等。每个程序可以看成基本符号串。将所有的基本符号定义成一个基本符号集合，则语言可以看成是在这个基本符号集合上定义的，按一定的规则构成的一切基本符号串组成的集合，给出如下的一些基本概念。,2.1.1,字母表,定义,2.1,字母表是元素的非空有穷集合，字母表中的元素称为,符号,，因此字母表也称为,符号表,。高级语言如,C,语言的字母表是由字母、数字、特殊符号和一些专用符号构成。,例,=a,b,，,=0,1,，,=0,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,0),3,字母表的闭包与正闭包的运算,设有字母表,A,，由它做方幂,A,0,，,A,1,，,A,2,，,A,n,。,A,的闭包定义如下：,定义,2.8,A,的闭包,A*=A,0,A,1,A,2,A,n,其中，,A,n,（,n=0,，,1,，,2,，,3,，,）中所有的符号串的长度为,n,，因此字母表,A,的闭包,A*,为字母表上一切长度为,n,的符号串所组成的集合。,如果不允许包含空串,，则得到字母表,A,的正闭包。,定义,2.9,A,的正闭包,A,+,=A,1,A,2,A,n,显然，,A*=A,0,A,+,，且,A,+,=AA*=A*A,。,例题,2.7,设字母表,=a,b,c,依次写出长度为,1,、,2,的符号串，可得到,的正闭包,+,：,+,=a,b,c,aa,ab,ac,bb,bc,在,+,上添入空串,即得,*,。,说明：根据闭包和正闭包的定义，则有,+,=*=*,由于一个字母表的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上某个符号串的集合，因此，在某个字母表上的语言是该字母表上正闭包的子集，且是真子集。对于,C,语言，可以说，,C,语言是基本符号集合的正闭包的真子集。,2.2,文法的定义及其分类,什么是文法，文法的直观概念是，文法作为一种工具，不仅严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。,2.2.2,文法的形式定义,1,重写规则,定义,2.10,重写规则，也叫产生式规则，或称为生成式,，是形如,或,:,的（,）有序对,其中,是某个字母表,V,+,中的一个元素，,是,V*,中的一个元素。,称为规则的左部，,称为规则的右部。,例如,A,B,读作“,A,定义为,B,”,，也就是说它是一条关于,A,的规则（产生式）。,2,文法,定义,2.11,文法,G,是一个四元组，,G=,（,V,N,，,V,T,，,P,，,S,），其中，,V,N,、,V,T,分别是非空有限的非终结符号集和终结符号集，,V,N,V,T,=,，,P,是产生式的集合，,SV,N,称为文法的识别符号或开始符号。,例题,2.8,在程序设计语言中，假设我们定义标识符的命名规则为字母,a,、,b,、,c,开头的，字母,a,、,b,、,c,和数字,1,、,2,、,3,的序列。命名规则为：,a,b,c,1,2,3,我们一般用大写字母代表左边的非终结符，设,N,代表,，,D,代表,，,L,代表,，则定义标识符的文法是：,G=(V,N,，,V,T,，,P,，,N),其中，,V,N,=N,，,L,，,D,V,T,=a,b,c,1,2,3,P,为产生式的规则：,NL,，,NNL,，,NND,，,La,，,Lb,，,Lc,，,D1,，,D2,，,D3,S,是开始符号,为,N.,关于产生式的规则说明一点，即若,A,，,A,，,A,可写成,A|,。“,|”,读做“或者”。,上面的产生式规则可以改写为：,P,为产生式的规则：,NL|NL|ND,La|b|c,D1|2|3,2.2.3,文法的分类,自从乔姆斯基（,Chomsky,）于,1956,年建立形式语言的描述以来，把文法分成四种类型，即,0,型、,1,型、,2,型和,3,型文法。,0,型文法,(,短语文法,),设,G=,（,V,N,，,V,T,，,P,，,S,），如果它的每个产生式,是这样一种结构：,（,V,N,V,T,）,+,，且至少含有一个非终结符，而,（,V,N,V,T,）*，则称,G,是一个,0,型文法,。,0,型文法又称短语文法，它的能力相当于一个图灵机。,例如，,A,1,型文法（上下文有关文法）,设,G=,（,VN,，,VT,，,P,，,S,）为一文法，若,P,中的每一个产生式,均满足,，仅仅,S,除外，则文法,G,是,1,型文法或上下文有关文法,。,所谓上下文有关文法即：,=1A2,，,=12,，符号串,1,和,2,可以认为是上下文，,A,只有出现在上下文之间中，才可以被符号串,替代，成为,=1A2,=12,因此，,1,型文法又称为上下文有关文法。,3,2,型文法（上下文无关文法）,设,G=(V,N,，,V,T,，,P,，,S),，若,P,中的每个产生式,满足,:,是一个非终结符,(V,N,V,T,)*,，则此文法称为,2,型文法或上下文无关文法,。有时将,2,型文法的产生式表示为形如：,A,，其中,AV,N,。也就是当用,取代非终结符,A,时，与,A,所在的上下文无关。上下文无关文法有足够的能力描述现今的程序设计语言。,例题,2.10,2,型文法,G=,（,VN,，,VT,，,P,，,N,）,其中，,VN=N,，,D,VT=0,，,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,P=NNDD,，,D0123456789,该文法描述的符号串的集合是整数。,3,型文法（右线性文法或正规文法）,对,2,型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即：,Aa,AaB,则称该文法为,3,型文法,，又称为,右线性文法或正规文法,，其中,A,、,BV,N,，,aV,T,.,例题,2.11,3,型文法,G=,（,V,N,，,V,T,，,P,，,S,）,其中，,V,N,=S,，,A,，,B,VT=0,，,1,P=S011A0B,，,A,1A0B,，,B010B,该文法产生的是二进制整数。,2.2.4,文法举例,例题,2.15,正规文法,G=,（,V,N,，,V,T,，,P,，,A,）,其中,VN=A,B,C,D,VT=x,y,z,P=AxByC,BzB yyC,CxD,D yDx,例题,2.16,2,型文法,G=,（,V,N,，,V,T,，,P,，,E,）,其中，,V,N,=E,，,T,，,F,VT=+,，*，（，），,i,P=EE+T|T,TT*F|T,F(E)|i,该文法能推出具有乘和加运算的算术表达式。,例题,2.17,正规文法,G=,（,V,N,，,V,T,，,P,，,S,）其中,VN=S,，,A,，,B,，,G,，,H,，,VT=d,，,，,+,，,P=SdB|+A|,A|.G,AdB|.G,BdB|.H|d,GdH,HdH|d,其中，,d,代表十进制数字。,根据以上我们对文法的定义我们不难发现,3,型文法类是,2,型文法类的特殊情况，,2,型文法类是,1,型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系：,3,型语言,2,型语言,1,型语言,0,型语言,2.2.5,各类文法与自动机的关系,语言是句子的集合，而句子又是由字母表上的符号串组成的。对于程序设计语言来讲，程序由语句构成，语句则有数字、标识符、保留字、数字等单词构成。因此对程序的编译事实上就是对句子进行检查。方法就是编写一个检查过程，运行该过程来判断编写的程序是否合法。合法就回答“正确”，不合法就回答“不正确”，并且将错误报出。,编写该过程的算法，抽象成一个数学模型，该数学模型称为自动机。将算法对程序的合法与否的检查转化为数学模型对程序中的句子的识别过程。自动机给出了用有穷方式来描述潜在的无穷的语言的另一种手段。自动机能够识别的句子的集合称为语言。对于每一类,Chomsky,语言类，正好有一类自动机与它相对应。,1,0,型语言与图灵机,图灵机是识别,0,型文法的识别装置。图灵机被引进作为描述过程的数学模型，过程的直观概念被看成是能机械实现的有穷指令的序列。图灵机的基本模型如图,2-1,所示。它有一个有限控制器、一个被分成若干单元的输入带和一个一次读入一个单元的读头组成,有限控制器,a,1,a,2,a,3,a,i,a,n,读头,图,2-1,2,1,型文法与线性界限自动机相对应,。,上下文有关文法所对应的自动机称为线性界限自动机。其功能是能够识别上下文无关语言，缩写为,LBA,。,3,2,型语言与下推自动机,2,型语言或上下文无关语言对应的自动机称为下推自动机。它是识别上下文无关语言的数学模型。缩写为,PDA,。,3,型语言与有穷状态自动机,3,型语言或正则语言所对应的自动机称为有穷自动机。缩写为,FA,。,无论那种自动机都分为确定性和非确定性之分,2.2.6,文法分类的意义,一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。也就是说，我们需要确定这个给定串的推导序列。如果从文法出发找不到这个推导序列，则该串就是非法的。,以上四类文法都分别与一个相当简单但功能很强的自动机相关。右线性文法可由一种有穷状态自动机识别。,2.3,文法产生的语言和句型的语法树,2.3.1,推导和规范推导,为了定义文法产生的语言，我们必须给出推导的概念。推导分为三大类：直接推导、,，长度为,n(n1),的推导和长度为,n,（,n0,）的推导。,定义,2.12,如,是文法,G=(V,N,V,T,P,S),的规则（或说是,P,中的一产生式），,(V,N,V,T,)*,，则称符号串,为符号串,应用产生式,所得到的直接推导。记为,。,定义,2.13,推导长度大于,0,的推导,：,如果 对于符号串,v,与,w,存在一个直接推导序列,u,0,u,1,u,2,u,3,u,n,(n0),其中,u,0,=v,与,u,n,=w,则称符号串,v,推导出,w,或称,w,归约到,v,，记作,v,*w,，称这个直接推导序列是长度为,n,的推导，且称符号串,w,是相对于符号串,v,的一个字。,定义,2.14,推导长度大于等于,0,的推导：如果对于符号串,v,和,w,，,v=w,或,v=w,，则记作,v,*w,，称符号串,v,广义推导到符号串,w,，或称,w,广义归约到,v,。,例,2.18,根据文法，考虑以,C,语言中的无正负号整数作为识别符号的文法。,（,1,）,（,2,）,|,(3),0|1|2|3|4|5|6|7|8|9,VT=0,1,2,3,4,5,6,7,8,9 VN=,判断数据,2634,是否是,C,语言合法的数据。,给出数据,2634,的推导。,4,4,34,34,634,2634,由此可见，,2634,是,C,语言的合法数据。每一步推导都是直接推导。可以表示为,2634,定义,2.15,如果在推导的任何一步,，其中,、,是句型，都是对,中的最左非终结符进行替换，则称这种推导为最左推导,。,定义,2.16,如果在推导的任何一步,，其中,、,是句型，都是对,中的最右非终结符进行替换，则称这种推导为最右推导,。,定义,2.17,在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型。,定义,2.15,如果在推导的任何一步,，其中,、,是句型，都是对,中的最左非终结符进行替换，则称这种推导为最左推导,。,定义,2.16,如果在推导的任何一步,，其中,、,是句型，都是对,中的最右非终结符进行替换，则称这种推导为最右推导,。,定义,2.17,在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型。,例,2.19,给出了下列文法,G,（,1,）,（,2,）,|,(3),0|1|2|3|4|5|6|7|8|9,VT=0,1,2,3,4,5,6,7,8,9 VN=,判断数据,2634,是否是,C,语言合法的数据。,【,解,】,（,1,）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：,4,4,34,34,634,2634,（,2,）用最左推导，每次直接推导都替换最左边的非终结符，推导过程如下：,2,26,263,2634,2.3.2,句型、句子和语言,定义,2.18,句型：设,GS,是一个文法，如果符号串,x,是从开始符号,S,推导得到的，即有,S=+x,，,x,V+,，则称符号串,x,是该文法,G,的一个句型。,定义,2.19,句子：,GS,是一个文法，如果符号串,x,是从开始符号,S,推导得到的，即有,S=+x,，并且,x,V,T,，则称该符号串为该文法的一个句子。,实质上，句子是句型的特殊情况，句子是由终结符组成，而句型是有终结符和非终结符组成。,定义,2.20,语言,GS,是一个文法，文法,G,产生的语言,L(G)=x|S=x,，并且,x,V,T,，即文法的语言是文法所有句子的集合。,例,2.20,2,型文法,G=(V,N,，,V,T,，,P,，,S),其中，,V,N,=S,VT=0,1,P=S0S1,S01,该文法产生的语言是,L(G)=0,n,1,n,其中,n1,例,2.21,文法,GS,定义如下,S,if E then S|if E then S else S|while E do S|begin L end|A,该文法产生的语言就是程序设计语言中的单分支、双分支、循环语句和顺序语句，其中每个非终结符的意义是：,S,代表语句，,L,代表语句串、,A,代表赋值语句，,E,代表布尔表达式。,例,2.22,设文法,GS,：,E,E+T|T,T,T*F|F,F,(E)|i,证明符号串,E+(E+T)*i,是文法的句型，,i+i*i,是文法的句子；并说明该文法产生的语言是什么。,【,证明,】,由于,E,E+T,E+T*F,E+T*i,E+F*i,E+(E)*i,E+(E+T)*i,所以,E+(E+T)*i,是文法的句型。,由,E,E+T,E+F,E+F*i,E+i*i,T+i*i,F+i*i,i+i*i,所以,i+i*i,是文法的句子。,该文法产生的语言是程序设计语言中的算术运算式，其中包括加、乘和括号运算。,2.3.3,语法树,在自然语言中，句子结构可以借助一种树形表示进行分析。如下面的句子：,They are students and teachers of the Physics Department,。,对该句子的结构进行分析，其树型结构如图,2-3,所示，由此可以看出，该句子是由主语、系词和表语组成，是一个语法正确的句子。,句子,主语,系词,表语,代词,They,are,名词,student,连接词,and,名词,teacher,定语,前置词,冠词,名词,of,the,Physics,名词,Department,图,2-3,句子结构,在自然语言中，可以通过树型表示直观地分析句子的结构；在形式语言中，我们提到了句型、推导的概念，在证明某个符号串是否是某个文法的句型时，采用从文法开始符号推导的方法，这个推导过程可以用语法树直观的表示出来。语法树也称为推导树，其定义如下：,给定文法,G=(V,N,V,T,P,S),，对于,G,的任何句型都能构造与之关联的语法树，这棵树满足下列四个条件：,（,1,）每个结点都有一个标记，此标记是,V,的一个符号。,（,2,）根的标记是,S,。,（,3,）若一结点,n,至少有一个它自己除外的子孙，并且有标记,A,，则,A,肯定在,V,N,中。,（,4,）如果结点,n,的直接子孙，从左到右的次序是结点,n,1,n,2,n,3,.n,k,，其标记分别为,A,1,，,A,2,，,A,3,，,A,K,。那么,AA,1,A,2,A,3,A,K,一定是,P,中的一个产生式。,例,2.23,设文法,GS,：,E,E+T|T,T,T*F|F,F,(E)|i,证明符号串,E+(E+T)*i,是文法的句型。,E,E,+,T,i,*,F,F,(,),T,E,+,E,T,2.3.4,二义性文法及其他,1,二义性文法及其定义,一个文法，如果它的一个句子或句型有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则称该文法具有二义性。,例,2.24,设文法,GS,：,Sif B then S|if B then S else S|i,：,=E,给出符号串,if B then if B then S else S,的语法树。,语法树的结构如图,2-5,所示。,从上面的语法图我们可以看出，字符串,if B then if B then S else S,能够画出两棵语法树，所以该文法是一个二义性文法。,在语言中，为了避免二义性的文法，往往对文法加以一定的限制，如限制条件语句,then,之后不允许再是条件语句，或者从语义解释方面限制条件语句中的,else,只能与其前面的、还没有和其他,else,配对的,then,配对。如此限制之后，符号串,if B then if B then S else S,就只有图,2-5,左边的树形结构了。,S,if,B,then,S,if,B,then,else,S,S,S,if,B,then,else,S,S,if,B,then,S,2,二义性文法的证明,要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。即不存在一个算法，它能在有限的步骤内，确切的判断出某个给定的文法是否是一个二义性文法。,我们要证明一个文法是否是一个二义性文法，就是找到该文法的一个句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。,例,2.25,文法,G=,（,E,，,+,，*，,I,(,),，,P,，,E,）其中,P,为：,E,i,E,E+E,E,E*E,E,(E),证明该文法是二义性文法，并将该文法改为等价的非二义性文法（等价的文法是指产生的语言相等的文法）。,【,证明,】,取句型,i*i+i,，写出该句型的两个不同的推导。画出推导的两棵不同的语法树。,推导,1,：,E,E+E,E*E+E,i*E+E,i*i+E,i*i+i,推导,2,：,E,E*E,i*E,i*E+E,i*i+E,i*i+i,推导的两棵语法树如图,2-6,所示。,将文法改为非二义性文法为：,E,T|E+T,T,F|T*F,F,（,E,）,|i,E,E,E,+,E,*,E,i,i,i,E,E,E,E,*,E,*,E,i,i,i,2.3.5,文法产生的语言和产生语言的文法,例,2.26,设,G=,（,VN,，,VT,，,P,，,S,），,VN=S,B,E,，,VT=a,b,c,，,P,由下列产生式组成：,S,aSBE,S,aBE,EB,BE,aB,ab,bB,bb,bE,be,eE,ee,（,1,）问该文法是,Chomsky,哪一类型的文法？,（,2,）它生成的语言是什么？,答：根据文法分类定义，由于文法中存在产生式，其左部由长度大于,1,的符号串构成，如产生式“,EB,BE”,，显然不符合,Chomsky,的,2,型和,3,型文法的定义。该文法产生式左部串的长度均小于等于右部串的长度，符合,1,型文法的定义，所以该文法是上下文有关文法。,（,2,）根据如下推导：对于每一个,n1,，我们将号产生式使用,n-1,次，得到推导序列：,S,a,n-1,S(BE),n-1,，然后使用产生式,(2),一次，得到：,S,a,n,(BE),n,，然后从,a,n,(BE),n,.,继续推导，总是对,EB,使用产生式的右部进行替换，而最终在得到的串中，所有的,B,都限于所有的,E,。设,n=3,，,aaBEBEBE,aaaBBEEBE,aaaBBEBEE,aaaBBBEEE,。即有：,S,a,n,B,n,E,n,.,接着，使用产生式,(4),一次,得到,Sa,n,bB,n-1,En,，然后使用产生式,n-1,次得到：,S,anbnEn,，然后使用产生式一次，使用产生式,n-1,次，得到：,S,anbnen,因此该文法产生的语言是,L(G)=anbnen|n1,。,例,2.27,设有上下文无关文法如下：,GS,：,S,AB,A,UT,U,a|aU,T,b|bT,B,c|cC,将文法的产生式代入产生如下文法：,GS,：,S,UTB,U,a|aU,T,b|bT,B,c|cC,考察文法，用,L(S),，,L(U),，,L(T),和,L(B),分别表示从终结符,S,，,U,，,T,和,B,出发推导出的符号串的集合，不难发现：,L,（,U,）,=a,i,|i1=a+,L,（,T,）,=b,j,|j1=a+,L,（,B,）,=c,k,|k1=a+,由于有,S,UTB,，则有：,L,（,S,）,=L(U)L(T)L(B),=(a,i,b,j,c,k,|i1,j1,k1),=a,+,b,+,c,+,例,2.28,构造一个上下文无关文法,G,，使其描述的语言,L,（,G,）是能够被,5,整除的无符号整数集合。,能够被,5,整除的整数其结构特点是，末位数一定是,0,或,5,。所以，只要保证生成的整数末位数字是,0,或,5,即可。据此，构造描述能被,5,整除的无符号整数集合的文法如下：,GS,：,S,N0|N5,N,DN|,D,0|1|2|3|4|5|6|7|8|9,例,2.29,写出一个上下文无关文法,G,，使得,L(G)=a,n,b,m,c,m,d,n,|n0,，,m1,分析该语言的特点，可以看出，,a,和,d,的个数是一样的，,b,和,c,的个数是一样的。,m,的取值范围从,1,开始，所以至少有一个,bc,，,n,的最小值为,0,。写出文法为：,S,aAd|A,A,bAc|bc,2.4,句型分析与句柄,对于上下文无关文法，语法树是句型推导过程的几何表示；是进行句型分析极好的工具。所谓句型分析就是识别一个符号串是否是某一个文法的句型。进一步说就是给定一个符号串时，按照某文法的规则为该符号串构造推导或语法树，以此来识别它是文法的一个句型。对于上下文无关文法，其句型分析方法有两大类，一类是自上而下的分析方法（又称自顶向下），另一类是自下而上（自底向上）的分析方法。,2.4.1,自上向下的分析方法,1,基本思想,自上而下的分析方法就是从识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就不是。或者说，以文法的识别符号作为根结点，看是否能构造出一个语法树，而且此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则就不是。,例,2.30,设文法,GS,：,S,aAbc|aB,A,ba,B,beB|d,输入串：,abed,，识别该串是否是该文法的一个句子。,方法：从文法的识别符号,S,开始出发，选择它的一个产生式,S,aAbc,得到直接推导,S,aAbc,以识别符,S,作为根结点，构造语法树，如下图,2-7,所示,S,a,A,b,c,b,a,图,2-7,自上而下的推导过程,S,a,A,b,c,S,a,B,S,a,B,B,e,b,S,a,B,e,b,B,d,（,a,）,（,b,）,（,c,）,（,d,）,（,e,）,2,分析过程,符号串,aAbc,与待检查的符号串,abed,的第一个符号相匹配。由于符号串,aAbc,的第,2,个符号是非终结符，因此需要对它进行替换。,A,只有一个产生式,A,ba,。以其右部替换,A,，得推导,S,aAbc,ababc,得