編譯器概論–游逸平

← 返回主頁面

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 的部份

[游逸平(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) 的動作

可能需要補一小段程式碼轉成 instruction 的過程
再豐富一點的 overview (第一部影片的內容)

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 的組合，以下為範例，詳情見課本或作業

所對應的語彙 (lexemes)	Token name	attribute
, ; : [ ] ( )	Delimiters	no attribute
array begin boolean	keyword	no attribute
var1 var2	identifier	Pointer to table entry
1 123 348579	integer	integer value 1, 123, …
"sdkfjh" "gfgjkhgjhg"	string	string content "sdkfjh" …

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
• Parser 建構出 parse tree (之後做語意分析)
• 過程中 Parser 和 Scanner 會更新 symbol 資訊到 symbol table

Implementation of Lexical Analysis

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

example 1

example 2

小問題： 像 if then else 這類的保留字會不會被當成一個 identifier? 會！
方法一：先放到 symbol table 當成保留字 (reserved word) 存起來
方法二：特別為那些保留字寫 rule (e.g. if -> KW: if) 來辨識保留字，不過這樣會跟原本的 rule 有衝突，造成 ambiguity，所以要訂出 rule 之間的優先順序。之後在作業中碰到的方法會是用方法二

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

實做上會採用 NFA 和 DFA 呢？ (點擊展開)

DFA，因為一次只有一個 transition 比較好做，但是圖的大小會比 NFA 大指數倍 (理論上)(實際上可能差不多)，之後會有詳細分析

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

不過實際上 regular expression matching engine 實做方法有千百種，依據不同使用場合有不同實做方式，例如 cregex 就是一個值得參考的短小精悍實做

實做 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;
    }
}

範例

有空再用 graphiz 畫

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:

完了才寫一天就又想偷懶了
需要有人斗內食物QQ

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可以長這樣
  

  $$(forall)alist(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! 資料有點久了，不過可以大致當個歷史教材看看