Slide 1Hidden slidesTodayGrammars, derivations, parse treesCYK executionConstructing the parse tree from the CYK graphCYK ParserRemoving Ambiguity in the GrammarHow many parse trees are here?One parse tree only!Ambiguity (Cont.)Ambiguity: ExampleAmbiguity. ExampleAmbiguity. ExampleDealing with AmbiguitySlide 23Precedence and Associativity DeclarationsAssociativity DeclarationsPrecedence DeclarationsImplementing disambiguity declarationsExampleImplementing the declarations in CYK/EarleyEarley ParserInefficiency in CYKExampleKey ideaThe intuitionExample (1)Example (1.1)Example (2)Example (3)Example (4)Example (5)Example (6)Example (7)Example (8)Example (a note)Generalize CYK edges: Three kinds of edgesEarley AlgorithmHW4Slide 68Example grammar in CS164Build a parse tree for 10+2*3, and evaluateSame SDT in the notation of the cs164 parserBuild AST for a regular expression1Lecture 9Syntax-Directed Translationgrammar disambiguation, Earley parser, syntax-directed translationRas Bodik Shaon BarmanThibaud HottelierHack Your Language!CS164: Introduction to Programming Languages and Compilers, Spring 2012UC BerkeleyHidden slidesThis slide deck contains hidden slides that may help in studying the material. These slides show up in the exported pdf file but when you view the ppt file in Slide Show mode.2TodayRefresh CYK parserbuilds the parse bottom upGrammar disambiguationselect desired parse trees without rewriting the grammarEarley parsersolves CYK’s inefficiencySyntax-directed translationit’s a rewrite (“evaluation”) of the parse tree3Grammars, derivations, parse treesExample grammarDECL --> TYPE VARLIST ;TYPE --> int | floatVARLIST --> id | VARLIST , idExample stringint id , id ;Derivation of the stringDECL --> TYPE VARLIST ; --> int VARLIST ; --> … --> --> int id , id ;4DECL10TYPE6VARLIST9VARLIST7id2,3id4;5int1CYK executionTYPE6-->int1DECL10 --> TYPE6 VARLIST9 ;5VARLIST9-->VARLIST7 ,3 id4VARLIST7-->id2int1id2id4,3;5VARLIST8-->id4DECL10TYPE6VARLIST9VARLIST7id2,3id4;5int15Constructing the parse tree from the CYK graphTYPE6-->int1DECL10 --> TYPE6 VARLIST9 ;5VARLIST9-->VARLIST7 ,3 id4VARLIST7-->id2int1id2id4,3;5VARLIST8-->id4DECL10TYPE6VARLIST9VARLIST7id2,3id4;5int17CYK ParserBuilds the parse bottom-upgiven grammar containing A → B C, when you find adjacent B C in the CYK graph, reduce B C to ASee the algorithm in Lecture 89Removing Ambiguity in the GrammarHow many parse trees are here?grammar: E → id | E + E | E * E input: id+id*id14id1+ *E6 → id1id3E11 → E9 * E8E11 → E6 + E10id5E9 → E 6 + E7E8 → id5E7 → id3E10→ E7 * E8 ambiguousOne parse tree only!The role of the grammar –distinguish between syntactically legal and illegal programsBut that’s not enough: it must also define a parse tree–the parse tree conveys the meaning of the program–associativity: left or right–precedence: * before +What if a string is parseable with multiple parse trees?–we say the grammar is ambiguous –must fix the grammar (the problem is not in the parser)1718Ambiguity (Cont.)Ambiguity is bad–Leaves meaning of some programs ill-definedAmbiguity is common in programming languages–Arithmetic expressions–IF-THEN-ELSE19Ambiguity: ExampleGrammar E → E + E | E * E | ( E ) | intStrings int + int + int int * int + int20Ambiguity. ExampleThis string has two parse treesEEE EE+int+intintEEE EE+int+intint+ is left-associative21Ambiguity. ExampleThis string has two parse treesEEE EE*int+intintEEE EE+int*intint* has higher precedence than +22Dealing with AmbiguityNo general (automatic) way to handle ambiguityImpossible to convert automatically an ambiguous grammar to an unambiguous one (we must state which tree desired)Used with care, ambiguity can simplify the grammar–Sometimes allows more natural definitions–We need disambiguation mechanismsThere are two ways to remove ambiguity:1) Declare to the parser which productions to preferworks on most but not all ambiguities2) Rewrite the grammara general approach, but manual rewrite neededwe saw an example in Lecture 8Disambiguation with precedence and associativity declarations 2324Precedence and Associativity DeclarationsInstead of rewriting the grammar–Use the more natural (ambiguous) grammar–Along with disambiguating declarationsBottom-up parsers like CYK and Earley allow declaration to disambiguate grammarsyou will implement those in PA5Examples …25Associativity DeclarationsConsider the grammar E E + E | int Ambiguous: two parse trees of int + int + intEEE EE+int +intintEEE EE+int+intintLeft-associativity declaration: %left +26Precedence DeclarationsConsider the grammar E E + E | E * E | int –And the string int + int * intEEE EE+int *intintEEE EE*int+intintPrecedence declarations: %left + %left *Implementing disambiguity declarationsTo disambiguate, we need to answer these questions:Assume we reduced the input to E+E*E. Now do we want parse tree (E+E)*E or E+(E*E)?Similarly, given E+E+E, do we want parse tree (E+E)+E or E+(E+E)?28Example29Implementing the declarations in CYK/Earleyprecedence declarations–when multiple productions compete for being a child in the parse tree, select the one with least precedenceleft associativity–when multiple productions compete for being a child in the parse tree, select the one with largest left subtreeEarley ParserInefficiency in CYKCYK may build useless parse subtrees –useless = not part of the (final) parse tree–true even for non-ambiguous grammarsExample grammar: E ::= E+id | id input: id+id+idCan you spot the inefficiency?This inefficiency is a difference between O(n3) and O(n2)It’s parsing 100 vs 1000 characters in the same time!Examplegrammar: E→E+id | id three useless reductions are done (E7, E8 and E10)id1+ +E6-->id1id3E11 --> E9 + id5id5E9-->E6 + id3E8-->id5E7-->id3E10-->E7 + E8Key ideaProcess the input left-to-rightas opposed to arbitrarily, as in CYKReduce only productions that appear non-useless consider only reductions with a chance to be in the parse treeKey ideadecide whether to reduce based on the input seen so farafter seeing more, we may still realize we built a useless treeThe algorithmPropagate a “context” of the parsing process.Context tells us what nonterminals can appear in the parse at the given point of input. Those that cannot won’t be reduced.The intuition53Use CYK edges (aka reductions), plus more edges.Idea: We ask “What
View Full Document
Unlocking...