SPARK / Earley Parser question

Stefan Franke 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
language grammars. 

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
any disadvantages.

Online references would be appreciated.

Stefan




More information about the Python-list mailing list