CD Notes
Detailed guide to context-free grammars in compiler design covering formal definition, derivations, parse trees, grammar transformations, and their use in defining programming language syntax.
Formal Definition
A context-free grammar G is a 4-tuple G = (V, T, P, S) where V is the set of non-terminal symbols (variables), T is the set of terminal symbols (tokens), P is the set of production rules, and S is the start symbol. Each production has the form A → α where A is a non-terminal and α is a string of terminals and non-terminals.
Components of a Grammar
Example grammar for simple expressions
V = {E, T, F} Non-terminals
T = {id, num, +, *, (, )} Terminals (from lexer)
S = E Start symbol
P = { Productions:
E → E + T (addition)
E → T (single term)
T → T * F (multiplication)
T → F (single factor)
F → ( E ) (parenthesized expr)
F → id (identifier)
F → num (number)
}
Notation conventions
Capital letters (A, B, E, T): non-terminals
Lowercase letters (a, b, c): terminals
Greek letters (α, β, γ): strings of terminals and non-terminals
| separates alternatives: A → α | β means A → α and A → β
Derivations
| E ⟹ E + T (E | E + T) |
| ⟹ T + T (E | T) |
| ⟹ F + T (T | F) |
| ⟹ id + T (F | id) |
| ⟹ id + T * F (T | T * F) |
| ⟹ id + F * F (T | F) |
| ⟹ id + id * F (F | id) |
| ⟹ id + id * id (F | id) |
| E ⟹ E + T (E | E + T) |
| ⟹ E + T * F (T | T * F) |
| ⟹ E + T * id (F | id) |
| ⟹ E + F * id (T | F) |
| ⟹ E + id * id (F | id) |
| ⟹ T + id * id (E | T) |
| ⟹ F + id * id (T | F) |
| ⟹ id + id * id (F | id) |
Grammar Transformations
Left Recursion Elimination
| Problem | Left-recursive grammars cause infinite loops in top-down parsers. |
| A | Aα | β (left recursive) |
| A | βA' |
| A' | αA' | ε |
| E | E + T | T |
| E | T E' |
| E' | + T E' | ε |
| Original | Transformed: |
| E | E + T | T E → T E' |
| T | T * F | F E' → + T E' | ε |
| F | ( E ) | id T → F T' |
| T' | * F T' | ε |
| F | ( E ) | id |
Left Factoring
| Problem | Common prefixes cause ambiguity for predictive parsers. |
| A | αβ₁ | αβ₂ |
| A | αA' |
| A' | β₁ | β₂ |
| stmt | if expr then stmt else stmt |
| stmt | if expr then stmt stmt' |
| stmt' | else stmt | ε |
Augmented Grammars
| Original: S | ... |
| Augmented: S' | S$ (S' is new start, $ is end marker) |
| This gives a clear "done" signal when S' | S is reduced. |
Grammar for a Simple Language
| program | stmt_list |
| stmt_list | stmt ; stmt_list | stmt ; |
| stmt | assign_stmt | if_stmt | while_stmt | block |
| assign_stmt | id = expr |
| if_stmt | if ( expr ) stmt | if ( expr ) stmt else stmt |
| while_stmt | while ( expr ) stmt |
| block | { stmt_list } |
| expr | expr + term | expr - term | term |
| term | term * factor | term / factor | factor |
| factor | ( expr ) | id | num |
Sentential Forms and Sentences
Precedence and Associativity in Grammars
Encoding operator precedence
Higher precedence → deeper in grammar hierarchy
E → E + T (+ is lower precedence, higher in tree)
T → T * F (* is higher precedence, deeper in tree)
F → id (operands are deepest)
Encoding left associativity
E → E + T (left recursive → left associative)
id + id + id parses as (id + id) + id
Encoding right associativity
A → B = A (right recursive → right associative)
a = b = c parses as a = (b = c)
Interview Questions
- Q: Why are context-free grammars needed instead of regular grammars for parsing?
A: Programming languages have recursive, nested structures (expressions within expressions, blocks within blocks) that require the self-referencing capability of CFG productions. Regular grammars (Type 3) cannot express recursive nesting. CFGs with their stack-based recognition (PDA) naturally handle arbitrary nesting depth.
- Q: What is the significance of left recursion elimination?
A: Top-down parsers (recursive descent, LL) attempt to match the leftmost non-terminal first. Left recursion (A → Aα) causes the parser to call A repeatedly without consuming input — an infinite loop. Eliminating left recursion transforms the grammar into a form suitable for top-down parsing while preserving the generated language.
- Q: How does a grammar encode operator precedence?
A: By layering non-terminals: lower-precedence operators appear in higher-level (earlier) productions, and higher-precedence operators in lower-level productions. This forces the parser to build the tree with higher-precedence operations deeper (evaluated first). Multiple precedence levels require multiple non-terminal levels.
- Q: Can every context-free language be parsed efficiently?
A: General CFL membership is O(n³) via CYK algorithm. However, most programming languages are designed to be parseable in O(n) by LL(1) or LR(1) parsers. Grammars are carefully designed (or transformed) to fit these deterministic, linear-time parsing frameworks.
- Q: What is an ambiguous grammar and how is it resolved?
A: A grammar where some string has multiple parse trees. Resolution approaches: (1) rewrite the grammar to be unambiguous, (2) add disambiguation rules (precedence/associativity declarations in yacc), (3) choose a parsing technique that resolves conflicts deterministically (like shift preference in LR parsing).
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Context-Free Grammars for Syntax Analysis.
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, context, free
Related Compiler Design Topics