Question 1

Given the following grammar:

S ® D:=E

D ® D.id

D ® id

E ® D+E

E ® D

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:

S ® E

E ® E & T

E ® T

T ® F | T

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. ("&" represents bitwise AND, "|" represents bitwise OR, and num consists of a sequence of one or more decimal digits).

Solution

Question 3

Given the following grammar for a fragment of Pascal:

S ® record Fieldlist end

Fieldlist ® Fieldlist ; Field

Fieldlist ® Field

Field ® Idlist : id

Idlist ® id , Idlist

Idlist ® id

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

Pascal	C
S ® record Fieldlist end	S ® struct {Fieldlist}
Fieldlist ® Fieldlist ; Field	Fieldlist ® Fieldlist Field
Field ® Idlist : id	Field ® id Idlist;

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

Solution