MIT 6 035MIT 6.035 Top-Down Parsing Martin Rinard Laboratory for Computer Science Massachusetts Institute of Technology•parsers•Orientation • Language specification • Lexical structure – regular expressions • Syntactic structure – grammar This Lecture recursive descent This Lecture -recursive descent parsers • Code parser as set of mutually recursive procedures • Structure of program matches structure of grammarStructure of program matches structure of grammar••Starting Point • Assume lexical analysis has produced a sequence of tokensof tokens • Each token has a type and value • Types correspond to terminalsTypes correspond to terminals • Values to contents of token read in • ExamplesExamples • Int 549 – integer token with value 549 read in • if -if keyword, no need for a value if if keyword, no need for a value • AddOp + - add operator, value +t tpy pBasic Approach • Start with Start symbol B ild l f d i ti• Build a leftmost derivation • If leftmost symbol is nonterminal, choose a production and apply itproduction and apply it • If leftmost symbol is terminal, match against input • If all terminals match, have found a parse! •Key: find correct productions for nonterminalseGraphical Illustration of Leftmost DerivationDerivation Sentential Form NT1 T1 T2 T3 NT2 NT3 Apply Production Her Not Here Here•or conve may represent•Grammar for Parsing Exampleg p Start→ Expr • Set of tokens is Expr→ Expr+ Term Expr→ Expr - Term Expr→ Term Set of tokens is { +, -, *, /, Int }, where Int = [0-9][0-9]* F nience Expr→ Term Term→ Term *Int Term→ Term /Int For convenience, may represent each Int n token by n Term → IntParsing Example Start Parse Tree Remaining Input StartTree 2-2*2 Sentential Form StartStart Current Position in Parse TreeppParsing Example Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Expr p Applied Production Expr Start→ ExprCurrent Position in Parse TreeParsing ExampleParse TreeRemaining InputStartTree2-2*2StartExprSentential FormExpr - TermpTermExpr -Applied ProductionExpr TermExpr→Expr + TermppExpr→Expr - TermExpr→Expr - TermExpr→Term→epppExpr→TermParsing Example Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Term-TermTermExpr -Applied Production Term Term Term Expr→ Expr+ Term p p Expr→ Expr - Term Expr→ Term Expr→ TermpppParsing Example Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form TermExpr -Int -Term Applied Production Term Int Term Term→ IntIntpParsing Example Start Parse Tree Remaining Input MatchStartTree 2-2*2 Expr Match Input Token! Sentential Form 2 -TermTermExpr -2 Term Term Int 2pParsing Example Start Parse Tree Remaining Input MatchStartTree -2*2 Expr Match Input Token! Sentential Form 2 -TermTermExpr -2 Term Term Int 2pParsing Example Start Parse Tree Remaining Input MatchStartTree 2*2 Expr Match Input Token! Sentential Form 2 -TermTermExpr -2 Term Term Int 2pppParsing Example Start Parse Tree Remaining Input StartTree 2*2 Expr Sentential Form 2 -Term*IntTermExpr -Applied Production 2 Term Int Term Term Int* Term→ Term *IntInt 2pppParsing Example Start Parse Tree Remaining Input StartTree 2*2 Expr Sentential Form 2 -Int *IntTermExpr -Applied Production 2 Int Int Term Term Int* Term→ IntInt 2 IntpParsing Example MatchStart Parse Tree Remaining Input Match Input Token! StartTree 2*2 Expr Sentential Form 2 -2*IntTermExpr -2 2 Int Term Term Int* Int 2 Int 2pParsing Example MatchStart Parse Tree Remaining Input Match Input Token! StartTree *2 Expr Sentential Form 2 -2*IntTermExpr -2 2 Int Term Term Int* Int 2 Int 2pParsing Example MatchStart Parse Tree Remaining Input Match Input Token! StartTree 2 Expr Sentential Form 2 -2*IntTermExpr -2 2 Int Term Term Int* Int 2 Int 2pParsing Example Start Parse Tree Remaining Input Parse StartTree 2 Expr Parse Complete! Sentential Form 2 -2*2TermExpr -2 2 2 Term Term Int 2* Int 2 Int 2••t t tSummary • Three Actions (Mechanisms) Al d i d• Apply production to expand current nonterminal in parse tree Match current terminal (consuming input)Match current terminal (consuming input) • Accept the parse as correct • Parser generates preorder traversal of parse treeParser generates preorder traversal of parse tree • visit parents before children • visit siblings from left to rightvisit siblings from left to right •p yPolicy Problem • Which production to use for each nonterminal? • Classical Separation of Policy and Mechanism • One Approach: Backtracking • Treat it as a search problem • At each choice point, try next alternative • If it is clear that current try fails, go back to previous choice and try something differentprevious choice and try something different • General technique for searching • Used a lot in classical AI and natural languageggprocessing (parsing, speech recognition)Backtracking Exampleg p Start Parse Tree Remaining Input StartTree 2-2*2 Sentential Form StartStartppBacktracking Exampleg p Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Expr p Applied Production Expr Start → ExprpppBacktracking Exampleg p Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Expr + Term Term Expr + Applied Production Expr Term Expr → Expr + TermpppBacktracking Exampleg p Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Term + Term Term Expr + Applied Production Term Term Term Expr → TermpppBacktracking Exampleg p Start Parse Tree Remaining InputMatchStartTree 2-2*2 Expr Match Input Token! Sentential Form Int + Term Term Expr + Token! Applied Production Int Term Term Term → IntIntpppBacktracking Exampleg p Start Parse Tree Remaining InputCan’tStartTree -2*2 Expr Can t Match Input Sentential Form 2 -Term Term Expr + Input Token! Applied Production 2 Term Term Term → IntInt 2ppBacktracking Exampleg p Start Parse Tree Remaining InputSoStartTree 2-2*2 Expr So Backtrack! Sentential Form Expr p Applied Production Expr Start → ExprpppBacktracking Exampleg p Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Expr -Term Term Expr -Applied Production Expr Term Expr → Expr - TermpppBacktracking Exampleg p Start Parse Tree Remaining Input StartTree 2-2*2 Expr Sentential Form Term -Term Term Expr -Term Applied Production Term Term Expr → TermpppBacktracking Exampleg p Start Parse Tree Remaining Input