1、編譯原理,第四章 語法分析自上而下分析,詞法分析器,語法分析器,語義分析與中間代碼生成器,優(yōu)化段,表 格 管 理,出 錯 處 理,目標(biāo)代碼生成器,第四章 語法分析自上而下分析,本章主要介紹語法分析的處理 要進(jìn)行語法分析，必須對語言的語法結(jié)構(gòu)進(jìn)行描述。 采用正規(guī)式和有限自動機(jī)可以描述和識別語言的單詞符號； 用上下文無關(guān)文法來描述語法規(guī)則。,上下文無關(guān)文法的定義： 一個上下文無關(guān)文法G是一個四元式 G=(VT，VN，S，P)，其中 VT：終結(jié)符集合(非空) VN：非終結(jié)符集合(非空)，且VT VN= S：文法的開始符號，SVN P：產(chǎn)生式集合(有限)，每個產(chǎn)生式形式為 P， PVN， (VT VN

2、)* 開始符S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。,例，定義只含+，*的算術(shù)表達(dá)式的文法 G=， 其中，P由下列產(chǎn)生式組成： E i E E+E E E*E E (E),定義：稱A直接推出，即 A 僅當(dāng)A 是一個產(chǎn)生式， 且， (VT VN)* 。 如果1 2 n，則我們稱這個序列是從1到n的一個推導(dǎo)。若存在一個從1到n的推導(dǎo)，則稱1可以推導(dǎo)出n 。 例：對文法(1) E (E) (E+E) (i+E) (i+i),用 表示：從1出發(fā)，經(jīng)過0步或若干步，可以推出n。,所以 ： 即 或,定義：假定G是一個文法，S 是它的開始符號。如果 ，則稱是一個句型。僅含終結(jié)符號的句型是一個句子。文法G所產(chǎn)生

3、的句子的全體是一個語言，將它記為 L(G)。,通常，用 表示：從1出發(fā)，經(jīng)過一步或若干步，可以推出n。,4.1 語法分析器的功能,語法分析的任務(wù)是分析一個文法的句子結(jié)構(gòu)。 語法分析器的功能：按照文法的產(chǎn)生式(語言的語法規(guī)則)，識別輸入符號串是否為一個句子(合式程序)。,.,語法分析的方法： 自下而上分析法(Bottom-up) 基本思想：從輸入串開始，逐步進(jìn)行“歸約”，直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。 算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語法分析。適合分析表達(dá)式。 LR分析法：規(guī)范歸約,G(E)： E

4、 i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E,i,+,*,i,i,語法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) 基本思想：它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找匹配的推導(dǎo)。 遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個相應(yīng)的子程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現(xiàn)對輸入串的識別。 預(yù)測分析程序 優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。,4.2 自上而下分析面臨的問題,自上而下就是從文法的開始符號出發(fā)，向下推導(dǎo)，推出句子。 帶“回溯”的

5、 不帶回溯的遞歸子程序(遞歸下降)分析方法。 自上而下分析的主旨：對任何輸入串，試圖用一切可能的辦法，從文法開始符號(根結(jié)點)出發(fā)，自上而下地為輸入串建立一棵語法樹。或者說，為輸入串尋找一個最左推導(dǎo)。,例3.4.1 假定有文法G(S): (1) SxAy (2) A*|* 分析輸入串x*y(記為)。,當(dāng)某個非終結(jié)符有多個產(chǎn)生式候選時，可能帶來如下問題: 1. 分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹配成功時，這種匹配可能是暫時的。出錯時，不得不“回溯”。 2. 文法左遞歸問題。一個文法是含有左遞歸的，如果存在非終結(jié)符P,含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。,4.3 LL(1)分析法

6、,構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性 克服回溯,4.3.1 左遞歸的消除,直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為 PP | 其中不以P開頭。 可以把P的規(guī)則等價地改寫為如下的非直接左遞歸形式： PP PP|,左遞歸變右遞歸,一般而言，假定P關(guān)于的全部產(chǎn)生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每個都不等于，每個都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： P1P | 2P | | nP P1P | 2P | | mP | ,左遞歸變右遞歸,例 文法G(E): EET | T TT*F | F F(E) | i 經(jīng)消

7、去直接左遞歸后變成： ETE E+TE | TFT T*FT | F(E) | i,(4.2),PP1 | P2 | | Pm | 1 | 2|n P1P | 2P | | nP P1P | 2P | | mP | ,例如文法G(S): SQc|c QRb|b RSa|a (4.3) 雖沒有直接左遞歸，但S、Q、R都是左遞歸的 SQcRbcSabc,一個文法消除左遞歸的條件： 不含以為右部的產(chǎn)生式 不含回路。,消除左遞歸的算法: 1. 把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，Pn；按此順序執(zhí)行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 D

8、O 把形如PiPj的規(guī)則改寫成 Pi1|2|k ; (其中Pj1|2|k是關(guān)于Pj的所有規(guī)則) 消除關(guān)于Pi規(guī)則的直接左遞歸性 END 3. 化簡由2所得的文法。去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。,例 考慮文法G(S) SQc|c QRb|b RSa|a 令它的非終結(jié)符的排序為R、Q、S。 對于R，不存在直接左遞歸。 把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)?QSab | ab | b,例 考慮文法G(S) SQc|c QRb|b RSa|a 令它的非終結(jié)符的排序為R、Q、S。 Q的規(guī)則變?yōu)?QSab | ab | b 現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S

9、變成 SSabc | abc | bc | c,例 考慮文法G(S) SQc|c QRb|b RSa|a S變成 SSabc | abc | bc | c 消除S的直接左遞歸后： SabcS | bcS | cS SabcS | QSab |ab | b RSa|a,例 考慮文法G(S) SQc|c QRb|b RSa|a 消除S的直接左遞歸后： SabcS | bcS | cS SabcS | QSab |ab | b RSa|a 關(guān)于Q和R的規(guī)則已是多余的，化簡為： SabcS | bcS | cS SabcS | (4.4),注意，由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一

10、樣。但不難證明，它們都是等價的。 例如，若對文法(4.3)的非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是： SQc | c QRb | b RbcaR | caR |a R (4.5) R bca R | 文法(4.4)和(4.5)的等價性是顯然的。,4.3.2 消除回溯、提左因子,為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。 A 1 | 2 | | n,令G是一個不含左遞歸的文法，對G的所有非終結(jié)符的每個候選定義它的終結(jié)首符集FIRST()為：,特別是，若 ，

11、則規(guī)定FIRST()。,如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個不同候選 i和 j FIRST(i)FIRST( j) 當(dāng)要求A匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符號a，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含a的。,提取公共左因子: 假定關(guān)于A的規(guī)則是 A 1 | 2 | | n | 1 | 2 | | m (其中，每個 不以開頭) 那么，可以把這些規(guī)則改寫成 AA | 1 | 2 | | m A 1 | 2 | | n 經(jīng)過反復(fù)提取左因子，就能夠把每個非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。,ETE E+TE | TFT T

12、*FT | F(E) | i i + i,4.3.3 LL(1)分析條件,i + i,IP,E,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT |

13、F(E) | i,i + i,IP,E,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E)

14、: ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,i + i,IP,E,T,E,F,T,i,+,T,E,F,T,i,G(E): ETE E+TE | TFT T*FT | F(E) | i,S T+,假定S是文法G的開始符號，對于G的任何非終結(jié)符A，我們定義,特別是，若 ，則規(guī)定 FOLLOW(A),4

15、.3.3 LL(1)分析條件,構(gòu)造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸， 2. 對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若 A 1| 2| n 則 FIRST( i)FIRST( j) (ij) 3. 對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含，則 FIRST( i)FOLLOW(A)= i=1,2,.,n 如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。,對于一個滿足上述條件的文法，可以對其輸入串進(jìn)行有效的無回溯的自上而下分析。 假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生式為 A 1 | 2 | | n 1.

16、若aFIRST( i)，則指派 i執(zhí)行匹配任務(wù)； 2. 若a不屬于任何一個候選首符集，則： (1) 若屬于某個FIRST(i )且 aFOLLOW(A)， 則讓A與自動匹配。 (2) 否則，a的出現(xiàn)是一種語法錯誤。,回顧：LL(1)分析法,構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性 克服回溯,一般而言，假定P關(guān)于的全部產(chǎn)生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每個都不等于，每個都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： P1P | 2P | | nP P1P | 2P | | mP | ,消除左遞歸的算法: 1. 把文法G的所有非終結(jié)符按

17、任一種順序排列成P1，P2，Pn；按此順序執(zhí)行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的規(guī)則改寫成 Pi1|2|k ; (其中Pj1|2|k是關(guān)于Pj的所有規(guī)則) 消除關(guān)于Pi規(guī)則的直接左遞歸性 END 3. 化簡由2所得的文法。去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。,回顧：LL(1)分析法,構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性 克服回溯,4.3.2 消除回溯、提左因子,為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個候選去執(zhí)行任

18、務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。 A 1 | 2 | | n,令G是一個不含左遞歸的文法，對G的所有非終結(jié)符的每個候選定義它的終結(jié)首符集FIRST()為：,特別是，若 ，則規(guī)定FIRST()。,如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個不同候選 i和 j FIRST(i)FIRST( j) 當(dāng)要求A匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符號a，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含a的。,提取公共左因子: 假定關(guān)于A的規(guī)則是 A 1 | 2 | | n | 1 | 2 | | m (其中，每個 不以開頭) 那么，可以把這些規(guī)則改寫成 AA |

19、 1 | 2 | | m A 1 | 2 | | n 經(jīng)過反復(fù)提取左因子，就能夠把每個非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。,i + i,IP,E,T,E,F,T,i,+,T,E,ETE E+TE | TFT T*FT | F(E) | i,假定S是文法G的開始符號，對于G的任何非終結(jié)符A，定義,特別是，若 ，則規(guī)定 FOLLOW(A),FOLLOW定義,構(gòu)造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸， 2. 對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若 A 1| 2| n 則 FIRST( i)FIRST( j) (ij) 3. 對文法

20、中的每個非終結(jié)符A，若它存在某個候選首符集包含，則 FIRST( i)FOLLOW(A)= i=1,2,.,n 如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。,對于一個滿足上述條件的文法，可以對其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生式為 A 1 | 2 | | n 1. 若aFIRST( i)，則指派 i執(zhí)行匹配任務(wù)； 2. 若a不屬于任何一個候選首符集，則： (1) 若屬于某個FIRST(i )且 aFOLLOW(A)， 則讓A與自動匹配。 (2) 否則，a的出現(xiàn)是一種語法錯誤。,構(gòu)造FIRST(),對每一文法符號XV

21、TVN構(gòu)造FIRST(X) 連續(xù)使用下面的規(guī)則，直至每個集合FIRST不再增大為止： 1. 若XVT，則FIRST(X)X。 2. 若XVN，且有產(chǎn)生式Xa，則把a(bǔ)加入到FIRST(X)中；若X也是一條產(chǎn)生式，則把也加到FIRST(X)中。,3. 若XY是一個產(chǎn)生式且YVN，則把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若XY1Y2Yk是一個產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)IRST(Yj)都含有(即Y1Yi-1)， 則把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有，j1，2，k，則把加

22、到FIRST(X)中。,對文法G的任何符號串=X1X2Xn構(gòu)造集合FIRST()。 1. 置FIRST()FIRST(X1)； 2. 若對任何1ji-1，F(xiàn)IRST(Xj)，則把FIRST(Xi)加至FIRST()中；特別是，若所有的FIRST(Xj)均含有，1jn，則把也加至FIRST()中。顯然，若則FIRST()。,構(gòu)造FOLLOW(A),對于文法G的每個非終結(jié)符A構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的規(guī)則，直至每個FOLLOW不再增大為止： 1. 對于文法的開始符號S，置于FOLLOW(S)中； 2. 若AB是一個產(chǎn)生式，則把FIRST()加至FOLLOW(B)中；,3. 若A

23、B是一個產(chǎn)生式，或AB是一個產(chǎn)生式而 (即FIRST()， 則把FOLLOW(A)加至FOLLOW(B)中。,例4.6 對于文法G(E) ETE E+TE | TFT T*FT | F(E) | i 構(gòu)造每個非終結(jié)符的FIRST和FOLLOW集合：,FIRST(E) =(,i FIRST(E)=+, FIRST(T) =(,i FIRST(T)=*, FIRST(F) =(,i,FOLLOW(E) =),# FOLLOW(E)=),# FOLLOW(T) =+,),# FOLLOW(T)=+,),# FOLLOW(F) =*,+,),#,4.4 遞歸下降分析程序構(gòu)造,構(gòu)造不帶回溯的自上而下分析

24、程序 要消除文法的左遞歸性 克服回溯,構(gòu)造不帶回溯的自上而下分析器 分析程序由一組遞歸過程組成，文法中每個非終結(jié)符對應(yīng)一個過程；所以這樣的分析程序稱為遞歸下降分析器。(因為文法的定義通常是遞歸的) 幾個全局過程和變量： ADVANCE，把輸入串指示器IP指向下一個輸入符號，即讀入一個單字符號 SYM，IP當(dāng)前所指的輸入符號 ERROR，出錯處理子程序,例:文法G(E): ETE E+TE | TFT T*FT | F(E) | i 每個非終結(jié)符有對應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需要從某個非終結(jié)符出發(fā)進(jìn)行展開(推導(dǎo))時，就調(diào)用這個非終結(jié)符對應(yīng)的子程序。,例:文法G(E): ETE E+T

25、E | TFT T*FT | F(E) | i 對應(yīng)的遞歸下降子程序為:,PROCEDURE E； BEGIN T；E END；,PROCEDURE E； IF SYM=+ THEN BEGIN ADVANCE； T；E END,PROCEDURE T； BEGIN F；T END,PROCEDURE T； IF SYM=* THEN BEGIN ADVANCE； F；T END；,例:文法G(E): ETE E+TE | TFT T*FT | F(E) | i 對應(yīng)的遞歸下降子程序為:,例:文法G(E): ETE E+TE | TFT T*FT | F(E) | i 對應(yīng)的遞歸下降子程序為:

26、,PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,主程序: PROGRAM PARSER; BEGIN ADVANCE; E; IF SYM # THEN ERROR END;,對應(yīng)的遞歸下降子程序為:,ETE | BC PROCEDURE E； BEGIN IF SYM FIRST(TE)THEN T；E ELSE IF SYM FIRST(BC)THEN B; C ELSE ERROR END；,E

27、TE E+TE | TFT T*FT | F(E) | I 對應(yīng)的遞歸下降子程序為:,PROCEDURE E； BEGIN T；E END；,PROCEDURE T； BEGIN F；T END,ETE E+TE | TFT T*FT | F(E) | I 對應(yīng)的遞歸下降子程序為:,PROCEDURE E； IF SYM=+ THEN BEGIN ADVANCE； T；E END ELSE IF SYM# AND SYM) THEN ERROR,ETE E+TE | TFT T*FT | F(E) | I 對應(yīng)的遞歸下降子程序為:,PROCEDURE T； IF SYM=* THEN BEGI

28、N ADVANCE； F；T END ELSE IF SYM# AND SYM) AND SYM+ THEN ERROR,ETE E+TE | TFT T*FT | F(E) | i 對應(yīng)的遞歸下降子程序為:,PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,ETE E+TE | TFT T*FT | F(E) | i 對應(yīng)的遞歸下降子程序為:,主程序: PROGRAM PARSER; BEGIN ADV

29、ANCE; E END;,在元符號“”和“|”的基礎(chǔ)上，擴(kuò)充幾個元語言符號： 1. 用花括號表示閉包運(yùn)算*。 2. 用表示0n可任意重復(fù)0次至n次，。 3. 用方括號表示01 ，即表示的出現(xiàn)可有可無(等價于|)。 引入上述元符號的文法亦稱擴(kuò)充的巴科斯范式。,文法的另一種表示法和轉(zhuǎn)換圖,例如，通常的“實數(shù)”可定義為： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign + | - 用擴(kuò)充的巴科斯范式來描述語法，直觀易懂，便于表示左遞歸消去和因子提取。,例4.5 文法 ET | E+T TF |

30、T*F Fi | (E) 可表示成 ET+T TF*F Fi | (E) (4.6),ET+T TF*F Fi | (E) (4.6) 可以用語法圖來表示語言的文法。,ET+T TF*F Fi | (E) (4.6) 可構(gòu)造一組遞歸下降分析程序：,PROCEDURE E； BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T END END；,PROCEDURE T； BEGIN F； WHILE SYM=* DO BEGIN ADVANCE； F END END；,ET+T TF*F Fi | (E) (4.6) 可構(gòu)造一組遞歸下降分析程序：,ET+T TF*F

31、Fi | (E) (4.6) 可構(gòu)造一組遞歸下降分析程序：,PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,1. 文法不含左遞歸， 2. 對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若 A 1| 2| n 則 FIRST( i)FIRST( j) (ij) 3. 對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含，則 FIRST( i)FOLLOW(A)= i=1,2,.,n 如

32、果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。,回顧：LL(1)文法條件,分析程序由一組遞歸過程組成，文法中每個非終結(jié)符對應(yīng)一個過程；所以這樣的分析程序稱為遞歸下降分析器。(因為文法的定義通常是遞歸的) 每個非終結(jié)符有對應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需要從某個非終結(jié)符出發(fā)進(jìn)行展開(推導(dǎo))時，就調(diào)用這個非終結(jié)符對應(yīng)的子程序。,回顧：構(gòu)造不帶回溯的自上而下分析器,4.5 預(yù)測分析程序,一、預(yù)測分析程序工作原理 預(yù)測分析程序或LL(1)分析法： 總控程序 分析表 MA，a矩陣，A VN ，a VT 是終結(jié)符或， 分析棧 STACK 用于存放文法符號,總控程序根據(jù)現(xiàn)行棧頂符號X和當(dāng)前

33、輸入符號a，執(zhí)行下列三種動作之一: 1. 若Xa，則宣布分析成功，停止分析。 2. 若Xa ，則把X從STACK棧頂逐出，讓a指向下一個輸入符號。,匹配成功,3. 若X是一個非終結(jié)符，則查看分析表M。 若MX，a中存放著關(guān)于X的一個產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號串按反序一一推進(jìn)STACK棧(若右部符號為，則意味不推什么東西進(jìn)棧)。在把產(chǎn)生式的右部符號推進(jìn)棧的同時應(yīng)做這個產(chǎn)生式相應(yīng)的語義動作。 若MX，a中存放著“出錯標(biāo)志”，則調(diào)用出錯診察程序ERROR。,推導(dǎo),預(yù)測分析程序的總控程序： BEGIN 首先把然后把文法開始符號推進(jìn)STACK棧； 把第一個輸入符號讀進(jìn)a； FLA

34、G:=TRUE; WHILE FLAG DO BEGIN 把STACK棧頂符號上托出去并放在X中； IF XVT THEN IF X= a THEN 把下一輸入符號讀進(jìn)a ELSE ERROR,匹配成功,ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MX,a=XX1X2XkTHEN 把Xk,Xk-1,X1一一推進(jìn)STACK棧 /* 若X1X2Xk=，不推什么進(jìn)棧 */ ELSE ERROR END OF WHILE; STOP /*分析成功，過程完畢*/ END,分析成功,推導(dǎo),例4.6 對于文法G(E) ETE E+T

35、E | TFT T*FT | F(E) | i 輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測分析：,步驟符號棧輸入串所用產(chǎn)生式 0#Ei1*i2+i3# 1#ETi1*i2+i3# ETE 2#ETFi1*i2+i3# TFT 3#ETii1*i2+i3# Fi,步驟符號棧輸入串所用產(chǎn)生式 3#ETii1*i2+i3# Fi 4#ET*i2+i3# 5#ETF*i2+i3# T*FT 6#ETF i2+i3# 7#ETii2+i3# Fi,步驟符號棧輸入串所用產(chǎn)生 7#ETii2+i3# Fi 8#ET+i3# 9#E+i3# T 10#ET+i3# E+TE 11#ETi3#,步驟符號棧輸入串所用產(chǎn)生 11#ETi3# 12#ETF i3# TFT 13#ETii3# Fi 14#ET# 15#E# T 16# E,二、分析表MA，a的構(gòu)造,構(gòu)造FIRST()和FOLLOW(A) 構(gòu)造分析表MA，a,構(gòu)造FIRST(),對每一文法符號XVTVN構(gòu)造FIRST(X) 連續(xù)使用下面的規(guī)則，直至每個集合FIRST不再增大為止： 1. 若XVT，則FIRST(X)X。 2. 若