CSCI 410 Fall 2002
Solution for the Final Exam

Problem 1:

A. Leftmost
B. Follow(A)
C. grammar, a parser
D. Finite State Automaton

Problem 2:

A. Context free language

B.

There are many possible answers but this one is the simplest:

B -> begin end
    | begin B end

Problem 3:

A. Semantic analysis

B. Symbol table

C. At declaration site, lookup id in symbol table to see if it is
already defined in an outer scope. If it is already defined, that is
sufficient condition to generate a warning.

D. inherited

E. type environment

Problem 4:

A.

f : 1
g : 0
g : 0

B.

f : 1
g : 1
g : 0

Problem 5:

A. 0 20
B. 3 3
C. 3 0
D. 3 3

Problem 6:

A.
                                       ---- a
                -------- * (t4, t1) ---
+ (t3,x,t6,b) --                       ---- b
                |
                |                       ------- c
                -------- - (t2, t5) ---
                                        ------- d

B. 

t1 = a * b
t2 = c - d
x = t1 + t2
b = x

Problem 7:

A.

1. The id is an attribute. Reg is the self ptr ($s0).
2. The id is a local or parameter. Reg is the frame ptr ($fp)

B.

1. offset in self object.
2. offset in stack frame.

Problem 8:

A. Label of method is known at compile time because there is only one
method per declaration. So, just jump to that fixed label.

B. Objects no longer need a dispatch pointer because it was only used
for dynamic dispatch. There is no need for dispatch tables for the
same reason.

Problem 9:

cgen(e1 max e2) =

cgen(e1);
cout << "push $a0";
cgen(e2);
string end = newlable();
cout << "$t0 = top";
cout << "pop";
cout << "if ($t0<$a0)";
cout << "goto " << end;
cout << $a0 = $t0";
cout << end << ":";