Re: Mark W. Hopkins theory perspective on parser engine technology?

On Mar 28, 11:58 am, Chris F Clark <c...@xxxxxxxxxxxxxxxxxxxx> wrote:
For example, if I recall correctly, he claimed at
1 time to have a linear parsing algorithm for a general CFG, which is
well known to be O(n**2).  Since I couldn't get enough response out of
him to understand where the apparent contradiction lay, I gave up.

It might help if you bring up an actual example that tries to
demonstrate your point. It will be an interesting exercise then to see
how this works out. Personally, I think the example involving cyclic
grammars, where the O(n) representation of the output set for a given
input (nonetheless) incorporates an infinite context-free subset over
the output alphabet (i.e. infinite ambiguity), pretty much seals the
deal. But, further examples will be always useful to add to the notes
on that site if clarification is required.
.