Parsing: Tokens to ASTs

The lexer gives the parser a sequence like INT(1) PLUS INT(2) STAR INT(3). That sequence is ambiguous: does * bind tighter than +? The grammar must say so. Parsing recovers nesting — the hierarchy that tells you 1 + (2 * 3), not (1 + 2) * 3.

The right tool is a context-free grammar (CFG). CFGs are strictly more powerful than regular expressions: they can describe balanced parentheses and recursive structure, things no finite automaton can match. Every mainstream programming language is defined by a CFG (possibly with a few context-sensitive patches bolted on).

The output of parsing is a tree, not a flat structure. Getting from tokens to that tree is the parser's only job.

A CFG is a set of production rules over terminals (token kinds) and nonterminals (syntactic categories).

expr   ::= expr PLUS  term
         | expr MINUS term
         | term
term   ::= term STAR  factor
         | term SLASH factor
         | factor
factor ::= INT
         | LPAREN expr RPAREN

This grammar encodes precedence structurally: term is nested deeper than expr, so multiplication binds tighter than addition. Left-recursion (expr ::= expr PLUS term) encodes left-associativity — 1 - 2 - 3 parses as (1 - 2) - 3.

BNF (Backus-Naur Form) is the standard notation. EBNF adds * and ? shorthands. Real language specs (C11, Java SE) are essentially large BNF documents.

The most readable parser strategy: one function per nonterminal, each calling others recursively. The grammar above maps directly to code:

def parse_factor(tokens):
    tok = tokens.peek()
    if tok.kind == 'INT':
        tokens.consume()
        return IntNode(tok.value)
    elif tok.kind == 'LPAREN':
        tokens.consume()          # eat '('
        node = parse_expr(tokens)
        tokens.expect('RPAREN')   # eat ')'
        return node
    raise SyntaxError(f'unexpected {tok}')

def parse_term(tokens):
    left = parse_factor(tokens)
    while tokens.peek().kind in ('STAR', 'SLASH'):
        op = tokens.consume().kind
        right = parse_factor(tokens)
        left = BinOpNode(op, left, right)
    return left

Recursive descent is the approach used in Clang, GCC (for C), CPython, and most hand-written production parsers. It handles LL(1) grammars naturally and can handle LL(k) with a bit of lookahead.

A parse tree (concrete syntax tree) mirrors the grammar exactly — every intermediate nonterminal becomes a node. For 1 + 2 * 3 it has nodes for expr, term, factor that carry no semantic payload. It's bulky.

An AST discards noise:

The AST is what all later compiler phases (semantic analysis, type checking, IR generation) actually walk. The parse tree is typically never materialized — the parser builds AST nodes directly.

The AST captures precedence in its shape — multiplication is deeper, so it binds tighter.

Two broad families of parsing algorithms:

Most production compilers use recursive descent (an LL variant) because it gives direct control over error messages. LALR(1) generators like Bison are common for language prototyping. Shift/reduce conflict: the parser sees a symbol on the stack and a lookahead token but can't decide whether to shift (push) or reduce (apply a rule).

A grammar is ambiguous if a single input string has more than one parse tree. The canonical example is the dangling else:

if (a) if (b) x(); else y();

Which if does else belong to? The naive CFG rule

stmt ::= IF LPAREN expr RPAREN stmt
       | IF LPAREN expr RPAREN stmt ELSE stmt
       | ...

gives two parse trees. C and Java resolve it by the nearest-enclosing-if rule (the else binds to the inner if). Most parser generators resolve the shift/reduce conflict by preferring shift — which happens to implement nearest-enclosing. The grammar is still technically ambiguous; the conflict-resolution rule patches it.

Real-world fix: use explicit endif (Ada, Pascal) or braces (Rust requires {}), eliminating the ambiguity at the grammar level.

Writing a separate nonterminal per precedence level is tedious for languages with 15 levels (C has exactly 15). The Pratt parser (top-down operator precedence) is an elegant alternative: each token carries a binding power integer, and a small loop drives the entire expression parser.

def parse_expr(tokens, min_bp=0):
    left = parse_atom(tokens)
    while True:
        op = tokens.peek()
        lbp = LEFT_BINDING_POWER.get(op.kind, -1)
        if lbp < min_bp:
            break
        tokens.consume()
        right = parse_expr(tokens, lbp + 1)  # +1 => left-assoc
        left = BinOpNode(op.kind, left, right)
    return left

Right-associativity (**, =): pass lbp instead of lbp + 1 as min_bp. Pratt parsers are used in Rust's parser and many modern language implementations precisely because they handle precedence tables directly, without grammar surgery.

A parser that crashes on the first error is useless. Production parsers implement error recovery so they can report multiple errors per file.

Common strategies:

• Panic mode: Discard tokens until a synchronization token is found (;, }, keyword). Simple, coarse.
• Error productions: Add grammar rules like stmt ::= ERROR SEMI that explicitly match known malformed constructs.
• Automatic recovery (ANTLR4): The parser inserts a missing token or deletes an unexpected one and continues — emitting an error message but pushing on.

Clang's recursive-descent parser uses synchronization sets: each parsing function knows which tokens could plausibly start a valid continuation. It skips everything else, re-establishes context, and tries again. Getting error recovery right is what separates a research parser from a production one.