《編譯原理》第4章 語法分析-自上而下分析

1、整理課件編譯原理第四章第四章 語法分析語法分析自上而下分析自上而下分析整理課件整理課件整理課件整理課件第四章第四章 語法分析語法分析自上而下分析自上而下分析n本章主要介紹本章主要介紹語法分析語法分析的處理的處理n要進行語法分析，必須對語言的要進行語法分析，必須對語言的語法結(jié)構(gòu)語法結(jié)構(gòu)進行描述。進行描述。采用采用正規(guī)式和有限自動機正規(guī)式和有限自動機可以描述和識別語言可以描述和識別語言的的單詞符號單詞符號；用用上下文無關(guān)文法上下文無關(guān)文法來描述來描述語法規(guī)則語法規(guī)則。整理課件整理課件n上下文無關(guān)文法上下文無關(guān)文法的定義：的定義： 一個上下文無關(guān)文法一個上下文無關(guān)文法G G是一個四元式是一個四元式

2、G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：終結(jié)符終結(jié)符集合集合( (非空非空) )V VN N：非終結(jié)符非終結(jié)符集合集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的：文法的開始符號開始符號，S S V VN NP P：產(chǎn)生式產(chǎn)生式集合集合( (有限有限) )，每個產(chǎn)生式形式為每個產(chǎn)生式形式為A A， A A V VN N， ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。整理課件整理課件n例，定義只含例，定義只含+，*的算術(shù)表達(dá)式的文法的算術(shù)

3、表達(dá)式的文法 G=， 其其中，中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E)整理課件整理課件n如果如果 1 2 n，則我們稱這個序，則我們稱這個序列是從列是從 1到到 n的一個的一個推導(dǎo)推導(dǎo)。若存在一個從。若存在一個從 1到到 n的推導(dǎo)，則稱的推導(dǎo)，則稱 1可以可以推導(dǎo)推導(dǎo)出出 n 。n例：對文法例：對文法(1)E (E) (E+E) (i+E) (i+i)整理課件整理課件n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或若干步一步或若干步，可以推出，可以推出 n n。n1n*1 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過0 0步或步

4、或若干步若干步，可以推出，可以推出 n n。* 所以所以 ： 即即 或或,|)(*TV SGLq定義：假定定義：假定G G是一個文法，是一個文法，S S 是它的開始符號。是它的開始符號。如果如果 ，則，則 稱是一個稱是一個句型句型。僅含終結(jié)符。僅含終結(jié)符號的句型是一個號的句型是一個句子句子。文法。文法G G所產(chǎn)生的句子的全所產(chǎn)生的句子的全體是一個體是一個語言語言，將它記為，將它記為 L(G)L(G)。*S整理課件整理課件第四章第四章 語法分析語法分析自上而下分析自上而下分析n語法分析器的功能語法分析器的功能n自上而下分析面臨的問題自上而下分析面臨的問題nLL(1)LL(1)分析法分析法n遞歸下

5、降分析程序構(gòu)造遞歸下降分析程序構(gòu)造n預(yù)測分析程序預(yù)測分析程序整理課件整理課件4.1 語法分析器的功能語法分析器的功能n語法分析的任務(wù)語法分析的任務(wù)是分析一個文法的句子是分析一個文法的句子結(jié)構(gòu)。結(jié)構(gòu)。n語法分析器的功能語法分析器的功能：按照文法的產(chǎn)生式按照文法的產(chǎn)生式( (語言的語法規(guī)則語言的語法規(guī)則) )，識別輸入符號串是，識別輸入符號串是否為一個句子。否為一個句子。n這里所說的輸入串是指由單詞符號（文法的終結(jié)符）這里所說的輸入串是指由單詞符號（文法的終結(jié)符）組成的有限序列。組成的有限序列。n對一個文法，當(dāng)給你一串符號時，怎樣知道它是不是對一個文法，當(dāng)給你一串符號時，怎樣知道它是不是該文法的一

6、個句子（程序）呢？該文法的一個句子（程序）呢？n這就要判斷，這就要判斷，整理課件整理課件源程序源程序單詞符號單詞符號取下一單詞取下一單詞.語法分語法分析樹析樹詞法分詞法分析器析器語法分語法分析器析器符號表符號表編譯程序編譯程序后續(xù)部分后續(xù)部分整理課件整理課件n語法分析的方法語法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：從輸入串開始，逐步進行基本思想：從輸入串開始，逐步進行“歸約歸約”，直到文法的開始符號。即從樹末端開始，構(gòu)造直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。語法樹。所謂歸約所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)，是指根據(jù)文法的產(chǎn)生式

7、規(guī)則，把產(chǎn)生式的右部替換成左部符號。則，把產(chǎn)生式的右部替換成左部符號。n算符優(yōu)先分析法：算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達(dá)式。性質(zhì)進行語法分析。適合分析表達(dá)式。nLRLR分析法：分析法：規(guī)范歸約規(guī)范歸約整理課件整理課件n語法分析的方法：語法分析的方法：n基本思想：基本思想：它從文法的開始符號出發(fā)，反復(fù)它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找使用各種產(chǎn)生式，尋找 匹配匹配 的的推導(dǎo)推導(dǎo)。n遞歸下降分析程序：遞歸下降分析程序：對每一語法變量對每一語法變量( (非終非終結(jié)符結(jié)符) )構(gòu)造一個相應(yīng)的子程序，每個子程序構(gòu)造一個相應(yīng)的子程

8、序，每個子程序識別一定的語法單位；通過子程序間的相互識別一定的語法單位；通過子程序間的相互調(diào)用實現(xiàn)對輸入串的識別。調(diào)用實現(xiàn)對輸入串的識別。n預(yù)測分析程序預(yù)測分析程序F優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。整理課件整理課件第四章第四章 語法分析語法分析自上而下分析自上而下分析n語法分析器的功能語法分析器的功能n自上而下分析面臨的問題自上而下分析面臨的問題nLL(1)LL(1)分析法分析法n遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造n預(yù)測分析程序預(yù)測分析程序整理課件整理課件4.2 自上而下分析面臨的問題自上而下分析面臨的問題n自上而下就是從文法的開始符號出發(fā)，向自上而下就是

9、從文法的開始符號出發(fā)，向下下推導(dǎo)推導(dǎo)，推出句子。，推出句子。p對任何輸入串，試圖用一切可能的辦法，對任何輸入串，試圖用一切可能的辦法，從文法開始符號從文法開始符號(根結(jié)點根結(jié)點)出發(fā)，自上而下地出發(fā)，自上而下地為輸入串建立一棵為輸入串建立一棵語法樹語法樹。p或者說，為輸入串尋找一個最左推導(dǎo)?；蛘哒f，為輸入串尋找一個最左推導(dǎo)。整理課件整理課件n例例3.4.1 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析分析輸入串輸入串x*y(記為記為 )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*整

10、理課件整理課件（1 1）當(dāng)某個非終結(jié)符有）當(dāng)某個非終結(jié)符有多個產(chǎn)生式候選多個產(chǎn)生式候選時，時，在在分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹配成功時，這種匹配可能是暫時的配成功時，這種匹配可能是暫時的。出錯。出錯時時，不得不不得不“回溯回溯”。（2 2）文法左遞歸問題：文法左遞歸問題：一個文法是含有左遞歸一個文法是含有左遞歸的，如果存在非終結(jié)符的，如果存在非終結(jié)符P PPP自上而下分析面臨的問題自上而下分析面臨的問題整理課件整理課件左遞歸左遞歸例：下面是描述算術(shù)表例：下面是描述算術(shù)表達(dá)式的算法達(dá)式的算法 S ES E EE+T|T EE+T|T TT TT

11、* *F|FF|F F(E)|id F(E)|id 含有左遞歸的文法將使自上而下的分含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)析陷入無限循環(huán)。為句子為句子idid* *id+idid+id構(gòu)造分析樹構(gòu)造分析樹 S S E E E + T E + T E + T E + TE + TE + T：整理課件整理課件第四章第四章 語法分析語法分析自上而下分析自上而下分析n語法分析器的功能語法分析器的功能n自上而下分析面臨的問題自上而下分析面臨的問題nLL(1)LL(1)分析法分析法n遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造n預(yù)測分析程序預(yù)測分析程序整理課件整理課件4.3 LL(1)分析法分析法n構(gòu)

12、造不帶回溯的自上而下分析算法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性要消除文法的左遞歸性克服回溯克服回溯整理課件整理課件4.3.1 左遞歸的消除左遞歸的消除n直接消除見諸于產(chǎn)生式中的左遞歸：假直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符定關(guān)于非終結(jié)符P的規(guī)則為的規(guī)則為PP | 其中其中 不以不以P開頭開頭。 我們可以把我們可以把P的規(guī)則等價地改寫為如下的的規(guī)則等價地改寫為如下的非直接左遞歸形式：非直接左遞歸形式：P P P P | 左遞歸變右遞歸PP P 整理課件整理課件n一般而言，假定一般而言，假定P關(guān)于的全部產(chǎn)生式是關(guān)于的全部產(chǎn)生式是PP 1 | P 2 | | P m |

13、1 | 2| n其中，每個其中，每個 都不等于都不等于 ，每個，每個 都不以都不以P開頭開頭 那么，消除那么，消除P的直接左遞歸性就是把這些規(guī)的直接左遞歸性就是把這些規(guī)則改寫成：則改寫成： P 1P | 2P | | nP P 1P | 2P | | mP | 左遞歸變右遞歸4.3.1 左遞歸的消除左遞歸的消除整理課件整理課件n例例 文法文法G(E):EET | TTT*F | FF(E) | i經(jīng)消去直接左遞歸后變成：經(jīng)消去直接左遞歸后變成： ETE E +TE | TFT T *FT | F(E) | i(4.2)PP 1 | P 2 | | P m | 1 | 2| nP 1P | 2P

14、 | | nP P 1P | 2P | | mP | 整理課件整理課件n例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)雖沒有直接左遞歸，但雖沒有直接左遞歸，但S、Q、R都是左遞歸的都是左遞歸的SQcRbcSabc消除一個文法的一切左遞歸的條件：消除一個文法的一切左遞歸的條件：（1）不含以）不含以 為右部的產(chǎn)生式為右部的產(chǎn)生式（但改寫后的文法可能但改寫后的文法可能含以含以 為右部的產(chǎn)生式為右部的產(chǎn)生式）（2）不含回路）不含回路。PP整理課件整理課件n消除左遞歸的算法消除左遞歸的算法:1. 把文法把文法G的所有非終結(jié)符按任一種順序排列成的所有非終結(jié)符按任一種順序排列成P1，P

15、2，Pn；按此順序執(zhí)行；按此順序執(zhí)行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的規(guī)則改寫成的規(guī)則改寫成 Pi 1 | 2 | k ; (其中其中Pj 1| 2| k是關(guān)于是關(guān)于Pj的所有規(guī)則的所有規(guī)則) 消除關(guān)于消除關(guān)于Pi規(guī)則的直接左遞歸性規(guī)則的直接左遞歸性 END3. 化簡由化簡由2所得的文法。去除那些從開始符號出發(fā)永所得的文法。去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。整理課件整理課件n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|an令它的非終結(jié)符的排序為令

16、它的非終結(jié)符的排序為R、Q、S。n對于對于R，不存在直接左遞歸。，不存在直接左遞歸。n把把R代入到代入到Q的有關(guān)候選后，把的有關(guān)候選后，把Q的規(guī)則的規(guī)則變?yōu)樽優(yōu)?QSab | ab | b整理課件整理課件n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|an令它的非終結(jié)符的排序為令它的非終結(jié)符的排序為R、Q、S。nQ的規(guī)則變?yōu)榈囊?guī)則變?yōu)?QSab | ab | bn現(xiàn)在的現(xiàn)在的Q不含直接左遞歸，把它代入到不含直接左遞歸，把它代入到S的有關(guān)候選后，的有關(guān)候選后，S變成變成SSabc | abc | bc | c整理課件整理課件n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|

17、anS變成變成SSabc | abc | bc | cn消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|a整理課件整理課件n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|an消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an關(guān)于關(guān)于Q和和R的規(guī)則已是多余的，化簡為：的規(guī)則已是多余的，化簡為：SabcS | bcS | cS S abcS | (4.4)整理課件整理課件n注意，由于對非終結(jié)符排序的不同，最注意，由于對非終結(jié)符排序

18、的不同，最后所得的文法在形式上可能不一樣。但后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的。不難證明，它們都是等價的。n例如，若對文法例如，若對文法(4.3)的非終結(jié)符排序選的非終結(jié)符排序選為為S、Q、R，那么，最后所得的無左遞，那么，最后所得的無左遞歸文法是：歸文法是：SQc | cQRb | bRbcaR | caR |a R (4.5)R bca R | n文法文法(4.4)和和(4.5)的等價性是顯然的。的等價性是顯然的。整理課件整理課件小結(jié)小結(jié)n自上而下分析面臨的問題自上而下分析面臨的問題 文法的左遞歸性文法的左遞歸性 回溯回溯n消除文法的左遞歸消除文法的左遞歸 直接左遞

19、歸的消除直接左遞歸的消除 間接左遞歸的消除間接左遞歸的消除整理課件整理課件4.3.2 消除回溯、提左因子消除回溯、提左因子n為了為了消除回溯消除回溯就必須保證：對文法的任就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠能夠根據(jù)它所面臨的輸入符號根據(jù)它所面臨的輸入符號準(zhǔn)確地指準(zhǔn)確地指派派它的一個候選它的一個候選去執(zhí)行任務(wù)，并且此候去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。選的工作結(jié)果應(yīng)是確信無疑的。nA 1 | 2 | | nSa.IPA.整理課件整理課件n令令G是一個不含左遞歸的文法，對是一個不含左遞歸的文法，對G的所的所有非終結(jié)符的每個候選

20、有非終結(jié)符的每個候選 定義它的終結(jié)首定義它的終結(jié)首符集符集FIRST( )為：為：.,|=)(*TVaaaFIRST 特別是，若特別是，若 ，則規(guī)定，則規(guī)定FIRST( )。*如果非終結(jié)符如果非終結(jié)符A的所有候選首符集兩兩不相交，的所有候選首符集兩兩不相交，即即A的任何兩個不同候選的任何兩個不同候選 i和和 jFIRST( i)FIRST( j) 當(dāng)要求當(dāng)要求A匹配輸入串時，匹配輸入串時，A就能根據(jù)它所面臨的就能根據(jù)它所面臨的第一個輸入符號第一個輸入符號a，準(zhǔn)確地指派某一個候選前去，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含a的的 。整

21、理課件整理課件n思考：思考： nFIRST( i)FIRST( j) 很好處理，但是很好處理，但是如果如果 的終結(jié)首符集有共同的部分怎么辦？的終結(jié)首符集有共同的部分怎么辦？nA 1 | 2 | | nn可提取其可提取其公共左因子公共左因子整理課件整理課件n提取公共左因子提取公共左因子: 假定關(guān)于假定關(guān)于A的規(guī)則是的規(guī)則是 A 1 | 2 | | n | 1 | 2 | | m (其中，每個其中，每個 不以不以 開頭開頭) 那么，可以把這些規(guī)則改寫成那么，可以把這些規(guī)則改寫成A A | 1 | 2 | | mA 1 | 2 | | nn經(jīng)過反復(fù)提取左因子，就能夠把每個非終經(jīng)過反復(fù)提取左因子，就能

22、夠把每個非終結(jié)符結(jié)符(包括新引進者包括新引進者)的所有候選首符集變的所有候選首符集變成為兩兩不相交。成為兩兩不相交。整理課件整理課件n ETE E +TE | TFT T *FT | F(E) | in i + i4.3.3 LL(1)分析條件分析條件n當(dāng)一個文法當(dāng)一個文法不含左不含左遞歸遞歸，并且滿足每，并且滿足每個非終結(jié)符的所有個非終結(jié)符的所有候選首符集兩兩不候選首符集兩兩不相交相交的條件，是不的條件，是不是就一定能進行有是就一定能進行有效的自上而下分析效的自上而下分析了呢？了呢？整理課件整理課件i + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) |

23、i整理課件整理課件i + i IPETEnG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi nG(E): ETE E +TE | TFT T *FT | F(E)

24、| i整理課件整理課件i + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi +TEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi +TEFTinG(

25、E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | i整理課件整理課件n思考：思考：當(dāng)非終結(jié)符當(dāng)非終結(jié)符A面臨輸入符號面臨輸入符號a，且，且a不屬于不屬于A的任意候選的任意候選首符集，首符集，但但A的某個候選首符集包含的某個候選首符集包含 時，是否就一定可以使時，是否就一定可以使A自動匹配（自動匹配（ A

26、 ）呢？）呢？n需要做判斷：需要做判斷：有當(dāng)有當(dāng)a是是允許在文法的某個句型中允許在文法的某個句型中跟跟在在A后面的終結(jié)符后面的終結(jié)符時，才可能允許時，才可能允許A自動匹配，否自動匹配，否則，則，a在這里的出現(xiàn)就是一個語法錯誤。在這里的出現(xiàn)就是一個語法錯誤。整理課件整理課件i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iS T+能否用能否用AA 自動匹配，需要判斷自動匹配，需要判斷當(dāng)前輸入符號當(dāng)前輸入符號是否在是否在緊跟在緊跟在A A后面的終結(jié)符集后面的終結(jié)符集FOLLOW(A)FOLLOW(A)中。中。整理課件整理課件n

27、假定假定S是文法是文法G的開始符號，對于的開始符號，對于G的任何的任何非終結(jié)符非終結(jié)符A，我們定義，我們定義.,.|)(*TVaAaSaAFOLLOWAS*特別是，若特別是，若 ，則規(guī)定，則規(guī)定 FOLLOW(A)4.3.3 LL(1)分析條件分析條件整理課件整理課件n構(gòu)造構(gòu)造不帶回溯不帶回溯的自上而下分析的文法條件的自上而下分析的文法條件1. 文法不含左遞歸，文法不含左遞歸，2. 對于文法中每一個非終結(jié)符對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的各個產(chǎn)生式的候選首符集兩兩不相交。即，若的候選首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3.

28、對文法中的每個非終結(jié)符對文法中的每個非終結(jié)符A，若它存在某個，若它存在某個候選首符集包含候選首符集包含 ，則，則FIRST( i)FOLLOW(A)= i=1,2,.,n如果一個文法如果一個文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為LL(1)LL(1)文法文法。第一個第一個L：從左到右掃描輸入串：從左到右掃描輸入串第二個第二個L：最左推導(dǎo)：最左推導(dǎo)1：分析時每一步只需向前查看一個符號：分析時每一步只需向前查看一個符號整理課件整理課件n對于一個滿足上述條件的文法，可以對其輸對于一個滿足上述條件的文法，可以對其輸入串進行有效的無回溯的自上而下分析。假入串進行有效的無回溯的自上而下

29、分析。假設(shè)要用非終結(jié)符設(shè)要用非終結(jié)符A進行匹配，面臨的輸入符進行匹配，面臨的輸入符號為號為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為A 1 | 2 | | n1. 若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2. 若若a不屬于任何一個候選首符集，則：不屬于任何一個候選首符集，則： (1) 若若 屬于某個屬于某個FIRST( i )且且 a FOLLOW(A)， 則則讓讓A與與 自動匹配自動匹配。 (2) 否則，否則，a的出現(xiàn)是一種語法錯誤。的出現(xiàn)是一種語法錯誤。整理課件整理課件求求FIRST(X)的算法如下：的算法如下：p80若若X VT，則，則FIRST(X)X。若若X

30、 VN，且有產(chǎn)生式，且有產(chǎn)生式Xa， a VT則把則把a加入到加入到FIRST(X)中；中；若若X VN ，X ，則，則 FIRST(X)中。中。對每個文法符號對每個文法符號X VT VN ，連續(xù)使用下連續(xù)使用下面的規(guī)則，直至每個面的規(guī)則，直至每個FIRST(X)不再增大為不再增大為止：止：.,|=)(*TVaaaFIRST整理課件整理課件 b) 當(dāng)當(dāng)Y1 ，Y2， ，Yi-1都都= , (1 i n) , 則則FIRST( Y1 )-, FIRST( Y2 )-, , FIRST( Yi )- 都包含在都包含在FIRST（X）中）中 c) 當(dāng)當(dāng)Y1 ，Y2， ，Yk都都= ,則則 FIRST

31、(X)，此時，此時FIRST(X)= FIRST( Y1 ) FIRST( Y2 ) FIRST( Yk ) 若若X ，Y1 ，Y2， ，Yk VN ，且有產(chǎn)生式且有產(chǎn)生式 X Y1 Y2 Yk： a) 當(dāng)當(dāng)Y1 不能不能= ，則，則FIRST(Y1 )中的所有符號中的所有符號都在都在FIRST（X）中）中整理課件整理課件n對每個非終結(jié)符對每個非終結(jié)符A，連續(xù)使用下面的規(guī)則，連續(xù)使用下面的規(guī)則，直至每個直至每個FOLLOW(A)不再增大為止：不再增大為止： 對于文法的開始符號對于文法的開始符號S，置，置于于FOLLOW(S)中；中； 對于對于A B 的的產(chǎn)生式，則把產(chǎn)生式，則把FIRST( )

32、- 加至加至FOLLOW(B)中；中；對于對于A B或或A B ，其中，其中 ， 則把則把FOLLOW(A)加至加至FOLLOW(B)中。中。求求FOLLOW(A)的算法如下：的算法如下：p82 注意：注意： 永遠(yuǎn)不進永遠(yuǎn)不進follow集！集！.,.|)(*TVaAaSaAFOLLOW整理課件整理課件n例例4.6 對于文法對于文法G(E)ETE E +TE | TFT T *FT | F(E) | i構(gòu)造每個非終結(jié)符的構(gòu)造每個非終結(jié)符的FIRST和和FOLLOW集合：集合： FIRST(E) =(,iFIRST(E )=+, FIRST(T) =(,iFIRST(T )=*, FIRST(F

33、) =(,i FOLLOW(E) =),#FOLLOW(E )=),#FOLLOW(T) =+,),#FOLLOW(T )=+,),#FOLLOW(F) =*,+,),#整理課件整理課件4.4 遞歸下降分析遞歸下降分析程序構(gòu)造程序構(gòu)造n構(gòu)造不帶回溯的自上而下分析程序構(gòu)造不帶回溯的自上而下分析程序要消除文法的左遞歸性要消除文法的左遞歸性克服回溯克服回溯整理課件整理課件n主要思路：主要思路： 分析程序由一組遞歸過程組成，對文法的每一分析程序由一組遞歸過程組成，對文法的每一個個非終結(jié)符非終結(jié)符（語法變量）構(gòu)造一個（語法變量）構(gòu)造一個相應(yīng)的子程相應(yīng)的子程序，序，識別對應(yīng)的語法單位；識別對應(yīng)的語法單位；

34、 ； 這樣的分析程序稱為這樣的分析程序稱為遞歸下降分析器遞歸下降分析器。( (因為文因為文法的定義通常是遞歸的法的定義通常是遞歸的) )n幾個全局過程和變量：幾個全局過程和變量：ADVANCE，把，把輸入串指示器輸入串指示器IP指向下一個指向下一個輸入符號，即讀入一個單字符號輸入符號，即讀入一個單字符號SYM，IP當(dāng)前所指的輸入符號當(dāng)前所指的輸入符號ERROR，出錯處理子程序，出錯處理子程序整理課件整理課件注意：注意：n每個每個非終結(jié)符非終結(jié)符有有對應(yīng)的子程序?qū)?yīng)的子程序的定義的定義n在分析過程中，當(dāng)在分析過程中，當(dāng)需要從某個非終結(jié)符需要從某個非終結(jié)符出發(fā)出發(fā)進行語法樹展開進行語法樹展開( (

35、推導(dǎo)推導(dǎo)) )時時，就調(diào)用，就調(diào)用這個非終結(jié)符這個非終結(jié)符對應(yīng)的子程序?qū)?yīng)的子程序。n子程序的名字可與對應(yīng)的非終結(jié)符的名子程序的名字可與對應(yīng)的非終結(jié)符的名字相同字相同n例：例：ATE | BC| 整理課件整理課件ATE | BC| 對應(yīng)的遞歸下降子程序為：對應(yīng)的遞歸下降子程序為：PROCEDURE A；BEGINIF SYM FIRST(TE) THEN BEGIN T；E END；/先調(diào)用先調(diào)用T子程序子程序,再調(diào)用再調(diào)用EELSE IF SYM FIRST(BC) THEN BEGIN B；C END； /先調(diào)用先調(diào)用B子程序子程序,再調(diào)用再調(diào)用CELSE IF SYM FOLLOW(A)

36、 THEN BEGIN END；ELSE ERRORENDELSE IF SYM / FOLLOW(A) THEN ERROR整理課件整理課件n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in對應(yīng)的遞歸下降子程序為對應(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;整理課件整理課件n例例: :文法文法G(E):G(E):ET

37、E E +TE | TFT T *FT | F(E) | in對應(yīng)的遞歸下降子程序為對應(yīng)的遞歸下降子程序為: : PROCEDURE E；BEGIN T；E END；PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E ENDPROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E END ELSE IF SYM# AND SYM) THEN ERROR / FOLLOW(E )=),#整理課件整理課件PROCEDURE T；BEGIN F；T ENDPROCEDURE T ；IF SYM=* THENBEGIN ADVA

38、NCE； F；T END；n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in對應(yīng)的遞歸下降子程序為對應(yīng)的遞歸下降子程序為: : 整理課件整理課件主程序主程序:PROGRAM PARSER;BEGIN ADVANCE; E; IF SYM # THEN ERROREND;整理課件整理課件n在元符號在元符號“”和和“|”的基礎(chǔ)上，擴充幾的基礎(chǔ)上，擴充幾個元語言符號：個元語言符號：1. 用用花括號花括號 表示表示閉包運算閉包運算 *。2. 用表示用表示 0n可任意可任意重復(fù)重復(fù)0次至次至n次次。3. 用用方括號方括號 表示表示 01 ，即表示，

39、即表示 的出現(xiàn)的出現(xiàn)可可有可無有可無(等價于等價于 | )。 引入上述元符號的文法亦稱引入上述元符號的文法亦稱擴充的巴科擴充的巴科斯范式斯范式。文法的另一種表示法和轉(zhuǎn)換圖文法的另一種表示法和轉(zhuǎn)換圖整理課件整理課件n例如，通常的例如，通常的“實數(shù)實數(shù)”可定義為：可定義為： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign + | -n用用擴充的巴科斯范式擴充的巴科斯范式來來描述語法描述語法，直觀易直觀易懂懂，便于表示左遞歸消去和因子提取。，便于表示左遞歸消去和因子提取。整理課件整理課件n例例4

40、.5 文法文法ET | E+TTF | T*FFi | (E)可表示成可表示成ET+TTF*FFi | (E) (4.6)整理課件整理課件n ET+TTF*FFi | (E) (4.6)n可以用語法圖來表示語言的文法。可以用語法圖來表示語言的文法。T+ETF*TFi)FE(整理課件整理課件n ET+TTF*FFi | (E) (4.6)n可構(gòu)造一組遞歸下降分析程序：可構(gòu)造一組遞歸下降分析程序：PROCEDURE E；BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T ENDEND；整理課件整理課件PROCEDURE T；BEGIN F； WHILE SYM=* D

41、O BEGIN ADVANCE； F ENDEND；n ET+TTF*FFi | (E) (4.6)n可構(gòu)造一組遞歸下降分析程序：可構(gòu)造一組遞歸下降分析程序：整理課件整理課件n ET+TTF*FFi | (E) (4.6)n可構(gòu)造一組遞歸下降分析程序：可構(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. 對于文法中每一個非

42、終結(jié)符對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的各個產(chǎn)生式的候選首符集兩兩不相交。即，若的候選首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對文法中的每個非終結(jié)符對文法中的每個非終結(jié)符A，若它存在某個，若它存在某個候選首符集包含候選首符集包含 ，則，則FIRST( i)FOLLOW(A)= i=1,2,.,n如果一個文法如果一個文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為LL(1)LL(1)文法文法?；仡櫍夯仡櫍篖L(1)文法條件文法條件整理課件整理課件nLL(1)分析法分析法假設(shè)要用非終結(jié)符假設(shè)要用非終結(jié)符A進行匹配，進

43、行匹配，面臨的輸入符號為面臨的輸入符號為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為 ： A 1 | 2 | | n 1.若若a FIRST（ i），），則指派則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2.若若a不屬于任何一個候選首符集，則：不屬于任何一個候選首符集，則：（1）若）若 屬于某個屬于某個FIRST（ i）且）且a FOLLOW(A),則讓則讓A與與 自動匹配。自動匹配。（2）否則，）否則，a的出現(xiàn)是一種語法錯誤。的出現(xiàn)是一種語法錯誤?；仡櫍夯仡櫍篖L(1)分析法分析法整理課件整理課件n分析程序由一組遞歸過程組成，文法中每分析程序由一組遞歸過程組成，文法中每個非終結(jié)符對應(yīng)一個過程；所以這樣的分個

44、非終結(jié)符對應(yīng)一個過程；所以這樣的分析程序稱為析程序稱為遞歸下降分析器遞歸下降分析器。( (因為文法因為文法的定義通常是遞歸的的定義通常是遞歸的) )n每個非終結(jié)符有對應(yīng)的子程序的定義，首每個非終結(jié)符有對應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需要從某個非終結(jié)符先在分析過程中，當(dāng)需要從某個非終結(jié)符出發(fā)進行展開出發(fā)進行展開( (推導(dǎo)推導(dǎo)) )時，就調(diào)用這個非終時，就調(diào)用這個非終結(jié)符對應(yīng)的子程序。結(jié)符對應(yīng)的子程序。回顧：回顧：構(gòu)造不帶回溯的自上而下分構(gòu)造不帶回溯的自上而下分析器析器整理課件整理課件特征特征 根據(jù)根據(jù)當(dāng)前當(dāng)前輸入符號輸入符號，為當(dāng)前要處，為當(dāng)前要處 理的非終結(jié)符理的非終結(jié)符選擇產(chǎn)生式選擇

45、產(chǎn)生式要求要求文法是文法是LL(1)LL(1)的的 預(yù)測分析程序預(yù)測分析程序整理課件整理課件預(yù)測分析器模型預(yù)測分析器模型總控程序總控程序X#輸入串輸入串分析棧分析棧STACKa1a2.ai#輸出輸出 預(yù)測分析表預(yù)測分析表M整理課件整理課件預(yù)測分析器模型預(yù)測分析器模型總控程序總控程序X#輸入串輸入串分析棧分析棧STACKa1a2.ai#輸出輸出 預(yù)測分析表預(yù)測分析表M分析棧分析棧 STACK 用于用于存放文法符號存放文法符號。分析開。分析開始時，棧底先放一個始時，棧底先放一個#，然后放進文法開，然后放進文法開始符號。始符號。# Sa1a2.ai#整理課件整理課件預(yù)測分析器模型預(yù)測分析器模型總控程

46、序總控程序X#輸入串輸入串分析棧分析棧STACKa1a2.ai#輸出輸出 預(yù)測分析表預(yù)測分析表M預(yù)測分析表是一個預(yù)測分析表是一個 MA，a形式的矩陣形式的矩陣，A VN ， a VT 是終結(jié)符或是終結(jié)符或；矩陣元素矩陣元素MA，a中存放著一條關(guān)于中存放著一條關(guān)于A的產(chǎn)生式的產(chǎn)生式，指出當(dāng)，指出當(dāng)A面面臨輸入符號臨輸入符號a時所采用的候選。時所采用的候選。 MA，a中也可能存放一個中也可能存放一個“出錯標(biāo)志出錯標(biāo)志”，指出，指出A根本不該面臨輸入符號根本不該面臨輸入符號a。整理課件整理課件某文法的某文法的LL(1)預(yù)測分析表預(yù)測分析表 整理課件整理課件預(yù)測分析器模型預(yù)測分析器模型總控程序總控程序

47、X#輸入串輸入串分析棧分析棧STACKa1a2.ai#輸出輸出 預(yù)測分析表預(yù)測分析表M總控程序總控程序在任何時候都是按在任何時候都是按STACK棧頂符號棧頂符號X和當(dāng)前的輸入符號和當(dāng)前的輸入符號a行事；它總是執(zhí)行下述行事；它總是執(zhí)行下述三種可能的動作之一：三種可能的動作之一：整理課件整理課件1. 若若Xa，則宣布分析成功，則宣布分析成功，停止分析。停止分析。2. 若若Xa ，則把，則把X從從STACK棧頂棧頂逐出，讓逐出，讓a指向下一個輸入符號。指向下一個輸入符號。匹配成功q總控程序總控程序根據(jù)現(xiàn)行根據(jù)現(xiàn)行棧頂符號棧頂符號X和當(dāng)前輸入和當(dāng)前輸入符號符號a，執(zhí)行下列三種動作之一，執(zhí)行下列三種動作

48、之一:整理課件整理課件3. 若若X是一個非終結(jié)符，則查看分析表是一個非終結(jié)符，則查看分析表M。 若若MX，a中存放著關(guān)于中存放著關(guān)于X的一個產(chǎn)生的一個產(chǎn)生式，把式，把X逐出逐出STACK棧頂，棧頂，把產(chǎn)生式把產(chǎn)生式的右部符號串按反序一一推進的右部符號串按反序一一推進STACK棧棧(若右部符號為若右部符號為 ，則意味不推什么東，則意味不推什么東西進棧西進棧)。在把產(chǎn)生式的右部符號推進。在把產(chǎn)生式的右部符號推進棧的同時應(yīng)做這個產(chǎn)生式相應(yīng)的語義棧的同時應(yīng)做這個產(chǎn)生式相應(yīng)的語義動作（目前暫且不管）。動作（目前暫且不管）。 若若MX，a中存放著中存放著“出錯標(biāo)志出錯標(biāo)志”，則，則調(diào)用出錯診察程序調(diào)用出錯

49、診察程序ERROR。推導(dǎo)整理課件整理課件n預(yù)測分析程序的總控程序：預(yù)測分析程序的總控程序：BEGIN 首先把首先把然后把文法開始符號推進然后把文法開始符號推進STACK棧；棧； 把第一個輸入符號讀進把第一個輸入符號讀進a； FLAG:=TRUE; WHILE FLAG DOBEGIN 把把STACK棧頂符號上托出去并放在棧頂符號上托出去并放在X中；中； IF X VT THEN IF X= a THEN 把下一輸入符號讀進把下一輸入符號讀進a ELSE ERROR 匹配成功整理課件整理課件 ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR

50、ELSE IF MX,a=XX1X2XkTHEN 把把Xk,Xk-1,X1一一推進一一推進STACK棧棧 /* 若若X1X2Xk= ，不推什么進棧，不推什么進棧 */ ELSE ERROR END OF WHILE;STOP /*分析成功，過程完畢分析成功，過程完畢*/END分析成功推導(dǎo)整理課件整理課件n例例4.6 對于文法對于文法G(E)ETE E +TE | TFT T *FT | F(E) | i輸入串為輸入串為i1*i2+i3，利用分析表進行預(yù)測分析：，利用分析表進行預(yù)測分析：i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF

51、(E)整理課件整理課件步驟步驟符號棧符號棧輸入串輸入串所用產(chǎn)生式所用產(chǎn)生式0#Ei1*i2+i3#1#E Ti1*i2+i3# ETE 2#E T Fi1*i2+i3# TFT 3#E T ii1*i2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)整理課件整理課件步驟步驟符號棧符號棧輸入串輸入串所用產(chǎn)生式所用產(chǎn)生式3#E T ii1*i2+i3# Fi4#E T *i2+i3#5#E T F*i2+i3# T *FT 6#E T F i2+i3#7#E T ii2+i3# Fii+*()#EETE ETE E

52、E +TE E E TTFT TFT T T T *FT T T FFiF (E)整理課件整理課件步驟步驟符號棧符號棧輸入串輸入串所用產(chǎn)生所用產(chǎn)生7#E T ii2+i3# Fi 8#E T +i3#9#E +i3# T 10#E T+i3# E +TE 11#E Ti3#i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)整理課件整理課件步驟步驟符號棧符號棧輸入串輸入串所用產(chǎn)生所用產(chǎn)生11#E Ti3#12#E T F i3# TFT 13#E T ii3# Fi14#E T #15#E # T 16# E i+*()#EETE

53、 ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)整理課件整理課件預(yù)測分析表預(yù)測分析表MA，a的構(gòu)造的構(gòu)造q構(gòu)造與文法構(gòu)造與文法G有關(guān)的集合有關(guān)的集合FIRST和和FOLLOWq構(gòu)造分析表構(gòu)造分析表MA，a整理課件整理課件求求FIRST(X)的算法如下：的算法如下：p80若若X VT，則，則FIRST(X)X。若若X VN，且有產(chǎn)生式，且有產(chǎn)生式Xa， a VT則把則把a加入到加入到FIRST(X)中；中；若若X VN ，X ，則，則 FIRST(X)中。中。對每個文法符號對每個文法符號X VT VN ，連續(xù)使用下連續(xù)使用下面的規(guī)則，直至每個面的規(guī)

54、則，直至每個FIRST(X)不再增大為不再增大為止：止：整理課件整理課件 b) 當(dāng)當(dāng)Y1 ，Y2， ，Yi-1都都= , (1 i n) , 則則FIRST( Y1 )-, FIRST( Y2 )-, , FIRST( Yi )- 都包含在都包含在FIRST（X）中）中 c) 當(dāng)當(dāng)Y1 ，Y2， ，Yk都都= ,則則 FIRST(X)，此時，此時FIRST(X)= FIRST( Y1 ) FIRST( Y2 ) FIRST( Yk ) 若若X ，Y1 ，Y2， ，Yk VN ，且有產(chǎn)生式且有產(chǎn)生式 X Y1 Y2 Yk： a) 當(dāng)當(dāng)Y1 不能不能= ，則，則FIRST(Y1 )中的所有符號中的所有符號都在都在FIRST（X）中）中整理課件整理課件n對每個非終結(jié)符對每個非終結(jié)符A，連續(xù)使用下面的規(guī)則，連續(xù)使用下面的規(guī)則，直至每個直至每個FOLLOW(A)不再增大為止：不再增大為止： 對于文法的開始符號對于文法的開始符號S，置，置于于FOLLOW(S)中；中； 對于對于A B 的的產(chǎn)生式，則把產(chǎn)生式，則把FIRST( )-