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.

LL(1) Parser

engineering100% Client-Side

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

LL(1) Parser: FIRST & FOLLOW Calculator

Paste a grammar to get FIRST and FOLLOW sets, the LL(1) parsing table and a step-by-step parse.

Grammar (one rule per line)

Write rules as A -> α | β with spaces between symbols; use ε (or eps) for the empty string. Symbols that appear on a left-hand side are non-terminals, everything else is a terminal, and the first rule's left-hand side is the start symbol.

FIRST & FOLLOW sets

Non-terminal	FIRST	FOLLOW
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 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

Parse an input string

Input (spaces optional)

Accepted in 17 steps

Step	Stack	Input	Action
1	$ E	id + id * id $	Output E → T E'
2	$ E' T	id + id * id $	Output T → F T'
3	$ E' T' F	id + id * id $	Output F → id
4	$ E' T' id	id + 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' T	id * id $	Output T → F T'
9	$ E' T' F	id * id $	Output F → id
10	$ E' T' id	id * id $	Match id
11	$ E' T'	* id $	Output T' → * F T'
12	$ E' T' F *	* id $	Match *
13	$ E' T' F	id $	Output F → id
14	$ E' T' id	id $	Match id
15	$ E' T'	$	Output T' → ε
16	$ E'	$	Output E' → ε
17	$	$	Accept

Previous ToolDisk Scheduler Next ToolLR(0) & SLR(1) Parser

How to use LL(1) Parser

1Paste your grammar, one rule per line (for example E' -> + T E' | ε), or load an example.
2If the grammar is left-recursive, click Remove left recursion to rewrite it.
3Read the FIRST and FOLLOW sets and the LL(1) table, then type an input string to trace the parse.

Related Tools

Disk Scheduler

Visualize disk head actuator seek tracks for FCFS, SSTF, SCAN, C-SCAN, and LOOK scheduling.

LR(0) & SLR(1) Parser

Build LR(0) item sets and the ACTION/GOTO table for LR(0) or SLR(1), find shift-reduce and reduce-reduce conflicts, and trace a bottom-up parse.

Page Replacement Calculator

Count page faults and hits for FIFO, LRU and Optimal page replacement with a frame-by-frame table, compare all three, and check for Belady's anomaly.

CPU Scheduling Calculator

Free CPU scheduling calculator for FCFS, SJF, SRTF, Priority and Round Robin: Gantt chart plus completion, turnaround, waiting and response times.

Regex to NFA Converter

Convert regular expression strings into equivalent Nondeterministic Finite Automata using Thompson's construction.

DFA Minimizer

Minimize Deterministic Finite Automata (DFA) using Hopcroft's partition-refinement algorithm.

NFA to DFA Converter

Convert Nondeterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA) using Subset Construction.

Finite Automata Simulator (NFA/DFA)

Draw, design, and simulate Deterministic and Nondeterministic Finite Automata (DFA/NFA) dynamically in-browser.

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.

Frequently Asked Questions

Help Us Improve LL(1) Parser

Did you find this tool helpful? Tell us how we can make it even better, or report a bug or request a new feature in under 1 minute.

Submit Feedback