Regex power

Here is a fantastic article about regular expressions, not as they are defined mathematically, but as implemented in real languages - with backreferences, regexes become NP-complete... Which blows my mind.  I had no idea!

They're still unreadable, of course.  Which means it might be worthwhile (1) to work through (or write) a really good tutorial set and (2) write some kind of ... regex preprocessing parser thing.  Which probably already exists, of course.

Anyway, that article led me to the existence of Thue, a string-rewriting language that looks ... weird, to say the least. Note that Thue is definitively described on a Wiki devoted to esoteric programming languages.