Shift Reduce Parser

In this class, We discuss Shift Reduce Parser.

For Complete YouTube Video: Click Here

The reader should have a prior understanding of the Bottom-up parsing example. Click Here.

Shift Reduce parsing identifies the acceptance of input strings in Bottom-up parsing.

We use an extra stack in shift-reduce parsing to parse the input string.

Actions in shift-reduce parsing.

1) Shift: Shift the next input symbol to the stack.

2) Reduce: Take elements from the stack. If they match the body of production, then reduce.

3) Accept: Successful completion

4) Error: Discover syntax mistake.

The below example shows the shift-reduce actions for the expression grammar.

Initially, the stack contains a dollar symbol.

The input string is placed in a buffer, and adding dollar at the end of the input string.

The first line shows shift action. The input id1 shifted to stack.

The second line is taking reduced action.

The id1 popped from the stack, and the non-terminal F pushed onto the stack.

The id1 matched the production F – id., so we took reduced action.

Important: When do we need to do shift and reduce?

The reader will get clarity on when to shift and reduce in our next classes.

In this class, you will understand the shift-reduce technique for accepting input strings.

Similarly, the remaining shift and reduced actions are shown in the table.

Finally, the stack remains with the starting non-terminal, and the input buffer containing the dollar is accepted state.