1 Lecture 9 Syntax-Directed Translation grammar disambiguation, Earley parser, syntax-directed translation Ras Bodik Shaon Barman Thibaud Hottelier Hack Your Language! CS164: Introduction to Programming Languages and Compilers, Spring 2012 UC BerkeleyHidden slides This 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. 2Today Refresh CYK parser builds the parse bottom up Grammar disambiguation select desired parse trees without rewriting the grammar Earley parser solves CYK’s inefficiency Syntax-directed translation it’s a rewrite (“evaluation”) of the parse tree 3Grammars, derivations, parse trees Example grammar DECL --> TYPE VARLIST ; TYPE --> int | float VARLIST --> id | VARLIST , id Example string int id , id ; Derivation of the string DECL --> TYPE VARLIST ; --> int VARLIST ; --> … --> --> int id , id ; 4 DECL10 TYPE6 VARLIST9 VARLIST7 id2 ,3 id4 ;5 int1CYK execution TYPE6-->int1 DECL10 --> TYPE6 VARLIST9 ;5 VARLIST9-->VARLIST7 ,3 id4 VARLIST7-->id2 int1 id2 id4 ,3 ;5 VARLIST8-->id4 DECL10 TYPE6 VARLIST9 VARLIST7 id2 ,3 id4 ;5 int1 5Key invariant Edge (i,j,T) exists iff T -->* input[i:j] – T -->* input[i:j] means that the i:j slice of input can be derived from T in zero or more steps – T can be either terminal or non-terminal Corollary: – input is from L(G) iff the algorithm creates the edge (0,N,S) – N is input lengthConstructing the parse tree from the CYK graph TYPE6-->int1 DECL10 --> TYPE6 VARLIST9 ;5 VARLIST9-->VARLIST7 ,3 id4 VARLIST7-->id2 int1 id2 id4 ,3 ;5 VARLIST8-->id4 DECL10 TYPE6 VARLIST9 VARLIST7 id2 ,3 id4 ;5 int1 7CYK graph to parse tree Parse tree nodes obtained from CYK edges are grammar productions Parse tree edges obtained from reductions (ie which rhs produced the lhs) 8CYK Parser Builds the parse bottom-up given grammar containing A → B C, when you find adjacent B C in the CYK graph, reduce B C to A See the algorithm in Lecture 8 9CYK: the algorithm CYK is easiest for grammars in Chomsky Normal Form CYK is asymptotically more efficient in this form O(N3) time, O(N2) space. Chomsky Normal Form: production forms allowed: A → BC or A → d or S → ε (only start non-terminal can derive ) Each grammar can be rewritten to this formCYK: dynamic programming Systematically fill in the graph with solutions to subproblems – what are these subproblems? When complete: – the graph contains all possible solutions to all of the subproblems needed to solve the whole problem Solves reparsing inefficiencies – because subtrees are not reparsed but looked upComplexity, implementation tricks Time complexity: O(N3), Space complexity: O(N2) – convince yourself this is the case – hint: consider the grammar to be constant size? Implementation: – the graph implementation may be too slow – instead, store solutions to subproblems in a 2D array • solutions[i,j] stores a list of labels of all edges from i to jRemoving Ambiguity in the GrammarHow many parse trees are here? grammar: E → id | E + E | E * E input: id+id*id 14 id1 + * E6 → id1 id3 E11 → E9 * E8 E11 → E6 + E10 id5 E9 → E 6 + E7 E8 → id5 E7 → id3 E10→ E7 * E8 ambiguousPA5 warning: “Nested ambiguity” Work out the CYK graph for this input: id+id*id+id. Notice there are multiple “ambiguous” edges – ie, edges inserted due to multiple productions – hence there is exponential number of parse trees – even though we have polynomial number of edges The point: don’t worry about exponential number of trees We still need to select the desired one, of course 15CYK on ambiguous grammar same algorithm, but may yield multiple parse trees – because an edge may be reduced (ie, inserted into the graph) using to multiple productions we need to chose the desired parse tree – we’ll do so without rewriting the grammar example grammar E → E + E | E * E | id 16One parse tree only! The role of the grammar – distinguish between syntactically legal and illegal programs But 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) 1718 Ambiguity (Cont.) Ambiguity is bad – Leaves meaning of some programs ill-defined Ambiguity is common in programming languages – Arithmetic expressions – IF-THEN-ELSE19 Ambiguity: Example Grammar E → E + E | E * E | ( E ) | int Strings int + int + int int * int + int20 Ambiguity. Example This string has two parse trees E E E E E + int + int int E E E E E + int + int int + is left-associative21 Ambiguity. Example This string has two parse trees E E E E E * int + int int E E E E E + int * int int * has higher precedence than +22 Dealing with Ambiguity No general (automatic) way to handle ambiguity Impossible 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 mechanisms There are two ways to remove ambiguity: 1) Declare to the parser which productions to prefer works on most but not all ambiguities 2) Rewrite the grammar a general approach, but manual rewrite needed we saw an example in Lecture 8Disambiguation with precedence and associativity declarations 2324 Precedence and Associativity Declarations Instead of rewriting the grammar – Use the more natural (ambiguous) grammar – Along with disambiguating declarations Bottom-up parsers like CYK and Earley allow declaration to disambiguate grammars you will implement those in PA5 Examples …25 Associativity Declarations Consider the grammar E E + E | int Ambiguous: two parse trees of int + int + int E E E E E + int + int int E E E E E + int + int int Left-associativity declaration: %left +26 Precedence Declarations Consider the grammar E E + E | E * E | int – And the string int + int * int E E E E E + int * int int E E E E E * int + int int Precedence declarations: %left + %left *Ambiguity declarations These are the two common forms of ambiguity – precedence: * higher
View Full Document
Unlocking...