AtlasLangimplementation

AtlasLang: The Parser

Recursive descent for statements and Pratt parsing for expressions, in one file, so you can read the two techniques next to each other — plus panic-mode recovery that synchronizes on `;` and statement keywords instead of stopping at the first error.

The question

How does AtlasLang turn a flat token list into a tree, and how does it keep going after a syntax error?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

An abstract syntax tree whose nodes carry the source span of the tokens they were built from, plus a list of diagnostics with a cascading flag. The tree answers what is applied to what — grouping, precedence, nesting — and answers nothing about meaning: whether a name exists, whether the operand types agree, whether the program does anything sensible. Keeping that line sharp is why the tree can be built from a file full of type errors.

What this phase may assume or do

The parser may assume the lexer's guarantees — a finite token list ending in a zero-width EOF, with every span slicing back to its text — and it owes two of its own. It must always terminate: every loop that calls a statement parser checks that the position advanced and forces it if not, because a recovering parser that consumes nothing on a malformed token spins forever. And it must not check meaning: a tree whose names do not resolve is a valid parse, because rejecting it here would move a semantic decision into a phase that cannot report it well.

Key points

  • Statements use recursive descent, so the call stack is the derivation; expressions use Pratt parsing, so precedence is a table rather than a tower of functions.
  • The binding-power table is the only place AtlasLang's precedence exists — there is no grammar file it is derived from.
  • Associativity is expressed as an inequality: right > left is left-associative, and reversing it changes what 1 - 2 - 3 means.
  • Unary operators bind at 13, tighter than every binary operator, expressed by calling the expression parser back with that minimum.
  • The parser builds structure and checks no meaning, so a file full of type errors still produces a tree.
  • Panic-mode recovery synchronizes on ; and statement keywords, and diagnostics raised before resynchronizing are flagged as cascading rather than presented as equals.
  • Every recovery loop forces forward progress, because a parser that consumes nothing on a malformed token hangs instead of erroring.

Two techniques, deliberately

Statements are parsed by recursive descent. There is a function per production — parseStmt, parseBlock, parseFn, parseType — and the call stack *is* the derivation. Reading parseStmt is reading the statement grammar, because a switch on the leading token dispatches to the production that token begins.

Expressions are parsed by a Pratt parser: one loop, one table of binding powers. The reason for the split is that precedence handled by recursive descent forces a tower of functions — parseExpression calls parseComparison calls parseTerm calls parseFactor — one layer per precedence level, and adding an operator means adding a layer and rewiring the ones around it. In the Pratt formulation, adding an operator is one row in a table.

The two live in the same file on purpose. They are the two techniques this domain teaches for hand-written parsers, and seeing them a hundred lines apart, over the same token stream, makes the difference concrete in a way that two separate examples cannot.

The binding-power table is the precedence of the language

implementationThe numbers themselves are arbitrary — only the ordering matters, and the gaps exist so a level can be inserted between two others without renumbering. Real languages differ on this table in ways that matter: C famously binds the bitwise operators looser than comparison, so a & b == c means a & (b == c), a decision widely regarded as a mistake and now impossible to change. AtlasLang has no bitwise operators, so it does not have to have an opinion.

Here is the whole of AtlasLang's expression precedence. Higher numbers bind tighter. There is no other source of truth — no grammar file, no comment, no convention. 1 + 2 * 3 groups as 1 + (2 * 3) for exactly one reason: * appears in this table with higher numbers than +.

Both a left and a right binding power are given for every operator, and the gap between them expresses associativity. A left-associative operator has right > left. Walk it through: parsing 1 - 2 - 3, the loop sees - with left power 9, which is at least the current minimum of 0, so it consumes the operator and parses the right-hand side with a minimum of 10. Inside that call, the next - has left power 9, which is less than 10, so the recursion stops immediately and returns just 2. Control returns to the outer loop, which builds (1 - 2) and then sees the second - again — producing ((1 - 2) - 3). Left-associative, from one inequality.

Flip it — make right < left — and the same loop produces (1 - (2 - 3)), which is right-associative and gives a different answer. That is a two-character change with a semantic consequence, and it is why [[associativity]] is a grammar property rather than an implementation detail.

Unary operators are separate. - and ! are prefix-only and bind at 13, tighter than every binary operator, so -a * b parses as (-a) * b. The unary parser calls the expression parser back with a minimum of 13, which is exactly how "binds tighter than anything below" is expressed in this scheme.

BINDING from src/compilers/sim/parser.tsimplementation
OperatorLeftRightReading
||12Loosest. Left-associative because right > left.
&&34Binds tighter than ||, so a || b && c is a || (b && c).
== !=56Tighter than the logical operators, so comparisons can be combined without parentheses.
< <= > >=78Tighter than equality. a < b == c < d groups the comparisons first.
+ -910Ordinary additive precedence.
* / %1112Tightest binary level. This row is why 1 + 2 * 3 is 7.
unary - !—13Prefix only, tighter than every binary operator.

What the tree does and does not say

The tree below is print(1 + 2 * 3); as this parser builds it. The multiplication sits *underneath* the addition, which is the precedence decision made structural — and it is the only place that decision now exists, because the token stream did not record it and the source text does not encode it.

Every node carries a span. A Binary node takes its start from its left operand and its end from its right, so the span of 2 * 3 is exactly the characters 2 * 3 and the span of 1 + 2 * 3 is exactly those. That is what makes the pipeline explorer able to highlight the source when you click a node, and what will make a type error on this expression underline the right text.

Notice what is absent. There is no node for the parentheses of print(...), none for the ;, and none for the grammar rules traversed on the way down. This is an AST, not a parse tree — see [[parse-tree-vs-ast]]. And there are no types and no resolved symbols: those fields exist on the node type and are undefined until the checker fills them in, which is the subject of [[atlaslang-types]].

The AST for print(1 + 2 * 3);, with real spans
AST — only what later phases match on
Print“print(1 + 2 * 3);”— A statement node. Its span covers the whole statement including the semicolon.
└── Binary +“1 + 2 * 3”— The addition is the root of the expression because `+` binds looser.
├── Number 1“1”
└── Binary *“2 * 3”— Underneath the addition — that is precedence, made structural.
├── Number 2“2”
└── Number 3“3”

Read it asDelete the * row from the binding table and this tree becomes (1 + 2) * 3 with no error anywhere: it still parses, still type-checks and still runs, and it prints 9 instead of 7. That is the hardest class of compiler bug — no diagnostic, no crash, just a different number — and it is why the precedence table gets its own tests.

Panic-mode recovery

A parser that stops at the first syntax error makes its user recompile once per typo. This one reports and continues, using panic-mode recovery: on an error, record a diagnostic, then skip tokens until reaching something that plausibly begins a new statement, and resume there.

The synchronization set is small and specific: LET, FN, IF, WHILE, RETURN, PRINT, RBRACE, EOF — plus the rule that recovery also stops immediately after a semicolon has just been consumed. That combination is chosen because those are the positions where the parser can be confident about what it is looking at. Land anywhere else and the next diagnostic is likely to be an artefact of the first.

Cascading errors are handled rather than ignored. The parser tracks whether it is in a panicking state — between reporting an error and successfully synchronizing — and marks any diagnostic raised during that window with a cascading flag. The message is still recorded, so a UI can offer to show it, but it is not what the user is told to fix. This matters more than it sounds: a single missing brace can otherwise generate dozens of confident, wrong messages, and burying the real one is worse than not reporting the others.

Two termination guards keep it honest. parseBlock and the top-level loop both record the position before parsing a statement and force an advance if nothing was consumed — otherwise a malformed token that no production accepts would be re-attempted forever. And parsePrefix, when it cannot find an expression, reports and returns a placeholder node rather than throwing, so the statement parser can finish the statement and recovery can continue from a known point.

  • Report, do not throw. Every error path returns something usable — a placeholder expression, an <error> name, a block that ends where the parser gave up.
  • Synchronize on statement starters. ; and the six statement keywords, plus } and end of input. Those are the positions where the parser knows where it is.
  • Flag cascades. Diagnostics raised while still panicking are marked, so the first real error stays visible.
  • Guarantee progress. Every recovery loop checks that the position advanced and forces it if not.
  • Say what was found. Messages are "Expected ; after a let binding" with the help "Found an identifier instead" — naming both halves, because either alone leaves the user guessing.

How it works

The steps, in the order the compiler takes them.

  • parseExpr(minBinding) parses a prefix expression, then loops while the next token has a left binding power of at least minBinding.
  • On each iteration it consumes the operator and recurses with the operator's *right* binding power, which is what makes right > left produce left-associativity.
  • parsePrefix handles literals, parenthesised expressions, identifiers, calls and the two unary operators, and returns a placeholder on failure rather than throwing.
  • parseStmt switches on the leading token to dispatch to the production it begins, and uses one token of lookahead to separate an assignment from a bare expression statement.
  • expect(kind, context) consumes a token or reports "Expected X ... Found Y instead", returning null so the caller can continue with what it has.
  • On error the parser sets a panicking flag; synchronize then skips tokens until a statement keyword, a closing brace, end of input, or the token after a semicolon.
  • Diagnostics raised while panicking are marked cascading, so a UI can rank the first real error above its consequences.
  • Function declarations are collected at the top level before statements, and every loop that parses statements forces an advance if the position did not change.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • Two operators given the same binding numbers as each other by accident, and an expression groups in a way that produces a wrong answer with no diagnostic anywhere.
  • Associativity reversed by writing right < left for a subtractive operator, and 10 - 3 - 2 evaluates to 9 instead of 5 — arithmetic that is wrong and looks fine.
  • A recovery loop that does not force progress, and a single stray character makes the compiler hang rather than report anything.
  • A synchronization set that is too permissive, so the parser resumes in the middle of an expression and produces a page of cascading nonsense above the real error.
  • A Binary node built with the operator token's span instead of left.start to right.end, and every type error on an expression underlines just the operator.
  • A parser that checks names or types, so a program with one undefined variable produces syntax errors, and the user is told the wrong thing about the wrong phase.

When it helps

  • Writing a parser by hand for a real language, where recursive descent plus Pratt is the combination most production frontends actually use.
  • Adding an operator to an existing language, where the Pratt formulation makes it a table entry and the recursive-descent formulation makes it a refactor.
  • Diagnosing "the program compiles and returns the wrong number", where an incorrect precedence or associativity table is a prime suspect and is easy to check.
  • Improving a compiler's error messages, where the recovery strategy and the cascade flag matter far more than the wording of any individual message.

When it hurts

  • For grammars that are genuinely ambiguous or require unbounded lookahead, where an LR-family parser or a GLR parser is the right tool — see [[ll-vs-lr]].
  • When the grammar changes constantly and correctness of the grammar itself is the risk, where a generator that reports conflicts is worth its costs — [[parser-generators]].
  • For tooling that needs a lossless tree with whitespace and comments preserved, which this parser does not produce.

What it costs

Every one of these is paid by something.

  • Pratt parsing buys precedence as data and pays with a mechanism that is less obvious to read than a function-per-level tower — the two binding numbers need explaining before the loop makes sense.
  • Recursive descent for statements buys code that reads like the grammar and pays by making left-recursive productions impossible to write directly, which constrains how the grammar can be phrased.
  • Panic-mode recovery buys multiple errors per compile and pays with cascading diagnostics that have to be detected and demoted, plus a synchronization set that is a judgement call.
  • Returning placeholder nodes instead of throwing buys a usable tree from a broken file and pays by letting later phases see nodes that do not correspond to anything the user wrote.
  • Refusing to check meaning buys clean phase separation and testability and pays with a parser that accepts programs everyone knows are wrong, deferring the complaint to a phase that has not run yet.

What else you could do

What a different compiler or language does instead, and when that is better.

  • A parser generator producing an LALR table would report grammar ambiguities as conflicts rather than silently resolving them, at the cost of worse error messages and a generated file nobody reads — [[parser-generators]].
  • A pure recursive-descent expression parser with one function per precedence level, which is more obvious and much more tedious to extend — [[recursive-descent]].
  • Precedence climbing, which is essentially Pratt parsing with a single binding power plus an associativity flag: equivalent power, arguably clearer, one more field per operator.
  • A shift-reduce parser driven by an explicit operator-precedence table, which is what many older compilers used and which makes the same information available in the same way — [[shift-reduce]].
  • Error recovery by insertion or deletion rather than by synchronization: guess the missing token and continue, which produces better messages for common typos and can also produce confident nonsense.

See it for yourself

The flag, dump or tool that shows you this directly.

  • /compilers/pipeline — the AST panel is this parser's output, and clicking a node highlights its span in the source.
  • Type print(1 + 2 * 3); and then print((1 + 2) * 3); and compare the trees and the printed values — 7 against 9.
  • Load the errors example to see recovery working across a lexer error, a parse error and a type error in one file.
  • Type let a = 1 with no semicolon, then more statements after it, and watch which diagnostics are marked cascading.
  • src/compilers/sim/parser.ts — the BINDING table is at the top and is about fifteen lines.
  • For comparison: clang -Xclang -ast-dump file.c prints a C AST, and python -c "import ast,sys;print(ast.dump(ast.parse(open(sys.argv[1]).read())))" prints a Python one.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Precedence comes from the grammar." In this parser it comes from a table of integers. In a generated LR parser it comes from precedence declarations. Either way it is data somebody wrote, not a property of arithmetic.
  • "The parser rejects invalid programs." It rejects programs with invalid *structure*. let x: bool = 5; parses perfectly and is rejected two phases later.
  • "Panic-mode recovery means the parser guesses what you meant." It means it skips to a place it can be confident about and resumes. It guesses nothing; that is why the synchronization set is so small.
  • "Extra errors after the first are the parser being thorough." They are usually artefacts, which is exactly why they are flagged as cascading rather than presented alongside the real one.

Misconceptions

The claim, and what is actually true.

Pratt parsing is a different kind of parser from recursive descent.
It is recursive descent for expressions with the precedence levels replaced by a numeric parameter. The same call stack, the same technique, with the tower of functions collapsed into a loop.
A parse error means the file is unparseable.
It means one construct was. Recovery exists precisely so the rest of the file is still parsed and its errors are still found.
Reporting more errors is better.
Reporting more *independent* errors is better. Reporting a cascade from one missing brace makes the real error harder to find, which is why they are tracked and demoted.
The AST is what the grammar describes.
The grammar describes a parse tree containing every rule and token. The AST keeps only what later phases match on, which is why there is no node for the semicolon.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The parser turns a flat list of tokens into a tree. Statements are handled by a function per kind of statement, so the code reads like the grammar. Expressions are handled by a loop plus a table saying how tightly each operator binds, which is what makes 1 + 2 * 3 group the multiplication first. When it hits something it cannot parse, it reports the problem, skips to the next statement and keeps going.

practical

If you are writing a parser, use recursive descent for statements and Pratt for expressions — it is what most production frontends do and it is the combination that stays readable as the language grows. Give the precedence table its own tests, because a mistake in it produces wrong answers with no diagnostic. Make every recovery loop check that the position advanced. And spend the effort on the synchronization set rather than on message wording: recovering to a bad position produces a page of confident nonsense that no amount of good phrasing rescues.

advanced

The two binding numbers per operator are worth understanding as a general encoding rather than a trick. minBinding is a claim about the context: "I will only consume operators that bind at least this tightly." Passing the operator's *right* power into the recursion sets the context for the right operand, so the gap between an operator's left and right power decides whether an operator of the same precedence may be consumed by the inner call or must be left for the outer one — which is exactly what associativity is. The scheme extends without new machinery: a ternary conditional is a prefix-and-infix operator with a low right power, a postfix operator has only a left power, and a right-associative assignment is the same table with the inequality flipped. That generality is why Pratt parsing survives contact with real languages, where a function-per-level tower has to be restructured every time a level is inserted.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationThe binding numbers, the synchronization set and the cascade flag are AtlasLang's, in src/compilers/sim/parser.ts at this revision. Other hand-written parsers pick different numbers and different recovery strategies, and generated parsers express the same information as precedence declarations that the generator turns into table entries. The technique transfers; the table does not.
simplifiedAtlasLang's grammar is deliberately easy to parse: no left recursion, no ambiguity requiring more than two tokens of lookahead, no user-defined operators, no context-dependent tokens. Real languages have all of these — C's declaration-versus-expression ambiguity, C++'s most vexing parse, JavaScript's automatic semicolon insertion — and each one costs a production parser far more than the whole of this file.
specPrecedence and associativity are choices a language specification makes and then cannot revise. C's decision to bind & and | looser than == is widely considered a mistake and is permanent, because changing it would silently alter the meaning of existing correct programs. This is one of the few decisions in a language that is genuinely irreversible.

If you were asked this in an interview

  • Why does giving an operator a right binding power greater than its left power make it left-associative?
  • What is in this parser's synchronization set, and what goes wrong if you make that set larger?
  • Where does AtlasLang's operator precedence live, and how would you test that it is right?

Connections

DSArecursionbinary-treestack
Domains that do not exist yet
  • Testing & Reliability Engineering — Round-trip and differential testing of a parser against generated inputs
    The precedence table is the part of this parser whose bugs produce no diagnostic, so it needs testing that does not rely on examples someone thought of — generate expressions, evaluate the tree, compare against an independent evaluator. The general technique belongs there; the reason this parser needs it is here.