# CS606 Assignment 2 Solution Spring 2018

CS606 – Compiler Construction

Total Marks: 20

Due Date:

May 28, 2018

Instructions

Please read the following instructions carefully before submitting assignment:

It should be clear that your assignment will not get any credit if:

o        Assignment is submitted after due date.

o        Submitted assignment does not open or file is corrupt.

o        Assignment is copied (From internet/ to from students).

Software (s) Used to develop Assignment

–          MS Word

–          MS Paint

Assignment Submission Instructions

Microsoft Word file is required to submit on LMS.

Assignment

Task 1: [Marks = 4]

Draw NFA of Regular Expression of table of 5 (Assignment 1 – Task1). Correct RE is provided below;

X = {1+2+3+4+5+6+7+8+9}

Y = {1+2+3+4+5+6+7+8+9+0}

RE =   (0+5) + (XY*(0+5))

Task 2: [Marks = 4 * 2 = 8 * 2 = 16]

Prove that which of the following grammars are ambiguous or not; (No marks are awarded if parse tress are not attached in solution and 2 parse trees are required to justify your answer for each grammar)

i –

S → AB | C

A → aAb | ab

B → cBd | cd

C → aCd | aDd

D → bDc | bc

If String “aabbccdd” is produced from the above grammar using parse tree, would it be ambiguous or not?

ii –

S → XYX | XYX | XYX | XYX

X → S | Z

Y → + | – | * | /

Z → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

If we are trying to produce String “9+2+4*8/5*4-3”, would this grammar seems to be ambiguous?