Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 61 ยท Parsing

LL(1) Table-Driven Parsing

Build an LL(1) parsing table from FIRST and FOLLOW sets, run a stack-based predictive parser step by step, and detect conflicts such as the dangling else.

A recursive descent parser hides the grammar inside code: each rule is a function, and the if chains in the functions encode the decisions. A table-driven LL(1) parser takes the opposite approach. The decisions live in a parsing table, and the parser itself is a tiny loop that never changes, whatever the grammar. Give the loop a different table and it parses a different language.

This is more than an alternative style. Building the table is a systematic way to find out whether a grammar is LL(1) at all, and it shows exactly which pairs of productions clash. Parser generators such as ANTLR (in its classic form) and many teaching tools work this way. You will need the FIRST and FOLLOW sets from earlier in the track, so refresh them if needed.

The parsing table

The table, usually written M, has one row for each nonterminal and one column for each terminal (plus the end marker $). The entry M[A, a] tells the parser which production to use when it must expand A and the next input token is a. An empty cell means "syntax error".

The table is filled in by looking at every production A -> ฮฑ:

  1. For every terminal a in FIRST(ฮฑ), put A -> ฮฑ into M[A, a].
  2. If ฮฑ can derive the empty string (ฮต is in FIRST(ฮฑ)), then for every terminal b in FOLLOW(A) (including $) put A -> ฮฑ into M[A, b].

Rule 1 says "this production can start with a". Rule 2 says "this production can vanish, and b may legally come right after A, so choosing it is the right move when we see b". A grammar is LL(1) exactly when no cell receives more than one production.

flowchart LR
    P["Production A โ†’ ฮฑ"] --> F["FIRST(ฮฑ) without ฮต"]
    P --> N{"ฮฑ can vanish?"}
    N -->|"yes"| W["FOLLOW(A)"]
    F --> M["M[A, token] = A โ†’ ฮฑ"]
    W --> M

Each production is filed under every token that could justify choosing it.

The stack machine

The driver keeps a stack of grammar symbols that the parser still expects to see, with the end marker $ at the bottom and the start symbol above it. It also keeps a pointer to the current input token, the lookahead. Then it repeats:

  • If the top of the stack is a terminal (or $): it must equal the lookahead. If it does, pop it and advance the input (a match). If not, report a syntax error.
  • If the top is a nonterminal A: look up M[A, lookahead]. If the cell is empty, report an error. Otherwise pop A and push the right-hand side of the production in reverse order, so that its first symbol ends up on top. (An ฮต production pushes nothing.)
  • If both the top and the lookahead are $, the input is accepted.
flowchart TD
    S["Look at stack top X and lookahead a"] --> T{"X is a terminal?"}
    T -->|"yes, X = a"| MA["pop X and advance input"]
    T -->|"yes, X differs from a"| ER["syntax error"]
    T -->|"no, X is a nonterminal"| L{"M[X, a] empty?"}
    L -->|"yes"| ER
    L -->|"no"| PU["pop X, push the right side reversed"]

The whole parser is this loop. Only the table changes between languages.

Notice that the stack always holds a prediction of what the rest of the input must look like. The nonterminals on it are promises, and each is resolved when its turn comes. That is exactly the call stack of recursive descent, made explicit.

A table generator and parser you can run

The program below reuses the analysis code from the FIRST and FOLLOW lesson, builds the table for the expression grammar and prints it as a grid (. marks an empty cell). It then runs the driver on id + id * id and prints one line per step: the stack with its top on the left, the remaining input and the action taken. A second run feeds it a broken input.

Python Building an LL(1) table and tracing the parser

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table first. The row for E2 has + T E2 under + and ฮต under both ) and $: the tail of a sum continues if a plus comes next and vanishes if the expression is over. The row for T2 has ฮต under + as well, because after a product a plus means "this term is finished".

Then follow the trace. The stack starts as E $. The step T2 -> ฮต appears several times and does not consume anything; it just discards a promise that turned out not to be needed. When the input is down to $, the parser quietly empties T2 and E2 and accepts with only $ left on both sides. In the second run, after + the parser expects a T, but the table has no entry for T under *, so it stops there and, using the row of the table, can list the tokens that would have been acceptable. The error message comes almost for free.

A table-driven parser can easily build a parse tree or an AST: attach an action to each expansion, or push marker symbols onto the stack that say "build a node now". Hand-written recursive descent usually does this more naturally, which is one reason it is more common for real languages.

Conflicts

When a cell receives two or more productions, the grammar is not LL(1). There are three typical causes:

  • A common prefix. S -> a S | a puts both productions under a. The cure is left factoring.
  • Left recursion. E -> E + T | T puts both productions under every token in FIRST(T). The cure is eliminating left recursion.
  • A real ambiguity. The grammar can derive some string in two ways, and no rewriting of the table will fix that. The famous example is the dangling else: with if a then if b then c else d, does the else belong to the inner or the outer if?

The next program is a conflict detector. It tells you which cells are overloaded and prints both productions that compete. It checks a grammar with a common prefix, the same grammar after left factoring, and the dangling-else grammar. For the last one, it then shows how real parser generators typically escape: the conflict is resolved by a rule (take the non-empty alternative, which attaches else to the nearest if) instead of being rewritten away.

Python Finding conflicts: common prefix, left factoring and the dangling else

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the dangling-else grammar, S2 -> e S | ฮต clashes in the cell [S2, e]: e may start the else-part, and e may also follow the whole statement (because S2 ends an inner S, which itself can be followed by the e of an outer if). Choosing S2 -> e S whenever the conflict appears matches the rule used in languages such as C and Java: an else belongs to the nearest unmatched if. The final run shows exactly one such decision, at the e token, and the parser accepts the input. Hand-written parsers make the same choice implicitly, with a greedy if self.peek() == "else" check.

Limits of LL(1)

LL(1) is simple and fast, but it is a restricted class of grammars. It cannot handle left recursion, it needs a grammar shaped to its lookahead, and the rewrites that make a grammar LL(1) (left factoring, replacing left recursion with tails) tend to obscure the original structure and produce awkward parse trees. More powerful techniques exist: LL(k) and ALL(*) parsers look further ahead, and bottom-up LR parsers accept a larger class of grammars, which you will meet in shift-reduce parsing. For expressions, a Pratt parser is a neat middle path.

Common mistakes

  • Pushing the right-hand side in the wrong order. Push it reversed, so the leftmost symbol is on top.
  • Leaving $ out of FOLLOW. The empty cells under $ are what let the parser finish.
  • Filling ฮต rules with FIRST instead of FOLLOW. An empty production is selected by the tokens that may follow the nonterminal.
  • Treating a conflict as a bug in the table code. A conflict is information about the grammar, not about the algorithm.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When is the production A -> ฮต placed in the cell M[A, b]?

    An empty production is chosen when the lookahead is something that may legally come after A, which is exactly FOLLOW(A).
  2. 2. A parsing table cell contains two productions. What does that tell you?

    Two entries in one cell are an LL(1) conflict. The grammar needs rewriting (or a conflict rule, as with the dangling else).
  3. 3. How does the LL(1) driver expand a nonterminal A with production A -> X Y Z?

    The leftmost symbol must be handled first, so it must end up on top of the stack. That means pushing the symbols in reverse order.
  4. 4. Which grammar problem makes the cell [S, a] receive both S -> a S and S -> a?

    Both alternatives start with the same token, so FIRST sets overlap. Left factoring moves the shared a out and postpones the choice.
  5. 5. In the dangling-else grammar, how is the conflict usually resolved?

    Most languages define that an else binds to the closest preceding if that does not have an else yet, which is the same as preferring the non-empty alternative.

Summary

  • An LL(1) table M[A, a] stores which production to use for nonterminal A when the lookahead is a.
  • Productions are filed under the tokens of their FIRST set, and empty-capable productions also under the tokens of FOLLOW(A).
  • The driver is a fixed loop over a stack: match terminals, expand nonterminals by popping them and pushing the right-hand side reversed, accept when $ meets $.
  • A cell with more than one production is a conflict and means the grammar is not LL(1): common prefixes, left recursion and real ambiguities such as the dangling else are the usual causes.
  • Empty cells give precise syntax errors, because the row lists the tokens that would have been valid.

Next: Pratt Parsing and Operator Precedence