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

### 1. Please find the first and follow sets for the following CFG grammars. `103` `104` `105` `106` `107` `108` `109`
#### $(A)$

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

#### $(B)$

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

#### $(C)$

E -> Prefix(E)
E -> V Tail
Prefix -> F
Prefix -> ε
Tail -> +E
Tail ->  ε

**solve:**
$(A)$
| Nonterminal | First | Follow |
|-------------|----------------|-------------------|
| S | {a, b, c, d} | {$, ε} |
| B | {b, c, d} | {ε, $} |
| C | {c, d} | {ε, $} |

$(B)$
| Nonterminal | First | Follow |
|-------------|---------------|--------|
| S | {a, b, c} | {$} |
| A | {a, ε} | {b, c} |
| B | {b, ε} | {c} |

$(C)$
| Nonterminal | First | Follow |
|-------------|---------------|---------------|
| E | {V, F, $($} | {$, $)$} |
| Prefix | {F, ε} | { $($} |
| Tail | {+, ε} | {$, $)$} |

### 2. For the following grammar **E -> E+E | ExE | (E) | id** `103` `104` `105` `106` `107` `108` `109`

#### $(A)$ Show this grammar is **ambiguous** for input sequence **id+idxid**

     E            E
   /   \        /   \
  E  +  E      E *   E
      / \     / \
     E * E    E +E
 
 id+id*id  | id+id*id     

#### $(B)$ Rewrite this grammar to be a non-ambiguous grammar by adding **precedence** and **association** (Please use **E, T, F**)

#### $(C)$ Eliminate left recursion (if this grammar has) for generating a new grammar

#### $(D)$ Find the **FIRST** and **FOLLOW** sets for each non-terminal

#### $(E)$ Find the predictive table for LL(1) table of this grammar

#### $(F)$ Please show this LL(1) can parse id+id*id by using stack and input queue.

---
**solve:**
$(A)$
The grammer permits two distinct leftmost derivations.
* (1)E
$\Rightarrow$ E + E
$\Rightarrow$ id + E
$\Rightarrow$ id + E * E
$\Rightarrow$ id + id * E
$\Rightarrow$ id + id * id
* (2)E
$\Rightarrow$ E * E
$\Rightarrow$ E + E * E
$\Rightarrow$ id + E * E
$\Rightarrow$ id + id * E
$\Rightarrow$ id + id * id

$(B)$

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

$(C)$

The rewritten grammar has no left recursion.

$(D)$

| Non-terminal | First | Follow |
| ------------ | -------------------------------| ------------------ |
| E | {(, id} | {$, )} |
| T | {(, id} | {+, $, )} |
| F | {(, id} | {*, +, $, )} |
| E' | {+, ε} | {$, )} |
| T' | {*, ε} | {+, $, )} |

$(E)$
| | ( | ) | id | + | * | $ |
| --- | ----- | ----- | ----- | ----- | ----- | ----- |
| E | E → TE' | | E → TE' | | | |
| T | T → FT' | | T → FT' | | | |
| F | F → (E) | | F → id | | | |
| E' | | E' → ε | | E' → + E | | E' → ε |
| T' | | T' → ε | | T' → ε | T' → * T | T' → ε |

$(F)$
| Stack | Input String | Production applied |
| ------------------- | -------------------- | ------------------ |
| $<ins>E </ins> | <ins>id</ins>+id*id$ | E -> TE' |
| $E'<ins>T </ins> | <ins>id</ins>+id*id$ | T -> FT' |
| $E'T'<ins>F </ins> | <ins>id</ins>+id*id$ | F -> id |
| $E'T'<ins>id </ins> | <ins>id</ins>+id*id$ | |
| $E'<ins>T' </ins> | <ins>+</ins>id*id$ | T' -> ε |
| $<ins>E' </ins> | <ins>+</ins>id*id$ | E' -> +E |
| $E<ins>+ </ins> | <ins>+</ins>id*id$ | |
| $<ins>E </ins> | <ins> id</ins>*id$ | E -> TE' |
| $E'<ins>T </ins> | <ins> id</ins>*id$ | T -> FT' |
| $E'T'<ins>F </ins> | <ins> id</ins>*id$ | F -> id |
| $E'T'<ins>id </ins> | <ins> id</ins>*id$ | |
| $E'<ins>T' </ins> | <ins> *</ins>id$ | T' -> *T |
| $E'T<ins>* </ins> | <ins> *</ins>id$ | |
| $E'<ins>T </ins> | <ins> id</ins>$ | T -> FT' |
| $E'T'<ins>F </ins> | <ins> id</ins>$ | F -> id |
| $E'T'<ins>id </ins> | <ins> id</ins>$ | |
| $E'<ins>T' </ins> | <ins> $</ins> | T' -> ε |
| $<ins>E' </ins> | <ins> $</ins> | E' -> ε |
| <ins>$ </ins> | <ins> $</ins> | |
---

### 3. For the regular expression `103` `104` `105` `106` `107` `108` `109`

R1 = (a|b)*bbc
R2 = a(a(a|b)*)*b
R3 = (a|b)*aba
R4 = (a|b)*abb

#### $(A)$ Show the NFA of this R

#### $(B)$ Show the DFA from the previous NFA
https://drive.google.com/drive/folders/1fP3MaLpCkAdFKXhCU2pjaG2KeNzuJW0r
#### $(C)$ Show the Minimize DFA
Chapter 3 page 42 or 43 會給寫法
### 4. Please show the following grammar is not LL(1) `103` `104` `106` `107` `108`

S -> iEtSS'|a
S' -> eS|ε
E -> b

**solve:**
考慮 S' -> ε 的 FOLLOW 集合，它等於 S 的 FOLLOW 集合。因為 S 可以展開為 S'，所以 S' -> ε 可以出現在 S 之後，也就是 S -> iEtSS'ε 的情況下。

現在來看 S -> iEtSS' 的 FIRST 集合和 S' -> eS 的 FIRST 集合：

FIRST(iEtSS') = {i}
FIRST(eS) = {e}

它們的交集不為空，因此無法透過選擇 FOLLOW 集合中的符號來決定該選擇哪個產生式。
### 5. Please identify the following parsers, which parser are belong to Top down approach, and which are belong to Bottom up approach? `104`

a. Operator Precedence
b. LR(0)
c. LR(1)
d. LL(1)
e. Shift-Reduce
f. SLR(1)
g. LALR(1)
h. Recursive Descent

**solve:**
Top down: d, h
Bottom up: a, b, c, e, f, g

### 6. Please use the following examples to demonstrate how to eliminate left recursion.`105` `108`

#### (1) A -> Aα|β
#### (2) A -> Aα1| Aα2| Aα3|β1|β2
#### (3) A -> Aα1| Aα2|β1|β2|γ
**solve:**
(1)
A → βA'
A' → αA' | ε
(2)
A → β1A' | β2A'
A' → α1A' | α2A' | α3A' | ε
(3)
A → β1A' | β2A' | γA'
A' → α1A' | α2A' | ε
### 7. Please use the following grammar to show a only one parsing tree for this sequence `105` `106` `107` `109`

if E1 then if E2 then S1 else S2


### 8. Please describe the main phases (functions) of a compiler in detail (including Error handling and Symbol table).Please must identify front-end and back-end of a compiler. `107` `109`

- Frontend: Scanner, Parser
- Backend: Type Checker, Translator, Optimizer, Code Generator

### 10. Please show the following grammar is LL(1) or not, and why `109`

(a) S -> Sa|a
(b) S -> aS|a
(c) S -> aR|ε, R -> S|ε
(d) S -> aRa, R -> S|ε

**solve:**
$(a)$ Left recursive
$(b)$ First (a*S*) $\bigcap$ First(a) = {a} $\neq \phi$
$(c)$ For *R: S* $\Rightarrow ^*$ $\varepsilon$ and $\varepsilon \Rightarrow ^*\varepsilon$
$(d)$ For *R*: FIRST(S) $\bigcap$ FOLLOW$(R)$ $\neq \phi$