[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Safe user-facing pattern matching.
- From: Gé Weijers <ge@...>
- Date: Fri, 31 Mar 2017 07:23:05 -0700
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)
This problem could be solved by using a regex implementation that limits itself to 'true' regular expressions that can be implemented by an FSA.
A very full featured one is:
Downside: it's written in C++, it should still be fairly easy to add a simple interface wrapper to Lua.