Prof. Bodik CS 164 Lecture 8 1Grammars and ambiguity CS1643:30-5:00 TT10 EvansGGGooooooProf. Bodik CS 164 Lecture 82Overview• derivations and parse trees– different derivations produce may produce same parse tree• ambiguous grammars– what they are– and how to fix themGGGooooooProf. Bodik CS 164 Lecture 83Recall: derivations and parse treesAderivation is a sequence of productionsS G… G…A derivation can be drawn as a parse tree– Start symbol is the tree’s root– For a production X GY1… Ynadd children Y1, …, Ynto node XYou need parse trees to build ASTsooooooGGGProf. Bodik CS 164 Lecture 84Derivation Example• Grammar• StringE E+E | E E | (E) | idoid id + idoooooGGGoProf. Bodik CS 164 Lecture 85Derivation Example (Cont.)EE+EE E+Eid E + Eid id + Eid id + idoooooEEE EE+id*ididGGGooooooProf. Bodik CS 164 Lecture 86Derivation in Detail (1)EEProf. Bodik CS 164 Lecture 87Derivation in Detail (2)EE+EoEE E+oooooooooooooooProf. Bodik CS 164 Lecture 88Derivation in Detail (3)E EEE+EE +ooEEE EE+*oooooooooooooooProf. Bodik CS 164 Lecture 89Derivation in Detail (4)EE+EE E+Eid E + EoooEEEEE+*idoooooooooooooooProf. Bodik CS 164 Lecture 810Derivation in Detail (5)EE+EE E+Eid E + id id + EEooooEEEEE+*ididoooooooooooooooProf. Bodik CS 164 Lecture 811Derivation in Detail (6)EE+EE E+Eid E + Eid id + Eid id + idoooooEEE EE+id*ididoooooooooooooooProf. Bodik CS 164 Lecture 812Notes on Derivations• A parse tree has– Terminals at the leaves– Non-terminals at the interior nodes• An in-order traversal of the leaves is the original input• The parse tree shows the association of operations, the input string does notProf. Bodik CS 164 Lecture 813Left-most and Right-most Derivations• The example is a left-mostderivation– At each step, replace the left-most non-terminal• There is an equivalent notion of a right-most derivationEE+EE+idE E + idE id + idid id + idooooooooooooooooooooProf. Bodik CS 164 Lecture 814Right-most Derivation in Detail (1)EEoooooooooooooooProf. Bodik CS 164 Lecture 815Right-most Derivation in Detail (2)EE+EoEE E+oooooooooooooooProf. Bodik CS 164 Lecture 816Right-most Derivation in Detail (3)idEE+EE+ooEE E+idoooooooooooooooProf. Bodik CS 164 Lecture 817Right-most Derivation in Detail (4)EE+EE+idE E + idoooEEE EE+id*oooooooooooooooProf. Bodik CS 164 Lecture 818Right-most Derivation in Detail (5)EE+EE+idE E E+ idid + idooooEEE EE+id*idProf. Bodik CS 164 Lecture 819Right-most Derivation in Detail (6)EE+EE+idE E + idE id + idid id + idoooooEEEEE+id*ididGoooooProf. Bodik CS 164 Lecture 820Derivations and Parse Trees• Note that right-most and left-most derivations have the same parse tree• The difference is only in the order in which branches are addedGoooooambiguityGoooooProf. Bodik CS 164 Lecture 822Ambiguity• GrammarE GE + E | E * E | ( E ) | int• Stringsint + int + intint * int + intoooooGProf. Bodik CS 164 Lecture 823Ambiguity. ExampleThis string has two parse treesEEE EE+int +intintEEE EE+int+intint+ is left-associativeoooooGProf. Bodik CS 164 Lecture 824Ambiguity. ExampleThis string has two parse treesEEE EE*int +intintEEE EE+int*intint* has higher precedence than +Prof. Bodik CS 164 Lecture 825Ambiguity (Cont.)• A grammar is ambiguous if it has more than one parse tree for some string– Equivalently, there is more than one right-most or left-most derivation for some string• Ambiguity is bad– Leaves meaning of some programs ill-defined• Ambiguity is common in programming languages– Arithmetic expressions– IF-THEN-ELSEGGooooProf. Bodik CS 164 Lecture 826Dealing with Ambiguity• There are several ways to handle ambiguity• Most direct method is to rewrite the grammar unambiguouslyE GE + T | TT GT * int | int | ( E )• Enforces precedence of * over +• Enforces left-associativity of + and *ooooGGProf. Bodik CS 164 Lecture 827Ambiguity. ExampleThe int * int + int has ony one parse tree nowEEEEE*int +intintETTintT+int*EintooooGGProf. Bodik CS 164 Lecture 828Ambiguity: The Dangling Else• Consider the grammarS oif E then S| if E then S else S| OTHER• This grammar is also ambiguousoooGGoProf. Bodik CS 164 Lecture 829The Dangling Else: Example• The expressionif E1then if E2then S3else S4has two parse treesifE1ifE2S3S4ifE1ifE2S3S4• Typically we want the second formoooGGoProf. Bodik CS 164 Lecture 830The Dangling Else: A Fix• else matches the closest unmatched then• We can describe this in the grammar (distinguish between matched and unmatched “then”)S oMIF /* all then are matched */ | UIF /* some then are unmatched */MIF oif E then MIF else MIF | OTHERUIF oif E then S| if E then MIF else UIF • Describes the same set of stringsProf. Bodik CS 164 Lecture 831The Dangling Else: Example Revisited• The expression if E1then if E2then S3else S4ifE1ifE2S3S4ifE1ifE2S3S4• Not valid because the then expression is not aMIF• A valid parse tree (for a UIF)ooProf. Bodik CS 164 Lecture 832Ambiguity• No general techniques for handling ambiguity• Impossible to convert automatically an ambiguous grammar to an unambiguous one• Used with care, ambiguity can simplify the grammar– Sometimes allows more natural definitions– We need disambiguation mechanismsooProf. Bodik CS 164 Lecture 833Precedence and Associativity Declarations• Instead of rewriting the grammar– Use the more natural (ambiguous) grammar– Along with disambiguating declarations• LR (bottom-up) parsers allow precedence and associativity declarations to disambiguate grammars• Examples …ooProf. Bodik CS 164 Lecture 834Associativity Declarations• Consider the grammar E oE + E | int• Ambiguous: two parse trees of int + int + intEEE EE+int +intintEEE EE+int+intint• Left-associativity declaration: %left +ooProf. Bodik CS 164 Lecture 835Precedence Declarations• Consider the grammar E oE + E | E * E | int– And the string int + int * intEEE EE+int *intintEEE EE*int+intint• Precedence declarations:
View Full Document
Unlocking...