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