Recursive Descent Parsing - UMD

3y ago
71 Views
2 Downloads
171.99 KB
25 Pages
Last View : 1d ago
Last Download : 2m ago
Upload by : Eli Jorgenson
Transcription

Recursive Descent Parsing!Goal Determine if we can produce the string to be parsed from thegrammar's start symbol!Approach Construct a parse tree: starting with start symbol at root,recursively replace nonterminal with RHS of production!Key question: which production to use? There can be many productions for each nonterminal We could try them all, backtracking if we are unsuccessful But this is slow!!Answer: lookahead Keep track of next token on the input string to be processed Use this to guide selection of productionCMSC 330 - Spring 20111

Recursive Descent ExampleE id n { L }L E;L εE{L}E ; L{x 3;{y 4;};}x 3E{LE;lookaheadyCMSC 330 - Spring 2011 4;L}εLε2

Recursive Descent: Basic Strategy!!Initially, “current node” is start nodeWhen processing the current node, 4 possibilities Node is the empty stringØ Move to next node in DFS order that has not yet beenprocessed Node is a terminal that matches lookaheadØ Advance lookahead by one symbol and move to next node inDFS order to be processed Node is a terminal that does not match lookaheadØ Fail! String cannot be parsed Node is a nonterminalØ Pick a production based on lookahead, generate children, thenprocess children recursivelyCMSC 330 - Spring 20113

Recursive Descent Parsing (cont.)!Key step Choosing which production should be selected!Two approaches BacktrackingØ Ø Ø Choose some productionIf fails, try different productionParse fails if all choices fail Predictive parsingØ Ø Ø Analyze grammar to find “First sets” for productionsCompare with lookahead to decide which production to selectParse fails if lookahead does not match FirstCMSC 330 - Spring 20114

First Sets!Example Suppose the lookahead is x For grammar S xyz abcØ Select S xyz since 1st terminal in RHS matches x For grammar S A BØ !A x yB zSelect S A, since A can derive string beginning with xIn general We want to choose a production that can derive asentential form beginning with the lookahead Need to know what terminals may be first in anysentential form derived from a nonterminal / productionCMSC 330 - Spring 20115

First Sets!Definition First(γ), for any sentential form γ, is the set of initialterminals of all strings that γ may expand to We’ll use this to decide what production to apply!Examples Given grammar S xyz abcØ Ø First(xyz) { x }, First(abc) { a }First(S) First(xyz) U First(abc) { x, a } Given grammar S A BØ Ø Ø A x yB zFirst(x) { x }, First(y) { y }, First(A) { x, y }First(z) { z }, First(B) { z }First(S) { x, y, z }CMSC 330 - Spring 20116

Calculating First(γ)!For a terminal a First(a) { a }!For a nonterminal N If N ε, then add ε to First(N) If N α1 α2 . αn, then (note the αi are all thesymbols on the right side of one single production):Ø Ø Add First(α1α2 . αn) to First(N), where First(α1 α2 . αn) isdefined as First(α1) if ε First(α1) Otherwise (First(α1) – ε) First(α2 . αn)If ε First(αi) for all i, 1 i k, then add ε to First(N)CMSC 330 - Spring 20117

First( ) ExamplesE id n { L }L E;L εE id n { L } εL E;LFirst(id) { id }First(" ") { " " }First(n) { n }First("{") { "{" }First("}") { "}" }First(";") { ";" }First(E) { id, "{" }First(L) { id, "{", ε }First(id) { id }First(" ") { " " }First(n) { n }First("{") { "{" }First("}") { "}" }First(";") { ";" }First(E) { id, "{", ε }First(L) { id, "{", ";" }CMSC 330 - Spring 20118

Recursive Descent Parser Implementation!For terminals, create function parse a If lookahead is a then parse a consumes the lookaheadby advancing to the next token and then returns Otherwise fails with a parse error if lookahead is not a!For each nonterminal N, create a function parse N Called when we’re trying to parse a part of the inputwhich corresponds to (or can be derived from) N parse S for the start symbol S begins the parseCMSC 330 - Spring 20119

Parser Implementation (cont.)!The body of parse N for a nonterminal N doesthe following Let N β1 . βk be the productions of NØ Here βi is the entire right side of a production- a sequence ofterminals and nonterminals Pick the production N βi such that the lookahead isin First(βi)Ø Ø Ø It must be that First(βi) First(βj) for i jIf there is no such production, but N ε then returnOtherwise fail with a parse error Suppose βi α1 α2 . αn. Then call parse α1(); . ;parse αn() to match the expected right-hand side,and returnCMSC 330 - Spring 201110

Recursive Descent Parser!Given grammar S xyz abc First(xyz) { x }, First(abc) { a }!Parserparse S( ) {if (lookahead “x”) {parse x; parse y; parse z);}else if (lookahead “a”) {parse a; parse b; parse c;}else error( );}CMSC 330 - Spring 2011// S xyz// S abc11

Recursive Descent Parser!Given grammar S A B zA x yB First(A) { x, y }, First(B) { z }!parse A( ) {if (lookahead “x”)parse S( ) {parse x();// A xif ((lookahead “x”) else if (lookahead “y”)parse y();// A y(lookahead “y”))else error( );parse A( ); // S A}else if (lookahead “z”) parse B( ) {parse B( ); // S Bif (lookahead “z”)else error( );parse z();// B zelse error( );}}ParserCMSC 330 - Spring 201112

ExampleE id n { L }L E;L εFirst(E) { id, "{" }parse E( ) {parse L( ) {if (lookahead “id”) {if ((lookahead “id”) parse id();(lookahead “{”)) {parse (); // E id nparse E( );parse n();parse ; (); // L E ; L}parse L( );else if (lookahead “{“) {}parse { ();else ;// L εparse L( ); // E { L } }parse } ();}else error( );}CMSC 330 - Spring 201113

Things to Notice!If you draw the execution trace of the parser You get the parse tree!Examples Grammar GrammarS xyzS abc String “xyz”S A BA x yB z String “x”parse S( )parse x()parse y()parse z()CMSC 330 - Spring 2011S/ \x y zparse S( )parse A( )parse xS A x14

Things to Notice (cont.)!This is a predictive parser Because the lookahead determines exactly whichproduction to use!This parsing strategy may fail on some grammars Possible infinite recursion Production First sets overlap Production First sets contain ε!Does not mean grammar is not usable Just means this parsing method not powerful enough May be able to change grammarCMSC 330 - Spring 201115

Left Factoring!Consider parsing the grammar E ab ac First(ab) a First(ac) a Parser cannot choose between RHS based onlookahead!!Parser fails whenever A α1 α2 and First(α1) First(α2) ! ε or !Solution Rewrite grammar using left factoringCMSC 330 - Spring 201116

Left Factoring Algorithm!Given grammar A xα1 xα2 xαn β!Rewrite grammar as A xL β L α1 α2 αn!!Repeat as necessaryExamples S ab ac S aLL b c S abcA abB a S aLL bcA bB ε L bcA bB ε L bL’ εL’ cA BCMSC 330 - Spring 201117

Left Recursion!Consider grammar S Sa ε First(Sa) a, so we’re ok as far as which production Try writing parserparse S( ) {if (lookahead “a”) {parse S( );parse a (); // S Sa}else { }} Body of parse S( ) has an infinite loopØ if (lookahead "a") then parse S( ) Infinite loop occurs in grammar with left recursionCMSC 330 - Spring 201118

Right Recursion!Consider grammar S aS ε Again, First(aS) a Try writing parserparse S( ) {if (lookahead “a”) {parse a();parse S( ); // S aS}else { }} Will parse S( ) infinite loop?Ø Invoking parse tok( ) will advance lookahead, eventually stop Top down parsers handles grammar w/ right recursionCMSC 330 - Spring 201119

Expression Grammar for Top-Down ParsingE T E'E' ε ET P T'T' ε * TP n (E) Notice we can always decide what production tochoose with only one symbol of lookaheadCMSC 330 - Spring 201120

Tradeoffs with Other Approaches!Recursive descent parsers are easy to write The formal definition is a little clunky, but if you followthe code then it’s almost what you might have doneif you weren't told about grammars formally They're unable to handle certain kinds of grammars!Recursive descent is good for a simple parser Though tools can be fast if you’re familiar with them!Can implement top-down predictive parsing as atable-driven parser By maintaining an explicit stack to track progressCMSC 330 - Spring 201121

Tradeoffs with Other Approaches!More powerful techniques need tool support Can take time to learn tools!Main alternative is bottom-up, shift-reduce parser Replaces RHS of production with LHS (nonterminal) Example grammarØ S aA, A Bc, B b Example parseØ Ø abc aBc aA SDerivation happens in reverse Something to look forward to in CMSC 430CMSC 330 - Spring 201122

What’s Wrong With Parse Trees?!Parse trees contain too much information ExampleØ Ø ParenthesesExtra nonterminals for precedence This extra stuff is needed for parsing!But when we want to reason about languages Extra information gets in the way (too much detail)CMSC 330 - Spring 201123

Abstract Syntax Trees (ASTs)!An abstract syntax tree is a more compact,abstract representation of a parse tree, with onlythe essential partsparsetreeCMSC 330 - Spring 2011AST24

Abstract Syntax Trees (cont.)!Intuitively, ASTs correspond to the data structureyou’d use to represent strings in the language Note that grammars describe trees So do OCaml datatypes (which we’ll see later) E a b c E E E-E E*E (E)CMSC 330 - Spring 201125

CMSC 330 - Spring 2011 Recursive Descent: Basic Strategy ! Initially, “current node” is start node When processing the current node, 4 possibilities Node is the empty string Move to next node in DFS order that has not yet been processed Node is a terminal that matches lookahead Advance lookahead by one symbol and move to next node in

Related Documents:

Evaluate recursive rules for sequences. Write recursive rules for sequences. Translate between recursive and explicit rules for sequences. Use recursive rules to solve real-life problems. Evaluating Recursive Rules So far in this chapter, you have worked with explicit rules for the nth te

Unit 2 Day 5 Recursive and Explicit.notebook September 23, 2019 Mastery Work: Worksheet #4 I can define orally and in writing: sequence, term (u1), general term (un), recursive formula, recursive rule, arithmetic sequence, common difference I can write the recursive formula for an arithmetic sequence.

The parsing algorithm optimizes the posterior probability and outputs a scene representation in a "parsing graph", in a spirit similar to parsing sentences in speech and natural language. The algorithm constructs the parsing graph and re-configures it dy-namically using a set of reversible Markov chain jumps. This computational framework

Model List will show the list of parsing models and allow a user of sufficient permission to edit parsing models. Add New Model allows creation of a new parsing model. Setup allows modification of the license and email alerts. The file parsing history shows details on parsing. The list may be sorted by each column. 3-4. Email Setup

the parsing anticipating network (yellow) which takes the preceding parsing results: S t 4:t 1 as input and predicts future scene parsing. By providing pixel-level class information (i.e. S t 1), the parsing anticipating network benefits the flow anticipating network to enable the latter to semantically distinguish different pixels

Mirror descent 5-2 Convex and Lipschitz problems minimizex f (x) subject to x ! C f is convex andLf-Lipschitz continuous Mirror descent 5-35 Outline Mirror descent Bregman divergence Alternative forms of mirror descent Convergence analysis f (xt) !! f (xt),x " xt " " 1 2!t #x " xt#2

and the hubness phenomenon (Section 2.2), which, as we will de-monstrate later, has a significant impact on NN-Descent. 2.1 NN-Descent The main purpose of the NN-Descent algorithm is to create a good approximation of the true K-NNG, and to create it as fast as possi-ble. The basic assumption made by NN-Descent can be summarized

Access to Accounting Software – SAMS – Assessment book . 2 . Notes for students . This sample assessment is designed to demonstrate as many of the possible question types you may find in a live assessment. It is not designed to be used on its own to determine whether you are ready for a live assessment. In a live assessment, you will be required to upload documents as part of your evidence .