# 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[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. 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:[2]

Relation Meaning
${\displaystyle a\lessdot b}$ a yields precedence to b
${\displaystyle a\doteq b}$ a has the same precedence as b
${\displaystyle a\gtrdot b}$ a takes precedence over b

These operator precedence relations allow to delimit the handles in the right sentential forms: ${\displaystyle \lessdot }$ marks the left end, ${\displaystyle \doteq }$ appears in the interior of the handle, and ${\displaystyle \gtrdot }$ marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.[3] The relations do not have the same properties as their un-dotted counterparts; e. g. ${\displaystyle a\doteq b}$ does not generally imply ${\displaystyle b\doteq a}$, and ${\displaystyle b\gtrdot a}$ does not follow from ${\displaystyle a\lessdot b}$. Furthermore, ${\displaystyle a\doteq a}$ does not generally hold, and ${\displaystyle a\gtrdot a}$ is possible.

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.[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.[14]

## References

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley.
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property". Journal of Computer and System Sciences. 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006.
• Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). "Algebraic Properties of Operator Precedence Languages". Information and Control. 37 (2): 115–133. doi:10.1016/S0019-9958(78)90474-6.
• Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Parallel parsing made practical". Science of Computer Programming. 112 (3): 245–249. doi:10.1016/j.scico.2015.09.002.
• Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization". SIAM Journal on Computing. 44 (4): 1026–1088. doi:10.1137/140978818. hdl:2434/352809.