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
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:
RelationMeaning
yields precedence to
has the same precedence as
takes precedence over

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. does not generally imply, and does not follow
from. Furthermore, does not generally hold, and is possible.
Let us assume that between the terminals and there is
always exactly one precedence relation. Suppose that $ is the end of the string.
Then for all terminals we define: and. 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:
They follow from the following facts:
The input string
after adding end markers and inserting precedence relations becomes

Operator Precedence Parsing

Having precedence relations allows to identify handles as follows:
It is generally not necessary to scan the entire sentential form to find the handle.

Operator Precedence Parsing AlgorithmAho, Sethi & Ullman 1988, p. 206.

Initialize: Set ip to point to the first symbol of w$
Repeat:
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 b or a b then
push b onto the stack
advance ip to the next input symbol
else if a b then
repeat
pop the stack
until the top stack terminal is related by 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.
They map terminal symbols to integers, and so the precedence relations
between the symbols are implemented by numerical comparison:
must hold if 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 FunctionsAho, Sethi & Ullman 1988, pp. 209-210.

  1. Create symbols and for each grammar terminal and for the end of string symbol;
  2. Partition the created symbols in groups so that and are in the same group if ;
  3. Create a directed graph whose nodes are the groups. For each pair of terminals do: place an edge from the group of to the group of if otherwise if place an edge from the group of to that of ;
  4. If the constructed graph has a cycle then no precedence functions exist. When there are no cycles, let be the length of the longest path from the group of and let be the length of the longest path from the group of.

    Example

Consider the following table :
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.