Bottom up Parser Table Construction David Walker COS 320 Programming 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 table finally the magic how to construct an LR parser table yet to read input stack NUM PLUS NUM PLUS NUM PLUS NUM exp PLUS exp PLUS 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 automaton finally the magic how to construct an LR parser table yet to read input stack NUM PLUS NUM PLUS NUM PLUS NUM exp PLUS exp PLUS 5 minus finite automaton terminals and non terminals label edges 2 exp 1 exp plus 3 exp 4 finally the magic how to construct an LR parser table yet to read input stack NUM PLUS NUM PLUS NUM PLUS NUM exp PLUS exp PLUS 5 minus finite automaton terminals and non terminals label edges 2 exp 1 state annotated stack 1 exp plus 3 exp 4 finally the magic how to construct an LR parser table yet to read input stack NUM PLUS NUM PLUS NUM PLUS NUM exp PLUS exp PLUS 5 minus finite automaton terminals and non terminals label edges 2 exp 1 state annotated stack 1 exp 2 exp plus 3 exp 4 finally the magic how to construct an LR parser table yet to read input stack NUM PLUS NUM PLUS NUM PLUS NUM exp PLUS exp PLUS 5 minus finite automaton terminals and non terminals label edges 2 exp 1 state annotated stack 1 exp 2 PLUS 3 exp plus 3 exp 4 finally the magic how to construct an LR parser table yet to read input stack NUM PLUS NUM PLUS NUM PLUS NUM exp PLUS exp PLUS 5 minus finite automaton terminals and non terminals label edges 2 exp 1 exp plus 3 exp 4 state annotated stack 1 exp 2 PLUS 3 1 exp 2 PLUS 3 this state and input tell us what to do next The 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 accept states Terminal seen next ID NUM 1 2 sn shift goto state n 3 rk reduce by rule k a accept n error The 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 13 states Terminal seen next ID NUM Non terminals X Y Z 2 sn shift goto state n gn goto state n 3 rk reduce by rule k a accept n error 1 The 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 13 states Terminal seen next ID NUM Non terminals X Y Z 2 sn shift goto state n gn goto state n 3 rk reduce by rule k a accept n error 1 LR 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 1 state number S S S L S x collection of LR 0 items LR 1 states look very similar it is just that the items contain some look ahead info LR 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 t Grammar 0 S S S L S x L S L L S 1 S S LR 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 t Grammar 0 S S S L S x L S L L S 1 S S S L LR 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 t Grammar 0 S S S L S x L S L L S 1 S S S L S x Full Closure LR 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 automaton Grammar 0 S S S L S x L S L L S S S S L S x Grammar 0 S S S L S x L S L L S S S S L S x S S S Grammar 0 S S S L S x L S L L S S S S L S x S S S S L L S L L S S L S x Grammar 0 S S S L S x L S L L S S S S L S x S S S S L L S L L S S L S x Grammar 0 S S S L S x L S L L S S …