# 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?