Grammars and ambiguityOverviewRecall: derivations and parse treesDerivation ExampleDerivation Example (Cont.)Derivation in Detail (1)Derivation in Detail (2)Derivation in Detail (3)Derivation in Detail (4)Derivation in Detail (5)Derivation in Detail (6)Notes on DerivationsLeft-most and Right-most DerivationsRight-most Derivation in Detail (1)Right-most Derivation in Detail (2)Right-most Derivation in Detail (3)Right-most Derivation in Detail (4)Right-most Derivation in Detail (5)Right-most Derivation in Detail (6)Derivations and Parse TreesambiguityAmbiguityAmbiguity. ExampleSlide 24Ambiguity (Cont.)Dealing with AmbiguitySlide 27Ambiguity: The Dangling ElseThe Dangling Else: ExampleThe Dangling Else: A FixThe Dangling Else: Example RevisitedSlide 32Precedence and Associativity DeclarationsAssociativity DeclarationsPrecedence DeclarationsProf. Bodik CS 164 Lecture 8 1Grammars and ambiguity CS1643:30-5:00 TT10 EvansProf. 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 themProf. Bodik CS 164 Lecture 83Recall: derivations and parse treesA derivation is a sequence of productions S … … A derivation can be drawn as a parse tree–Start symbol is the tree’s root–For a production X Y1 … Yn add children Y1, …, Yn to node X You need parse trees to build ASTsProf. Bodik CS 164 Lecture 84Derivation Example•Grammar•StringE E+E | E E | (E) | id id id + idProf. Bodik CS 164 Lecture 85Derivation Example (Cont.)EE+EE E+Eid E + Eid id + Eid id + id EEE EE+id*ididProf. Bodik CS 164 Lecture 86Derivation in Detail (1)EEProf. Bodik CS 164 Lecture 87Derivation in Detail (2)EE+EEE E+Prof. Bodik CS 164 Lecture 88Derivation in Detail (3)E EEE+EE + EEE EE+*Prof. Bodik CS 164 Lecture 89Derivation in Detail (4)EE+EE E+Eid E + E EEE EE+*idProf. Bodik CS 164 Lecture 810Derivation in Detail (5)EE+EE E+Eid E + id id + EE EEE EE+*ididProf. Bodik CS 164 Lecture 811Derivation in Detail (6)EE+EE E+Eid E + Eid id + Eid id + id EEE EE+id*ididProf. 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-most derivation–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 + id Prof. Bodik CS 164 Lecture 814Right-most Derivation in Detail (1)EEProf. Bodik CS 164 Lecture 815Right-most Derivation in Detail (2)EE+EEE E+Prof. Bodik CS 164 Lecture 816Right-most Derivation in Detail (3)idEE+EE+EE E+idProf. Bodik CS 164 Lecture 817Right-most Derivation in Detail (4)EE+EE+idE E + idEEE EE+id*Prof. Bodik CS 164 Lecture 818Right-most Derivation in Detail (5)EE+EE+idE E E+ idid + idEEE EE+id*idProf. Bodik CS 164 Lecture 819Right-most Derivation in Detail (6)EE+EE+idE E + idE id + idid id + id EEE EE+id*ididProf. 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 addedambiguityProf. Bodik CS 164 Lecture 822Ambiguity•Grammar E E + E | E * E | ( E ) | int•Strings int + int + int int * int + intProf. Bodik CS 164 Lecture 823Ambiguity. ExampleThis string has two parse treesEEE EE+int+intintEEE EE+int+intint+ is left-associativeProf. 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-ELSEProf. Bodik CS 164 Lecture 826Dealing with Ambiguity•There are several ways to handle ambiguity•Most direct method is to rewrite the grammar unambiguously E E + T | T T T * int | int | ( E )•Enforces precedence of * over +•Enforces left-associativity of + and *Prof. Bodik CS 164 Lecture 827Ambiguity. ExampleThe int * int + int has ony one parse tree nowEEE EE*int+intintETTintT+int*EintProf. Bodik CS 164 Lecture 828Ambiguity: The Dangling Else•Consider the grammar S if E then S | if E then S else S | OTHER•This grammar is also ambiguousProf. Bodik CS 164 Lecture 829The Dangling Else: Example•The expression if E1 then if E2 then S3 else S4 has two parse treesifE1ifE2S3S4ifE1ifE2S3S4•Typically we want the second formProf. 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 MIF /* all then are matched */ | UIF /* some then are unmatched */MIF if E then MIF else MIF | OTHERUIF if 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 E1 then if E2 then S3 else S4 ifE1ifE2S3S4ifE1ifE2S3S4•Not valid because the then expression is not a MIF•A valid parse tree (for a UIF)Prof. 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 mechanismsProf. 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 …Prof. Bodik CS 164 Lecture 834Associativity Declarations•Consider the
View Full Document
Unlocking...