Parse Trees and Ambiguity

Hello! Welcome to the next lesson in our exploration of the Theory of Computation.

In the previous lesson, we learned how to generate strings using Context-Free Grammars (CFGs) through a sequential process called derivation. We focused on two systematic approaches: leftmost and rightmost derivations. While these linear sequences of steps are formally precise, they aren't always the most intuitive way to grasp the structure of a generated string.

This lesson introduces a more visual and hierarchical way to represent derivations: the parse tree. You've likely encountered similar concepts in your work with compilers, where Abstract Syntax Trees (ASTs) are used to represent the structure of source code. A parse tree serves a similar purpose, revealing the grammatical structure that a CFG imposes on a string.

Our primary goal is to learn how to construct parse trees from derivations and, crucially, use them to identify a significant problem in grammar design: grammatical ambiguity.

1. Visualizing Derivations: The Parse Tree

A parse tree (or derivation tree) is a graphical representation of a derivation. It neatly captures how the start symbol of a grammar derives a particular string, showing the application of production rules in a hierarchical structure.

The formal rules for constructing a parse tree are straightforward:

Root: The root node is labeled with the grammar's start symbol.
Interior Nodes: Every interior node is labeled with a non-terminal.
Leaf Nodes: Every leaf node is labeled with a terminal symbol or $ε$ .
Productions as Parent-Child Relationships: If an interior node is labeled $A$ , and its children are labeled $X_{1}, X_{2}, \dots, X_{k}$ from left to right, then there must be a production rule $A \to X_{1} X_{2} \dots X_{k}$ in the grammar.
Yield: The yield of a parse tree is the string formed by concatenating the labels of the leaves in a left-to-right order. A derivation is valid if the yield of its parse tree is the target string.

To get a more formal handle on these definitions, please review the following resource.

CS 373: Theory of Computation - University of Illinois

These lecture notes from the University of Illinois provide a concise and formal definition of a parse tree and its properties.

Please read the section titled "Parse Trees" (slide 14). Focus on the five conditions that define a parse tree and the concept of the tree's "yield".

2. Constructing a Parse Tree

Let's see how a derivation directly translates into a parse tree. The key insight is that the parse tree represents the what (which rules were used) and not the when (the order they were applied).

Consider the following simple grammar for arithmetic expressions:

$E \to E + E ∣ E * E ∣ id$

Let's take a leftmost derivation for the string id+id*id:

$E \Rightarrow_{l m} E * E$
$\Rightarrow_{l m} E + E * E$
$\Rightarrow_{l m} id + E * E$
$\Rightarrow_{l m} id + id * E$
$\Rightarrow_{l m} id + id * id$

We can build the parse tree that corresponds to this derivation:

The first step, $E \Rightarrow E * E$ , gives us the root $E$ with children $E$ , *, and $E$ .
The second step, where the leftmost $E$ becomes $E + E$ , adds a new layer to the tree.
The subsequent steps, where each $E$ becomes id, form the leaves of the tree.

The following image provides an excellent visual summary of the components of a parse tree and makes a crucial point: different derivations (e.g., one that is leftmost and one that is not) can still result in the exact same parse tree. The tree abstracts away the specific order of non-terminal expansion.

Parse Trees and Derivations in Context-Free Grammars — This image defines the components of a parse tree and shows how different derivation sequences can produce the same hierarchical structure.

The key takeaway is that for any given derivation of a string, there is a corresponding parse tree. The structure of the tree is determined by the rules used, not the order in which non-terminals were expanded.

3. Identifying Grammatical Ambiguity

Now we arrive at the most important application of parse trees in this context: identifying ambiguity.

A grammar is ambiguous if there is at least one string in its language that has two or more distinct parse trees.

Why is this a problem? Imagine a compiler trying to parse an arithmetic expression. If the grammar is ambiguous, the compiler could build multiple valid parse trees, each implying a different order of operations.

Let's revisit our expression grammar: $E \to E + E ∣ E * E ∣ id$ .
Consider the string id + id * id. We already saw one parse tree for it. But is there another one?

Yes. We could have started with the production $E \to E + E$ . This would lead to a completely different derivation and a different parse tree.

The following video demonstrates this perfectly. It shows how the existence of two different leftmost derivations, two different rightmost derivations, or two different parse trees are all equivalent indicators of an ambiguous grammar.

Ambiguity in CFGs

This video from Neso Academy clearly illustrates the concept of ambiguity using our familiar expression grammar. It demonstrates how to find multiple derivations and construct the resulting parse trees.

Watch from 00:49 to 04:56. The video walks through creating two different leftmost derivations, two different rightmost derivations, and finally, the two distinct parse trees for the string id+id*id. This directly demonstrates the definition of ambiguity.

As the video shows, for the string id + id * id, we can generate two different parse trees:

Ambiguity in Context-Free Grammars Illustrated with Multiple Parse Trees — This image shows two distinct parse trees for the string `a+a*a` (using `a` instead of `id`). The left tree groups multiplication first `(a + (a*a))`, while the right tree groups addition first `((a+a) * a)`. This structural difference is the essence of ambiguity.

The existence of these two trees proves that the grammar $E \to E + E ∣ E * E ∣ id$ is ambiguous. A compiler using this grammar wouldn't know whether to perform the addition or the multiplication first, leading to incorrect results. This is why unambiguous grammars are so critical in programming language design.

Test your understanding!

A classic example of ambiguity in programming languages is the "dangling else" problem. Consider the following grammar for conditional statements, where $C$ represents a condition and $A$ represents an action:

$S \to if C then S$
$S \to if C then S else S$
$S \to A$

The string if C then if C then A else A can be interpreted in two ways. Does the else attach to the first if or the second if?

Prove that this grammar is ambiguous by finding two different leftmost derivations for this string and drawing their corresponding parse trees.

Show answer

Here are the two possible leftmost derivations and their interpretations:

Derivation 1 (else attaches to the inner if):

$S \Rightarrow_{l m} if C then S$
$\Rightarrow_{l m} if C then (if C then S else S)$ (Applied rule 2 to the S)
$\Rightarrow_{l m} if C then if C then A else S$ (Applied rule 3 to the first S)
$\Rightarrow_{l m} if C then if C then A else A$ (Applied rule 3 to the remaining S)

This corresponds to a parse tree where the if-then-else statement is nested inside the if-then statement.

Derivation 2 (else attaches to the outer if):

$S \Rightarrow_{l m} if C then S else S$
$\Rightarrow_{l m} if C then (if C then S) else S$ (Applied rule 1 to the first S)
$\Rightarrow_{l m} if C then if C then A else S$ (Applied rule 3 to the inner S)
$\Rightarrow_{l m} if C then if C then A else A$ (Applied rule 3 to the final S)

This corresponds to a parse tree where the second if-then is the "then" branch of the outer if-then-else statement.

Since the string has two distinct leftmost derivations (and thus two distinct parse trees), the grammar is ambiguous. Most programming languages resolve this by specifying that an else always binds to the nearest unmatched if.

Conclusion

In this lesson, we bridged the gap between the linear sequence of a derivation and its underlying hierarchical structure.

Key Takeaways:

A parse tree is a graphical representation of a derivation that shows how a string is generated from a grammar's start symbol.
The yield of a parse tree is the string of terminals read from its leaves.
Parse trees abstract away the order of non-terminal expansion; different derivations (e.g., leftmost vs. rightmost) can produce the same parse tree.
A grammar is ambiguous if there exists at least one string that has more than one parse tree. This is equivalent to that string having more than one leftmost derivation or more than one rightmost derivation.
Ambiguity is a serious issue in contexts like compiler design because it means the meaning of a string (like a line of code) is not uniquely determined by the grammar.

Preview of the Next Lesson:
Identifying ambiguity is a crucial skill. The natural next question is: can we fix it? While some languages are inherently ambiguous (meaning no unambiguous grammar exists for them), many ambiguous grammars can be rewritten to be unambiguous. Before we tackle that, we'll learn some essential "grammar hygiene" techniques. In the next lesson, we will explore algorithms to simplify CFGs by removing useless symbols, $ε$ -productions, and unit productions. These steps are fundamental to cleaning up grammars and preparing them for parsing algorithms.

Recommended resources

1. Visualizing Derivations: The Parse Tree

2. Constructing a Parse Tree

3. Identifying Grammatical Ambiguity

Conclusion