Regex: add a class for matching character classes

This will be used to match character classes (such as '[0-9a-f]'), but
it will also be used by the regular expression pattern parser to
determine whether a character is special.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: Implement compiler for regular expression patterns

Originally, this developer wanted to (ab)use the PikeVM with a
hand-crafted program and an added "callback" opcode to parse the regular
expressions.

However, this turned out to be completely unnecessary: there are no
ambiguities in regular expression patterns, so there is no need to do
anything else than parse the pattern, one character at a time, into a
nested expression that then knows how to write itself into a program for
the PikeVM.

While at it, we fix the preamble for find(): we implemented it initially
as (?:..*?) instead of (?:.*?) due to the lack of prioritization. But now
we have SPLIT_JMP, so we can do it correctly.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support the dot

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement * and + operators

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: Implement reluctant '?', '*' and '+'

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement find()

Now that we have non-greedy repeats, we can implement the find() (which
essentially prefixes the regular expression pattern with '.*?'.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: add support for character classes

Now we support regular expression patterns a la '[0-9]'.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement non-capturing groups

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement alternatives

Now we support regular expressions like 'A|B|C'.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support lookaheads

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: add a method to reverse the PikeVM program

A program for the PikeVM corresponds to a regular expression pattern. The
program matches the character sequence in left-to-right order. However,
for look-behind expressions, we will want to match the character sequence
backwards.

To this end, it is nice that regular expression patterns can be reversed
in a straight-forward manner. However, it would be nice if we could avoid
multiple parsing passes and simply parse even look-behind expressions as
if they were look-ahead ones, and then simply reverse the program for that
part.

Happily, it is not difficult to reverse the program so it is equivalent to
matching the pattern backwards.

There is one catch, though. Imagine matching the sequence "a" against the
regular expression "(a?)a?". If we match forward, the group will match the
letter "a", when matching backwards, it will match the empty string. So,
while the reverse pattern is equivalent to the forward pattern in terms of
"does the pattern match that sequence", but not its sub-matches. For that
reason, Java simply ignores capturing groups in look-behind patterns (and
for consistency, the same holds for look-ahead patterns).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support look-behind patterns

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement negative look-arounds

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support special character classes

This adds support for character classes such as \d or \W, leaving \p{...}
style character classes as an exercise for later.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Implement Pattern#split(String)

The particular pattern we use to test it is used in ImgLib2, based on
this answer on stackoverflow:

	http://stackoverflow.com/a/279337

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: support intersection/union of character classes

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement ^,$,\b and \B

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: implement counted quantifiers: {<n>,<m>}

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: let toString() in the Compiler reconstruct the regex

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Regex: document the strengths and limitations

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>