Tag: shift reduce parsing in compiler design

Shift Reduce Parser | Shift Reduce Parsing

Shift-Reduce Parser-

 

A shift-reduce parser is a bottom-up parser.

 

It takes the given input string and builds a parse tree-

  • Starting from the bottom at the leaves.
  • And growing the tree towards the top to the root.

 

 

Data Structures-

 

Two data structures are required to implement a shift-reduce parser-

  • A Stack is required to hold the grammar symbols.
  • An Input buffer is required to hold the string to be parsed.

 

Working-

 

Initially, shift-reduce parser is present in the following configuration where-

  • Stack contains only the $ symbol.
  • Input buffer contains the input string with $ at its end.

 

 

The parser works by-

  • Moving the input symbols on the top of the stack.
  • Until a handle β appears on the top of the stack.

 

The parser keeps on repeating this cycle until-

  • An error is detected.
  • Or stack is left with only the start symbol and the input buffer becomes empty.

 

 

After achieving this configuration,

  • The parser stops / halts.
  • It reports the successful completion of parsing.

 

Possible Actions-

 

A shift-reduce parser can possibly make the following four actions-

 

1. Shift-

 

In a shift action,

  • The next symbol is shifted onto the top of the stack.

 

2. Reduce-

 

In a reduce action,

  • The handle appearing on the stack top is replaced with the appropriate non-terminal symbol.

 

3. Accept-

 

In an accept action,

  • The parser reports the successful completion of parsing.

 

4. Error-

 

In this state,

  • The parser becomes confused and is not able to make any decision.
  • It can neither perform shift action nor reduce action nor accept action.

 

Rules To Remember

 

It is important to remember the following rules while performing the shift-reduce action-

  • If the priority of incoming operator is more than the priority of in stack operator, then shift action is performed.
  • If the priority of in stack operator is same or less than the priority of in stack operator, then reduce action is performed.

 

PRACTICE PROBLEMS BASED ON SHIFT-REDUCE PARSING-

 

Problem-01:

 

Consider the following grammar-

E → E – E

E → E x E

E → id

Parse the input string id – id x id using a shift-reduce parser.

 

Solution-

 

The priority order is: id > x > –

 

StackInput BufferParsing Action
$id – id x id $Shift
$ id– id x id $Reduce E → id
$ E– id x id $Shift
$ E –id x id $Shift
$ E – idx id $Reduce E → id
$ E – Ex id $Shift
$ E – E xid $Shift
$ E – E x id$Reduce E → id
$ E – E x E$Reduce E → E x E
$ E – E$Reduce E → E – E
$ E$Accept

 

Problem-02:

 

Consider the following grammar-

S → ( L ) | a

L → L , S | S

Parse the input string ( a , ( a , a ) ) using a shift-reduce parser.

 

Solution-

 

StackInput BufferParsing Action
$( a , ( a , a ) ) $Shift
$ (a , ( a , a ) ) $Shift
$ ( a, ( a , a ) ) $Reduce S → a
$ ( S, ( a , a ) ) $Reduce L → S
$ ( L, ( a , a ) ) $Shift
$ ( L ,( a , a ) ) $Shift
$ ( L , (a , a ) ) $Shift
$ ( L , ( a, a ) ) $Reduce S → a
$ ( L , ( S, a ) ) $Reduce L → S
$ ( L , ( L, a ) ) $Shift
$ ( L , ( L ,a ) ) $Shift
$ ( L , ( L , a) ) $Reduce S → a
$ ( L , ( L , S )) ) $Reduce L → L , S
$ ( L , ( L) ) $Shift
$ ( L , ( L )) $Reduce S → (L)
$ ( L , S) $Reduce L → L , S
$ ( L) $Shift
$ ( L )$Reduce S → (L)
$ S$Accept

 

Problem-03:

 

Consider the following grammar-

S → T L

T → int | float

L → L , id | id

Parse the input string int id , id ; using a shift-reduce parser.

 

Solution-

 

StackInput BufferParsing Action
$int id , id ; $Shift
$ intid , id ; $Reduce T → int
$ Tid , id ; $Shift
$ T id, id ; $Reduce L → id
$ T L, id ; $Shift
$ T L ,id ; $Shift
$ T L , id; $Reduce L → L , id
$ T L; $Shift
$ T L ;$Reduce S → T L
$ S$Accept

 

Problem-04:

 

Considering the string “10201”, design a shift-reduce parser for the following grammar-

S → 0S0 | 1S1 | 2

 

Solution-

 

StackInput BufferParsing Action
$1 0 2 0 1 $Shift
$ 10 2 0 1 $Shift
$ 1 02 0 1 $Shift
$ 1 0 20 1 $Reduce S → 2
$ 1 0 S0 1 $Shift
$ 1 0 S 01 $Reduce S → 0 S 0
$ 1 S1 $Shift
$ 1 S 1$Reduce S → 1 S 1
$ S$Accept

 

To gain better understanding about Shift-Reduce Parsing,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Operator Precedence Parsing

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.