intro.tex

\section{Introduction}

Regular languages are everywhere. Due to their apparent simplicity and
their concise representability in the form of regular expressions,
regular languages are used for many text processing
applications, reaching from text editors
\cite{DBLP:journals/cacm/Thompson68} to extracting data from web
pages.

Consequently, there are many algorithms and libraries that implement
parsing for regular expressions. Some of them are based on Thompson's
translation from regular expressions to nondeterministic finite
automata and then apply the powerset construction to obtain a
deterministic automaton. Others are based on derivatives
\cite{Brzozowski1964} and
map a regular expression directly to a deterministic
automaton. Partial derivatives \cite{Antimirov96Partial}
provide another transformation into a nondeterministic automaton. An
implementation based on Glushkov automata has been proposed
\cite{DBLP:conf/icfp/FischerHW10} with decent performance.
Cox's webpage \cite{cox07:_implem_regul_expres} gives a good overview
of efficient implementations of regular expression search. It includes
a discussion of his implementation of Google's RE2 \cite{cox10:_regul_expres_match_wild}.
Current research still uncovers new efficient algorithms for matching
subclasses of regular expressions \cite{DBLP:journals/jcss/GrozM17}.

Some of the algorithms for regular expression matching are rather
intricate and the natural question arises how to test these
algorithms. Static test suites are somewhat unsatisfactory as they
only cover a finite number of cases when the problem is infinite in
two dimensions (regular expressions and input words). Random testing
seems more appropriate: it can generate random expressions or it can
draw example expressions from online repositories with reams of real
life regular expressions \cite{regul_expres_librar}, but then there
needs to be an oracle for the generated language and it is non-trivial
to define generators for test inputs.

We eliminate the oracle by providing generators for positive and
negative example words. Generators for positive examples, which match
a given regular expression, have been
investigated \cite{DBLP:journals/jcss/GrozM17,
  DBLP:journals/tcs/AckermanS09, DBLP:journals/jfp/McIlroy04,
  DBLP:journals/actaC/Makinen97}, although mainly in a theoretical
context. Generating negative examples, which do \textbf{not} match an
expression, has not been considered before.

The generators presented in this work are yet more general. They
apply to \textbf{extended regular expressions} that contain
intersection and complement beyond the standard regular operators. The presence
of the complement operator enables the algorithms to generate strings
that certainly do not match a given (extended) regular expression.

Our algorithms produce lazy streams, which are guaranteed to be
productive (i.e., their next element is computed in finite time). A
user can limit the string length or the number of generated strings
without risking partiality.

Source code for implementations in Haskell\footnote{
  \url{https://github.com/peterthiemann/re-generate}
}
and in OCaml\footnote{%
  \url{https://github.com/regex-generate/regenerate}} is available
on GitHub. Examples can be run in a Web App\footnote{%
  \url{https://regex-generate.github.io/regenerate/}}.  Although
not tuned for efficiency they generate languages at a rate
between $1.3\cdot10^3$ and $1.4\cdot10^6$ strings per second, for
Haskell, and up to $3.6\cdot10^6$ strings per second, for OCaml. The
generation rate depends on the density of the language.

\S~\ref{sec:motivation}--\ref{sec:improvements} investigate the
overall design using Haskell. Fine tuning of the underlying data
structures is investigated using OCaml in \S~\ref{sec:ocaml}.
\S~\ref{sec:bench} reports benchmarking results, \S~\ref{sec:test}
considers testing, \S~\ref{sec:related-work} discusses related work,
and \S~\ref{sec:conclusions} concludes.

We assume fluency with Haskell and OCaml. 
Familiarity with formal languages is helpful, but not required as the
paper contains all relevant definitions. 

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: