FIRST FOLLOW Predictive Tables

Build predictive parsing tables and see how nullable rules and common prefixes affect determinism.

FIRST FOLLOW Predictive Tables Theory

An LL(1) predictive parser operates by looking ahead at the next token in the input stream and choosing exactly one production rule without backtracking. This is only possible for grammars where the choices are disjoint for any given nonterminal. We calculate FIRST and FOLLOW sets, and identify Nullable nonterminals to build this parsing table.

Worked Example: Nullable and Sets

Consider a simple non-recursive grammar: S -> A B, A -> a | epsilon, B -> b. We want to find FIRST(S), FOLLOW(A), and whether A is Nullable.

Nullable: Since A -> epsilon is a production, A is Nullable. B is not Nullable, so S is not Nullable.
FIRST sets: FIRST(B) = {b}. FIRST(A) = {a, epsilon}. For S, since A is Nullable, FIRST(S) = (FIRST(A) - {epsilon}) U FIRST(B) = {a, b}.
FOLLOW sets: S is the start symbol, so FOLLOW(S) = {$}. Since S -> A B, everything in FIRST(B) goes into FOLLOW(A). Thus FOLLOW(A) = {b}.
LL(1) Table Construction:
```
For A -> a: add to Table[A, a]\n For A -> epsilon: since A is Nullable, add to Table[A, f] for f in FOLLOW(A), which is Table[A, b]\n
```
The expected result is a conflict-free table where Table[A, a] contains A -> a and Table[A, b] contains A -> epsilon.

Experiment with Real Grammars

Use the controls in the FIRST FOLLOW Predictive Tables interactive module to explore how FIRST and FOLLOW sets resolve parsing decisions.

Select Grammar as "Conflict" and observe the Conflicting table cells metric. Notice it is 1, indicating the grammar is not LL(1).
Change Grammar to "Balanced" and set Tokens to "( ( ) )". Check Predictive parser accepts; it should say "Yes" because the grammar is conflict-free and the string belongs to the language.
Set Grammar to "Expression" and Nonterminal to "Q". Observe the FIRST set and FOLLOW set values updated automatically based on fixed-point iteration.

Limitations of LL(1) Parsing

LL(1) parsers cannot handle left-recursive grammars directly; left recursion must be eliminated beforehand. Additionally, they cannot parse all unambiguous grammars. For instance, common prefixes (like the dangling-else problem) cause conflicts that require left-factoring or more powerful parsing techniques like LR(1) or Earley parsing. The table construction shown assumes only one token of lookahead, limiting its expressive power.

Primary References

The formal definition and computation of FIRST and FOLLOW sets are foundational in compiler design. For an in-depth lecture on these concepts and predictive table construction, see theColumbia University Fall 2009 CS4115 Lecture Notes by Alfred V. Aho.

FIRST FOLLOW Predictive Tables