Question 1

Given the following grammar:

S ® D

D ® D;D

D ® I: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 arithmetic expressions:

S ® E

E ® E+T

E ® T

T ® T*F

T ® F

F ® num

F ® (E)

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 a fragment of Pascal:

S ® Stat

Stat ® begin Statlist end

Stat ® while Expr do Stat

Stat ® id:=Expr

Statlist ® Statlist;Stat

Statlist ® Stat

Expr ® id

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

Pascal	C
Stat ® begin Statlist end	Stat ® { Statlist }
Stat ® while Expr do Stat	Stat ® while (Expr) Stat
Stat ® id:=Expr	Stat ® id=Expr;
Statlist ® Statlist ; Stat	Stat ® Statlist Stat

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

Solution