【教学课件】第5章自顶向下语法分析方法.ppt
《【教学课件】第5章自顶向下语法分析方法.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第5章自顶向下语法分析方法.ppt(51页珍藏版)》请在三一办公上搜索。
1、第5章 自顶向下语法分析方法,确定的自顶向下分析思想 LL(1)文法的判别 某些非LL(1)文法到LL(1)文法的等 价变换 不确定的自顶向下分析思想 确定的自顶向下分析方法,返回目录,确定的自顶向下分析思想,文法G1S:SpASqBAcAdAaBdBBb,W=pccadd自顶向下的推导过程:S pA pcAd pccAdd pccadd,语法树:,S,p,A,S,p,A,c,A,d,S,p,A,c,A,d,c,A,d,S,p,A,c,A,d,c,A,d,a,这个文法的特点:每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。,文法G1S:SpASq
2、BAcAdAaBdBBb,文法G2S:SApSBqAaAcABbBdB,W=ccap自顶向下的推导过程:S Ap cAp ccAp ccap,语法树:,S,A,p,S,A,p,c,A,S,A,p,c,A,c,A,S,A,p,c,A,c,A,a,这个文法的特点:每个产生式的右部不全是由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。,文法G1S:SApSBqAaAcABbBdB,定义:设 G=(VT,VN,S,P)是上下文无关文法,FIRST()=a|a,a VT,V+,V*,若,则规定FIRST(),*,*,调用返回,FIRST(Ap)=
3、a,cFIRST(Bq)=b,d,文法G2S:SApSBqAaAcABbBdB,文法G3S:SaASdAbASA,W=abd试图推导的过程:S aA abAS abS abd,定义:设 G=(VT,VN,S,P)是上下文无关文法,AVN,S是开始符号。FOLLOW(A)=a|S A且aFRIST(),VT*,V+若S A,且,则规定#FOLLOW(A)即:FOLLOW(A)=a|S Aa,aVT若S A,则规定#FOLLOW(A)#作为输入串的结束符,或称为句子括号,如:#输入串#,*,*,*,*,*,调用返回,对A,A其中AVN,VN*,当和不同时推导出空时(设 不推导出空,推导出空),则当
4、FIRST()(FIRST()FOLLOW(A)=时,对于非终结符A的替换仍可唯一地确定候选。,定义:给定上下文无关文法的产生式A,AVN,V*,若,则SELECT(A)=FIRST()如果,则SELECT(A)=FIRST()FOLLOW(A),*,调用返回,定义:一个上下文无关文法是LL(1)文法的充要条件是:对每个非终结符A的两个不同产生式A和A,满足SELECT(A)SELECT(A)=其中,不同时能。,*,LL(1)文法的含义:,第一个L表示:自顶向下分析是从左向右扫描输入串。第二个L表示:分析过程中将用最左推导。1表示:只需向右看一个符号便可决定如何推导(即选择哪个产生式进行推导)
5、。类似也可以有LL(K)文法:需向前查看K个符号才可确定选用哪个产生式。,文法GS是否是LL(1)文法:SaASdAbASA,SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#,SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#,=,所以该文法是LL(1)文法。,设文法GS 为:SaASSbAbAA,SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b,SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SE
6、LECT(A)=ba,b,所以该文法不是LL(1)文法。,GS:SaASSbAbAA,对输入串W=ab进行推导:S aAS abAS abS 出错S aAS aS ab,LL(1)文法的判别,求出能推出的非终结符计算FIRST集计算FOLLOW集计算SELECT集判别是否是LL(1)文法,例:设文法GS 为:SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法。,1.求出能推出的非终结符,SABSbCAAbBBaDCADCbDaSDc,2.计算FIRST集,1.若XV,则FIRST(X)=X2.若XVN,且有产生式Xa,则aFIRST(X);若X也是一条产生式,则FIRST
7、(X).3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且,对于任何j,1j i-1,FIRST(Yj)都含有(即Y1.Y(i-1),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,K)均含有,则把加到FRIST(X)中.,*,SABSbCAAbBBaDCADCbDaSDc,FIRST(S)=(FIRST(A)-)FIRST(B)-)b=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cF
8、IRST(D)=a,c,FIRST(AB)=a,b,FIRST(AD)=a,b,c,3.计算FOLLOW集,1.对于文法的开始符号S,置#于FOLLOW(S)。;2.若B是一个产生式,则把 FIRST()加至FOLLOW(B)中;3.若B是一个产生式,或B是 一个产生式而(即FIRST()),则把FOLLOW(A),加至FOLLOW(B)中,*,SABSbCAAbBBaDCADCbDaSDc,FOLLOW(S)=#FOLLOW(D)FOLLOW(A)=aa,cFOLLOW(S)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FO
9、LLOW(C),FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,4.计算SELECT集,SABSbCAAbBBaDCADCbDaSDc,FIRST(S)=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,c,SELECT(SAB)=a,b,#SELECT(SbC)=bSELECT(A)=a,c,#,SELECT(Ab)=bSELECT(B)=#,SELECT(BaD)=aSELECT(CAD)=a,b,cSELEC
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 向下 语法分析 方法
链接地址:https://www.31ppt.com/p-5659041.html