Syntax analysis PartⅡI Chapter 4
2 Bottom-Up Parsing . LR methods (Left-to-right, Rightmost derivation) - SLR, Canonical LR, LALR .Other special cases: - Shift-reduce parsing - Operator-precedence parsing
Operator-Precedence Parsin g Special case of shift-reduce parsing We will not further discuss(you can skip textbook section 4.6)
Shift-Reduce parsing Grammar Reducing a sentence: Shift-reduce corresponds S→ aBE abbcde to a rightmost derivation A→ Abel abcde S→aABe B→d d e a ad e a abe a abcde These match a bbcde roduction's p right-hand sides A A A B B a bbcd ea bbcd ea bbcd ea b bcd
andles a handle is a substring of gr rammar svmbols in a right-sentential form that matches a right-hand side of a production lamma abode S→aABe Abcde A→ Abclb aade H anale B→d a abe a bbcd e a abcde NOT a handle. because aaae further reductions will fail (result is not a sentential form)
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)