[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Safe user-facing pattern matching.
- From: Martin <eden_martin_fuhrspam@...>
- Date: Sat, 22 Apr 2017 18:34:24 -0700
On 04/22/2017 08:01 AM, Coda Highland wrote:
> 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
Your algorithm matches with pattern ".-%b()$", not ".*%b()". It starts
with end of string and moves to beginning correctly capturing balanced
brackets in linear time.
$ lua
Lua 5.3.3 Copyright (C) 1994-2016 Lua.org, PUC-Rio
-- Added captures to pattern to highlight parts.
> ('(((((((())'):match('(.*)(%b())') -- original case, orig. string
((((((( ()
> ('(((((((())'):match('(.-)(%b())$') -- your case, original string
(((((( (())
> ('(((((((())a'):match('(.*)(%b())') -- original case, new string
((((((( ()
> ('(((((((())a'):match('(.-)(%b())$') -- your case, new string
nil
-- Martin