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

2、的單詞符號(hào)；用用上下文無關(guān)文法上下文無關(guān)文法來描述語法規(guī)則。來描述語法規(guī)則。 上下文無關(guān)文法的定義：上下文無關(guān)文法的定義： 一個(gè)上下文無關(guān)文法一個(gè)上下文無關(guān)文法G G是一個(gè)四元式是一個(gè)四元式 G=(V G=(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：文法的開始符號(hào)，：文法的開始符號(hào)，S S V VN NP P：產(chǎn)生式集合：產(chǎn)生式集合( (有限有限) )，每個(gè)產(chǎn)生式形式為，每個(gè)產(chǎn)生式形式為P P， P P V VN N， (

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

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

5、從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或若干步，可以推出一步或若干步，可以推出 n n。4.1 語法分析器的功能語法分析器的功能 語法分析的任務(wù)語法分析的任務(wù)是分析一個(gè)文法的句子是分析一個(gè)文法的句子結(jié)構(gòu)。結(jié)構(gòu)。 語法分析器的功能語法分析器的功能：按照文法的產(chǎn)生式：按照文法的產(chǎn)生式( (語言的語法規(guī)則語言的語法規(guī)則) )，識(shí)別輸入符號(hào)串是，識(shí)別輸入符號(hào)串是否為一個(gè)句子否為一個(gè)句子( (合式程序合式程序) )。源程序源程序單詞符號(hào)單詞符號(hào)取下一單詞取下一單詞.語法分語法分析樹析樹詞法分詞法分析器析器語法分語法分析器析器符號(hào)表符號(hào)表編譯程序編譯程序后續(xù)部分后續(xù)部分語法分析的方法：語法分析的方法：

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

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

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

9、號(hào)圖用一切可能的辦法，從文法開始符號(hào)(根根結(jié)點(diǎn)結(jié)點(diǎn))出發(fā)，自上而下地為輸入串建立一棵出發(fā)，自上而下地為輸入串建立一棵語法樹語法樹。或者說，為輸入串尋找一個(gè)最。或者說，為輸入串尋找一個(gè)最左推導(dǎo)。左推導(dǎo)。 例例3.4.1 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析輸入串分析輸入串x*y(記為記為 )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy* 當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，可當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，可能帶來如下問題能帶來如下問題: :1. 1. 分析過程中，當(dāng)一個(gè)非終結(jié)

10、符用某一個(gè)候選分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)時(shí)出錯(cuò)時(shí)，不得不，不得不“回溯回溯”。2. 2. 文法左遞歸問題。一個(gè)文法是含有左遞歸的文法左遞歸問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符，如果存在非終結(jié)符P PPP 含有左遞歸的文法將使自上而下的分含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)析陷入無限循環(huán)。4.3 LL(1)分析法分析法 構(gòu)造不帶回溯的自上而下分析算法構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性要消除文法的左遞歸性 克服回溯克服回溯4.3.1 左遞歸的消除左遞歸的消除 直接消除見諸于產(chǎn)生

11、式中的左遞歸：假直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符定關(guān)于非終結(jié)符P的規(guī)則為的規(guī)則為PP | 其中其中 不以不以P開頭。開頭。 可以把可以把P的規(guī)則等價(jià)地改寫為如下的非直的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：接左遞歸形式：P P P P | 左遞歸變右遞歸 一般而言，假定一般而言，假定P關(guān)于的全部產(chǎn)生式是關(guān)于的全部產(chǎn)生式是PP 1 | P 2 | | P m | 1 | 2| n其中，每個(gè)其中，每個(gè) 都不等于都不等于 ，每個(gè)，每個(gè) 都不以都不以P開頭開頭 那么，消除那么，消除P的直接左遞歸性就是把這些規(guī)的直接左遞歸性就是把這些規(guī)則改寫成：則改寫成： P 1P | 2P | |

12、nP P 1P | 2P | | mP | 左遞歸變右遞歸 例例 文法文法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 | | nP P 1P | 2P | | mP | 例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)雖沒有直接左遞歸，但雖沒有直接左遞歸，但S、Q、R都是左遞歸的都是左遞歸的SQcRbcSabc一個(gè)文法消除左遞歸的條件：一個(gè)文法消除左遞歸的條件：F

13、不含以不含以 為右部的產(chǎn)生式為右部的產(chǎn)生式F不含回路。不含回路。PP 消除左遞歸的算法消除左遞歸的算法:1. 把文法把文法G的所有非終結(jié)符按任一種順序排列成的所有非終結(jié)符按任一種順序排列成P1，P2，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. 化簡(jiǎn)由化簡(jiǎn)由2所得的文法。去除那些從開始符號(hào)出發(fā)永所得的文

14、法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。 例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|a 令它的非終結(jié)符的排序?yàn)榱钏姆墙K結(jié)符的排序?yàn)镽、Q、S。 對(duì)于對(duì)于R，不存在直接左遞歸。，不存在直接左遞歸。 把把R代入到代入到Q的有關(guān)候選后，把的有關(guān)候選后，把Q的規(guī)則的規(guī)則變?yōu)樽優(yōu)?QSab | ab | b 例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|a 令它的非終結(jié)符的排序?yàn)榱钏姆墙K結(jié)符的排序?yàn)镽、Q、S。 Q的規(guī)則變?yōu)榈囊?guī)則變?yōu)?QSab | ab | b 現(xiàn)在的現(xiàn)在的Q不含直接左遞歸，把它代入到不含直接左遞歸，把

15、它代入到S的有關(guān)候選后，的有關(guān)候選后，S變成變成SSabc | abc | bc | c 例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|a S變成變成SSabc | abc | bc | c 消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|a 例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|a 消除消除S的直接左遞歸后：的直接左遞歸后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|a 關(guān)于關(guān)于Q和和R的規(guī)則已是多余的，化簡(jiǎn)為：的規(guī)則已是多余的，化簡(jiǎn)為：Sab

16、cS | bcS | cS S abcS | (4.4) 注意，由于對(duì)非終結(jié)符排序的不同，最注意，由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但后所得的文法在形式上可能不一樣。但不難證明，它們都是等價(jià)的。不難證明，它們都是等價(jià)的。 例如，若對(duì)文法例如，若對(duì)文法(4.3)的非終結(jié)符排序選的非終結(jié)符排序選為為S、Q、R，那么，最后所得的無左遞，那么，最后所得的無左遞歸文法是：歸文法是：SQc | cQRb | bRbcaR | caR |a R (4.5)R bca R | 文法文法(4.4)和和(4.5)的等價(jià)性是顯然的。的等價(jià)性是顯然的。4.3.2 消除回溯、提左因子消除回溯、

17、提左因子 為了消除回溯就必須保證：對(duì)文法的任為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的選的工作結(jié)果應(yīng)是確信無疑的。 A 1 | 2 | | nSa.IPA. 令令G是一個(gè)不含左遞歸的文法，對(duì)是一個(gè)不含左遞歸的文法，對(duì)G的所的所有非終結(jié)符的每個(gè)候選有非終結(jié)符的每個(gè)候選 定義它的終結(jié)首定義它的終結(jié)首符集符集FIRST( )為：為：.,|=)(*TVaaaFIRST 特別是，若特別

18、是，若 ，則規(guī)定，則規(guī)定FIRST( )。*如果非終結(jié)符如果非終結(jié)符A的所有候選首符集兩兩不相交，的所有候選首符集兩兩不相交，即即A的任何兩個(gè)不同候選的任何兩個(gè)不同候選 i和和 jFIRST( i)FIRST( j) 當(dāng)要求當(dāng)要求A匹配輸入串時(shí)，匹配輸入串時(shí)，A就能根據(jù)它所面臨的就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的的 。 提取公共左因子提取公共左因子: 假定關(guān)于假定關(guān)于A的規(guī)則是的規(guī)則是 A 1 | 2 | | n | 1 | 2 | | m (其中，

19、每個(gè)其中，每個(gè) 不以不以 開頭開頭) 那么，可以把這些規(guī)則改寫成那么，可以把這些規(guī)則改寫成A A | 1 | 2 | | mA 1 | 2 | | n 經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符結(jié)符(包括新引進(jìn)者包括新引進(jìn)者)的所有候選首符集變的所有候選首符集變成為兩兩不相交。成為兩兩不相交。 ETE E +TE | TFT T *FT | F(E) | i i + i4.3.3 LL(1)分析條件分析條件i + i IPEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEnG(E): ETE E +TE |

20、TFT T *FT | F(E) | ii + i IPETEFTnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETE

21、FTi +TEnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTnG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTinG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | ii + i IPETEFTi

22、 +TEFTi nG(E): ETE E +TE | TFT T *FT | F(E) | iS T+ 假定假定S是文法是文法G的開始符號(hào)，對(duì)于的開始符號(hào)，對(duì)于G的任何的任何非終結(jié)符非終結(jié)符A，我們定義，我們定義.,.|)(*TVaAaSaAFOLLOWAS*特別是，若特別是，若 ，則規(guī)定，則規(guī)定 FOLLOW(A)4.3.3 LL(1)分析條件分析條件n構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，文法不含左遞歸，2. 對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若的候選首符集兩兩不相交

23、。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對(duì)文法中的每個(gè)非終結(jié)符對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)，若它存在某個(gè)候選首符集包含候選首符集包含 ，則，則FIRST( i)FOLLOW(A)= i=1,2,.,n如果一個(gè)文法如果一個(gè)文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為L(zhǎng)L(1)LL(1)文法文法。 對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自上而下分析入串進(jìn)行有效的無回溯的自上而下分析。 假設(shè)要用非終結(jié)符假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入進(jìn)行匹配，面臨的輸入符號(hào)為符

24、號(hào)為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為A 1 | 2 | | n1. 若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2. 若若a不屬于任何一個(gè)候選首符集，則：不屬于任何一個(gè)候選首符集，則： (1) 若若 屬于某個(gè)屬于某個(gè)FIRST( i )且且 a FOLLOW(A)， 則讓則讓A與與 自動(dòng)匹配。自動(dòng)匹配。 (2) 否則，否則，a的出現(xiàn)是一種語法錯(cuò)誤。的出現(xiàn)是一種語法錯(cuò)誤。回顧：回顧：LL(1)分析法分析法 構(gòu)造不帶回溯的自上而下分析算法構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性要消除文法的左遞歸性 克服回溯克服回溯 一般而言，假定一般而言，假定P關(guān)于的全

25、部產(chǎn)生式是關(guān)于的全部產(chǎn)生式是PP 1 | P 2 | | P m | 1 | 2| n其中，每個(gè)其中，每個(gè) 都不等于都不等于 ，每個(gè)，每個(gè) 都不以都不以P開頭開頭 那么，那么，消除消除P的直接左遞歸性就是把這些規(guī)的直接左遞歸性就是把這些規(guī)則改寫成則改寫成： P 1P | 2P | | nP P 1P | 2P | | mP | 消除左遞歸的算法消除左遞歸的算法:1. 把文法把文法G的所有非終結(jié)符按任一種順序排列成的所有非終結(jié)符按任一種順序排列成P1，P2，Pn；按此順序執(zhí)行；按此順序執(zhí)行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如Pi

26、Pj 的規(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. 化簡(jiǎn)由化簡(jiǎn)由2所得的文法。去除那些從開始符號(hào)出發(fā)永所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。回顧：回顧：LL(1)分析法分析法 構(gòu)造不帶回溯的自上而下分析算法構(gòu)造不帶回溯的自上而下分析算法 要消除文法的左遞歸性要消除文法的左遞歸性 克服回溯克服回溯4.3.2 消除回溯、提左因子消除回溯、提左因子 為了消除回溯就必須保證：為了消除回溯就必須

27、保證：對(duì)文法的任對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的選的工作結(jié)果應(yīng)是確信無疑的。 A 1 | 2 | | nSa.IPA. 令令G是一個(gè)不含左遞歸的文法，對(duì)是一個(gè)不含左遞歸的文法，對(duì)G的所的所有非終結(jié)符的每個(gè)候選有非終結(jié)符的每個(gè)候選 定義它的終結(jié)首定義它的終結(jié)首符集符集FIRST( )為：為：.,|=)(*TVaaaFIRST 特別是，若特別是，若 ，則規(guī)定，則規(guī)定FIRST( )。*如果非終

28、結(jié)符如果非終結(jié)符A的所有候選首符集兩兩不相交，的所有候選首符集兩兩不相交，即即A的任何兩個(gè)不同候選的任何兩個(gè)不同候選 i和和 jFIRST( i)FIRST( j) 當(dāng)要求當(dāng)要求A匹配輸入串時(shí)，匹配輸入串時(shí)，A就能根據(jù)它所面臨的就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的的 。 提取公共左因子提取公共左因子: 假定關(guān)于假定關(guān)于A的規(guī)則是的規(guī)則是 A 1 | 2 | | n | 1 | 2 | | m (其中，每個(gè)其中，每個(gè) 不以不以 開頭開頭) 那么，可以把這

29、些規(guī)則改寫成那么，可以把這些規(guī)則改寫成A A | 1 | 2 | | mA 1 | 2 | | n 經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符結(jié)符(包括新引進(jìn)者包括新引進(jìn)者)的所有候選首符集變的所有候選首符集變成為兩兩不相交成為兩兩不相交。i + i IPETEFTi +TEn ETE E +TE | TFT T *FT | F(E) | i 假定假定S是文法是文法G的開始符號(hào)，對(duì)于的開始符號(hào)，對(duì)于G的任何的任何非終結(jié)符非終結(jié)符A，定義，定義.,.|)(*TVaAaSaAFOLLOWAS*特別是，若特別是，若 ，則規(guī)定，則規(guī)定 FOLLOW(A)FOLLOW定

30、義定義n構(gòu)造不帶回溯的自上而下分析的文法條件構(gòu)造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，文法不含左遞歸，2. 對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若的候選首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對(duì)文法中的每個(gè)非終結(jié)符對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)，若它存在某個(gè)候選首符集包含候選首符集包含 ，則，則FIRST( i)FOLLOW(A)= i=1,2,.,n如果一個(gè)文法如果一個(gè)文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為L(zhǎng)L(1)L

31、L(1)文法文法。 對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自上而下分析。入串進(jìn)行有效的無回溯的自上而下分析。假假設(shè)要用非終結(jié)符設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符進(jìn)行匹配，面臨的輸入符號(hào)為號(hào)為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為A 1 | 2 | | n1. 若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務(wù)；執(zhí)行匹配任務(wù)；2. 若若a不屬于任何一個(gè)候選首符集，則：不屬于任何一個(gè)候選首符集，則： (1) 若若 屬于某個(gè)屬于某個(gè)FIRST( i )且且 a FOLLOW(A)， 則讓則讓A與與 自動(dòng)匹配。自動(dòng)匹配。 (2) 否則

32、，否則，a的出現(xiàn)是一種語法錯(cuò)誤。的出現(xiàn)是一種語法錯(cuò)誤。構(gòu)造構(gòu)造FIRST( ).,|=)(*TVaaaFIRST 對(duì)每一文法符號(hào)對(duì)每一文法符號(hào)X VTVN構(gòu)造構(gòu)造FIRST(X) 連續(xù)使用下面的規(guī)則，直至每個(gè)集合連續(xù)使用下面的規(guī)則，直至每個(gè)集合FIRST不再增大為止：不再增大為止：1. 若若X VT，則，則FIRST(X)X。2. 若若X VN，且有產(chǎn)生式，且有產(chǎn)生式Xa，則把，則把a(bǔ)加入到加入到FIRST(X)中；若中；若X 也是一條產(chǎn)生式，則把也是一條產(chǎn)生式，則把 也加到也加到FIRST(X)中。中。3. l若若XY是一個(gè)產(chǎn)生式且是一個(gè)產(chǎn)生式且Y VN，則把，則把FIRST(Y)中的所有非

33、中的所有非 -元素都加到元素都加到FIRST(X)中；中；l若若XY1Y2Yk是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對(duì)于任何都是非終結(jié)符，而且，對(duì)于任何j，1 j i-1，F(xiàn)IRST(Yj)都含有都含有 (即即Y1Yi-1 )， 則把則把FIRST(Yi)中的所有非中的所有非 -元素都加到元素都加到FIRST(X)中；特別是，若所有的中；特別是，若所有的FIRST(Yj)均含有均含有 ，j1，2，k，則把，則把 加到加到FIRST(X)中。中。 對(duì)文法對(duì)文法G的任何符號(hào)串的任何符號(hào)串 =X1X2Xn構(gòu)造構(gòu)造集合集合FIRST( )。1. 置置FIRST( )FIRST(

34、X1) ；2. 若對(duì)任何若對(duì)任何1 j i-1，F(xiàn)IRST(Xj)，則把，則把FIRST(Xi) 加至加至FIRST( )中；特別是中；特別是，若所有的，若所有的FIRST(Xj)均含有均含有 ，1 j n，則把則把 也加至也加至FIRST( )中。顯然，若中。顯然，若 則則FIRST( ) 。構(gòu)造構(gòu)造FOLLOW(A).,.|)(*TVaAaSaAFOLLOW 對(duì)于文法對(duì)于文法G的每個(gè)非終結(jié)符的每個(gè)非終結(jié)符A構(gòu)造構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的的辦法是，連續(xù)使用下面的規(guī)則，直至每個(gè)規(guī)則，直至每個(gè)FOLLOW不再增大為止不再增大為止：1. 對(duì)于文法的開始符號(hào)對(duì)于文法的開始符號(hào)S，

35、置于，置于FOLLOW(S)中；中；2. 若若A B 是一個(gè)產(chǎn)生式，則把是一個(gè)產(chǎn)生式，則把FIRST( ) 加至加至FOLLOW(B)中；中；3. 若若A B是一個(gè)產(chǎn)生式，或是一個(gè)產(chǎn)生式，或AB 是一個(gè)是一個(gè)產(chǎn)生式而產(chǎn)生式而 (即即FIRST( )， 則把則把FOLLOW(A)加至加至FOLLOW(B)中。中。 例例4.6 對(duì)于文法對(duì)于文法G(E)ETE E +TE | TFT T *FT | F(E) | i構(gòu)造每個(gè)非終結(jié)符的構(gòu)造每個(gè)非終結(jié)符的FIRST和和FOLLOW集合：集合： FIRST(E) =(,iFIRST(E )=+, FIRST(T) =(,iFIRST(T )=*, FIR

36、ST(F) =(,i FOLLOW(E) =),#FOLLOW(E )=),#FOLLOW(T) =+,),#FOLLOW(T )=+,),#FOLLOW(F) =*,+,),#4.4 遞歸下降分析遞歸下降分析程序構(gòu)造程序構(gòu)造 構(gòu)造不帶回溯的自上而下分析程序構(gòu)造不帶回溯的自上而下分析程序 要消除文法的左遞歸性要消除文法的左遞歸性 克服回溯克服回溯 構(gòu)造不帶回溯的自上而下分析器構(gòu)造不帶回溯的自上而下分析器 分析程序由一組遞歸過程組成，文法中每分析程序由一組遞歸過程組成，文法中每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過程；所以這樣的分個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過程；所以這樣的分析程序稱為遞歸下降分析器。析程序稱為遞歸下降分析

37、器。( (因?yàn)槲姆ㄒ驗(yàn)槲姆ǖ亩x通常是遞歸的的定義通常是遞歸的) ) 幾個(gè)全局過程和變量：幾個(gè)全局過程和變量： ADVANCE，把輸入串指示器，把輸入串指示器IP指向下一個(gè)指向下一個(gè)輸入符號(hào)，即讀入一個(gè)單字符號(hào)輸入符號(hào)，即讀入一個(gè)單字符號(hào) SYM，IP當(dāng)前所指的輸入符號(hào)當(dāng)前所指的輸入符號(hào) ERROR，出錯(cuò)處理子程序，出錯(cuò)處理子程序 例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | i 每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需要從某個(gè)非終首先在分析過程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開結(jié)符出發(fā)進(jìn)

38、行展開( (推導(dǎo)推導(dǎo)) )時(shí)，就調(diào)用這時(shí)，就調(diào)用這個(gè)非終結(jié)符對(duì)應(yīng)的子程序。個(gè)非終結(jié)符對(duì)應(yīng)的子程序。 例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | i 對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : PROCEDURE E；BEGIN T；E END；PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E ENDPROCEDURE T；BEGIN F；T ENDPROCEDURE T ；IF SYM=* THENBEGIN ADVANCE； F；T END； 例例: :文法文法G(E):G(E):ETE

39、 E +TE | TFT T *FT | F(E) | i 對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : 例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | i對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : 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

40、# THEN ERROREND; 對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : ETE | BCPROCEDURE E；BEGINIF SYM FIRST(TE)THEN T；E ELSE IF SYM FIRST(BC) THENB; CELSE ERROREND；ETE E +TE | TFT T *FT | F(E) | I對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : PROCEDURE E；BEGIN T；E END；PROCEDURE T；BEGIN F；T ENDETE E +TE | TFT T *FT | F(E) | I對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)?/p>

41、: : PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E END ELSE IF SYM# AND SYM) THEN ERRORETE E +TE | TFT T *FT | F(E) | I對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : PROCEDURE T ； IF SYM=* THEN BEGIN ADVANCE； F；T END ELSE IF SYM# AND SYM) AND SYM+ THEN ERRORETE E +TE | TFT T *FT | F(E) | i對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : PROCED

42、URE 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對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : 主程序主程序:PROGRAM PARSER;BEGIN ADVANCE; EEND; 在元符號(hào)在元符號(hào)“”和和“|”的基礎(chǔ)上，擴(kuò)充的基礎(chǔ)上，擴(kuò)充幾個(gè)元語言符號(hào)：幾個(gè)元語言符號(hào)：1. 用花括號(hào)用花括號(hào) 表示閉包運(yùn)算表示閉包運(yùn)算 *。2. 用表示用表示 0n可

43、任意重復(fù)可任意重復(fù)0次至次至n次，。次，。3. 用方括號(hào)用方括號(hào) 表示表示 01 ，即表示，即表示 的出現(xiàn)可的出現(xiàn)可有可無有可無(等價(jià)于等價(jià)于 | )。 引入上述元符號(hào)的文法亦稱引入上述元符號(hào)的文法亦稱擴(kuò)充的巴科擴(kuò)充的巴科斯范式斯范式。文法的另一種表示法和轉(zhuǎn)換圖文法的另一種表示法和轉(zhuǎn)換圖 例如，通常的例如，通常的“實(shí)數(shù)實(shí)數(shù)”可定義為：可定義為： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign + | - 用擴(kuò)充的巴科斯范式來描述語法，直觀易用擴(kuò)充的巴科斯范式來描述語法，直觀易懂，便于表示左

44、遞歸消去和因子提取。懂，便于表示左遞歸消去和因子提取。 例例4.5 文法文法ET | E+TTF | T*FFi | (E)可表示成可表示成ET+TTF*FFi | (E) (4.6) ET+TTF*FFi | (E) (4.6) 可以用語法圖來表示語言的文法。可以用語法圖來表示語言的文法。T+ETF*TFi)FE( ET+TTF*FFi | (E) (4.6) 可構(gòu)造一組遞歸下降分析程序：可構(gòu)造一組遞歸下降分析程序：PROCEDURE E；BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T ENDEND；PROCEDURE T；BEGIN F； WHILE SY

45、M=* DO BEGIN ADVANCE； F ENDEND； ET+TTF*FFi | (E) (4.6)可構(gòu)造一組遞歸下降分析程序可構(gòu)造一組遞歸下降分析程序： ET+TTF*FFi | (E) (4.6) 可構(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. 對(duì)于文法中每一個(gè)非終結(jié)符對(duì)于文法中每一個(gè)非終結(jié)符

46、A的各個(gè)產(chǎn)生式的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若的候選首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3. 對(duì)文法中的每個(gè)非終結(jié)符對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)，若它存在某個(gè)候選首符集包含候選首符集包含 ，則，則FIRST( i)FOLLOW(A)= i=1,2,.,n如果一個(gè)文法如果一個(gè)文法G滿足以上條件，則稱該文法滿足以上條件，則稱該文法G為為L(zhǎng)L(1)LL(1)文法文法。回顧：回顧：LL(1)文法條件文法條件 分析程序由一組遞歸過程組成，文法中每分析程序由一組遞歸過程組成，文法中每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過程；所以這樣的分個(gè)非終

47、結(jié)符對(duì)應(yīng)一個(gè)過程；所以這樣的分析程序稱為遞歸下降分析器。析程序稱為遞歸下降分析器。( (因?yàn)槲姆ㄒ驗(yàn)槲姆ǖ亩x通常是遞歸的的定義通常是遞歸的) ) 每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，首每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需要從某個(gè)非終結(jié)符先在分析過程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開出發(fā)進(jìn)行展開( (推導(dǎo)推導(dǎo)) )時(shí)，就調(diào)用這個(gè)非終時(shí)，就調(diào)用這個(gè)非終結(jié)符對(duì)應(yīng)的子程序。結(jié)符對(duì)應(yīng)的子程序。回顧：回顧：構(gòu)造不帶回溯的自上而下分構(gòu)造不帶回溯的自上而下分析器析器4.5 預(yù)測(cè)分析程序預(yù)測(cè)分析程序一、預(yù)測(cè)分析程序工作原理一、預(yù)測(cè)分析程序工作原理 預(yù)測(cè)分析程序或預(yù)測(cè)分析程序或LL(1)分析

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

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

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

51、XkTHEN 把把Xk,Xk-1,X1一一推進(jìn)一一推進(jìn)STACK棧棧 /* 若若X1X2Xk= ，不推什么進(jìn)棧，不推什么進(jìn)棧 */ ELSE ERROR END OF WHILE;STOP /*分析成功，過程完畢分析成功，過程完畢*/END分析成功推導(dǎo) 例例4.6 對(duì)于文法對(duì)于文法G(E)ETE E +TE | TFT T *FT | F(E) | i輸入串為輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測(cè)分析：，利用分析表進(jìn)行預(yù)測(cè)分析：i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)步驟步驟符號(hào)棧符號(hào)棧輸入串輸入串所用產(chǎn)生式所用

52、產(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)步驟步驟符號(hào)棧符號(hào)棧輸入串輸入串所用產(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)步

53、驟步驟符號(hào)棧符號(hào)棧輸入串輸入串所用產(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)步驟步驟符號(hào)棧符號(hào)棧輸入串輸入串所用產(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)二、分析表二、分析表MA，a的構(gòu)造的構(gòu)造q構(gòu)造構(gòu)造FIRST( )和和FOLLOW(A)q構(gòu)造分析表構(gòu)造分析表MA，a構(gòu)造構(gòu)造FIRST( ),|=)(*TVaaaFIRST 對(duì)每一文法符號(hào)對(duì)每一文法符號(hào)X VTVN構(gòu)造構(gòu)造FIRST(X) 連續(xù)使用下面的規(guī)則，直至每個(gè)集合連續(xù)使用下面的規(guī)則，直至每個(gè)集合FIRST不再增大為止：不再增大為止：1. 若若X VT，則，則FIRST(X)X。2. 若若