《編譯原理 緒論》PPT課件

《《編譯原理 緒論》PPT課件》由會員分享，可在線閱讀，更多相關《《編譯原理 緒論》PPT課件（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1 編 譯 原 理 2 題 外 話 一 、 本 課 程 討 論 的 領 域 和 希 望 達 到 的 目 的1 2 CCC 2002 中 國 計 算 機 科 學 與 技 術 學 科 專 業(yè) 發(fā) 展 戰(zhàn) 略 研 究 報 告 與 專 業(yè) 規(guī) 范（ 試 行 ） 提 出 了 計 算 機 科 學 與 技 術 學 科 的 知 識 體 系 ， 包 括 了 141個 基本 的 知 識 領 域 。 與 本 課 程 相 關 的 ： 1 程 序 設 計 基 礎 （ PF） ： 程 序 設 計 基 本 結 構 、 算 法 與 問 題 求 解 、基 本 數(shù) 據(jù) 結 構 、 遞 歸 、 事 件 驅(qū) 動 程 序 設 計 。

2、（ PLA） 2 程 序 設 計 語 言 （ PL） ： 程 序 設 計 語 言 概 論 、 虛 擬 機 、 語 言 翻譯 簡 介 、 聲 明 和 類 型 、 抽 象 機 制 、 面 向 對 象 程 序 設 計 （ 以 上 是 核 心 ） ； 函 數(shù) 程 序 設 計 、 語 言 翻 譯 系 統(tǒng) 、 類 型 系 統(tǒng) 、 程 序 設 計 語 言 的語 義 、 程 序 設 計 語 言 的 設 計 （ 以 上 是 選 修 ） 。 （ PLA、 PLT、 PLD） 1 1 領 域程 序 設 計 語 言 的 應 用 程 序 設 計 （ PLA）程 序 設 計 語 言 的 翻 譯 編 譯 器 的 構 造 （

3、 PLT）程 序 設 計 語 言 的 設 計 語 法 、 語 義 （ PLD） 3 題 外 話 （ 續(xù) 1）1 3 目 的1 了 解 PL的 基 本 要 素 、 工 作 原 理 、 語 言 翻 譯 的 基 本 方 法 ；2 用 不 同 的 PL進 行 程 序 設 計 ， 即 自 學 計 算 機 語 言 的 能 力 ；3 具 備 語 言 翻 譯 的 基 本 技 能 。二 、 學 習 方 法 2 1 本 課 程 的 特 點 理 論 與 實 踐 并 重 理 論 學 習 要 嚴 謹 、 方 法 掌 握 要 靈 活 提 高 自 學 能 力 （ push與 pull）2 2 理 論 與 技 術 的 關 系

4、 適 應 飛 速 變 化 的 技 術 的 根 本 是 注 重 基 礎 理 論 學 習 理 論 的 演 變 是 緩 慢 的 、 理 論 基 礎 是 相 通 的 相 同 的 原 理 可 以 應 用 于 不 同 的 技 術 4 題 外 話 （ 續(xù) 2）2 3 勤 動 手 、 多 實 踐 、 提 高 學 習 能 力 學 到 的 知 識 是 死 的 ， 總 有 過 時 的 時 候 。 只 有 通 過 學 習 知 識提 高 學 習 能 力 ， 才 是 立 于 不 敗 之 地 的 保 證 。 記 筆 記 ： 好 記 性 不 如 爛 筆 頭 ， 通 過 動 手 加 深 理 解 和 記 憶 。 做 作 業(yè) 、

5、做 上 機 題 ： 自 己 動 手 為 主 ， 參 考 “ 解 答 ” 為 輔 。 2 4 如 何 使 用 習 題 與 上 機 題 解 答 合 理 利 用 “ 解 答 ” 有 助 于 課 程 學 習 。 “ 解 答 ” 既 不 完 全 正確 也 不 是 最 好 的 。 習 題 解 答 ： 先 做 作 業(yè) ， 后 看 解 答 。 如 不 符 ， 思 考 原 因 ， 找出 最 好 答 案 。 上 機 解 答 ： 先 看 題 目 要 求 ， 根 據(jù) 要 求 自 己 設 計 并 實 現(xiàn) 。 如有 困 難 ， 部 分 參 考 解 答 。 提 倡 獨 立 思 考 ， 對 發(fā) 現(xiàn) 解 答 錯 誤 并 給 出

6、 正 確 解 法 、 做 出 選做 題 和 上 機 題 擴 充 部 分 者 ， 給 予 加 分 獎 勵 。 （ 只 給 第 一 組 ， 寫 明 姓 名 、 日 期 。 加 分 按 人 平 分 ） 根 據(jù) 需 要 上 習 題 課 。 5 題 外 話 （ 續(xù) 3）三 、 其 他3 1 課 代 表 與 輔 導 課 代 表 的 職 責 ： 收 繳 作 業(yè) ； 安 排 上 機 時 間 、 聯(lián) 系 上 機 事 宜 ；反 映 同 學 意 見 ； 監(jiān) 督 老 師 的 工 作 。 輔 導 時 間 ： 每 周 一 次 ， 課 代 表 與 同 學 商 量 后 確 定 。3 2 作 業(yè) 與 上 機 作 業(yè) 第 二 、

7、 五 章 收 繳 一 次 ， 第 三 、 四 章 收 繳 兩 次 。 有 獨 立 見 解 的可 直 接 交 給 主 講 老 師 ， 包 括 指 出 解 答 的 錯 誤 并 給 出 正 確 答 案 、選 做 題 答 案 等 。 （ 僅 以 第 一 個 收 到 的 為 準 ， 包 括 上 屆 ） 驗 收 上 機 題 ， 并 收 繳 上 機 報 告 。 報 告 內(nèi) 容 根 據(jù) 個 人 對 題 目 要求 的 理 解 寫 。 6 題 外 話 （ 續(xù) 4）中 文 ： 清 華 大 學 出 版 社 ， 呂 映 芝 等 ， “ 編 譯 原 理 ” 國 防 工 業(yè) 出 版 社 ， 陳 火 旺 等 ， “ 程 序

8、設 計 語 言 編 譯 原 理 ”（ 第 三 版 ） 西 北 工 業(yè) 大 學 出 版 社 ， 蔣 立 源 等 ， “ 編 譯 原 理 ”3 3 參 考 書 目英 文 ： 人 民 郵 電 出 版 社 ， Aho等 ， “ 編 譯 原 理 技 術 與 工 具 ” （ 影 印版 ） 高 等 教 育 出 版 社 ， Andrew W.Appel， “ 現(xiàn) 代 編 譯 程 序 實 現(xiàn) Java語 言 ” （ 影 印 版 ） 機 械 工 業(yè) 出 版 社 ， Steven S.Muchnick， “ 高 級 編 譯 器 設 計與 實 現(xiàn) ” （ 影 印 版 ） 清 華 大 學 出 版 社 ， Hopcrof

9、t等 ， “ 自 動 機 理 論 、 語 言 和 計 算 機 導 論 ” （ 影 印 版 ） 7 3 3 參 考 書 目Computer Systems: A Programmers Perspective作者： Randal E.Bryant; David OHallaron深入理解計算機系統(tǒng) 譯者：龔奕利，雷迎春 翻譯版 8 第 一 章 引 言 1.1 從 面 向 機 器 的 語 言 到 面 向 人 類 的 語 言面 向 機 器 的 語 言 ： 機 器 指 令 、 匯 編 語 言面 向 人 類 的 語 言 ： 通 用 程 序 設 計 語 言 、 非 過 程 式 語 言 ， 等 等例 1 :

10、 通 用 程 序 設 計 語 言 與 匯 編 語 言 （ 包 括 機 器 指 令 ） Pascal語 句 ： x := a+b；C+語 句 ： x = a+b；匯 編 指 令 ： 十 六 進 制 代 碼 匯 編 指 令A10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX 計 算 機 語 言 舉 例 9 計 算 機 語 言 舉 例 （ 續(xù) 1）給 出 003號 學 生 所 選 課 程 與 成 績 :Select 學 號 ,姓 名 ,課 程 名 ,成 績 from 學 生 ,選 課 where 學 生 .學 號 =

11、“ 003” ;例 2 SQL 學 生 ： 選 課 ：學 號 姓 名 性 別001 張 梧 男002 李 煦 男003 王 沁 女004 劉 荔 女 學 號 課 程 代 碼 課 程 名 成 績001 0104 離 散 數(shù) 學 80001 0205 數(shù) 據(jù) 結 構 90003 0104 離 散 數(shù) 學 85003 0205 數(shù) 據(jù) 結 構 95學 號 姓 名 課 程 名 成 績003 王 沁 離 散 數(shù) 學 85003 王 沁 數(shù) 據(jù) 結 構 95 10 計 算 機 語 言 舉 例 （ 續(xù) 2）例 3： LEX的 正 規(guī) 式 ： char(char|digit)* return idYacc的

12、產(chǎn) 生 式 ： E : E + E | E * E | id 例 4： Unix的 shell命 令SHELL=/bin/sh# include env_precomp.mkCPDIR = /u/pbsrc/chpORAHOME = /oracle/app/oracle/product/734. 11 按 范 型 劃 分 的 程 序 設 計 語 言CCC2002 PL：1. Simple Procedural Languages： FORTRAN C 2. Block-Structured Procedural Languages： Pascal3. Object-Based Language

13、s： Ada C+ Smalltalk4. Functional Languages： LISP ML Haskell OCaml5. Logic Programming Languages： Prolog 清 華 大 學 出 版 社 ， Terrence W.Pratt等 ， PROGRAMMING LANGUAGES Design and Implementation(影 印 版 )1. 過 程 式 語 言 、 面 向 對 象 語 言 ： 通 用 程 序 設 計 語 言 ， 包 括FORTRAN、 Pascal、 C/C+、 Ada83/Ada95、 Java等 ；2. 函 數(shù) 語 言 ：

14、 面 向 特 點 領 域 的 、 遞 歸 特 性 ， 典 型 代 表 ： Lisp；3. 說 明 性 、 非 算 法 式 語 言 ： 濃 厚 的 數(shù) 學 特 征 ， 典 型 代 表 ：LEX/YACC、 SQL； 4. 腳 本 式 語 言 ： 僅 是 一 種 安 排 ， 沒 有 復 雜 的 邏 輯 關 系 ， 典 型 代表 ： shell語 言 。 12 其 他 面 向 特 定 應 用 領 域 的 語 言1 互 連 網(wǎng) 應 用 ： HTML、 XML2 計 算 機 輔 助 設 計 ： MATLAB3 集 成 電 路 設 計 ： VHDL、 Verilog4 虛 擬 現(xiàn) 實 與 人 機 交 互

15、： VRML問 題 ： 如 何 將 形 形 色 色 的 語 言 翻 譯 成 可 以 在 計 算 機 上 運 行 的 0、 1串 13 1.2 語 言 之 間 的 翻 譯 習 慣 稱 法 ： 匯 編 語 言 機 器 指 令 ： 匯 編 （ 或 交 叉 匯 編 ） 程 序 設 計 語 言 匯 編 語 言 或 機 器 指 令 ： 編 譯 （ 或 解 釋 ） 高 級 語 言 之 間 ： 轉 換 （ 或 預 編 譯 ） 逆 向 ： 反 匯 編 、 反 編 譯 14 1.3 編 譯 器 與 解 釋 器 語 言 翻 譯 的 兩 種 基 本 形 態(tài)1.先 翻 譯 后 執(zhí) 行 2. 邊 翻 譯 邊 執(zhí) 行 例

16、5 假 設 有 源 程 序 ： read(x); write(x=, x); 15 1.3 編 譯 器 與 解 釋 器 （ 續(xù) ）1. 特 點 ： 編 譯 器 ： 工 作 效 率 高 ， 即 時 間 快 、 空 間 省 ； 交 互 性 與 動態(tài) 特 性 差 、 可 移 植 性 差 。 大 多 數(shù) PL采 用 此 方 法 翻 譯 ； 解 釋 器 ： 工 作 效 率 低 ， 即 時 間 慢 、 空 間 費 ； 交 互 性 與 動態(tài) 特 性 好 、 可 移 植 性 好 。 早 期 的 Basic和 Java等 ；2. 基 本 功 能 ： 二 者 相 同 ；3. 所 采 用 的 技 術 ： 從 翻 譯

17、 的 角 度 來 講 ， 兩 種 方 式 所 涉 及 的 原理 、 方 法 、 技 術 相 似 。 16 1.4 編 譯 器 的 工 作 原 理 與 基 本 組 成1.4.1 通 用 程 序 設 計 語 言 的 主 要 成 份1 從 語 言 抽 象 的 演 變 看 ：過 程 抽 象 數(shù) 據(jù) 類 型 （ ADT， 程 序 包 ） 類2 共 同 特 點 ： 兩 大 部 分 組 成 ： 聲 明 操 作 完 整 定 義3 以 過 程 式 語 言 為 例 ：聲 明 性 語 句 ： 提 供 操 作 對 象 的 性 質(zhì) ， 如 數(shù) 據(jù) 類 型 、 值 、 作 用 域 等 ；操 作 性 語 句 ： 確 定 操

18、 作 的 計 算 次 序 ， 完 成 實 際 操 作 。過 程 頭 過 程 體 過 程 定 義 4 編 譯 器 對 兩 類 語 句 的 翻 譯 ： 聲 明 ： 生 成 相 應 的 環(huán) 境 ， 一 般 是 配 置 存 儲 空 間 。 操 作 ： 生 成 可 執(zhí) 行 的 代 碼 序 列 。 例 6 一 個 Pascal過 程 17 1.4.2 以 階 段 劃 分 編 譯 器 1 自 然 語 言 的 翻 譯 過 程 ：識 別 單 詞識 別 句 子 結 構理 解 意 思譯 成 中 文 并 修 飾 2 編 譯 器 的 工 作 過 程 ：詞 法 分 析 語 法 分 析語 義 分 析目 標 代 碼 生 成3

19、 編 譯 器 的 階 段 （ 邏 輯 模 塊 劃 分 ）4 中 間 代 碼 的 重 要 作 用 18 1.4.3 編 譯 器 各 階 段 的 工 作例 7 Pascal源 程 序 語 句 如 下 ： var x, y, z : real; x := y + z * 60;（ 源 程 序 ） var x, y, z : real; x := y + z * 60; （ 記 號 流 ） var id1, id2, id3 : real; id1 := id2+id3*60; （ 語 法 樹 ） 19 1.4.3 編 譯 器 各 階 段 的 工 作 （ 續(xù) 1） 中 間 代 碼 的 形 式 與 作

20、用 ：(序 號 )(op， arg1, arg2, result) result := arg1 op arg2 (1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) 20 1.4.3 編 譯 器 各 階 段 的 工 作 （ 續(xù) 2）(1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) (1) (*, id3, 60.0, T1)(2) (+, id2, T1, id1) MOVF id3

21、, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1 MOVF R1, id1 R2 := id3R2 := R2 * 60.0R1 := id2R1 := R1 + R2id1 := R1id1 := id2 + id3 * 60.0 x := y + z * 60; 21 1.4.3 編 譯 器 各 階 段 的 工 作 （ 續(xù) 3）各 階 段 工 作 的 歸 納 1. 詞 法 分 析 ： 識 別 單 詞 ， 至 少 分 以 下 幾 大 類 ： 關 鍵 字 （ 保 留 字 ） 、標 識 符 、 字 面 量 、 特 殊 符 號 ；2. 語 法 分 析 ： 得 到

22、語 言 結 構 并 以 樹 的 形 式 表 示 ；3. 語 義 分 析 ： 考 察 結 構 正 確 的 句 子 是 否 語 義 合 法 ， 修 改 樹 結 構 ；4. 中 間 代 碼 生 成 （ 可 選 ） ： 生 成 一 種 既 接 近 目 標 語 言 ， 又 與 具 體機 器 無 關 的 表 示 ， 便 于 優(yōu) 化 與 代 碼 生 成 ； （ 到 目 前 為 止 ， 編 譯 器 與 解 釋 器 可 以 一 致 ） 5. 中 間 代 碼 優(yōu) 化 （ 可 選 ） :局 部 優(yōu) 化 、 循 環(huán) 優(yōu) 化 、 全 局 優(yōu) 化 等 ； 優(yōu)化 實 際 上 是 一 個 等 價 變 換 ， 變 換 前 后

23、的 指 令 序 列 完 成 同 樣 的 功能 ， 但 在 占 用 的 空 間 上 和 程 序 執(zhí) 行 的 時 間 上 都 更 省 、 更 有 效 。6. 目 標 代 碼 生 成 ： 不 同 形 式 的 目 標 代 碼 匯 編 、 可 重 定 位 、 內(nèi) 存形 式 （ Load-and-Go） ;7. 符 號 表 管 理 ： 合 理 組 織 符 號 ， 便 于 各 階 段 查 找 、 填 寫 等 ； 8. 出 錯 處 理 ： 錯 誤 的 種 類 詞 法 錯 、 語 法 錯 、 靜 態(tài) 語 義 錯 、 動 態(tài)語 義 錯 。 22 1.4.4 編 譯 器 的 分 析 /綜 合 模 式 前 端 ： 語

24、 言 結 構 和 意 義 的 分 析 ； 后 端 ： 語 言 意 義 處 理 ； 中 間 代 碼 ： 前 端 與 后 端 的 分 界 ； 23 1.4.4 編 譯 器 的 分 析 /綜 合 模 式 （ 續(xù) 1）4 編 譯 器 基 礎 架 構 （ Infrastructure） ： 源 代 碼 的 中 間 表示 、 一 組 前 端 、 一 組 后 端 ； 24 1.4.5 編 譯 器 掃 描 的 遍 數(shù) 1. 每 個 階 段 將 程 序 完 整 分 析 一 遍 的 工 作 模 式 稱 為 一 遍 掃 描 。 早期 編 譯 器 的 一 遍 定 義 為 從 外 存 讀 入 內(nèi) 存 再 寫 到 外 存

25、 ；2. 確 定 掃 描 遍 數(shù) 的 因 素 ： 軟 、 硬 件 條 件 ， 如 內(nèi) 存 太 小 ， 或 全 局 優(yōu) 化 語 言 結 構 ， 如 規(guī) 定 標 識 符 的 先 聲 明 后 引 用x := f(a, b, c);function f(a:integer; b:integer):integer; 編 譯 技 術 ， 如 拉 鏈 回 填 goto lab1;lab1: 25 1.5 編 譯 器 的 編 寫 1. 直 接 使 用 匯 編 語 言 和 程 序 設 計 語 言 ；2. 利 用 編 譯 器 編 寫 工 具 ： 詞 /語 法 、 語 法 制 導 翻 譯 、 代 碼 生成 、 數(shù)

26、據(jù) 流 分 析 等 ；3. 基 于 編 譯 器 基 礎 架 構 的 編 譯 器 構 造 系 統(tǒng) （ 開 放 式 編 譯 器 ，如 GCC、 SUIF等 ） 。 26 1.6 本 章 小 結 1 語 言 與 語 言 的 翻 譯2 編 譯 器 的 基 本 組 成 （ 工 作 ）3 編 譯 器 的 分 析 /綜 合 模 式 ， 編 譯 器 基 礎 架 構4 掃 描 遍 數(shù)5 編 譯 器 的 編 寫其 它1. 作 業(yè) ： 教 材 中 除 標 記 *的 全 做 ； 根 據(jù) 課 程 進 度 做 ； 第 二 、五 章 交 一 次 ， 第 三 、 四 章 交 各 兩 次 ；2. 課 代 表 ： 收 繳 作 業(yè)

27、 、 聯(lián) 系 上 機 、 反 映 同 學 意 見 ， 等3. 答 疑 ： 待 定 ；4. 上 機 作 業(yè) ： 交 上 機 報 告 ， 作 業(yè) 由 輔 導 教 師 驗 收 。 27 第 一 章 結 束 28返 回 例 6 一 Pascal的 過 程 如 下 (1) procedure sample(y: integer); 過 程 頭 (2) var x : integer; 過 程 體 （ 開 始 ） (3) begin x := y;(4) if x100 then x := 0(5) end; 過 程 體 （ 結 束 ） (1)是 過 程 頭 ， 它 是 一 個 聲 明 性 的 語 句 ，

28、 為 使 用 者 提 供 調(diào) 用 信 息 ， 包 括 過程 名 、 參 數(shù) 、 返 回 值 （ 若 有 的 話 ） 等 。 （ 接 口 ） (2)至 (5)是 過 程 體 ， 它 是 一 個 語 句 序 列 。 語 句 序 列 中 既 包 括 聲 明 性 語 句 也包 括 操 作 性 語 句 。 （ 實 現(xiàn) ） (2)是 聲 明 性 語 句 ， 而 (3)至 (5)是 操 作 性 語 句 。 編 譯 器 對 聲 明 性 語 句 的 處 理 一 般 是 生 成 相 應 的 環(huán) 境 (存 儲 空 間 )， 而 對 操作 性 語 句 則 是 生 成 此 環(huán) 境 中 的 可 執(zhí) 行 代 碼 序 列 。 為 了 便 于 編 譯 器 的 處 理 ， 操 作 性 語 句 中 使 用 的 每 個 操 作 對 象 ， 均 應 在 使用 前 聲 明 ， 即 符 合 先 聲 明 后 引 用 的 原 則 。