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

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.

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

- Click to derive all the required sets and construct the parse table.

Or, click each button sequentially. - Click to initialize the parser.
- Click repeatedly to parse the source code.

Grammar

Terminals

Terminals will go here

Non-terminals

Non-terminals will go here

Nullables

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

Table will go here

( 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:

- The start production must be the first line.
- All terminals must be non-alphabetic
*or*start with a lower-case letter. - All non-terminals must start with an Upper-Case Letter.
- The epsilon character represents an empty production.
- Every production must have
*only*one right-hand result.

So A ➝ B | c must be rendered with two productions A ➝ B and A ➝ c - In the code, all tokens must be separated by whitespace.

- ana-grabr — Interactive helper for finding anagrams for real words.
- gear-grafr — Tool for plotting gear ratios for bicycles.

- Anagrammer — An application of permutations to real words.
- The Chaos Pages — A series of pages exploring iterated systems.
- The Golden Ratio Pages — A similar series of pages exploring the famous ratio.
- Gear Ratios — These may not be golden, but they are important for people who ride and work with bicycles.
- Gaussian Elimination — A Web tool for reducing matrices to row echelon form — and keeping a list of the steps you take.
- Enumeration — A Web tool for finding permutations and combinations.
- Combinatorial Music Theory — A lecture connecting graph theory with musical scales and chords.
- The 3D Pages — My JavaScript implementation of interactive 3D graphics .
- The DSP Pages — Explaining the Fourier transform in the discrete domains.
- Graph Clock — A good example of using JavaScript to make a self-modifying Web page, and a little puzzle about elementary connected graphs.
- Regular Expressions — Sometimes a non-match can hang the system.
- The Z-Board — A new kind of MIDI controller.