Answer Key for CSE-304 Final Exam of Fall '98

1.
  a. (f)lex. If the document is well formed, each of the constructs in
     HTML has only one equivalent construct in LaTex, since in HTML one
     command ends before the next one begins - i.e., there is no nesting
     of commands.
  b. No. (f)lex and yacc (or bison). If the document is not well formed,
     then it is possible that a command doesn't end and another command
     starts. Only with the help of parser can we detect this.

2. Yes.
%%
^.*competetion.*\n   {}
^.*\n                {printf ("%s", yytext) ; }
%%

3. 
  a. 4 6 * - 7 +
  b. Yes. See the procedure to translate an infix expression to postfix
     expression on page 33.
  c. E -> E  E  * | E  E  + | E  - | NUM

4.
  Let Sigma be the set of Terminal symbols and Pi be the set of non-terminals.
  a. O(|Sigma| * |Pi|), where |Sigma| and |Pi| are sizes of Sigma and Pi, resp.
        For each of the rules (of size |Pi|), there are entries for each of
        the terminals (|Sigma|)
  b. O(n)
        It is a tree of n leaves. Apart from the nodes whose children
        are leaves, all other nodes are *binary*. So we have
        3n-1 nodes (n leaves, n immediate parents of leaves, n-1 internal
        binary nodes) in the parse tree
  c. O((|Sigma| + |Pi|) * (|Sigma| + 2 * |Pi|))
        For each of the states (|Sigma| + 2 * |Pi|), there are |Sigma| 'action's
        and |Pi| 'goto's.
  d. O(n)
        Each step grows the tree by at least one node.
  e. O(n)
        Each symbol is shifted once. Some reduce actions are taken, so the
        actual time taken is a constant times more, but the order doesn't
        change.

6.
  a.
     E: synthesized
     T: synthesized
     F: synthesized

  b.
     E -> E1 + T
            { E.dx = E1.dx + T.dx ; }
     E -> T
            { E.dx = T.dx ; }
     T -> T1 * F
            { T.dx = T1.val * F.dx + F.val * T1.dx ; }
     T -> F
            { T.dx = F.dx ; }
     F -> ( E )
            { F.dx = E.dx ; }
     F -> INT
            { F.dx = 0 ; }
     F -> x
            { F.dx = 1 ; }

  c. Yes. Because dx is synthesized and a shift-reduce parser builds
	the parse tree bottom-up.

7.
  1. int
  2. float
  3. float
  4. float
  5. int
  6. float
  7. float
  8. float
  9. int
  10. float

8.
  Attributes 'begin' and 'end' store labels (returned by call to new_label).
  a. S -> for ( E1 ; E2 ; E3 ) S1
           { E2.begin = new_label () ;
             S.end = new_label () ;
             E1.code ||
             emit (E2.begin :) ||
             E2.code ||
             emit (E2.val 0) ||
             emit (jz S.end) ||
             emit (S1.code) ||
             emit (E3.code) ||
             emit (jmp E2.begin) ||
             emit (S.end :) ; }
   b. Attribute 'parent' points to the non-terminal from which S is derived.
      Thus, S.parent.end gives the label of end of the statement of S.parent.
      'parent' is in inherited attribute.
      S -> continue
           { emit (jmp S.parent.begin) ; }
   c. S -> continue ( E )
           { emit (E.code) ||
             emit (E.val 0) ||
             emit (jz S.parent.begin) ; }