Upgrade to Pro — share decks privately, control downloads, hide ads and more …

第 8 章、編譯器

第 8 章、編譯器

陳鍾誠

June 08, 2022
Tweet

More Decks by 陳鍾誠

Other Decks in Education

Transcript

  1. 第 8 章、編譯器  8.1 簡介  8.2 詞彙掃描 

    8.3 語法剖析  8.4 語意分析  8.5 中間碼產生  8.6 組合語言產生  8.7 最佳化  8.8 實務案例:gcc 編譯器
  2. 8.1 簡介  編譯器  將高階語言轉換成組合語言(或機器碼) 的工具 sum = sum

    + i LD R1 sum LD R2 i ADD R3 R2 R1 ST R3 sum 編譯器 Compiler 圖 8.1 編譯器的輸入與輸出
  3. C0 語言  C0 語言  代表 C 語言第 0

    版的意思,就是小型的 C 語言。  只包含 for 迴圈與基本運算。  範例
  4. C0 語言的 EBNF 語法  星號 * 代表重複零次以上  加號

    + 代表重複一次以上  問號 ? 代表重複 0 或 1 次
  5. 編譯器的六大階段  1. 詞彙掃描 (Scan 或 Lexical Analysis)  將整個程式分成一個一個的基本詞彙

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

    sum = sum + i sum = sum + i id = id + id EXP:int ITEM:int ITEM:int + STMT sum:id:int = + sum i T0 = T0 sum sum:id:int i:id:int 高階語言 詞彙串列 語法樹 中間碼產生 (P-code Generator) 語意樹 最佳化 (Optimization) 組合語言產生 (ASM generator) ADD R1, R2, R1 中間碼 組合語言
  7. 8.3 語法剖析  剖析器  由上而下的剖析法  像是遞迴下降法、LL 法 

    由下而上的剖析法  像是運算子優先矩陣法、LR 法  本章所採用的方法  遞迴下降法  其餘方法請參考編譯器的專門書籍。
  8. 遞迴下降法  方法  剖析器的撰寫者, 只要能夠將 EBNF 語法轉換為遞迴 下降函數, 就能製作出遞迴下降剖析器。

     轉換方法 if isNext(b) { next(b); parseB(); } else if isNext(c) { next(c); parseC(); } 規則:A = b B | c C while (isNext(b)) { next(b); parseB(); } 規則:A = (b B)*
  9. 圖 8.10 <範例 8.1> 剖析到 sum=0 時 的語法樹與堆疊結構 PROG BaseList

    PROG BaseList BASE STMT 成 長 方 向 堆疊 (Stack) BASE STMT sum: id = 0:number EXP ITEM EXP ITEM
  10. 8.4 語意分析  執行時機  當語法樹建立完成後, 緊接著通常會進行語意分析的 動作。  執行動作

     語意分析必須確定每個節點的型態, 並且檢查這些型 態是否可以相容, 然後才輸出具有標記的語法樹, 也 就是語意樹。
  11. 語意分析的範例 EXP ITEM ITEM + STMT sum:id = sum:id i:id

    EXP:int ITEM:int ITEM:int + STMT sum:id:int = sum:id:int i:id:int (a) 語法樹 (b) 語意樹 語意分析 圖 8.11 語意分析:將語法樹標註上節點型態
  12. 8.5 中間碼產生  使用時機  一旦語意樹建立完成, 我們就可以利用程式將樹中的 每個節點, 展開為中間碼 

    方法  利用遞迴的方式, 從根節點開始, 遞迴的展開每個子 節點, 直到所有節點的中間碼都產生完畢為止。
  13. 中間碼產生的演算法  規則:STMT = id ‘=’ EXP  範例:sum =

    sum + i  呼叫 generate(exp) :其中的 exp 為 sum + i  pcode 一行會產生 = T0 sum  並傳回 T0 作為 sum = sum + i 運算式的值
  14. 8.6 組合語言產生  時機  一旦中間碼產生完畢, 程式就可以輕易的將中間碼轉 換成組合語言。  方法

     將中間碼指令轉為組合語言指令  必須考慮佔存器的載入與儲存  範例 + sum i T0 LD R1 sum LD R2 i ADD R3 R1 R2 ST R3 T0
  15. 8.7 最佳化 + sum i T0 LD R1 sum LD

    R2 i ADD R3 R1 R2 ST R3 T0 中間碼 組合語言 轉換 ADD R3 R1 R2 最佳化 當 sum 已經在 R1 中, i 已經在 R2 中, 而且 T0 對應到 R3 時
  16. 8.8 實務案例:gcc 編譯器  gcc 編譯器的過程  C 語言 

    (剖析)  generic 語法樹  (產生)  gimple 中間碼  (語意分析)  RTL 中間碼  (最佳化)  (組合語言產生)  組合語言
  17. GENERIC (剖析樹) C C++ … GIMPLE (中間碼) RTL (中間碼) 組合語言

    Parsing Generic converter Gimplify Tree SSA optimizer RTL generator RTL optimizer ASM generator 圖 8.15 GNU 編譯器的流程
  18. 範例 8.7 中間碼 Gimple 與 RTL 之對照範例  將 Gimple

    轉為 RTL 的範例  8.7(b) RTL 範例的解讀
  19. 結語  高階語言  (掃描)  詞彙串列  (剖析) 

    語法樹  (語意分析)  語意樹  (中間碼產生) 中間碼  (組合語言產生)  組合語言  (組譯器)  目的檔「機器碼」
  20. 習題  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 語言程式為組合語言, 並觀察其編譯後 的組合語言, 指出最佳化後哪些指令被省略了
  21. 圖 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 Term + Factor Factor Factor * i:id i:id sum:id stmt sum:id Item Item Item = * i i t1 + sum t1 t2 = t2 sum
  22. 圖 8.4 編譯器的六階段模型 高階語言程式 (Source code) 一連串的詞彙 (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 ) 經過最佳化的碼 (Optimized Code ) 中間碼 (Intermediate Code ) 具型態標記的抽象語法 樹 (Annotated Abstract Syntax Tree) 抽象語法樹 (Abstract Syntax Tree) 一連串的詞彙 (A sequence of tokens)
  23. 圖 8.5 階段一、掃描的過程示意圖 sum = sum + i * i

    sum = sum + i * i id = id + id * id 程式 詞彙串列 類型串列 掃描
  24. 階段二、剖析的過程示意圖 sum = sum + i * i id =

    id + id * id Exp Term Term + Factor Factor Factor * i:id i:id sum:id stmt sum:id Item Item Item = 詞彙串列 類型串列 剖析樹 剖析
  25. 語意分析的過程示意圖 Exp Term Term + Factor Factor Factor * i:id

    i:id sum:id stmt sum:id Item Item Item = int int int int 設定型態
  26. 中間碼產生過程的示意圖 Exp Term Term + Factor Factor Factor * i:id

    i:id sum:id stmt sum:id Item Item Item = 中間碼產生 * i i t1 + sum t1 t2 = t2 sum
  27. 階段六、程式碼產生過程的示意圖 * 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 組合語言
  28. 程式剖析到 i=1 完成時的語法樹與堆 疊結構 <PROG> <BaseList> <BASE> <FOR> for (

    i: id = <STMT> 1:number <PROG> <BaseList> <BASE> <FOR> 成 長 方 向 堆疊 (Stack) <EXP> <TERM> <FACTOR> <ITEM> <BASE> <STMT> sum: id = 0:number <EXP> <TERM> <FACTOR> <ITEM> ;
  29. 副程式呼叫時的堆疊變化情況 框架指標FP 區域變數 x 區域變數 y 參數t (=x=1) FP SP

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