# Class 10: Ambiguous Grammars

Back to Introduction to Grammars and Parsing. On to Parsing Expressions.

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 anbn (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.

## History

Monday, 22 January 2001

• Created as a blank outline.

Monday, 12 February 2001

• Filled in the details. All new!

Back to Introduction to Grammars and Parsing. On to Parsing Expressions.

Disclaimer: I usually create these pages on the fly. This means that they are rarely proofread and may contain bad grammar and incorrect details. It also means that I may update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This page was generated by Siteweaver on Mon Apr 30 10:51:50 2001.