home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #1 / monster.zip / monster / PROG_C / SNIP9404.ZIP / GREP.C < prev    next >
C/C++ Source or Header  |  1994-04-03  |  16KB  |  568 lines
  1. /*
  2.  * The  information  in  this  document  is  subject  to  change
  3.  * without  notice  and  should not be construed as a commitment
  4.  * by Digital Equipment Corporation or by DECUS.
  5.  *
  6.  * Neither Digital Equipment Corporation, DECUS, nor the authors
  7.  * assume any responsibility for the use or reliability of  this
  8.  * document or the described software.
  9.  *
  10.  *      Copyright (C) 1980, DECUS
  11.  *
  12.  * General permission to copy or modify, but not for profit,  is
  13.  * hereby  granted,  provided that the above copyright notice is
  14.  * included and reference made to  the  fact  that  reproduction
  15.  * privileges were granted by DECUS.
  16.  */
  17. #include <stdio.h>
  18.  
  19. /*
  20.  * grep
  21.  *
  22.  * Runs on the Decus compiler or on vms, On vms, define as:
  23.  *      grep :== "$disk:[account]grep"      (native)
  24.  *      grep :== "$disk:[account]grep grep" (Decus)
  25.  * See below for more information.
  26.  */
  27.  
  28. char    *documentation[] = {
  29. "grep searches a file for a given pattern.  Execute by",
  30. "   grep [flags] regular_expression file_list\n",
  31. "Flags are single characters preceeded by '-':",
  32. "   -c      Only a count of matching lines is printed",
  33. "   -f      Print file name for matching lines switch, see below",
  34. "   -n      Each line is preceeded by its line number",
  35. "   -v      Only print non-matching lines\n",
  36. "The file_list is a list of files (wildcards are acceptable on RSX modes).",
  37. "\nThe file name is normally printed if there is a file given.",
  38. "The -f flag reverses this action (print name no file, not if more).\n",
  39. 0 };
  40.  
  41. char    *patdoc[] = {
  42. "The regular_expression defines the pattern to search for.  Upper- and",
  43. "lower-case are always ignored.  Blank lines never match.  The expression",
  44. "should be quoted to prevent file-name translation.",
  45. "x      An ordinary character (not mentioned below) matches that character.",
  46. "'\\'    The backslash quotes any character.  \"\\$\" matches a dollar-sign.",
  47. "'^'    A circumflex at the beginning of an expression matches the",
  48. "       beginning of a line.",
  49. "'$'    A dollar-sign at the end of an expression matches the end of a line.",
  50. "'.'    A period matches any character except \"new-line\".",
  51. "':a'   A colon matches a class of characters described by the following",
  52. "':d'     character.  \":a\" matches any alphabetic, \":d\" matches digits,",
  53. "':n'     \":n\" matches alphanumerics, \": \" matches spaces, tabs, and",
  54. "': '     other control characters, such as new-line.",
  55. "'*'    An expression followed by an asterisk matches zero or more",
  56. "       occurrances of that expression: \"fo*\" matches \"f\", \"fo\"",
  57. "       \"foo\", etc.",
  58. "'+'    An expression followed by a plus sign matches one or more",
  59. "       occurrances of that expression: \"fo+\" matches \"fo\", etc.",
  60. "'-'    An expression followed by a minus sign optionally matches",
  61. "       the expression.",
  62. "'[]'   A string enclosed in square brackets matches any character in",
  63. "       that string, but no others.  If the first character in the",
  64. "       string is a circumflex, the expression matches any character",
  65. "       except \"new-line\" and the characters in the string.  For",
  66. "       example, \"[xyz]\" matches \"xx\" and \"zyx\", while \"[^xyz]\"",
  67. "       matches \"abc\" but not \"axb\".  A range of characters may be",
  68. "       specified by two characters separated by \"-\".  Note that,",
  69. "       [a-z] matches alphabetics, while [z-a] never matches.",
  70. "The concatenation of regular expressions is a regular expression.",
  71. 0};
  72.  
  73. #define LMAX    512
  74. #define PMAX    256
  75.  
  76. #define CHAR    1
  77. #define BOL     2
  78. #define EOL     3
  79. #define ANY     4
  80. #define CLASS   5
  81. #define NCLASS  6
  82. #define STAR    7
  83. #define PLUS    8
  84. #define MINUS   9
  85. #define ALPHA   10
  86. #define DIGIT   11
  87. #define NALPHA  12
  88. #define PUNCT   13
  89. #define RANGE   14
  90. #define ENDPAT  15
  91.  
  92. int cflag=0, fflag=0, nflag=0, vflag=0, nfile=0, debug=0;
  93.  
  94. char *pp, lbuf[LMAX], pbuf[PMAX];
  95.  
  96. extern char *cclass(), *pmatch();
  97.  
  98.  
  99. /*** Main program - parse arguments & grep *************/
  100. main(argc, argv)
  101. int argc;
  102. char *argv[];
  103. {
  104.    register char   *p;
  105.    register int    c, i;
  106.    int             gotpattern;
  107.  
  108.    FILE            *f;
  109.  
  110.    if (argc <= 1)
  111.       usage("No arguments");
  112.    if (argc == 2 && argv[1][0] == '?' && argv[1][1] == 0) {
  113.       help(documentation);
  114.       help(patdoc);
  115.       return;
  116.       }
  117.    nfile = argc-1;
  118.    gotpattern = 0;
  119.    for (i=1; i < argc; ++i) {
  120.       p = argv[i];
  121.       if (*p == '-') {
  122.          ++p;
  123.          while (c = *p++) {
  124.             switch(tolower(c)) {
  125.  
  126.             case '?':
  127.                help(documentation);
  128.                break;
  129.  
  130.             case 'C':
  131.             case 'c':
  132.                ++cflag;
  133.                break;
  134.  
  135.             case 'D':
  136.             case 'd':
  137.                ++debug;
  138.                break;
  139.  
  140.             case 'F':
  141.             case 'f':
  142.                ++fflag;
  143.                break;
  144.  
  145.             case 'n':
  146.             case 'N':
  147.                ++nflag;
  148.                break;
  149.  
  150.             case 'v':
  151.             case 'V':
  152.                ++vflag;
  153.                break;
  154.  
  155.             default:
  156.                usage("Unknown flag");
  157.             }
  158.          }
  159.          argv[i] = 0;
  160.          --nfile;
  161.       } else if (!gotpattern) {
  162.          compile(p);
  163.          argv[i] = 0;
  164.          ++gotpattern;
  165.          --nfile;
  166.       }
  167.    }
  168.    if (!gotpattern)
  169.       usage("No pattern");
  170.    if (nfile == 0)
  171.       grep(stdin, 0);
  172.    else {
  173.       fflag = fflag ^ (nfile > 0);
  174.       for (i=1; i < argc; ++i) {
  175.          if (p = argv[i]) {
  176.             if ((f=fopen(p, "r")) == NULL)
  177.                cant(p);
  178.             else {
  179.                grep(f, p);
  180.                fclose(f);
  181.             }
  182.          }
  183.       }
  184.    }
  185. }
  186.  
  187. /*** Display a file name *******************************/
  188. file(s)
  189. char *s;
  190. {
  191.    printf("File %s:\n", s);
  192. }
  193.  
  194. /*** Report unopenable file ****************************/
  195. cant(s)
  196. char *s;
  197. {
  198.    fprintf(stderr, "%s: cannot open\n", s);
  199. }
  200.  
  201. /*** Give good help ************************************/
  202. help(hp)
  203. char **hp;
  204. {
  205.    register char   **dp;
  206.  
  207.    for (dp = hp; *dp; ++dp)
  208.       printf("%s\n", *dp);
  209. }
  210.  
  211. /*** Display usage summary *****************************/
  212. usage(s)
  213. char    *s;
  214. {
  215.    fprintf(stderr, "?GREP-E-%s\n", s);
  216.    fprintf(stderr,
  217.       "Usage: grep [-cfnv] pattern [file ...].  grep ? for help\n");
  218.    exit(1);
  219. }
  220.  
  221. /*** Compile the pattern into global pbuf[] ************/
  222. compile(source)
  223. char       *source;   /* Pattern to compile */
  224. {
  225.    register char  *s;         /* Source string pointer     */
  226.    register char  *lp;        /* Last pattern pointer      */
  227.    register int   c;          /* Current character         */
  228.    int            o;          /* Temp                      */
  229.    char           *spp;       /* Save beginning of pattern */
  230.  
  231.    s = source;
  232.    if (debug)
  233.       printf("Pattern = \"%s\"\n", s);
  234.    pp = pbuf;
  235.    while (c = *s++) {
  236.       /*
  237.        * STAR, PLUS and MINUS are special.
  238.        */
  239.       if (c == '*' || c == '+' || c == '-') {
  240.          if (pp == pbuf ||
  241.               (o=pp[-1]) == BOL ||
  242.               o == EOL ||
  243.               o == STAR ||
  244.               o == PLUS ||
  245.               o == MINUS)
  246.             badpat("Illegal occurrance op.", source, s);
  247.          store(ENDPAT);
  248.          store(ENDPAT);
  249.          spp = pp;               /* Save pattern end     */
  250.          while (--pp > lp)       /* Move pattern down    */
  251.             *pp = pp[-1];        /* one byte             */
  252.          *pp =   (c == '*') ? STAR :
  253.             (c == '-') ? MINUS : PLUS;
  254.          pp = spp;               /* Restore pattern end  */
  255.          continue;
  256.       }
  257.       /*
  258.        * All the rest.
  259.        */
  260.       lp = pp;         /* Remember start       */
  261.       switch(c) {
  262.  
  263.       case '^':
  264.          store(BOL);
  265.          break;
  266.  
  267.       case '$':
  268.          store(EOL);
  269.          break;
  270.  
  271.       case '.':
  272.          store(ANY);
  273.          break;
  274.  
  275.       case '[':
  276.          s = cclass(source, s);
  277.          break;
  278.  
  279.       case ':':
  280.          if (*s) {
  281.             switch(tolower(c = *s++)) {
  282.  
  283.             case 'a':
  284.             case 'A':
  285.                store(ALPHA);
  286.                break;
  287.  
  288.             case 'd':
  289.             case 'D':
  290.                store(DIGIT);
  291.                break;
  292.  
  293.             case 'n':
  294.             case 'N':
  295.                store(NALPHA);
  296.                break;
  297.  
  298.             case ' ':
  299.                store(PUNCT);
  300.                break;
  301.  
  302.             default:
  303.                badpat("Unknown : type", source, s);
  304.  
  305.             }
  306.             break;
  307.          }
  308.          else    badpat("No : type", source, s);
  309.  
  310.       case '\\':
  311.          if (*s)
  312.             c = *s++;
  313.  
  314.       default:
  315.          store(CHAR);
  316.          store(tolower(c));
  317.       }
  318.    }
  319.    store(ENDPAT);
  320.    store(0);                /* Terminate string     */
  321.    if (debug) {
  322.       for (lp = pbuf; lp < pp;) {
  323.          if ((c = (*lp++ & 0377)) < ' ')
  324.             printf("\\%o ", c);
  325.          else    printf("%c ", c);
  326.         }
  327.         printf("\n");
  328.    }
  329. }
  330.  
  331. /*** Compile a class (within []) ***********************/
  332. char *cclass(source, src)
  333. char       *source;   /* Pattern start -- for error msg. */
  334. char       *src;      /* Class start */
  335. {
  336.    register char   *s;        /* Source pointer    */
  337.    register char   *cp;       /* Pattern start     */
  338.    register int    c;         /* Current character */
  339.    int             o;         /* Temp              */
  340.  
  341.    s = src;
  342.    o = CLASS;
  343.    if (*s == '^') {
  344.       ++s;
  345.       o = NCLASS;
  346.    }
  347.    store(o);
  348.    cp = pp;
  349.    store(0);                          /* Byte count      */
  350.    while ((c = *s++) && c!=']') {
  351.       if (c == '\\') {                /* Store quoted char    */
  352.          if ((c = *s++) == '\0')      /* Gotta get something  */
  353.             badpat("Class terminates badly", source, s);
  354.          else    store(tolower(c));
  355.       }
  356.       else if (c == '-' &&
  357.             (pp - cp) > 1 && *s != ']' && *s != '\0') {
  358.          c = pp[-1];             /* Range start     */
  359.          pp[-1] = RANGE;         /* Range signal    */
  360.          store(c);               /* Re-store start  */
  361.          c = *s++;               /* Get end char and*/
  362.          store(tolower(c));      /* Store it        */
  363.       }
  364.       else {
  365.          store(tolower(c));      /* Store normal char */
  366.       }
  367.    }
  368.    if (c != ']')
  369.       badpat("Unterminated class", source, s);
  370.    if ((c = (pp - cp)) >= 256)
  371.       badpat("Class too large", source, s);
  372.    if (c == 0)
  373.       badpat("Empty class", source, s);
  374.    *cp = c;
  375.    return(s);
  376. }
  377.  
  378. /*** Store an entry in the pattern buffer **************/
  379. store(op)
  380.    int op;
  381. {
  382.    if (pp >= &pbuf[PMAX])
  383.       error("Pattern too complex\n");
  384.    *pp++ = op;
  385. }
  386.  
  387. /*** Report a bad pattern specification ****************/
  388. badpat(message, source, stop)
  389. char  *message;       /* Error message */
  390. char  *source;        /* Pattern start */
  391. char  *stop;          /* Pattern end   */
  392. {
  393.    fprintf(stderr, "-GREP-E-%s, pattern is\"%s\"\n", message, source);
  394.    fprintf(stderr, "-GREP-E-Stopped at byte %d, '%c'\n",
  395.          stop-source, stop[-1]);
  396.    error("?GREP-E-Bad pattern\n");
  397. }
  398.  
  399. /*** Scan the file for the pattern in pbuf[] ***********/
  400. grep(fp, fn)
  401. FILE       *fp;       /* File to process            */
  402. char       *fn;       /* File name (for -f option)  */
  403. {
  404.    register int lno, count, m;
  405.  
  406.    lno = 0;
  407.    count = 0;
  408.    while (fgets(lbuf, LMAX, fp)) {
  409.       ++lno;
  410.       m = match();
  411.       if ((m && !vflag) || (!m && vflag)) {
  412.          ++count;
  413.          if (!cflag) {
  414.             if (fflag && fn) {
  415.                file(fn);
  416.                fn = 0;
  417.             }
  418.             if (nflag)
  419.                printf("%d\t", lno);
  420.             printf("%s\n", lbuf);
  421.          }
  422.       }
  423.    }
  424.    if (cflag) {
  425.       if (fflag && fn)
  426.          file(fn);
  427.       printf("%d\n", count);
  428.    }
  429. }
  430.  
  431. /*** Match line (lbuf) with pattern (pbuf) return 1 if match ***/
  432. match()
  433. {
  434.    register char   *l;        /* Line pointer       */
  435.  
  436.    for (l = lbuf; *l; ++l) {
  437.       if (pmatch(l, pbuf))
  438.          return(1);
  439.    }
  440.    return(0);
  441. }
  442.  
  443. /*** Match partial line with pattern *******************/
  444. char *pmatch(line, pattern)
  445. char               *line;     /* (partial) line to match      */
  446. char               *pattern;  /* (partial) pattern to match   */
  447. {
  448.    register char   *l;        /* Current line pointer         */
  449.    register char   *p;        /* Current pattern pointer      */
  450.    register char   c;         /* Current character            */
  451.    char            *e;        /* End for STAR and PLUS match  */
  452.    int             op;        /* Pattern operation            */
  453.    int             n;         /* Class counter                */
  454.    char            *are;      /* Start of STAR match          */
  455.  
  456.    l = line;
  457.    if (debug > 1)
  458.       printf("pmatch(\"%s\")\n", line);
  459.    p = pattern;
  460.    while ((op = *p++) != ENDPAT) {
  461.       if (debug > 1)
  462.          printf("byte[%d] = 0%o, '%c', op = 0%o\n",
  463.                l-line, *l, *l, op);
  464.       switch(op) {
  465.  
  466.       case CHAR:
  467.          if (tolower(*l++) != *p++)
  468.             return(0);
  469.          break;
  470.  
  471.       case BOL:
  472.          if (l != lbuf)
  473.             return(0);
  474.          break;
  475.  
  476.       case EOL:
  477.          if (*l != '\0')
  478.             return(0);
  479.          break;
  480.  
  481.       case ANY:
  482.          if (*l++ == '\0')
  483.             return(0);
  484.          break;
  485.  
  486.       case DIGIT:
  487.          if ((c = *l++) < '0' || (c > '9'))
  488.             return(0);
  489.          break;
  490.  
  491.       case ALPHA:
  492.          c = tolower(*l++);
  493.          if (c < 'a' || c > 'z')
  494.             return(0);
  495.          break;
  496.  
  497.       case NALPHA:
  498.          c = tolower(*l++);
  499.          if (c >= 'a' && c <= 'z')
  500.             break;
  501.          else if (c < '0' || c > '9')
  502.             return(0);
  503.          break;
  504.  
  505.       case PUNCT:
  506.          c = *l++;
  507.          if (c == 0 || c > ' ')
  508.             return(0);
  509.          break;
  510.  
  511.       case CLASS:
  512.       case NCLASS:
  513.          c = tolower(*l++);
  514.          n = *p++ & 0377;
  515.          do {
  516.             if (*p == RANGE) {
  517.                p += 3;
  518.                n -= 2;
  519.                if (c >= p[-2] && c <= p[-1])
  520.                   break;
  521.             }
  522.             else if (c == *p++)
  523.                break;
  524.          } while (--n > 1);
  525.          if ((op == CLASS) == (n <= 1))
  526.             return(0);
  527.          if (op == CLASS)
  528.             p += n - 2;
  529.          break;
  530.  
  531.       case MINUS:
  532.          e = pmatch(l, p);       /* Look for a match    */
  533.          while (*p++ != ENDPAT); /* Skip over pattern   */
  534.          if (e)                  /* Got a match?        */
  535.             l = e;               /* Yes, update string  */
  536.          break;                  /* Always succeeds     */
  537.  
  538.       case PLUS:                 /* One or more ...     */
  539.          if ((l = pmatch(l, p)) == 0)
  540.             return(0);           /* Gotta have a match  */
  541.       case STAR:                 /* Zero or more ...    */
  542.          are = l;                /* Remember line start */
  543.          while (*l && (e = pmatch(l, p)))
  544.             l = e;               /* Get longest match   */
  545.          while (*p++ != ENDPAT); /* Skip over pattern   */
  546.          while (l >= are) {      /* Try to match rest   */
  547.             if (e = pmatch(l, p))
  548.                return(e);
  549.             --l;                 /* Nope, try earlier   */
  550.          }
  551.          return(0);              /* Nothing else worked */
  552.  
  553.       default:
  554.          printf("Bad op code %d\n", op);
  555.          error("Cannot happen -- match\n");
  556.       }
  557.    }
  558.    return(l);
  559. }
  560.  
  561. /*** Report an error ***********************************/
  562. error(s)
  563. char *s;
  564. {
  565.    fprintf(stderr, "%s", s);
  566.    exit(1);
  567. }
  568.