6/16/2009CS 421 Lecture 8: Top-down parsing Lecture outline Recursive-descent formalized FIRST sets LL(1) condition Transformations to LL(1) form Grammars for expressions16/16/2009Review: context-free grammar Given: Set of terminals (tokens) T Set of non-terminals (variables) V A cfgGis a set of productionsof the formA→X1…Xn(n≥ 0)whereA∈V, X1…Xn∈G= V ∪T One symbol designated as “start symbol”26/16/2009Top-down parsing: outline Top-down parsing Start parsing with start symbol Apply production rules one by one More than one production for rule A Look at the next token to decide which production to apply36/16/2009Top-down parsing: pseudocode For each non-terminal with productionsA→X1…Xn| Y1…Yn| … | Z1…Zn Define parseA:parseA toklis = choose production based on hd toklis:if A → X1… Xn: handle X1… Xnelse if A → Y1… Yn: handle Y1… Ynelse if …handle X1… Xn: handle X1; handle X2; … ; handle Xnwhere handle t : if hd toklis = tthen remove t and continueelse errorhandle B : parseB toklis46/16/2009“choose production based on hd toklis” Need to formalize some things… Define ⇒ “Derives in one step”X1…Xn⇒ w1…wn, where Xi∈Gand wi∈G*if there exists jsuch that Xj→wjis a production in G, and for all i ≠j, Xi=wi ⇒ +and ⇒ * are the transitive and reflexive-transitive closures of ⇒. Say X1…Xnderives αif X1…Xn⇒* α.E.g., α is a sequence of G if the start symbol of G derives αand α consists solely of tokens.56/16/2009More DefinitionsX1…Xnis nullableif it can derive ε. FIRST(X1…Xn) = { t ∈T |X1…Xn⇒* tα for some α}∪ { _ |X1…Xnnullable} G is left-recursive if there exists A: A ⇒+Aα for some α. G is LL(1)if G is not left-recursive, and ∀A, if the productions of Aare: A→X| Y | … | Z then the sets FIRST(X), …, FIRST(Z) are pairwise disjoint.66/16/2009Top-down parsing: revisited If G is LL(1), then for each non-terminal A with productionsA→X1…Xn| Y1…Yn| … | Z1…Zn Define parseA:parseA toklis = let t = hd toklis inif t ∈ FIRST(X1… Xn) then handle X1… Xnelse if t ∈ FIRST(Y1… Yn) then handle Y1… Ynelse if …else if t ∈ FIRST(Z1… Zn) or _ ∈ FIRST(Z1… Zn)handle Z1… Znelse errorhandle X1… Xn: handle X1; handle X2; … ; handle Xnhandle t : if hd toklis = tthen remove t and continueelse errorhandle B : parseB toklis76/16/2009Transformation to LL(1) Left refactoring: A → αβ | αγ ⇒ A → α B B → β | γ Left-recursion removal: A → Aα | β ⇒ A → β B B → ε | α B86/16/2009Example Consider non-LL(1) grammar 3 from previous class: A → id | ‘(‘ B ‘)’ B → A | A ‘+’ B Grammar 3 transformed to LL(1) form: A → id | ‘(‘ B ‘)’ B → A C C → ‘+’ A C | ε96/16/2009Ambiguity More than one valid parse tree for one input No test for ambiguity Recursive descent and LR(1) parsing not applicable to ambiguous grammar Possible to “cheat” with LR parser – will see how next week106/16/2009Expression grammars Expressions are challenging for several reasons Should be LL(1) and LR(1) Grammar should enforce precedence, if possible Grammar should enforce associativity, if possible Grammar shouldn’t be ambiguous Should be easy to construct abstractsyntax tree Especially hard to write LL(1) parser for expressions Not so hard for LR(1)116/16/2009Enforcing precedence Consider: x + y * z x * y + z How should we parse?126/16/2009Enforcing associativity Consider: x - y - z x = y = z + 1 How should we parse?136/16/2009Example: expression grammars Some expression grammars: GA: E → id | E – E | E * E GB: E → id | id – E | id * E GC: E → id | E – id | E * id146/16/2009Example: GA GA: E → id | E – E | E * E Ambiguity? LR(1)/LL(1)? Precedence? Associativity? x – y * z156/16/2009Example: GB GB: E → id | id – E | id * E Ambiguity? LR(1)/LL(1)? Precedence? Associativity? x – y * z x * y – z x – y – z166/16/2009Example: GC GC: E → id | E – id | E * id Ambiguity? LR(1)/LL(1)? Precedence? Associativity? x – y * z x * y – z x – y – z176/16/2009Example: more expression grammars Some more expression grammars: GD: E → T - E | TT → id | id * T GE: E → E - T | TT → id | T * id GF: E → T E’E’ → ε | - ET → id T’T’ → ε | * T186/16/2009Example: GD GD: E → T - E | TT → id | id * T Ambiguity? LR(1)/LL(1)? Precedence? Associativity? x – y * z x * y – z x – y – z196/16/2009Example: GE GE: E → E - T | TT → id | T * id Ambiguity? LR(1)/LL(1)? Precedence? Associativity? x – y * z x * y – z x – y – z206/16/2009Example: GF GF: E → T E’E’ → ε | - ET → id T’T’ → ε | * T Ambiguity? LR(1)/LL(1)? Precedence? Associativity? x – y * z x * y – z x – y – z216/16/2009Next class More parsing (yay!) Bottom-up parsing
View Full Document
Unlocking...