第四章自頂向下的語法分析(編輯修改稿)
2024-11-16 11:25 本頁面
【文章內容簡介】 hen FIRST(X):=FIRST(X)∪ {ε}。 2020/11/17 20 LL(1)文法的判定 算法 計算 FIRST(α)。 輸入：文法 G=(V， T， P， S)， α?(V∪ T)*， α= X1… Xn。 輸出： FIRST(α)。 步驟： 1．計算 FIRST(X1)。 2． FIRST(α):= FIRST(X1){ε}。 3． k:=1。 4． while (ε∈ FIRST(Xk) and kn) do begin 5． FIRST(α):= FIRST(α)∪ (FIRST(Xk+1){ε})。 6． k:=k+1 end 7． if (k=n and ε∈ FIRST(Xk)) then FIRST(α):=FIRST(α)∪ {ε}。 2020/11/17 21 例 表達式文法的語法符號的 FIRST 集 FIRST(F)={（ , id} FIRST(T)=FIRST(F)={（ , id} FIRST(E)=FIRST(T)={（ , id} FIRST(E39。)={+， ε} FIRST(T39。)={*,ε} FIRST(+)={+}, FIRST(*)={*} FIRST(（ )={（ } FIRST(） )={） } FIRST(id)={id} E→TE39。 E39?！?TE’|ε T→FT39。 T39?！?FT’|ε F→(E)|id 2020/11/17 22 LL(1)文法的判定 算法 計算 FOLLOW集。 輸入：文法 G=(V， T， P， S)， A?V。 輸出： FOLLOW(A)。 步驟： 1．對 ?X∈ V， FOLLOW(X) := ?。 2． FOLLOW(S) := {}， 為句子的結束符 。 3．對 ?X∈ V，重復下面的第 4步到第 5步，直到所有FOLLOW集不變?yōu)橹埂? 4．若 A→αBβ∈ P，則FOLLOW(B):=FOLLOW(B)∪ FIRST(β)–{ε}。 5．若 A→αB或 A→αBβ∈ P，且 β ε， A≠B，則 FOLLOW(B):=FOLLOW(B)∪ FOLLOW(A)。 *?2020/11/17 23 例 表達式文法的語法變量的 FOLLOW 集 FOLLOW(E) = { , ) } FOLLOW(E39。)= FOLLOW( E ) = { , ) } FOLLOW(T) = {FIRST(E39。){ε}}∪ FOLLOW(E)∪ FOLLOW(E39。)= {+,),} FOLLOW(T39。)= FOLLOW(T)= {+,),} FOLLOW(F) = FIRST(T’)∪ FOLLOW(T)∪ FOLLOW(T39。) ={*,+,),} E→TE39。 E39?！?TE39。|ε T→FT39。 T39。→*FT39。|ε F→(E)|id FIRST(F)={（ ,id} FIRST(T)=FIRST(F)={（ ,id} FIRST(E)=FIRST(T)={（ ,id} FIRST(E39。)={+， ε} FIRST(T39。)={*,ε} 2020/11/17 24 表達式文法是 LL(1) 文法 ? E → T E39。 ? E39?！?+ T E39。 ｜ ε ? T → F T39。 ? T39?！?* F T39。 ｜ ε ? F → ( E ) ｜ id 考察 ? E39。 : + 不在 FOLLOW( E39。 ) = { ), } ? T39。 : * 不在 FOLLOW( T39。 ) = { +, ), } ? F: ( 和 id 不同 2020/11/17 25 非 LL(1)文法的不確定性 例 對文法 ? S→cAd ? A→ab|a 輸入 cad 的分析 S d c A b a S d c A a 2020/11/17 26 不確定性的解決方法 1) 采用回溯算法 ? 過于復雜，效率低下 2）改寫文法 ? 將非 LL(1)文法改寫為等價的 LL(1)文法 ? 無法改寫時： ? 增加其它的判別因素 ? 文法過于復雜，無法用自頂向下方法處理 2020/11/17 27 預測分析法 ? 系統(tǒng)維持一個分析表和一個分析棧，根據(jù)當前掃描到的符號，選擇當前語法變量（處于棧頂）的候選式進行推導 ——希望找到相應輸入符號串的最左推導。 ? 一個通用的控制算法 ? 一個分析棧， 為棧底符號 ? 一個輸入緩沖區(qū)， 為輸入串結束符 ? 一個統(tǒng)一形式的分析表 M ? 不同語言使用內容不同的分析表 2020/11/17 28 預測分析器的構成 輸入緩沖區(qū) (符號序列 ) 棧 預測分析程序 預測分析表 M 輸出的 產生式序列 2020/11/17 29 系統(tǒng)的執(zhí)行與特點 ? 在系統(tǒng)啟動時，輸入指針指向輸入串的第一個字符，分析棧中存放著棧底符號 和文法的開始符號。 ? 根據(jù)棧頂符號 A和讀入的符號 a，查看分析表 M,以決定相應的動作。 ? 優(yōu)點： 1）效率高 2）便于維護、自動生成 ? 關鍵 —— 分析表 M的構造 2020/11/17 30 預測分析程序的總控程序 算法 預測分析程序的總控程序。 輸入：輸入串 w和文法 G=(V, T, P, S)的分析表 M。 輸出：如果 w屬于 L(G)，則輸出 w的最左推導，否則報告錯誤 。 步驟： 1．將棧底符號 和文法開始符號 S壓入棧中 。 2． repeat 3． X:=當前棧頂符號 。 4． a:=當前輸入符號 。 5． if X∈ T∪ {} then 6． if X=a then 7． {if X≠ then begin 8． 將 X彈出棧 。 9． 前移輸入指針 10． end} 2020/11/17 31 預測分析程序的總控程序 11． else error 12． else 13． if M[X, a]=Y1Y2… Yk then begin 14． 將 X彈出棧 。 15． 依次將 Yk， … ， Y2，
教學課件相關推薦
鄂ICP備17016276號-1