SPARK / Earley Parser question
spamfranke at bigfoot.de
Thu Apr 27 01:26:21 CEST 2000
I'm designing a grammar with John Aycock's SPARK toolkit.
Earley's algorithm is said to be n^3 time bound in general, n^2 for
unambiguous grammars and linear for most practical programming
Are there some rules of thumbs which kind of rules should be avoided
to retain linear complexity?
In particular, I wonder if using empty right-hand sides for rules has
Online references would be appreciated.
More information about the Python-list