Faculty of Engineering / Compilers Theory
Computers and Control Dept / Second term 2006
Problem Set (3)
(1) Consider the grammar
S→ (L)|a
L→L,S|S
(a) Find parse trees for the following sentences:
I. (a,a)
II. (a,(a,a))
III. (a,((a,a),(a,a)))
(b) Construct both the leftmost and the rightmost derivations for each of the sentences in part (a).
(2) Consider the grammar
S→aSbS | bSaS | Î
(a) Show that the grammar is ambiguous by constructing two leftmost derivations for the sentence abab.
(b) Construct the corresponding parse trees for abab.
(3) Consider the following grammar
S → a A B
A → b A | ε
B → c b
(a) Compute the FIRST set and FOLLOW set for each of the nonterminal S, A, and B.
(b) Construct a nonrecursive LL(1) parsing table for this grammar.
(4) Write a grammar that accepts the same language as the grammar below, but that is suitable for LL(1) parsing. That is, eliminate the left recursion, and (if necessary) left-factor.
S → S ; S
S → id = E
S → print ( L )
E → id
E → num
E → E + E
E → ( S , E )
L → E
L → L , E
(5) Consider the following grammar
S → u B D z
B → B v
B → w
D → E F
E → y
E → ε
F → x
F → ε
(a) Calculate FIRST and FOLLOW set for this grammar
(b) Construct the LL(1) parsing table
(c) Give evidence that the grammar is not LL(1)
(d) Modify the grammar to make an LL(1) grammar that accepts the same language.
(6) Consider the Grammar:
P→ S
S→ A | A ;
A→ id = E
E→ E+E | E-E | E*E | E/E | (E) | T
T→ id | const
(a) Transform the grammar (if needed) so that it is LL(1). Note that we assume all operations associate to the left and they have the usual precedence relation.
(b) Construct tables for the FIRST, FOLLOW
(c) Construct the Parsing Table
(d) Add error recovery entries to the Parsing Table
(e) Use the Parsing Table to parse the input id*(id+id-id)
(f) Use the Parsing Table to parse the erroneous input id*/(id+id-id