Parsing & ASTs: Structure Over Text

Why this module exists

Tokens are linear; grammar is hierarchical. Parsing converts the former into a typed tree that later stages can rely on.

That means:

• parser decides precedence and associativity
• analyzer/compiler can ignore operator ambiguity
• diagnostics happen early, with source locations

1) Grammar as executable specification

Use explicit precedence levels:

expr       -> equality

equality   -> comparison ( ("==" | "!=") comparison )*
comparison -> term ( ("<" | "<=" | ">" | ">=") term )*
term       -> factor ( ("+" | "-") factor )*
factor     -> unary ( ("*" | "/") unary )*
unary      -> ("!" | "-") unary | primary
primary    -> NUMBER | IDENT | "(" expr ")" | call
call       -> IDENT "(" args? ")"
args       -> expr ( "," expr )*

Each line maps to one recursive-descent function.

2) Left associativity and loops

1 - 2 - 3 must parse as (1 - 2) - 3, not 1 - (2 - 3).

Typical pattern:

• parse left side
• while matching same-precedence op
  • parse right side
  • create new binary node with prior left

This is where left associativity is encoded explicitly.

3) AST shape and invariants

Keep node kinds explicit:

• Number
• Ident
• Unary
• Binary
• Call
• Grouping

Useful invariants:

• every node has span metadata (start, end or line/column)
• binary nodes always have both children
• identifiers carry raw symbol name
• call nodes record explicit arg order

AST should be durable intermediate data, not a parser throwaway.

4) Parsing strategy choices

Recursive descent (this pack)

• direct mapping from grammar
• easy to inspect and test

Pratt parsing (advanced path)

• table-driven precedence
• flexible for many operators

Recursive descent remains best for learning because the behavior maps cleanly to grammar rules.

5) Error handling and recovery

At minimum:

• include expected token + got token
• include location
• return a usable diagnostic object

Recovery strategy:

1. emit parser error
2. skip tokens until a synchronization token (;, }, EOF)
3. continue parsing remaining constructs

This enables multiple errors in one run without false cascades.

6) What goes wrong in practice

Common parser defects:

• precedence inversions (1 + 2 * 3 becomes (1 + 2) * 3)
• associativity mistakes from recursion instead of loops
• missing span tracking
• malformed call argument counts
• no synchronization and one typo breaks all downstream parsing

Most bugs should be caught by AST snapshots and parser-only tests.

7) Practice checkpoints (almost solved)

1) Precedence

Input: 1 + 2 * 3
Expected AST: (+ 1 (* 2 3))

2) Left associativity

Input: 8 - 3 - 1
Expected AST: (- (- 8 3) 1)

3) Grouping

Input: (1 + 2) * 3
Expected AST: (* (group (+ 1 2)) 3)

4) Function calls

Input: f(1, a + 2)
Expected structure: callee f, args [1, (+ a 2)].

5) Error location

Input: 1 + should report missing primary near end of input.

6) Recovery

Input: 1 + ; 2 + 3 should recover and still parse the second addition.