ADMIN
  See preservation hall jazz band
  Questions on project, phase 1?

P1: S -> epsilon
P2: S -> aSb
P3: S -> bSa
P4: S -> SS

ASSIGNMENT BY 5PM TODAY: Prove that this describes the language
of all strings over { a,b } with equal numbers of a's and b's.

QUESTION: How can you tell if a grammar is ambiguous?
(Formally: How can you prove that a grammar is not ambiguous?)

ASSIGNMENT FOR 11AM WEDNESDAY: Come up with an answer to the
previous question.

----

Return to Ambiguous Grammars

Ambiguous grammar is a grammar in which there are multiple
derivations for the same string.

Ambiguous grammars are generally a bad idea, because they
lead to multiple interpretations of the same string.

We need to make ambiguous grammars unambiguous

Technique:
  (1) Find an ambiguous string
  (2) Decide which derivation is correct and which derivations
      are incorrect.
  (3) Divide the (language that corresponds to some nonterminal)
      into two classes and see how that helps.
      + Update grammar.
  (4) Prove that the new grammar is equivalent.

Today: Everybody's favorite ambiguous grammar: Expressions

R1: Exp -> num
R2: Exp -> id
R3: Exp -> Exp op Exp
R4: Exp -> ( Exp )

Claim: This grammar is ambiguous
Proof: num(1) op(+) num(2) op(*) num(3)

Update the grammar with "Things that have addition and don't
bother to include parenthesis that would make our life much
more convenient."

Factor: All addition is parenthesized
Exp: Addition may or may not be parenthesized

Also need to separate my operators into additive operators
(_+,-) and multiplicative operators (*,/).

R1: Factor -> num
R2: Factor -> id
R3: Exp -> Exp addop Exp
R4: Factor -> Factor mulop Factor
R5: Factor -> ( Exp )
R6: Exp -> Facto

Is this still ambiguous?  Yes!
Proof: num(1) op(/) num(2) op(/) num(3)

Claim: The two parse trees give the same value.
Perhaps Grinnell needs to offer precalc again.
This claim is false.

Which parse trees are correct?  The ones that are left
associative.

We'll deal with the addition problem first.

R1: Factor -> num
R2: Factor -> id
R3: Exp -> Exp addop Factor
R4: Factor -> Factor mulop Factor
R5: Factor -> ( Exp )
R6: Exp -> Fact

Now we get to deal with the multiplication problem.
Suggestions?

Introduce something new for legal stuff to the right of
a mulop.  "Term"
R1: Term -> num
R2: Term -> id
R3: Exp -> Exp addop Factor
R4: Factor -> Factor mulop Term
R5: Term -> ( Exp )
R6: Exp -> Factor
R7: Factor -> Term

What questions should we ask ourselves?
* Is it the same language? Boy, I hope so.
* Is it still ambiguous?  Boy, I hope not.

How has the disambiguation affected us?
* Added many more rules.
* Added two new nonterminals.
* Gives us confidence that we can use our parse trees.
* Makes derivations longer.

The tree we use for "proving" a string is in our language
is not necessarily the one we'll use to understand the string.