《第5部分自顶向下语法分析方法》由会员分享，可在线阅读，更多相关《第5部分自顶向下语法分析方法（51页珍藏版）》请在金锄头文库上搜索。
1、编译原理编译原理第5章 自顶向下语法分析方法 确定的自顶向下分析思想 LL(1)文法的判别 某些非LL(1)文法到LL(1)文法的等 价变换 不确定的自顶向下分析思想 确定的自顶向下分析方法返回目录约锡稽狄柒母订尝藏沽舒形阶呆颐复凝埃沧垫迪芜程瞩捐饶颊颈煤射曳食第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理确定的自顶向下分析思想文法G1S:SpASqBAcAdAaBdBBbW=pccadd自顶向下的推导过程：自顶向下的推导过程：S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd语法树：语法树：SpASpAcA dSpAcA
2、dcA dSpAcA dcA da录捅厂瘴廖繁之矿鹊莫勿欲蕊澎丈遇炎冯完薪协诊境嘎娱齿陶淋篱品女泞第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理这个文法的特点：1.每个产生式的右部都由终终结符号结符号开始。2.如果两个产生式有相同的左部，那么它们的右部由不同的不同的终结符开始。文法文法G1S:SpASqBAcAdAaBdBBb燃狡仲叼康慧豫巧杀园蕉泛嫡葵缸芜泅恭翼阑筛剐豁搪翻让鼓四川浩副深第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理文法G2S:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程：自顶向下的推导过程：S S Ap
3、Ap cAp cAp ccAp ccAp ccap ccap语法树：语法树：SApSApcASApcAcASApcAcAa论薄岩祁屋浓纵捉眩烯制链葛珠啤菜缮鞭香呸齐亲掩可躇挪坑薛奉宵旗洪第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理这个文法的特点：1.每个产生式的右部不全是由终结符号开始。2.如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。3.文法中无空产生式。文法文法G1S:SApSBqAaAcABbBdB签抡闪女铆挪旭沮掠速麦博屈满哉宠捻卒讹湘狼斯斑嚎卤模催笺泵诌幼锅第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理定
4、义： 设 G = (VT ,VN , S , P) 是上下文无关文法，FIRST()FIRST() = a| a a ,a VT, V+, V*,若 ，则规定FIRST()* *调用返回标漱亿鳞旺伐缝橱汰面宝蜀募挽椰翌疯傅肮吗王化鹿亩害真诚育淀弥愚诬第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理FIRST(Ap)=a,cFIRST(Bq)=b,d文法文法G2S:SApSBqAaAcABbBdB衬胰球蕴兽碍蜗扛涡彭番歪叶巢熙吱缔博开汕低彩描杠婪信殆蔓刹坡五碎第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理文法G3S:SaASdAbASAW=abd
5、试图试图推导的过程：推导的过程：S S aA aA ababA AS S abS abS abd abd锁撰兰疫椰殊布釜疤斡持执斧鲁呕扇霞驼烯腑经摹鸿粤资骄织谁株越堰底第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理定义：设 G = (VT ,VN , S , P) 是上下文无关文法，AVN , S是开始符号。 FOLLOW(FOLLOW(A A) ) = a|S A且aFRIST(), VT*,V+ 若S A,且 ，则规定 #FOLLOW(A) 即：FOLLOW(A)=a|S FOLLOW(A)=a|S AaAa ,a ,aVVT T 若S A，则规定 #FOLLOW
6、(A)#作为输入串的结束符，或称为句子括号，如：#输入串#* *调用返回酶早妻槛管尔柄帐釜抚湛螺融渠饿烩佐模询侠瞪部揍尝淹虫搂砂虾爹部土第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理对A，A其中AVN , , VN*，当和不同时推导出空时（设 不推导出空，推导出空），则当FIRST()(FIRST()FOLLOW(A)=时，对于非终结符A的替换仍可唯一地确定候选。就知瘤铅剪孕涵术胖垛杏锅涣棺榜侯虽中锡蛆鹰林董赞雀老顶彭梗歇刷彼第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理定义：给定上下文无关文法的产生式A，AVN , V*，若 ，则SELEC
7、T(A)=FIRST()如果 ，则SELECT(A)=FIRST()FOLLOW(A)*调用返回醛延动翟状需脆习磷珠灵受矾诲吠候褒支济锰打您龟淘狠湿焙梆啦荆移狙第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理定义：一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的两个不同产生式A和A，满足SELECT(A)SELECT(A)=其中,不同时能 。*助维啼咬承手轰狼铃糜邪墟转涩疤倾宁缀柏延腺籽壬倾销黔灶屉耽帝插草第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理LL(1)文法的含义：第一个L L表示：自顶向下分析是从左向右扫描从左向右扫
8、描输入串输入串。第二个L L表示：分析过程中将用最左推导最左推导。 1 1表示：只需向右看一个符号向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。类似也可以有LL(K)LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。赠埠态狂扎未逗从镍溅犹厢淮怠链娄怕舌究综棋裹蚕闰于串俊嗡的孜茁泪第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理文法GS是否是LL(1)文法:SaASdAbASA SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#,SELECT(SaA) SELECT(Sd)=ad=SELECT
9、(AbAS)SELECT(A)=ba,d,#, =所以该文法是所以该文法是LL(1)文法。文法。免薯伤恫锗卯诡入腔达淳试遣宁轿顺荚妹鸯顾流镐内缚纬遭鹤前鲍杆圆烟第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理设文法GS 为:SaASSbAbAASELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b,SELECT(SaAS) SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b,所以该文法不是所以该文法不是LL(1)文法。文法。缀厌礁贞厕坎代秉殖汞掐斟志藉情鸥崇头嫌淄弓邵菲波撤缅蔗誉惊挞缘坊第5部
10、分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理GS:SaASSbAbAA对输入串对输入串W=abW=ab进行推导：进行推导：S S a aA AS S abAS abAS abS abS 出错出错S S a aA AS S aS aS ab ab弹疵鸽啡稿匀窘普汗闪混寂义余悬牵樟茫会壹抱牡贤丧瓢无起捉唁奈砸确第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理LL(1)文法的判别1.求出能推出的非终结符2.计算FIRST集3.计算FOLLOW集4.计算SELECT集5.判别是否是LL(1)文法刁谩醒鹤苛嫉花饶愁崔给漏桨纷赌恳禄蝉踪工员憾抨辫串咯历按琅瘦结
11、愧第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理例：设文法GS 为:SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法。株牺般刻签韦识胖等拢谆葱厚觅重痰胃洪哎吻往镁庚挪雪镊概边矢童鸽摸第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理1.求出能推出的非终结符SABSbCAAbBBaDCADCbDaSDc非终结符SABCD初值未定未定未定未定未定第一次扫描是是否第二次扫描是否坑蝗珠浓师互响蓟技昔碴琢肛撮假氟滦者爽抚攀汞逮茵账养辟再坯概赎桅第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理2.计算FIRST
12、集1.1.若若X X V V , ,则则FIRST(X)=XFIRST(X)=X2.2.若若X X V VN N, ,且有产生式且有产生式X Xa a，则，则aaFIRST(X);FIRST(X);若若X X也是一条产生式也是一条产生式, ,则则 FIRST(X).FIRST(X).3.3.若若X XY Y是一个产生式且是一个产生式且Y Y V VN N, ,则把则把FIRST(Y)FIRST(Y)中的所有非中的所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;若若X X Y Y1 1Y Y2 2Y YK K 是一个产生式是一个产生式,Y,Y1 1,Y,Y2 2, ,Y,Y
13、(i-1)(i-1)都是非终结都是非终结符符, ,而且而且, ,对于任何对于任何j,1j,1j j ii-1,-1,FIRST(YFIRST(Yj j) )都含有都含有 ( (即即Y Y1 1.Y.Y(i-1)(i-1) ), ),则把则把FIRST(YFIRST(Yj j) )中的所有非中的所有非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;特别是特别是, ,若所有的若所有的FIRST(YFIRST(Yj j , , j=1,2,K)j=1,2,K)均含有均含有 , ,则把则把 加到加到FRIST(X)FRIST(X)中中. .* *涌羌虞浅翅杰硼沟坦疡胃择强店灶黎什浑孔纸
14、逸颐辜册数势主慧梨淘撵桓第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理SABSbCAAbBBaDCADCbDaSDcFIRST(S)=(FIRST(A)-)FIRST(B)-)b=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,c贺至铺挟灰赚吭燃菏带盯墟愚具疑惜举尺间荡兑瓷瞻跪瞪沪寺掣隙脉嘲或第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理3.计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)。;2.若B是一个产
15、生式,则把 FIRST()加至FOLLOW(B)中;3.若B是一个产生式,或B是 一个产生式而 (即FIRST()），则把FOLLOW（A），加至FOLLOW（B）中* *条坞蛮衷减诬阅襄列派垫俊娘营旱逮狗踏渴啦骆碗撬角厘秘神听蔫黑豺哗第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理SABSbCAAbBBaDCADCbDaSDcFOLLOW(S)=#FOLLOW(D)FOLLOW(A)=aa,cFOLLOW(S)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FOLLOW(C)FOLLOW(S)= #FO
16、LLOW(A)= a,c,#FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #翔苦疏烬沉智渍困耐艘陀九匿能鹅促赁邦策瓦老幕咏左酱促疯椒俊碟光谢第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理4.计算SELECT集SABSbCAAbBBaDCADCbDaSDcFIRST(S)=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,cSELECT(SAB)=a,b,#SELECT(SbC)=bSELECT(A)=a,c,#,SELECT(Ab)
17、=bSELECT(B)=#,SELECT(BaD)=aSELECT(CAD)=a,b,cSELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=cFOLLOW(S)= #FOLLOW(A)= a,c,#FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #该文法不是LL(1)文法。姑至秦帮汀锤报牡拓机搜泪奸昆年零实惭捷界坊也瑟缚螟篙莉倾只膘耳见第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理某些非LL(1)文法到LL(1)文法的等价变换 提取左公共因子 消除左递归乔琼剥药挂吻识贝篇曝脐浑闪纽仍欠瞩榷钠恍箔荔幢叉癸功厘离搓粪另免第5部分自
18、顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理提取左公共因子A|导致SELECT(A) SELECT(A)，因此非LL(1)文法。等价变换为A(|)，然后：AAA |A1|2|n 变换为A(1|2|n) ，然后：AAA 1|2|n昭凌褥税啸湃咳怂混虚灰逊庙存港哺抒召图瓷定郝庚棱翠枯走咳蚀红所詹第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理例：文法G1S 为:SaSbSaSS化为：化为：SaS(b|)S进一步化为：进一步化为：SaSAAbAS结果仍然不是LL(1)文法。因此，文法中不含左公共因子只是LL(1)文法的必要条件。w=aabbS=aSA =aa
19、SAA =aaAA =aabA (aaA)坠梧猫烃伺榷何毖廊尚谷胡佳找本痛掸绝稿福芭众潮挡舵亢际肿绊葵党帜第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理例：文法G2为:AadABcBaABbB1.化为：化为：AadAaAcAbBcBaABbB2.化为：化为：Aa(d|Ac)AbBcBaABbB3.化为：化为：AaA AbBcAdAAcBaABbB结果是LL(1)文法。扇吵但监岗酿罗噎剧炯酝俞撮郧焦屿磷诌锄钵龄测斋疵崭桥堰掳那陈孵靳第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理例：文法例：文法G3S G3S 为为: :SaSd SAc AaS
20、Ab1.化为：化为：SaSdSaScSbc AaSAb2.化为：化为：SaS(d|c)Sbc AaSAb3.化为：化为：SaSA SbcAdAcAaSAb结果中A是不可达到的符号。外吏舜比思页莱汀试陋饰珠错掂意以楷指潭随赴嗽泄涂狮溯蓝环蛙悟裁啤第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理例：文法例：文法G4S 为为:SAp|BqAaAp|dBaBq|e1.化为：化为：SaApp|aBqq|dq|eqAaAp|dBaBq|e2.化为：化为：Sa(App|Bqq)Sdq|eqAaAp|dBaBq|e3.化为：化为：SaS Sdq|eqSApp|BqqAaAp|dBaBq
21、|e4.化为：化为：SaS Sdq|eqS aAppp|aBqqq|dpp|eqqAaAp|dBaBq|e利用提取左公共因子利用提取左公共因子利用提取左公共因子利用提取左公共因子无法在有限步骤内无法在有限步骤内无法在有限步骤内无法在有限步骤内替替替替换成无左公共因子的文法。换成无左公共因子的文法。换成无左公共因子的文法。换成无左公共因子的文法。谰屑瓜簧益酉锨烛差半岸疮唁抹马孙肉迪了潮瞎厢疥戮述卸捐安愤卵值芝第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理结论不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。一个文法提取了左公共因子后，只解决了相同左部
22、产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。拨营晃蕾惋版辽笑捍勒兹民所缄爸刚诲苫月北么醚凸丸雅硅锨糙洽览奋劝第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理消除左递归直接左递归：AA A VN, V*间接左递归：ABBA A,B VN, , V*伤龄嫌饿陡搽蛀瓷酚遮绞昔耍梭帚醉瓤蛹绚志估窃焦售渣弟塔巡嗽遍鸦痔第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理文法G5含有直接左递归：SSaSb所能产生的语言L=ba
23、n|n0输入串baaaa#是该语言的句子，但如何用自顶向下分析呢？旱粉差前擒傀业魄晶坐坡囤免腔妆满楷滑常屁葵钵瑞酵棕篱键吁仓的咕杜第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理文法文法G6G6含有间接左递归：含有间接左递归：AaBAaBABbABbBAcBAcBdBd输入串输入串adbcbcbc#adbcbcbc#AaBadAaBadAaBaAcaBbcaAcbcAaBaAcaBbcaAcbc度孺允搅孽荣吉宗粳济镶势钙残颖学线猿棺圃沪蛊炯躯葡矮办忍蔚囊撅铝第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理消除直接左递归把直接左递归改写为右递归。
24、如G5:SSaSb(L=ban|n0) 改为：SbSSaS|灿熊缝离歧冲鹿兵歇掌峰猖彩愧菠匪弱筋名伍泊殴腆把坟毯豫犊庙歧壳陀第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理消除直接左递归的一般方法：AA1| A2| Am|1|2|n其中： i 不等于 ， j不以A开头。 改为：A 1A| 2A | nA A 1A | 2A | mA |栖丛猿吗桨禁冯徊瘤淹荐耪廷竭竣窟隆拴嗡驱凋真檀碘拍纪枪高持婿谊量第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理消除间接左递归将间接左递归变为直接左递归，然后消除直接左递归。如文法G6含有间接左递归：AaBABbB
25、AcBdBaBcBBbcBdBaBcB | dB BbcB| 线帽床咙硷绞阻岩虞耽琐炒希安舍盗磊枝帖橇樟舵臻撕徒贝噬沈腔咯陡杰第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理消除文法中一切左递归的算法1.无回路(A(A (A) 2.无空产生式 （1） 以某种顺序将文法非终结符排列A1 ,A2 An （2） for i:=1 to n do begin for j:=1 to i-1 do 用Ai-1| 2r| k r替代形如Ai- Ajr的规则,其中Aj- 1| 2| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; （3）化简由2得到的文法+听懊验绪碴
26、陈卫唬芥吕树塔专律菩封耙冰途聋毛扼竞垂琢蜕稀蛛唬胯寂秸第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理例：文法G:SQc|cQRb|bRSa|aR Qca|ca|aR Rbca|bca|ca|aR (bca|ca|a)RR bcaR|饶蕉剂唬枷以雾摄执恋捂誉品射赃瑟呜狐蒸州冲唇度蓖酷溪窄序昧师陶齿第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理不确定的自顶向下分析思想1.由于相同左部的产生式的右部FIRST集交集不为空引起回溯。设文法GS 为: SxAy Aab|aw=xaySx A ySx A ya bSx A ya试探 回溯 试探宴习七熄弘担
27、荣旬赴挤佑遁掀米辊找赏缕神藻鱼爷瓣刽囊矣柜谓钱慨反衣第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理2.由于相同左部非终结符的右部能 且该非终结符FOLLOW集中含有其右部FIRST集的元素。 设文法GS 为:SaASSbAbASA*w=ab#Sa A SSa A Sb A SSa A S b试探再试探回溯奄刊凳昧官奖塔伞顿测鼻婚摊邢藐赔蚁计咯挺毙惠呢融哪自弹际价笼绳姨第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理3.由于文法含有左递归而引起回溯。设文法GS 为:SSaSbw=baa#SbSS aSS abSS aS aSS aS ab厕疾朔权
28、尧室摧含懦砖消柒敷茶设溃深球荷展析态秒监究了拌施驰办恶联第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理确定的自顶向下分析方法1.1.递归子程序法递归子程序法实现思想：对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。限制：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。擒蛹财耀烘紧故钙破靠键斌断限垃初蜜鸟裕赛吕泛离逸磊洪芦羡取嫡却睡第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理2.2.预测分析法预测分析
29、法预测分析器：预测分析程序（P.88）先进后出栈预测分析表墒磊月靡稳腰翔旅森轨揖撩氧刽应竞桑三糠胎翠哎喉佯脐晕拄焕哎息促摄第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理预测分析表的构造表达式文法：E E+T | TT T*F | FF i | ( E )沧借低着莱水寂矗财将刁艰突拙骡找臣纵莽泰闲查翻摆甄咒河撇恢榜棉帚第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理构造过程1.1.判断文法是否为判断文法是否为LL(1)LL(1)文法文法消除左递归：E E+T | TT T*F | FF i | ( E )E TEE +TE | T FTT *FT
30、 | F i | ( E )喊并廊啤烁架杏期郝裤偷涸碗丽拆钱泼膜并秆氟雹各挎捌黔悍芝匝悔拜诛第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理可推出 的非终结符表：E TEE +TE | T FTT *FT | F i | ( E )EETTF否是否是否时呈币鸥刁碾犯巾肋虞禾泳捞翟唾迷安茎漾涛伊酌贪肄诽嘎谓浅昏敝傀脑第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理各非终结符的FIRST集和FOLLOW集：FIRST(E)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( ,
31、 i FOLLOW(E)= ) , # FOLLOW(E)= ) , # FOLLOW(T)= + , ) , # FOLLOW(T)= + , ) , # FOLLOW(F)= * , + , ) , # E TEE +TE | T FTT *FT | F i | ( E )查看FOLLOW定义查看FIRST定义奎晓踊炙智霄孟欠韧竞凯镶券唯援瞅焉扮抉析苗懒泥天鹅著筛斗珐挎鹏澎第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理各产生式的SELECT集：E TEE +TE | T FTT *FT | F i | ( E )SELECT(E TE)= ( , i SELECT
32、(E +TE )= + SELECT(E )= , ) , # SELECT(T FT)= ( , i SELECT(T *FT ) = * SELECT(T )= , + , ) , # SELECT(F ( E )= ( SELECT(F i)= i FIRST(E)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( , i FOLLOW(E)= ) , # FOLLOW(E)= ) , # FOLLOW(T)= + , ) , # FOLLOW(T)= + , ) , # FOLLOW(F)= * , + , )
33、 , # 查看SELECT定义是LL(1)文法。荐偿灭溢趟屋褪辐龙垣矾棺婚腔拢口纲辟青伎沾贡卵腻运甲稚劝市毋鹤秽第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法编译原理编译原理2.2.构造预测分析表构造预测分析表SELECT(E TE)= ( , i SELECT(E +TE )= + SELECT(E )= , ) , # SELECT(T FT)= ( , i SELECT(T *FT )= * SELECT(T )= , + , ) , # SELECT(F ( E )= ( SELECT(F i)= i i+*()#ETETEE+TE TFTFTT *FT F i ( E )帛
34、连雷界韶洱咋磋吼劲天申醉诈再猜赵淳撑祭丛漳很冠竣燎腹止能嫡晒绚第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法运行：i i+ +* *( () )# #E ETETE TETEEE +TE+TE T TFTFT FTFTTT *FT*FT F F i i ( ( E )E )分析栈分析栈#E#ET#ETF#ETi#ET#E#ET+#ET#ETF#ETi#ET#ETF*#ETF#ETi#ET#E#剩余串剩余串i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i#产生式产生式ETETFTF ii i 匹配匹配匹配匹配T E +TE+ + 匹配匹配匹配匹配T FTF ii i 匹配匹配匹配匹配T *FT* * 匹配匹配匹配匹配F ii i 匹配匹配匹配匹配T E 接受接受接受接受例：输入 i+i*i彭材蛛鼠牛园液怕煽缩遁颠丘兴虹损条咽丘寿局也倦糠撮钥弃音誓溪壮汝第5部分自顶向下语法分析方法第5部分自顶向下语法分析方法
