Stack Implementation of Shift-Reduce parsing Stack Input Action d+idids shift + id"$ reduce E→id How to Grammar SE +id*ids shift SE+ id"ids shift resolve E→E+E SE+id sids| reduce E→id conflicts? E→E*E SE+E "ids shift(or reduce?) E→(E) SE+E d$ shift E→id SE+Eid s| reduce E→id SE+EE duce e E SE+E uceE→E Find handles E accept to reduce
Conflicts Shift-reduce and reduce-reduce conflicts are caused by The limitations of the LR parsing method(even when the grammar is unambiguous ambiguity of the grammar
Shift-Reduce parsing Shift-reduce conflicts Stack Input Action S. if E then S else. s shift or reduce? Ambiguous grammar S→ if e then s I if e then s else s I other R esolve in ravor of shift so else matches closest if
Shift-Reduce parsing Reduce-Reduce conflicts Stack Input Action $shift a$ reduce A→aorB→a? Grammar C→AB A B R esolve in favor of reduce A otherwise were stuck!
ROK Parsers: USe a dFa for Shift /reduce decisions start State l State l gotone C→AB lamma State goto(L,, B S→C l6: State l S→"goto(l4 C→AB C→AB C→·AB A B a oto(, a) B C an onlv goto(lo, a) State I State l reduce A→a B A→a B→a)