Re: Bison back-tracking

[Hans Aberg]

At 20:02 +0100 0-11-24, Hans Aberg wrote:
>Akim Demaille wrote:
>>I agree it might be necessary, but after all Bison is here for LALR(1)
>>period.
...
>Hans Aberg wrote:
>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.

The book by Robin Hunter, "Compilers", 5.2, says that any LR(k) _language_,
k > 1, is also a LR(1) language, and even a LR(0) language if each sentence
is followed by an end marker.

However, there are for example LR(2) grammars which are not LR(1), say
%token a, t
%%
S:  F ',' S
  | F

F:  a L

L:  t
  | t ',' L
which in Bison produces the error
  contains 1 shift/reduce conflict.

The above grammar can be transformed into a LR(1):
S: a t F

F:  { /* empty */ }
  | ',' I F

I:  a t
  | t
(Or so loc.cit. says.)

So Bison is just LR(1) or LALR(1) then, with no grammar transformation
capabilities. -- Loc.cit. suggests to first try say the simpler LALR(1)
algorithm, and in the cases it fails, to use the LR(1) algorithm; but it
does not cite an example of a LR(1) grammar which isn't LALR(1), so I
cannot check if Bison does that, or is simply LALR(1).

  Hans Aberg
                  * Email: Hans Aberg <mailto:address@hidden>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>