LL(1) parsing with a table

Advanced

Introduction

Recursive descent hides its decisions inside code. A table-driven parser makes them explicit: a table says, for each nonterminal and each possible next token, which rule to use. The parser itself is then a short loop with a stack, the same for every grammar. This is how parser generators work, and building the table shows precisely which grammars can be parsed by looking at just one token.

How it works

The table has a row per nonterminal and a column per terminal (plus $). For each rule A → α:

  1. for every terminal a in FIRST(α), put the rule in M[A, a];
  2. if α can derive ε, put it in M[A, b] for every b in FOLLOW(A).

If some cell receives two different rules, that is a conflict: the grammar is not LL(1). Left-recursive grammars always conflict, and so do rules that start the same way, such as S → a b | a c (fixed by left factoring: S → a S', S' → b | c).

The parser keeps a stack that starts with $ and the start symbol. Each step looks at the top of the stack and the next token a:

  • if the top is a terminal, it must equal a: pop it and move to the next token (match);
  • if the top is a nonterminal A, look up M[A, a]; if it is empty that is a syntax error, otherwise pop A and push the rule's body in reverse, so that its first symbol ends on top;
  • when $ is matched with the end of the input, the parser accepts.

The rules used, in order, form a leftmost derivation, which is the first L of LL(1); the other L is for reading the input left to right, and the 1 is the single token of lookahead.

Syntax

for each rule A -> body:
    for t in FIRST(body):            table[(A, t)] = body
    if body can vanish:
        for t in FOLLOW(A):          table[(A, t)] = body
stack = ["$", start]
# loop: match a terminal, or expand a nonterminal with table[(top, next_token)]

Example

grammar = {
    "E": [["T", "E'"]],
    "E'": [["+", "T", "E'"], []],
    "T": [["F", "T'"]],
    "T'": [["*", "F", "T'"], []],
    "F": [["(", "E", ")"], ["id"]],
}
first = {"E": {"(", "id"}, "E'": {"+"}, "T": {"(", "id"}, "T'": {"*"}, "F": {"(", "id"}}
follow = {"E": {")", "$"}, "E'": {")", "$"}, "T": {"+", ")", "$"}, "T'": {"+", ")", "$"}, "F": {"*", "+", ")", "$"}}

table = {}
for head, bodies in grammar.items():
    for body in bodies:
        starts = first[body[0]] if body and body[0] in grammar else ({body[0]} if body else follow[head])
        for t in starts:
            table[(head, t)] = body


def parse(tokens):
    tokens = tokens + ["$"]
    stack, i = ["$", "E"], 0
    while stack:
        top, a = stack.pop(), tokens[i]
        if top == a:
            i += 1
            if a == "$":
                return "accept"
        elif top in grammar and (top, a) in table:
            body = table[(top, a)]
            print(f"  {top} -> {' '.join(body) or 'ε'}")
            stack.extend(reversed(body))
        else:
            return f"error at {a!r}"


for text in ["id + id * id", "( id"]:
    print(text)
    print(" ", parse(text.split()))
Open in compiler

Line by line

  1. The FIRST and FOLLOW sets are those computed in the previous lesson.
  2. The table loop puts each rule under the tokens that can start it, and an ε-rule under the tokens that can follow its left side.
  3. parse keeps an explicit stack; pushing a body in reverse makes its first symbol the next one to handle.
  4. For id + id * id the rules printed are the leftmost derivation, and the input is accepted.
  5. For ( id the parser expects ) but reaches the end, so it reports an error at $.

Expected result

id + id * id
  E -> T E'
  T -> F T'
  F -> id
  T' -> ε
  E' -> + T E'
  T -> F T'
  F -> id
  T' -> * F T'
  F -> id
  T' -> ε
  E' -> ε
  accept
( id
  E -> T E'
  T -> F T'
  F -> ( E )
  E -> T E'
  T -> F T'
  F -> id
  T' -> ε
  E' -> ε
  error at '$'

In the real world

ANTLR generates LL parsers (with more lookahead when needed) for languages from Java to SQL. Table-driven LL(1) parsers appear in embedded systems and in tools that need predictable memory use, because they never recurse. Knowing the conflicts also explains grammar design choices, such as why many languages put a keyword at the start of every statement.

Common mistakes

  • Pushing the body in the wrong order, so symbols are handled backwards.
  • Forgetting the FOLLOW rule for ε-productions, so valid input is rejected.
  • Ignoring conflicts, which silently picks one rule and rejects valid input.
  • Feeding a left-recursive grammar, which always conflicts.

Best practices

  • Remove left recursion and left-factor the grammar before building the table.
  • Report every conflict with its nonterminal and token, so the grammar can be fixed.
  • Print the rules used while testing; they should form a sensible leftmost derivation.

Summary

An LL(1) table puts each rule under the tokens that can start it, and ε-rules under the tokens that can follow their left side. A stack-based loop then matches terminals and expands nonterminals from the table, producing a leftmost derivation without recursion. A cell with two rules means the grammar is not LL(1).

Quick check

1. Where does the rule E' → ε go in the table?
2. What does a table cell with two rules mean?
3. Why push a rule's body in reverse order?
4. What does the 1 in LL(1) stand for?

Key takeaways

  • Rule A → α goes in M[A, a] for every a in FIRST(α), and in M[A, b] for every b in FOLLOW(A) if α can vanish.
  • The parser pops the stack: it matches terminals and expands nonterminals using the table.
  • A cell with two rules means one token of lookahead is not enough.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.