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

Grammar
E -> num E -> ( E Op E ) Op -> + Op -> *


Terminals

Parser

Remarks

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.

See Also

iPhone Apps

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

Web Apps

• 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.