Syntax Analysis

Learning Objectives

• Define syntax analysis and explain its position between lexical analysis and semantic analysis
• Write and interpret a context-free grammar for a simple expression language
• Build a parse tree for a given token stream by hand
• Distinguish top-down parsing from bottom-up parsing and name their common implementations
• Trace recursive descent parsing on a concrete input
• Explain why left recursion breaks top-down parsers and how to eliminate it

Quick Answer

Syntax analysis is the second phase of compilation. It takes the token stream produced by the lexical analyzer and checks whether the tokens are arranged according to the grammatical rules of the language, using a context-free grammar (CFG). The output is a parse tree (or a more compact abstract syntax tree) that represents the program's grammatical structure. Parsers come in two families: top-down parsers, which build the tree from the root downward by predicting productions, and bottom-up parsers, which build it from the leaves upward by reducing tokens into higher-level constructs. If the tokens can't be arranged into a valid tree, the parser reports a syntax error.

How Syntax Analysis Fits the Compiler Pipeline

Lexical analysis already told us "this is a keyword, this is a number, this is a plus sign." Syntax analysis asks the next question: are these things in a legal order? int + 5; consists entirely of valid tokens, but no C grammar rule allows a keyword to be added to a number, so the parser rejects it. This is the core division of labor: the lexer works on isolated tokens, while the parser works on sequences and nesting — which requires more expressive power than regular expressions can provide.

Context-Free Grammars

A context-free grammar (CFG) is a set of production rules that describe how valid strings in a language can be built. Each rule has a non-terminal on the left (a placeholder representing a category of construct) and a sequence of terminals and non-terminals on the right (what it can expand into). Terminals are the actual tokens from the lexer; non-terminals never appear in the final token stream — they exist only to structure the grammar.

Here's a grammar for simple arithmetic expressions with addition and multiplication:

E  -> E + T | T
T  -> T * F | F
F  -> ( E ) | id

E (expression), T (term), and F (factor) are non-terminals. +, *, (, ), and id are terminals. This grammar is deliberately layered: T binds tighter than E, which is how it encodes that multiplication has higher precedence than addition without needing any extra rules about precedence.

Why it exists: Regular expressions can't express nesting — they have no way to say "a ( must eventually be matched by a ) with balanced content in between," because that requires unbounded memory of how many open parentheses have been seen. A CFG's recursive production rules (F -> ( E ), where E can itself contain another F) handle arbitrary nesting naturally.

Parse Trees

A parse tree is a graphical representation of a derivation — it shows how the start symbol of the grammar was expanded, step by step, into the actual token sequence. Every internal node is a non-terminal; every leaf is a terminal (a token).

Take the input id + id * id using the grammar above. Reading it left to right and applying the precedence baked into the grammar, the parse tree looks like this:

Notice that the tree naturally groups id * id together under one T, before that T is combined with the first id under E. This shape is exactly why * gets evaluated before + when you later walk the tree to generate code — precedence is a structural property of the tree, not something the code generator has to special-case.

In practice, compilers usually build an abstract syntax tree (AST) rather than a full parse tree. An AST drops the non-terminal bookkeeping nodes and keeps only the meaningful structure — for id + id * id, the AST would just have a + node with id as one child and a * node (with two id children) as the other.

Top-Down Parsing

Top-down parsers start at the grammar's start symbol and try to predict, one production at a time, which rule will produce the actual input. The most intuitive form is recursive descent parsing: write one function per non-terminal, and have each function call the functions for the non-terminals on the right-hand side of its rule.

Here is a recursive descent parser for the expression grammar above (adapted to return computed values rather than a tree, so the trace is easy to follow):

def parse_expression(tokens):
    value = parse_term(tokens)
    while tokens and tokens[0] == '+':
        tokens.pop(0)          # consume '+'
        value += parse_term(tokens)
    return value

def parse_term(tokens):
    value = parse_factor(tokens)
    while tokens and tokens[0] == '*':
        tokens.pop(0)          # consume '*'
        value *= parse_factor(tokens)
    return value

def parse_factor(tokens):
    if tokens[0] == '(':
        tokens.pop(0)          # consume '('
        value = parse_expression(tokens)
        tokens.pop(0)          # consume ')'
        return value
    return int(tokens.pop(0))  # a number literal

tokens = ['3', '*', '(', '2', '+', '5', ')']
print(parse_expression(tokens))  # 21

Tracing this by hand: parse_expression calls parse_term, which calls parse_factor and reads 3. Back in parse_term, the next token is *, so it consumes it and calls parse_factor again. That call sees (, so it recurses into parse_expression, which parses 2 + 5 as 7, then consumes the closing ). parse_term now has 3 * 7 = 21, and since the next token is nothing (+ never appears), parse_expression returns 21 directly.

Left recursion is fatal for recursive descent. A rule like E -> E + T written directly as a function (parse_expression calling itself first, before consuming any token) recurses infinitely without ever reading input. That's why the grammar above is written with a while loop instead — it's the standard trick of rewriting left recursion into iteration (equivalently, into a right-recursive helper rule) so the parser makes progress on every call.

Table-driven top-down parsers, called LL(1) parsers, do the same job without hand-written functions: they use a parsing table built from FIRST and FOLLOW sets to decide, by looking at just one lookahead token, which production to apply.

Bottom-Up Parsing

Bottom-up parsers work in the opposite direction: they start from the raw tokens and repeatedly reduce groups of symbols on a stack into single non-terminals, using shift-reduce parsing, until the entire input has been reduced to the start symbol.

For id + id * id, a shift-reduce parser would: shift id, reduce it to F, reduce F to T, shift +, shift id, reduce to F then T, shift *, shift id, reduce to F, reduce T * F to T, then finally reduce T + T-shaped stack content into E. The decision of when to shift versus when to reduce is precomputed into a state table.

The main bottom-up families are:

• LR(0) / SLR(1): Simple table construction, but cannot handle all practical grammars.
• LALR(1): Merges states from a more powerful construction to keep tables small; this is what tools like yacc and bison generate, and what powers most production parsers.
• LR(1) / GLR: Full lookahead power, handling more grammars (including some ambiguous ones with GLR) at the cost of larger tables or more complex machinery.

Bottom-up parsers can handle a strictly larger class of grammars than LL parsers — in particular, they don't choke on left recursion, which is one reason grammar-generator tools default to LALR rather than LL.

Key Terms

Term	Definition	Related Concept
Context-Free Grammar (CFG)	A set of production rules (non-terminal → symbols) that define a language's valid structures	Non-terminal, terminal
Non-terminal	A placeholder symbol in a grammar that expands into other symbols	Production rule
Terminal	An actual token from the lexer that appears in the final input	Token
Production Rule	A rewrite rule showing how a non-terminal can expand	CFG
Parse Tree	A tree showing the full derivation of a string from the grammar's start symbol	Abstract Syntax Tree
Abstract Syntax Tree (AST)	A compact tree keeping only semantically meaningful structure, without grammar bookkeeping nodes	Parse Tree
Recursive Descent Parsing	A top-down parsing technique using one function per non-terminal	Top-down parsing
Left Recursion	A production where a non-terminal's expansion begins with itself, breaking naive recursive descent	LL parsing
LL(1) Parser	A table-driven top-down parser using one token of lookahead	Top-down parsing
Shift-Reduce Parsing	A bottom-up technique that shifts tokens onto a stack and reduces them into non-terminals	LR parsing
LALR(1)	A practical bottom-up parsing method used by tools like yacc/bison	Bottom-up parsing

Common Mistakes

Misconception: Syntax analysis checks whether a program does the right thing. Why it's wrong: Syntax analysis only verifies grammatical structure — that tokens appear in a legal order according to the CFG. It has no concept of variable types, declarations, or meaning. Correct understanding: int x = "hello"; is syntactically perfect (keyword, identifier, operator, literal, semicolon in the right order) but semantically wrong. Catching that type mismatch is the job of semantic analysis, the next phase.

---

Misconception: Top-down and bottom-up parsers can handle exactly the same set of grammars, just built differently. Why it's wrong: They differ in real, practical ways. LL parsers (top-down) cannot handle left-recursive grammars without rewriting them first. LR/LALR parsers (bottom-up) handle left recursion natively and accept a strictly larger class of grammars. Correct understanding: The choice of parsing strategy isn't just an implementation detail — it constrains which grammars you can write directly. This is why hand-written parsers (recursive descent, top-down) often need grammars manually restructured, while generated parsers (yacc/bison, bottom-up) are more forgiving.

---

Misconception: A parse tree and an abstract syntax tree are the same thing. Why it's wrong: A parse tree faithfully records every production used during derivation, including non-terminals that exist purely for grammar bookkeeping (like the separate E, T, F layers used to encode precedence). Correct understanding: An AST strips out that bookkeeping and keeps only the operations and operands that matter for later phases. The parse tree for id + id * id has many more nodes than its AST, which needs only a + node and a * node.

Comparison and Connections

Aspect	Top-Down Parsing (LL)	Bottom-Up Parsing (LR/LALR)
Tree construction direction	Root to leaves	Leaves to root
Handles left recursion?	No — must rewrite grammar	Yes, natively
Typical implementation	Recursive descent (hand-written) or LL(1) table	Shift-reduce with LALR(1) table
Common tools	Hand-written parsers, ANTLR (LL(*))	yacc, bison, GNU Bison
Grammar class supported	Smaller (LL grammars)	Larger (LR grammars)
Ease of debugging	Easier to trace by hand (maps to function calls)	Harder to trace manually (state machine on a stack)

Practice Questions

Recall

1. What two things does a context-free grammar rule consist of? Answer guidance: A single non-terminal on the left-hand side, and a sequence of terminals and/or non-terminals on the right-hand side that it can expand into.

2. What is the output of the syntax analysis phase? Answer guidance: A parse tree, or more commonly in real compilers, an abstract syntax tree (AST) representing the grammatical structure of the program.

Understanding

3. Why can't regular expressions alone describe a full programming language grammar? Answer guidance: Regular expressions describe regular languages, which cannot express unbounded nesting (like balanced parentheses or nested blocks). Context-free grammars can, through recursive production rules.

4. Why does the grammar E -> E + T | T, T -> T * F | F correctly encode that * has higher precedence than +, without an explicit precedence rule? Answer guidance: The grammar is layered so that T (built from *) must be fully formed before it can appear inside an E production. This forces multiplication to bind tighter structurally — the parse tree groups * expressions before combining them with +.

Application

5. Using the grammar E -> E + T | T, T -> T * F | F, F -> ( E ) | id, draw (or describe) the parse tree for id * id + id. Answer guidance: The top-level E splits into an E (containing T -> T * F -> id * id) and a + T (where T -> F -> id). The multiplication is nested inside the left operand of the addition, reflecting that id * id is computed first.

6. Trace the recursive descent parser in this page's example on the input 2 + 3 * 4. What value does it return, and what is the last operation performed? Answer guidance: It returns 14. parse_expression reads 2 via parse_term/parse_factor, sees +, then calls parse_term again which reads 3, sees *, and multiplies by 4 to get 12. The final step is 2 + 12 = 14, so the last arithmetic operation performed is the addition.

Analysis

7. Why does naive recursive descent break on the rule E -> E + T, and how does rewriting it as a while loop fix the problem? Answer guidance: A function implementing E -> E + T directly would call itself as its very first action, before consuming any token, causing infinite recursion with no progress. Rewriting it as "parse one T, then loop while the next token is +, consuming a T each time" replaces the self-call with iteration, guaranteeing that each loop iteration consumes at least one token.

8. A language designer wants to generate their parser with a tool like bison instead of hand-writing recursive descent. What tradeoff are they making? Answer guidance: They gain the ability to use a broader class of grammars (including left-recursive ones) and get more efficient, less error-prone table-driven parsing, but they lose the intuitive one-function-per-rule structure and the ease of inserting custom error messages or logic mid-parse that recursive descent offers.

FAQ

Why do compilers use parse trees or ASTs instead of just working directly with the token stream? The token stream is a flat sequence with no structure — it doesn't say which operator binds to which operands. A tree makes that structure explicit, so later phases (semantic analysis, code generation) can walk it recursively and process each subexpression independently.

What happens when the parser encounters a syntax error, like a missing semicolon? Most parsers use error recovery techniques, such as "panic mode," where they discard tokens until they find a synchronization point (like the next semicolon or closing brace) and resume parsing from there. This lets the compiler report multiple syntax errors in one pass instead of stopping at the first one.

Is one parsing strategy strictly "better" than the other? Not universally. Top-down parsers (especially hand-written recursive descent) are easier to understand, debug, and extend with custom logic, which is why many modern compilers (including Clang and CPython's newer parser) use them. Bottom-up parsers, generated by tools, can handle a broader class of grammars automatically and are common when the grammar is complex and unlikely to change often.

Can a grammar be ambiguous, and what does that mean for parsing? Yes — an ambiguous grammar allows more than one valid parse tree for the same input, which is a real problem because the compiler needs a single, unambiguous structure to proceed. The classic example is if-then-else without disambiguation rules: if a then if b then s1 else s2 could attach the else to either if. Compilers resolve this with explicit disambiguation rules (like "match else with the nearest unmatched if") rather than leaving it to chance.

Do I need to memorize LL and LR parsing table construction for an exam? It depends on the course, but even without memorizing the table-construction algorithms, you should be able to explain the conceptual difference (top-down prediction versus bottom-up reduction), trace a recursive descent parser by hand, and explain why left recursion is a problem for top-down parsing. These are the most commonly tested ideas.

How does operator precedence actually get enforced during parsing if I'm not using a grammar with separate E/T/F layers? Some parsers use a technique called operator-precedence parsing (or precedence climbing), which assigns numeric precedence and associativity values to each operator and uses them directly during parsing instead of encoding precedence into the grammar's layering. It produces the same correct tree shape with a flatter grammar and less recursive function-call overhead.

Quick Revision

• Syntax analysis is the second compiler phase; it converts a token stream into a parse tree (or AST) using a context-free grammar
• A CFG consists of production rules: non-terminal → sequence of terminals/non-terminals
• Terminals are actual tokens; non-terminals are grammar placeholders that never appear in final output
• A parse tree records every production used; an AST strips bookkeeping nodes and keeps only meaningful structure
• Top-down parsing (e.g., recursive descent, LL(1)) predicts productions from the start symbol downward
• Left recursion breaks naive recursive descent — it must be rewritten as iteration or right recursion
• Bottom-up parsing (e.g., LALR(1), used by yacc/bison) shifts tokens and reduces them into non-terminals from the leaves up
• Bottom-up parsers accept a strictly larger class of grammars than LL parsers, including left-recursive ones
• Precedence and associativity can be encoded either through grammar layering (E/T/F) or through explicit operator-precedence parsing
• Syntax errors are recovered from using techniques like panic mode, allowing multiple errors to be reported per compile
• Syntax analysis checks structure only — it says nothing about types or meaning, which is semantic analysis's job

Related Topics

Prerequisites: Lexical analysis, regular expressions vs. context-free grammars, basic tree data structures

Related Topics: Formal language theory, grammar ambiguity and disambiguation, parser generator tools (yacc, ANTLR)

Next Topics: Semantic analysis, symbol tables and type checking, intermediate code generation