PadhaikoAll subjects

Syntax Analysis (Parsing)

Compiler Design (ENCT 326)

Open in the Padhaiko app

3.1 Role of syntax analysis

The syntax analyzer (universally termed the parser) occupies the central position in the compiler front-end. It receives the stream of tokens produced by the lexical analyzer and verifies whether the sequence conforms to the syntactic rules of the source language, formalised as a Context-Free Grammar (CFG).

Diagram: parser and its neighboursText
                  token stream
  Lexical Analyzer ------------> Syntax Analyzer (Parser) ------> Abstract Syntax Tree
                  <------------          |      ^      \          (or parse tree)
                  getNextToken()         |      |       \                |
                                         |      |        \               v
                                         v      v         v        Semantic Analyzer
                                   Symbol Table  Error Handler
                                   (two-way)     (errors reported to it)

3.1.1 Core Responsibilities of the Parser

  1. Syntactic Structure Verification: Validates that expressions, statements, declarations, and control-flow blocks satisfy language syntax rules.
  2. Syntax Tree Construction: Builds a hierarchical intermediate data structure (an Abstract Syntax Tree or parse tree) that reflects operator precedence, associativity, and statement nesting.
  3. Symbol Table Interaction: Coordinates with the symbol table to register variable declarations, function prototypes, and scope block boundaries.
  4. Error Detection and Diagnostic Reporting: Pinpoints syntax errors (e.g., missing delimiters, mismatched brackets) with precise source-file line and column indicators.

3.1.2 Syntax Error Recovery Strategies

Unlike runtime crashes, a production compiler must not abort after encountering the first syntax error. It should report meaningful diagnostic messages and recover sufficiently to parse the rest of the translation unit:

Syntax Error Recovery Techniques
Recovery ModeMechanismTrade-Offs
Panic ModeThe parser discards incoming tokens until a member of a pre-selected set of synchronizing tokens (such as ;, }, or end) is reached.Easiest to implement; guaranteed to prevent infinite loops, but may miss errors in skipped code.
Phrase-Level RecoveryThe parser replaces a prefix of the remaining input with a string that allows parsing to continue (e.g., inserting a missing semicolon or deleting an extraneous comma).Corrects common human typos locally, but risks creating false secondary errors if the repair does not match user intent.
Error ProductionsGrammar designers augment the language grammar with explicit productions for anticipated common errors (e.g., omitting the condition parentheses in if).Produces highly targeted, friendly error messages; inflates the parser table size.
Global CorrectionAlgorithms compute the minimum number of insertions, deletions, and replacements needed to transform an invalid token stream into a syntactically valid one.Theoretically optimal, but computationally expensive in time and memory (), making it impractical for routine compilation.

3.2 Context-free grammars and parse trees

3.2.1 Formal Definition of a Context-Free Grammar

Definition

Context-Free Grammar (CFG)

A Context-Free Grammar (CFG) is a 4-tuple where:

3.2.2 Derivations

A derivation is a sequence of production rule applications starting from the start symbol that generates a terminal string :

3.2.3 Parse Trees vs. Abstract Syntax Trees

A parse tree is a concrete graphical representation of a derivation:

AspectParse Tree (Concrete Syntax Tree)Abstract Syntax Tree (AST)
Grammar RepresentationContains every nonterminal and terminal, including syntactic delimiters (parentheses, commas, semicolons)Retains only essential semantic nodes; operators become interior nodes, operands become leaves
Node DensityHighly verbose and deep; contains extensive chain derivation nodes (e.g., )Compact and direct; eliminates single-child chain derivations
Compiler PhaseGenerated during syntax analysisConsumed by semantic analysis, intermediate code generation, and optimization

3.3 Parsing techniques: Top-down (recursive descent, LL(1)) and bottomup (LR(1))

Parsing strategies fall into two major categories: Top-Down Parsing and Bottom-Up Parsing.

Diagram: parsing techniquesText
Parsing Techniques
|
+-- Top-Down Parsers
|     +-- Recursive Descent (Backtracking)
|     +-- Predictive LL(1) (Non-backtracking)
|
+-- Bottom-Up Parsers
      +-- Operator Precedence
      +-- LR Family (Shift-Reduce)
            +-- LR(0)
            +-- SLR(1)
            +-- LALR(1)
            +-- Canonical LR(1)

3.3.1 Top-Down Parsing and LL(1) Grammars

A top-down parser attempts to construct the parse tree starting at the root () and working downward toward the leaves (input tokens).

1. FIRST and FOLLOW Sets

Top-down predictive parsers select the correct production rule without backtracking by computing and sets:

Definition

FIRST and FOLLOW Sets

If can be the rightmost symbol in a sentential form, the end-marker belongs to .

Rules for Computing FIRST:

  1. If is a terminal, .
  2. If is a production, then .
  3. If is a nonterminal and is a production:
    • Add all non- symbols of to .
    • If , add all non- symbols of , and so on.
    • If all derive , add to .

Rules for Computing FOLLOW:

  1. Place in , where is the start symbol.
  2. If there is a production , then everything in (except ) is in .
  3. If there is a production , or where , then everything in is in .

2. Construction of LL(1) Parsing Table

An LL(1) parser scans input from Left-to-right, constructs a Leftmost derivation, and uses 1 token of lookahead. For each production in grammar :

  1. For each terminal , add to .
  2. If , then for each terminal (including ), add to .
  3. All undefined entries are error entries.
Theorem

LL(1) Grammar Condition

A grammar is if and only if its parsing table has no multiple entries. Equivalently, for every pair of distinct productions :

  1. .
  2. At most one of and can derive .
  3. If , then .

3.3.2 Bottom-Up Parsing and LR(1) Parsers

A bottom-up parser constructs a parse tree starting from the input terminal string at the leaves and repeatedly performs reductions toward the start symbol .

1. Shift-Reduce Engine

The parser maintains a stack and an input buffer:

2. Canonical LR(1) Parsers

LR parsers read input from Left-to-right, construct a Rightmost derivation in reverse, and use tokens of lookahead:

where is a production, represents the parser stack position, and is the lookahead terminal.

AspectLL(1) ParsingLR(1) Parsing
Derivation OrderLeftmost derivationRightmost derivation in reverse
Grammar ClassSmallest class; cannot parse left-recursive grammarsLargest deterministic class; parses virtually all programming constructs
Decision PointMust predict production before seeing any of its bodyPostpones decision until the entire production body has been matched
Table ComplexityModest size ()Very large state count (often thousands of states before LALR merging)

3.4 Operator precedence

An operator precedence grammar is an -free context-free grammar with the special property that no production has an empty right-hand side () or two adjacent nonterminals on its right-hand side:

3.4.1 Precedence Relations

Between any pair of terminal symbols and , at most one of three precedence relations holds:

3.4.2 Precedence Functions

Storing an operator precedence table for terminals requires entries. To reduce table size, compilers map relations to two numerical precedence functions and mapping terminals to integers:

This compresses an table ( cells) into two arrays of length ( integers).


3.5 Handling issues like left recursion and ambiguity

3.5.1 Ambiguity in Grammars

Definition

Ambiguous Grammar

A context-free grammar is ambiguous if there exists at least one string that admits two or more distinct parse trees (or equivalently, two or more distinct leftmost derivations).

The Dangling-Else Problem

Consider the conditional statement grammar:

For the nested statement:

The else clause can syntactically associate with either the inner if or outer if, generating two distinct parse trees. Resolution: Compilers disambiguate by enforcing the semantic rule: each else matches the closest preceding unmatched then.

Text
Matched_Statement -> if E then Matched_Statement else Matched_Statement | Other
Open_Statement    -> if E then Statement
                   | if E then Matched_Statement else Open_Statement

3.5.2 Elimination of Left Recursion

A grammar is left-recursive if it has a nonterminal such that . Left recursion causes top-down predictive and recursive-descent parsers to loop infinitely.

Direct Left Recursion Elimination

Given direct left-recursive productions for :

where no begins with . Replace them with:

3.5.3 Left Factoring

When two productions for a nonterminal share a common prefix, a predictive top-down parser cannot decide which production to choose based on token of lookahead:

Transformation (Left Factoring):


Worked Examples

Example 1

1

Consider the standard arithmetic expression grammar:

  1. Eliminate left recursion.
  2. Compute and sets for all nonterminals.
  3. Construct the parsing table.

Eliminating Left Recursion: Applying the transformation rule:

Computing FIRST and FOLLOW Sets:

  • FIRST Sets:
  • FOLLOW Sets:
    • (Start symbol gets , and is followed by ` in )

Constructing LL(1) Parsing Table:

Answer:

The left-recursion-free grammar produces single-entry table cells across all rows, confirming that arithmetic expressions with precedence and parentheses form an language.

Example 2

2

Construct the canonical collection of item sets for the augmented grammar:

Determine the total number of states and verify how LALR(1) merging reduces the state count.

Computing Canonical LR(1) Item Sets:

  • State :
  • Transitions from :
    • (Accepting state)
  • Transitions from :
  • Transitions from :
    • (loop)
  • Transitions from :
    • (loop)

Total canonical states ( through ).

LALR(1) State Merging: Comparing item cores (ignoring lookahead terminals):

  • and have identical cores merge into with lookaheads .
  • and have identical cores merge into with lookaheads .
  • and have identical cores merge into with lookaheads .

Number of merged states pairs ( states merged into ). Resulting states:

Specifically: ( total states).

Answer:

The canonical collection has states. Merging states with identical cores reduces the automaton to states without introducing reduce-reduce conflicts.

Example 3

3

Demonstrate that the grammar is ambiguous by exhibiting two distinct leftmost derivations for the string .

Derivation 1 (Leftmost):

Here, the first production applied is .

Derivation 2 (Leftmost):

Wait, the first derivation rewrote the inner and trailing . In the second derivation, the first nonterminal is expanded to , producing the exact same terminal string with a fundamentally different parse tree shape.

Answer:

Since the terminal string admits two structurally distinct parse trees, the grammar is ambiguous.


Exercises

Practice Exercises — Syntax Analysis and Parsing

Question 1

Compare , , , and grammars in terms of language recognition power, table construction complexity, and conflict occurrence.

Hierarchy of Parser Power: The language inclusion hierarchy is strictly ordered:

Every language can be parsed by , but can handle left-recursive and much broader classes of context-free grammars.

Comparison Dimensions:

  • Table Size: , , and have compact table sizes ( or several hundred states). Canonical generates an order of magnitude more states ( states) because items with identical cores but different lookaheads are kept split.
  • Conflict Handling:
    • places reduce actions under , often producing spurious shift-reduce conflicts where lookaheads are actually impossible.
    • merges states with identical cores; it never creates new shift-reduce conflicts, but can occasionally introduce reduce-reduce conflicts.
    • resolves all deterministic context-free conflicts with lookahead.
Answer:

is the most powerful but has the largest state table; merges states with identical cores to match table size while retaining nearly all power; is top-down and requires left-factored, non-left-recursive grammars.

Question 2

Define a handle in shift-reduce parsing. Why is handle pruning equivalent to finding a rightmost derivation in reverse?

Definition of a Handle: A handle of a right-sentential form (where ) is a production and a position in where may be replaced by to yield the previous right-sentential form in a rightmost derivation:

Here, at that specific location is the handle.

Equivalence to Reverse Rightmost Derivation: In a rightmost derivation, the last production applied always replaces a nonterminal immediately adjacent to the terminal prefix:

A bottom-up parser starts at , identifies handle , and reduces it to get . Repeating handle reductions sequentially yields the reverse sequence , which traces the rightmost derivation backwards.

Answer:

A handle is a substring in a right-sentential form that matches the RHS of a production whose reduction represents one step along the reverse rightmost derivation. Handle pruning systematically reverses the steps of a canonical rightmost derivation from input tokens back to the start symbol .

Question 3

Eliminate indirect and direct left recursion from the grammar:

Substituting Nonterminal into : Order nonterminals as . For , substitute the productions of into : Since , replacing in gives:

Now the productions for are:

Eliminating Direct Left Recursion on : Group left-recursive terms: . Non-left-recursive terms: . Applying the direct transformation:

Combined with , all left recursion is eliminated.

Answer:

The resulting left-recursion-free grammar is: ; ; .

Question 4

A programming language grammar is processed by both an generator (such as Yacc/Bison) and a canonical parser generator:

  1. The parser produces states.
  2. The canonical parser produces states.
  3. The language has terminal symbols, and each table entry occupies .

Calculate:

LALR(1) ACTION Table Memory:

Canonical LR(1) ACTION Table Memory:

Memory Ratio:

Answer:
  • table memory: .
  • Canonical table memory: .
  • Ratio: Canonical requires exactly more memory.
Question 5

Explain how shift-reduce conflicts and reduce-reduce conflicts arise in bottom-up parsing. Why does an ambiguous grammar always lead to parsing conflicts in both and tables?

Shift-Reduce and Reduce-Reduce Conflicts:

  • Shift-Reduce Conflict: In a parser state, the parser cannot decide whether to shift the next input symbol onto the stack or reduce the current top-of-stack handle using a production . Example: dangling else where lookahead else can be shifted (bind to inner if) or reduced (terminate inner if).
  • Reduce-Reduce Conflict: In a parser state, the top of the stack matches the right-hand sides of two distinct productions ( and ), and the lookahead terminal is valid for reducing under both productions.

Impact of Ambiguity: An ambiguous grammar generates multiple parse trees for the same sentence.

  • In , multiple parse trees mean multiple productions can predictively expand a nonterminal on the same lookahead, placing multiple rules in cell .
  • In , multiple parse trees mean the parser arrives at a configuration where shifting a terminal or reducing one of two handles leads to different valid rightmost derivations, triggering inevitable shift-reduce or reduce-reduce conflicts.

Thus, no ambiguous grammar can ever be or .

Answer:

Shift-reduce conflicts occur when shifting and reducing are both valid next moves; reduce-reduce conflicts occur when two distinct productions are eligible for reduction. Ambiguity inherently guarantees conflicts because a deterministic parser cannot choose between two equally valid parse trees with lookahead.

← Lexical Analysis (part 2: 2.4–2.6)Syntax-Directed Translation and Semantic Analysis (part 1: 4.1–4.4) →