How to use the LL(1) Parsing Table Generator
- 1. Type the grammarOne rule per line with | between alternatives and ε for empty. The first rule is the start.
- 2. Add an inputOptionally type a string like id + id * id. The tool adds $ at the end.
- 3. Check the tableSee the parsing table, any conflict cells, FIRST and FOLLOW sets, and the parse trace.
How the LL(1) table is built
An LL(1) parser reads input left to right, builds a leftmost derivation and looks at 1 token ahead. Its table M[A, a] tells it which production to use for non-terminal A when the next token is a. For each production A → α:
- For every terminal a in FIRST(α), put A → α in M[A, a].
- If ε is in FIRST(α), put A → α in M[A, b] for every b in FOLLOW(A), including $.
A grammar is LL(1) if no cell gets two productions. Left recursion, or two alternatives that start with the same terminal, always cause a conflict. Remove left recursion and left-factor the grammar first.
Worked example
For E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε and F → ( E ) | id:
- M[E, id] = M[E, (] = E → T E'.
- M[E', +] = E' → + T E'. M[E', )] = M[E', $] = E' → ε, because FOLLOW(E') = { ), $ }.
- M[T', *] = T' → * F T'. M[T', +], M[T', )] and M[T', $] get T' → ε.
Parsing id + id * id $ starts with stack $ E. Each step either expands the top non-terminal using the table or matches a terminal. The parse accepts in 17 steps.
Spotting non-LL(1) grammars
The dangling-else grammar S → i E t S S' | a, S' → e S | ε, E → b has a conflict at M[S', e]. Here e is in both FIRST(e S) and FOLLOW(S'). Parsers settle this by choosing S' → e S, which matches each else with the nearest then. When a conflict appears, the tool marks the cell with ⚠ and the trace uses the first entry. Check the sets with the FIRST and FOLLOW calculator.
Frequently asked questions
What makes a grammar not LL(1)?
A cell in the table with two or more productions. Common causes are left recursion, common prefixes and ambiguity.
How do I remove left recursion?
Rewrite A → A α | β as A → β A' and A' → α A' | ε. Then rebuild the table.
Why does the stack show $ at the left?
The stack is written with the bottom on the left and the top on the right, so $ is always at the bottom.
Can I enter tokens without spaces?
Yes. The tool splits the input by matching the grammar's terminals, longest first. Spaces are safer for long tokens.