As a matter of interest, is there a known worst-case complexity for the precomputation required by Earley's algorithm to handle arbitrary CFGs?
Earley's algorithm handles exactly arbitrary (in particular ambiguous) CFGs without precomputation.
see i.e. Aho,Ullman, "The Theory of Parsing, Translation, and Compiling" Vol.1, 1972
I don't believe that expected-case O(N^3) behaviour counts as "not hard", even if it's not exponential. These things have a way of biting you when you least expect it.
Right, this (worst-case) behaviour may be bad, but that can only be (and partly was already) answered in practice. (A constant factor or constant overhead for precomputations can spoil anything.)
Christian
_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
