Top-Down ParsingOutlineSlide 3Slide 4In One SlideIntro to Top-Down ParsingRecursive Descent ParsingRecursive Descent ExampleRecursive Descent Example (2)Slide 10When Recursive Descent Does Not WorkSlide 12Elimination of Left RecursionExample of Eliminating Left RecursionMore Left Recursion EliminationGeneral Left RecursionSummary of Recursive DescentPredictive ParsersSometimes Things Are PerfectLL(1)Predictive Parsing and Left FactoringLeft-Factoring ExampleSlide 23LL(1) Parsing Table ExampleLL(1) Parsing Table Example AnalysisSlide 26LL(1) Parsing Tables: ErrorsUsing Parsing TablesLL(1) Parsing AlgorithmSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40LL(1) LanguagesQ: Movies (263 / 842) Q: Music (238 / 842) Q: Books (727 / 842) Top-Down Parsing. ReviewSlide 46Slide 47Slide 48Constructing Predictive Parsing TablesSlide 50Computing First SetsExample First Set ComputationComputing Follow SetsExample Follow Set ComputationConstructing LL(1) Parsing TablesLL(1) Table Construction ExampleSlide 57Avoid Multiple Definitions!Notes on LL(1) Parsing TablesSimple Parsing StrategiesHomework#1Top-Down ParsingTop-Down Parsing#2Extra Credit Question•Given this grammar G:–E  E + T–E  T–T  T * int–T  int–T  ( E )• Is the string int * (int + int) in L(G)? –Give a derivation or prove that it is not.#3Revenge of Theory•How do we tell if DFA P is equal to DFA Q?–We can do: “is DFA P empty?”•How?–We can do: “P := not Q” •How?–We can do: “P := Q intersect R” •How?– So do: “is P intersect not Q empty?”• Does this work for CFG X and CFG Y?•Can we tell if s is in CFG X?#4 Outline•Recursive Descent Parsing•Left Recursion•LL(1) Parsing– LL(1) Parsing Tables–LP(1) Parsing Algorithm•Constructing LL(1) Parsing Tables– First, Follow#5In One Slide•An LL(1) parser reads tokens from left to right and constructs a top-down leftmost derivation. LL(1) parsing is a special case of recursive descent parsing in which you can predict which single production to use from one token of lookahead. LL(1) parsing is fast and easy, but it does not work if the grammar is ambiguous, left-recursive, or not left-factored (i.e., it does not work for most programming languages).#6Intro to Top-Down Parsing• Terminals are seen in order of appearance in the token stream: t1 t2 t3 t4 t5The parse tree is constructed–From the top–From left to rightAt1BCt2Dt3t4t4#7Recursive Descent Parsing•We’ll try recursive descent parsing first–“Try all productions exhaustively, backtrack” •Consider the grammar E  T + E | T T  ( E ) | int | int * T •Token stream is: int * int• Start with top-level non-terminal E•Try the rules for E in order#8Recursive Descent Example•Try E0  T1 + E2 •Then try a rule for T1  ( E3 )–But ( does not match input token int•Try T1  int . Token matches. –But + after T1 does not match input token *•Try T1  int * T2–This will match but + after T1 will be unmatched•Have exhausted the choices for T1–Backtrack to choice for E0E  T + E | TT  ( E ) | int | int * T Input = int * int#9Recursive Descent Example (2)•Try E0  T1•Follow same steps as before for T1–And succeed with T1  int * T2 and T2  int–With the following parse treeE0T1int*T2intE  T + E | TT  ( E ) | int | int * T Input = int * int#10Recursive Descent Parsing•Parsing: given a string of tokens t1 t2 ... tn, find its parse tree•Recursive descent parsing: Try all the productions exhaustively– At a given moment the fringe of the parse tree is: t1 t2 … tk A …–Try all the productions for A: if A ! BC is a production, the new fringe is t1 t2 … tk B C … – Backtrack when the fringe doesn’t match the string – Stop when there are no more non-terminals#11When Recursive Descent Does Not Work•Consider a production S  S a:– In the process of parsing S we try the above rule– What goes wrong?•A left-recursive grammar has S + S for some Recursive descent does not work in such cases–It goes into an 1 loop#12What's Wrong With That Picture?#13Elimination of Left Recursion•Consider the left-recursive grammarS  S  | •S generates all strings starting with a  and followed by a number of • Can rewrite using right-recursion S   T T   T | #14Example ofEliminating Left Recursion•Consider the grammarS ! 1 | S 0 (  = 1 and  = 0 )It can be rewritten as S ! 1 T T ! 0 T | #15More Left Recursion Elimination•In generalS  S 1 | … | S n | 1 | … | m•All strings derived from S start with one of 1,…,m and continue with several instances of 1,…,n •Rewrite as S  1 T | … | m T T  1 T | … | n T | #16General Left Recursion•The grammar S  A  | A  S  is also left-recursive becauseS + S  •This left-recursion can also be eliminated•See book, Section 2.3•Detecting and eliminating left recursion are popular test questions#17Summary of Recursive Descent•Simple and general parsing strategy– Left-recursion must be eliminated first– … but that can be done automatically•Unpopular because of backtracking– Thought to be too inefficient (repetition)•We can avoid backtracking– Sometimes ...#18Predictive Parsers•Like recursive descent but parser can “predict” which production to use–By looking at the next few tokens– No backtracking •Predictive parsers accept LL(k) grammars– First L means “left-to-right” scan of input– Second L means “leftmost derivation”– The k means “predict based on k tokens of lookahead”•In practice, LL(1) is used#19Sometimes Things Are Perfect•The “.ml-lex” format you emit in PA2 •Will be the input for PA3–actually the reference “.ml-lex” will be used•It can be “parsed” with no lookahead –You always know just what to do next•Ditto with the “.ml-ast” output of PA3• Just write a few mutually-recursive functions•They read in the input, one line at a time#20LL(1)•In recursive descent, for each non-terminal and input token there may be a choice of which production to use•LL(1) means that for each non-terminal and token there is only one production that could lead to success•Can be specified as a 2D table– One dimension for current non-terminal to expand– One