编译原理第2章文法和语言.pptx

《编译原理第2章文法和语言.pptx》由会员分享，可在线阅读，更多相关《编译原理第2章文法和语言.pptx（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、字母、数字、各种标点符号和各种运算符。第5页/共82页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页/共82页2.1 2.1 字母表和符号串字母表和符号串 符号串的长度：指符号串x中所含符号的个数，

4、记为|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页/共82页2.1 2.1 字母表和符号串字母表和符号串 符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串。例 u、uni、university都是university的前缀符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串。例 ty、sity、univer

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

6、于空集合有，有 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页/共82页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 第11页/共82页2.1 2.1 字母表和符号串字母表和符号串 集合的正闭包：设A为一个

7、集合，则：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页/共82页例：2.2 文法(P14)文法实际上就是描述语言语法结构的形式规则。第13页/共82页例第14页/共82页例第15页/共82页文法G的形式定义：G=(Vn，Vt，P，Z)Vn(非终结符号集)是一个由非终结符号（一般是大写字母或用）构成的非空有穷集合。Vt(终结符号集)是一个由终结符号（如小写字母、数字、标点符号等）构成的非空有穷

8、集合。VtVn=，VtVn，V是该文法的字母表或词汇表。P(产生式集)是一个由产生式或规则构成的非空有穷集合。产生式的形式为：或:=产生式的左部V+，即不能为空，产生式的右部V*，“”或”“:=”含义相同，表示“定义为”或“由组成”。Z是文法的识别符号或开始符号，Z Vn，要求Z至少必须在某个产生式的左部出现一次。第16页/共82页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页/共82页2.2 2.2 文法文法例2-

9、1(P15)文法 G1可以简化写成：G1:the ate banana monkey the ate banana monkey 或第18页/共82页2.2 2.2 文法文法 例2-2(P15)有如下简化表示文法，只给出规则集，写出该文法的终结符号集合、非终结符号集合和识别符号。0123456789解：根据简化约定，可确定：Vn=,Vt=0,1,2,3,4,5,6,7,8,9识别符号：第19页/共82页2.2 2.2 文法文法文法的EBNF表示（P16）：用一些特殊的元符号“|”、“”和“”、“”、“（”和“）”、“”和“”来表示文法。例2-3 对例2.2文法的13条规则可缩写成：:=:=|:

10、=0|1|2|3|4|5|6|7|8|9“|”：表示“或”。对于具有相同左部的那些规则，如 1，2，n 缩写为:1|2|n第20页/共82页2.2 2.2 文法文法“”：用于括起由中文字组成的非终结符号或由多个字母组成的符号。例（一般写成monkey）第21页/共82页2.2 2.2 文法文法“”和“”：表示可重复连接，tkm表示符号串t可重复连接k到m次，而t表示符号串t可重复连接0到无穷次。例13 等价于：|EE+T|T 与 ET+T 相同字母打头、后面可跟字母或数字的不超过8个字符的标识符文法则为：|07第22页/共82页2.2 2.2 文法文法“”和“”：表示括起来的内容可有可无。如t

11、表示符号串t可有可无。例 IF THEN IF THEN ELSE 可写成：IF THEN ELSE 第23页/共82页2.2 2.2 文法文法“（”和“）”：表示括号内的成分优先。常用于在规则中提取公因子。例 Uxy|xw|xz 可写成：Ux（y|w|z）第24页/共82页2.2 2.2 文法文法 练习（P27习题6）已知文法ET|E+T|E-TTF|T*F|T/FF(E)|i写出该文法的开始符号、Vn和Vt。解：根据简化约定，可确定：开始符号：EVn=E,T,FVt=+,-,*,/,(,),i第25页/共82页2.132.13文法和语言分类文法和语言分类（P26P26）0型文法(或短语结构

12、文法)若文法中有如下形式的规则：其中，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页/共82页2.132.13文法和语言分类文法和语言分类（P26P26）1型文法(或上下文有关文法)若文法中有如下形式的规则：Uu 其中，UVn，、V*

13、，u 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页/共82页2.132.13文法和语言分类文法和语言分类（P26P26）2型文法(或上下文无关文法)若文法中的规则都具有如下形式：Uu 其中，U Vn，u V*，即2型文法中的规则左部必须是一个非终结符号，

14、规则右部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页/共82页2.132.13文法和语言分类文法和语言分类（P27P27）3型文法(或正规文法)若文法中的规则都具有如下形式：Ua|Wa（左线性）或 Ua|aW（右线性）其中，U，WVn，aVt(a可为)。3型文

15、法中的产生式全部是左线性产生式或全部是右线性产生式。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页/共82页2.132.13文法和语言分类文法和语言分类 练习 判断以下文法的类型 S:=ABCC:=BCC:=ABA:=GEBG:=GBFAG:=ADDB:=BDDE:=AEFB:=BFFE:=EaAA:=文法GZ:Z:=0B|1CB:=1Z|1C:=0Z|00型文法3型文法第30页

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

17、是文法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页/共82页2.3 2.3 推导推导 练习 已知文法G:|a|b|z 0|1|9 指出下面直接推导所使用

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

19、2.3 2.3 推导推导+*第38页/共82页2.3 2.3 推导推导例 已知文法：:=:=|:=0|1|2|3|4|5|6|7|8|9 2，也可记为：2，从到的推导，无须使用任何规则，其推导长度n=0，则记作：+*第39页/共82页2.3 2.3 推导推导 例 GS:SaASASbAASSSaAba证明S aabbaa。证明：第1种 SaASaAaaSbAaaSbbaaaabbaa 第2种 SaASaSbASaabASaabbaSaabbaa第3种 SaASaSbASaSbAaaabAaaabbaa+第40页/共82页2.3 2.3 推导推导规范推导（或最右推导）：在推导的任何一步，都是对中

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

21、Sbbaa和aabbaa是该文法的句型，也是该文法的规范句型。+规范句型：能用规范推导产生的句型。第42页/共82页2.4 2.4 句型和句子句型和句子句子:设Z是文法G的识别符号，如果Z x，xVt*，则称符号串x为文法G的一个句子。显然，句型包括句子或说句子是特殊的句型，句子是完全由终结符号组成的句型。+例 在S aabbaa中,有SaASaAaaSbAaaSbbaaaabbaa则,aabbaa是该文法的句子。+第43页/共82页2.4 2.4 句型和句子句型和句子每一个句子都有一个规范推导，但并非每一个句型都有规范推导。例 :=:=|:=0|1|2|3|4|5|6|7|8|9 2句型“2

22、”不是规范句型 3 3句型“3”是规范句型 第44页/共82页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页/共82页2.5 2.5 语言语言例 the ate banana monkey 其语言只有下面4个句子：the monkey ate the banana the banana a

23、te the monkey the monkey ate the monkey the banana ate the banana第46页/共82页2.5 2.5 语言语言练习句子:=主语谓语 主语:=代词|名词 代词:=你|我|他 名词:=王明|大学生|工人|英语 谓语:=动词直接宾语 动词:=是|学习 直接宾语:=代词|名词下列是否是句子？我是大学生王明是大学生王明学习英语他学习英语你是工人下列是否是句子？我大学生是大学生是王明英语学习王明大学生学习他工人是英语第47页/共82页2.5 2.5 语言语言 文法和语言的关系：给定一个文法，就能从结构上唯一的确定其语言，即:GL(G)。给定一种

24、语言，能确定其文法，但不唯一，即:LG1 或G2 或。等价文法：如果不同的文法可描述相同的语言，则称这些文法为等价文法。文法语言1:1n:1第48页/共82页2.5 2.5 语言语言例2-5(P19)已知语言为 L(G)=abna|n 1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为:ZaBa BBb|b 还可以构造文法G1为:ZaBa BbB|b 显然，G和G1是两个不同的文法，但它们都可以描述语言abna|n1,因此它们是等价文法。第49页/共82页2.62.6递归规则与递归文法递归规则与递归文法(P20)(P20)递归规则：是指那些在规则的右部含有与规则左部相同符号的规则。

25、右递归规则：形如U:=xU的规则。例 U:=xUy，因为规则右部含有与规则左部相同符号U，所以U:=xUy就是一条递归规则。左递归规则：形如U:=Uy的规则。第50页/共82页2.62.6递归规则与递归文法递归规则与递归文法直接递归文法：至少包含一条递归规则的文法。例 设文法GA:A:=B B:=X|BA X:=Xa|Xb|a|b该文法是一个具有直接左递归性的文法。第51页/共82页2.62.6递归规则与递归文法递归规则与递归文法间接递归文法：表面上看文法的每条规则都不是递归规则，但存在某个推导会导致递归出现。例 设有文法GS:S:=Qd Q:=Rb|Se R:=Sa|Qf|a S Qd Se

26、d，即S Sed文法G是一个间接递归文法。+第52页/共82页2.62.6递归规则与递归文法递归规则与递归文法语言的句子的个数是有穷还是无穷取决于定义该语言的文法是否是递归的。例 例2-1（P15）的文法是无递归的，因此其所产生的句子是有穷的，只产生4个句子。例2-3（P16）的文法有递归规则，属于递归文法，所以它所描述的语言为所有无符号整数，是无穷的。第53页/共82页2.62.6递归规则与递归文法递归规则与递归文法递归文法包括直接递归文法和间接递归文法，运用递归文法使我们能用有穷的文法刻画无穷的语言。练习 判定如下文法所描述的语言是否是有穷的。S:=(S)S:=解：因为文法中的第一条产生式

27、S:=(S)是递归规则，所以该文法是递归文法，所描述的语言为L(GS)=,(),(),(),=(n)n|n0，是无穷的。第54页/共82页2.8 2.8 语法树语法树(P21)(P21)语法树（或推导树）：用树形结构来直观地表示句型的推导过程。设有文法G=(Vn,Vt,P,S)，对于文法G的任意一个句型都存在一棵相应的语法树，这棵树满足下列4个条件：如果树中的一个结点A有若干个直接后继，从左到右分别是B1,B2,B3,Bn，则有A:=B1B2B3Bn P。如果树中的一个结点至少有一个直接后继，则说明该结点一定是一个非终结符号。树的根结点是文法的开始符号S。树中的每个结点都有一个标记，此标记是V

28、中的一个符号。第55页/共82页2.8 2.8 语法树语法树例:GS:SaASASbAASSSaAba例 上例中的S aabbaa SaASaAaaSbAaaSbbaaaabbaa(规范推导)SaASaSbASaabASaabbaSaabbaa(最左推导)SaASaSbASaSbAaaabAaaabbaa(非左非右推导)+第56页/共82页2.8 2.8 语法树语法树文法的句型都是按照文法的产生式来生成相应的语法树，其生成过程如下：推导过程不同，生成语法树的过程也不同，但是，如果文法是无二义性的，则最终生成的语法树是相同的。语法树的末端节点（叶节点）从左向右排列起来，构成句型。如果叶节点都是终

29、结符号，则从左向右构成句子。b.根据句型的结构特点来选择文法中产生式，最终生成该句型对应的语法树。a.以文法G的开始符号作为语法树的根结点第57页/共82页2.10 2.10 由树构造推导过程由树构造推导过程（P23P23）根据已有的语法树，可以从上而下或从下而上建立推导。从下而上的方法：逐层地修剪子树末端节点来建立推导。当有两棵以上子树时，原则上修剪那一棵都可以，如果每次总是修剪最左边的子树，即相当于每步都对归约句型的句柄归约，则称为“最左归约”或“规范归约”。规范推导与规范归约互为逆过程。从上而下的方法：从树根开始由上而下逐层地用子节点代替父节点。当一层中有两棵以上子树根时，原则上先选哪一

30、棵树根替换都可以。而每步都对最右边的子树树根符号替换，则构造出的推导是规范推导。第58页/共82页2.10 2.10 由树构造推导过程由树构造推导过程练习 已知文法：E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i对应的语法树如图所示,请根据该语法树写它的规范推导。第59页/共82页2.10 2.10 由树构造推导过程由树构造推导过程句型E+(E+T)*i的规范推导：第60页/共82页2.10 2.10 由树构造推导过程由树构造推导过程语法树和推导之间的对应关系：每一棵语法树至少存在一个推导与之相对应每一个推导都存在一棵语法树语法树推导1:n1:1第61页/共82页

31、2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄（P21P21）短语：设GZ是一文法,w=xuy是一句型,如果有 Z xUy 且U u,其中UVn,uV+,则称u是一个相对于非终结符号U的句型w的短语。显然,w是相对Z的句型w的短语。句柄：任一句型的最左简单短语称为该句型的句柄。一个句型的句柄一定是该句型的简单短语。简单短语(或直接短语)：若有 Z xUy 且U u，则称u是一个相对于非终结符号U的句型w的简单短语。一个句型的直接短语一定是该句型的短语。*+*第62页/共82页2.7 2.7 短语、简单短语和句柄短语、简单短语和句柄求一个句型的短语、简单短语和句柄的方法:语法树（建议用

32、该方法）：由文法的开始符号开始，通过产生式来构造与该句型相对应的语法树。推导法：由文法的开始符号开始，找出该句型的所有推导。第63页/共82页2.9 2.9 子树和短语子树和短语(P22)(P22)例 已知文法：E:=E+T|T T:=T*F|F F:=(E)|i 句型E+(E+T)*i对应的语法树如图所示,请根据该语法树写它的短语、简单短语和句柄。第64页/共82页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第65页/共82页

33、2.9 2.9 子树和短语子树和短语例 GS:SaASASbAASSSaAba 求句型aabbaa的短语、简单短语和句柄。句型aabbaa的短语为：aabbaa、abba、a(左起第2个)、ba、a(最后1个)句型aabbaa的简单短语为：a(左起第2个)、ba、a(最后1个)句型aabbaa的句柄为：a(左起第2个)第66页/共82页2.11 2.11 文法的二义性文法的二义性（P23P23）二义性文法：如果一个文法所定义的某个句子或句型，它存在两棵（或两棵以上）不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。例2-11(P23)有文法GE：E=E+E|E*E|（E）|i，分

34、析该文法是否为二义性文法。EE+EE*EiiiEE*EEEiii+解：句子i+i*i存在两棵不同的语法树，因此文法G 是二义性文法。第67页/共82页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*iE+E*iE+i*ii+i*i即，在

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

36、意味着else和第2个if配对（就近配对），语法树2表示else和第1个if配对。因此，在if语句中规定else与最近的if配对(即就近配对)。第70页/共82页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第71页/共82页2

37、.12 2.12 有关文法的实用限制有关文法的实用限制（P25P25）文法的实用限制：就是从实用的观点出发，对文法做一些必要的限制。以下是对文法的实用限制：文法不能是二义性的。不能有U=U这样的有害规则。不能有多余规则推导中始终用不到的规则。(不可达规则)一旦使用某规则后无法推出终结符号串的规则。(无用规则)第72页/共82页2.12 2.12 有关文法的实用限制有关文法的实用限制 检查多余规则的方法：检查文法中每一条规则左部的每个非终结符号U是否满足下述两个条件：(1)U必须在某个句型中出现，即有：Z xUy(2)必须能够从U推导出终结符号串，即:U t，tVt*不满足这两个条件的规则就是多

38、余规则。*+第73页/共82页2.12 2.12 有关文法的实用限制有关文法的实用限制 压缩（或化简）文法的方法：1.删去形如U:=U的有害规则；（即去掉U:=U）2.删去无用规则；（即使任何一个非终结符都能推导出终结符号串）3.删去不可达规则。（即使任何一个非终结符都能在某句型中出现）压缩后的文法与原文法是等价的。第74页/共82页2.12 2.12 有关文法的实用限制有关文法的实用限制例2-14(P25)有文法：Z=Aa，A=Ca|Bb，B=Ba|a，C=Cb，D=b，去掉有害规则和多余规则。解：规则C=Cb也是一条无用规则，因为一旦使用了这条规则以后，将使推导无穷地进行下去，即C Cb

39、Cbb Cbbb，无法推出终结符号串。而规则A=Ca因为会产生C，所以也要去掉。由于非终结符号D不出现任何规则的右部且D不是开始符号，所以在句子的推导中不可能用到规则D=b，因此它是不可达规则，应该去掉。最后得到的文法为：Z=Aa A=Bb B=Ba|a第75页/共82页2.12 2.12 有关文法的实用限制有关文法的实用限制练习 压缩文法Z:=E+TE:=E|S+F|TF:=F|FP|PP:=GG:=G|GG|FT:=T*i|iQ:=E|E+F|T|SS:=i压缩后的文法为：Z:=E+T E:=T T:=T*i|i 第76页/共82页小小 结结1 文法的定义（四元组）、分类（4种类型）和二义

40、性2 最左推导、规范推导(或最右推导)3 语言、句型和句子4 用语法树求短语、简单短语（或直接短语）和句柄5语法树和推导的对应关系6递归文法7压缩文法（删除有害规则和多余规则）第77页/共82页习题习题 （P27P27）1.设字母表A=a，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及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,请写出全部由此文法描述的只含有四个符号的句

41、子。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的短语、简单短语以及句柄。8.设有文法GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？9.写一文法，使其语言是奇正整数集合。10.给出语言anbm|n,m1的文法。第78页/共82页作作 业业 1 11.判断以下文法的类型，说明理由。(1)文法GE：S aS|aBB bCC aC|a（2）文法GS:=|=|=a|b|z|A|B|Z =1|

42、2|9|0（3）文法GA:Aabc|aBbc Bb bB Bc Cbcc bC Cb aC aaB aC aa第79页/共82页作作 业业 1 12 考虑文法GS：SaAb ABcA|B Bd|指出该文法的终结符号及非终结符号；(1)给出句子adcb的语法分析树；(2)构造句子adcb的最左推导和规范推导。注意：下次上课前交。第80页/共82页作作 业业 2 2 3 设有文法GS：S P|aPb P ba|bQa Q ab,考虑它所定义的语言L(GS).4.考虑文法GS：SaSbS|bSaS|讨论句子abab的最左推导，说明该文法是二义性的。5.对于题2，画出符号串adcb的语法树，写出adcb的短语、简单短语以及句柄。注意：下次上课前交。第81页/共82页感谢您的观看。第82页/共82页