Grammars and Parsing

A grammar is the rulebook for sentence structure: "a declaration is let, a name, =, an expression and ;".

Learning Objectives

Read grammars: terminals, non-terminals, productions and EBNF; encode precedence and associativity; recognise ambiguity.

Implement recursive-descent and Pratt (precedence-climbing) parsers; compare LL, LR and parser combinators.

Build ASTs (not parse trees) for expressions, statements, blocks and functions, with source spans.

Report errors and recover with panic mode and synchronisation tokens; test and fuzz parsers; understand incremental parsing.

Plain-Language Explanation

A grammar is the rulebook for sentence structure: "a declaration is let, a name, =, an expression and ;". A parser reads tokens and checks they follow the rules, building a tree that shows how the pieces nest — for example that in 1 + 2 * 3 the multiplication happens first. When it finds a mistake it reports it, skips ahead to a safe point, and keeps looking for more mistakes.

Precise Technical Explanation

Grammar, terminals, non-terminals, productions A context-free grammar has terminals (tokens such as "let" or NUMBER), non-terminals (named rules such as expression) and productions that rewrite a non-terminal into a sequence of terminals and non-terminals. A program is valid if the start symbol (program) can derive its token sequence.

Extended Backus–Naur Form adds repetition { … }, optional [ … ] and grouping ( … ). Conventions vary (ISO EBNF uses , for concatenation and ; to end rules, as in this course; other styles use *, ? and |).

Here "let" and ";" are terminals; { … } means zero or more; precedence is encoded by layering — term (multiplication) sits *below* expression (addition), so multiplication binds tighter.

Precedence and associativity Precedence decides which operator groups first (* before +); associativity decides grouping among equal operators: left-associative 10 - 4 - 3 = (10 - 4) - 3 = 3; right-associative assignment a = b = c = a = (b = c). In a layered grammar, a loop term { "+" term } produces left associativity; a recursive rule assignment = IDENTIFIER "=" assignment produces right associativity.

expr = expr "+" expr | expr "*" expr | NUMBER allows two trees for 1 + 2 * 3. Fix ambiguity by layering (as above) or by declaring precedence to a parser generator. The classic "dangling else" is resolved by attaching else to the nearest if.

One function per non-terminal; each function consumes tokens and calls the functions for sub-rules. MiniLang's parser (expression → assignment → or → … → primary) is recursive descent: easy to write, excellent error messages, and the approach used by GCC, Clang, V8, Roslyn and CPython's earlier hand-written parts.

Pratt parsing / precedence climbing Assign each operator a binding power; parse a prefix expression, then loop while the next operator binds more tightly than the current minimum, recursing with the operator's power. Adds operators by table entry instead of new functions.

LL and LR parsing overview LL(k) parsers read left to right and build the tree top-down, choosing productions with k tokens of look-ahead (recursive descent is hand-written LL). LR parsers (LALR, used by yacc/bison) build bottom-up by shifting tokens and reducing them by productions, handling left-recursive grammars directly. CPython ≥ 3.9 uses a PEG parser generator (ordered choice with memoisation).

Parser combinators overview Parsers built as values from smaller parsers with combinators (sequence, choice, many) — common in functional languages; convenient for small grammars, and needing care for performance and error messages.

Parse trees versus ASTs A parse tree (concrete syntax tree) contains every token and every grammar rule, including parentheses and single-child chains (expression → term → factor → number). An AST keeps only meaningful structure. Formatters and refactoring tools keep concrete trees (with comments and whitespace); compilers use ASTs.

Expression parsing is where precedence, associativity, unary operators and calls meet; MiniLang's chain is assignment → or → and → equality → comparison → term → factor → unary → call → primary.

Statements and declarations Statements start with a keyword (print, if, while, return, {) or are expression statements; declarations (let, fun) introduce names. Separating them lets a language forbid declarations where they make no sense.

Blocks and nested syntax block = "{" { declaration } "}" nests arbitrarily; the parser recurses, and the AST records the nesting that scopes are built from.

Function declaration syntax fun name(params) { body }: name, a comma-separated parameter list (with a limit — 255 in MiniLang, because bytecode operands are one byte), and a block body.

A good syntax error says what was expected, what was found and where: Syntax error [line 1:5]: Expect variable name. (found '=').

After an error, discard tokens until a point where parsing can safely resume, then continue — so one mistake does not hide others or produce cascades.

The resume points: after a ;, or before a keyword that starts a declaration or statement (let, fun, if, while, print, return, {).

Error productions and recovery trade-offs Some parsers add rules for common mistakes (if x { without parentheses) to give targeted messages. More recovery means better messages but more complexity and risk of misleading follow-up errors.

Source spans in AST nodes Every AST node records the span from its first to last token; diagnostics, debuggers, coverage tools and source maps rely on it.

Parser testing and fuzzing Golden tests (source → printed AST), precedence/associativity tables, error-message tests, round-trip tests (print the AST as source, re-parse, compare), and fuzzing — the parser must terminate with diagnostics on any input.

Incremental parsing overview Editors re-parse only changed regions, reusing unchanged subtrees (tree-sitter, Roslyn's red-green trees), to stay responsive on every keystroke.

program     = { declaration } ;
declaration = "let", identifier, "=", expression, ";" ;
expression  = term, { ("+" | "-"), term } ;
term        = factor, { ("*" | "/"), factor } ;
factor      = number | identifier | "(", expression, ")" ;

Why It Matters in Real Systems

Parsers sit on every input path — compilers, config loaders, query engines, protocol handlers. Correct precedence prevents silent miscalculation; robust recovery makes errors usable; fuzzing prevents crashes on hostile input.

Key Terms

A grammar rule rewriting a non-terminal Precedence / associativity

Which operator groups first / how equal operators group One function per grammar rule Precedence-driven expression parser

Skip to a synchronisation token after an error

Syntax or Instruction Format

MiniLang's full grammar is in the course overview. The expression layer, from lowest to highest precedence:

expression = assignment ;
assignment = IDENTIFIER, "=", assignment | logic_or ;
logic_or   = logic_and, { "or", logic_and } ;
logic_and  = equality, { "and", equality } ;
equality   = comparison, { ( "==" | "!=" ), comparison } ;
comparison = term, { ( ">" | ">=" | "<" | "<=" ), term } ;
term       = factor, { ( "+" | "-" ), factor } ;
factor     = unary, { ( "*" | "/" ), unary } ;
unary      = ( "!" | "-" ), unary | call ;

Complete Example

Precedence and associativity in MiniLang's real ASTs:

Output (MiniLang reference implementation):

Panic-mode recovery reports three independent errors in one pass and still parses the valid declaration:

A complete Pratt parser in Python producing the same shapes (CPython 3.13.1):

1 + 2 * 3;
10 - 4 - 3;
a = b = 5;
-x * 2;

ExprStmt
└── Binary(+)
    ├── Number(1)
    └── Binary(*)
        ├── Number(2)
        └── Number(3)
ExprStmt
└── Binary(-)
    ├── Binary(-)
    │   ├── Number(10)
    │   └── Number(4)
    └── Number(3)
ExprStmt
└── Assign(a)
    └── Assign(b)
        └── Number(5)
ExprStmt
└── Binary(*)
    ├── Unary(-)
    │   └── Variable(x)
    └── Number(2)

let = 3;
print(1 + );
let ok = 2;
print(ok)

Let(ok)
└── Number(2)
Syntax error [line 1:5]: Expect variable name. (found '=')
Syntax error [line 2:11]: Expect expression. (found ')')
Syntax error [line 5:1]: Expect ';' after print statement. (found end of input)

import re

BINDING = {"+": 10, "-": 10, "*": 20, "/": 20}          # higher binds tighter


def tokens(src):
    return re.findall(r"\d+|[A-Za-z_]\w*|[-+*/()]", src) + ["<eof>"]


class Parser:
    def __init__(self, src):
        self.toks, self.i = tokens(src), 0

    def next(self):
        tok = self.toks[self.i]
        self.i += 1
        return tok

    def peek(self):
        return self.toks[self.i]

    def expression(self, min_power=0):
        tok = self.next()
        if tok == "(":                                   # prefix: parenthesised expression
            left = self.expression()
            if self.next() != ")":
                raise SyntaxError("expected ')'")
        elif tok == "-":                                 # prefix: unary minus binds tighter than * and /
            left = ("neg", self.expression(30))
        elif tok.isdigit() or tok[0].isalpha():
            left = tok
        else:
            raise SyntaxError(f"unexpected {tok!r}")
        while self.peek() in BINDING and BINDING[self.peek()] > min_power:
            op = self.next()
            right = self.expression(BINDING[op])         # same power → left-associative
            left = (op,
…

1 + 2 * 3    → ('+', '1', ('*', '2', '3'))
10 - 4 - 3   → ('-', ('-', '10', '4'), '3')
(1 + 2) * 3  → ('*', ('+', '1', '2'), '3')
-x * 2       → ('*', ('neg', 'x'), '2')
1 + * 2      → SyntaxError: unexpected '*'

Line-by-Line Explanation

1 + 2 * 3: Binary(*) is the right child of Binary(+) — multiplication groups first.

10 - 4 - 3: the left child is Binary(-) — left associativity.

a = b = 5: Assign(a) contains Assign(b) — right associativity.

Recovery: after "Expect variable name" the parser skips to the ;, parses the next statement, reports the missing operand, recovers again, parses let ok = 2;, and finally reports the missing ; at end of input.

Pratt: expression(min_power) keeps consuming operators that bind more tightly than min_power; recursing with the operator's own power makes equal operators group to the left.

Step-by-Step Runtime Behavior

For 1 + 2 * 3, the Pratt loop reads 1, sees + (10 > 0) and parses the right side with minimum 10; inside, it reads 2, sees * (20 > 10) and builds (* 2 3); back outside, it builds (+ 1 (* 2 3)).

Common Misconceptions

"Parentheses appear in the AST." They only shape it (MiniLang keeps a Grouping node for spans and printing; many ASTs drop it).

"A grammar that accepts the right programs is enough." It must also produce the right trees.

"Recursive descent cannot handle left recursion." It cannot handle *left-recursive rules* directly — rewrite them as loops, as MiniLang does.

Common Bugs and Failure Modes

Wrong associativity (recursive instead of looping rules), unary minus with the wrong precedence, infinite recursion on left-recursive rules, error cascades, losing spans, stack overflow on deeply nested input.

Corrected or Safer Patterns

Encode associativity deliberately; test a precedence table; synchronise after errors; limit nesting depth for untrusted input.

Debugging and Inspection Techniques

Print ASTs (the course's AST explorer, Python's ast.dump), trace which rule handles each token, and keep a corpus of tricky inputs.

Performance Considerations

Recursive descent and Pratt parsers are linear time for practical grammars; PEG parsers memoise to avoid exponential backtracking.

Security Considerations

Deep nesting can overflow the native stack of a recursive parser (((((…))))); limit depth or use an explicit stack. Parsers of untrusted input (JSON, YAML, XML) need size and depth limits.

Portability and Version Caveats

Grammars evolve: Python's match statement uses soft keywords, which the PEG parser made practical; JavaScript's automatic semicolon insertion makes its grammar context-sensitive.

Real-World Use Cases

Compilers, linters, formatters, query languages, template engines, data-format parsers, language servers.

Best Practices

Write the grammar first, keep one parse function per rule, keep spans, recover from errors, fuzz.

Exercises

E1 · Beginner. Draw the AST for 2 * (3 + 4).

Answer: Binary(*) with children Number(2) and Grouping → Binary(+) with Number(3) and Number(4).

E2 · Intermediate. Add an exponent operator ^ (right-associative, binding tighter than *) to the Pratt parser.

Answer: Add "^": 30 to BINDING (and raise unary minus to 40 if -2^2 should be -(2^2)); in the loop, recurse with BINDING[op] - 1 for ^ so an equal operator on the right binds first: 2^3^2 → (^ 2 (^ 3 2)).

E3 · Advanced challenge. Why does panic mode synchronise on ; *after* consuming it, but on keywords *before* consuming them?

Answer: A ; ends the broken statement, so parsing resumes after it; a keyword starts the next statement, so the parser must not consume it — it is the first token of the statement to parse next.

Quiz

? In MiniLang, how does `10 - 4 - 3` group?
+ (10 - 4) - 3 :: Binary operators are left-associative.
- 10 - (4 - 3) :: That would give 9 instead of 3.
- It is a syntax error. :: It is valid.
- It depends on the VM. :: Grouping is decided by the parser.

? What is a synchronization token used for?
+ Resuming parsing after a syntax error. :: Panic-mode recovery skips to one.
- Marking the end of the file. :: That is EOF.
- Separating threads. :: Unrelated.
- Starting a comment. :: Comments are removed by the lexer.

? Which are differences between parse trees and ASTs? (select all that apply)
+ Parse trees include every token, such as parentheses and semicolons. :: Concrete syntax.
+ ASTs omit single-child rule chains. :: They keep only meaningful structure.
- ASTs cannot have source positions. :: They should record spans.
+ Formatters often keep concrete syntax (including comments). :: They must reproduce the source.

Summary and Key Takeaways

Grammars define structure; layering encodes precedence and loops-versus-recursion encode associativity. Recursive descent and Pratt parsing turn tokens into ASTs with spans, report precise errors, recover in panic mode, and must be tested and fuzzed.