Re: Safe user-facing pattern matching.

[Coda Highland <chighland@...>]

On Sat, Apr 22, 2017 at 1:40 PM, 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()".
>
> This is due dreaded left recursion: in ('(((((((())'):match('.*%b()')
> for any unprocessed char we don't know whether it belongs to "%b()" or
> to ".*" part.

Nope, you can match it in linear time with a stack and a counter:

1. Push every character onto a stack until you hit the end of the string.
2. If the stack is empty, end.
3. Pop a character.
4. If the character was not '(' or ')', end.
4. If the character was ')', increment the counter by 1.
5. If the character was '(', decrement the counter by 1.
6. If the counter is negative, end.
7. Go to 2.

/s/ Adam