Selection preference for rules

A selection preference can be added to a grammar rule to help resolve conflicts. The following input shows a simple example of how a selection preference can resolve conflicts between two rules:

a1 : a b ['+' '-']
     { /* Action 1 */ } ;
a2 : a b
     { /* Action 2 */ } ;

The selection preference is indicated by zero or more tokens inside brackets. If the token that follows the b is one of the tokens inside the brackets, the parser uses the grammar rule for a1. If it is not one of the given tokens, the parser uses the rule for a2. In this way, the conflict between the two rules is resolved; the preference tells which one to select, depending on the value of the lookahead token.

Note: A selection preference states that a rule is to be used when the next token is one of the ones that are listed in the brackets and is not to be used if it is not in the brackets.

The lookahead token is merely used to determine which rule to select. It is not part of the rule itself. For example, suppose you have:

a1 : a b ['+' '-'] ;
a2 : a b ;
xx : a1 op expr ;

and suppose you have an a, a b, and + as the lookahead token. The + indicates that the a and b is to be reduced to a1. The parser does this and finds that the a1 is part of the xx rule. The + lookahead token is associated with the op symbol in the xx rule. In other words, a selection preference does not use up an input token; it just looks at the token value to help resolve a conflict.

The brackets of a selection preference can contain no tokens, as in:

x : y z [␠];

This says that the parser will never use this rule unless it cannot be avoided.

Selection preferences can also be stated by using the construct:

[‸ T1 T2 T3 …]

where the first character is a caret (∧) and T1, T2, and so on are tokens. When this is put on the end of a rule, it indicates that the rule is to be used if the lookahead token is not one of the listed tokens. For example:

a1 : a b
   { /* Action 1 */ } ;
a2 : a b [‸ '+' '-']
   { /* Action 2 */ } ;

says that rule a2 is to be used if the token after the b is not a + or -. If the token is + or -, a2 is not to be used (so a1 is).

Selection preference constructs can be put in the middle of rules as well as on the end. For example, you can write:

expr : expr ['+' '-'] op expr
       { /* Action 1 */ }
     │ expr op expr
       { /* Action 2 */ } ;

This states that if the first expr is followed by a + or - you want to use the first rule; otherwise, you want to use the second. The preference does not use up the + or - token; you still need a symbol (op) to represent such tokens.

Selection preferences that appear in the middle of a rule are implemented in the same way as multiple actions, using dummy rules. The previous example results in something like the following:

$23 : ['+' '-'] ;
expr : expr $23 op expr
       { /* Action 1 */ }
     │ expr op expr
       { /* Action 2 */ } ;

(where the 23 in $23 is just a number chosen at random). The dummy rule that is created is a null string with the selection preference on the end. The first token for op is the + or - that was the lookahead token in rule $23.

If a selection preference in the middle of a rule is immediately followed by an action, only one dummy rule is created to handle both the action and the preference.

In most cases, a selection preference counts as a $N symbol, but it has no associated value. For example, in:

expr : expr ['+' '-'] op expr

there is:

$1 — first expr
$2 — no value
$3 — op
$4 — second expr

If the preference is followed by an action, the preference and the action count as a single $N symbol, the value of which is equal to the $$ value of the action. For example, in:

expr : expr ['+' '-'] {action} op expr

there is:

$1 — first expr
$2 — $$ of action
$3 — op
$4 — second expr

The %prec construct is incompatible with rules that contain selection preferences, because the preference is all that is needed to resolve conflicts. For this reason, yacc issues an error message if a rule contains both a preference and the %prec construct.

Selection preferences can be used to resolve most conflicts. Indeed, there might be cases where the most practical course of action is to write a number of conflicting rules that contain selection preferences to resolve the conflicts, as in:

expr : expr ['+' '-'] op expr
     │ expr ['*' '/' '%'] op expr
     │ expr ['&'; '|'] op expr
              ...

Note: Selection preferences of the form:

[error]
[‸ error]

are not useful. Selection preferences are implemented through (dummy) Reduce actions, but the parser's error-handling routines always look for Shift actions and ignore reductions.