Question 1

Given the following grammar:

S ® C

C ® case id of B end

C ® id:=id

B ® B;B

B ® id:C

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 (:= is a single token and id consists of a sequence of one or more alphabetic characters).

Solution Question 2

Given the following grammar for arithmetic expressions in reverse Polish notation:

S ® E

E ® E E Op

E ® num

Op ® +

Op ® -

Op ® *

Op ® /

Write a program that takes any valid input for this language and writes out the integer resulting from the evaluation of the input expression (num consists a sequence of one or more decimal digits).

Solution Question 3

Given the following grammar for string expressions:

S ® E

E ® E + T

E ® T

T ® - T

T ® string

T ® (E)

+ represents string concatenation. For example: abc + def = abcdef

- removes the first letter from a string. For example: - - Geoff = off

string consists of a sequence of one or more alphabetic characters

Write a program that takes any valid input for this language and writes out the string resulting from the evaluation of the input expression

Solution