《Chapt文法和语言实用实用教案》由会员分享，可在线阅读，更多相关《Chapt文法和语言实用实用教案（82页珍藏版）》请在金锄头文库上搜索。
1、学习学习(xux)重点重点n1文法的定义(dngy)、分类和二义性n2最左推导、规范推导(或最右推导)n3语言、句型和句子n4短语、简单短语(或直接短语)和句柄n5语法树第1页/共81页第一页，共82页。形式形式语言语言(P12)n如果不考虑语义和语用，只从语法这一侧面来看语 言 ， 它 是 由 符 合 某 种 语 法 （ 用 规 则 定 义(dngy)）的句子构成的集合，这种意义下的语言称作形式语言。例 汉语：所有符合(fh)汉语语法的句子的全体 英语：所有符合(fh)英语语法的句子的全体 程序设计语言：所有符合(fh)该语言语法的程序的 全体第2页/共81页第二页，共82页。形式形式语言语
2、言n形式语言抽象地定义为一个数学(shxu)系统，即能用数学(shxu)符号和规则描述的语言。形式语言理论是对符号串集合的表示法、结构及其特性的研究。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。第3页/共81页第三页，共82页。2.1 2.1 字母表和符号串字母表和符号串(P12) 字母表 (或符号集) ：元素(yun s)的非空有穷集合。例 二进制数语言的字母表=0,1 汉语的字母表中包括汉字、数字(shz)及标点符号等 PASCAL语言的字母表是由字母、数字(shz)、若干专用符号及BEGIN、IF之类的保留字组成 C语言的字母表由字母、数字(shz)、若干专用符号以及if
3、、else、while等关键字组成第4页/共81页第四页，共82页。2.1 2.1 字母表和符号串字母表和符号串 符号(fho)：字母表中的元素。 例 =a,b,for,1，则a,b,for,1都是的符号(fho)。 不要把符号(fho)理解成字符。 典型的符号有字母、数字、各种标点符号和各种运算符。 第5页/共81页第五页，共82页。2.1 2.1 字母表和符号串字母表和符号串 符号串：由字母表上0个或多个符号所组成(z chn)的任何有穷序列。空符号串 也是字母表上的符号串，它由0个符号组成(z chn)。例 =0,1，则， 0，1，01，10，00，11，100，0110，1111100
4、00等二进制数都是上的符号串 =a,b,c,+,*，则， a ， b ， c ， + ， *，aa，ab，ac，a+，a*，ba，bb，bc，b+，b*，aaa，bbb等都是上的符号串一个(y )字母表上的全部符号串所组成的集合是无穷的。 第6页/共81页第六页，共82页。2.1 2.1 字母表和符号串字母表和符号串 符号(fho)串的长度：指符号(fho)串x中所含符号(fho)的个数，记为|x|。特别地， |=0。例 =a,b,c,+,*， |abc|=3，|abc+*abc|=8符号串相等(xingdng)：若x、y是字母表上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相
5、等(xingdng)时，则符号串x与符号串y相等(xingdng)，记作x=y。例 当x=abbc，y=abbc 时，则x=y 当x=ab，y=ba 时，则xy 第7页/共81页第七页，共82页。2.1 2.1 字母表和符号串字母表和符号串 符号串的前缀：指从符号串x的末尾删除0或多个(du )符号后得到的符号串。例 u、uni、university都是university的前缀符号串的后缀：指从符号串x的开头删除0或多个(du )符号后得到的符号串。例 ty、sity、university都是university的后缀 符号串的子串：指从符号串x的开头和末尾删除0或多个(du )符号后得到的
6、符号串，例 ver是university的子串, 符号串的前缀、后缀都是它的子串。第8页/共81页第八页，共82页。2.1 2.1 字母表和符号串字母表和符号串 符号串的连接：若x、y是两个(lin )符号串，则xy是将符号串y连接在符号串x的后面。例 x=ab，y=ba，则 xy=abba若x、y是字母表上的两个(lin )符号串，则xy也是字母表上的符号串。 除x=x=x外，连接(linji)没有交换率， 即 xy yx 。 第9页/共81页第九页，共82页。2.1 2.1 字母表和符号串字母表和符号串 集合的乘积运算：令A、B为两个(lin )符号串集合，AB=xy|xA ,yB 。对于
7、空集合有，有 A=A =A 。例 A=a,b， B=c,d，则AB=ac,ad,bc,bd 符号串的幂运算(yn sun)：若x是符号串，则： x0=, x1=x ， x2=xx，xn=xxx=xxn-1=xn-1 x，其中 n0 。 例 x=abc, x0=， x1=abc， x2=abcabc，第10页/共81页第十页，共82页。2.1 2.1 字母表和符号串字母表和符号串 集合(jh)的幂运算：设A为符号串集合(jh)，则： 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 第11页
8、/共81页第十一页，共82页。2.1 2.1 字母表和符号串字母表和符号串 集合(jh)的正闭包：设A为一个集合(jh)，则： A+ =A1A2.An例 A =a,b，则A+ =a,b,aa,ab,ba,bb,aaa,aab,集合的闭包：设A为一个(y )集合，则： A* =A0 A+ 例 A =a,b，则A* =,a,b,aa,ab,ba,bb,aaa,aab,一个(y )集合的闭包比正闭包多个。 第12页/共81页第十二页，共82页。例：2.2 文法(wnf)(P14) 文法实际上就是(jish)描述语言语法结构的形式规则。 第13页/共81页第十三页，共82页。第14页/共81页第十四页
9、，共82页。例终结符号集Vt=the, gray, wolf, will, eat, goat非终结符号集Vn=, , , , , , , , , 产生式集P= , 开始符号Z= 又称为语法规则集，即符号(fho)的组成规则组成语言的基本(jbn)符号语言的语法成分第15页/共81页第十五页，共82页。文法G的形式(xngsh)定义：G=(Vn，Vt，P，Z)Vn(非终结符号集)是一个由非终结符号（一般是大写字母或用）构成的非空有穷集合。Vt (终结符号集)是一个由终结符号（如小写字母、数字、标点符号等）构成的非空有穷集合。 VtVn=，VtVn，V是该文法的字母表或词汇表。P(产生式集)是一
10、个由产生式或规则构成的非空有穷集合。 产生式的形式(xngsh)为： 或:= 产生式的左部V+，即不能为空，产生式的右部V*，“”或”“:=”含义相同，表示“定义为”或“由组成”。Z是文法的识别符号或开始符号， Z Vn，要求Z至少必须在某个产生式的左部出现一次。第16页/共81页第十六页，共82页。2.2 2.2 文法文法(wnf)(wnf)例2-1(P15)文法 G1=(Vn，Vt，P，Z)，其中：Vn=， ， ， ， ， Vt= the，ate，banana，monkey P由下面8条规则组成:识别符号： the ate banana monkey 第17页/共81页第十七页，共82页。
11、2.2 2.2 文法文法(wnf)(wnf)例2-1(P15)文法 G1可以(ky)简化写成： G1 : the ate banana monkey the ate banana monkey 或第18页/共81页第十八页，共82页。2.2 2.2 文法文法(wnf)(wnf) 例2-2(P15) 有如下简化表示文法，只给出规则集，写出该文法的终结符号(fho)集合、非终结符号(fho)集合和识别符号(fho)。0123456789解：根据简化约定，可确定：Vn=, Vt=0,1,2,3,4,5,6,7,8,9识别符号：第19页/共81页第十九页，共82页。2.2 2.2 文法文法(wnf)(
12、wnf)文法的EBNF表示（P16）：用一些特殊(tsh)的元符号“|”、“”和“”、“”、“（” 和“）”、“” 和“”来表示文法。例2-3 对例2.2文法的13条规则可缩写成： := :=| :=0|1|2|3|4|5|6|7|8|9“|”：表示“或” 。 对于具有相同左部的那些规则， 如 1， 2 ， n 缩写为: 1 |2 |n第20页/共81页第二十页，共82页。2.2 2.2 文法文法(wnf)(wnf)“”：用于括起由中文字组成的非终结符号(fho)或由多个字母组成的符号(fho)。例（一般写成monkey ）第21页/共81页第二十一页，共82页。2.2 2.2 文法文法(wn
13、f)(wnf)“”和“”：表示可重复(chngf)连接，tkm表示符号串t可重复(chngf)连接k到m次，而t表示符号串t可重复(chngf)连接0到无穷次。例13 等价于： | EE+T|T 与 ET+T 相同字母打头、后面可跟字母或数字的不超过8个字符的标识符文法则为： |07第22页/共81页第二十二页，共82页。2.2 2.2 文法文法(wnf)(wnf)“”和“ ”：表示括起来的内容(nirng)可有可无。如t表示符号串t可有可无。例 IF THEN IF THEN ELSE 可写成： IF THEN ELSE 第23页/共81页第二十三页，共82页。2.2 2.2 文法文法(wn
14、f)(wnf)“（”和“）”：表示括号(kuho)内的成分优先。常用于在规则中提取公因子。例 Uxy|xw|xz 可写成： Ux（y|w|z）第24页/共81页第二十四页，共82页。2.2 2.2 文法文法(wnf)(wnf) 课堂练习（1）已知字母表=begin, end, if, then, else，则它的符号有_。（2）某程序设计语言的一个源程序，就是(jish)该语言字母表上的满足相应语法规则的一个_。 A. 终结符号 B. 非终结符号 C. 字符串 D. 文法（3）已知文法 SaBc | bAB AaAb| b Bb | 写出该文法的开始符号、 Vn和Vt。第25页/共81页第二十
15、五页，共82页。2.132.13文法和语言文法和语言(yyn)(yyn)分类（分类（P26P26） 0型文法(或短语结构文法) 若文法中有如下形式的规则： 其中(qzhng)， V+ (即可以是V上的符号序列，但不能为空)，V* (即是V上的符号序列，可以是) 。如果文法中有产生式的右部为，并且该产生式的左部不是一个非终结符，则该文法一定是0型文法。0型文法描述的语言为0型语言。例 文法(wnf)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:= ，该文法(wnf)是
16、一个0型文法(wnf)。 第26页/共81页第二十六页，共82页。2.132.13文法文法(wnf)(wnf)和语言分类（和语言分类（P26P26） 1型文法(或上下文有关文法) 若文法中有如下形式的规则： Uu 其中， UVn，、V*，u V* ，即规则左部可为符号序列，其中U为非终结符号且只有(zhyu)在左右为和的环境下U可变为u。1型文法的产生式左部的长度小于等于其右部的长度，但S除外。1型文法描述的语言为1型语言。例 文法G2=(Vn,Vt,P,S) ，其中(qzhng), Vn=S,A,B,C ，Vt=a,b,c ，P=S:=aSBC,S:=aBC,aB:=ab,bB:=bb,bC
17、:=bc,CB:=BC,cC:=cc ，该文法是一个1型文法。第27页/共81页第二十七页，共82页。2.132.13文法文法(wnf)(wnf)和语言分类（和语言分类（P26P26） 2型文法(wnf)(或上下文无关文法(wnf) 若文法(wnf)中的规则都具有如下形式： Uu 其中， U Vn ， u V*，即2型文法(wnf)中的规则左部必须是一个非终结符号，规则右部u是V上的符号序列。该文法(wnf)相当于对1型文法(wnf)中的规则形式加以限制，即要求和必须为空。2型文法(wnf)也称作上下文无关文法(wnf)，描述的语言为2型语言。一般用2型文法(wnf)来描述程序设计语言的语法规
18、则。例 文法G3=(Vn,Vt,P,N) ，其中(qzhng), 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页第二十八页，共82页。2.132.13文法和语言文法和语言(yyn)(yyn)分类（分类（P27P27） 3型文法(或正规(zhnggu)文法) 若文法中的规则都具有如下形式： Ua |Wa（左线性）或 Ua|aW（右线性） 其中， U，WVn，aVt ( a可为)。 3型文法中的产生式全部是左线性产生式或全部是右线性产生式。 3型文法描述的语言为3型语言。用
19、3型文法描述程序设计语言的单词的构词规则，如标识符、无符号整数等。例 左线性3型文法： NN0|N1|N2|N3|N4|N5|N6|N7|N8|N9 N0|1|2|3|4|5|6|7|8|9 这个文法定义的语言就是无符号(fho)整数。 第29页/共81页第二十九页，共82页。2.132.13文法文法(wnf)(wnf)和语言分类和语言分类 练习(linx) 判断以下文法的类型 S:=ABCC:=BCC:=ABA:=GEBG:=GBFAG:=ADDB:=BDDE:=AEFB:=BFFE:=EaAA:=文法(wnf)GZ:Z:=0B|1CB:=1Z|1C:=0Z|00型文法3型文法第30页/共8
20、1页第三十页，共82页。2.132.13文法和语言文法和语言(yyn)(yyn)分类分类 练习(linx) 判断以下文法的类型 文法(wnf)GS:S:=AA:=aABD|abBBD:=CBCB:=CDCD:=BDbB:=bbD:=c文法GZ:Z:=B0C|C1B:=Z1|1C:=Z0|01型文法2型文法第31页/共81页第三十一页，共82页。文法的四种(szhn)分类第32页/共81页第三十二页，共82页。2.132.13文法和语言文法和语言(yyn)(yyn)分类分类四种文法的关系：通过对文法的产生式逐渐增加限制来定义四种文法，因此 0型语言包含(bohn)1型语言，1型语言包含(bohn
21、)2型语言，2型语言包含(bohn)3型语言。或者说，3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0型文法的特例 。第33页/共81页第三十三页，共82页。n直接推导（）：是文法G的一个(y)产生式，x,yV*，符号串xy中的非终结符号用替换，从而得到符号串xy，则表示为：nxyxyn其中“”读为“直接推导出”或“直接产生”。即称xy直接推导出xy,或xy直接产生xy。若从反方向看，则称xy直接归约到xy。显然，文法的产生式右部是其左部的直接推导。例 已知文法GS： S0S1， S010S10011 (使用(shyng)规则S01,x=0,y=1)S 0S1 (使用(shy
22、ng)规则S0S1,x=,y=)0S100S11 (使用(shyng)规则S0S1,x=0,y=1)2.3 2.3 推导推导(tudo)(P17) (tudo)(P17) 第34页/共81页第三十四页，共82页。2.3 2.3 推导推导(tudo) (tudo) 练习 已知文法G:| a|b|z 0|1|9 指出下面直接推导(tudo)所使用的规则： abc abc5第35页/共81页第三十五页，共82页。n推导(tudo)（）：如果存在一直接推导(tudo)序列n01n，则表示为：n0nn其中，“”读为“推导(tudo)出”或“产生”，即0推导(tudo)出或产生n。若从反方向看，则称n归约
23、到0。n是推导(tudo)长度，要求n0。2.3 2.3 推导推导(tudo) (tudo) +第36页/共81页第三十六页，共82页。2.3 2.3 推导推导(tudo)(tudo)例 已知文法： := :=| :=0|1|2|3|4|5|6|7|8|9有： 2 将上述三个直接(zhji)推导连接起来，可得如下推导过程： 2则记： 2，显然，n=3。+第37页/共81页第三十七页，共82页。n广义推导（）：如果有0n或0=n,即n0，则表示为：n0nn其中，“”读为“广义推导出”或“广义产生(chnshng)”。若从反方向看，则称n广义归约到0。2.3 2.3 推导推导(tudo) (tud
24、o) +*第38页/共81页第三十八页，共82页。2.3 2.3 推导推导(tudo)(tudo)例 已知文法： := :=| :=0|1|2|3|4|5|6|7|8|9 2，也可记为： 2， 从到的推导，无须使用(shyng)任何规则，其推导长度n=0，则记作： +*第39页/共81页第三十九页，共82页。2.3 2.3 推导推导(tudo)(tudo) 例 GS:SaASASbAASSSaAba证明(zhngmng)S aabbaa。证明(zhngmng)：第1种 SaASaAaaSbAaaSbbaaaabbaa 第2种 SaASaSbASaabASaabbaSaabbaa第3种 SaAS
25、aSbASaSbAaaabAaaabbaa+第40页/共81页第四十页，共82页。2.3 2.3 推导推导(tudo)(tudo)规范(gufn)推导（或最右推导）：在推导的任何一步，都是对中的最右非终结符进行替换。最左推导：在推导的任何一步(y b)，都是对中的最左非终结符进行替换。例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(规范推导) SaASaSbASaabASaabbaSaabbaa(最左推导) SaASaSbASaSbAaaabAaaabbaa(非左非右推导)+第41页/共81页第四十一页，共82页。2.4 2.4 句型句型(j xn)(j xn)
26、和句子（和句子（P18P18）句型：设Z是文法G的识别(shbi)符号，如果Z x，xV* ，则称符号串x为文法G的一个句型。显然，Z是文法G的一个句型。*例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa 则, aAS、aAa、aSbAa、aSbbaa和aabbaa是该文法的句型(j xn)，也是该文法的规范句型(j xn)。+规范句型：能用规范推导产生的句型。第42页/共81页第四十二页，共82页。2.4 2.4 句型句型(j xn)(j xn)和句子和句子句子:设Z是文法G的识别符号，如果Z x，xVt* ，则称符号串x为文法G的一个句子。显然，句型包括句子或说
27、句子是特殊的句型，句子是完全由终结(zhngji)符号组成的句型。+例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa则, aabbaa是该文法(wnf)的句子。+第43页/共81页第四十三页，共82页。2.4 2.4 句型句型(j xn)(j xn)和句子和句子每一个句子都有一个规范(gufn)推导，但并非每一个句型都有规范(gufn)推导。例 := :=| :=0|1|2|3|4|5|6|7|8|9 2句型“2 ”不是(b shi)规范句型 3 3句型“3”是规范句型 第44页/共81页第四十四页，共82页。2.5 2.5 语言语言(yyn)(yyn)（P19P1
28、9）语言:一个(y )文法GZ所产生的所有句子的集合L(GZ), 称为文法GZ所定义的语言, 即: L(GZ)=x|xVt* , 且Z x 例 已知文法GS：S:=0S1|01，求其所产生(chnshng)的语言。解： S 01 S 0S1 0011 S 0S1 00S11 000111 L(GS)=01，0011，000111，=0n1n|n0+第45页/共81页第四十五页，共82页。2.5 2.5 语言语言(yyn)(yyn)例 the ate banana monkey 其语言只有(zhyu)下面4个句子： the monkey ate the banana the banana ate
29、 the monkey the monkey ate the monkey the banana ate the banana第46页/共81页第四十六页，共82页。2.5 2.5 语言语言(yyn)(yyn)练习句子:=主语谓语 主语:=代词|名词 代词:= 你 | 我 | 他 名词:= 王明(wng mng) | 大学生 | 工人 | 英语 谓语:=动词直接宾语 动词:= 是 | 学习 直接宾语:= 代词|名词下列是否是句子？我是大学生王明是大学生王明学习(xux)英语他学习(xux)英语你是工人下列是否是句子？我大学生是大学生是王明英语学习王明大学生学习他工人是英语第47页/共81页第四
30、十七页，共82页。2.5 2.5 语言语言(yyn) (yyn) 文法和语言(yyn)的关系：给定一个文法，就能从结构上唯一的确定其语言(yyn)，即: GL(G)。给定一种语言(yyn)，能确定其文法，但不唯一，即: LG1 或G2 或。等价(dngji)文法：如果不同的文法可描述相同的语言，则称这些文法为等价(dngji)文法。文法语言1:1n:1第48页/共81页第四十八页，共82页。2.5 2.5 语言语言(yyn)(yyn)例2-5(P19) 已知语言为 L(G)=abna|n 1，构造产生该语言的文法。解：根据语言的形式(xngsh)，可构造其文法G为: ZaBa BBb|b 还可
31、以构造文法G1为: ZaBa BbB|b 显然，G和G1是两个不同的文法，但它们都可以描述语言abna|n1,因此它们是等价文法。 第49页/共81页第四十九页，共82页。2.62.6递归规则递归规则(guz)(guz)与递归文法与递归文法(P20)(P20)递归规则(guz)：是指那些在规则(guz)的右部含有与规则(guz)左部相同符号的规则(guz)。右递归规则(guz)： 形如U:=xU的规则(guz)。例 U:=xUy，因为规则右部含有与规则左部相同符号U， 所以U:=xUy就是一条递归规则。左递归规则：形如U:=Uy的规则。第50页/共81页第五十页，共82页。2.62.6递归规则
32、递归规则(guz)(guz)与递归文法与递归文法直接递归文法(wnf)：至少包含一条递归规则的文法(wnf)。例 设文法(wnf)GA: A:=B B:=X|BA X:=Xa|Xb|a|b该文法(wnf)是一个具有直接左递归性的文法(wnf)。 第51页/共81页第五十一页，共82页。2.62.6递归规则递归规则(guz)(guz)与递归文法与递归文法间接递归文法：表面上看文法的每条规则都不是递归规则，但存在某个(mu )推导会导致递归出现。例 设有文法GS: S:=Qd Q:=Rb|Se R:=Sa|Qf|a S Qd Sed，即S Sed文法G是一个(y )间接递归文法。+第52页/共81
33、页第五十二页，共82页。2.62.6递归规则递归规则(guz)(guz)与递归文法与递归文法语言的句子(j zi)的个数是有穷还是无穷取决于定义该语言的文法是否是递归的。例 例2-1（P15）的文法是无递归的，因此(ync)其所产生的句子是有穷的，只产生4个句子。例2-3（P16）的文法有递归规则，属于递归文法，所以它所描述的语言为所有无符号整数，是无穷的。第53页/共81页第五十三页，共82页。2.62.6递归规则递归规则(guz)(guz)与递归文法与递归文法递归文法(wnf)包括直接递归文法(wnf)和间接递归文法(wnf)，运用递归文法(wnf)使我们能用有穷的文法(wnf)刻画无穷的
34、语言。练习 判定如下文法所描述(mio sh)的语言是否是有穷的。 S:=(S) S:=解：因为文法中的第一条产生式S:=(S)是递归规则，所以该文法是递归文法，所描述的语言为L(GS)=,(),(),(), =(n)n|n0，是无穷的。第54页/共81页第五十四页，共82页。2.8 2.8 语法语法(yf)(yf)树树(P21)(P21)语法树（或推导树）：用树形结构来直观地表示句型的推导过程。设有文法(wnf)G=(Vn,Vt,P,S)，对于文法(wnf)G的任意一个句型都存在一棵相应的语法树，这棵树满足下列4个条件：如果树中的一个结点(ji din)A有若干个直接后继，从左到右分别是B1
35、,B2,B3,Bn，则有A:=B1B2B3Bn P。如果树中的一个结点至少有一个直接后继，则说明该结点一定是一个非终结符号。树的根结点是文法的开始符号S。树中的每个结点都有一个标记，此标记是V中的一个符号。第55页/共81页第五十五页，共82页。2.8 2.8 语法语法(yf)(yf)树树例: GS:SaASASbAASSSaAba例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(规范(gufn)推导) SaASaSbASaabASaabbaSaabbaa(最左推导) SaASaSbASaSbAaaabAaaabbaa(非左非右推导)+第56页/共81页第五十六页
36、，共82页。2.8 2.8 语法语法(yf)(yf)树树文法的句型都是按照文法的产生(chnshng)式来生成相应的语法树，其生成过程如下：推导过程(guchng)不同，生成语法树的过程(guchng)也不同，但是，如果文法是无二义性的，则最终生成的语法树是相同的。语法树的末端节点（叶节点）从左向右排列起来，构成句型。如果叶节点都是终结符号，则从左向右构成句子。b.根据句型的结构特点来选择文法中产生式，最终生成该句型对应的语法树。a.以文法G的开始符号作为语法树的根结点第57页/共81页第五十七页，共82页。2.8 2.8 语法语法(yf)(yf)树树练习：已知文法 SaBc | bAB Aa
37、Ab| b Bb | 写出符号串babbb的规范推导(tudo)，并画出语法树。第58页/共81页第五十八页，共82页。2.10 2.10 由树构造由树构造(guzo)(guzo)推导过程（推导过程（P23P23）根据已有的语法(yf)树，可以从上而下或从下而上建立推导。从下而上的方法：逐层地修剪子树末端节点来建立推导。当有两棵以上子树时，原则上修剪那一棵都可以，如果每次总是(zn sh)修剪最左边的子树，即相当于每步都对归约句型的句柄归约，则称为“最左归约”或“规范归约”。规范推导与规范归约互为逆过程。 从上而下的方法：从树根开始由上而下逐层地用子节点代替父节点。当一层中有两棵以上子树根时，
38、原则上先选哪一棵树根替换都可以。而每步都对最右边的子树树根符号替换，则构造出的推导是规范推导。第59页/共81页第五十九页，共82页。2.10 2.10 由树构造推导由树构造推导(tudo)(tudo)过程过程练习 已知文法(wnf)： E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i对应的语法树如图所示,请根据该语法树写它的规范推导。第60页/共81页第六十页，共82页。2.10 2.10 由树构造推导由树构造推导(tudo)(tudo)过程过程句型(j xn)E+(E+T)*i的规范推导：第61页/共81页第六十一页，共82页。2.10 2.10 由树构造推导由
39、树构造推导(tudo)(tudo)过程过程语法(yf)树和推导之间的对应关系：每一棵语法(yf)树至少存在一个推导与之相对应每一个推导都存在一棵语法(yf)树语法(yf)树推导1:n1:1第62页/共81页第六十二页，共82页。2.7 2.7 短语短语(duny)(duny)、简单短语、简单短语(duny)(duny)和句柄（和句柄（P21P21）短语：设GZ是一文法, w=xuy是一句型,如果有 Z xUy 且U u ,其中UVn , uV+,则称u为句型w(相对(xingdu)于非终结符号U)的短语。显然,w是相对(xingdu)Z的句型w的短语。句柄：任一句型的最左简单短语(duny)称
40、为该句型的句柄。一个句型的句柄一定是该句型的简单短语(duny)。 简单短语(或直接短语)：若有 Z xUy 且U u，则称u是句型w相对于非终结符号U的简单短语。一个句型的直接短语一定是该句型的短语。 *+*第63页/共81页第六十三页，共82页。2.7 2.7 短语短语(duny)(duny)、简单短语、简单短语(duny)(duny)和句柄和句柄求一个句型的短语(duny)、简单短语(duny)和句柄的方法: 语法树（建议用该方法(fngf)）：由文法的开始符号开始，通过产生式来构造与该句型相对应的语法树。推导法：由文法的开始符号开始，找出该句型的所有推导。第64页/共81页第六十四页，
41、共82页。2.9 2.9 子树和短语子树和短语(duny)(P22)(duny)(P22)例 已知文法： E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i对应(duyng)的语法树如图所示,请根据该语法树写它的短语、简单短语和句柄。第65页/共81页第六十五页，共82页。2.9 2.9 子树和短语子树和短语(duny)(duny)句型(j xn)E+(E+T)*i的短语为： E+(E+T)*i、 (E+T)*i 、 (E+T)、 E+T 、 i句型(j xn)E+(E+T)*i的简单短语为： E+T 、 i句型E+(E+T)*i的句柄为： E+T第66页/共81页第
42、六十六页，共82页。2.9 2.9 子树和短语子树和短语(duny)(duny)例 GS:SaASASbAASSSaAba 求句型aabbaa的短语(duny)、简单短语(duny)和句柄。句型aabbaa的短语(duny)为： aabbaa 、 abba、 a(左起第2个) 、 ba 、 a(最后1个) 句型aabbaa的简单短语为： a(左起第2个) 、 ba 、 a(最后1个) 句型aabbaa的句柄为： a(左起第2个) 第67页/共81页第六十七页，共82页。2.9 2.9 子树和短语子树和短语(duny)(duny)课堂练习已知文法 GZ:ZAbB | bBAA Ba | cBAb
43、 | d求句型(j xn)cbdab的短语、简单短语和句柄。第68页/共81页第六十八页，共82页。2.11 2.11 文法文法(wnf)(wnf)的二义性（的二义性（P23P23）二义性文法：如果一个文法所定义的某个句子或句型，它存在(cnzi)两棵（或两棵以上）不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。 例2-11(P23) 有文法(wnf)GE：E= E+E | E*E |（E）| i，分析该文法(wnf)是否为二义性文法(wnf)。EE+EE*EiiiEE*EEEiii+解：句子i+i*i存在两棵不同的语法树，因此文法G 是二义性文法。 第69页/共81页第六十九
44、页，共82页。2.11 2.11 文法文法(wnf)(wnf)的二义性的二义性EE+EE*EiiiEE*EEEiii+语法(yf)树1 在语法树1中， i+i*i的规范推导为：EE+EE+E*EE+E*iE+i*ii+i*i即，在语法树1中的*先作为句柄归约，表示*优先于+进行(jnxng)运算。 语法树2 二义性产生的后果会导致分析结果不同，导致对句子的理解不同。因此，在算术表达式中规定乘除高于加减，从而避免二义性。 在语法树2中， i+i*i的规范推导为：EE*EE*iE+E*iE+i*ii+i*i即，在语法树2中的+先作为句柄归约，表示+优先于*进行运算。第70页/共81页第七十页，共8
45、2页。2.11 2.11 文法文法(wnf)(wnf)的二义性的二义性例2-12(P24) if语句(yj)文法如下：= ifthen |ifthenelse |说明该文法是二义性文法。解：假设有一个(y )if语句嵌套的句型为：ifthen ifthenelse 该句型存在两棵不同的语法树，所以该文法是二义性文法。第71页/共81页第七十一页，共82页。2.11 2.11 文法文法(wnf)(wnf)的二义性的二义性语句 布尔表达式 if then语句 布尔表达式 ifthen语句 else 语句 语句 布尔表达式 if then语句 布尔表达式 if then 语句 else语句 语法(y
46、f)树1 语法(yf)树2 语法树1意味着else和第2个if配对（就近配对），语法树2表示else和第1个if配对。 因此，在if语句中规定else与最近的if配对(即就近配对)。第72页/共81页第七十二页，共82页。2.11 2.11 文法文法(wnf)(wnf)的二义性的二义性文法的二义性是不可判定的，即不存在一种算法，它能够在有限(yuxin)步内确切地判定一个文法是否是二义性的。例2-13 改写文法GE： E= E+E | E*E |（E）| i，使其无二义性。解：新添非终结符号T和F，将文法改写成：E= T |E+T，T=F |T*F，F= (E) | i 这样，就避免了二义性。
47、用改写后的文法给出句i+i*i的语法树如右图所示。此时(c sh)的语法树是唯一的。 ET+EF*TTiFFii第73页/共81页第七十三页，共82页。2.12 2.12 有关文法有关文法(wnf)(wnf)的实用限制（的实用限制（P25P25） 文法的实用限制：就是从实用的观点出发，对文法做一些(yxi)必要的限制。以下是对文法的实用限制：文法(wnf)不能是二义性的。不能有U=U这样的有害规则。不能有多余规则推导中始终用不到的规则。(不可达规则)一旦使用某规则后无法推出终结符号串的规则。(无用规则)第74页/共81页第七十四页，共82页。2.12 2.12 有关有关(yugun)(yugu
48、n)文法的实用限制文法的实用限制 检查多余(duy)规则的方法：检查文法中每一条规则左部的每个非终结符号U是否满足下述两个条件：(1) U必须在某个句型中出现，即有：Z xUy(2)必须能够从U推导出终结符号串，即: U t，tVt*不满足这两个条件的规则就是多余(duy)规则。 *+第75页/共81页第七十五页，共82页。2.12 2.12 有关有关(yugun)(yugun)文法的实用限制文法的实用限制 压缩（或化简）文法(wnf)的方法：1.删去(shn q)形如U:=U的有害规则； （即去掉U:=U） 2.删去无用规则；（即使任何一个非终结符都能推导出终结符号串）3.删去不可达规则。（
49、即使任何一个非终结符都能在某句型中出现）压缩后的文法与原文法是等价的。 第76页/共81页第七十六页，共82页。2.12 2.12 有关文法有关文法(wnf)(wnf)的实用限制的实用限制例2-14(P25) 有文法：Z=Aa，A=Ca|Bb，B=Ba|a，C=Cb ，D=b，去掉(q dio)有害规则和多余规则。解：规则C=Cb也是一条无用规则，因为一旦使用了这条规则以后，将使推导无穷地进行下去，即C Cb Cbb Cbbb，无法推出终结符号串。而规则A=Ca因为会产生C，所以也要去掉。 由于非终结符号D不出现任何规则的右部且D不是开始符号，所以在句子的推导中不可能用到规则D=b，因此它是不
50、可达规则，应该(ynggi)去掉。 最后得到的文法为： Z=Aa A=Bb B=Ba|a第77页/共81页第七十七页，共82页。2.12 2.12 有关文法的实用有关文法的实用(shyng)(shyng)限制限制练习 压缩(y su)文法Z:=E+TE:=E|S+F|TF:=F|FP|PP:=GG:=G|GG|FT:=T*i|iQ:=E|E+F|T|SS:=i压缩(y su)后的文法为： Z:=E+T E:=T T:=T*i|i 第78页/共81页第七十八页，共82页。小小 结结1 文法的定义（四元组）、分类（4种类型）和二义性2 最左推导、规范推导(或最右推导)3 语言(yyn)、句型和句子
51、4 用语法树求短语、简单短语（或直接短语）和句柄语法树和推导的对应关系递归文法压缩文法（删除有害规则和多余规则）第79页/共81页第七十九页，共82页。习题习题(xt) (xt) （P27P27）1. 设字母表A=a，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及(yj)A+.2. 令=a，b，c，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）33. 设有文法GS：S=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。4. 已知文法GZ：Z=U0V1 , U=Z11 , V=Z00 ,请写出全部由此文法描述的只含有四个符号的
52、句子。5. 已知文法GS：S=AB, A=aA , B=bBcbc , 写出该文法描述的语言。6. 已知文法E=TE+TE-T 、 T=FT*FT/F 、 F=(E)i，写出该文法的开始符号、终结符号集合Vt、非终结符号集合Vn。7. 对第6题的文法，写出句型T+T*F+i的短语、简单短语以及(yj)句柄。8. 设有文法GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？9. 写一文法，使其语言是奇正整数集合。 10. 给出语言anbm|n,m1的文法。 第80页/共81页第八十页，共82页。感谢您的欣赏(xnshng)！第81页/共81页第八十一页，共82页。内容(nirng)总结学习重点。A+ =A1A2。.An。（一般写成monkey ）。如t表示符号串t可有可无。n 是推导(tudo)长度，要求n0。语法树的末端节点（叶节点）从左向右排列起来，构成句型。根据已有的语法树，可以从上而下或从下而上建立推导(tudo)。规范推导(tudo)与规范归约互为逆过程。从上而下的方法：从树根开始由上而下逐层地用子节点代替父节点。感谢您的欣赏第八十二页，共82页。
