Giuseppe Della Penna, Benedetto Intrigila, Enrico Tronci, Marisa Venturini Zilli:
Synchronized regular expressions
Acta Informatica 39 (2003) 1, 31-70, Springer

http://link.springer-ny.com/link/service/journals/00236/tocs/t3039001.htm. 


Abstract

Text manipulation is one of the most common tasks for everyone
using a computer. The increasing number of textual information in
electronic format that every computer user collects everyday
stresses the need of more powerful tools to interact with texts.
Indeed, much work has been done to provide non--programming tools
that can be useful for the most common text manipulation issues.
Regular Expressions (RE), introduced by Kleene, are well--known in
the formal language theory. RE received several extensions,
depending on the application of interest. In almost all the
implementations of RE search algorithms 
(e.g. the \texttt{egrep} UNIX command, or the Perl language pattern
matching constructs) we find \emph{backreferences}, 
i.e. expressions that make reference to the string
matched by a previous subexpression. 

Generally speaking, it seems
that all the kinds of synchronizations between subexpressions in a
RE can be very useful when interacting with texts. Therefore, we
introduce the Synchronized Regular Expressions (SRE) as an
extension of the Regular Expressions. We use SRE to present a
formal study of the already known backreferences extension,
and of a new extension proposed by us, which we
call the \emph{synchronized exponents}. Moreover, since we are
talking about formalisms that should have a practical utility and
can be used in real applications, we have the problem of how to
present SRE to the \emph{final users}. Therefore, in this paper we
also propose a user--friendly syntax for SRE to be used in
implementations of SRE--powered search algorithms.