Re: Bison back-tracking

[Akim Demaille]

| Backtracking is sometimes required with some grammars, even though Bison
| seems to know how to eliminate that: For example, the grammar
| %token a, b, c, d
| %%
| S: c A d { }
| 
| A: a b { } | a { }
| %%

Sorry, I didn't pay attention to your grammar, but there is no magic
in the fact that Bison knows how to parse this.  Bison parsers (just
like any Yacc parser) keep track of where they are in the eligible
rules, and what to do depending upon the current lookahead symbol.

Here, when it's in A right after having read an `a', i.e., when it is
in the state corresponding to

        A : a . b
          | a .

(where the dot represents the possible degree of recognition of a
rule), it knows that if a `b' is the next token, then it shall shift
the `b', otherwise the rule A -> a.

Using --verbose shows this extremely well:

state 2

    A  ->  a . b   (rule 2)
    A  ->  a .   (rule 3)

    b           shift, and go to state 4

    $default    reduce using rule 3 (A)