[vezzy-fnord]

Regexes can't do recursive things

Basic regular expressions cannot, but regexes actually can. PCRE pioneered the technique AFAIK, and it later spread to Perl, Python, Ruby and other runtimes. Perl has this feature called lazy regular subexpressions which can be used to evaluate Perl expressions upon matching a subexpression, thus giving you the ability to recurse.

[rspeer]

So, yes, some implementations of regular expressions are Turing complete because they run arbitrary code, but that is rather the opposite of a way to make parsers safer.

On that note, once you can run arbitrary functions on your matches, you could match /.*/ and then the function you run is html5lib.parse. Is that still a regular expression?