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

1、整理課件編譯原理第四章第四章 語(yǔ)法分析語(yǔ)法分析自上而下分析自上而下分析整理課件整理課件整理課件整理課件第四章第四章 語(yǔ)法分析語(yǔ)法分析自上而下分析自上而下分析n本章主要介紹本章主要介紹語(yǔ)法分析語(yǔ)法分析的處理的處理n要進(jìn)行語(yǔ)法分析，必須對(duì)語(yǔ)言的要進(jìn)行語(yǔ)法分析，必須對(duì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)語(yǔ)法結(jié)構(gòu)進(jìn)行描述。進(jìn)行描述。采用采用正規(guī)式和有限自動(dòng)機(jī)正規(guī)式和有限自動(dòng)機(jī)可以描述和識(shí)別語(yǔ)言可以描述和識(shí)別語(yǔ)言的的單詞符號(hào)單詞符號(hào)；用用上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法來(lái)描述來(lái)描述語(yǔ)法規(guī)則語(yǔ)法規(guī)則。整理課件整理課件n上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法的定義：的定義： 一個(gè)上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)文法G G是一個(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：文法的：文法的開始符號(hào)開始符號(hào)，S S V VN NP P：產(chǎn)生式產(chǎn)生式集合集合( (有限有限) )，每個(gè)產(chǎn)生式形式為每個(gè)產(chǎn)生式形式為A A， A A V VN N， ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。至少必須在某個(gè)產(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，則我們稱這個(gè)序，則我們稱這個(gè)序列是從列是從 1到到 n的一個(gè)的一個(gè)推導(dǎo)推導(dǎo)。若存在一個(gè)從。若存在一個(gè)從 1到到 n的推導(dǎo)，則稱的推導(dǎo)，則稱 1可以可以推導(dǎo)推導(dǎo)出出 n 。n例：對(duì)文法例：對(duì)文法(1)E (E) (E+E) (i+E) (i+i)整理課件整理課件n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)一步或若干步一步或若干步，可以推出，可以推出 n n。n1n*1 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)0 0步或步

4、或若干步若干步，可以推出，可以推出 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è)語(yǔ)言語(yǔ)言，將它記為，將它記為 L(G)L(G)。*S整理課件整理課件第四章第四章 語(yǔ)法分析語(yǔ)法分析自上而下分析自上而下分析n語(yǔ)法分析器的功能語(yǔ)法分析器的功能n自上而下分析面臨的問(wèn)題自上而下分析面臨的問(wèn)題nLL(1)LL(1)分析法分析法n遞歸下

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

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

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

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

9、從文法的開始符號(hào)出發(fā)，向下下推導(dǎo)推導(dǎo)，推出句子。，推出句子。p對(duì)任何輸入串，試圖用一切可能的辦法，對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)從文法開始符號(hào)(根結(jié)點(diǎn)根結(jié)點(diǎn))出發(fā)，自上而下地出發(fā)，自上而下地為輸入串建立一棵為輸入串建立一棵語(yǔ)法樹語(yǔ)法樹。p或者說(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(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)某個(gè)非終結(jié)符有）當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選多個(gè)產(chǎn)生式候選時(shí)，時(shí)，在在分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)。出錯(cuò)時(shí)時(shí)，不得不不得不“回溯回溯”。（2 2）文法左遞歸問(wèn)題：文法左遞歸問(wèn)題：一個(gè)文法是含有左遞歸一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符的，如果存在非終結(jié)符P PPP自上而下分析面臨的問(wèn)題自上而下分析面臨的問(wèn)題整理課件整理課件左遞歸左遞歸例：下面是描述算術(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 含有左遞歸的文法將使自上而下的分含有左遞歸的文法將使自上而下的分析陷入無(wú)限循環(huán)析陷入無(wú)限循環(huán)。為句子為句子idid* *id+idid+id構(gòu)造分析樹構(gòu)造分析樹 S S E E E + T E + T E + T E + TE + TE + T：整理課件整理課件第四章第四章 語(yǔ)法分析語(yǔ)法分析自上而下分析自上而下分析n語(yǔ)法分析器的功能語(yǔ)法分析器的功能n自上而下分析面臨的問(wèn)題自上而下分析面臨的問(wèn)題nLL(1)LL(1)分析法分析法n遞歸下降分析程序構(gòu)造遞歸下降分析程序構(gòu)造n預(yù)測(cè)分析程序預(yù)測(cè)分析程序整理課件整理課件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ī)則等價(jià)地改寫為如下的的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：非直接左遞歸形式：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其中，每個(gè)其中，每個(gè) 都不等于都不等于 ，每個(gè)，每個(gè) 都不以都不以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消除一個(gè)文法的一切左遞歸的條件：消除一個(gè)文法的一切左遞歸的條件：（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. 化簡(jiǎn)由化簡(jiǎn)由2所得的文法。去除那些從開始符號(hào)出發(fā)永所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。遠(yuǎn)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。整理課件整理課件n例例 考慮文法考慮文法G(S)SQc|cQRb|bRSa|an令它的非終結(jié)符的排序?yàn)榱?/p>

16、它的非終結(jié)符的排序?yàn)镽、Q、S。n對(duì)于對(duì)于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é)符的排序?yàn)榱钏姆墙K結(jié)符的排序?yàn)镽、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ī)則已是多余的，化簡(jiǎn)為：的規(guī)則已是多余的，化簡(jiǎn)為：SabcS | bcS | cS S abcS | (4.4)整理課件整理課件n注意，由于對(duì)非終結(jié)符排序的不同，最注意，由于對(duì)非終結(jié)符排序

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

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

20、有非終結(jié)符的每個(gè)候選 定義它的終結(jié)首定義它的終結(jié)首符集符集FIRST( )為：為：.,|=)(*TVaaaFIRST 特別是，若特別是，若 ，則規(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的的 。整

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 (其中，每個(gè)其中，每個(gè) 不以不以 開頭開頭) 那么，可以把這些規(guī)則改寫成那么，可以把這些規(guī)則改寫成A A | 1 | 2 | | mA 1 | 2 | | nn經(jīng)過(guò)反復(fù)提取左因子，就能夠把每個(gè)非終經(jīng)過(guò)反復(fù)提取左因子，就能

22、夠把每個(gè)非終結(jié)符結(jié)符(包括新引進(jìn)者包括新引進(jìn)者)的所有候選首符集變的所有候選首符集變成為兩兩不相交。成為兩兩不相交。整理課件整理課件n ETE E +TE | TFT T *FT | F(E) | in i + i4.3.3 LL(1)分析條件分析條件n當(dāng)一個(gè)文法當(dāng)一個(gè)文法不含左不含左遞歸遞歸，并且滿足每，并且滿足每個(gè)非終結(jié)符的所有個(gè)非終結(jié)符的所有候選首符集兩兩不候選首符集兩兩不相交相交的條件，是不的條件，是不是就一定能進(jìn)行有是就一定能進(jìn)行有效的自上而下分析效的自上而下分析了呢？了呢？整理課件整理課件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面臨輸入符號(hào)面臨輸入符號(hào)a，且，且a不屬于不屬于A的任意候選的任意候選首符集，首符集，但但A的某個(gè)候選首符集包含的某個(gè)候選首符集包含 時(shí)，是否就一定可以使時(shí)，是否就一定可以使A自動(dòng)匹配（自動(dòng)匹配（ A

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

27、假定假定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)生式的候選首符集兩兩不相交。即，若的候選首符集兩兩不相交。即，若A 1| 2| n 則則 FIRST( i)FIRST( j) (i j)3.

28、對(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)文法文法。第一個(gè)第一個(gè)L：從左到右掃描輸入串：從左到右掃描輸入串第二個(gè)第二個(gè)L：最左推導(dǎo)：最左推導(dǎo)1：分析時(shí)每一步只需向前查看一個(gè)符號(hào)：分析時(shí)每一步只需向前查看一個(gè)符號(hào)整理課件整理課件n對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無(wú)回溯的自上而下分析。假入串進(jìn)行有效的無(wú)回溯的自上而下

29、分析。假設(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) 否則，否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。整理課件整理課件求求FIRST(X)的算法如下：的算法如下：p80若若X VT，則，則FIRST(X)X。若若X

30、 VN，且有產(chǎn)生式，且有產(chǎn)生式Xa， a VT則把則把a(bǔ)加入到加入到FIRST(X)中；中；若若X VN ，X ，則，則 FIRST(X)中。中。對(duì)每個(gè)文法符號(hào)對(duì)每個(gè)文法符號(hào)X VT VN ，連續(xù)使用下連續(xù)使用下面的規(guī)則，直至每個(gè)面的規(guī)則，直至每個(gè)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)，此時(shí)，此時(shí)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 )中的所有符號(hào)中的所有符號(hào)都在都在FIRST（X）中）中整理課件整理課件n對(duì)每個(gè)非終結(jié)符對(duì)每個(gè)非終結(jié)符A，連續(xù)使用下面的規(guī)則，連續(xù)使用下面的規(guī)則，直至每個(gè)直至每個(gè)FOLLOW(A)不再增大為止：不再增大為止： 對(duì)于文法的開始符號(hào)對(duì)于文法的開始符號(hào)S，置，置于于FOLLOW(S)中；中； 對(duì)于對(duì)于A B 的的產(chǎn)生式，則把產(chǎn)生式，則把FIRST( )

32、- 加至加至FOLLOW(B)中；中；對(duì)于對(duì)于A B或或A B ，其中，其中 ， 則把則把FOLLOW(A)加至加至FOLLOW(B)中。中。求求FOLLOW(A)的算法如下：的算法如下：p82 注意：注意： 永遠(yuǎn)不進(jìn)永遠(yuǎn)不進(jìn)follow集！集！.,.|)(*TVaAaSaAFOLLOW整理課件整理課件n例例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 )=*, 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主要思路：主要思路： 分析程序由一組遞歸過(guò)程組成，對(duì)文法的每一分析程序由一組遞歸過(guò)程組成，對(duì)文法的每一個(gè)個(gè)非終結(jié)符非終結(jié)符（語(yǔ)法變量）構(gòu)造一個(gè)（語(yǔ)法變量）構(gòu)造一個(gè)相應(yīng)的子程相應(yīng)的子程序，序，識(shí)別對(duì)應(yīng)的語(yǔ)法單位；識(shí)別對(duì)應(yīng)的語(yǔ)法單位；

34、 ； 這樣的分析程序稱為這樣的分析程序稱為遞歸下降分析器遞歸下降分析器。( (因?yàn)槲囊驗(yàn)槲姆ǖ亩x通常是遞歸的法的定義通常是遞歸的) )n幾個(gè)全局過(guò)程和變量：幾個(gè)全局過(guò)程和變量：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ò)處理子程序整理課件整理課件注意：注意：n每個(gè)每個(gè)非終結(jié)符非終結(jié)符有有對(duì)應(yīng)的子程序?qū)?yīng)的子程序的定義的定義n在分析過(guò)程中，當(dāng)在分析過(guò)程中，當(dāng)需要從某個(gè)非終結(jié)符需要從某個(gè)非終結(jié)符出發(fā)出發(fā)進(jìn)行語(yǔ)法樹展開進(jìn)行語(yǔ)法樹展開( (

35、推導(dǎo)推導(dǎo)) )時(shí)時(shí)，就調(diào)用，就調(diào)用這個(gè)非終結(jié)符這個(gè)非終結(jié)符對(duì)應(yīng)的子程序?qū)?yīng)的子程序。n子程序的名字可與對(duì)應(yīng)的非終結(jié)符的名子程序的名字可與對(duì)應(yīng)的非終結(jié)符的名字相同字相同n例：例：ATE | BC| 整理課件整理課件ATE | BC| 對(duì)應(yīng)的遞歸下降子程序?yàn)椋簩?duì)應(yīng)的遞歸下降子程序?yàn)椋篜ROCEDURE 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對(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;整理課件整理課件n例例: :文法文法G(E):G(E):ET

37、E E +TE | TFT T *FT | F(E) | in對(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 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對(duì)應(yīng)的遞歸下降子程序?yàn)閷?duì)應(yīng)的遞歸下降子程序?yàn)? : 整理課件整理課件主程序主程序:PROGRAM PARSER;BEGIN ADVANCE; E; IF SYM # THEN ERROREND;整理課件整理課件n在元符號(hào)在元符號(hào)“”和和“|”的基礎(chǔ)上，擴(kuò)充幾的基礎(chǔ)上，擴(kuò)充幾個(gè)元語(yǔ)言符號(hào)：個(gè)元語(yǔ)言符號(hào)：1. 用用花括號(hào)花括號(hào) 表示表示閉包運(yùn)算閉包運(yùn)算 *。2. 用表示用表示 0n可任意可任意重復(fù)重復(fù)0次至次至n次次。3. 用用方括號(hào)方括號(hào) 表示表示 01 ，即表示，

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

40、.5 文法文法ET | E+TTF | T*FFi | (E)可表示成可表示成ET+TTF*FFi | (E) (4.6)整理課件整理課件n ET+TTF*FFi | (E) (4.6)n可以用語(yǔ)法圖來(lái)表示語(yǔ)言的文法?？梢杂谜Z(yǔ)法圖來(lái)表示語(yǔ)言的文法。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. 對(duì)于文法中每一個(gè)非

42、終結(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)LL(1)文法文法。回顧：回顧：LL(1)文法條件文法條件整理課件整理課件nLL(1)分析法分析法假設(shè)要用非終結(jié)符假設(shè)要用非終結(jié)符A進(jìn)行匹配，進(jìn)

43、行匹配，面臨的輸入符號(hào)為面臨的輸入符號(hào)為a，A的所有產(chǎn)生式為的所有產(chǎn)生式為 ： A 1 | 2 | | n 1.若若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)是一種語(yǔ)法錯(cuò)誤。的出現(xiàn)是一種語(yǔ)法錯(cuò)誤?；仡櫍夯仡櫍篖L(1)分析法分析法整理課件整理課件n分析程序由一組遞歸過(guò)程組成，文法中每分析程序由一組遞歸過(guò)程組成，文法中每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過(guò)程；所以這樣的分個(gè)

44、非終結(jié)符對(duì)應(yīng)一個(gè)過(guò)程；所以這樣的分析程序稱為析程序稱為遞歸下降分析器遞歸下降分析器。( (因?yàn)槲姆ㄒ驗(yàn)槲姆ǖ亩x通常是遞歸的的定義通常是遞歸的) )n每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，首每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，首先在分析過(guò)程中，當(dāng)需要從某個(gè)非終結(jié)符先在分析過(guò)程中，當(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)造不帶回溯的自上而下分析器析器整理課件整理課件特征特征 根據(jù)根據(jù)當(dāng)前當(dāng)前輸入符號(hào)輸入符號(hào)，為當(dāng)前要處，為當(dāng)前要處 理的非終結(jié)符理的非終結(jié)符選擇產(chǎn)生式選擇

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

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

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

48、之一:整理課件整理課件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)的語(yǔ)義棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作（目前暫且不管）。動(dòng)作（目前暫且不管）。 若若MX，a中存放著中存放著“出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志”，則，則調(diào)用出錯(cuò)診察程序調(diào)用出錯(cuò)

49、診察程序ERROR。推導(dǎo)整理課件整理課件n預(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

50、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 /*分析成功，過(guò)程完畢分析成功，過(guò)程完畢*/END分析成功推導(dǎo)整理課件整理課件n例例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

51、(E)整理課件整理課件步驟步驟符號(hào)棧符號(hào)棧輸入串輸入串所用產(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)整理課件整理課件步驟步驟符號(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

52、E +TE E E TTFT TFT T T T *FT T T FFiF (E)整理課件整理課件步驟步驟符號(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

53、 ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)整理課件整理課件預(yù)測(cè)分析表預(yù)測(cè)分析表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(bǔ)加入到加入到FIRST(X)中；中；若若X VN ，X ，則，則 FIRST(X)中。中。對(duì)每個(gè)文法符號(hào)對(duì)每個(gè)文法符號(hào)X VT VN ，連續(xù)使用下連續(xù)使用下面的規(guī)則，直至每個(gè)面的規(guī)

54、則，直至每個(gè)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)，此時(shí)，此時(shí)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 )中的所有符號(hào)中的所有符號(hào)都在都在FIRST（X）中）中整理課件整理課件n對(duì)每個(gè)非終結(jié)符對(duì)每個(gè)非終結(jié)符A，連續(xù)使用下面的規(guī)則，連續(xù)使用下面的規(guī)則，直至每個(gè)直至每個(gè)FOLLOW(A)不再增大為止：不再增大為止： 對(duì)于文法的開始符號(hào)對(duì)于文法的開始符號(hào)S，置，置于于FOLLOW(S)中；中； 對(duì)于對(duì)于A B 的的產(chǎn)生式，則把產(chǎn)生式，則把FIRST( )-