Top-Down Parsing CS308 Compiler Theory 1
Top-Down Parsing CS308 Compiler Theory 1
Top-Down Parsing The parse tree is created top to bottom. ·Top-down parser Recursive-Descent Parsing Backtracking is needed(If a choice of a production rule does not work,we backtrack to try other alternatives.) It is a general parsing technique,but not widely used. ·Not efficient Predictive Parsing ·no backtracking ·efficient needs a special form of grammars(LL(1)grammars). Recursive Predictive Parsing is a special form of Recursive Descent parsing without backtracking. Non-Recursive(Table Driven)Predictive Parser is also known as LL(1)parser. CS308 Compiler Theory 2
Top-Down Parsing • The parse tree is created top to bottom. • Top-down parser – Recursive-Descent Parsing • Backtracking is needed (If a choice of a production rule does not work we backtrack to try other Backtracking is needed (If a choice of a production rule does not work, we backtrack to try other alternatives.) • It is a general parsing technique, but not widely used. • Not efficient Not efficient – Predictive Parsing • no backtracking • effi i t fficient • needs a special form of grammars (LL(1) grammars). • Recursive Predictive Parsing is a special form of Recursive Descent parsing without backtracking. • Non-Recursive (Table Driven) Predictive Parser is also known as LL(1) parser. CS308 Compiler Theory 2
Recursive-Descent Parsing (uses Backtracking) Backtracking is needed. It tries to find the left-most derivation. S->aBc B->bc b input:abc a a C fails,backtrack b b CS308 Compiler Theory 3
Recursive-Descent Parsing (uses Backtracking) • Backtracking is needed. • It tries to find the left-most derivation. S → aBc B → bc | b S S input: abc a B c a Bc fails backtrack b c b fails, backtrack CS308 Compiler Theory 3
Predictive Parser a grammar → → a grammar suitable for predictive eliminate left parsing (a LL(1)grammar) left recursion factor no 100 guarantee. When re-writing a non-terminal in a derivation step,a predictive parser can uniquely choose a production rule by just looking the current symbol in the input string. A→01.|0m input:..a.… current token CS308 Compiler Theory 4
Predictive Parser a grammar Î Î a grammar suitable for predictive eliminate left parsi ( () ) ing (a LL(1) grammar) left recursion factor no %100 guarantee. • When re-writing a non-terminal in a derivation step, a predictive parser can uniquely choose a production rule by just looking the current can uniquely choose a production rule by just looking the current symbol in the input string. A → α1 | ... | αn input: ... a ....... current token CS308 Compiler Theory 4
Predictive Parser (example) stmt→if.… while ..... begin.… f0Y.… 。 When we are trying to write the non-terminal stmt,if the current token is if we have to choose first production rule. When we are trying to write the non-terminal stmt,we can uniquely choose the production rule by just looking the current token. We eliminate the left recursion in the grammar,and left factor it.But it may not be suitable for predictive parsing(not LL(1)grammar). CS308 Compiler Theory
Predictive Parser (example) stmt → if ...... | while ...... | begin ...... | for ..... • When we are trying to write the non-terminal stmt, if the current token is if we have to choose first production rule. • When we are trying to write the non-terminal stmt, we can uniquely choose the production rule by just looking the current token. • We eliminate the left recursion in the grammar, and left factor it. But it t b it bl f di ti i ( t LL(1) ) CS308 Compiler Theory 5 may no t be suit able for predi ctive pars ing (no t LL(1) grammar )
Recursive Predictive Parsing Each non-terminal corresponds to a procedure. Ex:A→aBb (This is only the production rule for A) proc A match the current token with a,and move to the next token; -call‘B'; match the current token with b,and move to the next token; CS308 Compiler Theory 6
Recursive Predictive Parsing • Each non-terminal corresponds to a procedure. Ex: A → aBb (This is only the production rule for A) proc A { - match the current token with a and move to the next token; match the current token with a, and move to the next token; - call ‘B’; - match the current token with b and move to the next token; match the current token with b, and move to the next token; } CS308 Compiler Theory 6
Recursive Predictive Parsing (cont.) A→aBb|bAB proc A{ case of the current token a':-match the current token with a,and move to the next token; -call‘B'; match the current token with b,and move to the next token; b':-match the current token with b,and move to the next token; -call‘A; call B': CS308 Compiler Theory 7
Recursive Predictive Parsing (cont.) A → aBb | bAB proc A { case of th t t k { f the curren t t o ken { ‘a’: - match the current token with a, and move to the next token; - call ‘B ;’ - match the current token with b, and move to the next token; ‘b :’ - match the current token with b and move to the next token; match the current token with b, and move to the next token; - call ‘A’; - call ‘B’ ; } } CS308 Compiler Theory 7
Recursive Predictive Parsing (cont.) When to apply s-productions. A->aA bB 8 If all other productions fail,we should apply an 8-production.For example,if the current token is not a or b,we may apply the 8-production. Most correct choice:We should apply an 8-production for a non- terminal A when the current token is in the follow set of A (which terminals can follow A in the sentential forms). CS308 Compiler Theory 8
Recursive Predictive Parsing (cont.) • When to apply ε-productions. A → aA | bB | ε • If all other productions fail, we should apply an ε-production. For example, if the current token is not a or b, we may apply the ε-production. • M h i W h ld l Most correct c h o ice: We s hould app ly an ε - prodif uct ion for a nonterminal A when the current token is in the follow set of A (which terminals can follow A in the sentential forms) terminals can follow A in the sentential forms). CS308 Compiler Theory 8
Recursive Predictive Parsing (Example) A->aBe cBd C B→bB|8 C→f proc C{match the current token with f, proc A{ and move to the next token;} case of the current token a:-match the current token with a, and move to the next token; proc B call B; case of the current token{ match the current token with e, b:-match the current token with b, and move to the next token; and move to the next token; c:-match the current token with c, call B and move to the next token; e,d:do nothing call B; match the current token with d, and move to the next token; follow set of B f:-call C first set of C CS30 Compiler Theory 9
Recursive Predictive Parsing (Example) A → aBe | cBd | C B → bB | ε C → f proc C { match the current token with f, proc A { and h k} move to t he next to ken; } case of the current token { a: - match the current token with a, and move to the next token; and move to the next token; proc B { proc B { - call B; case of the current token { - match the current token with e, b: - match the current token with b, and move to the next token; and move to the next token; and move to the next token; and move to the next token; c: - match the current token with c, - call B and move to the next token; e,d: do nothing - call B; } - match the current token with d, } and move to the next token; f: - call C follow set of B CS308 Compiler Theory 9 } } first set of C
Non-Recursive Predictive Parsing--LL(1)Parser Non-Recursive predictive parsing is a table-driven parser. It is a top-down parser. It is also known as LL(1)Parser. input buffer stack←→Non-recursiveoutput Predictive Parser Parsing Table CS308 Compiler Theory 10
Non-Recursive Predictive Parsing -- LL(1) Parser • Non-Recursive predictive parsing is a table-driven parser. • It is a top-down parser. • It is also known as LL(1) Parser. input buffer stack Non-recursive output Predictive Parser Parsin g Table CS308 Compiler Theory 10