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.