The next five questions refer to the following grammar:
E ::= E ``*'' F | F
F ::= F ``+'' G | G
G ::= ``--'' H | H
H ::= N | Id | ``('' E ``)''
This grammar:
- (A) is ambiguous
- (B) is unambiguous
- (C) does not define a language
- (D) recognizes only ambiguous strings
- (E) has more than one parse tree for some string
The operator precedences enforced by this grammar are:
- (A) None
- (B) ``+'' lower than ``*''; and
``*'' lower than ``-''
- (C) ``*'' higher than ``+''; and
``-'' higher than ``*''
- (D) ``*'' lower than ``+''; and
``+'' lower than ``-''
- (E) arbitrary
The operators ``*'' and ``+'' are:
- (A) both left associative
- (B) both right associative
- (C) neither left nor right associative
- (D) both left and right associative
- (E) unknown associativity
Which of the following strings cannot be generated by
this grammar:
- (A) ``3+4*5''
- (B) ``- 5''
- (C) ``((--(2+2)))''
- (D) ``-(-5 + 6)''
- (E) ``(2 + - 5)''
If we change the second line of the grammar to be
F & ::= & F ``+'' G | F ``--'' G | G
then
- (A) The new grammar is ambiguous
- (B) The new grammar is unambiguous
- (C) The binary operator ``--'' has lower precedence than ``+''
- (D) The binary operator ``--'' has higher precedence than ``+''
- (E) The new grammar recognizes exactly the same strings
as the original grammar
Which of the following is an inductive definition of natural numbers:
- (A) 0,1,2,3,...
- (B) all integers greater than or equal to 0
- (C) 0 is a natural number; if n is a natural number then n+1 is
a natural number, for all n> 0
- (D) n is a natural number, for all n> 0
- (E) {n | n> 0}
Consider two definitions of factorial:
fun fact 0 = 1 local
|fact n = n * fact(n-1); fun tfact(0,k) = k
|tfact(n,k) = tfact(n-1,n*k)
in
fun fastfact n = tfact(n,1)
end;
We can prove fact(n) = fastfact(n) by applying mathematical
induction (over n) to what property:
- (A) fact(n) = tfact(n,1)
- (B) k*fact(n) = tfact(n,k)
- (C) fact(n) = fastfact(n)
- (D) fact(n) = tfact(n,k)
- (E) fact(n*k) = tfact(n,k)
Consider the following Standard ML function:
fun petruchio(nil,nil) = true
|petruchio(x::xs,y::ys) = petruchio(xs,ys)
|petruchio(xs,ys) = false
What does this function do:
- (A) test whether two lists are identical
- (B) test whether two lists are of the same type
- (C) test whether two lists are the same length
- (D) test whether two lists contain the same elements
- (E) test whether it is given two lists as arguments
The language Standard ML is higher order because
- (A) it is an upper-class language
- (B) it does not contain assignment
- (C) it is purely functional
- (D) it has a well-defined semantics
- (E) functions can be passed as values and returned as results
For the next five items, specify the value of the given expression,
assuming the following definitions
fun s n = n+1;
fun compose(f,g) = fn x => f(g(x));
fun twice(f,y) = f(f(y));
fun ctwice f y = f(f(y));
fun sum(g,0) = g(0)
|sum(g,n) = g(n) + sum(g,n-1);
(fn f => (fn x=>f(f(f x)))) s 1
- (A) 1
- (B) 2
- (C) 3
- (D) 4
- (E) 5
twice(compose(s,s),0)
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
sum(fn x=>x*x-2,3)
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
compose(fn x=>x+1,fn y=>y-1)(4)
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
twice(ctwice,s) 2
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
For the next five items, specify the most general type of the given
function definition.
fun f (x,y) = if x>0 then x+y else x-y
- (A) int
- (B) int -> int -> int
- (C) (int * 'a ) -> int
- (D) (int * int) -> int
- (E) int ->int
fun s(x,y) = (y,x)
- (A) ('a * 'b)
- (B) 'a -> 'a
- (C) ('a * 'a) -> ('a * 'a)
- (D) (int * int) -> (int * int)
- (E) ('a * 'b) -> ('b * 'a)
fun g (0,h,y) = y
|g (n,h,y) = h(g(n-1,h,y)) + 1.0
- (A) int
- (B) (int * (real-> real) * real) -> real
- (C) (int * (real-> int )* real) -> real
- (D) (int * (int -> real)* real) -> real
- (E) (int * int * real) -> real
fun nfold(f,0,x) = x
|nfold(f,n,x) = f(nfold(f,n-1,x))
- (A) int
- (B) ('a * int * 'a) -> 'a
- (C) ((int -> int ) * int * int ) -> int
- (D) (('a -> 'b) * int * 'a) -> 'b
- (E) (('a -> 'a) * int * 'a) -> 'a
fun qz x = (fn y => x+y)
- (A) int
- (B) (int -> int ) -> int
- (C) int * int -> int
- (D) int -> int
- (E) int -> int -> int
The Penn State women's volleyball team
- (A) was national champions last year
- (B) is fun to watch
- (C) has the longest home winning streak
- (D) plays in Rec Hall
- (E) all of the above