HW1 -- Due 4/21/98 in class.

1) Evaluate your favorite language based on the criteria given in
class.


2) Grammar :

    <assign> -> <id> := <expr>
    <id>     -> A | B | C
    <expr>   -> <id> + <expr>
              | <id> * <expr>
              | (<expr>)
              | <id>

Given the above grammar, show a parse tree and leftmost derivation for
each of the following statements:

a) A := A * (B + (C * A))
b) B := C * (A * C + B)
c) A := A * (B + (C))


3) Give an unambiguous grammar that generates the same language as:
     
        S -> SS | (S) | ()

4) Give regular expressions for:

a) Binary strings ending in 01
b) Decimal integers divisible by 5
c) C identifiers
d) Binary strings consisting of either an odd number of 1's or an odd
number of 0's

5) Given the following virtual machine

      ident := var
      ident := ident + 1
      ident := ident - 1
      goto label
      if var relop var goto label

      where relop = { = , <>, >, <, >=, <= },

give the operational semantic definition of the following:

a) Pascal repeat
b) Pascal for-downto
c) FORTRAN DO of the form: DO LABEL K = start, end, step
d) Pascal if-then-else
e) C for
d) C switch

6) Compute the weakest precondition for each of the following
assignment statements and postconditions

a) a := 2 * (b -1) - 1 {a > 0}
b) b := (c + 10) / 3 {b > 6}
c) a := a + 2 * b - 1 {a > 1}
d) x := 2 * y + x - 1 {x > 11}