自上而下語(yǔ)法分析PPT課件

1、自上而下語(yǔ)法分析編譯技術(shù)之四主講 魯 斌2v高級(jí)語(yǔ)言的語(yǔ)法結(jié)構(gòu)適合用上下無(wú)關(guān)文法描述，因高級(jí)語(yǔ)言的語(yǔ)法結(jié)構(gòu)適合用上下無(wú)關(guān)文法描述，因此，我們將上下文無(wú)關(guān)文法作為語(yǔ)法分析的基礎(chǔ)此，我們將上下文無(wú)關(guān)文法作為語(yǔ)法分析的基礎(chǔ)v本章和下一章，我們將介紹編譯程序構(gòu)造中的一些本章和下一章，我們將介紹編譯程序構(gòu)造中的一些典型的語(yǔ)法分析方法典型的語(yǔ)法分析方法34.1 概述概述v語(yǔ)法分析是編譯過(guò)程的核心部分。它的任務(wù)是在詞法分析識(shí)語(yǔ)法分析是編譯過(guò)程的核心部分。它的任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語(yǔ)法結(jié)構(gòu)是否別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則符合語(yǔ)法規(guī)則v下圖

2、表明了語(yǔ)法分析器在編譯程序中的地位下圖表明了語(yǔ)法分析器在編譯程序中的地位v按照語(yǔ)法分析樹(shù)的建立方法，我們可以粗略地把語(yǔ)法分析方按照語(yǔ)法分析樹(shù)的建立方法，我們可以粗略地把語(yǔ)法分析方法分為兩類(lèi)：一類(lèi)是法分為兩類(lèi)：一類(lèi)是自上而下分析法自上而下分析法，另一類(lèi)為，另一類(lèi)為自下而上分自下而上分析法析法源程序源程序詞法分析器詞法分析器單詞符號(hào)單詞符號(hào)取下一取下一單詞符號(hào)單詞符號(hào)語(yǔ)法分析器語(yǔ)法分析器語(yǔ)法語(yǔ)法分析樹(shù)分析樹(shù)后續(xù)部分后續(xù)部分符符 號(hào)號(hào) 表表4例：自頂向下構(gòu)造最左推導(dǎo)（aabbaa) SaASa A SbA SS baASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS

3、S54.2 4.2 自上而下分析面臨的問(wèn)題自上而下分析面臨的問(wèn)題v自上而下分析的一般方法：對(duì)任何輸入串，用一切自上而下分析的一般方法：對(duì)任何輸入串，用一切可能的方法從文法開(kāi)始符號(hào)（根結(jié)）出發(fā)，自上而可能的方法從文法開(kāi)始符號(hào)（根結(jié)）出發(fā)，自上而下地為輸入串建立一棵語(yǔ)法樹(shù)，或?qū)ふ乙粋€(gè)最左推下地為輸入串建立一棵語(yǔ)法樹(shù)，或?qū)ふ乙粋€(gè)最左推導(dǎo)導(dǎo)v這種分析過(guò)程本質(zhì)上是一種試探過(guò)程，是反復(fù)使用這種分析過(guò)程本質(zhì)上是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程不同產(chǎn)生式謀求匹配輸入串的過(guò)程6v例例4.1：假定有文法：假定有文法SxAyAab|a分析輸入串分析輸入串xay（記為（記為w）。）。SxAySx

4、AyaabSxAy(a)(b)(c)7v例例4.2：假定有文法：假定有文法SSaSb分析輸入串分析輸入串baaa。8v由上例看到，自上而下分析法存在許多困難和缺點(diǎn)由上例看到，自上而下分析法存在許多困難和缺點(diǎn)n文法的左遞歸性文法的左遞歸性PP使分析陷入無(wú)限循環(huán)使分析陷入無(wú)限循環(huán)n回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來(lái)回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來(lái)n虛假匹配問(wèn)題虛假匹配問(wèn)題n難于知道出錯(cuò)位置難于知道出錯(cuò)位置n效率低，代價(jià)高，實(shí)踐價(jià)值不大效率低，代價(jià)高，實(shí)踐價(jià)值不大v因此，為解決這些問(wèn)題我們要消除左遞歸和回溯因此，為解決這些問(wèn)題我們要消除左遞歸和回溯+94.3 LL(1) 分

5、析法分析法4.3.1 左遞歸的消除左遞歸的消除4.3.2 消除回溯、提左因子消除回溯、提左因子4.3.3 LL(1)文法文法104.3.1 左遞歸的消除左遞歸的消除v一般而言，假定關(guān)于一般而言，假定關(guān)于A的全部產(chǎn)生式是的全部產(chǎn)生式是AA 1| A 2| A m| 1| 2 | | n 其中，每個(gè)其中，每個(gè) 都不等于都不等于 ，而每個(gè)，而每個(gè) 都不以都不以A開(kāi)頭，開(kāi)頭，那么，消除那么，消除A的直接左遞歸性就是把這些規(guī)則改寫(xiě)的直接左遞歸性就是把這些規(guī)則改寫(xiě)成：成： A 1 A| 2 A| n A A1A| 2A| | mA| 11v例例4.3：文法文法EE+T|TTT*F|FF(E)|i消去直接左

6、遞歸：消去直接左遞歸：ETEE+TE|TFT （4.1）T*FT|F(E)|iv直接左遞歸和非直接左遞歸的消除方法均在必須掌握之列直接左遞歸和非直接左遞歸的消除方法均在必須掌握之列12v若一個(gè)文法不含回路（若一個(gè)文法不含回路（AA），也不含以），也不含以為右部為右部的產(chǎn)生式，則消除一切左遞歸的算法是：的產(chǎn)生式，則消除一切左遞歸的算法是：把文法把文法G的所有非終結(jié)符排序：的所有非終結(jié)符排序：A1, A2, , AnFOR i:=1 TO n DOBEGIN FOR j:=1 TO i-1 DO 把形如把形如AiAj的規(guī)則改寫(xiě)成的規(guī)則改寫(xiě)成 Ai1|2|k 其中其中Aj1|2|k是關(guān)于是關(guān)于Aj的

7、所有規(guī)則；的所有規(guī)則； 消除關(guān)于消除關(guān)于Ai規(guī)則的直接左遞歸性規(guī)則的直接左遞歸性END化簡(jiǎn)上述文法化簡(jiǎn)上述文法*13例例4.4：考慮文法：考慮文法：SQc|c Q Rb|b R Sa|a 消除左遞歸。消除左遞歸。解：解：將終結(jié)符排序?yàn)閷⒔K結(jié)符排序?yàn)镽、Q、S。對(duì)于。對(duì)于R不存在直接左遞歸。把不存在直接左遞歸。把R帶入帶入到到Q中有關(guān)的候選式：中有關(guān)的候選式： Q Sab|ab|b 現(xiàn)在現(xiàn)在Q同樣不含直接左遞歸，把它帶入同樣不含直接左遞歸，把它帶入S的有關(guān)候選式：的有關(guān)候選式： S Sabc|abc|bc|c 經(jīng)消除經(jīng)消除S的直接左遞歸后我們們得到整個(gè)文法的直接左遞歸后我們們得到整個(gè)文法 S a

8、bcS|bcS|cS S abcS| Q Sab|ab|b R Sa|a 由于關(guān)于由于關(guān)于Q,R的規(guī)則式多余的則可化簡(jiǎn)的規(guī)則式多余的則可化簡(jiǎn)得到：得到： S abcS|bcS|cS SabcS| 144.3.2 消除回溯、提左因子消除回溯、提左因子v令令G是一個(gè)不含左遞歸的文法，對(duì)是一個(gè)不含左遞歸的文法，對(duì)G 的所有的非終的所有的非終結(jié)符號(hào)的每個(gè)候選結(jié)符號(hào)的每個(gè)候選 定義它的終結(jié)首符集定義它的終結(jié)首符集FIRST( )為：為： FIRST( )=a| *a,a VTv若若* ，則規(guī)定，則規(guī)定 FIRST( )。 換句話(huà)說(shuō)換句話(huà)說(shuō)FIRST( )是是 的所有可能推導(dǎo)的開(kāi)頭終結(jié)符或可能的所有可能推

9、導(dǎo)的開(kāi)頭終結(jié)符或可能的的 15v如果非終結(jié)符如果非終結(jié)符A 的所有候選首符集兩兩不相交，即的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同的候選的任何兩個(gè)不同的候選 i和和 j FIRST( i) FIRST( j) = 那么，當(dāng)要求那么，當(dāng)要求A匹配輸入串時(shí)，匹配輸入串時(shí)，A 就能根據(jù)它所面就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a 的的 16v如何把一個(gè)文法改造成任何終結(jié)首符集的所有候選首符集兩如何把一個(gè)文法改造成任何終結(jié)首符集的所有候選首符集兩兩不相交呢？

10、其辦法是兩不相交呢？其辦法是提取公共左因子提取公共左因子v假定關(guān)于假定關(guān)于A 的規(guī)則是的規(guī)則是A1| 2| |n| 1| 2| | m （其中每個(gè)（其中每個(gè) 不以不以 開(kāi)頭）開(kāi)頭） 那末，可以把這些規(guī)則改寫(xiě)成：那末，可以把這些規(guī)則改寫(xiě)成：A A| 1| 2| | mA 1 | 2 | | n 17例：例：有產(chǎn)生式有產(chǎn)生式 B bBcA|b 由于由于FIRST(bBcA) FIRST(b) =b ，則需要提，則需要提取公共左因子，將產(chǎn)生式改寫(xiě)成：取公共左因子，將產(chǎn)生式改寫(xiě)成：B bCC BcA| 18 v 問(wèn)題問(wèn)題 例：例：考慮文法考慮文法4.1，對(duì)輸入串，對(duì)輸入串i+i進(jìn)行自上而下分析進(jìn)行自上

11、而下分析EFETT(b)i+iIPi+iIP(a)ETEi+iIP(c)FTTEEiEFETT(d)i+iIPiEi+iFEIPTT(e)i+ETiFTETEE+TE|TFTT*FT|F(E)|i19v假定假定S是文法是文法G開(kāi)始符號(hào)，對(duì)任何非終結(jié)符開(kāi)始符號(hào)，對(duì)任何非終結(jié)符A定義：定義： FOLLOW(A) = a | S* Aa, a VT v若若S* A， 則規(guī)定則規(guī)定# FOLLOW(A). 也就是說(shuō)，也就是說(shuō)，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接是所有句型中出現(xiàn)在緊接A之后的終結(jié)之后的終結(jié)符或符或#v因此，當(dāng)非終結(jié)符因此，當(dāng)非終結(jié)符A面臨輸入符號(hào)面臨輸入符號(hào)a，且，且a不屬于不屬于

12、A的任意候選首符集但的任意候選首符集但A的某個(gè)候選首符集包含的某個(gè)候選首符集包含 時(shí)，時(shí)，只有當(dāng)只有當(dāng)aFOLLOW(A)，才可能允許，才可能允許A自動(dòng)匹配自動(dòng)匹配204.3.3 LL(1)文法文法v判斷某給定文法是否為判斷某給定文法是否為L(zhǎng)L(1)文法其條件為：文法其條件為：文法不含左遞歸文法不含左遞歸對(duì)于文法中每個(gè)非終結(jié)符對(duì)于文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若兩兩不相交。即，若 A 1 | 2 | n 則：則： FIRST( i) FIRST( j) = （i j )對(duì)文法中每一個(gè)非終結(jié)符對(duì)文法中每一個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集，

13、若它存在某個(gè)候選首符集包含包含 ，則，則 FIRST(A) FLLOW(A)= v一個(gè)文法若滿(mǎn)足以上條件，則稱(chēng)該文法一個(gè)文法若滿(mǎn)足以上條件，則稱(chēng)該文法G為為L(zhǎng)L(1)文法文法21v對(duì)于對(duì)于LL(1)文法，可以對(duì)其輸入串進(jìn)行有效的無(wú)回文法，可以對(duì)其輸入串進(jìn)行有效的無(wú)回溯的自上而下分析。假設(shè)要用非終結(jié)符溯的自上而下分析。假設(shè)要用非終結(jié)符A匹配，輸匹配，輸入符號(hào)入符號(hào)a，A的所有產(chǎn)生式為的所有產(chǎn)生式為A 1 | 2 | nn若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)執(zhí)行匹配任務(wù)n若若a不屬于任何一個(gè)候選首符集，則不屬于任何一個(gè)候選首符集，則u若若FIRST( i)且且a FLLOW(

14、A)，則讓?zhuān)瑒t讓A與與 自動(dòng)匹配自動(dòng)匹配u否則，否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤的出現(xiàn)是一種語(yǔ)法錯(cuò)誤224.4 遞歸下降分析法遞歸下降分析法v當(dāng)一個(gè)文法滿(mǎn)足當(dāng)一個(gè)文法滿(mǎn)足LL(1)條件時(shí)，我們就可以構(gòu)造一條件時(shí)，我們就可以構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序由個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序由一組遞歸過(guò)程組成，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終一組遞歸過(guò)程組成，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣一個(gè)分析程序稱(chēng)為結(jié)符。這樣一個(gè)分析程序稱(chēng)為遞歸下降分析器遞歸下降分析器23v例如，文法例如，文法4.1的每個(gè)非終結(jié)符所對(duì)應(yīng)的遞的每個(gè)非終結(jié)符所對(duì)應(yīng)的遞歸過(guò)程如下：歸過(guò)程如下：PROCEDUR

15、E E; PROCEDURE T;BEGIN BEGINT;E F;TEND; END;PROCEDURE E; PROCEDURE T;IF SYM=+ THEN IF SYM=* THENBEGIN BEGIN ADVANCE; ADVANCE;T;E F;TEND; END;PROCEDURE F;IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;ETEE+TE|TFTT*FT|F(E)|i244.5 預(yù)測(cè)分析法預(yù)測(cè)分析法v使

16、用高級(jí)語(yǔ)言的遞歸過(guò)程描述遞歸下降分析器，只使用高級(jí)語(yǔ)言的遞歸過(guò)程描述遞歸下降分析器，只有當(dāng)具有實(shí)現(xiàn)這種過(guò)程的編譯系統(tǒng)時(shí)才有實(shí)際意義有當(dāng)具有實(shí)現(xiàn)這種過(guò)程的編譯系統(tǒng)時(shí)才有實(shí)際意義v實(shí)現(xiàn)實(shí)現(xiàn)LL(1)分析的另一種有效方式是使用一張分析分析的另一種有效方式是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制。我們現(xiàn)在介紹的表和一個(gè)棧進(jìn)行聯(lián)合控制。我們現(xiàn)在介紹的預(yù)測(cè)分預(yù)測(cè)分析程序析程序就是屬于這種類(lèi)型的就是屬于這種類(lèi)型的LL(1)分析器分析器254.5.1預(yù)測(cè)分析程序工作過(guò)程預(yù)測(cè)分析程序工作過(guò)程v預(yù)測(cè)分析表是一個(gè)預(yù)測(cè)分析表是一個(gè)MA, a形式的矩陣形式的矩陣v對(duì)于任何對(duì)于任何(X,a)，總控程序執(zhí)行下述動(dòng)作之一，總控程

17、序執(zhí)行下述動(dòng)作之一n若若X=a=#，則分析成功，停止，則分析成功，停止n若若X=a#，則把，則把X從從STACK棧頂逐出，讓棧頂逐出，讓a指向下一個(gè)輸入符號(hào)指向下一個(gè)輸入符號(hào)n若若X是一個(gè)非終結(jié)符，則依據(jù)分析表是一個(gè)非終結(jié)符，則依據(jù)分析表M中的不同內(nèi)容作不同處理中的不同內(nèi)容作不同處理a#輸入串輸入串總控程序總控程序預(yù)測(cè)分析表預(yù)測(cè)分析表Mx#輸出輸出26v預(yù)測(cè)分析器的總控程序：預(yù)測(cè)分析器的總控程序：置置 ip指向指向 w#的第一個(gè)符號(hào)；令的第一個(gè)符號(hào)；令X為棧頂符號(hào)，為棧頂符號(hào)，a是是 ip所指向的符號(hào)所指向的符號(hào)BEGINpush(st,#); push(st,S);FLAG:=TRUE;WH

18、ILE FLAG DOBEGIN IF X VT THEN IF X=a THEN pop(st); ip:=ip+1 ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF Mx,a=XX1X2Xk THEN pop(st);push(st,Xk);push(st,X1) ELSE ERROR、END OF WHILE;STOPEND27 i1 + i2 * i3 #輸入輸入預(yù)測(cè)分析控制程序#E ET TF i ET+ TF i ETEFTEi1TEi1E i1+TE i1+FTE i1+i2TE棧ETEE

19、+TE|TFTT*FT|F(E) | i28例：例：輸入串為輸入串為i1+i2，利用分析表進(jìn)行預(yù)測(cè)分析。，利用分析表進(jìn)行預(yù)測(cè)分析。符號(hào)棧符號(hào)棧 輸入串輸入串 MX,b1 #E i1+i2# E TE2 #ET i1+i2# T FT3 #ETF i1+i2# F i4 #ET i i1+i2# 匹配匹配5 # ET +i2# T 6 #E +i2# E +TE7 #ET+ +i2# 匹配匹配8 # ET i2# T FT 9 #ETF i2# F i10 #ETi i2# 匹配匹配11 #ET # T 12 #E # E 13 # # 接受接受ETEE+TE|TFTT*FT|F(E) | ii

20、+*()#ETETEE+TETFTFTT*FTFi(E)29v計(jì)算計(jì)算FIRSTFIRST集集若若X X V V , ,則則FIRST(X)=XFIRST(X)=X若若X X V VN N, ,且有產(chǎn)生式且有產(chǎn)生式X Xa a，則把，則把a(bǔ) a加入到加入到FIRST(X)FIRST(X)中中; ;若若X X也是一條產(chǎn)生式也是一條產(chǎn)生式, ,則把則把 也加到也加到FIRST(X)FIRST(X)中中若若X XY Y是一個(gè)產(chǎn)生式且是一個(gè)產(chǎn)生式且Y Y V VN N, ,則把則把FIRST(Y)FIRST(Y)中的所有中的所有非非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;若若X

21、 X Y Y1 1Y Y2 2Y YK K 是一個(gè)產(chǎn)是一個(gè)產(chǎn)生式生式,Y,Y1 1,Y,Y2 2, ,Y,Y(i-1)(i-1)都是非終結(jié)符都是非終結(jié)符, ,而且而且, ,對(duì)于任何對(duì)于任何j,1j,1j j i-i-1, FIRST(Y1, FIRST(Yj j) )都含有都含有 ( (即即Y Y1 1.Y.Y(i-1) (i-1) =* ), ),則把則把FIRST(YFIRST(Yi i) )中的所有非中的所有非 元素都加到元素都加到FIRST(X)FIRST(X)中中; ;特特別是別是, ,若所有的若所有的FIRST(YFIRST(Yj j , , j=1,2,j=1,2,K),K)均含

22、有均含有 , ,則把則把 加到加到FRIST(X)FRIST(X)中中 4.5.2 預(yù)測(cè)分析表的構(gòu)造預(yù)測(cè)分析表的構(gòu)造30v求求First(), =X1 1X2 2Xn n 置置FIRST(FIRST()=FIRST()=FIRST(X1)1) 若對(duì)任何若對(duì)任何1ji-1, 1ji-1, FIRST(XFIRST(Xj j) )，則把，則把FIRST(FIRST(Xi)i) 加入加入FIRST(FIRST() )中中特別是特別是, ,若所有的若所有的FIRST(XFIRST(Xj j) )均含有均含有 , 1jn, 1jn，則把，則把 加加到到FRIST(FRIST() )中中v顯然，若顯然，若

23、= = ，則，則FIRST(FIRST()=)= 31v計(jì)算計(jì)算FOLLOWFOLLOW集集對(duì)于文法的開(kāi)始符號(hào)對(duì)于文法的開(kāi)始符號(hào)S,S,置置# #于于FOLLOW(S)FOLLOW(S)中中若若 BB是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, ,則把則把FIRST()FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中若若BB是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, ,或或BB是一個(gè)產(chǎn)生式而是一個(gè)產(chǎn)生式而=* ( (即即 FIRST()FIRST()），則把），則把FOLLOWFOLLOW（A A）加至）加至FOLLOWFOLLOW（B B）中）中32 例例4.8 對(duì)于文法對(duì)于文法 ETE E +TE| T F

24、T T *FT| F (E)| i 我們構(gòu)造每個(gè)非終結(jié)符的我們構(gòu)造每個(gè)非終結(jié)符的FIRST和和FOLLOW集合集合 解：解：FIRST(E) = (, i FOLLOW(E) = ), # FIRST(E) = +, FOLLOW(E) = ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FIRST(T) = *, FOLLOW(T) =+ , ), # FIRST(F) = (, i FOLLOW(F) =*, +, ) , # 在這里我們要注意在這里我們要注意FOLLOW(F)的求解過(guò)程其中：的求解過(guò)程其中：v因?yàn)橐驗(yàn)門(mén) FT，所以，所以FIRST(T)

25、=*應(yīng)加入應(yīng)加入FOLLOW(F)中中v因?yàn)橐驗(yàn)門(mén) ,所以將所以將FOLLOW(T)=+, ), #加到加到FOLLOW(F)中中33v構(gòu)造分析表構(gòu)造分析表M的算法是：的算法是：對(duì)文法對(duì)文法G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式A執(zhí)行第二步和第三步；執(zhí)行第二步和第三步；對(duì)于每個(gè)終結(jié)符對(duì)于每個(gè)終結(jié)符a FIRST( )，把，把A加到加到MA,a中；中；若若FIRST( ) ，則對(duì)任何的，則對(duì)任何的b FOLLOW(A)把把A加至加至MA,b中；中；把所有無(wú)定義的把所有無(wú)定義的MA,a標(biāo)上標(biāo)上“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”v一個(gè)文法一個(gè)文法G的預(yù)測(cè)分析表的預(yù)測(cè)分析表M不含多重定義入口，當(dāng)且僅不含多重定義入口，當(dāng)且僅當(dāng)該

26、文法為當(dāng)該文法為L(zhǎng)L(1)的的34例：例：構(gòu)造文法構(gòu)造文法4.1的分析表。的分析表。 ETE FIRST(TE) = (, i E +TE | FIRST(+TE)=+ FOLLOW(E)=)， T FT FIRST(FT) = (, i T *FT | FIRST(*FT)=* FOLLOW(T)=+,)，F(xiàn) (E) | i FIRST(E)=( FIRST(i)=i ETEE+TE|TFTT*FT|F(E) | ii+*()#ETETEE +TE TFTFTT *FT F i ( E )35i+*()#ETETEE +TE TFTFTT *FT F i ( E )符號(hào)棧符號(hào)棧#E#ET#E

27、TF#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#產(chǎn)生式產(chǎn)生式/動(dòng)作動(dòng)作ETETFTF iT E +TET FTF iT *FTF iT E 例：輸入例：輸入 i+i*iETEE+TE|TFTT*FT|F(E) | i36v例：例：已知文法已知文法GA為為AaABe|a BBb|d試給出與試給出與GA等價(jià)的等價(jià)的LL(1)文法文法GA構(gòu)造構(gòu)造GA的預(yù)測(cè)分析表，并給出輸入串的預(yù)測(cè)分析表，并給出輸入串a(chǎn)ade#的分析過(guò)程

28、的分析過(guò)程 解：解：文法文法GA不是不是LL(1)文法的原因是：文法的原因是：n產(chǎn)生式產(chǎn)生式AaABe|a，使得，使得FIRST(aABe)FIRST(a)=a n產(chǎn)生式產(chǎn)生式BBb|d含有左遞歸含有左遞歸要構(gòu)造與要構(gòu)造與GA等價(jià)的等價(jià)的LL(1)文法，就要消除上述兩種問(wèn)題文法，就要消除上述兩種問(wèn)題37將將AaABe|a修改為：修改為：AaC CABe| 將將BBb|d修改為：修改為： BdB BbB| 因此得到文法因此得到文法GA： AaC BdB BbB| CABe| 求每一個(gè)非終結(jié)符的求每一個(gè)非終結(jié)符的FIRST集：集：FIRST(A)=a FIRST(B)=d FIRST(B)=b,

29、FIRST(C)=a, 求每一個(gè)非終結(jié)符的求每一個(gè)非終結(jié)符的FOLLOW集：集：FOLLOW(A)=#FIRST(Be)=#, d FOLLOW(B)=FIRST(e)=eFOLLOW(B)=FOLLOW(B)=e FOLLOW(C)=FOLLOW(A)= #, d對(duì)對(duì)BbB| ，有，有FIRST(B)FOLLOW(B)=b, e= 對(duì)對(duì)CABe| ，有，有FIRST(C)FOLLOW(C)= a, #, d= 而文法的其他產(chǎn)生式都只有一個(gè)非而文法的其他產(chǎn)生式都只有一個(gè)非 的右部，因而滿(mǎn)足的右部，因而滿(mǎn)足LL(1)文法的要求，文法的要求，即分析過(guò)程中不會(huì)出現(xiàn)回溯。即分析過(guò)程中不會(huì)出現(xiàn)回溯。所以

30、文法所以文法GA就是所求的與原文法等價(jià)的就是所求的與原文法等價(jià)的LL(1)文法。文法。38v構(gòu)造構(gòu)造GA的預(yù)測(cè)分析表的預(yù)測(cè)分析表對(duì)對(duì)AaC，F(xiàn)IRST(aC)=a, MA, a=” AaC”對(duì)對(duì)BdB，F(xiàn)IRST(dB)=d, MB, d=”BdB”對(duì)對(duì)BbB| ，F(xiàn)IRST(bB)=b, MB, b=”BbB”FOLLOW(B)=e, MB, e=” B”對(duì)對(duì)CABe| ，F(xiàn)IRST(ABe)=a, MC, a=”CABe”FOLLOW(C)=#, d, MC, #=”C”, MC, d=”C”39v所以得到的所以得到的LL(1)分析表是：分析表是：abde#AAaCBBdBBBbBBCCA

31、BeCC40v對(duì)輸入串對(duì)輸入串a(chǎn)ade#的分析的分析過(guò)程如下：過(guò)程如下：步驟步驟符號(hào)棧符號(hào)棧輸入串輸入串產(chǎn)生式產(chǎn)生式/動(dòng)作動(dòng)作1#Aaade#AaC2#Caaade#匹配匹配3#Cade#CABe4#eBAade#AaC5#eBCaade#匹配匹配6#eBCde#C7#eBde#BdB8#eBdde#匹配匹配9#eBe#B10#ee#匹配匹配11#接受接受41例題與習(xí)題解答例題與習(xí)題解答例例1：試構(gòu)造與下列文法試構(gòu)造與下列文法GS等價(jià)的無(wú)左遞歸文法。等價(jià)的無(wú)左遞歸文法。 GS: SSa|Nb|c (1) N Sd|Ne|f (2)解：解：以以S,NS,N為序?yàn)樾? ,對(duì)于對(duì)于（1）我們引入新非

32、終結(jié)符）我們引入新非終結(jié)符S 則：則： S NbS |cS 1 SaS| 2 將將 S代入代入 （2） N Ne |NbSd |cSd |f 引入新非終結(jié)符引入新非終結(jié)符N N cSdN |fN 3 N eN |bSdN | 442例例2：文法文法G的規(guī)則集為的規(guī)則集為; P begin d : X end X d : X | sY Y : sY | 做出該文法做出該文法LL(1)分析表。分析表。解：解： 非終結(jié)符只有非終結(jié)符只有 P , X ,Y 只有只有FIRST(Y)含有含有 ，則需要求出，則需要求出FOLLOW(Y)且且 FOLLOW(Y) =FOLLOE(X)=end則有則有LL(1

33、)表：表： begin d : end s #P begin d : X endX d : X sYY :sY 練練 習(xí)習(xí)43 例例3：給出語(yǔ)言給出語(yǔ)言L(fǎng)=1na0n1ma0m|n0, m=0 的的LL(1)文法文法GS并說(shuō)并說(shuō)明其理由。明其理由。 解：解：觀察句子觀察句子,發(fā)現(xiàn)可分成兩部分發(fā)現(xiàn)可分成兩部分 1na0n 和和 1ma0m兩部分中符號(hào)的兩部分中符號(hào)的個(gè)數(shù)個(gè)數(shù)n和和m沒(méi)有制約關(guān)系。則可改造成下列文法：沒(méi)有制約關(guān)系。則可改造成下列文法： S AB A 1A0 |1a0 B 1B0 |a 對(duì)于產(chǎn)生式對(duì)于產(chǎn)生式 A 1A0 |1a0 兩個(gè)候選式兩個(gè)候選式 FIRST(1A0) FIRST(1a0)=1 所以上邊文法不是所以上邊文法不是LL(1)文法：需左提公因子，得到：文法：需左提公因子，得到： S AB A 1C C A0 |a0 B 1B0 |a 此文法滿(mǎn)足此文法滿(mǎn)足LL(1)文法的要求。文法的要求。44例例4：文法文法GS： S(L) | a L L,S | S 請(qǐng)消除左遞歸，并構(gòu)造請(qǐng)消除左遞歸，并構(gòu)造LL(1)預(yù)測(cè)分析表，并說(shuō)明對(duì)輸入串預(yù)測(cè)分析表，并說(shuō)明對(duì)輸入串(a，(a，a)的分析過(guò)程。的分析過(guò)程。 解：解：將所給文法