編譯原理 第6章自頂向下分析法11-7

1、第第6章章 自上而下語法分析自上而下語法分析編譯原理編譯原理u 自上而下語法分析思想自上而下語法分析思想u 非非LL(1)文法到文法到LL(1)文法的等價(jià)變換文法的等價(jià)變換u LL(1)分析法分析法u 遞歸下降分析程序遞歸下降分析程序本章知識(shí)點(diǎn)：本章知識(shí)點(diǎn)：編譯原理編譯原理n是以詞法分析器生成的單詞符號(hào)序列作為輸入，是以詞法分析器生成的單詞符號(hào)序列作為輸入，根據(jù)語言的語法規(guī)則（上下文無關(guān)文法），識(shí)別根據(jù)語言的語法規(guī)則（上下文無關(guān)文法），識(shí)別出各種語法成分（如表達(dá)式、語句、程序）。出各種語法成分（如表達(dá)式、語句、程序）。n并在分析過程中進(jìn)行語法檢查，檢查所給單詞符并在分析過程中進(jìn)行語法檢查，檢查

2、所給單詞符號(hào)序列是否是該語言文法的一個(gè)號(hào)序列是否是該語言文法的一個(gè)句子句子。n若是若是,以某種形式的以某種形式的語法樹語法樹作為輸出；否則指出作為輸出；否則指出錯(cuò)誤的性質(zhì)和位置。錯(cuò)誤的性質(zhì)和位置。語法分析功能語法分析功能編譯原理編譯原理語法分析方法分類語法分析方法分類u自上而下分析法自上而下分析法：從文法的開始符號(hào)出發(fā)從文法的開始符號(hào)出發(fā)，尋找尋找與與輸入符號(hào)串輸入符號(hào)串匹配匹配的的推導(dǎo)，推導(dǎo)，或者說，為輸入串尋找一個(gè)或者說，為輸入串尋找一個(gè)最左最左推導(dǎo)。推導(dǎo)。u自下而上分析法自下而上分析法：從從輸入符號(hào)串輸入符號(hào)串開始開始，逐步進(jìn)行逐步進(jìn)行歸約歸約，直至，直至歸約歸約到到文法的文法的開始符號(hào)

3、開始符號(hào)。 編譯原理編譯原理語法分析語法分析自上而下分析自上而下分析自下而上分析自下而上分析確定的確定的不確定的不確定的算法優(yōu)先分析法算法優(yōu)先分析法遞歸下降子程序法遞歸下降子程序法預(yù)測分析法預(yù)測分析法LRLR分析法分析法編譯原理編譯原理一一. 自上二而下語法分析思想自上二而下語法分析思想n自頂向下分析法也稱面向目標(biāo)的分析方法自頂向下分析法也稱面向目標(biāo)的分析方法,也就是從也就是從文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完全匹配的句子全匹配的句子,若輸入串是給定的句子若輸入串是給定的句子,則必能推出則必能推出,反之必然出錯(cuò)。反之必然出錯(cuò)。n確定的自頂向

4、下分析方法，首先要解決從文法的開確定的自頂向下分析方法，首先要解決從文法的開始符號(hào)出發(fā)，如何根據(jù)當(dāng)前的輸入符號(hào)（單詞符號(hào)始符號(hào)出發(fā)，如何根據(jù)當(dāng)前的輸入符號(hào)（單詞符號(hào)）唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符往）唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo)，或構(gòu)造一棵相應(yīng)的語法樹。下推導(dǎo)，或構(gòu)造一棵相應(yīng)的語法樹。6.1 6.1 自上而下語法分析概論自上而下語法分析概論編譯原理編譯原理二二.舉例說明舉例說明 例例1.1.若有文法若有文法G1SG1S： S S pApA | | qBqB A A cAdcAd | a | a B B dB | b dB | b 若輸入串若輸入串W=W=pccad

5、dpccadd。自頂向下推導(dǎo)過程為自頂向下推導(dǎo)過程為S=S=pApA=pcAdpcAd=pccAddpccAdd=pccaddpccaddn每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開始。每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開始。n如果兩個(gè)產(chǎn)生式有相同的左部，那么它們?nèi)绻麅蓚€(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開始。的右部由不同的終結(jié)符開始。編譯原理編譯原理例例2.2. 若有文法若有文法G2SG2S為為S ApS BqA aA cAB bB db當(dāng)輸入串當(dāng)輸入串W=ccap，那么試圖推出輸入那么試圖推出輸入串的推導(dǎo)過程為：串的推導(dǎo)過程為：S=Ap=cAp=ccAp=ccapn產(chǎn)生式的右部不全是由終結(jié)符開

6、始產(chǎn)生式的右部不全是由終結(jié)符開始n如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開始。由不同的終結(jié)符或非終結(jié)符開始。n文法中無空產(chǎn)生式文法中無空產(chǎn)生式編譯原理編譯原理例例3.3. 若有文法若有文法GS:GS:SaASdAbASA 若輸入串若輸入串W=abd，則試圖推導(dǎo)出，則試圖推導(dǎo)出abd串的串的推導(dǎo)過程為：推導(dǎo)過程為：=aA=abAS=abS=abd 當(dāng)某一非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生當(dāng)某一非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生式時(shí)，它的非空產(chǎn)生式右部的首符號(hào)集兩兩式時(shí)，它的非空產(chǎn)生式右部的首符號(hào)集兩兩不相交，并與在推導(dǎo)過程中不相交，并與在推導(dǎo)

7、過程中緊跟緊跟該非終結(jié)符該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符集也不相交，則仍可右邊可能出現(xiàn)的終結(jié)符集也不相交，則仍可構(gòu)造確定的自頂向下分析。構(gòu)造確定的自頂向下分析。編譯原理編譯原理6.2 適合自上而下分析的文法適合自上而下分析的文法n消除左遞歸消除左遞歸n消除左公因子消除左公因子nLL（1）文法）文法編譯原理編譯原理一一. .提取左公共因子提取左公共因子將產(chǎn)生式將產(chǎn)生式A|r 等價(jià)變換為等價(jià)變換為:A(|r)，將括號(hào)內(nèi)用一新引入的非終結(jié)符將括號(hào)內(nèi)用一新引入的非終結(jié)符A表示表示,得得 AA，A|r一般形式：若一般形式：若A1|2|n,提取左公共因子后變?yōu)樘崛∽蠊惨蜃雍笞優(yōu)锳A， A 1|2|n若在若

8、在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.編譯原理編譯原理例例1.文法文法G1：SaSb|aS|解：提左因子得解：提左因子得:SaS(b|)| 引進(jìn)新的非終結(jié)符得引進(jìn)新的非終結(jié)符得:SaSS|Sb|舉例舉例編譯原理編譯原理例例2 若文法若文法G2的產(chǎn)生式為的產(chǎn)生式為：A AadadA ABcBcB BaAaAB BbBbB舉例舉例編譯原理編譯原理 對右部以非終結(jié)符開對右部以非終結(jié)符開始的產(chǎn)生式，用其相始的產(chǎn)生式，用其相同左部而右部以終結(jié)同左部而右部以終結(jié)符開始的產(chǎn)生式進(jìn)行符開始的產(chǎn)生式進(jìn)行相應(yīng)替換相應(yīng)替換(1)A ad(2)A aAc(3)A bBc(4)B aA(5)B

9、 bB提取產(chǎn)生式提取產(chǎn)生式(1)、(2)的左的左公共因子得：公共因子得：A a(d|Ac)A bBcB aAB bB替換后：替換后：(1)A aA (2)A bBc(3)A d(4)A Ac(5)B aA(6)B bB編譯原理編譯原理二二.消除左遞歸消除左遞歸n產(chǎn)生式產(chǎn)生式 (1)A- (1)A-AbAb (2)A- (2)A-Bb,BBb,B-AaAan形如形如(1)(1)產(chǎn)生式文法包含產(chǎn)生式文法包含 簡單直接左遞歸簡單直接左遞歸n形如形如(2)(2)產(chǎn)生式文法包含產(chǎn)生式文法包含 間接左遞歸間接左遞歸n改寫規(guī)則：改寫規(guī)則：S Sa | bS bSSaS | 編譯原理編譯原理文法：文法：E-E

10、+T|TT-T*F|FF-(E)|i i舉例：舉例：E TE，E +T E | T FT ，T*FT | F-(E)|iS Sa | bS bSSaS | 編譯原理編譯原理舉例舉例 消除間接左遞歸消除間接左遞歸 先先將將間接左遞歸變?yōu)橹苯幼筮f歸，然間接左遞歸變?yōu)橹苯幼筮f歸，然后再消除直接左遞歸。后再消除直接左遞歸。文法：文法：1.AaB2.ABb3.BAc4.Bd用用產(chǎn)生式產(chǎn)生式(1)、(2)的右部代的右部代替產(chǎn)生式替產(chǎn)生式(3)的右部得到：的右部得到：(1)B aBc(2)B Bbc(3)B d編譯原理編譯原理消除左遞歸后：消除左遞歸后：B (aBc | d)B B bcB | 將原來的產(chǎn)生

11、式將原來的產(chǎn)生式A aB, A Bb加入，最加入，最終文法為：終文法為：(1) A aB(2) A Bb(3) B (aBc|d)B (4) B bcB | 編譯原理編譯原理習(xí)題習(xí)題 消除左遞歸消除左遞歸 提取左公因子提取左公因子1.文法：文法：AaABe|a BBb|d2. 文法：文法：SAa|b ASB Bab3.文法：文法：AbaB| BAbb|a編譯原理編譯原理1. 0) Aa Nn1) NA B en2) Nn3) Bd N1n4) N1b N1n5) N12.0) Sb N1) NB a N2) N3) Ba b3.0) AbaB1) A2) BbN3) Ba4) NaBbb5)

12、Nb編譯原理編譯原理6.3 LL(1)分析法分析法nLL(1)分析過程分析過程nLL(1)文法文法nLL(1)文法相關(guān)三個(gè)集合求解文法相關(guān)三個(gè)集合求解nLL(1)分析法分析過程分析法分析過程 編譯原理編譯原理一一.LL(1).LL(1)文法文法LL(1)LL(1)的含義是：的含義是：第一個(gè)第一個(gè)L L表示從左到右掃描輸入串表示從左到右掃描輸入串第二個(gè)第二個(gè)L L表示分析過程用最左推導(dǎo)表示分析過程用最左推導(dǎo)1 1表明只需向前看一個(gè)符號(hào)便可以決定選哪表明只需向前看一個(gè)符號(hào)便可以決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，類似地類似地LL(kLL(k) )文法需要向前看文法需要向前看K K個(gè)符號(hào)才可

13、以確定選用個(gè)符號(hào)才可以確定選用哪個(gè)產(chǎn)生式。哪個(gè)產(chǎn)生式。編譯原理編譯原理二二.LL(1)文法判定文法判定1. 首符號(hào)集首符號(hào)集FIRSTFIRST2.2.后繼符號(hào)集后繼符號(hào)集FOLLOWFOLLOW3.3.選擇集合選擇集合SELECTSELECT判斷條件判斷條件 : 第一，文法無左遞歸第一，文法無左遞歸第二，文法無左公因子第二，文法無左公因子第三，第三， 對每個(gè)具有相同左部的產(chǎn)生式對每個(gè)具有相同左部的產(chǎn)生式A與與A，滿滿足足 SELECT(A)SELECT(A)=。 其中其中，中至多只有一個(gè)能推出中至多只有一個(gè)能推出。編譯原理編譯原理三三.3個(gè)集合相關(guān)集合求解個(gè)集合相關(guān)集合求解1. 首符號(hào)集首符

14、號(hào)集FIRST：2. 后繼符號(hào)集后繼符號(hào)集FOLLOW3. 選擇集合選擇集合SELECT編譯原理編譯原理 1 .首符號(hào)集首符號(hào)集FIRST()定義：另定義：另X為一個(gè)文法符號(hào)（包括終結(jié)符，非終結(jié)符和為一個(gè)文法符號(hào)（包括終結(jié)符，非終結(jié)符和 ），集合），集合FIRST(x)由終結(jié)符組成（包括由終結(jié)符組成（包括），定義如下，定義如下 若若, ,則則FIRST(X)=XFIRST(X)=X 若若X X V VN N, ,且有產(chǎn)生式且有產(chǎn)生式，則則aFIRST(XaFIRST(X) ); ;若若也是一條產(chǎn)生也是一條產(chǎn)生式式, ,則則 FIRST(X)FIRST(X). . 若若是文法規(guī)則且是文法規(guī)則且Y

15、 Y V VN N, ,則把則把FIRST(Y)FIRST(Y)中的所有非中的所有非 元元素都加素都加到到FIRST(X)FIRST(X)中中; ; 若有規(guī)則若有規(guī)則,Y1,Y2,Y(i-1) , 且對于任何且對于任何j,1j i-1,FIRST(Yj)都含有都含有 (即即 ),則則FIRST(Y1)- ， FIRST(Y2)- ， FIRST(Yi-1)- ，F(xiàn)IRST(Yi)都都包含在包含在FIRST（X）中；）中； , 則則 FIRST(X) 概括說概括說FIRST()是由是由推導(dǎo)出的以終結(jié)符為首的（推導(dǎo)出的以終結(jié)符為首的（包括包括）集合。集合。例例1文法文法G2S: SApSBqAaA

16、cABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRST(b)=bFIRST(dB)=d 由于由于同一非終結(jié)符同一非終結(jié)符的兩個(gè)的兩個(gè)產(chǎn)生式的右部產(chǎn)生式的右部推導(dǎo)出來的推導(dǎo)出來的開始開始符號(hào)集符號(hào)集不相交，因此可根據(jù)當(dāng)前輸入符屬于哪個(gè)產(chǎn)生式右部不相交，因此可根據(jù)當(dāng)前輸入符屬于哪個(gè)產(chǎn)生式右部的開始符號(hào)集而決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，可以進(jìn)行確定的開始符號(hào)集而決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，可以進(jìn)行確定的自頂向下分析的自頂向下分析編譯原理編譯原理SABSbCAAbBBaDCADCbDaSDcFIRST(AD)=(FIRST(A)-) FIRS

17、T(D)=a,b,cFIRST(S)=FIRST(AB)b=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)= FIRST(AD)b=a,b,cFIRST(D)=a,cFIRST(AB)=(FIRST(A)-) (FIRST(B)-) =a,b,例例2：文法：文法G2S: 編譯原理編譯原理2.后繼符號(hào)集后繼符號(hào)集FOLLOW(B)定義：給出一個(gè)非終結(jié)符定義：給出一個(gè)非終結(jié)符A，那么集合，那么集合FOLLOW(B)則是由終則是由終結(jié)符組成的，此外還有輸入字符串結(jié)尾標(biāo)志符號(hào)結(jié)符組成的，此外還有輸入字符串結(jié)尾標(biāo)志符號(hào)#對于對于B是是文法的開始符號(hào)文法的開始符號(hào), #置于置于F

18、OLLOW(B)中中;若若B是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式,則把則把FIRST()- 加加到到FOLLOW(B)中中;若若B是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式,或或B是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， (即即 FIRST()），），則把則把FOLLOW（A）加至加至FOLLOW（B）中中 概括說概括說FOLLOW(A)是指非終結(jié)符直接后繼的終結(jié)是指非終結(jié)符直接后繼的終結(jié)符組成的集合。符組成的集合。例例3 文法文法G3S: SaA|d ， AbAS|,求求 A和和S的后繼符號(hào)集的后繼符號(hào)集由由 S=* S 得得 # FOLLOW(S) 由由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOW

19、(S)=# ,a,d 由由S=* aA 得得# FOLLOW(A) 由由S=* abAS=* abAaA 得得 a FOLLOW(A) =* abAd 得得 d FOLLOW(A) FOLLOW(A)=# ,a,d編譯原理編譯原理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,c, #FOLLOW(B)= #FOLLOW(C)= #FOLLOW

20、(D)= #SABSbCAAbBBaDCADCbDaSDc例例4 文法文法G4S:編譯原理編譯原理3 .選擇集合選擇集合SELECT(A) 定義：對給定的上下文無關(guān)文法的產(chǎn)生式定義：對給定的上下文無關(guān)文法的產(chǎn)生式AA，AVAVN N，VV* *，若若* *, , 則則SELECT(ASELECT(A)=)=FIRST(FIRST() )若若* * =, =, 則則SELECT(ASELECT(A) )=(=(FIRST()-)FOLLOW(AFIRST()-)FOLLOW(A) ) 若若*,則則SELECT(A)=FIRST()若若=*, 則則SELECT(A)=(FIRST()-)FOLLO

21、W(A)說明：說明： 對于產(chǎn)生式對于產(chǎn)生式AA與與AA，若若 SELECT(A)SELECT(ASELECT(A)SELECT(A)=)=，則一定可以則一定可以進(jìn)行確定的自頂向下分析進(jìn)行確定的自頂向下分析例例 G3S: SaA Sd AbAS ASELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A)=FOLLOW(A)=# ,a,d例例 有文法有文法GS為：為：SaAS SbAbAASELECT(SaAS)= aSELECT(Sb)= bSELECT(AbA)= bSELECT(A)=Foll

22、ow(A)= a,b由于由于SELECT(AbA)SELECT(A)=b，所以文法所以文法GS不是不是LL(1)文法文法編譯原理編譯原理例題：判斷文法是不是例題：判斷文法是不是LL(1)文法文法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,#FOLLOW(S)= $FOLLOW(A)= a,c, #FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #該文法不是該

23、文法不是LL(1)文法。文法。SELECT(Dc)=cSELECT(DaS)=aSELECT(Cb)=bSELECT(CAD)=a,b,cSELECT(BaD)=aSELECT(B)=#SELECT(Ab)=bSELECT(A)=a,c, #SELECT(SbC)=b編譯原理編譯原理習(xí)題習(xí)題 判斷文法是不是判斷文法是不是LL(1)文法文法1. 0) Aa Nn1) NA B en2) Nn3) Bd N1n4) N1b N1n5) N12.0) Sb N1) NB a N2) N3) Ba b3.0) AbaB1) A2) BbN3) Ba4) NaBbb5) Nb編譯原理編譯原理四四.LL(

24、1)分析法分析法分析步驟：分析步驟：1.判斷是否為判斷是否為LL(1)文法，是文法，是2.構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表3.句子分析過程句子分析過程編譯原理編譯原理(1)(1)判定判定文法是否為文法是否為LL(1)LL(1)？(2)(2)求出每條產(chǎn)生式的求出每條產(chǎn)生式的SELECTSELECT集集(3)(3)依照依照SELECTSELECT集把產(chǎn)生式填入分析表集把產(chǎn)生式填入分析表對每個(gè)終結(jié)符或?qū)γ總€(gè)終結(jié)符或#用用a a表示表示若若a a SELECT(ASELECT(A ) )，則把，則把AA 放入放入MA,aMA,a 中，把所中，把所有無定義的有無定義的MA,aMA,a 標(biāo)上出錯(cuò)標(biāo)記。標(biāo)上出錯(cuò)

25、標(biāo)記。預(yù)測分析表的構(gòu)造方法預(yù)測分析表的構(gòu)造方法編譯原理編譯原理q 根據(jù)棧頂符號(hào)根據(jù)棧頂符號(hào)X和當(dāng)前輸入符號(hào)和當(dāng)前輸入符號(hào)a，執(zhí)行下列三種動(dòng)作之一執(zhí)行下列三種動(dòng)作之一:1. 若若Xa，則宣布分析成功，停止分析。則宣布分析成功，停止分析。2. 若若Xa ，則把則把X從從STACK棧頂逐出，讓棧頂逐出，讓a指向下一個(gè)輸入指向下一個(gè)輸入符號(hào)。符號(hào)。3. 若若X是一個(gè)非終結(jié)符，則查看分析表是一個(gè)非終結(jié)符，則查看分析表M。 若若MX，a中存放著關(guān)于中存放著關(guān)于X的一個(gè)產(chǎn)生式，把的一個(gè)產(chǎn)生式，把X逐出逐出STACK棧頂，棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧棧

26、(若右部符號(hào)為若右部符號(hào)為 ，則意味不推什么東西進(jìn)棧，則意味不推什么東西進(jìn)棧)。在。在把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語義動(dòng)作。義動(dòng)作。 若若MX，a中存放著中存放著“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序，則調(diào)用出錯(cuò)診察程序ERROR。句子執(zhí)行過程句子執(zhí)行過程編譯原理編譯原理MX,a有產(chǎn)生式有產(chǎn)生式？彈出棧頂符放入彈出棧頂符放入XNYYNNNN YY Y把把#和文法開始符和文法開始符S壓入分析棧壓入分析棧;當(dāng)前輸入符送當(dāng)前輸入符送a把產(chǎn)生式右部把產(chǎn)生式右部反序反序進(jìn)棧。進(jìn)棧。XVT ?X=$ ? X=a ?X=a?讀下一輸

27、入讀下一輸入符到符到a出錯(cuò)出錯(cuò)結(jié)束結(jié)束出錯(cuò)出錯(cuò)預(yù)測分析程序流程預(yù)測分析程序流程編譯原理編譯原理例例 文法文法G EE+TTTT*FFF(E)i（1）消除）消除G的左遞歸得到文法的左遞歸得到文法 GETE E+TE TFT T*FTF(E)i（2）求出每個(gè)產(chǎn)生式的求出每個(gè)產(chǎn)生式的select集集,G是是LL(1)文法文法 SELECT(ETE ) = (,i SELECT(E+TE ) = + SELECT(E ) = ),$ SELECT(TFT ) = (,i SELECT(T*FT ) = * SELECT(T ) = +,),$ SELECT(F(E) ) = ( SELECT(F i

28、) = i 編譯原理編譯原理（2）求出每個(gè)產(chǎn)生式的求出每個(gè)產(chǎn)生式的select集集,G是是LL(1)文法文法 SELECT(ETE ) = (,i SELECT(E+TE ) = + SELECT(E ) = ),$ SELECT(TFT ) = (,i SELECT(T*FT ) = * SELECT(T ) = +,),$ SELECT(F(E) ) = ( SELECT(F i ) = i （3 3）依照選擇集合把產(chǎn)生式填入分析表）依照選擇集合把產(chǎn)生式填入分析表注：表中空白處為出錯(cuò)注：表中空白處為出錯(cuò)F (E)(E)F i iFT T T* FTFTT TT FTFTT FTFTTE E

29、 E+TEEETEETEE$）（*+i編譯原理編譯原理輸入串輸入串i+i*i#的分析過程的分析過程F (E)(E)F i iFT T T* FTFTT TT FTFTT FTFTTE E E+TEEETEETEE$）（*+i+匹配匹配+i*i #ET+7E+TE+i*i #E6T +i*i #ET5i匹配匹配i+i*i #ETi4Fii+i*i #ETF3TFTi+i*i#ET2ETEi+i*i#E1所用產(chǎn)生式所用產(chǎn)生式剩余輸入串剩余輸入串分析棧分析棧步驟步驟編譯原理編譯原理TFTi*i # ET8Fii # ETF13i匹配匹配i # ETi14T # ET15E # E16接受接受#17*

30、匹配匹配*i # ETF*12T * *FTFT*i # ET11i匹配匹配i*i # ETi10Fii*i # ETF9F (E)(E)F i iFT T T* FTFTT TT FTFTT FTFTTE E E+TEEETEETEE$）（*+i編譯原理編譯原理6.4 遞歸下降分析法遞歸下降分析法q基本思想：對文法中的每個(gè)非終結(jié)符編寫一個(gè)函數(shù)（或基本思想：對文法中的每個(gè)非終結(jié)符編寫一個(gè)函數(shù)（或子程序），用來識(shí)別由該非終結(jié)符所表示的語法成分。子程序），用來識(shí)別由該非終結(jié)符所表示的語法成分。當(dāng)非終結(jié)符有多條產(chǎn)生式時(shí)，按當(dāng)前輸入符屬于哪條產(chǎn)當(dāng)非終結(jié)符有多條產(chǎn)生式時(shí)，按當(dāng)前輸入符屬于哪條產(chǎn)生式的生式

31、的SELECTSELECT集可唯一確定選擇哪個(gè)產(chǎn)生式進(jìn)行匹配。集可唯一確定選擇哪個(gè)產(chǎn)生式進(jìn)行匹配。p由于描述語言的文法常常是遞歸定義的，因此相應(yīng)的函由于描述語言的文法常常是遞歸定義的，因此相應(yīng)的函數(shù)或子程序必然以相互遞歸的方式進(jìn)行調(diào)用，故此分析數(shù)或子程序必然以相互遞歸的方式進(jìn)行調(diào)用，故此分析法稱為遞歸下降分析法。法稱為遞歸下降分析法。編譯原理編譯原理p特點(diǎn)：特點(diǎn)：優(yōu)點(diǎn)：簡單直觀、易于構(gòu)造優(yōu)點(diǎn)：簡單直觀、易于構(gòu)造缺點(diǎn)：對文法要求高，必須滿足缺點(diǎn)：對文法要求高，必須滿足LL(1)LL(1)文法；遞歸調(diào)用文法；遞歸調(diào)用多，速度慢，占用空間多多，速度慢，占用空間多n幾個(gè)全局過程和變量：幾個(gè)全局過程和變量：nScanner()Scanner()，把輸入串指示器，把輸入串指示器IPIP指向下一個(gè)輸入符號(hào)，指向下一個(gè)輸入符號(hào)