LL(1) Parsing

Build a parse table for an LL(1) grammar and use it to find the leftmost derivation of a line of code.

Brief Explanation

A grammar is LL(1) if (roughly) you can unambiguously decide which grammar rule to use from exactly one token of lookahead. Although LL parsers have some shortcomings, they are easier to understand than LR parsers, which have always seemed to me like reaching into your left pocket with your right hand: it gives you the right result but is quite contorted.

An LL(1) grammar is well suited to table-based parsing. This page implements all the steps in constructing and using such a table.

Try It Yourself

A simple LL(1) grammar is provided, along with a correct line of code. (You can change the grammar; instructions below.)

  1. Click to derive all the required sets and construct the parse table.
    Or, click each button sequentially.
  2. Click to initialize the parser.
  3. Click repeatedly to parse the source code.

Table Builder



Terminals will go here

Non-terminals will go here

Nullables will go here

FIRST(A) = { t : (tε & A →* tβ) | (t = ε & A →* ε) }
FIRST set will go here

FOLLOW(A) = { t : (t$ & S →+ αAtβ) | (t = $ & S →* αA) }
FOLLOW set will go here

Numbered Grammar
Numbered grammar will go here

Table will go here


Source (current token is red)
( num * ( num + num ) )

Actions (token ; terminal/non-terminal stack ; action token/rule)
Actions will go here

Derivation (substitution rule➝)
Derivation will go here


Example 1 is the grammar that appears when you (re)load this page. Example 2 is the left-factored form of the common example grammar

E ➝ T + E | T
T ➝ num | num * num | ( E )

You can change the grammar as you see fit. Some requirements:

See Also

iPhone Apps

Web Apps