Syntax Analysis
(Parsing)

Parsing is the heart of the front end. We start from context-free grammars, contrast the two great parsing families, and finish at the AST that the rest of the compiler consumes.

The lexer (Part 03) handed us a flat stream of tokens. The parser checks that those tokens form a valid sentence of the source language's grammar and, in the process, recovers the structure the flat stream lost — nesting, grouping, precedence.

The lexer/parser split mirrors the Chomsky hierarchy: regular languages for tokens, context-free languages for phrase structure. Anything beyond — declared-before-use, type agreement — is left to semantic analysis (Part 05).

A CFG is a 4-tuple G = (N, Σ, P, S): non-terminals N, terminals Σ, productions P, and a distinguished start symbol S. Each production rewrites one non-terminal into a string of terminals and non-terminals.

Expr   → Expr "+" Term
       | Expr "-" Term
       | Term
Term   → Term "*" Factor
       | Term "/" Factor
       | Factor
Factor → "(" Expr ")"
       | number
       | ident

A derivation applies productions step by step, each rewriting one non-terminal, until only terminals remain. Each intermediate string is a sentential form; one with no non-terminals left is a sentence.

Expr
⇒ Expr + Term         (Expr→Expr+Term)
⇒ Term + Term         (Expr→Term)
⇒ Factor + Term       (Term→Factor)
⇒ a + Term            (Factor→ident)
⇒ a + Term * Factor   (Term→Term*Factor)
⇒ a + Factor * Factor
⇒ a + b * Factor
⇒ a + b * c

The parse tree (concrete syntax tree) records every grammar symbol used — including chains like Term→Factor and the parentheses. The AST (abstract syntax tree) keeps only the essential structure. Same input a + b * c:

Eleven nodes collapse to five. The AST drops single-child chains and punctuation; * sits below +, so precedence survives as shape.

A grammar is ambiguous if some sentence has more than one parse tree (equivalently, more than one leftmost derivation). Ambiguity means the structure — and therefore the meaning — is undefined.

E → E "+" E
  | E "*" E
  | number

S → "if" E "then" S "else" S
  | "if" E "then" S
  | other

Some ambiguity is inherent — no equivalent unambiguous grammar exists — but the cases compilers meet are almost always fixable.

The cure for the ambiguous expression grammar is to stratify it into one non-terminal per precedence level. Higher precedence sits lower in the grammar (closer to the leaves), so it binds tighter.

Expr   → Expr "+" Term  | Term      // + is left-assoc,
Term   → Term "*" Factor | Factor   //   lowest precedence
Factor → "-" Factor                  // unary minus
       | Power
Power  → Atom "^" Power | Atom       // ^ is RIGHT-assoc
Atom   → number | "(" Expr ")"

Not every CFG can be parsed deterministically with bounded lookahead. The parsing classes form a containment hierarchy — each is the set of grammars a given method can handle. Bigger means more grammars accepted.

Note: LL and LR are incomparable in general for arbitrary k — the clean chain above is the practical k=1 picture. ANTLR's ALL(*) and GLR sit outside it, trading determinism for power.

Each class trades grammar generality against implementation simplicity and error quality. The dominant production choice is hand-written recursive descent (an LL flavour) or LALR(1) via a generator.

The most direct parser: one function per non-terminal. The call stack is the parse stack; the grammar reads straight off the code. This is how GCC, Clang and most hand-written parsers work.

// Expr → Term (('+'|'-') Term)*
Node *parse_expr(Parser *p) {
    Node *lhs = parse_term(p);
    while (peek(p) == '+' || peek(p) == '-') {
        Tok op = advance(p);          // consume operator
        Node *rhs = parse_term(p);
        lhs = mk_binary(op, lhs, rhs); // build AST node
    }
    return lhs;
}

// Factor → number | '(' Expr ')'
Node *parse_factor(Parser *p) {
    if (peek(p) == '(') {
        expect(p, '(');
        Node *e = parse_expr(p);
        expect(p, ')');               // error if missing
        return e;
    }
    return mk_num(expect(p, NUMBER));
}

To decide which production to take from one lookahead, a predictive parser precomputes two sets. FIRST(α) = terminals that can begin a string derived from α. FOLLOW(A) = terminals that can appear immediately after A.

E  → T E'
E' → "+" T E' | ε
T  → F T'
T' → "*" F T' | ε
F  → "(" E ")" | id

For expressions, recursive descent needs a function per precedence level. Pratt parsing (Vaughan Pratt, 1973) collapses them into one loop driven by binding powers — the technique behind many real parsers (Go, Clang's expressions, rustc, Crafting Interpreters).

# binding power table: (left_bp, right_bp)
BP = {'+':(10,11), '-':(10,11),    # left-assoc
      '*':(20,21), '/':(20,21),
      '^':(31,30)}                  # right-assoc

def expr(p, min_bp=0):
    lhs = atom(p)                   # number / (expr) / unary
    while True:
        op = p.peek()
        if op not in BP: break
        lbp, rbp = BP[op]
        if lbp < min_bp: break      # stop: weaker than caller
        p.next()                    # consume operator
        rhs = expr(p, rbp)          # recurse with op's right bp
        lhs = ('binary', op, lhs, rhs)
    return lhs

Top-down parsers can't handle left-recursion (infinite loop) or common prefixes (can't choose with one token). Two mechanical transforms make a grammar LL-friendly while preserving the language.

// before  (left-recursive)
A → A α | β

// after   (right-recursive + ε)
A  → β A'
A' → α A' | ε

// concretely
Expr → Expr "+" Term | Term
   ⇓
Expr  → Term Expr'
Expr' → "+" Term Expr' | ε

// before  (common prefix — can't pick)
S → "if" E "then" S "else" S
  | "if" E "then" S

// after   (factor the shared prefix)
S  → "if" E "then" S S'
S' → "else" S | ε

Bottom-up parsers build the tree from the leaves up, tracing a rightmost derivation in reverse. They keep a stack and repeatedly choose between two moves: shift the next token onto the stack, or reduce a stack suffix matching a production's RHS back to its LHS.

How does the parser know when a handle is on the stack? It runs a DFA over grammar symbols. Each state is a set of LR(0) items — productions with a dot • marking how much has been seen. The dot at the end means “handle complete → reduce”.

LR(0) alone often hits states with both a shift and a reduce item and no way to choose. The three flavours differ in how much lookahead context they attach to reduce decisions.

The automaton is compiled into two tables. ACTION[state, terminal] → shift s, reduce r, accept, or error. GOTO[state, non-terminal] → the state to enter after a reduction. The driver is a tiny, fixed loop.

// Table-driven LR driver (the heart of yacc output)
for (;;) {
  State s = top(stack);
  Token a = peek();
  Action act = ACTION[s][a];
  switch (act.kind) {
    case SHIFT:                 // sN
      push(act.state);
      advance();
      break;
    case REDUCE:                // rN: A → β
      pop(|β| states);
      State t = top(stack);
      push(GOTO[t][A]);
      emit_ast_node(A);         // semantic action
      break;
    case ACCEPT: return root;
    case ERROR:  recover();     // see slide 21
  }
}

A conflict is a table cell with two actions — the grammar isn't in the class the generator targets. Every yacc/bison user meets these; resolving them is a craft.

state: S → if E then S • [• else …]
on 'else':  shift  → inner if   (usual)
            reduce → outer if

A → x •     (reduce A→x)
B → x •     (reduce B→x)   ← which?

You rarely write LR tables by hand. A generator reads a grammar with embedded semantic actions and emits the parser. The choice of tool fixes the grammar class, the error story, and the workflow.

A compiler that stops at the first error is useless. Good parsers recover — report the error, then resynchronise to keep finding more — without an avalanche of bogus follow-on errors.

The parser's real product is the AST. It's built on the fly by semantic actions — code attached to productions (or written inline in recursive descent) that constructs a node as each rule completes.

// A typical AST as a Rust enum (sum type)
enum Expr {
    Num(f64),
    Var(String),
    Unary  { op: UnOp,  rhs: Box<Expr> },
    Binary { op: BinOp, lhs: Box<Expr>, rhs: Box<Expr> },
    Call   { callee: String, args: Vec<Expr> },
}
enum Stmt {
    Let   { name: String, init: Expr },
    If    { cond: Expr, then: Box<Stmt>, els: Option<Box<Stmt>> },
    Block(Vec<Stmt>),
    Expr(Expr),
}

# bison semantic action ($$ = result, $1.. = children)
expr : expr '+' term  { $$ = mk_bin(ADD, $1, $3); }
     | term           { $$ = $1; }

Both produce the same AST; they differ in how they find it and in their engineering trade-offs. The industry has largely converged on hand-written recursive descent + Pratt for serious compilers, generators for everything else.