operator precedence parsing

RGPV: Compiler Design: Unit 2



A grammar G is said to be operator precedence if it possess following properties:

1.      No production on the right side is Ɛ.

2.      There should not be any production rule possessing 2 adjacent non terminals at the right hand side.

Consider the grammar for arithmetic expression

       E→ EAE| (E)| -E| id

       A → +|*|/ |-| ^

This grammar is not an operator precedent grammar as in the production rule

       E → EAE

It contains 2 consecutive non terminals. Hence we first convert it into equivalent operator    precedence grammar by removing A.

      E → E+E|E*E|E/E|E-E|E^E

      E → (E)|-E| id

In Operator precedence parsing we first define precedence relations <· = and ·> between pair of terminals. The meaning of these relations is

1.      p <· q means p gives more precedence than q.

2.      p ·> q means p takes precedence over q.

3.      p=q means has same precedence as q.

These meanings appear similar to the less than, equal to and greater than operators. Now by considering the precedence relation between the arithmetic operators we will construct the operator precedence table. The operators precedence’s we have considered are id, +, *, $.




Now consider the string

id+ id*id

We will insert $ symbols at the start and end of the input string. We will also insert precedence operator by referring the precedence relation table.

$ <· id ·> + <· id ·>* <· id ·>$

We will follow following steps to parse the given string-

1.      Scan the input from left to right until ·> is encountered.

2.      Scan backwards over = until <· is encountered.

3.      The handle is a string between <· and ·>.



The parsing can be done as follows:



Advantages of operator precedence parsing

1.      This type of parsing is simple to implement.

2.      Operator precedence parser is the only parser which can parse ambiguous grammar also.


Disadvantages of operator precedence parsing

1.      This type of parsing can be applicable for only small class of grammars.



The operator precedence parsing is done in a language having operators. Hence in SNOBOL operator precedence parsing is done.
















Related topics

Professor Jayesh video tutorial

Please use contact page in this website if you find anything incorrect or you want to share more information about the topic discussed above.