An operator precedence grammar is a kind of grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 for formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

s.

Technically, an operator precedence grammar is a context-free grammar

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

 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

Relation (mathematics)

In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

 to be
defined between the terminals of the grammar. A parser that exploits these relations

Operator-precedence parser

An operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation with order of operations format into an internally optimized computer-readable format...

 is considerably simpler than more general-purpose parsers such as LALR parser

LALR parser

In computer science, an LALR parser is a type of LR parser based on a finite-state-automata concept. The data structure used by an LALR parser is a pushdown automaton...

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:

Relation	Meaning
a <• b	a yields precedence to b
a =• b	a has the same precedence as b
a •> b	a takes precedence over b

These operator precedence relations allow to delimit the handles

Bottom-up parsing

Bottom-up parsing is a strategy for analyzing unknown information that attempts to identify the most fundamental units first, and then to infer higher-order structures from them...

in the right sentential forms

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

: <• 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:

	id	+	*	$
id		•>	•>	•>
+	<•	•>	<•	•>
*	<•	•>	•>	•>
$	<•	<•	<•

They follow from the following facts:

• + has lower precedence than * (hence + <• * and * •> +).
• Both + and * are left-associative (hence + •> + and * •> *).

The input string

id₁ + id₂ * id₃

after adding end markers and inserting precedence relations becomes

$ <• id₁ •> + <• id₂ •> * <• id₃ •> $

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

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 to find the handle.

Operator Precedence Parsing Algorithm

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:
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

1. Create symbols f_a and g_a for each grammar terminal a and for the end of string symbol;
2. 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);
3. Create a directed graph
   Graph (mathematics)
   In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
   
   whose nodes are the groups, next 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;
4. 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):

	id	+	*	$
id		•>	•>	•>
+	<•	•>	<•	•>
*	<•	•>	•>	•>
$	<•	<•	<•

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:

	id	+	*	$
f	4	2	4	0
g	5	1	3	0

External links

• Nikolay Nikolaev: IS53011A Language Design and Implementation, Course notes for CIS 324, 2010.