Re: Bison back-tracking

[Hans Aberg]

Akim Demaille wrote:
>| Backtracking is sometimes required with some grammars, ...
>I agree it might be necessary, but after all Bison is here for LALR(1)
>period.
>
>In addition recent discussions on the GCC mailing lists seem to reveal
>the performances can be really poor (which was expected...).
>
>        http://gcc.gnu.org/ml/gcc/2000-11/msg00982.html

I saw it.

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

Right, by a suitable lookahead one might avoid backtracking. I think (if I
remember it correctly) though that even though all grammars LR(k), k > 1,
can be transformed into a LR(1) grammar, it is not true that any LR(k), k >
1, grammar is a LR(1) as it stands. -- So there should perhaps be examples
where either backtracking or a grammar transformation is required.

Another situation where backtracking might be required I think is if the
grammar is somehow dynamic -- one does not know what rules that can be
applied until the terminals have been read.

I did some experimentation with such a parser. It is recursive descent, and
each terminal has dynamically allocated syntax information. When the parser
finds a token, it asks it of which contexts to which it applies and then
proceed accordingly.

>| I figure the safe way is to abort if the
>| error looks serious.
>
>That's safe but not very user friendly.  I use many error rules, and
>never faced a similar problem.  But I do not use actions in between
>tokens.

Well, my experience with a C++ compiler I use is that it often gets out of
sync after the first error. Then it may report a hundred errors which
really are a consequence of that it got out of sync in the first place.

So I have some doubts with the traditional view of user friendly compilers
which moves along despite finding errors. The usefulness really depends on
circumstances.

On the other hand, I have found it very useful if the error is pinpointed
very accurately both as to the location and its nature.