---
# System prepended metadata

title: Mid 1
tags: [thu, note, compiler]

---

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

### 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
```
```
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,ε}
First(A) = {a,ε}
First(B) = {b,ε}
```
#### $(C)$
```
E -> Prefix(E)
E -> V Tail
Prefix -> F
Prefix -> ε
Tail -> +E
Tail ->  ε

```

```
First(E) = {F,V,ε}
First(Prefix) = {F,ε}
First(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 x E
                     /   / \                        / \   \
                    /   E x E                      E + E   \
                   /   /     \                    /     \   \
                  id + id  x  id                 id  +  id x id
```
#### $(B)$ Rewrite this grammar to be a non-ambiguous grammar by adding **precedence** and **association** (Please use **E, T, F**)
```
E -> E + T | T
T -> T x F | F
F -> (E) | id
```
#### $(C)$ Eliminate left recursion (if this grammar has) for generating a new grammar
```
E  ->  TE'
E' -> +TE' | ε
T  ->  FT'
T' -> xFT' | ε
F  ->  (E) | id
```
#### $(D)$ Find the **FIRST** and **FOLLOW** sets for each non-terminal
```
First(E)  = {(,id}  Follow(E)  = {$,)}  
First(E') = {+,ε}   Follow(E') = {$,)}
First(T)  = {(,id}  Follow(T)  = {+,$,)}
First(T') = {x,ε}   Follow(T') = {+,$,)}
First(F)  = {(,id}  Follow(F)  = {x,+,$,)}
```
#### $(E)$ Find the predictive table for LL(1) table of this grammar



|   | ( | ) | + | x | id | $ |
|---|---|---|---|---|----|---|
| E | E -> T E' |  |  |  | E -> T E' |  |
| E' |  | E' -> + T E' |  | E' -> ε |  | E' -> ε |
| T | T -> F T' |  |  |  | T -> F T' |  |
| T' |  | T' -> ε | T' -> + F T' | T' -> x F T' | T' -> ε | T' -> ε |
| F | F -> ( E ) |  |  |  | F -> id |  |



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

![](https://i.imgur.com/kHAgNNp.jpg =75%x)


### 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

#### $(C)$ Show the Minimize DFA

### 4. Please show the following grammar is not LL(1) `103` `104` `106` `107` `108`

```
S -> iEtSS'|a
S' -> eS|ε
E -> b
```
要證明一個文法不是LL(1)文法，需要找到至少一個產生式在解析表中出現衝突。當表中對於相同的非終端符號和輸入符號有多個輸入時，就會發生衝突。

這個文法的解析表：
|   | i  | a  | e  | b  | $  |
|---|---|---|---|---|---|
| S | S -> iEtSS' | S -> a |    |    | S -> a |
| S' |             | S' -> ε | S' -> eS |    | S' -> ε |
| E |             |      |    | E -> b |    |

### 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
```
```
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α|β
```
A  -> βA'
A' -> αA' | ε
```
#### (2) A -> Aα1| Aα2| Aα3|β1|β2
```
A  -> β1A' | β2A'
A' -> α1A' | α2A' | α3A' | ε
```
#### (3) A -> Aα1 | Aα2 | β1 | β2 | γ
```
A  -> β1A' | β2A' | γ
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
```
![](https://i.imgur.com/ZoRJ8zs.png)

### 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`

### 9. For each A -> αB or αBβ, where ε$\in$ FIRST (β), add all of FOLLOW(A) to FOLLOW(B) `107`
![](https://i.imgur.com/6QpIze2.png)

### 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|ε
```

a: $No , Left\space recursive$
b: $No , First(aS) \cap First(a) = \{a\} \not=\varnothing$
c: $No , For\space R:S\implies*ε \space and\space ε\implies*ε$ 
d: $No, For\space S: First(R)\cap Follow(S)\not=\varnothing$
