LR(0) fails to display an R/R conflict?

mdaines / grammophone

A tool for analyzing and transforming context-free grammars.

https://mdaines.github.io/grammophone

MIT License

200 stars 23 forks source link

LR(0) fails to display an R/R conflict? #41

Closed modulovalue closed 5 months ago

modulovalue commented 5 months ago

Consider the following grammar:

S -> E.
E -> E.

On grammophone

It looks like there's a bug with this grammar:

Since SLR(1), LALR(1) and LR(1) are strictly more expressive than LR(0), it looks to me like they should never not recognize a grammar that LR(0) can recognize.

It seems that LR(0) should show an R/R conflict here, but it doesn't:

LALR(1), for example, does show an R/R conflict:

mdaines commented 5 months ago

It looks like the U of C tool gives the expected results then? http://smlweb.cpsc.ucalgary.ca/lr0.php?grammar=S+-%3E+E.%0AE+-%3E+E.&substs=

I don't remember why there isn't any column for end of input in the LR(0) table.

Just to be clear though, this is supposed to be a cyclic grammar?

modulovalue commented 5 months ago

I don't remember why there isn't any column for end of input in the LR(0) table.

Oh, I missed that there's no column for $, that has to be it. Maybe the LR(0) construction is just missing some alphabet.add("$"); invocation?

Just to be clear though, this is supposed to be a cyclic grammar?

All I can say is that I did not intend to test any specific grammar, this discovery was just an accident.

mdaines commented 5 months ago

I've deployed the changes referenced above. Thank you for pointing this out!