home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / textprocess / grep_2 / release / Resources / ReadMe < prev    next >
Text File  |  1989-03-11  |  8KB  |  151 lines
  1. This README documents GNU e?grep version 1.3.
  2.  
  3. Changes needed to the makefile under various perversions of Unix are
  4. described therein.
  5.  
  6. If the type "char" is unsigned on your machine, you will have to fix
  7. the definition of the macro SIGN_EXTEND_CHAR() in regex.c.  A reasonable
  8. definition might be:
  9.         #define SIGN_EXTEND_CHAR(c) ((c)>(char)127?(c)-256:(c))
  10.  
  11. GNU e?grep is provided "as is" with no warranty.  The exact terms
  12. under which you may use and (re)distribute this program are detailed
  13. in a comment at the top of grep.c.
  14.  
  15. GNU e?grep is based on a fast lazy-state deterministic matcher (about
  16. twice as fast as stock Unix egrep) hybridized with a Boyer-Moore-Gosper
  17. search for a fixed string that eliminates impossible text from being
  18. considered by the full regexp matcher without necessarily having to
  19. look at every character.  The result is typically many times faster
  20. than Unix grep or egrep.  (Regular expressions containing backreferencing
  21. may run more slowly, however.)
  22.  
  23. GNU e?grep attempts, as closely as possible, to understand compatibly
  24. the regexp syntaxes of the Unix programs it replaces.  The following table
  25. details the various special characters understood in both the grep and
  26. egrep incarnations:
  27.  
  28. (grep)  (egrep)         (explanation)
  29.   .        .            matches any single character except newline
  30.   \?       ?            postfix operator; preceeding item is optional
  31.   *        *            postfix operator; preceeding item 0 or more times
  32.   \+       +            postfix operator; preceeding item 1 or more times
  33.   \|       |            infix operator; matches either argument
  34.   ^        ^            matches the empty string at the beginning of a line
  35.   $        $            matches the empty string at the end of a line
  36.   \<       \<           matches the empty string at the beginning of a word
  37.   \>       \>           matches the empty string at the end of a word
  38.  [chars] [chars]        match any character in the given class; if the
  39.                         first character after [ is ^, match any character
  40.                         not in the given class; a range of characters may
  41.                         be specified by <first>-<last>; for example, \W
  42.                         (below) is equivalent to the class [^A-Za-z0-9]
  43.  \( \)    ( )           parentheses are used to override operator precedence
  44.  \<1-9>   \<1-9>        \<n> matches a repeat of the text matched earlier
  45.                         in the regexp by the subexpression inside the
  46.                         nth opening parenthesis
  47.   \        \            any special character may be preceded by a backslash
  48.                         to match it literally
  49.  
  50. (the following are for compatibility with GNU Emacs)
  51.   \b       \b           matches the empty string at the edge of a word
  52.   \B       \B           matches the empty string if not at the edge of a word
  53.   \w       \w           matches word-constituent characters (letters & digits)
  54.   \W       \W           matches characters that are not word-constituent
  55.  
  56. Operator precedence is (highest to lowest) ?, *, and +, concatenation,
  57. and finally |.  All other constructs are syntactically identical to
  58. normal characters.  For the truly interested, a comment in dfa.c describes
  59. the exact grammar understood by the parser.
  60.  
  61. GNU e?grep understands the following command line options:
  62.         -A <num>        print <num> lines of context after every matching line
  63.         -B <num>        print <num> lines of context before every matching line
  64.         -C              print 2 lines of context on each side of every match
  65.         -<num>          print <num> lines of context on each side
  66.         -V              print the version number on stderr
  67.         -b              print every match preceded by its byte offset
  68.         -c              print a total count of matching lines only
  69.         -e <expr>       search for <expr>; useful if <expr> begins with -
  70.         -f <file>       take <expr> from the given <file>
  71.         -h              don't display filenames on matches
  72.         -i              ignore case difference when comparing strings
  73.         -l              list files containing matches only
  74.         -n              print each match preceded by its line number
  75.         -s              run silently producing no output except error messages
  76.         -v              print only lines that contain no matches for the <expr>
  77.         -w              print only lines where the match is a complete word
  78.         -x              print only lines where the match is a whole line
  79.  
  80. The options understood by GNU e?grep are meant to be (nearly) compatible
  81. with both the BSD and System V versions of grep and egrep.
  82.  
  83. The following incompatibilities with other versions of grep exist:
  84.         the context-dependent meaning of * is not quite the same (grep only)
  85.         -b prints a byte offset instead of a block offset
  86.         the \{m,n\} construct of System V grep is not implemented
  87.  
  88. GNU e?grep has been thoroughly debugged and tested by several people
  89. over a period of several months; we think it's a reliable beast or we
  90. wouldn't distribute it.  If by some fluke of the universe you discover
  91. a bug, send a detailed description (including options, regular
  92. expressions, and a copy of an input file that can reproduce it) to me,
  93. mike@wheaties.ai.mit.edu.
  94.  
  95. GNU e?grep is brought to you by the efforts of several people:
  96.  
  97.         Mike Haertel wrote the deterministic regexp code and the bulk
  98.         of the program.
  99.  
  100.         James A. Woods is responsible for the hybridized search strategy
  101.         of using Boyer-Moore-Gosper fixed-string search as a filter
  102.         before calling the general regexp matcher.
  103.  
  104.         Arthur David Olson contributed code that finds fixed strings for
  105.         the aforementioned BMG search for a large class of regexps.
  106.  
  107.         Richard Stallman wrote the backtracking regexp matcher that is
  108.         used for \<digit> backreferences, as well as the getopt that
  109.         is provided for 4.2BSD sites.  The backtracking matcher was
  110.         originally written for GNU Emacs.
  111.  
  112.         D. A. Gwyn wrote the C alloca emulation that is provided so
  113.         System V machines can run this program.  (Alloca is used only
  114.         by RMS' backtracking matcher, and then only rarely, so there
  115.         is no loss if your machine doesn't have a "real" alloca.)
  116.  
  117.         Scott Anderson and Henry Spencer designed the regression tests
  118.         used in the "regress" script.
  119.  
  120.         Paul Placeway wrote the manual page, based on this README.
  121.  
  122. If you are interested in improving this program, you may wish to try
  123. any of the following:
  124.  
  125. 1.  Make backreferencing \<digit> faster.  Right now, backreferencing is
  126.     handled by calling the Emacs backtracking matcher to verify the partial
  127.     match.  This is slow; if the DFA routines could handle backreferencing
  128.     themselves a speedup on the order of three to four times might occur
  129.     in those cases where the backtracking matcher is called to verify nearly
  130.     every line.  Also, some portability problems due to the inclusion of the
  131.     emacs matcher would be solved because it could then be eliminated.
  132.     Note that expressions with backreferencing are not true regular
  133.     expressions, and thus are not equivalent to any DFA.  So this is hard.
  134.  
  135. 2.  There is a bug in the backtracking matcher, regex.c, such that the |
  136.     operator is not properly commutative.  Let x and y be arbitrary
  137.     regular expressions, and suppose both x and y have matches at
  138.     some point in the target text.  Then the regexp x|y should select
  139.     the longest of the two matches.  With the backtracking matcher, if the
  140.     first match succeeds it does not even try the second, even though
  141.     the second may be a longer match.  This is obviously of no concern
  142.     for grep, which does not care exactly where or how long a match is,
  143.     so long as it knows it is there.  On the other hand, the backtracking
  144.     matcher is used in GNU AWK, wherein its behavior can only be considered
  145.     a bug.
  146.  
  147. 3.  Handle POSIX style regexps.  I'm not sure if this could be called an
  148.     improvement; some of the things on regexps in the POSIX draft I have
  149.     seen are pretty sickening.  But it would be useful in the interests of
  150.     conforming to the standard.
  151.