[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Bison back-tracking
From: |
Hans Aberg |
Subject: |
Re: Bison back-tracking |
Date: |
Fri, 24 Nov 2000 14:50:22 +0100 |
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