Syntax Analysis (Parsing)
Open in the Padhaiko app3.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).
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
- Syntactic Structure Verification: Validates that expressions, statements, declarations, and control-flow blocks satisfy language syntax rules.
- Syntax Tree Construction: Builds a hierarchical intermediate data structure (an Abstract Syntax Tree or parse tree) that reflects operator precedence, associativity, and statement nesting.
- Symbol Table Interaction: Coordinates with the symbol table to register variable declarations, function prototypes, and scope block boundaries.
- 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:
| Recovery Mode | Mechanism | Trade-Offs |
|---|---|---|
| Panic Mode | The 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 Recovery | The 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 Productions | Grammar 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 Correction | Algorithms 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
Context-Free Grammar (CFG)
A Context-Free Grammar (CFG) is a 4-tuple where:
- is a finite set of nonterminal symbols (syntactic variables representing sentence sets).
- is a finite set of terminal symbols (tokens emitted by the lexical analyzer), where .
- is a finite set of production rules of the form , where and .
- is the distinguished start symbol.
3.2.2 Derivations
A derivation is a sequence of production rule applications starting from the start symbol that generates a terminal string :
- If is a production, then represents a single derivation step.
- denotes a derivation in zero or more steps.
- Leftmost Derivation (): At every step, the leftmost nonterminal in the sentential form is rewritten.
- Rightmost Derivation (): At every step, the rightmost nonterminal is rewritten. A rightmost derivation in reverse is called a canonical derivation, which models bottom-up shift-reduce parsing.
3.2.3 Parse Trees vs. Abstract Syntax Trees
A parse tree is a concrete graphical representation of a derivation:
- The root node is labeled with the start symbol .
- Each interior node is labeled with a nonterminal symbol .
- The children of an interior node correspond, from left to right, to the symbols on the right-hand side of the production used in the derivation.
- Leaf nodes are labeled with terminals or . The concatenation of leaf labels from left to right forms the yield of the parse tree.
| Aspect | Parse Tree (Concrete Syntax Tree) | Abstract Syntax Tree (AST) |
|---|---|---|
| Grammar Representation | Contains every nonterminal and terminal, including syntactic delimiters (parentheses, commas, semicolons) | Retains only essential semantic nodes; operators become interior nodes, operands become leaves |
| Node Density | Highly verbose and deep; contains extensive chain derivation nodes (e.g., ) | Compact and direct; eliminates single-child chain derivations |
| Compiler Phase | Generated during syntax analysis | Consumed 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.
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:
FIRST and FOLLOW Sets
- : For any grammar string , is the set of terminals that begin strings derived from . If , then .
- : For a nonterminal , is the set of terminals that can appear immediately to the right of in some sentential form:
If can be the rightmost symbol in a sentential form, the end-marker belongs to .
Rules for Computing FIRST:
- If is a terminal, .
- If is a production, then .
- 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:
- Place in , where is the start symbol.
- If there is a production , then everything in (except ) is in .
- 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 :
- For each terminal , add to .
- If , then for each terminal (including ), add to .
- All undefined entries are error entries.
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 :
- .
- At most one of and can derive .
- 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:
- Shift: Pushes the current input terminal onto the stack.
- Reduce: Replaces a substring at the top of the stack matching the RHS of a production with its LHS nonterminal. This substring is called a handle.
- Accept: Halts when the stack holds only the start symbol and the input buffer is empty ().
- Error: Discovers a syntax error when no legal shift or reduce operation exists.
2. Canonical LR(1) Parsers
LR parsers read input from Left-to-right, construct a Rightmost derivation in reverse, and use tokens of lookahead:
- An item is of the form:
where is a production, represents the parser stack position, and is the lookahead terminal.
- Closure of an LR(1) item set : If , then for each production and each terminal , add to .
- GOTO function:
| Aspect | LL(1) Parsing | LR(1) Parsing |
|---|---|---|
| Derivation Order | Leftmost derivation | Rightmost derivation in reverse |
| Grammar Class | Smallest class; cannot parse left-recursive grammars | Largest deterministic class; parses virtually all programming constructs |
| Decision Point | Must predict production before seeing any of its body | Postpones decision until the entire production body has been matched |
| Table Complexity | Modest 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:
- : "yields precedence to" (terminal appears before a handle starting with ).
- : "has same precedence as" (both terminals belong to the same handle).
- : "takes precedence over" (terminal is the trailing end of a handle).
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
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.
Matched_Statement -> if E then Matched_Statement else Matched_Statement | Other
Open_Statement -> if E then Statement
| if E then Matched_Statement else Open_Statement3.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
1
Consider the standard arithmetic expression grammar:
- Eliminate left recursion.
- Compute and sets for all nonterminals.
- 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:
The left-recursion-free grammar produces single-entry table cells across all rows, confirming that arithmetic expressions with precedence and parentheses form an language.
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).
The canonical collection has states. Merging states with identical cores reduces the automaton to states without introducing reduce-reduce conflicts.
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.
Since the terminal string admits two structurally distinct parse trees, the grammar is ambiguous.
Exercises
Practice Exercises — Syntax Analysis and Parsing
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.
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.
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.
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 .
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.
The resulting left-recursion-free grammar is: ; ; .
A programming language grammar is processed by both an generator (such as Yacc/Bison) and a canonical parser generator:
- The parser produces states.
- The canonical parser produces states.
- The language has terminal symbols, and each table entry occupies .
Calculate:
- The memory consumed by the ACTION table under in kilobytes ().
- The memory consumed by the ACTION table under canonical in kilobytes ().
- The ratio of memory to memory.
LALR(1) ACTION Table Memory:
Canonical LR(1) ACTION Table Memory:
Memory Ratio:
- table memory: .
- Canonical table memory: .
- Ratio: Canonical requires exactly more memory.
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
elsewhere lookaheadelsecan be shifted (bind to innerif) or reduced (terminate innerif). - 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 .
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.