形式语言与自动机理论电子教案06公开课获奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,/10/10,1,第6章 上下文无关语言,G,bra,：,S,S(S)|,L(G,bra,),不是,RL,是CFL,高级程序设计语言绝大多数语法构造都可以用上下文无关文法(CFG)描述。,BNF(巴科斯范式：Backus normal form，又叫Backus-naur form)。,第1页,/10/10,2,第6章 上下文无关语言,重要内容,有关CFL分析,派生和归约、派生树,CFG化简,无用符、单一产生式、空产生式,CFG范式,F,GNF,CFG自嵌套特性,第2页,/10/10,3,第6章 上下文无关语言,重点,CFG化简。,CFG到GNF转换。,难点,CFG到GNF转换，尤其是其中用右递归替代左递归问题。,第3页,/10/10,4,6.1 上下文无关语言,文法G=(V，T，P，S)被称为是上下文无关。假如除了形如A产生式之外，对于P，均有|，并且V成立。,关键：对于AV，假如AP，则不管A出目前句型任何位置，我们都可以将A替代成，而不考虑A上下文。,第4页,/10/10,5,6.1.1 上下文无关文法派生树,算术表达式文法,Gexp1：EE+T|E-T|T,TT*F|T/F|F,FFP|P,P(E)|N(L)|id,Nsin|cos|exp|abs|log|int,LL,E|E,第5页,/10/10,6,6.1.1 上下文无关文法派生树,算术表达式x+x/y2不一样样派生,E,E+T,T+T,F+T,P+T,x+T,x+T/F,x+F/F,x+P/F,x+x/F,x+x/F,P,x+x/P,P,x+x/y,P,x+x/y,2,E,E+T,E+T/F,E+T/FP,E+T/F2,E+T/P2,E+T/y2,E+F/y2,E+P/y2,E+x/y2,T+x/y2,F+x/y2,P+x/y2,x+x/y,2,E,E+T,T+T,T+T/F,F+T/F,F+T/FP,P+T/FP,x+T/FP,x+F/FP,x+F/F2,x+F/P2,x+P/P2,x+P/y2,x+x/y,2,第6页,/10/10,7,6.1.1 上下文无关文法派生树,文法Gexp1句子x+x/y2构造。,第7页,/10/10,8,6.1.1 上下文无关文法派生树,派生树(derivation tree),一棵(有序)树(ordered tree),树每个顶点有一种标识X，且XVT,树根标识为S；,假如非叶子顶点v标识为A，v儿子从左到右依次为v1，v2，vn，并且它们分别标识为X1，X2，Xn，则AX1X2XnP；,假如X是一种非叶子顶点标识，则XV；,假如顶点v标识为，则v是该树叶子，并且v是其父顶点惟一儿子。,第8页,/10/10,9,6.1.1 上下文无关文法派生树,别称,生成树,分析树(parse tree),语法树(syntax tree),次序,v1，v2是派生树T两个不一样样顶点，假如存在顶点v，v至少有两个儿子，使得v1是v较左儿子后裔，v2是v较右儿子后裔，则称顶点v1在顶点v2左边，顶点v2在顶点v1右边。,第9页,/10/10,10,6.1.1 上下文无关文法派生树,成果(yield),派生树T所有叶子顶点从左到右依次标识为X1，X2，Xn，则称符号串X1X2Xn是T成果。,一种文法可以有多棵派生树，它们可以有不一样样成果。,句型派生树：“G成果为派生树”。,第10页,/10/10,11,6.1.1 上下文无关文法派生树,派生子树(subtree),满足派生树定义中除了对跟结点标识规定以外各条树叫派生子树(subtree)。,假如这个子树根标识为A，则称之为A子树。,惟一差异是根结点可以标识非开始符号。,第11页,/10/10,12,6.1.1 上下文无关文法派生树,定理6-1 设CFG G=(V，T，P，S)，S*充足必要条件为G有一棵成果为派生树。,证明：,证一种更为一般结论：对于任意AV，A*充足必要条件为G有一棵成果为A-子树。,充足性：设G有一棵成果为A-子树，非叶子顶点个数n施归纳，证明A*成立。,第12页,/10/10,13,6.1.1 上下文无关文法派生树,设A-子树有k+1个非叶子顶点，根顶点A儿子从左到右依次为v1，v2，vm，并且它们分别标识为X1，X2，Xm。,AX1X2XmP。,以X1，X2，Xm为根子树成果依次为1，2，m。,X1，X2，Xm为根子树非叶子顶点个数均不不小于k。,第13页,/10/10,14,6.1.1 上下文无关文法派生树,X1*1,X2*2,Xm*m,并且,=12m,第14页,/10/10,15,6.1.1 上下文无关文法派生树,A,X,1,X,2,X,m,*,1,X,2,X,m,*,1,2,X,m,*,1,2,m,第15页,/10/10,16,6.1.1 上下文无关文法派生树,第16页,/10/10,17,6.1.1 上下文无关文法派生树,必要性,设An，现施归纳于派生步数n，证明存在成果为A-子树。,设nk(k1)时结论成立，往证当n=k+1时结论也成立：令Ak+1，则有：,AX1X2Xm,*1X2Xm,*12Xm,*12m,第17页,/10/10,18,6.1.1 上下文无关文法派生树,第18页,/10/10,19,6.1.1 上下文无关文法派生树,例6-1,设,G,bra,：,S,S(S)|,，,()(),和,(S)(S),派生树。,第19页,/10/10,20,6.1.1 上下文无关文法派生树,有关标识结点,第20页,/10/10,21,6.1.1 上下文无关文法派生树,最左派生(leftmost derivation),派生过程中，每一步都是对目前句型最左变量进行替代。,左句型(left sentencial form),最左派生得到句型可叫做左句型。,最右归约(rightmost reduction),与最左派生对相归约叫做最有归约。,第21页,/10/10,22,6.1.1 上下文无关文法派生树,最右派生(rightmost derivation),派生过程中，每一步都是对目前句型最右变量进行替代。,右句型(right sentencial form),最右派生得到句型可叫做右句型。,最左归约(leftmost reduction),与最左派生对相归约叫做最右归约。,第22页,/10/10,23,6.1.1 上下文无关文法派生树,规范派生(normal derivation),最右派生。,规范句型(normal sentencial form),规范派生产生句型。,规范归约(normal reduction),最左归约。,第23页,/10/10,24,6.1.1 上下文无关文法派生树,定理6-2 假如是CFG G一种句型，则G中存在最左派生和最右派生。,证明：,基本思绪：对派生步数n施归纳，证明对于任意AV，假如An，在G中，存在对应从A到最左派生：An左。,第24页,/10/10,25,6.1.1 上下文无关文法派生树,A,X,1,X,2,X,m,*,1,X,2,X,m,*,1,2,X,m,*,1,2,m,A,左,X,1,X,2,X,m,*左,1,X,2,X,m,*左,1,2,X,m,*,左,1,2,m,同理可证，句型有最右派生。,第25页,/10/10,26,6.1.1 上下文无关文法派生树,定理6-3 假如是CFG G一种句型，派生树与最左派生和最右派生是一一对应，不过，这棵派生树可以对应多种不一样样派生。,第26页,/10/10,27,6.1.2 二义性,简朴算术表达式二义性文法,Gexp2：EE+E|E-E|E/E|E*E,E EE|(E)|N(L)|id,Nsin|cos|exp|abs|log|int,LL,E|E,第27页,/10/10,28,6.1.2 二义性,E,E+E,x+E,x+E/E,x+x/E,x+x/E,E,x+x/y,E,x+x/y,2,句子x+x/y2在文法中三个不一样样最左派生,E,E/E,E+E/E,x+E/E,x+x/E,x+x/E,E,x+x/y,E,x+x/y,2,E,E,E,E/E,E,E+E/E,E,x+E/E,E,x+x/E,E,x+x/y,E,x+x/y,2,第28页,/10/10,29,6.1.2 二义性,对应3个不一样样语法树,第29页,/10/10,30,6.1.2 二义性,二义性(ambiguity),CFG G=(V，T，P，S)，假如存在wL(G)，w至少有两棵不一样样派生树，则称G是二义性。否则，G为非二义性。,二义性问题是不可解(unsolvable)问题。,第30页,/10/10,31,6.1.2 二义性,例6-2 用其他措施消除二义性。,Gifa：Sif E then S else S|if E then S,Gifm：SU|M,Uif E then S,Uif E then M else U,Mif E then M else M|S,Gifh：STS|CS,Cif E then,T CS else,第31页,/10/10,32,6.1.2 二义性,例 6-3 设,Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1,可以用如下文法产生语言Lambiguity：,G：SAB|0C3,A01|0A1,B23|2B3,C0C3|12|1D2,D12|1D2,语言Lambiguity不存在非二义性文法。,第32页,/10/10,33,6.1.2 二义性,固有二义性(inherent ambiguity),假如语言L不存在非二义性文法，则称L是固有二义性，又称L是先天二义性。,文法可以是二义性。,语言可以是固有二义性。,第33页,/10/10,34,6.1.3 自顶向下分析和自底向上分析,自顶向下分析措施,通过考察与否可以从给定文法开始符号派生出一种符号串，可以鉴定一种符号串与否为该文法句子。,例,SaAb|bBa,AaAb|bBa,Bd,第34页,/10/10,35,aabdabb派生树自顶向下“生长”过程,第35页,/10/10,36,6.1.3 自顶向下分析和自底向上分析,自底向上分析措施,通过考察与否可以将一种符号串归约为给定文法开始符号，完毕鉴定一种符号串与否为该文法句子任务。,和归约与派生是互逆过程相对应，自顶向下分析与自底向上分析互逆分析过程。,第36页,/10/10,37,aabdabb派生树自底向上“生长”过程,第37页,/10/10,38,6.2 上下文无关文法化简,如下文法具有无用“东西”,G1：S0|0A|E,A|0A|1A|B,B_C,C0|1|0C|1C,D1|1D|2D,E0E2|E02,去掉,无用“东西”后,文法,G,2,：S,0|0A,A,|0A|1A|B,B,_C,C,0|1|0C|1C,第38页,/10/10,39,6.2 上下文无关文法化简,去掉产生式A,后,文法,G,3,：S,0|0A,A,0|1|0A|1A|B,B,_C,C,0|1|0C|1C,去掉产生式A,B,后,文法,G,4,：S,0|0A,A,0|1|0A|1A|_C,C,0|1|0C|1C,可以去掉文法中无用符号、产生式和单一产生式。,第39页,/10/10,40,6.2.1 去无用符号,无用符号(useless symbol),对于任意XVT，假如存在wL(G)，X出目前w派生过程中，即存在，(VT)*，使得S*X*w，则称X是有用，否则，称X是无用符号。,对CFG G=(V，T，P，S),G中符号X既也许是有用，也也许是无用。当X是无用时候，它既也许是终极符号，也也许是语法变量。,第40页,/10/10,41,6.2.1 去无用符号,对于任意XVT，假如X是有用，它必须同步满足如下两个条件：,存在wT*，使得X*w；,，(VT)*，使得S*X。,注意到文法是语言有穷描述，因此，集合V，T，P都是有穷。从而我们有也许构造出有效算法，来完毕消除文法无用符号工作。,第41页,/10/10,42,6.2.1 去无用符号,算法 6-1 删除派生不出终极符号行变量。,输入：CFG G=(V，T，P，S)。,输出：CFG G=(V，T，P，S)，V中不含派生不出终极符号行变量，并且L(G)=L(G)。,重要环节：,第42页,/10/10,43,6.2.1 去无用符号,(1)OLDV=,;,(2)NEWV=A|A,wP且wT,*,；,(3),while,OLDVNEWV,do,begin,(4)OLDV=NEWV；,(5)NEWV=OLDVA|A,P且(TOLDV),*,end,(6)V=NEWV；,(7)P=A,|A,P且 AV且(TV),*,第43页,/10/10,44,6.2.1 去无用符号,第(3)条语句控制对NEWV进行迭代更新。第一次循环将那些恰通过两步可以派生出终极符号行变量放入NEWV；第二次循环将那些恰通过三步和某些至少通过三步可以派生出终极符号行变量放入NEWV；，第n次循环将那些恰通过n步和某些至少通过n+1步可以派生出终极符号行变量放入NEWV。这个循环一直进行下去，直到所给文法G中所有可以派生出终极符号行变量都被放入NEWV中。,第44页,/10/10,45,6.2.1去无用符号,定理 6-4 算法6-1是对旳。,证明要点：首先证明对于任意AV，A被放入V中充要条件是存在wT，An w。再证所构造出文法是等价。,(1)对A被放入NEWV循环次数n施归纳，证明必存在wT，满足A w。,第45页,/10/10,46,6.2.1去无用符号,(2)施归纳于派生步数n，证明假如An w，则A被算法放入到NEWV中。实际上，对原教材所给证明进行分析，同步考虑算法6-1实际运行，可以证明，A是在第n次循环前被放入到NEWV中。,(3)证明L(G)=L(G)。显然有L(G)L(G)，因此只需证明L(G)。,第46页,/10/10,47,6.2.1 去无用符号,算法 6-2 删除不出目前任何句型中语法符号。,输入：CFG G=(V，T，P，S)。,输出：CFG G=(V，T，P，S)，VT中符号必在G某个句型中出现，并且有L(G)=L(G)。,重要环节：,第47页,/10/10,48,6.2.1 去无用符号,重要环节：,(1)OLDV=;,(2)OLDT=;,(3)NEWV=SA|SAP;,(4)NEWT=a|SaP;,第48页,/10/10,49,6.2.1去无用符号,(5),while,OLDVNEWV 或者OLDTNEWT,do,begin,(6)OLDV=NEWV;,(7)OLDT=NEWT;,(8)NEWV=OLDVB|AOLDV且 A,BP 且BV;,(9)NEWT=OLDTa|AOLDV且 A,aP 且aT;,end,第49页,/10/10,50,6.2.1去无用符号,(10)V=NEWV;,(11)T=NEWT;,(12)P=A,|A,P且 AV且(TV),*,。,第50页,/10/10,51,6.2.1去无用符号,定理 6-5 算法6-2是对旳。,证明要点：,(1)施归纳于派生步数n，证明假如Sn X，则当XV时，X在算法中被语句(3)或者语句(8)放入NEWV；当XT时，它在算法中被语句(4)或者语句(9)放入NEWT。,(2)对循环次数n施归纳，证明假如X被放入NEWT或者NEWV中，则必然存在，(NEWVNEWT)*，使得Sn X。,(3)证明L(G)=L(G)。,第51页,/10/10,52,6.2.1去无用符号,定理6-6 对于任意CFL L，L，则存在不含无用符号CFG G，使得L(G)=L。,证明要点：,依次用算法6-1和算法6-2对文法进行处理，可以得到等价不含无用符号文法。,不可先用算法6-2后用算法6-1。,第52页,/10/10,53,6.2.1去无用符号,例 6-2-1 设有如下文法,SAB|a|BB，Aa，Cb|ABa,先用算法6-2，文法被化简成：,SAB|a|BB，Aa,再用算法6-1，可得到文法：,S a，Aa,显然，该文法中变量A是新无用变量。,第53页,/10/10,54,6.2.2 去-产生式,-产生式（-production）,形如A,产生式叫做,-产生式。,-产生式,又称为,空产生式（null production。,可空(nullable)变量,对于文法G=(V，T，P，S)中任意变量A，假如A,+,，则称A为,可空变量。,第54页,/10/10,55,6.2.2 去-产生式,对形如AX1X2Xm产生式进行考察，找出文法可空变量集U，然后对于HU，从产生式AX1X2Xm中删除H中变量。对于不一样样H，得到不一样样A产生式，用这组A产生式替代产生式AX1X2Xm。,必须防止在这个过程中产生新-产生式：当 X1，X2，XmU时，不可将X1，X2，Xm同步从产生式AX1X2Xm中删除。,第55页,/10/10,56,6.2.2 去-产生式,算法6-3 求CFG G可空变量集U。,输入：CFG G=(V，T，P，S)。,输出：G可空变量集U。,重要环节：,(1)OLDU=;,(2)NEWU=A|AP;,第56页,/10/10,57,6.2.2 去-产生式,(3)while NEWUOLDU do,begin,(4)OLDU=NEWU;,(5)NEWU=OLDU A|AP并且OLDU*,end,(6)U=NEWU,第57页,/10/10,58,6.2.2 去-产生式,定理 6-7 对于任意CFG G，存在不含-产生式CFG G使得L(G)=L(G)-。,证明：,(1)构造,设CFG G=(V，T，P，S)，,用算法6-3求出G可空变量集U，,构造P。,第58页,/10/10,59,6.2.2 去-产生式,对于 AX1X2XmP,将A12m放入P，其中,if XiU then i=Xi或者i=；,if XiU then i=Xi,规定：在同一产生式中，1，2，m不能同步为。,第59页,/10/10,60,6.2.2 去-产生式,证明对于任意wT+，AnG w充足必要条件是A。,必要性：设AnG w，施归纳于n，证明AmG w成立。,当n=1时，由AG w知，AwP，按照定理所给构造G措施，必然有AwP。因此，AG w成立。,第60页,/10/10,61,6.2.2 去-产生式,设nk时结论成立(k1)，当n=k+1时,A,X,1,X,2,X,m,*,G,w,1,X,2,X,m,*,G,w,1,w,2,X,m,*,G,w,1,w,2,w,m,其中w,1,w,2,w,m,=w，且w,1,，w,2,，w,m,T,*,。,第61页,/10/10,62,6.2.2 去-产生式,注意到w，必存在1im，wi，设i，j，k是w1，w2，wm中所有非空串下标，并且1ijkm，即：,w=wiwjwk,按照G构造措施，A XiXjXkP,再由归纳假设，,Xi*G wi，Xj*G wj，Xk*G wk。,第62页,/10/10,63,6.2.2 去-产生式,A*G XiXjXk,*G wiXjXk,*G wiwjXk,*G wiwjwk,因此，结论对n=k+1成立。由归纳法原理，结论对所有n成立。,第63页,/10/10,64,6.2.2 去-产生式,充足性：设AmG w，施归纳于m，证明AnG w成立。,当m=1时，由AG w知，AwP，按照定理所给构造G措施，必然有AP。Aw是通过删除产生式A右部中可空变量而构造出来，因此，,AG*G w 成立。,第64页,/10/10,65,6.2.2 去-产生式,设nk时结论成立(k1)，当m=k+1时,A,*,G,X,i,X,j,X,k,*,G,w,i,X,j,X,k,*,G,w,i,w,j,X,k,*,G,w,i,w,j,w,k,=w,其中X,i,*,G,w,i,，X,j,*,G,w,j,，X,k,*,G,w,k,。,第65页,/10/10,66,6.2.2 去-产生式,表明A XiXjXkP。按照G构造措施，必然存在A X1X2XmP，并且,Xi，Xj，XkX1，X2，Xm,X1，X2，Xm-Xi，Xj，XkU,从而，,AG X1X2Xm,*G XiXjXk,第66页,/10/10,67,6.2.2 去-产生式,再根据Xi*G wi，Xj*G wj，Xk*G wk和归纳假设，有,Xi*G wi，Xj*G wj，Xk*G wk。,这表明，如下派生成立：,AG X1X2Xm,*G XiXjXk,*G wiXjXk,*G wiwjXk,*G wiwjwk=w,第67页,/10/10,68,6.2.2 去-产生式,表明结论对m=k+1成立。由归纳法原理，结论对任意m成立。,注意到A 任意性，当S=A时结论成立。即：,S*G w 充足必要条件是S*G w,亦即：L(G)=L(G)-。,定理得证。,第68页,/10/10,69,6.2.3 去单一产生式,文法G,exp1,：E,E+T|E-T|T,T,T*F|T/F|F,F,FP|P,P,(E)|N(L)|id,N,sin|cos|exp|abs|log|int,L,L,E|E,存在派生：,E,T,F,P,id,第69页,/10/10,70,6.2.3 去单一产生式,G,exp3,：E,E+T|E-T|T*F|T/F|FP|(E)|N(L)|id,T,T*F|T/F|FP|(E)|N(L)|id,F,FP|(E)|N(L)|id,P,(E)|N(L)|id,N,sin|cos|exp|abs|log|int,L,L,E|E,该文法中不存在类似派生。,第70页,/10/10,71,6.2.3 去单一产生式,单一产生式(unit production),形如AB产生式称为单一产生式。,定理 6-8对于任意CFG G，L(G)，存在等价CFG G1，G1不含无用符号、-产生式和单一产生式。,满足本定理CFG为化简过文法。,已经有去无用符号和去-产生式结论，因此只讨论去单一产生式问题。,第71页,/10/10,72,6.2.3 去单一产生式,证明要点：,（1）构造G2，满足L(G2)=L(G)，并且G2中不含单一产生式。,用非单一产生式A1取代A1*G An用到产生式系列 A1A2，A2A3，An-1An，An。其中，A1A2，A2A3，An-1An都是单一产生式。（n1）,第72页,/10/10,73,6.2.3 去单一产生式,（2）证明L(G2)=L(G)。,用A1所完毕派生A1与产生式系列A1A2，A2A3，An-1An，An所完毕派生A1*G An相对应。,在原文法中也许会出现一种变量在派生过程中循环出现实状况况，在wL(G)证明w L(G2)过程中，要取w在G中一种最短最左派生。,S=0G1G2GGn=w,第73页,/10/10,74,6.2.3 去单一产生式,（3）删除G2中无用符号。,由于在删除单一产生式后，文法中也许出现新无用符号，因此，我们还需要再次删除新出现无用符号。,此外，在去-产生式后也许会产生新单一产生式，也也许会引进新无用符号。这是值得注意。,第74页,/10/10,75,6.3 乔姆斯基范式,乔姆斯基范式文法(Chomsky normal form，F)简称为Chomsky文法，或Chomsky范式。,CFG G=(V，T，P，S)中产生式形式：,ABC，Aa,其中，A、B、CV，aT。,F中，不容许有-产生式、单一产生式。,第75页,/10/10,76,6.3 乔姆斯基范式,例 6-3-1 试将文法Gexp4转换成等价 GNF。,Gexp4：EE+T|T*F|FP|(E)|id,TT*F|FP|(E)|id,FFP|(E)|id,P(E)|id,可以分两步走,变成A a和A A1A2An形式。,变成 F。,第76页,/10/10,77,第一步,E,EA,+,T|T A,*,F|F A,P|A,(,EA,5,|id,T,TA,*,F|FA,P|A,(,EA,),|id,F,FA,P|A,(,EA,),|id,P,A,(,EA,),|id,A,+,+,A,*,*,A,A,(,(,A,),),第77页,/10/10,78,第二步,Gexp F：EEA1|TA2,E FA3|A(A4|id,TTA2|FA3|A(A4|id,FFA3|A(A4|id,PA(A4|id,A+,A*,A,A,(,(,A,),),A,1,A,+,T,A,2,A,*,F,A,3,A,P,A,4,EA,),第78页,/10/10,79,6.3 乔姆斯基范式,定理6-9 对于任意CFG G，L(G)，存在等价 F G2。,证明要点：,1.构造 F,按照上述例子所描述转换措施，在构造给定CFG F时，可以分两步走。,假设G为化简过文法,构造G1=(V1，T，P1，S)G1中产生式都是形如AB1B2Bm和Aa产生式，其中，A，B1，B2，BmV1，aT，m2,第79页,/10/10,80,6.3 乔姆斯基范式,构造 F G2=(V2，T，P2，S)。,m3时，引入新变量：B1、B2、Bm-2，将G1形如AA1A2Am产生式替代成,AA1B1,B1A2B2,Bm-2Am-1Am,第80页,/10/10,81,6.3 乔姆斯基范式,2.构造对旳性证明。,按照上述构造，证明被替代产生式是等价。,例如：在第二步中A A1B1，B1A2B2，Bm-2Am-1Am与AA1A2Am等价。,第81页,/10/10,82,6.3 乔姆斯基范式,例 6-6 试将如下文法转换成等价 F。,SbA|aB,AbAA|aS|a,BaBB|bS|b,第82页,/10/10,83,6.3 乔姆斯基范式,先引入变量Ba，Bb和产生式Baa，Bbb，完毕第一步变换。,SBbA|BaB,ABbAA|BaS|a,BBaBB|BbS|b,Baa,Bbb,第83页,/10/10,84,6.3 乔姆斯基范式,引入新变量B,1,、B,2,S,B,b,A|B,a,B,A,B,b,B,1,|B,a,S|a,B,B,a,B,2,|B,b,S|b,B,a,a,B,b,b,B,1,AA,B,2,BB,第84页,/10/10,85,6.3 乔姆斯基范式,不能由于本来有产生式A a和B b而放弃引进变量Ba、Bb和产生式Baa、Bbb。,L(A)=x|xa，b+&x中a个数比b个数恰多1个。,L(B)=x|xa，b+&x中b个数比a个数恰多1个。,L(Ba)=a。,L(Bb)=b。,第85页,/10/10,86,6.4 格雷巴赫范式,格雷巴赫范式文法(Greibach normal form,GNF)简称为Greibach文法，或Greibach范式。,Aa,其中，AV，aT，V*。,在GNF中，有如下两种形式产生式,Aa,AaA1A2Am(m1),第86页,/10/10,87,6.4 格雷巴赫范式,右线性文法是一种特殊GNF。,由于GNF中不存-产生式，因此对任意GNF G，L(G)。,当L(G)时，可以找到一种GNF G，使得 L(G)=L(G)。,通过化简CFG，均有一种等价GNF。,第87页,/10/10,88,6.4 格雷巴赫范式,引理 6-1 对于任意CFG G=(V，T，P，S)，ABP，且G中所有B产生式为,B1|2|n,取G1=(V，T，P1，S),P1=(P-AB)A1，A2，An,则，L(G1)=L(G)。,第88页,/10/10,89,6.4 格雷巴赫范式,证明,如下两组产生式等价,AB；B1|2|n,A1，A2，An,第89页,/10/10,90,6.4 格雷巴赫范式,递归(recursive),假如G中存在形如AnA派生，则称该派生是有关变量A递归，简称为递归派生。,当n=1时，称该派生有关变量A直接递归(directly recursive)，简称为直接递归派生。,形如AA产生式是变量A直接递归(directly recursive)产生式。,第90页,/10/10,91,6.4 格雷巴赫范式,当n2时，称该派生是有关变量A间接递归(indirectly recursive)派生。简称为间接递归派生。,当=时，称对应(直接/间接)递归为(直接/间接)左递归(left-recursive)；,当=时，称对应(直接/间接)递归为(直接/间接)右递归(right-recursive)。,第91页,/10/10,92,6.4 格雷巴赫范式,引理 6-2 对于任意CFG G=(V，T，P，S)，G中所有A产生式,A,1,|,2,|,m,A,1,B,|,2,B|,m,B,B,1,|,2,|,n,B,1,B,|,2,B|,n,B,可以被等价地替代为产生式组,A,A,1,|A,2,|A,n,A,1,|,2,|,m,第92页,/10/10,93,6.4 格雷巴赫范式,证明要点：,用直接右递归取代本来直接左递归。,两组产生式产生符号串都是,前者是先产生,然后产生,k,。,第93页,/10/10,94,6.4 格雷巴赫范式,后者先产生,k,。,然后产生,第94页,/10/10,95,6.4 格雷巴赫范式,第95页,/10/10,96,6.4 格雷巴赫范式,定理6-10 对于任意CFG G，L(G)，存在等价GNF G1。,证明要点：,(1)使用引理6-1将产生式都化成如下形式产生式,AA1A2Am,AaA1A2Am-1,Aa,其中，A，A1，A2，AmV1，aT，m2。,第96页,/10/10,97,6.4 格雷巴赫范式,(2)根据引理6-1和6-2，将产生式变成如下形式产生式,AiAjij+1,Aia,Bi,其中，V2=V1 B1，B2，Bn，V1 B1，B2，Bn=。,“B类变量”：B1，B2，Bn是在文法改造过程中引入新变量。,V1中变量称为“A类变量”。,第97页,/10/10,98,6.4 格雷巴赫范式,（3）根据引理6-1，从编号较大变量开始，逐渐替代，使所有产生式满足GNF规定：,1)for k=m-1 to 1 do,2)if AkAk+1P2 then,3)for 所有Ak+1产生式Ak+1 do 将产生式Ak放入P3；,4)for k=1 to n do,5)根据引理6-1，用P3中产生式将所有Bk产生式替代成满足GNF规定形式。,第98页,/10/10,99,6.5 自嵌套文法,自嵌套文法(self-embedding grammar),CFG G=(V，T，P，S)是化简后文法，假如G中存在有形如A+A派生，则称G为自嵌套文法，其中、(VT)+。,自嵌套文法描述语言可以是正则语言,例如：,S0S0|1S1|0S1|1S0|0S|1S|0|1,第99页,/10/10,100,6.5 自嵌套文法,定理 6-11 非自嵌套文法产生语言是正则语言。,证明要点：,（1）将G化成GNF,（2）取RG G=(V,T,P,S)，其中,V=|V+并且|m(n-2)+1,P=A a|AaP并且V*,当=时，=。,第100页,/10/10,101,6.6 小结,本章讨论了CFG派生树，A子树，最左派生与最右派生，派生与派生树关系，二义性文法与固有二义性语言，句子自顶向下分析和自底向上分析；无用符号消去算法，空产生式消除，单一产生式消除。CFG F和GNF；CFG自嵌套特性。,(1)S*充足必要条件为G有一棵成果为派生树。,(2)假如是CFG G一种句型，则G中存在最左派生和最右派生。,第101页,/10/10,102,6.6 小结,(3)文法也许是二义性，但语言只也许是固有二义性，且这种语言是存在。,(4)对于任意CFG G，L(G)，存在等价CFG G1，G1不含无用符号、-产生式和单一产生式。,(5)对于任意CFG G，L(G)，存在等价 F G2。,(6)对于任意CFG G，L(G)，存在等价GNF G3。,(7)非自嵌套文法产生语言是正则语言。,第102页,