3.1 CFG, Derivation Trees, and Ambiguity: Ensuring Nested Structures Have a Single Meaning

Finite state is insufficient for unrestricted nesting. Start with the rules: how can finite productions describe (())() and give 1 + 2 * 3 its intended grouping? If one token sequence grows two different trees, later calculations may disagree.

Learning Objectives

• Write context-free grammars and perform derivations;
• Distinguish between sentential forms, sentences, derivations, and parse trees;
• Identify grammatical ambiguity;
• Express operator precedence and associativity using grammar hierarchy.

1. Context-Free Grammar

A context-free grammar remains a quadruple:

$$G=(V,\mathrm{\Sigma },P,S),$$

but each production rule must have a single non-terminal on the left-hand side:

$$A\to \alpha ,A\in V,\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }.$$

"Context-free" means that whenever an instance of $A$ appears, it can be replaced according to the rule, without needing to inspect what comes before or after it. It does not imply that program structure lacks context, nor that semantic analysis can be entirely divorced from environment state.

Balanced parentheses can be generated by the following grammar:

S → ( S ) S | ε

The first segment S handles the inner parentheses, while the second segment S manages subsequent adjacent parenthetical sequences:

S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ⇒ (())S
  ⇒ (())(S)S ⇒ (())()S ⇒ (())()

2. Sentential Forms, Sentences, and Derivation Order

A string derived from the start symbol in zero or more steps is a sentential form. It may contain terminals, nonterminals, or both. A sentential form that contains no nonterminals is called a sentence.

If at each step the leftmost nonterminal is replaced, the derivation is called a leftmost derivation. If the rightmost nonterminal is replaced at each step, it is called a rightmost derivation. Different replacement orders may simply reflect different traversals of the same parse tree and do not automatically imply ambiguity.

For example:

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

The leftmost derivation of id + id * id is:

E ⇒ E + T
  ⇒ T + T
  ⇒ F + T
  ⇒ id + T
  ⇒ id + T * F
  ⇒ id + F * F
  ⇒ id + id * F
  ⇒ id + id * id

3. Parse Trees Preserve Structure

The root node of a syntax tree is the start symbol, internal nodes represent nonterminals, and leaves read left to right form the input string, with $\epsilon$ leaves contributing no characters. The layered grammar shown above places multiplication in a deeper T subtree, resulting in:

       E
     / | \
    E  +  T
    |    /|\
    T   T * F
    |   |   |
    F   F   id
    |   |
   id  id

Parsers typically do not pass the full, concrete syntax tree directly to subsequent stages. Parentheses, semicolons, and intermediate nonterminals may be useful for parsing and analysis, but not all of them need to be preserved; Chapter 6 will compress this structure into an abstract syntax tree (AST).

4. Ambiguity in Grammars

If a single sentence can be parsed into two different syntax trees (equivalently, two distinct leftmost derivations) the grammar is ambiguous.

E → E + E | E * E | id

For id + id * id, the expression can be interpreted as either:

id + (id * id)

or

(id + id) * id

This is not a problem that a parser can reliably resolve by arbitrarily choosing one interpretation. Language specifications must define operator precedence and associativity, and even then, the grammar or parser configuration must be carefully designed to enforce correct parsing behavior.

The language and the grammar must be separated: the same language may have both ambiguous and unambiguous grammars. Moreover, some context-free languages are inherently ambiguous, there exists no unambiguous context-free grammar that can describe them.

5. Using Layers to Express Precedence

Layered grammar:

Expr   → Expr + Term | Term
Term   → Term * Factor | Factor
Factor → ( Expr ) | id

Factor represents an identifier or parenthesized expression. Term combines these factors through multiplication, making multiplication bind more tightly than addition. This specifies tree structure, not which parsing step must execute first. Left recursion naturally produces left-associative structures for consecutive subtractions:

Expr → Expr - Term | Term

a - b - c parses as (a - b) - c. If exponentiation is required to be right-associative, it can be defined as:

Power → Primary ^ Power | Primary

The grammar structure expresses the language's semantics and should not be altered merely to accommodate a particular parser. If recursive descent parsing cannot directly handle left recursion, the language's meaning and binding behavior must be preserved through transformation (such as restructuring to eliminate left recursion) or an iterative implementation at the appropriate layer should be used instead.

6. Dangling else

Grammar:

Stmt → if ( Expr ) Stmt
     | if ( Expr ) Stmt else Stmt
     | other

Input:

if (a) if (b) x else y

else can pair with either the inner or outer if. Most languages specify that it binds to the nearest unmatched if. This rule can be encoded using matched/unmatched nonterminals, or implemented via explicit conflict resolution rules in an LR parser. The key is consistency across grammar, parser behavior, and formatting tools.

A classic rewrite is:

Stmt      → Matched | Unmatched
Matched   → if ( Expr ) Matched else Matched | other
Unmatched → if ( Expr ) Stmt
          | if ( Expr ) Matched else Unmatched

7. Grammar Transformations Don't Guarantee Ambiguity Elimination

Recursive descent parsers often require eliminating direct left recursion:

A → A α | β

When $\alpha$ is nonempty and the $\beta$ alternatives do not begin with $A$, rewrite it as:

A → β A'
A' → α A' | ε

When there's a common prefix, left factoring can be applied:

A → α β | α γ

Rewritten as:

A → α A'
A' → β | γ

This handles only the displayed direct left recursion. Indirect left recursion, recursion hidden by nullable productions, and FIRST/FOLLOW conflicts still need checking.

These transformations primarily improve predictive parsing conditions. They do not automatically eliminate all ambiguity and may alter the parse-tree shape. If AST construction depends on the original structure, semantic actions must be adjusted accordingly.

8. General CFG Parsing and Engineering Subsets

Membership in a context-free grammar (CFG) is decidable. The CYK algorithm can parse CFGs after they are converted to Chomsky normal form, using dynamic programming and taking $O(n^3)$ time for a fixed grammar, or commonly $O(|P|n^3)$ when production count is included. Empty input needs a separate check for whether the start symbol derives $\epsilon$; Earley’s algorithm works with general CFGs as well and tends to perform faster depending on the grammar’s structure.

Tools can use LL/LR grammars with their corresponding algorithms, or PEGs with ordered-choice semantics. PEG is a separate formalism, not a CFG subclass; replacing alternatives with ordered choice can change the accepted language. It is incorrect to state broadly that "all CFGs can be parsed linearly"; linear performance depends on the grammar’s type, the parsing algorithm used, and how conflicts are resolved.

Common Misconceptions

• Different derivation orders imply ambiguity: Compare parse trees or leftmost derivations, not arbitrary replacement sequences.
• Eliminating left recursion eliminates ambiguity: These are fundamentally different concepts.
• Operator precedence belongs solely to the lexical phase: Tokens are identical; the grammar or parser rules encode precedence by determining the tree structure.
• Context-free grammars (CFGs) include type rules: Name binding and type checking typically require additional environments and semantic rules.

Exercise

1. Write a CFG for the list [id, id, ...], allowing for empty lists.
2. Write grammars for left-associative subtraction and right-associative exponentiation.
3. Draw the syntax tree for the layered grammar of id + id * id.
4. Use a matched/unmatched grammar derivation to parse a nested if, and verify the binding location of else.

Summary

CFG uses recursive productions to describe nested structures, and parse trees restore the string into a hierarchical relationship. Ambiguity means that the same input can be interpreted in multiple structural ways, this must be resolved by language rules, not by arbitrary parsing order.

In the next lesson, we equip this recursive structure with a machine: a finite state machine handles control flow, while a stack keeps track of unfinished nesting.