Qualification Exam Programming and Compiler Part

Posted on by
Reply

(Fall 2008)

1) Compare a non-tail recursive and a tail recursive in run time behavior context
2) Why Left recursive production cannot be in LL(1)?
3) How to prove two regular expressions generate the same language
4) LL(1) and SLR(1) grammar
5) Draw Stack created before and after enter the sub routine, (static and dynamic chains)
6) Why no shift-shift conflict in DFA
7) scoping , value passing and reference passing (write the value from a given complicated program)
8) Explain (or propose something intelligent) about compiler Optimization
a) value numbering
b) global data flow analysis
c) register allocation

Qualification Exam Theory Part

Posted on by
Reply

(Fall 2008 Topics)

1) Structural Induction, Induction

2) Logically Valid of [;\forall;] and [;\exists;] in [; \exists z R(x,z) and \forall y R(x,f(x,y);]

3) [; L \cap K;] , [;L \cup K;] [; L -K ;]: context free closure

4) {a^nb^{f(n)} | n \in N;] is not regular
and a^nb^{kn}| n,k \in N;] is context free

5) The function f(n) :the number of perfect square numbers that < n,
f(n) is Primitive Recursive

6) The set of {m |p+q, when [;p \in P;] and [; q \in Q;] and P and Q are recursive enumerable sets } is a recursive enumerable set.