[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: |
Tue, 9 Jan 2001 13:05:24 +0100 |
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/>
- Re: Bison back-tracking,
Hans Aberg <=