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
- 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.
