Question 1
Given the following grammar:
S -> E
E -> E , E
E -> if E then E else E fi
E -> while E do E od
E -> id := num
E -> id
Write a parser for this language, i.e. a program that will take any
input and answer yes if it corresponds to this grammar, and
no otherwise.
Solution
Question 2
Giving the following grammar for lists:
S -> L
L -> empty
L -> ( cons N L )
L -> ( reverse L )
N -> "any sequence of digits"
Where empty is the empty list, (cons n l) adds the number n to
the head of the list l, and (reverse l) reverses the list l,
write an evaluator that will print out all the elements of one of
these lists (in the order that they appear).
For example, given the following input:
(cons 8 (reverse (cons 7 (cons 6 empty))))
The result would be: 8, 6, 7
Solution
Question 3
Given the following grammar for statements:
Stat -> Stat ; Stat
Stat -> Name = Expr
Expr -> ( fn Var => Expr)
Expr -> Var
Var -> "any (single) lower-case letter"
Name -> "any sequence of upper-case letters"
Write a program that takes an input corresponding to this grammar and
prints it out, but with all whitespace removed and each instance of Var
replaced by a number,
where "a" is replaced by 0, "b" by 1,..., "z" by 25.
For example, given the input
ID = (fn c => c); FIRST = (fn x => (fn y => x))
your program should print:
ID=(fn2=>2);FIRST=(fn23=>(fn24=>23))
Solution