第5章自頂向下語(yǔ)法分析方法(6學(xué)時(shí))

第5章自頂向下語(yǔ)法分析方法理解“能使用自頂向下分析技術(shù)的文法必須是LL(1)文法”LL(1)文法的充要條件LL(1)文法的判別某些非LL(1)文法

到LL(1)文法

的等價(jià)變換提取左公共因子消除左遞歸（直接左遞歸、間接左遞歸）不確定的自頂向下分析思想確定的自頂向下分析方法遞歸子程序法預(yù)測(cè)分析法[判別LL(1)文法；構(gòu)造預(yù)測(cè)分析表；分析輸入串]預(yù)備知識(shí)語(yǔ)法分析的作用：識(shí)別單詞符號(hào)序列是否是給定文法的正確程序。語(yǔ)法分析的方法：自頂向下分析法：“面向目標(biāo)的分析方法”

從開(kāi)始符號(hào)出發(fā)，企圖推導(dǎo)出與輸入的單詞串完全匹配的句子。（1）確定的方法：需要對(duì)文法有一定的限制。 優(yōu)點(diǎn)：簡(jiǎn)單、直觀（2）不確定的方法：帶回溯的分析方法——窮舉的試探方法 缺點(diǎn)：效率低、代價(jià)高自頂向下分析自底向上分析確定的方法不確定的方法算符優(yōu)先分析LR分析5.1確定的自頂向下分析思想主要思想：從文法的開(kāi)始符號(hào)出發(fā)，如何根據(jù)當(dāng)前的單詞符號(hào)，唯一地確定選用哪個(gè)產(chǎn)生式來(lái)替換相應(yīng)的VN向下推導(dǎo)。例1：文法 G1[S]：S→pA S→qB A→cAd A→a B→dB B→b對(duì)應(yīng)的語(yǔ)法樹(shù)：SpAcAdcAdaSpApcAdpccAddpccadd這個(gè)文法的特點(diǎn)：（保證了推導(dǎo)過(guò)程唯一）每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開(kāi)始。左部相同的產(chǎn)生式，它們的右部由不同的終結(jié)符開(kāi)始。W=pccadd

自頂向下的推導(dǎo)過(guò)程：文法例1例2：文法G[S]:

S→Ap

S→Bp

A→a

A→cA

B→b

B→dBW=ccap

自頂向下的推導(dǎo)過(guò)程：語(yǔ)法樹(shù)：SApcAcAaSApcApccApccap這個(gè)文法的特點(diǎn)：（保證了推導(dǎo)過(guò)程唯一）每個(gè)產(chǎn)生式的右部不全是由終結(jié)符號(hào)開(kāi)始。左部相同的產(chǎn)生式，它們的右部由不同的終結(jié)符或非終結(jié)符開(kāi)始。（引出First集合）文法中無(wú)空產(chǎn)生式。（→ε）文法例2為得到唯一的推導(dǎo)過(guò)程，條件為：左部相同的產(chǎn)生式，其“右部的首符號(hào)集合”不相交。

定義：設(shè)G=(VT,VN,S,P)是上下文無(wú)關(guān)文法，

FIRST(α)={a|αaβ,a∈VT,α,β∈V*}

若αε，則規(guī)定ε∈FIRST(α)**例2：文法G[S]:

S→Ap

S→Bp

A→a

A→cA

B→b

B→dB求：First(Ap)First(Bp)First(a)First(cA)First(b)First(dB)={a,c}={b,d}={a}={c}==lvwi26dFirst集合例3：文法G[S]:

S→aA

S→d

A→bAS

A→εW=abd自頂向下的推導(dǎo)過(guò)程：SaAabASabSabd文法例3這個(gè)文法的特點(diǎn)：文法中包含空產(chǎn)生式。（→ε）為得到唯一的推導(dǎo)過(guò)程，條件為： 當(dāng)某一VN的產(chǎn)生式含空產(chǎn)生式， 則它的非空產(chǎn)生式的First集兩兩互不相交，且

與推導(dǎo)過(guò)程中緊跟該VN可能出現(xiàn)的VT集合也不相交。Follow集定義：設(shè)G=(VT,VN,S,P)是上下文無(wú)關(guān)文法，A∈VN,S是開(kāi)始符號(hào)。

FOLLOW(A)={a|SA且a∈FIRST(),∈VT*,∈V+}若SA,且

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

#作為輸入串的結(jié)束符，或稱為句子括號(hào)，

如：#輸入串#***Follow集合**通俗地講：

FOLLOW(A)={a|S…Aa…,a∈VT}

若S…A，則規(guī)定

#∈FOLLOW(A)返回舉例，求例3中每個(gè)非終結(jié)符的Follow集為得到唯一的推導(dǎo)過(guò)程，條件為： 當(dāng)某一VN的產(chǎn)生式含空產(chǎn)生式， 則它的非空產(chǎn)生式的First集兩兩互不相交且 與推導(dǎo)過(guò)程中緊跟該VN可能出現(xiàn)的VT集合也不相交可得到唯一的推導(dǎo)過(guò)程的條件等價(jià)的表示： 若 A→αA→β其中A∈VN,α,β∈VN*，α不推導(dǎo)出空，β能推導(dǎo)出空，

則FIRST(α)∩((FIRST(β)-{ε})∪FOLLOW(A))=ΦSELECT集定義：

給定上下文無(wú)關(guān)文法的產(chǎn)生式A→α，A∈VN,α∈V*，

若αε，則

SELECT(A→α)=First(α)

若αε，則

SELECT(A→α)=(First(α)-{ε})∪Follow(A)**SELECT集合舉例，求例3中每個(gè)產(chǎn)生式的Select集返回定義：

一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充要條件： 對(duì)每個(gè)VN，A的兩個(gè)不同產(chǎn)生式A→α，A→β， 滿足SELECT(A→α)∩SELECT(A→β)=φ 其中，α、β不能同時(shí)推導(dǎo)出ε?？墒褂谩白皂斚蛳路治觥钡奈姆ǚQ為L(zhǎng)L(1)文法。必須滿足的條件：LL(1)文法L：scanfromLeft從左向右掃描輸入串L：analyzefromLeft：分析過(guò)程是最左推導(dǎo)1：只需向右看一個(gè)符號(hào)便可以決定選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。例4：判斷文法G[S]是否為L(zhǎng)L(1)文法？G[S]: S→aAS S→b A→bA A→εLL(1)文法判別舉例解：Select(S→aAS)={a} Select(S→b)=Select(A→bA)=Select(A→ε)=(First(ε)-{ε})∪Follow(A)∵Follow(A)=First(S)∪Follow(A)={a,b}∴Select(A→ε)=(First(ε)-{ε})∪Follow(A)={a,b}由于 Select(S→aAS)∩Select(S→b)=Ф

Select(A→bA)∩Select(A→ε)≠Ф故該文法不是LL(1)文法，不能用自頂向下分析技術(shù)。舉例：對(duì)輸入串a(chǎn)b進(jìn)行推導(dǎo)就可能產(chǎn)生錯(cuò)誤。5.2LL(1)文法的判別判別步驟：求出能推出ε的非終結(jié)符計(jì)算FIRST集計(jì)算FOLLOW集計(jì)算SELECT集判別是否是LL(1)文法例5：設(shè)文法G[S]為: S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

判斷它是否是LL(1)文法。判別步驟：求出能推出ε的非終結(jié)符計(jì)算FIRST集計(jì)算FOLLOW集計(jì)算SELECT集判別是否是LL(1)文法NEXT1.求出能推出ε的非終結(jié)符建立一個(gè)以VN的個(gè)數(shù)為上限的一維數(shù)組X[]，數(shù)組元素為VN，對(duì)應(yīng)每個(gè)VN有一標(biāo)志位；（該標(biāo)志位記錄能否推出ε，其值為：“未定”、“是”、“否”）置初值——將數(shù)組X[]中對(duì)應(yīng)的每一個(gè)VN的標(biāo)記置為“未定”；刪除所有右部含VT的產(chǎn)生式，若某一VN為左部的產(chǎn)生式全被刪除，則將數(shù)組中對(duì)應(yīng)的標(biāo)記值改為“否”；若某一的某產(chǎn)生式右部為ε，則數(shù)組中對(duì)應(yīng)的標(biāo)記值為“是”，并刪除該VN為左部的所有產(chǎn)生式；掃描產(chǎn)生式右部的每個(gè)VN，若該VN在數(shù)組中對(duì)應(yīng)標(biāo)志為“是”，則刪去該VN，轉(zhuǎn)6；若該VN在數(shù)組中對(duì)應(yīng)標(biāo)志為“否”，則轉(zhuǎn)7；若該VN刪去后，所在產(chǎn)生式右部為空，則該產(chǎn)生式左部的VN在數(shù)組中對(duì)應(yīng)的標(biāo)志改為“是”，并刪去該VN為左部的所有產(chǎn)生式；否則轉(zhuǎn)8；刪去該產(chǎn)生式，若該產(chǎn)生式左部在剩余的產(chǎn)生式中是唯一的左部（即A→α…，再無(wú)其它“A→β”的產(chǎn)生式），則把書(shū)組中該VN對(duì)應(yīng)的標(biāo)志改為“否”；返回5，直至掃描完一邊文法的產(chǎn)生式后，數(shù)組中的標(biāo)志不再改變。1.求出能推出ε的非終結(jié)符S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c非終結(jié)符SABCD初值未定未定未定未定未定第1次掃描是是否第2次掃描是否返回2.計(jì)算FIRST集求First(x)的算法：若x∈VT,則first(x)={x}若X∈VN,且有產(chǎn)生式Xa…,a∈VT,則a∈first(X)若X∈VN,xε,則ε∈first(X)若X∈VN,且有產(chǎn)生式XY1Y2…Yn,其中Y1,Y2,…Yn都∈VN當(dāng)Y1,Y2,…Yi-1都能推導(dǎo)出ε時(shí)(1<=i<=n),則 first(Y1)-{ε}∈first(X) first(Y2)-{ε}∈first(X)

… first(Yi)∈first(X)當(dāng)Y1,Y2,…Yn都能推導(dǎo)出ε時(shí),則first(X)=(first(Y1)-{ε})∪(first(Y2)-{ε})∪…… ∪(first(Yn)-{ε})∪{ε}方法一：根據(jù)定義計(jì)算方法二：關(guān)系圖法（自學(xué)）定義：First(α)={a|αaβ,a∈VT,α,β∈V*}若αε，則ε∈First(α)First(S)=(First(A)-{ε})∪(First(B)-{ε})∪{ε}∪ ={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}First(AB)={a,b,ε} First(bB)=First(ε)={ε} First(b)=First(aD)={a} First(AD)={a,b,c}First(aS)={a} First(c)={c}S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c2.計(jì)算FIRST集返回設(shè)S為開(kāi)始符號(hào)，把{#}加入Follow(S)中（#為句子括號(hào)）若A→αBβ，則把First(β)–{ε}

加入Follow(B)中， 如果βε，則把Follow(A)也加入Follow(B)中。反復(fù)2，直到每個(gè)VN的Follow集不再增大為止。3.計(jì)算FOLLOW集方法一：根據(jù)定義計(jì)算方法二：關(guān)系圖法（自學(xué)）Follow(S)={#}∪Follow(D)Follow(A)={a}∪{a,c}∪Follow(S)Follow(B)=Follow(S)Follow(C)=Follow(S)Follow(D)=Follow(B)∪Follow(C)Follow(S)={#}Follow(A)={a,c,#}Follow(B)={#}Follow(C)={#}Follow(D)={#}返回3.計(jì)算FOLLOW集S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c定義：對(duì)于產(chǎn)生式Aα

，A∈VN，α∈V*

若αε，則Select(Aα)=First(α)若αε，則Select(Aα)=(First(α)-{ε})∪Follow(A)

4.計(jì)算SELECT集Select(SAB)=(First(AB)-{ε})∪Follow(S)={a,b,#}Select(SbC)=First(bC)=Select(Aε)=(First(ε)-{ε})∪Follow(A)={a,c,#}Select(Ab)=First(b)=Select(Bε)=(First(ε)-{ε})∪Follow(B)={#}Select(B→aD)=First(aD)={a}Select(C→AD)=First(AD)={a,b,c}Select(C→b)=First(b)=Select(D→aS)=First(aS)={a}Select(D→c)=First(c)={c}續(xù)上例：S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cFollow(S)={#}Follow(A)={a,c,#}Follow(B)={#}Follow(C)={#}Follow(D)={#}First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}First(AB)={a,b,ε}First(AD)={a,b,c}返回LL(1)文法：左部相同的產(chǎn)生式的SELECT集的交集均為空。5.判別Select(SAB)={a,b,#}Select(SbC)=Select(Aε)={a,c,#}Select(Ab)=Select(Bε)={#}Select(B→aD)={a}Select(C→AD)={a,b,c} Select(C→b)=Select(D→aS)={a} Select(D→c)={c}S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c返回Select(SAB)∩Select(SbC)=≠φSelect(Aε)∩Select(Ab)=φSelect(Bε)∩Select(B→aD)=φSelect(C→AD)∩Select(C→b)=≠φ存在交集非空的SELECT集合，所以該文法不是LL(1)文法。5.3某些非LL(1)文法到LL(1)文法的等價(jià)變換非LL(1)文法若文法含有左公共因子，一定不是LL(1)文法若文法含有直接或間接左遞歸，一定不是LL(1)文法非LL(1)文法LL(1)文法的等價(jià)變換：提取左公共因子消除左遞歸5.3.1.1提取左公共因子對(duì)形如 Aαβ|αγ

進(jìn)行等價(jià)變換為：Aα(β|γ)進(jìn)一步變換：

AαA’A’β|γ

對(duì)形如 Aαβ1|αβ2|…|αβn

進(jìn)行等價(jià)變換為： Aα(β1|β2|…|βn)進(jìn)一步變換(引入新非終結(jié)符A’)：AαA’A’β1|β2|…|βn注：若A’β1|β2|…|βn中仍含左公共因子，再次提取，直至所有的產(chǎn)生式不再有左公共因子。例6：文法G[S]為:S→aSbS→aSS→ε解：結(jié)論1：文法中不含左公共因子只是LL(1)文法的必要條件。即：

LL(1)文法一定不含左公共因子不含左公共因子的文法不一定是LL(1)文法SaS(b|ε)SεSaSbSaSSεSaSS’SεS’bS’εSaSS’S’b|εSε5.3.1.2提取隱含的左公共因子隱式變顯式：右部以VN開(kāi)始的產(chǎn)生式，用該VN對(duì)應(yīng)的產(chǎn)生式進(jìn)行相應(yīng)替換再用一般形式進(jìn)行提?。篈αβ1|αβ2|…|αβn等價(jià)變換為：AαA’A’β1|β2|…|βn例7：文法G[S]為:

S→aSd

S→Ac

A→aS

A→bS→aSd

S→aScS→bcA→aS

A→bS→aS(d|c)

S→bcA→aS

A→bS→aSA'

S→bcA'→dA'→cA→aS

A→bA是多余產(chǎn)生式！S→aSA'S→bcA'→dA'→c5.3.1.3不能在有限步驟內(nèi)提取完左公共因子的文法例8：文法G[S]為:S→ApS→BqA→aApA→dB→aBqB→eSaAppSdpSaBqqSeqAaApAdBaBqBeSa(App|Bqq)SdpSeqAaApAdBaBqBeSaS’S’AppS’BqqSdpSeqAaApAdBaBqBe繼續(xù)替換S’產(chǎn)生式右部的A和B，只能使產(chǎn)生式無(wú)限地增加下去。結(jié)論2：不是所有文法，都能在有限的步驟內(nèi)提取完“左公共因子”。5.3.2消除左遞歸左遞歸的形式：直接左遞歸

A→Aβ AVN,βV*間接左遞歸

A→Bβ

B→Aα A,BVN,α,βV*文法提取左公共因子后，并不一定是LL(1)文法。只有不含空產(chǎn)生式，且無(wú)左公共因子，且無(wú)左遞歸時(shí)，文法才是LL(1)文法。否則需要進(jìn)行判別。把“直接左遞歸”改為“右遞歸”：AAα1|Aα2|…|AαmAβ1|β2|…|βn改寫(xiě)為：Aβ1A’|β2A’|…|βnA’A’α1A’|α2A’|…|αmA’|A’ε5.3.2.1消除直接左遞歸例9：消除文法G[S]的左遞歸。 S→Sa

S→b

解：左遞歸文法改寫(xiě)為： SbS’

S’aS’ S’ε先把“間接左遞歸”變?yōu)椤爸苯幼筮f歸”再將“直接左遞歸”化為“右遞歸”：AAα1|Aα2|…|AαmAβ1|β2|…|βn 改寫(xiě)為：Aβ1A’|β2A’|…|βnA’A’α1A’|α2A’|…|αmA’|A’ε5.3.2.2消除間接左遞歸例10：消除文法G[A]的間接左遞歸。A→aB

A→Bb

B→Ac

B→d

“間接”變“直接”

AaB AAcb Adb BAc Bd“左遞歸”化為“右遞歸”

AaBA’|dbA’ A’cbA’|ε BAc Bd3消除文法中一切左遞歸以某種順序?qū)N的排序?yàn)椋篈1，A2，…，Anfor(i=1;i<=n;i++){for(j=1;j<=i-1;j++)//以A1，…，Ai-1的產(chǎn)生式代入Ai產(chǎn)生式{若Aj的產(chǎn)生式為：Ajδ1|δ2|…|δk 則形如AiAjγ的產(chǎn)生式變?yōu)椋篈iδ1γ|δ2γ|…|δkγ}

消除Ai中的一切直接左遞歸}刪除多余產(chǎn)生式例11：消除文法G[A]的一切左遞歸。S→Qc|c

Q→Rb|b

R→Sa|a例11：消除文法G[A]的一切左遞歸。 S→Qc|c

Q→Rb|b

R→Sa|a解：終結(jié)符排序?yàn)椋篠,Q,R(1)對(duì)于S：無(wú)直接左遞歸（不用消除）(2)對(duì)于Q：右部不含S開(kāi)頭的產(chǎn)生式 無(wú)直接左遞歸（不用消除）(3)對(duì)于R：右部含S開(kāi)頭的產(chǎn)生式，則：

SQc QRb RQca Sc Qb Rca Ra 右部含Q開(kāi)頭的產(chǎn)生式：

SQc QRb RRbca Sc Qb Rbca Rca Ra消除直接左遞歸：

SQc QRb R(bca|ca|a)R’ Sc Qb R’bcaR’|ε(4)考察是否存在無(wú)用產(chǎn)生式：沒(méi)有“無(wú)用產(chǎn)生式”，所以不用刪除。5.5確定的自頂向下分析方法遞歸子程序法:主要思想： 對(duì)文法中每個(gè)非終結(jié)符編寫(xiě)一個(gè)遞歸過(guò)程，每個(gè)過(guò)程的功能是識(shí)別由該非終結(jié)符推出的串，當(dāng)某非終結(jié)符的產(chǎn)生式有多個(gè)候選時(shí)能夠按LL(1)形式可唯一地確定選擇某個(gè)候選進(jìn)行推導(dǎo)。優(yōu)點(diǎn)： 簡(jiǎn)單、直觀、易于構(gòu)造。（PL/0的語(yǔ)法分析）缺點(diǎn)： 對(duì)文法要求高，必須滿足LL(1)文法； 由于遞歸調(diào)用多，速度慢，占用空間多。5.5確定的自頂向下分析方法預(yù)測(cè)分析法:預(yù)測(cè)分析器的組成： 預(yù)測(cè)分析程序、先進(jìn)后出棧、預(yù)測(cè)分析表預(yù)測(cè)分析法的步驟：（1）提取左公共因子，消除左遞歸（2）判斷文法是否為L(zhǎng)L(1)文法（3）若是，構(gòu)造預(yù)測(cè)分析表； 否則，不能進(jìn)行“確定的自頂向下”分析（4）預(yù)測(cè)分析程序根據(jù)“預(yù)測(cè)分析表”并利用“分析?！?，對(duì)輸入串進(jìn)行分析例12：文法G[E]: EE+T|T 構(gòu)造預(yù)測(cè)分析表。 TT*F|F Fi|(E)

解：（1）消除左遞歸： VN排列為E,T,F 消除E一切直接左遞歸： ETE’ TT*F Fi E’+TE’|ε TF F(E) 消除T的一切直接左遞歸： ETE’ TFT’ Fi E’+TE’|ε T’*FT’|ε F(E) F沒(méi)有左遞歸。 文法無(wú)左公共因子。 所以，提取左公共因子和消除左遞歸后的文法為：

ETE’ TFT’ Fi E’+TE’ T’*FT’ F(E) E’ε T’ε（2）判斷改寫(xiě)后的文法是否為L(zhǎng)L(1)文法：可推導(dǎo)出ε的VN表： E E’ T T’ F 否 是 否 是 否求First集：First(E)={i,(} First(E’)={+,ε}First(T)={i,(} First(T’)={*,ε}First(F)={i,(}First(TE’)=First(T)={i,(}First(FT’)=First(F)={i,(}求Follow集：Follow(E)={#,)}Follow(E’)=Follow(E)∪Follow(E’)={ #,)}Follow(T)=(First(E’)-{ε})∪Follow(E’)={+,#,)}Follow(T’)=Follow(T)∪Follow(T’)={+,#,)}Follow(F)=(First(T’)-{ε})∪Follow(T)∪Follow(T’) ={*,+,#,)}

求各產(chǎn)生式的SELECT集：SELECT(ETE’)=First(TE’)={i,(}SELECT(E’+TE’)=First(+TE’)={+}SELECT(E’ε)=Follow(E’)={#,)}SELECT(TFT’)=First(FT’)={i,(}SELECT(T’*FT’)=First(*FT’)={*}SELECT(T’ε)=Follow(T’)={+,#,)}SELECT(F(E))=First((E))={(}SELECT(Fi)=First(i)={i}判定：SELECT(E’