Chapter 4: Syntax Analysis Part 2: Top-Down ParsingMotivationBasic intuitionLookaheadPredictive ParsingExampleKey IdeaMatchingNo Matching?Dealing with non-terminalsOn the ExampleGain?Final outcomeNegative outcomeOverall Top-Down AlgorithmAre We Done ?The Lookahead WindowLookahead Size and LanguagesTop-Down ParsingSlide 20Recursive Descent Parsing ConceptsPredictive Parsing : RecursiveTransition Diagrams (TDs)How are Transition Diagrams Used ?How can Transition Diagrams be Simplified ?How can Transition Diagrams be Simplified ? (2)How can Transition Diagrams be Simplified ? (3)How can Transition Diagrams be Simplified ? (4)How can Transition Diagrams be Simplified ? (5)How can Transition Diagrams be Simplified ? (6)Additional Transition Diagram SimplificationsMotivating Table-Driven ParsingNon-Recursive / Table DrivenAlgorithm for Non-Recursive ParsingSlide 35Trace of ExampleLeftmost Derivation for the ExampleWhat’s the Missing Puzzle Piece ?Computing First(X) : All Grammar SymbolsComputing First(X) : All Grammar Symbols - continuedConceptually: What is First (E, T, …) in Derivation?Slide 42Example 2Computing Follow(A) : All Non-TerminalsConceptually: What is Follow in Derivation?Slide 46Computing Follow : 2nd ExampleFirst & Follow – One More LookSlide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Motivation Behind First & FollowConstructing Parsing TableConstructing Parsing Table - ExampleConstructing Parsing Table – Example 2Slide 67Slide 68Parsing Process Over TimeSlide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 87Slide 88LL(1) GrammarsError RecoveryPanic Mode RecoveryRevised Parsing Table / ExampleSkip & SynchRevised Parsing Table / Example(2)Phase-Level RecoveryHow Would You Implement TD ParserRevised Parsing Table:Revised Parsing Table: (2)How is Parser Constructed ?Final Comments – Top-Down ParsingCH4p2.1CSE4100Chapter 4: Syntax AnalysisChapter 4: Syntax Analysis Part 2: Top-Down Parsing Part 2: Top-Down ParsingProf. Steven A. DemurjianComputer Science & Engineering DepartmentThe University of Connecticut371 Fairfield Way, Unit 2155Storrs, CT [email protected]://www.engr.uconn.edu/~steve(860) 486 - 4818Material for course thanks to:Laurent MichelAggelos KiayiasRobert LeBarreCH4p2.2CSE4100MotivationMotivationSourceSourceWe have a grammarProductProductWe want a parsing algorithmIdeaIdeaSynthesize the algorithm from the grammarProblemProblemHow are we going to use the grammar ???Hint...Hint...We can look at the beginning of the input...CH4p2.3CSE4100Use a sliding window over the input streamUse a sliding window over the input streamBenefitBenefitReveal the input SlowlyA little bit at a time–1 token at a time–Maybe 2 at a time ?But systematically–Left to RightWhat kind of derivation can use tokens in this way?What kind of derivation can use tokens in this way?Basic intuitionBasic intuitionThe InputCH4p2.4CSE4100LookaheadLookaheadTechniqueTechniqueUse a window of lookaheadGuide a LEFTMOST derivation with the window contentSo...So...How to guide ?CH4p2.5CSE4100Predictive ParsingPredictive ParsingLookaheadLookaheadPredictive tool!Helps to select the right productionQuestionQuestionHow?Answered with an example...Answered with an example...CH4p2.6CSE4100ExampleExampleConsider the grammarConsider the grammarAnd the input fragmentAnd the input fragmentWhich production should we start with ?Which production should we start with ?Why?stmt → if expr then stmt else stmt| while expr do stmt| for ( expr ; expr ; expr) stmt| { stmtList } | lvalue = exprlvalue → idexpr → id | integerwhile x do { if x then ....CH4p2.7CSE4100Key IdeaKey IdeaUse the production bodyUse the production bodyTo know what can start a productionSelecting a productionSelecting a productionPick the rule that can start with the symbol in the lookahead window!Using the productionUsing the productionWhat should we do with chosen production? while expr do stmtProductionInputwhile x do { if x then ....MatchingMatchingCH4p2.8CSE4100MatchingMatchingWhen input matchesWhen input matchesEat the matched symbolsIn the productionIn the inputMove the window further downDeal with the rest of the productionHow?while expr do stmtProductionInputwhile x do { if x then ....CH4p2.9CSE4100No Matching?No Matching?What does it mean?What does it mean?Example belowExample belowIn production:NON-TERMINAL exprIn window:TERMINAL x [an identifier token]What should we do ?What should we do ?while expr do stmtProductionInputwhile x do { if x then ....CH4p2.10CSE4100Dealing with non-terminalsDealing with non-terminalsSimple...Simple...The non-terminal is defined somewhereThe non-terminal is defined by a set of productionsCorollaryCorollaryPop the non-terminalUse the lookahead to choose a production for NT.Push and RecurCH4p2.11CSE4100On the ExampleOn the ExampleRecall the grammar and the current stateRecall the grammar and the current statewhile expr do stmtProductionInputwhile x do { if x then ....stmt → if expr then stmt else stmt.... lvalue → idexpr → id | integer2. Choose production for expr result: expr → id3. Push & Recur...result:while id do stmtProductionInputwhile x do { if x then ....1. Pop result: exprCH4p2.12CSE4100Gain?Gain?RecallRecallThe topmost symbol ( id )The lookahead x [an instance of id]Gain?Gain?The top symbol and lookahead match!So....So....RecurRecursive call will match them and pop themKeep on goingCH4p2.13CSE4100Final outcomeFinal outcomeWhat can happen in the end ?What can happen in the end ?We “eat” (match) the entire inputMeaning ?We get “stuck” at some pointWhat does it mean (to be stuck)How can we get stuck ?CH4p2.14CSE4100Negative outcomeNegative outcomeWe can get stuck We can get stuck Lookahead window and topmost non-terminal yield...An empty prediction!This is the “classic” syntax errorExpecting xyz–A list of tokens predicting the productions of the current non-terminalGot abc–“abc” is the actual content of the lookahead windowSyntax error at file:line. Expecting xyz got abcCH4p2.15CSE4100Overall Top-Down AlgorithmOverall Top-Down