CS606 Compiler Construction Assignment No. 1 Ideal Solution Fall 2014

[Entboy]

CS606 Compiler Construction Assignment No. 1 Solution and Discussion Fall 2014


Question No 1: Marks 10
Let CFG be G = (N,T, S, P) where;

N = {<goal>, <expression>, <term>, <factor>}
T = {A, B, C, *, +}
S = <goal>
P=<1,2,3,4,5,6,7,8,9,10>
Derive the expression “A *B+C”. [5 Marks]
Construct a parse tree for expression “A *B+C”. [5 Marks]
Question No 2: Marks 10
Construct Nondeterministic finite automata (NFA) for regular expression (ab|ba)* by using Thompson’s Construction Algorithm

Ideal Solution

[B]Production[/B]	[B]Result[/B]
	<goal>
1:<goal>?<expression>	<expression>
2: <expression>?<expression><factor><term>	< expression><factor><term>
5: <term>?C	< expression><factor>C
7 :< factor>? +	< expression> + C
2: < expression>?< expression><factor><term>	< expression><factor><term> + C
4: <term>? B	< expression><factor> B+C
6: <factor>? *	< expression> *B+C
3: < expression>? <term>	<term> *B+C
5: <term>? A	A*B+C