Re: Safe user-facing pattern matching.

[Martin <eden_martin_fuhrspam@...>]

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