###### tags: `compiler` `note` `thu`

# Compiler: Parsing [WIP]

- 輸入都一樣有一個字串、一個文法
- 輸出也都一樣是一個syntax tree
- 區別在於建構的方式，一個從樹根開始建(Top down)，一個從樹葉開始(Bottom up)。

---
## 1. Top down
- 從整棵樹的樹根開始往下拆。
### a. LL methods
- LL = Left-to-right, Leftmost derivation(從左邊開始代換)
- 期中考之前教到的就是這個。

---
## 2. Bottom up
- 從下面的樹葉開始組回去到樹根。
- 優點：無需改寫文法
### a. Shift-Reduce methods
- 從輸入字串開始，使用Production Rule從leaves往root的方向發展。

#### i. LR-methods
- LR = Left-to-right, Rightmost derivation(從右邊開始代換)
- The Closure operation.
- 每步吃掉symbol(terminal/non-terminal)時都像NFA一樣每個都要推進，推進不了的就消失
- 當遇到non-terminal時，自動新增他的production rule

##### Example:
Consider the following grammar:
- S -> E$
- E -> E + T
- E -> T
- T -> id
- T -> (E)
則:

| # | Actions | Description |
| -------- | -------- | -------- |
| 1 | Shift | 通常簡寫為S，表示移動至下一個狀態 |
| 2 | Reduce | 化簡。簡寫為R。通常加上使用的化簡規則編號。 |
| 3 | Accept | 接受。為Reduce的特殊情形。當Reduce第0個規則時就被稱為Accept.|
| 4 | Error | 當出現未定義的規則時(找不到下一步的方法)，即為錯誤。 |

- 由上方的表格我們可以建構出他的動作table

| State | 0 | 1 |...|
| ------| ---| -------- | ----|
| Action| S | S, A(R0)| ...|

- E後面多一個$是為了使這個文法可以被LR(0)所解析。
- 如果一個State有兩個以上的動作的話(A不算，所以這個表格每個state只有一個)，就不是LR(0)了。
- 如下圖所見，LR(0)需要很強的條件。箭頭方向表示處理不了時的轉移順序。

- 完整範例：

---
- LR(0), SLR(1), Canonical LR = LR(1), LALR(1)
- 有1的表示會多看一個Terminal Symbol
- 會用到的最多就到LR(1)