Syntax Analysis and AST

Definition: Syntax Analysis (parsing) validates that a token sequence conforms to a formal Context-Free Grammar and constructs an Abstract Syntax Tree (AST) representing that structure.

How It Works

Grammars are specified in BNF/EBNF; precedence and associativity declarations resolve ambiguities like whether a - b - c groups left ((a-b)-c, left-associative) or which if a dangling else binds to (the nearest unmatched one, by convention)
Recursive Descent (Top-Down): one hand-written function per grammar rule, calling into each other recursively; requires the grammar to be free of left-recursion, and typically uses Pratt parsing / precedence climbing for expressions so operator precedence doesn’t require one recursive function per precedence level
LL(1) Parsers: top-down, table-driven, decide which production to use from one token of lookahead
LR(1)/LALR Parsers (bottom-up): shift-reduce parsers built from parser generators like Yacc/Bison; handle a strictly larger class of grammars than LL, but the generated tables are harder to hand-debug, and conflicts show up as “shift/reduce” or “reduce/reduce” errors in the generator output
AST construction: the tree discards syntax only needed to disambiguate parsing, parentheses, semicolons, redundant grouping, and keeps only the semantically meaningful structure: a binary expression node with an operator and two children, not a parenthesis token
Semantic Analysis then walks the AST to build a Symbol Table (mapping names to declarations, scopes, and types), perform name resolution, enforce type checking, and catch errors like using a variable before declaration or calling a function with the wrong argument types
Error recovery: production parsers don’t stop at the first syntax error; they use panic-mode recovery (skip tokens until a synchronizing token like ; or }) or error-production rules so the IDE or compiler can report multiple errors in one pass
A Parse Tree (concrete syntax tree) keeps every grammar rule and token, including punctuation; the AST is a deliberately simplified derivative of it, which is why “parsing” and “AST construction” are sometimes described as two steps even when a single pass produces the AST directly without ever materializing the full parse tree
Operator precedence parsing / Pratt parsing assigns each operator a binding power; the parser recursively parses sub-expressions only as long as the next operator’s binding power is high enough, which handles arbitrarily many precedence levels without one grammar rule per level
Parser combinators build parsers by composing small functions (sequence, choice, many) directly in a host language instead of generating one from a separate grammar file, trading some performance for parsers that are easy to read, test, and modify incrementally
A visitor pattern or tree-walking interpreter is the typical way later phases traverse the AST: each node type has a corresponding visit method, so adding a new analysis means adding a new visitor rather than modifying every node class

Under the Hood

Given: parsing a + b * c with the usual precedence, multiplication binds tighter than addition. Step 1: the parser applies grammar rules for expr, term, and factor, producing a full parse tree with one node per grammar rule application. Step 2: AST construction discards the intermediate term/factor bookkeeping nodes that exist only to encode precedence, keeping only the operators and operands that matter semantically. Answer: the AST has + at the root, a as its left child, and a * subtree (b, c) as its right child, correctly reflecting that b * c evaluates before the addition even though + appears first in reading order.

Given: parsing if (x) if (y) f(); else g();, the classic dangling-else ambiguity. Step 1: without a rule, the grammar allows the else to attach to either the outer or inner if. Step 2: the standard disambiguation rule attaches else to the nearest unmatched if. Answer: the AST attaches else g(); to the inner if (y), not the outer if (x), matching what every mainstream C-family language actually does at runtime.

Given: parsing the expression 2 + 3 * 4 with a Pratt parser using binding powers + = 10 and * = 20. Step 1: the parser reads 2, then sees + with binding power 10 and recurses to parse its right-hand side. Step 2: inside that recursion it reads 3, then sees * with binding power 20, which is higher than the 10 it’s allowed to continue at, so it recurses again and consumes 3 * 4 as one sub-expression before returning. Answer: the result is 2 + (3 * 4), an AST with + at the root and a * subtree on the right, produced without ever hand-writing a separate grammar rule per precedence level.

Why It Matters

Provides the structured tree data model that IDE code completion, linters, static analysis tools, refactoring tools, and code generators all build on top of
Catching grammar and semantic errors here, before code generation, means the compiler gives precise, source-located error messages instead of failing mysteriously deep in the backend
The AST is the handoff point to Intermediate Representation (IR) generation; a clean, well-typed AST makes IR generation close to mechanical, while a messy one pushes complexity downstream where it’s harder to diagnose
Multiple errors per compile run depend entirely on parser error recovery working well; without it, developers would have to fix one syntax error, recompile, hit the next one, and repeat, one at a time
Language servers (the backend behind IDE autocomplete, via the Language Server Protocol) keep an AST resident in memory and incrementally re-parse only the edited region, which is only possible because the AST is a well-defined, addressable structure rather than an implicit byproduct of code generation

Common Pitfalls

Ambiguous grammars (dangling-else, incompletely specified operator precedence) cause genuine parser ambiguity that must be resolved with explicit precedence rules or grammar rewrites, not left to the parser generator’s default tie-breaking
Left recursion (expr -> expr '+' term) causes naive recursive-descent parsers to infinite-loop; it must be eliminated or handled with iterative or Pratt-style parsing instead
Treating parsing and semantic analysis as fully separable: some constructs, like resolving whether T(x) is a cast or a function call, or user-defined operator overloading, genuinely require type or symbol information mid-parse in some languages
Building the parse tree and never simplifying it into an AST, which leaves every later phase wading through punctuation nodes that carry no semantic meaning
Choosing a parsing technique for its theoretical elegance over the language’s actual needs: LALR handles many real-world grammars fine, but some language constructs (like C++‘s most-vexing-parse ambiguities) need extra disambiguation logic no parser generator provides automatically
Silently swallowing syntax errors during error recovery, so the parser produces a plausible-looking but semantically wrong AST instead of clearly reporting that recovery happened
Forgetting that a PEG’s ordered choice (try rule A, else try rule B) is not the same as a context-free grammar’s ambiguity: a PEG always picks the first matching alternative, which can silently hide a grammar bug that a true CFG-based tool would flag as ambiguous

Comparison

Technique	Direction	Lookahead	Grammar restriction	Typical use
Recursive descent	Top-down	Usually 1 token (or Pratt for expressions)	No left recursion	Hand-written parsers (Clang, most language frontends)
LL(1)	Top-down	1 token	No left recursion, must be LL(1)	Simple table-driven parsers
LALR(1)	Bottom-up	1 token	Broader than LL(1)	Yacc/Bison-generated parsers
PEG (Parsing Expression Grammar)	Top-down	Backtracking allowed	Ordered choice, no true ambiguity	Modern parser combinators, some DSLs

Node kind	Parse tree	AST
Parentheses	Explicit nodes	Discarded, implied by tree shape
Semicolons/commas	Explicit tokens	Discarded
Grammar rule nesting	One node per rule (`term`, `factor`)	Collapsed to semantic nodes only
Operator	Leaf token	Interior node with typed operands

Example

Parsing 3 + 5 * 2 with correct precedence creates an AST with root +, left child 3, and right child a * subtree (5, 2), reflecting that multiplication binds tighter than addition even though + appears in the middle of the token stream:

Clang and GCC both use hand-written recursive-descent parsers rather than a generated LALR parser, specifically because C and C++ need context-sensitive disambiguation (typedef-name lookup, template angle-bracket parsing) that’s much easier to express in hand-written code than in a pure grammar-generator table. Python’s own parser was rewritten from LL(1) to a PEG-based parser in Python 3.9 (PEG parser, PEP 617) to support new grammar features that the old LL(1) grammar couldn’t express cleanly.

TypeScript’s compiler exposes its AST as a public, documented API (via the typescript npm package), which is what makes tools like ESLint’s TypeScript plugin, Prettier, and countless refactoring codemods possible. The AST there isn’t just an internal compiler detail; it’s a stable contract other tools are built against, which is why breaking AST-shape changes are treated as a much bigger deal in TypeScript releases than most internal compiler changes.

Given: an IDE needs to offer “extract variable” as a refactoring on a selected expression. Step 1: the IDE locates the AST subtree corresponding to the user’s text selection. Step 2: it checks that subtree is a valid, side-effect-free expression node (not a partial statement or an assignment target). Step 3: it generates a new let declaration node assigning that subtree to a fresh variable name, and replaces the original subtree in the AST with a reference to that variable. Answer: the refactor is entirely an AST-to-AST transformation; the IDE never has to reason about raw text ranges or re-parse anything beyond the edited region, which is why AST-based tooling is both more reliable and faster than regex-based find-and-replace refactoring.

Referenced by

Dig deeper

Spot an error in this note?