User-Defined Operators (ad-hoc overloading)

[Christian Maeder]

Andrew J Bromage wrote:
> 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