Possible off-by-one in genLR0items startRules

[marco-comini]

Hi,

I think there may be an off-by-one bug in genLR0items.

The initial LR(0) kernels are seeded with:

startRules = [ Set.singleton (Lr0 rule 0) | rule <- [0..n_starts] ]

where n_starts = length (starts g).

This creates n_starts + 1 initial kernels.

However, elsewhere start rules seem to be treated as only the first n_starts rules, e.g. with logic like:

isStartRule rule = rule < n_starts

So the two conventions do not appear consistent.

In practice, with multiple %name directives, I observe one extra initial seeded state corresponding to the first ordinary grammar production after the synthetic start rules. This introduces states unrelated to any declared entry point.

It looks like the seed range in genLR0items should perhaps be:

[0 .. n_starts - 1]

instead of:

[0 .. n_starts]

I can provide a minimal reproducer if needed.

[sgraf812]

Thanks. Yes, an MWE would be much appreciated. Also if you know the cure, do you feel like you could contribute a patch?

[marco-comini]

Here is a minimal reproducible example.

File Bug.y:

%name parseS S
%tokentype { Token }
%token
  a       { A }
  w       { W }
  useless { U }

%%

UseLess : useless UseLess  { () }
        | useless          { () }

S : a w  { () }

{
data Token = A | W | U
}

Run:

happy -i Bug.y

In the generated Bug.info, I would expect only the 4 states needed for %name parseS S (namely 0, 3, 4, 5) not 8 states.

Instead, Happy generates an extra initial seeded component coming from the first ordinary grammar rule (UseLess), even though UseLess is unrelated to S and unreachable from the declared entry point.

In the head it also reports

rule 1 is unused
rule 2 is unused

while states 1,2,6,7 use them.

In general the LR(0) collection seems to include:

• one initial state for %start_XXX for each %name XXX
• one extra initial state for the first ordinary grammar production

This looks consistent with genLR0items seeding

[0 .. n_starts]

instead of

[0 .. n_starts - 1]

Could you confirm whether this is intended, or whether it is an off-by-one bug in the initial LR(0) seeds?

Regarding the last request, I would certainly be happy to contribute a patch. I just need to learn how this should be done. I will read the documentation and do it soon.