Sample Problems -- CMSC 331 -- Spring 17

Stuff to Study and/or Think About

	
1.  What are the types of the following:

	a) fun stuff f base [] = base:(int->int) |
               stuff f base a::b = f(a,(stuff f base b));

        b) fun inc x = inc (x+1);

	c) fun in1 0 = 0 |
               in1 x = in1(x+1);

	d) fun temp x = x + (x 0);

	e) fun temp2 x = (x 0) + (x 1);

	f) fun squash [] = [] |
	     squash ({a,b}::c) = ((a+b):int)::(squash c);

	g) fun arbsquash f [] = [] |
               arbsquash f ({a,b}::c) = ((f a b)::(arbsquash f c));


2. Define referential transparency.

3. Write an ML function to find the smallest item in a list.

4. Write an ML function to subtract pairs of ints.
   e.g. {7,5} - {2,4} = {5,1}

5. Write an ML function to add up all of the ints in an int list.

6. Find the tokens in the following string "if (a=b) then x=7 else y=y-1;"

7. Write a grammar  which generates all the sentences where it starts with n copies of "a", followed by exactly n copies of "b".  (n>0)

8.  assign -> id = expr
    id -> A | B | C
    expr -> expr + term | term
    term -> term * factor | factor
    factor -> ( expr ) | id

show parse tree & left-most derivation for:

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

9) program -> BEGIN stmt_list END
   stmt_list -> stmt | stmt ; stml_list
   stmt  -> var = expr
   var  -> A | B | C
   expr -> var + var | var - var | var

Convert this BNF grammar to EBNF.