短语、直接短语和句柄.ppt

2.4 短语、直接短语和句柄,短语,令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有,则称 是相对于非终结符A的,句型的短语。,2.4 短语、直接短语和句柄,则称是直接短语。,直接短语,且 A,令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有,2.4 短语、直接短语和句柄,注意：短语和直接短语的区别在于第二个条件,直接短语中的第二个条件表示有文法规则 A，因此，每个直接短语都是某规则右部。,2.4 短语、直接短语和句柄,句柄,一个句型的最左直接短语称为该句型的句柄。,句柄特征：,(1)它是直接短语，即某规则右部。,(2)它具有最左性。,2.4 短语、直接短语和句柄,注意:短语、直接短语和句柄都是针对某一句型的，都是指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。,2.4 短语、直接短语和句柄,例如 设有文法GS=(S,A,B,a,b,P,S)其中P为：,求句型 baSb的全部短语、直接短语和句柄。,SAB,AAa|bB,Ba|Sb,2.4 短语、直接短语和句柄,对文法，首先建立该句型的推导过程：,最左推导:,最右推导:,分析 根据短语定义，可以从句型的推导过程 中找出其全部短语、直接短语和句柄。,句型 baSb,2.4 短语、直接短语和句柄,句型baSb中的子串Sb，是(相对于非终结符B)句型baSb的短语，且为直接短语。,B Sb,句型本身是(相对于非终结符S)句型baSb的短语。,根据最左推导:,2.4 短语、直接短语和句柄,句型baSb中的子串a，是(相对于非终结符B)句型baSb的短语，且为直接短语、句柄。,句型baSb中的子串ba，是(相对于非终结符A)句型baSb的短语。,B a,根据最右推导:,2.5 语法树与文法的二义性,推导和语法树,1.语法树,对句型的推导过程给出一种图形表示,这种表示称为语法树，也称推导树。,2.5.1 推导和语法树,例如 设有文法GE:,构造句型i*i+i的语法树。,首先给出句型的推导过程(最左推导)：,EE+T|ET|T,TT*F|T/F|F,F(E)|i,EE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i,2.5.1 推导和语法树,根据推导过程构造句型i*i+i的语法树如下：,EE+T,E,E,+,T,T+T,T,T*F+T,T,*,F,F*F+T,F,i*F+T,i,i*i+T,i,i*i+F,F,i*i+i,i,2.5.1 推导和语法树,由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。,因为文法的每一个句型(句子)都存在一 个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。,EE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i,2.5.1 推导和语法树,对句型i*i+i，还可给出最右推导：,2.5.1 推导和语法树,这也就是说，一棵语法树表示了 一个句型的种种可能的(但未必是所 有的)不同推导过程,包括最左(最右)推导。,3.5.1 推导和语法树,2.子树,语法树的子树是由某一结点连同所有分枝组成的部分。,3.5.1 推导和语法树,3.简单子树,语法树的简单子树是指只有单层分枝的子树。,2.5.1 推导和语法树,句型的短语、直接短语和句柄的直观解释是：,短语：子树的末端结点形成的符号串是 相对于子树根的短语。,直接短语：简单子树的末端结点形成的 符号串是相对于简单子树根的直接短语。,句柄：最左简单子树的末端结点形成的 符号串是句柄。,2.5.1 推导和语法树,短语:,i*i+i,i*i,第一个i,第二个i,第三个i,三个i都是直接短语,第一个i是句柄,注意:i+i不是句型的短语,句子 i*i+i,2.5.1 推导和语法树,前例 对文法GS=(S,A,B,a,b,P,S),其中P为：,可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。,SAB,AAa|bB,Ba|Sb,2.5.1 推导和语法树,分析 首先根据句型baSb的推导过程画出对 应的语法树如下：,Sb 为句型的相对于B的短语、直接短语,baSb 为句型的相对于S的短语,ba 为句型的相对于A的短语,a 句型的相对于B的短语、直接短语和句柄,SABbBBbaBbaSb,SABASbbBSbbaSb,由语法树可知,2.5.2 文法的二义性,从前面的讨论可以看出，对于文法G中 任一句型的推导序列,我们总能为它构造 一棵语法树，现在我们提出一个问题：,文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？,2.5.2 文法的二义性,例如 设有文法GE：,句子 i*i+i 有两个不同的最左推导，对应两棵不同的语法树。,E E+E|E*E|(E)|i,2.5.2 文法的二义性,最左推导1 EE+EE*E+E i*E+Ei*i+E i*i+i,最左推导2 EE*Ei*E i*E+Ei*i+E i*i+i,2.5.2 文法的二义性,如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。,E E+E|E*E|(E)|i,2.5.3 文法二义性的消除,1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。,2.5.3 文法二义性的消除,2.构造一个等价的无二义性文法。即 把排除二义性的规则合并到原有文法中,改写原有的文法。,例如，对于上例文法GE，将运算符的 优先顺序和结合规则：*优先于;、*左结合加到原有文法中,可构造出无二义 性文法如下：,2.5.3 文法二义性的消除,则句子i*i+i只有唯一一棵语法树：,EE+T|T,TT*F|F,F(E)|i,2.5.3 文法二义性的消除,例2 定义某程序语言条件语句的文法G为:,试证明该文法是二义性的并消除之。,分析 该文法的句子 if b if b A else A 对应下面两棵不同的语法树：,Sif b S,|if b S else S,|A(其它语句）,2.5.3 文法二义性的消除,所以该文法是二义的。,Sif b S|if b S else S|A,句子 if b if b A else A,2.5.3 文法二义性的消除,消除文法的二义性可采用下面两种方法：,不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的 if 相对。,文法G的句子 if b if b A else A只对应唯一的一棵语法树，消除了二义性。,2.5.3 文法二义性的消除,2.改写文法G为G,S S1|S2,S1 if b S1 else S1|A,S2 if b S|if b S1 else S2,G:,Sif b S,|if b S else S,|A(其它语句）,G:,2.5.3 文法二义性的消除,这是因为通过分析，得知引起二义性的原因是:ifelse 语句的 if 后可以是if型，因此改写文法时规定:if else之间只能是ifelse语句或其他语句。,2.5.3 文法二义性的消除,S S1|S2,S1 if b S1 else S1|A,S2 if b S|if b S1 else S2,对改写后的文法，句子 if b if b A else A 只对应唯一的一棵语法树。,通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G),即这两个文法所产生的语言是相同的。,2.5.3 文法二义性的消除,应该指出的是文法的二义性和语言的二义性是两个不同的概念。,2.5.3 文法二义性的消除,将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如 L=ai bj ck|i=j 或 j=k 且 i,j,k1便是这种语言。,2.6 文法和语言的分类,著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0型、1型、2型、3型。划分的依据是对文法中的规则施加不同的限制。,2.6 文法和语言的分类,0型文法（无限制文法）,若文法G=(VN,VT,P,S)中的每条规则 是这样一种结构：,而且中至少含一个非终结符,则称G 是0型文法。,(VNVT)+,(VNVT)*,0型文法描述的语言是0型语言。,0型文法没有加任何限制条件，又称为 无限制性文法，相应的语言称为无限制 性语言。,0型语言由图灵机识别。,2.6 文法和语言的分类,例如，有0型文法G=(VN,VT,P,S),其中：VN=A,B,S,VT=0,1,其描述的 0 型语言为 L0(GS)=,P:S 0AB,1B 0,B SA|01,A1 SB1,A0 S0B STOP,2.6 文法和语言的分类,1型文法（上下文有关文法）,1型文法也称为上下文有关文法，相应 的语言又称为上下文有关语言。,若文法G=(VN,VT,P,S)中的每一条规则的 形式为 A,其中：,(VNVT)*,AVN,则称G是1型文法。,1型文法描述的语言是1型语言。,1型语言由线性界限自动机识别。,(VNVT)+,2.6 文法和语言的分类,例如，有1型文法G=(VN,VT,P,S),其中：VN=S,A,B,VT=a,b,c,P:S aSAB|abB,BA BA,BA AA,AA AB,bA bb,bB bc,cB cc,其描述的1型语言为L1(GS)=anbncn|n1,2.6 文法和语言的分类,2型文法（上下文无关文法）,2型文法又称上下文无关文法，其产生的 语言又称为上下文无关的语言。,若文法G=(VN,VT,P,S)中的每一条规则的 形式为 A,其中：,AVN,(VNVT)*,则称G是2型文法。,2型文法描述的语言是2型语言。,2型语言由下推自动机识别。,例如前面描述算术表达式的文法GE:,EE+E|E*E|(E)|i,2.6 文法和语言的分类,其描述的语言为 L2(GS)=x|x a,b+且x中a和b的个数相同,例如，有2型文法G=(VN,VT,P,S),其中：VN=S,A,B,VT=a,b,P=S aB|bA,A a|aS|bAA,B b|bS|aBB,2.6 文法和语言的分类,2.6 文法和语言的分类,3型文法（正规文法）,右线性文法和左线性文法都称为3型文法。,若文法G=(VN,VT,P,S)中的每一条规则的形式 为A aB 或 A a,其中：,A,BVN,a VT*,则称G是右线性文法。,若文法G=(VN,VT,P,S)中的每一条规则的形式 为A Ba 或 A a,其中：,A,BVN,a VT*,则称G是左线性文法。,3型文法描述的语言是3型语言。,3型语言由有穷自动机识别。,3型文法也称正规文法。正规文法产生的语言 称为正规语言。,例如，用左线性正规文法和右线性正规文法定义标识符,2.6 文法和语言的分类,用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：,左线性文法:P:I l|Il|Id,右线性文法:P:I l|lT Tl|d|lT|dT,例如，用左线性正规文法和右线性正规文法定义无符号整数,2.6 文法和语言的分类,用N代表无符号整数;d代表任意一个数字；则定义的无符号整数文法为：,左线性文法:P:N Nd|d,右线性文法:P:N dN|d,2.6 文法和语言的分类,由上述四类文法的定义可知,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的，有 L0 L1 L2 L3。,2.7 有关文法的实用限制和变换,文法是用来描述程序设计语言的，在 实际应用中需要对文法加一些限制条件。,1.文法中不能含有形如A A 的规则。这种规则我们称之为有害规则。,对文法的实用限制有以下两点：,2.7 有关文法的实用限制和变换,2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：,(1)某条规则 A 的左部符号A不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。,(2)对文法中的某个非终结符A，无法从它推出任何终结符号串来。,2.7 有关文法的实用限制和变换,例如 设有文法GS:,P:S Bd,A Ad|d,B Cd|Ae,C Ce,D e,删除多余规则后的文法变换为:,P:S Bd,A Ad|d,B Ae,2.7 有关文法的实用限制和变换,若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。,作业,P26 2.1 2.2（2）2.3 L1，L2，L3 2.7 2.8 2.9 2.11 2.12,本章重点介绍了语言的语法结构的形式描 述、语法树以及文法的二义性,主要内容有：,1.设计一个文法定义一个已知的语言,(1)文法是一个四元组 G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。,从文法定义可知,文法对于程序设计者来 说，文法给出了语言的精确定义和描述。,本章小结,本小结花时45分钟2004/2/28,(2)分析已知语言句子的结构特征,设计 出相应的一组规则，但不唯一。,(4)若语言是无穷集合,设计该语言的文 法一定是递归的。,本章小结,(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。,分析 根据语言句子的结构特征，设计出相 应规则,例1.给出语言 L2=an bm|mn1 的文法,P2:SAB,L2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，,AaAb|ab,BbB|,本章小结,分析 根据语言句子的结构特征，设计出相 应规则,例2.给出语言 L1=a2n+1|n0 的文法,P1:AaB|a,P1：AaAa|a,或,L1=a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，,Baa|aBa,本章小结,本章小结,分析 根据语言句子的结构特征，设计出相应规则,例3.给出语言L3=anbmck|n,m,k0的文法,P3:AaA|bB|cC|,P3:AaA|B,或,L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc,ab,abb,bc,bcc，,CcC|,BbB|cC|,CcC|,BbB|C,本章小结,L4=0,2,4,6,8,10,12,14,16,18,20,22,24,26,例4.写一个 文法,使其语言是正偶数的集合,每个偶数不以0开头。,P4:NE|AE,N0|2|4|6|8|BN,或,分析 不以0开头的偶数集合中串的结构特征:,AD|AD,E0|2|4|6|8,D1|2|3|9,D0|1|2|3|9,B1|2|3|9|B0,P4:,本章小结,A 0A1|,P:S 1S0|0A1|,例5.给出语言L=1n0m1m0n|n,m0的 文法。,分析 根据语言句子的结构特征,设计 出相应规则,L=,01,0011,10,1100,1010,100110,110100,11001100,本章小结,P:S a|0S0|1S1,例6.给出语言L=WaWt|W0|1*,Wt 表示W的逆的文法。,分析 根据语言句子的结构特征，设计 出相应规则,L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,W=,0,1,01,10,00,11,101,110,100,111,本章小结,2.已知一个文法，确定该文法所定义的 语言。,(2)给定一个文法，可根据语言和推导定 义推导出文法的句子，从而确定出该文法 所定义的语言。,本章小结,自然语言描述。例如,L=x|xa,b+且x中a,b个数相同,式子描述。例如 L=a2nbb|n0。,正规式描述。,(3)语言可用,本章小结,例1 文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？,分析 AbAbbAbbbAbnAbna,L(GA)=bna|n0,本章小结,例2 文法GN为:,N ND|DD 0|1|2|3|4|5|6|7|8|9,(1)GN所生成的语言是什么？,(2)给出句子0127的最左、最右推导。,本章小结,L(GN)=|0,1,2,9+,=|为可带前导0的正整数,=|为数字串,最左推导:,NNDN7ND7N27ND27 N127D1270127,最右推导:,NNDNDDNDDDDDDD 0DDD01DD012D0127,N ND|DD 0|1|2|3|4|5|6|7|8|9,本章小结,例3.已知文法GS=(A,B,a,b,c,d,P,S),其中 P 为:,分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anbnc2Bd2 anbncm-1Bdm-1anbncmdm,L(GS)=anbncmdm|n,m1,该文法 所生成的语言是什么？,A aAb|ab,B cBd|cd,S AB,本章小结,3.求句型的短语、直接短语和句柄,(1)短语、直接短语和句柄是对某句 型而言的。,(2)短语总是句型的某个子串，它对应 子树未端结点形成的符号串。,(3)直接短语是某条规则右部，它对应 简单子树未端结点形成的符号串。,(4)最左边的直接短语是句柄。,本章小结,例1 已知文法GE：,证明 E+T*F是它的一个句型,指出这个句型的短语直接短语和句柄。,EE+TE+T*F,短语:E+T*F、T*F,E+T*F是它的一个句型。,画出该句型的语法树:,句柄:T*F,直接短语:T*F,EE+T|E-T|T,TT*F|T/F|T,T(E)|i,2.9相似,本章小结,例2 已知文法GS：,试找出符号串(a)和(A(SaA)(b)的短语 直接短语和句柄(如果有的话)。,S(AS)|(b),A(SaA)|(a),符号串(a)不是文法的句型，因此 它没有短语直接短语和句柄。,2.11,本章小结,S(AS)(A(AS)(A(A(b)(A(SaA)(b),符号串(A(SaA)(b)是文法的句型，画出该句型的语法树如下图：,S(AS)|(b),A(SaA)|(a),本章小结,从句型的语法树求 短语:(A(SaA)(b)(SaA)(b)(SaA)(b),直接短语：(SaA)、(b),句柄：(SaA),S(AS)|(b),A(SaA)|(a),对于句型(A(SaA)(b),本章小结,4文法二义性的判断,一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。,本章小结,例1 设有文法GS:SiSeS|iS|i,试证明文法GS有二义性。,分析 因为对文法的句子 iiiei 有如下两 棵不同的语法树与之对应，所以该文法 是二义的,本章小结,SiSeS|iS|i,句子 iiiei 对应下面两颗语法树：,本章小结,NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9,1.试证明文法GN有二义性。,2.此文法所描述的语言是什么？,3.试写出另一文法G使L(G)=L(G)且 G是无二义性的。,例2 设有文法GN:,本章小结,分析 因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的,NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9,本章小结,该文法所描述的语言是所有无符号偶数 的集合(可以0开头)。,改写后的文法GS为:NSE|E SSD|D E0|2|4|6|8 D0|1|2|3|4|5|6|7|8|9,NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9,本节完,