Class 13: Ambiguous Grammars

Held: Wednesday, 18 February 2004

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

Related Pages:

• EBoard.

Notes:

• I've extended the due date on phase 2 of the project.
• Cool biocomputing talk tomorrow! Extra credit for attending and sending a short reflection.

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
  

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.]
• When rewriting the grammar, we decide upon categories of things that are and are not allowed in particular places, and write rules for those kinds of things.
• 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.