![编译原理 之 自顶向下语法分析方法.ppt_第1页](http://file1.renrendoc.com/fileroot2/2020-1/22/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c1.gif)
![编译原理 之 自顶向下语法分析方法.ppt_第2页](http://file1.renrendoc.com/fileroot2/2020-1/22/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c2.gif)
![编译原理 之 自顶向下语法分析方法.ppt_第3页](http://file1.renrendoc.com/fileroot2/2020-1/22/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c3.gif)
![编译原理 之 自顶向下语法分析方法.ppt_第4页](http://file1.renrendoc.com/fileroot2/2020-1/22/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c4.gif)
![编译原理 之 自顶向下语法分析方法.ppt_第5页](http://file1.renrendoc.com/fileroot2/2020-1/22/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c/7c4c0ef9-eea3-49ea-bd5b-2c473ecb8a6c5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第五章自顶向下语法分析方法,本章要点LL(1)分析First集合和Follow集合使用递归下降分析算法进行自顶向下的分析预测分析程序非LL(1)文法的改造,自上而下分析算法,自顶向下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子,若输入串是给定的句子,则必能推出,反之必然出错。自顶向下分析法又分为确定的和不确定的两种。,5.1确定的自顶向下分析思想,确定的自顶向下分析方法,首先要解决从文法的开始符号出发,如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导,或构造一棵相应的语法树。,例5.1,若有文法G1S:SpA|
2、qBAcAd|aBdB|b若输入串W=pccadd。自顶向下推导过程为S=pA=pcAd=pccAdd=pccadd,这个文法有以下两个特点:,每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。,例5.2,若有文法G2S为:SApSBqAaAcABbBdb,当输入串W=ccap,那么试图推出输入串的推导过程为:S=Ap=cAp=ccAp=ccap,例5.2文法的特点是:,产生式的右部不全是由终结符开始如果两个产生式有相同的左部,它们的右部是由不同的终结符或非终结符开始。文法中无空产生式,定义5.1,设G=(VT,VN,P,S)是上下文无关文法FIR
3、ST()=a|a,aVT,V*若则规定FRIST()不难求出在文法G2中FIRST(Ap)=a,cFIRST(Bq)=b,d,例5.3,若有文法GS:SaASdAbASA若输入串W=abd,则试图推导出abd串的推导过程为:S=aA=abAS=abS=abd,从例5.3可以得出下列结论,当某一非终结符的产生式中含有空产生式时,它的非空产生式右部的首符号集两两不相交,并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交,则仍可构造确定的自顶向下分析。,定义5.2,设G=(VT,VN,P,S)是上下文无关文法,AVN,S是文法开始符号FOLLOW(A)=aSA且aVTaFRIST(),V*
4、,V+若SA,且,则#FOLLOW(A),定义5.3,给定上下文无关文法的产生式A,AVN,V*,若*,则SELECT(A)=FIRST()如果,则SELECT(A)=(FIRST()-)FOLLOW(A),定义5.4,一个上下文无关文法是LL(1)文法的充分必要条件是,对每个非终结符A的两个不同产生式,A,A,满足SELECT(A)SELECT(A)=其中、不能同时。,LL(1)文法的含义:,第1个“L”指的是由左向右地处理输入。第2个“L”指的是它为输入串描绘出一个最左推导。括号中的数字1意味着它只需向右看一个符号便可决定如何推导即选择哪个产生式(规则)进行推导。,例5.3的文法,SaAS
5、dAbASA,不难看出:SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#所以SELECT(SaA)SELECT(Sd)=SELECT(AbAS)SELECT(A)=,例5.4,设文法GS为:SaASSbAbAA,则SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,bSELECT(SaAS)SELECT(Sb)=SELECT(AbA)SELECT(A),5.2LL(1)文法的判别,1求出推出的非终结符2计算FIRST集3计算FOLLOW集4计算SELECT集,1求出推出的非终结符,扫描
6、文法中的产生式删除所有右部含有终结符的产生式,若这使得以某个非终结符为左部的所有产生式都被删除,说明该非终结符不能推出.若某个非终结符的某个产生式的右部为,说明该非终结符能推出.删除以该非终结符为左部的所有产生式.扫描产生式右部的每一个符号若扫描到的非终结符能推出,则删除该非终结符,如这样使产生式右部为空,说明该非终结符能推出.删除以该非终结符为左部的所有产生式.若扫描到的非终结符不能推出,则删除该产生式,如这样使以该非终结符为左部的所有产生式都被删除,说明该非终结符不能推出.重复,直到扫描完文法的产生式,数组中非终结符的特征在没有改变为止.,例5.5若文法GS为:,SABSbCAAbBBaD
7、CADCbDaSDc,SABABCAD,SABCAD,CAD,Step1,Step2,Step3,定义法:求文法符号FIRST(X),若XV,则FIRST(X)=X;若XVN,且有产生式Xa,则把a加入到FIRST(X)中;若XVN,X也是一条产生式,则把也加到FIRST(X)中;若XVN,XY1Y2Yn是一个产生式,Y1,Y2,Yi-1(1in)都是非终结符,而且对于任何j,1ji-1,FIRST(Yj)都含有(即Y1,.,Yi-1),则把FIRST(Yj)(1ji-1)中的所有非元素以及FIRST(Yi),都加到FIRST(X)中;在(d)中,若所有的FIRST(Yj,j=1,2,n)均能
8、推出,则FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)。反复使用上述(b)-(e)步骤,直到每个符号的FIRST集合不再增大为止。,求符号串的FIRST(),=Y1Y2Yn当Y1*时,FIRST()=FIRST(Y1).对于任何j,1ji-1,2in,FIRST(Yj)都含有(即Y1,.,Yi-1),则:FIRST()=(FIRST(Y1)-)(FIRST(Yi-1)-)FIRST(Yi).当所有Yi(1in),则FIRST()=FIRST(Y1)FIRST(Yn).,例5.5若文法GS为:,SABSbCAAbBBaDCADCbDaSDc,文法GS的每个非终结符的FI
9、RST集:FIRST(S)=FIRST(A)FIRST(B)=a,b,FIRST(A)=b,FIRST(B)=a,FIRST(C)=(FIRST(A)-)FIRST(D)bFIRST(D)=a,cFIRST(C)=a,b,c,例5.5若文法GS为:,SABSbCAAbBBaDCADCbDaSDc,文法GS的每个产生式右部符号串的FIRST集:FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=(FIRST(A)-)FIRST(D)=a,b,cFIRST(aS)=aFIRST(c)=c,
10、关系图法:求文法符号FIRST(X),文法符号X对应图中一个结点,若XV,用X表示;若XVN,用FIRST(X)表示。若X是文法的一个产生式,且,则FIRST(A)FIRST(X),XVN;或FIRST(A)X,XVT.凡是从FIRST(A)结点有路径可到达的终结符结点的终结符都属于FIRST(A).A,则FIRST(A)=FIRST(A),例5.5若文法GS为:(关系图法),SABSbCAAbBBaDCADCbDaSDc,FIRST(S),FIRST(A),FIRST(B),b,a,FIRST(C),FIRST(D),c,FIRST集:FIRST(S)=a,b,FIRST(A)=b,FIRS
11、T(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c,3计算FOLLOW集,(1)定义法:对于文法的开始符号S,置#于FOLLOW(S)中;若B是一个产生式,则把FIRST()-加至FOLLOW(B)中;如,则把FOLLOW(A)加至FOLLOW(B)中;这是因为当有形如:D1A1,B的产生式,A,B,DVN,1,1,V*,在推导过程中可能出现如下的句型序列:S1A1=1B1=1B1有:FOLLOW(A)FOLLOW(B)反复使用(b)步骤,直到每个非终结符号的FOLLOW集合不再增大为止。,例5.5若文法GS为:,SABSbCAAbBBaDCADCbDaSDc,文法GS的每个非
12、终结符的FOLLOW集:FOLLOW(S)=#FOLLOW(D)FOLLOW(A)=FIRST(B)-FOLLOW(S)FIRST(D)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FOLLOW(C)FOLLOW(S)=#;FOLLOW(A)=a,#,cFOLLOW(B)=#;FOLLOW(C)=#FOLLOW(D)=#,(2)关系图法:S是开始符号,FOLLOW(X)#.若BX是文法的一个产生式,且,则FOLLOW(B)FIRST(X),XVN;或FOLLOW(B)X,XVT.若B是文法的一个产生式,且,则FOLLOW(B)
13、FOLLOW(A).对图中每个FIRST(A)结点,若X是文法的一个产生式,且,则FIRST(A)FIRST(X),XVN;或FIRST(A)X,XVT.凡从FOLLOW(A)结点有路径可到达的终结符或#的结点,其标记的终结符或#都属于FOLLOW(A).,例5.5若文法GS为:(关系图法),SABSbCAAbBBaDCADCbDaSDc,FOLLOW(A),FIRST(B),FOLLOW(S),a,c,FOLLOW集:FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,FOLLOW(B),FOLLOW(C),FOLLOW(D
14、),FIRST(D),#,4计算SELECT集,给定上下文无关文法的产生式A,AVN,V*,若*,则SELECT(A)=FIRST()如果,则SELECT(A)=(FIRST()-)FOLLOW(A),FOLLOW集:FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,文法GS的每个产生式右部符号串的FIRST集:FIRST(AB)=FIRST(A)FIRST(B)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(AD)=(FIRST(A)-)FIRST(D)=a,b,cFI
15、RST(aS)=aFIRST(c)=c,文法GSSABSbCAAbBBaDCADCbDaSDc,文法GS的SELECT集:SELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=a,b,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=(FIRST()-)FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=(FIRST()-)FOLLOW(B)=#SELECT(BaD)=FIRST(aD)=aSELECT(CAD)=FIRST(AD)=a,b,cSELECT(Cb)=FIRST(b)=bSELECT(DaS)=FIRST(a
16、S)=aSELECT(Dc)=FIRST(c)=c,相同左部产生式的SELECT集的交集为:SELECT(SAB)SELECT(SbC)=bSELECT(A)SELECT(Ab)=SELECT(B)SELECT(BaD)=#a=SELECT(CAD)SELECT(Cb)=a,b,cbSELECT(DaS)SELECT(Dc)=ac=关于S和C的相同左部,其产生式的SELECT集的交集不为空,该文法不是LL(1)文法.,5.3某些非LL(1)文法到LL(1)文法的等价变换,提左公因子A|A(|)消除左递归,例5.6若文法G1的产生式为:,SaSbSaSS,对产生式(1)、(2)提取左公共因子后得
17、SaS(b|)S,进一步变换后为文法G1:SaSAAbAS,例5.7若文法G2的产生式为:,AadABcBaABbB,对右部以非终结符开始的产生式,用其相同左部而右部以终结符开始的产生式进行相应替换,(1)Aad(2)AaAc(3)AbBc(4)BaA(5)BbB,提取产生式(1)、(2)的左公共因子得:,Aa(d|Ac)AbBcBaABbB,引进新非终结符A后得G2:,AaAAbBcAdAAcBaABbB不难验证:G1仍不是LL(1)文法,而G2不是LL(1)文法.因此不含左公因子只是LL(1)文法的必要条件,不是充分条件.,文法G5含有直接左递归SSaSb为了消除左递归,将这个文法规则重写
18、为两个规则:SbSSaS|这两个文法表示的语言:ban|n0,不难验证改写后的文法为LL(1)文法.,情况1:简单直接左递归,情况2:普遍的直接左递归,这种情况发生在有如下格式的产生式AAa1|Aa2|.|Aam|b1|b2|.|bn中。其中a1,.,am不等于,b1,.,bn均不以A开头。在这种情况下,其解法与简单情况类似,只需将选择相应地扩展:Ab1A|b2A|.|bnAAa1A|a2A|.|amA|,情况3:消除间接左递归,先将间接左递归变为直接左递归,然后再消除直接左递归。,例消除下列文法中的左递归,AaBABbBAcBd,用产生式(1)、(2)的右部代替产生式(3)的右部得到:BaB
19、cBBbcBd,消除左递归后得:B(aBc|d)BBbcB|,将原来的产生式AaB,ABb加入,最终文法为:(1)AaB(2)ABb(3)B(aBc|d)B(4)BbcB|,需要验证改写后的文法是否为LL(1)文法?,5.5确定的自顶向下分析方法,特征根据下一个输入符号为当前要处理的非终结符选择产生式要求文法是LL(1)的预测分析程序的实现技术1预测分析法2递归子程序法,预测分析方法,一个预测分析器是由三个部分组成:预测分析程序先进后出栈预测分析表其中预测分析表可用一个矩阵M表示。矩阵的元素MA,a中的内容为一条关于A的产生式,表明当用非终结符A向下推导面临输入符a时,所应采取的候选产生式,当
20、元素内容无产生式时,则出错。,预测分析程序的框图,构造预测分析表,对每个终结符或“#”号用a表示。若aSELECT(A),则把A放入MA,a中。把所有无定义的MA,a标上出错标记。,以表达式文法为例构造预测分析表:,GE:ETEE+TEETFTT*FTTF(E)Fi,GE:EE+T|TTT*F|FT*FTFi|(E),(1)判断文法是否LL(1)?,消除左递归,GE:ETEE+TEETFTT*FTTF(E)Fi,FIRST(E),Step1.判断是否LL(1)文法,可推出的非终结符表,非终结符FIRST集,FIRST(T),FIRST(E),+,FIRST(F),FIRST(T),*,(,i,
21、FIRST(E)=(,i,FIRST(T)=(,i,FIRST(F)=(,i,FIRST(E)=+,FIRST(T)=*,.,GE:ETEE+TEETFTT*FTTF(E)Fi,非终结符FOLLOW集,FOLLOW(E),#,FOLLOW(T),FIRST(E),FOLOW(E),FOLLOW(F),FIRST(T),FOLLOW(T),),+,*,FOLLOW(E)=),#,FOLOW(E)=),#,FOLOW(T)=),#,+,FOLOW(T)=),#,+,FOLOW(F)=),#,+,*.,GE:ETEE+TEETFTT*FTTF(E)Fi,各产生式的SELECT集,SELECT(ETE
22、)=(,iSELECT(E+TE)=+SELECT(E)=),#SELECT(TFT)=(,iSELECT(T*FT)=*SELECT(T)=),#,+SELECT(F(E)=(SELECT(Fi)=i,相同左部其产生式的SELECT集的交集为空,所以该文法是LL(1)文法.,Step1.构造预测分析表对每个非终结符或#用a表示,若aSELECT(Aa),则把Aa放入MA,a中,把所有无定义的MA,a标记出错.,表达式文法GE的预测分析表,对输入串i+i#的分析过程,递归子程序法,它的实现思想是对应文法中的每个非终结符编写一个递归过程,每个递归过程的功能是识别由该终结符推出的串,当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。,例如,考虑表达式文法:,expexpaddopterm|termaddop+|-termtermmulopfactor
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 纳税申报实训-第四版 课件 王红 第4、5章 所得税纳税申报模拟实训、其他小税种的纳税申报模拟实训
- 第 四 章 波 形 发 生 电 路
- 2024至2030年中国阻燃一次性工作服市场前景动态及发展潜力评估报告
- 2024-2030年全球与中国4,4二氟环己甲酸行业市场现状调研分析及发展前景报告
- 2024-2030年中国静电膜市场专题研究及市场前景预测评估报告
- 2024-2030年中国藤条散香器市场专题研究及市场前景预测评估报告
- 2024-2030年中国空气流量传感器市场专题研究及市场前景预测评估报告
- 2024至2030年中国水磨石板材行业市场调查分析与投资发展商机研究报告
- 2024至2030年中国市政绿化维护市场前景展望及未来运营策略分析报告
- 2024-2030年中国工业气体减压调节器市场专题研究及市场前景预测评估报告
- 谁打电话的时间长(同步练习)-五年级上册数学 北师大版(含答案)
- 年产10000吨铸造件加工生产线建设项目环评报告表
- 大班歌曲《快乐的一天开始了》课件PPT
- 基础会计-完整全套教学课件
- 外墙吊绳安全施工方案范本
- 评价中层干部优缺点范文(通用7篇)
- 计算机辅助设计(AutoCAD 2020)思政课件全套 第1-3篇 学好AutoCAD软件 实现职业梦想、AutoCAD技术在国家建设中的应用与成果展示、AutoCAD辅助绘图经验谈
- 【课件】Welcome+Unit+Discovering+Useful+Structures+课件人教版(2019)必修第一册
- 倒排工期施工计划
- 美术鉴赏-拉斐尔
- 高一上学期数学教学进度安排表
评论
0/150
提交评论