FIRST and FOLLOW Calculator (LL(1) Parsing Table)
Compute nullable, FIRST and FOLLOW sets and the LL(1) parsing table of a grammar, find conflicts and left recursion, and trace a predictive parse.
Start symbol: E (the left side of the first rule). $ marks the end of the input.
| Nonterminal | Nullable | FIRST | FOLLOW |
|---|---|---|---|
| E | no | { (, id } | { ), $ } |
| E' | yes | { +, ε } | { ), $ } |
| T | no | { (, id } | { +, ), $ } |
| T' | yes | { *, ε } | { +, ), $ } |
| F | no | { (, id } | { +, *, ), $ } |
| + | * | ( | ) | id | $ | |
|---|---|---|---|---|---|---|
| E | E → T E' | E → T E' | ||||
| E' | E' → + T E' | E' → ε | E' → ε | |||
| T | T → F T' | T → F T' | ||||
| T' | T' → ε | T' → * F T' | T' → ε | T' → ε | ||
| F | F → ( E ) | F → id |
| Stack | Input | Action |
|---|---|---|
| E $ | id + id * id $ | E → T E' |
| T E' $ | id + id * id $ | T → F T' |
| F T' E' $ | id + id * id $ | F → id |
| id T' E' $ | id + id * id $ | match id |
| T' E' $ | + id * id $ | T' → ε |
| E' $ | + id * id $ | E' → + T E' |
| + T E' $ | + id * id $ | match + |
| T E' $ | id * id $ | T → F T' |
| F T' E' $ | id * id $ | F → id |
| id T' E' $ | id * id $ | match id |
| T' E' $ | * id $ | T' → * F T' |
| * F T' E' $ | * id $ | match * |
| F T' E' $ | id $ | F → id |
| id T' E' $ | id $ | match id |
| T' E' $ | $ | T' → ε |
| E' $ | $ | E' → ε |
| $ | $ | accept |
Building a top-down (LL(1)) parser starts with three things for every nonterminal: whether it can derive the empty string, its FIRST set and its FOLLOW set. From those comes the predictive parsing table, and any cell with two rules is a conflict that makes the grammar unsuitable for LL(1). This calculator works all of that out, lists conflicts, removes left recursion and traces a predictive parse of your input.
How to use this tool
- Type the grammar, one rule per line, like E -> T E' with alternatives separated by |.
- Use ε (or eps) for the empty string; the first rule's left side is the start symbol.
- Optionally enter an input string to parse.
- Read the sets, the LL(1) table, the conflicts and the parse trace.
Formula
FIRST(αβ) = FIRST(α) ∪ (FIRST(β) if α ⇒* ε) · A → αBβ: FIRST(β) − {ε} ⊆ FOLLOW(B), and FOLLOW(A) ⊆ FOLLOW(B) if β ⇒* ε
The sets are computed by repeating these rules until nothing changes, and $ is put in FOLLOW of the start symbol. Rule A → α goes into table cell M[A, a] for every terminal a in FIRST(α), and, when α can be empty, for every symbol in FOLLOW(A). Left recursion is found through nullable prefixes too (indirect recursion), and removed with the standard algorithm from Aho, Lam, Sethi and Ullman, adding primed nonterminals.
Example
For the expression grammar in the box, FIRST(E) = FIRST(T) = FIRST(F) = { (, id }, FIRST(E') = { +, ε } and FIRST(T') = { *, ε }; FOLLOW(E) = FOLLOW(E') = { ), $ }, FOLLOW(T) = FOLLOW(T') = { +, ), $ } and FOLLOW(F) = { +, *, ), $ }. No cell has two rules, so the grammar is LL(1), and "id + id * id" is accepted. The left-recursive version E -> E + T | T is rewritten into exactly this grammar.
Frequently asked questions
Why is ε in FIRST but never in FOLLOW?
FIRST(A) contains ε when A can derive the empty string. FOLLOW(A) lists terminals that can appear right after A, plus $ for the end of the input — ε is not a symbol that can follow anything.
How do I write symbols longer than one character?
Separate every symbol with spaces: E -> E + T | id. In one-character mode capital letters (with optional ' or digits) are nonterminals and every other character is a terminal.
What does a conflict mean?
Two rules for the same nonterminal start with the same lookahead token, so a predictive parser cannot choose. Left factoring, removing left recursion or changing the language usually fixes it; some languages, such as dangling else, are not LL(1) at all.
Sources
Last updated:
Page address with these inputs: https://kakao.mobile/tools/context-free-grammar-tool/
Cite or embed this tool
kakaoCalc. (2026, November 8). FIRST and FOLLOW Calculator (LL(1) Parsing Table). https://kakao.mobile/tools/context-free-grammar-tool/
“FIRST and FOLLOW Calculator (LL(1) Parsing Table).” kakaoCalc, 8 Nov. 2026, kakao.mobile/tools/context-free-grammar-tool/.
Paste this code into your page. The widget runs in your visitors' browsers, shows no ads and keeps a link back to this page. Embedding terms