Context-free grammars and top-down parsing

The scanner tells us what the words of a program are; the parser determines how they fit together. Its input is the token stream and its output is a tree that makes the program's structure explicit: which expression is the condition of an if, which statements form a loop body, which operator applies to which operands. Parsing is the best-understood part of compiler construction, thanks to a body of theory developed in the 1960s, and it is the phase where the gap between theory and practice is smallest. This lesson and the next cover the two great families of parsing methods: top-down methods, which build the tree from the root and are easy to write by hand, and bottom-up methods, which build it from the leaves and are usually generated by tools.

CMPUT-325 (lesson 2) introduced context-free grammars, derivations, ambiguity and recursive-descent parsing at the level a language designer needs. We now look at parsing as a compiler writer must: which grammars a method can handle, how to transform grammars that it cannot, how to compute the sets that drive a predictive parser, how to handle precedence efficiently, and how to recover from errors.

Context-free grammars

A context-free grammar consists of terminals (the token kinds), nonterminals (syntactic categories such as expression or statement), a start symbol, and productions of the form \(A \to \alpha\), where A is a nonterminal and α is a string of terminals and nonterminals. A derivation starts from the start symbol and repeatedly replaces a nonterminal by the right-hand side of one of its productions; the language of the grammar is the set of terminal strings that can be derived. A parse tree records a derivation: each interior node is a nonterminal, its children are the symbols of the production used, and the leaves read from left to right spell the input. The name context-free means that a nonterminal can be replaced regardless of what surrounds it. Grammars are usually written in Backus–Naur Form (BNF) or extended BNF, which adds repetition and optional parts.

This grammar for arithmetic expressions encodes both precedence and associativity in its structure. Multiplication is lower in the tree than addition because T is derived from E, so * binds more tightly. The productions \(E \to E + T\) are left-recursive, which makes the operators left-associative: a − b − c parses as (a − b) − c. A grammar that allows two different parse trees for the same string is ambiguous. The simpler grammar \(E \to E + E \mid E * E \mid \mathit{id}\) is ambiguous, because it does not say which operator applies first, and ambiguity is a property compilers cannot tolerate because the two trees usually mean different things. No algorithm can decide whether an arbitrary context-free grammar is ambiguous (CMPUT-474 proves results of this kind), so grammar writers rely on well-understood patterns and on parser generators that report conflicts.

The parse tree contains details that later phases do not need: chains of nonterminals such as E to T to F, and tokens like parentheses whose only purpose is grouping. Compilers therefore build an abstract syntax tree (AST), which keeps the operators and operands and discards the rest. Most parsers build the AST directly rather than building a parse tree and simplifying it. Lesson 5 designs Tern's AST.

Top-down parsing and recursive descent

A top-down parser starts with the start symbol and tries to derive the input, always expanding the leftmost nonterminal, so it traces a leftmost derivation. Recursive descent implements this with one procedure per nonterminal; the procedure for A decides which production of A to use and calls the procedures for its symbols in turn. The difficulty is the decision. A predictive parser decides by looking at the next token, the lookahead, without backtracking. That works only if the grammar is suitable, and two common features make it unsuitable.

The first is left recursion. With the production \(E \to E + T\), the procedure for E would call itself immediately without consuming input and recurse forever. Left recursion is removed by rewriting: \(A \to A\alpha \mid \beta\) becomes \(A \to \beta A'\) and \(A' \to \alpha A' \mid \varepsilon\), where ε is the empty string. The language is unchanged, but the trees become right-leaning, so the parser must rebuild left-associative ASTs itself, usually with a loop, as our miniature compiler did in lesson 1. The second is common prefixes: with \(S \to \mathbf{if}\ E\ \mathbf{then}\ S \mid \mathbf{if}\ E\ \mathbf{then}\ S\ \mathbf{else}\ S\), the parser cannot choose until it has seen the whole then-part. Left factoring postpones the choice: \(S \to \mathbf{if}\ E\ \mathbf{then}\ S\ S'\) with \(S' \to \mathbf{else}\ S \mid \varepsilon\).

FIRST and FOLLOW sets

To choose productions mechanically, a predictive parser needs two sets. FIRST(α) is the set of terminals that can begin a string derived from α, plus ε if α can derive the empty string. FOLLOW(A) is the set of terminals that can appear immediately after A in some sentential form, with the end-of-input marker written as $ for the start symbol. Both are computed by iterating simple rules until nothing changes, a fixed-point computation of the kind we will meet again in data-flow analysis. With these sets, the parser expands A by \(A \to \alpha\) when the lookahead is in FIRST(α), or, if α can derive ε, when the lookahead is in FOLLOW(A). A grammar is LL(1), meaning it can be parsed left to right, producing a leftmost derivation, with one token of lookahead, if these rules never give two choices for the same nonterminal and lookahead.

# FIRST and FOLLOW sets and the LL(1) parse table for the expression grammar
# after left recursion has been removed. "eps" is the empty string.
G = {   # nonterminal -> list of productions (each a list of symbols)
    "E":  [["T", "E'"]],
    "E'": [["+", "T", "E'"], ["eps"]],
    "T":  [["F", "T'"]],
    "T'": [["*", "F", "T'"], ["eps"]],
    "F":  [["(", "E", ")"], ["id"]],
}
NT = list(G); START = "E"
FIRST = {A: set() for A in NT}
def first_of(seq):                      # FIRST of a sequence of symbols
    out = set()
    for X in seq:
        if X == "eps": continue
        f = FIRST[X] if X in G else {X}
        out |= f - {"eps"}
        if "eps" not in f: return out
    return out | {"eps"}
changed = True
while changed:                          # iterate to a fixed point
    changed = False
    for A in NT:
        for rhs in G[A]:
            new = first_of(rhs) - FIRST[A]
            if new: FIRST[A] |= new; changed = True
FOLLOW = {A: set() for A in NT}; FOLLOW[START].add("$")
changed = True
while changed:
    changed = False
    for A in NT:
        for rhs in G[A]:
            for i, B in enumerate(rhs):
                if B not in G: continue
                f = first_of(rhs[i + 1:])
                new = (f - {"eps"}) | (FOLLOW[A] if "eps" in f else set())
                if new - FOLLOW[B]: FOLLOW[B] |= new; changed = True
order = ["id", "+", "*", "(", ")", "$"]
srt = lambda s: " ".join(sorted(s, key=lambda t: (order + ["eps"]).index(t)))
for A in NT: print(f"{A:3} FIRST = {{{srt(FIRST[A])}}}   FOLLOW = {{{srt(FOLLOW[A])}}}")
table, conflicts = {}, 0
for A in NT:
    for rhs in G[A]:
        f = first_of(rhs)
        for a in (f - {"eps"}) | (FOLLOW[A] if "eps" in f else set()):
            if (A, a) in table: conflicts += 1
            table[A, a] = rhs
print("\nLL(1) table (blank = error):")
print("     " + "".join(f"{a:>11}" for a in order))
for A in NT:
    print(f"{A:4} " + "".join(f"{' '.join(table[A, a]) if (A, a) in table else '':>11}" for a in order))
print("conflicts:", conflicts)

E   FIRST = {id (}   FOLLOW = {) $}
E'  FIRST = {+ eps}   FOLLOW = {) $}
T   FIRST = {id (}   FOLLOW = {+ ) $}
T'  FIRST = {* eps}   FOLLOW = {+ ) $}
F   FIRST = {id (}   FOLLOW = {+ * ) $}

LL(1) table (blank = error):
              id          +          *          (          )          $
E           T E'                             T E'                      
E'                   + T E'                              eps        eps
T           F T'                             F T'                      
T'                      eps     * F T'                   eps        eps
F             id                            ( E )                      
conflicts: 0

The table has no conflicts, so the transformed grammar is LL(1). Each blank entry is an error: if the parser is expanding T' and sees id, no valid program can continue that way. Observe how ε-productions are placed in the columns of FOLLOW: E' disappears when the lookahead is ) or $, which is exactly when an expression has ended.

Table-driven LL parsing

Instead of recursive procedures, an LL(1) parser can use an explicit stack and the table. The stack holds the symbols still to be matched, with the start symbol on top initially. At each step, if the top is a terminal, it must equal the lookahead and both are consumed; if it is a nonterminal, the table entry for it and the lookahead says which production to push, in reverse order so that its first symbol ends up on top. The parser accepts when the stack and the input are both down to $. The trace below parses id + id * id and then an invalid input.

# A table-driven LL(1) parser: an explicit stack replaces recursion.
# The table is the one computed above.
T = {("E", "id"): ["T", "E'"], ("E", "("): ["T", "E'"],
     ("E'", "+"): ["+", "T", "E'"], ("E'", ")"): [], ("E'", "$"): [],
     ("T", "id"): ["F", "T'"], ("T", "("): ["F", "T'"],
     ("T'", "*"): ["*", "F", "T'"], ("T'", "+"): [], ("T'", ")"): [], ("T'", "$"): [],
     ("F", "id"): ["id"], ("F", "("): ["(", "E", ")"]}
def parse(tokens):
    toks = tokens + ["$"]; i = 0; stack = ["$", "E"]
    print(f"{'stack':22}{'input':18}action")
    while True:
        top, a = stack[-1], toks[i]
        print(f"{' '.join(stack):22}{' '.join(toks[i:]):18}", end="")
        if top == a == "$": print("accept"); return True
        if top == a: stack.pop(); i += 1; print(f"match {a}"); continue
        rhs = T.get((top, a))
        if rhs is None: print(f"error: unexpected {a!r} while expanding {top}"); return False
        stack.pop(); stack.extend(reversed(rhs))
        print(f"{top} -> {' '.join(rhs) or 'eps'}")
parse(["id", "+", "id", "*", "id"])
print()
parse(["id", "+", "*", "id"])

stack                 input             action
$ E                   id + id * id $    E -> T E'
$ E' T                id + id * id $    T -> F T'
$ E' T' F             id + id * id $    F -> id
$ E' T' id            id + id * id $    match id
$ E' T'               + id * id $       T' -> eps
$ E'                  + id * id $       E' -> + T E'
$ E' T +              + id * id $       match +
$ E' T                id * id $         T -> F T'
$ E' T' F             id * id $         F -> id
$ E' T' id            id * id $         match id
$ E' T'               * id $            T' -> * F T'
$ E' T' F *           * id $            match *
$ E' T' F             id $              F -> id
$ E' T' id            id $              match id
$ E' T'               $                 T' -> eps
$ E'                  $                 E' -> eps
$                     $                 accept

stack                 input             action
$ E                   id + * id $       E -> T E'
$ E' T                id + * id $       T -> F T'
$ E' T' F             id + * id $       F -> id
$ E' T' id            id + * id $       match id
$ E' T'               + * id $          T' -> eps
$ E'                  + * id $          E' -> + T E'
$ E' T +              + * id $          match +
$ E' T                * id $            error: unexpected '*' while expanding T

The parser detects the error at the earliest possible point: after id +, no valid expression can continue with *. This valid-prefix property, shared by LL and LR parsers, makes their error positions accurate. LL table-driven parsers are produced by generators such as ANTLR, whose current version uses an adaptive algorithm called ALL(*) that looks ahead as far as needed and handles a much larger class of grammars than LL(1). ANTLR is widely used for domain-specific languages, data formats and tools.

Recursive descent in practice

Most hand-written parsers, including those of GCC (since it replaced its yacc-based C and C++ parsers in the 2000s), Clang, the Go compiler, rustc, V8 and javac, are recursive descent. They are not pure LL(1): they look further ahead when needed, consult the symbol table to resolve C's notorious ambiguity between declarations and expressions (is a * b; a multiplication or a pointer declaration?), and use loops rather than tail nonterminals for repetition. The advantages are control and clarity: the parser is ordinary code that can produce excellent error messages, recover gracefully and build the AST directly. The cost is that nothing checks the grammar for you; conflicts that a generator would report silently become bugs.

Parsing expressions with precedence: Pratt parsing

Expression grammars with many precedence levels make recursive descent tedious: C has around fifteen levels, and a separate procedure per level means a chain of fifteen calls to parse a single identifier. Vaughan Pratt's top-down operator precedence method (1973), also known as precedence climbing, handles all binary operators in one loop. Each operator has a binding power. The procedure parse_expression(min) first parses a prefix (a literal, a name, a parenthesized expression or a unary operator applied to its operand), then repeatedly looks at the next operator: if it binds more tightly than min, it consumes it, parses the right operand with that operator's binding power as the new minimum, and combines. Left associativity comes from parsing the right operand with the same binding power, so an equal-precedence operator stops the inner call; right associativity, for operators such as assignment or exponentiation, uses a power one lower. Postfix operators such as calls and indexing fit in the same loop.

# A Pratt (precedence-climbing) parser for Tern expressions. Each binary
# operator has a binding power; a loop absorbs operators that bind more
# tightly than the context it was called from. Output: AST as nested tuples.
import re
BP = {"||": 1, "&&": 2, "==": 3, "!=": 3, "<": 4, "<=": 4, ">": 4, ">=": 4,
      "+": 5, "-": 5, "*": 6, "/": 6, "%": 6}
RIGHT = set()                                   # Tern has no right-associative binary ops
def lex(s):
    return re.findall(r"\d+|[A-Za-z_]\w*|==|!=|<=|>=|&&|\|\||[-+*/%<>!()\[\],]", s) + ["$"]
class Parser:
    def __init__(p, src): p.t = lex(src); p.i = 0
    def peek(p): return p.t[p.i]
    def take(p, want=None):
        tok = p.t[p.i]
        if want and tok != want: raise SyntaxError(f"expected {want!r} but found {tok!r}")
        p.i += 1; return tok
    def expr(p, min_bp=0):
        left = p.prefix()
        while True:
            op = p.peek()
            if op == "(":                       # call: highest precedence postfix
                p.take(); args = []
                while p.peek() != ")":
                    args.append(p.expr()); p.peek() == "," and p.take()
                p.take(")"); left = ("call", left, args); continue
            if op == "[":                       # indexing
                p.take(); idx = p.expr(); p.take("]"); left = ("index", left, idx); continue
            bp = BP.get(op)
            if bp is None or bp <= min_bp: return left
            p.take()
            right = p.expr(bp - 1 if op in RIGHT else bp)
            left = (op, left, right)
    def prefix(p):
        tok = p.take()
        if tok.isdigit(): return int(tok)
        if tok in ("true", "false"): return tok == "true"
        if tok == "(": e = p.expr(); p.take(")"); return e
        if tok in ("-", "!"): return ("neg" if tok == "-" else "not", p.expr(7))
        if re.fullmatch(r"[A-Za-z_]\w*", tok): return tok
        raise SyntaxError(f"unexpected {tok!r} at start of expression")
for src in ["1 + 2 * 3 - 4", "a - b - c", "x < y + 1 && !done || f(n - 1, a[i]) == 0",
            "-a * b", "(1 + 2) * 3", "1 + * 2"]:
    try: print(f"{src:44} => {Parser(src).expr()}")
    except SyntaxError as e: print(f"{src:44} => error: {e}")

1 + 2 * 3 - 4                                => ('-', ('+', 1, ('*', 2, 3)), 4)
a - b - c                                    => ('-', ('-', 'a', 'b'), 'c')
x < y + 1 && !done || f(n - 1, a[i]) == 0    => ('||', ('&&', ('<', 'x', ('+', 'y', 1)), ('not', 'done')), ('==', ('call', 'f', [('-', 'n', 1), ('index', 'a', 'i')]), 0))
-a * b                                       => ('*', ('neg', 'a'), 'b')
(1 + 2) * 3                                  => ('*', ('+', 1, 2), 3)
1 + * 2                                      => error: unexpected '*' at start of expression

The trees show precedence and associativity working together: a − b − c groups to the left, comparison binds more tightly than &&, which binds more tightly than ||, and the call f(n − 1, a[i]) is parsed as a postfix operator on f. Unary minus binds more tightly than multiplication here because its operand is parsed with a binding power of 7, above every binary operator. Pratt parsers are used in many real compilers and tools for expressions, often inside an otherwise ordinary recursive-descent parser; Tern's parser in lesson 5 is built exactly that way.

Syntax error recovery

A parser that stops at the first error is frustrating to use, so real parsers recover and continue. Panic-mode recovery discards tokens until it finds a synchronizing token, such as a semicolon or closing brace, from which parsing can sensibly resume; in recursive descent, each statement procedure can catch an error, report it, skip to the next semicolon or closing brace, and return. Phrase-level recovery makes a local repair, such as inserting a missing semicolon, when one repair is overwhelmingly likely. Error productions add rules to the grammar for common mistakes so the parser can recognize them and give a specific message. The art lies in avoiding cascades, where one real error produces dozens of spurious ones; a common trick is to suppress further messages until a few tokens have been parsed successfully. Modern compilers go further: rustc and Clang print the offending line with a marker under the error and often a suggested fix, and language servers keep parsing incomplete code as you type so that editors can offer completion.

LL(1) and beyond

The LL(1) class is quite restrictive. Every LL(1) grammar is unambiguous and has no left recursion, and many natural grammars must be transformed, sometimes heavily, to fit. LL(k) parsers with k tokens of lookahead are more powerful, and modern variants such as ALL(*) adapt k to the input. Another approach avoids grammars altogether: parsing expression grammars (PEGs), introduced by Bryan Ford in 2004, use ordered choice, trying alternatives in sequence and committing to the first that succeeds, which makes them unambiguous by construction. CPython replaced its LL(1) parser with a PEG parser in version 3.9 (2020), which let the language adopt syntax, such as parenthesized context managers and the match statement, that the old parser could not handle. The trade-off is that ordered choice can silently hide alternatives that a CFG tool would flag as a conflict.

Worked examples