Re: Safe user-facing pattern matching.

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

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.

--

--

Gé