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

1、第4章語法分析自上而下分析第4章 語法分析 自上而下分析第4章語法分析自上而下分析4.1 語法分析器的功能4.2 自上而下分析面臨的問題4.3 LL(1)分析法4.4 遞歸下降分析程序構造4.5 預測分析程序第4章 語法分析 自下而上分析第4章語法分析自上而下分析n語法分析器的位置語法分析器詞法分析器符號表編譯程序的后續(xù)部分token取下一個單詞語法樹第4章語法分析自上而下分析語法分析器n語法分析器的輸入qToken序列：詞法分析產(chǎn)生的輸出，是各個單詞都正確的源程序，是一個有限序列n語法分析器的功能q按照語言的語法構成規(guī)則, 識別輸入的符號串輸入的符號串能否構成一個句子。規(guī)則是用文法的產(chǎn)生式來

2、定義的。q對給定一個輸入串，如何判定它是不是一個句子？q根據(jù)文法的產(chǎn)生式規(guī)則，從開始符號出發(fā)，看能否推導出這個輸入串匹配的句子。這就需要建立與輸入串匹配的語法分析樹。n語法分析器的輸出q分析樹：如何表示？ P89q錯誤處理信息：定位、繼續(xù)編譯第4章語法分析自上而下分析 常用的語法分析方法：常用的語法分析方法：根據(jù)建立語法分析樹的方法不同，語法分析方法有兩類： 自頂向下分析遞歸下降分析預測分析(LL)自底向上分析 算符優(yōu)先分析 LR分析( LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR)LALR)自上而下分析法自上而下分析法：從文法的開始符號出發(fā)，向下推導從文法的

3、開始符號出發(fā)，向下推導(使用最左推使用最左推導導) ，盡可能使用各種產(chǎn)生式，推導出與輸入串，盡可能使用各種產(chǎn)生式，推導出與輸入串匹配的句子。匹配的句子。自下而上分析法自下而上分析法：從輸入符號串開始，逐步進行歸約從輸入符號串開始，逐步進行歸約(最右推導的最右推導的逆過程逆過程)，直至歸約到文法的開始符號。，直至歸約到文法的開始符號。第4章語法分析自上而下分析自頂向下分析n自上而下分析的主旨是：對任何輸入串，試圖用一切可能的辦法，從文法的開始符號出發(fā)，自上而下地為輸入串建立一個語法樹。n從推導的角度看，從開始符號出發(fā)，使用最左推導，試圖推導出與輸入符號串相同的句子。n從語法樹的角度看，從根節(jié)點出

4、發(fā)，反復使用所有可能的產(chǎn)生式，謀求輸入串的匹配，試圖向下構造一棵語法樹，其末端結點正好與輸入符號串相同。n這是一個反復試探的過程。第4章語法分析自上而下分析自頂向下分析面臨的問題自頂向下分析面臨的問題 n問題1：回溯例1：設有文法(1) S - xAy (2) A - *|* 現(xiàn)有輸入串：x*y 其分析過程如下：SxAy*失敗，需要退回，重新選取失敗，需要退回，重新選取A A的侯選式的侯選式這時使得分析器的動作不穩(wěn)定這時使得分析器的動作不穩(wěn)定產(chǎn)生的原因？x*y輸入符號串：第4章語法分析自上而下分析n問題2：左遞歸n左遞歸：是左遞歸的，如果一個文法中存在某個非終結符號A，使A A。n如果是A A

5、，則稱為直接左遞歸，否則稱為間接左遞歸。例2：設有文法：E-E+T|TT-T*F|FF-(E)|i(1) 現(xiàn)有輸入串i*i+i, 其分析過程是：EE+TE+TE+T失?。河捎谑褂米钭笸茖?，對左遞歸文法進失?。河捎谑褂米钭笸茖?，對左遞歸文法進行自頂向下分析時，會導致死循環(huán)。行自頂向下分析時，會導致死循環(huán)。產(chǎn)生的原因？第4章語法分析自上而下分析結論n左遞歸和回溯問題的產(chǎn)生直接與描述語言的文法有關n因此，要對文法進行確定的自頂向下分析應該改造文法，使其不含左遞歸和回溯第4章語法分析自上而下分析左遞歸的消除n1. 1. 直接左遞歸的消除：直接左遞歸的消除：q假定產(chǎn)生式為：假定產(chǎn)生式為：PP|PP|，將

6、其替換為形式等價，將其替換為形式等價的產(chǎn)生式組：的產(chǎn)生式組：例2：文法 E - E+T|T T-T*F|F F-(E)|i消去左遞歸后為： E - TE E-+TE| T-FT T-*FT| F-(E)|i PP P P 第4章語法分析自上而下分析q一般而言，產(chǎn)生式為：一般而言，產(chǎn)生式為：AAA1 1|A|A2 2|A|An n| |1 1| |2 2|m m 將其替換為：將其替換為：A1 B|2 B |m BB1 B|2 B |n B| 2. 2. 間接左遞歸的消除間接左遞歸的消除 (1) (1) 代入代入 (2) (2) 消除直接左遞歸消除直接左遞歸第4章語法分析自上而下分析回 溯n回溯產(chǎn)

7、生的真正原因真正原因是：某非終結符對應多個侯選式，它們右部的第一個終結符相同，從而導致語法分析器選擇了錯誤的侯選式。n如果希望沒有回溯，對文法有什么要求？第4章語法分析自上而下分析n定義：對G的所有非終結符的每個侯選式定義首終結符集： First() = a| a,aVT若 ，則 First() 因此，不產(chǎn)生回溯的條件不產(chǎn)生回溯的條件就是：對非終結符A的任意兩個不同的侯選式ai 和aj ，都有：First(ai)aj) = 當要求用A進行匹配時，就能根據(jù)所面臨的輸入字符，準確地選取一個A的侯選式。第4章語法分析自上而下分析消除回溯的方法n反復使用“提取公共左因子提取公共左因子”的方法的方法來改

8、造文法，使得文法的每個非終結符號的各個候選式的首終結符兩兩不相交，來避免回溯。n例： 設產(chǎn)生式為設產(chǎn)生式為：A1 1|2 2|n n 將其替換為：將其替換為：AAA1|2|n第4章語法分析自上而下分析n例3：有如下兩個產(chǎn)生式： if E then S1 else S2; if E then S1;提取左因子后： if E then S1 B; B else S2 | ;第4章語法分析自上而下分析n是否滿足：沒有左遞歸，每個侯選式的首終結符集不相交這兩個條件，就一定能進行有效的自頂向下分析呢？n例：使用下述文法對 i + i 進行分析： E TE E +TE| T FT T *FT| F (E)

9、|i第一步：ifirst(TE) ifirst(FT) ifirst(F)ETEFTi第三步：+first(E)第二步：+first(T) 用用自動匹配自動匹配 不讀輸入符號不讀輸入符號+TEFTiLL(1)分析條件：第4章語法分析自上而下分析n并不是在任何情況下，A面對輸入符號a， a不屬于A的任何侯選式，但A中含產(chǎn)生式時都可以使用自動匹配。n定義(后隨符號集)：假定S是文法的開始符號，對于 AN N： FOLLOW(A)=a|SFOLLOW(A)=a|SAaAa，aaT T 特別，若 S SAA，則，則，# # FOLLOW(A)FOLLOW(A)n因此，當非終結符A面臨a時， 且a不屬于

10、A的任何侯選首終結符集，但A的某個候選首終結符集中含，只有當a FOLLOW(A)FOLLOW(A)時才能自動進行匹配。* * *第4章語法分析自上而下分析nLL(1) 文法：(對文法進行不帶回溯的確定的自頂向下分析的條件)，據(jù)此判別是否為LL(1)文法。q(1) 文法不含左遞歸q(2) 對文法中的任一個非終結符A的各個產(chǎn)生式的侯選首終結符集兩兩不相交，即：若A1|2|n ，則 First(ai)aj) = q(3) 對文法中的每個非終結符A,若它存在某個首選符集含有 ，則 First(A)A) = 第4章語法分析自上而下分析LL(1)文法的分析過程n(P73)假設要用非終結符A進行匹配，面臨

11、輸入符號a，A的所有侯選式為： A1|2|nn分析過程為分析過程為：q若a First(Ai),則使用i去執(zhí)行匹配任務。q若a不屬于任何一個產(chǎn)生式的首選符集，n(1)若不屬于任何一個 First(Ai)，則出錯。n(2)若屬于某個First(Ai),同時a Follow(A), 則讓A 與自動匹配；否則，a的出現(xiàn)是一種語法錯誤。第4章語法分析自上而下分析兩個集合的構造1、FIRST2、FOLLOW第4章語法分析自上而下分析1、FIRST集的求法集的求法 (1)文法符號的終結首符集：FIRST（X） XVT FIRST（X) =X XVN, 需觀察X為左部的產(chǎn)生式規(guī)則定義：定義：FIRST()=

12、a| a.=a| a.特別是，若特別是，若 ，則規(guī)定，則規(guī)定 FIRST ()*第4章語法分析自上而下分析FIRST集的求法集的求法 Aa. A1| 2|.| n FIRST(A)AAX1X2.XKA X1X2.XK*a. X2.XKFIRST(X1)FIRST(X2).X2.XK . 第4章語法分析自上而下分析FIRST集的求法集的求法 例：求下面每個非終結符號的FIRST集合： E TE E +TE |T FTT *FT |F (E) | i FIRST(E) = FIRST(E )=FIRST(T) =FIRST(T )=FIRST(F) = （，i +, *, （, i （, i 第4

13、章語法分析自上而下分析1 1、FIRSTFIRST集的求法集的求法 (1)文法符號的終結首符集：FIRST（X） XVT FIRST（X) =X XVN, 需觀察X為左部的產(chǎn)生式規(guī)則(2)候選式的終結首符集：FIRST（） =X1X2Xn第4章語法分析自上而下分析2 2、FOLLOWFOLLOW集的求法集的求法 BAFOLLOW(A)BA*若A是開始符號#FIRST()FIRST()FOLLOW(B)FOLLOW(B)FOLLOW(B)FOLLOW(B)第4章語法分析自上而下分析FOLLOWFOLLOW集的求法集的求法 例：求下面每個非終結符號的FOLLOW集： E TE E +TE |T F

14、TT *FT |F (E) | i FIRST(E) = (, i FIRST(E) = (, i FIRST(E FIRST(E )= +, )= +, FIRST(T) = (, i FIRST(T) = (, i FIRST(T FIRST(T )= )= * *, , FIRST(F) = (, i FIRST(F) = (, i FOLLOW(E) = FOLLOW ( E )=FOLLOW (T) =FOLLOW (T )=FOLLOW (F) = #, ) #, ) +,#, ) +,#, ) *,+,#, ) 第4章語法分析自上而下分析練習：求下題的FIRST和FOLLOW集合

15、。 Sa | (T) TST T ,ST | STT FIRST a , ( a , ( , , FOLLOW # , , ) ) ) 第4章語法分析自上而下分析4.4 遞歸下降分析程序的構造void E() T; E第4章語法分析自上而下分析4.5 預測分析程序一、預測分析表構造二、預測分析程序第4章語法分析自上而下分析4.5 預測分析程序一、預測分析表的構造 1、FIRST集合構造 2、FOLLOW集合構造 3、預測分析表的構造第4章語法分析自上而下分析3、預測分析表的構造、預測分析表的構造 A1|2|nLL（1）分析過程為）分析過程為：(1)若a FIRST(i),則使用i去執(zhí)行匹配任務

16、。(2)若a不屬于任何一個產(chǎn)生式的首選符集，則：n若屬于某個FIRST(i),同時a FOLLOW(A), 則讓A 與自動匹配；n否則，a的出現(xiàn)是一種語法錯誤。構造分析表的方法：構造分析表的方法：（1）對每個A，執(zhí)行第2步和第3步；（2）對每個終結符a FIRST(），把A加至MA,a中；（3）若FIRST()，則對任何b FOLLOW()，把A加至MA,b中；（4）把所有無定義的位置上標上“出錯標志”。第4章語法分析自上而下分析例：E TEE +TE |T FTT *FT |F (E) |i i+*()#EETTFETEETEE+TEE E T FTT FTT T T FiF(E)T*FT3

17、、預測分析表的構造、預測分析表的構造 第4章語法分析自上而下分析二、預測分析程序4.5 預測分析程序第4章語法分析自上而下分析初始：a1a2.an#S#分析棧輸入串某個中間結果a.#X.#分析棧輸入串a(chǎn). xVN查看預測分析表: Xx1.xn分析棧a.#. .#輸入串x1xn下一步產(chǎn)生的結果第4章語法分析自上而下分析a.#X.#分析棧輸入串b. xVT.#.#分析棧輸入串X=aX!=aX=a =# 下一步產(chǎn)生的結果某個中間結果 出錯！ 分析結束 第4章語法分析自上而下分析2、預測分析過程實例、預測分析過程實例n下面用預測分析方法對輸入串i+i*i# 進行分析，給出棧的變化過程如下：步驟分析棧剩余輸入串所用產(chǎn)生式2 #ET i+i*i#ETETFT 1#E i+i*i#第4章語法分析自上而下分析3#ETFi+i*i#4#ETii+