形式语言和自动机课件——上下文无关文法与下推自动机.ppt

《形式语言和自动机课件——上下文无关文法与下推自动机.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4.5上下文无关文法与下推自动机上下文无关文法与下推自动机的等价性:PDA与上下文无关文法之间存在着对应关系。即：PDA(M)＝>CFGCFG=>PDA(M)1CollegeofComputerScience&Technology,BUPT从上下文无关文法构造等价的下推自动机定理4.5.1（由CFG可导出PDA）：设上下文无关文法G＝（N，T，P，S），产生语言L（G），则存在PDAM，以空栈接受语言Lφ(M),使Lφ(M)=L(G)。证明：构造下推自动机M，使M按文法G的最左推导方式工作。2CollegeofComputerScience&Technology,B

2、UPT构造方法设CFGG=(N,T,P,S)，构造一个空栈接受方式的PDAM＝（Q，T，Γ，δ，q0，z0，F）其中Q＝{q},Γ=N∪T,q0＝q，z0＝S,F＝φ(∵以空栈接受)即M=({q},T,NT,,q,S,F),转移函数定义如下：(1)对每一AN,(q,,A)={(q,)"A”P};（即将栈顶的A换为β）(2)对每一aT,(q,a,a)={(q,)}.（即若栈顶为终结符，则退栈）从上下文无关文法构造等价的下推自动机3CollegeofComputerScience&Technology,BUPTqε，z0＝S/β若S→β∈Pε，

3、A/α若A→α∈Pa,a/εaT,从上下文无关文法构造等价的下推自动机用图形表示：例1对右边产生式所代表CFG，依上述方法构造的PDA为EEOE(E)vdO＋({q},{v,d,+,,(,)},{E,O,v,d,+,},,q,E,φ),其中定义为(q,,E)={(q,EOE),(q,(E)),(q,v),(q,d)},{(q,＋),(q,)},(q,,O)={(q,)},(q,v,v)=(q,d,d)={(q,)}(q,＋,＋)=(q,,)=(q,(,()=(q,),))=4CollegeofComputerSci

4、ence&Technology,BUPT自顶向下的分析过程定理的物理意义：利用下推自动机进行自顶向下的分析，检查一个句子的最左推导过程。步骤如下：(1)初始时，将文法开始符号压入空栈.(2)如果栈为空，则分析完成.(3)如果栈顶为一非终结符，先将其从栈中弹出.选择下一个相应于该非终结符的产生式，并将其右部符号从右至左地一一入栈.如果没有可选的产生式，则转出错处理.(4)如果栈顶为一终结符，那么这个符号必须与当前输入符号相同，将其弹出栈，读下一符号，转第(2)步；否则，回溯到第(3)步.5CollegeofComputerScience&Technology,BUPT例

5、2：利用下推自动机进行自顶向下的分析过程EEOE(E)vdO＋EEOEEOvEOEEE)(E)E)OEE)OvE)OE)＋E))d)v(v＋d)qε，z0＝E/β若E→β∈Pε，O/a,a/εa∊{(,),v,d,+,}ε，O/+6CollegeofComputerScience&Technology,BUPT定理的证明证明思路欲证，对任何wT,wL(G)wL(M).先证明如下结论,ifAw,then(q,w,A)├(q,,).归纳于Aw的步数n.基础n=1，Aw必为产生式，(q,w,A)├(q,w,w)├(q,,).归纳

6、设第一步使用产生式AX1X2…Xm，必有w=w1w2…wm，(q,w,A)├(q,w,X1X2…Xm)├(q,w2…wm,X2…Xm)├(q,w3…wm,X3…Xm)├…├(q,,).所以:ifSw,then(q,w,S)├(q,,).即,wL(G)wL(M).7CollegeofComputerScience&Technology,BUPT定理的证明先证明如下结论,if(q,w,A)├(q,,),thenAw.归纳于(q,w,A)├(q,,)的步数n.归纳n>1，设第一步使用产生式AX1X2…Xm，可以将w分为w=w1w2…wm，

7、满足(q,wi,Xi)├(q,,)，所以:对任何wT,if(q,w,S)├(q,,),thenSw.即,wL(M)wL(G).因此，AX1X2…Xm，w1w2…wm=w无论Xi为终结符，还是非终结符，都有Xiwi.基础n=1，必有w=，且A为G的产生式，所以Aw.8CollegeofComputerScience&Technology,BUPT例：构造一个PDAM，使Lφ(M)=L(G)。其中G是我们常用来生成算术表达式的文法：G＝（N，T，P，E）N＝{E,T,F},T={+,,(,),a},S={E}P:E