CSCI 330: Exam 1 Sample Problems

1. What does the following OCaml function do?

let rec mystery1 (f:int->int) (s:int) (l:int list) =
  match l with
  | [] -> f s
  | h::t -> mystery1 f h t



2. Is the function above tail recursive? Why or why not?



3. What is the value of the following OCaml code:

let x =
  let y = 4 in
  let z = 2 in
  let x = y * y + z in
  y - z




4. Partially apply the following OCaml code and write the "value" of f10:

let f a b =
  if a > b then
    a
  else
    b
;;

let f10 = f 10
;;



5. Compute the weakest precondition for the following sequence of statements:

x = y / 2 + 4
z = 2 * x + 3
y = 2 * x - 3
{ y > 1 }




6. For the following questions, use this BNF grammar:

Assign := Var '=' Expr

Expr := '(' Expr ')'
      | Expr '+' Expr
      | Expr '-' Expr
      | Digit
      | Var

Var := 'A' | 'B'

Digit := '0' | '1' | ... | '8' | '9'


A). What are the terminals and non-terminals in the grammar?

B). Convert the grammar to a minimal EBNF grammar.

C). Perform a left-most derivation of "B=B-(A+A)+1"

D). Show that the grammar is ambiguous by showing two parse trees

E). Given the one rule in the grammar above:   Assign := Var '=' Expr
    What attributes should be introduced to do type checking on assignments?
    Hints: Consider what must be synthesized or inherited vs. what is intrinsic
           You will need to add attribute rules to other rules