Technically, an operator precedence grammar is a context-free grammar that has the property (among others)[1] that no production has either an empty right-hand side or two adjacent nonterminals in its right-hand side.
These properties allow precedence relations to be defined between the terminals of the grammar.
Operator-precedence parsers can be constructed for a large class of context-free grammars.
Operator precedence grammars rely on the following three precedence relations between the terminals:[2] These operator precedence relations allow to delimit the handles in the right sentential forms:
Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.
Let us assume that between the terminals ai and ai+1 there is always exactly one precedence relation.
If we remove all nonterminals and place the correct precedence relation:
For example, the following operator precedence relations can be introduced for simple expressions:[4] They follow from the following facts:[5] The input string[4] after adding end markers and inserting precedence relations becomes Having precedence relations allows to identify handles as follows:[4] It is generally not necessary to scan the entire sentential form to find the handle.
The algorithm below is from Aho et al.:[6] An operator precedence parser usually does not store the precedence table with the relations, which can get rather large.
[7] They map terminal symbols to integers, and so the precedence relations between the symbols are implemented by numerical comparison:
[8] The below algorithm is from Aho et al.:[9] Consider the following table (repeated from above):[10] Using the algorithm leads to the following graph: from which we extract the following precedence functions from the maximum heights in the directed acyclic graph: The class of languages described by operator-precedence grammars, i.e., operator-precedence languages, is strictly contained in the class of deterministic context-free languages, and strictly contains visibly pushdown languages.
[11] Operator-precedence languages enjoy many closure properties: union, intersection, complementation,[12] concatenation,[11] and they are the largest known class closed under all these operations and for which the emptiness problem is decidable.
Another peculiar feature of operator-precedence languages is their local parsability,[13] that enables efficient parallel parsing.
There are also characterizations based on an equivalent form of automata and monadic second-order logic.