Parsing the Structure: How Syntax Analysis Turns Tokens into Trees

This article is Part 3 of the Compiler Design series. Part 1 covers all six compilation stages and Part 2 covers lexical analysis — start from the beginning if you haven’t already.

After lexical analysis hands us a clean stream of tokens, the compiler faces a harder question: do those tokens form a valid programme? A sequence of words can be grammatically wrong even when every individual word is legitimate. Syntax analysis is the stage that figures this out.

What is Syntax Analysis?

Syntax analysis is Stage 2 of compilation. The parser (also called the syntax analyser) consumes the token stream produced by the lexer and checks whether it conforms to the grammar of the programming language. If it does, the parser produces a hierarchical structure — a parse tree or Abstract Syntax Tree (AST) — that encodes the grammatical relationships between tokens.

The resulting tree is what every subsequent stage — semantic analysis, IR generation, code generation — actually works with. The flat list of tokens is gone; the tree takes its place.

Grammar: The Rules of the Language

A programming language’s grammar defines what token sequences are syntactically valid. Grammars are typically written in Backus-Naur Form (BNF) or its extended variant (EBNF):

declaration  → type identifier '=' expression ';'
expression   → term (('+' | '-') term)*
term         → factor (('*' | '/') factor)*
factor       → NUMBER | IDENTIFIER | '(' expression ')'
type         → 'int' | 'float' | 'char'

Each rule says: “this grammar construct can be made up of these smaller constructs or tokens.” The grammar is recursive — expression can contain term, which can contain factor, which can contain another expression in parentheses.

This recursion is what gives languages the ability to express arbitrarily complex nested expressions from a finite set of rules.

Why Grammar Matters for Parsing

When the parser encounters a token, it consults the grammar to decide which rule applies. This process of matching tokens to grammar rules — and deciding which rule to try at each step — is the core challenge of parser design.

How the Parser Works

Parsers follow one of two broad strategies:

Top-Down Parsing

The parser starts at the root grammar rule and works downward, trying to derive the input token by token. It predicts which rule applies based on the next token it sees.

• Recursive descent parsers implement this directly as mutually recursive functions — one function per grammar rule.
• LL(k) parsers formalise this approach with a parsing table driven by the next k tokens.

Top-down parsers are intuitive to write and debug. Most hand-written parsers — including those inside GCC, Clang, and many language interpreters — are recursive descent.

Bottom-Up Parsing

The parser starts from the raw tokens and repeatedly reduces groups of tokens to grammar rules, working upward to the root. It accumulates tokens on a stack and “reduces” when it recognises a complete grammar construct.

• LR parsers (and their variants: LALR, SLR, GLR) implement this with a shift-reduce automaton.
• Tools like yacc and bison generate LALR parsers automatically from a grammar specification.

Bottom-up parsers handle a larger class of grammars than top-down parsers, which is why they’re common in generated parsers for complex languages.

The Parse Tree (Concrete Syntax Tree)

When the parser successfully matches the token stream against the grammar, it builds a parse tree. Every grammar rule that was applied becomes an internal node; every token becomes a leaf.

For int sum = a + b, the parse tree shows:

• A Declaration node at the root
• Children for the type (int), the identifier (sum), and the Expression
• The Expression node has children for the identifiers a and b and the + operator

Parse trees include everything — keywords, punctuation, intermediate grammar nodes. They are a complete record of exactly how the parser matched the input to the grammar.

The Abstract Syntax Tree (AST)

A parse tree is accurate but verbose. The Abstract Syntax Tree (AST) keeps only what matters semantically and throws away the rest.

What gets removed in the AST:

• Intermediate grammar rule nodes (like Term, Factor) that carry no meaning beyond grouping
• Punctuation tokens: parentheses, semicolons, commas
• The specific grammar derivation — only the semantic intent remains

What gets kept:

• Operators (as internal nodes, with their operands as children)
• Identifiers and literals (as leaves)
• Control flow constructs (if/else, loops) with their conditions and bodies
• Declarations with their types and initialisers

A key insight: the shape of the AST encodes operator precedence. In a + b * c, the * node sits below the + node because * has higher precedence — the multiplication is a child of the addition, meaning it’s computed first. You don’t need to store precedence rules separately; the tree structure captures them.

Every subsequent stage — semantic analysis, IR generation — operates on the AST, not the original source code.

Syntax Errors

A syntax error occurs when the token stream cannot be matched to any valid derivation from the grammar’s root rule. Common examples:

int x = ;           // missing expression after =
if (x > 0           // missing closing parenthesis
return               // missing value and semicolon

The parser’s job isn’t just to detect the first error and stop — good parsers implement error recovery, skipping or inserting tokens to get back to a valid state so they can continue and report as many errors as possible in a single pass.

An important point: syntax analysis only catches structural errors. It cannot catch semantic mistakes. The statement "hello" + 5 might be syntactically valid (it matches the grammar for expression) but semantically wrong (you can’t add a string and an integer). Catching that is the job of the next stage.

Three Terms to Remember

Grammar — A set of rules that define what sequences of tokens form valid programmes in a language.

Parse Tree — A complete tree representation of how the token stream was matched to the grammar, including every intermediate rule and every token.

Abstract Syntax Tree (AST) — A trimmed, semantically meaningful tree derived from the parse tree, stripped of punctuation and intermediate grammar nodes. The input to every subsequent compilation stage.

What Comes Next

With a valid AST in hand, the compiler moves to semantic analysis — Stage 3. The parser checked that the programme is grammatically correct; the semantic analyser checks that it actually means something valid. It resolves types, verifies scope, builds the symbol table, and ensures that the operations the AST describes are legal for the types involved.