自頂向下的語(yǔ)法分析

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

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

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

例2推導(dǎo)過(guò)程：S#Ap#

cAp#

ccAp#

ccap#9S→Ap|Bq

A→cA|a

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

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

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

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

abASabS

abd12FOLLOW集的定義設(shè)G=(VT，VN，P，S)是上下文無(wú)關(guān)文法，A∈VN，S是開(kāi)始符號(hào)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)

（用“#”作為輸入串的結(jié)束符，或稱(chēng)輸入串括號(hào)）*****13結(jié)論當(dāng)文法中含有形如

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

=>ε，則

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

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

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

A→bAS|εSELECT(S→aA)={a}SELECT(S→d)=q4ewumkSELECT(A→bAS)=SELECT(A→ε)={a,d,#}SELECT(S→aA)∩SELECT(S→d)={a}∩ygumwe4=?SELECT(A→bAS)∩SELECT(A→ε)=∩{a,d,#}=?文法為L(zhǎng)L(1)文法，可對(duì)輸入串進(jìn)行確定的自頂向下分析。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)文法.不能對(duì)輸入串（如w=ab）進(jìn)行確定的自頂向下的語(yǔ)法分析。

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

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

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

存在左公因子ifEthenS

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

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

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

的規(guī)則改寫(xiě)為

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→

進(jìn)一步變?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引入新終結(jié)符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)文法，否則需進(jìn)一步判定。(1)A→ad(2)A→aAc(3)A→bBc(4)B→aA(5)B→bB31消除直接左遞歸直接左遞歸若文法中含有形如A→Aα|β的產(chǎn)生式，則稱(chēng)文法中含有直接左遞歸（生成的串的形式為ba...）直接左遞歸的消除：將A→Aα|β替換為A→βA’

A’→αA’｜ε文法S->Sa|b改寫(xiě)后對(duì)輸入串baaa#是否可進(jìn)行確定分析？32表達(dá)式文法消除左遞歸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一般而言，假定關(guān)于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的所有非終結(jié)符按任一種順序排列成A1，A2，…，An；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DOBEGIN

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

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

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

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

Q→Sab|ab|b現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，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關(guān)于Q和R的規(guī)則已是多余的，化簡(jiǎn)為：

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

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

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

，其中、不同時(shí)能=>ε，這樣的文法稱(chēng)為L(zhǎng)L(1)文法。為求SELECT(A→)，需求出FIRST(),若

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

E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i能推出空能推出空不能推出空不能推出空不能推出空442)計(jì)算FIRST集求一個(gè)文法符號(hào)的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，當(dāng)Y1，Y2，…，Yi-1都=>時(shí)(1≤i≤n)，則First(Y1)–{}，F(xiàn)irst(Y2)–{}，…，F(xiàn)irst(Yi-1)–{}，F(xiàn)irst(Yi)都包含在First(X)中(5)當(dāng)(4)所有Yi=>時(shí)(i=1，2，…，n)，則First(X)包含

First(Y1)∪First(Y2)∪…∪First(Yn)∪{}反復(fù)使用(2)～(5)直到每個(gè)符號(hào)的FIRST集不再擴(kuò)大為止**45表達(dá)式文法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，當(dāng)Y1，Y2，…，Yi-1都=>時(shí)(1≤i≤n)，則First(Y1)–{}，F(xiàn)irst(Y2)–{}，…，F(xiàn)irst(Yi-1)–{}，F(xiàn)irst(Yi)都包含在First(X)中(5)當(dāng)(4)所有Yi=>時(shí)(i=1，2，…，n)，則First(X)=First(Y1)∪First(Y2)∪…∪First(Yn)∪{}｛(,i｝｛*,ε｝｛+,ε｝46求出每個(gè)文法符號(hào)的FIRST集后可以求出一個(gè)符號(hào)串的FIRST集若符號(hào)串V*，=X1X2…Xn，當(dāng)X1不能=>，則置First()=First(X1)若對(duì)任何j(1≤j≤i-1，2≤i≤n)，F(xiàn)IRST(Xj)，F(xiàn)IRST(Xi)，則當(dāng)所有FIRST(Xj)(1≤j≤n)，都含有時(shí)，則如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)=ggauwo4∪{ε}={d,ε}First(L)={e}First(M)=First(K)∪={b,d,ε}例：求文法G[s]每個(gè)非終結(jié)符的First集47是是是否是483)計(jì)算FOLLOW集(1)對(duì)于文法的開(kāi)始符號(hào)S，置#于FOLLOW(S)中(2)若ＡαBβ是一個(gè)產(chǎn)生式，則把FIRST(β)的非空元素加至FOLLOW(B)中;

如果β=>(即FIRST(β)），則把FOLLOW(A)加至FOLLOW(B)中。(3)反復(fù)使用(2)直至每個(gè)非終結(jié)符的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’)=

{+，*，)，#}表達(dá)式文法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)對(duì)于文法的開(kāi)始符號(hào)S，置#于FOLLOW(S)中(2)若ＡαBβ是一個(gè)產(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]每個(gè)非終結(jié)符的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｝關(guān)于同一非終結(jié)符的不同產(chǎn)生式的SELECT集合交集為空結(jié)論：G’[E]是LL（1）文法4)計(jì)算SELECT集FIRST(E)={(,i}FIRST(E’)={+,ε}FIRST(T)={(,i}FIRST(T’)={*,ε}FIRST(F)={(,i}FOLLOW(E)={),#}FOLLOW(E’)={),#}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={+,*,),#}給定上下文無(wú)關(guān)文法的產(chǎn)生式A→，A∈VN，∈V*，若=>*

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

=>*

ε，則

SELECT(A→)=(FIRST()-{ε})∪FOLLOW(A)求文法G[s]的Select集并判定是否為L(zhǎng)L(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關(guān)系圖法求FIRST集、FOLLOW集（略）54例文法:

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

C→AD|b

D→aS|c判斷其是否為L(zhǎng)L(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}此時(shí)是否能夠得到結(jié)論？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}判定：結(jié)論：G[S]不是LL(1)文法文法S→AB|bCA→b|B→aD|

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

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

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

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

……

iftoken∈Select(A->βn)

thenθ(βn)else

err()

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

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

則相應(yīng)的遞歸子程序可如下：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;語(yǔ)法分析主程序：BeginReadToken;Z()；

IFtoken

<

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

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

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

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

T()；E()

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

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

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

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

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

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對(duì)應(yīng)的遞歸下降子程序?yàn)?

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

<

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

M[A,a]是一個(gè)矩陣，AVN

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

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

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

符號(hào)棧

輸入串

所用產(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步驟

符號(hào)棧

輸入串

所用產(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步驟

符號(hào)棧

輸入串

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

符號(hào)棧

輸入串

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

T→*FT|F→(E)|i 1.首先計(jì)算每個(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)={*,+,),#}832.計(jì)算產(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.構(gòu)造表達(dá)式文法的分析表也可只寫(xiě)產(chǎn)生式右部SELECT集的另一種表示84①LL(1)的含義（P78）②預(yù)測(cè)分析法是