Operator-precedence grammar

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:

These operator precedence relations allow to delimit the handles in the right sentential forms: $⋖$ marks the left end, $≐$ appears in the interior of the handle, and $⋗$ 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 ≐ b$ does not generally imply $b ≐ a$ , and $b ⋗ a$ does not follow from $a ⋖ b$ . Furthermore, $a ≐ a$ does not generally hold, and $a ⋗ 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: $$ ⋖ b$ and $b ⋗ $$ . If we remove all nonterminals and place the correct precedence relation: $⋖$ , $≐$ , $⋗$ 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}{ccccc} i d & + & * & $ \\ i d & ⋗ & ⋗ & ⋗ \\ + & ⋖ & ⋗ & ⋖ & ⋗ \\ * & ⋖ & ⋗ & ⋗ & ⋗ \\ $ & ⋖ & ⋖ & ⋖ \end{array}

They follow from the following facts:

+ has lower precedence than * (hence $+ ⋖ *$ and $* ⋗ +$ ).
Both + and * are left-associative (hence $+ ⋗ +$ and $* ⋗ *$ ).

The input string

{i d}_{1} + {i d}_{2} * {i d}_{3}

after adding end markers and inserting precedence relations becomes

$ ⋖ {i d}_{1} ⋗ + ⋖ {i d}_{2} ⋗ * ⋖ {i d}_{3} ⋗ $

4 more chapters are free with a Lably account.

Operator precedence parsing

Having precedence relations allows to identify handles as follows:

scan the string from left until seeing $⋗$
scan backwards (from right to left) over any $≐$ until seeing $⋖$
everything between the two relations $⋖$ and $⋗$ , 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.:

<b id="mwgg">If</b> $ is on the top of the stack and ip points to $ <b id="mwgw">then</b> return <b id="mwhA">else</b> Let a be the top terminal on the stack, and b the symbol pointed to by ip <b id="mwhQ">if</b> <i id="mwhg">a</i> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt53" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\lessdot"}}' id="mwhw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \lessdot }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⋖<!-- ⋖ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lessdot }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48abe158799d6c5ee0a960cec7e5321a5bf0ad61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \lessdot }"/></span> <i id="mwiA">b</i> <b id="mwiQ">or</b> <i id="mwig">a</i> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt54" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\doteq"}}' id="mwiw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \doteq }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>≐<!-- ≐ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \doteq }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de69082f1885891812d259864e762e1543db2d6a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.307ex; margin-bottom: -0.478ex; width:1.808ex; height:2.009ex;" alt="{\displaystyle \doteq }"/></span> <i id="mwjA">b</i> <b id="mwjQ">then</b> push <i id="mwjg">b</i> onto the stack advance ip to the next input symbol <b id="mwjw">else if</b> <i id="mwkA">a</i> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt55" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\gtrdot"}}' id="mwkQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \gtrdot }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⋗<!-- ⋗ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gtrdot }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ade4309e8e12df271a3a66cda676411771e74fe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \gtrdot }"/></span> <i id="mwkg">b</i> <b id="mwkw">then</b> <b id="mwlA">repeat</b> pop the stack <b id="mwlQ">until</b> the top stack terminal is related by <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt56" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\lessdot"}}' id="mwlg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \lessdot }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⋖<!-- ⋖ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lessdot }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48abe158799d6c5ee0a960cec7e5321a5bf0ad61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle \lessdot }"/></span> to the terminal most recently popped <b id="mwlw">else</b> error() <b id="mwmA">end</b>

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 ⋖ 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 ≐ 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 ⋖ b$ , otherwise if $a ⋗ 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}{ccccc} i d & + & * & $ \\ i d & ⋗ & ⋗ & ⋗ \\ + & ⋖ & ⋗ & ⋖ & ⋗ \\ * & ⋖ & ⋗ & ⋗ & ⋗ \\ $ & ⋖ & ⋖ & ⋖ \end{array}

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:

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.

Precedence relations

Example

Operator precedence parsing

Operator precedence parsing algorithm

Precedence functions

Algorithm for constructing precedence functions

Example

Operator-precedence languages

More in Computing and communication