CD Notes
Comprehensive introduction to syntax analysis covering the role of parsers, parsing techniques classification, grammar representation, and the relationship between parsers and lexers.
What is Parsing?
Parsing (syntax analysis) is the second phase of compilation that takes a stream of tokens from the lexer and determines whether they form a valid sentence according to the grammar of the programming language. It builds a parse tree or abstract syntax tree representing the hierarchical structure of the program.
Role of the Parser
Context-Free Grammars for Parsing
| E | E + T | T |
| T | T * F | F |
| F | ( E ) | id |
Classification of Parsing Techniques
Top-Down vs Bottom-Up Parsing
| Grammar: E | T + E | T, T → id |
| String | id + id + id |
| ├ | T + E from start symbol |
| │ ├ | id + E |
| │ │ ├ | T + E |
| │ │ │ ├ | id + E |
| │ │ │ │ └ | T |
| │ │ │ │ └ | id |
| T + T + E | ... (reduce T to E, then T+E to E) |
| Top-Down | Leftmost derivation (expand leftmost non-terminal) |
| Bottom-Up | Rightmost derivation in reverse (reduce rightmost handle) |
Parser Output: Parse Trees
Error Handling in Parsing
Types of syntax errors
1. Missing token: if (x > 0 ← missing )
2. Extra token: x = y + * z ← unexpected *
3. Mismatched: { if(x) }... ← wrong structure
4. Wrong order: int = x 5; ← declaration syntax wrong
Error recovery strategies
┌────────────────────────────────────────────────────┐
│ Panic Mode: Skip tokens until synchronizing token │
│ (semicolons, closing braces, keywords) │
├────────────────────────────────────────────────────┤
│ Phrase Level: Local correction (insert/delete) │
│ Missing semicolon → insert it, continue │
├────────────────────────────────────────────────────┤
│ Error Productions: Add grammar rules for errors │
│ stmt → error ; (skip to next semicolon) │
├────────────────────────────────────────────────────┤
│ Global Correction: Find minimum edit distance │
│ (too expensive for practical use) │
└────────────────────────────────────────────────────┘
Derivations and Parsing
Leftmost Derivation (used by top-down parsers)
E ⟹ E + T ⟹ T + T ⟹ F + T ⟹ id + T ⟹ id + T*F ⟹ id + F*F ⟹ id + id*F ⟹ id + id*id
Rightmost Derivation (used by bottom-up parsers)
E ⟹ E + T ⟹ E + T*F ⟹ E + T*id ⟹ E + F*id ⟹ E + id*id ⟹ T + id*id ⟹ F + id*id ⟹ id + id*id
Each derivation gives the same parse tree but different derivation order.
Top-down parsers construct leftmost derivations.
Bottom-up parsers discover rightmost derivations in reverse.
FIRST and FOLLOW Sets Preview
Parser Generators
| yacc/bison | LALR(1) parser generators |
| ANTLR | LL(*) parser generator |
| PEG parsers | Parsing Expression Grammars |
| Input | Grammar specification + semantic actions |
| Output | Parser source code (C, Java, etc.) |
| expr | expr '+' term { $$ = $1 + $3; } |
| term | term '*' factor { $$ = $1 * $3; } |
Interview Questions
- Q: Why is parsing done separately from lexical analysis?
A: Separation of concerns: lexers handle character-level patterns (regular languages), parsers handle structure (context-free languages). This modularity simplifies both, allows different implementation techniques (DFA vs PDA), and makes the compiler more maintainable. The lexer also eliminates whitespace and comments before the parser sees tokens.
- Q: What is the difference between a parse tree and an AST?
A: A parse tree includes every grammar symbol (all non-terminals and terminals), making it verbose. An AST retains only semantically meaningful nodes (operators, operands, control structures), discarding grammar artifacts. Parse trees reflect the grammar; ASTs reflect the program's meaning.
- Q: Why can't regular expressions be used for parsing?
A: Regular expressions cannot count or match nested structures (balanced parentheses, nested blocks). Parsing requires context-free grammars which have recursive rules and use a stack (PDA). For example, matching nested if-else or { } blocks requires remembering nesting depth — impossible for finite automata.
- Q: What makes a grammar ambiguous and why does it matter?
A: A grammar is ambiguous if some string has two or more parse trees. This matters because different parse trees may give different meanings (e.g., id-id-id could associate left or right). Parsers need unambiguous grammars (or disambiguation rules) to produce a unique interpretation.
- Q: How do practical parsers handle errors gracefully?
A: They use error recovery to continue parsing after an error, finding as many errors as possible in one pass. Panic mode skips to a synchronization point (;, }, end). Production-level recovery inserts or deletes tokens locally. Good error messages include the unexpected token, expected tokens, and source location.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Introduction to Parsing in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, analysis, introduction, parsing
Related Compiler Design Topics