Prevent duplicate states from being added to tables

[aredridel]

Prevent duplicate states from being added to tables

[kach]

Ah, thanks for taking a look. Speed is definitely an issue we need to work on. Perhaps we need a Java-esque State.prototype.equals(another_state)?

Should I put up my Lua parser as a significantly nontrivial test case for you to play with? It may help catch obscure bugs/generate large tests; or it may just cause more headaches.

[aredridel]

Oh heck yes. I know @silentbicycle is also working on a Lua Earley parser, so at the least, he'd love that!

[aredridel]

I don't have a good gut feeling on whether an equals(other) method is the best way to go, or to try to exploit object identity. How this ties in to building DFA states in #11 is perhaps relevant, too, or perhaps makes it unneeded, since the operation there is state = nextStateFor(character), and the state has the table pre-built in it.

Also I just noticed that my grammar is now very post-midnight and I need to sleep, apparently!

[kach]

https://gist.github.com/11024526

[aredridel]

I just realized that the duplicate states are the different (ambiguous) derivations in my grammar.

[rwindelz]

when COMPLETE adds the additional duplicate states to the current chart, it allows the closure to complete the full set of states in the chart. in order to remove the duplicate states, the closure calculation will have to change. i've seen other Earley parsers use a naive closure calc - 'process the full chart until it is not possible to add any more states' - that gets expensive.