Debian Codegraph @

documentation/manual/algorithm/ruleprec.yo

raw
1 Consider the following (somewhat peculiar) grammar:
2 verbinclude(demos/peculiar)
3
4 Even though operator precedence and association rules are used the grammar
5 still displays a shift/reduce conflict. One of the grammar's states consists
6 of the following two items:
7 verb(
8 0: expr -> term .
9 1: term -> term . '*' factor
10 )
11 and b() reduces to item 0, dropping item 1 rather than shifting a tt('*') and
12 proceeding with item 0.
13
14 When considering states where shift/reduce conflicts are encountered the
15 `shiftable' items of these states shift when encountering terminal tokens that
16 are also in the follow sets of the reducible items of these states. In the
17 above example item 1 shifts when tt('*') is encountered, but tt('*') is also
18 an element of the set of look-ahead tokens of item 0. B() must now decide what
19 to do. In cases we've seen earlier b() could make the decision because the
20 reducible item itself had a well known precedence. The precedence of a
21 reducible item is defined as the precedence of the rule's LHS. Item
22 0 in the above example is an item of the rule tt(expr -> term).
23
24 The precedence of a production rule is defined as follows:
25 itemization(
26 it() If tt(%prec) is used then the precedence of the production rule is
27 equal to the precedence of the terminal that is specified with the tt(%prec)
28 directive;
29 it() If tt(%prec) is not used then the production rule's precedence is
30 equal to the precedence of the first terminal token that is used in the
31 production rule;
32 it() In all other cases the production rule's precedence is set to the
33 maximum possible precedence.
34 )
35
36 Since tt(expr -> term) does not contain a terminal token and does not use
37 tt(%prec), its precedence is the maximum possible precedence. Consequently in
38 the above state the shift/reduce conflict is solved by em(reducing) rather
39 than shifting.
40
41 Some final remark as to why the above grammar is peculiar. It is peculiar as
42 it combines precedence and association specifying directives with auxiliary
43 nonterminals that may be useful conceptually (or when implementing an
44 expression parser `by hand') but which are not required when defining grammars
45 for b(). The following grammar does not use tt(term) and tt(factor) but
46 recognizes the same grammar as the above `peculiar' grammar without reporting
47 any shift/reduce conflict:
48 verbinclude(demos/notpeculiar)
49