Parsing

Parsing takes the flat stream of tokens the lexer produced and discovers the grammatical structure hiding within it, typically producing a tree — an Abstract Syntax Tree (AST) — that every later stage of the compiler will actually work with.

A parser checks whether a stream of tokens follows the language's grammar rules, and if it does, builds a structured representation of that code — usually a tree — capturing how the tokens relate to each other (which expression is inside which, which statements belong to which function, and so on).

A flat list of tokens on its own doesn't capture structure — it doesn't say which operator applies to which operands, or which statements are nested inside which function or loop. A tree structure makes that nesting and grouping explicit, which every later stage (checking types, generating code) fundamentally depends on.

Every compiler and interpreter parses its input; so does anything else that needs to understand structured text according to fixed rules — a JSON parser, an HTML parser, a SQL query parser, and a programming-language compiler's parser are all solving fundamentally the same kind of problem for their respective grammars.

Think of diagramming an English sentence in grade school — breaking "The quick fox jumps over the lazy dog" into subject, verb, and object, with modifiers attached to the words they describe. A parser does exactly this for code: given the sequence of words (tokens), it figures out the grammatical structure — which parts are the operands of that + sign, which statements form the body of this if — and represents that structure as a tree.

Even though + appears textually before *, the parser builds a tree where * is nested more deeply — reflecting that multiplication binds tighter than addition. Evaluating this tree bottom-up (4 * 2 = 8, then 3 + 8 = 11) gives the mathematically correct answer, which a naive left-to-right token reading would not.

A grammar formally defines a language's valid structure, typically written in a notation like BNF (Backus-Naur Form) or its extended variant EBNF — a set of production rules saying, for example, that an "expression" can be a number, or another expression plus another expression, and so on recursively.

A parse tree (or concrete syntax tree, CST) mirrors the grammar's rules very literally, including every grammatical detail; an Abstract Syntax Tree (AST) is a cleaned-up, more compact version that keeps only what's semantically meaningful (dropping parentheses used purely for grouping, redundant grammar-only nodes, and so on) — ASTs are what compilers actually use in every later stage, since parse trees carry more detail than is useful.

Common parsing strategies include recursive descent (a simple, hand-writable technique where each grammar rule becomes a function that calls other rules' functions — very common for hand-written parsers), and table-driven approaches like LL and LR parsing (including the widely used LALR variant), typically produced by parser-generator tools rather than hand-written, because the underlying tables are tedious and error-prone to construct manually.

Operator precedence and associativity (covered in the earlier Operators & Expressions fundamentals topic) must be correctly encoded into the grammar or the parsing algorithm itself — this is exactly why 3 + 4 * 2 correctly parses with multiplication grouped more tightly, rather than being parsed strictly left to right.

Writing an ambiguous grammar — one where the same token sequence can be validly parsed in more than one structurally different way — which either requires extra disambiguation rules or produces a parser generator error/warning about grammar conflicts.

Confusing a parse error (the token sequence doesn't match the grammar at all — a true syntax error) with a semantic error (the code is grammatically valid, but means something invalid, like using an undeclared variable) — these come from entirely different compiler stages and call for different debugging approaches.

Assuming parsing is "just" about matching parentheses and brackets — real grammars must also correctly encode precedence, associativity, and often quite subtle disambiguation rules for constructs that could otherwise be read multiple ways.

Hand-writing a recursive-descent parser for a grammar that isn't actually well-suited to it (for example, one with left recursion, which naive recursive descent cannot handle directly without rewriting the grammar or adding special handling).

Using a parser-generator tool (like ANTLR, Bison/Yacc, or a parser-combinator library) rather than hand-writing a full parser from scratch for anything beyond a small, simple grammar — generated parsers are far less error-prone for handling the full complexity of a real grammar correctly.

Writing a small recursive-descent parser by hand as a learning exercise for a simple expression grammar, since it's one of the most direct ways to viscerally understand how grammar rules become working code.

Reading a "shift-reduce conflict" or "reduce-reduce conflict" warning from a parser-generator tool as a sign the grammar itself is ambiguous or needs additional precedence/associativity declarations, rather than a bug purely in the generated code.

Top-down vs. bottom-up parsing Recursive descent and LL parsers are top-down: they start from the grammar's highest-level rule (like "program") and work downward, predicting which specific rule applies next based on the upcoming tokens. LR (and LALR) parsers are bottom-up: they start from the raw tokens and progressively combine ("reduce") them into higher-level grammar constructs, working upward toward the complete program. The two approaches can handle different classes of grammars efficiently, which is why both remain in wide use for different situations.

Pratt parsing (operator-precedence parsing) A parsing technique especially well suited to expressions with many operators of differing precedence and associativity — instead of encoding precedence entirely into a deeply nested grammar hierarchy, each operator is assigned a numeric "binding power," and the parser uses those numbers directly to decide how tightly to group each operator's operands. Pratt parsing is popular for hand-written parsers specifically because it handles complex expression grammars far more cleanly than naive recursive descent would.

A production-quality parser doesn't simply stop at the very first syntax error — it attempts error recovery (commonly by skipping tokens until it finds a likely-safe restart point, like the next semicolon or closing brace) so it can continue parsing and report multiple distinct errors in a single compilation attempt, rather than forcing the programmer through a slow one-error-at-a-time fix-and-recompile cycle.

What's the difference between a parse tree and an AST?

A parse tree (concrete syntax tree) mirrors the grammar very literally, including every grammatical detail and rule invocation. An AST is a cleaned-up, more compact version, dropping purely syntactic details (like grouping parentheses) that don't carry independent meaning — ASTs are what compilers actually work with in later stages.

What's the difference between top-down and bottom-up parsing?

Top-down parsing (recursive descent, LL) starts from the grammar's highest-level rule and works downward, predicting the next rule to apply. Bottom-up parsing (LR, LALR) starts from the raw tokens and progressively combines them upward into higher-level constructs.

Why does 3 + 4 * 2 parse with the multiplication grouped more tightly, even though it appears later in the token stream?

Because the grammar (or the parsing algorithm's precedence rules) encodes that multiplication binds more tightly than addition, so the parser builds a tree where 4 * 2 is a single subexpression that then becomes the right-hand operand of the addition — reflecting mathematical precedence rather than left-to-right token order.

What's the difference between a syntax error and a semantic error?

A syntax error means the token sequence doesn't match the language's grammar at all — the parser can't build a valid tree from it. A semantic error means the code is grammatically valid (the parser succeeds) but violates a meaning-level rule, like using an undeclared variable or assigning mismatched types — caught by semantic analysis, a later stage.

Tokens: 3  +  4  *  2

AST (respecting * binding tighter than +):

        +
       / \
      3   *
         / \
        4   2