自頂向下的語法分析

1第五章自頂向下語法分析方法2語法分析語法分析（Ch3:句子分析）是編譯程序的核心部分。其作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子（程序）。語法分析方法自頂向下分析自底向上分析3自頂向下分析——面向目標的分析方法確定的自頂向下分析方法需對文法有一定的限制，但由于實現(xiàn)方法簡單、直觀，便于手工構造或自動生成語法分析器，是最常用的方法之一。不確定的自頂向下分析方法是帶回溯的分析方法，實際是一種窮舉的試探方法，效率低，代價高，使用較少。自頂向下的語法分析4自頂向下的語法分析5.1確定的自頂向下分析思想5.2不確定的自頂向下分析5.3非LL(1)文法的等價變換5.4LL(1)文法的判別5.5確定的自頂向下分析方法5確定的自定向下分析方法，是從文法的開始符號出發(fā)，考慮如何根據(jù)當前的輸入符號（單詞符號）惟一的確定選用哪個產(chǎn)生式替換相應非終結符向下推導，或如何構造一棵相應的語法樹。什么樣的文法能夠進行確定的自頂向下語法分析？5.1確定的自頂向下分析思想6文法G1[S]：S→pA|qBA→cAd|aB→dB|c識別輸入串w=pccadd#是否是G1[S]的句子例1自頂向下的推導過程為：S

pApcAdpccAddpccadd##7文法特點：每個產(chǎn)生式右部都由終結符號開始如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結符開始文法在推導過程中完全可以根據(jù)當前的輸入符號決定選擇哪個產(chǎn)生式往下推導，分析過程唯一確定。S→pA|qBA→cAd|aB→dB|c8文法G2[S]：S→Ap|Bq

A→cA|aB→dB|b識別輸入串w=ccap#是否是G2[S]的句子

例2推導過程：S#Ap#

cAp#

ccAp#

ccap#9S→Ap|Bq

A→cA|a

B→dB|b文法特點：產(chǎn)生式的右部不全是由終結符開始如果兩個產(chǎn)生式有相同的左部，它們的右部由不同的終結符或非終結符開始文法中無空產(chǎn)生式對于產(chǎn)生式中相同左部含有非終結符開始的產(chǎn)生式時，可通過考察產(chǎn)生式向下推導時能夠推導出的第一個終結符唯一確定該用哪個產(chǎn)生式進行替換。具有相同左部的產(chǎn)生式向下推導時能夠推導出不同的終結符10FIRST集的定義設G=(VT，VN，P，S)是上下文無關文FIRST()={a|=>a，a∈VT，，∈V*}若=>ε則規(guī)定ε∈FRIST()

稱FRIST()為的開始符號集或首符號集。在文法G2中：S->ApA->cA|aFRIST(Ap)={a，c}S->BqB->dB|bFRIST(Bq)={b，d}

使得面向非終結符S為某一輸入符號x尋求匹配時,可由x與兩集合的歸屬關系確定選用哪個產(chǎn)生式進行推導。（文法1同）**交集為空無空產(chǎn)生式11例3（含空產(chǎn)生式的文法）文法G[S]：S→aA|dA→bAS|ε識別輸入串w=abd#

是否是G[S]的句子當某一非終結符的產(chǎn)生式中含有空產(chǎn)生式時，它的非空產(chǎn)生式右部的首符號集兩兩不相交，并與在推導過程緊跟該非終結符右邊可能出現(xiàn)的終結符集也不相交，則仍可構造確定的自頂向下分析。A->bAS|b|εA->bAS|d|ε推導過程：SaA

abASabS

abd12FOLLOW集的定義設G=(VT，VN，P，S)是上下文無關文法，A∈VN，S是開始符號FOLLOW(A)={aS=>A,a∈VT，a∈FRIST()，∈V*，∈V+}若S=>

A，且=>ε，則#∈FOLLOW(A)也可定義為：FOLLOW(A)={aS=>…Aa…，且a∈VT}若有S=>

…A，則規(guī)定#∈FOLLOW(A)

（用“#”作為輸入串的結束符，或稱輸入串括號）*****13結論當文法中含有形如

A→A→（A∈VN，，∈V*）的產(chǎn)生式時，若和不能同時推導出空，假定=>ε,=>ε則當FIRST()∩(FIRST()∪FOLLOW(A))=?時，若當前非終結符為A,面臨某一輸入符號x，可由x的歸屬決定選擇A的哪個候選式對非終結符A進行替換。**14Select集（Predict集）給定上下文無關文法的產(chǎn)生式A→，A∈VN，∈V*，若=>ε，則SELECT(A→)=FIRST()如果

=>ε，則

SELECT(A→)=(FIRST()-{ε})∪FOLLOW(A)**一個上下文無關文法能進行確定的自頂向下語法分析的充分必要條件是：對每個非終結符A的兩個不同產(chǎn)生式，A→，A→，滿足

SELECT(A→)∩SELECT(A→)=?

其中、不同時能=>ε,這樣的文法稱為LL(1)文法。LL(1)文法*16LL(1)文法能夠使用自頂向下分析技術的文法是LL(1)文法。LL(1)的含義第1個L:自頂向下分析時從左向右掃描輸入串第2個L:分析過程中將用最左推導1:只需向右看一個符號便可決定如何推導即選擇哪個產(chǎn)生式（進行）推導類似也可以有LL(k)文法，也就是需向前查看k個符號才可確定選用哪個產(chǎn)生式。17例文法G[S]：S→aA|d

A→bAS|εSELECT(S→aA)={a}SELECT(S→d)=6116111SELECT(A→bAS)=SELECT(A→ε)={a,d,#}SELECT(S→aA)∩SELECT(S→d)={a}∩6661661=?SELECT(A→bAS)∩SELECT(A→ε)=∩{a,d,#}=?文法為LL(1)文法，可對輸入串進行確定的自頂向下分析。18例文法G[S]：S→aAS|b

A→bA|εSELECT(S→aAS)={a}SELECT(S→b)=SELECT(A→bA)=SELECT(A→ε)={a，b}SELECT(S→aAS)∩SELECT(S→b)={a}∩=?SELECT(A→bA)∩SELECT(A→ε)=∩{a,b}≠?該文法不是LL(1)文法.不能對輸入串（如w=ab）進行確定的自頂向下的語法分析。

S=>aAS=>abAS=>abS=>?=>aS=>ab195.2不確定的自頂向下分析當文法不滿足LL(1)文法的條件時，不能進行確定的自頂向下分析，分析過程中會出現(xiàn)回溯現(xiàn)象，即只能進行不確定的自頂向下分析。三種情況下會引起分析過程中的回溯：20第一種情況關于同一非終結符的不同產(chǎn)生式右部FIRST集交集不為空而引起回溯：如：文法S->xAyA->ab|a輸入串w=xay，分析過程可能為：關于同一非終結符的不同產(chǎn)生式右部以相同的符號串開始（A->|），稱為具有左公因子。左公因子的存在必定會使FIRST集交集不為空。SxAyabSxAya21第二種情況關于同一非終結符的不同產(chǎn)生式右部存在能=>ε的產(chǎn)生式，且該非終結符的FOLLOW集與其它產(chǎn)生式右部FIRST集的交集不為空。如文法G[S]：S→aAS|b

A→bA|εFirst(bA)與Follow(A)的交集不為空。對輸入串W=ab的分析存在回溯（前面已經(jīng)證明）。*22第三種情況文法中含有左遞歸。文法G，存在U∈Vn，如果有U->U…,則G為左遞歸文法（直接左遞歸）類似的：U->V…V->U…（間接左遞歸）如：S->SaS->b

輸入串W=baa的分析：S=>b=>Sa=>ba=>Saa=>baa（回溯）不難證實，若文法中含有間接左遞歸，也會引起回溯。23不確定的自頂向下分析分析過程是一種試探過程，分析過程需進行回溯，也稱這種方法是帶回溯的自頂向下分析方法。語法分析的同時往往進行語義分析，回溯代價高，在實際的編譯程序設計中很少使用。245.3非LL(1)文法的改造若文法中含有左公因子或左遞歸，則文法肯定不是LL(1)文法，不能進行確定的自頂向下語法分析。通過提取左公共因子、消除左遞歸對文法進行等價變換，在某些特殊情況下可使非LL(1)文法變?yōu)長L(1)文法。提取左公因子，消除左遞歸之后文法只是滿足LL(1)文法的必要條件，而不是充分條件，所以不一定是LL(1)文法。25提取左公因子若文法中含有形如Ａβ|的產(chǎn)生式，則稱文法中含有左公因子。這將導致關于同一非終結符的不同產(chǎn)生式右部的FIRST集交集不為空，不滿足LL(1)文法的充要條件。如if語句的文法S→ifEthenS|ifEthenSelseS|other

存在左公因子ifEthenS

影響:遇到if時難以判斷用哪一個產(chǎn)生式進行匹配（推導）26提取左公因子可將文法中的Aβ|變換為：ＡB

Bβ|（B為新引入的非終結符）若β和中仍含有左公共因子，可再次提取，直至引入新非終結符的有關產(chǎn)生式再無左公共因子為止。如if語句文法S→ifEthenS|ifEthenSelseS|other改寫為：

S→ifEthenSS’|otherS'→ε|elseS27提取左公因子更一般的，可將形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm

的規(guī)則改寫為

A→αA’|γ1|γ2|…|γmA'→β1|β2|…|βn28例1：文法G1的產(chǎn)生式為(1)S→aSb(2)S→aS(3)S→(1)(2)提取左公共因子后得S→aS(b|)S→

進一步變?yōu)镚1’：S→aSAS→A→bA→

（非LL(1)文法）

29例2：文法G2的產(chǎn)生式為(1)A→ad

(2)A→Bc(3)B→aA(4)B→bB將(3)(4)代入(2)得到：

(1)A→ad(2)A→aAc(3)A→bBc(4)B→aA(5)B→bB左公共因子可能是隱式的30提取(1)(2)的左公共因子

A→a(d|Ac)A→bBcB→aAB→bB引入新終結符A’(1)A→aA’(2)A→bBc(3)A’→d(4)A’→Ac(5)B→aA(6)B→bB（LL(1)文法）注意：有些文法不能在有限步驟內(nèi)提取左公因子。(P86例5.9)提取左公因子后若不含空產(chǎn)生式和左遞歸則文法是LL(1)文法，否則需進一步判定。(1)A→ad(2)A→aAc(3)A→bBc(4)B→aA(5)B→bB31消除直接左遞歸直接左遞歸若文法中含有形如A→Aα|β的產(chǎn)生式，則稱文法中含有直接左遞歸（生成的串的形式為ba...）直接左遞歸的消除：將A→Aα|β替換為A→βA’

A’→αA’｜ε文法S->Sa|b改寫后對輸入串baaa#是否可進行確定分析？32表達式文法消除左遞歸G[E]:E→E+T｜TT→T*F｜FF→i｜(E)消除左遞歸后為：E→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i將A→Aα|β替換為A→βA’A’→αA’｜ε33一般而言，假定關于P的全部產(chǎn)生式是P→P1|P2|…|Pm

|1|2|…|n

則消除P的直接左遞歸之后為：

P→1P|2P|…|nPP→1P|2P|…|mP|左遞歸變右遞歸消除直接左遞歸34消除間接左遞歸間接左遞歸SAa|b(1)(2)ASd|(3)(4)先變換成直接左遞歸((1)(2)代入(3))SAa|bAAad|bd|

再消除左遞歸SAa|bAbdA|A

A

adA|35消除一切左遞歸1.把文法G的所有非終結符按任一種順序排列成A1，A2，…，An；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DOBEGIN

把形如Ai→Aj的規(guī)則改寫成

Ai→1|2|…|k;(其中Aj→1|2|…|k是關于Aj的所有規(guī)則)END

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

END3.化簡由2所得的文法。去除無用產(chǎn)生式。注意該算法要求文法中不含形如A->A的產(chǎn)生式和空產(chǎn)生式。36消除一切左遞歸例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a 雖沒有直接左遞歸，但S、Q、R都是左遞歸的SQcRbcSabc37文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結符的排序為R、Q、S對于R，不存在直接左遞歸，把R代入到Q的有關候選后，把Q的規(guī)則變?yōu)?/p>

Q→Sab|ab|b現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關候選后，S變成S→Sabc|abc|bc|c消除一切左遞歸38S變成：S→Sabc|abc|bc|c消除S的直接左遞歸后：

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

S→abcS|bcS|cS S→abcS|消除一切左遞歸39注意，由于對非終結符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的。例如，若對前面文法的非終結符排序選為S、Q、R，那么，最后所得的無左遞歸文法是：

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

消除一切左遞歸40非LL(1)文法的改造提取左公因子，消除左遞歸之后文法只是滿足LL(1)文法的必要條件，而不是充分條件，所以不一定是LL(1)文法。根據(jù)定義進行判別415.4LL(1)文法的判別根據(jù)定義進行判別對每個非終結符A的兩個不同產(chǎn)生式，A→，A→，滿足SELECT(A→)∩SELECT(A→)=?

，其中、不同時能=>ε，這樣的文法稱為LL(1)文法。為求SELECT(A→)，需求出FIRST(),若

=>ε，則還需求出FOLLOW(A),因此判別步驟為：1)求出能推出的非終結符2)計算非終結符的FIRST集3)計算非終結符的FOLLOW集（若所有非終結符均不能推出空，此步可省）4)計算SELECT集合，根據(jù)定義判定。*42以改造后的表達式文法為例G’[E]E→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i431)求出能推出的非終結符P79-80(略)：逐次掃描的過程一般情況：若有形如A->的空產(chǎn)生式，則A能推出空若每個產(chǎn)生式右部都含有終結符，則肯定不能推出空當關于某一非終結符的一個產(chǎn)生式右部全是非終結符且每一個都能推出空時，該非終結符能推出空如：文法G’[E]E→TE’

E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i能推出空能推出空不能推出空不能推出空不能推出空442)計算FIRST集求一個文法符號的FIRST集(1)若XV，則FIRST(X)={X}(2)若XVN，且有產(chǎn)生式Xa…，aV，則aFIRST(X)(3)若XVN，X，則FIRST(X)(4)若X，Y1，Y2，…，Yn都VN，而有X→Y1Y2…Yn，當Y1，Y2，…，Yi-1都=>時(1≤i≤n)，則First(Y1)–{}，F(xiàn)irst(Y2)–{}，…，F(xiàn)irst(Yi-1)–{}，F(xiàn)irst(Yi)都包含在First(X)中(5)當(4)所有Yi=>時(i=1，2，…，n)，則First(X)包含

First(Y1)∪First(Y2)∪…∪First(Yn)∪{}反復使用(2)～(5)直到每個符號的FIRST集不再擴大為止**45表達式文法FIRST(E)=FIRST(T)={}FIRST(E’)=FIRST(T)=FIRST(F)={}FIRST(T’)=FIRST(F)=E→TE’

否E’→+TE’|ε是T→FT’

否T’→*FT’｜ε是F→(E)｜i否(,i(,i(1)若XV，則FIRST(X)={X}(2)若XVN，且有產(chǎn)生式Xa…，aV，則aFIRST(X)(3)若XVN，X，則FIRST(X)(4)若X，Y1，Y2，…，Yn都VN，而有X→Y1Y2…Yn，當Y1，Y2，…，Yi-1都=>時(1≤i≤n)，則First(Y1)–{}，F(xiàn)irst(Y2)–{}，…，F(xiàn)irst(Yi-1)–{}，F(xiàn)irst(Yi)都包含在First(X)中(5)當(4)所有Yi=>時(i=1，2，…，n)，則First(X)=First(Y1)∪First(Y2)∪…∪First(Yn)∪{}｛(,i｝｛*,ε｝｛+,ε｝46求出每個文法符號的FIRST集后可以求出一個符號串的FIRST集若符號串V*，=X1X2…Xn，當X1不能=>，則置First()=First(X1)若對任何j(1≤j≤i-1，2≤i≤n)，F(xiàn)IRST(Xj)，F(xiàn)IRST(Xi)，則當所有FIRST(Xj)(1≤j≤n)，都含有時，則如FIRST(TE’)=FIRST(T)={(,i}FIRST(*FT’)={*}文法G[s]:S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM根據(jù)定義求解First(S)=First(M)∪First(H)∪{ε}∪{a}={a,b,d,e,ε}First(H)=First(L)∪{ε}={e,ε}First(K)=1611116∪{ε}={d,ε}First(L)={e}First(M)=First(K)∪={b,d,ε}例：求文法G[s]每個非終結符的First集47是是是否是483)計算FOLLOW集(1)對于文法的開始符號S，置#于FOLLOW(S)中(2)若ＡαBβ是一個產(chǎn)生式，則把FIRST(β)的非空元素加至FOLLOW(B)中;

如果β=>(即FIRST(β)），則把FOLLOW(A)加至FOLLOW(B)中。(3)反復使用(2)直至每個非終結符的FOLLOW集不再增大為止。*49FOLLOW(E)={)，#}FOLLOW(E’)=FOLLOW(E)={)，#}FOLLOW(T)=

(FIRST(E’)-{ε})∪FOLLOW(E)∪FOLLOW(E’)={+，)，#}FOLLOW(T’)=FOLLOW(T)={+，)，#}FOLLOW(F)=(FIRST(T’)-{ε})∪FOLLOW(T)∪FOLLOW(T’)=

{+，*，)，#}表達式文法FIRST(E)={(,i}FIRST(E’)={+,ε}FIRST(T)={(,i}FIRST(T’)={*,ε}FIRST(F)={(,i}E→TE’

否E’→+TE’|ε是T→FT’

否T’→*FT’｜ε是F→(E)｜i否(1)對于文法的開始符號S，置#于FOLLOW(S)中(2)若ＡαBβ是一個產(chǎn)生式，則把FIRST(β)的非空元素加至FOLLOW(B)中，如果β=>(即FIRST(β)），則把FOLLOW（A）加至FOLLOW（B）中。文法G[s]:S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM根據(jù)定義求解Follow(S)={o,#}Follow(H)=Follow(S)∪{f}={f,o,#}Follow(K)=Follow(M)={e,o,#}Follwo(L)=(First(So)-{ε})∪Follow(K)∪(First(M)-{ε})∪Follow(M)=

{a,b,d,e,o,#}Follow(M)=(First(H)-{ε})∪Follow(S)∪(First(L)-{ε})=

{e,o,#}例：求文法G[s]每個非終結符的Follow集是是是否是First(S)={a,b,d,e,ε}First(H)={e,ε}First(K)={d,ε}First(L)={e}First(M)={b,d,ε}51E’–>+TE’|SELECT(E’–>+TE’)=FIRST(+TE’)=｛+｝SELECT(E’–>)=FOLLOW(E′)=｛)

,＃｝T’–>*FT’|SELECT(T’–>*FT’)=FIRST(*FT’)=｛*｝SELECT(T’–>)=FOLLOW(T′)=｛+，)，＃｝F–>(E)|iSELECT(F–>(E))=FIRST((E))=｛(｝SELECT(F–>i)=FIRST(i)=｛i｝關于同一非終結符的不同產(chǎn)生式的SELECT集合交集為空結論：G’[E]是LL（1）文法4)計算SELECT集FIRST(E)={(,i}FIRST(E’)={+,ε}FIRST(T)={(,i}FIRST(T’)={*,ε}FIRST(F)={(,i}FOLLOW(E)={),#}FOLLOW(E’)={),#}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={+,*,),#}給定上下文無關文法的產(chǎn)生式A→，A∈VN，∈V*，若=>*

ε，則SELECT(A→)=FIRST()。如果

=>*

ε，則

SELECT(A→)=(FIRST()-{ε})∪FOLLOW(A)求文法G[s]的Select集并判定是否為LL(1)文法文法G[s]:S->MH|aH->LSo|εK->dML|εL->eHfM->K|bLM52First(S)={a,b,d,e,ε}First(H)={e,ε}First(K)={d,ε}First(L)={e}First(M)={b,d,ε}Follow(S)={o,#}Follow(H)={f,o,#}Follow(K)={e,o,#}First(L)={a,b,d,e,o,#}Follow(M)={e,o,#}是是是否是?YES！53關系圖法求FIRST集、FOLLOW集（略）54例文法:

S→AB|bCA→b|B→aD|

C→AD|b

D→aS|c判斷其是否為LL(1)文法求FIRST集FIRST(S)=(FIRST(A)-{ε})∪FIRST(B)-{ε})∪{ε}∪={a,b,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}此時是否能夠得到結論？55文法S→AB|bCA→b|B→aD|

C→AD|b

D→aS|c求FOLLOW集FOLLOW(S)={#}∪FOLLOW(D)={}(First(B)-{})∪(First(D)-{})∪FOLLOW(S)

={a,c}

∪FOLLOW(S)={}FOLLOW(B)=FOLLOW(S)={}FOLLOW(C)=FOLLOW(S)={}FOLLOW(D)=FOLLOW(B)∪FOLLOW(C)={}FIRST(B)={a,ε}FIRST(D)={a,c}####a,c,#FOLLOW(A)=56求SELECT集合S→AB|bCSELECT(S→AB)=(FIRST(AB)-{})∪FOLLOW(S)={a,b,#}SELECT(S→bC)=FIRST(bC)=交集不為空A→b|SELECT(A→b)=FIRST(b)=SELECT(A→)=)=(FIRST()-{})∪FOLLOW(A)={a,c,#}文法S→AB|bCA→b|B→aD|

C→AD|bD→aS|c57B→aD|

SELECT(B→aD)=FIRST(aD)={a}SELECT(B→)=)=(FIRST()-{})∪FOLLOW(B)={#}C→AD|bSELECT(C→AD)=FIRST(AD)={a,b,c}SELECT(C→b)=FIRST(b)=交集不為空D→aS|cSELECT(D→aS)=FIRST(aS)={a}SELECT(D→c)=FIRST(c)={c}判定：結論：G[S]不是LL(1)文法文法S→AB|bCA→b|B→aD|

C→AD|bD→aS|c58典型例題及解答給定一文法，進行改寫后判定是否為LL(1)P97例2P98例3通常將非終結符的FIRST集FOLLOW集表示在一張表中（例如P96表5.5）作業(yè)：P101.7，選做其一595.5確定的自頂向下分析方法遞歸子程序法（預測分析）分析高效（線性時間）、容易實現(xiàn)（方便手工編碼）、錯誤定位和診斷信息準確、被很多開源和商業(yè)的編譯器所采用GCC4.0，LLVM，……表驅動的預測分析方法分析高效（線性時間）、錯誤定位和診斷信息準確、有很多開源或商業(yè)的生成工具ANTLR，……前提：文法為LL(1)文法60遞歸子程序法實現(xiàn)思想對每個非終符按其產(chǎn)生式結構產(chǎn)生相應語法分析子程序；終結符產(chǎn)生匹配命令，而非終結符則產(chǎn)生調(diào)用命令。因為文法遞歸相應子程序也遞歸，所以稱這種方法為遞歸子程序法（遞歸下降分析方法）。61當產(chǎn)生式形如:A->β1|β2|…|βn

則按下面的方法編寫子程序A：（Pascal風格）procedureA()

beginiftoken∈Select(A->β1)thenθ(β1)else

iftoken∈Select(A->β2)thenθ(β2)else

……

iftoken∈Select(A->βn)

thenθ(βn)else

err()

end其中對βi=X1X2…Xn，θ(βi)=θ’(X1);θ’(X2);…;θ’(Xn);如果X∈VN，θ’(X)=X();如果X∈VT，θ’(X)=Match(X)

（若匹配，則Match中應包含向前讀一輸入符號的動作，也有的書中寫為：advance()或nextsym()）如果X=ε,θ(ε)=skip(空語句)遞歸子程序法62遞歸子程序法例：1）假設有文法Z→aBaB→bB|cSelect(Z→aBa)={a},Select(B→bB)=,Select{B→c}={c}

則相應的遞歸子程序可如下：63procedureZ()//Z→aBabegin

iftoken==athenMatch(a)；//ReadToken

B（）；

Match(a)；

elseerr()；

end;procedureB()//B→bB|c

begin

iftoken==bthenMatch(b);//ReadToken

B（）;

elseiftoken==cthenMatch(c);

elseerr()

end;語法分析主程序：BeginReadToken;Z()；

IFtoken

<

>’#’THENerr()EndZ→aBaB→bB|c對輸入串a(chǎn)bbbbbbbbbbbbca#的遞歸下降分析match(a);B();match(a);abbbbbbbbbbbbca64例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應的遞歸下降子程序為:

PROCEDUREE()BEGIN T()；E()END

PROCEDUREE()BEGINIFtoken==‘+’THEN BEGIN ADVANCE()；

T()；E()

END//否則認為與匹配END65PROCEDURET()BEGIN F()；T()END例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應的遞歸下降子程序為:

PROCEDURET()BEGINIFtoken==‘*’THENBEGINADVANCE()；

F()；T()END//否則認為與匹配END66例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應的遞歸下降子程序為:

PROCEDUREF()BEGINIFtoken==‘i’THENADVANCE()ELSE IFtoken==‘(’THEN BEGIN ADVANCE(); E()；

IFtoken==‘)’THENADVANCE() ELSEERR() END ELSEERR()END67例：2）文法G(E):E→TEE→+TE|T→FT

T→*FT|F→(E)|i對應的遞歸下降子程序為:

主程序:PROGRAMPARSER()BEGINADVANCE();E();IFtoken

<

>’#’THENERR()END.68遞歸子程序法優(yōu)點：1）直觀、簡單、可讀性好2）便于擴充缺點：1)遞歸算法的實現(xiàn)效率低2)處理能力相對有限（只能處理LL(1)文法）3)通用性差，難以自動生成69表驅動的預測分析（LL(1)分析方法）自頂向下分析的另一種方法。一個預測分析器（或LL(1)分析器）由三部分組成：總控程序：對所有的文法和輸入串都是一樣的。分析表

M[A,a]是一個矩陣，AVN

，aVT或‘?！琈[A,a]有兩種情況：產(chǎn)生式A->X1X2…Xn空（出錯標志）分析表對不同的文法是不同的分析棧

STACK用于存放分析過程中的文法符號改造后表達式文法的LL(1)分析表70總控程序分析表X#輸入串分析棧STACKa1a2...ai…#預測分析器預測分析器71總控程序是如何工作的？回憶一個自頂向下的分析過程（手工）：文法G1[S]：S→pA|qBA→cAd|aB→dB|c識別輸入串w=pccadd#是否是G1[S]的句子自頂向下的推導過程為：S#pA#pcAd#pccAdd#pccadd#自動化72初始情況下：分析棧中為“#S”（S為文法開始符號），分析串以#結束?？偪爻绦蚋鶕?jù)現(xiàn)行棧頂符號X和當前輸入符號a，執(zhí)行下列三種動作之一:1.若X＝a＝‘?！瑒t宣布分析成功，停止分析。2.若X＝a‘?！瑒tX出棧，a指向下一個輸入符號。匹配成功總控程序分析成功733.若X是一個非終結符，則查看分析表M。若M[X，a]中存放著關于X的一個產(chǎn)生式，則X出棧，將產(chǎn)生式右部符號串逆序入棧(若產(chǎn)生式右部為，則只將X出棧即可)若M[X，a]為空或為“出錯標志”，則調(diào)用錯誤處理程序進行相應的錯誤處理。推導總控程序74例：對于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 輸入串為i1*i2+i3，利用分析表進行預測分析：75步驟

符號棧

輸入串

所用產(chǎn)生式0 #E i1*i2+i3#E→TE1 #ET i1*i2+i3#T→FT2 #ETF i1*i2+i3#F→i3 #ETi i1*i2+i3# i匹配為何要逆序入棧76步驟

符號棧

輸入串

所用產(chǎn)生式3 #ETi i1*i2+i3# i匹配4 #ET *i2+i3#T→*FT5 #ETF* *i2+i3# *匹配6 #ETFi2+i3#F→i7 #ETi i2+i3#i匹配77步驟

符號棧

輸入串

所用產(chǎn)生7 #ETi i2+i3#i匹配8 #ET +i3#T→9 #E +i3# E→+TE10 #ET+ +i3# +匹配11 #ET i3#T→FT78步驟

符號棧

輸入串

所用產(chǎn)生11 #ET i3#T→FT12 #ETF i3# F→i13 #ETi i3# i匹配14 #ET #T→15 #E # E→16 # # acc(接受)79課堂練習：已知文法G[S]及其LL(1)分析表，請給出對輸入串a(chǎn)aabd#的預測分析過程。80分析表M[A,a]的構造基本思想:當文法中某一非終結符出現(xiàn)在棧頂時,根據(jù)當前的輸入符號,分析表應指示要選擇該非終結符的哪一條規(guī)則進行下一步的匹配（推導）。構造方法：對每個終結符或’#’用a表示若aSelect(A->α)，則把A->α放入M[A,a]所有無定義的M[A,a]標上出錯標記或置空。81也可表述為（略）：在對文法G的每個非終結符A及其任意候選都構造出FIRST()和FOLLOW(A)之后，現(xiàn)在可以用它們來構造G的分析表M[A，a]。1.對文法G的每個產(chǎn)生式A→執(zhí)行第2步和第3步；2.對每個終結符aFIRST()，把A→加至M[A，a]中；3.若FIRST()，則對任何bFOLLOW(A)把A→加至M[A，b]中。4.把所有無定義的M[A，a]標上“出錯標志”。82例如：對于文法G(E)E→TEE→+TE|T→FT

T→*FT|F→(E)|i 1.首先計算每個非終結符的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)={*,+,),#}832.計算產(chǎn)生式的Select集合SELECT(E–>TE’)=FIRST(TE’)=｛(，i｝SELECT(T–>FT’)=FIRST(FT’)=｛(，i｝E’–>+TE’|SELECT(E’–>+TE’)=FIRST(+TE’)=｛+｝SELECT(E’–>)=FOLLOW(E′)=｛)，＃｝T’–>*FT’|SELECT(T’–>*FT’)=FIRST(*FT’)=｛*｝SELECT(T’–>)=FOLLOW(T′)=｛+，)，＃｝F–>(E)|iSELECT(F–>(E))=FIRST((E))=｛(｝SELECT(F–>i)=FIRST(i)=｛i｝3.構造表達式文法的分析表也可只寫產(chǎn)生式右部SELECT集的另一種表示84①LL(1)的含義（P78）②預測分析法是