ToolSphere

LL(1) Parser

Computer science

Compute FIRST and FOLLOW sets, remove left recursion, build the LL(1) parsing table, detect conflicts and trace a parse step by step.

Type a grammar and a token string to build its predictive table and follow the parse.

Accepted: the input matches this grammar.

Grammar (one rule per line)

One rule per line, spaces between symbols: E -> E + T | T. Write ε (or eps) for an empty right side, one that matches nothing. The first rule is the start.

FIRST & FOLLOW sets

Non-terminalFIRSTFOLLOW
E{ (, id }{ $, ) }
E'{ +, ε }{ $, ) }
T{ (, id }{ +, $, ) }
T'{ *, ε }{ +, $, ) }
F{ (, id }{ *, +, $, ) }

LL(1) check

No conflicts: this grammar is LL(1).

LL(1) parsing table

Non-terminal+*()id$
E
E'
T
T'
F

Click any entry to see why it is there: a production A → α goes under every terminal in FIRST(α), and under FOLLOW(A) too when α can derive ε.

Parse an input string

Accepted in 17 steps

StepStackInputAction
1$ Eid + id * id $Output E → T E'
2$ E' Tid + id * id $Output T → F T'
3$ E' T' Fid + id * id $Output F → id
4$ E' T' idid + id * id $Match id
5$ E' T'+ id * id $Output T' → ε
6$ E'+ id * id $Output E' → + T E'
7$ E' T ++ id * id $Match +
8$ E' Tid * id $Output T → F T'
9$ E' T' Fid * id $Output F → id
10$ E' T' idid * id $Match id
11$ E' T'* id $Output T' → * F T'
12$ E' T' F ** id $Match *
13$ E' T' Fid $Output F → id
14$ E' T' idid $Match id
15$ E' T'$Output T' → ε
16$ E'$Output E' → ε
17$$Accept

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use LL(1) Parser

  1. 1Paste your grammar, one rule per line (for example E' -> + T E' | ε), or load an example.
  2. 2If the grammar is left-recursive, click Remove left recursion; if two alternatives share a prefix, click Left factor.
  3. 3Read the FIRST and FOLLOW sets and the LL(1) table. Click any table entry to see whether it came from FIRST or FOLLOW.
  4. 4If the grammar is not LL(1), read why: each conflict is labelled FIRST/FIRST or FIRST/FOLLOW, with the reason for every production in the cell.
  5. 5Type an input string to trace the parse step by step.

About LL(1) Parser

FIRST, FOLLOW, and Why LL(1) Parsing Needs Both

An LL(1) parser decides which grammar production to apply by looking at just one token of lookahead — which only works if that single token unambiguously identifies the correct production. FIRST sets (which terminal symbols can begin a string derived from a given non-terminal) and FOLLOW sets (which terminals can immediately follow a non-terminal in some derivation) are the machinery that makes this one-token decision possible, by predicting exactly what token to expect next at each point in a derivation.

A grammar is genuinely LL(1)-parseable only if, for every non-terminal with multiple productions, their FIRST sets don't overlap (with FOLLOW sets brought in for productions that can derive the empty string) — if they do overlap, one token of lookahead isn't enough to decide which production applies, and the grammar needs restructuring (or a more powerful parsing strategy) before an LL(1) parser can handle it.

Building the parsing table from FIRST/FOLLOW sets, then tracing a token string through the parser's stack step by step, is exactly how compiler courses demonstrate whether a given grammar is well-behaved for simple top-down parsing — a check that's tedious but mechanical by hand, and easy to get wrong on a non-trivial grammar.

Worked example

For the classic expression grammar E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → ( E ) | id:

  • FIRST(E) = FIRST(T) = FIRST(F) = { (, id }, FIRST(E') = { +, ε } and FIRST(T') = { *, ε }
  • FOLLOW(E) = FOLLOW(E') = { ), $ }, FOLLOW(T) = FOLLOW(T') = { +, ), $ } and FOLLOW(F) = { *, +, ), $ }

The parsing table has no conflicts, so the grammar is LL(1), and id + id * id is accepted. This grammar is the left-recursion-free form of E → E + T | T, T → T * F | F, F → ( E ) | id, which is exactly what the Remove left recursion button produces from it.

Why is my grammar not LL(1)?

A conflict means two productions landed in the same table cell, and there are only two ways that happens:

  • FIRST/FIRST: two alternatives of A can both start with the same token. Usually the grammar is left-recursive, or two alternatives share a prefix and need left factoring.
  • FIRST/FOLLOW: one alternative of A can derive ε, so it goes under every token in FOLLOW(A), and one of those tokens also starts another alternative. The dangling else is the classic case: after left factoring S → i E t S | i E t S e S | a into S → i E t S S' | a and S' → e S | ε, the cell M[S', e] still holds both S' → e S and S' → ε, because e ∈ FOLLOW(S'). No rewrite fixes that: the grammar is ambiguous, and real parsers resolve it by always shifting the else.

The tool names the kind, shows why each production is in the cell, and suggests the fix that applies.

Where this fits

The table here is built from the sets the FIRST and FOLLOW calculator computes, which is where to look when a cell has a conflict. If the grammar is left-recursive or cannot be left-factored into LL(1), bottom-up parsing usually works where top-down fails: try the same grammar in the LR parser, which handles left recursion as written.

Guides and tutorials

Frequently asked questions

Why does LL(1) parsing need both FIRST and FOLLOW sets?

FIRST sets predict which token can start a non-terminal's derivation; FOLLOW sets handle the case where a production can derive the empty string, in which case what comes *after* the non-terminal in the grammar is what actually determines the correct choice.

What does it mean if a grammar isn't LL(1)?

The parser can't decide which production to apply using only one token of lookahead — some non-terminal's productions have overlapping FIRST (or FIRST/FOLLOW) sets, which means the grammar needs restructuring or a more powerful parsing approach.

Is left recursion compatible with LL(1) parsing?

No — left-recursive grammars cause an LL(1) (or any top-down) parser to loop infinitely without ever consuming input, so left recursion must be eliminated (rewritten as right recursion) before LL(1) parsing can work.

How do I remove left recursion from a grammar?

Rewrite A → A α | β as A → β A' and A' → α A' | ε. For indirect left recursion, first substitute earlier non-terminals into later ones (the standard algorithm from the Dragon Book). The Remove left recursion button does both.

How do I type ε (epsilon)?

Use ε, eps or epsilon; all three are treated as the empty string. Put a space between every symbol, for example E' -> + T E' | eps.

What is left factoring and when do I need it?

When two alternatives of a non-terminal start with the same symbols, one token of lookahead can't choose between them. Left factoring pulls the shared prefix out: A → α β₁ | α β₂ becomes A → α A' and A' → β₁ | β₂. The Left factor button does this, repeatedly, until no two alternatives share a first symbol.

How is each entry in the LL(1) parsing table calculated?

For each production A → α, put it under every terminal in FIRST(α). If α can derive ε, also put it under every terminal in FOLLOW(A), including $. Click any cell in the table to see which rule placed it there, for example M[E', )] = E' → ε because ) ∈ FOLLOW(E').

Have a suggestion for LL(1) Parser?Share your feedback ↗