CS606 Compiler Construction Assignment No.1 Semester Fall 2012

[Vuhelper]

CS606 Compiler Construction Assignment No.1 Semester Fall 2012


Assignment No. 01
Semester Fall 2012
Compiler Construction CS606
Total Marks: 20
Due Date: 13/11/2012
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
BEST OF LUCK
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”.