編譯原理ppt課件(參考版)
2025-05-06 01:55本頁面
【正文】 FOLLOW(S)={, a, b, c, d } 可構(gòu)造 LL(1)預(yù)測分析表如下： a b c d S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c ? (3)在分析表的控制下，句子 adccd的分析過程如下： 棧 當(dāng)前輸入符號 輸入串 說明S a dccd S →B AAB a dccd B →a AAAa a dccdAA d ccd A →dAd d ccdA c cd A →B SSB c cd B →cSc c cdS c d S →B AAB c d B →cAc c dA d A →dd d 分析成功a b c d S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c 。 FOLLOW(A)={a, b, c, d }。 FOLLOW(B)={a, b, c, d }。FIRST(S)={a, b, c}。→ ε17 練習(xí)一 ? 文法 G[V]： V→N | N[E] E→V | V+E N→i 是否為 LL(1)文法？若不是，如何改造成 LL(1)文法？ ? 解： ? LL(1)文法的基本條件是不含左遞歸和回溯（公共左因子）， 而 G[V]中含有回溯，所以先消除回溯得到文法 G’[V]： G’[V]： V→NV’ V’→ ε |[E]V’ E→VE’ E’→ ε |+EE’ N→i ? 由 LL(1)文法的充要條件可證 ? G’ [V]是 LL(1)文法 ? 文法 G[s]: S→BA A→BS|d B→aA|bS|c ? 證明文法 G是 LL(1)文法 ? 構(gòu)造 LL(1)分析表 ? 寫出句子 adccd的分析過程 ? 解： ? 一個 LL(1)文法的充要條件是 ?對每一個非終結(jié)符 A的任何兩個不同產(chǎn)生式 A→ α|β，有下面的條件成立 ?FIRST(α)∩FIRST(β)=Φ ? 若 β*?ε , 則有 FIRST(α)∩FOLLOW(A)=Φ 練習(xí)二（一） 練習(xí)二（二） ? 對于文法 G[s]: S→BA A→BS|d B→aA|bS|c ? FIRST集 ? FIRST(B)={a, b, c}。→ ε16 E39。T39。T39。T39。T i T →F T 39。11 E39。 +i E 39。 +i T39。T39。T39。 →* F T 39。T39。T39。T39。F i*+i T →F T 39。3 E39。 FOLLOW(T?) ∈ FOLLOW(F) ? 例 : 對于文法 G(E) E→TE ? E?→+TE ? | ? T→FT ? T?→*FT ? | ? F→(E) | i 構(gòu)造每個非終結(jié)符的 FIRST和 FOLLOW集合： FIRST(E) ={ (, i } FOLLOW(E) ={ ), } FIRST(E?)={ +, ? } FOLLOW(E?)={ ), } FIRST(T) ={ (, i } FOLLOW(T) ={ +, ), } FIRST(T?)={ *, ? } FOLLOW(T?)={ +, ), } FIRST(F) ={ (, i } FOLLOW(F) ={ *, +, ), } i + * ( ) E E → TE ? E → TE ? E ? E ?→ +TE ? E ?→ ? E ?→ ? T T → FT ? T → FT ? T ? T ?→ ? T ?→ * FT ? T ?→ ? T ?→ ? F F → i F → (E) LL(1)文法 ? 如果 文法 G是左遞歸或二義的 ，那么 分析表 M至少含有一個多重定義入口 ? 因此， 消除左遞歸 和 提取左因子 將 有助于獲得無多重定義的分析表 M ? 一個文法 ,若它的分析表 M不含多重定義入口 ,則稱它是一個 LL(1)文法 ? 一個文法 G的預(yù)測分析表 M不含多重定義入口，當(dāng)且僅當(dāng)該文法為 LL(1)的 一個文法 G為 LL(1)的，當(dāng)且僅當(dāng)對于文法 G中每一個非終結(jié)符 A的任何兩個產(chǎn)生式 A→ ? | ?，下面的條件成立： 1. FIRST(? )∩ FIRST(?)＝ ? 2. 若 ? ? (即 ??FIRST(?))，則 FIRST(? )∩ FOLLOW(A)= ? * ? LL(1)文法的條件 LL(1)分析中的錯誤處理 ? 發(fā)現(xiàn)錯誤 ?棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配 ?非終結(jié)符 A于棧頂，面臨的輸入符為 a，但分析表M的 M[A, a]為空 ? “應(yīng)急”恢復(fù)策略 ?跳過輸入串中的一些符號直至遇到“同步符號”為止 ? 同步符號的選擇 ?“ synch”表示由相應(yīng)非終結(jié)符的后繼符號集得到的同步符號 加入同步符號的 LL(1)分析表 ? 把 FOLLOW(A)中的所有符號作為 A的同步符號 FIRST(E) ={ (, i } FOLLOW(E) ={ ), } FIRST(E?)={ +, ? } FOLLOW(E?)={ ), } FIRST(T) ={ (, i } FOLLOW(T) ={ +, ), } FIRST(T?)={ *, ? } FOLLOW(T?)={ +, ), } FIRST(F) ={ (, i } FOLLOW(F) ={ *, +, ), } i + * ( ) E E → TE ? E → TE ? sy nch sy nch E ? E ?→ +T E ? E ?→ ? E ?→ ? T T → FT ? sy nch T → FT ? sy nch sy nch T ? T ?→ ? T ?→ * FT ? T ?→ ? T ?→ ? F F → i sy nch sy nch F → (E) sy nch sy nch 同步符號的選擇 ? 把 FOLLOW(A)中的所有符號作為 A的同步符號
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1