編譯技術(shù)_語法分析1(1)ppt課件

1、編譯原理第四章第四章 語法分析語法分析自上而下分析自上而下分析1.2四元式四元式單詞符號單詞符號語法單位語法單位四元式四元式目標(biāo)代碼目標(biāo)代碼詞法分析器詞法分析器語法分析器語法分析器語義分析與中間代碼生語義分析與中間代碼生成器成器優(yōu)化段優(yōu)化段源程序源程序表表格格管管理理出出錯錯處處理理目標(biāo)代碼生成器目標(biāo)代碼生成器3第四章第四章 語法分析語法分析自上而下分析自上而下分析n本章主要介紹語法分析的處理本章主要介紹語法分析的處理n要進(jìn)行語法分析，必須對語言的語法結(jié)構(gòu)進(jìn)行描述。要進(jìn)行語法分析，必須對語言的語法結(jié)構(gòu)進(jìn)行描述。采用正規(guī)式和有限自動機(jī)可以描述和識別語言的單詞符號；采用正規(guī)式和有限自動機(jī)可以描述和

2、識別語言的單詞符號；用上下文無關(guān)文法來描述語法規(guī)則。用上下文無關(guān)文法來描述語法規(guī)則。4n上下文無關(guān)文法的定義：上下文無關(guān)文法的定義： 一個上下文無關(guān)文法一個上下文無關(guān)文法G G是一個四元式是一個四元式 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)生式形式為P P， P P V VN

3、N， ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。5n例，定義只含例，定義只含+，*的算術(shù)表達(dá)式的文法的算術(shù)表達(dá)式的文法 G=， 其中，其中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E)6n定義：稱定義：稱 A 直接推出直接推出，即，即 A 僅當(dāng)僅當(dāng)A 是一個產(chǎn)生式，是一個產(chǎn)生式， 且且 ， (VT VN)* 。n如果如果 1 2 n，則我們稱這個序列是從，則我們稱這個序列是從 1到到 n的一個推導(dǎo)。若存的一個推導(dǎo)。若存在一個從在一個從 1到到 n的推導(dǎo)，則稱的推導(dǎo)，則稱 1

4、可以推導(dǎo)出可以推導(dǎo)出 n 。n例：對文法例：對文法(1)E (E) (E+E) (i+E) (i+i)7n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過一步或若干步，可以推出出發(fā)，經(jīng)過一步或若干步，可以推出 n n。n1n*1 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過0 0步或若干步，可以推出步或若干步，可以推出 n n。* 所以所以 ： 即即 或或,|)(*TV SGLq定義：假定定義：假定G G是一個文法，是一個文法，S S 是它的開始符號。如果是它的開始符號。如果 ，則，則 稱是一個稱是一個句句型型。僅含終結(jié)符號的句型是一個。僅含終結(jié)符號的句型是一個句子句子。文法。文法G

5、 G所產(chǎn)生的句子的全體是一個所產(chǎn)生的句子的全體是一個語言語言，將，將它記為它記為 L(G)L(G)。*S 84.1 語法分析器的功能語法分析器的功能n語法分析的任務(wù)是分析一個文法的句子結(jié)構(gòu)。語法分析的任務(wù)是分析一個文法的句子結(jié)構(gòu)。n語法分析器的功能：按照文法的產(chǎn)生式語法分析器的功能：按照文法的產(chǎn)生式( (語言的語法規(guī)則語言的語法規(guī)則) )，識別輸入符，識別輸入符號串是否為一個句子號串是否為一個句子( (程序程序) )。9源程序源程序單詞符號單詞符號取下一單詞取下一單詞.語法分語法分析樹析樹詞法分詞法分析器析器語法分語法分析器析器符號表符號表編譯程序編譯程序后續(xù)部分后續(xù)部分10n語法分析的方法：

6、語法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：從輸入串開始，逐步進(jìn)行基本思想：從輸入串開始，逐步進(jìn)行“歸約歸約”，直到文法的開始符號。即，直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。把產(chǎn)生式的右部替換成左部符號。n算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語法分析。適合算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語法分析。適合分析表達(dá)式。分析表達(dá)式。nLRLR分析法：規(guī)范歸約分析法：規(guī)范歸約11G(E

7、)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E Ei+ +* *EiiEEEE12n語法分析的方法：語法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找基本思想：它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找 匹配匹配 的的推導(dǎo)推導(dǎo)。n遞歸下降分析法：對每一語法變量遞歸下降分析法：對每一語法變量( (非終結(jié)符非終結(jié)符) )構(gòu)造一個相應(yīng)的子程構(gòu)造一個相應(yīng)的子

8、程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現(xiàn)對輸入串的識別。聯(lián)合作用實現(xiàn)對輸入串的識別。n預(yù)測分析程序預(yù)測分析程序F優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。134.2.1 自上而下分析面臨的問題自上而下分析面臨的問題n自上而下就是從文法的開始符號出發(fā)，向下自上而下就是從文法的開始符號出發(fā)，向下推導(dǎo)推導(dǎo)，推出句子。，推出句子。帶帶“回溯回溯”的的不帶回溯的遞歸子程序不帶回溯的遞歸子程序(遞歸下降遞歸下降)分析方法。分析方法。n自上而下分析的主旨：對任何輸入串，試圖用一切可能的辦法，從文法

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

10、n1 | n1W=abbb W=abbb S S b S b 16n當(dāng)某個非終結(jié)符有多個產(chǎn)生式候選時，可能帶來如下問題當(dāng)某個非終結(jié)符有多個產(chǎn)生式候選時，可能帶來如下問題: :1. 1. 分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹配成功時，這種匹配可分析過程中，當(dāng)一個非終結(jié)符用某一個候選匹配成功時，這種匹配可能是暫時的能是暫時的。出錯。出錯時時，不得不，不得不“回溯回溯”。2. 2. 文法左遞歸問題文法左遞歸問題。一個文法是含有左遞歸的，如果存在非終結(jié)符一個文法是含有左遞歸的，如果存在非終結(jié)符P PPP含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。

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

12、1 | P 2 | | P m | 1 | 2| n其中，每個其中，每個 都不等于都不等于 ，每個，每個 都不以都不以P開頭開頭 那么，消除那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：的直接左遞歸性就是把這些規(guī)則改寫成： P 1P | 2P | | nP P 1P | 2P | | mP | 左遞歸變右遞歸20n例例 文法文法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 | | n

13、P P 1P | 2P | | mP | 21n例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)雖沒有直接左遞歸，但雖沒有直接左遞歸，但S、Q、R都是左遞歸的都是左遞歸的SQcRbcSabc一個文法消除左遞歸的條件：一個文法消除左遞歸的條件：F不含以不含以 為右部的產(chǎn)生式為右部的產(chǎn)生式F不含回路。不含回路。PP22n消除左遞歸的算法消除左遞歸的算法:1. 把文法把文法G的所有非終結(jié)符按任一種順序排列成的所有非終結(jié)符按任一種順序排列成P1，P2，Pn；按此順序；按此順序執(zhí)行；執(zhí)行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如

14、把形如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ā)永遠(yuǎn)無法到達(dá)的非終結(jié)符所得的文法。去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。的產(chǎn)生規(guī)則。23n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|an令它的非終結(jié)符的排序為令它的非終結(jié)符的排序為R、Q、S。n對于對于R，不存在直接左遞歸。，不存在直接左遞歸。n把把R代入到代入到Q的有關(guān)候選后，把的有關(guān)候選后，把Q的規(guī)則

15、變?yōu)榈囊?guī)則變?yōu)?QSab | ab | b24n例例 考慮文法考慮文法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 | c25n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|anS變成變成SSabc | abc | bc | cn消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab |

16、 bRSa|a26n例例 考慮文法考慮文法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)27n注意，由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一注意，由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的。樣。但不難證明，它們都是等價的。n例如，若對文法例如，若對文法(4.3)的非終結(jié)符排序選為的非終

17、結(jié)符排序選為S、Q、R，那么，最后所得的，那么，最后所得的無左遞歸文法是：無左遞歸文法是：SQc | cQRb | bRbcaR | caR |a R (4.5)R bca R | n文法文法(4.4)和和(4.5)的等價性是顯然的。的等價性是顯然的。284.2.4 消除回溯、提左因子消除回溯、提左因子n為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個候選去執(zhí)行任串時，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。務(wù)，并

18、且此候選的工作結(jié)果應(yīng)是確信無疑的。nA 1 | 2 | | nSa.IPA.29n令令G是一個不含左遞歸的文法，對是一個不含左遞歸的文法，對G的所有非終結(jié)符的每個候選的所有非終結(jié)符的每個候選 定義它的定義它的終結(jié)首符集終結(jié)首符集FIRST( )為：為：.,|=)(*TVaaaFIRST 特別是，若特別是，若 ，則規(guī)定，則規(guī)定FIRST( )。* 如果非終結(jié)符如果非終結(jié)符A的所有候選首符集兩兩不相交，即的所有候選首符集兩兩不相交，即A的任何兩個不同候選的任何兩個不同候選 i和和 jFIRST( i)FIRST( j) 當(dāng)要求當(dāng)要求A匹配輸入串時，匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符號就

19、能根據(jù)它所面臨的第一個輸入符號a，準(zhǔn)確地指派某，準(zhǔn)確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含一個候選前去執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含a的的 。30n提取公共左因子提取公共左因子: 假定關(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ù)提取左因子，就能夠把每個非終結(jié)符經(jīng)過反復(fù)提取左因子，就能夠把每個非終結(jié)符(包括新引進(jìn)者包括新引進(jìn)者)的所有候選的所有候選首符集變成為

20、兩兩不相交。首符集變成為兩兩不相交。31n ETE E +TE | TFT T *FT | F(E) | in i + i4.2.4 LL(1)分析條件分析條件32i + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) | i33i + i IPETEnG(E): ETE E +TE | TFT T *FT | F(E) | i34i + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i35i + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i36i + i I

21、PETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i37i + i IPETEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | i38i + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | i39i + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | i40i + i IPETEFTi +TEFTnG(E): ETE E +TE | TFT T *FT | F(E) | i41i + i IPETEFTi +T

22、EFTinG(E): ETE E +TE | TFT T *FT | F(E) | i42i + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | i43i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | i44i + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iS T+45n假定假定S是文法是文法G的開始符號，對于的開始符號，對于G的任何非終結(jié)符的任何非終結(jié)符A，我們定義，我們定義.,.|)(*T

23、VaAaSaAFOLLOWAS*特別是，若特別是，若 ，則規(guī)定，則規(guī)定 FOLLOW(A)4.2.4 LL(1)分析條件分析條件46n構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，文法不含左遞歸，2. 對于文法中每一個非終結(jié)符對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即的各個產(chǎn)生式的候選首符集兩兩不相交。即，若，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對文法中的每個非終結(jié)符對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含，若它存在某個候選首符集包含 ，則，則FIRST( i)FOL

24、LOW(A)= i=1,2,.,n如果一個文法如果一個文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為LL(1)LL(1)文法文法。47n對于一個滿足上述條件的文法，可以對其輸入串進(jìn)行有效的無回溯的自上而下對于一個滿足上述條件的文法，可以對其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號為進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為A 1 | 2 | | n1. 若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2. 若若a不屬于任何一個候選首符集，則：不屬于任何一個候選首符集，則： (

25、1) 若若 屬于某個屬于某個FIRST( i )且且 a FOLLOW(A)， 則讓則讓A與與 自動匹配。自動匹配。 (2) 否則，否則，a的出現(xiàn)是一種語法錯誤。的出現(xiàn)是一種語法錯誤。48.,|=)(*TVaaaFIRST4.2.6 構(gòu)造構(gòu)造FIRST( )若若* 則規(guī)定則規(guī)定 FIRST( )直觀上說文法符號串直觀上說文法符號串 的開始符號集是由的開始符號集是由 推導(dǎo)出的開頭的終結(jié)符推導(dǎo)出的開頭的終結(jié)符（包括（包括）組成。）組成。 49n例文法例文法GS: SApSBqAaAcABbBdBFIRST(Ap)=a,cFIRST(Bq)=b,dFIRST(a)=a FIRST(cA)=cFIRS

26、T(b)=bFIRST(dB)=d由于同一非終結(jié)符的兩個產(chǎn)生式的右部推導(dǎo)出來的開始符號集不相交，因此可根由于同一非終結(jié)符的兩個產(chǎn)生式的右部推導(dǎo)出來的開始符號集不相交，因此可根據(jù)當(dāng)前輸入符屬于哪個產(chǎn)生式右部的開始符號集而決定選哪個產(chǎn)生式進(jìn)行推導(dǎo)，據(jù)當(dāng)前輸入符屬于哪個產(chǎn)生式右部的開始符號集而決定選哪個產(chǎn)生式進(jìn)行推導(dǎo)，可以進(jìn)行確定的自頂向下分析可以進(jìn)行確定的自頂向下分析50n對每一文法符號對每一文法符號X VTVN構(gòu)造構(gòu)造FIRST(X) 連續(xù)使用下面的規(guī)則，直至每個集合連續(xù)使用下面的規(guī)則，直至每個集合FIRST不再增大為止：不再增大為止：1. 若若X VT，則，則FIRST(X)X。2. 若若X

27、VN，且有產(chǎn)生式，且有產(chǎn)生式Xa，則把，則把a(bǔ)加入到加入到FIRST(X)中；若中；若X 也是一也是一條產(chǎn)生式，則把條產(chǎn)生式，則把 也加到也加到FIRST(X)中。中。513. l若若XY是一個產(chǎn)生式且是一個產(chǎn)生式且Y VN，則把，則把FIRST(Y)中的所有非中的所有非 -元素都加到元素都加到FIRST(X)中；中；l若若XY1Y2Yk是一個產(chǎn)生式，是一個產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對于任都是非終結(jié)符，而且，對于任何何j，1 j i-1，F(xiàn)IRST(Yj)都含有都含有 (即即Y1Yi-1 )， 則把則把FIRST(Yi)中的所有非中的所有非 -元素都加到元素都加到FIRST(X

28、)中；特別是，若所有的中；特別是，若所有的FIRST(Yj)均含有均含有 ，j1，2，k，則把，則把 加到加到FIRST(X)中。中。52n對文法對文法G的任何符號串的任何符號串 =X1X2Xn構(gòu)造集合構(gòu)造集合FIRST( )。1. 置置FIRST( )FIRST(X1) ；2. 若對任何若對任何1 j i-1，F(xiàn)IRST(Xj)，則把，則把FIRST(Xi) 加至加至FIRST( )中；中；特別是，若所有的特別是，若所有的FIRST(Xj)均含有均含有 ，1 j n，則把，則把 也加至也加至FIRST( )中。顯然，若中。顯然，若 則則FIRST( ) 。53n例例4.6 對于文法對于文法G

29、(E)ETE E +TE | TFT T *FT | F(E) | i | x構(gòu)造每個非終結(jié)符的構(gòu)造每個非終結(jié)符的FIRST：54x xi i(,i,x*,(,i,x+,(,i,xFirstFirst集集(3)(3)x xi i(,i,x*,(,i,x+,(,i,xFirstFirst集集(2)(2)x xi i (,i,x+,FirstFirst集集(1)(1)E E T TT TF Fi ix xE E*,(,i,xi ix x+,FirstFirst集集(0)(0) * *, , (,i,x55.,.|)(*TVaAaSaAFOLLOW4.2.6 構(gòu)造構(gòu)造FOLLOW(A)若有若有S=*

30、 A，則規(guī)定，則規(guī)定 # FOLLOW(A)（注：（注： # 輸入串輸入串#，#做為輸入串的結(jié)束符）做為輸入串的結(jié)束符）直觀上說直觀上說,非終結(jié)符非終結(jié)符A的后跟符號集是由句型中緊跟的后跟符號集是由句型中緊跟A后的那些終結(jié)符后的那些終結(jié)符（包括（包括#）組成。）組成。56n例例 文法文法G S:SaA|d AbAS|由由 S=* S 得得 # FOLLOW(S) 由由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOW(S)=#,a,d由由S=* aA 得得 # FOLLOW(A) 由由S=* abAS=* abAaA 得得 a FOLLOW(A) =* abAd 得

31、得 d FOLLOW(A) FOLLOW(A)=#,a,d57n對于文法對于文法G的每個非終結(jié)符的每個非終結(jié)符A構(gòu)造構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的辦法是，連續(xù)使用下面的規(guī)則，直至每個的規(guī)則，直至每個FOLLOW不再增大為止：不再增大為止：1. 對于文法的開始符號對于文法的開始符號S，置于，置于FOLLOW(S)中；中；2. 若若A B 是一個產(chǎn)生式，則把是一個產(chǎn)生式，則把FIRST( ) 加至加至FOLLOW(B)中；中；3. 若若A B是一個產(chǎn)生式，或是一個產(chǎn)生式，或AB 是一個產(chǎn)生式而是一個產(chǎn)生式而 (即即FIRST( )， 則把則把FOLLOW(A)加至加至FOLLOW(

32、B)中。中。58n例例4.6 對于文法對于文法G(E)ETE E +TE | TFT T *FT | F(E) | i | x構(gòu)造每個非終結(jié)符的構(gòu)造每個非終結(jié)符的FOLLOW集：集：59*,+,#,)+,#,)+,#,)#,)#,)FollowFollow集集(2)(2) +,#,)#,)#,)FollowFollow集集(1)(1)E E T TT TF FE E*+#,)FollowFollow集集(0)(0)+,#,)*,+,#,)60n例例4.6 對于文法對于文法G(E)ETE E +TE | TFT T *FT | F(E) | i構(gòu)造每個非終結(jié)符的構(gòu)造每個非終結(jié)符的FIRST和和F

33、OLLOW集合：集合： FIRST(E) =(,iFIRST(E )=+, FIRST(T) =(,iFIRST(T )=*, FIRST(F) =(,i FOLLOW(E) =),#FOLLOW(E )=),#FOLLOW(T) =+,),#FOLLOW(T )=+,),#FOLLOW(F) =*,+,),#614.2.7 預(yù)測分析程序預(yù)測分析程序一、預(yù)測分析程序工作原理一、預(yù)測分析程序工作原理n if(a FIRST( i) 用用A i推導(dǎo)推導(dǎo)n else if(a FOLLOW(A)用用A 推導(dǎo)推導(dǎo)n else 語法錯誤語法錯誤n預(yù)測分析程序或預(yù)測分析程序或LL(1)分析法：分析法：總控

34、程序總控程序分析表分析表 MA，a矩陣，矩陣，A VN ，a VT 是終結(jié)符或是終結(jié)符或，分析棧分析棧 STACK 用于存放文法符號用于存放文法符號62總控程序總控程序分析表分析表X#輸入串輸入串分析棧分析棧STACKa1a2.ai#預(yù)測分析程序的工作圖預(yù)測分析程序的工作圖# Sa1a2.ai#分析開始時：分析開始時：輸出流輸出流63q 總控程序根據(jù)現(xiàn)行棧頂符號總控程序根據(jù)現(xiàn)行棧頂符號X和當(dāng)前輸入符號和當(dāng)前輸入符號a，執(zhí)行下列三種動作之一，執(zhí)行下列三種動作之一:1. 若若Xa，則宣布分析成功，停止分析。，則宣布分析成功，停止分析。2. 若若Xa ，則把，則把X從從STACK棧頂逐出，讓棧頂逐出

35、，讓a指向下一個輸入符號。指向下一個輸入符號。匹配成功643. 若若X是一個非終結(jié)符，則查看分析表是一個非終結(jié)符，則查看分析表M。 若若MX，a中存放著關(guān)于中存放著關(guān)于X的一個產(chǎn)生式，把的一個產(chǎn)生式，把X逐出逐出STACK棧頂，棧頂，把把產(chǎn)生式的右部符號串按反序一一推進(jìn)產(chǎn)生式的右部符號串按反序一一推進(jìn)STACK棧棧(若右部符號為若右部符號為 ，則，則意味不推什么東西進(jìn)棧意味不推什么東西進(jìn)棧)。在把產(chǎn)生式的右部符號推進(jìn)棧的同時應(yīng)做。在把產(chǎn)生式的右部符號推進(jìn)棧的同時應(yīng)做這個產(chǎn)生式相應(yīng)的語義動作。這個產(chǎn)生式相應(yīng)的語義動作。若若MX，a中存放著中存放著“出錯標(biāo)志出錯標(biāo)志”，則調(diào)用出錯診察程序，則調(diào)用出

36、錯診察程序ERROR。推導(dǎo)65預(yù)測分析程序流程預(yù)測分析程序流程上托棧頂符放入上托棧頂符放入XNYYNNNN YY Y把把#和文法開始符壓入分析棧；和文法開始符壓入分析棧； 當(dāng)前輸入符送當(dāng)前輸入符送a把產(chǎn)生式右部反把產(chǎn)生式右部反序進(jìn)棧序進(jìn)棧XVT ?X=# ? X=a ?X=a?讀下一輸入讀下一輸入符到符到aMX,a有產(chǎn)生式有產(chǎn)生式？出錯出錯結(jié)束結(jié)束出錯出錯預(yù)測分析程序工作過程預(yù)測分析程序工作過程66n預(yù)測分析程序的總控程序：預(yù)測分析程序的總控程序：BEGIN 首先把首先把然后把文法開始符號推進(jìn)然后把文法開始符號推進(jìn)STACK棧；棧； 把第一個輸入符號讀進(jìn)把第一個輸入符號讀進(jìn)a； FLAG:=T

37、RUE; WHILE FLAG DOBEGIN 把把STACK棧頂符號上托出去并放在棧頂符號上托出去并放在X中；中； IF X VT THEN IF X= a THEN 把下一輸入符號讀進(jìn)把下一輸入符號讀進(jìn)a ELSE ERROR 匹配成功67 ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MX,a=XX1X2XkTHEN 把把Xk,Xk-1,X1一一推進(jìn)一一推進(jìn)STACK棧棧 /* 若若X1X2Xk= ，不推什么進(jìn)棧，不推什么進(jìn)棧 */ ELSE ERROR END OF WHILE;STOP /*分析成功，過程完畢分

38、析成功，過程完畢*/END分析成功推導(dǎo)68n例例4.6 對于文法對于文法G(E)ETE E +TE | TFT T *FT | F(E) | i輸入串為輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測分析：，利用分析表進(jìn)行預(yù)測分析：i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)69步驟步驟符號棧符號棧輸入串輸入串所用產(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 TT

39、FT TFT T T T *FT T T FFiF (E)70步驟步驟符號棧符號棧輸入串輸入串所用產(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 E +TE E E TTFT TFT T T T *FT T T FFiF (E)71步驟步驟符號棧符號棧輸入串輸入串所用產(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

40、 ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)72步驟步驟符號棧符號棧輸入串輸入串所用產(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 ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)73二、分析表二、分析表MA，a的構(gòu)造的構(gòu)造q構(gòu)造構(gòu)造FIRST( )和和FOLLOW(A)q構(gòu)造分析表構(gòu)造分析表MA，a74n例例4.6 對于文法對于文法G(E)ETE E +TE | TFT T *FT |

41、 F(E) | i構(gòu)造每個非終結(jié)符的構(gòu)造每個非終結(jié)符的FIRST和和FOLLOW集合：集合： FIRST(E) =(,iFIRST(E )=+, FIRST(T) =(,iFIRST(T )=*, FIRST(F) =(,i FOLLOW(E) =),#FOLLOW(E )=),#FOLLOW(T) =+,),#FOLLOW(T )=+,),#FOLLOW(F) =*,+,),#75n在對文法在對文法G的每個非終結(jié)符的每個非終結(jié)符A及其任意候選及其任意候選 都構(gòu)造出都構(gòu)造出FIRST( )和和FOLLOW(A)之后，現(xiàn)在可以用它們來構(gòu)造之后，現(xiàn)在可以用它們來構(gòu)造G的分析表的分析表MA，a。1.

42、 對文法對文法G的每個產(chǎn)生式的每個產(chǎn)生式A 執(zhí)行第執(zhí)行第2步和第步和第3步；步；2. 對每個終結(jié)符對每個終結(jié)符a FIRST( )，把，把A 加至加至MA，a中；中；3. 若若FIRST( )，則對任何，則對任何b FOLLOW(A)把把A 加至加至MA，b中。中。4. 把所有無定義的把所有無定義的MA，a標(biāo)上標(biāo)上“出錯標(biāo)志出錯標(biāo)志”。76i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)77n如果如果G是左遞歸或二義的，那么，是左遞歸或二義的，那么，M至少含有一個多重定義入口。因此，至少含有一個多重定義入口。因此，消除左遞歸和

43、提取左因子將有助于獲得無多重定義的分析表消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。n可以證明，一個文法可以證明，一個文法G的預(yù)測分析表的預(yù)測分析表M不含多重定義入口，當(dāng)且僅當(dāng)該不含多重定義入口，當(dāng)且僅當(dāng)該文法為文法為LL(1)的。的。78G(S):S iCtS | iCtSeS | aC b提取左因子之后，改寫成：提取左因子之后，改寫成：G(S):S iCtSS | aS eS | C babeit#SSaSiCtSS S S S eSS CCbF (E)最近匹配原則 794.2.10 遞歸下降分析遞歸下降分析程序構(gòu)造程序構(gòu)造n構(gòu)造不帶回溯的自上而下分析程序構(gòu)造不帶回溯的自上而下

44、分析程序要消除文法的左遞歸性要消除文法的左遞歸性克服回溯克服回溯80q實現(xiàn)思想：實現(xiàn)思想：對文法中的每個非終結(jié)符編寫一個遞歸過程，識別由該非終結(jié)符推出的對文法中的每個非終結(jié)符編寫一個遞歸過程，識別由該非終結(jié)符推出的串。當(dāng)非終結(jié)符有多條產(chǎn)生式時，按當(dāng)前輸入符屬于哪條產(chǎn)生式的串。當(dāng)非終結(jié)符有多條產(chǎn)生式時，按當(dāng)前輸入符屬于哪條產(chǎn)生式的FIRST集或集或FOLLOW集（集（A ）可唯一確定選擇哪個產(chǎn)生式進(jìn)行匹配。）可唯一確定選擇哪個產(chǎn)生式進(jìn)行匹配。當(dāng)識別到終結(jié)符時，與當(dāng)前輸入符號匹配，并讀取下一輸入符；當(dāng)識別到終結(jié)符時，與當(dāng)前輸入符號匹配，并讀取下一輸入符；當(dāng)識別到非終結(jié)符時，則調(diào)用該非終結(jié)符相應(yīng)的過

45、程。當(dāng)識別到非終結(jié)符時，則調(diào)用該非終結(jié)符相應(yīng)的過程。81n例例 算術(shù)表達(dá)式文法算術(shù)表達(dá)式文法G: ETE E+TE TFT T*FTF(E)i判斷判斷G是是LL(1)文法文法1 判斷是否可以應(yīng)用遞歸子程序法判斷是否可以應(yīng)用遞歸子程序法822 構(gòu)造文法構(gòu)造文法G的遞歸下降分析器的遞歸下降分析器n定義：定義：當(dāng)一個文法滿足當(dāng)一個文法滿足LL(1)LL(1)條件時，就為它構(gòu)造一個不帶回溯的自頂向下的分析程條件時，就為它構(gòu)造一個不帶回溯的自頂向下的分析程序，這個分析程序由一組遞歸過程組成，每個過程對應(yīng)文法的一個非終結(jié)符。序，這個分析程序由一組遞歸過程組成，每個過程對應(yīng)文法的一個非終結(jié)符。這樣的一個分析

46、程序稱為遞歸下降分析器。這樣的一個分析程序稱為遞歸下降分析器。83n組成：組成：遞歸下降分析器由一個主程序遞歸下降分析器由一個主程序MAINMAIN和每個非終結(jié)符對應(yīng)的一個遞歸過程組成。和每個非終結(jié)符對應(yīng)的一個遞歸過程組成。用到的一些子過程：用到的一些子過程：過程過程GETNEXTGETNEXT負(fù)責(zé)讀入下一個負(fù)責(zé)讀入下一個TOKENTOKEN字字過程過程ERRORERROR負(fù)責(zé)報告語法錯誤負(fù)責(zé)報告語法錯誤約定：約定：變量變量TOKENTOKEN存放已讀入的存放已讀入的TOKENTOKEN字字過程進(jìn)入時變量過程進(jìn)入時變量TOKENTOKEN存放了一個待匹配的存放了一個待匹配的TOKENTOKEN

47、字字退出過程時，變量退出過程時，變量TOKENTOKEN中仍存放著一個待匹配的中仍存放著一個待匹配的TOKENTOKEN字。字。 84非終結(jié)符相應(yīng)的分析子程序的構(gòu)造方法非終結(jié)符相應(yīng)的分析子程序的構(gòu)造方法對于每個非終結(jié)符對于每個非終結(jié)符U，編寫一個相應(yīng)的子程序，編寫一個相應(yīng)的子程序P(U);對于產(chǎn)生式對于產(chǎn)生式Ux1 | x2 |xn，x1,.xn都都 關(guān)于關(guān)于U的子程序的子程序P(U)按如下方法構(gòu)造：按如下方法構(gòu)造：if TOKEN in first(x1) then p(x1) else if TOKEN in first(x2) then p(x2) else . if TOKEN in

48、first(xn) then p(xn) else ERROR85如果如果U還有空產(chǎn)生式還有空產(chǎn)生式U ,則算法中的語句：則算法中的語句：if TOKEN in first(xn) then p(xn) else ERROR改寫為改寫為if TOKEN in first(xn) then p(xn) else if TOKEN not in follow(U) then ERROR對于符號串對于符號串x=y1y2yn；p(x)的含義為：的含義為：begin p(y1);p(y2);p(yn) end如果如果yiVN，則，則P(yi)就代表調(diào)用就代表調(diào)用yi的子程序；的子程序；yiVT T，則，

49、則P(yi)為形如下述語句的一段為形如下述語句的一段程序程序if TOKEN=yi then GETNEXT(TOKEN) else ERROR86(1) program MAIN; /* 主程序主程序 */ begin GETNEXT (TOKEN); E (TOKEN); /* 轉(zhuǎn)匹配轉(zhuǎn)匹配ETE */ if TOKEN # then ERROR end. 構(gòu)造文法構(gòu)造文法G：ETE E+TE TFT T*FTF(E)i的遞歸下降分析器的遞歸下降分析器(2) procedure E (TOKEN); /*匹配匹配ETE*/ begin T (TOKEN); /*轉(zhuǎn)匹配轉(zhuǎn)匹配TFT*/ E (TOKEN) /*轉(zhuǎn)匹配轉(zhuǎn)匹配E+TE*/ end; 87(3) procedure E (TOKEN); /*匹配匹配E+TE*/ begin if TOKEN=+ then /*選擇產(chǎn)生式選擇產(chǎn)生式E+TE*/ begin GETNEXT (TOKEN);/*匹配匹配+,讀下一個讀下一個TOKEN字字*/ T (TOKEN); /*轉(zhuǎn)匹配轉(zhuǎn)匹配TFT*/ E (TOKEN) /*轉(zhuǎn)匹配轉(zhuǎn)匹配E+TE*/ end else /*E對應(yīng)的語句對應(yīng)的語句*/if TOKEN) and TOKEN# then ER