第5章自頂向下語(yǔ)法分析方法-全文預(yù)覽
【正文】 右看一個(gè)符號(hào) 便可決定如何推導(dǎo)（即選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)）。 FOLLOW(A) = {a|S ?A?且 a∈FRIST( ?), ?∈V T*,?∈V + } 若 S ?A?,且 ? ε，則規(guī)定 ∈ FOLLOW(A) 即： FOLLOW(A)={a|S … Aa… ,a ∈V T} 若 S …A ， 則規(guī)定 ∈ FOLLOW(A) 作為輸入串的結(jié)束符，或稱(chēng)為句子括號(hào)，如： 輸入串 * ? * ? * ? * ? * ? 調(diào)用返回 編譯原理 對(duì) A→ α， A→ β其中 A∈ VN , α, β ∈ VN*， 當(dāng) α和 β不同時(shí)推導(dǎo)出空時(shí)（設(shè) α不推導(dǎo)出空， β推導(dǎo)出空），則當(dāng)FIRST(α)∩(FIRST(β)∪ FOLLOW(A))=Φ時(shí)，對(duì)于非終結(jié)符 A的替換仍可唯一地確定候選。 ? 文法 G1[S]: S→pA S→qB A→cAd A→a B→dB B→b 編譯原理 ? 文法G2[S]: S→Ap S→Bq A→a A→cA B→b B→dB W=ccap自頂向下的推導(dǎo)過(guò)程： S ? Ap ? cAp ? ccAp ? ccap 語(yǔ)法樹(shù)： S A p S A p c A S A p c A c A S A p c A c A a 編譯原理 這個(gè)文法的特點(diǎn)： 1. 每個(gè)產(chǎn)生式的右部 不全是由 終結(jié)符號(hào) 開(kāi)始 。 2. 如果 兩個(gè)產(chǎn)生式 有相同的左部 ，那么它們的 右部由不同的 終結(jié)符開(kāi)始 。 ? 文法 G1[S]: S→Ap S→Bq A→a A→cA B→b B→dB 編譯原理 定義： 設(shè) G = (VT ,VN , S , P) 是上下文無(wú)關(guān)文法， FIRST(α) = {a|α aβ,a∈ VT,α ∈ V+, β ∈ V*,} 若 α ε， 則規(guī)定 ε∈ FIRST(α) * ? * ? 調(diào)用返回 編譯原理 ? FIRST(Ap)={a,c} ? FIRST(Bq)={b,d} ? 文法 G2[S]: S→Ap S→Bq A→a A→cA B→b B→dB 編譯原理 ? 文法 G3[S]: S→aA S→d A→bAS A→ε W=abd試圖 推導(dǎo)的過(guò)程： S ? aA ? abAS ? abS ? abd 編譯原理 定義：設(shè) G = (VT ,VN , S , P) 是上下文無(wú)關(guān)文法，A∈ VN , S是開(kāi)始符號(hào)。 第二個(gè) L表示：分析過(guò)程中將用 最左推導(dǎo) 。 編譯原理 ? 設(shè)文法 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)文法。若 X ? Y1Y2…YK 是一個(gè)產(chǎn)生式 ,Y1,Y2,…,Y(i1)都是非終結(jié)符 ,而且 ,對(duì)于任何 j,1≤ j ≤i 1,FIRST(Yj)都含有?(即 Y1..Y(i1) ? ),則把 FIRST(Yj)中的所有非 ?元素都加到 FIRST(X)中 。 ? Ａ → αB是一個(gè)產(chǎn)生式 ,或 Ａ → αBβ是 ?? 一個(gè)產(chǎn)生式而 β ?(即 ??FIRST(β )）， 則把FOLLOW（ A）， 加至 FOLLOW（ B） 中． * ? 編譯原理 S→AB S→bC A→ ε A→b B→ ε B→aD C→AD C→b D→aS D→c 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)= {} 編譯原理 SELECT集 S→AB S→bC A→ ε A→b B→ ε B→aD
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1