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

編譯原理第四章

語法分析—自上而下分析編輯ppt源程序詞法分析器錯(cuò)誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編輯ppt第四章語法分析—自上而下分析本章主要介紹語法分析的處理要進(jìn)行語法分析，必須對語言的語法結(jié)構(gòu)進(jìn)行描述。采用正規(guī)式和有限自動(dòng)機(jī)可以描述和識別語言的單詞符號；用上下文無關(guān)文法來描述語法規(guī)則。編輯ppt上下文無關(guān)文法的定義：一個(gè)上下文無關(guān)文法G是一個(gè)四元式

G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT

VN=S：文法的開始符號，SVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為A，AVN，(VT

VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。編輯ppt例，定義只含+，*的算術(shù)表達(dá)式的文法

G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列產(chǎn)生式組成：EiEE+EEE*EE(E)編輯ppt如果1

2

n，則我們稱這個(gè)序列是從1到n的一個(gè)推導(dǎo)。若存在一個(gè)從1到n的推導(dǎo)，則稱1可以推導(dǎo)出n

。例：對文法(1)E(E)(E+E)(i+E)(i+i)編輯ppt通常，用

表示：從1出發(fā)，經(jīng)過一步或若干步，可以推出n。

用表示：從1出發(fā)，經(jīng)過0步或若干步，可以推出n。

所以：即或定義：假定G是一個(gè)文法，S是它的開始符號。如果，則稱是一個(gè)句型。僅含終結(jié)符號的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G)。編輯ppt第四章語法分析—自上而下分析語法分析器的功能自上而下分析面臨的問題LL(1)分析法遞歸下降分析程序構(gòu)造預(yù)測分析程序編輯ppt4.1語法分析器的功能語法分析的任務(wù)是分析一個(gè)文法的句子結(jié)構(gòu)。語法分析器的功能：按照文法的產(chǎn)生式(語言的語法規(guī)則)，識別輸入符號串是否為一個(gè)句子。這里所說的輸入串是指由單詞符號（文法的終結(jié)符）組成的有限序列。對一個(gè)文法，當(dāng)給你一串符號時(shí)，怎樣知道它是不是該文法的一個(gè)句子（程序）呢？這就要判斷，看是否能從文法的開始符號出發(fā)推導(dǎo)出這個(gè)輸入串，或建立一棵與輸入串匹配的語法樹。編輯ppt源程序單詞符號取下一單詞...語法分析樹詞法分析器語法分析器符號表編譯程序后續(xù)部分編輯ppt語法分析的方法：自下而上分析法(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ī)范歸約編輯ppt語法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。遞歸下降分析程序：對每一語法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識別一定的語法單位；通過子程序間的相互調(diào)用實(shí)現(xiàn)對輸入串的識別。預(yù)測分析程序優(yōu)點(diǎn)：直觀、簡單和宜于手工實(shí)現(xiàn)。編輯ppt第四章語法分析—自上而下分析語法分析器的功能自上而下分析面臨的問題LL(1)分析法遞歸下降分析程序構(gòu)造預(yù)測分析程序編輯ppt4.2自上而下分析面臨的問題自上而下就是從文法的開始符號出發(fā)，向下推導(dǎo)，推出句子。自上而下分析的主旨：對任何輸入串，試圖用一切可能的辦法，從文法開始符號(根結(jié)點(diǎn))出發(fā)，自上而下地為輸入串建立一棵語法樹?；蛘哒f，為輸入串尋找一個(gè)最左推導(dǎo)。編輯ppt例3.4.1假定有文法G(S):(1)S→xAy(2)A→**|*

分析輸入串x*y(記為)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*編輯ppt（1）當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，在分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)時(shí)，不得不“回溯”。（2）文法左遞歸問題：一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P自上而下分析面臨的問題編輯ppt左遞歸例：下面是描述算術(shù)表達(dá)式的算法

S→EE→E+T|TT→T*F|FF→(E)|id含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。為句子id*id+id構(gòu)造分析樹

S

EE+TE+TE+T：編輯ppt第四章語法分析—自上而下分析語法分析器的功能自上而下分析面臨的問題LL(1)分析法遞歸下降分析程序構(gòu)造預(yù)測分析程序編輯ppt4.3LL(1)分析法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性克服回溯編輯ppt4.3.1左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為

P→P|

其中不以P開頭。我們可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：P→P P→P|左遞歸變右遞歸P→P→P

→…→

…編輯ppt一般而言，假定P關(guān)于的全部產(chǎn)生式是

P→P1|P2|…|Pm

|1|2|…|n其中，每個(gè)都不等于，每個(gè)都不以P開頭那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：

P→1P|2P|…|nP P→1P|2P|…|mP|左遞歸變右遞歸4.3.1左遞歸的消除編輯ppt例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：

E→TEE→+TE|

T→FTT→*FT|F→(E)|i (4.2)P→P1|P2|…|Pm

|1|2|…|nP→1P|2P|…|nPP→1P|2P|…|mP|編輯ppt例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a (4.3)雖沒有直接左遞歸，但S、Q、R都是左遞歸的SQcRbcSabc消除一個(gè)文法的一切左遞歸的條件：（1）不含以為右部的產(chǎn)生式（但改寫后的文法可能含以為右部的產(chǎn)生式）（2）不含回路。編輯ppt消除左遞歸的算法:1.把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，…，Pn；按此順序執(zhí)行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pj的規(guī)則改寫成

Pi→1|2|…|k;(其中Pj→1|2|…|k是關(guān)于Pj的所有規(guī)則)

消除關(guān)于Pi規(guī)則的直接左遞歸性

END3.化簡由2所得的文法。去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。編輯ppt例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镽、Q、S。對于R，不存在直接左遞歸。把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)镼→Sab|ab|b編輯ppt例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镽、Q、S。Q的規(guī)則變?yōu)镼→Sab|ab|b現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S變成S→Sabc|abc|bc|c編輯ppt例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|aS變成S→Sabc|abc|bc|c消除S的直接左遞歸后：

S→abcS|bcS|cS S→abcS| Q→Sab|ab|b R→Sa|a編輯ppt例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a消除S的直接左遞歸后：

S→abcS|bcS|cS S→abcS| Q→Sab|ab|b R→Sa|a關(guān)于Q和R的規(guī)則已是多余的，化簡為：

S→abcS|bcS|cS S→abcS|(4.4)編輯ppt注意，由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價(jià)的。例如，若對文法(4.3)的非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是：

S→Qc|c Q→Rb|b R→bcaR|caR|aR(4.5) R→bcaR|

文法(4.4)和(4.5)的等價(jià)性是顯然的。編輯ppt小結(jié)自上而下分析面臨的問題

文法的左遞歸性

回溯消除文法的左遞歸

直接左遞歸的消除

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

特別是，若，則規(guī)定FIRST()。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選

i和

jFIRST(i)∩FIRST(j)＝當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的。編輯ppt思考：

FIRST(i)∩FIRST(j)＝很好處理，但是如果的終結(jié)首符集有共同的部分怎么辦？？？？A→1|2|…|n可提取其公共左因子編輯ppt提取公共左因子:

假定關(guān)于A的規(guī)則是

A→1|2|…|n|1|2|…|m (其中，每個(gè)

不以開頭)

那么，可以把這些規(guī)則改寫成A→A

|1|2|…|mA→1|2|…|n經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。編輯pptE→TEE→+TE|T→FTT→*FT|F→(E)|ii+i4.3.3LL(1)分析條件當(dāng)一個(gè)文法不含左遞歸，并且滿足每個(gè)非終結(jié)符的所有候選首符集兩兩不相交的條件，是不是就一定能進(jìn)行有效的自上而下分析了呢？編輯ppti+iIPEG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’FT’G(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppti+iIPETE’FT’i+TE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|i編輯ppt思考：當(dāng)非終結(jié)符A面臨輸入符號a，且a不屬于A的任意候選首符集，但A的某個(gè)候選首符集包含時(shí)，是否就一定可以使A自動(dòng)匹配（A→）呢？需要做判斷：有當(dāng)a是允許在文法的某個(gè)句型中跟在A后面的終結(jié)符時(shí)，才可能允許A自動(dòng)匹配，否則，a在這里的出現(xiàn)就是一個(gè)語法錯(cuò)誤。編輯ppti+iIPETE’FT’i+TE’FT’iG(E):E→TEE→+TE|T→FTT→*FT|F→(E)|iS…T’+…能否用A→自動(dòng)匹配，需要判斷當(dāng)前輸入符號是否在緊跟在A后面的終結(jié)符集FOLLOW(A)中。編輯ppt假定S是文法G的開始符號，對于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定＃FOLLOW(A)4.3.3LL(1)分析條件編輯ppt構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸，2.對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A→1|2|…|n

則FIRST(i)∩FIRST(j)＝

(ij)3.對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，則FIRST(i)∩FOLLOW(A)=i=1,2,...,n如果一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法。 第一個(gè)L：從左到右掃描輸入串第二個(gè)L：最左推導(dǎo)1：分析時(shí)每一步只需向前查看一個(gè)符號編輯ppt對于一個(gè)滿足上述條件的文法，可以對其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生式為A→1|2|…|n1.若aFIRST(i)，則指派

i執(zhí)行匹配任務(wù)；2.若a不屬于任何一個(gè)候選首符集，則：

(1)若屬于某個(gè)FIRST(i)且aFOLLOW(A)，則讓A與自動(dòng)匹配。

(2)否則，a的出現(xiàn)是一種語法錯(cuò)誤。編輯ppt求FIRST(X)的算法如下：p80①若XVT，則FIRST(X)＝{X}。②若XVN，且有產(chǎn)生式X→a…，aVT則把a(bǔ)加入到FIRST(X)中；③若XVN，X→，則FIRST(X)中。對每個(gè)文法符號XVT∪VN，連續(xù)使用下面的規(guī)則，直至每個(gè)FIRST(X)不再增大為止：編輯pptb)當(dāng)Y1，Y2，……，Yi-1都=>ε,(1in)

,則FIRST(

Y1)-{ε},FIRST(

Y2)-{ε},……,FIRST(

Yi)-{ε}

都包含在FIRST（X）中c)

當(dāng)Y1，Y2，……，Yk都=>ε,則ε∈FIRST(X)，此時(shí)FIRST(X)=FIRST(

Y1)∪FIRST(

Y2)∪……

∪FIRST(

Yk)∪{ε}④若X，Y1，Y2，……，YkVN，且有產(chǎn)生式

X→Y1Y2……Yk：a)當(dāng)Y1不能=>ε

，則FIRST(Y1)中的所有符號都在FIRST（X）中編輯ppt對每個(gè)非終結(jié)符A，連續(xù)使用下面的規(guī)則，直至每個(gè)FOLLOW(A)不再增大為止：①對于文法的開始符號S，置＃于FOLLOW(S)中；②對于A→B的產(chǎn)生式，則把FIRST()-{}加至FOLLOW(B)中；③對于A→B或AB，其中，則把FOLLOW(A)加至FOLLOW(B)中。求FOLLOW(A)的算法如下：p82

注意：永遠(yuǎn)不進(jìn)follow集！??！編輯ppt例4.6對于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 構(gòu)造每個(gè)非終結(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)={*,+,),#}編輯ppt4.4遞歸下降分析程序構(gòu)造構(gòu)造不帶回溯的自上而下分析程序要消除文法的左遞歸性克服回溯編輯ppt主要思路：

分析程序由一組遞歸過程組成，對文法的每一個(gè)非終結(jié)符（語法變量）構(gòu)造一個(gè)相應(yīng)的子程序，識別對應(yīng)的語法單位；

通過子程序間的相互調(diào)用實(shí)現(xiàn)對輸入串的識別；

這樣的分析程序稱為遞歸下降分析器。(因?yàn)槲姆ǖ亩x通常是遞歸的)遞歸下降分析程序構(gòu)造幾個(gè)全局過程和變量：ADVANCE，把輸入串指示器IP指向下一個(gè)輸入符號，即讀入一個(gè)單字符號SYM，IP當(dāng)前所指的輸入符號ERROR，出錯(cuò)處理子程序編輯ppt

注意：

每個(gè)非終結(jié)符有對應(yīng)的子程序的定義在分析過程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行語法樹展開(推導(dǎo))時(shí)，就調(diào)用這個(gè)非終結(jié)符對應(yīng)的子程序。子程序的名字可與對應(yīng)的非終結(jié)符的名字相同例：A→TE

|BC|

編輯ppt遞歸下降子程序A→TE

|BC|

對應(yīng)的遞歸下降子程序?yàn)椋篜ROCEDUREA；BEGIN IFSYMFIRST(TE’) THENBEGINT；EEND；//先調(diào)用T子程序,再調(diào)用E’ELSEIFSYMFIRST(BC) THENBEGINB；CEND；//先調(diào)用B子程序,再調(diào)用CELSEIFSYMFOLLOW(A)THENBEGINEND；ELSEERRORENDELSEIFSYM/FOLLOW(A)THENERROR編輯ppt例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREF；

IFSYM=‘i’THENADVANCE

ELSE IFSYM=‘(’THEN BEGIN ADVANCE; E；

IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;編輯ppt例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE；BEGIN T；EEND；

PROCEDUREE；

IFSYM=‘+’THEN BEGIN

ADVANCE；

T；E

ENDPROCEDUREE；

IFSYM=‘+’THEN BEGIN

ADVANCE；

T；E

ENDELSEIFSYM<>’#’ANDSYM<>’)’THENERROR//

FOLLOW(E)={),#}編輯pptPROCEDURET；BEGIN F；TENDPROCEDURET；IFSYM=‘*’THENBEGINADVANCE；

F；TEND；例:文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應(yīng)的遞歸下降子程序?yàn)?

編輯ppt主程序:PROGRAMPARSER;BEGINADVANCE;E;IFSYM<>’#’THENERROREND;編輯ppt在元符號“→”和“|”的基礎(chǔ)上，擴(kuò)充幾個(gè)元語言符號：1.用花括號{}表示閉包運(yùn)算*。2.用表示{}0n可任意重復(fù)0次至n次。3.用方括號[]表示{}01

，即表示的出現(xiàn)可有可無(等價(jià)于|)。引入上述元符號的文法亦稱擴(kuò)充的巴科斯范式。文法的另一種表示法和轉(zhuǎn)換圖編輯ppt例如，通常的“實(shí)數(shù)”可定義為：

decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+|-用擴(kuò)充的巴科斯范式來描述語法，直觀易懂，便于表示左遞歸消去和因子提取。編輯ppt例4.5文法E→T|E+TT→F|T*FF→i|(E)可表示成E→T{+T}T→F{*F}F→i|(E) (4.6)編輯pptE→T{+T}T→F{*F}F→i|(E) (4.6)可以用語法圖來表示語言的文法。T+ETF*TFi)FE(編輯pptE→T{+T}T→F{*F}F→i|(E) (4.6)可構(gòu)造一組遞歸下降分析程序：PROCEDUREE；BEGINT；

WHILESYM=‘+’DOBEGINADVANCE；

TENDEND；編輯pptPROCEDURET；BEGINF；

WHILESYM=‘*’DOBEGINADVANCE；

FENDEND；E→T{+T}T→F{*F}F→i|(E) (4.6)可構(gòu)造一組遞歸下降分析程序：編輯pptE→T{+T}T→F{*F}F→i|(E) (4.6)可構(gòu)造一組遞歸下降分析程序：PROCEDUREF；

IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E；

IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;編輯ppt1.文法不含左遞歸，2.對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A→1|2|…|n

則FIRST(i)∩FIRST(j)＝

(ij)3.對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，則FIRST(i)∩FOLLOW(A)=i=1,2,...,n如果一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法。 回顧：LL(1)文法條件編輯pptLL(1)分析法——假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號為a，A的所有產(chǎn)生式為：

A→1|2|…|n

1.若a∈FIRST（i），則指派i執(zhí)行匹配任務(wù)；2.若a不屬于任何一個(gè)候選首符集，則：（1）若屬于某個(gè)FIRST（i）且a∈FOLLOW(A),則讓A與自動(dòng)匹配。（2）否則，a的出現(xiàn)是一種語法錯(cuò)誤?；仡櫍篖L(1)分析法編輯ppt分析程序由一組遞歸過程組成，文法中每個(gè)非終結(jié)符對應(yīng)一個(gè)過程；所以這樣的分析程序稱為遞歸下降分析器。(因?yàn)槲姆ǖ亩x通常是遞歸的)每個(gè)非終結(jié)符有對應(yīng)的子程序的定義，首先在分析過程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開(推導(dǎo))時(shí)，就調(diào)用這個(gè)非終結(jié)符對應(yīng)的子程序?；仡櫍簶?gòu)造不帶回溯的自上而下分析器編輯ppt特征——

根據(jù)當(dāng)前輸入符號，為當(dāng)前要處理的非終結(jié)符選擇產(chǎn)生式要求——文法是LL(1)的4.5

預(yù)測分析程序編輯ppt預(yù)測分析器模型總控程序X#輸入串分析棧STACKa1a2...ai…#輸出預(yù)測分析表M編輯ppt預(yù)測分析器模型總控程序X#輸入串分析棧STACKa1a2...ai…#輸出預(yù)測分析表M分析棧STACK用于存放文法符號。分析開始時(shí)，棧底先放一個(gè)‘#’，然后放進(jìn)文法開始符號。#Sa1a2...ai…#編輯ppt預(yù)測分析器模型總控程序X#輸入串分析棧STACKa1a2...ai…#輸出預(yù)測分析表M預(yù)測分析表是一個(gè)M[A，a]形式的矩陣，AVN

，aVT是終結(jié)符或‘?！?；矩陣元素M[A，a]中存放著一條關(guān)于A的產(chǎn)生式，指出當(dāng)A面臨輸入符號a時(shí)所采用的候選。M[A，a]中也可能存放一個(gè)“出錯(cuò)標(biāo)志”，指出A根本不該面臨輸入符號a。編輯ppt某文法的LL(1)預(yù)測分析表編輯ppt預(yù)測分析器模型總控程序X#輸入串分析棧STACKa1a2...ai…#輸出預(yù)測分析表M總控程序在任何時(shí)候都是按STACK棧頂符號X和當(dāng)前的輸入符號a行事；它總是執(zhí)行下述三種可能的動(dòng)作之一：編輯ppt1.若X＝a＝‘?！瑒t宣布分析成功，停止分析。2.若X＝a‘?！?，則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號。匹配成功總控程序根據(jù)現(xiàn)行棧頂符號X和當(dāng)前輸入符號a，執(zhí)行下列三種動(dòng)作之一:編輯ppt3.若X是一個(gè)非終結(jié)符，則查看分析表M。若M[X，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號串按反序一一推進(jìn)STACK棧(若右部符號為，則意味不推什么東西進(jìn)棧)。在把產(chǎn)生式的右部符號推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語義動(dòng)作（目前暫且不管）。若M[X，a]中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序ERROR。推導(dǎo)編輯ppt預(yù)測分析程序的總控程序：BEGIN

首先把‘?！缓蟀盐姆ㄩ_始符號推進(jìn)STACK棧；把第一個(gè)輸入符號讀進(jìn)a；

FLAG:=TRUE;WHILEFLAGDO BEGIN

把STACK棧頂符號上托出去并放在X中；

IFXVTTHEN IFX=aTHEN把下一輸入符號讀進(jìn)a ELSEERROR

匹配成功編輯pptELSEIFX=‘#’THEN IFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…Xk}THEN

把Xk,Xk-1,…,X1一一推進(jìn)STACK棧

/*若X1X2…Xk=，不推什么進(jìn)棧*/ELSEERRORENDOFWHILE;STOP/*分析成功，過程完畢*/END分析成功推導(dǎo)編輯ppt例4.6對于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 輸入串為i1*i2+i3，利用分析表進(jìn)行預(yù)測分析：編輯ppt步驟

符號棧

輸入串

所用產(chǎn)生式0 #E i1*i2+i3#1 #ET i1*i2+i3# E→TE2 #ETF i1*i2+i3# T→FT3 #ETi i1*i2+i3# F→i編輯ppt步驟

符號棧

輸入串

所用產(chǎn)生式3 #ETi i1*i2+i3# F→i4 #ET *i2+i3#5 #ETF* *i2+i3# T→*FT6 #ETFi2+i3#7 #ETi i2+i3#F→i編輯ppt步驟

符號棧

輸入串

所用產(chǎn)生7 #ETi i2+i3#F→i8 #ET +i3#9 #E +i3# T→10 #ET+ +i3# E→+TE11 #ET i3#編輯ppt步驟

符號棧

輸入串

所用產(chǎn)生11 #ET i3#12 #ETF i3# T→FT13 #ETi i3# F→i14 #ET #15 #E # T→16 # # E→編輯ppt預(yù)測分析表M[A，a]的構(gòu)造構(gòu)造與文法G有關(guān)的集合FIRST和FOLLOW構(gòu)造分析表M[A，a]編輯ppt求FIRST(X)的算法如下：p80①若XVT，則FIRST(X)＝{X}。②若XVN，且有產(chǎn)生式X→a…，aVT則把a(bǔ)加入到FIRST(X)中；③若XVN，X→，則FIRST(X)中。對每個(gè)文法符號XVT∪VN，連續(xù)使用下面的規(guī)則，直至每個(gè)FIRST(X)不再增大為止：編輯pptb)當(dāng)Y1，Y2，……，Yi-1都=>ε,(1in)

,則FIRST(

Y1)-{ε},FIRST(

Y2)-{ε},……,FIRST(

Yi)-{ε}

都包含在FIRST（X）中c)

當(dāng)Y1，Y2，……，Yk都=>ε,則ε∈FIRST(X)，此時(shí)FIRST(X)=FIRST(

Y1)∪FIRST(

Y2)∪……

∪FIRST(

Yk)∪{ε}④若X，Y1，Y2，……，YkVN，且有產(chǎn)生式

X→Y1Y2……Yk：a)當(dāng)Y1不能=>ε

，則FIRST(Y1)中的所有符號都在FIRST（X）中編輯ppt對每個(gè)非終結(jié)符A，連續(xù)使用下面的規(guī)則，直至每個(gè)FOLLOW(A)不再增大為止：①對于文法的開始符號S，置＃于FOLLOW(S)中；②對于A→B的產(chǎn)生式，則把FIRST()-{}加至FOLLOW(B)中；③對于A→B或AB，其中，則把FOLLOW(A)加至FOLLOW(B)中。求FOLLOW(A)的算法如下：p82

注意：永遠(yuǎn)不進(jìn)