Operator Precedence Parsing

In this class, We discuss Operator Precedence Parsing.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of Bottom-up parsing techniques. Click Here.

Operator precedence parsing is a bottom-up parsing technique.

The operator precedence parsing work for ambiguous grammar also.

Condition for Operator Precedence Parsing Grammar:

1) The right side of the production should not contain epsilon.

2) There should be adjacent two non-terminals.

Example:

A – BD

We discuss a few relations in operator precedence parsing.

The reader will get clarity about the relations when we explain the example.

We use the below relation symbols in operator precedence parsing.

1) >

2) <

3) =

We are writing operator precedence parsing for identifying expressions.

In the expressions, we follow precedence and associative rules.

Precedence:

‘+ < *’ the relation < shows the precedence of operator + is less when compared to operator *.

Similarly, ‘* > +’ the relation > shows the precedence of operator * is greater than +.

Associative:

If we want to maintain the associative, how do we do?

Example:

a+b+c For operator + we follow left-associative. so a+b should be evaluated first.

So we assign ‘+ > +’ The left operator + from the expression a+b and right operator + from the expression +c.

We maintain left-associative, so we gave relation ‘+ > +’

If we need to maintain right-associative, we give the relation ‘+<+’.

Operator precedence parsing table:

For the given grammar, we need to generate an operator precedence table according to the required conditions.

We use the below grammar in our example.

E – E + E | E * E | id

The above grammar is ambiguous. Still, we can use it to identify the expression provided parsing table.

We are using the operators + and * in our example.

The operator * has the highest precedence when compared to operator +.

The symbol id is given the highest precedence out of all symbols.

The symbol $ is given the least precedence out of all symbols.

The below table shows the operator precedence table.

The precedence table [id, id] is showing blank. The blank symbol means an error occurred.

From the grammar, there is the possibility of getting id -id side by side.

We may get id + id or id * id.

[id,+] is given relation >. because id has the highest precedence.

Why [*,*] given relation >. because we follow left-associative.

The [$, $] is going to the acceptance state.

The reader will get much clarity about the operator precedence table with an example.

How do we parse the input string?

Example:

The input string is id + id * id.

We use a stack during the parsing.

Initially, We fill the stack with a dollar symbol.

We place the end of the input string with a dollar symbol.

We follow two conditions to parse the input string.

1) SHIFT

The below table shows the complete parsing of the input string.

The first line of the table is taking shift action.

The stack top is a dollar symbol, and the input shows id.

So look at the block [$, id]. We have the relation <. so we do shift action.

Whenever the relation is <or =, we do shift action.

The shift action will send the input symbol onto the stack.

We send the id onto the stack.

2) REDUCE

The second line in the above table is [id, +] having relation >.

We do reduce action.

We reduce the symbol id to non-terminal E.

Important:

Understand the point why we give id the highest precedence?

Here we have seen [id, +] before taking + onto the stack. First, reduce id to E. then only we encounter E + E.

The 3rd line in the above table has a non-terminal at the top of the stack.

So don,t consider non-terminal. Go with the first terminal symbol encountered on top of the stack.

We have [$,+] we do shift action.

Similarly, We do the remaining parsing.

Finally, we take acceptance if we find [$, $].