This README documents GNU e?grep version 1.5. All bugs reported for
previous versions have been fixed. I would like to emphasize: Please
send bug reports directly to me ([email protected]), *not* bug-gnu-utils.

Changes needed to the makefile under various perversions of Unix are
described therein.

If the type "char" is unsigned on your machine, you will have to fix
the definition of the macro SIGN_EXTEND_CHAR() in regex.c. A reasonable
definition might be:
#define SIGN_EXTEND_CHAR(c) ((c)>(char)127?(c)-256:(c))

GNU e?grep is provided "as is" with no warranty. The exact terms
under which you may use and (re)distribute this program are detailed
in a comment at the top of grep.c.

GNU e?grep is based on a fast lazy-state deterministic matcher (about
twice as fast as stock Unix egrep) hybridized with a Boyer-Moore-Gosper
search for a fixed string that eliminates impossible text from being
considered by the full regexp matcher without necessarily having to
look at every character. The result is typically many times faster
than Unix grep or egrep. (Regular expressions containing backreferencing
may run more slowly, however.)

GNU e?grep attempts, as closely as possible, to understand compatibly
the regexp syntaxes of the Unix programs it replaces. The following table
details the various special characters understood in both the grep and
egrep incarnations:

(grep)(egrep)(explanation)
. .matches any single character except newline
\? ?postfix operator; preceeding item is optional
* *postfix operator; preceeding item 0 or more times
\+ +postfix operator; preceeding item 1 or more times
\| |infix operator; matches either argument
^ ^matches the empty string at the beginning of a line
$ $matches the empty string at the end of a line
\< \ \> \>matches the empty string at the end of a word
[chars] [chars]match any character in the given class; if the
first character after [ is ^, match any character
not in the given class; a range of characters may
be specified by -; for example, \W
(below) is equivalent to the class [^A-Za-z0-9]
\( \) ( )parentheses are used to override operator precedence
\<1-9> \<1-9>\ matches a repeat of the text matched earlier
in the regexp by the subexpression inside the
nth opening parenthesis
\ \any special character may be preceded by a backslash
to match it literally

(the following are for compatibility with GNU Emacs)
\b \bmatches the empty string at the edge of a word
\B \Bmatches the empty string if not at the edge of a word
\w \wmatches word-constituent characters (letters & digits)
\W \Wmatches characters that are not word-constituent

Operator precedence is (highest to lowest) ?, *, and +, concatenation,
and finally |. All other constructs are syntactically identical to
normal characters. For the truly interested, a comment in dfa.c describes
the exact grammar understood by the parser.

GNU e?grep understands the following command line options:
-A print lines of context after every matching line
-B print lines of context before every matching line
-Cprint 2 lines of context on each side of every match
-print lines of context on each side
-Vprint the version number on stderr
-bprint every match preceded by its byte offset
-cprint a total count of matching lines only
-e search for ; useful if begins with -
-f take from the given
-hdon't display filenames on matches
-iignore case difference when comparing strings
-llist files containing matches only
-nprint each match preceded by its line number
-srun silently producing no output except error messages
-vprint only lines that contain no matches for the
-wprint only lines where the match is a complete word
-xprint only lines where the match is a whole line

The options understood by GNU e?grep are meant to be (nearly) compatible
with both the BSD and System V versions of grep and egrep.

The following incompatibilities with other versions of grep exist:
the context-dependent meaning of * is not quite the same (grep only)
-b prints a byte offset instead of a block offset
the \{m,n\} construct of System V grep is not implemented

GNU e?grep has been thoroughly debugged and tested by several people
over a period of several months; we think it's a reliable beast or we
wouldn't distribute it. If by some fluke of the universe you discover
a bug, send a detailed description (including options, regular
expressions, and a copy of an input file that can reproduce it) to me,
[email protected].

GNU e?grep is brought to you by the efforts of several people:

Mike Haertel wrote the deterministic regexp code and the bulk
of the program.

James A. Woods is responsible for the hybridized search strategy
of using Boyer-Moore-Gosper fixed-string search as a filter
before calling the general regexp matcher.

Arthur David Olson contributed code that finds fixed strings for
the aforementioned BMG search for a large class of regexps.

Richard Stallman wrote the backtracking regexp matcher that is
used for \ backreferences, as well as the getopt that
is provided for 4.2BSD sites. The backtracking matcher was
originally written for GNU Emacs.

D. A. Gwyn wrote the C alloca emulation that is provided so
System V machines can run this program. (Alloca is used only
by RMS' backtracking matcher, and then only rarely, so there
is no loss if your machine doesn't have a "real" alloca.)

Scott Anderson and Henry Spencer designed the regression tests
used in the "regress" script.

Paul Placeway wrote the manual page, based on this README.

If you are interested in improving this program, you may wish to try
any of the following:

1. Make backreferencing \ faster. Right now, backreferencing is
handled by calling the Emacs backtracking matcher to verify the partial
match. This is slow; if the DFA routines could handle backreferencing
themselves a speedup on the order of three to four times might occur
in those cases where the backtracking matcher is called to verify nearly
every line. Also, some portability problems due to the inclusion of the
emacs matcher would be solved because it could then be eliminated.
Note that expressions with backreferencing are not true regular
expressions, and thus are not equivalent to any DFA. So this is hard.

2. There is a bug in the backtracking matcher, regex.c, such that the |
operator is not properly commutative. Let x and y be arbitrary
regular expressions, and suppose both x and y have matches at
some point in the target text. Then the regexp x|y should select
the longest of the two matches. With the backtracking matcher, if the
first match succeeds it does not even try the second, even though
the second may be a longer match. This is obviously of no concern
for grep, which does not care exactly where or how long a match is,
so long as it knows it is there. On the other hand, the backtracking
matcher is used in GNU AWK, wherein its behavior can only be considered
a bug.

3. Handle POSIX style regexps. I'm not sure if this could be called an
improvement; some of the things on regexps in the POSIX draft I have
seen are pretty sickening. But it would be useful in the interests of
conforming to the standard.