Shift Reduce Parsing - Naukri Code 360

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.

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.
- A stack to keep the grammar symbols for accessing the production rules.

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

Basic Operations in Shift-Reduce Parsing

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

Shift- This operation involves moving the current symbol from the input buffer onto the stack.
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.
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.
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.

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).

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.