Re: CYK & Context-Free Expressions

Rock Brentwood <markwh04@xxxxxxxxx> writes:

In particular, it is not
O(n^2) (nor is anything like this a "standard proof" in the first
place to be "contradicted" by anyone).

I'm not sure what you are referring to by "it", recognition or
parsing. However, since I believe we have always been discussing
parsing (and not recognition), and that was what I meant by the n**2
bound. I was actually trying to cite the n**3 bounds known for Earley
parsing, but substituted quadratic for cubic. What I was trying to
question was your assertion that parsing could be done in linear time
(for anything more than the deterministic context free languages).
That is the result that seems counter-intuitive to me, and the reason
I want to understand what your papers mean (not the only reason(*), but a
significant one), so that I can discover if you have an insight that
would be very significant to me.

Once, we have parsing problems that are non-linear (although perhaps
n*log(n) would be acceptable), that class of grammars is generally
impractical. So, if you have a way of making a larger set of parsing
problems linear, it is an interesting result.

The question is have you done that? And, if so, have you done it in a
way that still preserves properties that are relevant to me?

Until I can understand your work, I don't know...

Hope this helps,
-Chris

******************************************************************************
Chris Clark Internet: christopher.f.clark@xxxxxxxxxxxxxxxxxxxxxx
Compiler Resources, Inc. or: compres@xxxxxxxxxxxxx
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

*) I would also be interested in your papers even if you don't prove
any surprising results, because you attack the problem in a way I
have not seen it attacked otherwise, and just doing so probably
provides insights (or makes certain things more obvious).
.

Relevant Pages

  • Low risk vulnerabilities in ftp file list handling
    ... Several ftp parsing libraries are vulnerable to attack by simply feeding ... This attack is not actually that useful fortunately. ...
    (Bugtraq)
  • Re: Earley parser bugs?
    ... can further explain why Earley's parsing extension to his recognizer ... Any examples or references to papers would be appreciated. ... Parsing From Earley Recognisers_, to appear in ENTCS. ... incorrect Earley parsing given there is the ...
    (comp.compilers)