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 _______________________________________________ help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
