mdaines / grammophone

A tool for analyzing and transforming context-free grammars.
https://mdaines.github.io/grammophone
MIT License
200 stars 23 forks source link

Include end of input symbol in LR(0) tables #43

Closed mdaines closed 5 months ago

mdaines commented 5 months ago

This addresses #41.

When implementing this originally, I omitted the end of input symbol from LR(0) parse tables. This is possibly because Louden 1997 doesn't include such a column in one of its examples.

However, since grammar classification uses the parsing tables, it wasn't able to detect that this grammar had a reduce/reduce conflict:

S -> E.
E -> E.

Of course, this grammar is cyclic and has no terminal symbols, so if classification doesn't check for reduce-reduce conflicts using a table that omits the end of input symbol, it will think there are no conflicts (since they were dropped when creating the table from the automaton).

LL(1) classification has a similar problem, which I'll address in another PR.