Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Shift Reduce Parsing?
3.
Basic Operations in Shift-Reduce Parsing
4.
Shift-Reduce Parsing Working
5.
Examples
5.1.
Example 1:
5.2.
Example 2:
6.
Advantages of Shift Reduce Parsing
7.
Disadvantages of Shift Reduce Parsing
8.
Frequently Asked Questions
8.1.
What conflicts may occur during shift-reduce parsing?
8.2.
Which data structure is used for shift-reduce parsing?
8.3.
Can we call shift-reduce parsing as bottom-up parsing?
8.4.
Where does the handle in a shift reduce parser appear?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Shift Reduce Parsing

Author Pakhi Garg
2 upvotes

Introduction

A shift-reduce parser is a bottom-up parsing technique that uses a stack. It shifts input symbols onto the stack and reduces them based on grammar rules until the input is completely parsed. It continuously reduces or shifts symbols until a valid parse is achieved.

Shift Reduce Parsing

In this article, we will learn about what is shift-reduce parsing, its operations, and working with the help of some examples.

What is Shift Reduce Parsing?

The Shift reduce parsing is a type of bottom-up parsing as it generates a parse tree from the leaves (bottom) to the root(up).

  • In shift-reduce parsing, the input string is reduced to the starting symbol.
  • This reduction can be achieved by directly handling the rightmost derivation from the starting symbol to the input string.
  • Two Data Structure are required to perform shift-reduce parsing-
    • An input buffer to hold the input string.
    • stack to keep the grammar symbols for accessing the production rules.

Now, we will discuss the basic operations performed in shift-reduce parsing.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Basic Operations in Shift-Reduce Parsing

There are four basic operations a shift-reduce parser can perform:

  1. Shift- This operation involves moving the current symbol from the input buffer onto the stack.
     
  2. Reduce- When the parser knows the right hand of the handle is at the top of the stack, the reduce operation applies the applicable production rules, i.e., pops out the RHS of the production rule from the stack and pushes the LHS of the production rule onto the stack. 
     
  3. Accept- After repeating the shift and reduce operations, if the stack contains the starting symbol of the input string and the input buffer is empty, i.e., includes the $ symbol, the input string is said to be accepted.
     
  4. Error- If the parser cannot perform the shift or the reduce operation, also the string is not accepted, then it is said to be in the error state.

Now we will discuss the working of shift-reduce parsing.

Shift-Reduce Parsing Working

  • Initially, the stack contains the $ symbol, and the input buffer contains the input string with the $ symbol at its end.
Shift-Reduce Parsing Working
  • For performing the shift-reduce parsing, push the input symbols at the top of the stack (shift operation) until a handle ß appears on the top of a stack (reduce operation).
  • Repeat the above step until
    • An error is detected or
    • The string is accepted, i.e., the stack contains only the start symbol, and the input buffer becomes empty (has only the $ symbol).
Shift Reduce Parsing working 2
  • If we achieve the above configuration, the parsing will be completed successfully.

Now, let’s consider some examples to understand the shift-reduce parsing.

Examples

Before coming to examples, we must remember some rules.

  • Rule 1: If the priority of the incoming operator is higher than the operator's priority at the top of the stack, then we perform the shift action.
  • Rule 2: If the priority of the incoming operator is equal to or less than the operator's priority at the top of the stack, then we perform the reduce action.

Now we will take some examples to understand shift-reduce parsing.

Example 1:

Consider the following grammar.

E → E + E

E → E x E

E → id

Perform shift-reduce parsing for the input string “id + id x id”.

Solution: We will take a stack containing the $ symbol and place the given input string in the input buffer.

Note: The priority order of operators is: id > x > + > E > $.

Stack

Input Buffer

Parsing Action

$

id+idxid$

 

The top of the stack contains $ while the current input symbol is the starting symbol, i.e., id. The priority of id > $. Thus, we will follow rule 1 and will perform the shift operation.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

 

 

Now, the symbol at the top of the stack is id, and the current input symbol is +. Since the priority of + < id, we will follow rule 2 and perform the reduce operation.

For performing the reduce operation, we will check the grammar containing id on the right-hand side. Since E → id, we can reduce id by E.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

 

 

Next, the priority of + > E, perform the shift operation.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

 

 

Next, the priority of id > +, perform the shift operation.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

 

 

Next, the priority of x < id, perform the reduce operation. Since in the grammar E → id, we can reduce id by E.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

 

 

Next, the priority of x > E, perform the shift operation.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

Shift

$E+Ex

id$

 

 

Next, the priority of id > x, perform the shift operation.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

Shift

$E+Ex

id$

Shift

$E+Exid

$

 

 

Next, the priority of $ < id, perform the reduce operation. Since in the grammar E → id, we can reduce id by E.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

Shift

$E+Ex

id$

Shift

$E+Exid

$

Reduce by E → id

$E+ExE

$

 

 

Next, the priority of $ < E, we will perform the reduce operation. Since there is no grammar containing E, we will check the grammar containing xE. However, there is also no grammar containing xE, check the grammar containing ExE. We find that E → E x E. So, we will reduce ExE by E.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

Shift

$E+Ex

id$

Shift

$E+Exid

$

Reduce by E → id

$E+ExE

$

Reduce by E → E x E

$E+E

$

 

 

Next, the priority of $ < E, we will perform the reduce operation. Since there is no grammar containing E, we will check the grammar containing +E. However, there is also no grammar containing +E, check the grammar containing E+E. We find that E → E + E. So, we will reduce E+E by E.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

Shift

$E+Ex

id$

Shift

$E+Exid

$

Reduce by E → id

$E+ExE

$

Reduce by E → E x E

$E+E

$

Reduce by E → E + E

$E

$

 

 

Now, the stack only contains the starting symbol of the input string E and the input buffer is empty, i.e., includes the $ symbol. Hence, the parser will accept the string and will be completed.

Stack

Input Buffer

Parsing Action

$

id+idxid$

Shift

$id

+idxid$

Reduce by E → id

$E

+idxid$

Shift

$E+

idxid$

Shift

$E+id

xid$

Reduce by E → id

$E+E

xid$

Shift

$E+Ex

id$

Shift

$E+Exid

$

Reduce by E → id

$E+ExE

$

Reduce by E → E x E

$E+E

$

Reduce by E → E + E

$E

$

Accept

 

Example 2:

Consider the following grammar.

S → S + S

S → S - S

S → (S)

S → a

Perform shift-reduce parsing for the input string “a1-(a2+a3)”.

Solution: The priority order of operators is: a1/a2/a3 > () > +/- > S > $.

Stack

Input Buffer

Parsing Action

$

a1-(a2+a3)$

Shift

$a1

-(a2+a3)$

Reduce by S → a

$S

-(a2+a3)$

Shift

$S-

(a2+a3)$

Shift

$S-(

a2+a3)$

Shift

$S-(a2

+a3)$

Reduce by S → a

$S-(S

+a3)$

Shift

$S-(S+

a3)$

Shift

$S-(S+a3

)$

Reduce by S → a

$S-(S+S

)$

Shift

$S-(S+S)

$

Reduce by S → S + S

$S-(S)

$

Reduce by S → (S)

$S-S

$

Reduce by S → S - S

$S

$

Accept

Advantages of Shift Reduce Parsing

  • Efficiency: Shift-reduce parsing is generally more efficient than other parsing techniques, especially for larger and more complex grammars.
  • Bottom-up Parsing: Shift-reduce parsers work in a bottom-up manner. It allows them to handle a broader class of grammar, including left-recursive grammar.
  • Generality: Shift-reduce parsing is a general technique applicable to various programming languages and grammar. It makes it versatile and widely applicable.
  • Error Recovery: Shift-reduce parsers can recover errors by detecting and handling errors encountered during parsing. It allows the process to continue with subsequent input.
  • Handling Ambiguity: Shift-reduced parsers can effectively handle grammar and provide multiple parse trees or interpretations when required.

Disadvantages of Shift Reduce Parsing

  • Shift-Reduce Conflicts: Shift-reduce parsing can encounter conflicts when multiple actions are applicable at a given parsing state, which results in shift-reduce conflicts.
  • Ambiguity Resolution: While shift-reduce parsers can handle ambiguity, resolving ambiguities can be complex and require additional grammar modifications or priority rules.
  • Grammar Design Complexity: Designing an efficient and unambiguous grammar suitable for shift-reduce parsing can be challenging and require revision and careful consideration.
  • Handling Left Recursion: Shift-reduce parsers may struggle with left-recursive grammars, increasing parsing time and leading to inefficiencies.
  • Limited Lookahead: Shift-reduce parsers typically have limited lookahead capabilities, making it challenging to make optimal parsing decisions in complex situations.

Frequently Asked Questions

What conflicts may occur during shift-reduce parsing?

Shift-reduce parsing conflicts, specifically shift-reduce conflicts, can arise when the parser faces a choice between shifting a token onto the stack or reducing a set of tokens to a production.

Which data structure is used for shift-reduce parsing?

Shift-reduce parsing uses a stack data structure to keep track of the parsed symbols and a lookahead buffer to determine parsing actions based on the input tokens.

Can we call shift-reduce parsing as bottom-up parsing?

Yes, shift-reduce parsing is a type of bottom-up parsing. It starts from the input tokens and builds the parse tree from the leaves (tokens) towards the root (start symbol).

Where does the handle in a shift reduce parser appear?

In a shift-reduce parser, the handle appears at the top of the stack when a portion of the stack's content matches the right-hand side of a production, indicating a reduction action.

Conclusion

In this article, we have studied shift-reduce parsing of syntax analysis. We went through the concept thoroughly, discussing the basic operations, working, and examples of shift-reduce parsing.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning!

Live masterclass