View source for Operator-precedence grammar

An '''operator precedence grammar''' is a kind of [[Formal grammar|grammar]] for [[formal language]]s.

Technically, an operator precedence grammar is a [[context-free grammar]] that has the property (among others)<ref>{{harvnb|Aho|Sethi|Ullman|1988|p=203}}</ref>
that no production has either an empty right-hand side or two adjacent nonterminals in its
right-hand side. These properties allow precedence [[Relation (mathematics)|relations]] to be
defined between the terminals of the grammar. A [[Operator-precedence parser|parser that exploits these relations]] is considerably simpler than more general-purpose parsers, such as [[LALR parser]]s. 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:<ref>{{harvnb|Aho|Sethi|Ullman|1988|pp=203–204}}</ref>

{| class="wikitable"
|-
! Relation
! Meaning
|-
| <math>a \lessdot b</math>
| {{mvar|a}} yields precedence to {{mvar|b}}
|-
| <math>a \doteq b</math>
| {{mvar|a}} has the same precedence as {{mvar|b}}
|-
| <math>a \gtrdot b</math>
| {{mvar|a}} takes precedence over {{mvar|b}}
|}

These operator precedence relations allow to delimit the [[Bottom-up parsing|handles]] in the [[Formal grammar|right sentential forms]]: <math>\lessdot</math> marks the left end, <math>\doteq</math> appears in the interior of the handle, and <math>\gtrdot</math> marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.<ref>{{harvnb|Aho|Sethi|Ullman|1988|pp=205–206}}</ref>
The relations do not have the same properties as their un-dotted counterparts;
e.&nbsp;g. <math>a \doteq b</math> does not generally imply <math>b \doteq a</math>, and <math>b \gtrdot a</math> does not follow
from <math>a \lessdot b</math>. Furthermore, <math>a \doteq a</math> does not generally hold, and <math>a \gtrdot a</math> is possible.

Let us assume that between the terminals {{mvar|a<sub>i</sub>}} and {{math|''a''<sub>''i''+1</sub>}} there is always exactly one precedence relation. Suppose that $ is the end of the string.
Then for all terminals {{mvar|b}} we define:  <math>\$ \lessdot b</math> and <math>b \gtrdot \$</math>. If we remove all nonterminals and place the correct precedence relation:
<math>\lessdot</math>, <math>\doteq</math>, <math>\gtrdot</math> 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:<ref name="Asu">{{harvnb|Aho|Sethi|Ullman|1988|p=205}}</ref>

:<math>\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}</math>

They follow from the following facts:<ref>{{harvnb|Aho|Sethi|Ullman|1988|p=204}}</ref>
* + has lower precedence than * (hence <math>+ \lessdot *</math> and <math>* \gtrdot +</math>).
* Both + and * are [[left-associative]] (hence <math>+ \gtrdot +</math> and <math>* \gtrdot *</math>).

The input string<ref name="Asu" />
: <math>\mathrm{id}_1 + \mathrm{id}_2 * \mathrm{id}_3</math>
after adding end markers and inserting precedence relations becomes
: <math>\$ \lessdot \mathrm{id}_1 \gtrdot + \lessdot \mathrm{id}_2 \gtrdot * \lessdot \mathrm{id}_3 \gtrdot \$</math>

== Operator precedence parsing ==

Having precedence relations allows to identify handles as follows:<ref name="Asu" />

* scan the string from left until seeing <math>\gtrdot</math>
* scan backwards (from right to left) over any <math>\doteq</math> until seeing <math>\lessdot</math>
* everything between the two relations <math>\lessdot</math> and <math>\gtrdot</math>, including any intervening or surrounding nonterminals, forms the handle

It is generally not necessary to scan the entire [[Formal grammar|sentential form]] to find the handle.

== Operator precedence parsing algorithm ==
The algorithm below is from Aho et al.:<ref>{{harvnb|Aho|Sethi|Ullman|1988|p=206}}</ref>
 '''If''' $ is on the top of the stack and ip points to $ '''then''' return
 '''else'''
     Let a be the top terminal on the stack, and b the symbol pointed to by ip
     '''if''' ''a'' <math>\lessdot</math> ''b'' '''or''' ''a'' <math>\doteq</math> ''b'' '''then'''
         push ''b'' onto the stack
         advance ip to the next input symbol
     '''else if''' ''a'' <math>\gtrdot</math> ''b'' '''then'''
         '''repeat'''
             pop the stack
         '''until''' the top stack terminal is related by <math>\lessdot</math> to the terminal most recently popped
     '''else''' error()
 '''end'''

== 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.<ref>{{harvnb|Aho|Sethi|Ullman|1988|pp=208–209}}</ref>
They map terminal symbols to integers, and so the precedence relations between the symbols are implemented by numerical comparison:
{{tmath|f(a) < g(b)}} must hold if <math>a \lessdot b</math> holds, etc.

Not every table of precedence relations has precedence functions, but in practice for most grammars such functions can be designed.<ref>{{harvnb|Aho|Sethi|Ullman|1988|p=209}}</ref>

=== Algorithm for constructing precedence functions ===
The below algorithm is from Aho et al.:<ref>{{harvnb|Aho|Sethi|Ullman|1988|pp=209–210}}</ref>
# Create symbols {{mvar|f<sub>a</sub>}} and {{mvar|g<sub>a</sub>}} for each grammar terminal {{mvar|a}} and for the end of string symbol;
# Partition the created symbols in groups so that {{mvar|f<sub>a</sub>}} and {{mvar|g<sub>b</sub>}} are in the same group if <math>a \doteq b</math> (there can be symbols in the same group even if their terminals are not connected by this relation);
# Create a [[Graph (discrete mathematics)|directed graph]] whose nodes are the groups. For each pair {{tmath|(a,b)}} of terminals do: place an edge from the group of {{mvar|g<sub>b</sub>}} to the group of {{mvar|f<sub>a</sub>}} if {{nobreak|<math>a \lessdot b</math>,}} otherwise if <math>a \gtrdot b</math> place an edge from the group of {{mvar|f<sub>a</sub>}} to that of {{mvar|g<sub>b</sub>}};
# If the constructed graph has a cycle then no precedence functions exist. When there are no cycles, let {{tmath|f(a)}} be the length of the [[longest path]] from the group of {{mvar|f<sub>a</sub>}} and let {{tmath|g(a)}} be the length of the longest path from the group of {{mvar|g<sub>a</sub>}}.

=== Example ===

Consider the following table (repeated from above):<ref>{{harvnb|Aho|Sethi|Ullman|1988|p=210}}</ref>

:<math>\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}</math>
Using the algorithm leads to the following graph:

     gid
       \
  fid   f*
     \  /
      g*
     /
   f+  
    | \
    |  g+
    |  |
   g$  f$

from which we extract the following precedence functions from the maximum heights in the [[directed acyclic graph]]:

:{| class="wikitable" 
|-
!
! 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 language]]s, and strictly contains [[visibly pushdown language]]s.<ref name=CrespiReghizziMandrioli-JCSS2012>{{harvnb|Crespi Reghizzi|Mandrioli|2012}}</ref>

Operator-precedence languages enjoy many closure properties: union, intersection, complementation,<ref name=CrespiReghizziMandrioliMartin-1978>{{harvnb|Crespi Reghizzi|Mandrioli|Martin|1978}}</ref> concatenation,<ref name=CrespiReghizziMandrioli-JCSS2012 /> 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,<ref>{{harvnb|Barenghi|Crespi Reghizzi|Mandrioli|Panella|2015}}</ref> that enables efficient parallel parsing.

There are also characterizations based on an equivalent form of automata and monadic second-order logic.<ref>{{harvnb|Lonati|Mandrioli|Panella|Pradella|2015}}</ref>

== Notes ==
{{Reflist}}

== References ==
* {{cite book |last=Aho |first=Alfred V. |last2=Sethi |first2=Ravi |last3=Ullman |first3=Jeffrey D. |date=1988 |title=Compilers — Principles, Techniques, and Tools |publisher=Addison-Wesley}}
*{{cite journal|last1=Crespi Reghizzi|first1=Stefano|last2=Mandrioli|first2=Dino|title=Operator precedence and the visibly pushdown property|journal=Journal of Computer and System Sciences|year=2012|volume=78|issue=6|pages=1837–1867|doi=10.1016/j.jcss.2011.12.006|doi-access=free}}
*{{cite journal|last1=Crespi Reghizzi|first1=Stefano|last2=Mandrioli|first2=Dino|last3=Martin|first3=David F.|title=Algebraic Properties of Operator Precedence Languages|journal=Information and Control|year=1978|volume=37|issue=2|pages=115–133|doi=10.1016/S0019-9958(78)90474-6|doi-access=free}}
*{{cite journal|last1=Barenghi|first1=Alessandro|last2=Crespi Reghizzi|first2=Stefano|last3=Mandrioli|first3=Dino|last4=Panella|first4=Federica|last5=Pradella|first5=Matteo|title=Parallel parsing made practical|journal=Science of Computer Programming|year=2015|volume=112|issue=3|pages=245–249|doi=10.1016/j.scico.2015.09.002|doi-access=free|hdl=11311/971391|hdl-access=free}}
*{{cite journal|last1=Lonati|first1=Violetta|last2=Mandrioli|first2=Dino|last3=Panella|first3=Federica|last4=Pradella|first4=Matteo|title=Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization|journal=SIAM Journal on Computing|year=2015|volume=44|issue=4|pages=1026–1088|doi=10.1137/140978818|hdl=2434/352809|hdl-access=free}}

== Further reading ==
* {{Cite journal | last = Floyd | first = R. W. | authorlink = Robert W. Floyd | title = Syntactic Analysis and Operator Precedence | journal = Journal of the ACM | volume = 10 | issue = 3 | pages = 316–333 | date=July 1963 | doi = 10.1145/321172.321179| s2cid = 19785090 | doi-access = free }}

== External links ==
* Nikolay Nikolaev: [http://homepages.gold.ac.uk/nikolaev/cis324.htm IS53011A Language Design and Implementation], Course notes for CIS&nbsp;324, 2010.

{{Parsers}}

{{DEFAULTSORT:Operator-Precedence Grammar}}
[[Category:Formal languages]]