Operator-precedence Grammar - Precedence Relations

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

Read more about this topic:  Operator-precedence Grammar

Famous quotes containing the words precedence and/or relations:

    It is difficult to separate the tapestry
    From the room or loom which takes precedence over it.
    John Ashbery (b. 1927)

    I only desire sincere relations with the worthiest of my acquaintance, that they may give me an opportunity once in a year to speak the truth.
    Henry David Thoreau (1817–1862)