Project idea - python

[Neel Krishnaswami]

Bob Schmertz <schmertz at wam.umd.edu> wrote:
> 
> SPARK - sounds like a Python implementation of Yacc/Bison, though from
> what I can tell it doesn't handle complex grammars such as LR
> (http://www.csr.UVic.CA/~aycock/python/)
 
SPARK uses the Earley parsing algorithm, which can parse *any* context
free grammar, even if the grammar is ambiguous or otherwise wonky.

IIRC, Earley parsers have the neat property of being "adaptive" --
their performance is O(n) on LL/LR grammars, rising up to O(n**3) for
pathologically ambiguous grammars. This generality doesn't come for
free, though -- the extra overhead in data structures tends to reduce
their speed by roughly a factor of 10 versus the usual algorithms for
simple grammars.

But for this modest price you can specify the grammar that most
naturally generates your language, rather than going through weird
contortions needed to satisfy Yacc. :)


Neel