*** Solution to CSCI 410 F97 Final Exam ***	  [Bono]

Problem 1 [9]

A[1].  lexical analyzer


B[1]. DFA or FSA


C[3]. parser; grammar


D[4]. rightmost in reverse




Problem 2 [6]

def: an ambiguous grammar is one for which there is a string in the
language for which there exist two different parse trees.
alt def: one for which a string has two different leftmost derivations
(two diff derivations is not sufficient)

ex:  E --> E + E
     E --> id




Problem 3 [13]

A[10]:

S  -> XS'
S' -> abS'
    | aSS'
    | eps

X  -> aX'
    | bX'
X' -> cX'
    | eps

B[3]: top down
alt answers: recursive descent, LL(1), predictive parsing

Problem 4 [8]

a.  2   (lex/value)
b.  10  (lex/ref)
c.  -2  (dyn/value)
d.  0   (dyn/ref)


Problem 5 [X points]

       action	      goto
     a   b   c   $    S   X
  -------------------------
0|  s4  s5  s3     || 1   2
1|             acc ||
2|  s4  s5  s3     || 6   2
3|  r2  r2      r2 ||
4|  r3  r3  r3  r3 ||
5|  r4  r4  r4  r4 ||
6|  s4  s5         ||     7
7|  r1  r1      r1 ||



Problem 6 [12]

Part 1

A:  0  Ag	B:  0  Ag	D:  0  Dg
    4  Ah           4  Ah           4  Ah
                    8  Bj           8  Dk
(ok if they don't say 0, 4, etc.)

Part 2

(ok if they leave out the object ID pointer, and object size)

A:  dispatchPtr	    B:  dispatchPtr	D: dispatchPtr
    a		        a		   a 
    		        b		   c



Problem 7 [6]

O(Id) = T0
O, M |- e1 : T1
T1 <= T0
---------------------
O, M |- Id <- e1 : T1

(if they give T0 instead of T1 in last line, just take off one point)




Problem 8 [5]
                   _______________________________
                   |                             |
                   |                             v
  --> [1,2] --> [3-8] --> [9,10] --> [11,12] --> [13,14] -->
                 ^             |
                 |_____________|



Problem 9 [10]


Part A.









Part B.

t2 = 7 * d
t1 = b + c
t3 = t1 * t2
d = t3 + t3

(may use different temp names)



Problem 10 [17]

Part A [5]

note: switch, default, case, and intconst are terminals
(they may call intconst something different).  so is some punctuation.

E --> switch E { Cases default : E }

Cases --> OneCase                (right-recursive or left-recursive version ok)
          | OneCase Cases

OneCase --> case intconst  : E ;


Part B [10]

cgen(switch ...) =

  endstuff = newLabel();
  cgen(expr0);
  cout << "push $a0" << endl;     // save e0 on the stack
  for (i = 1; i <= n; i++) {
    next = newLabel();            // if top != valuei goto next test
    cout << "if ( 4($sp) != " << valuei << "goto " << next << endl;
    cgen(expri);                  // generate code for this expr
    cout << "goto " << endstuff << endl;      // jmp to end of case
    cout << next << ":";               // emit label for next test
  }
  cgen (exprn+1) ;   // fell through all tests: do default caase
  cout << endstuff << ":" << endl;

  cout << "$a0 := 4($sp)" << endl;  // put value of whole case in $a0
  pop;                  // restore stack to what it was before doing case