第5章自頂向下語(yǔ)法分析方法

1、第第5 5章章 自頂向下語(yǔ)法分析方法自頂向下語(yǔ)法分析方法 教學(xué)要求：教學(xué)要求：本章介紹編譯程序的第二個(gè)本章介紹編譯程序的第二個(gè)階段語(yǔ)法分析的設(shè)計(jì)方法和實(shí)現(xiàn)原理，階段語(yǔ)法分析的設(shè)計(jì)方法和實(shí)現(xiàn)原理，包括自上而下分析的無(wú)回朔的遞歸下降包括自上而下分析的無(wú)回朔的遞歸下降分析、分析、 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ù)測(cè)分析表構(gòu)造，文法，預(yù)測(cè)分析表構(gòu)造，LLLL（1 1）分析法。）分

2、析法。 5.1 5.1 確定的自頂向下分析思想確定的自頂向下分析思想 文法文法G1S:SpASqBAcAdAaBdBBbW=pccadd自頂向下的推導(dǎo)過(guò)程：自頂向下的推導(dǎo)過(guò)程：S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd語(yǔ)法樹：語(yǔ)法樹：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）無(wú)限循環(huán)（文法出現(xiàn)左遞歸）無(wú)限循環(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) 是上下文無(wú)關(guān)是上下文無(wú)關(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) 是上下文無(wú)關(guān)文是上下文無(wú)關(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)生式來(lái)推導(dǎo)）（確定選擇那個(gè)產(chǎn)生式來(lái)推導(dǎo)） 定義：給定上下文無(wú)關(guān)文法的產(chǎn)生式定義：給定上下文無(wú)關(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è)上下文無(wú)關(guān)文法是定義：一個(gè)上

6、下文無(wú)關(guān)文法是的的充要條件是：充要條件是： 對(duì)每個(gè)非終結(jié)符對(duì)每個(gè)非終結(jié)符A的任兩個(gè)不同產(chǎn)生式的任兩個(gè)不同產(chǎn)生式A和和A，滿足滿足SELECT(A)SELECT(A)=其中其中,不能同時(shí)不能同時(shí) *LL(1)文法的含義：文法的含義： 第一個(gè)第一個(gè) 表示：自頂向下分析是表示：自頂向下分析是。 第二個(gè)第二個(gè) 表示：分析過(guò)程中將用表示：分析過(guò)程中將用。 表示：只需表示：只需便可決定如何便可決定如何推導(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)文法。文法。對(duì)輸入串對(duì)輸入串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)對(duì)于文法的開始符號(hào)對(duì)于文法的開始符號(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說(shuō)明：說(shuō)明：（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)生式，且無(wú)題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無(wú)左遞歸時(shí)，則改寫后的文法是左遞歸時(shí)，則改寫后的文法是LL(1)LL(1)文法，文法，否則還需用否則還需用LL(1)LL(1)文法的判別方式進(jìn)行判斷文法的判別方式進(jìn)行判斷才能確定

16、是否為才能確定是否為L(zhǎng)L(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 |（2 2）消除間接左遞歸）消除間接左

17、遞歸 將間接左遞歸變?yōu)橹苯幼筮f歸，然后消除將間接左遞歸變?yōu)橹苯幼筮f歸，然后消除直接左遞歸。直接左遞歸。AaBABbBAcBdAaBABbBaBcBBbcBdAaBABbBaBcB | dB BbcB |5.5 5.5 確定的自頂向下分析方法確定的自頂向下分析方法 1.1.遞歸子程序法遞歸子程序法 2.2.預(yù)測(cè)分析法預(yù)測(cè)分析法 1.1.遞歸子程序法遞歸子程序法 遞歸下降法遞歸下降法( (Recursive-Descent Parsing)Recursive-Descent Parsing) 對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)語(yǔ)法分析子程序應(yīng)語(yǔ)法分析子程序. .

18、 終結(jié)符產(chǎn)生匹配命令終結(jié)符產(chǎn)生匹配命令 非終結(jié)符則產(chǎn)生調(diào)用命令非終結(jié)符則產(chǎn)生調(diào)用命令 文法遞歸相應(yīng)子程序也遞歸，所以稱這文法遞歸相應(yīng)子程序也遞歸，所以稱這種方法為遞歸子程序方法或遞歸下降法。種方法為遞歸子程序方法或遞歸下降法。假設(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 err

19、orend;end;procedure B ( )procedure B ( )beginbegin if token=b then Match(b); if token=b then Match(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:=n

20、exttoken ELSE error END;q產(chǎn)生式產(chǎn)生式AA 被選擇的條件是：被選擇的條件是： 當(dāng)前的輸入符屬于當(dāng)前的輸入符屬于SELECT(SELECT(AA ) )。q至多一個(gè)產(chǎn)生式被選擇的條件是：至多一個(gè)產(chǎn)生式被選擇的條件是： SELECT (A(A k k) ) SELECT (A(A j j )=)=，當(dāng)當(dāng)k k j jq遞歸子程序方法的條件：遞歸子程序方法的條件： (1) (1)SELECT(ASELECT(A k k) )SELECT(A(A j j )=)=，當(dāng)當(dāng)k k j j (2) (2)任一非終結(jié)符任一非終結(jié)符A A都不是左遞歸的。都不是左遞歸的。2.2.預(yù)測(cè)分析法

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

22、驅(qū)動(dòng)下完成的。的驅(qū)動(dòng)下完成的。二、預(yù)測(cè)分析表的構(gòu)造二、預(yù)測(cè)分析表的構(gòu)造1 1對(duì)文法對(duì)文法G G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式A A執(zhí)行第執(zhí)行第2 2步；步；2 2對(duì)每個(gè)終結(jié)符號(hào)對(duì)每個(gè)終結(jié)符號(hào)aSELECTaSELECT（A A），），把把 A A加至加至MA,aMA,a中；中； 3 3把所有無(wú)定義的把所有無(wú)定義的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é)符

23、號(hào)或是一個(gè)終結(jié)符號(hào)或# #thenthen if X=a then if X=a then 把把X X從棧中彈出，并且更新從棧中彈出，并且更新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 e

24、nd end else error()else error() until X=# /until X=# /* *棧為空棧為空* */ /三、預(yù)測(cè)分析程序三、預(yù)測(cè)分析程序例例 G:E E+T | T T T*F | F F i | ( E )試分析輸入串試分析輸入串i+ii+i* *i i是否是句子是否是句子. . 1.1.將文法轉(zhuǎn)換為將文法轉(zhuǎn)換為L(zhǎng)L(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)生式的SELECTSEL