Chapt文法和语言实用PPT课件

1、学习重点学习重点n1 文法的定义、分类和二义性n2 最左推导、规范推导(或最右推导)n3 语言、句型和句子n4 短语、简单短语(或直接短语)和句柄n5 语法树第1页/共81页形式形式语言语言(P12)n如果不考虑语义和语用，只从语法这一侧面来看语言，它是由符合某种语法（用规则定义）的句子构成的集合，这种意义下的语言称作形式语言。 例 汉语：所有符合汉语语法的句子的全体 英语：所有符合英语语法的句子的全体 程序设计语言：所有符合该语言语法的程序的 全体第2页/共81页形式形式语言语言n形式语言抽象地定义为一个数学系统，即能用数学符号和规则描述的语言。形式语言理论是对符号串集合的表示法、结构及其特

2、性的研究。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。第3页/共81页2.1 2.1 字母表和符号串字母表和符号串(P12) 字母表 (或符号集) ：元素的非空有穷集合。例 二进制数语言的字母表=0,1 汉语的字母表中包括汉字、数字及标点符号等 PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成 C语言的字母表由字母、数字、若干专用符号以及if、else、while等关键字组成第4页/共81页2.1 2.1 字母表和符号串字母表和符号串 符号：字母表中的元素。 例 =a,b,for,1，则a,b,for,1都是的符号。 不要把符号理解成字符。

3、 典型的符号有字母、数字、各种标点符号和各种运算符。 第5页/共81页2.1 2.1 字母表和符号串字母表和符号串 符号串：由字母表上0个或多个符号所组成的任何有穷序列。空符号串 也是字母表上的符号串，它由0个符号组成。例 =0,1，则， 0，1，01，10，00，11，100，0110，111110000等二进制数都是上的符号串 =a,b,c,+,*，则， a ， b ， c ， + ， *，aa，ab，ac，a+，a*，ba，bb，bc，b+，b*，aaa，bbb等都是上的符号串一个字母表上的全部符号串所组成的集合是无穷的。 第6页/共81页2.1 2.1 字母表和符号串字母表和符号串 符

4、号串的长度：指符号串x中所含符号的个数，记为|x|。特别地， |=0。例 =a,b,c,+,*， |abc|=3，|abc+*abc|=8符号串相等：若x、y是字母表上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。例 当x=abbc，y=abbc 时，则x=y 当x=ab，y=ba 时，则xy 第7页/共81页2.1 2.1 字母表和符号串字母表和符号串 符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串。例 u、uni、university都是university的前缀符号串的后缀：指从符号串x的开头删除0或多个符号后得

5、到的符号串。例 ty、sity、university都是university的后缀 符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，例 ver是university的子串, 符号串的前缀、后缀都是它的子串。第8页/共81页2.1 2.1 字母表和符号串字母表和符号串 符号串的连接：若x、y是两个符号串，则xy是将符号串y连接在符号串x的后面。例 x=ab，y=ba，则 xy=abba若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。 除x=x=x外，连接没有交换率， 即 xy yx 。 第9页/共81页2.1 2.1 字母表和符号串字母表和符号串 集合的乘积运算

6、：令A、B为两个符号串集合，AB=xy|xA ,yB 。对于空集合有，有 A=A =A 。例 A=a,b， B=c,d，则AB=ac,ad,bc,bd 符号串的幂运算：若x是符号串，则： x0=, x1=x ， x2=xx，xn=xxx=xxn-1=xn-1 x，其中 n0 。 例 x=abc, x0=， x1=abc， x2=abcabc，第10页/共81页2.1 2.1 字母表和符号串字母表和符号串 集合的幂运算：设A为符号串集合，则： A0= A1=A A2=AA An=AAA=AAn-1=An-1 A，其中 n0 例 A =a，b，则 A0= A1=a,b A2=aa,ab,ba,bb

7、 第11页/共81页2.1 2.1 字母表和符号串字母表和符号串 集合的正闭包：设A为一个集合，则： A+ =A1A2.An例 A =a,b，则A+ =a,b,aa,ab,ba,bb,aaa,aab,集合的闭包：设A为一个集合，则： A* =A0 A+ 例 A =a,b，则A* =,a,b,aa,ab,ba,bb,aaa,aab,一个集合的闭包比正闭包多个。 第12页/共81页例：2.2 文法(P14) 文法实际上就是描述语言语法结构的形式规则。 第13页/共81页第14页/共81页例终结符号集Vt=the, gray, wolf, will, eat, goat非终结符号集Vn=, , ,

8、, , , , , , 产生式集P= , 开始符号Z= 又称为语法规则集，即符号的组成规则组成语言的基本符号语言的语法成分第15页/共81页文法G的形式定义：G=(Vn，Vt，P，Z)Vn(非终结符号集)是一个由非终结符号（一般是大写字母或用）构成的非空有穷集合。Vt (终结符号集)是一个由终结符号（如小写字母、数字、标点符号等）构成的非空有穷集合。 VtVn=，VtVn，V是该文法的字母表或词汇表。P(产生式集)是一个由产生式或规则构成的非空有穷集合。 产生式的形式为： 或:= 产生式的左部V+，即不能为空，产生式的右部V*，“”或”“:=”含义相同，表示“定义为”或“由组成”。Z是文法的识

9、别符号或开始符号， Z Vn，要求Z至少必须在某个产生式的左部出现一次。第16页/共81页2.2 2.2 文法文法例2-1(P15)文法 G1=(Vn，Vt，P，Z)，其中：Vn=， ， ， ， ， Vt= the，ate，banana，monkey P由下面8条规则组成:识别符号： the ate banana monkey 第17页/共81页2.2 2.2 文法文法例2-1(P15)文法 G1可以简化写成： G1 : the ate banana monkey the ate banana monkey 或第18页/共81页2.2 2.2 文法文法 例2-2(P15) 有如下简化表示文法，

10、只给出规则集，写出该文法的终结符号集合、非终结符号集合和识别符号。0123456789解：根据简化约定，可确定：Vn=, Vt=0,1,2,3,4,5,6,7,8,9识别符号：第19页/共81页2.2 2.2 文法文法文法的EBNF表示（P16）：用一些特殊的元符号“|”、“”和“”、“”、“（” 和“）”、“” 和“”来表示文法。例2-3 对例2.2文法的13条规则可缩写成： := :=| :=0|1|2|3|4|5|6|7|8|9“|”：表示“或” 。 对于具有相同左部的那些规则， 如 1， 2 ， n 缩写为: 1 |2 |n第20页/共81页2.2 2.2 文法文法“”：用于括起由中文

11、字组成的非终结符号或由多个字母组成的符号。例（一般写成monkey ）第21页/共81页2.2 2.2 文法文法“”和“”：表示可重复连接，tkm表示符号串t可重复连接k到m次，而t表示符号串t可重复连接0到无穷次。例13 等价于： | EE+T|T 与 ET+T 相同字母打头、后面可跟字母或数字的不超过8个字符的标识符文法则为： |07第22页/共81页2.2 2.2 文法文法“”和“ ”：表示括起来的内容可有可无。如t表示符号串t可有可无。例 IF THEN IF THEN ELSE 可写成： IF THEN ELSE 第23页/共81页2.2 2.2 文法文法“（”和“）”：表示括号内的

12、成分优先。常用于在规则中提取公因子。例 Uxy|xw|xz 可写成： Ux（y|w|z）第24页/共81页2.2 2.2 文法文法 课堂练习（1）已知字母表=begin, end, if, then, else，则它的符号有_。（2）某程序设计语言的一个源程序，就是该语言字母表上的满足相应语法规则的一个_。 A. 终结符号 B. 非终结符号 C. 字符串 D. 文法（3）已知文法 SaBc | bAB AaAb| b Bb | 写出该文法的开始符号、 Vn和Vt。第25页/共81页2.132.13文法和语言分类文法和语言分类（P26P26） 0型文法(或短语结构文法) 若文法中有如下形式的规则

13、： 其中， V+ (即可以是V上的符号序列，但不能为空)，V* (即是V上的符号序列，可以是) 。如果文法中有产生式的右部为，并且该产生式的左部不是一个非终结符，则该文法一定是0型文法。0型文法描述的语言为0型语言。例 文法G1=(Vn,Vt,P,S)，其中：Vn=S,A,B,C,D,E ，Vt=a ，P=S:=ACaB,Ca:=aaC,CB:=DB,CB:=E,aD:=Da,AD:=AC,aE:= ，该文法是一个0型文法。 第26页/共81页2.132.13文法和语言分类文法和语言分类（P26P26） 1型文法(或上下文有关文法) 若文法中有如下形式的规则： Uu 其中， UVn，、V*，u

14、 V* ，即规则左部可为符号序列，其中U为非终结符号且只有在左右为和的环境下U可变为u。1型文法的产生式左部的长度小于等于其右部的长度，但S除外。1型文法描述的语言为1型语言。例 文法G2=(Vn,Vt,P,S) ，其中, Vn=S,A,B,C ，Vt=a,b,c ，P=S:=aSBC,S:=aBC,aB:=ab,bB:=bb,bC:=bc,CB:=BC,cC:=cc ，该文法是一个1型文法。第27页/共81页2.132.13文法和语言分类文法和语言分类（P26P26） 2型文法(或上下文无关文法) 若文法中的规则都具有如下形式： Uu 其中， U Vn ， u V*，即2型文法中的规则左部必

15、须是一个非终结符号，规则右部u是V上的符号序列。该文法相当于对1型文法中的规则形式加以限制，即要求和必须为空。2型文法也称作上下文无关文法，描述的语言为2型语言。一般用2型文法来描述程序设计语言的语法规则。例 文法G3=(Vn,Vt,P,N) ，其中, Vn=N,D ，Vt=0,1,2,3,4,5,6,7,8,9 ，P=N:=ND|D,D:=0|1|2|3|4|5|6|7|8|9 ，该文法是一个2型文法。第28页/共81页2.132.13文法和语言分类文法和语言分类（P27P27） 3型文法(或正规文法) 若文法中的规则都具有如下形式： Ua |Wa（左线性）或 Ua|aW（右线性） 其中，

16、U，WVn，aVt ( a可为)。 3型文法中的产生式全部是左线性产生式或全部是右线性产生式。 3型文法描述的语言为3型语言。用3型文法描述程序设计语言的单词的构词规则，如标识符、无符号整数等。例 左线性3型文法： NN0|N1|N2|N3|N4|N5|N6|N7|N8|N9 N0|1|2|3|4|5|6|7|8|9 这个文法定义的语言就是无符号整数。 第29页/共81页2.132.13文法和语言分类文法和语言分类 练习 判断以下文法的类型 S:=ABCC:=BCC:=ABA:=GEBG:=GBFAG:=ADDB:=BDDE:=AEFB:=BFFE:=EaAA:=文法GZ:Z:=0B|1CB:

17、=1Z|1C:=0Z|00型文法3型文法第30页/共81页2.132.13文法和语言分类文法和语言分类 练习 判断以下文法的类型 文法GS:S:=AA:=aABD|abBBD:=CBCB:=CDCD:=BDbB:=bbD:=c文法GZ:Z:=B0C|C1B:=Z1|1C:=Z0|01型文法2型文法第31页/共81页文法的四种分类第32页/共81页2.132.13文法和语言分类文法和语言分类四种文法的关系：通过对文法的产生式逐渐增加限制来定义四种文法，因此 0型语言包含1型语言，1型语言包含2型语言，2型语言包含3型语言。或者说，3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0

18、型文法的特例 。第33页/共81页n直接推导（）：是文法G的一个产生式， x,yV*，符号串xy中的非终结符号用替换，从而得到符号串xy，则表示为： xy xy 其中“”读为“直接推导出”或“直接产生” 。即称xy直接推导出xy,或xy直接产生xy。若从反方向看，则称xy直接归约到xy。显然，文法的产生式右部是其左部的直接推导。 例 已知文法GS： S0S1， S010S10011 (使用规则S01,x=0,y=1)S 0S1 (使用规则S0S1,x=,y=)0S100S11 (使用规则S0S1,x=0,y=1)2.3 2.3 推导推导(P17) 第34页/共81页2.3 2.3 推导推导 练

19、习 已知文法G:| a|b|z 0|1|9 指出下面直接推导所使用的规则： abc abc5第35页/共81页n推导（ ）：如果存在一直接推导序列0 1 n， 则表示为： 0 n 其中， “ ”读为“推导出”或“产生”，即 0推导出或产生n。若从反方向看，则称n归约到0。 n 是推导长度，要求n0 。2.3 2.3 推导推导 +第36页/共81页2.3 2.3 推导推导例 已知文法： := :=| :=0|1|2|3|4|5|6|7|8|9有： 2 将上述三个直接推导连接起来，可得如下推导过程： 2则记： 2，显然，n=3。+第37页/共81页n广义推导（ ）：如果有0 n 或0 =n, 即n

20、 0，则表示为： 0 n 其中， “ ”读为“广义推导出”或“广义产生”。若从反方向看，则称n广义归约到0。2.3 2.3 推导推导 +*第38页/共81页2.3 2.3 推导推导例 已知文法： := :=| :=0|1|2|3|4|5|6|7|8|9 2，也可记为： 2， 从到的推导，无须使用任何规则，其推导长度n=0，则记作： +*第39页/共81页2.3 2.3 推导推导 例 GS:SaASASbAASSSaAba证明S aabbaa。证明：第1种 SaASaAaaSbAaaSbbaaaabbaa 第2种 SaASaSbASaabASaabbaSaabbaa第3种 SaASaSbASaS

21、bAaaabAaaabbaa+第40页/共81页2.3 2.3 推导推导规范推导（或最右推导）：在推导的任何一步，都是对中的最右非终结符进行替换。最左推导：在推导的任何一步，都是对中的最左非终结符进行替换。例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(规范推导) SaASaSbASaabASaabbaSaabbaa(最左推导) SaASaSbASaSbAaaabAaaabbaa(非左非右推导)+第41页/共81页2.4 2.4 句型和句子句型和句子（P18P18）句型：设Z是文法G的识别符号，如果Z x，xV* ，则称符号串x为文法G的一个句型。显然，Z是文法

22、G的一个句型。*例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa 则, aAS、aAa、aSbAa、aSbbaa和aabbaa是该文法的句型，也是该文法的规范句型。+规范句型：能用规范推导产生的句型。第42页/共81页2.4 2.4 句型和句子句型和句子句子:设Z是文法G的识别符号，如果Z x，xVt* ，则称符号串x为文法G的一个句子。显然，句型包括句子或说句子是特殊的句型，句子是完全由终结符号组成的句型。+例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa则, aabbaa是该文法的句子。+第43页/共81页2.4 2.4 句型和句子句

23、型和句子每一个句子都有一个规范推导，但并非每一个句型都有规范推导。例 := :=| :=0|1|2|3|4|5|6|7|8|9 2句型“2 ”不是规范句型 3 3句型“3”是规范句型 第44页/共81页2.5 2.5 语言语言（P19P19）语言:一个文法GZ所产生的所有句子的集合L(GZ), 称为文法GZ所定义的语言, 即: L(GZ)=x|xVt* , 且Z x 例 已知文法GS：S:=0S1|01，求其所产生的语言。解： S 01 S 0S1 0011 S 0S1 00S11 000111 L(GS)=01，0011，000111，=0n1n|n0+第45页/共81页2.5 2.5 语言

24、语言例 the ate banana monkey 其语言只有下面4个句子： the monkey ate the banana the banana ate the monkey the monkey ate the monkey the banana ate the banana第46页/共81页2.5 2.5 语言语言练习句子:=主语谓语 主语:=代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:=动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词下列是否是句子？我是大学生王明是大学生王明学习英语他学习英语你是工人下列是否是句子？

25、我大学生是大学生是王明英语学习王明大学生学习他工人是英语第47页/共81页2.5 2.5 语言语言 文法和语言的关系：给定一个文法，就能从结构上唯一的确定其语言，即: GL(G)。给定一种语言，能确定其文法，但不唯一，即: LG1 或G2 或。等价文法：如果不同的文法可描述相同的语言，则称这些文法为等价文法。文法语言1:1n:1第48页/共81页2.5 2.5 语言语言例2-5(P19) 已知语言为 L(G)=abna|n 1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为: ZaBa BBb|b 还可以构造文法G1为: ZaBa BbB|b 显然，G和G1是两个不同的文法，但它们

26、都可以描述语言abna|n1,因此它们是等价文法。 第49页/共81页2.62.6递归规则与递归文法递归规则与递归文法(P20)(P20)递归规则：是指那些在规则的右部含有与规则左部相同符号的规则。右递归规则： 形如U:=xU的规则。例 U:=xUy，因为规则右部含有与规则左部相同符号U， 所以U:=xUy就是一条递归规则。左递归规则：形如U:=Uy的规则。第50页/共81页2.62.6递归规则与递归文法递归规则与递归文法直接递归文法：至少包含一条递归规则的文法。例 设文法GA: A:=B B:=X|BA X:=Xa|Xb|a|b该文法是一个具有直接左递归性的文法。 第51页/共81页2.62

27、.6递归规则与递归文法递归规则与递归文法间接递归文法：表面上看文法的每条规则都不是递归规则，但存在某个推导会导致递归出现。例 设有文法GS: S:=Qd Q:=Rb|Se R:=Sa|Qf|a S Qd Sed，即S Sed文法G是一个间接递归文法。+第52页/共81页2.62.6递归规则与递归文法递归规则与递归文法语言的句子的个数是有穷还是无穷取决于定义该语言的文法是否是递归的。例 例2-1（P15）的文法是无递归的，因此其所产生的句子是有穷的，只产生4个句子。例2-3（P16）的文法有递归规则，属于递归文法，所以它所描述的语言为所有无符号整数，是无穷的。第53页/共81页2.62.6递归规

28、则与递归文法递归规则与递归文法递归文法包括直接递归文法和间接递归文法，运用递归文法使我们能用有穷的文法刻画无穷的语言。练习 判定如下文法所描述的语言是否是有穷的。 S:=(S) S:=解：因为文法中的第一条产生式S:=(S)是递归规则，所以该文法是递归文法，所描述的语言为L(GS)=,(),(),(), =(n)n|n0，是无穷的。第54页/共81页2.8 2.8 语法树语法树(P21)(P21)语法树（或推导树）：用树形结构来直观地表示句型的推导过程。设有文法G=(Vn,Vt,P,S)，对于文法G的任意一个句型都存在一棵相应的语法树，这棵树满足下列4个条件：如果树中的一个结点A有若干个直接后

29、继，从左到右分别是B1,B2,B3,Bn，则有A:=B1B2B3Bn P。如果树中的一个结点至少有一个直接后继，则说明该结点一定是一个非终结符号。树的根结点是文法的开始符号S。树中的每个结点都有一个标记，此标记是V中的一个符号。第55页/共81页2.8 2.8 语法树语法树例: GS:SaASASbAASSSaAba例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(规范推导) SaASaSbASaabASaabbaSaabbaa(最左推导) SaASaSbASaSbAaaabAaaabbaa(非左非右推导)+第56页/共81页2.8 2.8 语法树语法树文法的句型

30、都是按照文法的产生式来生成相应的语法树，其生成过程如下：推导过程不同，生成语法树的过程也不同，但是，如果文法是无二义性的，则最终生成的语法树是相同的。语法树的末端节点（叶节点）从左向右排列起来，构成句型。如果叶节点都是终结符号，则从左向右构成句子。b.根据句型的结构特点来选择文法中产生式，最终生成该句型对应的语法树。a.以文法G的开始符号作为语法树的根结点第57页/共81页2.8 2.8 语法树语法树练习：已知文法 SaBc | bAB AaAb| b Bb | 写出符号串babbb的规范推导，并画出语法树。第58页/共81页2.10 2.10 由树构造推导过程由树构造推导过程（P23P23）

31、根据已有的语法树，可以从上而下或从下而上建立推导。从下而上的方法：逐层地修剪子树末端节点来建立推导。当有两棵以上子树时，原则上修剪那一棵都可以，如果每次总是修剪最左边的子树，即相当于每步都对归约句型的句柄归约，则称为“最左归约”或“规范归约”。规范推导与规范归约互为逆过程。 从上而下的方法：从树根开始由上而下逐层地用子节点代替父节点。当一层中有两棵以上子树根时，原则上先选哪一棵树根替换都可以。而每步都对最右边的子树树根符号替换，则构造出的推导是规范推导。第59页/共81页2.10 2.10 由树构造推导过程由树构造推导过程练习 已知文法： E:=E+T|T T:=T*F|F F:=(E)|i

32、句型E+(E+T)*i对应的语法树如图所示,请根据该语法树写它的规范推导。第60页/共81页2.10 2.10 由树构造推导过程由树构造推导过程句型E+(E+T)*i的规范推导：第61页/共81页2.10 2.10 由树构造推导过程由树构造推导过程语法树和推导之间的对应关系：每一棵语法树至少存在一个推导与之相对应每一个推导都存在一棵语法树语法树推导1:n1:1第62页/共81页2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄（P21P21）短语：设GZ是一文法, w=xuy是一句型,如果有 Z xUy 且U u ,其中UVn , uV+,则称u为句型w(相对于非终结符号U)的短语。显然

33、,w是相对Z的句型w的短语。句柄：任一句型的最左简单短语称为该句型的句柄。一个句型的句柄一定是该句型的简单短语。 简单短语(或直接短语)：若有 Z xUy 且U u，则称u是句型w相对于非终结符号U的简单短语。一个句型的直接短语一定是该句型的短语。 *+*第63页/共81页2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄求一个句型的短语、简单短语和句柄的方法: 语法树（建议用该方法）：由文法的开始符号开始，通过产生式来构造与该句型相对应的语法树。推导法：由文法的开始符号开始，找出该句型的所有推导。第64页/共81页2.9 2.9 子树和短语子树和短语(P22)(P22)例 已知文法：

34、E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i对应的语法树如图所示,请根据该语法树写它的短语、简单短语和句柄。第65页/共81页2.9 2.9 子树和短语子树和短语句型E+(E+T)*i的短语为： E+(E+T)*i、 (E+T)*i 、 (E+T)、 E+T 、 i句型E+(E+T)*i的简单短语为： E+T 、 i句型E+(E+T)*i的句柄为： E+T第66页/共81页2.9 2.9 子树和短语子树和短语例 GS:SaASASbAASSSaAba 求句型aabbaa的短语、简单短语和句柄。句型aabbaa的短语为： aabbaa 、 abba、 a(左起第2

35、个) 、 ba 、 a(最后1个) 句型aabbaa的简单短语为： a(左起第2个) 、 ba 、 a(最后1个) 句型aabbaa的句柄为： a(左起第2个) 第67页/共81页2.9 2.9 子树和短语子树和短语课堂练习已知文法 GZ:ZAbB | bBAA Ba | cBAb | d求句型cbdab的短语、简单短语和句柄。第68页/共81页2.11 2.11 文法的二义性文法的二义性（P23P23）二义性文法：如果一个文法所定义的某个句子或句型，它存在两棵（或两棵以上）不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。 例2-11(P23) 有文法GE：E = E+E |

36、E*E |（E）| i，分析该文法是否为二义性文法。EE+EE*EiiiEE*EEEiii+解：句子i+i*i存在两棵不同的语法树，因此文法G 是二义性文法。 第69页/共81页2.11 2.11 文法的二义性文法的二义性EE+EE*EiiiEE*EEEiii+语法树1 在语法树1中， i+i*i的规范推导为：EE+EE+E*EE+E*iE+i*ii+i*i即，在语法树1中的*先作为句柄归约，表示*优先于+进行运算。 语法树2 二义性产生的后果会导致分析结果不同，导致对句子的理解不同。因此，在算术表达式中规定乘除高于加减，从而避免二义性。 在语法树2中， i+i*i的规范推导为：EE*EE*i

37、E+E*iE+i*ii+i*i即，在语法树2中的+先作为句柄归约，表示+优先于*进行运算。第70页/共81页2.11 2.11 文法的二义性文法的二义性例2-12(P24) if语句文法如下： = ifthen |ifthenelse |说明该文法是二义性文法。解：假设有一个if语句嵌套的句型为：ifthen ifthenelse 该句型存在两棵不同的语法树，所以该文法是二义性文法。第71页/共81页2.11 2.11 文法的二义性文法的二义性语句 布尔表达式 if then语句 布尔表达式 ifthen语句 else 语句 语句 布尔表达式 if then语句 布尔表达式 if then 语

38、句 else语句 语法树1 语法树2 语法树1意味着else和第2个if配对（就近配对），语法树2表示else和第1个if配对。 因此，在if语句中规定else与最近的if配对(即就近配对)。第72页/共81页2.11 2.11 文法的二义性文法的二义性文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内确切地判定一个文法是否是二义性的。例2-13 改写文法GE： E = E+E | E*E |（E）| i，使其无二义性。解：新添非终结符号T和F，将文法改写成：E = T |E+T，T =F |T*F，F = (E) | i 这样，就避免了二义性。用改写后的文法给出句i+i*i的语法树如右图所示。此时的语法树是唯一的。 ET+EF*TTiFFii第73页/共81页2.12 2.12 有关文法的实用限制有关文法的实用限制（P25P25） 文法的实用限制：就是从实用的观点出发，对文法做一些必要的限制。以下是对文法的实用限制：文法不能是二义性的。不能有U =U这样的有害规则。不能有多余规则推导中始终用不到的规则。(不可达规则)一旦使用某规则后无法推出终结符号串的规则。(无用规则)第74页/共81页2.12 2.12 有关文法的实用限制有关文法的实用限制 检查多余规则的方法：检查文法中每一条规则