教科書：系統程式 - 第 8 章、編譯器

Size: px

Start display at page:

Download "教科書：系統程式 - 第 8 章、編譯器"

斤牧
5 years ago
Views:

1 第 8 章編譯器作者 : 陳鍾誠旗標出版社

2 第 8 章編譯器 8.1 簡介 8.2 詞彙掃描 8.3 語法剖析 8.4 語意分析 8.5 中間碼產生 8.6 組合語言產生 8.7 最佳化 8.8 實務案例 :gcc 編譯器

3 8.1 簡介編譯器將高階語言轉換成組合語言 ( 或機器碼 ) 的工具 sum = sum + i 編譯器 Compiler LD R1 sum LD R2 i ADD R3 R2 R1 ST R3 sum 圖 8.1 編譯器的輸入與輸出

4 C0 語言 C0 語言代表 C 語言第 0 版的意思, 就是小型的 C 語言只包含 for 迴圈與基本運算範例

5 C0 語言的 EBNF 語法星號 * 代表重複零次以上加號 + 代表重複一次以上問號? 代表重複 0 或 1 次

6 編譯器的六大階段 1. 詞彙掃描 (Scan 或 Lexical Analysis) 將整個程式分成一個一個的基本詞彙 (token) 2. 語法剖析 (Parsing 或 Syntax Analysis) 剖析器利用語法規則進行比對, 以逐步建立語法樹 3. 語意分析 (Semantic Analysis) 為語法樹加註節點型態, 並檢查型態是否相容, 然後輸出語意樹 4. 中間碼產生 (Pcode Generator) 語意樹被轉換成中間碼 5. 最佳化 (Optimization) 考慮暫存器的配置問題, 降低指令數量, 增加效率 6. 組合語言產生 (Assembly Code Generator) 將中間碼轉換為組合語言輸出

7 圖 8.3 編譯器的六大階段掃描器 (Lexer) 高階語言詞彙串列 sum = sum + i sum = sum + i id = id + id 剖析器 (Parser) 語意分析 (Semantic Analysis) 中間碼產生 (P-code Generator) 最佳化 (Optimization) 語法樹語意樹中間碼 sum:id:int = ITEM:int STMT sum:id:int EXP:int + sum i T0 = T0 sum + ITEM:int i:id:int 組合語言產生 (ASM generator) 組合語言 ADD R1, R2, R1

8 8.2 詞彙掃描詞彙掃描將程式切分成一個一個的詞彙 (token) 範例 1:sum = sum + i 範例 2:printf("%d", 30)

9 詞彙掃描的程式

10 以正規表達式進行掃描整數 number = [0-9]+ 名稱 id = [A-Za-z_][A-Za-z0-9_]*

11 使用迴圈逐字進行掃描

12 8.3 語法剖析剖析器由上而下的剖析法像是遞迴下降法 LL 法由下而上的剖析法像是運算子優先矩陣法 LR 法本章所採用的方法遞迴下降法其餘方法請參考編譯器的專門書籍

13 遞迴下降法方法剖析器的撰寫者, 只要能夠將 EBNF 語法轉換為遞迴下降函數, 就能製作出遞迴下降剖析器轉換方法規則 :A = b B c C if isnext(b) { next(b); parseb(); } else if isnext(c) { next(c); parsec(); } 規則 :A = (b B)* while (isnext(b)) { next(b); parseb(); }

14 遞迴下降法範例 1

15 C0 語言的剖析器 ( 第 1 頁 )

16 C0 語言的剖析器 ( 第 2 頁 )

17 C0 語言的剖析器 ( 第 3 頁 )

18 C0 語言的剖析器 ( 第 4 頁 )

19 C0 語言的剖析器 ( 第 5 頁 )

20 C0 語言的剖析器 ( 第 6 頁 )

21 圖 8.10 < 範例 8.1> 剖析到 sum=0 時的語法樹與堆疊結構 PROG BaseList BASE STMT 堆疊 (Stack) PROG BaseList BASE STMT EXP ITEM 成長方向 sum: id = EXP ITEM 0:number

22 8.4 語意分析執行時機當語法樹建立完成後, 緊接著通常會進行語意分析的動作執行動作語意分析必須確定每個節點的型態, 並且檢查這些型態是否可以相容, 然後才輸出具有標記的語法樹, 也就是語意樹

23 語意分析的範例 STMT 語意分析 STMT sum:id = EXP sum:id:int = EXP:int ITEM + ITEM ITEM:int + ITEM:int sum:id i:id sum:id:int i:id:int (a) 語法樹 (b) 語意樹圖 8.11 語意分析 : 將語法樹標註上節點型態

24 語法正確但語意錯誤的程式範例範例 8.2 語意分析器將會發現到 a 與 b 是無法相乘的, 因而輸出錯誤訊息

25 8.5 中間碼產生使用時機一旦語意樹建立完成, 我們就可以利用程式將樹中的每個節點, 展開為中間碼方法利用遞迴的方式, 從根節點開始, 遞迴的展開每個子節點, 直到所有節點的中間碼都產生完畢為止

26 將 C0 語言編譯成中間碼的範例 1

27 中間碼產生的演算法規則 :STMT = id = EXP 範例 :sum = sum + i 呼叫 generate(exp) : 其中的 exp 為 sum + i pcode 一行會產生 = T0 sum 並傳回 T0 作為 sum = sum + i 運算式的值

28 圖 8.13 中間碼產生的演算法 ( 第 1 頁 )

29 圖 8.13 中間碼產生的演算法 ( 第 2 頁 )

30 圖 8.13 中間碼產生的演算法 ( 第 3 頁 )

31 圖 8.13 中間碼產生的演算法 ( 第 4 頁 )

32 8.6 組合語言產生時機一旦中間碼產生完畢, 程式就可以輕易的將中間碼轉換成組合語言方法將中間碼指令轉為組合語言指令必須考慮佔存器的載入與儲存範例 + sum i T0 LD R1 sum LD R2 i ADD R3 R1 R2 ST R3 T0

33 範例 8.4 將中間碼轉換為組合語言

34 圖 8.14 將中間碼轉換為 CPU0 組合語言的演算法

35 指令的改寫對常數值的載入指令改寫為 LDI

36 8.7 最佳化中間碼 + sum i T0 轉換組合語言 LD R1 sum LD R2 i ADD R3 R1 R2 ST R3 T0 當 sum 已經在 R1 中, i 已經在 R2 中, 而且 T0 對應到 R3 時最佳化 ADD R3 R1 R2

37 範例 8.5 最佳化的範例

38 8.8 實務案例 :gcc 編譯器 gcc 編譯器的過程 C 語言 ( 剖析 ) generic 語法樹 ( 產生 ) gimple 中間碼 ( 語意分析 ) RTL 中間碼 ( 最佳化 ) ( 組合語言產生 ) 組合語言

39 圖 8.15 GNU 編譯器的流程 C C++ GENERIC ( 剖析樹 ) GIMPLE ( 中間碼 ) RTL ( 中間碼 ) Parsing Generic converter Gimplify Tree SSA optimizer RTL generator RTL optimizer ASM generator 組合語言

40 範例 8.6 gcc 編譯器的中間碼格式

41 範例 8.7 中間碼 Gimple 與 RTL 之對照範例將 Gimple 轉為 RTL 的範例 8.7(b) RTL 範例的解讀

42 要求 gcc 編譯器輸出 rtl 中間碼指令 : 加上 dr 參數, 可讓 gcc 輸出 rtl 中間碼

43 RTL 檔案的內容

44 Gcc 的最佳化功能

45 範例 8.9 gcc 不同層級的最佳化實例

46 結語高階語言 ( 掃描 ) 詞彙串列 ( 剖析 ) 語法樹 ( 語意分析 ) 語意樹 ( 中間碼產生 ) 中間碼 ( 組合語言產生 ) 組合語言 ( 組譯器 ) 目的檔機器碼

47 習題 8.1 請為 C0 語言加上 if 語句的 EBNF 語法, 加入到圖 8.2 中 8.2 接續上題, 請在圖 8.9 當中加入剖析 if 語句的演算法 8.3 接續上題, 請在圖 8.13 當中加入將 if 語句轉為中間碼的演算法 8.4 請為範例 8.5 (b) 的無最佳化組合語言, 提出一個簡單的最佳化機制, 並寫出您的最佳化方法實施後, 所產生的組合語言程式碼 8.5 請使用 gcc 的 -O0 與 -O3 參數, 分別已無最佳化與高級最佳化的方式, 編譯任意一個 C 語言程式為組合語言, 並觀察其編譯後的組合語言, 指出最佳化後哪些指令被省略了

49 其他圖片, 不包含在書當中的

51 Gimple

53 較抽象的編譯器定義方式來源程式 Source Code 編譯器 Compiler 目標程式 Target Code

54 圖 8.3 編譯器的三大階段掃描剖析程式碼產生高階語言程式 (Source code) sum = sum + i * i 掃描器 (Lexer) 一連串的詞彙 (A sequence of tokens) sum = sum + i * i id = id + id * id stmt 剖析器 (Parser) sum:id = Term Exp + Term 剖析樹 (Parsing tree) Factor Factor * Factor Item Item Item 程式產生 (Code Generation) 目的程式碼 (Target code) sum:id i:id * i i t1 + sum t1 t2 = t2 sum i:id

55 圖 8.4 編譯器的六階段模型高階語言程式 (Source code) 1. 掃描器 (Lexer) 一連串的詞彙 (A sequence of tokens) 一連串的詞彙 (A sequence of tokens) 2. 剖析器 (Parser) 抽象語法樹 (Abstract Syntax Tree) 抽象語法樹 (Abstract Syntax Tree) 3. 語意分析 (Semantic Analysis) 具型態標記的抽象語法樹 (Annotated Abstract Syntax Tree) 具型態標記的抽象語法樹 (Annotated Abstract Syntax Tree) 4. 中間碼產生 (Intermediate Code Generator) 中間碼 (Intermediate Code ) 中間碼 (Intermediate Code ) 5. 最佳化 (Optimizer) 經過最佳化的碼 (Optimized Code ) 經過最佳化的碼 (Optimized Code ) 6. 程式碼產生 (Code Generation) 目的程式碼 (Target code)

56 圖 8.5 階段一掃描的過程示意圖程式 sum = sum + i * i 掃描詞彙串列類型串列 sum = sum + i * i id = id + id * id

57 階段二剖析的過程示意圖詞彙串列類型串列 sum = sum + i * i id = id + id * id 剖析 stmt sum:id = Exp Term + Term 剖析樹 Factor Factor * Factor Item Item Item sum:id i:id i:id

58 語意分析的過程示意圖 stmt sum:id = Exp int Term + Term Factor Factor * Factor Item Item Item sum:id i:id i:id int int int 設定型態

59 中間碼產生過程的示意圖 stmt sum:id = Exp Term + Term Factor Factor * Factor Item Item Item sum:id i:id i:id 中間碼產生 * i i t1 + sum t1 t2 = t2 sum

60 階段五最佳化過程的示意圖 * i i t1 + sum t1 t2 = t2 sum 最佳化 * i i t1 + sum t1 sum

61 階段六程式碼產生過程的示意圖 Pcode 中間碼 * i i t1 + sum t1 sum 程式碼產生 CPU0 組合語言 LD LD MUL ADD ST R1, i R2, sum R3, R1, R1 R2, R3, R2 R2, sum

62 程式剖析到 i=1 完成時的語法樹與堆疊結構 <PROG> 堆疊 (Stack) <BASE> <BaseList> <BASE> <FOR> <PROG> <BaseList> <BASE> <FOR> 成長方向 <STMT> ; for ( <STMT> sum: id = <EXP> i: id = <EXP> <TERM> <TERM> <FACTOR> <FACTOR> <ITEM> <ITEM> 0:number 1:number

63 副程式呼叫時的堆疊變化情況 +4-4 FP 0 框架指標 FP 框架指標 FP 框架指標 FP -4 區域變數 x 區域變數 x 區域變數 x -8 區域變數 y +12 區域變數 y 區域變數 y SP -12 參數 t (=x=1) +8 參數 t (=x=1) 參數 t (=x=1) +4 y=f1(x) 返回地址 y=f1(x) 返回地址 FP 0 保存的 FP 保存的 FP SP -4 區域變數 b +12 區域變數 b +8 參數 *p (=&t) +4 b=f2(&t) 返回地址 FP SP 0-4 保存的 FP 區域變數 r (a) 呼叫 y=f1(x) 前 (b) 呼叫 y=f1(x) 後 (c) 呼叫 b=f2(&t) 後註 : 在 CPU0 當中, 返回值都是儲存在 R1 返回圖 8.20 < 範例 8.4 > 程式的堆疊變化情況

64 使用 gcc 跨平台編譯的範例圖 arm-elf-gcc array_sum_arm.s arm-elf-gcc array_sum_arm.o array_sum.c gcc array_sum_ia32.s gcc array_sum_ia32.o

教科書：系統程式 - 第 7 章、高階語言

教科書：系統程式 - 第 7 章、高階語言第 7 章高階語言作者 : 陳鍾誠旗標出版社第 7 章高階語言 7.1 簡介 7.2 語法理論 7.3 語意理論 7.4 執行環境 7.5 實務案例 :C 語言 7.1 簡介高階語言的核心是語法理論利用生成規則 ( 例如 :BNF, EBNF 等 ) 描述程式的語法根據生成規則撰寫剖析程式, 轉換成語法樹對語法樹進行解譯或編譯的動作編譯器 v.s. 直譯器直譯器利用程式解讀該語法樹,