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) 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. Operator precedence grammars rely on the following three precedence relations between the terminals: 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 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: 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. For example, the following operator precedence relations can be introduced for simple expressions: They follow from the following facts: has lower precedence than * (hence and ). Both + and * are left-associative (hence and ). The input string after adding end markers and inserting precedence relations becomes 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 to find the handle.