Top-Down Parsing

Top-Down Parsing
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
MIT MIT 6 6 .035 035 Top-Down Parsing Martin Rinard Laboratory for Computer Science Massachusetts Institute of Technology Orientation • Language specification • Lexical structure – regular expressions • Syntactic structure – grammar • • This This Lecture Lecture - recursive recursive d descent escent parsers parsers • Code parser as set of mutually recursive procedures • Structure Structure o of f p program rogram matches matches s structure tructure of of grammar grammar Starting Point • Assume lexical analysis has produced a sequence of of tokens tokens • Each token has a type and value • • Types Types c correspond orrespond t to o t terminals erminals • Values to contents of token read in • • Examples Examples • Int 549 – integer token with value 549 read in • if if - if if keyword, keyword, no no need need for for a a value value • AddOp + - add operator, value + Basic Approach • Start with Start symbol • B B uild ild a ll eft f tmost t d d erii vati tion • If leftmost symbol is nonterminal, choose a production production and and apply apply it it • If leftmost symbol is terminal, match against inp put • If all terminals match, have found a parse •Key y: find correct p productions for nonterminals Graphical Illustration of Leftmost Derivation Derivation Sentential Form NT T T T NT NT 1 1 2 3 2 3 Apply Production Not Here Her Her e e Grammar for Parsing g Examp p le Start→ Expr • Set Set o of f t tok okens ens iis s Expr→ Expr + Term +, -, , /, Int , where Expr→ Expr - Term Int = 0-90-9 Expr Expr→→ Te Ter rm m • • F Fo or r c con onv ve enience nience , ma may y r repr epre esent sent Term→ Term Int each Int n token by n Term→ Term / Int Term → Int Parsing Example Parse Remaining Input Tr Tre ee e Start Start 2-22 Sentential Form Start Start Current Position in Parse Tree Parsing Example Parse Remaining Input Tr Tre ee e Start Start 2-22 Expr p Sentential Form Expr Expr App pplied Production Start→ Expr Current Position in Parse Tree Parsing Example Parse Remaining Input Tr Tre ee e Start Start 2-22 Expr p Sentential Form Expr - Term Expr Expr - Te Ter rm m Expr→ Expr + Term App pplied Production Expr→ Expr - Term Expr→ Expr - Term Expr→ TermParsing Example Parse Remaining Input Tr Tre ee e Start Start 2-22 Expr p Sentential Form Expr - Term Te Ter rm m - Te Ter rm m Term App pplied Production Expr p →→ Expr p + Te erm Expr→ Expr - Term Expr→ Term Expr→ Term Expr→ Term Parsing Example Parse Remaining Input Tr Tre ee e Start Start 2-22 Expr p Sentential Form Expr - Term Int Int - Te Ter rm m Term App pplied Production Int Term→ IntParsing Example Parse Remaining Input Tr Tre ee e Match Match Start Start 2-22 Input Token Expr p Sentential Form Expr - Term 2 2 - Te Ter rm m Term Int 2 Parsing Example Parse Remaining Input Tr Tre ee e Match Match Start Start -22 Input Token Expr p Sentential Form Expr - Term 2 2 - Te Ter rm m Term Int 2 Parsing Example Parse Remaining Input Tr Tre ee e Match Match Start Start 22 Input Token Expr p Sentential Form Expr - Term 2 2 - Te Ter rm m Term Int 2 Parsing Example Parse Remaining Input Tr Tre ee e Start Start 22 Expr p Sentential Form Expr - Term 2 2 - Te Ter rm mInt Int Term Term Int App pplied Production Int 2 Term→ Term IntParsing Example Parse Remaining Input Tr Tre ee e Start Start 22 Expr p Sentential Form Expr - Term 2 2 - Int Int Int Int Term Term Int App pplied Production Int 2 Term→ Int Int Parsing Example Parse Remaining Input Tr Tre ee e Match Match Start Start 22 Input Token Expr p Sentential Form Expr - Term 2 2 - 2 2 Int Int Term Term Int Int 2 Int 2 Parsing Example Parse Remaining Input Tr Tre ee e Match Match Start Start 2 Input Token Expr p Sentential Form Expr - Term 2 2 - 2 2 Int Int Term Term Int Int 2 Int 2 Parsing Example Parse Remaining Input Tr Tre ee e Match Match Start Start 2 Input Token Expr p Sentential Form Expr - Term 2 2 - 2 2 Int Int Term Term Int Int 2 Int 2 Parsing Example Parse Remaining Input Tr Tre ee e Pa Par rs se e Start Start 2 Complete Expr p Sentential Form Expr - Term 2 2 - 2 2 2 2 Term Term Int 2 Int 2 Int 2