Operator Precedence Parser

Operator Grammar

Operator Grammar is a grammar in which:

• No Production right side is ε, and
• No Production has two adjacent non-terminals

Example:

E →E + E | E * E | (E) | id

S →a A c B e

A →A b | b

B →d

Exercise

Which of the following grammars are Operator Grammar?

• E →E A E | (E) | id , A →+ | *
• S →a | b | (T) , T →T S | S

Operator Precedence Parsing

For an operator grammar, one can easily construct a parser known as operator precedence parser which has the following advantages and limitations:

Advantages:

• The parser is simply a manipulation on tokens without any reference to the grammar
• Once the parser is constructed one can ignore the grammar

Limitations:

• By using this technique, only small class of grammars can be parsed
• Generally, this technique is used to build parsers for only expressions
• This technique can be used to construct the parser for an entire language provided the language is “all operators”. Example: SNOBOL
• Difficult to handle operators with two different precedence's. Example is minus, which can be unary or binary depending on the context.

Design

• In designing operator precedence parser for a grammar, three disjoint relations are defined known as Precedence Relations represented as, <., $\overset{.}{\mathop{=}}\,$ And .> between certain pairs of terminals
• For two terminals a and b, the remaining of the relations is

Relations	Meaning
a <.b	a yields precedence to b
a $\overset{.}{\mathop{=}}\,$ b	a has the same precedence as b
a .> b	a takes precedence over b

• These relations guide the way to select the handles

Important Points

The precedence relations are not similar to less than (<), equal (=) and greater than(>) in mathematics

The relations may not be disjoint, i.e., sometimes for any two terminal a and b, have two or more relations may hold simultaneously

Example: a <. B and a .> b may hold simultaneously

                a <.b, a $\overset{.}{\mathop{=}}\,$ b and a .> b may hold simultaneously.

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.