86

Shift reduce parsing

• Shift reduce parsing is a process of reducing a string to the start symbol of a grammar.
• Shift reduce parsing uses a stack to hold the grammar and an input tape to hold the string.

• Sift reduce parsing performs the two actions: shift and reduce. That’s why it is known as shift reduces parsing.
• 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.

Example:

Grammar:

Input string:

Parsing table:

There are two main categories of shift reduce parsing as follows:

1. Operator-Precedence Parsing
2. LR-Parser