Class 10: Ambiguous Grammars

Held Friday, September 20, 2002

Summary

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

Notes

• Happy Family Weekend! Welcome to any families attending class.
• Are there questions on phase 1 of the project?
  • I've updated the due date to Friday, since you requested that we use Friday as our standard due date.
• I'm working on more detailed notes for yesterday's class. Unfortunately, dealing with an administrative snafu took up all of yesterday.
• In case you hadn't figured it out yet, you should have started chapter 4 of the red dragon. Since this is an upper-level course and we're following topics more-or-less in order, I'll assume that you can figure out what to read.
• Quiz: 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

• Ambiguity
• A Conditional Grammar
• Resolving Ambiguity
• An Expression Grammar

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.

Expesssions

• Note that the standard definition of expressions is particularly ambiguous.

  Exp: NUM
  Exp: ID
  Exp: Exp MULOP Exp
  Exp: Exp ADDOP Exp
  Exp: LPAREN Exp RPAREN
  

• This grammar does not provide for precedence or associativity.
• We'll return to it in the next class.