Drawtomata / LL(1) parsing table generator
LL(1) parsing table generator
Type a grammar above and Drawtomata builds the LL(1) table, marks conflicts and explains them, and traces a predictive parse of the input string. Left recursion removal and left factoring are one click away.
Building the table
- Compute FIRST and FOLLOW.
- For each production A → α and each terminal a in FIRST(α), put A → α in M[A, a].
- If ε is in FIRST(α), also put A → α in M[A, b] for every b in FOLLOW(A), including $.
The grammar is LL(1) if no cell holds two productions.
When a grammar is not LL(1)
Left-recursive grammars such as E → E + T | T are never LL(1). Remove the left recursion first (E → T E', E' → + T E' | ε), and left factor alternatives that start the same way. Ambiguous grammars, such as the dangling else, stay in conflict whatever you do.
Questions
What does the parse trace show?
The stack, the remaining input and the action at every step: match a terminal, or expand a nonterminal with the production from the table.