第5章自頂向下語法分析方法-展示頁
2024-09-13 09:09本頁面
【正文】 ?A?,且 ? ε，則規(guī)定 ∈ FOLLOW(A) 即： FOLLOW(A)={a|S … Aa… ,a ∈V T} 若 S …A ， 則規(guī)定 ∈ FOLLOW(A) 作為輸入串的結(jié)束符，或稱為句子括號，如： 輸入串 * ? * ? * ? * ? * ? 調(diào)用返回 編譯原理 對 A→ α， A→ β其中 A∈ VN , α, β ∈ VN*， 當(dāng) α和 β不同時推導(dǎo)出空時（設(shè) α不推導(dǎo)出空， β推導(dǎo)出空），則當(dāng)FIRST(α)∩(FIRST(β)∪ FOLLOW(A))=Φ時，對于非終結(jié)符 A的替換仍可唯一地確定候選。 3. 文法中無空產(chǎn)生式。 ? 文法 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)過程： S ? Ap ? cAp ? ccAp ? ccap 語法樹： S A p S A p c A S A p c A c A S A p c A c A a 編譯原理 這個文法的特點： 1. 每個產(chǎn)生式的右部 不全是由 終結(jié)符號 開始 。編譯原理 第 5章 自頂向下語法分析方法 確定的自頂向下分析思想 LL(1)文法的判別 某些非 LL(1)文法到 LL(1)文法的等 價變換 不確定的自頂向下分析思想 確定的自頂向下分析方法 返回目錄 編譯原理 確定的自頂向下分析思想 ? 文法G1[S]: S→pA S→qB A→cAd A→a B→dB B→b W=pccadd自頂向下的推導(dǎo)過程： S ? pA ? pcAd ? pccAdd ? pccadd 語法樹： S p A S p A c A d S p A c A d c A d S p A c A d c A d a 編譯原理 這個文法的特點： 1. 每個產(chǎn)生式的右部都 由 終結(jié)符號 開始 。 2. 如果 兩個產(chǎn)生式 有相同的左部 ，那么它們的 右部由不同的 終結(jié)符開始 。 2. 如果 兩個產(chǎn)生式 有相同的左部 ，那么它們的 右部由不同的 終結(jié)符 或 非終結(jié)符開始 。 ? 文法 G1[S]: S→Ap S→Bq A→a A→cA B→b B→dB 編譯原理 定義： 設(shè) G = (VT ,VN , S , P) 是上下文無關(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)的過程： S ? aA ? abAS ? abS ? abd 編譯原理 定義：設(shè) G = (VT ,VN , S , P) 是上下文無關(guān)文法，A∈ VN , S是開始符號。 編譯原理 定義：給定上下文無關(guān)文法的產(chǎn)生式 A→ α，A∈ VN , α∈ V*， 若 α ε， 則 SELECT(A→ α)=FIRST(α) 如果 α ε， 則SELECT(A→α) =FIRST(α)∪ FOLLOW(A) * ? * ? 調(diào)用返回 編譯原理 定義：一個上下文無關(guān)文法是 LL(1)文法的充要條件是： 對每個非終結(jié)符 A的兩個不同產(chǎn)生式A→ α和 A→ β， 滿足 SELECT(A→ α)∩SELECT(A→ β)=Φ 其中 α,β不同時能 ε。 第二個 L表示：分析過程中將用 最左推導(dǎo) 。 類似也可以有 LL(K)文法：需向前查看 K個符號才可確定選用哪個產(chǎn)生式。 編譯原理 ? 設(shè)文法 G[S] 為 : S→aAS S→b A→bA A→ ε SELECT(S→aAS) ={a} SELECT(S→b) = SELECT(A→bA) = SELECT(A→ ε) ={a,b,ε} SE
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1