CS606 Compiler Construction Assignment No 1 Solution & Discussion Due Date:13-11-2012

[+ M.Tariq Malik]

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]
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”.

[innocent larki]

i have done this one...so w8 m working on it....i will upload after 1 hour

[majida]

thanksssss alotttt in advance m w8ing 4 da solution.....

[innocent larki]

i m not sure about 2nd q ....so do it as ur own

[M saqib khan]

I have tried 2nd Q

[Abdul Waheed]

Yes it is correct. but do not submit this anyone because it will considered as copy paste.