[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Odd parser behaviour

From: Hans Aberg
Subject: Re: Odd parser behaviour
Date: Mon, 25 Sep 2006 11:02:34 +0200

On 25 Sep 2006, at 10:45, Heiko Wundram wrote:

[I now see Hans Aberg's reply - so ok, it's an artifact of LALR(1), I
can live with that - and I hereby second any motion to introduce that
 LR(1) option]

It's not only an artifact of LALR(1). AFAIK, bison table generation uses $default rules which might create additional (though in the context invalid) reductions, to compress the parsing table, because then reductions don't have to be stored for every input token explicitly. So, the behaviour you're seeing is only partially due to LALR(1), but also to the table compression algorithm employed by bison. An LALR(1) parser would not reduce on state 1 either, because there's no way that you can see lookahead A or F in any form
of combined LR(1) states (which state 1 is).

I am not sure what additional compressions that Bison uses besides LALR(1), but the phenomenon is due to these compressions, where one deliberately merges states, accepting certain additional extra reductions. The technique is described in the ("Dragon") book by Aho et al., "Compilers...".

  Hans Aberg

reply via email to

[Prev in Thread] Current Thread [Next in Thread]