What a Parser Actually Does

The lexer has already done real work. It decided that 12 is one number rather than two digits, that >= is one operator rather than two, that the run of spaces between them is not a token at all. What it produced is still a list: a total order over classified lexemes, and nothing more.

A list can answer "what is the third thing" and "how many things are there". It cannot answer "which of these operands does that operator take", because that is a claim about *containment*, and a list has no containment. Every question the rest of the compiler wants to ask — is this expression a call, what is the body of that loop, which branch does this else belong to — is a containment question. That is why parsing exists as a phase.

Two grammars over the same tokens produce two different trees, and both parsers are correct. The one below stratifies expressions into expr, term and factor, and that layering — not any code in the parser — is what makes * bind tighter than +. Flatten the two levels into a single expr -> expr op expr rule and the same input has two derivations, which is what [[ambiguous-grammars]] is about.

This is the most useful thing to internalise about the phase: precedence and associativity are properties of the language, written into its grammar, and a parser is a procedure for recovering the tree the grammar already implies. When a compiler gets a + b * c wrong, the bug is almost never a typo in the parser — it is a precedence level in the wrong place, and it produces no error at all. See [[operator-precedence]] and [[associativity]].

The confident wrong statement, and it is worth demolishing explicitly, is "a parser understands whether the program makes semantic sense." It does not, it must not, and a parser that tried would be wrong about real programs.

Every one of these parses cleanly and is nonsense: undefinedVariable + 1. "hello" - true. f(1, 2, 3) where f takes one argument. return at the top level of a file. x = x where x is a constant. In each case the token sequence matches the grammar exactly, so the parser must accept it and hand on a tree. Rejection happens later, in name resolution and type checking, because only those phases have the table of declarations and the typing rules that the question requires — see [[semantic-analysis]] and [[type-checking]].

The separation is not fastidiousness, it is what makes forward references possible at all. In C++, Java, Rust and Go a function may call a function declared two hundred lines below it. When the parser reaches the call, the callee does not exist in any table yet. If the parser were checking, it would have to reject. Because it only builds structure, resolution can run afterwards over a complete tree and see every declaration in the file at once — which is exactly what [[declaration-order]] is about.

The output is not merely "structured input". It is a data structure with a shape that every later pass is written against: resolution walks it attaching symbols, type checking walks it attaching types, lowering walks it emitting IR. Because containment is now explicit, each of those is an ordinary tree traversal rather than a bespoke scan — see [[ast-traversal]] and [[visitor-pattern]].

The tree also carries spans forward. Each node records the source range of the tokens it was built from, so that a type error discovered four phases later can still point at the exact characters that caused it. A parser that builds a tree without spans produces a compiler that can never say more than "type error somewhere in this file" — which is why [[source-locations]] and [[spans-and-ranges]] sit in the very next module.