lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mon, Apr 24, 2017 at 2:07 PM, Gé Weijers <> wrote:
> On Mon, Apr 24, 2017 at 1:18 PM, Coda Highland <> 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