Introduction:

Resolving ambiguity by deleting conflicting actions can also be done in SLR-tables. In general, there are more cases where this can be done successfully for SLR-parsers than for LL(1)-parsers. In particular, ambiguity in expression grammars can be eliminated this way in an SLR table, but not in an LL(1) table. Most LR-parser generators allow declarations of precedence and associativity for tokens used as infix-operators. These declarations are then used to eliminate conflicts in the parse tables.

There are several advantages to this approach:

• Ambiguous expression grammars are more compact and easier to read than unambiguous grammars.
• The parse tables constructed from ambiguous grammars are often smaller than tables produced from equivalent unambiguous grammars.
• Parsing using ambiguous grammars is (slightly) faster, as fewer reductions of the form Exp2-> Exp3 etc. are required.

Using precedence rules to eliminate conflicts is very simple:

A conflict between shifting on and reducing by the production

Exp!Exp Exp.

A conflict between shifting on and reducing by the production

Exp!Exp*Exp.

A conflict between shifting on * and reducing by the production

Exp!Exp Exp.

A conflict between shifting on * and reducing by the production

Exp!Exp*Exp.

And several more of similar nature involving - and /, for a total of 16 conflicts. Let us take each of the four conflicts above in turn and see how precedence rules can be used to eliminate them. We use the rules that and * are both left-associative and that * binds more strongly than .

1. This conflict arises from expressions like a b c. After having read a b, the next input symbol is a . We can now either choose to reduce a b, grouping around the first addition before the second, or shift on the plus, which will later lead to b c being reduced and hence grouping around the second addition before the first. Since the rules give that is left-associative, we prefer the first of these options and, hence, eliminate the shift-action from the table and keep the reduce-action.

2. The offending expressions here have the form a*b c. Since the rules make multiplication bind stronger than addition, we, again, prefer reduction over shifting.

3.  In expressions of the form a b*c, the rules, again, make multiplication bind stronger, so we do a shift to avoid grouping around the operator and, hence, eliminate the reduce-action from the table.

4.  This case is identical to case 1, where an operator that by the rules is left associative conflicts with itself. We, like in case 1, handle this by eliminating the shift.

In general, elimination of conflicts by operator precedence declarations can be summarized into the following rules:

a) If the conflict is between two operators of different priority, eliminate the action with the lowest priority operator in favour of the action with the highest priority. The operator associated with a reduce-action is the operator used in the production that is reduced.

b) If the conflict is between operators of the same priority, the associativity (which must be the same, as noted in section 3.4.1) of the operators is used: If the operators are left-associative, the shift-action is eliminated and the reduce-action retained. If the operators are right-associative, the reduce action is eliminated and the shift-action retained. If the operators are non associative, both actions are eliminated.

c)  If there are several operators with declared precedence in the production that is used in a reduce-action, the last of these is used to determine the precedence of the reduce-action.

Prefix and postfix operators can be handled similarly. Associativity only applies to infix operators, so only the precedence of prefix and postfix operators matters. Note that only shift-reduce conflicts are eliminated by the above rules. Some parser generators allow also reduce-reduce conflicts to be eliminated by precedence rules (in which case the production with the highest-precedence operator is preferred), but this is not as obviously useful as the above.

Previous Next