Parsing & ASTs: Structure Over Text

Construct ASTs from precedence and associativity.
Track token consumption across recursive parser calls.
Reject extra tokens without inventing later postfix syntax.

1 / 6

Readiness

Trace tiny-lexer tokens and EOF.
Distinguish a binary node from its two operands.

2 / 6

Worked reconstruction

For 18 - 6 / 3 - 1:

The first term begins with number 18.
It sees -; factor consumes the whole 6 / 3, producing Div(6,3).
Term builds Sub(18,Div(6,3)).
The next - wraps that tree: Sub(Sub(18,Div(6,3)),1).
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.

3 / 6

Diagnose before implementing

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?

4 / 6

Independent transfer

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.

5 / 6

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.

6 / 6