Context-Free Languages and Grammars
1. Why Beyond Regular
Regular languages cannot express nesting/matching (e.g. balanced {...}, aⁿbⁿ). Context-free languages (CFLs) use a stack and describe programming syntax — expressions, statements, blocks.
2. CFG Definition — 4-tuple (V, T, P, S)
- V: variables/non-terminals (e.g. E, Stmt)
- T: terminals/tokens (e.g. id, +, {, })
- P: productions
A → α - S: start symbol
Example — arithmetic:
E → E + T | T
T → T * F | F
F → ( E ) | id | num
Derivation for id + id * id:
E ⇒ E+T ⇒ T+T ⇒ F+T ⇒ id+T ⇒ id+T*F ⇒ id+F*F ⇒ id+id*id
3. Parse Tree vs Syntax Tree
parse tree (full): syntax tree (abstract):
E +
E + T / \
T T*F id *
id id id / \
id id
Parse tree shows every derivation step; syntax tree keeps only operators/operands.
4. CFL Properties
- Closed under ∪, concatenation, * — not under ∩, complement.
- Decidable: membership via CYK / PDA; ambiguity undecidable in general.
5. Exam Points
- Define CFG with example + derivation + parse tree — 7 marks, very frequent.
- Why regular insufficient, CFG needed — 3 marks, frequent.
- Parse tree vs syntax tree difference — 3-5 marks, frequent.