Re: Safe user-facing pattern matching.

[Coda Highland <chighland@...>]

On Mon, Apr 24, 2017 at 2:07 PM, Gé Weijers <ge@weijers.org> wrote:
>
>
> On Mon, Apr 24, 2017 at 1:18 PM, Coda Highland <chighland@gmail.com> wrote:
>>
>> But if you go waaaaaay upthread, the actual point is: How can you
>> constrain the definition of string patterns in a way that's still
>> concise to write, allows you to match interesting things, and operates
>> in guaranteed linear time?
>>
>> Constraining things to JUST pure regular languages satisfies the first
>> and third requirements, but there are obvious things that you would
>> want to handle that you can't.
>
>
> Roberto's claim was that %b patterns could be allowed. I have yet to see how
> to do that in the general case and still end up with linear behavior. It's
> well know how to transform a non-determinstic finite state automaton into a
> deterministic one, but the same transformation does not exist for stack
> machines.
>
> That said, the language generated by %b patterns added to the limited REs
> supported by Lua may well be recognized in linear time, but I don't have the
> foggiest idea how.

I can see how to do it in O(n^2) time, which is better than naive
backtracking. I'd have to spend time on it to see if I could improve
on that.

/s/ Adam