Overview of Bottom up Parsing
- These parsers construct the parse tree starting from leaves to the root. i.e., in a bottom fashion
- This process can be accomplished by reducing the given string to the start symbol of the grammar
- Bottom up Parsing is followed by shift reduce parser
Example:
Consider the following CFG
D → TL;
T → int
T → float
T → char
L → L,id
L → id
input string : int id,id;
Shift Reduce Parsing or Technique
Shift Reduce Parser uses a stack containing grammar symbols. During the parser operation, symbols from the input are shifted onto the stackImplementing Shift Reduce Technique
The actions performed by parser are
Shift: The next input symbol is shifted on to the stack
Reduce: The parser knows that the right end of the handle is at the top of the stack. It then locates the left end of the handle within the stack and decides with what non-terminal must replace the handle.
Accept: Parser announces successful completion of parsing.
Error: An error occurred and parser calls and error recovery routine
Note: The parser may shift Zero or more symbols to find a handle.
Working
At each step in the parsing, a string matching the right side of a production is replaced by the symbol on the left until the entire string is replaced by the start symbol
Example:
Consider the grammar
S→ aAcBe
A →Ab | b
B → d and parsing of the string
w = abbcde
To reduce w to S, start scanning w from left to right to find substrings that matches right side of productions b and d to qualify
Replace b by A to get aAbcde (why not d will explained later)
Now replace Ab by A to get aAcde (why not d will explained later)
Now replace d by B to aAcBe and finally aAcBe by S
Reduction
The replacement of the right side of a production by the left side in the parsing processing is called Reduction
The entire process of shift reduce technique involves reducing the given string to the start symbol
The example shown requires 4 reductions to reduce the string to the start symbol
The reductions trace a right most derivation in reverse (canonical reduction sequence) of the string
Example: The right most derivation of the string abbcde is
S ⇒ a A c B e
⇒ a A c d e
⇒ a A b c d e
⇒ a b
b c d e
The reduction goes in the reverse direction (replaced
sub strings are underlined)
The reverse of a right most derivation is nothing but
shift reduce parser
