Debian Codegraph @

documentation/manual/directives/prec.yo

raw
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