Course contentsShow
← Computer Science
Lesson 1817 of 2,87241. Context-Free LanguagesFree lesson

Ambiguous Grammars

Identify grammars where a string can have multiple distinct parse trees and understand implications.

Ambiguous Grammars

What you'll learn: How to recognize when a grammar allows multiple interpretations of the same string — and why that matters.

What Is an Ambiguous Grammar?

A context-free grammar is ambiguous if at least one string in its language has two or more distinct parse trees (or equivalently, two or more distinct leftmost/rightmost derivations). This means the grammar doesn't uniquely determine the structure of certain strings.

Think of it like reading the sentence "I saw the man with the telescope." Did you use a telescope to see him, or did you see a man who was holding a telescope? Two different meanings, one sentence — that's ambiguity in natural language, and grammars can have the same problem.

Why Does Ambiguity Matter?

In programming languages, parse trees determine meaning. If 3 + 4 * 5 can be parsed as (3 + 4) * 5 = 35 or as 3 + (4 * 5) = 23, your compiler might compute the wrong answer! Ambiguity means the grammar doesn't enforce a single interpretation.

Example: The Classic Arithmetic Expression

Consider this grammar for arithmetic:

E → E + E
E → E * E
E → num

The string 2 + 3 * 4 has two parse trees:

  • Tree 1: (2 + 3) * 4 — addition happens first
  • Tree 2: 2 + (3 * 4) — multiplication happens first

Both are valid according to the grammar rules, making it ambiguous.

Resolving Ambiguity

You fix ambiguity by rewriting the grammar to enforce precedence and associativity rules (concepts you'll explore soon). The key is making the grammar structure reflect the intended meaning.

Key Takeaway: An ambiguous grammar produces multiple distinct parse trees for the same string, which can lead to incorrect or unpredictable interpretations — especially critical in programming language design.