usr/src/cmd/man/src/util/instant.src/tptregexp/README

   1 #
   2 #pragma ident   "%Z%%M% %I%     %E% SMI"
   3 #
   4 #
   5 # Copyright (c) 1994
   6 # Open Software Foundation, Inc.
   7 #
   8 # Permission is hereby granted to use, copy, modify and freely distribute
   9 # the software in this file and its documentation for any purpose without
  10 # fee, provided that the above copyright notice appears in all copies and
  11 # that both the copyright notice and this permission notice appear in
  12 # supporting documentation.  Further, provided that the name of Open
  13 # Software Foundation, Inc. ("OSF") not be used in advertising or
  14 # publicity pertaining to distribution of the software without prior
  15 # written permission from OSF.  OSF makes no representations about the
  16 # suitability of this software for any purpose.  It is provided "as is"
  17 # without express or implied warranty.
  18 #
  19
  20 This is a nearly-public-domain reimplementation of the V8 regexp(3) package.
  21 It gives C programs the ability to use egrep-style regular expressions, and
  22 does it in a much cleaner fashion than the analogous routines in SysV.
  23
  24         Copyright (c) 1986 by University of Toronto.
  25         Written by Henry Spencer.  Not derived from licensed software.
  26
  27         Permission is granted to anyone to use this software for any
  28         purpose on any computer system, and to redistribute it freely,
  29         subject to the following restrictions:
  30
  31         1. The author is not responsible for the consequences of use of
  32                 this software, no matter how awful, even if they arise
  33                 from defects in it.
  34
  35         2. The origin of this software must not be misrepresented, either
  36                 by explicit claim or by omission.
  37
  38         3. Altered versions must be plainly marked as such, and must not
  39                 be misrepresented as being the original software.
  40
  41 Barring a couple of small items in the BUGS list, this implementation is
  42 believed 100% compatible with V8.  It should even be binary-compatible,
  43 sort of, since the only fields in a "struct regexp" that other people have
  44 any business touching are declared in exactly the same way at the same
  45 location in the struct (the beginning).
  46
  47 This implementation is *NOT* AT&T/Bell code, and is not derived from licensed
  48 software.  Even though U of T is a V8 licensee.  This software is based on
  49 a V8 manual page sent to me by Dennis Ritchie (the manual page enclosed
  50 here is a complete rewrite and hence is not covered by AT&T copyright).
  51 The software was nearly complete at the time of arrival of our V8 tape.
  52 I haven't even looked at V8 yet, although a friend elsewhere at U of T has
  53 been kind enough to run a few test programs using the V8 regexp(3) to resolve
  54 a few fine points.  I admit to some familiarity with regular-expression
  55 implementations of the past, but the only one that this code traces any
  56 ancestry to is the one published in Kernighan & Plauger (from which this
  57 one draws ideas but not code).
  58
  59 Simplistically:  put this stuff into a source directory, copy regexp.h into
  60 /usr/include, inspect Makefile for compilation options that need changing
  61 to suit your local environment, and then do "make r".  This compiles the
  62 regexp(3) functions, compiles a test program, and runs a large set of
  63 regression tests.  If there are no complaints, then put regexp.o, regsub.o,
  64 and regerror.o into your C library, and regexp.3 into your manual-pages
  65 directory.
  66
  67 Note that if you don't put regexp.h into /usr/include *before* compiling,
  68 you'll have to add "-I." to CFLAGS before compiling.
  69
  70 The files are:
  71
  72 Makefile        instructions to make everything
  73 regexp.3        manual page
  74 regexp.h        header file, for /usr/include
  75 regexp.c        source for regcomp() and regexec()
  76 regsub.c        source for regsub()
  77 regerror.c      source for default regerror()
  78 regmagic.h      internal header file
  79 try.c           source for test program
  80 timer.c         source for timing program
  81 tests           test list for try and timer
  82
  83 This implementation uses nondeterministic automata rather than the
  84 deterministic ones found in some other implementations, which makes it
  85 simpler, smaller, and faster at compiling regular expressions, but slower
  86 at executing them.  In theory, anyway.  This implementation does employ
  87 some special-case optimizations to make the simpler cases (which do make
  88 up the bulk of regular expressions actually used) run quickly.  In general,
  89 if you want blazing speed you're in the wrong place.  Replacing the insides
  90 of egrep with this stuff is probably a mistake; if you want your own egrep
  91 you're going to have to do a lot more work.  But if you want to use regular
  92 expressions a little bit in something else, you're in luck.  Note that many
  93 existing text editors use nondeterministic regular-expression implementations,
  94 so you're in good company.
  95
  96 This stuff should be pretty portable, given appropriate option settings.
  97 If your chars have less than 8 bits, you're going to have to change the
  98 internal representation of the automaton, although knowledge of the details
  99 of this is fairly localized.  There are no "reserved" char values except for
 100 NUL, and no special significance is attached to the top bit of chars.
 101 The string(3) functions are used a fair bit, on the grounds that they are
 102 probably faster than coding the operations in line.  Some attempts at code
 103 tuning have been made, but this is invariably a bit machine-specific.