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

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

到LL(1)文法

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

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

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

S→Ap

S→Bp

A→a

A→cA

B→b

B→dBW=ccap

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

定義：設(shè)G=(VT,VN,S,P)是上下文無關(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}==isxyjk8First集合例3：文法G[S]:

S→aA

S→d

A→bAS

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

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

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

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

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

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

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

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

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

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

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

若αε，則

SELECT(A→α)=First(α)

若αε，則

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

一個上下文無關(guān)文法是LL(1)文法的充要條件： 對每個VN，A的兩個不同產(chǎn)生式A→α，A→β， 滿足SELECT(A→α)∩SELECT(A→β)=φ 其中，α、β不能同時推導(dǎo)出ε。可使用“自頂向下分析”的文法稱為LL(1)文法。必須滿足的條件：LL(1)文法L：scanfromLeft從左向右掃描輸入串L：analyzefromLeft：分析過程是最左推導(dǎo)1：只需向右看一個符號便可以決定選擇哪個產(chǎn)生式進行推導(dǎo)。例4：判斷文法G[S]是否為LL(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ù)。舉例：對輸入串a(chǎn)b進行推導(dǎo)就可能產(chǎn)生錯誤。5.2LL(1)文法的判別判別步驟：求出能推出ε的非終結(jié)符計算FIRST集計算FOLLOW集計算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é)符計算FIRST集計算FOLLOW集計算SELECT集判別是否是LL(1)文法NEXT1.求出能推出ε的非終結(jié)符建立一個以VN的個數(shù)為上限的一維數(shù)組X[]，數(shù)組元素為VN，對應(yīng)每個VN有一標(biāo)志位；（該標(biāo)志位記錄能否推出ε，其值為：“未定”、“是”、“否”）置初值——將數(shù)組X[]中對應(yīng)的每一個VN的標(biāo)記置為“未定”；刪除所有右部含VT的產(chǎn)生式，若某一VN為左部的產(chǎn)生式全被刪除，則將數(shù)組中對應(yīng)的標(biāo)記值改為“否”；若某一的某產(chǎn)生式右部為ε，則數(shù)組中對應(yīng)的標(biāo)記值為“是”，并刪除該VN為左部的所有產(chǎn)生式；掃描產(chǎn)生式右部的每個VN，若該VN在數(shù)組中對應(yīng)標(biāo)志為“是”，則刪去該VN，轉(zhuǎn)6；若該VN在數(shù)組中對應(yīng)標(biāo)志為“否”，則轉(zhuǎn)7；若該VN刪去后，所在產(chǎn)生式右部為空，則該產(chǎn)生式左部的VN在數(shù)組中對應(yīng)的標(biāo)志改為“是”，并刪去該VN為左部的所有產(chǎn)生式；否則轉(zhuǎn)8；刪去該產(chǎn)生式，若該產(chǎn)生式左部在剩余的產(chǎn)生式中是唯一的左部（即A→α…，再無其它“A→β”的產(chǎn)生式），則把書組中該VN對應(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.計算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)出ε時(1<=i<=n),則 first(Y1)-{ε}∈first(X) first(Y2)-{ε}∈first(X)

… first(Yi)∈first(X)當(dāng)Y1,Y2,…Yn都能推導(dǎo)出ε時,則first(X)=(first(Y1)-{ε})∪(first(Y2)-{ε})∪…… ∪(first(Yn)-{ε})∪{ε}方法一：根據(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.計算FIRST集返回設(shè)S為開始符號，把{#}加入Follow(S)中（#為句子括號）若A→αBβ，則把First(β)–{ε}

加入Follow(B)中， 如果βε，則把Follow(A)也加入Follow(B)中。反復(fù)2，直到每個VN的Follow集不再增大為止。3.計算FOLLOW集方法一：根據(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.計算FOLLOW集S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

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

，A∈VN，α∈V*

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

4.計算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)文法的等價變換非LL(1)文法若文法含有左公共因子，一定不是LL(1)文法若文法含有直接或間接左遞歸，一定不是LL(1)文法非LL(1)文法LL(1)文法的等價變換：提取左公共因子消除左遞歸5.3.1.1提取左公共因子對形如 Aαβ|αγ

進行等價變換為：Aα(β|γ)進一步變換：

AαA’A’β|γ

對形如 Aαβ1|αβ2|…|αβn

進行等價變換為： Aα(β1|β2|…|β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開始的產(chǎn)生式，用該VN對應(yīng)的產(chǎn)生式進行相應(yīng)替換再用一般形式進行提取：Aαβ1|αβ2|…|αβn等價變換為：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)生式無限地增加下去。結(jié)論2：不是所有文法，都能在有限的步驟內(nèi)提取完“左公共因子”。5.3.2消除左遞歸左遞歸的形式：直接左遞歸

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

A→Bβ

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

S→b

解：左遞歸文法改寫為： SbS’

S’aS’ S’ε先把“間接左遞歸”變?yōu)椤爸苯幼筮f歸”再將“直接左遞歸”化為“右遞歸”：AAα1|Aα2|…|AαmAβ1|β2|…|βn 改寫為：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的排序為：A1，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é)符排序為：S,Q,R(1)對于S：無直接左遞歸（不用消除）(2)對于Q：右部不含S開頭的產(chǎn)生式 無直接左遞歸（不用消除）(3)對于R：右部含S開頭的產(chǎn)生式，則：

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

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

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

ETE’ TFT’ Fi E’+TE’ T’*FT’ F(E) E’ε T’ε（2）判斷改寫后的文法是否為LL(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’