編譯原理與技術(shù)講義 第4章 自頂向下的語法分析

1、編譯原理與技術(shù)第4章 自頂向下的語法分析 青島大學(xué)信息工程學(xué)院主要內(nèi)容自頂向下語法分析概述 LL(1)文法遞歸下降分析技術(shù) 預(yù)測分析技術(shù)LL(1)分析中的錯誤處理 編譯原理與技術(shù)24.1 自頂向下語法分析的一般方法基本思想：對任何輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下，從左到右地為輸入串建立分析樹?；蛘哒f，為輸入串尋找最左推導(dǎo)。 特點：本質(zhì)上是一種試探過程，反復(fù)使用不同的產(chǎn)生式謀求匹配輸入串。 編譯原理與技術(shù)3例4.1：設(shè)文法GS：ScAd，Aab|a，輸入串為cad，自頂向下進行語法分析，并構(gòu)造相應(yīng)語法樹。4.1 自頂向下語法分析的一般方法先按文法的開始符號產(chǎn)生根結(jié)點S，

2、選擇S惟一的產(chǎn)生式構(gòu)造語法樹，如圖4.1(a)所示。把S的子結(jié)點從左到右與輸入串中的字符相比較，第一個子結(jié)點c匹配輸入串第一個符號。第二個子結(jié)點是非終結(jié)符A，要選擇A的產(chǎn)生式進一步構(gòu)造。而A有兩個候選式，先選擇Aab構(gòu)造語法樹，如圖4.1(b)所示。(a) (b) (c)圖4.1 輸入串cad的語法分析樹編譯原理與技術(shù)4 此時A的最左子結(jié)點a匹配輸入串第二個符號。而A的第二個子結(jié)點b和輸入串第三個符號不一致，說明A的這個產(chǎn)生式不能用來產(chǎn)生該輸入串。這就需要回到子結(jié)點A，選用另一個產(chǎn)生式Aa來構(gòu)造語法樹，如圖4.1(c)所示。這種回頭選用其他產(chǎn)生式的過程稱為回溯?；厮輹r，要把由前面產(chǎn)生式Aab得

3、到的子樹刪除，并重新讀入在子結(jié)點A處的當(dāng)時符號a。用新的產(chǎn)生式構(gòu)造語法樹后，A的子結(jié)點為a，與當(dāng)前符號一致，讀入最后一個輸入符號d。此時結(jié)點A完成匹配，它的右邊是結(jié)點d，與當(dāng)前符號一致。這樣就完成了輸入串的匹配，說明輸入串cad是該文法的一個句子。上面的分析同時也給出了輸入串cad的最左推導(dǎo)過程：S cAd cad。 4.1 自頂向下語法分析的一般方法(a) (b) (c)編譯原理與技術(shù)5這種一般方法存在一些問題：(1) 左遞歸問題 自頂向下分析采取最左推導(dǎo)，文法中含有左遞歸會使自上而下的分析過程陷入無限循環(huán)。因此，必須消除文法的左遞歸。(2) 回溯問題 反復(fù)尋找可正確匹配的產(chǎn)生式時可能需要不

4、斷回溯，虛假匹配現(xiàn)象需要使用更復(fù)雜的回溯技術(shù)。這樣將會產(chǎn)生許多額外工作，因此應(yīng)設(shè)法消除回溯。4.1 自頂向下語法分析的一般方法編譯原理與技術(shù)6(3) 出錯處理 分析不成功時，要確定出錯的具體位置比較困難。 (4) 效率問題 這種帶回溯的自頂向下方法實際上是一種窮盡一切可能的試探法，因此效率很低，代價較高，從而該方法只有理論意義，在實際應(yīng)用中價值不大。4.1 自頂向下語法分析的一般方法編譯原理與技術(shù)74.2 LL(1)文法要實現(xiàn)無回溯的自頂向下語法分析，對相應(yīng)文法必須要有一定的限制。首先，文法應(yīng)該不含左遞歸，若文法中含有左遞歸，則需使用文法的等價變換消除左遞歸。其次，還要消除回溯。通過提取左因子

5、消除某些文法的回溯，為什么？沒有左遞歸和左因子的文法是否一定可以進行確定的自頂向下分析？ 編譯原理與技術(shù)8首符集FIRST4.2 LL(1)文法例4.2： 文法G1S:SpA | qB AcAd | a BdB | bw1 = pccadd自頂向下的推導(dǎo)過程：S pA pcAd pccAdd pccadd語法樹：ddSpASpAcAdSpAcAdcAdSpAcAcAa編譯原理與技術(shù)94.2 LL(1)文法文法G1S: SpA | qB AcAd | a BdB | b這個文法的特點：每個產(chǎn)生式的右部都由終結(jié)符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開始。 對于這樣的文法

6、，分析輸入串時，可以跟據(jù)輸入串的當(dāng)前符號確定選取產(chǎn)生式。 比如w1 = pccadd，第一個符號是p，而從開始符號S出發(fā)，只有選擇產(chǎn)生式SpA推導(dǎo)，才能出現(xiàn)符號p。同樣，要出現(xiàn)第二個符號c，必須選擇產(chǎn)生式AcAd。 這樣，雖然具有相同左部的產(chǎn)生式不只一個，但文法的特點決定了每一步推導(dǎo)只能選擇惟一的產(chǎn)生式，從而可以避免回溯。 編譯原理與技術(shù)104.2 LL(1)文法 例4.3： 文法G2S: SAa | Bb Aa | cA Bb | dBw2=ccaa自頂向下的推導(dǎo)過程：S Aa cAa ccAa ccaa語法樹：SAaSAacASAacAcASAacAcAa編譯原理與技術(shù)114.2 LL(1

7、)文法文法G2S: SAa | Bb Aa | cA Bb | dB這個文法的特點：每個產(chǎn)生式的右部不全是由終結(jié)符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符或非終結(jié)符開始。文法中無空產(chǎn)生式。 對于這樣的文法，分析輸入串時，也可以跟據(jù)輸入串的當(dāng)前符號確定地選取產(chǎn)生式。比如推導(dǎo)w2=ccaa時，首先考慮開始符號S，它可以推出以A或B開頭的符號串。而由以A和B為左部的產(chǎn)生式可知，A只能推出以a, c開頭的符號串，B只能推出以b, d開頭的符號串。因此，要得到w2的第一個符號c，只有選擇產(chǎn)生式SAa，AcA。同樣，要出現(xiàn)第二個符號c，仍需選擇產(chǎn)生式AcA，沒有別的選擇。這樣，文法

8、的特點決定了每一步推導(dǎo)只能選擇確定的產(chǎn)生式，從而可以避免回溯。編譯原理與技術(shù)12由上面兩個例子可知，一個文法在推導(dǎo)過程中是否會產(chǎn)生回溯，與文法中具有相同左部的每個產(chǎn)生式右部所能推出的開頭符號有關(guān)系。 定義4.1: 設(shè)G = (VN,VT , P, S)是上下文無關(guān)文法，對于V*，V=VNVT，定義首符集FIRST()為 FIRST() = a | , aVT, ,V* 即 FIRST() = a | a, aVT, V* 特別地，若 ，則規(guī)定FIRST()，即FIRST()是能推導(dǎo)出的所有在開頭位置的終結(jié)符或空符。4.2 LL(1)文法編譯原理與技術(shù)134.2 LL(1)文法 由此我們可以看出

9、，如果文法中不含空符產(chǎn)生式，并且每個非終結(jié)符的所有候選式右部的首符集兩兩不相交，則推導(dǎo)中就不會產(chǎn)生回溯。而提取左因子正是為了達(dá)到這個目的，即反復(fù)提取左因子后，就能夠把每個非終結(jié)符（包括新引進的非終結(jié)符）的所有候選首符集變成兩兩不相交。因此，提取左因子可以使得不含空符產(chǎn)生式的文法消除回溯。編譯原理與技術(shù)144.2 LL(1)文法后繼符集FOLLOW例4.4：文法G3S: SAa | Bb Aa | cA | Bb | dB輸入串w3 = cca自頂向下的推導(dǎo)過程為：S Aa cAa ccAa cca G3與例4.3中文法G2惟一不同之處在于，G3中非終結(jié)符A的候選式中含有空符產(chǎn)生式。分析時，對于

10、輸入串w3的前兩個符號cc，可以確定使用產(chǎn)生式AcA，而要得到第三個符號a，按照a所在的首符集我們應(yīng)該選擇產(chǎn)生式Aa，但是顯然這種選擇是錯誤的，因為這樣得到的是符號串ccaa而不是cca。實際上，這時正確的選擇是產(chǎn)生式A，也就是讓A自動匹配到空符，就可以得到與輸入串匹配的符號串cca。編譯原理與技術(shù)154.2 LL(1)文法 這說明只要求文法每個非終結(jié)符的所有候選首符集兩兩不相交是不夠的，還需要進一步討論。 觀察上面例子可以看出，之所以會出現(xiàn)上述問題，是因為文法中含有空符產(chǎn)生式A，并且推導(dǎo)過程中A后面跟的終結(jié)符a恰好也是A的一個右部首符集中的符號。也就是說，a既能緊跟在A的后面出現(xiàn)，也能由A推

11、出。這樣，如果遇到當(dāng)前非終結(jié)符是A而輸入串中相應(yīng)符號為a時，就不容易確定該用產(chǎn)生式A將A自動匹配空符得到緊跟其后的a，還是用產(chǎn)生式Aa推出a。 文法G3S: SAa | Bb Aa | cA | Bb | dB編譯原理與技術(shù)16因此，一個文法能否進行確定的自頂向下語法分析，不僅僅與文法中具有相同左部的產(chǎn)生式右部的FIRST集有關(guān)系，若有產(chǎn)生式右部可能推出，則還與其左部非終結(jié)符的后繼符號集合有關(guān)。 定義4.2: 設(shè)G = (VN,VT , P, S)是上下文無關(guān)文法，對于PVN，定義后繼符集FOLLOW(P)為 FOLLOW(P) = a | S P且aFRIST(), VT*, V+ 即 FO

12、LLOW(P)=a | S Pa , aVT 。 特別地，若S P，則規(guī)定$FOLLOW(P)。即FOLLOW(P)是推導(dǎo)過程中所有可能緊跟在P之后的終結(jié)符或邊界符號$（$用來界定輸入串，表示為：$輸入串$）。4.2 LL(1)文法編譯原理與技術(shù)17 可以看出，開始符號S后面不會跟任何符號，但是有S S，因此FOLLOW(S)=$。 非終結(jié)符A后面可能不跟任何符號，即S A，也可能跟開始符號S，而S推導(dǎo)的符號串只能以a, d開頭，即FIRST(S)= a, d，因此FOLLOW(A)= a, d, $。 4.2 LL(1)文法 例4.5： 文法G4S: SaA | d AbAS |輸入串w4

13、= abd的推導(dǎo)過程為：S aA abAS abS abd編譯原理與技術(shù)18一般地，文法中含有形如P|，PVN，,V*的產(chǎn)生式時，若, 不能同時推導(dǎo)出空符，不妨設(shè) , ，則當(dāng) FIRST()( FIRST()FOLLOW(P) = 時，對于非終結(jié)符P可以確定地選取產(chǎn)生式。 4.2 LL(1)文法 比如例4.4中，產(chǎn)生式Aa | cA |，F(xiàn)OLLOW(A)=a,$， FIRST()=FIRST(a | cA)=a,c， FIRST()=FIRST()=， FIRST()( FIRST()FOLLOW(A)= a,ca,$= a 。 因此不能確定選取產(chǎn)生式。 而例4.5中，產(chǎn)生式AbAS |，F(xiàn)

14、OLLOW(A)=a,d,$， FIRST()=FIRST(bAS)=b，F(xiàn)IRST()=FIRST()=， FIRST()( FIRST()FOLLOW(A)= ba,d,$= 。 因此可以確定選取產(chǎn)生式。 編譯原理與技術(shù)19選擇集SELECT 定義4.3: 給定不含左遞歸的上下文無關(guān)文法的產(chǎn)生式P , PVN, V*，定義選擇集SELECT(P )為 若 ，則SELECT(P ) = FIRST( ) 若 ，則SELECT(P ) = (FIRST( )- )FOLLOW(P) 也就是說，當(dāng)文法中含有形如P|（PVN， , V*, , 不同時能推出）的產(chǎn)生式時，能夠使用確定的自頂向下分析必

15、須使文法滿足 SELECT(P)SELECT(P)= 4.2 LL(1)文法編譯原理與技術(shù)20 比如，例4.5中 SELECT(SaA) = FIRST(aA) = a， SELECT(Sd) = FIRST(d) = d SELECT(AbAS) = FIRST(bAS) = b， SELECT(A) = (FIRST()- )FOLLOW(A) = a,d,$ SELECT(SaA) SELECT(Sd) = ad = SELECT(AbAS) SELECT(A) = ba,d,$ = 因此，文法G4可以進行確定的自頂向下語法分析。 4.2 LL(1)文法例4.5： 文法G4S: SaA

16、| d AbAS |編譯原理與技術(shù)21LL(1)文法 定義4.4: 文法G是LL(1)文法，當(dāng)且僅當(dāng)每個非終結(jié)符P的任何兩個候選式P|（, V*）滿足： 不存在終結(jié)符a，使得和推出的符號串都能以a開頭。即FIRST()FIRST() = 若 , ，則所能推出的符號串的開頭符號不在FOLLOW(P)中。即FIRST()FOLLOW(P) = 4.2 LL(1)文法編譯原理與技術(shù)224.2 LL(1)文法 由SELECT集可以得到LL(1)文法的另一個等價定義： 定義4.5: 一個上下文無關(guān)文法是LL(1)文法，當(dāng)其僅當(dāng)對于每個非終結(jié)符P的任何兩個候選式P | 滿足SELECT( P ) SELE

17、CT( P ) = 其中PVN，, V*，且, 不同時推出。例4.6：下面文法是否是LL(1)文法？ （1）G1S: SaA | d AbAS | （2）G2S: SaAS | b AbA | 編譯原理與技術(shù)234.2 LL(1)文法 解：用定義4.4判斷（1）對于S aA | d ，F(xiàn)IRST(aA) FIRST(d)= ad= ； 對于A bAS | ，F(xiàn)IRST(bAS) FIRST()= b= ； FIRST(bAS)=b，F(xiàn)OLLOW(A)= a, d, $， FIRST(bAS) FOLLOW(A)=ba, d, $= ； 因此文法G1滿足條件, ，由定義4.4知該文法是LL(1)

18、文法。（2）對于S aA | b ，F(xiàn)IRST(aA) FIRST(b)=ab= ， 對于A bAS | ，F(xiàn)IRST(bAS) FIRST()=b= ， FIRST(bAS) = b，F(xiàn)OLLOW(A) = a, b, $ FIRST(bAS) FOLLOW(A) = ba, b, $ = b。 因此文法G2滿足條件，但不滿足條件，從而不是LL(1)文法。 編譯原理與技術(shù)244.2 LL(1)文法 用定義4.5判斷（1）SELECT(SaA) = FIRST(aA) = a SELECT(Sd) = FIRST(d) = d SELECT(AbAS) = FIRST(bAS) = b SEL

19、ECT(A) = (FIRST()- )FOLLOW(A) = a,d,$ 所以 SELECT(SaA)SELECT(Sd) = ad = SELECT(AbAS)SELECT(A) = ba,d,$ = 由定義4.5知文法G1是LL(1)文法。（2）SELECT(SaAS) = FIRST(aAS) = a SELECT(Sb) = FIRST(b) = b SELECT(AbA) = FIRST(bA) = b SELECT(A) = (FIRST()- )FOLLOW(A) = a,b,$ 所以 SELECT(SaAS)SELECT(Sb) = ab = SELECT(AbA)SELEC

20、T(A) = ba,b,$由定義4.5知文法G2不是LL(1)文法。 編譯原理與技術(shù)254.2 LL(1)文法LL(1)文法的特點沒有左因子不是二義的不含左遞歸 一個文法中若含有左遞歸和左因子，則它一定不是LL(1)文法，也就不可能用確定的自頂向下分析法。然而，某些含有左遞歸和左因子的文法可以通過等價變換，消除左遞歸和左因子后可能變?yōu)長L(1)文法，不過仍需要用LL(1)文法的定義加以判別。也就是說，文法中不含左遞歸和左因子只是LL(1)文法的必要條件。 編譯原理與技術(shù)264.3 遞歸下降分析技術(shù)基本思想為文法中每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串，當(dāng)某非終結(jié)

21、符的產(chǎn)生式有多個候選式時，按LL(1)形式唯一確定選擇哪個候選式進行推導(dǎo)，若遇到某候選式為，認(rèn)為其自動匹配。把這些遞歸過程組合起來就構(gòu)成了文法的遞歸下降分析程序。 編譯原理與技術(shù)274.3 遞歸下降分析技術(shù)遞歸下降分析器的設(shè)計 設(shè)LL(1)文法G=(VN，VT，P，S)， VN=X1，X2，Xn。對G的每個非終結(jié)符號Xi，可以按照下面方法設(shè)計子程序Pi( )： （1）對于形如Xi 1 | 2 | | m 的產(chǎn)生式，在相應(yīng)子程序Pi( )中，應(yīng)該能夠判斷當(dāng)前輸入符號a屬于哪個候選式j(luò) 的FIRST集，并轉(zhuǎn)入該候選式相應(yīng)代碼段，繼續(xù)識別。對候選式的選擇可用if語句或case語句實現(xiàn)。編譯原理與技術(shù)

22、284.3 遞歸下降分析技術(shù) （2）對于形如XiY1Y2Yk（YjVNVT）的產(chǎn)生式，相應(yīng)子程Pi( )是一個依次識別其右部各符號Yj（j=1,2,k）的過程：如果YjVT，則判斷當(dāng)前輸入符號是否與Yj匹配；若YjVN則應(yīng)有調(diào)用相應(yīng)于Yj的子程序的代碼。 （3）對于形如Xi的產(chǎn)生式，在相應(yīng)的子程序Pi( )中，應(yīng)該能夠判斷當(dāng)前輸入符號a是否屬于集合FOLLOW(Xi)，從而決定是從Pi( )返回還是報錯。 （4）在各個子程序Pi( )中，均應(yīng)含有進行語法檢查的代碼。編譯原理與技術(shù)294.3 遞歸下降分析技術(shù) 例4.8：下面文法產(chǎn)生Pascal類型的子集，我們用dotdot表示“.”，以強調(diào)這個

23、字符序列作為一個詞法單元。 type simple | id | array simple of type simple integer | char | num dotdot num 顯然該文法是LL(1)文法，為其構(gòu)造遞歸下降分析器。 編譯原理與技術(shù)304.3 遞歸下降分析技術(shù) 使用類Pascal語言為非終結(jié)符type設(shè)計子程序如下： proccdure type;begin case lookahead of in integer, char, num: simple( ) : begin match (); match (id) end array: begin match (arra

24、y); match ( ); simple( ); match ( ); match (of ); type( ) end other error( ) end caseend;編譯原理與技術(shù)314.3 遞歸下降分析技術(shù) 在這段代碼中，使用變量lookahead來存放向前查看的單詞符號，根據(jù)該單詞符號的不同而選擇不同的動作。 具體來說，如果lookaheadFIRST(simple)=integer, char, num，則轉(zhuǎn)入simple子程序；如果當(dāng)前單詞符號為，則調(diào)用匹配函數(shù)match，檢查是否匹配，若匹配則讀入下一個單詞符號，存放到變量lookahead中，然后繼續(xù)調(diào)用匹配函數(shù)matc

25、h，檢查當(dāng)前符號是否與match函數(shù)的參數(shù)id匹配，若匹配則意味著可以選取產(chǎn)生式type id；如果當(dāng)前單詞為array，則依次執(zhí)行以下操作：匹配array，匹配 ，調(diào)用simple子程序，匹配 ，匹配of，遞歸調(diào)用type子程序；如果lookahead中的單詞符號不是上述符號，則調(diào)用出錯處理函數(shù)error。編譯原理與技術(shù)324.3 遞歸下降分析技術(shù) 我們用nexttoken作為讀取下一個單詞符號的函數(shù)，則match函數(shù)的設(shè)計如下： procedure match (t : token); begin if lookahead = t then lookahead := nexttoken(

26、) else error( ) end if end;編譯原理與技術(shù)334.3 遞歸下降分析技術(shù) 類似地，給出非終結(jié)符simple的子程序如下： procedure simple; begin case lookahead of integer: match (integer) char: match (char) num: begin match (num); match (dotdot); match (num) end other error( ) end caseend;編譯原理與技術(shù)344.3 遞歸下降分析技術(shù) 這樣，我們得到了兩個非終結(jié)符的子程序，遞歸下降分析的主程序設(shè)計就比較簡單

27、了。首先需要讀入一個單詞符號，然后調(diào)用開始符號的子程序，讓其自動遞歸下降進行子過程調(diào)用。當(dāng)所有調(diào)用結(jié)束，最終回到主程序時，判斷是否到達(dá)輸入串末尾，如果到達(dá)，則分析成功，否則出錯。我們用函數(shù)gettoken讀入輸入串第一個單詞符號，則主程序偽代碼如下： begin lookahead =gettoken( ); type( ); if lookahead =$ exit; else error( ) end if end編譯原理與技術(shù)354.3 遞歸下降分析技術(shù) 將上面的各程序組合起來，就得到了該類型定義文法的遞歸下降分析器。現(xiàn)在使用該分析器分析輸入串a(chǎn)rray integer of char，

28、首先讀入第一個單詞array，然后調(diào)用開始符號type的子程序，依次進行下面操作：匹配array，讀取下一符號 ；匹配 ，讀取下一單詞integer；調(diào)用simple的子程序，匹配integer，讀取下一符號 。返回type過程，繼續(xù)進行下面操作：匹配 ，讀取下一單詞of；匹配of，讀取下一單詞char；遞歸調(diào)用type過程，因為char在integer, char, num中，所以調(diào)用simple過程，匹配char，讀取下一符號，即輸入串的結(jié)束符$。返回最近的type過程，結(jié)束操作，返回外層type過程，結(jié)束操作，返回主程序。此時變量lookahead中存放的是結(jié)束符$，因此該分析過程結(jié)束。

29、說明該輸入串符合Pascal類型定義。 編譯原理與技術(shù)364.3 遞歸下降分析技術(shù)例4.9：為下列表達(dá)式文法GE編寫遞歸下降識別程序。 E E+T | T T T*F | F F (E) | i解： 步驟1：消除左遞歸： E TE E +TE | T FT T *FT | F (E) | i 步驟2：編寫遞歸下降識別子程序，這里使用C語言形式。見下頁圖。編譯原理與技術(shù)37 編譯原理與技術(shù)384.3 遞歸下降分析技術(shù) 步驟3：編寫遞歸下降識別主程序main( ) lookahead=getsymbol( ); E( ); if lookahead =$ exit; else error( );編

30、譯原理與技術(shù)394.3 遞歸下降分析技術(shù) 使用該識別程序識別輸入串：i * i + i，首先讀入符號i，然后調(diào)用子程序E，在E中調(diào)用子程序T，在T中調(diào)用子程序F，匹配i，讀入下一符號*，子程序F調(diào)用完畢，回到T。在T中繼續(xù)調(diào)用子程序T，匹配*，讀入下一符號i。在T中繼續(xù)調(diào)用子程序F，匹配i，讀入下一符號+，回到子程序T。在T中遞歸調(diào)用子程序T，不執(zhí)行任何操作返回T，進而返回T，進而返回E。在E中繼續(xù)調(diào)用子程序E，匹配+，讀入下一符號i，調(diào)用子程序T。在T中調(diào)用子程序F，匹配i，讀入下一符號，為輸入串結(jié)束符$，返回E。在E中遞歸調(diào)用E，不執(zhí)行任何操作返回E，進而返回E。至此子程序E調(diào)用完畢，回到

31、主程序，檢查到達(dá)輸入串末尾，從而識別成功。 編譯原理與技術(shù)404.3 遞歸下降分析技術(shù) 用花括號表示閉包運算*。 用n0表示可任意重復(fù)0到n次， 特別地，n0=0= 。 用方括號表示10， 即表示可以出現(xiàn)也可以不出現(xiàn)，等價于 | 。擴充的巴科斯范式EBNF 例4.10：例4.9的表達(dá)式文法用擴充的巴科斯范式表示為：E T+T T F*F F (E) | i與每個非終結(jié)符相對應(yīng)的遞歸子程序的偽代碼如下：編譯原理與技術(shù)41 編譯原理與技術(shù)424.3 遞歸下降分析技術(shù) 使用該識別程序識別輸入串：i * i + i。首先讀入符號i，然后調(diào)用子程序E，在E中調(diào)用T，在T中調(diào)用F，匹配i，讀入下一符號*，

32、返回T。在T中匹配*，讀入下一符號i；調(diào)用F，匹配i，讀入下一符號+，返回T，返回E。在E中匹配+，讀入下一符號i，調(diào)用T。在T中調(diào)用F，匹配i，讀入下一符號，為輸入串結(jié)束符$，返回T，返回E，返回主程序。檢查到達(dá)輸入串末尾，從而識別成功。 顯然，使用EBNF編寫的遞歸子程序數(shù)量較少，分析過程也比較簡單。但是需要注意的是，將BNF轉(zhuǎn)化為EBNF通常不是一件很容易的事情。 編譯原理與技術(shù)434.3 遞歸下降分析技術(shù)遞歸下降分析的特點 優(yōu)點 實現(xiàn)思想簡單明了，程序結(jié)構(gòu)和語法規(guī)則有直接的對應(yīng)關(guān)系。由于每個過程表示一個非終結(jié)符號的處理，添加語義加工工作比較方便。遞歸下降分析需要書寫程序的語言支持遞歸調(diào)

33、用，如果遞歸調(diào)用機制是高效的，那么分析程序也是高效的。編譯原理與技術(shù)444.3 遞歸下降分析技術(shù)缺點遞歸下降分析對文法要求比較高，必須滿足LL(1)文法。 當(dāng)然在某些語言中個別產(chǎn)生式的推導(dǎo)當(dāng)不滿足LL(1)而滿足LL(2)時，也可以采用多向前掃描一個符號的辦法。由于遞歸調(diào)用多，所以速度慢，占用空間多。 盡管如此，遞歸下降分析方法仍是許多程序語言（例如PASCAL，C等編譯系統(tǒng)）常常采用的語法分析方法。編譯原理與技術(shù)454.4 預(yù)測分析技術(shù) 預(yù)測分析程序的工作過程 一個預(yù)測分析器由預(yù)測分析程序(總控程序)、先進后出棧(STACK)、預(yù)測分析表三個部分組成，其中只有預(yù)測分析表與文法有關(guān)，它是一個二

34、維矩陣，存放非終結(jié)符X面臨輸入符號a時應(yīng)選擇的產(chǎn)生式，一般用MX, a表示，是預(yù)測分析程序分析時的主要依據(jù)。 編譯原理與技術(shù)464.4 預(yù)測分析技術(shù) 圖4.2 預(yù)測分析器模型編譯原理與技術(shù)474.4 預(yù)測分析技術(shù)預(yù)測分析程序開始時，將$置入STACK棧，將開始符號S置入STACK棧，將第一個輸入符號讀入a，將棧頂符號讀入X?？偪爻绦驁?zhí)行下面四種動作之一。（1）推導(dǎo) 若XVN，并且MX, a中存有產(chǎn)生式X X1X2Xk，則X 出棧，X1, X2, , Xk反序置入STACK棧（X 時直接將X出棧即可）；（2）匹配 若X=a$，則X出棧，把下一輸入符號讀入a。（3）接受 若X=a=$，則分析成功，

35、停止分析過程。（4）出錯 若XVT，但Xa，或者若XVN，但MX, a 中存放出錯標(biāo)記error，則報告出錯。編譯原理與技術(shù)484.4 預(yù)測分析技術(shù) 預(yù)測分析程序工作示意圖 編譯原理與技術(shù)494.4 預(yù)測分析技術(shù)算法4.1 非遞歸的預(yù)測分析輸入： 輸入串w和文法GS的分析表M輸出： 如果wL(G), 輸出w的最左推導(dǎo)，否則報告錯誤。$ S進棧, S在棧頂, w$在輸入緩沖區(qū), ip指向w$的第一個符號; /準(zhǔn)備工作flag:=true /flag作為控制標(biāo)記while flag do 令X等于棧頂符號, a等于ip指向的符號; if XVN then do if MX, a = X Y1Y2

36、Yk then do 從棧中彈出X; 把Yk,Yk1, , Y1依次壓入棧, Y1在棧頂; 輸出產(chǎn)生式X Y1Y2 Yk else error ( ) /報告錯誤 else if X = a then do if X=$ then flag:=false /結(jié)束循環(huán) else 把X從棧頂彈出, ip指向下一符號 else error ( )end while;編譯原理與技術(shù)504.4 預(yù)測分析技術(shù)預(yù)測分析表的構(gòu)造 構(gòu)造FIRST集 首先求出文法中每個文法符號的首符集，即為XVTVN構(gòu)造FIRST(X)。方法如下：若XVT，則FIRST(X)=X；若XVN，且有產(chǎn)生式X a，則FIRST(X)=

37、 FIRST(X)a。 特別地，若有產(chǎn)生式X，則FIRST(X)= FIRST(X)；編譯原理與技術(shù)514.4 預(yù)測分析技術(shù)若XVN，且有產(chǎn)生式X Y1Y2Yk，(i=1, 2, , k)，則 若 1ik，使得FIRST(Yj)， (j=1, 2, , i-1)，即Y1Y2Yi-1 ，則FIRST(X)= FIRST(X)(FIRST(Yj)- )； 若 1ik，都有FIRST(Yj)，則FIRST(X)= FIRST(X)反復(fù)利用以上規(guī)則，直到FIRST(X)不再增大為止。然后求符號串的首符集FIRST ()，算法如下：編譯原理與技術(shù)524.4 預(yù)測分析技術(shù)算法4.2 求符號串的首符集FIR

38、ST ()輸入： 文法G, 符號串=X1X2Xn及FIRST(Xi), 其中Xi(VNVT), 1i n輸出： 首符集FIRST ()FIRST()=, k=0for i = 1 to n do if FIRST(Xi) then 置FIRST()=FIRST()(FIRST(Xi)-) 且 k=k+1 else 置FIRST()=FIRST()FIRST(Xi) 結(jié)束循環(huán)end for；if k=n then 置FIRST()=FIRST()編譯原理與技術(shù)534.4 預(yù)測分析技術(shù)例4.11：文法GS: S AB | bC A b | B aD | CAD | b D aS | c 各非終結(jié)符

39、的首符集為： FIRST(D)=a, c FIRST(B)=a, FIRST(A)=b, FIRST(C) = (FIRST(A)-) FIRST(D) b=a, b, c FIRST(S) = (FIRST(A)-) (FIRST(B)-) b = a, b, 符號串AB的首符集為： FIRST(AB)= (FIRST(A)-) (FIRST(B)-) = a, b, 考慮產(chǎn)生式SAB | bC，因為 FIRST(AB) FIRST(bC)= a, b, b ， 由定義4.6可知，該文法不是LL(1)文法。 編譯原理與技術(shù)544.4 預(yù)測分析技術(shù)構(gòu)造FOLLOW集若P是文法開始符號，則FOL

40、LOW(P)=$；若有產(chǎn)生式PQ，則FOLLOW(Q)= FOLLOW(Q) ( FIRST()-)若有產(chǎn)生式PQ，或者有產(chǎn)生式PQ而，即FIRST()，則FOLLOW(Q)= FOLLOW(Q) FOLLOW(P)反復(fù)使用上面規(guī)則，直到每個FOLLOW集不再增大為止。編譯原理與技術(shù)554.4 預(yù)測分析技術(shù)算法4.3 求非終結(jié)符后繼集FOLLOW輸入： 文法GS及FIRST(X), 所有X(VNVT)輸出： 所有非終結(jié)符的后繼集FOLLOWFOLLOW (S)=$FOLLOW (P)=, 所有PVN, PSfor 每一個產(chǎn)生式 do if 該產(chǎn)生式形如PQ then 置 FOLLOW(Q)=

41、FOLLOW(Q) ( FIRST()-) if then 置FOLLOW(Q)= FOLLOW(Q) FOLLOW(P) if 該產(chǎn)生式形如PQ then 置 FOLLOW(Q)= FOLLOW(Q) FOLLOW(P)end for；編譯原理與技術(shù)564.4 預(yù)測分析技術(shù)例4.12：仍討論例4.11文法GS: S AB | bC A b | B aD | CAD | b D aS | c 所有非終結(jié)符求FOLLOW集過程如下： FOLLOW(S)=$FOLLOW(D) FOLLOW(A)=aa,cFOLLOW(S) FOLLOW(B)=FOLLOW(S) FOLLOW(C)=FOLLOW(

42、S) FOLLOW(D)=FOLLOW(B)FOLLOW(C) 從FOLLOW(S)=$開始，不斷循環(huán)求解直到所有FOLLOW集不再增大，最后可得： FOLLOW(S)= $ FOLLOW(A)= a, c, $ FOLLOW(B)= $ FOLLOW(C)= $ FOLLOW(D)= $編譯原理與技術(shù)574.4 預(yù)測分析技術(shù)構(gòu)造SELECT集 算法4.4 求選擇集SELECT輸入： 文法GS及FIRST(X), 所有X(VNVT), FOLLOW(P), 所有PVN輸出： 所有產(chǎn)生式的選擇集SELECTfor 每一個產(chǎn)生式P , PVN, V* do if then 置SELECT(P )

43、= FIRST( ) if then 置SELECT(P ) = (FIRST( )- )FOLLOW(P)end for；編譯原理與技術(shù)584.4 預(yù)測分析技術(shù)例4.13：例4.11中文法GS: S AB | bC A b | B aD | C AD | b D aS | c 對所有產(chǎn)生式求SELECT集的過程為： SELECT(SAB)=FIRST(AB) FOLLOW(S)= b, a, $ SELECT(SbC)=FIRST(bC)=b SELECT(A)=FIRST()FOLLOW(A)= a, c, $ SELECT(Ab)=FIRST(b)=b SELECT(B)=FIRST()

44、FOLLOW(B)=$ SELECT(BaD)=FIRST(aD)=a SELECT(CAD)=FIRST(AD)= a, b, c SELECT(Cb)=FIRST(b)=b SELECT(DaS)=FIRST(aS)=a SELECT(Dc)=FIRST(c)=c編譯原理與技術(shù)594.4 預(yù)測分析技術(shù) 由以上計算結(jié)果可得相同左部產(chǎn)生式的SELECT交集為： SELECT(SAB)SELECT(SbC)= b, a, $ b=b SELECT(A)SELECT(Ab)= a, c, $ b= SELECT(B)SELECT(BaD)=$a= SELECT(CAD)SELECT(Cb) b,

45、a, c bb SELECT(DaS)SELECT(Dc)=ac 由LL(1)文法定義知該文法不是LL(1)文法，因為關(guān)于S和C的相同左部其產(chǎn)生式的SELECT集的交集不為空。 編譯原理與技術(shù)604.4 預(yù)測分析技術(shù)例4.14：文法GE: ETE E +TE | T FT T *FT | F (E) | i 求所有非終結(jié)符的FIRST集和FOLLOW集，以及所有產(chǎn)生式的SELECT集，并判斷是否是LL(1)文法。 編譯原理與技術(shù)614.4 預(yù)測分析技術(shù) 所有非終結(jié)符的FIRST集： FIRST ( E ) = (, i FIRST ( E ) = +, FIRST ( T ) = (, i F

46、IRST ( T ) = *, FIRST ( F ) = (, i 文法GE: ETE E +TE | T FT T *FT | F (E) | i編譯原理與技術(shù)624.4 預(yù)測分析技術(shù) 所有非終結(jié)符的FOLLOW集： FOLLOW ( E ) = ),$ FOLLOW ( E ) = ),$ FOLLOW ( T ) = +, ), $ FOLLOW ( T ) = +, ), $ FOLLOW ( F ) = *, +, ),$ 文法GE: ETE E +TE | T FT T *FT | F (E) | i編譯原理與技術(shù)634.4 預(yù)測分析技術(shù) 所有產(chǎn)生式的SELECT集為： SELE

47、CT( E TE )=(, i SELECT( E +TE )=+ SELECT( E )= ), $ SELECT( T FT )= (, i SELECT( T *FT )= * SELECT( T )= +, ), $ SELECT( F (E) )= ( SELECT( F i ) i 是LL(1)文法。 文法GE: ETE E +TE | T FT T *FT | F (E) | i編譯原理與技術(shù)644.4 預(yù)測分析技術(shù)構(gòu)造預(yù)測分析表M 方法一：對每個產(chǎn)生式P討論SELECT(P)，將P放入預(yù)測分析表M中非終結(jié)符P所在的行，SELECT(P)中每個終結(jié)符a所在的列。所有產(chǎn)生式都討論過

48、之后，表中沒有產(chǎn)生式的地方放入出錯標(biāo)記。構(gòu)造算法如下：編譯原理與技術(shù)654.4 預(yù)測分析技術(shù)算法4.5 構(gòu)造預(yù)測分析表輸入： 文法GS所有產(chǎn)生式的SELECT集輸出： 預(yù)測分析表Mfor 每一個產(chǎn)生式P do for 每個終結(jié)符aSELECT(P) do 把P放入MP, a end for;end for;把所有無定義的MP, a標(biāo)上出錯標(biāo)記。 編譯原理與技術(shù)664.4 預(yù)測分析技術(shù) 方法二：對每個產(chǎn)生式P先討論FIRST()，將P放入預(yù)測分析表M中非終結(jié)符P所在的行，F(xiàn)IRST()中每個終結(jié)符a所在的列。然后看FIRST()中是否有空符，若有，則討論FOLLOW(P)，將P放入預(yù)測分析表M中

49、非終結(jié)符P所在的行、FOLLOW(P)中每個終結(jié)符b所在的列。所有產(chǎn)生式都討論過之后，表中沒有產(chǎn)生式的地方放入出錯標(biāo)記。構(gòu)造算法如下： 編譯原理與技術(shù)674.4 預(yù)測分析技術(shù)算法4.6 構(gòu)造預(yù)測分析表輸入： 文法GS所有非終結(jié)符的FIRST集和FOLLOW集輸出： 預(yù)測分析表Mfor 每一個產(chǎn)生式P do for 每個終結(jié)符aFIRST() do 把P放入MP, a end for; if FIRST() then for 每個bFOLLOW(P) do 把P放入MP, a end for;end for;把所有無定義的MP, a標(biāo)上出錯標(biāo)記error。 編譯原理與技術(shù)684.4 預(yù)測分析技術(shù)

50、例4.12: 利用例4.14中所求得的FIRST集FOLLOW集和SELECT集，按照算法4.5和算法4.6均可構(gòu)造出文法GE的預(yù)測分析表，如表4.1所示，其空白處均為出錯標(biāo)記error。 i+*()$EETEETEEE +TEEETT FTT FTTTT *FTTTFF iF (E)表4.1：例4.14的預(yù)測分析表M編譯原理與技術(shù)69利用該預(yù)測分析表分析輸入串i+i*i，其過程為： 分析步驟STACK棧剩余輸入符號串動作/使用的產(chǎn)生式（1）$ Ei+i*i $推導(dǎo)/ E TE（2）$ E Ti+i*i $推導(dǎo)/ T FT（3）$ E T Fi+i*i $推導(dǎo)/ F i（4）$ E T ii+i*i $匹配（5）$ ET+i*i $推導(dǎo)/ T（6）$ E+i*i $推導(dǎo)/E +TE（7）$ E T +i*i $匹配（8）$ E Ti*i $推導(dǎo)/ T FT（9）$ E T