編譯器概論–游逸平

← 返回主頁面

2022/1 edit: 近期應該會開始把剩下的補完

Lecture 0 - Why learn Compiler?

• Reverse engineering
• Data processing
• Write better code
• Security
• Compiler 是驅動眾多技術的關鍵 e.g. ref1

If you don’t know how compilers work, then you don’t know how computers work. If you’re not 100% sure whether you know how compilers work, then you don’t know how they work.
Steve Yegge

注意本課程所提及的內容其實已經稍嫌過時，比較屬於上個世紀的技術，現今編譯器技術發展迅速，此課程內容只佔了非常小的一部分。建議各大學課程可以改用這本〈Engineering a compiler〉作為編譯器課程教材。有興趣更深入了解的建議再額外閱讀 gcc 或是 clang 的文件，或是 LLVM 框架的文件等第一手資料，以及 你所不知道的 C 語言：編譯器原理和案例分析。透過廣泛閱讀才有機會掌握現在迅速變革的技術。

Lecture 1 - Overview

先備課程：正規語言–陳穎平 (計算理論)

此課程著重於圖中 compiler 的部份

Image Not Showing Possible Reasons

• The image file may be corrupted
• The server hosting the image is unavailable
• The image path is incorrect
• The image format is not supported

Learn More →

[游逸平(https://people.cs.nctu.edu.tw/~ypyou)]

Compiler

• Front End (Analysis)
  • Lexical Analyzer
  • Syntax Analyzer
  • Semantic Analyzer
• IR - Intermediate Representation
• Back End (Synthesis)
  • Code Optimizer
  • Code Generator
  • 本課程不詳細介紹
• Error Handler
  • 處理各個階段產生錯誤 (Programmer會很感謝貼心的error reporter的)
  • 本課程不詳細介紹
• Symbol Table
  • 把各項處理的結果儲存起來的一種資料結構，包括函式名，變數名等，以供各階段需要時調用

Why FrontEnd/IR/BackEnd?

Ans: Reuse of Components
假設今天已經做好一個 c/c++ 的compiler，想改寫給Java用，那就只需要更改負責分析程式碼的 Front End 就好了，Back End可以繼續沿用。

同理，假設今天想從 x86 指令集執行換到 arm 指令集上執行，也只需要更改 Back End 就好

Assembler

把組語組譯成一個或多個 object program (不可執行)

Linker

把多個不可執行的 object file merge (例如.o) 起來變成可執行的 object file( 例如 .out/.exe)，被引用的函式庫也是在這階段被 link 起來

• Symbol resolution
• Relocation

Loader/Dynamic Linker

• Loader: 負責把程式 load 到 memory 中執行
• Dynamic Linker: 是一種 loader，在程式執行中有需要的時候把 .so (Shared Object) 或是 .dll (Dynamic linking library) 載入記憶體，並進行連結 (linking) 與重新定位 (relocation) 的動作

Others notes

越容易撰寫越有彈性的語言 compiler 要負起的責任就越大，例如需要考慮到各式的語法組合出來的各種 corner cases。

Interpreter vs Compiler vs Just-in-time compiler

Interpreter 像是一台 VM
一般我們用的 compiler 是 ahead-of-time compiler

Course project overview

Lecture 2 - Lexical 1

Lexical Analysis(語彙分析)

將輸入的字串分析，切割成數個 token，例如：
if ( b == 0 ) a = b; ，變成
KW: if ( ID NUM ) ID = ID SEMI

Token

描述原始碼中一些字串邏輯上的意義的最小單位，為一對 token name 和 attribute 的組合，以下為範例，詳情見課本或作業

Pattern

一段表達式描述 lexeme 如何對應到 token，可以使用正規語言 (regular expression) 表達式，例如：[A−Za−z_][A−Za−z0−9_]*

Error Recovery

(非課程重點) 碰到無法分析的錯誤該怎麼處理？

• panic mode: 忽略接下來的所有字元直到看到一個正確的
• Aggressive: 修改 input

Regular Expression

規則有點多，自己看講義吧，要注意優先度。之前考試有出過給一個特定情境，請寫出能篩選出特定格式的 RE。

推薦一個線上測試 RE 的工具：https://regex101.com/
他還會逐步分析你寫的 RE，展示 test cases 是如何 match 到的

RE 是有能力限制的，並非所有語言都能描述，例如一個 ( 就要與一個 ) 配對或是其他巢狀的敘述是無法使用 RE 描述的，會變成 infinite state machine

Interaction between Scanner and Parser

[游逸平(https://people.cs.nctu.edu.tw/~ypyou)]

• 讀取 Source Program
• Parser 呼叫 scanner 給 token
  Image Not Showing Possible Reasons

  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported

  Learn More →
• Parser 建構出 parse tree (之後做語意分析)
• 過程中 Parser 和 Scanner 會更新 symbol 資訊到 symbol table

Implementation of Lexical Analysis

其中一種方法是使用 Transition Diagram 來描述並使用 while 配switch 實做

Lecture 3 - Lexical 2

Finite Automata

輸入一個字串，從 start state 開始照著 transition rules 走，會停在 Final state 的就是 accept 其餘皆 reject。

Special rule: Epsilon moves，前一個 state 可以直接走到下一個 state

NFA vs DFA

• NFA
  • 一個輸入可以從一個 state 可以有多個 transition 到不只一個 next state (包含自己)
  • 可以有 epsilon move
• DFA
  • 一個輸入只會有一個 transition 從一個 state 走到下一個 state（包含自己）
  • 沒有 epsilon move

兩者實質上是等價的，RE 一定可以轉成同等辨識能力 NFA 和 DFA

其中一種儲存 transition 的方法是用 state 對 state 的 transition table，使用查表的方式使用，如此就不用寫一堆 switch cases。不過有可能會有太多沒使用到的欄位的缺點，之後會介紹另一個比較有效率的儲存方式。

實做 NFA 的麻煩點

• Backtrack/Backup
• Parallelism
• Look-ahead

但是 NFA 對人類來說比較好建構，比較直覺，所以會先 Tompson's construction 建構出 NFA ，之後再轉成 DFA

Thompson's construction

Trivial

Analysis

• 最多會有 (n(operators) + n(operands)) * 2 個 state
  • 因為一個 operator 和 operand 最多只會產生兩個 state (有些只有一個，例如 concatenate)
• 一個 state state，一個 accepting state
• 除了 accepting state 的 state 會有
  • 一個使用合法字元或 epsilon transit 出去的 transition
  • 或是兩個 epsilon transition 出去

NFA to DFA

核心概念：合併 epsilon transitions

操作方法：

• epsilon-closure(state s)
  • 把一坨 epsilon 連接的 NFA 的 state 合併成一個
• epsilon-closure(set T)
  • 對 T 裡面的 s 都做一次 epsilon-closure
• move(T, a)
  • 對 T 裡面的 s 都輸入 symbol a

Subset construction

• 產生出 start state
  • 對 NFA 的 state state 做 epsilon closure 並視作已經處理完的 state
• 只要有還沒有處理過的 state
  • 把還沒有處理過的 state 做 move(T, a)
  • 把 move 完得到的 set 視為處理完的 state
  • 如果 move 完是 Final state 就標示為 Final state
  • 新增 transition a 在 move 前後的 set 之間

pseudo algorithm:

add e_closure(s0) as an unmarked state to Dstates;
while (there is an unmarked state T in Dstates) {
    mark T;
    for (each input symbol a) {
        U = e_closure(move(T, a));
        if (U is not in Dstates) {
            add U as an unmarked state to Dstates;
            mark as final if U contains the original final state;
        }
        Dtran[T, a] = U;
    }
}

範例

Analysis

• 每一個 DFA state 其實是一坨 NFA state
• 理論上 DFA state 個數量會是 NFA 的指數倍，但實際上他們的數量大致相同
• 可以有不只一個 DFA 認得相同的 RE，即兩者之間等價，所以盡可能合併可合併的 state 取得較小的 DFA，降低實做的複雜度

DFA minimization

Distinguishability between states:

如何辨識兩個 state 可不可以合併：

• Final 和 non-Final 不可合併
• 對所有輸入，不管從 state s 還是 t 出發都會做一樣的決定，那他們就是 indistinguishable (equivalent)

講義上的定義：

• String x distinguishes state s from state t if exactly one of the states reached from s and t by following the path with label x is an accepting state
• State s is distinguishable from state t if there is some string that distinguishes them
  • E.g., empty string distinguishes any accepting state from any non-accepting state
  • E.g., string bb distinguishes state A from state B

Method

• Initialization: 把 state 分成 Final 和 non-final
• Division within:

Lecture 4 - lex

作業內容暫時先跳過

Lecture 5 - CFG

Lecture 6 - Parsing 1

Lecture 7 - Parsing 2

Lecture 8 - yacc

作業內容暫時先跳過

Lecture 9 - SDT (Semantic Analysis)

SDD/SDT

• SDD： 比較 high level - guide line
• SDT： 比較 low leve - 細節。e.g. 在Body的部份寫action, 什麼時候該做什麼
• Attrbute： 存放分析時所需要的資訊，甚至是IR

舉例：算式in-fix轉post-fix

SDD: 看到expr oprator term就把expr的 attibute concatenate term 的 attibute 再 concatenate oprator

SDT: semantic actions,
E.g. rest -> + term { print('+') } rest 1
把SDD定義的動作實做出來

Synthesis/Inherit Attribute

• Synthesis: 來自child的attribute。大多時機是把小孩的attribute合成成自己的attribute，例如加法。
• inherit: 來自父母或兄弟姊妹的attribute。大多時機是對其他人的attribute有attribute有dependency，需要從父母或兄弟姊妹pass attribute來計算自己的。會需要傳遞是因為 parse tree 和 abstract syntax tree 的結構不一樣，所以 parse tree 需要傳遞資訊

舉例：以先乘除後加減的計算算式

請參照講義上 parse tree 的箭頭
[待補圖]

Order of evaluate attribute

正常型況下沒有 cycle 的 DAG (的topology sort的所有可能) 才能執行 SDD，這會需要 two pass，也就是先建構完 parse tree 才建構AST。

如果要邊建構 parse tree 邊執行 SDD，會需要對 SDD 做限制

• S-attribute (S: synthesized)
• L-attribute (L: left-to-right), S-attribute 包含於 L-attribute

S-attribute

S-attribute 只要用 buttom up 的順序就能計算，所以 buttom up parsing 就可以邊 parse 邊計算。

L-attribute

(derivation rule)只能由左至右傳遞 attribute，避免產生cycle，亦即在 parse tree 中只能由左至右，由上至下傳遞

Semantic Rule with side effect???

建立Syntax tree

• parse tree: 透過CFG建立的樹
• syntax tree: 透過執行SDD從 parse tree 建立一棵語法樹(小提醒: inherit attribute就在這邊扮演傳遞資訊的角色)，syntax tree才是可執行、可分析的tree。第四次作業的分析就是base on syntax tree。

Implementation of SDT

General SDT implementation

• 建一顆 parse tree
• 執行 action 增加 node
• post traversal 產出 Syntax tree

not that general SDT

post-fix SDT: 都放在 body 最右手邊的 action。最簡單實做的SDT。使用一個stack

舉例：用一個stack和多個action處理四則運算。

SDT with action inside productions: 還沒 match 完整條 grammar rule 就執行 action。不是所有這類的SDT都能正常的邊 parse 邊執行。

有問題的SDT在 parsing 的時候會有conflict，亦即在做LR parsing的時候會有conflict

不確定yacc看到有問題的SDT(講義上的舉例)會怎麼做，需要查一下。保守作法就是action都寫在最後面就好了

有問題的SDT還是可以執行的，但是就是沒辦法邊parse邊執行，需要採正常的兩階段執行

消除left recursion why?

blablablablab…

L-attributed SDD to SDT

Lecture 10 - IR

編譯器的中介語言，需要有IR的原因在 Lecture 1 已經提及了。

IR有high level到low level之分，高的比較接近我們寫的程式碼，低的比較接近machine code

Syntax tree: 把parse tree精鍊過只剩下所需資料的tree
DAG: 一樣leaf都是operand，不過operator不會重複出現，還有GVA(Global Value Numbering)最佳化。產生一個node之前會檢查是不是已經存在了，已經存在了就直接指過去，<ValueNumber , Signature> pair存在hash table裡面來查詢 signature: <op, l, r>

Basic info

之前提到的Three address code (e.g. t1 = t2 + t3) 比較接近 machine code表示法，接下來說明一些資料結構來存放three address code

課本裡的IR有8種operation，我們這邊以這8種為例

ph1 ph2 ph3 ph4 ph5 ph6 ph7 ph8

ph = placeholder，等等補
詳情請自行參考講義

不管什麼語言都轉成這8種opration

範例:把Do-while loop轉成IR

using symbolic label/numbering label兩種後者比較接近machine code

選擇允許的IR的operation是一個很重要的設計

• 比較接近machine code的設計比較容易轉成真的machine code
• 但是會不好維持原本的架構
• 所以會分成很多層級的IR，high到low給不同的用途

IR的資料結構

Quadruple

< op - arg1 - arg2 - result >
three address直接的轉譯的結果
透過temperary存放result

• 直覺
  • 比較好做最佳化，像是instruction reordering(不能打破dependency)
  • 在triple裡面移動指令VN reference也要改，Quad不用，可以直接移動
• 但是比較佔空間
  • 所以就有Indirect Triple出現啦

Triple

沒有temperary需要value number來reference其他operation的計算結果
行為上和syntax tree一樣(op, arg1, arg2)

Indirect Numbering

Triple的變形，解決需要reference的問題。多maintain一個array，這個array會存放每個指令，對調指令時是對調array裡面存放指令的順序而不是更動指令本身，所以就不用動reference了

不過大多open source的IR還是quad因為比較直覺(編譯什麼的吃多一點記憶體很正常的吧)

SSA(課本沒有)

一個變數只會被定義一次
所以會需要renaming，如果有重複用到同一個變數的話
不過在condition的時候會有confliction，所以會用phy function來解決(最後轉成machine code的時候會拿掉)

現今open source compiler常用

• 優點
  • code optimization比較方便
  • 不同命名消除dependency，做什麼調換順序的比較方便，甚至可以發覺更多可以最佳化的點

詳情請見：〈SSA-based Compiler Design〉

Type Checking

在Symantic Analysis的時候會檢查。現在CPU都是control unit和arithmetic-logic unit是分開的，所以data存在哪個相對位址 (storage layout，等等補圖) compiler要先決定好，arithmetic-logic unit 只負責去存取

Static data: 存放的位置不改變，e.g. 全域變數, static variable
dynamic data: e.g. malloc, new, local variable

Type Expression：表示型別的方式, variable, function都有，在動態語言裡面甚至有type variable在type expression裡面來攜帶型別資訊。儲存上可以用graph來儲存

什麼叫做「一樣」的型別？

• Structure eq. : 以下任一者成立即相同
  • same basic type
  • same structure
  • typedef
• Name eq.
  • 要完完全全一模一樣（待補充）
  • structure eq. 三條都滿足

Storage layout of Names

看到變數宣告就知道要分配多少空間、放在哪，再存放到symbol table，下次要存取變數就查表，直接去那個位置拿資料

小疑問，如果一個頻繁呼叫的函式，裡面用local variable是合適的嗎？因為local variable會一直不停被allocate, deallocate，這樣很耗時嗎？

• address alignment
  當存取資料的位址不能被4(在一次存取4 byte的平台上而言，帶補充)整除時，就會多耗很多operation去拿資料，例如一次拿出來之後再抽絲剝繭拿出你要的

在traverse parse tree的時候用SDT產出相關資料

• 例如建構出syntax tree中陣列的型別資訊
• 然後就可以用型別資訊決定變數要存放在table中哪個記憶體位置
• Symbol table裡面存的是相對位置，table起始位置再加上offest才會存到你要的symbol(或是另一張symbol table)
• 起始位置用一個top pointer指著，方便存取
  以上在你做完作業4之後會很有感覺

Translation of Expressions

用SDD定義看到各express的grammar rule該怎麼做

1. 做運算後存起來到new出來的temp或是覆蓋
2. 產生IR(new temp出來可以對應到儲存資訊到temp register)

array的記憶體擺放方法，這個是compiler決定好的，像fortran這種row major的擺法或是C這種column major
存取方法: base + offset

• 兩種Type checking

  • Type Synthesis: 可以由以宣告的型別推斷expression的型別，所有的東西都有type expression，每做一個動作就是推斷出目前該有的型別為何
  • Type Inference: 有type variable, 用他來說明型別

• 有Overloading時該怎麼知道在用哪個？
  一樣是作type checking，每個東西都有type expression，checking完一樣的就用他。Template function也是一樣的道理，檢查傳進來的參數的型別
  e.g. function的type expression可以長這樣
  \[ (for\ all)\ a\ list(a) -> integer \]
  input -> output

Compiler正規化推斷型別的流程 <–我覺得這部份會考歐

用已知的資訊推導未知資訊
(帶補講義圖p.62)

• unification
  • ?
  • ??
  • ???
  • 演算法
    • 遞迴unify(a,b)

題外話：Just In Time compiler 也是需要先做 type inference

Control flow Statements

Boolean expression

short circuit expression

• 在or中有人true就直接回傳true了
• 在and中有人false就直接回傳false了

缺點：

• 可能在剩餘的expression中有必須被執行的statement被跳過了
• 不過這應該是programmer的問題

SDD for Boolean expression

backpatching: 把label換成instruction編號

• 把IR存在array裡面

Lecture 11 - Runtime

Lecture 12 - Code Generation & Code Optimization

Compiler 最有趣的地方都在這邊

參考資料

• 淺談編譯器最佳化技術 - 把基本的最佳化方法淺顯易懂的介紹了一遍

Lectuer 13 - Controlflow

← 返回主頁面

廢話

G_G …
我怎麼寫起來都像廢話，排版也亂七八糟

之後有空慢慢寫

2022 - March -

老師：欸我明年被指派要上編譯系統= =
老師：你有沒有修過編譯器
我：有
老師：（(:DDD)）

呃…好我懂了

那明年來上這個好了
How to compile C/C++ for WASM, pure Clang, no libs, no framework
https://github.com/ern0/howto-wasm-minimal

或是參考 你所不知道的 C 語言：編譯器原理和案例分析，從最佳化開始講之類的，至少用現代化一點的教材

參考資料

• 淺談編譯器最佳化技術 - 把基本的最佳化方法淺顯易懂的介紹了一遍
• Optimizations in C++ Compilers - 比較詳細一點的最佳化
• 一點都不深入的了解 Compiler、 Interpreter 和 VM - 讓你貼近生活一點1
• Let’s Build A Simple Interpreter. Part 1. - 讓你貼近生活一點2
• 你所不知道的 C 語言: 執行階段程式庫 (CRT) - Run Time 的補充資料
• 2000 行 C 編譯器實做 - 教學導向，清楚好懂
• Compiler explorer 即時預覽一段程式碼及其被編譯出來的組合語言
  • Godbolt's talk at cpponsea 2019: What Everyone Should Know About How Amazing Compilers Are，快速提供提供幾個範例告訴你 compiler 擅長做什麼以及是如何最佳化的
  • Godbolt's talk at CppCon2017: What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid

LLVM

聽過 GCC 就也要聽過 LLVM

• COSCUP2016 - LLVM框架、由淺入淺 - 影片應該可以在Youtube找到，但是我有點懶
• LLVM 總是打開你的心：從電玩模擬器看編譯器應用實例 - 其實你也可以自己做一台紅白機，Jserv 最近的課就在做一台 GameBoy 模擬器
• COSCUP 2014 : open source compiler 戰國時代的軍備競賽 - GCC vs LLVM! 資料有點久了，不過可以大致當個歷史教材看看