第4章語法分析自上而下分析

1、第四章 語法分析該講語法分析了！該講語法分析了！這可是很重要的章節(jié)這可是很重要的章節(jié)主要內(nèi)容：主要內(nèi)容：本章將重點(diǎn)介紹典型的語法分析方法及相本章將重點(diǎn)介紹典型的語法分析方法及相關(guān)的概念和實(shí)現(xiàn)技術(shù)關(guān)的概念和實(shí)現(xiàn)技術(shù)語法分析分為：語法分析分為：自上而下自上而下:自下而上：自下而上：遞歸下降分析法遞歸下降分析法 LL LL（1 1）預(yù)測(cè)分析法）預(yù)測(cè)分析法推導(dǎo)推導(dǎo)算符優(yōu)先分析法算符優(yōu)先分析法LRLR分析法分析法歸約歸約從根向葉的方從根向葉的方向建立分析樹向建立分析樹從葉向根的方從葉向根的方向建立分析樹向建立分析樹4.14.1語法分析器的功能語法分析器的功能詞法分析器詞法分析器語法分析器語義分析語義分析

2、符號(hào)表符號(hào)表源程序單詞符號(hào)單詞符號(hào)語法樹語法樹中間中間表示表示 完成的任務(wù)：完成的任務(wù)： 對(duì)詞法分析器產(chǎn)生的單詞符對(duì)詞法分析器產(chǎn)生的單詞符號(hào)進(jìn)行處理，輸出分析樹號(hào)進(jìn)行處理，輸出分析樹 與單詞相關(guān)的與單詞相關(guān)的信息記錄到符號(hào)表中信息記錄到符號(hào)表中類型檢查類型檢查錯(cuò)誤處理錯(cuò)誤處理語法分析器任務(wù)源程序源程序單詞符號(hào)單詞符號(hào)取下一單詞取下一單詞.語法分語法分析樹析樹詞法分詞法分析器析器語法分語法分析器析器符號(hào)表符號(hào)表編譯程序編譯程序后續(xù)部分后續(xù)部分n語法分析階段語法分析階段編譯過程的核心階段編譯過程的核心階段n語法分析的任務(wù)是分析一個(gè)文法的句子結(jié)構(gòu)。語法分析的任務(wù)是分析一個(gè)文法的句子結(jié)構(gòu)。n語法分析器

3、的功能：按照文法的產(chǎn)生式語法分析器的功能：按照文法的產(chǎn)生式( (語言語言的語法規(guī)則的語法規(guī)則) )，識(shí)別輸入符號(hào)串是否為一個(gè)句，識(shí)別輸入符號(hào)串是否為一個(gè)句子子( (合式程序合式程序) )。n語言的語法結(jié)構(gòu)：用上下文無關(guān)文法描述。語言的語法結(jié)構(gòu)：用上下文無關(guān)文法描述。n對(duì)于一個(gè)文法，怎樣判斷輸入符號(hào)串是不是對(duì)于一個(gè)文法，怎樣判斷輸入符號(hào)串是不是該文法的一個(gè)句子？該文法的一個(gè)句子？推導(dǎo)：是否能從文法的開始符號(hào)出發(fā)推導(dǎo)出推導(dǎo)：是否能從文法的開始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串。這個(gè)輸入串。語法樹：能否建立一棵與輸入串相匹配的語語法樹：能否建立一棵與輸入串相匹配的語法分析樹。法分析樹。分類分類按語法樹建立方法

4、按語法樹建立方法n語法分析的方法：語法分析的方法：n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：從輸入串開始，逐步進(jìn)行基本思想：從輸入串開始，逐步進(jìn)行“歸歸約約”，直到文法的開始符號(hào)。即從樹末端開，直到文法的開始符號(hào)。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。符號(hào)。n算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語法分析。適合分析表達(dá)式。合性質(zhì)進(jìn)行語法分析。適合分析表達(dá)式。nLRLR分析法

5、：規(guī)范歸約分析法：規(guī)范歸約G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E Ei+ +* *EiiEEEEn語法分析的方法：語法分析的方法：n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找用各種產(chǎn)生式，尋找 匹配匹配 的的推導(dǎo)推導(dǎo)。n遞歸下降分析法：對(duì)每一語法變量遞歸下降分析法：對(duì)每一語法變量( (非終結(jié)符非終結(jié)符) )構(gòu)

6、造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。n預(yù)測(cè)分析程序預(yù)測(cè)分析程序F優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。4.24.2自頂向下分析法自頂向下分析法4.2.1 使用的技術(shù)、存在的問題及解決方法4.2.2 LL(1)文法4.2.3 遞歸下降法4.2.4 LL（1）預(yù)測(cè)分析法4.2.1 4.2.1 自上而下分析面臨的問題及解決辦自上而下分析面臨的問題及解決辦法法n自上而下就是從文法的開始符號(hào)出發(fā)，向下自上而下就

7、是從文法的開始符號(hào)出發(fā)，向下推導(dǎo)推導(dǎo)，推出句子。，推出句子。n帶帶“回溯回溯”的的n不帶回溯的遞歸子程序不帶回溯的遞歸子程序( (遞歸下降遞歸下降) )分析方法。分析方法。n自上而下分析的主旨：對(duì)任何輸入串，試圖自上而下分析的主旨：對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)用一切可能的辦法，從文法開始符號(hào)( (根結(jié)根結(jié)點(diǎn)點(diǎn)) )出發(fā)，自上而下地為輸入串建立一棵出發(fā)，自上而下地為輸入串建立一棵語語法樹法樹?；蛘哒f，為輸入串尋找一個(gè)最左推?；蛘哒f，為輸入串尋找一個(gè)最左推導(dǎo)。導(dǎo)。n例例1 1 假定有文法假定有文法G(S):G(S): (1) SxAy (1) SxAy (2) A (2) A

8、* * *| |* * 分析分析輸入串輸入串x x* *y(y(記為記為 ) )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*n當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，可能當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，可能帶來如下問題帶來如下問題: :1. 1. 分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)。出錯(cuò)時(shí)時(shí)，不得不，不得不“回溯回溯”。2. 2. 文法左遞歸問題文法左遞歸問題。一個(gè)文法是含有左遞歸的一個(gè)文法是含有左遞歸

9、的，如果存在非終結(jié)符，如果存在非終結(jié)符P PPP 含有左遞歸的文法將使自上而下的分析陷含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。入無限循環(huán)。一、左遞歸問題一、左遞歸問題 如果文法如果文法G具有一個(gè)非終結(jié)符具有一個(gè)非終結(jié)符A使得對(duì)使得對(duì) 某個(gè)字符串某個(gè)字符串存在推導(dǎo)存在推導(dǎo)A=A ,例：下面是描述算術(shù)表達(dá)式的算法 S E EE+T|T TT*F|F F(E)|idid為句子idid*idid+idid構(gòu)造分析樹構(gòu)造分析樹 S S E + T E + T E + T E + TE + TE + T： 則稱文法則稱文法G是左遞歸的；是左遞歸的； 如果如果AA ，則稱文法則稱文法G是是直接左遞歸

10、直接左遞歸的的+左遞歸會(huì)使分析進(jìn)入到無限循環(huán)之中左遞歸會(huì)使分析進(jìn)入到無限循環(huán)之中消除簡(jiǎn)單左遞歸的方法：消除簡(jiǎn)單左遞歸的方法： 對(duì)于含有左遞歸的產(chǎn)生式對(duì)于含有左遞歸的產(chǎn)生式 AA | 可用下面的非左遞歸的產(chǎn)生式可用下面的非左遞歸的產(chǎn)生式 代替：代替： A A A A| 例：下面是描述算術(shù)表達(dá)式的算法 EE+T|T TT*F|F F(E)|idid消除E和T的直接左遞歸，得到： ETE E +TE|T FTF(E)|idT*FT| 17 對(duì)于一般情況而言，若某一文法對(duì)于一般情況而言，若某一文法G的產(chǎn)生的產(chǎn)生式具有如下形式：式具有如下形式： 則可用如下方法消除左遞歸則可用如下方法消除左遞歸:AA 1

11、| A 2 | A m| 1| 2| n A1A| 2A | n AA 1A| 2A| | mA | 很容易證明改造前后的文法是等價(jià)的很容易證明改造前后的文法是等價(jià)的例例2 2：文法：文法G G（P P）：）： P P （QQ）|aP|a|aP|a Q Q ,P|P Q Q ,P|P試消除左遞歸試消除左遞歸消除左遞歸后，方法改為：消除左遞歸后，方法改為：P （Q）|aPa Q P Q ， SQc|c SQc|c Q Rb|bQ Rb|b R Sa|a R Sa|aS這樣的遞歸無法用前面的方法消除這樣的遞歸無法用前面的方法消除對(duì)于含有間接左遞歸的文法：對(duì)于含有間接左遞歸的文法：=Qc=Rbc=

12、Sabc出現(xiàn)了左遞歸出現(xiàn)了左遞歸消除左遞歸的一般算法：消除左遞歸的一般算法：輸入：無循環(huán)推導(dǎo)和輸入：無循環(huán)推導(dǎo)和產(chǎn)生式的方法產(chǎn)生式的方法G G輸出：與輸出：與G等價(jià)的無左遞歸文法等價(jià)的無左遞歸文法算法：算法：1.以某種順序排列非終結(jié)符以某種順序排列非終結(jié)符A 1A 2A n2.for i=1 to n do begin for j=1 to i-1 do begin 改寫改寫A i A j 規(guī)則，方法如下：規(guī)則，方法如下： 如果如果A j 1| 2| k 則則A i 1 | 2 | n ；end 消除消除A i中的所有直接左遞歸中的所有直接左遞歸End3.化簡(jiǎn)由化簡(jiǎn)由2所得文法所得文法 SQc

13、|c SQc|c Q Rb|bQ Rb|b R Sa|a R Sa|a對(duì)如下文法消除左遞歸：1.將非終結(jié)符排序?yàn)镽、Q、S2.R不存在左遞歸，將R代入Q： Q Sab|ab|bQ Sab|ab|b3. Q不存在左遞歸，將Q代入S S Sabc|abc|bc|cS Sabc|abc|bc|c4.4.消除直接左遞歸后，得文法：消除直接左遞歸后，得文法： SabcS SabcS| bcS| bcS| cS| cS S SabcSabcS| | Q Rb|bQ Rb|b R Sa|a R Sa|a5.5.化簡(jiǎn)文法化簡(jiǎn)文法 SabcS SabcS| bcS| bcS| cS| cS S SabcSabc

14、S| | 練習(xí)：練習(xí)：1.1.已知文法已知文法GAGA：A-Ba|Aa|cA-Ba|Aa|c B-Bb|Ab|d B-Bb|Ab|d消除左遞歸的文法？消除左遞歸的文法？2.2.文法文法GSGS：S-ABS-AB A-bB|Aa A-bB|Aa B-Sb|a B-Sb|a消除左遞歸的文法？消除左遞歸的文法？二、回溯問題二、回溯問題提取左因子提取左因子為句子為句子if E1 then S1 else S2構(gòu)造一棵語法樹構(gòu)造一棵語法樹文法：文法： stmtif expr then stmt |S |if expr then stmt else stmt stmt if expr then stmt

15、E1 if then stmt 回溯回溯 造成這種情況的原因是產(chǎn)生式具有相同的造成這種情況的原因是產(chǎn)生式具有相同的首符號(hào)首符號(hào)，從而導(dǎo)致不清楚該用哪個(gè)來替換非，從而導(dǎo)致不清楚該用哪個(gè)來替換非終結(jié)符終結(jié)符 可通過可通過改寫改寫產(chǎn)生式來產(chǎn)生式來推遲推遲這種決定，直到這種決定，直到看見看見足夠多的輸入符號(hào)，可以作出正確選擇足夠多的輸入符號(hào)，可以作出正確選擇為止為止上例可改為：上例可改為： stmtif expr then stmt S |S S else stmt | stmt if expr then stmt S E1 else stmt 提取左因子算法：提取左因子算法：輸入：文法輸入：文法G

16、G輸出：一個(gè)等價(jià)的提取了左因子的文法輸出：一個(gè)等價(jià)的提取了左因子的文法方法：對(duì)于方法：對(duì)于A 1| 2 | n| 可改寫為：可改寫為： A A| A 1| 2 | n例例3 3：文法：文法G G（P P）：）： P P （QQ）|aP|a|aP|a Q Q ,P|P Q Q ,P|P試消除回朔試消除回朔三、FIRST與FOLLOW集1.FIRST1.FIRST集集回朔和左遞歸搞的人回朔和左遞歸搞的人真煩哪！真煩哪！ 怎樣才能做怎樣才能做到每次選的到每次選的產(chǎn)生都正確產(chǎn)生都正確呢？呢？ 郁悶?zāi)模∮魫災(zāi)?！FIRSTFIRST（ ）=a| =a ,aVT如果如果 = 則則 FIRSTFIRST（ ）

17、。）。例：例： stmtif expr then stmt S S else stmt S 定義：定義：FIRSTFIRST（ ）是由）是由推導(dǎo)出的所有的第一推導(dǎo)出的所有的第一個(gè)終結(jié)符號(hào)組成的集合，即：個(gè)終結(jié)符號(hào)組成的集合，即： 算法：算法： 求求FIRSTFIRST（X X）的算法描述如下：）的算法描述如下：例：例： First(if expr then stmt S)= if First( else stmt )= else First( )=)=如果如果X X是非終結(jié)符，且是非終結(jié)符，且X YX Y1 1 Y Y2 2 Y Yk k, ,則則a) Ya) Y1 1 = = FIRST(Y

18、 FIRST(Y1 1 ) )中的所有符號(hào)都在中的所有符號(hào)都在 FIRSTFIRST（X X）中）中b) Yb) Y1 1 Y Y2 2 Y Yi-1i-1= = , FIRSTFIRST（ Y Yi i ）, ,中的所有符號(hào)都在中的所有符號(hào)都在FIRSTFIRST（X X）中）中如果如果X X 是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， 則則 FIRSTFIRST（X X）如果如果X X是終結(jié)符，則是終結(jié)符，則FIRSTFIRST（X X）是）是XXc) c) Y Y1 1 Y Y2 2 Y Yk k= = ,則則 FIRSTFIRST（X X）例例4 4：有文法：有文法G G（S S） S BAS BA

19、 A BS A BS A d A d B aA B aA B bS B bS B c B c 試寫出其試寫出其FIRSTFIRST集集First(B)=aFirst(B)=bFirst(B)=c First(S)=First(BA)=a,b,c First(A)=First(BS)=a,b,c First(A)=d2.FOLLOW2.FOLLOW集集定義：定義：FOLLOWFOLLOW（A A）是由所有句型中緊跟）是由所有句型中緊跟在在A A后面的終結(jié)符后面的終結(jié)符a a組成的集合組成的集合 * *FOLLOWFOLLOW（A A）=a|S= =a|S= Aa ,a Vt 算法：算法： #FO

20、LLOW（S）對(duì)于對(duì)于A B的產(chǎn)生式，的產(chǎn)生式， 則則FIRST（ ）- 放入放入FOLLOWFOLLOW（B B）對(duì)于對(duì)于A B或或A B，其中其中= 則將則將FOLLOWFOLLOW（A A）放入放入FOLLOWFOLLOW（B B）中）中例5：對(duì)于文法G ETE E +TE| T T FT T*FT| F(E)|idid求其求其FIRSTFIRST和和 FOLLOWFOLLOW集集解：解：FIRST(F)=(,idFIRST(T)=*, FIRST(T )= FIRST(F) = (,id FIRST(E)=+, FIRST(E)=FIRST(T) =(,idFOLLOW(F)= FIR

21、ST（T) FOLLOW(T) =+,),*, # FOLLOW(E)=), # FOLLOW(E)=FOLLOW(E)=), # FOLLOW(T)=FOLLOW(T) =FIRST(E) FOLLW(E) =+,), # 例：例： A aA A bA A cAB A B B dC 對(duì)句子對(duì)句子abcd.進(jìn)行分析進(jìn)行分析AFIRST(aA)=a FIRST(bA)=bFIRST(cAB)=cFIRST()=FOLLOW(A)=d=aA =abA =abcAB =abcB =abcdCFirst和和Follow的用處的用處4.2.2 LL（1）文法一個(gè)上下文無關(guān)文法若滿足下列條件，一個(gè)上下文無

22、關(guān)文法若滿足下列條件，我們就稱它為我們就稱它為L(zhǎng)L（1）文法）文法文法不含左遞歸文法不含左遞歸文法中每個(gè)非終結(jié)符文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生的各個(gè)產(chǎn)生式的首終結(jié)符集兩兩不相交，即，若式的首終結(jié)符集兩兩不相交，即，若 A 1| 2 | n 則則 FIRST（ i ）FIRST（ j ）= 文法中每個(gè)非終結(jié)符文法中每個(gè)非終結(jié)符A若其首字符若其首字符集中含有集中含有，則，則 FIRSTFIRST（ i ）FOLLOWFOLLOW（A A）= = 這里這里L(fēng)L（1）中的）中的只有只有LL（1）文法，）文法，才可以實(shí)現(xiàn)確定的才可以實(shí)現(xiàn)確定的自頂向下語法分析自頂向下語法分析LL（1）的定義里保證）的定義

23、里保證了每一步分析的確定性，了每一步分析的確定性，你看出來了嗎？你看出來了嗎？第一個(gè)第一個(gè)L表示從左表示從左到右掃描輸入串，到右掃描輸入串，第二個(gè)第二個(gè)L表示最左表示最左推導(dǎo)，推導(dǎo)，1表示分析時(shí)每步表示分析時(shí)每步只需向前查看一只需向前查看一個(gè)符號(hào)個(gè)符號(hào)n對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符用非終結(jié)符A A進(jìn)行匹配，面臨的輸入符號(hào)為進(jìn)行匹配，面臨的輸入符號(hào)為a a，A A的所有產(chǎn)生式為的所有產(chǎn)生式為AA 1 1 | | 2 2 | | | | n n1. 1. 若

24、若a a FIRST(FIRST( i i) )，則指派，則指派 i i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2. 2. 若若a a不屬于任何一個(gè)候選首符集，則：不屬于任何一個(gè)候選首符集，則： (1) (1) 若若 屬于某個(gè)屬于某個(gè)FIRST(FIRST( i i ) )且且 a a FOLLOW(A)FOLLOW(A)， 則讓則讓A A與與 自動(dòng)匹配。自動(dòng)匹配。 (2) (2) 否則，否則，a a的出現(xiàn)是一種語法錯(cuò)誤。的出現(xiàn)是一種語法錯(cuò)誤。例例5 ： 對(duì)于文法對(duì)于文法G(E)ETE E +TE | TFT T *FT | F(E) | i構(gòu)造每個(gè)非終結(jié)符的構(gòu)造每個(gè)非終結(jié)符的FIRST和和FOLLOW集

25、合：集合： FIRST(E) =(,iFIRST(E )=+, FIRST(T) =(,iFIRST(T )=*, FIRST(F) =(,i FOLLOW(E) =),#FOLLOW(E )=),#FOLLOW(T) =+,),#FOLLOW(T )=+,),#FOLLOW(F) =*,+,),#i + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i

26、i + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTnG(E):

27、 ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iS T+練習(xí)：練習(xí)：1.1.設(shè)有文法設(shè)有文法GSG

28、S：S-aAbDe|d A-BSD|eS-aAbDe|d A-BSD|e B-Sac|cD| B-Sac|cD| D-Se| D-Se| (1)求每個(gè)非終結(jié)符的求每個(gè)非終結(jié)符的FOLLOW集，集，F(xiàn)IRST集。集。(2)判斷是否為判斷是否為L(zhǎng)L(1)文法？文法？2.設(shè)有文法設(shè)有文法GSGS：S-aABbcd|S-aABbcd| A-ASd| A-ASd| B-SAh|eC| B-SAh|eC| D-Sf|Cg| D-Sf|Cg| (1)求每個(gè)非終結(jié)符的求每個(gè)非終結(jié)符的FOLLOW集，集，F(xiàn)IRST集。集。(2)判斷是否為判斷是否為L(zhǎng)L(1)文法？文法？4.2.3 遞歸下降法為每一個(gè)非終結(jié)符編制

29、一個(gè)遞為每一個(gè)非終結(jié)符編制一個(gè)遞歸下降過程，歸下降過程，方法：方法： 過程的名字就產(chǎn)生過程的名字就產(chǎn)生式左部的非終結(jié)符，式左部的非終結(jié)符， 過程體則是過程體則是 按產(chǎn)生式的右部符號(hào)順序編寫的，按產(chǎn)生式的右部符號(hào)順序編寫的，每匹配一個(gè)終結(jié)符，則再讀入下每匹配一個(gè)終結(jié)符，則再讀入下一個(gè)輸入符號(hào)；一個(gè)輸入符號(hào)； 對(duì)于產(chǎn)生式右部對(duì)于產(chǎn)生式右部的每個(gè)非終結(jié)符，則遞歸調(diào)用相的每個(gè)非終結(jié)符，則遞歸調(diào)用相應(yīng)過程應(yīng)過程例：對(duì)于文法G ETE E +TE| T T FT T*FT| F(E)|idid 其遞歸下降分析程其遞歸下降分析程序編寫如下：序編寫如下：PROCEDURE EBEGIN T； E；ENDPRO

30、CEDURE TBEGIN F； T；ENDPROCEDURE EIF SYM=+ THENADVANCE； T； E；ENDPROCEDURE TIF SYM=* THENADVANCE； F； T；END 這一步實(shí)際這一步實(shí)際上就匹配了一個(gè)上就匹配了一個(gè)輸入符號(hào)輸入符號(hào)PROCEDURE FIF SYM=idid THEN ADVANCE；ELSE IF SYM=（ THEN BEGIN ADVANCE； E； IF SYM=） THEN ADVANCE； ELSE ERROR END ELSE ERROR； 當(dāng)調(diào)用一個(gè)當(dāng)調(diào)用一個(gè)過程的時(shí)候，過程的時(shí)候，就相當(dāng)于進(jìn)行就相當(dāng)于進(jìn)行了一步了一步

31、推導(dǎo)推導(dǎo)4.2.4 LL（1）預(yù)測(cè)分析法一、特征 根據(jù)當(dāng)前輸入符號(hào)，為當(dāng)前要處 理的非終結(jié)符選擇產(chǎn)生式二、表驅(qū)動(dòng)的預(yù)測(cè)分析器包含：二、表驅(qū)動(dòng)的預(yù)測(cè)分析器包含： 一個(gè)輸入緩沖區(qū)一個(gè)輸入緩沖區(qū) 一個(gè)棧一個(gè)棧 一張分析表一張分析表 一個(gè)輸出流一個(gè)輸出流要求文法是LL(1)的三、預(yù)測(cè)分析器模型：三、預(yù)測(cè)分析器模型： a + b #預(yù)測(cè)分析程序預(yù)測(cè)分析程序XYZ#分析表分析表M輸出輸出#是輸入串的結(jié)是輸入串的結(jié)束標(biāo)記，也是棧束標(biāo)記，也是棧底符號(hào)底符號(hào)四、預(yù)測(cè)分析表四、預(yù)測(cè)分析表M預(yù)測(cè)分析表是一個(gè)預(yù)測(cè)分析表是一個(gè)MA，a形式的矩陣形式的矩陣其中：其中： A為非終結(jié)符，為非終結(jié)符，a為終結(jié)符或?yàn)榻K結(jié)符或 #

32、MA，a中存放著一條關(guān)于中存放著一條關(guān)于A的產(chǎn)生式，指的產(chǎn)生式，指出當(dāng)出當(dāng)A面臨面臨a時(shí)所應(yīng)采取的候選；時(shí)所應(yīng)采取的候選；MA，a中也可能存放一條中也可能存放一條“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，指出不應(yīng)該面臨指出不應(yīng)該面臨a例：對(duì)于文法G 1 ETE 2 E +TE| 3 T T FT 4 T*FT| 5 F(E)|idid 其預(yù)測(cè)分析表為：其預(yù)測(cè)分析表為：解：解：FIRST(F)=(,idFIRST(T)=*, FIRST(T )= FIRST(F) = (,id FIRST(E)=+, FIRST(E)=FIRST(T) =(,idFOLLOW(F)= FIRST（E FIRST(T) =id,),

33、*, # FOLLOW(T)=FOLLOW(T) =FIRST(E) FOLLW(E) =+,), # FOLLOW(T)=FIRST(E) FOLLOW(E) =+,), #FOLLOW(E)=FOLLOW(E)=), #非終非終結(jié)符結(jié)符輸入符號(hào)輸入符號(hào)EETTFid*()#+ETEETEE+TEE E TFTTFTT T T T *FTF(E)Fid預(yù)測(cè)分析表預(yù)測(cè)分析表預(yù)測(cè)分析表的構(gòu)造預(yù)測(cè)分析表的構(gòu)造 for i:A do for a= FIRSTFIRST（ ） begin begin MA,a= MA,a= A; end if if FIRSTFIRST（ ） for bFOLLOW（

34、 A） MA,b= MA,b= A; 將將M的空白處均置為的空白處均置為error即即A 非終非終結(jié)符結(jié)符輸入符號(hào)輸入符號(hào)EETTFid*()+ETEETEE+TEE E TFTTFTT T T T *FTF(E)Fid預(yù)測(cè)分析表預(yù)測(cè)分析表FIRST(E)= (,idFIRST(E)=+, FOLLOW(E)=), FIRST(T ) = (,idFIRST(T)=*, FOLLOW(T)=+,), # FIRST(F)= (,id五、預(yù)測(cè)分析器的工作方式五、預(yù)測(cè)分析器的工作方式3、如果、如果X=a= # ,分析成功分析成功1、如果、如果X=a #，則，則POP，advance2、如果、如果X

35、 Vn,查查MX，a表表 若若MX，a=XUVW,則用則用WVU替換棧頂；替換棧頂； 若若MX，a=error,則調(diào)用錯(cuò)誤恢復(fù)程序則調(diào)用錯(cuò)誤恢復(fù)程序當(dāng)前棧頂符號(hào)當(dāng)前棧頂符號(hào)X和當(dāng)前輸入符號(hào)為和當(dāng)前輸入符號(hào)為a，則語法，則語法分析器的動(dòng)作為：分析器的動(dòng)作為：預(yù)測(cè)分析程序的算法：預(yù)測(cè)分析程序的算法：輸入：串輸入：串w和文法和文法G的分析表的分析表M輸出：如果輸出：如果w屬于屬于L（G），則輸出），則輸出w的最的最左推導(dǎo)，否則報(bào)錯(cuò)左推導(dǎo)，否則報(bào)錯(cuò)方法：開始時(shí)，方法：開始時(shí)， # S在棧里在棧里 w #在輸入緩沖區(qū)在輸入緩沖區(qū)令令ip指向指向w #的第一個(gè)符號(hào)的第一個(gè)符號(hào) 令令X是棧頂符號(hào)，是棧頂符號(hào)

36、，a是是ip指向的符號(hào)指向的符號(hào)Repeat If X Vt, then if X=a then pop X，ip指向下一個(gè)符號(hào)指向下一個(gè)符號(hào) else error() Else if MX,a= X YX Y1 1 Y Y2 2 Y Yk k thenthen pop X; pop X; push Y push Yk k Y Yk-1k-1 Y Y1; 1; 輸出輸出 X YX Y1 1 Y Y2 2 Y Yk k Until X= Until X= # if X=a= # 接收接收 else error句子句子id+id*id的分析過程的分析過程棧棧輸入輸入輸出輸出# E# ET# ETF

37、# ET# E# ETid# ET+ # ET # ETF# ETid# ET# ETF# ETid # ET# E# ETF*id+id*id # id+id*id # id+id*id # id+id*id # +id*id # +id*id # +id*id # id*id # id*id # id*id # *id # *id # id # id # # # # ETE TFT Fid T E+TE TFT Fid T*FT Fid T E 練習(xí)：文法練習(xí)：文法G G（S S） SSSS* *aT|aTaT|aT T +aT| T +aT|消去左遞歸，求消去左遞歸，求FIRSTFIRS

38、T和和FOLLOWFOLLOW寫出句子寫出句子a a* *a a* *a+aa+a的分析過程的分析過程解：解：S aTS S *aTS| T +aT| FIRST(S)=a FIRST(S)=*, FIRST(T)=+ , FOLLOW(S)=# FOLLOW(S)=# FOLLOW(T)=*, # * + a # S S aTS S S *aTS S T T T +aT T 句子句子a*a*a+a的分析過程的分析過程棧棧輸入輸入輸出輸出# S# STa# ST# STa*# ST# S# S # STa* # ST# ST a+# ST# S a*a*a+a # a*a*a+a # *a*a+a # *a*a+a # *a*a+a # *a+a # *a+a # *a+a # +a # +a # # # SaT ST T T +aT T S *aTSS *aTSS # #七、預(yù)測(cè)分析的錯(cuò)誤恢復(fù)七、預(yù)測(cè)分析的錯(cuò)誤恢復(fù)1、發(fā)現(xiàn)錯(cuò)誤棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配非終結(jié)符A位于棧頂，面臨的輸入符為a，但分析表M的MA,a為空2 2、“應(yīng)急應(yīng)急”恢復(fù)策略恢復(fù)策略跳過輸入串中的一些符號(hào)直至遇到跳過輸入串中的一些符號(hào)直至遇到“同同步符