Re: Safe user-facing pattern matching.

[Gé Weijers <ge@...>]

On Sun, Apr 23, 2017 at 9:06 AM, Martin <eden_martin_fuhrspam@gmx.de> wrote:

>> Yes, AFAIK it's impossible to match ".*%b()" in linear time. That
>> message was regarding FSA to match "%b()".

So I was wrong. It's possible to match ".*%b()" in linear time.
It is almost equivalent of matching "()". Thank you for showing it!

You can match this particular _expression_ in linear time going from right to left, because the language of the reverse string ("^%b().*$") is a LR(1) language. 

Here's another problem:

  "^a*(%bab)(%bbc)c*$"

This won't match if the number of b's is larger than the sum of the numbers of a's and c's. And "%bab" matches "a-+abb", for instance, whereas "a*" won't match any letters except 'a'.

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?

Gé

--

--

Gé