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 )