###### tags: `compiler` `note` `thu`
# Quiz 1

### 1. Please describe the ***main phases (functions)*** of a compiler in detail, including Error handling and Symbol table. `105` `106` `108` `109` `110`


---
### 2. Please describe four components of Context Free Grammar. `105` `106` `108` `109` `110`
- $T$: A set of tokens (terminal symbols)
- 終點是海上的幾個小島
- $N$: A set of Non-terminals
- 到終點之前有多個中間島
- $P$: A set of productions
- 中間島之間互相有交通工具
- $S$: A designated start symbol
- 勇者從起點出發

---
### 3. Please describe the five tuples $(Q, \Sigma, \delta, q_0, F)$ of a NFA. `105` `109` `110`

#### $Q$: A finite set of states. (狀態)
- For example, Q = $\{q_0, q_1, q_2\}$.
#### $\Sigma$: A finite input alphabet. (可能的輸入)
- For example, Σ = $\{a, b, c\}$.
#### $\delta$: A transition function that maps each state and input symbol (or empty string) to a set of states. (對輸入的處理, e.g. 改變狀態)
- For example, $\delta(q_0, a) = \{q_0, q_1\},\ \delta(q_1, b) = \{q_2\}\ and\ \delta(q_2, \epsilon) = \{q_1\}$.
#### $q_0$: The initial state of the automation. (初始狀態)
- For example, $q_0$.
#### $F$: A set of accepting (or final) states. (接受狀態)
- For example, $F = {q_2}$.

---
### 4. Ambiguous grammar. `105` `106` `108` `109` `110`

#### A. What is an ambiguous grammar?

Ambiguous grammar是一種CFG，其中存在一個token可以有多個production或parsing tree

#### B. Please show that the following grammar is ambiguous.

E->E+E|E-E|E×E|E/E|(E)|id

`idxid+id`可由不同的代換順序組合而成，因此為Ambiguous。
1. E -> E + id -> ExE + id -> idxid + id
2. E -> ExE + E -> idxid + E -> idxid + id
#### C. Rewrite this grammar to be non-ambiguous grammar by adding precedence and association.

E -> E+T | E-T | T
T -> TxF | T/F | F
F -> (E) | id

#### D. Eleminate ***left recursion*** (if any) for generating a new grammar.

E -> TE'
E' -> +TE' | -TE' | ε
T -> FT'
T' -> xFT' | /FT' | ε
F -> (E) | id

---
### 5. Please find the first sets for the following two CFG grammars: `105`
#### A.

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}

#### B.

S->ABc
A->a
A->ε
B->b
B->ε

則:

First(S) = {a, b, c} // 前面的ε會被後面的terminal吃掉
First(A) = {a, ε}    // 因為空字串後面如果接了非空字串
First(B) = {b, ε}    // 整個就會變成非空字串(第一個token自然就不會是ε)

---
### 6. For the following regular expressions, find the NFA, DFA, minimized DFA. `105` `106` `108` `109` `110`
#### A. $R_1$ = (a|b)*abc
#### B. $R_2$ = (a|b)*abb
#### C. $R_3$ = a(a(a|b)*)*b
#### D. $R_4$ = a*b+
#### E. $R_5$ = ε|(a*b)

---
### 7. Please describe the ***Regular Expressions for the following*** NFAs, respectively. `106` `108`
#### 1. $(abc^+)^+$
#### 2. $(a|b)^*abb$

---
### 8. Please identify the following parsers that which parser belongs to Top down approach, and which belongs to Bottom up approach? `106` `108` `109` `110`
#### a. Operator Precedence
#### b. LR(0)
#### c. LR(1)
#### d. LL(1)
#### e. Shift-Reduce
#### f. SLR(1)
#### g. LALR(1)
#### h. Recursive Descent
#### i. Predictive
- Topdown: d, h, i
- Bottom up: a, b, c, e, f, g

---
### 9. If `r` and `s` are regular expressions denoting languages `L(r)` and `M(s)` respectively, please find the following language: `109` `110`

| expression | Language |
| -------- | -------- |
| `r \| s` | $L(r)\cup M(s)$ |
| `rs` | $L(r)M(s)$ |
| `r*` | $(L(r))^*$ |
| `r+` | $(L(r))^+$ |
| `r` | $L(r)$ |

---
| Component | DFA | NFA |
|--------------------|-------------------------------------------|-----------------------------------------------|
| Alphabet | Finite set of input symbols | Finite set of input symbols |
| States | Finite set of internal states | Finite set of internal states |
| Start State | Single designated initial state | Single designated initial state |
| Transition Function| Maps each state and symbol to one state | Maps each state and symbol to a set of states |
| Accepting States | Subset of states that accept the input | Subset of states that accept the input |

:100: