# Compiler (Online course)

## Week 1 (Introductiion & the Cool Programming Language)


### Structure of compiler

1. Lexical Analysis (詞彙分析)
空白鍵為 token 之一

2. Parsing (語法分析)
將一段程式碼分成 parsing tree

3. Semantic Analysis (語意分析)
分析語意是否正確

4. Optimization (最佳化)
- 注意有浮點數的情況，運算時要考慮值有可能是 `NAN`

5. Code generation
轉化為組合語言或機械語言

### The economy of programming languages
- 要在舊的程式語言當中新增新的功能會消耗相當大的成本，所以一直會有新的程式語言推出，除此之外在不同的領域內適合的程式語言也不一樣。新的程式語言會依循先前的語言所開發，使得程式開發者會需要花很多的時間適應新的程式語言。

### cool overview (Classroom Object Oriented Language)
一隻為了 compiler 課程開發出來的程式語言，透過由 C++ 寫成的編譯器 (coolc) ，會將程式碼編譯成 MIPS 組合語言，並使用 (spim) 這個 simulator 來執行程式
範例 1：

class Main inherits IO {
  main() : Object {
    out_string("Hello, world!\n")
  };
};

- 程式一定要有 class Main，且裡面要有 main() 函式
- 函式冒號後面為 return type

範例 2:
- a2i 表示 ACII to INT
- if 的結尾要有 fi
- 此程式為計算 n 階層數值大小

範例 3:
- 迭代版計算階層
- loop 結尾要加 pool
- let 用來變數宣告，最後面還要加一次變數名稱 (不確定此用法，待驗證)
- `=` 在 cool 裡面代表 comparison

範例 4:
- List 為一個用來串接字串用的 class，此 class 含有兩個 element ，`next` 為一個 `pointer` 指向下一個要被串接的字串
- `flatten` 為印出完整字串的函式
- case 用法 --> 依照 item type 而 return 不同的值
- cool 內沒有所謂的 `null` ，要用空指標就需要直接宣告一指標當空指標，注意 `isvoid` 用法

>[wiki](https://en.wikipedia.org/wiki/Cool_(programming_language))
[The Cool Reference Manual](https://theory.stanford.edu/~aiken/software/cool/cool-manual.pdf)
>

## Week 2 (Lexical Analysis & Finite Automata)

### Lexical Analysis
- Token Class (< token class, substring >)
- Identifier (英文開頭)
- Keyword (`while`, `if` ...)
- Numbers
- Whitespace (包含 `\t`, `\n`)
- operator (包含標點(punctuation))

#### Lookahead Problem
- 程式語言是否忽略空白
- 讀到第一個 `=` 時不確定是 `assignment` 或是 `equal`
- 讀到第一個 `e` 時不確定是 `keyword` 還是 `variable`

#### Unbounded Lookahead
以下程式語言的 `keyword` 可以拿來當作 `variable` 使用，欲知道 `DECLARE` 是 陣列名稱或是 `keyword` 需要先去最前面看是否有 `=` 存在才能判斷，然後裡面的 `ARG` 可以有無限多個，稱之為 `unbounded lookahead`

#### Conclusion

### Regular Language
- Epslon 不是 `empty language` 而是有一個 `empty string` 的 `langa
- Epsilon 永遠是 `Iteration` 的一個子集合
- Regular Expression over `sigma` ，代表 `sigma` 內的 `element` 可以做以下運算

#### Example
- 1* 表示 `i` 個 1 做聯集
- (1 + 0)1 表示 1 和 0 做聯集再串接 1
- 紫色表示有多種形式皆能表示成等號右邊的樣子

#### Conclusion

### Formal Language
- regular language 為一種 formal language
DEF:

#### Meaning Function (L)
透過 `L` function 將 `expression` (syntax) 映射成 `sets string` (semantics)

#### Seperate syntax from semantics
`syntax` 與 `semantics` 並不是 1 對 1 映射的，可以是多對一，例如：阿拉伯數字與羅馬數字符號雖不同，但語意是相同的
>compiler 的最佳化就用到此觀念
>

### Lexcical Specifications
**Keyword specifications (keyword 的闡述)**
**Integer specifications**
**Identifier specifications**
**Whitespace specifications**
**floatint**
:::info
特殊符號
:::

#### Step

- `R` 為總集合
- 反覆上述步驟分析 `input`
- 將 `input` 歸類成多個 `token class`
**特例 1**
- 總是取 `Maxmal Munch`
>參考 [quiz1](https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/courseware/708cb92d25c24fbdad592929b4a80917/474787266e5f48e8a5af71a0f9b29978/?activate_block_id=i4x%3A%2F%2FEngineering%2FCompilers%2Fsequential%2F474787266e5f48e8a5af71a0f9b29978)
- 右邊是拿 `==` 當作例子 (`assignment` or `equal`)
**特例 2**
- 當有一個 `input` 符合多個 `token` 時，選擇優先權較高的適用
**特例 3**
- 當 `input` 不符合任何 `token` 時，發出錯誤訊息

#### Conclusion

### Finite Automata (有限狀態機)
A good implementation modle for regular expression
#### DEF:
#### Example 1:
- 箭頭代表 `input poointer`
- 當 get stuck in accepting state 的時候，若 `input pointer` 還沒指最底會發生 `reject`
- 在 `start state` 收到沒有被定義的 `input` 時也會發生 `reject`

#### Example 2:

#### Epsilon move:

#### DFA v.s. NFA

- DFA
- 同一個 `input` 不能有兩條路境
- 不能有 `epsilon-moves`
- 所需時間較短 (不用判斷多種 case )
- 所需空間較大
- NFA
- 同一個 `input` 可以有多條路徑
- 所需時間較長
- 所需空間較小

### Lexical analysis (流程)
#### 流程圖
- 前兩階段是"定義" `Regular expressions`
- 後面為 `implementation`

- 每個 rexp(regular expression) 都要定義一個 `NFA`

#### Example 1:

#### Example 2:
- 由內而外畫
- 先把 `(1 + 0)` 畫好

### NFA -> DFA
- 有時候要直接表示成 `DFA` 比較困難，需要先表示成 `NFA` 再轉換成 `DFA`
- 轉換的原則是將合併後的 `state` 看成一個 `state`,例如: {q0,q1} 為一個 `state`
- 在 `NFA` 當中有 `n` 個 `state`，則 `DFA` 最多會有 `2^n - 1` 個 `state`
> `state` 的組成方式為 {q0, q1, q2.... qn} ，每個 `state` 都有"要"或者"不要"兩個選項，總共能組成 `2^n` 個不同的 `state` ，減掉全部都"不要"，所以最多會有 `2^n - 1` 個 `state`
>
- 因為 `NFA` 轉 `DFA` 的 `state` 數目為有限值 `2^n - 1`，因此可以保證轉換一定成立
>範例
>[[Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata](http://www.evanlin.com/moocs-coursera-automata-note1/)
>[Theory of Computation | Conversion from NFA to DFA](https://www.geeksforgeeks.org/theory-of-computation-conversion-from-nfa-to-dfa/)
>
### Table driven implementation
- 將 `DFA` 話成 table ，可用程式表示
- 使用二維陣列紀錄

- 使用一維陣列用指標紀錄
- 可將一樣的狀況指向同一塊記憶體位址，進而節省空間

- NFS 也可以畫成 table`
- 速度較慢，空間較小

### Quiz 1 回顧
- 記得 `Maximal munch` ，在做 `produces the tokenization` 時要找最長符合的結果
- 第三題的部份也是要找 `max` 所以答案為 3、4 則一，但不懂為什麼 3 的 `priority` 較高
- 第十題要從全部 `0、1` 能組合出的集合，扣掉題目所給的集合

## Week 3 (Parsing & Top-Down Parsing)
### Introduction to Parsing
`Lexer` 將 `input` 轉成 `tokens` 之後，下一步就是將 `token` 丟給 `parser` 做進一步的處理
`Lexer` 無法 `check the syntax` ，例如：`Lexer` 無法明確分析出有幾個括號 (這對程式語言來說是很重要的)，像是第二張圖，它就只能分析出有偶數個 `1` 或者奇數個，但這對於編譯器來說是不夠用的。
我們可以剖析( parse ) 一個字串，逐字對應至 `Grammar` 確立語法，進而判斷原本字串是不是 `Language` 當中的字串。
Regular Language 的極限：正規語言是循序性的語言，不具備從屬關係、階層關係、巢狀結構、樹狀結構、遞迴結構。

#### Parser Tree

### Context Free Grammers (上下文無關文法)
#### 定義
- Terminals: 定義好的符號 ex: {0,1}
- non-terminals: 又稱 `variables` 有限集合的符號 ex: {A,B,S}
- Start Symbol: 類似於 RE 中的 `start state` ex: S
- Production: 稱為"投射"，一種對應關係，將 `non-terminals` 映射到 `non-terminals` 或者 `terminals` 通常用 `->` 表示 ex: S->S|0|1
- Derivations: 稱為"推導"，將 CFG 從 `Start symbol` 開始，投射多次後達到推導結果，符號為 `=>`
>`Production` 指的是從 A 映射到 B 的"方法"，`Derivations` 則是指從 `start symbol` 開始推導到我們想要的結果這段"推導過程"
>

#### 基本範例
先來點簡單的範例

將 `derivation` 過程轉成 `parse tree`
>`parse tree` 的規則
>
>
#### 左衍生 vs. 右衍生

依照消除的順序不同又可以分成 `左衍生 leftmost derivation` 和 `右衍生 rightmost derivation` ，這兩種方法推導出來的字串"完全相等"，可以任意互換

#### 曖昧文法 (ambiguous Grammar)
曖昧文法指的是同一個 `string` 可以對應到兩顆不同的 `parse tree` ，再做 `parse` 時應避免曖昧文法的出現，ex:

曖昧文法在 `parse tree` 上的結果

**if else then 的例子**

if Expression then
    if Expression then
    
    else ....

考慮上述情況，我們傾向將 `else` 看作離它最近的 `then` ，上述例子則會將 `else` 視為第二個 `if then` 的情況

#### 解決曖昧文法
最直接的方法就是 `rewrite grammar`

有時候 `rewrite grammar` 對我們來說是很困難的，我們可以使用較直覺的方法，設定 `優先權 precedence` 和 `關聯性 associativity`


> `associativity` -> 當 `priority` 相同時左邊優先於右邊處裡 ex: `1 - 2 + 3 = 0 != -4`
> `precedence` -> 不同的優先權 ex: `+`、`*`
> `associativity` 在 `wiki` 上的例子
>
>

### Error Handling
分為 `Lexical 詞彙的錯誤` ， `syntax 語法的錯誤` ， `Semantic 語意的錯誤`

Panic mode

Error correction
- 試著修正錯誤的 program
- 很難實現
- 會降低 `parsing` 的速度
- 修正錯誤


#### Abstrct Syntax Trees (AST)
`AST` 為一個資料結構，是簡化 `parse tree` 過後的結果
ex: 5 + (2 + 3)

### Recursive Descent Parsing
`Descent` 的意思是下降，`RDP` 是指程式碼用 `recursive top down` 的方法做 `parsing`
>影片中後半段有詳細的過程可以參考
>[參考](https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/courseware/0a40e5575adf4310a4046e8500760cfc/2e6a6dd7f3a54326aa132b36dbcd3d7d/?child=first)
>

程式碼實踐
>其中 `return` 得 `next = save` 是為了做 `backtrack` 使用，也就是說 `E1()` 若錯誤，需要把指向 `string` 的 `pointer` 歸還為初始位址
>

**Recursive Descent Limitations**
當程式比對到第一個一樣時就會直接套用，`string` 後面如果不一樣則無法做 `backtrack` ，看例子比較好明白
- 上面程式應該要將 `T 換成 int * T` 才能有正確的結果，但 `recursive` 第一次比對到 `int` 和 `input string` 的最前面符合後，就無法做 `backtrack` 了

>正常的演算法應該會避免此問題，但這裡為了簡單解釋就沒有考慮
>

#### Left Recursion
此種狀況在 `recursive descent` 中會造成無限迴圈，因此在做 `recursive descent` 時要先將 `left Recursion` 消除

>參考文獻
>[自動機理論-Automata筆記-第三週: ](http://www.evanlin.com/moocs-coursera-automata-note3/)
>[Language / Grammar](http://www.csie.ntnu.edu.tw/~u91029/Language.html)
>

## Weeek 4 (Bottom-Up Parsing)
### 7-01 Predictive Parsing and LL(1)
介紹如何使用 `parsing table` ，之後舉 `LL(1)` 當例子，而 LL(1) 還是 `top down` 的 `parsing
#### DEF
- By looking at the next few tokens
- No backtracking
- lookahead restricted grammers
- LL(K) (left-to-right, leftmost, k token lookahead)
- 指透過 `parsing table` 達到 `predict` 的效果，不像之前需要每個可能都試試看，若錯誤再用遞迴修正。這裡的 `predict` 根上面的 `lookahead` 的 `k` 是不一樣的東西，`k` 是指往後看幾個 `input` (不確定有沒有理解錯誤)

#### LL(1)
- Top down parsing
- At each step only one choice of production (改寫 `grammer` 使其只有唯一可能)

- By "Parsing table" (透過查表的方式可以避免遞迴)


#### Parsing table

- 若 `parsing table` 內對應到的為空，則代表 `error` 的發生
- `Parsing table` 的建立可以依靠下面所講的 `First()` 和 `Follow` 來實踐



### First() and Follow()
#### Why First() and Follow

First()
- 可用來避免遞迴的發生
- 有現在的 `state` 還有 `input` 再加上 `First() set` ，就可以知道目前的 `state` 拿到這個 `input` 後應該 `derive` 的結果
- Example
- 有了 `First()` 就可以知道 `A` 應該 derive 成 `a` 而不是 `bc`

Follow()
- can make a Non-terminal to vanish out if needed to generate the string from the parse tree.
- Example
- 試想再沒有 `Follow()` 的情況下，若 `C` 沒能指向 `b` ，則結果會發生 `error` ，`Follow()` 感覺可以理解成 `lookahead`

>參考
>[Compiler Design | Why FIRST and FOLLOW?](https://www.geeksforgeeks.org/compiler-design-why-first-and-follow/)
#### First()
- If there is a variable, and from that variable if we try to drive all the strings then the beginning Terminal Symbol is called the first.
- 這個函數的集合是 `Terminal Symbol`
- 集合是由 `Non terminal` 衍生出來的
- Example
補充：
- First(E) = First(T) = First(F)...

>參考
>[Compiler Design | FIRST Set in Syntax Analysis
](https://www.geeksforgeeks.org/compiler-design-first-in-syntax-analysis/)

#### Follow()
- What is the Terminal Symbol which follow a variable in the process of derivation.
- 此函數的集合也是 `Terminal Symbol`
- Rules
- Example
- 在找 `follow()` 的時候要特別注意 `non terminal` 可能會指向"空"，如 `example2` 的 `Follow(A)`

>參考
>[Compiler Design | FOLLOW Set in Syntax Analysis](https://www.geeksforgeeks.org/compiler-design-follow-set-in-syntax-analysis/)
>

#### convert to LL(1) Parsing table
The table without `epsilon` (e)

The table with `epsilon` (透過 `follow()` 決定)

>參考
>[Compiler Design | Construction of LL(1) Parsing Table](https://www.geeksforgeeks.org/compiler-design-construction-of-ll1-parsing-table/)
>

### Bottom up Parsing
- 較廣泛使用
- 分類
- L -> left-to-right
- R -> rightmost
- SLR -> simple LR
- Rightmost
- a bottom-up parser traces a rightmost derivation in reverse
- 從 `root` 開始看，每次做 `parsing` 都必須是對最右邊的 `non-terminal` 做

#### 一些術語介紹
**Right sentential forms**
- 從右邊化簡的形式
**handle**
- is a substring that matches the body of the prodution, and whose reduction represents one step along the reverse of rightmost derivation
- 可以透過 `grammer` 做轉換的叫做 `production` ，而轉換結果最後能導致走向唯一對的路徑稱之為 `handle`
- Example
- 按照 `grammer` (參考課本之)，第三步驟的 `T` 可以變成 `E` ，但此一步驟會導致最後無法化簡成一個 `E` ，應此 `E -> T` 不是 `handle`
- 決定 `handle` 的問題可以視為決定 `shift or reduction` 的問題

**Item**
- item of grammer G is a production of G with a dot at some position of the body
- example

**Closure**
- 
- 可以看成是某個 `item` 最後能走到的所有路徑到包含在 `closure` 裡面
- Example

**Viable Prefixes**
- The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes.
- `stack` 放的東西是之後可以被 reduced 的
- 同一種 `viable prefix` 情況下可能會有多條可行路徑
- Example
例子中 (E + T *) 是 `viable prefix` 且有 3 條可行路徑

**GOTO function**
- GOTO(I,X)
- I is a set of items (ex: E -> T), also called `state`
- X is a grammer symbol
- specifies the transition from state for `I` under input `X`
- Example

:::info
`closure` 和 `GOTO function` 都是為了要描述 `bunttom up parsing` 的演算法所用的專有名詞
下面是一個 `LR(0)` 演算法的狀態圖 (automation) ，該圖中每個 `state` (I) ，都代表一個 `closur` ，而每個轉換 `state` 的箭頭都代表一個 `GOTO function`
:::

### Shift-Reduce Parsing
- 一種 `bottom-up parsing`
- 用一個 `stack` 來儲存 `grammer symbol` (當前已經從 `input` 轉換成 `grammer symbol` 的部份)
- 用一個 `input buffer` 來儲存還沒被 `parse` 的 `data`
- `handle` 總會產生在 `stack` 的最上面
- 此演算法會有四種 `Action`
- Example

#### Conflicts During Shift-Reduce Parsing
- 衝突的發生在於不知道要選擇做 `shift` 還是 `reduce` ，有可能做 `reduce` 的 `grammer` 並不是 `handle` 而導致錯誤
- Example
- 當遇到 if...then... 時不確定要作 `reduction` 或者 `shift`，有可能後面還有接 `else`

### Introduction to LR Parsing: Simple LR (SLR)
- A table-driven parsing, like LL parsers
- An LR parser makes shift-reduce decisions by maintain state (I) to keep track of where we are in a parse.
- 簡而言之就是在一個狀態機上 `automaton` 根據拿到的 `input` 做移動，若不能移動就做 `reduction` ，最後會移動到 `accept state`
- Algorithm
- 中間的 `parsing program` 不會改變，會改變的只有 `GOTO` 和 `ACTION`
- `program` 拿到 `input` 後，拿 `(state,input)` 去 `table` 比對現在該做什麼事
- 做 `shift` 的話會改變 `state` ，但不會產生新的 `grammer`
- 做 `reduce` 也會改變 `state` ，但會產生新的 `grammer`
- `input` push 到 stack 後，完全用 `state` 表示 `input` ，一個 `state` 的順序只會對應到一組 `input` 順序
- start state `s0` dosen't represent a grammer symbol, and serves as a bottom-of-stack maker
- 做 `reduce` 完畢後把產生的 `grammer` 從 `stack` pop 出來，並用剩下的 `grammer` 代表的 `state` 做 `GOTO` 的動作

- example 1 (給予狀態圖表)

- example 2 (給予 parsing table)
- 感覺這裡的 `Action` 做的事也符合 `GOTO function` 的定義，應該只是名詞問題

>龍書 273~279 未看
>

:::warning
# Some resource
- [Writing your own programming language and compiler with Python](https://blog.usejournal.com/writing-your-own-programming-language-and-compiler-with-python-a468970ae6df)
- [Create a working compiler with the LLVM framework, Part 1](https://www.ibm.com/developerworks/library/os-createcompilerllvm1/index.html)
- [The Design of a Custom 32-bit RISC CPU and
LLVM Compiler Backend](https://scholarworks.rit.edu/cgi/viewcontent.cgi?article=10699&context=theses)
:::

###### tags: `class note`