Re: Safe user-facing pattern matching.

[Coda Highland <chighland@...>]

On Fri, Apr 28, 2017 at 11:44 PM, Martin <eden_martin_fuhrspam@gmx.de> wrote:
>> So of course there's an ad-hoc linear time algorithm to match this, but
>> the point is: can we come up with a matching algorithm that writes that
>> ad-hoc algorithm automatically, i.e. can we solve the general case?
>
> I think the more common questions besides this are
>
>   * does current regexps language is powerful enough to match all
>     possible strings that can be matched in linear time?
>     (probably not)
>   * does such language exists?
>   * could this language be constructed?
>
> This recalls me Goedel's statement that on any complex enough
> axioms basis may be assertions whose trueness or falseness
> cannot be proved anyhow.
>
> -- Martin

No, yes, and yes, in that order, but you missed a constraint. The
problem is that to encompass ALL possible O(n)-parseable grammars you
have to open up the full scope of Turing completeness, which then
violates our original intent of safely running untrusted patterns
because you can't prove that a given pattern will behave.

On the other hand, the LR grammars provide a comfortably large subset
of interesting languages that can be matched in O(n) time.

/s/ Adam