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:

    Let not England forget her precedence of teaching nations how to live.
    John Milton (1608–1674)

    As death, when we come to consider it closely, is the true goal of our existence, I have formed during the last few years such close relations with this best and truest friend of mankind, that his image is not only no longer terrifying to me, but is indeed very soothing and consoling! And I thank my God for graciously granting me the opportunity ... of learning that death is the key which unlocks the door to our true happiness.
    Wolfgang Amadeus Mozart (1756–1791)