【教学课件】第2章形式语言概述.ppt

《【教学课件】第2章形式语言概述.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第2章形式语言概述.ppt（97页珍藏版）》请在三一办公上搜索。

1、第二章形式语言概述,本章学习目标,形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言 的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是:文法和语言的形式定义文法的分类句型的分析和语法树,2.1字母表和符号串,任何一种语言都是由基本符号构成的。计算机高级语言作为计算机的语言，程序有语句构成，语句有一些基本符号构成，这些基本符号是保留字如main，if，then等、字母、数字和专用符号等。每个程序可以看成基本符号串。将所有的基本符号定义成一个基本符号集合，则语言可以看成是在这个基本符号集合上定义的，按一定的规则构成的一切基本符号串组成

2、的集合，给出如下的一些基本概念。,字母表,定义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,=,=,;（，）,符号串,1符号串定义2.2 符号串是由字母表中的符号所组成的有穷序列。例2.1 某个字母表=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,;，则建立在上的符号串有：if(2+3=5)then a=6 el

3、se b=8;2符号串的长度符号串x中所包含的符号的个数称为符号串x的长度，记为|x|。例如字母表0，1，则|010110|=6。记为空串，长度为0。,3子字符串定义2.3 设有非空符号串u=xvy，其中x、v、y是符号串，且v，则称v为符号串u的子符号串。例题2.2设字母表=a，b，c，d，+，-，*，/，(，)上有符号串x=a+b*(c+d)，则a、a+b*与（c+d）等都是x的子符号串，且其长度分别为a=1、a+b*=4与(c+d)=54符号串的头和尾定义2.4 如果z=xy是一个符号串，则x是z的头,而y是z的尾。如果y非空，则x是z的固有头，又称为真前缀；若x非空，则y是z的固有尾，

4、又称为真后缀。,例题2.3 假设字母表=a,b,c上的符号串z=abc，则、a、ab、abc都是z的头，且除abc外都是x的固有头；、c、bc、abc都是z 的尾，且除abc外都是z的固有尾。若只对符号串的头部感兴趣，记做z=x。若只对尾部感兴趣，则记为z=x。5符号串的运算定义2.5 符号串的连接运算：设 x与y是同一个字母表上的两个符号串，把y的各个符号相继写在x的符号后所得到的符号串称为x与y的连接，记为xy。,例题2.4设在字母表a,b,c上有符号串 x=ab与y=cba，则z=xy=abcba。这里x=2,y=3,z=5。对于字母表上的任何符号串x，都有x=x=x定义2.6 符号串的

5、方幂：设x是某个字母表上的符号串，把x自身连接n次，即z=xxx（n个x），称为符号串x的n次方幂，记为z=xn。例如，x=ab则x3=ababab,符号串集合,1符号串集合的定义定义2.6 若集合A中一切元素都是某字母表上的符号串，则称A是该字母表上的符号串的集合。字母表上的符号串的集合通常用大写字母来表示A、B、C、表示。例题2.5 设某个字母表a,b,c,d上有两个符号串的集合记为A=a,bc,B=abc,cd,ab,2符号串集合的运算定义2.7 两个符号串集合A和B的乘积AB定义为：AB=xyxA，且yB例题2.6 设A=a,b，B=c,d,e 则AB=ac,ad,ae,bc,bd,b

6、e对于任何空集合，都有A=A=A类似于符号串的方幂，可以定义符号串集合的方幂，特别地定义字母表A的方幂为：A0=，A1=A，An=An-1A(n0),3字母表的闭包与正闭包的运算设有字母表A，由它做方幂A0，A1，A2，An,。A的闭包定义如下：定义 2.8 A的闭包A*=A0A1 A2 An,其中，An（n=0，1，2，3，）中所有的符号串的长度为n，因此字母表A的闭包 A*为字母表上一切长度为n的符号串所组成的集合。如果不允许包含空串，则得到字母表A的正闭包。定义2.9 A的正闭包 A+=A1 A2 An显然，A*=A0 A+，且A+=AA*=A*A。,例题2.7 设字母表=a,b,c,依

7、次写出长度为1、2的符号串，可得到 的正闭包+：+=a,b,c,aa,ab,ac,bb,bc,在+上添入空串即得*。说明：根据闭包和正闭包的定义，则有+=*=*由于一个字母表的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上某个符号串的集合，因此，在某个字母表上的语言是该字母表上正闭包的子集，且是真子集。对于C语言，可以说，C语言是基本符号集合的正闭包的真子集。,2.2 文法的定义及其分类,什么是文法，文法的直观概念是，文法作为一种工具，不仅严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。,文法的形式定义,1重写规

8、则定义2.10重写规则，也叫产生式规则，或称为生成式，是形如或:的（,）有序对,其中,是某个字母表V+中的一个元素，是V*中的一个元素。称为规则的左部，称为规则的右部。例如 AB读作“A定义为B”，也就是说它是一条关于A的规则（产生式）。2文法定义2.11 文法G是一个四元组，G=（VN，VT，P，S），其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式的集合，SVN 称为文法的识别符号或开始符号。例题2.8在程序设计语言中，假设我们定义标识符的命名规则为字母a、b、c开头的，字母a、b、c和数字1、2、3的序列。命名规则为：,abc123,我们一般用大写字母代表

9、左边的非终结符，设N 代表，D代表，L代表，则定义标识符的文法是：G=(VN，VT，P，N)其中，VN=N，L，DVT=a,b,c,1,2,3P为产生式的规则：NL，NNL，NND，La，Lb，Lc，D1，D2，D3S 是开始符号,为N.关于产生式的规则说明一点，即若A，A，A可写成A|。“|”读做“或者”。上面的产生式规则可以改写为：,P为产生式的规则：NL|NL|NDLa|b|cD1|2|3,文法的分类,自从乔姆斯基（Chomsky）于1956年建立形式语言的描述以来，把文法分成四种类型，即0型、1型、2型和3型文法。0型文法(短语文法)设G=（VN，VT，P，S），如果它的每个产生式是这

10、样一种结构：（VNVT）+，且至少含有一个非终结符，而（VNVT）*，则称G是一个0型文法。0型文法又称短语文法，它的能力相当于一个图灵机。例如，A,1型文法（上下文有关文法）设G=（VN，VT，P，S）为一文法，若P中的每一个产生式均满足，仅仅S除外，则文法G是1型文法或上下文有关文法。所谓上下文有关文法即：=1A2，=12，符号串1 和2可以认为是上下文，A只有出现在上下文之间中，才可以被符号串替代，成为=1A2=12因此，1型文法又称为上下文有关文法。,32型文法（上下文无关文法）设G=(VN，VT，P，S)，若P中的每个产生式满足:是一个非终结符,(VNVT)*，则此文法称为2 型文法

11、或上下文无关文法。有时将2型文法的产生式表示为形如：A，其中AVN。也就是当用取代非终结符A时，与A所在的上下文无关。上下文无关文法有足够的能力描述现今的程序设计语言。,例题2.102 型文法G=（VN，VT，P，N）其中，VN=N，DVT=0，1，2，3，4，5，6，7，8，9P=NNDD，D0123456789该文法描述的符号串的集合是整数。,3型文法（右线性文法或正规文法）对2型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即：Aa AaB则称该文法为3型文法，又称为右线性文法或正规文法，其中A、BVN，aVT.例题2.113型文法 G=（VN，VT

12、，P，S）其中，VN=S，A，BVT=0，1P=S011A0B，A1A0B，B010B该文法产生的是二进制整数。,文法举例,例题2.15正规文法G=（VN，VT，P，A）其中,VN=A,B,C,DVT=x,y,z P=AxByCBzB yyC CxDD yDx例题2.162型文法G=（VN，VT，P，E）其中，VN=E，T，FVT=+，*，（，），iP=EE+T|T,TT*F|T,F(E)|i该文法能推出具有乘和加运算的算术表达式。,例题2.17正规文法G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+，P=SdB|+A|A|.GAdB|.GBdB|.H|dGdHHdH|d其

13、中，d代表十进制数字。根据以上我们对文法的定义我们不难发现3型文法类是2型文法类的特殊情况，2型文法类是1型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系：3型语言2型语言1型语言0型语言,各类文法与自动机的关系,语言是句子的集合，而句子又是由字母表上的符号串组成的。对于程序设计语言来讲，程序由语句构成，语句则有数字、标识符、保留字、数字等单词构成。因此对程序的编译事实上就是对句子进行检查。方法就是编写一个检查过程，运行该过程来判断编写的程序是否合法。合法就回答“正确”，不合法就回答“不正确”，并且将错误报出。,编写该过程的

14、算法，抽象成一个数学模型，该数学模型称为自动机。将算法对程序的合法与否的检查转化为数学模型对程序中的句子的识别过程。自动机给出了用有穷方式来描述潜在的无穷的语言的另一种手段。自动机能够识别的句子的集合称为语言。对于每一类Chomsky语言类，正好有一类自动机与它相对应。,10型语言与图灵机,图灵机是识别0型文法的识别装置。图灵机被引进作为描述过程的数学模型，过程的直观概念被看成是能机械实现的有穷指令的序列。图灵机的基本模型如图2-1所示。它有一个有限控制器、一个被分成若干单元的输入带和一个一次读入一个单元的读头组成,21型文法与线性界限自动机相对应,。上下文有关文法所对应的自动机称为线性界限自

15、动机。其功能是能够识别上下文无关语言，缩写为LBA。,32型语言与下推自动机,2型语言或上下文无关语言对应的自动机称为下推自动机。它是识别上下文无关语言的数学模型。缩写为PDA。,3型语言与有穷状态自动机,3型语言或正则语言所对应的自动机称为有穷自动机。缩写为FA。无论那种自动机都分为确定性和非确定性之分,文法分类的意义,一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。也就是说，我们需要确定这个给定串的推导序列。如果从

16、文法出发找不到这个推导序列，则该串就是非法的。以上四类文法都分别与一个相当简单但功能很强的自动机相关。右线性文法可由一种有穷状态自动机识别。,2.3文法产生的语言和句型的语法树,推导和规范推导为了定义文法产生的语言，我们必须给出推导的概念。推导分为三大类：直接推导、，长度为n(n1)的推导和长度为n（n0）的推导。定义2.12如是文法G=(VN,VT,P,S)的规则（或说是P中的一产生式），,(VNVT)*，则称符号串为符号串应用产生式所得到的直接推导。记为。,定义2.13推导长度大于0的推导：如果 对于符号串v 与w存在一个直接推导序列u0 u1u2u3un(n0)其中u0=v与un=w,则

17、称符号串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|9VT=0,1,2,3,4,5,6,7,8,9 VN=,判断数据2634是否是C语言合法的数据。给出数据2634的推导。4434346342634由此可见，2634是C 语言的合法数据。每一步推导都是直接推导。可以

18、表示为2634,定义2.15如果在推导的任何一步，其中、是句型，都是对中的最左非终结符进行替换，则称这种推导为最左推导。定义2.16如果在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换，则称这种推导为最右推导。定义2.17在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型。,定义2.15如果在推导的任何一步，其中、是句型，都是对中的最左非终结符进行替换，则称这种推导为最左推导。定义2.16如果在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换，则称这种推导为最右推导。定义2.17在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型

19、。,例2.19给出了下列文法G（1）（2）|(3)0|1|2|3|4|5|6|7|8|9VT=0,1,2,3,4,5,6,7,8,9 VN=,判断数据2634是否是C语言合法的数据。【解】（1）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：4434346342634,（2）用最左推导，每次直接推导都替换最左边的非终结符，推导过程如下：2262632634,句型、句子和语言,定义2.18句型：设GS是一个文法，如果符号串x是从开始符号S推导得到的，即有S=+x，xV+，则称符号串x是该文法G的一个句型。定义2.19句子：GS是一个文法，如果符号串x是从开始符号S推导得到的，即

20、有S=+x，并且xVT，则称该符号串为该文法的一个句子。实质上，句子是句型的特殊情况，句子是由终结符组成，而句型是有终结符和非终结符组成。定义2.20语言GS是一个文法，文法G产生的语言L(G)=x|S=x，并且xVT，即文法的语言是文法所有句子的集合。,例2.20 2型文法G=(VN，VT，P，S)其中，VN=SVT=0,1P=S0S1,S01该文法产生的语言是L(G)=0n1n,其中n1,例2.21 文法GS定义如下Sif E then S|if E then S else S|while E do S|begin L end|A该文法产生的语言就是程序设计语言中的单分支、双分支、循环语句

21、和顺序语句，其中每个非终结符的意义是：S代表语句，L代表语句串、A代表赋值语句，E代表布尔表达式。,例2.22 设文法GS：EE+T|TTT*F|FF(E)|i证明符号串E+(E+T)*i是文法的句型，i+i*i 是文法的句子；并说明该文法产生的语言是什么。【证明】,由于EE+TE+T*FE+T*iE+F*iE+(E)*i E+(E+T)*i所以 E+(E+T)*i是文法的句型。由EE+TE+FE+F*iE+i*iT+i*iF+i*ii+i*i所以i+i*i 是文法的句子。该文法产生的语言是程序设计语言中的算术运算式，其中包括加、乘和括号运算。,语法树,在自然语言中，句子结构可以借助一种树形表

22、示进行分析。如下面的句子：They are students and teachers of the Physics Department。对该句子的结构进行分析，其树型结构如图2-3所示，由此可以看出，该句子是由主语、系词和表语组成，是一个语法正确的句子。,在自然语言中，可以通过树型表示直观地分析句子的结构；在形式语言中，我们提到了句型、推导的概念，在证明某个符号串是否是某个文法的句型时，采用从文法开始符号推导的方法，这个推导过程可以用语法树直观的表示出来。语法树也称为推导树，其定义如下：,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树，这棵树满足下列四个条件：

23、（1）每个结点都有一个标记，此标记是V的一个符号。（2）根的标记是S。（3）若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。（4）如果结点n的直接子孙，从左到右的次序是结点n1,n2,n3.nk，其标记分别为A1，A2，A3，AK。那么AA1A2A3AK一定是P中的一个产生式。,例2.23 设文法GS：EE+T|TTT*F|FF(E)|i证明符号串E+(E+T)*i是文法的句型。,二义性文法及其他,1二义性文法及其定义一个文法，如果它的一个句子或句型有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则称该文法具有二义性。例2.24 设文法GS：

24、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就只有

25、图2-5左边的树形结构了。,2二义性文法的证明,要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。即不存在一个算法，它能在有限的步骤内，确切的判断出某个给定的文法是否是一个二义性文法。我们要证明一个文法是否是一个二义性文法，就是找到该文法的一个句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。,例2.25 文法G=（E，+，*，I,(,)，P，E）其中P为：Ei EE+EEE*EE(E)证明该文法是二义性文法，并将该文法改为等价的非二义性文法（等价的文法是指产生的语言相等的文法）。,【证明】取句型i*i+i，写出该句型的两个不同的推导。画

26、出推导的两棵不同的语法树。推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i推导的两棵语法树如图2-6所示。将文法改为非二义性文法为：ET|E+TTF|T*FF（E）|i,文法产生的语言和产生语言的文法,例2.26 设G=（VN，VT，P，S），VN=S,B,E，VT=a,b,c，P由下列产生式组成：SaSBESaBEEBBEaBabbBbbbEbeeEee（1）问该文法是Chomsky哪一类型的文法？（2）它生成的语言是什么？,答：根据文法分类定义，由于文法中存在产生式，其左部由长度大于1的符号串构成，如产生式“EBBE”，显然不符合

27、Chomsky 的2型和3型文法的定义。该文法产生式左部串的长度均小于等于右部串的长度，符合1型文法的定义，所以该文法是上下文有关文法。,（2）根据如下推导：对于每一个n1，我们将号产生式使用n-1次，得到推导序列：S an-1S(BE)n-1，然后使用产生式(2)一次，得到：S an(BE)n，然后从an(BE)n.继续推导，总是对EB使用产生式的右部进行替换，而最终在得到的串中，所有的B都限于所有的E。设n=3，aaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S anBnEn.接着，使用产生式(4)一次,得到SanbBn-1En，然后使用产生式n-1 次得到：

28、S anbnEn，然后使用产生式一次，使用产生式n-1次，得到：S anbnen 因此该文法产生的语言是L(G)=anbnen|n1。,例2.27 设有上下文无关文法如下：GS：SABAUTUa|aUTb|bTBc|cC将文法的产生式代入产生如下文法：GS：SUTB Ua|aUTb|bTBc|cC,考察文法，用L(S)，L(U)，L(T)和L(B)分别表示从终结符S，U，T和B出发推导出的符号串的集合，不难发现：L（U）=ai|i1=a+L（T）=bj|j1=a+L（B）=ck|k1=a+由于有SUTB，则有：L（S）=L(U)L(T)L(B)=(aibjck|i1,j1,k1)=a+b+c+

29、,例2.28 构造一个上下文无关文法G，使其描述的语言L（G）是能够被5整除的无符号整数集合。能够被5整除的整数其结构特点是，末位数一定是0或5。所以，只要保证生成的整数末位数字是0或5即可。据此，构造描述能被5整除的无符号整数集合的文法如下：GS：SN0|N5NDN|D0|1|2|3|4|5|6|7|8|9,例2.29 写出一个上下文无关文法G，使得L(G)=anbmcmdn|n0，m1分析该语言的特点，可以看出，a和d的个数是一样的，b和c的个数是一样的。m的取值范围从1开始，所以至少有一个bc，n的最小值为0。写出文法为：SaAd|A AbAc|bc,2.4句型分析与句柄,对于上下文无关

30、文法，语法树是句型推导过程的几何表示；是进行句型分析极好的工具。所谓句型分析就是识别一个符号串是否是某一个文法的句型。进一步说就是给定一个符号串时，按照某文法的规则为该符号串构造推导或语法树，以此来识别它是文法的一个句型。对于上下文无关文法，其句型分析方法有两大类，一类是自上而下的分析方法（又称自顶向下），另一类是自下而上（自底向上）的分析方法。,2.4.1 自上向下的分析方法,1基本思想 自上而下的分析方法就是从识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就不是。或者说，以文法的识别符号作为根结点，看是否能构造出一个语法树，而且

31、此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则就不是。,例2.30 设文法GS：SaAbc|aBAbaBbeB|d输入串：abed，识别该串是否是该文法的一个句子。方法：从文法的识别符号S开始出发，选择它的一个产生式SaAbc 得到直接推导S aAbc以识别符S作为根结点，构造语法树，如下图2-7所示,2分析过程,符号串aAbc与待检查的符号串abed的第一个符号相匹配。由于符号串aAbc的第2个符号是非终结符，因此需要对它进行替换。A只有一个产生式Aba。以其右部替换A，得推导SaAbcababc得到

32、语法树，如图2-7（b）所示。符号串ababc与待查符号串abed的第2个符号相匹配，但与第3个符号不相匹配，匹配失败。此时，需要退回到非终结符 A，重新选择S另外的产生式，再做试探。这种选择的过程称之为回溯。,选择S的另外一条产生式的规则SaB，得到直接推导SaB，得到语法树2-7（c），再选取其中的一条产生式BbeB，得到推导SaBabeB，得到语法树如图（d），将Bd代入即可得到该字符串abed。,3存在问题,自上而下分析方法是从文法的识别符号开始，选择相应的产生式规则进行推导。但在推导过程中会出现回溯现象。我们把出现回溯的分析称为不确定的自顶上下分析方法。这种方法花费时间多，效率低，编

33、程实现时复杂，如果对文法加以限制，就可以避免回溯，这就出现了我们后面要提到的LL(1)分析方法,确定的自上而下的分析方法,例2.31 设文法GSSaBc|bCdBeB|fCdC|c试检查符号串aefc是不是该文法的句子。,识别符S有两条产生式，它们的右部首符号分别是终结符a和b。待检查符号串aefc的首符号是a，所以从识别符S出发，只能选择其产生式SaBc得到直接推导SaBc得到语法树如图2-8（a）所示。其中，非终结符B有两条产生式，它们右部首符号分别是终结符e与f，而待检查的符号串aefc的第2个符号是终结符e，所以选择B的产生式BeB得到推导SaBcaeBc，得到语法树如图2-8（b）所

34、示。,由于待检查的符号串aefc的第3个符号是终结符f，因而对句型aeBc中的非终结符B选择其产生式Bf的推导SaBcaeBcaefc得到语法树如图2-8（c）所示。如此推导出的符号串aefc，语法树的叶子结点序列是aefc，与待检查的符号串aefc相匹配。,例2.32 若有文法GSSAp|BqAaAcABbBdB当输入串W=ccap，那么试图推出输入串的推导过程为：SApcApccApccap很容易构造相应语法树，如图2-9所示。,自下而上的分析方法,1基本思想自下而上的分析方法的基本思想是从待检查的符号串出发，看最终是否能归约到文法的识别符号。如果能归约到文法的开始的识别符号，则表明此待检

35、查的符号串是该文法的一个句型或句子，否则便不是。,例2.33 若有文法GSScAdAabAa识别输入串w=cabd是否是该文法的句子。首先从输入串开始，扫描cabd，从中寻找一个子串，该子串与某一产生式的右端相匹配。子串a和子串ab都是合格的，假若我们选用了ab，用产生式的左端A去替代它，即把ab归约到A，得到串cAd。构造一个直接推导cAdcabd，即从cabd叶子开始向上构造语法树，接下去在得到的串cAd中又找到了子串cAd与产生式的右端相匹配，则用S替代cAd，或称将cAd归约到S，得到了又一直接推导ScAd，形成了最终的语法树。分析过程如图2-10所示。,2存在问题,在自上向下的分析中

36、，假定要被代换的最左非终结符的符号是V，且有n条规则：V1|2|3|n，那么如何确定用哪个右部去替换V？有一种解决方法是从各种可能的选择中挑选一种，并希望它是正确的。如果发现它是错误的，我们必须退回，再试着进行另外的选择，这种方式称为回溯。,在自下向上的分析方法中，在分析程序工作的每一步中，都从当前串中选择一个子串，将它归约到某个非终结符号，我们暂且把这个子串称为“可归约串”。出现的问题是如何确定这个“可归约串”？比如在上例中，我们在对输入串cabd 的分析中，如果不是选择ab，用产生式，而是选择a，用产生式将a归约到A，那么最终就达不到S的结果，也就不知道cabd是一个句子。因此在归约时，a

37、b是“可归约串”而不是a。如何求“可归约串”成为自下而上进行分析的关键。下面我们用“句柄”的概念来描述“可归约,3句柄的概念,（1）形式化定义定义2.21令G是一文法，S是文法的开始符号，是文法的一个句型。如果有：SA且A则称是句型相对于非终结符A的短语。特别地，如有A则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。（2）求一个句型的句柄给定某个句型，要求出该句型的句柄，比较直观的方法就是画出该句型的语法树。该语法树的一棵子树的叶子结点（从左到右）组成的符号串便是这个句型关于子树根结点的一个短语。,语法树的一棵简单子树（只有单层子树）的叶子结点组成的符号串是这个句型关

38、于简单子树根结点的一个直接短语。语法树的最左的简单子树叶子结点组成的符号串就是这个句型的句柄。例2.34 已知文法GS：S(R)|a|RTTS,T|S句型=(a,(T),(S,T)的语法树如图2-11所示。,【解答】观察该语法树，共有10个非叶子结点，10棵子树。因此有短语aT(T)S,T(S,T)(T),(S,T)a,(T),(S,T)(a,(T),(S,T),文法的存储,一个文法的语法图由该文法所有非终结符的定义图组成。每个非终结符号的定义图是一个结构型数据。名字定义下一个候选式右部后继写成高级语言的结构型数据形式，则为：type struc=boxesboxes=recordname:a

39、rray110 of char;def:struc;nextp:struc;rights:struc;end;,其中，“名字”是用某种内部形式表示的终结符号或非终结符号的名字。“定义”是一个指针，对于非终结符号，它指向其第一个侯选式结构图的开始位置。对于终结符号，它为0；“下一个侯选式”是一个指针，指向相同左部的下一个侯选式的开始位置。若无侯选式，则它为0；“右部后继”是一个指针，指向同一个右部的下一个符号。另用一个一维数组记录所有的非终结符号定义图的开始地址。也就是说，这个数组的每个元素都是一个指针，分别指向相应的非终结符号的第一个候选式的定义图。,例2.35文法EEAT|TTTMF|FF（

40、E）|iA+|M*|/按照上面的存储结构，画出文法的存储结构如图2-12所示：,小 结,文法是形式语言的一个十分重要的基本概念。文法可定义为一个四元组，文法G=（VN，VT，P，S），其中，VN是一个非终结符集，VT是一个终结符集，P是一个产生式集，S是文法的开始符号。Chomsky 将文法分为0 型，1型，2型和3型文法。程序设计语言的词法规则属于3型文法（正规文法），程序设计语言的语法和语义部分一般是采用2型文法来描述。,对于一个文法，我们需要研究它的句型，句子和语言。要识别一个符号串是不是一个文法的句子，需要对它进行语法分析。分析方法有两类，一类是自上而下分析法，另一类是自下而上的分析方

41、法。为了进行语法分析，需要事先将产生式存储在计算机中。可以为文法建立一个产生式表，把文法的所有的产生式都放在这个产生式表中。为了在分析过程中能迅速查找到相应的产生式，还可以建立一个目录表。,习 题,1设字母表A=a，符号串x=aaa，写出下列符号串及其长度：x0，xx，x5以及A+和A*。2令=a,b,c，又令x=abc，y=b，z=aab，写出下列符号串及它们的长度：xy，xyz，(xy)3。3设文法GS：SSS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。4已知文法SAB A|aA Bbc|bBc写出该文法描述的语言。,5已知文法ET|E+T|E-TTF|T*F|T/FF(E)|i写出该文法的开始符号、终结符集合VT、非终结符集合VN。,6对于文法ET|E+T|E-TTF|T*F|T/FF(E)|i写出句型T+T*F+i的短语、简单短语以及句柄。7设计出语言anbm|n,m1的文法。8文法G=(A，B，S，a,b,c,P,S)其中P为：SAc|AbAabBbc写出LGS）的全部元素。,9已知文法ZaZb Zab 写出L（GZ）的全部元素。10为句子i+i*i构造两棵语法树，从而证明下述文 法是二义性的。i|()|+|*|/11写出生成下述语言的上下文无关文法。（1）anbnambm|n,m0(2)1n0m1m0n|n,m012句型、句子和语言之间有什么关系？,