編譯原理—清華大學(xué)—第2版_第5章自頂向下語法分析方法

1、第第5 5章章 自頂向下語法分析方法自頂向下語法分析方法 教學(xué)要求：教學(xué)要求：本章介紹編譯程序的第二個(gè)本章介紹編譯程序的第二個(gè)階段語法分析的設(shè)計(jì)方法和實(shí)現(xiàn)原理，階段語法分析的設(shè)計(jì)方法和實(shí)現(xiàn)原理，包括自上而下分析的無回朔的遞歸下降包括自上而下分析的無回朔的遞歸下降分析、分析、 LL(1)LL(1)分析法。要求理解遞歸下分析法。要求理解遞歸下降分析、降分析、LL(1)LL(1)文法的基本概念；掌握文法的基本概念；掌握LL(1)LL(1)分析表的構(gòu)造與分析方法。分析表的構(gòu)造與分析方法。 教學(xué)重點(diǎn)：教學(xué)重點(diǎn)：LL(1)LL(1)文法，預(yù)測分析表構(gòu)造，文法，預(yù)測分析表構(gòu)造，LLLL（1 1）分析法。）分

2、析法。 5.1 5.1 確定的自頂向下分析思想確定的自頂向下分析思想 文法文法G1S:SpASqBAcAdAaBdBBbW=pccadd自頂向下的推導(dǎo)過程：自頂向下的推導(dǎo)過程：S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd語法樹：語法樹：SpAcA dcA da確定的自頂向下分析確定的自頂向下分析1 1、基本思想：、基本思想： 從識(shí)別符出發(fā)，不斷建立直接推導(dǎo)，試圖構(gòu)造一從識(shí)別符出發(fā)，不斷建立直接推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串相同個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串相同的符號(hào)串。的符號(hào)串。2 2、遇到問題、遇到問題: :

3、（1 1）回溯（出現(xiàn)若干個(gè)左部相同的產(chǎn)生式）回溯（出現(xiàn)若干個(gè)左部相同的產(chǎn)生式） （2 2）無限循環(huán)（文法出現(xiàn)左遞歸）無限循環(huán)（文法出現(xiàn)左遞歸）3 3、解決方法：、解決方法： （1 1）避免回溯）避免回溯 （2 2）消除左遞歸）消除左遞歸 為了避免回溯為了避免回溯, ,先研究三個(gè)定義：先研究三個(gè)定義： 符號(hào)串符號(hào)串開始符號(hào)開始符號(hào)FIRSTFIRST集集 非終結(jié)符非終結(jié)符A A后跟符號(hào)后跟符號(hào)FOLLOWFOLLOW集集 產(chǎn)生式的選擇集合產(chǎn)生式的選擇集合SELECTSELECT集集 定義：設(shè)定義：設(shè) G = (VT ,VN , S , P) 是上下文無關(guān)是上下文無關(guān)文法，文法， = a|,a V

4、T,V*若若 ，則規(guī)定則規(guī)定FIRST()*1 1、符號(hào)串、符號(hào)串開始符號(hào)開始符號(hào)FIRSTFIRST集的定義：集的定義： FIRST(Ap)=a,c FIRST(Bq)=b,d 文法文法G2S:SApSBqAaAcABbBdB2 2、非終結(jié)符、非終結(jié)符A A后跟符號(hào)后跟符號(hào)FOLLOWFOLLOW集的定義：集的定義： 定義：設(shè)定義：設(shè) G = (VT ,VN , S , P) 是上下文無關(guān)文是上下文無關(guān)文法，法，AVN , S是開始符號(hào)。是開始符號(hào)。 若若S A，則規(guī)定則規(guī)定 #FOLLOW(A)*# #作為輸入串的結(jié)束符，或稱為句子括號(hào)，作為輸入串的結(jié)束符，或稱為句子括號(hào)， 如：如：# #

5、輸入串輸入串# #3 3、產(chǎn)生式、產(chǎn)生式AA的選擇集合的選擇集合SELECTSELECT的定義：的定義：（確定選擇那個(gè)產(chǎn)生式來推導(dǎo)）（確定選擇那個(gè)產(chǎn)生式來推導(dǎo)） 定義：給定上下文無關(guān)文法的產(chǎn)生式定義：給定上下文無關(guān)文法的產(chǎn)生式A，AVN , V*，若若 ，則則=FIRST()如果如果 ，則則 =(FIRST()-)FOLLOW(A)*例：例： SaA Sd A AbASSELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(A)=FOLLOW(A)=a，d，#SELECT(AbAS)=FIRST(bAS)=b 定義：一個(gè)上下文無關(guān)文法是定義：一個(gè)上

6、下文無關(guān)文法是的的充要條件是：充要條件是： 對每個(gè)非終結(jié)符對每個(gè)非終結(jié)符A的的任兩個(gè)任兩個(gè)不同產(chǎn)生式不同產(chǎn)生式A和和A，滿足滿足SELECT(A)SELECT(A)=其中其中,不能同時(shí)不能同時(shí) *LL(1)文法的含義：文法的含義： 第一個(gè)第一個(gè) 表示：自頂向下分析是表示：自頂向下分析是。 第二個(gè)第二個(gè) 表示：分析過程中將用表示：分析過程中將用。 表示：只需表示：只需便可決定如何便可決定如何推導(dǎo)（即選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)）。推導(dǎo)（即選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)）。 類似也可以有類似也可以有文法：需向前查看文法：需向前查看K個(gè)個(gè)符號(hào)才可確定選用哪個(gè)產(chǎn)生式。符號(hào)才可確定選用哪個(gè)產(chǎn)生式。 文法文法GS是否是

7、是否是LL(1)文法文法: :SaASdAbASA SELECT(SaA) =aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,#SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#=所以該文法是所以該文法是LL(1)文法。文法。 例：文法例：文法GS 為為: :SaASSbAbAA則：則：SELECT(SaAS)=a SELECT(Sb)=b SELECT(AbA)=b SELECT(A)=a,bSELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b所以該文法

8、不是所以該文法不是LL(1)文法。文法。對輸入串對輸入串W=abW=ab進(jìn)行推導(dǎo)：進(jìn)行推導(dǎo)：SELECT(AbA)SELECT(A)=ba,bS Sa aA AS SabASabASabSabS出錯(cuò)出錯(cuò)S Sa aA AS SaSaSabab5.2 LL(1)文法的判別文法的判別求出能推出求出能推出的非終結(jié)符的非終結(jié)符計(jì)算計(jì)算FIRST集集計(jì)算計(jì)算FOLLOW集集計(jì)算計(jì)算SELECT集集判別是否是判別是否是LL(1)文法文法 例：設(shè)文法例：設(shè)文法GS 為為:SABSbCAAbBBaDCADCbDaSDc判斷它是否是判斷它是否是LL(1)文法。文法。1.1.求出能推出求出能推出 的非終結(jié)符的非終

9、結(jié)符SABSbCAAbBBaDCADCbDaSDc能推出能推出 的非終結(jié)符為：的非終結(jié)符為： A A，B B，S SSABSbCAAbBBaDCADCbDaSDcFIRST(S)=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,c2.2.計(jì)算計(jì)算FIRSTFIRST集集3.3.計(jì)算計(jì)算FOLLOWFOLLOW集集(1)(1)對于文法的開始符號(hào)對于文法的開始符號(hào)S, ,置置#于于FOLLOW(FOLLOW(S) )中中; ;(2)(2)若若B是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式, , 則把則把

10、FIRST()-FIRST()- 加至加至FOLLOW(B)FOLLOW(B)中中; ; 若若 ( (即即 FIRST()FIRST()），），則把則把FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中中SABSbCAAbBBaDCADCbDaSDcFOLLOW(S)=#FOLLOW(D)FOLLOW(S)= #FOLLOW(A)= a,c,#FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #FOLLOW(A)=a FOLLOW(S) a,cFOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FO

11、LLOW(B)FOLLOW(C) =FOLLOW(S)4.計(jì)算計(jì)算SELECT集集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,#SELECT(SbC)=bSELECT(A)=a,c,#,SELECT(Ab)=bSELECT(B)=#SELECT(BaD)=aSELECT(CAD)=a,b,cSELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=cFOLLOW(S

12、)= #FOLLOW(A)= a,c,#FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #該文法不是該文法不是LL(1)文法。文法。5.3 某些非某些非LL(1)文法到文法到LL(1)文法文法 的等價(jià)變換的等價(jià)變換LL(1)LL(1)文法的性質(zhì)：文法的性質(zhì)： LL(1)LL(1)文法不含左公共因子文法不含左公共因子 LL(1)LL(1)文法不含左遞歸文法不含左遞歸1、提取左公共因子提取左公共因子 產(chǎn)生式形如：產(chǎn)生式形如：A A1 1| |2 2|n n| | 表示不以表示不以 開頭的字符串。開頭的字符串。 2.2.引進(jìn)非終極符引進(jìn)非終極符A A ，使產(chǎn)生式替換使產(chǎn)生式替換

13、為：為： A AA A | | A A1 1| | 2 2| n n例例1 1：消除下面文法的左公共因子：消除下面文法的左公共因子Stm id := ExpStm id := ExpStm id (ExpL)Stm id (ExpL)ExpL Exp ExpL Exp ExpL Exp,ExpLExpL Exp,ExpL Stmid StmStmid Stm StmStm := Exp:= ExpStmStm ( ExpL )( ExpL )ExpLExp ExpLExpLExp ExpL ExpL ExpL ExpL ，ExpL ExpL 例例2 2：消除下面文法的左公共因子：消除下面文法的

14、左公共因子A AadadA ABcBcB BaAaAB BbBbB替換替換A AadadA AaAcaAcA AbBcbBcB BaAaAB BbBbB提因子提因子A Aa(d|Ac)a(d|Ac)A AbBcbBcB BaAaAB BbBbB引進(jìn)引進(jìn)AAA AaAaA A A d dA A AcAcA AbBcbBcB BaAaAB BbBbB說明：說明：（1）文法中不含左公共因子只是文法中不含左公共因子只是LL（1）文文法的必要條件。法的必要條件。 例如：例如：GS： S-aSb S-aS S- 變換后：變換后：G1SS-aSA A-bA- S- SELECT(S-aSA)=aSELECT

15、(S- )=FOLLOW(S)=#,bSELECT(A-b)=bSELECT(A- )= FOLLOW(S)=#,b化為：化為：SaS(b|)S結(jié)果仍然不是結(jié)果仍然不是LL(1)文法文法。（2 2）一個(gè)文法提取了左公共因子后，只解決）一個(gè)文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的了相同左部產(chǎn)生式右部的FIRSTFIRST集不相交問集不相交問題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無左遞歸時(shí)，則改寫后的文法是左遞歸時(shí)，則改寫后的文法是LL(1)LL(1)文法，文法，否則還需用否則還需用LL(1)LL(1)文法的判別方式進(jìn)行判斷文法的判別方式進(jìn)行判斷才能確定

16、是否為才能確定是否為LL(1)LL(1)文法。文法。2 2、消除左遞歸、消除左遞歸 直接左遞歸直接左遞歸：AA A VN, V* 間接左遞歸間接左遞歸：ABBA A,B VN, , V*（1 1）消除直接左遞歸）消除直接左遞歸 把直接左遞歸改寫為右遞歸把直接左遞歸改寫為右遞歸 如如G5:SSaSb(L=ban|n0) 改為改為：SbSSaS| 消除直接左遞歸的一般方法消除直接左遞歸的一般方法： AA1| A2| Am|1|2|n 其中其中： i 不等于不等于 ， j不以不以A開頭開頭。 改為改為： A 1A| 2A | nA A 1A | 2A | mA | 例例 文法文法G(E):G(E):

17、EEEET|TT|TTTTT* *F|FF|FF(E)|iF(E)|i經(jīng)消去直接左遞歸后變成：經(jīng)消去直接左遞歸后變成： ETEETE E E +TE+TE | | TFTTFT T T * *FTFT | | F(E)|i F(E)|iPP 1 | P 2 | | P m | 1 | 2| nP 1P | 2P | | nP P 1P | 2P | | mP | （2 2）消除間接左遞歸）消除間接左遞歸 將間接左遞歸變?yōu)橹苯幼筮f歸，然后消除將間接左遞歸變?yōu)橹苯幼筮f歸，然后消除直接左遞歸。直接左遞歸。AaBABbBAcBdAaBABbBaBcBBbcBdAaBABbBaBcB | dB BbcB

18、 |5.5 5.5 確定的自頂向下分析方法確定的自頂向下分析方法 1.1.遞歸子程序法遞歸子程序法 2.2.預(yù)測分析法預(yù)測分析法 1.1.遞歸子程序法遞歸子程序法 遞歸下降法遞歸下降法( (Recursive-Descent Parsing)Recursive-Descent Parsing) 對每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相對每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)語法分析子程序應(yīng)語法分析子程序. . 終結(jié)符產(chǎn)生匹配命令終結(jié)符產(chǎn)生匹配命令 非終結(jié)符則產(chǎn)生調(diào)用命令非終結(jié)符則產(chǎn)生調(diào)用命令 文法遞歸相應(yīng)子程序也遞歸，所以稱這文法遞歸相應(yīng)子程序也遞歸，所以稱這種方法為遞歸子程序方法或遞歸下降法。種方法為

19、遞歸子程序方法或遞歸下降法。假設(shè)有文法假設(shè)有文法ZaBaZaBaBbB|cBbB|c則相應(yīng)的遞歸子程序可如下：則相應(yīng)的遞歸子程序可如下：procedure Z( )procedure Z( )begin begin if token=a then Match(a) if token=a then Match(a)； B B； Match(a) Match(a) else error else errorend;end;procedure B ( )procedure B ( )beginbegin if token=b then Match(b); if token=b then Match(

20、b); B; B; else else if token=c if token=c then Match(c); then Match(c); else error else errorend;end;主程序：主程序：Begin readtoken Z endBegin readtoken Z endPROCEDURE match(t); BEGIN IF token=t THEN token:=nexttoken ELSE error END;2.2.預(yù)測分析法預(yù)測分析法一一. . 基本思想基本思想 預(yù)測分析是在每步推導(dǎo)中預(yù)測分析是在每步推導(dǎo)中, ,對被替換的非終對被替換的非終結(jié)符號(hào)結(jié)符號(hào)A

21、 A和當(dāng)前向前看符號(hào)和當(dāng)前向前看符號(hào)a a能選擇能選擇A A的某條產(chǎn)生式的某條產(chǎn)生式進(jìn)行推導(dǎo)。進(jìn)行推導(dǎo)。 非遞歸預(yù)測分析的基本思想是，根據(jù)文法非遞歸預(yù)測分析的基本思想是，根據(jù)文法G G，構(gòu)造一張分析表構(gòu)造一張分析表M M，表中元素表中元素MAMA，aa存放的，要存放的，要么是被選擇的產(chǎn)生式（正確分析情況）；要么是么是被選擇的產(chǎn)生式（正確分析情況）；要么是出錯(cuò)處理程序入口（分析出現(xiàn)錯(cuò)誤）。整個(gè)分析出錯(cuò)處理程序入口（分析出現(xiàn)錯(cuò)誤）。整個(gè)分析是在分析表是在分析表M M的驅(qū)動(dòng)下完成的。的驅(qū)動(dòng)下完成的。二、預(yù)測分析表的構(gòu)造二、預(yù)測分析表的構(gòu)造1 1對文法對文法G G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式A A執(zhí)行第執(zhí)

22、行第2 2步；步；2 2對每個(gè)終結(jié)符號(hào)對每個(gè)終結(jié)符號(hào)aSELECTaSELECT（A A），），把把 A A加至加至MA,aMA,a中；中； 3 3把所有無定義的把所有無定義的MA,aMA,a標(biāo)上錯(cuò)誤標(biāo)記。標(biāo)上錯(cuò)誤標(biāo)記。置置ipip指向指向w#w#的第一個(gè)符號(hào)的第一個(gè)符號(hào),#,#進(jìn)棧，進(jìn)棧，S(S(開始符號(hào)開始符號(hào)) )進(jìn)棧進(jìn)棧 repeatrepeat 令令X X是棧頂符號(hào)，是棧頂符號(hào)，a a是是ipip所指向的符號(hào)；所指向的符號(hào)； if Xif X是一個(gè)終結(jié)符號(hào)或是一個(gè)終結(jié)符號(hào)或# #thenthen if X=a then if X=a then 把把X X從棧中彈出，并且更新從棧中彈出

23、，并且更新ipip else error() else error() else / else /* *X X是非終結(jié)符號(hào)是非終結(jié)符號(hào)* */ / if MX,aif MX,a XY XY1 1Y Y2 2YYk k then begin then begin 把把X X從棧中彈出；從棧中彈出； 把把Y Yk k，Y Yk-1k-1，, Y, Y1 1壓入棧中，即壓入棧中，即Y Y1 1在頂上；在頂上； 輸出產(chǎn)生式輸出產(chǎn)生式XYXY1 1Y Y2 2YYk k end end else error() else error() until X=# / until X=# /* *棧為空棧為空*

24、 */ /三、預(yù)測分析程序三、預(yù)測分析程序例例 G:E E+T | T T T*F | F F i | ( E )試分析輸入串試分析輸入串i+ii+i* *i i是否是句子是否是句子. . 1.1.將文法轉(zhuǎn)換為將文法轉(zhuǎn)換為LL(1)LL(1)文法文法E E+T | TT T*F | FF i | ( E )消除左遞歸消除左遞歸E TEE +TE | T FTT *FT | F i | ( E )可推出可推出的非終結(jié)符表：的非終結(jié)符表：E TEE +TE | T FTT *FT | F i | ( E )EETTF是是是是否否否否否否各非終結(jié)符的各非終結(jié)符的FIRSTFIRST集和集和FOLLOWFOLLOW集：集：FIRST(E)=FIRST(E)=FIRST(T)=FIRST(T)=FIRST(F)=FOLLOW(E)=FOLLOW(E)=FOLLOW(T)=FOLLOW(T)=FOLLOW(F)=ETEE+TE|TFTT*FT|Fi|( E ) ( , i + , ( , i * , ( , i ) , # ) , # + , ) , # + , ) , # * , + , ) , # 各產(chǎn)生式的各產(chǎn)生式的SELECTSELE