| 1 |
Syntax: bf(%prec) tt(token) |
| 2 |
|
| 3 |
The construction bf(%prec) tt(token) may be used in non-empty production |
| 4 |
rules to overrule the actual precedence of an operator in those |
| 5 |
production rules. Well known is the construction |
| 6 |
verb( |
| 7 |
expression: |
| 8 |
'-' expression %prec UMINUS |
| 9 |
{ |
| 10 |
... |
| 11 |
} |
| 12 |
) |
| 13 |
Here, the default precedence and precedence of the tt(`-') token as the |
| 14 |
subtraction operator is overruled by the precedence and precedence of the |
| 15 |
tt(UMINUS) token, which is frequently defined as: |
| 16 |
verb( |
| 17 |
%right UMINUS |
| 18 |
) |
| 19 |
E.g., a list of arithmetic operators could consists of: |
| 20 |
verb( |
| 21 |
%left '+' '-' |
| 22 |
%left '*' '/' '%' |
| 23 |
%right UMINUS |
| 24 |
) |
| 25 |
giving tt(* /) and tt(%) a higher precedence than tt(+) and tt(-), |
| 26 |
ensuring at the same time that tt(UMINUS) is given both the highest precedence |
| 27 |
and a right-associativity. |
| 28 |
|
| 29 |
In the above production rule the operator order would result in the |
| 30 |
construction |
| 31 |
verb( |
| 32 |
'-' expression |
| 33 |
) |
| 34 |
being evaluated from right to left, having a higher precedence than either |
| 35 |
the multiplication or the addition operators. |
| 36 |
|
| 37 |
The tt(%prec) directive associates priorities to (non-empty) rules. These |
| 38 |
priorities are interpreted whenever there are (shift-reduce) conflicts. If |
| 39 |
there are no conflicts, priorities are not required, and are consequently |
| 40 |
ignored. |
| 41 |
|
| 42 |
When the parser analyzes the above grammar, a conflict em(is) |
| 43 |
encountered. Consider the following simple grammar, in which only the minus |
| 44 |
(tt('-')) operator is used, albeit in beinary and unary form: |
| 45 |
|
| 46 |
verb( |
| 47 |
%token NR |
| 48 |
%left '-' |
| 49 |
%right UNARY |
| 50 |
|
| 51 |
expr: |
| 52 |
NR |
| 53 |
| |
| 54 |
expr '-' expr |
| 55 |
| |
| 56 |
'-' expr %prec UNARY |
| 57 |
; |
| 58 |
) |
| 59 |
When analuzing this grammar, bic() defines em(states) (cf. chapter |
| 60 |
ref(ALGORITHM)) defining what to do when encountering certain input |
| 61 |
tokens. Each possibility is defined by an em(item), in which a dot (tt(.)) is |
| 62 |
commonly used to show to which point a production rule has been |
| 63 |
recognized. For the above grammar one such state looks like this: |
| 64 |
verb( |
| 65 |
0: expr -> '-' expr . { '-' <EOF> } |
| 66 |
1: expr -> expr . '-' expr |
| 67 |
) |
| 68 |
The elements between parentheses define the em(look-ahead) tokens: the |
| 69 |
token that may appear next for em(reducible) rules. Item 0 is such a reducible |
| 70 |
rule, and it is used to reduce tt('-' expr) to an expression (tt(expr)). |
| 71 |
|
| 72 |
The second item shows the production rule defining the binary minus |
| 73 |
operator. Its left-hand side expression has been recognized, and the parser |
| 74 |
expects to see a minus operator next. |
| 75 |
|
| 76 |
The conflict is caused by the expected minus operator in item 1, and a |
| 77 |
minus operator that may follow item 0. As there is only one look-ahead symbol |
| 78 |
(since bic() can only handle LALR(1) grammars) the grammer contains a |
| 79 |
shift-reduce conflict: shift, and continue with item 1; or reduce, and |
| 80 |
continue with item 0. In this case, tt(%prec) solves the issue, by giving item |
| 81 |
0 a higher precedence than item 1 (whose precedence is equal to the precedence |
| 82 |
of its first terminal token, which is the binary minus operator's |
| 83 |
precedence). |
| 84 |
|
| 85 |
Although never encountered in real life, it's also possible to give the |
| 86 |
unary minus operator a em(lower) priority than the binary minus operator. The |
| 87 |
grammar, in this case, looks like this: |
| 88 |
verb( |
| 89 |
%token NR |
| 90 |
%right UNARY |
| 91 |
%left '-' |
| 92 |
|
| 93 |
expr: |
| 94 |
NR |
| 95 |
| |
| 96 |
expr '-' expr |
| 97 |
| |
| 98 |
'-' expr %prec UNARY |
| 99 |
; |
| 100 |
) |
| 101 |
|
| 102 |
With this grammar we encounter a state with these two items: |
| 103 |
verb( |
| 104 |
0: expr -> '-' expr . { <EOF> } |
| 105 |
1: expr -> expr . '-' expr |
| 106 |
) |
| 107 |
Here, the conflict no longer manifests itself, as the minus operator no |
| 108 |
longer appears in item 0's look-ahead set. The resulting parser will, when |
| 109 |
encountering a minus, shift the minus, and proceed according to item 1, and |
| 110 |
when anything else is encountered reduce the tt('-' expr) production to |
| 111 |
tt(expr). In real life this means that an expression like tt(-4 - 3) |
| 112 |
evaluates to -1. |
| 113 |
|
| 114 |
To illustrate a situation where tt(%prec) won't work consider this |
| 115 |
grammar: |
| 116 |
verb( |
| 117 |
%token NR |
| 118 |
%left '-' |
| 119 |
%right POSTFIX |
| 120 |
|
| 121 |
expr: |
| 122 |
NR |
| 123 |
| |
| 124 |
expr '-' expr |
| 125 |
| |
| 126 |
expr '-' %prec POSTFIX |
| 127 |
; |
| 128 |
) |
| 129 |
When this grammar is analyzed the following state is encountered: |
| 130 |
verb( |
| 131 |
0: expr -> expr '-' . expr |
| 132 |
1: expr -> expr '-' . { '-' <EOF> } |
| 133 |
2: expr -> . NR |
| 134 |
3: expr -> . expr '-' expr |
| 135 |
4: expr -> . expr '-' |
| 136 |
) |
| 137 |
To appreciate why tt(%prec) doesn't work here, consider the various |
| 138 |
look-ahead tokens. For items 0, 3, and 4 the look-ahead token is the |
| 139 |
non-terminal tt(expr); for item 2 the look-ahead token is the terminal tt(NR), |
| 140 |
and for item 1, handling the postfix minus operator, it is a minus |
| 141 |
character. Thus, there isn't any conflict between the shiftable items and the |
| 142 |
reducible item 1, and consequently the tt(%prec) specification isn't |
| 143 |
used. Any attempt to define a grammar handling a postfix minus operator will |
| 144 |
fail. A common solution consists of defining a separate operator, explicitly |
| 145 |
giving it its appropriate priority and associativity. E.g., |
| 146 |
verb( |
| 147 |
%token NR |
| 148 |
%left '-' |
| 149 |
%right '_' // underscore |
| 150 |
|
| 151 |
expr: |
| 152 |
NR |
| 153 |
| |
| 154 |
expr '-' expr |
| 155 |
| |
| 156 |
expr '_' // underscore as postfix minus |
| 157 |
; |
| 158 |
) |
| 159 |
|