Name all conflicts in Bottom up parser,explain with example why conflict occured


#1

Name each type of conflict that occur in bottom up parser.
Give an example of each and explain why that particular conflict has occur.


#2

first let us discuss about bottom up parsing

Bottom up parsing starts from leaf node of a tree and works in upward direction till it reaches the root node.Here we start from a sentence and then apply production rules in reverse manner inorder to reach the start symbol.the image given below depicts the bottom up parsers available.

bottom up–>shift-reduce–>LR parsing.
LR parsing----1.SLR parsing
2.LR parser
3.LALR parser
shift-reduce parsing:–the shift reduce parsing uses 2 unique steps for bottom up parsing.these steps are known as shift step and reduce step.

shift step:–the shift step refers to advancement of the input pointer to nextinput symbol,which is called the shift symbol.the symbol is pushed onto the stack.the shifted symbol is treated as a single node of the parse tree.

reduce step:–when the parse finds a complete grammer rules(RHS) and replaces it to (LHS) it is known as reduce step.this occurs when the top of stack contains a handle.to reduce,a POP function is performed on the stackwhich pops off the handle and replaces it with LHS non terminal symbol.

LR parser:–LR parser is a non recursive
,shift-reduce,bottom up parser.it uses a wide class of context-free grammerwhich makes it the most efficient syntax analysis technique.there are three widely used algorithms available for constructing an LR parser:
SLR(1):–simple LR parser:
works on smallest case of grammer
few number of states,hence very small table
simple and fast construction
LR(1):–LR parser
works on complete set of LR(1) grammer
generates large table and large number of states
slow construction
LALR(1):–Look Ahead LR parser
works on intermediate size of grammer
number of states are same as that of SLR(1).

CONFLICTS:

  • Generic shift reduce strategy:
    *if there is a handle on top of stack,reduce
    *otherwise,shift.
    *if it is legal to shift or reduce there is a SHIFT-REDUCE CONFLICT.
    *if it is legal to reduce by two different productions,there is a REDUCE-REDUCE CONFLICT.

SOURCES OF CONFLICTS:–
ambiguous grammars always cause conflicts.
but beware,so do many non ambiguous grammars.

CONFLICTS EXAMPLE:–
E —> E+E
l E*E
l (E)
l int

one shift-reduce parse:–

l int * int + int shift
… …
E * E l + int reduce E–>E * E
E l + int shift
E + l int shift
E + int l reduce E–>int
E+E l reduce E–>E+E
E l

another shift-reduce parse:–

l int * int + int shift
… …
E * E l +int shift
E * E + l int shift
E * E + int l reduce E–>int
E * E + E l reduce E–>E+E
E * E l reduce E–>E * E
E l

points on example:

in the second step E * E l + int we can either shift or reduce by E–>E * E
choice determines associativity of + and *
grammar can be rewritten to enforce precedence.
precedence declarations are an alternative.