Bottom-up parsingWelcome to the running exampleExample input, parse treeChaotic bottom-up parsingSlide 5Don’t celebrate yet!Lesson from chaotic parserWhat’s this non-determinism, again?Non-deterministic chaotic parserProperties of the n.d. chaotic parserOverviewNon-deterministic LR parserTwo simple rules to restrict # of instancesWait a minute!Wait a minute! (cont)LR parser actionsExample of a correct LR parser sequenceExample of an incorrect LR parser sequenceSlide 19Slide 20Revisit the incorrect LR parser sequenceDoomed stack configurationsHow to find doomed parser instances?The stack-checking DFAConstructing the stack-checking DFAProf. Bodik CS 164 Lecture 9 1Bottom-up parsingCS1643:30-5:00 TT10 EvansProf. Bodik CS 164 Lecture 92Welcome to the running example•we’ll build a parser for this grammar: E E + T | E – T | T T T * int | int •see, the grammar is–left-recursive–not left-factored•… and our parser won’t mind!–we can make the grammar ambiguous, tooProf. Bodik CS 164 Lecture 93Example input, parse tree•input:int + int * int•its parse tree:int + *int intTETTEProf. Bodik CS 164 Lecture 94Chaotic bottom-up parsingKey idea: build the derivation in reverseint + *int intEETTTEE + TT + TT + T * intint + T * intint + int * intProf. Bodik CS 164 Lecture 95Chaotic bottom-up parsing•The algorithm:1. stare at the input string s•feel free to look anywhere in the string2. find in s a right-hand side r of a production Nr•ex.: found int for a production T int3. reduce the found string r into its non-terminal N–ex.: replace int with T4. if string reduced to start non-terminal–we’re done, string is parsed, we got a parse tree5. otherwise continue in step 1Prof. Bodik CS 164 Lecture 96Don’t celebrate yet!•not guaranteed to parse a correct string–is this surprising?•example:int + *int intETand we are stuckint + E * intint + T * intint + int * intProf. Bodik CS 164 Lecture 97Lesson from chaotic parser•Lesson: –if you’re lucky in selecting the string to reduce next, then you will successfully parse the string•How to “beat the odds”?–that is, how to find a lucky sequence of reductions that gives us a derivation of the input string?–use non-determinism!Prof. Bodik CS 164 Lecture 98What’s this non-determinism, again?•You took cs164, then became a stock broker:–want 16 celebrities sign you as their private broker–here’s how: send free advice to 1024 celebrities•to half of them: “MSFT will go up tomorrow, buy now”•guess what’s your advice for the other 512 folks–send free advice to 512 who got the correct advice•to half of them: “AAPL will go down tomorrow, sell now”–…–then apply for a broker job with the 16 who got six correct predictions in a row•that’s sorta how we’ll parse the stringProf. Bodik CS 164 Lecture 99Non-deterministic chaotic parserThe algorithm:1. find in input all strings that can be reduced–assume there are k of them2. create k copies of the (partially reduced) input–it’s like spawning k identical instances of the parser3. in each instance, perform one of k reductions–and then go to step 1, advancing and further spawning all parser instances4. stop when at least one parser instance reduced the string to start non-terminalProf. Bodik CS 164 Lecture 910Properties of the n.d. chaotic parserClaim: –the input will be parsed by (at least) one parser instance But:–exponential blowup: k*k*k*…*k parser copies–(how many k’s are there?)Also:–Multiple (usually many) instances of the parser produce the correct parse tree. This is wasteful.Prof. Bodik CS 164 Lecture 911Overview•Chaotic bottom-up parser–it will give us the parse tree, but only if it’s lucky•Non-deterministic bottom-up parser–creates many parser instances to make sure at least one builds the parse trees for the string–an instance either builds the parse tree or gets stuck•Non-deterministic LR parser (next)–restrict where a reduction can be made–as a result, fewer instances necessaryProf. Bodik CS 164 Lecture 912Non-deterministic LR parser•What we want: –create multiple parser instances•to find the lucky sequence of reductions–but the parse tree is found by at most one instance•zero if the input has syntax errorProf. Bodik CS 164 Lecture 913Two simple rules to restrict # of instances1. split the input in two parts: •right: unexamined by parser •left: in the parser (we’ll do the reductions here)int + int * int after reduction: T + int * int 2. reductions allowed only on right part next to split allowed: T + int * int after reduction: T + T * int not allowed: int + int * int after reduction: T + int * int hence, left part of string can be kept on the stackProf. Bodik CS 164 Lecture 914Wait a minute!Aren’t these restrictions fatally severe? –the doubt: no instance succeeds to parse the inputNo. recall: one parse tree multiple derivations–in n.d. chaotic parser, the instances that build the same parse tree each follow a different derivationProf. Bodik CS 164 Lecture 915Wait a minute! (cont)recall: two interesting derivations–left-most derivation, right-most derivationLR parser builds right-most derivation –but does so in reverse: first step of derivation is the last reduction (the reduction to start nonterminal)–example coming in two slideshence the name:–L: scan input left to right–R: right-most derivationso, if there is a parse tree, LR parser will build it!–this is the key theoremProf. Bodik CS 164 Lecture 916LR parser actions•The left part of the string will be on the stack–the symbol is the top of stack•Two simple actions–reduce: •like in chaotic parser,•but must replace a string on top of stack–shift:•shifts to the right, •which moves a new token from input onto stack, potentially enabling more reductions•These actions will be chosen non-deterministicallyProf. Bodik CS 164 Lecture 917Example of a correct LR parser sequenceA “lucky” sequence of shift/reduce actions (string parsed!):int + *int intEETTTEE + TE + T * int E + T *int E + T * int E + int * int E + int * int E + int * intT + int * intint + int * int int + int * intProf. Bodik CS 164 Lecture 918Example of an incorrect LR parser sequenceWhere did the parser instance make the mistake?int + *int intTTTstuck!
View Full Document
Unlocking...