Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Jun 11, 2024
Difficulty: Medium

Operator Precedence Parsing

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

The parser is a compiler phase that accepts a token string as input and turns it into the matching intermediate representation using existing grammar. A parser is also known as a syntax analyzer. There are two types of parsing techniques in compiler design: Top-down parsing and Bottom-up parsing.

  • Top-Down ParsingIt is a parsing strategy that starts at the top of the parse tree and works its way down by applying grammatical rules.
     
  • Bottom-up Parsing- It is a parsing strategy that starts with the lowest level of the parse tree and works its way up using grammatical rules.

This article will discuss a type of bottom-up parsing- operator precedence parsing.

operator precedence parsing

Let’s start.

What is Operator Precedence Parsing?

Operator precedence parsing is a type of Shift Reduce Parsing. In operator precedence parsing, an operator grammar and an input string are fed as input to the operator precedence parser, which may generate a parse tree. Note that a parse tree will only be generated if the input string gets accepted. 

In operator precedence parsing, the shift and reduce operations are done based on the priority between the symbol at the top of the stack and the current input symbol.

The operator precedence parser performs the operator precedence parsing using operator grammar. 

Let’s see what operator grammar is.

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

What is Operator Grammar

A grammar is said to be an operator grammar if it follows these two properties:

  1. There should be no ε (epsilon) on the right-hand side of any production.
  2. There should be no two non-terminals adjacent to each other.

Examples of operator grammar are A + B, A - B, A x B, etc.

Now, let’s see the operator precedence relations.

Operator Precedence Relations

There are three operator precedence relations. These are-

  1. a ⋗ b: This relation implies that terminal “a” has higher precedence than terminal “b”.
  2. a ⋖ b: This relation implies that terminal “a” has lower precedence than terminal “b”.
  3. a ≐ b: This relation implies that terminal “a” has equal precedence to terminal “b”.

Now, let’s see the steps to perform the operator precedence parsing.

Precedence Table

A precedence table is used in operator precedence parsing to establish the relative precedence of operators and to resolve shift-reduce conflicts during the parsing process. The table instructs the parser when to shift (consume the input and proceed to the next token) and when to reduce (apply a production rule to reduce a set of tokens to a non-terminal symbol). It is an essential Data Structure for building a shift-reduce parser.

A precedence table is commonly expressed as a two-dimensional matrix, with rows and columns corresponding to grammatical operators. The table's elements define the order of precedence between the operators. 

Parsing Action

  • Add the $ sign to both ends of the provided input text
     
  • Now, scan the input string from left to right until you find the
     
  • Scan to the leftover all the equal precedence until you reach the first leftmost
     
  • Everything between the left and rightmost corners is a handle
     
  • $ on $ indicates that parsing was successful

Examples

Example 1: 

Operator grammar includes operators with different levels of precedence and associativity. The grammar specifies the syntactic structure of expressions, which can be used to derive parse trees for expressions.

In this example, you will learn how to parse a string step by step using operator precedence parsing.

Consider the following grammar 

T → T+T/TxT/id

With the help of the above grammar, parse the input string “id+idxid”.

Solution:

Step 1: 

Stack

Relation

Input Buffer

Parsing Action

$

 

id+idxid$

 

 

Step 2: The given grammar T → T+T/TxT/id is an operator grammar. So we don’t need to modify it.

Step 3: Operator Precedence Table

For drawing the operator precedence table, we will take the terminals present in the grammar on the left-hand side and right-hand side. 

  • If the symbol on the left-hand side has higher precedence than the right-hand side symbol, insert the ⋗ symbol in the table.
  • If the symbol on the left-hand side has lower precedence than the right-hand side symbol, insert the ⋖ symbol in the table.  
  • If the symbol on the left-hand side has equal precedence to the right-hand side symbol, insert nothing in the case of terminals, ⋗ symbol in the operators, and A in the case of the $ symbol in the table.  

Thus, the operator precedence table for the given grammar will be-

 

+

x

id

$

+

⋗ 

⋖ 

⋖ 

⋗ 

x

⋗ 

⋗ 

⋖ 

⋗ 

id

⋗ 

⋗ 

⋗ 

$

⋖ 

⋖ 

⋖ 

A

 

Step 4: Parsing the input string.

We will use the operator precedence table to parse the given input string. We will compare the symbol at the top of the stack and the current input symbol. Based on the precedence relation, we will perform either the shift operation or the reduced operation. 

Thus, the parsing will be as follows.

Stack

Relation

Input Buffer

Parsing Action

$

⋖ 

id+idxid$

Shift

$id

⋗ 

+idxid$

Reduce by T → id

$T

⋖ 

+idxid$

Shift

$T+

⋖ 

idxid$

Shift

$T+id

⋗ 

xid$

Reduce by T → id

$T+T

⋖ 

xid$

Shift

$T+Tx

⋖ 

id$

Shift

$T+Txid

⋗ 

$

Reduce by T → id

$T+TxT

⋗ 

$

Reduce by T → T x T

$T+T

⋗ 

$

Reduce by T → T + T

$T

A

$

Accept

 

The given string is parsed and accepted.

Step 5: Generating the parse tree.

We will start from the bottom of the stack and generate the parse tree.

Parse Tree

Example 2: 

Operator grammar defines the precedence and associativity of operators, which is necessary for successfully parsing phrases. It is simple to read and understand, making it a common choice for constructing programming language syntax.

In this example, you'll see how efficiently we can parse a string using the operational parsing method.

Consider the following grammar: 

E → E+T/T

T → TxV/V

V → a/b/c/d

With the help of the above grammar, parse the input string “a+bxcxd”.

Solution:

Step 1: 

Stack

Relation

Input Buffer

Parsing Action

$

 

a+bxcxd$

 

 

Step 2: The grammar E → E+T/T, T → TxV/V, V → a/b/c/d is an operator grammar. So we don’t need to modify it.

Step 3: Operator Precedence Table

The operator precedence table for the given grammar will be-

 

+

x

a

b

c

d

$

+

⋗ 

⋖ 

⋖ 

⋖ 

⋖ 

⋖ 

⋗ 

x

⋗ 

⋗ 

⋖ 

⋖ 

⋖ 

⋖ 

⋗ 

a

⋗ 

⋗ 

⋗ 

b

⋗ 

⋗ 

⋗ 

c

⋗ 

⋗ 

⋗ 

d

⋗ 

⋗ 

⋗ 

$

⋖ 

⋖ 

⋖ 

⋖ 

⋖ 

⋖ 

A

 

Step 4: Parsing the input string.

Stack

Relation

Input Buffer

Parsing Action

$

⋖ 

a+bxcxd$

Shift

$a

⋗ 

+bxcxd$

Reduce by V → a

$V

⋖ 

+bxcxd$

Shift

$V+

⋖ 

bxcxd$

Shift

$V+b

⋗ 

xcxd$

Reduce by V → b

$V+V

⋖ 

xcxd$

Shift

$V+Vx

⋖ 

cxd$

Shift

$V+Vxc

⋗ 

xd$

Reduce by V → c

$V+VxV

⋗ 

xd$

Reduce by T → V

$V+VxT

⋗ 

xd$

Reduce by E → T

$V+VxE

⋗ 

xd$

Error

 

Since no production contains E on its right-hand side, this parsing will lead to an error.

Thus, the given input string cannot be parsed using the operator precedence operator by the given grammar. So, we cannot generate a parse tree.

Advantages of Operator Precedence Parsing

  • Simplicity: Operator precedence parsing is straightforward to implement, making it accessible for simple grammar parsing.
  • Efficiency: It offers efficient parsing for expressions involving operators, with minimal overhead.
  • No Backtracking: This method does not require backtracking, leading to predictable parsing performance.
  • Handle Operator Precedence: It naturally handles different levels of operator precedence and associativity rules.
  • Deterministic: Provides a deterministic parsing method for a subset of grammars, ensuring consistent results.

Disadvantages of Operator Precedence Parsing

  • Limited Applicability: Effective primarily for arithmetic and similar expressions; not suitable for more complex grammatical structures.
  • Ambiguity Handling: Struggles with handling ambiguities in grammar without additional rules or modifications.
  • Restrictive Grammars: Requires grammars to be free of left recursion and to have a unique precedence relationship between every pair of terminals.
  • Error Recovery: Offers limited error recovery options, making it challenging to diagnose and correct syntax errors.
  • Complexity with Non-Operators: Incorporating non-operator tokens or constructs increases complexity and may require additional parsing mechanisms.

Frequently Asked Questions

Which binary operators have the same precedence in parsing?

There are three operator precedence relations. The relation a < b means that a has lower precedence than b. Similarly, a > b means that a has higher precedence than b. And the relations a = b, here a "has equal precedence as" b. So, = have the same precedence in parsing.

What are the common errors in operator precedence parsing?

Character pair errors and reducibility errors are the two types of operator precedence parsing mistakes. A character pair mistake arises when there is no operator precedence relationship in the grammar between two symbols. A reducibility error happens when you are unable to lower the handle to the left side of a production.

How are handles found in operator precedence parsing?

Having precedence relations allows to identify handles as follows: - Scan the string from the left until seeing •> - Scan backward the string from right to left until seeing <• - Everything between the two relations <• and •> forms the handle. Note that not the entire sentential form is scanned to find the handle.

Which class of operator has the highest precedence?

The operator precedence is in charge of evaluating expressions. In Java, the parenthesis() and Array subscript[] take the highest precedence. For example, addition and subtraction take higher precedence over left and right shift operators.

Which operator has the lowest precedence?

The operator with the lowest precedence is the assignment operator ("="). This means that in an expression, assignment is evaluated last, ensuring that all other operations are completed before assigning the result to a variable. This helps in maintaining the correct order of operations in programming.

Conclusion

In this article, we have studied operator precedence in compiler design. We went through the concept thoroughly, discussing operator grammar, operator precedence relations, steps, and examples.

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, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning! 

Topics covered
1.
Introduction
2.
What is Operator Precedence Parsing?
3.
What is Operator Grammar
4.
Operator Precedence Relations
5.
Precedence Table
6.
Parsing Action
7.
Examples
7.1.
Example 1: 
7.2.
Example 2: 
8.
Advantages of Operator Precedence Parsing
9.
Disadvantages of Operator Precedence Parsing
10.
Frequently Asked Questions
10.1.
Which binary operators have the same precedence in parsing?
10.2.
What are the common errors in operator precedence parsing?
10.3.
How are handles found in operator precedence parsing?
10.4.
Which class of operator has the highest precedence?
10.5.
Which operator has the lowest precedence?
11.
Conclusion