P PLIL M IC N print Er M print \"W\" W TWIE C if E {P if E {P) else tP) (note: t

Question

P PLIL M IC N print Er M print "W" W TWIE C if E {P if E {P) else tP) (note: this has a variable o) E CEOE) IV V 0 112 I 3 (note: this has a terminal 0 (zero)) T a I b I c Id 1 Define G [10%] Show the set of variables of G Show the set of terminals of G What is the start variable of G? 2 Proving G is not LL(1) [10%] Prove that G is not an LL(1) grammar. 3 Transforming G [15%] Find an equivalent grammar G which is LL(1), by using the grammar transformation techniques shown in lectures, or otherwise. Describe the process and show your working. 4 LL(1) parse table [15%] Complete the LL(1) parse table for G. Describe the process and show your working, including: 1. FIRST sets for all the production rules of G 2. FOLLOW sets for variables of G only if they are needed

Explanation / Answer

1. Set of Variables= {P,L,M,N,W,C,E,O,V,T}

   Set of terminals = { ;,print,",{,},if,else,(,),+,-,*,0,1,2,3,a,b,c,d}

Start Variable = {P}

2. G is not LL(1) grammar because it has Left Recursion in the production PPL . And it also has Non determinism in the production Cif E {P} | if E {P} else {P}. For the grammar to be LL(1) it should be free from Left Recursion and Non-determinism.

3. We can remove Left recursion and Non determinism to make the grammar LL(1).

Elimination of Left Recursion:

If AA|

then A A

        A A |

Lets remove the Left recursion from the grammar:

if PPL|L

then

PLP

PLP|

Removal of Non Determinism:

If A -> |

then

A -> A'

A' -> |

This is also known as Left Factoring.

Lets Left factor the Given Grammar:

Cif E {P} | if E {P} else {P}

then

Cif E {P} C'

C' else {P} |

Hence, the complete Grammar G' is :

PLP

PLP|

LN; | M; | C

N print E

M print “W”

WTW |

Cif E {P} C'

C' else {P} |

E (EOE) | V

O + |-|*

V 0|1|2|3

T a|b|c|d

I hope this has helped you. Feel free to ask any doubts if you have any. Good Luck !

VARIABLES FIRST FOLLOW P print,if $,} P' print,if, $,} L print,if print,if N print ; M print ; W a,b,c,d, " C if print,if C' else, print,if E (,0,1,2,3 ;,+,-,*,) O +,-,* (,0,1,2,3 V 0,1,2,3 ;,+,-,*,) T a,b,c,d a,b,c,d,"

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.