{ }FIRST & FOLLOW
Compiler Design · Syntax Analysis

Compute FIRST and FOLLOW sets of any context-free grammar

Type your productions, and the calculator iterates until no set changes, then shows every pass, the final sets and the LL(1) predictive parsing table.

A–Z non-terminals a, +, (, … terminals # epsilon (ε) $ end marker | alternatives

Grammar

first line = start symbol

Examples

One production per line: S=AB, E->TR or R=+TR|#.

Concepts

FIRST(X)

The set of terminals that can begin strings derived from X. If X can derive the empty string, # is included.

  1. For A → aα, add a to FIRST(A).
  2. For A → Bα, add FIRST(B) except #; continue with α if B can derive #.
  3. If every symbol of the right side can derive #, add # to FIRST(A).

FOLLOW(A)

The set of terminals that can appear immediately to the right of A in a sentential form.

  1. Add $ to FOLLOW of the start symbol.
  2. For A → αBβ, add FIRST(β) except # to FOLLOW(B).
  3. If β can derive # or is absent, add FOLLOW(A) to FOLLOW(B).