CS606 Compiler Construction Assignment 1 Solution Spring 2014

Assignment No. 01 Semester: Spring 2014 Compiler Construction CS606

Total Marks: 20 Due Date: 12/05/2014

Objective: To learn and understand basic concepts of Context free grammar, parse tree, regular expression, deterministic and nondeterministic finite automata in building a Lexical analyzer.

Instructions: It should be clear that your assignment will not get any credit (zero marks will be awarded) if: o The assignment is submitted after due date. o The submitted assignment does not open or file corrupt. o The assignment is copied (from other student or copy from handouts or internet). o Student name and ID are not mentioned in the assignment file. o It is in some format other than .doc or .docx(MS Word Document). For any query about the assignment, contact at cs606@vu.edu.pk

Question No 1: Marks 10 Let CFG be G = (Vn, Vt, S, P) where;  Vn = {, , , }  Vt = {x, y, z, -, +}  S = You are required to: 1. Derive expression “x – y + z”. [5 Marks] 2. Construct a parse tree for expression “x – y + z”. [5 Marks]

Question No 2: Marks 10 Construct Nondeterministic finite automata (NFA) for regular expression (a | a*b) using Thompson’s Construction Algorithm.