  A rewb is a regular expression extended with a feature called backreference.
It is broadly known that backreference is a practical extension of regular
expressions, and is supported by most modern regular expression engines, such
as those in the standard libraries of Java, Python, and more. Meanwhile,
indexed languages are the languages generated by indexed grammars, a formal
grammar class proposed by A.V.Aho. We show that these two models' expressive
powers are related in the following way: every language described by a rewb is
an indexed language. As the smallest formal grammar class previously known to
contain rewbs is the class of context sensitive languages, our result strictly
improves the known upper-bound. Moreover, we prove the following two claims:
there exists a rewb whose language does not belong to the class of stack
languages, which is a proper subclass of indexed languages, and the language
described by a rewb without a captured reference is in the class of nonerasing
stack languages, which is a proper subclass of stack languages. Finally, we
show that the hierarchy investigated in a prior study, which separates the
expressive power of rewbs by the notion of nested levels, is within the class
of nonerasing stack languages.

Formal Languages and Automata Theory