Re: Empty rule spoiling error reporting

[Hans Aberg]

At 03:56 +0400 2004/08/04, hz kto wrote:
>My grammar contains a lot of optional rules like this
>
>opt_something1: /*empty/
>       |<some grammar>
>       |<some grammar>
>       |<some grammar> ...
>
>And then
>
>rule1 : token3 {...}
>       | token2 {...}
>       | opt_something1 token1 {...}
>
>
>When in certain context parser does not see token1,2,3 nor anything
>non-empty from opt_something1, it matches an empty rule and then, when it
>starts searching for tokens that could follow next, it only finds token1
>since it already in the state corresponding to opt_something1.
>
>Is it possible to make a check inside error reporting routine for whether
>the last thing matched was an "empty" rule?
>Then I could just pop one state of the stack and start error reporting as
>normally. (I can't really remove optional rules that match empty strings,
>it would make the grammar many times bigger)

It sounds as though you are hitting a problem with LALR(1) error reporting.
In LR(1), when you are in the state that contains the items
  rule1 -> . token3
  ...
  rule1 -> . opt_something1 token1
and all else coming from . opt_something1, and not a valid token shows up
in the input, it will report an error immediately.

Under LALR(1), which Bison uses, the states have been compacted in a way
that the error may be reported first after some additional rules have been
reduced (and thus, their actions have been exported). This is the downside
with LALR(1), deliberately chosen to save parsing table space.

There is, as far as I know, no way to augment LALR(1) so that it behaves as
LR(1) in this respect. Bison does not currently support LR(1). You can know
that a rule has been exported by setting a flag in its action, but I do not
see how you could exploit that. The states themselves inside the parser are
just numbers, and you cannot extract any state information about them
directly; only limited information about lookaheads and actions can be
extracted from the parsing tables.

So your best shot is probably to explain more carefully why you need this
feature, in case you want to stick with Bison.

  Hans Aberg