FIRST FOLLOW Predictive Tables
Build predictive parsing tables and see how nullable rules and common prefixes affect determinism.
Free theory articleBuild predictive parsing tables and see how nullable rules and common prefixes affect determinism.
Concept & interpretation
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.
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.