loading...

CS606 Compiler Construction Assignment No 1 Solution Fall 2012

Question No 1: Marks 10
Let CFG be G = (Vn, Vt, S, P) where Vn = {<goal>, <expression>, <term>, <factor>}, Vt = {1, 2,
3, x, y, z, -, +}, S = <goal> and Productions(P) are;
<goal> <expression>
<expression> <term> / <expression> + <term>
<term> <factor> / <term> – <factor>
<factor> 1 / 2 / 3 / x / y / z
Considering the above productions of a CFG, you are required to do the following tasks:
a. Derive the expression “x + 2 – y”. [5 Marks]

Productions Result
  Goal
1:goal→expr expr
2:expr→expr+term expr+term
3:term→term-factr expr+term-factr
4:factr→y expr+term-y
3:term→factr expr+factr-y
4:factr→2 expr+2-y
2:expr→term Term+2-y
3:term→factr Factr+2-y
4:factr→x x+2-y

b. Construct a parse tree for the expression “x + 2 – y”. [5 Marks]

Question No 2: Marks 10
Construct Nondeterministic finite automata (NFA) for regular expression (a | b)* using Thompson’s Construction Algorithm. Show the sequence of moves made by each in processing the input string “ababbab”.

DOWNLOAD SOLUTION HERE
loading...