第4章語法分析(2)

1、1第四章第四章 語法分析語法分析(2)4.4 自頂向下語法分析24.4 自頂向下語法分析自頂向下語法分析q 自頂向下(top-down)的語法分析算法是通過最左推導(dǎo)來分析輸入的單詞序列(tokens)q 自頂向下的分析算法有兩類允許回溯的遞歸下降分析LL(1)分析：一種沒有回溯的遞歸下降分析法。wSlm3例例4.14 id+id*id的語法分析樹構(gòu)造過程的語法分析樹構(gòu)造過程q 對應(yīng)文法E TE E +TE | T FT T *FT | F ( E ) | id4id+id*id E TE E +TE | T FT T *FT | F ( E ) | idE=TE=FTE=idTE=idE=id

2、+TElookaheada+b*c最左推導(dǎo)最左推導(dǎo)5id+id*id64.4.1 遞歸下降語法分析的一般方法遞歸下降語法分析的一般方法q 為輸入tokens尋找最左推導(dǎo)。q 遞歸下降分析的基本方法將一個非終結(jié)符A的文法規(guī)則看作識別A的過程的定義。A的文法規(guī)則的右部指示過程的代碼結(jié)構(gòu)匹配文法規(guī)則中出現(xiàn)的終結(jié)符a：match(a)調(diào)用文法規(guī)則中出現(xiàn)的非終結(jié)符文法S cAd A ab | a寫出代碼7非終結(jié)符對應(yīng)的典型過程非終結(jié)符對應(yīng)的典型過程8考慮文法S cAd A ab | a為輸入串w = cad 建立分析樹。例例4.15 文法文法cadScdAcadScdAabcadScdAacadScdA

3、ab出現(xiàn)問題出現(xiàn)問題: 回溯回溯backtrack！cadScdAa9缺點(diǎn)缺點(diǎn)q 不能處理左遞歸q 復(fù)雜的回溯技術(shù)q 回溯導(dǎo)致語義工作推倒重來q 難以報告出錯的確切位置q 效率低104.4.5 FIRST和和FOLLOW函數(shù)函數(shù)q 對文法加什么樣的限制可以保證沒有回溯？q 先定義兩個和文法有關(guān)的函數(shù)FIRST()FOLLOW(A)10S=stmt=. if ( abc 0 )lookahead例：stmt if expr then stmt else stmt | while expr do stmt | begin stmt_list end First(if expr then stmt

4、else stmt)= if First(while expr do stmt)= while 另一種情況：另一種情況：11E TEE +TE | T FT T *FT | F ( E ) | idFirst(TE)= First(T) = First(+TE) = + Follow(E) = ), $ E=E=. ( a + c ) * elookahead12FIRST( )q FIRST()是從推導(dǎo)出的串的起始終結(jié)符的集合。q FIRST( ) = a | a, a VT 特別是， 時，規(guī)定FIRST( ) 例如：A xB|yC，F(xiàn)irst(xB)=x,First(yC)=yq 對A的任

5、何兩個不同的選擇i 和j，希望有FIRST(i ) FIRST(j ) = 但有一個前提， FIRST(i )和FIRST(j)都不含*例如：A 1 | 2| 3假設(shè)First (1)=a,b, First(2)=c,d,e,First(3)=f,gS uAvBw, 當(dāng)前輸入:c*13FOLLOW(A)q FOLLOW(A)是在所有句型中緊跟在A后面的終結(jié)符集合。q FOLLOW(A) = a|S Aa，a VTS Aa 約定：如果A是某個句型的最右符號（SA），那么$屬于FOLLOW(A) 因?yàn)?S$ A$*14計(jì)算計(jì)算FIRST(X)q若X VT，則FIRST(X) = X。q若X ，則將

6、 加入FIRST(X)。 q若X VN，且X Y1Y2Yk ，則將FIRST(Y1) 加入FIRST(X) 若Y1 ，將FIRST(Y2) 加入FIRST(X)； 若Y1 Y2 ，將FIRST(Y3) 加入FIRST(X)； 若Y1.Yk-1 ，將FIRST(Yk) 加入FIRST(X)； 若對所有的j=1,2,k, Yj* ，將加入FIRST(X)；例如：X為a*例如A xB|yC，F(xiàn)irst(xB)=x,First(yC)=y, First(A)=x,y;15q 例：stmt if expr then stmt else stmt | while expr do stmt| begin s

7、tmt_list endq First(stmt) = ifif, whilewhile, beginbegin P1P2P3IFIFWHILEWHILEBEGINBEGINENDENDstmt產(chǎn)生式P1產(chǎn)生式P2產(chǎn)生式P31515S=stmt=. if ( abc 0 )lookahead First(if expr then stmt else stmt)= if First(while expr do stmt)= while 16計(jì)算計(jì)算FOLLOW(A)q 給定一個非終結(jié)符號A，則集合FOLLOW(A)由終結(jié)符號或$組成，定義如下：若A是文法開始符號，則$在FOLLOW(A)中；若存

8、在產(chǎn)生式A B ，則FIRST()-在Follow(B)中；若存在產(chǎn)生式A B或A B，且*，則FOLLOW(B)包括FOLLOW(A)。1. (因?yàn)椋喝鬉 B，則.Aa.=. B a.,此時，a是B的follow)17q 注意：$標(biāo)記輸入結(jié)束。 永遠(yuǎn)也不是FOLLOW集合中的元素。FOLLOW僅針對非終結(jié)符定義。18例例4.19已知文法產(chǎn)生式：已知文法產(chǎn)生式：S iEtSS | aS eS | E bFIRST(S) = i, aFIRST(S) = e, FIRST(E) = bFOLLOW(S) 包含$；S iEtSS，將FIRST(S)即e加入 FOLLOW(S) S eS，將FOLL

9、OW(S)加入FOLLOW(S) S iEtSS ，將FOLLOW(S)加入FOLLOW(S) 因此，有FOLLOW(S) = FOLLOW(S) =e, $ FOLLOW(E) = taSb19E TEE + TE | T FTT * FT | F (E) | id例例4.17 計(jì)算計(jì)算FIRST集和集和FOLLOW集集FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E) = +, FRIST(T) = *, FOLLOW(E) = FOLLOW(E) = ), $FOLLOW(T) = FOLLOW (T) = +, ), $FOLLOW(F)

10、= +, *, ), $ 204.4.2 預(yù)測語法分析器預(yù)測語法分析器(Predictive Parsing) q 通過改寫文法，消除左遞歸，提取左因子，也許也許可以得到不帶回溯的遞歸下降分析器。 q 對A 1 | 2 | | n，通過觀測候選式所推導(dǎo)出的第一個符號，能夠選擇合適的產(chǎn)生式來擴(kuò)展q 例：stmt if expr then stmt else stmt | while expr do stmt| begin stmt_list endS=stmt=. if ( abc 0 )lookaheadififwhilewhilebeginbeginstmtstmt if expr then

11、 stmt else stmtstmt while expr do stmtstmt begin stmt_list endlookahead文法的預(yù)測分析表22非終結(jié)符非終結(jié)符輸入符號輸入符號 ( lookahead )id+*()$E E T T FETE TFT FidE+TE T T *FT F(E)TFT ETE T E E T E=E=.+TE =. a + c * elookaheadE TEE +TE | T FT T *FT | F ( E ) | idE E + T | TT T * F | FF ( E ) | id文法的預(yù)測分析表23如何構(gòu)造語法分析表如何構(gòu)造語法分析表

12、 M?q 1st : 計(jì)算語法的First集和Follow集q 2nd: 使用構(gòu)造算法來生成M。Parsing Table244.4.6 預(yù)測分析表的構(gòu)造預(yù)測分析表的構(gòu)造算法4.4 預(yù)測分析表的構(gòu)造輸入：文法G輸出：分析表M方法： （1）對文法的每個產(chǎn)生式A ，執(zhí)行(2)和(3)。（2）對FIRST()的每個終結(jié)符a，把A加入MA, a。（3）如果在FIRST()中，對FOLLOW(A)的每個終結(jié)符b（包括$），把A 加入MA, b。（4）M的其它沒有定義的條目都是error。25例例4.38FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E) =

13、+, FRIST(T) = *, FOLLOW(E) = FOLLOW(E) = ), $FOLLOW(T) = FOLLOW (T) = +, ), $FOLLOW(F) = +, *, ), $ E TEE + TE | T FTT * FT | F (E) | idINPUT SYMBOLid+*()$E E T T FETE TFT FidE+TE T T *FT F(E)TFT ETE T E E T 264.4.7 LL(1)文法文法q L: 從左到右掃描輸入串q L : 最左推導(dǎo)q 1 : 向前看一個字符lookaheadq 分析表中沒有多重定義的表目的文法稱為LL(1)文法。2

14、7例例4.19 多重定義的條目多重定義的條目 S iEtSS | aS eS | E bFIRST(S) = i, a FIRST(S) = e, FIRST(E) = b FOLLOW(S) = FOLLOW(S) =e, $ FOLLOW(E) = t非終非終結(jié)符結(jié)符 輸輸 入入 符符 號號 a b eit$S S a S iEtSS S S S eS S E E b 28q 該文法是具有二義性的：遇到e(else)時不知該選擇哪個產(chǎn)生式。q 消除二義性可以只選擇S eS ，遵循與e最近的t(then)配對的原則29LL(1)文法文法q LL(1)文法中的任何兩個產(chǎn)生式文法中的任何兩個產(chǎn)生

15、式A | 都滿足下列條都滿足下列條件：件：FIRST( ) FIRST( ) = 不存在終結(jié)符a，使得 和 導(dǎo)出的串都以a開始。若若 * ，那么，那么FIRST( ) FOLLOW(A) = 和 至多一個能導(dǎo)出空串 如果導(dǎo)出空串，那么不能導(dǎo)出以FOLLOW(A)中終結(jié)符開始的任何串。30LL(1)文法文法q LL(1)文法具有的特殊性質(zhì)沒有公共左因子不是二義的不含左遞歸文法S cAd A ab | a要提取公共左因子aA aAA b | 要提取消除左遞歸D bDD aD | S cDD Da | bS=cD=cbD= Follow(S)= $ = Follow(D) = Follow(D)31

16、4.4.4 非遞歸的預(yù)測分析非遞歸的預(yù)測分析q 可以使用顯式的棧，而不是遞歸調(diào)用來完成分析。32成功的自頂向下的分析的一般示意法：成功的自頂向下的分析的一般示意法：q 兩個基本動作：利用文法選擇A 將棧頂部的非終結(jié)符A替換成串。將棧頂?shù)挠浱柡拖乱粋€輸入記號匹配。分析棧 輸入(lookahead) 動作$StartSymbol InputString$ $ $ 接受 33例：生成配對括號的文法例：生成配對括號的文法S (S) S | 對串（），下表給出自頂向下的分析程序的動作：分析棧輸入動作$ S ( ) $ S (S) S $ S ) S ( ( ) $ 匹配$ S ) S ) $ S $ S

17、 ) ) $ 匹配$ S $ S $ $ 接受 自頂向下的分析程序的動作對于LL(1)文法，將 邊作為默認(rèn)選擇可以解決是否選擇一個 邊的二義性問題。34a + b $輸入預(yù)測分析程序分析表分析表M輸出 XYZ$棧35輸入：輸入：輸入符號串w和文法G的分析表M輸出：輸出：若wL(G)，則輸出w的最左推導(dǎo)； 否則，報告出錯信息。方法：初始狀態(tài)： $在棧底，S在棧頂； w$在輸入緩沖區(qū)中。 預(yù)測分析程序利用預(yù)測分析表M對于輸入作出分析。 算法算法4.3 非遞歸預(yù)測分析方法非遞歸預(yù)測分析方法36置ip指向w$的第一個符號，棧為$和開始符號Srepeat 令X是棧頂符號, a是ip所指向的符號； if

18、X 是一個終結(jié)符號或$ then if X=a then從棧中彈出X，ip指向下一個符號 else error() else /*X是非終結(jié)符號*/ if MX,a=XY1Y2. . Yk then begin從棧中彈出X; 將 Yk,Yk-1,. .,Y1壓入棧中，即Y1在棧頂； 輸出產(chǎn)生式 XY1Y2. . Yk end else error()until X=$ /*棧為空*/圖4-14 預(yù)測分析程序預(yù)測分析程序Input pointer就是就是lookahead37例例4.16圖圖4-15 文法的分析表M非終結(jié)符非終結(jié)符E TEE +TE | T FT T *FT | F ( E )

19、| id輸入符號輸入符號id+*()$E E T T FETE TFT FidE+TE T T *FT F(E)TFT ETE T E E T 38圖圖4-16 預(yù)測分析器在輸入預(yù)測分析器在輸入id+id*id上的動上的動作作 $E$ET$ETF$ETid$ET$E$ET+$ETid + id * id$id + id * id$id + id * id$id + id * id$+ id * id$+ id * id$+ id * id$id * id$E TET FTF idT E +TESTACKINPUTOUTPUT39圖圖4-16 預(yù)測分析器在輸入預(yù)測分析器在輸入id+id*id上的

20、動上的動作作 (續(xù)續(xù))STACKINPUTOUTPUT$ETF$ETid$ET$ETF*$ETF$ETid$ET$E$id * id$id * id$* id$* id$id$id$T FTF idT *FTF idT E 40例子采用最左推導(dǎo)例子采用最左推導(dǎo)E TE FTE id TE id E id + TE id + FTE id + id TE id + id * FTE id + id * id TE id + id * id E id + id * id已經(jīng)掃描過的輸入符號加上棧中的文法符號(from top to bottom)構(gòu)成該推導(dǎo)的左句型左句型。414.4.8 出錯恢復(fù)（

21、出錯恢復(fù)（Error Recovery）q 詞法錯誤如標(biāo)識符、關(guān)鍵字或算符的拼寫錯q 語法錯誤如算術(shù)表達(dá)式的括號不配對q 語義錯誤如算符作用于不相容的運(yùn)算對象q 邏輯錯誤如無窮的遞歸調(diào)用42分析器對錯誤處理的基本目標(biāo)分析器對錯誤處理的基本目標(biāo)q 清楚而準(zhǔn)確地報告錯誤的出現(xiàn)q 迅速地從每個錯誤中恢復(fù)過來，以便診斷后面的錯誤，并盡量少出現(xiàn)偽錯誤q 不應(yīng)該使正確程序的處理速度降低太多 43棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配棧頂是非終結(jié)符棧頂是非終結(jié)符A，輸入符號是，輸入符號是a，而，而MA , a是空是空白白 No allowable actions非遞歸預(yù)測分析在

22、什么場合下發(fā)現(xiàn)錯誤非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤44Panic Mode Recovery(應(yīng)急方式應(yīng)急方式)q 非遞歸預(yù)測分析采用緊急方式的錯誤恢復(fù)，發(fā)現(xiàn)錯誤時，分析器拋棄一些輸入記號，直到輸入記號屬于某個指定的同步記號集合為止。45選擇同步記號集合的啟發(fā)式方法選擇同步記號集合的啟發(fā)式方法q 把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合中。if expr then（then是expr的一個同步記號）46選擇同步記號集合的啟發(fā)式方法選擇同步記號集合的啟發(fā)式方法q 把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中。assign-stmt := expr ; if （賦值語句的開始符號作為表達(dá)式的同步符號，以免遺漏分號時忽略一大段程序。）47選擇同步記號集合的啟發(fā)式方法選擇同步記號集合的啟發(fā)式方法q 把FIRST(A)的終結(jié)符加入A的同步記號集合。q 如果A * ，可以將產(chǎn)生空串的產(chǎn)生式作為默認(rèn)選擇q 如果棧頂?shù)慕K結(jié)符不能被匹配，彈出該記號，相當(dāng)于所有其它記號都在同步記號集合中。48Revised Parsing Table / ExamplesynchsynchsynchNon-terminalINPUT SYMBOLid+*()$EETTFETETFTFidE+TET T*FTF(E)TFTETET E E T synchsynchsynch