Question 1

Given the following grammar:

S ® E

E ® E[I]

E ® id

I ® id,I

I ® 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 (id consists of a sequence of one or more alphabetic characters).

Solution

Question 2

Given the following grammar for a fragment of propositional logic:

S ® E

E ® T and E

E ® T

T ® T => F

T ® F

F ® true

F ® false

F ® (E)

Write a program that takes any valid input for this language and writes out the boolean resulting from the reduction of this input. (=> is a single token which represents logical implication - e1 => e2 is true unless e1 is true and e2 is false).

Solution

Question 3

Given the following grammar for a fragment of Pascal:

S ® Stat

Stat ® case Exp of Caselist end

Stat ® id:=Exp

Caselist ® Caselist;Case

Caselist ® Case

Case ® id:Stat

Exp ® id

Write a program that translates this into the equivalent in C, where the equivalent is as follows:

Pascal	C
Stat ® case Exp of Caselist end	Stat ® switch (Exp) {Caselist}
Stat ® id:=Exp	Stat ® id=Exp;
Caselist ® Caselist ; Case	Caselist ® Caselist Case
Case ® id:Stat	Case ® case id:Stat break;

(id consists of a sequence of one or more alphabetic characters)

Solution