編譯器概論--游逸平
===

[**←** 返回主頁面 :house:](https://hackmd.io/1OBQAda9R7C-ufE0ski4Xg)

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

# Lecture 0 - Why learn Compiler?
* Reverse engineering
* Data processing
* Write better code
* Security
* Compiler 是驅動眾多技術的關鍵 e.g. [ref1](https://www.facebook.com/groups/system.software2020/permalink/489917168609154/)

> 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.
> [name= Steve Yegge]

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

# Lecture 1 - Overview

先備課程：[正規語言--陳穎平](/7XN2PKySSxuepfcm_8Jb1Q) (計算理論)

此課程著重於圖中 compiler 的部份
> 
> [name= [游逸平](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) 的動作

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

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

## 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](https://en.wikipedia.org/wiki/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

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/1200px-Chomsky-hierarchy.svg.png" height=200 width=250></img>

## Interaction between Scanner and Parser
> 
>
> [name=[游逸平](https://people.cs.nctu.edu.tw/~ypyou)]

* 讀取 Source Program
* Parser 呼叫 scanner 給 token :repeat:
* Parser 建構出 parse tree (之後做語意分析)
* 過程中 Parser 和 Scanner 會更新 symbol 資訊到 symbol table

## Implementation of Lexical Analysis
其中一種方法是使用 Transition Diagram 來描述並使用 `while` 配`switch` 實做

:bulb: **example 1**

:bulb: **example 2**

:::info

**小問題：** 像 `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

:::spoiler
<summary>實做上會採用 NFA 和 DFA 呢？ (點擊展開)</summary>
DFA，因為一次只有一個 transition 比較好做，但是圖的大小會比 NFA 大指數倍 (理論上)(實際上可能差不多)，之後會有詳細分析
:::
<br>

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

:::info
不過實際上 regular expression matching engine 實做方法有千百種，依據不同使用場合有不同實做方式，例如 [cregex](https://github.com/jserv/cregex) 就是一個值得參考的短小精悍實做
:::

實做 NFA 的麻煩點
* Backtrack/Backup
* Parallelism
* Look-ahead

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

## Thompson's construction
~~Trivial~~
:construction:

### 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;
    }
}

### 範例
:construction:
有空再用 graphiz 畫

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

### DFA minimization
:construction: 範例
我懶得畫，有空再補
或是看誰要幫我補

#### 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:

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

# Lecture 4 - lex

作業內容暫時先跳過

# Lecture 5 - CFG

# Lecture 6 - Parsing 1

<!--先寫出top down 和 buttom up parser 的overview再詳細解釋-->

# 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
* pre-order traversal 產出 Syntax tree

- not all SDT can be parse
- 要先轉成 L/S SDD

- steps
- marker nonterminals
- 
- if it's LR Grammar, 就可以 parse (上圖改寫)
- reduction 階段再做 action 即可

### 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?*
因為要改寫 LR 可以支援，因為一個是 Bottom-up 一個 Top-Bottom
> *blablablablab...*

L-attributed SDD to SDT

:construction: 待補....

# 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](https://link.springer.com/book/10.1007/978-3-030-80515-9)〉

## 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

<!--小提醒：static在RAM裡面最多4GB, 考GPE的時候要小心歐
好吧其實我不太確定
-->

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 最有趣的地方都在這邊

## 參考資料
* [淺談編譯器最佳化技術](https://ncku365-my.sharepoint.com/:b:/g/personal/p76104809_ncku_edu_tw/EW9e2-ghXjFDpgTbuRSoU7wB_YinfvhZAyBTUOXGks1vRA?e=qEBgta) - 把基本的最佳化方法淺顯易懂的介紹了一遍

# Lectuer 13 - Controlflow

[**←** 返回主頁面 :house:](https://hackmd.io/1OBQAda9R7C-ufE0ski4Xg)

---
## 廢話

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

之後有空慢慢寫 :zzz: 不知道專題和準備推甄會花多少時間

*2022 - March -*
> 老師：欸我明年被指派要上編譯系統= =
> 老師：你有沒有修過編譯器
> 我：有
> 老師：（(:DDD)）
>
> 呃......好我懂了

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

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

## 參考資料
* [淺談編譯器最佳化技術](https://ncku365-my.sharepoint.com/:b:/g/personal/p76104809_ncku_edu_tw/EW9e2-ghXjFDpgTbuRSoU7wB_YinfvhZAyBTUOXGks1vRA?e=qEBgta) - 把基本的最佳化方法淺顯易懂的介紹了一遍
* [Optimizations in C++ Compilers](https://queue.acm.org/detail.cfm?id=3372264) - 比較詳細一點的最佳化
* [一點都不深入的了解 Compiler、 Interpreter 和 VM](https://www.spreered.com/compiler_for_dummies/) - 讓你貼近生活一點1
* [Let’s Build A Simple Interpreter. Part 1. ](https://ruslanspivak.com/lsbasi-part1/) - 讓你貼近生活一點2
* [你所不知道的 C 語言: 執行階段程式庫 (CRT)](https://hackmd.io/@sysprog/c-runtime?type=view) - Run Time 的補充資料
* [2000 行 C 編譯器實做](https://github.com/jserv/shecc) - 教學導向，清楚好懂
* [Compiler explorer](https://gcc.godbolt.org/) 即時預覽一段程式碼及其被編譯出來的組合語言
* Godbolt's talk at cpponsea 2019: [What Everyone Should Know About How Amazing Compilers Are](https://www.youtube.com/watch?v=w0sz5WbS5AM)，快速提供提供幾個範例告訴你 compiler 擅長做什麼以及是如何最佳化的
* Godbolt's talk at CppCon2017: [What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid](https://www.youtube.com/watch?v=bSkpMdDe4g4)

## LLVM
***聽過 GCC 就也要聽過 LLVM***
* [COSCUP2016 - LLVM框架、由淺入淺](https://www.slideshare.net/hydai/coscup2016-llvm) - 影片應該可以在Youtube找到，但是我有點懶
* [LLVM 總是打開你的心：從電玩模擬器看編譯器應用實例 ](https://www.slideshare.net/jserv/nes-llvm) - 其實你也可以自己做一台紅白機，Jserv 最近的課就在做一台 [GameBoy 模擬器](https://www.facebook.com/groups/system.software2020/permalink/486446318956239/)
* [COSCUP 2014 : open source compiler 戰國時代的軍備競賽 ](https://www.slideshare.net/kitocheng/coscup-2014-open-source-compiler) - GCC vs LLVM! 資料有點久了，不過可以大致當個歷史教材看看