11-25-2014, 09:17 PM
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
[TABLE="width: 479"]
[TR]
[TD="width: 298"]
[B]Production[/B]
[/TD][TD="width: 299"]
[B]Result[/B]
[/TD][/TR]
[TR]
[TD="width: 298"][/TD]
[TD="width: 299"]
<goal>
[/TD][/TR]
[TR]
[TD="width: 298"]
1:<goal>?<expression>
[/TD][TD="width: 299"]
<expression>
[/TD][/TR]
[TR]
[TD="width: 298"]
2: <expression>?<expression><factor><term>
[/TD][TD="width: 299"]
< expression><factor><term>
[/TD][/TR]
[TR]
[TD="width: 298"]
5: <term>?C
[/TD][TD="width: 299"]
< expression><factor>C
[/TD][/TR]
[TR]
[TD="width: 298"]
7 :< factor>? +
[/TD][TD="width: 299"]
< expression> + C
[/TD][/TR]
[TR]
[TD="width: 298"]
2: < expression>?< expression><factor><term>
[/TD][TD="width: 299"]
< expression><factor><term> + C
[/TD][/TR]
[TR]
[TD="width: 298"]
4: <term>? B
[/TD][TD="width: 299"]
< expression><factor> B+C
[/TD][/TR]
[TR]
[TD="width: 298"]
6: <factor>? *
[/TD][TD="width: 299"]
< expression> *B+C
[/TD][/TR]
[TR]
[TD="width: 298"]
3: < expression>? <term>
[/TD][TD="width: 299"]
<term> *B+C
[/TD][/TR]
[TR]
[TD="width: 298"]
5: <term>? A
[/TD][TD="width: 299"]
A*B+C
[/TD][/TR]
[/TABLE]