home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / DGREP.DOC < prev    next >
Encoding:
Text File  |  1990-03-16  |  5.0 KB  |  134 lines
  1.  
  2.         DGREP
  3.         -----
  4.  
  5. Dgrep is a fast Unix egrep clone. Basically, it matches a regular
  6. expression to the lines from one or several input files and displays
  7. those lines that contain the regular expression. Dgrep understands the
  8. UNIX extended regular expressions (see usage in dgrep.c or dgrep -h).
  9. If no files are given, standard input is assumed. Although dgrep is
  10. egrep clone, there are some differences, e.g. currently not all option
  11. characters are same (but most of them are). Also few options are added,
  12. some of which are from the GNU grep (see usage in dgrep.c or dgrep -h
  13. for options).
  14.  
  15. Return values:
  16. -------------
  17.  
  18. 0, if matches are found
  19. 1, if no matches are found
  20. 2, if syntax error or inaccessible files
  21. 3, if internal error
  22.  
  23. Portability:
  24. -----------
  25.  
  26. Originally written for MS-DOS under Turbo C, but has been ported to MSC
  27. 5.[01], OS/2 and BSD UNIX 4.3 with gcc compiler. This program should be
  28. relatively easy to port to any environment with ANSI C compiler.
  29.  
  30. Authors:
  31. -------
  32.  
  33. J.Ruuth wrote most of the code
  34. P.Soini wrote boyer-moore initialization and some other things
  35.  
  36. Algorithms:
  37. ----------
  38.  
  39. Dgrep uses two algorithms to search expressions. Literal strings are
  40. searched with the Boyer-Moore-algorithm and regular expressions are
  41. searched with the deterministic finite state automata. To speed up the
  42. searches literal strings from the regular expression are also searched
  43. with the Boyer-Moore-algorithm. Dgrep uses a lazy evaluation technique
  44. for the deterministic finite state automata, so the state transitions
  45. are calculated only when they are actually needed.
  46.  
  47. Algorithm to create DFA directly from the regular expression is
  48. described in the reference [1]. This implementation uses quite directly
  49. ideas and algorithms from that book. Also lazy evalution tecnique is
  50. mentioned there but no algorithm is given. So lazy evalution is based
  51. on my own ideas, which certainly  need improvements. The fast version
  52. is modeled after the ideas from the reference [4].
  53.  
  54. Boyer-Moore-algorithm is from the James A. Wood's fastgrep
  55. implementation. It seems to be quite direct port from the original
  56. speedups suggested by Boyer and Moore in their original paper [7]. The
  57. initialization code is written by P.Soini, and it should guarantee that
  58. the execution time is linear even in the worst case.
  59.  
  60. References:
  61. ----------
  62.  
  63. [1] A.V.Aho, R.Sethi, J.D.Ullman: 'Compilers, Principles, Tecniques and 
  64.     Tools', Addison-Wesley 1986
  65. [2] A.V.Aho, M.J.Corasick: 'Fast pattern matching: An aid to bibliographic
  66.     search', Comm. ACM, June 1975
  67. [3] GNU grep, version 0.999b, June 1988
  68. [4] A.Hume: 'A Tale of Two Greps', Software - Practise and Experience,
  69.     November 1988
  70. [5] J.A.Woods: fastgrep implementation and discussion in the net, 1986
  71.  
  72. Boyer-Moore-algorithm:
  73.  
  74. [6] A.Apostolico and R.Giancarlo: 'The Boyer-Boore-Galil string searching
  75.     strategies revisited', SIAM J. Computing, February 1986
  76. [7] R.S.Boyer and J.S.Moore: 'A Fast string searching algorithm', Comm. ACM,
  77.     October 1977
  78. [8] R.N.Horspool: 'Practical fast searching in strings', Software - Practise
  79.     and Experience, June 1980
  80. [9] D.E.Knuth, J.H.Morris and V.R.Pratt: 'Fast pattern matching in strings',
  81.     SIAM J. Computing, June 1977
  82.  
  83. Version history:
  84. ---------------
  85.  
  86. Changed to use new deterministic regular expression algorithm.
  87.     J.Ruuth 15-Mar-1988    (v.1.10)
  88.  
  89. More options.
  90.     J.Ruuth 25-Mar-1988    (v.1.11)
  91.  
  92. Changed to dynamically use maximum I/O buffer size that does not cause
  93. pointer wraparound with boyer-moore algorithm. It is meaningful only
  94. under 80(1?8[68]|286)|V[234]0 processors and 80[34]86 under 16-bit OS
  95. (OS/2|MS-DOS). Implemented for Turbo C and MSC 5.1 and Quick C 1.01.
  96. For 32-bit environments you can adjust I/O buffer size by simply
  97. changing the constant MAXBUF in file system.h and recompiling.
  98.     P.Soini 03-Apr-1988    (v.1.20)
  99.  
  100. O(n+m)-time regular expression searcher (old was O(nm)-time) and  some
  101. changes from GNU grep.
  102.     J.Ruuth 21-Nov-1988    (v.1.30)
  103.  
  104. Guaranteed worst case performance reduced to O(m+n)-time after 
  105. modifications to the boyer-moore algorithm supplied by Petri Soini.
  106.     J.Ruuth 06-Dec-1988    (v.1.40)
  107.  
  108. Added touch-option.
  109.     J.Ruuth 17-Jan-1989    (v.1.44)
  110.  
  111. Added options to print leading and trailing context of the match. I
  112. tought it was quite a unique idea, but GNU grep already does it,  so
  113. option craracters are borrowed from it.
  114.     J.Ruuth 17-Mar-1989    (v.1.50)
  115.  
  116. Fixed a bug in read_exp().
  117.     J.Ruuth 08-Jun-1989
  118.  
  119. Fixed a bug when buffer didn't end with an end of line character, and
  120. changed interface slightly to the reg_comp.
  121.     J.Ruuth 17-Aug-1989    (v.1.60)
  122.  
  123. Changed usege to display different things at different situations.
  124.     J.Ruuth 12-Sep-1989    (v.1.61)
  125.  
  126. Fixes for BSD's tolower() and toupper() odd behaviour.
  127.     J.Ruuth 21-Oct-1989    (v.1.62)
  128.  
  129. Added possibility to make faster reg_exec using more memory.
  130.     J.Ruuth 14-Jan-1990 (v.1.70)
  131.  
  132. Added input buffer alignment to physical disk blocks.
  133.     J.Ruuth 16-Mar-1990 (v.1.71)
  134.