-
Notifications
You must be signed in to change notification settings - Fork 0
/
abstract.tex
21 lines (19 loc) · 1010 Bytes
/
abstract.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Regular expressions are part of every programmer's toolbox. They are
used for a wide variety of language-related tasks and there are many algorithms for
manipulating them. In particular, matching algorithms that detect
whether a word belongs to the language described by a regular
expression are well explored,
yet new algorithms appear frequently. However, there is
no satisfactory methodology for testing such matchers.
We propose a testing methodology which is based on generating positive
as well as negative examples of words in the language. To this end, we
present a new algorithm to generate the language described by a
generalized regular expression with intersection and complement
operators. The complement operator allows us to generate both
positive and negative example words from a given regular expression.
We implement our generator in Haskell and OCaml and show that its
performance is more than adequate for testing.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: