編譯原理第五章

1、自頂向下語法分析第五章5.0 概述概述v語法分析是編譯程序的核心部分 v語法分析的任務：1、識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子 ；2、按照語言既定的語法規(guī)則，對字符串形式的源程序進行語法檢查，并識別出相應的語法成分 。v語法分析的處理依據(jù)是語言的文法規(guī)則 v分析結(jié)果是識別出的無語法錯誤的語法成分，可以與語法樹的形式來表示。 v語法分析的關(guān)鍵是句型識別問題 v設給定文法G和字符串（句子），檢查、判斷句子是否是文法G所能產(chǎn)生的合法的句子，同時檢查和處理語法錯誤。語法分析器的作用及在編譯程序中的作用scanner語法分析器語義分析。中間代碼生成源程序源程序取下一個單詞分析樹源程

2、序語法分析的方法分成兩大類 語法分析語法分析自頂向下分析方法自底向上分析方法確定的自頂向下分析方法不確定的自頂向下分析方法算符優(yōu)先分析方法LR分析方法v自頂向下語法分析也稱面向目標的分析方法自頂向下語法分析也稱面向目標的分析方法：從文法的開始符號出發(fā)推導出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，否則出錯。v確定的分析方法確定的分析方法：對文法有一定的限制，方法簡單、直觀，便于實現(xiàn)，是常用的方法。v不確定的分析方法不確定的分析方法：帶回溯的分析方法，是一種窮舉的試探方法，效率低、代價高，較少使用。51 確定確定的自頂向下分析思想的自頂向下分析思想v給定的條件是：1、

3、已知文法條件；2、給出輸入的字符串。判斷該輸入的字符串是已知文法的句子。v判定的思路是：從文法開始符號出發(fā)，根據(jù)輸入的符號唯一地唯一地確定選用哪個產(chǎn)生式替換相應的非終結(jié)符往下推導。最終與輸入字符串相匹配。v實際上，根據(jù)文法的特點（確切地講根據(jù)產(chǎn)生式的不同特點），推導過程的復雜程度也不一樣。v如果文法有如下的特點：（1）每個產(chǎn)生式的右部都由終結(jié)符開始。（2）如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開始。對于這樣的文法顯然在推導過程中完全可以根據(jù)當前的輸入符號決定選擇那個產(chǎn)生式往下推導，也就是說分析過程是唯一確定的。v例例5.1v若有文法GS:vSpAqBvAcAdavBdBbv若

4、輸入串為pccadd。推導判斷是否合法？文法是確定性的文文法是確定性的文法，但是被識別的法，但是被識別的句子可能是不符合句子可能是不符合文法的！文法的！v如果文法有如下特點：產(chǎn)生式的右部不全是由終結(jié)符開始。如果兩個產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開始。文法中無空產(chǎn)生式。v如果左部相同，右部不同，但是右部的符號串可以推導出的首符號集不相交首符號集不相交，因而，可以根據(jù)輸入符號串判定相應的產(chǎn)生式進行推導。這樣的推導過程仍然是確定的。v例5-2：若有文法GS：vSApvSBqvAavAcAvBbvBdB1.判斷符號串ccap表面看不確定，實際上確定！v例5.2的推導過程如下：

5、 開始符號S的兩個產(chǎn)生式的右部都不是以終結(jié)符開始； 根據(jù)右部非終結(jié)符所推導出的首字符集，判斷選擇那個產(chǎn)生式； FIRST（Ap）=a,c；FIRST(Bq)=b,d；兩個字符集不相交； 唯一確定SAp作為選擇。vSApcApccApccap為推導過程。 v輸入串ccap為可以接受。v存在一個回溯的問題，即在替換某個非終結(jié)符時，存在多種選擇，當選擇某個推導到后面可能無解，必須退回重新選擇。1.消除回溯或者避免回溯可以通過求解首字符集，判斷消除回溯或者避免回溯可以通過求解首字符集，判斷首字符集不相交首字符集不相交。 v定義定義：設G=(VT，VN，S，P)是上下文無關(guān)文法。FIRST()=a* a

6、， aVT，V*若*，則規(guī)定FIRST()稱FIRST()為的開始符號集合開始符號集合或首字符集首字符集。v文法GS：SApSBqAaAcABbBdBv產(chǎn)生式左部分相同的右部分的首字符集都不相交。所以，該文法可以進行自頂向下的確定性分析。v那么如果在產(chǎn)生式中存在空產(chǎn)生式，如何判定它可以確定的進行語法分析？v例53 若有文法GS：SaA；Sd；AbAS；A。 判斷字符串：abdv推導過程：S aAabASabSabSabdv當某個非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生式時，它的非空產(chǎn)生式右部的首字符集兩兩不相交，并且在推導過程中緊跟在該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符也不相交，則仍可以構(gòu)造確定的語法分析。v這

7、種情況下就要看該非終結(jié)符的后跟符號集后跟符號集（FOLLOW）。通常情況下，只需要考慮通常情況下，只需要考慮FIRST集集合就可以了。但是，當產(chǎn)生式右部合就可以了。但是，當產(chǎn)生式右部出現(xiàn)出現(xiàn)或者能夠推導出或者能夠推導出，則應該考，則應該考慮該產(chǎn)生式左部的非終結(jié)符的后跟慮該產(chǎn)生式左部的非終結(jié)符的后跟字符集。字符集。v后跟符號集（后跟符號集（FOLLOW）定義：）定義：設G=(VT,VN,S,P)是上下文無關(guān)文法，AVN，S是開始符號。FOLLOW(A)=aS *.Aa.，a VT，若有S *.A，則規(guī)定# FOLLOW(A)v#作為輸入串的結(jié)束符號。作為輸入串的結(jié)束符號。v假設文法中有形如下的產(chǎn)

8、生式：假設文法中有形如下的產(chǎn)生式：AAv若和不能同時推導為。如不為，可以為。v在推導過程中，可以確定地替換A的條件是FIRST() ( FIRST() U FOLLOW(A) ) =v事實上，在語法分析上還是追求確定的自上而下的分析方法。 v當確定首字符集和后跟字符集，就可以形成一個新的字符集：選擇字符集選擇字符集SELECT。v根據(jù)對選擇字符集的判斷就可以判定語法分析是否可以為確定的。v給定上下文無關(guān)文法的產(chǎn)生式給定上下文無關(guān)文法的產(chǎn)生式Aa AVn,aV*，v若若為非空的產(chǎn)生式，為非空的產(chǎn)生式，SELECT（A）=FIRST（）v若若包含空產(chǎn)生式，包含空產(chǎn)生式，SELECT（A）=（FIR

9、ST（）-）FOLLOW(A)v通過通過FIRST（）和）和FOLLOW(A)就可以求出就可以求出SELECT（A）從而就可以判定針對這個非終結(jié)符是否可以）從而就可以判定針對這個非終結(jié)符是否可以進行確定的語法分析。進行確定的語法分析。v我們將滿足自頂向下分析技術(shù)條件的文法為LL（1）文法。v一個上下文無關(guān)文法是一個上下文無關(guān)文法是LL（1）文法的充分必要條件）文法的充分必要條件是，對每個非終結(jié)符是，對每個非終結(jié)符A的兩個不同產(chǎn)生式，的兩個不同產(chǎn)生式，A；A，滿足：，滿足：SELECT（A）SELECT（A）=；其中，；其中，、不能同時包含空產(chǎn)生式。不能同時包含空產(chǎn)生式。vLL（1）文法含義是：

10、第一個）文法含義是：第一個L表明自頂向下分析是從表明自頂向下分析是從左向右掃描輸入串，第二個左向右掃描輸入串，第二個L表明分析過程是用最左表明分析過程是用最左推導，推導，1表明只需向右看一個符號便可以決定如何推表明只需向右看一個符號便可以決定如何推導即選擇哪個產(chǎn)生式進行推導。導即選擇哪個產(chǎn)生式進行推導。v選擇集合選擇集合SELECT：v例：例： SaA Sd A AbASvSELECT(SaA )=FIRST（）=avSELECT(Sd )=FIRST（d）=dv SELECT(AbAS )=bvSELECT(A)=a,d,#vSELECT(SaA ) SELECT(Sd )= vSELECT

11、(AbAS ) SELECT(A)= v可知文法為可知文法為LL（1）文法，可用確定的自頂向）文法，可用確定的自頂向下分析。下分析。例題vS pAvS qBvA cAdvA avB dBvB bl每個產(chǎn)生式右部都由終結(jié)符開始l如果兩個產(chǎn)生式有相同的左部,那么它們的右部由不同的終結(jié)符開始l這是直觀的、確定的分析方法的文法例題vS ApvS BqvA cAvA avB dBvB bl產(chǎn)生式右部不不都由終結(jié)符開始l如果兩個產(chǎn)生式有相同的左部,那么它們的右部由不同的終結(jié)符或非終結(jié)符開始l如果左部相同，右部的符號串可以推導出的首字符集合首字符集合不相交l文法中無空產(chǎn)生式l這是隱蔽的，但是是確定的分析方這

12、是隱蔽的，但是是確定的分析方法的文法法的文法例題vS aAvS dvA bASvA l 當某個非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生式時，它的非空產(chǎn)生式右部的首字符集合兩兩不相交l 并且在推導過程中緊跟該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符集合也不相交l 仍然是確定的分析方法的文法仍然是確定的分析方法的文法l 后跟字符集合的求解一定要注意：后跟字符集合的求解一定要注意： 它是針對某個非終結(jié)符的計算；它是針對某個非終結(jié)符的計算； 它將來要用到以這個非終結(jié)符作為左部，它將來要用到以這個非終結(jié)符作為左部，并且能夠推導出空的產(chǎn)生式并且能夠推導出空的產(chǎn)生式 在推導過程中，有可能出現(xiàn)在該非終結(jié)在推導過程中，有可能出現(xiàn)在該非

13、終結(jié)符后面的終結(jié)符。因為是推導，所以一符后面的終結(jié)符。因為是推導，所以一定要從開始符號出發(fā)。定要從開始符號出發(fā)。 特別要注意特別要注意# #，什么時候?qū)儆诤蟾址?，什么時候?qū)儆诤蟾址?。集。例題vS aASvS bvA bAvA l 最后一個產(chǎn)生式可以推導出空，在將來分析過程中，就很有可能用到它的這個特點，因此，需要求出產(chǎn)生式左部非終結(jié)符的后跟字符集。這個產(chǎn)生式的SELECT集合，除了包括首字符集以外，還應考慮A的后跟字符集l A的后跟字符集中不包括#，這是因為，從S出發(fā)進行推導，永遠不會出現(xiàn)S A這樣的形式這樣的形式52 LL（1）文法的判別）文法的判別v當我們需選用自頂向下分析技術(shù)時，首

14、先必須判定所給文法是否是LL（1）文法。 v我們對任給文法需要計算FIRST、FOLLOW、SELECT集合，進而判別文法是否為LL（1）文法。lSELECT是關(guān)于產(chǎn)生式的；lFIRST包含兩個情況：一是產(chǎn)生式右部；另一個是非終結(jié)符；lFOLLOW是關(guān)于能推出空的產(chǎn)生式左部的非終結(jié)符的；求出能推出求出能推出的非終結(jié)符的非終結(jié)符v利用一個以文法的非終結(jié)符個數(shù)為上界，每個非終結(jié)符為元素的一維數(shù)組。逐步掃描，確定能夠推出的非終結(jié)符。計算計算FIRST集集v根據(jù)定義計算FIRST()=a*a, a VT, 、V*若*，則規(guī)定FIRST()；對每個文法符號XV計算計算FIRST(X),有：有：v若若XV

15、T, 則則FIRST(X)=X；v若若XVN, 且有產(chǎn)生式且有產(chǎn)生式X a， a VT,則則a FIRST(X)；v若若XVN, 且且X ，則則 FIRST(X)；v若若XVN,Y1,Y2,Yi都都VN,且有產(chǎn)生式且有產(chǎn)生式XY1,Y2,Yn ,當當Y1,Y2,Yi-1都都*，則FIRST(Y1)-，F(xiàn)IRST(Y2)-， FIRST(Yi-1)-， FIRST(Yi)都包含在FIRST(X)中；a)當d)中的所有的Yi *，（i=1，2，n），則FIRST(X)= FIRST(Y1) FIRST(Y2) FIRST(Yn) .通常情況下，我們要求出所有非終結(jié)符的通常情況下，我們要求出所有非終

16、結(jié)符的FIRST集合，這是為了將來求集合，這是為了將來求FOLLOW集集合是用得上；重要的是求產(chǎn)生式右部符號串的合是用得上；重要的是求產(chǎn)生式右部符號串的FIRST集合，這是求集合，這是求SELECT集合的重集合的重要元素。要元素。vS ABvS bCvA vA bvB vB aDvC ADvC bvD aSvD c計算計算FIRST集集v根據(jù)關(guān)系圖法計算每個文法符號對應圖中一個節(jié)點，對應終結(jié)符的節(jié)點時用符號本身標記，對應非終結(jié)符的節(jié)點時用FIRST(A)標記。（這里A表示非終結(jié)符）如果文法中有產(chǎn)生式AX,且*，則從對應A的節(jié)點到對應X的節(jié)點連一條射線??；凡是從FIRST(A)節(jié)點有路徑可到達的

17、終結(jié)符節(jié)點所標記的終結(jié)符都為FIRST(A)成員；是否為FIRST(A)成員由直接方法判斷。bcaFIRST(S)FIRST(B)FIRST(D)FIRST(A)FIRST(C)vS ABvS bCvA vA bvB vB aDvC ADvC bvD aSvD cX可能是終結(jié)符，也可能是非終結(jié)符。計算計算FOLLOW集集v根據(jù)定義計算v對文法中的每一個非終結(jié)符AVN,計算計算FOLLOW(A):設設S為文法的開始符號，把為文法的開始符號，把#加入加入FOLLOW(S)中；中；若AB是一個產(chǎn)生式，則把FIRST()的非空元素加入到FOLLOW(A)中；a)反復使用b)直到每個非終結(jié)符的FOLLO

18、W集合不再擴大為止。這里要特別注意：當 *時，則FOLLOW(A)的內(nèi)容也加入到FOLLOW(B)中，這是因為假如有：D 1A2A B的兩個產(chǎn)生式，在推導過程中有：S *1A2 1 B 2事實上，往往我們先求出所有的非終結(jié)符的FOLLOW集合，然后根據(jù)產(chǎn)生式是否能推導出空空來決定是否采用計算計算FOLLOW集集v根據(jù)關(guān)系圖法計算文法G中的每個符號和“#”對應圖中的一個節(jié)點，對應終結(jié)符的節(jié)點用符號本身標記，對應非終結(jié)符的節(jié)點，則用FOLLOW(A)或FIRST(A)標記；從開始符號S的FOLLOW(S)節(jié)點到“#”號的節(jié)點連接一個射線弧；如果文法中有產(chǎn)生式ABX，且 *，則從FOLLOW(B)節(jié)

19、點到FIRST(X)節(jié)點連接一射線弧，當XVT, 則與則與X相連；相連；如果文法中有產(chǎn)生式如果文法中有產(chǎn)生式AB，且 *，則從FOLLOW(B)節(jié)點到FOLLOW(A)節(jié)點連接一射線??；對每一個FIRST(A)節(jié)點，如果有產(chǎn)生式AX，且 *，則從FIRST(A)到FIRST(X)連一射線弧，若XVT, 則與則與X相連；相連；a)凡是從凡是從FOLLOW(A)節(jié)點有路徑可以到達的終結(jié)符或節(jié)點有路徑可以到達的終結(jié)符或“#”號的節(jié)號的節(jié)點，其所標記的終結(jié)符或點，其所標記的終結(jié)符或“#”號即為號即為FOLLOW(A)的成員。的成員。vS ABvS bCvA vA bvB vB aDvC ADvC bv

20、D aSvD c#caFOLLOW(S)FIRST(B)FIRST(D)FOLLOW(A)FOLLOW(C)FOLLOW(B)FOLLOW(D)計算計算SELECT集集v根據(jù)FIRST集集和FOLLOW集集求SELECT集集v需要判斷每個終結(jié)符是否可推導出空產(chǎn)生式。需要判斷每個終結(jié)符是否可推導出空產(chǎn)生式。例題vS ABvS bCvA vA bvB vB aDvC ADvC bvD aSvD c首先，判斷能推出首先，判斷能推出的非終結(jié)符。求的非終結(jié)符。求這個非中符的后跟字符集。有些，能這個非中符的后跟字符集。有些，能夠直觀判斷，有些，需要推導；夠直觀判斷，有些，需要推導；求求FIRST集合，這里

21、需要兩個步驟。集合，這里需要兩個步驟。先計算每個非終結(jié)符的先計算每個非終結(jié)符的FIRST集合；集合；然后，再求每個產(chǎn)生式右部符號串的然后，再求每個產(chǎn)生式右部符號串的FIRST集合。我們需要結(jié)果是后者，集合。我們需要結(jié)果是后者，但前者在計算后者是會用到；但前者在計算后者是會用到；求求FOLLOW集合，需要注意：集合，需要注意：FOLLOW集合一定是針對非終結(jié)符的；集合一定是針對非終結(jié)符的；有些可以直觀計算；有些可以直觀計算；有些要注意推導，有些要注意推導，A B形式時，形式時，如果如果能推導出能推導出，則則FOLLOW（A）也屬于也屬于FOLLOW（B）例題vS ABvS bCvA vA bvB

22、 vB aDvC ADvC bvD aSvD c非終結(jié)符名稱是否推出FIRST集合FOLLOW集合S是b,a, #A是b, a,c,#B是a, #C否b,a, c#D否a, c#例題產(chǎn)生式產(chǎn)生式SELECT集合集合S ABb,a,#SbCbA a,c,#A bbB #BaDaCADa,b,cCbbDaSaDccabc#SABAB; bCABA A b BaD CADAD; bADDaSc5.3 某些非LL（1）文法到LL（1）文法的等價交換v確定的自頂向下分析要求對給定語言的文法必須是LL（1）形式。v但是，不是所有的語言都有LL（1）文法。v不是LL（1）文法的原因，要么是直接或間接左遞歸；

23、要么含有左公共因子。v左公共因子：文法中形如A|v直接左遞歸：AA；v間接左遞歸：AB；BAv消除左遞歸或左公共因子，能否將非LL（1）文法轉(zhuǎn)換成LL（1）文法？提取左公共因子提取左公共因子v若文法中含有形如：A|的產(chǎn)生式，這導致了對相同左部的產(chǎn)生式其右部的FIRST集相交，不滿足LL（1）文法的充分必要條件。v將產(chǎn)生式A|等價變換為： A（|）v引進新的非終結(jié)符A，使產(chǎn)生式變換為： AA；A |v一般形式為： A1|2|3|.|nv提取左公因子： A（1|2|3|.|n）v引進新非終結(jié)符A： AA； A1|2|.|nv若123.n中仍含有左公共因子，可再次提取，這樣反復進行提取，直到引進新非

24、終結(jié)符的有關(guān)產(chǎn)生式再無左公共因子為止。例5. 6 （提取左公共因子后為非LL（1）v若文法G1的產(chǎn)生式為：v（1）SSbv（2） SSv（3） S ；v對（1）（2）提取左公共因子后得：vSS（b| ）vS ；v進一步變換為文法G1vSSAvAbvA vS ；例5. 7（提取左公共因子后為LL（1）v若文法G2的產(chǎn)生式為：v1、Aad；2、ABcv3、BaA；4、BbBv產(chǎn)生式2的右部以非終結(jié)符開始，因此，左公共因子可能是隱含的。用其相同左部而右部以終結(jié)符開始的產(chǎn)生式進行相應替換。v1、 Aad； 2、AaAc；3、 AbBcv4、 BaA；5、BbBv提取1、2的左公共因子得：vAa（d|A

25、c）； AbBc； BaA；BbBv引進新非終結(jié)符A，得文法G2vAaA； AbBc； Ad； A Ac； vBaA；BbB例5.8（提取左公共因子后，產(chǎn)生無用產(chǎn)生式，必須化簡文法）v若有文法G3的產(chǎn)生式為：v1、SaSd；2、SAc；v3、AaS；4、Abv用3、4中的右部替換2中的右部的A，得v1、 SaSd； 2、SaSc；3、 Sbc；v4、 AaS；5、Abv對1、2提取左公共因子v SaS（d|c）；v引進新的非終結(jié)符A后得v1、 SaSA；2、Sbc；v3、A d|c；v4、AaS；5、Abv非終結(jié)符A變成不可到達的符號，產(chǎn)生式4、5為無用的產(chǎn)生式。例5.9（不能在有限步驟內(nèi)提取

26、完左公共因子）v若有文法G4的產(chǎn)生式為v1、SAp|Bq；2、AaAp|d；3、BaBq|ev用2、3的右部替換1中的A、B得v1、SaApp|aBqq；2、Sdp|eqv3、AaAp|d；4、BaBq|ev對1提取左共因子的vSa（App|Bqq）；v引入新的非終結(jié)符S后得v1、 SaS； 2、Sdp|eq ；3、S App|Bqq；v4、AaAp|d；5、BaBq|e；v用4、5中的右部替換3中的A、B，再提取左共因子，不斷進行。v不一定每個文法的左公共因子都能在有限步驟內(nèi)替換無左公共因子的文法。v一個文法提取了左公共因子后，只解決了相同左一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式

27、右部的部產(chǎn)生式右部的FIRST集不相交問題集不相交問題，當改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是LL（1）文法，否則還需要用LL（1）文法的判別方式進行判斷才能確定是否為LL（1）文法。消除左遞歸v一個文法含有下列形式的產(chǎn)生式時：va) AAvb) AB ； BAv在a)中可稱為含有左遞歸的規(guī)則或稱為直接左遞歸；在b) 中為文法中含有左遞歸或間接左遞歸；文法中只要含有a)或b) 或者二者皆有均認為文法是左遞歸的。v文法是左遞歸時不能采用自頂向下分析方法。例5.11v有文法G6為：v1、AaB；2、ABb；v3、 BAc；4、 Bd；v若有輸入串為adbcbcbc#，則分析過程

28、的語法樹如下：AaBAcBbdAaBAcBbAc利用這樣的推導不是不能推導出匹配，而是要不斷地進行回溯。不是確定的分析方法。v含有左遞歸的文法絕對不是LL（1）文法。不能用確定的自頂向下分析法。v為了使某些含有左遞歸的文法經(jīng)等價變換消除左遞歸后可能變成LL（1）文法，可采用下列變換公式：va) 消除直接左遞歸，把直接左遞歸改寫為右遞歸vb）消除間接左遞歸，先將間接變直接，然后，按a）vc）消除文法中一切左遞歸的算法。消除直接左遞歸，把直接左遞歸改寫為右遞歸v對文法：SSa；Sb 可改寫為：vSbS；S a S |v新舊文法的語句集都為新舊文法的語句集都為:ban|n=0 所以文法等價所以文法等

29、價.消除間接左遞歸v對文法：AaB；ABb；BAc；B dv包含間接左遞歸：用1、2的右部代替產(chǎn)生式3的非終結(jié)符A得vBaBc； BBbc； B d 消除左遞歸后得vB（aBc|d）B；BbcB| 再把原來的1、2產(chǎn)生式加入得vAaB；ABb； B（aBc|d）B；BbcB| 消除文法中一切左遞歸的算法v1、把文法中的所有非終結(jié)符按某個順序排序；v 如：A1，A2，A3，Anv2、從A1開始消除左部為A1的產(chǎn)生式的直接左遞歸，然后把左部為A1的所有規(guī)則的右部逐個替換左部為A2右部為A1開始的產(chǎn)生式中的A1，并消除左部為A2的產(chǎn)生式中的直接左遞歸。以此類推。v3、去掉無用產(chǎn)生式。例v有文法產(chǎn)生式

30、為：v（1）SQc|c；（2）QRb|b；（3）RSa|a；v該文法的每個非終結(jié)符互為間接左遞歸。v一、若非終結(jié)符按S、Q、R排序v左部為S的產(chǎn)生式無直接左遞歸，2中又不含S，所以將1的右部代入3中得到：4、RQca|ca|a；（至此1號非終結(jié)符解決完畢）v解決2號非終結(jié)符Q，將2中的右部代入4得到：5、 RRbca|ca|a；v對5消除直接左遞歸得： R（bca|ca|a）R；RbcaR|v最終文法變?yōu)椋簐（1）SQc|c；（2）QRb|b；v（2）R（bca|ca|a）R；（4）RbcaR|v二、若非終結(jié)符按R、Q、S排序v則把3代入2：QSab|ab|b；再將該產(chǎn)生式代入1得：vSSab

31、c|abc|bc|c；消除直接左遞歸，最終文法變?yōu)椋簐S（abc|bc|c）S；SabcS| ；QRb|b；RSa|a5.4 不確定的自頂向下分析思想v由于相同左部的產(chǎn)生式的右部FIRST集交集不為空而引起回溯。v由于相同左部非終結(jié)符的右部存在能推導出空產(chǎn)生式，且該非終結(jié)符FOLLOW集中含有其他右部FIRST集的元素。v由于文法含有左遞歸而引起回溯5.5 確定的自頂向下分析方法v預測分析方法v一個預測分析器由三個部分組成：預測分析程序、先進后出棧、預測分析器表。v其中只有預測分析器表與文法有關(guān)。表驅(qū)動預測分析程序模型測分析程序模型 Input Input #總控程序總控程序預測分析表預測分析表stackv預測分析表可用一個矩陣M(或稱二維數(shù)組)表示。矩陣元素MA,a中的下標A表示非終結(jié)符， a為終結(jié)符或句子括號“#”，矩陣元素