Bottom up Parsing

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 stack
Implementing 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 bb 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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.