Bottom-up Parser Table ConstructionProgramming Language Parsingfinally the magic: how to construct an LR parser tableSlide 4Slide 5Slide 6Slide 7Slide 8The Parse TableSlide 10Slide 11LR(0) parsingSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31computing parse tableSlide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53LR(0)Slide 55Slide 56SLRLR(1) & LALRGrammar RelationshipssummaryBottom-up Parser Table ConstructionDavid WalkerCOS 320Programming Language Parsing•LL(k) (top-down) parsing–compute nullable, first, follow sets then parsing table–use synchronizing tokens (Follow(X)) for error recovery–derive ML program •LR(k) parsing -- more powerful than LL(k) parsers–according to parser table:•shift tokens from input on to stack•reduce stack symbols using grammar rules•accept or signal errors–Fisher-Burke error repair•global technique (try every possible insertion/replacement/substitution in k-token window)–Now the magic: how to construct the parser tablefinally the magic: how to construct an LR parser table•At every point in the parse, the LR parser table tells us what to do next–shift, reduce, error or accept•To do so, the LR parser keeps track of the parse “state” ==> a state in a finite automatonexp PLUS ( exp PLUSNUM PLUS ( NUM PLUS NUM ) PLUS NUMyet to readinput:stack:finally the magic: how to construct an LR parser tableexp PLUS ( exp PLUSNUM PLUS ( NUM PLUS NUM ) PLUS NUMyet to readinput:stack:1423expplusexp5minusexpfinite automaton;terminals and non terminalslabel edges(finally the magic: how to construct an LR parser tableexp PLUS ( exp PLUSNUM PLUS ( NUM PLUS NUM ) PLUS NUMyet to readinput:stack:1423expplusexp5minusexpfinite automaton;terminals and non terminalslabel edges1 state-annotated stack:(finally the magic: how to construct an LR parser tableexp PLUS ( exp PLUSNUM PLUS ( NUM PLUS NUM ) PLUS NUMyet to readinput:stack:1423expplusexp5minusexpfinite automaton;terminals and non terminalslabel edges1 exp 2 state-annotated stack:(finally the magic: how to construct an LR parser tableexp PLUS ( exp PLUSNUM PLUS ( NUM PLUS NUM ) PLUS NUMyet to readinput:stack:1423expplusexp5minusexpfinite automaton;terminals and non terminalslabel edges1 exp 2 PLUS 3state-annotated stack:(finally the magic: how to construct an LR parser tableexp PLUS ( exp PLUSNUM PLUS ( NUM PLUS NUM ) PLUS NUMyet to readinput:stack:1423expplusexp5minusexpfinite automaton;terminals and non terminalslabel edges1 exp 2 PLUS 3 ( 1 exp 2 PLUS 3state-annotated stack:(this stateand inputtell us whatto do nextThe Parse Table•At every point in the parse, the LR parser table tells us what to do next according to the automaton state at the top of the stack–shift, reduce, error or acceptstates Terminal seen next ID, NUM, := ...12 sn = shift & goto state n3 rk = reduce by rule k... a = acceptn = errorThe Parse Table•Reducing by rule k is broken into two steps:–current stack is:A 8 B 3 C ....... 7 RHS 12–rewrite the stack according to X ::= RHS:A 8 B 3 C ....... 7 X–figure out state on top of stack (ie: goto 13)A 8 B 3 C ....... 7 X 13states Terminal seen next ID, NUM, := ... Non-terminals X,Y,Z ...12 sn = shift & goto state n gn = goto state n3 rk = reduce by rule k... a = acceptn = errorThe Parse Table•Reducing by rule k is broken into two steps:–current stack is:A 8 B 3 C ....... 7 RHS 12–rewrite the stack according to X ::= RHS:A 8 B 3 C ....... 7 X–figure out state on top of stack (ie: goto 13)A 8 B 3 C ....... 7 X 13states Terminal seen next ID, NUM, := ... Non-terminals X,Y,Z ...12 sn = shift & goto state n gn = goto state n3 rk = reduce by rule k... a = acceptn = errorLR(0) parsing•each state in the automaton represents a collection of LR(0) items:–an item is a rule from the grammar combined with “@” to indicate where the parser currently is in the input•eg: S’ ::= @ S $ indicates that the parser is just beginning to parse this rule and it expects to be able to parse S then $ next•A whole automaton state looks like this: S’ ::= @ S $S ::= @ ( L )S ::= @ x1state numbercollection ofLR(0) items• LR(1) states look very similar, it is just that the items contain some look-ahead infoLR(0) parsing•To construct states, we begin with a particular LR(0) item and construct its closure–the closure adds more items to a set when the “@” appears to the left of a non-terminal–if the state includes X ::= s @ Y s’ and Y ::= t is a rule then the state also includes Y ::= @ tS’ ::= @ S $1Grammar:0. S’ ::= S $•S ::= ( L )•S ::= x•L ::= S•L ::= L , SLR(0) parsing•To construct states, we begin with a particular LR(0) item and construct its closure–the closure adds more items to a set when the “@” appears to the left of a non-terminal–if the state includes X ::= s @ Y s’ and Y ::= t is a rule then the state also includes Y ::= @ tS’ ::= @ S $S ::= @ ( L )1Grammar:0. S’ ::= S $•S ::= ( L )•S ::= x•L ::= S•L ::= L , SLR(0) parsing•To construct states, we begin with a particular LR(0) item and construct its closure–the closure adds more items to a set when the “@” appears to the left of a non-terminal–if the state includes X ::= s @ Y s’ and Y ::= t is a rule then the state also includes Y ::= @ tS’ ::= @ S $S ::= @ ( L )S ::= @ x1Grammar:Full Closure0. S’ ::= S $•S ::= ( L )•S ::= x•L ::= S•L ::= L , SLR(0) parsing•To construct an LR(0) automaton:–start with start rule & compute initial state with closure–pick one of the items from the state and move “@” to the right one symbol (as if you have just parsed the symbol)•this creates a new item ...•... and a new state when you compute the closure of the new item•mark the edge between the two states with:–a terminal T, if you moved “@” over T–a non-terminal X, if you moved “@” over X –continue until there are no further ways to move “@” across items and generate new states or new edges in the automatonS’ ::= @ S $S ::= @ ( L )S ::= @ xGrammar:0. S’ ::= S $•S ::= ( L )•S ::= x•L ::= S•L ::= L , SS’ ::= @ S $S ::= @ ( L )S ::= @ xGrammar:S’ ::= S @ $S0. S’ ::= S $•S ::= ( L )•S ::= x•L ::= S•L ::= L , SS’ ::= @ S $S ::= @ ( L )S ::= @ xGrammar:S’ ::= S