第5章 自頂向下語法分析方法3

1、第第5章章 自頂向下語法分析方法自頂向下語法分析方法考查重點考查重點1.自上而下語法分析的基本思想自上而下語法分析的基本思想2.求求FIRST、FOLLOW、SELECT集合集合的方法的方法3.提取左公因子提取左公因子與與消除左遞歸消除左遞歸的方法的方法4.遞歸下降分析程序的構(gòu)造遞歸下降分析程序的構(gòu)造5.LL(1)文法的判定，分析表的構(gòu)造與文法的判定，分析表的構(gòu)造與輸入串的分析過程輸入串的分析過程語法分析的任務(wù)語法分析的任務(wù) 1.語法分析是編譯過程的語法分析是編譯過程的核心核心部分部分。 2.語法分析的作用語法分析的作用：識別由詞法分析輸出的單詞序列是否符合該語言的文法文法（？）正確句子（程序

2、）。3.分析方法分析方法 自頂向下分析法自頂向下分析法(確定確定與不確定不確定 )從推導(dǎo)的角度看，從識別符號出發(fā)，試圖推導(dǎo)出與輸入符號串相同的符號串。一般來講，推導(dǎo)是最左推導(dǎo)最左推導(dǎo)。構(gòu)造推導(dǎo)的構(gòu)造推導(dǎo)的關(guān)鍵問題關(guān)鍵問題: 在構(gòu)造最左推導(dǎo)的過程中,面對當(dāng)前讀入的單詞符號面對當(dāng)前讀入的單詞符號(向向前前看符號)和當(dāng)前被替換的非終結(jié)符兩者當(dāng)前被替換的非終結(jié)符兩者,應(yīng)該選擇這個應(yīng)該選擇這個非終結(jié)符的哪條候選式去替換它非終結(jié)符的哪條候選式去替換它(推導(dǎo)推導(dǎo))。自底向上分析法自底向上分析法（算符優(yōu)先算符優(yōu)先、LR分析器分析器）1.確定確定的自頂向下的分析方法的自頂向下的分析方法 在推導(dǎo)過程中，可以完全根

3、據(jù)向完全根據(jù)向前前看符號看符號唯一唯一決定選擇哪個產(chǎn)生式往下推導(dǎo)選擇哪個產(chǎn)生式往下推導(dǎo)，因此,分析過程是完全確定的。這種分析稱為確定的自頂向下分析方法。 特征特征根據(jù)下一個輸入符號下一個輸入符號為當(dāng)前要處理的非終結(jié)符選擇產(chǎn)生式 要求要求文法是LL(1)的 u第一個L從左到右掃描輸入串左到右掃描輸入串 u第二個L 生成的是最左推導(dǎo)左推導(dǎo) u向前前看一個輸入符號（lookahead) 5.1 確定的自頂向下分析思想確定的自頂向下分析思想例例1：文法文法G1S:SpA|qBAcAd|aBdB|b w=pccadd自頂向下的推導(dǎo)過程：自頂向下的推導(dǎo)過程：S S pApA pcAdpcAd pccAdd

4、pccAdd pccaddpccadd 思考：思考：該文法的特點？該文法的特點？ 2型文法且無空產(chǎn)生式無空產(chǎn)生式。 如果兩個產(chǎn)生式有相同左部，那么它們右部由不同終結(jié)不同終結(jié)符或非終結(jié)符符或非終結(jié)符開始。例例2：文法文法G2S:SAp|BqAa|cABb|dBw=ccap自頂向下的推導(dǎo)過程：自頂向下的推導(dǎo)過程：S S ApAp cApcAp ccApccAp ccapccap分析能分析能確定確定推導(dǎo)原因：推導(dǎo)原因：前提前提：2型文法中型文法中無空產(chǎn)生式無空產(chǎn)生式 在文法中，對于每個非終結(jié)符在文法中，對于每個非終結(jié)符A的定義的定義 A1|2|.|n 任給任給i,j(1i,jn,ij),從從i和和j

5、推導(dǎo)出來的推導(dǎo)出來的第一個第一個終結(jié)符號集合終結(jié)符號集合(稱為開始符號集稱為開始符號集FIRST)不相交不相交,即即:FIRST(i)FIRST(j)= 結(jié)論結(jié)論 ： 在推導(dǎo)過程中完全可以根據(jù)向在推導(dǎo)過程中完全可以根據(jù)向前前看符號看符號是是屬于哪個產(chǎn)生式右部的開始符號集合屬于哪個產(chǎn)生式右部的開始符號集合而決定選而決定選擇相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)，因此，擇相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)，因此，分析過程是完分析過程是完全確定的全確定的。FIRST定義定義：設(shè) G = (VT ,VN , S , P) 是2型型文法，F(xiàn)IRST() = a| a,a VT, V*若若 ，則規(guī)定則規(guī)定FIRST()直觀定義理解直觀定

6、義理解： FIRST()=a a ，aT FIRST()包含了對應(yīng)的串的所有可能的首終結(jié)所有可能的首終結(jié)符號集符號集(選擇產(chǎn)生式的依據(jù)選擇產(chǎn)生式的依據(jù)) *如例如例2文法文法G2S:SAp|BqAa|cABb|dBw=ccap自頂向下的推導(dǎo)過程：自頂向下的推導(dǎo)過程：S S ApAp cApcAp ccApccAp ccapccap選擇選擇S S的產(chǎn)生式的依據(jù)的產(chǎn)生式的依據(jù)FIRST(Ap)=a,c FIRST(Bq)=b,d思考：思考：FIRSTFIRST（S S）= =？意味？意味？例例3 文法文法G3S:SaASdAbASAw=abd試圖試圖推導(dǎo)的過程：推導(dǎo)的過程：S S aAaA aba

7、bA AS S abSabS abdabd選擇選擇A的的產(chǎn)生式的依據(jù)產(chǎn)生式的依據(jù)FIRST(bAS)=b FIRST()=分析：分析：無無d，但若但若A為為，則，則A的后面能推出的后面能推出d思考：思考：若若A有一條有一條產(chǎn)生式能推出產(chǎn)生式能推出，則需要尋找什么則需要尋找什么？FOLLOW(A)定義：設(shè)定義：設(shè) G = (VT ,VN , S , P) 是上下文無關(guān)是上下文無關(guān)文法，文法，AVN , S是開始符號。是開始符號。 FOLLOW(A) = a|a|S S A A 且且a aFIRST(FIRST( ),), VVT T* *, , VV+ + 若若S S A A ,且且 ，則規(guī)定，

8、則規(guī)定 #FOLLOW(A)直觀定義理解直觀定義理解： FOLLOW(A)=aS Aa，aT 若S A，則規(guī)定 #FOLLOW(A) #作為輸入串的結(jié)束符，或稱為句子括號，如： #輸入串#FOLLOW(A)表示句型中表示句型中可能緊跟在可能緊跟在A后面的終結(jié)符后面的終結(jié)符號號 例例：G3S: SaA|d AbAS| 求求FOLLOW(A) =？* 2型文法中型文法中對于對于 A A其中其中AVN , ,VN*， 當(dāng)當(dāng)和和不同時推導(dǎo)出空時（設(shè)不同時推導(dǎo)出空時（設(shè) 不推導(dǎo)出空，不推導(dǎo)出空，推導(dǎo)出推導(dǎo)出空），則當(dāng)空），則當(dāng)FIRST()(FIRST()FOLLOW(A)=時，對于時，對于非終結(jié)符非終

9、結(jié)符A的替換的替換仍可仍可唯一地確定候選唯一地確定候選。w=abd試圖試圖推導(dǎo)的過程：推導(dǎo)的過程：S S aAaA ababA AS S abSabS abdabd選擇選擇A的的產(chǎn)生式的依據(jù)產(chǎn)生式的依據(jù)FIRST(bAS)=b FIRST() FOLLOW(A) = ,a,d,#例例3 文法文法G3S:SaASdAbASA思考思考： 若若2型文法中含有型文法中含有產(chǎn)生式，如何唯一確定候產(chǎn)生式，如何唯一確定候選產(chǎn)生式？選產(chǎn)生式？SELECT定義：給定上下文無關(guān)文法的產(chǎn)生式A，AVN , V*，若 ，則SELECT(A)=FIRST() 如果 ，則 SELECT(A)=FIRST()-FOLLOW

10、(A) P72SELECT(A) 表示選擇此產(chǎn)生式得到的終結(jié)符號集表示選擇此產(chǎn)生式得到的終結(jié)符號集定義定義：一個上下文無關(guān)文法是LL(1)文法文法充要條件：對每個非終結(jié)符A兩個不同產(chǎn)生式A和A，滿足：SELECT(A)SELECT(A)=其中,不能同時 第一個第一個L：自頂向下分析是：自頂向下分析是從左向右掃描從左向右掃描輸入串。輸入串。第二個第二個L：分析過程中將用：分析過程中將用最左推導(dǎo)最左推導(dǎo)。 1：只需：只需向右看一個符號向右看一個符號可決定選擇哪個產(chǎn)生式進(jìn)行推導(dǎo)?？蓻Q定選擇哪個產(chǎn)生式進(jìn)行推導(dǎo)。*例例：文法：文法GS是否是是否是LL(1)文法文法? SaA|d AbAS| SELECT

11、(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#SELECT(SaA) SELECT(Sd) =ad=SELECT(AbAS)SELECT(A) =ba,d,#=所以該文法是所以該文法是LL(1)文法文法。例例：設(shè)文法：設(shè)文法GS 為為:SaAS|bAbA|SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,bSELECT(SaAS) SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b所以該文法所以該文法不是不是LL(1)文法。文法。思考思考：輸入串：輸入串 #ab#的

12、推導(dǎo)？的推導(dǎo)？ 例例文法：文法：GSGS: :SaAS|SaAS|b bAbA|AbA|對輸入串對輸入串w=w=a ab b進(jìn)行推導(dǎo)：進(jìn)行推導(dǎo)：S S a aA AS S aSaS ababS S a aA AS S abASabAS abSabS出錯出錯 正確正確說明說明：只有只有是是LL(1)文法，文法，自頂而下方法自頂而下方法分析才是分析才是確定確定的的SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b5.2 LL(1)文法的判別文法的判別1.求出能推出求出能推出的非終結(jié)符的非終結(jié)符2.計算計算FIRST集集3.計算計算FOLLOW集

13、集4.計算計算SELECT集集5.判別是否是判別是否是LL(1)文法文法1.求出能推出求出能推出的非終結(jié)符的非終結(jié)符SABSbCAAbBBaDCADCbDaSDc非終結(jié)符非終結(jié)符SABCD初值初值未定未定未定未定未定未定未定未定未定未定第一次掃描第一次掃描是是是是否否第二次掃描第二次掃描是是否否能推出能推出的非終結(jié)符的非終結(jié)符: S、A、D例例：設(shè)文法：設(shè)文法GS :判斷否是判斷否是LL(1)文法？文法？2.計算計算FIRST集集若若X X V V , ,則則FIRST(X)=XFIRST(X)=X若若X X V VN N, ,且有產(chǎn)生式且有產(chǎn)生式X Xa a，則則aaFIRST(X)FIRS

14、T(X); ;若若X X也是一條產(chǎn)生式也是一條產(chǎn)生式, ,則則 FIRST(X)FIRST(X). .若若XY是一個產(chǎn)生式且是一個產(chǎn)生式且Y VN,則把則把FIRST(Y)中的中的所有非所有非 元元素都加到素都加到FIRST(X)中中; 若若X Y1Y2YK 是一個產(chǎn)生式是一個產(chǎn)生式,Y1,Y2,Y(k-1)都都是非終結(jié)符是非終結(jié)符,而且而且,對于任何對于任何j,1j k-1,FIRST(Yj)都都含有含有 (即即Y1.Y(k-1) ),則把則把FIRST(Yj)中的所有中的所有非 元素與元素與FIRST(Yk)都加到都加到FIRST(X)中中; 特別是特別是,若所有的若所有的FIRST(Yj

15、, j=1,2,K)均含有均含有 ,則則把把 加到加到FIRST(X)中中. (注意第注意第3點點）SABSbCAAbBBaDCADCbDaSDcFIRST(D)=a,cFIRST(AD)=(FIRST(A)-) FIRST(D)=a,b,cFIRST(S)=FIRST(AB) b=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)= FIRST(AD) b=a,b,cFIRST(AB)=(FIRST(A)-) (FIRST(B)-) =a,b,說明說明：找出：找出所有所有關(guān)于含某個非終結(jié)符的關(guān)于含某個非終結(jié)符的左部左部的的產(chǎn)生式，產(chǎn)生式，結(jié)合右部特點結(jié)合右部特點，求，求

16、FIRST。3.計算計算FOLLOW集集對于文法的對于文法的開始符號開始符號S, ,置置#于于FOLLOW(FOLLOW(S) ) 中中; ; 若若B是一個產(chǎn)生式是一個產(chǎn)生式,則把則把FIRST()- 加至加至FOLLOW(B)中中; 若若B是一個產(chǎn)生式是一個產(chǎn)生式,或或B是一個產(chǎn)生是一個產(chǎn)生式，而式，而 (即即 FIRST()），），則把則把FOLLOW（A）加至加至FOLLOW（B）中中 (第第3點舉例說明點舉例說明）文法文法G3S:SaAe|AdAbB|bBfBc思考思考：FOLLOW(S) =FOLLOW(A) = e,dFOLLOW(B) = f,.?SABSbCAAbBBaDCAD

17、CbDaSDcFOLLOW(S)=#FOLLOW(D)FOLLOW(A)=aa,cFOLLOW(S) /？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(D)= #說明說明：找出：找出所有所有關(guān)于含某個非終結(jié)符的關(guān)于含某個非終結(jié)符的右部右部的的產(chǎn)生式，產(chǎn)生式，結(jié)合右部特點結(jié)合右部特點，求，求FOLLOW。4.計算計算SELECT集集SABSbCAAbBBaDCADCbDaSDcFIRST(

18、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)= #該文法該文法不不是是LL(1)文法。文法。SELECT(Dc)=cSELECT(DaS)=aSELECT(Cb)=bSELECT(CAD)=a,b,cSELECT(BaD)=aSELECT(B)=#SELECT(Ab)=bSELECT(A)=a,c,#SELECT(

19、SbC)=b5.3某些非某些非LL(1)文法到文法到LL(1)文法的等價變換文法的等價變換n提取左公共因子提取左公共因子n消除左遞歸消除左遞歸一、提取左公共因子一、提取左公共因子A|導(dǎo)致導(dǎo)致SELECT(A) SELECT(A)，因此非因此非LL(1)文法。文法。A1|2|n 變換為變換為A(1|2|n) ，然后：然后：AAA 1|2|n等價變換為等價變換為A(|)，然后：然后：AAA |例例1：G1S :SaSbSaSSSaS(b|)SSaSAS AbA思考思考：G1與與G2提取左公共因子提取左公共因子結(jié)果是結(jié)果是LL(1)文法？。文法？。結(jié)論結(jié)論：文法中不含左公共因子只是：文法中不含左公共

20、因子只是LL(1)文法文法必要條件必要條件 G2S ： AadABcBaABbBAadAaAcAbBcBaABbBAa(d|Ac)AbBcBaABbBAaA AbBcAdAAcBaABbB例例3：文法G3S 為:SaSdSAcAaSAb1.化為：化為：SaSdSaScSbc AaSAb2.化為：化為：SaS(d|c)Sbc AaSAb3.化為：化為：SaSA SbcAdAcAaSAb結(jié)果中結(jié)果中A是不可達(dá)到的符號。是不可達(dá)到的符號。例例4：文法：文法G4S :SAp|BqAaAp|dBaBq|e1.化為：化為：SaApp|aBqq|dq|eqAaAp|dBaBq|e2.化為：化為：Sa(App

21、|Bqq)Sdq|eqAaAp|dBaBq|e3.化為：化為：SaS Sdq|eqSApp|BqqAaAp|dBaBq|e4.化為：化為：SaS Sdq|eqS aAppp|aBqqq|dpp|eqqAaAp|dBaBq|en利用提取左利用提取左公共因子公共因子無無法在有限步法在有限步驟內(nèi)驟內(nèi)替換成替換成無左公共因無左公共因子的文法子的文法結(jié)論結(jié)論不一定每個文法的左公共因子都能在有限的不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。步驟內(nèi)替換成無左公共因子的文法。一個文法提取了左公共因子后，一個文法提取了左公共因子后，只解決了只解決了相同左部產(chǎn)生式右部的相同左部產(chǎn)生式右部

22、的FIRST集不相交問集不相交問題題，當(dāng)改寫后的，當(dāng)改寫后的文法不含空產(chǎn)生式文法不含空產(chǎn)生式，且，且無無左遞歸時左遞歸時，則改寫后的文法是，則改寫后的文法是LL(1)文法，文法，否則還需用否則還需用LL(1)文法的判別方式進(jìn)行判斷文法的判別方式進(jìn)行判斷才能確定是否為才能確定是否為LL(1)文法。文法。二、消除左遞歸二、消除左遞歸1.直接左遞歸直接左遞歸：AA A VN, V*例例：文法G5含有直接左遞歸：SSa|b所能產(chǎn)生的語言L=ban|n0輸入串baaaa#是該語言句子，但如何用自頂向下分析呢？2.間接左遞歸間接左遞歸：ABBA A,B VN, , V*例例：文法G6含有間接左遞歸：AaB

23、|BbBAc|d消除直接左遞歸消除直接左遞歸方法方法：把直接左遞歸改寫為右遞歸右遞歸。如如G5: SSa Sb(L=ban|n0) 改為（必須確保語言不變必須確保語言不變） ：SbSSaS| /必須掌握此種方式！必須掌握此種方式！消除直接左遞歸的一般方法消除直接左遞歸的一般方法： AA1| A2| Am|1|2|n其中：其中： i 不等于不等于 ， j不以不以A開頭開頭。改為改為：A 1A| 2A | nA A 1A | 2A | mA |消除間接左遞歸消除間接左遞歸方法：方法：將間接左遞歸變?yōu)橹苯幼筮f歸將間接左遞歸變?yōu)橹苯幼筮f歸消除直接左遞歸。消除直接左遞歸。例例文法文法G6含有間接左遞歸：

24、含有間接左遞歸： AaBABbBAcBd 注意：注意：A的取代要全面！的取代要全面！AaBABb BaBcBBbcBdAaBABbBaBcB | dB BbcB| 消除文法中一切左遞歸的算法（消除文法中一切左遞歸的算法（自己看自己看）n充分條件：充分條件：1.無回路無回路(A(A (A) 2.無空產(chǎn)生式無空產(chǎn)生式+n（3）化簡由化簡由2得到的文法得到的文法n（2） for i:=1 to n do for j:=1 to i-1 do 用用Ai- 1r| 2r| k r替代替代 形如形如Ai- Ajr的規(guī)則的規(guī)則,其中其中 Aj- 1| 2| k是關(guān)于是關(guān)于Aj的全部產(chǎn)生式的全部產(chǎn)生式; n

25、消除消除Ai規(guī)則的規(guī)則的直接左遞歸直接左遞歸; n n（1） 以某種順序?qū)⑽姆ǚ墙K結(jié)符排列以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1 ,A2 An例例：n文法G:SQc|cQRb|bRSa|aR Qca|ca|aR Rbca|bca|ca|aR (bca|ca|a)R R bcaR|參考P.84n最終文法：（非終結(jié)符最終文法：（非終結(jié)符排序為排序為S、Q、R）SQc|cQRb|bR (bca|ca|a)RR bcaR|（非終結(jié)符排序為（非終結(jié)符排序為R、Q、S）?n文法G:SQc|cQRb|bRSa|aQSab|ab|bSSabc|abc|bc|cS(abc|bc|c)SSabcSQSab|ab|bRS

26、a|an最終文法：（非終結(jié)符最終文法：（非終結(jié)符排序為排序為R、Q、S ） S(abc|bc|c)S SabcS5.4不確定的自頂向下分析思想（不確定的自頂向下分析思想（了解了解）n1.由于相同左部的產(chǎn)生式的右部由于相同左部的產(chǎn)生式的右部FIRST集交集不為空引起回溯。集交集不為空引起回溯。SxAyAab|aw=xaySx A ySx A ya bSx A ya試探試探回溯回溯試探試探n2.由于相同左部非終結(jié)符的右部能由于相同左部非終結(jié)符的右部能 且該且該非終結(jié)符非終結(jié)符FOLLOW集中含有其右部集中含有其右部FIRST集的元素。集的元素。n設(shè)文法設(shè)文法GS 為為:SaASSbAbASA*w=

27、ab#Sa A SSa A Sb A SSa A S b試探再試探回溯n3.由于文法含有左遞歸而引起回溯。由于文法含有左遞歸而引起回溯。n設(shè)文法設(shè)文法GS 為為:SSaSbw=baa#SbSS aSS abSS aS aSS aS ab5.5 確定的自頂向下分析方法確定的自頂向下分析方法1.遞歸子程序法遞歸子程序法u前提前提 ：LL(1)文法文法 u實現(xiàn)思想實現(xiàn)思想： 識別程序由一組函數(shù)組成。識別程序由一組函數(shù)組成。每個函數(shù)對應(yīng)于一個每個函數(shù)對應(yīng)于一個非終結(jié)符號非終結(jié)符號。 每一個函數(shù)的功能是：選擇正確的右部，掃描完每一個函數(shù)的功能是：選擇正確的右部，掃描完相應(yīng)的串。在右部中有非終結(jié)符號時，調(diào)

28、用該終結(jié)相應(yīng)的串。在右部中有非終結(jié)符號時，調(diào)用該終結(jié)符號對應(yīng)的函數(shù)來完成。符號對應(yīng)的函數(shù)來完成。u限制限制：對文法要求高，必須滿足：對文法要求高，必須滿足LL(1)文法；由于文法；由于遞歸調(diào)用多，速度慢，占用空間多。遞歸調(diào)用多，速度慢，占用空間多。例例：對于產(chǎn)生式 E-TE 用E1表示E E() if(當(dāng)前符號可能是T的開始符號) T(); E1(); else error(); 例例：對于產(chǎn)生式 E-+TE|e 用E1表示E E1() if(ch=+) getnextchar(); T(); E1()； else if(ch=e) return； else error(); 2.預(yù)測分析法預(yù)

29、測分析法(1)預(yù)測分析程序預(yù)測分析程序 （P.88）(2) 分析棧分析棧 (3) 預(yù)測分析表預(yù)測分析表預(yù)測分析表的構(gòu)造預(yù)測分析表的構(gòu)造例例：表達(dá)式文法：表達(dá)式文法E E+T | T T T*F | F F i | ( E )(1).判斷文法是否為判斷文法是否為LL(1)文法文法 a、消除左遞歸消除左遞歸/提取左公因子提取左公因子：E E+T | TT T*F | FF i | ( E )E TEE +TE | T FTT *FT | F i | ( E )b、推出推出 的非終結(jié)符表的非終結(jié)符表：EETTF否否是是否否是是否否c、各非終結(jié)符的各非終結(jié)符的FIRST集合如下集合如下：FIRST(E

30、)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( , i E TEE +TE | T FTT *FT | F i | ( E )查看FOLLOW定義查看FIRST定義d、各非終結(jié)符的各非終結(jié)符的FOLLOW集合如下集合如下：FOLLOW(E)= ) , # FOLLOW(E)= ) , # FOLLOW(T)= + , ) , # FOLLOW(T)= + , ) , # FOLLOW(F)= * , + , ) , # e、各產(chǎn)生式的各產(chǎn)生式的SELECT集集：E TEE +TE | T FTT *FT | F

31、i | ( E )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 FIRST(E)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( , i FOLLOW(E)= ) , # FOLLOW(E)= ) , # FOLLOW(T)= + , ) , # FOLLOW(T)=

32、 + , ) , # FOLLOW(F)= * , + , ) , # 查看SELECT定義文法文法GE是是LL(1)文法。文法。(2).構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表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+TETFTFTT*FTFi ( E )說明說明：若：若a屬于屬于SELECT(A)，則把則把A放入放入MA,a中。中。注意注意：#與空值、與空值、 ？(3).運行運行：i+*()#ETE TE E+TE TFT FT T *FT Fi ( 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#產(chǎn)生式產(chǎn)生式ETETFTF ii 匹配匹配T E +TE+ 匹