Compiler Design and Construction - Old Questions

3.  What is shift reduce parsing techniques? Show shift reduce parsing action for the string (x+x)*a, given the grammar

The process of reducing the given input string into the starting symbol is called shift-reducing parsing.

A shift reduce parser uses a stack to hold the grammar symbol and an input buffer to hold the input string W. 

Sift reduce parsing performs the two actions: shift and reduce.

• At the shift action, the current symbol in the input string is pushed to a stack.
• At each reduction, the symbols will replaced by the non-terminals. The symbol is the right side of the production and non-terminal is the left side of the production.

Now,

Given grammar;

Input String: (x+x)*a

Shift reduce parsing action for given input string is shown below:

At $S*a parser can neither perform shift action nor reduce action. Hence, error occurred.