DFA for shift /reduce decisions The states of the dfa are used to determine Grammar if a handle is on top of the stack S→C C→AB Stack Input Action $0 aas start in state 0 A aas shift(and goto state 3) B 0a3 as reduce A→a(goto2) $0A2 as shift(goto 5) $0A2a5 s reduce B→a(goto4) $0A2B4 s reduce C→AB(otol) State To goto(o, C) $0C1 S| accept(S→C) State l C→·AB A→°a
Model of anir parser inputS, a a. S ck LR Parsing pros output el action goto Constructed with LROO method shift DFA SLR method realce LR(I) method, or accept LALR(I method
LR Parsing driver Configuration(=lr parser state) (50X1S1X2S2…Xm i+1 a, S) stack input If action[sm, ai ]= shift s then push a;, push s, and advance input (50X1S1X2S :·4mm s. a If action[sm, ai]=reduce A-B and goto[sm-nA]=s with r=lBl then pop 2r symbols, push A, and push s (S0X1S1X22…,Xn A n-r m-1 ) If action [sm, a, ] =accept then stop If action[sm, a; ]= error then attempt recovery
Example lr parse table action goto laminar state id I +*()SE TF 1.E→E+T 0s5 2.E→T acc 3.T→TF 2s7 4.T→F 5.F→(E) 6.F→id 23456 823 r6 r6 r6r6 Shift goto 5 7s5 10 r1)s7 10 3r3 production #1 1 5r5
Example LR Parsin Stack Input Action $0 id*id+ids shift 5 SO id 5 id+ids reduce 6 goto 3 lamma 0F3 "id+ids reduce 4 goto 2 l.E→E+T 0T2 id +ids shift 7 $0T2*7 2.E→T id+ids shift 5 $0T2*7id5 +ids reduce 6 goto 10 3.T→T*F 0T2*7F10 reduce 3 goto 4.T→F $0T2 +ids reduce 2 goto 1 5.F→(E) $0E1 +ids shift 6 6.F→id 0E1+6 ids shift 5 SOEl+aid 5 reduced goto $0E1+6F3 reduce 4 goto 9 $0E1+6T9 reduce 1 goto 1 0