pczarn/gearley

Use maximal sentence length to prune the Earley table

pczarn opened this issue · 1 comments

The Earley table can be scanned and reduced by removing items that are too old to be useful. Better do this every now and then for recent Earley sets, and rarely for the entire table or large parts of it.

This should be tuned, so that cache misses are infrequent when the beginning of the table is outside of cache. (Don't scan the Earley table too often, but try to do it while the its scanned parts are in the cache.)

There is a problem related to variable-width tokens. We want to assume that all tokens are 1 position wide. As far as I know, unrestricted variable-width tokens are impossible if we choose to use maximal sentence length.

This is a potential space complexity improvement.

We remove recent useless Earley sets. Much easier.