Re: Bison back-tracking

[Hans Aberg]

At 11:03 +0100 0-11-24, Akim Demaille wrote:
>> Is Bison deterministic or does sometimes Bison back-track?
...
>It does not backtrack, it is fully deterministic.  Look for Btyacc for
>a back tracking Yacc.  It's funny to see that Corbett worked on it,
>and pretty many files are common with Bison :)

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 { }
%%

will back-track on the sentence "cad" in a top-down parsing (example 4.14
from book by Aho et al).

>> ... back-tracking ...
>This cannot happen.  Nevertheless, if you insert actions between the
>symbols, and you have `error' tokens then something somewhat similar
>can happen.  See the nodes about lexical tie-ins in the documentation.

Thanks for pointing this out. I figure the safe way is to abort if the
error looks serious.

  Hans Aberg