Class 29: Ambiguous Grammars, Concluded

Held Wednesday, April 14

Summary

• Reading: Louden, chapter 6

Contents

Handouts

• Notes on presentations.

Notes

• Quizzes are due at the start of class. We'll spend a few minutes talking about them after we've finished with administrative details.
• How did you feel about the structure and content of Monday's class? Was it helpful? If you're not comfortable talking about this in class, please send me email.
• Any questions on assignment 5?
• We'll spend a few minutes discussing the upcoming presentations (dates, requirements, etc.)

Discussion of Quizzes

• See the previous outline.

Ambiguous Grammars, Revisited

• We've seen that while ambiguous grammars are not harmful from the syntactic perspective, they are harmful from the semantic perspective.
• We've begun to look at how to disambiguate the expression grammar.
• So far, we have added some precedence by deciding that multiplication operations can only have subtrees that have no unparenthesized addition.
• This gives us

  Exp ::= Exp AddOp Exp
       |  Term
  Term ::= Term MulOp Term
        |  (Exp)
        |  num
        |  id
  AddOp ::= plus | minus
  MulOp ::= times | divide
  

• We're now ready to consider precedence.

Adding Associativity to the Expression Grammar

• Have we solved the associativity problem? No. You'll observe that we can still misparse a-a-a.
• How do we handle associativity?
  • By considering which tree is correct.
  • By considering why the incorrect tree is incorrect.
  • By trying to change the grammar to eliminate the incorrect tree.
• Why is the incorrect tree incorrect? Because there is unparenthesized subtraction ``to the right of'' subtraction.
• What should we do? Come up with a category for ``no unparenthesized subtraction or addition''.
• Do we have such a category? Yes, we called it Term.
• Hence, we can write

  Exp ::= Exp AddOp Term
  

• Are there other similar areas we must worry about?. Yes, we'll need to worry about repeated division (or multiplication). We can use the same strategy.
• We'll introduce Factor as ``no unparenthesized multiplication of addition''.
• We can use it in

  Term ::= Term MulOp Factor
  

• We also need to define it.

The Final Grammar

• Here is our unambiguous grammar, so far.

  Exp ::= Exp AddOp Term
       |  Term
  Term ::= Term MulOp Factor
        |  Factor
  Factor ::= '(' Exp ')'
          |  num
          |  id
  AddOp ::= plus | minus
  MulOp ::= times | divide
  

• Have we changed the language? No, but the proof is difficult (and left as an exercise for those of you in 341 :-).
• We could further extend this grammar in many ways.
  • Include the unary operators. Note that each at most one unary operator is typically used (e.g., -+num is meaningless, as is ---num).
  • Include exponentiation. Is exponentiation left or right associative?
  • Include other operations.
  • Function calls.
  • ...
• These extensions are left as an exercise to the reader.

A Note on Order of Evaluation

• Many people assume that the parse structure completely determines the order of evaluation.
• However, this is not true in most languages.
• Consider alpha() + beta() * gamma()
• We know that the result of beta() is multiplied by the result of gamma() and that result is then added to alpha().
• Do you know what order alpha(), beta() and gamma() are evaluated in? In most languages, the answer is ``it's up to the implementer''.
• Does it make a difference? In many cases, yes. Consider the following code fragment in a generic language.

  global integer x = 1;
  
  function zebra
  begin
    x = x + 1;
    return x;
  end zebra;
  
  ...
  y = zebra() + zebra() - zebra();
  

• What is the value of y?

History

• Created Tuesday, January 19, 1999 as a blank outline.
• Filled in the details on Wednesday, April 14, 1999. The section on associativity was taken from outline 7 of CS302 98S. It was rewritten to accommodate changes to the structure of the class (we're covering topics in a much different order).
• Moved uncovered topics to the subsequent outline on Thursday, April 15, 1999.