Calculate Nullable First and Follow for This Grammar

What are Nullable, First, and Follow?

In formal language theory, these three concepts are essential for parsing and analyzing context-free grammars:

Nullable Set

A non-terminal is nullable if it can derive the empty string (ε). The nullable set contains all non-terminals that can produce ε directly or indirectly through other nullable non-terminals.

First Set

The first set of a string or non-terminal contains all terminals that can appear as the first symbol in any string derived from that string or non-terminal. For a non-terminal, it includes the first symbols of all productions starting with that non-terminal.

Follow Set

The follow set of a non-terminal contains all terminals that can appear immediately after the non-terminal in any sentential form derived from the start symbol. It helps determine where a non-terminal can be followed by specific terminals.

How to Calculate Nullable, First, and Follow

Calculating Nullable Set

1. Identify all non-terminals in the grammar.
2. For each non-terminal A, check if there's a production A → ε. If yes, A is nullable.
3. For productions like A → BC, A is nullable if both B and C are nullable.
4. Repeat the process until no more non-terminals can be added to the nullable set.

Calculating First Set

1. For each terminal a, First(a) = {a}.
2. For a non-terminal A, First(A) includes:
   • All terminals that directly follow A in productions.
   • First(B) for any non-terminal B that follows A in productions.
3. If a production starts with a nullable non-terminal, include First of the next symbol.
4. Repeat until no more terminals can be added to any First set.

Calculating Follow Set

1. Follow(S) = {$} where S is the start symbol and $ is the end marker.
2. For a production A → αBβ:
   • Add First(β) to Follow(B), excluding ε.
   • If β can derive ε, add Follow(A) to Follow(B).
3. Repeat until no more terminals can be added to any Follow set.

Example Calculation

Consider the following grammar:

Nullable Set Calculation

• A → ε → A is nullable
• B → ε → B is nullable
• S → aB or bA → S is not nullable (no ε production)

First Set Calculation

• First(S) = {a, b}
• First(A) = {a, ε}
• First(B) = {b, ε}

Follow Set Calculation

• Follow(S) = {$}
• Follow(A) = {b} (from S → bA)
• Follow(B) = {a} (from S → aB)