Practice questions for midterm 1
================================

Questions 1-3 use this definition of type exp:

   type exp = Plus of exp*exp | Times of exp*exp | Minus of exp*exp
            | Negate of exp | Var of string | Int of int

1. Write removeMinus: exp -> exp which replaces every occurrence
   of an expression of the form Minus(e,e') by Plus(e, Negate(e')).
   For example:

    removeMinus (Minus (Minus(Int 3, Var "x"), Times(Int 3, Var "a")))
      = Plus (Plus(Int 3, Negate (Var "x")),
              Negate (Times(Int 3, Var "a")))

2. Write simplify: exp -> exp which simplifies occurrences of
   multiplication by zero to zero, multiplication by one to its
   other argument, and additions or subtractions of zero:
   For example:

     simplify (Mult(Int 1, Plus(Var "x", Int 0))) = Var "x"


3. Write pp: exp -> string which ``pretty-prints'' its argument,
i.e. renders it in concrete syntax.  For example:

   pp (Mult(Var "x", Plus(Int 3, Var "y"))) = "(x*(3+y))"

4. Write an ocamllex specification that extracts the
next integer (sequence of digits) from an input stream and returns it
as an integer value; if there are not digits in the input,
it should return -1.

5. For this grammar:

   E -> E+T | T
   T -> T*P | P
   P -> id | ( E )

(a) Give an example of an E-sentence, and an E-form that is not a sentence;
    similarly for T and P.

(b) Give a parse tree for "a*(b*c)".

(c) Give a numbering of that tree in a post-order traversal.  Then
    show the shift-reduce parse for the tree.


For the next two questions, suppose we use this type to represent
the *concrete* syntax given above:

    type token = PlusT | TimesT | Id of string | LParen | RParen

    type etree = E_prod1 of etree * token * ttree | E_prod2 of ttree
     and ttree = T_prod1 of ttree * token * ptree | T_prod2 of ptree
     and ptree = P_prod1 of token | P_prod2 of token * etree * token

For example, the parse tree for "x+y" would be represented
by this value of type etree:

       E_prod1(E_prod2(T_prod2(P_prod1 (Id "x"))),
               PlusT,
               T_prod2(P_prod1 (Id "y")))

(d)  Define legaltree: etree -> bool, to check if it is legal in the
     sense that the token in eprod1 is PlusT, the token in tprod1 is
     TimesT, etc.  You will need to define auxiliary functions
     legaltreeT and legaltreeP.

(e)  Define frontier: etree -> token list.  Again, you will need auxiliary
     functions for values of type ttree and ptree.

(f)  Define absE: etree -> exp, where exp is the type defined above:

        type exp = Plus of exp*exp | Times of exp*exp | Minus of exp*exp
                 | Negate of exp | Var of string | Int of int
 
     For example, if e is the value of type etree shown above
     (representing the parse tree of "x+y"), then absE e =
     Plus(Var "x", Var "y").  You will need to define auxiliary
     functions absT and absP.

6. For each of the following grammars, calculate FIRST and
   FOLLOW sets (showing the tables calculated at each iteration),
   and say whether the grammar is LL(1).

   (a)  S -> aSe  |  B
        B -> bBe  |  C
        C -> cCe  |  d

   (b)  S -> I  |  b
        I -> aESF
        F -> eS  |  epsilon
        E -> t  |  f

   (c) A -> BCe  |  gDB
       B -> bCDE  |  epsilon
       C -> DaB  |  ca
       D -> dD  |  epsilon
       E -> gAf  |  c