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
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
works on complete set of LR(1) grammer
generates large table and large number of states
LALR(1):–Look Ahead LR parser
works on intermediate size of grammer
number of states are same as that of SLR(1).
- Generic shift reduce strategy:
*if there is a handle on top of stack,reduce
*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.
E —> E+E
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
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
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.