Its known that regular expressions implemented in a recursive fashion (instead of a NFA/DFA) can need in some cases exponential running time. Lua patterns are implemented via a recursive matcher (they allow backtracking), but they are less powerful than regular expressions (forgetting %b pattern).
Can Lua patterns need an exponential running time? And without backtracking (any occurrence of %0, %1, %2... pattern)? If so, I will appreciate some examples.
Yes, lua patterns can take exponential time. Try running:
string.find('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa',
'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?'
.. 'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa')
They can still run reasonably fast if you keep the patterns simple though so I would try testing some real examples on your own data.