Shift Reduce Parser

Bottom up parsing is also known as shift reduce parsing. In this the string is reduce till we reach start symbol or error. In this parse is constructed in reverse mannaer i.e. from leaves to root, in other word from bottom to top. The more general format of shift reduce paring is LR parsing(Left to Right parsing).Bottom up parsing is also known as shift reduce parsing. In this the string is reduce till we reach start symbol or error. In this parse is constructed in reverse manner i.e. from leaves to root, in other word from bottom to top. The more general format of shift reduce paring is LR parsing(Left to Right parsing).

To perform shift reduce parsing, we should have input string stored in input buffer and stack for storing and accessing the production rules.

We can divide the process of parsing in four steps.

Shift- In this symbol is moved from input buffer onto the stack

Reduce- If handle is present at the top of stack, then reduction is done by using appropriate production rule.

Accept- If input buffer is empty and start symbol is at the top of stack, then parsing action is called Accpet. It mean the input string is successfully accepted by the grammer.

Error- If parser has nor accepted the input string nor can perform shift reduce action, then this situation leads to error.

Let’s understand above concept by solving one problem

Consider the following simple grammar

S->S+S
S->S-S
S->id

The input string is id+id-id
Perform shift reduce parsing to check whether the given is accepted by the grammar or not Initially $ symbol is pushed on to the stack and also applied at the end of input string

StackInput BufferParsing Action
$id+id-id$Shift
$id+id-id$Reduce by S->id
$S+id-id$Shift
$S+id-id$Shift
$S+id-id$Reduce by S->id
$S+S-id$Shift
$S+S-id$Shift
$S+S-id$Reduce by S->id
$S+S-S$Reduce by S->S+S
$S-S$Reduce by S->S-S
$S$Accept
Table.1 Parsing Table for ex.1

As you can see, start symbol is on the top of stack and input buffer is empty, we can say that the string is accepted.

Let us consider another example

S->S+S
S->S-S
S->id

The input string is id+id*id

Perform shift reduce parsing to check whether the given is accepted by the grammar or not

Initially $ symbol is pushed on to the stack and also applied at the end of input string

StackInput BufferParsing Action
$id+id*id$Shift
$id+id*id$Reduce by S->id
$S+id*id$Shift
$S+id*id$Shift
$S+id*id$Reduce by S->id
$S+S*id$Shift
$S+S*id$Shift
$S+S*id$Reduce by S->id
$S+S*S$Reduce by S->S+S
$S*S$Error Can’t reduce No such Production
Table.2 Parsing Table for ex.2

As you can see, although the input sting is empty, but stack top has a production which can not be reduced further to reach up to start symbol, so we have got an error.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *