# Operator-precedence grammar

An operator precedence grammar is a kind of grammar for formal languages.
Technically, an operator precedence grammar is a context-free grammar that has the property (among others) 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. A parser that exploits these relations is considerably simpler than more general-purpose parsers, such as LALR parsers. Operator-precedence parsers can be constructed for a large class of context-free grammars.

## Precedence relations

Operator precedence grammars rely on the following three precedence relations between the terminals:
| Relation | Meaning |
| $a\lessdot b$ | a yields precedence to b |
| $a\doteq b$ | a has the same precedence as b |
| $a\gtrdot b$ | a takes precedence over b |
These operator precedence relations allow to delimit the handles in the right sentential forms: $\lessdot$ marks the left end, $\doteq$ appears in the interior of the handle, and $\gtrdot$ marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles. The relations do not have the same properties as their un-dotted counterparts; e. g. $a\doteq b$ does not generally imply $b\doteq a$, and $b\gtrdot a$ does not follow from $a\lessdot b$. Furthermore, $a\doteq a$ does not generally hold, and $a\gtrdot a$ is possible.
Let us assume that between the terminals a$_i$ and a$_{i+1}$ there is always exactly one precedence relation. Suppose that $ is the end of the string. Then for all terminals b we define: $\$\lessdot b$ and $b\gtrdot \$$. If we remove all nonterminals and place the correct precedence relation: $\lessdot$, $\doteq$, $\gtrdot$ between the remaining terminals, there remain strings that can be analyzed by an easily developed bottom-up parser.

### Example

For example, the following operator precedence relations can be introduced for simple expressions:
    ${\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}$
They follow from the following facts:
* + has lower precedence than * (hence $+\lessdot *$ and $*\gtrdot +$).
* Both + and * are left-associative (hence $+\gtrdot +$ and $*\gtrdot *$).
The input string
    $\mathrm {id} _{1}+\mathrm {id} _{2}*\mathrm {id} _{3}$
after adding end markers and inserting precedence relations becomes
    $\$\lessdot \mathrm {id} _{1}\gtrdot +\lessdot \mathrm {id} _{2}\gtrdot *\lessdot \mathrm {id} _{3}\gtrdot \$$

## Operator precedence parsing

Having precedence relations allows to identify handles as follows:
* scan the string from left until seeing $\gtrdot$
* scan backwards (from right to left) over any $\doteq$ until seeing $\lessdot$
* everything between the two relations $\lessdot$ and $\gtrdot$, including any intervening or surrounding nonterminals, forms the handle
It is generally not necessary to scan the entire sentential form to find the handle.

## Operator precedence parsing algorithm

The algorithm below is from Aho et al.:

## Precedence functions

An operator precedence parser usually does not store the precedence table with the relations, which can get rather large. Instead, precedence functions f and g are defined. They map terminal symbols to integers, and so the precedence relations between the symbols are implemented by numerical comparison: ⁠$f(a)<g(b)$⁠ must hold if $a\lessdot b$ holds, etc.
Not every table of precedence relations has precedence functions, but in practice for most grammars such functions can be designed.

### Algorithm for constructing precedence functions

The below algorithm is from Aho et al.:
* Create symbols f$_a$ and g$_a$ for each grammar terminal a and for the end of string symbol;
* Partition the created symbols in groups so that f$_a$ and g$_b$ are in the same group if $a\doteq b$ (there can be symbols in the same group even if their terminals are not connected by this relation);
* Create a directed graph whose nodes are the groups. For each pair ⁠$(a,b)$⁠ of terminals do: place an edge from the group of g$_b$ to the group of f$_a$ if $a\lessdot b$, otherwise if $a\gtrdot b$ place an edge from the group of f$_a$ to that of g$_b$;
* If the constructed graph has a cycle then no precedence functions exist. When there are no cycles, let ⁠$f(a)$⁠ be the length of the longest path from the group of f$_a$ and let ⁠$g(a)$⁠ be the length of the longest path from the group of g$_a$.

### Example

Consider the following table (repeated from above):
    ${\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}$
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:
    id + * $ f 4 2 4 0 g 5 1 3 0

## Operator-precedence languages

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.
Operator-precedence languages enjoy many closure properties: union, intersection, complementation, concatenation, 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, that enables efficient parallel parsing.
There are also characterizations based on an equivalent form of automata and monadic second-order logic.