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

# Grammar

## 1. 語法: Backus-Naur Form
### 簡介
- 我們在分析程式的時候，都會使用***Context-free grammar (CFG)***。
- 其中最為常用的就是***Backus-Naur Form***
- CFG有下列的屬性
1. 有一堆***token/terminal*** (最小的有意義單位)
2. 有一堆***nonterminals*** (代換的中間產物)
3. 有一堆***productions*** (代換的規則)
4. 有分析(代換)的***起點***

- 其實就一層層recursion代換下去，以建立AST。(inorder)
- 而當一種語法可以由多種不同的AST呈現時，我們就稱其為***曖昧的(Ambiguous)***。
### 符號
- Define: `::=`
- Nonterminal: `<>, {}, []`
- Alternative/Or: `|`
- Terminal symbols: 直接寫出來。

## 2. Parsing
- 對於所有的***CFG***，parsing的動作必然可以在$O(n^3)$的時間內完成。
### a. Top-down
- 從AST的root開始構造
#### $\alpha$. Recursive descent parsing
- 使用recursion代換
- 每個***nonterminal***都有，也只有一個procedure對應。
- 如果一個***nonterminal***對應到多種不同可能的結果，則使用後續的***token***(***input lookahead***)來進行判斷。
- 效能較差, 限制較少
#### $\beta$. Predictive parsing
- 為***Recursive descent parsing***的一種特殊情形。
- 效能較好，限制較多, e.g. `LL(1)`

### b. Bottem-up
- 從AST的leaves開始構造

## 3. 使用Predictive Parser的細節
我們需要對Grammar做一些處理，使其達到要求後才能使用。
### a. Left Factor
將***production***共同的部份取出，用一個新的***nonterminal***代換。
- e.g.

    stmt -> if (expr) stmt | if (expr) stmt else stmt

化成:

    stmt -> if (expr) stmt rest
    rest -> else stmt | ϵ

### b. Left recursion至Right recursion的轉換
將可能導致無窮迴圈的***Left recursion***改寫成***Right recursion***。
- e.g.

    A -> Aa | b

化成:

    A -> bR
    R -> aR | ϵ

### c. $\epsilon$-Production
去除無意義，只會輸出空字川的$\epsilon$-***Production***
- e.g.

    A -> ϵ

## 4. 其它
### a. FIRST($\alpha$)
- 表示出$\alpha$包含的所有可能為字串之首的token。
- $\alpha$為一個sentential form，可能包含一個或多個terminal, nonterminal
- e.g.

    S->aSe
    S->B
    B->bBe
    B->C
    C->cCe
    C->d

可得

    FIRST(S) = {a, b, c, d}
    FIRST(B) = {b, c, d}
    FIRST(C) = {c, d}