Sample Problems for CMSC331 Midterm One -- Spring 2024

1)
assign -> id = expr
id -> A | B | C | D
expr -> expr + term | expr - term |term
term -> term * factor | term / factor |factor
factor -> ( expr ) | id

show the parse tree for the following:

D = B * B / (4 * A * C) + B

C = (C/A) * (A/B) * B

2) Remember the function "map: ('a -> 'b) -> 'a list -> 'b list" which applies a given function to each member of a list, and creates a new list from the results? Write a simple implementation of that function.

3) What is the type of this functions:

fun curry f x y = f (x, y);

4) Write a regular expression which recognizes digital clock times (hours, minutes and seconds).


5) Given the following signature:

signature CTree = sig
   type ctree
   val empty: ctree
   val insert: int -> ctree -> ctree
   val howmany: ctree -> int
   end;

{where insert 5 (insert 5 (insert 5 empty)) = 3
  and  insert 4 (insert 3 empty) = 2}

Write a structure which implements the signature.


6) Find the lexemes in the following string:
"case a when 5 then a+15 when 6 then a-25 else a*35 end;"


7) Convert the following EBNF grammar into BNF:

expr = identifier [unaryop]
unaryop = ++ | -- 

8) Write an ML function which determines if all of the chars in a string are in alphabetical order.

9) What are the types of these expressions:

fun zwap z = (z true) + (z false);

fun blurb f g h k = f(g k, h k);

fun bubble [] = 5::[] |
    bubble (a::l) = bubble(3::a::l);