Wiki**3

Computing the FIRST Set

The FIRST set for a given string or symbol can be computed as follows:

1. If a is a terminal symbol, then FIRST(a) = {a}
2. If X is a non-terminal symbol and X -> ε is a production then add ε to FIRST(X)
3. If X is a non-terminal symbol and X -> Y₁...Y_n is a production, then

   a ∈ FIRST(X) if a ∈ FIRST(Y_i) and ε ∈ FIRST(Y_j), i<j (i.e., Y_j ε)

As an example, consider production X -> Y₁...Y_n

• If Y₁ ε then FIRST(X) = FIRST(Y₁)
• If Y₁ ε and Y₂ ε then FIRST(X) = FIRST(Y₁) \ {ε} ∪ FIRST(Y₂)
• If Y_i ε (∀i) then FIRST(X) = ∪_i(FIRST(Y_i)\{ε}) ∪ {ε}