Parsing & ASTs: Structure Over Text

Parse(tokens) returns one expression tree and an error. The provided Expr represents numbers, identifiers, unary expressions, binary expressions, and named calls. It has no Grouping node or source-span fields. Parentheses control shape then disappear from the AST. A richer compiler may retain spans, but adding fields is not required by this task.

Grammar into control flow

Use the precedence chain equality → comparison → term → factor → unary → primary. Each binary level parses one tighter expression, then loops over its own operators. Repeated subtraction is left associative because each iteration wraps the prior tree as the new left child. Unary parsing recurses at the same level, allowing !!x and --2.

Worked reconstruction

For 18 - 6 / 3 - 1:

1. The first term begins with number 18.
2. It sees -; factor consumes the whole 6 / 3, producing Div(6,3).
3. Term builds Sub(18,Div(6,3)).
4. The next - wraps that tree: Sub(Sub(18,Div(6,3)),1).
5. EOF confirms there is no second unparsed expression.

The hand result is 15. A right-recursive subtraction chain would produce 18-(2-1)=17, so this input distinguishes associativity. 18-(6/3-1) explicitly requests that latter tree; parentheses delegate to the full expression parser and then require a closing token.

A call is IDENT(args) here: ExprCall.Value stores the name and Args retains source order. f(2,3) works; general f()(2) is a v3 feature. Parsing neither resolves f nor runs it.

Failure boundary

Fail on the first missing delimiter, missing operand, or extra token. This API returns one error, not a recovered sequence of diagnostics. Error recovery at semicolons is a useful later design exercise, not part of this expression parser. Compare this representation with the LLVM parser/AST tutorial, which also separates tree construction from execution but uses its own grammar.

Debugging lab

A parser accepts 2 3 and returns Number(2). Another parser handles 8-3-1 as 8-(3-1). Which invariant is violated in each case?

Compare your diagnosis after attempting the lab

The first forgot the final EOF check. The second recursed over the whole remaining term instead of looping over same-precedence operators. Full consumption and associativity are independent obligations.

Transfer task

Draw ASTs for f(4,2+1)*3, -(4+2)*3, and 9/3/3. Predict which recursive function owns each delimiter. Then make one token invalid and locate the earliest failing parser call.

Carry forward

Carry exact AST shape and argument order into lowering. Save a noncommutative example so a later stack-order bug cannot hide behind addition.

Build expr-parser. Keep a before/after trace of one failing test. Use the checkpoint to diagnose specific skills; passing it does not replace implementing and testing the artifact.