【正文】 生式A→ab 的右部還是用 A→a 的右部去替換。所以導(dǎo)致必須用帶回溯的自頂向下分析 ， 這是一個(gè)不確定的分析 文法含有左遞歸，可見(jiàn)一個(gè)文法含有左遞歸時(shí)不能用確定的自頂向下分析 文法含有左遞歸，一個(gè)文法含有左遞歸時(shí)不能用確定的自頂向下分析。由以上例子可以看出，例 ～例 的自頂向下分析 , 可用帶回溯的自頂向下分析。 LL(1) 文法的定義和判別 由 1～例 6可知， 一個(gè)文法能否用確定的自頂向下分析與文法中相同左部的每個(gè)產(chǎn)生式右部的開(kāi)始符號(hào)集合有關(guān)，當(dāng)某個(gè)非終結(jié)符能推出 ε 時(shí)則與該非終結(jié)符的后跟符號(hào)集合也有關(guān)。綜合以上兩點(diǎn)，即一個(gè)文法能否用確定的自頂向下分析與產(chǎn)生式的 Select集有關(guān)。此外在產(chǎn)生式中不存在左遞歸。 ? 定義 一個(gè)上下文無(wú)關(guān)文法是 LL(1)文法的充分必要條件是：對(duì)每個(gè)非終結(jié)符 A的兩個(gè)不同產(chǎn)生式， A→ α, A→ β,滿足SELECT(A→ α)∩ SELECT(A→ β)=? 其中 α， β不同時(shí)能 ε LL(1) 文法的定義 LL(1)文法的含義： 第一個(gè) L 從左到右掃描輸入串 第二個(gè) L 生成的是最左推導(dǎo) 1 向右看一個(gè)輸入符號(hào)便可 決定選擇哪個(gè)產(chǎn)生式。 例：判斷下列文法是否是 LL(1)文法 G： S→ aA S→ d A→ bAS A→ ε 解： select(S→ aA)={a} select(S → d)=nhcuj7d3 select (S→ aA)∩ select(S → d)=216。 select(A→ bAS)= select(A→ ε) ={First(ε){ε}}∪ Follow(A) =Follow(A)={a,d,} select (A→ bAS)∩ select(A → ε)=216。 所以，該文法是 LL（ 1）文法。 例：判斷下列文法是否是 LL(1)文法 文法 G [S]為： S→aAS S→b A→bA A→ε 例 文法 G [S]為： S→aAS S→b A→bA A→ε 則 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)文法，因而也就不可能用確定的自頂向下分析。 LL(1)文法的判別 當(dāng)我們需選用自頂向下分析技術(shù)時(shí)，首先必 須判別所給文法是否是 LL(1)文法。因而我 們對(duì)任給文法需計(jì)算 FIRST、 FOLLOW、 SELECT集合，進(jìn)而判別文法是否為 LL(1)文 法。 若 X∈ VN； Y1， Y2， … ， Yi∈ VN，且有產(chǎn)生式 X→Y1 Y2 … Yn ；當(dāng) Y1 Y2 … Yi 1都 ε時(shí)， (其中 1≤i≤n)，則 FIRST(Y1)、FIRST(Y2)、 … 、 FIRST(Yi1)的所有非空元素和 FIRST(Yi)都包含在FIRST(X)中。 當(dāng) (4)中所有 Yi ε,(i=1,2,…n) ，則 FIRST(X)=(FIRST(Y1)－ {ε} ） ∪ （ FIRST(Y2)－ {ε} ） ∪ … ∪ （ FIRST(Yn) － {ε} ） ∪ {ε} 反復(fù)使用上述 (2)～ (5)步直到每個(gè)符號(hào)的 FIRST集合不再增大為止。 例 文法 G [S]為： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 求每個(gè)終結(jié)符的 First集。 例 文法 G [S]為： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c FIRST(S)={FIRST(A)－ {ε}}∪ {FIRST(B)－ {ε}}∪ {ε}∪ ={b,a,ε} FIRST(A)=∪ {ε}={ b,ε} FIRST(B)＝ {ε}∪ {a}＝ {a,ε} FIRST(C)={FIRST(A) － {ε}}∪ FIRST(D)∪ FIRST(b)={b,a,c} FIRST(D)={a}∪ {c}={a,c} 也可以由關(guān)系圖法求文法符號(hào)的 FIRST集，可作為一種驗(yàn)證。其方法為： (a) 每個(gè)文法符號(hào)對(duì)應(yīng)圖中一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)終結(jié)符的結(jié)點(diǎn)時(shí)用符號(hào)本身標(biāo)記，對(duì)應(yīng)非終結(jié)符的結(jié)點(diǎn)用 FIRST(A)標(biāo)記。這里 A表示非終結(jié)符。 (b) 如果文法中有產(chǎn)生式 A→αXβ ，且 α ε, 則從對(duì)應(yīng) A的結(jié)點(diǎn)到對(duì)應(yīng) X的結(jié)點(diǎn)連一條箭弧。 (c) 凡是從 FIRST(A)結(jié)點(diǎn)有路徑可到達(dá)的終結(jié)符結(jié)點(diǎn)所標(biāo)記的終結(jié)符都為 FIRST(A)的成員。 (d) 由 ε 是否為某非終結(jié)符 FIRST集的成員，若是則將 ε 加入該非終結(jié)符的 FIRST集中。 文法 G [S]為： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c FIRST(S)={b,a,ε} FIRST(A)={b,ε} FIRST(B)={a,ε} FIRST(C)={a,b,c} FIRST(D)={a,c} 計(jì)算 FOLLOW集 根據(jù)定義計(jì)算 對(duì)文法中每一 A∈ VN 計(jì)算 FOLLOW(A) (a) 設(shè) S為文法中開(kāi)始符號(hào)，把 {}加入 FOLLOW(S)中 (這里“ ” 為句子括號(hào) )。 (b) 若 A→αBβ 是一個(gè)產(chǎn)生式，則把 FIRST(β)的非空元素加入 FOLLOW(B)中。 如果 β ε則把 FOLLOW(A)也加入 FOLLOW(B)中。 (c) 反復(fù)使用 (b)直到每個(gè)非終結(jié)符的 FOLLOW集不再增大為止。 例：文法 G [S]為： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 求每個(gè)非終結(jié)符的 Follow集。 文法 G [S]為： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 解： FOLLOW(S)={}∪ FOLLOW(D) ＝ {} FOLLOW(A)=(FIRST(B) － {ε}) ∪ FOLLOW(S) ∪ FIRST(D) ＝ {a,c} FOLLOW(B)=FOLLOW(S)={} FOLLOW(C)=FOLLOW(S)={} FOLL