Context-Free Languages in Compiler Design

Introduction to Context-Free Languages

A Context-Free Language (CFL) is a language that can be generated by a Context-Free Grammar (CFG). These languages form the backbone of programming language syntax and are essential for understanding how compilers parse source code. Every programming language you use daily — C, Java, Python — has its syntax defined by a context-free grammar.

Context-free languages sit at Level 2 in the Chomsky hierarchy, more powerful than regular languages but less powerful than context-sensitive languages. The key distinction is that CFLs can handle nested structures like balanced parentheses, matching begin-end blocks, and recursive definitions that regular languages cannot express.

Formal Definition

A language L is context-free if and only if there exists a context-free grammar G such that L = L(G).

A Context-Free Grammar G is defined as a 4-tuple: G = (V, T, P, S) where:

• V = set of variables (non-terminals)
• T = set of terminal symbols
• P = set of production rules of the form A → α, where A ∈ V and α ∈ (V ∪ T)*
• S = start symbol, S ∈ V

Relationship with Pushdown Automata

Every CFL is accepted by some Pushdown Automaton (PDA), and every language accepted by a PDA is context-free. This equivalence is fundamental:

Examples of Context-Free Languages

Language of Balanced Parentheses

Language of Equal a's and b's

Arithmetic Expressions

Closure Properties of CFLs

Context-free languages are closed under certain operations but not others:

Proof of Union Closure

If L1 = L(G1) with start symbol S1 and L2 = L(G2) with start symbol S2, then L1 ∪ L2 is generated by:

• Add new start symbol S
• Add productions: S → S1 | S2
• Include all productions from G1 and G2

Proof of Concatenation Closure

For L1·L2:

• Add new start symbol S
• Add production: S → S1 S2
• Include all productions from both grammars

Pumping Lemma for Context-Free Languages

The pumping lemma is used to prove that certain languages are NOT context-free.

Statement: If L is a context-free language, then there exists a constant p (pumping length) such that for any string w ∈ L with |w| ≥ p, w can be written as w = uvxyz where:

1. |vxy| ≤ p
2. |vy| ≥ 1 (v and y are not both empty)
3. For all i ≥ 0, uvⁱxyⁱz ∈ L

Using Pumping Lemma to Prove Non-CFL

Example: Prove L = { aⁿbⁿcⁿ | n ≥ 0 } is not context-free.

Parse Trees and Ambiguity

A parse tree visually represents a derivation:

A grammar is ambiguous if there exist two different parse trees for the same string.

Deterministic vs Non-deterministic CFLs

• DCFL (Deterministic CFL): Accepted by a deterministic PDA. Most programming languages fall here.
• Non-deterministic CFL: Requires a non-deterministic PDA. Example: L = {ww^R | w ∈ {a,b}*}

DCFLs are NOT closed under union or intersection, but ARE closed under complementation.

Applications in Compiler Design

1. Syntax Definition: Programming language grammars are CFGs
2. Parser Construction: LL and LR parsers work on deterministic CFLs
3. Nested Structures: Function calls, loops, conditionals
4. Type Expressions: Recursive type definitions

Chomsky Normal Form (CNF)

Every CFL (not containing ε) can be generated by a grammar in CNF where every production is of the form:

• A → BC (two non-terminals)
• A → a (single terminal)

Greibach Normal Form (GNF)

Every CFL (not containing ε) can be generated by a grammar in GNF where every production is of the form:

• A → aα, where a is a terminal and α ∈ V*

GNF is useful because it ensures exactly one terminal is generated per derivation step, making it suitable for top-down parsing.

CFL Decision Properties

Interview Questions

1. Q: Can the intersection of two CFLs be non-context-free?

A: Yes. Consider L1 = {aⁿbⁿcᵐ | n,m ≥ 0} and L2 = {aᵐbⁿcⁿ | n,m ≥ 0}. Both are CFLs, but L1 ∩ L2 = {aⁿbⁿcⁿ | n ≥ 0} which is not context-free.

1. Q: Why are programming languages based on CFGs rather than regular grammars?

A: Programming languages have nested structures (balanced parentheses, nested if-else, recursive function calls) that require a stack-based memory — something regular languages cannot express. CFGs with their recursive production rules naturally model these nested constructs.

1. Q: What is the time complexity of CFL membership testing?

A: The CYK algorithm tests membership in O(n³) time for general CFGs. For unambiguous grammars parsed by LL(1) or LR(1) parsers, it is O(n) — linear time.

1. Q: How do you prove a language is context-free?

A: Either construct a CFG that generates the language, or construct a PDA that accepts it. For example, to show {aⁿb²ⁿ | n ≥ 0} is CFL, provide grammar: S → aSbb | ε.

1. Q: What is the relationship between inherently ambiguous languages and DCFLs?

A: An inherently ambiguous CFL has no unambiguous grammar. Such languages cannot be DCFLs because every DCFL has an unambiguous grammar. Example: L = {aⁿbⁿcᵐdᵐ} ∪ {aⁿbᵐcᵐdⁿ} is inherently ambiguous.