Class 10: Ambiguous Grammars

Held Monday, February 12, 2001

Summary

Today we consider a significant problem in the use of grammars: Ambiguous grammars.

Notes

• Are there questions on phase 1 of the project?
• Reminder: Thursday's Math Journal Club covers summer research opportunities in Mathematics.
• Thought problem: You know how to write a CFG for aⁿbⁿ (or at least I think you do). How about ``strings of a's and b's with equal numbers of a's and b's''?

Overview

• Parse Trees
• Ambiguity
• A Conditional Grammar
• Resolving Ambiguity

Parse Trees

• As we learned last class, grammars describe languages.
• A string, s, in in L(G) if there exist a sequence of productions in L(G) that transform S to s.
• We also observed that there can be different sequences of productions that generate the same string.
  • Some of these sequences differ only in the choice of which nonterminal to expand first.
• To clarify derivations (and to make it clear that the process can work in either direction), we often draw parse trees, pictorial representations of derivations.
• Parse trees are easiest to draw for context-free grammars.
• At the root of the tree is S, the start symbol.
• At the leaves of the tree are terminals, which are read from left to right.
• Internal nodes are nonterminals.
• The children of an internal node are the symbols at the right-hand side of a production for the nonterminal.
• We can build trees in two ways: working up from the leaves or down from the root.
• Some examples may clarify this issue.

Ambiguity

• Some grammars are ambiguous in that there is more than one parse tree for the same statement.
• Consider

  S ::= 
     |  SS
     |  a
  

  • How many trees are there for aa?
• Ambiguity is bad, particularly as the structure of a parse tree may give information about desired interpretations.
• The specification of a language should therefore be unambiguous.

Ambiguous Conditionals

• Here is a simple grammar for conditionals in a language. I've turned some nonterminals into terminals for simplicity.

  Statement ::= Conditional
             |  OTHER
  Conditional ::= IF TEST THEN Statement
               |  IF TEST THEN Statement ELSE Statement
  

• Why is this ambgiuous? It's up to you to help figure it out.

Removing Ambiguity

• Surprisingly (or perhaps not so surprisingly), removing ambiguity from a grammar requires non-trivial effort.
• Here are the steps I typically use:
  • Identify some ambiguous statements. [Hard.]
  • Build the alternate parse trees. [Easy.]
  • Select the one that is correct. [Requires thought.]
  • Rewrite the grammar (typically adding new productions) to disallow the invalid parse trees. [Hard.]
• We'll consider many examples.

An Unambiguous Conditional Grammar

• To be developed in class.