Definition

A Context-Free Grammar (CFG) is a 4-tuple (V, T, P, S) — non-terminals, terminals, production rules, start symbol — used to define the syntax of programming languages (more expressive than regular grammars; can express nested/recursive structures like matched parentheses).

Key Points

• Why not regular expressions for syntax? Regex/FA cannot count or match nested structures (e.g., balanced brackets) — CFGs can, via recursive production rules.
• Chomsky Hierarchy (classification by generative power): Type 0 (unrestricted) ⊃ Type 1 (context-sensitive) ⊃ Type 2 (context-free) ⊃ Type 3 (regular). Programming language syntax sits at Type 2.
• Derivation: applying productions to expand the start symbol into a string — leftmost derivation (expand leftmost non-terminal first) vs rightmost derivation.
• Parse tree: graphical representation of a derivation.
• Ambiguous grammar: a grammar where some string has more than one parse tree / leftmost derivation — undesirable, usually rewritten (e.g., via precedence rules) to remove ambiguity.

Example

Grammar for simple arithmetic expressions:

E → E + E | E * E | ( E ) | id

This grammar is ambiguous (no precedence enforced) — id + id * id has two different parse trees depending on grouping.

📌 CSS Frequency: High — "define CFG, show it's ambiguous, construct a parse tree" is a recurring long question.

Model Answer (short)

"A context-free grammar consists of terminals, non-terminals, production rules, and a start symbol, and is used because it can express recursive/nested constructs that regular expressions cannot. A grammar is ambiguous if some string has two distinct parse trees; compilers typically rewrite such grammars using precedence and associativity rules to remove ambiguity before parsing."