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

到LL(1)文法

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

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

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

S→Ap

S→Bp

A→a

A→cA

B→b

B→dBW=ccap

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

定義：設G=(VT,VN,S,P)是上下文無關文法，

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

若αε，則規定ε∈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}={b}=2lne6fjFirst集合例3：文法G[S]:

S→aA

S→d

A→bAS

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

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

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

ε，則規定#∈FOLLOW(A)

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

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

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

若S…A，則規定

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

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

給定上下文無關文法的產生式A→α，A∈VN,α∈V*，

若αε，則

SELECT(A→α)=First(α)

若αε，則

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

一個上下文無關文法是LL(1)文法的充要條件： 對每個VN，A的兩個不同產生式A→α，A→β， 滿足SELECT(A→α)∩SELECT(A→β)=φ 其中，α、β不能同時推導出ε。可使用“自頂向下分析”的文法稱為LL(1)文法。必須滿足的條件：LL(1)文法L：scanfromLeft從左向右掃描輸入串L：analyzefromLeft：分析過程是最左推導1：只需向右看一個符號便可以決定選擇哪個產生式進行推導。例4：判斷文法G[S]是否為LL(1)文法？G[S]: S→aAS S→b A→bA A→εLL(1)文法判別舉例解：Select(S→aAS)={a} Select(S→b)={b}Select(A→bA)={b}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)文法，不能用自頂向下分析技術。舉例：對輸入串ab進行推導就可能產生錯誤。5.2LL(1)文法的判別判別步驟：求出能推出ε的非終結符計算FIRST集計算FOLLOW集計算SELECT集判別是否是LL(1)文法例5：設文法G[S]為: S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

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

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

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

… first(Yi)∈first(X)當Y1,Y2,…Yn都能推導出ε時,則first(X)=(first(Y1)-{ε})∪(first(Y2)-{ε})∪…… ∪(first(Yn)-{ε})∪{ε}方法一：根據定義計算方法二：關系圖法（自學）定義：First(α)={a|αaβ,a∈VT,α,β∈V*}若αε，則ε∈First(α)First(S)=(First(A)-{ε})∪(First(B)-{ε})∪{ε}∪{b} ={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}First(AB)={a,b,ε} First(bB)={b}First(ε)={ε} First(b)={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集返回設S為開始符號，把{#}加入Follow(S)中（#為句子括號）若A→αBβ，則把First(β)–{ε}

加入Follow(B)中， 如果βε，則把Follow(A)也加入Follow(B)中。反復2，直到每個VN的Follow集不再增大為止。3.計算FOLLOW集方法一：根據定義計算方法二：關系圖法（自學）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定義：對于產生式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)={b}Select(Aε)=(First(ε)-{ε})∪Follow(A)={a,c,#}Select(Ab)=First(b)={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)={b}Select(D→aS)=First(aS)={a}Select(D→c)=First(c)={c}續上例：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)文法：左部相同的產生式的SELECT集的交集均為空。5.判別Select(SAB)={a,b,#}Select(SbC)={b}Select(Aε)={a,c,#}Select(Ab)={b}Select(Bε)={#}Select(B→aD)={a}Select(C→AD)={a,b,c} Select(C→b)={b}Select(D→aS)={a} Select(D→c)={c}S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c返回Select(SAB)∩Select(SbC)={b}≠φSelect(Aε)∩Select(Ab)=φSelect(Bε)∩Select(B→aD)=φSelect(C→AD)∩Select(C→b)={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)進一步變換(引入新非終結符A’)：AαA’A’β1|β2|…|βn注：若A’β1|β2|…|βn中仍含左公共因子，再次提取，直至所有的產生式不再有左公共因子。例6：文法G[S]為:S→aSbS→aSS→ε解：結論1：文法中不含左公共因子只是LL(1)文法的必要條件。即：

LL(1)文法一定不含左公共因子不含左公共因子的文法不一定是LL(1)文法SaS(b|ε)SεSaSbSaSSεSaSS’SεS’bS’εSaSS’S’b|εSε5.3.1.2提取隱含的左公共因子隱式變顯式：右部以VN開始的產生式，用該VN對應的產生式進行相應替換再用一般形式進行提取：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是多余產生式！S→aSA'S→bcA'→dA'→c5.3.1.3不能在有限步驟內提取完左公共因子的文法例8：文法G[S]為:S→ApS→BqA→aApA→dB→aBqB→eSaAppSdpSaBqqSeqAaApAdBaBqBeSa(App|Bqq)SdpSeqAaApAdBaBqBeSaS’S’AppS’BqqSdpSeqAaApAdBaBqBe繼續替換S’產生式右部的A和B，只能使產生式無限地增加下去。結論2：不是所有文法，都能在有限的步驟內提取完“左公共因子”。5.3.2消除左遞歸左遞歸的形式：直接左遞歸

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

A→Bβ

B→Aα A,BVN,α,βV*文法提取左公共因子后，并不一定是LL(1)文法。只有不含空產生式，且無左公共因子，且無左遞歸時，文法才是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’ε先把“間接左遞歸”變為“直接左遞歸”再將“直接左遞歸”化為“右遞歸”：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消除文法中一切左遞歸以某種順序將VN的排序為：A1，A2，…，Anfor(i=1;i<=n;i++){for(j=1;j<=i-1;j++)//以A1，…，Ai-1的產生式代入Ai產生式{若Aj的產生式為：Ajδ1|δ2|…|δk 則形如AiAjγ的產生式變為：Aiδ1γ|δ2γ|…|δkγ}

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

Q→Rb|b

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

Q→Rb|b

R→Sa|a解：終結符排序為：S,Q,R(1)對于S：無直接左遞歸（不用消除）(2)對于Q：右部不含S開頭的產生式 無直接左遞歸（不用消除）(3)對于R：右部含S開頭的產生式，則：

SQc QRb RQca Sc Qb Rca Ra 右部含Q開頭的產生式：

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

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

求各產生式的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’