Properties and Applications of Context-Free Languages

Non-CFLs, deterministic CFLs, and predictive parsing

Properties of Context-Free Languages

Some languages are not context-free

Pushdown automata are more powerful than finite automata, but one stack still imposes limits. A stack is well suited to one nested or matched dependency; it struggles when several independent, unbounded relationships must be enforced simultaneously.

Examples of languages that are not context-free include:

\[ \{a^ib^ic^i:i\ge1\}, \]

\[ \{ww:w\in\{a,b\}^*\}, \]

and

\[ \{xcx:x\in\{a,b\}^*\}. \]

The difficulties are instructive:

• \(a^ib^ic^i\) requires one count to agree across three separated blocks;
• \(ww\) requires remembering an arbitrary first half in its original order;
• \(xcx\) requires reproducing an arbitrary string rather than its reversal; and
• semantic programming-language requirements such as “declare a variable before use” or “the number of arguments must match the number of parameters” may depend on information beyond context-free syntax.

Examples motivating the boundary of the context-free languages.

There is a pumping lemma for context-free languages, but its decomposition is more complicated than the regular pumping lemma because a PDA can coordinate two regions of a string using its stack. Other tools, such as closure arguments and Ogden’s lemma, are also useful for proving that languages are not context-free.

Closure properties

The context-free languages are closed under the three regular operations:

\[ L_1\cup L_2, \qquad L_1L_2, \qquad L_1^*. \]

These closures follow directly from CFG constructions or nondeterministic PDA constructions.

However, CFLs are not closed under intersection or complement.

Not closed under intersection

Consider

\[ L_1=\{a^ib^ic^j:i,j\ge1\} \]

and

\[ L_2=\{a^ib^jc^j:i,j\ge1\}. \]

Each language is context-free: \(L_1\) matches the numbers of as and bs, while \(L_2\) matches the numbers of bs and cs. But

\[ L_1\cap L_2 = \{a^ib^ic^i:i\ge1\}, \]

which is not context-free. Therefore, CFLs are not closed under intersection.

Not closed under complement

Suppose CFLs were closed under complement. Because they are closed under union, De Morgan’s law would give

\[ L_1\cap L_2 = \overline{\overline{L_1}\cup\overline{L_2}}, \]

which would make them closed under intersection. This contradicts the preceding example. Therefore, CFLs are not closed under complement.

Closure properties of context-free languages.

Intersection with a regular language

CFLs are not closed under intersection with one another, but they satisfy an important restricted closure property:

Theorem. If \(L_1\) is context-free and \(L_2\) is regular, then \(L_1\cap L_2\) is context-free.

Product construction intuition

Let a PDA recognize \(L_1\) and a DFA recognize \(L_2\). Construct a new PDA whose finite control stores a pair

\[ (q_P,q_D), \]

where \(q_P\) is the current PDA state and \(q_D\) is the current DFA state. The new machine:

• simulates the PDA’s state and stack behavior;
• updates the DFA component whenever an input symbol is consumed; and
• accepts only when both components accept.

This succeeds because only one component uses a stack. Attempting the same construction with two arbitrary PDAs would require tracking two independent stacks, which is more powerful than a PDA.

Why familiar DFA closure proofs fail for PDAs

Intersection

For DFAs, the product construction stores a pair of states. For PDAs, simulating two machines would require a pair of states and two stacks. A standard PDA has only one stack, and encoding two independently changing stack tops in one stack is not generally possible.

Complement

For a complete DFA, every input follows one computation path, so swapping accepting and rejecting states produces the complement.

For an NPDA, acceptance means that some branch accepts. Swapping final and nonfinal states does not transform

\[ \exists\text{ an accepting branch} \]

into

\[ \text{no branch accepts}. \]

Branches can also crash, loop through \(\varepsilon\)-moves, or finish in different configurations. The DFA argument therefore does not carry over.

Deterministic Context-Free Languages

DPDAs and DCFLs

A deterministic pushdown automaton (DPDA) has at most one legal move from any configuration. Informally, it may not face a choice between multiple transitions, including a choice between consuming input and taking an \(\varepsilon\)-transition.

A language recognized by some DPDA is a deterministic context-free language (DCFL).

Examples include:

• balanced delimiters;
• \(\{a^nb^n:n\ge0\}\); and
• \(\{w\#w^R:w\in\Sigma^*\}\), where # marks the midpoint.

Unmarked palindromes require guessing the midpoint and illustrate why nondeterminism can be essential.

The containment is strict:

\[ \mathrm{DCFL}\subsetneq\mathrm{CFL}. \]

Unlike CFLs in general, DCFLs are closed under complement, subject to the usual care that the DPDA be placed in a suitable complete form and that end-of-input behavior be explicit.

Using complement to separate DCFL from CFL

Because DCFLs are closed under complement, any CFL whose complement is not context-free cannot be deterministic context-free.

Consider

\[ A=\{a^ib^jc^k:i\ne j\text{ or }j\ne k,\ i,j,k\ge0\}. \]

This language is context-free: it is a union of languages that detect one of the two inequalities.

Assume for contradiction that \(A\) is a DCFL. Then \(\overline{A}\) would also be a DCFL and hence a CFL. Intersect it with the regular language \(a^*b^*c^*\):

\[ \overline{A}\cap a^*b^*c^* = \{a^nb^nc^n:n\ge0\}. \]

Because CFLs are closed under intersection with regular languages, the right-hand language would be context-free. It is not. Therefore, \(A\) is context-free but not deterministic context-free.

A closure-based proof that a particular CFL is not a DCFL.

Applications: Compilers

From source code to structure

Formal-language theory underlies the front end of a compiler:

source code → scanner → token stream → parser → parse tree

The scanner and parser phases of a compiler.

The two phases solve different problems:

• Lexical analysis groups characters into tokens.
• Parsing organizes those tokens according to a context-free grammar.

Regular and context-free models therefore work together rather than compete.

Scanning: regular structure

A scanner, or lexer, recognizes tokens such as:

• identifiers and reserved words;
• numeric literals;
• string literals;
• punctuation and operators; and
• comments.

Token classes are commonly specified with regular expressions. For example, a simplified PHP-style variable token might use

\$[A-Za-z0-9]+

A tool can convert such patterns into finite automata and generate scanner code automatically.

The scanner usually discards irrelevant whitespace and emits a token stream such as

IDENTIFIER  PLUS  INTEGER  SEMICOLON

This abstraction allows the parser to reason about syntactic categories rather than individual characters.

Parsing: context-free structure

A parser determines whether the token stream can be derived from the programming language’s grammar and, if so, constructs a parse tree.

Consider

\[ expr\rightarrow expr+digit\mid expr-digit\mid digit, \]

\[ digit\rightarrow0\mid1\mid2\mid3\mid4\mid5\mid6\mid7\mid8\mid9. \]

A leftmost derivation of 9-5+2 is

\[ expr \Rightarrow expr+digit \Rightarrow expr-digit+digit \Rightarrow digit-digit+digit \Rightarrow9-digit+digit \Rightarrow9-5+digit \Rightarrow9-5+2. \]

A parse tree and leftmost derivation for 9-5+2.

The parse tree captures the program’s hierarchical structure and guides later phases such as semantic analysis and code generation.

Why the generic PDA construction is impractical

The proof that every CFG has an equivalent PDA is mathematically important, but the constructed PDA is nondeterministic: when a variable is on top of the stack, it guesses which production to apply.

A real parser cannot efficiently simulate every possible branch. Compiler design therefore asks a more practical question:

Can the next production be chosen deterministically from the current variable and a small amount of upcoming input?

This is the role of lookahead and parse tables.

Predictive parsing example

Consider the grammar for balanced square brackets followed by an end marker \(\dashv\):

\[ S\rightarrow T\dashv, \]

\[ T\rightarrow[T]T\mid\varepsilon. \]

When expanding \(T\):

• if the next symbol is [, use \(T\rightarrow[T]T\);
• if the next symbol is ] or \(\dashv\), use \(T\rightarrow\varepsilon\).

One symbol of lookahead is sufficient to choose the correct production.

Parse tables

A predictive parse table indexes a production by:

• the variable on top of the parser’s stack; and
• the next input symbol.

For the bracket grammar:

Variable	[	]	\(\dashv\)
\(S\)	\(S\rightarrow T\dashv\)	—	\(S\rightarrow T\dashv\)
\(T\)	\(T\rightarrow[T]T\)	\(T\rightarrow\varepsilon\)	\(T\rightarrow\varepsilon\)

A one-symbol-lookahead parse table for balanced brackets.

A table entry with one production gives a deterministic move. A missing entry reports a syntax error. Multiple competing productions indicate that the grammar is not LL(1) in its current form.

In a full compiler course, the table is constructed from FIRST and FOLLOW sets:

• \(FIRST(\alpha)\) contains tokens that may begin strings derived from \(\alpha\);
• \(FOLLOW(A)\) contains tokens that may immediately follow variable \(A\); and
• nullable productions use FOLLOW information to decide when \(A\rightarrow\varepsilon\) is appropriate.

The problem of left recursion

The equivalent balanced-bracket grammar

\[ T\rightarrow T[T]\mid\varepsilon \]

is left recursive: \(T\) can immediately derive a sentential form beginning with \(T\) again.

A top-down parser attempting to expand \(T\) may repeatedly apply

\[ T\Rightarrow T[T]\Rightarrow T[T][T]\Rightarrow\cdots \]

without consuming input. Lookahead cannot determine how many recursive expansions should occur, so the parser may loop forever.

Eliminating immediate left recursion

Suppose

\[ A\rightarrow A\alpha\mid\beta, \]

where \(\beta\) does not begin with \(A\). Replace it with

\[ A\rightarrow\beta A', \]

\[ A'\rightarrow\alpha A'\mid\varepsilon. \]

The original grammar describes one \(\beta\) followed by zero or more \(\alpha\)s. The transformed grammar makes this repetition explicit without left recursion.

For

\[ T\rightarrow T[T]\mid\varepsilon, \]

we obtain

\[ T\rightarrow U, \]

\[ U\rightarrow[T]U\mid\varepsilon. \]

Equivalently, the extra variable can be omitted and the earlier grammar \(T\rightarrow[T]T\mid\varepsilon\) used directly.

The standard transformation for immediate left recursion.

More general algorithms handle indirect left recursion involving several variables.

The problem of common prefixes

Consider the schematic grammar

\[ decision\rightarrow\texttt{if then} \mid \texttt{if then else}. \]

After seeing if, one token of lookahead cannot determine which production was intended because both alternatives begin with the same prefix.

The solution is left factoring.

Left factoring

In general, replace

\[ A\rightarrow\alpha\beta_1\mid\alpha\beta_2 \]

with

\[ A\rightarrow\alpha A', \]

\[ A'\rightarrow\beta_1\mid\beta_2. \]

The parser consumes the common prefix \(\alpha\) before deciding between the remaining alternatives.

For the schematic decision grammar:

\[ decision\rightarrow\texttt{if then}\ decision', \]

\[ decision'\rightarrow\texttt{else}\mid\varepsilon. \]

Left factoring delays the choice until enough input has been consumed to distinguish the alternatives.

Note

This toy grammar illustrates common-prefix removal but suppresses the conditions and statement bodies present in a real if grammar. The well-known “dangling else” problem also involves ambiguity and requires an appropriate grammar or language rule associating an else with an if.

LL(1) grammars

An LL(1) parser:

• scans the input from Left to right;
• constructs a Leftmost derivation; and
• uses 1 token of lookahead.

An LL(\(k\)) parser uses at most \(k\) tokens of lookahead to choose each production.

Removing left recursion and left factoring are important grammar transformations for predictive parsing, but they do not guarantee that every unambiguous CFG becomes LL(1). Some languages require more lookahead or a different parsing strategy, and some context-free languages have no LL(\(k\)) grammar for any fixed \(k\).

Likewise, not every important programming-language rule is context-free. Requirements involving declarations, types, scopes, and agreement between distant program elements are typically checked during semantic analysis, after parsing has established the syntactic structure.

Putting the pieces together

Compiler concern	Formal model	Typical implementation
Token patterns	Regular languages	Regex, DFA-based scanner
Nested syntax	Context-free languages	CFG and parser
Predictive production choice	Deterministic parsing discipline	LL(1) table with lookahead
Declarations, types, and scope	Context-sensitive semantic rules	Symbol tables and semantic analysis

Theory of computation provides the boundaries and constructions; compiler design chooses representations that are efficient and useful in practice.

Check your understanding

1. Why does intersecting two CFLs suggest the need for two stacks?
2. Why does swapping accepting and rejecting states fail for an NPDA?
3. Why are DCFLs closed under complement even though CFLs are not?
4. What roles do regular and context-free languages play in a compiler?
5. Why is the generic CFG-to-PDA construction nondeterministic?
6. How does lookahead make predictive parsing deterministic?
7. Why does left recursion cause a top-down parser to loop?
8. What problem does left factoring solve?
9. What do the two letters and the number in “LL(1)” mean?