-\1f
-File: bison.info, Node: Shift/Reduce, Next: Precedence, Prev: Look-Ahead, Up: Algorithm
-
-Shift/Reduce Conflicts
-======================
-
- Suppose we are parsing a language which has if-then and if-then-else
-statements, with a pair of rules like this:
-
- if_stmt:
- IF expr THEN stmt
- | IF expr THEN stmt ELSE stmt
- ;
-
-Here we assume that `IF', `THEN' and `ELSE' are terminal symbols for
-specific keyword tokens.
-
- When the `ELSE' token is read and becomes the look-ahead token, the
-contents of the stack (assuming the input is valid) are just right for
-reduction by the first rule. But it is also legitimate to shift the
-`ELSE', because that would lead to eventual reduction by the second
-rule.
-
- This situation, where either a shift or a reduction would be valid,
-is called a "shift/reduce conflict". Bison is designed to resolve
-these conflicts by choosing to shift, unless otherwise directed by
-operator precedence declarations. To see the reason for this, let's
-contrast it with the other alternative.
-
- Since the parser prefers to shift the `ELSE', the result is to attach
-the else-clause to the innermost if-statement, making these two inputs
-equivalent:
-
- if x then if y then win (); else lose;
-
- if x then do; if y then win (); else lose; end;
-
- But if the parser chose to reduce when possible rather than shift,
-the result would be to attach the else-clause to the outermost
-if-statement, making these two inputs equivalent:
-
- if x then if y then win (); else lose;
-
- if x then do; if y then win (); end; else lose;
-
- The conflict exists because the grammar as written is ambiguous:
-either parsing of the simple nested if-statement is legitimate. The
-established convention is that these ambiguities are resolved by
-attaching the else-clause to the innermost if-statement; this is what
-Bison accomplishes by choosing to shift rather than reduce. (It would
-ideally be cleaner to write an unambiguous grammar, but that is very
-hard to do in this case.) This particular ambiguity was first
-encountered in the specifications of Algol 60 and is called the
-"dangling `else'" ambiguity.
-
- To avoid warnings from Bison about predictable, legitimate
-shift/reduce conflicts, use the `%expect N' declaration. There will be
-no warning as long as the number of shift/reduce conflicts is exactly N.
-*Note Suppressing Conflict Warnings: Expect Decl.
-
- The definition of `if_stmt' above is solely to blame for the
-conflict, but the conflict does not actually appear without additional
-rules. Here is a complete Bison input file that actually manifests the
-conflict:
-
- %token IF THEN ELSE variable
- %%
- stmt: expr
- | if_stmt
- ;
-
- if_stmt:
- IF expr THEN stmt
- | IF expr THEN stmt ELSE stmt
- ;
-
- expr: variable
- ;
-
-\1f
-File: bison.info, Node: Precedence, Next: Contextual Precedence, Prev: Shift/Reduce, Up: Algorithm
-
-Operator Precedence
-===================
-
- Another situation where shift/reduce conflicts appear is in
-arithmetic expressions. Here shifting is not always the preferred
-resolution; the Bison declarations for operator precedence allow you to
-specify when to shift and when to reduce.
-
-* Menu:
-
-* Why Precedence:: An example showing why precedence is needed.
-* Using Precedence:: How to specify precedence in Bison grammars.
-* Precedence Examples:: How these features are used in the previous example.
-* How Precedence:: How they work.
-
-\1f
-File: bison.info, Node: Why Precedence, Next: Using Precedence, Up: Precedence
-
-When Precedence is Needed
--------------------------
-
- Consider the following ambiguous grammar fragment (ambiguous because
-the input `1 - 2 * 3' can be parsed in two different ways):
-
- expr: expr '-' expr
- | expr '*' expr
- | expr '<' expr
- | '(' expr ')'
- ...
- ;
-
-Suppose the parser has seen the tokens `1', `-' and `2'; should it
-reduce them via the rule for the subtraction operator? It depends on
-the next token. Of course, if the next token is `)', we must reduce;
-shifting is invalid because no single rule can reduce the token
-sequence `- 2 )' or anything starting with that. But if the next token
-is `*' or `<', we have a choice: either shifting or reduction would
-allow the parse to complete, but with different results.
-
- To decide which one Bison should do, we must consider the results.
-If the next operator token OP is shifted, then it must be reduced first
-in order to permit another opportunity to reduce the difference. The
-result is (in effect) `1 - (2 OP 3)'. On the other hand, if the
-subtraction is reduced before shifting OP, the result is
-`(1 - 2) OP 3'. Clearly, then, the choice of shift or reduce should
-depend on the relative precedence of the operators `-' and OP: `*'
-should be shifted first, but not `<'.
-
- What about input such as `1 - 2 - 5'; should this be `(1 - 2) - 5'
-or should it be `1 - (2 - 5)'? For most operators we prefer the
-former, which is called "left association". The latter alternative,
-"right association", is desirable for assignment operators. The choice
-of left or right association is a matter of whether the parser chooses
-to shift or reduce when the stack contains `1 - 2' and the look-ahead
-token is `-': shifting makes right-associativity.
-
projects / bison.git / blobdiff