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

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

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

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

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

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

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

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

詞彙掃描的程式

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

使 用 迴 圈 逐 字 進 行 掃 描

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

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

遞迴下降法 – 範例 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

範例 8.5 最佳化的範例

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

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

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

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

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

RTL 檔案的內容

Gcc 的最佳化功能

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

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

習題 8.1 請為 C0 語言加上 if 語句的 EBNF 語法, 加入到圖 8.2 中。 8.5 請使用 gcc 的 -O0 與 -O3 參數, 分別已無最佳化與高級最佳化的方 式, 編譯任意一個 C 語言程式為組合語言, 並觀察其編譯後 的組合語言, 指出最佳化後哪些指令被省略了

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

Gimple

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

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

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

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

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

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

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

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

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

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

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

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