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 (among others)[1] 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.

## Contents

* 1 Precedence relations
* 1.1 Example
* 2 Operator precedence parsing
* 3 Operator precedence parsing algorithm
* 4 Precedence functions
* 4.1 Algorithm for constructing precedence functions
* 4.2 Example
* 5 Operator-precedence languages
* 6 Notes
* 7 References
* 8 Further reading
* 9 External links

## Precedence relations

Operator precedence grammars rely on the following three precedence relations between the terminals:[2]

Relation  | Meaning

|

[math]\displaystyle{ a \lessdot b }[/math] | a yields precedence to b
[math]\displaystyle{ a \doteq b }[/math] | a has the same precedence as b
[math]\displaystyle{ a \gtrdot b }[/math] | a takes precedence over b

These operator precedence relations allow to delimit the handles in the right sentential forms: [math]\displaystyle{ \lessdot }[/math] marks the left end, [math]\displaystyle{ \doteq }[/math] appears in the interior of the handle, and [math]\displaystyle{ \gtrdot }[/math] marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.[3] The relations do not have the same properties as their un-dotted counterparts; e. g. [math]\displaystyle{ a \doteq b }[/math] does not generally imply [math]\displaystyle{ b \doteq a }[/math], and [math]\displaystyle{ b \gtrdot a }[/math] does not follow from [math]\displaystyle{ a \lessdot b }[/math]. Furthermore, [math]\displaystyle{ a \doteq a }[/math] does not generally hold, and [math]\displaystyle{ a \gtrdot a }[/math] is possible.

Let us assume that between the terminals ai and ai+1 there is always exactly one precedence relation. Suppose that $ is the end of the string. Then for all terminals b we define: [math]\displaystyle{ \$ \lessdot b }[/math] and [math]\displaystyle{ b \gtrdot \$ }[/math]. If we remove all nonterminals and place the correct precedence relation: [math]\displaystyle{ \lessdot }[/math], [math]\displaystyle{ \doteq }[/math], [math]\displaystyle{ \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:[4]

[math]\displaystyle{ \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:[5]

* \+ has lower precedence than * (hence [math]\displaystyle{ + \lessdot * }[/math] and [math]\displaystyle{ * \gtrdot + }[/math]).
* Both + and * are left-associative (hence [math]\displaystyle{ + \gtrdot + }[/math] and [math]\displaystyle{ * \gtrdot * }[/math]).

The input string[4]

[math]\displaystyle{ \mathrm{id}_1 + \mathrm{id}_2 * \mathrm{id}_3 }[/math]

after adding end markers and inserting precedence relations becomes

[math]\displaystyle{ \$ \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:[4]

* scan the string from left until seeing [math]\displaystyle{ \gtrdot }[/math]
* scan backwards (from right to left) over any [math]\displaystyle{ \doteq }[/math] until seeing [math]\displaystyle{ \lessdot }[/math]
* everything between the two relations [math]\displaystyle{ \lessdot }[/math] and [math]\displaystyle{ \gtrdot }[/math], 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.:[6]

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]\displaystyle{ \lessdot }[/math] b or a [math]\displaystyle{ \doteq }[/math] b then
push b onto the stack
advance ip to the next input symbol
else if a [math]\displaystyle{ \gtrdot }[/math] b then
repeat
pop the stack
until the top stack terminal is related by [math]\displaystyle{ \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.[7] They map terminal symbols to integers, and so the precedence relations between the symbols are implemented by numerical comparison: [math]\displaystyle{ f(a) \lt g(b) }[/math] must hold if [math]\displaystyle{ 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.[8]

### Algorithm for constructing precedence functions

The below algorithm is from Aho et al.:[9]

1. Create symbols fa and ga for each grammar terminal a and for the end of string symbol;
2. Partition the created symbols in groups so that fa and gb are in the same group if [math]\displaystyle{ a \doteq b }[/math] (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 [math]\displaystyle{ (a,b) }[/math] of terminals do: place an edge from the group of gb to the group of fa if [math]\displaystyle{ a \lessdot b }[/math], otherwise if [math]\displaystyle{ a \gtrdot b }[/math] place an edge from the group of fa to that of gb;
4. If the constructed graph has a cycle then no precedence functions exist. When there are no cycles, let [math]\displaystyle{ f(a) }[/math] be the length of the longest path from the group of fa and let [math]\displaystyle{ g(a) }[/math] be the length of the longest path from the group of ga.

### Example

Consider the following table (repeated from above):[10]

[math]\displaystyle{ \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+
|  |
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

## 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.[11]

Operator-precedence languages enjoy many closure properties: union, intersection, complementation,[12] concatenation,[11] 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,[13] that enables efficient parallel parsing.

There are also characterizations based on an equivalent form of automata and monadic second-order logic.[14]

## Notes

1. ↑ Aho, Sethi & Ullman 1988, p. 203
2. ↑ Aho, Sethi & Ullman 1988, pp. 203–204
3. ↑ Aho, Sethi & Ullman 1988, pp. 205–206
4. ↑ 4.0 4.1 4.2 Aho, Sethi & Ullman 1988, p. 205
5. ↑ Aho, Sethi & Ullman 1988, p. 204
6. ↑ Aho, Sethi & Ullman 1988, p. 206
7. ↑ Aho, Sethi & Ullman 1988, pp. 208–209
8. ↑ Aho, Sethi & Ullman 1988, p. 209
9. ↑ Aho, Sethi & Ullman 1988, pp. 209–210
10. ↑ Aho, Sethi & Ullman 1988, p. 210
11. ↑ 11.0 11.1 Crespi Reghizzi & Mandrioli 2012
12. ↑ Crespi Reghizzi, Mandrioli & Martin 1978
13. ↑ Barenghi et al. 2015
14. ↑ Lonati et al. 2015

## References

* Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley.
* Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property". Journal of Computer and System Sciences 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006.
* Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). "Algebraic Properties of Operator Precedence Languages". Information and Control 37 (2): 115–133. doi:10.1016/S0019-9958(78)90474-6.
* Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Parallel parsing made practical". Science of Computer Programming 112 (3): 245–249. doi:10.1016/j.scico.2015.09.002.
* Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization". SIAM Journal on Computing 44 (4): 1026–1088. doi:10.1137/140978818.

## Further reading

* Floyd, R. W. (July 1963). "Syntactic Analysis and Operator Precedence". Journal of the ACM 10 (3): 316–333. doi:10.1145/321172.321179.

## External links

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

* v
* t
* e

Parsing algorithms

Top-down|

* LL
* Recursive descent
* Tail recursive
* Pratt parser

Bottom-up|

* Precedence
* Simple
* Operator
* Shunting-yard
* Bounded-context
* LR
* Simple
* Look-ahead
* Canonical
* Generalized
* CYK
* Recursive ascent
* Shift-reduce

Mixed, other|

* Combinator
* Chart
* Earley

Related topics|

* PEG
* Definite clause grammar
* Dynamic programming
* Memoization
* Parser generator
* LALR
* Metacompiler
* Parse tree
* AST
* Scannerless parsing
* History of compiler construction
* Comparison of parser generators

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Operator-precedence grammar. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Operator-precedence_grammar&oldid=3381184"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template