Operator precedence parsing

Compiler Design

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.

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.

Application

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

Hence in SNOBOL operator precedence parsing is done.