“The computer was born to solve problems that did not exist before.”

Random Posts

Monday, November 22, 2021

Shift reduce parsing

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.

Shift reduce parsing

  • 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:

S → S+S    
S → S-S    
S → (S)  
S → a

Input string:

a1-(a2+a3)  

Parsing table:


Shift reduce parsing 1

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

  1. Operator-Precedence Parsing
  2. LR-Parser

No comments:

Post a Comment

Post Top Ad

Your Ad Spot

Pages

SoraTemplates

Best Free and Premium Blogger Templates Provider.

Buy This Template