home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / egrep.y < prev    next >
Encoding:
Text File  |  1979-02-26  |  10.4 KB  |  595 lines
  1. /*
  2.  * egrep -- print lines containing (or not containing) a regular expression
  3.  *
  4.  *    status returns:
  5.  *        0 - ok, and some matches
  6.  *        1 - ok, but no matches
  7.  *        2 - some error
  8.  */
  9. %token CHAR DOT CCL NCCL OR CAT STAR PLUS QUEST
  10. %left OR
  11. %left CHAR DOT CCL NCCL '('
  12. %left CAT
  13. %left STAR PLUS QUEST
  14.  
  15. %{
  16. #include <stdio.h>
  17.  
  18. #define MAXLIN 350
  19. #define MAXPOS 4000
  20. #define NCHARS 128
  21. #define NSTATES 128
  22. #define FINAL -1
  23. char gotofn[NSTATES][NCHARS];
  24. int state[NSTATES];
  25. char out[NSTATES];
  26. int line 1;
  27. int name[MAXLIN];
  28. int left[MAXLIN];
  29. int right[MAXLIN];
  30. int parent[MAXLIN];
  31. int foll[MAXLIN];
  32. int positions[MAXPOS];
  33. char chars[MAXLIN];
  34. int nxtpos;
  35. int nxtchar 0;
  36. int tmpstat[MAXLIN];
  37. int initstat[MAXLIN];
  38. int xstate;
  39. int count;
  40. int icount;
  41. char *input;
  42.  
  43. long    lnum;
  44. int    bflag;
  45. int    cflag;
  46. int    fflag;
  47. int    lflag;
  48. int    nflag;
  49. int    hflag    = 1;
  50. int    sflag;
  51. int    vflag;
  52. int    nfile;
  53. long    blkno;
  54. long    tln;
  55. int    nsucc;
  56.  
  57. int    f;
  58. int    fname;
  59. %}
  60.  
  61. %%
  62. s:    t
  63.         ={ unary(FINAL, $1);
  64.           line--;
  65.         }
  66.     ;
  67. t:    b r
  68.         ={ $$ = node(CAT, $1, $2); }
  69.     | OR b r OR
  70.         ={ $$ = node(CAT, $2, $3); }
  71.     | OR b r
  72.         ={ $$ = node(CAT, $2, $3); }
  73.     | b r OR
  74.         ={ $$ = node(CAT, $1, $2); }
  75.     ;
  76. b:
  77.         ={ $$ = enter(DOT);
  78.            $$ = unary(STAR, $$); }
  79.     ;
  80. r:    CHAR
  81.         ={ $$ = enter($1); }
  82.     | DOT
  83.         ={ $$ = enter(DOT); }
  84.     | CCL
  85.         ={ $$ = cclenter(CCL); }
  86.     | NCCL
  87.         ={ $$ = cclenter(NCCL); }
  88.     ;
  89.  
  90. r:    r OR r
  91.         ={ $$ = node(OR, $1, $3); }
  92.     | r r %prec CAT
  93.         ={ $$ = node(CAT, $1, $2); }
  94.     | r STAR
  95.         ={ $$ = unary(STAR, $1); }
  96.     | r PLUS
  97.         ={ $$ = unary(PLUS, $1); }
  98.     | r QUEST
  99.         ={ $$ = unary(QUEST, $1); }
  100.     | '(' r ')'
  101.         ={ $$ = $2; }
  102.     | error 
  103.     ;
  104.  
  105. %%
  106. yyerror(s) {
  107.     fprintf(stderr, "egrep: %s\n", s);
  108.     exit(2);
  109. }
  110.  
  111. yylex() {
  112.     extern int yylval;
  113.     int cclcnt, x;
  114.     register char c, d;
  115.     switch(c = nextch()) {
  116.         case '$':
  117.         case '^': c = '\n';
  118.             goto defchar;
  119.         case '|': return (OR);
  120.         case '*': return (STAR);
  121.         case '+': return (PLUS);
  122.         case '?': return (QUEST);
  123.         case '(': return (c);
  124.         case ')': return (c);
  125.         case '.': return (DOT);
  126.         case '\0': return (0);
  127.         case '\n': return (OR);
  128.         case '[': 
  129.             x = CCL;
  130.             cclcnt = 0;
  131.             count = nxtchar++;
  132.             if ((c = nextch()) == '^') {
  133.                 x = NCCL;
  134.                 c = nextch();
  135.             }
  136.             do {
  137.                 if (c == '\0') synerror();
  138.                 if (c == '-' && cclcnt > 0 && chars[nxtchar-1] != 0) {
  139.                     if ((d = nextch()) != 0) {
  140.                         c = chars[nxtchar-1];
  141.                         while (c < d) {
  142.                             if (nxtchar >= MAXLIN) overflo();
  143.                             chars[nxtchar++] = ++c;
  144.                             cclcnt++;
  145.                         }
  146.                         continue;
  147.                     }
  148.                 }
  149.                 if (nxtchar >= MAXLIN) overflo();
  150.                 chars[nxtchar++] = c;
  151.                 cclcnt++;
  152.             } while ((c = nextch()) != ']');
  153.             chars[count] = cclcnt;
  154.             return (x);
  155.         case '\\':
  156.             if ((c = nextch()) == '\0') synerror();
  157.         defchar:
  158.         default: yylval = c; return (CHAR);
  159.     }
  160. }
  161. nextch() {
  162.     register char c;
  163.     if (fflag) {
  164.         if ((c = getc(stdin)) == EOF) return(0);
  165.     }
  166.     else c = *input++;
  167.     return(c);
  168. }
  169.  
  170. synerror() {
  171.     fprintf(stderr, "egrep: syntax error\n");
  172.     exit(2);
  173. }
  174.  
  175. enter(x) int x; {
  176.     if(line >= MAXLIN) overflo();
  177.     name[line] = x;
  178.     left[line] = 0;
  179.     right[line] = 0;
  180.     return(line++);
  181. }
  182.  
  183. cclenter(x) int x; {
  184.     register linno;
  185.     linno = enter(x);
  186.     right[linno] = count;
  187.     return (linno);
  188. }
  189.  
  190. node(x, l, r) {
  191.     if(line >= MAXLIN) overflo();
  192.     name[line] = x;
  193.     left[line] = l;
  194.     right[line] = r;
  195.     parent[l] = line;
  196.     parent[r] = line;
  197.     return(line++);
  198. }
  199.  
  200. unary(x, d) {
  201.     if(line >= MAXLIN) overflo();
  202.     name[line] = x;
  203.     left[line] = d;
  204.     right[line] = 0;
  205.     parent[d] = line;
  206.     return(line++);
  207. }
  208. overflo() {
  209.     fprintf(stderr, "egrep: regular expression too long\n");
  210.     exit(2);
  211. }
  212.  
  213. cfoll(v) {
  214.     register i;
  215.     if (left[v] == 0) {
  216.         count = 0;
  217.         for (i=1; i<=line; i++) tmpstat[i] = 0;
  218.         follow(v);
  219.         add(foll, v);
  220.     }
  221.     else if (right[v] == 0) cfoll(left[v]);
  222.     else {
  223.         cfoll(left[v]);
  224.         cfoll(right[v]);
  225.     }
  226. }
  227. cgotofn() {
  228.     register c, i, k;
  229.     int n, s;
  230.     char symbol[NCHARS];
  231.     int j, nc, pc, pos;
  232.     int curpos, num;
  233.     int number, newpos;
  234.     count = 0;
  235.     for (n=3; n<=line; n++) tmpstat[n] = 0;
  236.     if (cstate(line-1)==0) {
  237.         tmpstat[line] = 1;
  238.         count++;
  239.         out[0] = 1;
  240.     }
  241.     for (n=3; n<=line; n++) initstat[n] = tmpstat[n];
  242.     count--;        /*leave out position 1 */
  243.     icount = count;
  244.     tmpstat[1] = 0;
  245.     add(state, 0);
  246.     n = 0;
  247.     for (s=0; s<=n; s++)  {
  248.         if (out[s] == 1) continue;
  249.         for (i=0; i<NCHARS; i++) symbol[i] = 0;
  250.         num = positions[state[s]];
  251.         count = icount;
  252.         for (i=3; i<=line; i++) tmpstat[i] = initstat[i];
  253.         pos = state[s] + 1;
  254.         for (i=0; i<num; i++) {
  255.             curpos = positions[pos];
  256.             if ((c = name[curpos]) >= 0) {
  257.                 if (c < NCHARS) symbol[c] = 1;
  258.                 else if (c == DOT) {
  259.                     for (k=0; k<NCHARS; k++)
  260.                         if (k!='\n') symbol[k] = 1;
  261.                 }
  262.                 else if (c == CCL) {
  263.                     nc = chars[right[curpos]];
  264.                     pc = right[curpos] + 1;
  265.                     for (k=0; k<nc; k++) symbol[chars[pc++]] = 1;
  266.                 }
  267.                 else if (c == NCCL) {
  268.                     nc = chars[right[curpos]];
  269.                     for (j = 0; j < NCHARS; j++) {
  270.                         pc = right[curpos] + 1;
  271.                         for (k = 0; k < nc; k++)
  272.                             if (j==chars[pc++]) goto cont;
  273.                         if (j!='\n') symbol[j] = 1;
  274.                         cont:;
  275.                     }
  276.                 }
  277.                 else printf("something's funny\n");
  278.             }
  279.             pos++;
  280.         }
  281.         for (c=0; c<NCHARS; c++) {
  282.             if (symbol[c] == 1) { /* nextstate(s,c) */
  283.                 count = icount;
  284.                 for (i=3; i <= line; i++) tmpstat[i] = initstat[i];
  285.                 pos = state[s] + 1;
  286.                 for (i=0; i<num; i++) {
  287.                     curpos = positions[pos];
  288.                     if ((k = name[curpos]) >= 0)
  289.                         if (
  290.                             (k == c)
  291.                             | (k == DOT)
  292.                             | (k == CCL && member(c, right[curpos], 1))
  293.                             | (k == NCCL && member(c, right[curpos], 0))
  294.                         ) {
  295.                             number = positions[foll[curpos]];
  296.                             newpos = foll[curpos] + 1;
  297.                             for (k=0; k<number; k++) {
  298.                                 if (tmpstat[positions[newpos]] != 1) {
  299.                                     tmpstat[positions[newpos]] = 1;
  300.                                     count++;
  301.                                 }
  302.                                 newpos++;
  303.                             }
  304.                         }
  305.                     pos++;
  306.                 } /* end nextstate */
  307.                 if (notin(n)) {
  308.                     if (n >= NSTATES) overflo();
  309.                     add(state, ++n);
  310.                     if (tmpstat[line] == 1) out[n] = 1;
  311.                     gotofn[s][c] = n;
  312.                 }
  313.                 else {
  314.                     gotofn[s][c] = xstate;
  315.                 }
  316.             }
  317.         }
  318.     }
  319. }
  320.  
  321. cstate(v) {
  322.     register b;
  323.     if (left[v] == 0) {
  324.         if (tmpstat[v] != 1) {
  325.             tmpstat[v] = 1;
  326.             count++;
  327.         }
  328.         return(1);
  329.     }
  330.     else if (right[v] == 0) {
  331.         if (cstate(left[v]) == 0) return (0);
  332.         else if (name[v] == PLUS) return (1);
  333.         else return (0);
  334.     }
  335.     else if (name[v] == CAT) {
  336.         if (cstate(left[v]) == 0 && cstate(right[v]) == 0) return (0);
  337.         else return (1);
  338.     }
  339.     else { /* name[v] == OR */
  340.         b = cstate(right[v]);
  341.         if (cstate(left[v]) == 0 || b == 0) return (0);
  342.         else return (1);
  343.     }
  344. }
  345.  
  346.  
  347. member(symb, set, torf) {
  348.     register i, num, pos;
  349.     num = chars[set];
  350.     pos = set + 1;
  351.     for (i=0; i<num; i++)
  352.         if (symb == chars[pos++]) return (torf);
  353.     return (!torf);
  354. }
  355.  
  356. notin(n) {
  357.     register i, j, pos;
  358.     for (i=0; i<=n; i++) {
  359.         if (positions[state[i]] == count) {
  360.             pos = state[i] + 1;
  361.             for (j=0; j < count; j++)
  362.                 if (tmpstat[positions[pos++]] != 1) goto nxt;
  363.             xstate = i;
  364.             return (0);
  365.         }
  366.         nxt: ;
  367.     }
  368.     return (1);
  369. }
  370.  
  371. add(array, n) int *array; {
  372.     register i;
  373.     if (nxtpos + count > MAXPOS) overflo();
  374.     array[n] = nxtpos;
  375.     positions[nxtpos++] = count;
  376.     for (i=3; i <= line; i++) {
  377.         if (tmpstat[i] == 1) {
  378.             positions[nxtpos++] = i;
  379.         }
  380.     }
  381. }
  382.  
  383. follow(v) int v; {
  384.     int p;
  385.     if (v == line) return;
  386.     p = parent[v];
  387.     switch(name[p]) {
  388.         case STAR:
  389.         case PLUS:    cstate(v);
  390.                 follow(p);
  391.                 return;
  392.  
  393.         case OR:
  394.         case QUEST:    follow(p);
  395.                 return;
  396.  
  397.         case CAT:    if (v == left[p]) {
  398.                     if (cstate(right[p]) == 0) {
  399.                         follow(p);
  400.                         return;
  401.                     }
  402.                 }
  403.                 else follow(p);
  404.                 return;
  405.         case FINAL:    if (tmpstat[line] != 1) {
  406.                     tmpstat[line] = 1;
  407.                     count++;
  408.                 }
  409.                 return;
  410.     }
  411. }
  412.  
  413.  
  414. main(argc, argv)
  415. char **argv;
  416. {
  417.     while (--argc > 0 && (++argv)[0][0]=='-')
  418.         switch (argv[0][1]) {
  419.  
  420.         case 's':
  421.             sflag++;
  422.             continue;
  423.  
  424.         case 'h':
  425.             hflag = 0;
  426.             continue;
  427.  
  428.         case 'b':
  429.             bflag++;
  430.             continue;
  431.  
  432.         case 'c':
  433.             cflag++;
  434.             continue;
  435.  
  436.         case 'e':
  437.             argc--;
  438.             argv++;
  439.             goto out;
  440.  
  441.         case 'f':
  442.             fflag++;
  443.             continue;
  444.  
  445.         case 'l':
  446.             lflag++;
  447.             continue;
  448.  
  449.         case 'n':
  450.             nflag++;
  451.             continue;
  452.  
  453.         case 'v':
  454.             vflag++;
  455.             continue;
  456.  
  457.         default:
  458.             fprintf(stderr, "egrep: unknown flag\n");
  459.             continue;
  460.         }
  461. out:
  462.     if (argc<=0)
  463.         exit(2);
  464.     if (fflag) {
  465.         if (freopen(fname = *argv, "r", stdin) == NULL) {
  466.             fprintf(stderr, "egrep: can't open %s\n", fname);
  467.             exit(2);
  468.         }
  469.     }
  470.     else input = *argv;
  471.     argc--;
  472.     argv++;
  473.  
  474.     yyparse();
  475.  
  476.     cfoll(line-1);
  477.     cgotofn();
  478.     nfile = argc;
  479.     if (argc<=0) {
  480.         if (lflag) exit(1);
  481.         execute(0);
  482.     }
  483.     else while (--argc >= 0) {
  484.         execute(*argv);
  485.         argv++;
  486.     }
  487.     exit(nsucc == 0);
  488. }
  489.  
  490. execute(file)
  491. char *file;
  492. {
  493.     register char *p;
  494.     register cstat;
  495.     register ccount;
  496.     char buf[1024];
  497.     char *nlp;
  498.     int istat;
  499.     if (file) {
  500.         if ((f = open(file, 0)) < 0) {
  501.             fprintf(stderr, "egrep: can't open %s\n", file);
  502.             exit(2);
  503.         }
  504.     }
  505.     else f = 0;
  506.     ccount = 0;
  507.     lnum = 1;
  508.     tln = 0;
  509.     p = buf;
  510.     nlp = p;
  511.     if ((ccount = read(f,p,512))<=0) goto done;
  512.     blkno = ccount;
  513.     istat = cstat = gotofn[0]['\n'];
  514.     if (out[cstat]) goto found;
  515.     for (;;) {
  516.         cstat = gotofn[cstat][*p&0377];    /* all input chars made positive */
  517.         if (out[cstat]) {
  518.         found:    for(;;) {
  519.                 if (*p++ == '\n') {
  520.                     if (vflag == 0) {
  521.                 succeed:    nsucc = 1;
  522.                         if (cflag) tln++;
  523.                         else if (sflag)
  524.                             ;    /* ugh */
  525.                         else if (lflag) {
  526.                             printf("%s\n", file);
  527.                             close(f);
  528.                             return;
  529.                         }
  530.                         else {
  531.                             if (nfile > 1 && hflag) printf("%s:", file);
  532.                             if (bflag) printf("%ld:", (blkno-ccount-1)/512);
  533.                             if (nflag) printf("%ld:", lnum);
  534.                             if (p <= nlp) {
  535.                                 while (nlp < &buf[1024]) putchar(*nlp++);
  536.                                 nlp = buf;
  537.                             }
  538.                             while (nlp < p) putchar(*nlp++);
  539.                         }
  540.                     }
  541.                     lnum++;
  542.                     nlp = p;
  543.                     if ((out[(cstat=istat)]) == 0) goto brk2;
  544.                 }
  545.                 cfound:
  546.                 if (--ccount <= 0) {
  547.                     if (p <= &buf[512]) {
  548.                         if ((ccount = read(f, p, 512)) <= 0) goto done;
  549.                     }
  550.                     else if (p == &buf[1024]) {
  551.                         p = buf;
  552.                         if ((ccount = read(f, p, 512)) <= 0) goto done;
  553.                     }
  554.                     else {
  555.                         if ((ccount = read(f, p, &buf[1024]-p)) <= 0) goto done;
  556.                     }
  557.                     if(nlp>p && nlp<=p+ccount)
  558.                         nlp = p+ccount;
  559.                     blkno += ccount;
  560.                 }
  561.             }
  562.         }
  563.         if (*p++ == '\n') {
  564.             if (vflag) goto succeed;
  565.             else {
  566.                 lnum++;
  567.                 nlp = p;
  568.                 if (out[(cstat=istat)]) goto cfound;
  569.             }
  570.         }
  571.         brk2:
  572.         if (--ccount <= 0) {
  573.             if (p <= &buf[512]) {
  574.                 if ((ccount = read(f, p, 512)) <= 0) break;
  575.             }
  576.             else if (p == &buf[1024]) {
  577.                 p = buf;
  578.                 if ((ccount = read(f, p, 512)) <= 0) break;
  579.             }
  580.             else {
  581.                 if ((ccount = read(f, p, &buf[1024] - p)) <= 0) break;
  582.             }
  583.             if(nlp>p && nlp<=p+ccount)
  584.                 nlp = p+ccount;
  585.             blkno += ccount;
  586.         }
  587.     }
  588. done:    close(f);
  589.     if (cflag) {
  590.         if (nfile > 1)
  591.             printf("%s:", file);
  592.         printf("%ld\n", tln);
  593.     }
  594. }
  595.