[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Safe user-facing pattern matching.
- From: Roberto Ierusalimschy <roberto@...>
- Date: Fri, 31 Mar 2017 11:58:18 -0300
> Many regular expression implementations have added features that can't be
> implemented by a finite state automaton, and they end up requiring
> backtracking. Lua's "%bxy" feature is one of them, as are 'back references'
> in the search string: ^(.*)-\1$ (two equal strings separated by a hyphen)
Small correction: "%bxy" certainly cannot be implemented by a finite
state automaton, but it does not require backtracking. It is
easy to do an efficient (linear) implementation of "%bxy" and integrate
it with a finite state automaton. ('back references' as in Perl, on the
other hand, are NP complete.)