程序設計語言編譯原理第三版第4章(編輯修改稿)
2025-02-02 18:29 本頁面
【文章內容簡介】 1)分析法 構造不帶回溯的自上而下分析的文法的條件： （ 1）文法 不含左遞歸 。 （ 2）文法中每一個非終結符 A的各個產(chǎn)生式的候選首符集 兩兩不相交 即：若 A?α 1|α 2|… |α n 則 first(α i)∩first(α j)=Φ （ｉ ≠ ｊ） (3) 對文法中的每個非終結符Ａ，若它存在 某個候選首符 集包含 ? ，則 first(A)∩follow(A)= Φ 若一個文法 G滿足以上條件 ,則稱該文法 G為 LL(1)文法 . (1)文法的自上而下分析 (有效的無回溯的 ) 分析： A?α 1|α 2|… |α n 167。 LL(1)分析法 對非終結符 A進行匹配 ,此時面臨的輸入符號為 a: (1)若 a∈first( α i ),則指派 α i去執(zhí)行匹配任務 。 (2)若 a不屬于任何一個候選首符集 ,則 ① 若 ?∈first( α i ),且 a∈follow(A), 則讓 A與 ?自動匹配 。 ② 否則 ,a的出現(xiàn)是一種語法錯誤 . 一 .實現(xiàn)思想 對應文法中每個非終結符編寫一個遞歸過程 ,每個過程 的 功能 是 識別由該非終結符推出的串 ,當某非終結符的產(chǎn)生 式有多個侯選時能夠按 LL(1)形式可唯一地確定選擇某個侯 選進行推導 . 167。 遞歸下降分析程序構造 二 .基本構造方法 :對文法的 每個非終結符號 ,都根據(jù)其產(chǎn)生式 的各個候選式的結構 ,為其 編寫一個對應的子程序 (或函數(shù) ), 該子程序完成相應的非終結符對應的語法成分的識別和分 析任務 . 對某個非終結符 ,用規(guī)則的右部符號串去匹配輸入串 .分析 過程是按文法規(guī)則自上而下一級一級地 調用有關子程序 來完成 . ?167。 遞歸下降分析程序構造 (1)Advance/Sym/IP (2)圖 (1){ } * (2){ }n0 可重復 0次或任意次 . (3)[ ] ∣ ????? ?167。 遞歸下降分析程序構造 三 .優(yōu)缺點分析 :簡單直觀 ,易于構造 . :(1)對文法要求高 ,必須滿足 LL(1)文法 。 (2)由于遞歸調用多 ,所以速度慢占用空間多 . 應用舉例 : Pascal, C語言 預測分析器模型 167。 預測分析程序 167。 預測分析程序 —— M[A,a]形式的矩陣表示 矩陣元素 M[A,a]存放內容： 一條 A的 產(chǎn)生式 或 出錯標志 ； 矩陣元素 — 實際是 相應的分析動作 （即所選用的推導的產(chǎn)生式）。 —— 用于存放 分析過程中的文法符號 。 功能： 依據(jù) 分析表 和 分析棧 聯(lián)合控制 輸入字符串 的 識別和分析 ， 它在 任何時候 都是 根據(jù) 當前分析棧的 棧頂符號 X和當前的 輸入字符 a來 執(zhí)行控制功能 。 167。 預測分析程序 二 . 預測分析表的構造 一 . 預測分析程序工作過程 一、預測分析程序工作過程 167。 預測分析程序 (1)初始化 :依次把 ’ ’和文法開始符號壓入分析棧 , 將輸入串第一個符號讀入 a。 167。 預測分析程序 (2)若 X∈V T ① X＝ a≠ ””, 則 將 X從分析棧頂 退掉 , a指向下一個輸入字符 。 (3)若 X∈V N , 則查分析表 . 此時對 M[X,a]: ② X＝ a＝ ” ”, 表示分析成功 ,停止分析過程 。 ③ X≠ a ,表示不匹配的出錯情況 . ① 若 M[A, a]={ X→X1X2… X k },則 將 X從棧中彈出并將 Xk,Xk1,… ,X1一一推進棧 。 ② 若 M[A, a]中為 空白 ,則 表示出錯 ,可 調用語法出錯處理子程序 . 下面用預測分析方法對輸入串 i+i*i 進行分析，給出棧的變化過程如下： 步驟 分析棧 剩余輸入串 所用產(chǎn)生式 2 E?T i+i*i E?TE? T?FT ? 1 E i+i*i
范文總結相關推薦
鄂ICP備17016276號-1