0
$\begingroup$

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?

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

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{(}$, ε}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy