Homework 02

Problem 1

Find nullable, FIRST, and FOLLOW sets for this grammar; then construct the LL(1) parsing table.
1.S′ → S EOF
2.S →
3.S → XS
4.B → \ begin { WORD }
5.E → \ end { WORD }
6.X → BSE
7.X → { S }
8.X → WORD
9.X → begin
10.X → end
11.X → \ WORD

Problem 2

1) Give an example grammar with its corresponding parsing table where left recursion causes ambiguity. How do you get rid of it in this case: A → Aa|b?

2) The following grammar is for regular expressions over symbols a and b only, using + instead of | (to avoid notation conflict)
rexpr → rexpr + rterm | rterm
rterm → rterm rfactor| rfactor
rfactor → rfactor * | rprimary
rprimary → a | b

a)Left-factor this grammar
b)Is the resulting grammar suitable for top-down parsing ?
c)Eliminate the left recursion from the original grammar
d)Is the resulting grammar suitable for top-down parsing ?

Problem 3

Write an unambiguous grammar for the following language:
Balanced parentheses and brackets, where a closing bracket also closes any outstanding open parentheses (up to the previous open bracket).
Example: [([](()[(][])]

Possible solution:
A → [B]A|(A)A|““
B → [B]B|(B)B|B'
B' → (B'|”“

It seems to recognize the right language and to be unambiguous. Do you agree?