For many years, regular expressions with back referencing have been used in a variety of software products in common use, including operating systems, editors, and programming languages. In these products, regular expressions have been extended with a naming construct. If a subexpression is named by some variable, whenever this subexpression matches some string, that string is assigned to the variable. Later occurrences of the same variable will then match the string assigned to it. This construction greatly increases the power of regular expressions and is useful in text searching as well as in text substitution in large documents. We study the nested usage of this operator, and prove that the power of the expressions increase with the number of nested levels that are allowed.
|Tidsskrift||Information Processing Letters|
|Status||Udgivet - 1998|