[Types-sig] MobiusPython

[Jeff Epler]

On Mon, Mar 12, 2001 at 05:59:00PM -0800, Paul Prescod wrote:
> I'm worried about the slowness of the SPARK toolkit. I've seen
> exponential behavior with it before and Eric Raymond just mentioned some
> on python-dev. You really have to know what you are doing to get good
> performance and I don't!

I saw Eric's message.  What a coincidence that it comes at the same time as
mine.

I don't understand the maths behind the time complexities of the "Earley"
parser either (I stop just after 'bubble sort is O(n^2), and that's bad'),
but I'll defer to John Aycock, who says that
	The time complexity of Earley's algorithm is O(n^3) in the
	worst case, that being the meanest, nastiest, most ambiguous
	context-free grammar you could possibly think of.  Unless you're
	parsing natural language, this won't happen.  For any unambiguous
	grammar, the worst case drops to O(n^2), and for a set of grammars
	which loosely coincides with the LR(k) grammars, the complexity
	drops to O(n).
I suspect that the Python grammar is in the last group, and thus has the
desirable O(n) complexity.

In any case, the fact that Mobius is based on SPARK shouldn't make Mobius
unsuitable for this task even if SPARK is slow, if the intention is
*prototyping* the extensions.  Once the syntax is solid, it can be coded
directly into Python-2.x/Grammar/Grammar.

(That said, the performance of my parser is not great, to the extent that
it takes about 1 second/LOC on my 486-75 laptop, where I often develop
Mobius --- so far, speed has not been my goal, passing the parser test
suite is)

Jeff