Computing FIRST and FOLLOW sets

Suppose we have the following grammar:

S -> A ( S ) B | ε
A -> S | S B | x | ε
B -> S B | y

where S is the start symbol, S, A, B are non-terminal symbols, x, y, (, ) are terminal symbols, and ε is the empty string.

I'm trying to compute the FIRST() and FOLLOW() sets of S, A, and B.

FIRST(S) = FIRST(A ( S ) B) ∪ {ε}
FIRST(A) = FIRST(S) ∪ FIRST(SB) ∪ {x} ∪ {ε}
FIRST(B) = FIRST(S B) ∪ {y}

How can I compute FIRST(S), since I don't know what the FIRST(A) is? How should I attack the problem? Any ideas?

• Do you know fix points ? – François Jun 27 '15 at 19:29
• @FrançoisGodi No, they really mean A ( S ) B. The parentheses here are alphabet symbols. – Yuval Filmus Jun 27 '15 at 19:30
• Stavros, you can look at site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/… the second example. – François Jun 27 '15 at 19:37

If you just keep applying FIRST, it not hard to understand where to stop.

FIRST($\mathtt{S}$) = FIRST($\mathtt {A(S)B}$) ∪ {ε}

In your example, FIRST($\mathtt{A}$) includes ε, so

FIRST($\mathtt{S}$) = FIRST($\mathtt {A}$)\{ε} ∪ FIRST($\mathtt {(S)B}$) ∪ {ε} = FIRST($\mathtt {A}$)\{ε} ∪ {$\mathtt{(}$} ∪ {ε}

Now, as FIRST($\mathtt{A}$)\{ε} = FIRST($\mathtt{S}$)\{ε} ∪ FIRST($\mathtt{SB}$)\{ε} ∪ {$\mathtt{x}$}, then

FIRST($\mathtt{S}$) = FIRST($\mathtt{S}$)\{ε} $\cup$ FIRST($\mathtt{SB}$)\{ε} ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

Notice that the appearances of $\mathtt{S}$ on the left side are redundant here, so we get (again, because FIRST($\mathtt{S}$) includes ε):

FIRST($\mathtt{S}$) = FIRST($\mathtt{B}$)\FIRST($\mathtt{S}$) ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

The end result is FIRST($\mathtt{S}$) = {$\mathtt{y}$, $\mathtt{x}$, $\mathtt{(}$, ε}