Operator-precedence grammar

Operator precedence grammars rely on the following three precedence relations between the terminals:{{harvnb|Aho|Sethi|Ullman|1988|pp=203–204}}

These operator precedence relations allow to delimit the handles in the right sentential forms: $\backslash lessdot$ marks the left end, $\backslash doteq$ appears in the interior of the handle, and $\backslash gtrdot$ marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.{{harvnb|Aho|Sethi|Ullman|1988|pp=205–206}}

The relations do not have the same properties as their un-dotted counterparts;

e. g. $a\; \backslash doteq\; b$ does not generally imply $b\; \backslash doteq\; a$, and $b\; \backslash gtrdot\; a$ does not follow

from $a\; \backslash lessdot\; b$. Furthermore, $a\; \backslash doteq\; a$ does not generally hold, and $a\; \backslash gtrdot\; a$ is possible.

Let us assume that between the terminals {{mvar|a_i}} and {{math|a_i+1}} there is always exactly one precedence relation. Suppose that $ is the end of the string.

Then for all terminals {{mvar|b}} we define: $\backslash \$\; \backslash lessdot\; b$ and $b\; \backslash gtrdot\; \backslash \$$. If we remove all nonterminals and place the correct precedence relation:

$\backslash lessdot$, $\backslash doteq$, $\backslash gtrdot$ between the remaining terminals, there remain strings that can be analyzed by an easily developed bottom-up parser.

For example, the following operator precedence relations can

be introduced for simple expressions:{{harvnb|Aho|Sethi|Ullman|1988|p=205}}

:$\backslash 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:{{harvnb|Aho|Sethi|Ullman|1988|p=204}}

• + has lower precedence than * (hence $+\; \backslash lessdot\; *$ and $*\; \backslash gtrdot\; +$).
• Both + and * are left-associative (hence $+\; \backslash gtrdot\; +$ and $*\; \backslash gtrdot\; *$).

The input string

: $\backslash mathrm\{id\}\_1\; +\; \backslash mathrm\{id\}\_2\; *\; \backslash mathrm\{id\}\_3$

after adding end markers and inserting precedence relations becomes

: $\backslash \$\; \backslash lessdot\; \backslash mathrm\{id\}\_1\; \backslash gtrdot\; +\; \backslash lessdot\; \backslash mathrm\{id\}\_2\; \backslash gtrdot\; *\; \backslash lessdot\; \backslash mathrm\{id\}\_3\; \backslash gtrdot\; \backslash \$$

Having precedence relations allows to identify handles as follows:

• scan the string from left until seeing $\backslash gtrdot$
• scan backwards (from right to left) over any $\backslash doteq$ until seeing $\backslash lessdot$
• everything between the two relations $\backslash lessdot$ and $\backslash 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.

The algorithm below is from Aho et al.:{{harvnb|Aho|Sethi|Ullman|1988|p=206}}

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 $\backslash lessdot$ b or a $\backslash doteq$ b then

push b onto the stack

advance ip to the next input symbol

else if a $\backslash gtrdot$ b then

repeat

pop the stack

until the top stack terminal is related by $\backslash lessdot$ to the terminal most recently popped

else error()

end

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.{{harvnb|Aho|Sethi|Ullman|1988|pp=208–209}}

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 $a\; \backslash lessdot\; b$ holds, etc.

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

The below algorithm is from Aho et al.:{{harvnb|Aho|Sethi|Ullman|1988|pp=209–210}}

1. Create symbols {{mvar|f_a}} and {{mvar|g_a}} for each grammar terminal {{mvar|a}} and for the end of string symbol;
2. Partition the created symbols in groups so that {{mvar|f_a}} and {{mvar|g_b}} are in the same group if $a\; \backslash doteq\; b$ (there can be symbols in the same group even if their terminals are not connected by this relation);
3. Create a 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_b}} to the group of {{mvar|f_a}} if {{nobreak|$a\; \backslash lessdot\; b$,}} otherwise if $a\; \backslash gtrdot\; b$ place an edge from the group of {{mvar|f_a}} to that of {{mvar|g_b}};
4. 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_a}} and let {{tmath|g(a)}} be the length of the longest path from the group of {{mvar|g_a}}.

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

:$\backslash 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:

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:

:

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.{{harvnb|Crespi Reghizzi|Mandrioli|2012}}

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

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

{{Reflist}}

• {{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}}

• {{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 }}

• Nikolay Nikolaev: [http://homepages.gold.ac.uk/nikolaev/cis324.htm IS53011A Language Design and Implementation], Course notes for CIS 324, 2010.

{{Parsers}}

{{DEFAULTSORT:Operator-Precedence Grammar}}

Category:Formal languages