Parser
Understand what a parser does, how it sits between the lexer and the rest of the compiler, and what it produces — from a raw token stream to a structured parse tree.
What is a Parser?
After the lexer breaks source code into tokens, the parser takes over. Its job is to check whether those tokens form a grammatically valid program — and if so, to build a structured representation of that program.
Think of it this way:
The parser transforms that token stream into a structured tree (AST):
The parser does two things:
- Syntax checking — reports errors if the token stream violates the grammar.
- Structure building — builds a parse tree (or AST) that captures the program's meaning.
Where the Parser Fits
The parser is the second phase of a compiler, called syntax analysis. It uses the grammar of the programming language (a context-free grammar) to check and understand the structure of the program.
Input, Output, and the Grammar
Input
The parser receives a token stream from the lexer. Each token has a type (keyword, identifier, operator, literal) and sometimes a value.
Grammar
The parser uses a context-free grammar (CFG) that defines the language's syntax. For example:
This grammar tells the parser what sequences of tokens are valid expressions.
Output
The parser produces a parse tree (also called a concrete syntax tree) or an abstract syntax tree (AST):
| Tree Type | Description |
|---|---|
| Parse tree | Every grammar rule is a node — includes all terminals and non-terminals |
| AST | Compact form — only semantically important nodes are kept |
Parse tree for "a + b * c":
The AST keeps only the essential structure — operator nodes become the tree, identifiers become leaves:
Types of Parsers
Parsers are classified by the direction in which they build the parse tree and the direction in which they scan the input.
All practical parsers scan input left to right (L). The difference is in how they build the tree:
Top-Down Parsers
Start from the start symbol (root) of the grammar and try to match the input by expanding non-terminals downward.
Top-down parsers build the tree from the top (root) to the bottom (leaves).
Examples:
- Recursive Descent Parser — writes one function per non-terminal
- Predictive Parser / LL(1) Parser — uses a parsing table to avoid backtracking
Bottom-Up Parsers
Start from the input tokens (leaves) and reduce them up to the start symbol.
Bottom-up parsers build the tree from the leaves up to the root.
Examples:
- LR Parser — handles a larger class of grammars than LL
- LALR Parser — used in tools like yacc and bison
Comparison
| Feature | Top-Down (LL) | Bottom-Up (LR) |
|---|---|---|
| Tree construction | Root → leaves | Leaves → root |
| Grammar class | LL(k) grammars | LR(k) grammars — larger class |
| Ease of implementation | Easier (recursive descent) | Needs parser generator tools |
| Error messages | Usually more readable | Can be cryptic |
| Left recursion | Must be eliminated | Handles it naturally |
Parser vs. Lexer — Division of Responsibility
A common question is: why have two separate phases? Why not just have the parser handle everything?
The reason is separation of concerns — each phase handles a different class of language structure, and keeping them separate makes the compiler simpler and faster.
| Concern | Lexer | Parser |
|---|---|---|
| Formal model | Regular grammar / DFA | Context-free grammar / PDA |
| Handles | Tokens (identifiers, numbers, keywords) | Statement and expression structure |
| Cannot handle | Nested structures, pairing | ✓ CFGs can handle nesting |
| Speed | O(n) — very fast | O(n) for LL/LR, O(n³) general |
What the lexer does not check:
The lexer sees tokens one at a time and has no memory of the past. It can recognise that ( and ) are valid parenthesis tokens, but it cannot check if they are balanced. That is the parser's job.
What the parser does not check:
The parser checks syntax (structure), not semantics (meaning). It accepts grammatically correct code regardless of whether variables are declared or types match.