Home » Operator Precedence Parsing

Operator Precedence Parsing

by Online Tutorials Library

Operator precedence parsing

Operator precedence grammar is kinds of shift reduce parsing method. It is applied to a small class of operator grammars.

A grammar is said to be operator precedence grammar if it has two properties:

  • No R.H.S. of any production has a∈.
  • No two non-terminals are adjacent.

Operator precedence can only established between the terminals of the grammar. It ignores the non-terminal.

There are the three operator precedence relations:

a ⋗ b means that terminal “a” has the higher precedence than terminal “b”.

a ⋖ b means that terminal “a” has the lower precedence than terminal “b”.

a ≐ b means that the terminal “a” and “b” both have same precedence.

Precedence table:

Operator precedence parsing 3

Parsing Action

  • Both end of the given input string, add the $ symbol.
  • Now scan the input string from left right until the ⋗ is encountered.
  • Scan towards left over all the equal precedence until the first left most ⋖ is encountered.
  • Everything between left most ⋖ and right most ⋗ is a handle.
  • $ on $ means parsing is successful.

Example

Grammar:

Given string:

Let us consider a parse tree for it as follows:

Operator precedence parsing 6

On the basis of above tree, we can design following operator precedence table:

Operator precedence parsing 7

Now let us process the string with the help of the above precedence table:

Operator precedence parsing 8

Next TopicLR Parser

You may also like