home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource3 / 167_01 / fgrep.c < prev    next >
Text File  |  1985-11-15  |  23KB  |  925 lines
  1. /* 
  2. HEADER:     CUG
  3. TITLE:        FGREP.C - Search File(s) for Fixed Pattern(s);
  4. VERSION:    1.06;
  5. DATE:        09/13/86;
  6. DESCRIPTION:    "A full implementation of the UNIX 'fgrep'
  7.         utility. The algorithm used in this program
  8.         constructs a deterministic finite state automaton
  9.         (FSA) for pattern matching from the substrings,
  10.         then uses the FSA to process the text string in
  11.         one pass. The time taken to construct the FSA is
  12.         proportional to the sum of the lengths of the
  13.         substrings. The number of state transitions made
  14.         by the FSA in processing the text string is
  15.         independent of the number of substrings.";
  16. KEYWORDS:    fgrep, grep, filter, UNIX, pattern-matching;
  17. SYSTEM:        ANY;
  18. FILENAME:    FGREP.C;
  19. WARNINGS:    "The '-s' option may not be consistently
  20.         supported by various non-Unix operating systems
  21.         and compilers. Also, the Unix-specific '-b'
  22.         option of 'fgrep' is not supported. Finally,
  23.         non-Unix operating systems may not accept
  24.         lowercase character strings on the command line,
  25.         although these can be entered through files.";
  26. CRC:        xxxx
  27. SEE-ALSO:    FGREP.DOC;
  28. AUTHORS:    Ian Ashdown - byHeart Software;
  29. COMPILERS:    ANY;
  30. REFERENCES:    AUTHORS: Bell Telephone Laboratories;
  31.         TITLE:     UNIX Programmer's Manual Vol. 1, p. 166;
  32.         AUTHORS: A.V. Aho & M.J. Corasick;
  33.         TITLE:     'Efficient String Matching: An Aid to
  34.              Bibliographic Search'
  35.              Communications of the ACM
  36.              pp. 333 - 340, Vol. 18 No. 6 (June '75);
  37. ENDREF
  38. */
  39.  
  40. /*-------------------------------------------------------------*/
  41.  
  42. /* FGREP.C - Search File(s) For Fixed Pattern(s)
  43.  *
  44.  * Version 1.06          September 13th, 1986
  45.  *
  46.  * Modifications:
  47.  *
  48.  *   V1.00 (84/12/01)    - beta test release
  49.  *   V1.01 (85/01/01)    - added -P option
  50.  *            - improved command line validation
  51.  *   V1.02 (85/01/06)    - modified "run_fsa()" and "bd_move()"
  52.  *   V1.03 (85/02/11)    - added -S option
  53.  *   V1.04 (85/09/08)    - corrected "bd_go()" for UNIX
  54.  *   V1.05 (85/09/20)    - (Lloyd Rice, Computalker Consultants)
  55.  *            - added definitions for Lattice C
  56.  *            - linecount complemented for -CV option
  57.  *            - buffer added for "stoupper()"
  58.  *            - allowed for signed char representations
  59.  *   V1.06 (86/09/13)    - corrected -P option bug
  60.  *
  61.  * Copyright 1985,1986: Ian Ashdown
  62.  *                byHeart Software
  63.  *                620 Ballantree Road
  64.  *                West Vancouver, B.C.
  65.  *                Canada V7S 1W3
  66.  *
  67.  * This program may be copied for personal, non-commercial use
  68.  * only, provided that the above copyright notice is included in
  69.  * all copies of the source code. Copying for any other use
  70.  * without previously obtaining the written permission of the
  71.  * author is prohibited.
  72.  *
  73.  * Notes:
  74.  *
  75.  * The algorithm used in this program constructs a deterministic
  76.  * finite state automaton (FSA) for pattern matching from the sub-
  77.  * strings, then uses the FSA to process the text string in one
  78.  * pass. The time taken to construct the FSA is proportional to
  79.  * the sum of the lengths of the the substrings. The number of
  80.  * state transitions made by the FSA in processing the text
  81.  * string is independent of the number of substrings.
  82.  *
  83.  * Algorithm Source:
  84.  *
  85.  * "Efficient String Matching: An Aid to Bibliographic Search"
  86.  * Alfred V. Aho & Margaret J. Corasick
  87.  * Communications of the ACM
  88.  * pp. 333 - 340, Vol. 18 No. 6 (June '75)
  89.  *
  90.  * USAGE: fgrep [-vclnhyefxps] [strings] <files>
  91.  *
  92.  * where:
  93.  *
  94.  *    -v    All lines but those matching are printed.
  95.  *    -c    Only a count of the matching lines is printed.
  96.  *    -l    The names of the files with matching lines are
  97.  *        listed (once), separated by newlines.
  98.  *    -n    Each line is preceded by its line number in the
  99.  *        file.
  100.  *    -h    Do not print filename headers with output lines.
  101.  *    -y    All characters in the file are mapped to upper
  102.  *        case before matching. (This is the default if the
  103.  *        string is given in the command line under CP/M,
  104.  *        as CP/M maps everything on the command line to
  105.  *        upper case. Use the -f option if you need both
  106.  *        lower and upper case.) Not a true UNIX "fgrep"
  107.  *        option (normally available under "grep" only),
  108.  *        but too useful to leave out.
  109.  *    -e    <string>. Same as a string argument, but useful
  110.  *        when the string begins with a '-'.
  111.  *    -f    <file>. The strings (separated by newlines) are
  112.  *        taken from a file. If several strings are listed
  113.  *        in the file, then a match is flagged if any of
  114.  *        the strings are matched. If -f is given, any
  115.  *        following argument on the command line is taken
  116.  *        to be a filename.
  117.  *    -x    Only lines matched in their entirety are printed.
  118.  *    -p    Each matched line is preceded by the matching
  119.  *        substring(s). Not a UNIX "fgrep" option, but too
  120.  *        useful to leave out.
  121.  *    -s    No output is produced, only status. Used when
  122.  *        when "fgrep" is run as a process that returns a
  123.  *        status value to its parent process. Under CP/M, a
  124.  *        non-zero value returned by "exit()" may terminate
  125.  *        a submit file that initiated the program,
  126.  *        although this is implementation-dependent.
  127.  *
  128.  * DIAGNOSTICS:
  129.  *
  130.  * Exit status is 0 if any matches are found, 1 if none, 2 for
  131.  * error condition.
  132.  *
  133.  * BUGS:
  134.  *
  135.  * The following UNIX-specific option is not supported:
  136.  *
  137.  *    -b    Each line is preceded by the block number in
  138.  *        which it was found
  139.  *
  140.  * Lines are limited to 256 characters.
  141.  *
  142.  */
  143.  
  144. /*** Definitions ***/
  145.  
  146. #define TRUE          -1
  147. #define FALSE           0
  148. #define MAX_LINE     257  /* Maximum number of characters */
  149.                   /* per line plus NULL delimiter */
  150. #define CP/M              /* Comment out for compilation */
  151.                   /* under UNIX or MS-DOS */
  152.  
  153. /* The following definition applies to the Lattice C compiler
  154.  * (Version 2.15) for MS-DOS. The Lattice library does not have
  155.  * the Unix function "index()". However, it does have an
  156.  * equivalent function called "stpchr()".
  157.  */
  158.  
  159. /* #define index stpchr */    /* Remove comment delimiters for */
  160.                   /* Lattice C version 2.15 */
  161.  
  162. #define CMD_ERR       0    /* Error codes */
  163. #define OPT_ERR       1
  164. #define INP_ERR       2
  165. #define STR_ERR       3
  166. #define MEM_ERR       4
  167.  
  168. /*** Typedefs ***/
  169.  
  170. typedef int BOOL;    /* Boolean flag */
  171.  
  172. /* Some C compilers, including Lattice C, do not support the
  173.  * "void" data type. Remove the following comment delimiters for
  174.  * such compilers.
  175.  */
  176.  
  177. /* typedef int void; */
  178.  
  179. /*** Data Structures ***/
  180.  
  181. /* Queue element */
  182.  
  183. typedef struct queue
  184. {
  185.   struct state_el *st_ptr;
  186.   struct queue *next_el;
  187. } QUEUE;
  188.  
  189. /* Transition element */
  190.  
  191. typedef struct transition
  192. {
  193.   char lchar;            /* Transition character */
  194.   struct state_el *nextst_ptr;    /* Transition state pointer */
  195.   struct transition *next_el;
  196. } TRANSITION;
  197.  
  198. /* FSA state element */
  199.  
  200. typedef struct state_el
  201. {
  202.   TRANSITION *go_ls;    /* Pointer to head of "go" list */
  203.   TRANSITION *mv_ls;    /* Pointer to head of "move" list */
  204.   struct state_el *fail_state;    /* "failure" transition state */
  205.   char *out_str;    /* Terminal state message (if any) */
  206. } FSA;
  207.  
  208. /*** Global Variables and Structures ***/
  209.  
  210. /* Dummy "failure" state */
  211.  
  212. FSA FAIL_STATE;
  213.  
  214. /* Define a separate data structure for State 0 of the FSA to
  215.  * speed processing of the input while the FSA is in that state.
  216.  * Since the Aho-Corasick algorithm only defines "go" transitions
  217.  * for this state (one for each valid input character) and no
  218.  * "failure" transitions or output messages, only an array of
  219.  * "go" transition state numbers is needed. The array is accessed
  220.  * directly, using the input character as the index.
  221.  */
  222.  
  223. FSA *MZ[128];    /* State 0 of FSA */
  224.  
  225. BOOL vflag = FALSE,    /* Command-line option flags */
  226.      cflag = FALSE,
  227.      lflag = FALSE,
  228.      nflag = FALSE,
  229.      hflag = FALSE,
  230.      yflag = FALSE,
  231.      eflag = FALSE,
  232.      fflag = FALSE,
  233.      xflag = FALSE,
  234.      pflag = FALSE,
  235.      sflag = FALSE;
  236.  
  237. /*** Include Files ***/
  238.  
  239. #include <stdio.h>
  240. #include <ctype.h>
  241.  
  242. /*** Main Body of Program ***/
  243.  
  244. int main(argc,argv)
  245. int argc;
  246. char **argv;
  247. {
  248.   char *temp;
  249.   BOOL match_flag = FALSE,
  250.        proc_file();
  251.   void bd_go(),
  252.        bd_move(),
  253.        error();
  254.  
  255.   /* Check for minimum number of command line arguments */
  256.  
  257.   if(argc < 2)
  258.     error(CMD_ERR,N