Where do regexes with backreferences belong in the chomsky hierarchy (do they belong there at all)?

Question

I'm somewhat confused here - RegExes with back references are apparently not regular expressions, because they they can, for instance, be used to describe the copy language ('ww' for any word w), which is context-sensitive. Yet at the same time, they still can't be used to describe context free languages like HTML (or even just matching parentheses) - at least I wouldn't know how such a thing would look like in e.g. POSIX regular expressions.

That being said - do "regular expressions" of this kind belong anywhere in the Chomsky hierarchy, or are they some frankenstein-abomination between the lines?

Answer 1

They don't really fit.

Regexes with backreferences can match some non-context-free languages (for example (.*)\1) but also can't match all context-free languages (the typical example being nested parentheses).

Here is a relevant post on the CSTheory StackExchange, which has a few more details.

Note also that some implementations (e.g. .NET or Perl) go further than backreferences and can match nested parentheses.