[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Odd parser behaviour
From: |
Heiko Wundram |
Subject: |
Re: Odd parser behaviour |
Date: |
Mon, 25 Sep 2006 11:17:25 +0200 |
User-agent: |
KMail/1.9.4 |
Am Montag, 25. September 2006 11:02 schrieben Sie:
> 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...".
Before my last mail, I sat down and created the LALR(1) sets by hand. In the
case of the "pure" LALR(1) sets for this grammar, there are no possible
reductions/shifts on lookahead tokens A or F in state 1, because it doesn't
result from a merger of the starting state (which as the only possible state
contains the valid lookahead A, resulting in shift here) with some other
state.
Seeing a reduction on lookahead A comes from the $default reduction, which is
implemented to speed up table lookup (in this case, there's either a shift
which is explicitly listed or reduction on opt_C on all possible lookaheads
which are valid in state 1 [BCDE], so basically bison decides to combine them
to a default reduce in case no shift matches). This introduces other possible
(but invalid) reduction chains which don't come from LALR, but will error out
on the first unmatched shift in any case (when a rule appears which doesn't
have any possible reductions, just shifts, see for example state 12 resulting
automaton, which is the error state for AA), just as LALR would when states
are merged.
So, basically, this form of table compression might introduce erraneous
reduction chains (just as LALR does), but on the other hand allows for faster
lookup. It's also described in the Dragon-Book, AFAIK.
If one of the bison developers is around: correct me if this is utterly and
completely wrong, but as far as I understand bison, this is the way it
works. ;-)
--
--- Heiko Wundram.
____ _ _ ___ _____
/ ___| ___| |__ _ __| | _____ _ __ ___ |_ _|_ _|
| | _ / _ \ '_ \| '__| |/ / _ \ '_ \/ __| | | | |
| |_| | __/ | | | | | < __/ | | \__ \_ | | | |
\____|\___|_| |_|_| |_|\_\___|_| |_|___(_)___| |_|
FON 0511-59027954
FAX 0511-59027957
Gehrkens.IT GmbH
Mailänder Strasse 2
http://www.gehrkens.it
http://www.xencon.net
- Odd parser behaviour, Tim Van Holder, 2006/09/24
- Re: Odd parser behaviour, Heiko Wundram, 2006/09/24
- Re: Odd parser behaviour, Tim Van Holder, 2006/09/25
- Re: Odd parser behaviour, Heiko Wundram, 2006/09/25
- Re: Odd parser behaviour, Hans Aberg, 2006/09/25
- Re: Odd parser behaviour, Tim Van Holder, 2006/09/25
- Re: Odd parser behaviour, Heiko Wundram, 2006/09/25
- Re: Odd parser behaviour, Hans Aberg, 2006/09/25
- Re: Odd parser behaviour,
Heiko Wundram <=
- Re: Odd parser behaviour, Tim Van Holder, 2006/09/25