home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / awk / awk320sr.zip / AWKPAT.C < prev    next >
C/C++ Source or Header  |  1991-04-25  |  10KB  |  495 lines

  1. /*
  2.  * Awk regular expression compiler/interpreter
  3.  *
  4.  * Copyright (C) 1988, 1989, 1990, 1991 by Rob Duff
  5.  * All rights reserved
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <mem.h>
  11.  
  12. extern void kbhit(void);
  13.  
  14. #include "awkfstr.h"
  15. #include "awk.h"
  16.  
  17. static char *patptr;
  18.  
  19. extern int yynext(void);
  20. extern void yyerror(char*);
  21. extern void *yyalloc(unsigned);
  22.  
  23. int re_next(void);
  24. int re_term(int);
  25. int re_sequence(int);
  26. int re_factor(char*, int);
  27. int re_expression(char*, int);
  28. int re_class(void);
  29. int re_mapc(void);
  30. int re_next(void);
  31.  
  32. void re_back(int);
  33.  
  34. void moveup(char*, int);
  35. int classed(char*, int);
  36.  
  37. char *fstrnsub(char*, FSTR, FSTR, int);
  38.  
  39. #define reljmp(r) ((r) + (*((unsigned short*)(r))) + sizeof(short))
  40.  
  41. static FSTR pmatch(FSTR, char*);
  42. static FSTR star(FSTR, char*, char*);
  43.  
  44. FSTR    bol;
  45. char    eor;
  46. short   rechar;
  47.  
  48. short   rstart;
  49. short   rcount;
  50. short   rlength;
  51.  
  52. static unsigned char cclass[32];
  53.  
  54. /*
  55.  * Compile a regular expression
  56.  */
  57. char *regexp(int copy)
  58. {
  59.     int     c;
  60.     char    *lp;
  61.  
  62.     if (copy==1)
  63.         eor = '/';
  64.     else
  65.         eor = '\0';
  66.     rechar = EOF;
  67.     patptr = buffer;
  68.     c = re_expression(patptr, re_next());
  69.     *patptr++ = R_END;
  70.     if (copy > 0) {
  71.         if (copy == 1 && c != '/')
  72.             yyerror("syntax error");
  73.         c = (int)(patptr - buffer);
  74.         lp = yyalloc(c);
  75.         memcpy(lp, buffer, c);
  76.         return lp;
  77.     }
  78.     else {
  79.         return buffer;
  80.     }
  81. }
  82.  
  83. static int re_expression(char *lp, int c)
  84. {
  85.     c = re_sequence(c);
  86.     if (c == '|') {
  87.         *patptr++ = R_END;
  88.         moveup(lp, R_END);
  89.         c = re_expression(patptr, re_next());
  90.         *patptr++ = R_END;
  91.         moveup(lp, R_BAR);
  92.     }
  93.     return(c);
  94. }
  95.  
  96. static int re_sequence(int c)
  97. {
  98.     if (c == '^') {
  99.         *patptr++ = R_BOL;
  100.         c = re_next();
  101.     }
  102.     while (c != '|' && c != ')' && c != '$' && c != eor  && c != EOF)
  103.         c = re_factor(patptr, c);
  104.     if (c == '$') {
  105.         *patptr++ = R_EOL;
  106.         c = re_next();
  107.     }
  108.     return c;
  109. }
  110.  
  111. static int re_factor(char *lp, int c)
  112. {
  113.     c = re_term(c);
  114.     switch(c) {
  115.     case '*': c = R_STAR; break;
  116.     case '+': c = R_PLUS; break;
  117.     case '?': c = R_QUEST; break;
  118.     default: return(c);
  119.     }
  120.     *patptr++ = R_END;
  121.     moveup(lp, c);
  122.     c = re_next();
  123.     return(c);
  124. }
  125.  
  126. static int re_term(int c)
  127. {
  128.     if (c == eor)
  129.         return c;
  130.     switch(c) {
  131.     case EOF:
  132.     case '*':
  133.     case '+':
  134.     case '?':
  135.     case '|':
  136.     case '^':   return (EOF);
  137.     case ')':
  138.     case '$':   return (c);
  139.     case '.':   *patptr++ = R_ANY; break;
  140.     case '[':   return re_class();
  141.     case '(':
  142.         c = re_expression(patptr, re_next());
  143.         if (c != ')')
  144.             return (EOF);
  145.         break;
  146.     case '\n':
  147.         if (eor == '/')
  148.             return (EOF);
  149.         *patptr++ = R_CHAR;
  150.         *patptr++ = '\n';
  151.         break;
  152.     case '/':
  153.         if (eor == '/')
  154.             return ('/');
  155.         *patptr++ = '/';
  156.         break;
  157.     case '\\':
  158.         c = re_mapc();
  159.     default:
  160.         if (c < ' ' /* ASCII */)
  161.             *patptr++ = R_CHAR;
  162.         *patptr++ = c;
  163.     }
  164.     return re_next();
  165. }
  166.  
  167. /*
  168.  * Compile a character class
  169.  */
  170. static int re_class()
  171. {
  172.     int     c, i, o;
  173.  
  174.     if ( (c = re_next()) == EOF )
  175.         return (EOF);
  176.     for (i = 0; i < 32; i++)
  177.         cclass[i] = 0;
  178.     if ( c == '^') {
  179.         o = R_NCLAS;
  180.         c = re_next();
  181.     }
  182.     else
  183.         o = R_CLASS;
  184.  
  185.     if (c == ']') {
  186.         cclass[c >> 3] |= 1 << (c & 7);
  187.         c = re_next();
  188.     }
  189.     while (c != ']') {
  190.         if (c == EOF || c == '\n')
  191.             return EOF;
  192.         if (c == '\\')
  193.             c = re_mapc();
  194.         i = re_next();
  195.         if (i == '-') {
  196.             i = re_next();
  197.             if (i == '\n' || i == EOF)
  198.                 return EOF;
  199.             if (i == ']') {
  200.                 cclass[c >> 3] |= 1 << (c & 7);
  201.                 cclass['-' >> 3] |= 1 << ('-' & 7);
  202.             }
  203.             else {
  204.                 if (i == '\\')
  205.                     i = re_mapc();
  206.                 if (i <= c)
  207.                     return (EOF);
  208.                 while (c <= i) {
  209.                     cclass[c >> 3] |= 1 << (c & 7);
  210.                     c++;
  211.                 }
  212.                 i = re_next();
  213.             }
  214.         }
  215.         else
  216.             cclass[c >> 3] |= 1 << (c & 7);
  217.         c = i;
  218.     }
  219.     if (o == R_NCLAS)
  220.         cclass[0] |= 0x1;
  221.     else
  222.         cclass[0] &= 0xFE;
  223.     *patptr++ = o;
  224.     for (i = 0; i < 32; i++)
  225.         *patptr++ = cclass[i];
  226.     return re_next();
  227. }
  228.  
  229. void moveup(char *lp, int op)
  230. {
  231.     register char *sp;
  232.     int     i;
  233.     TRIX    trix;
  234.  
  235.     sp = patptr;
  236.     while (sp >= lp) {
  237.         sp[3] = sp[0];
  238.         sp--;
  239.     }
  240.     trix.ival = patptr - lp;
  241.     *lp++ = op;
  242.     patptr += 3;
  243.     for (i = 0; i < sizeof(short); i++)
  244.         *lp++ = trix.sval[i];
  245. }
  246.  
  247. static int re_mapc()
  248. {
  249.     int     c, n, octv;
  250.  
  251.     c = re_next();
  252.     switch (c) {
  253.     case '\n':
  254.         return(R_EOL);
  255.     case 'b':
  256.         return('\b');
  257.     case 'f':
  258.         return('\f');
  259.     case 'n':
  260.         return('\n');
  261.     case 'r':
  262.         return('\r');
  263.     case 't':
  264.         return('\t');
  265.     case '0':
  266.     case '1':
  267.     case '2':
  268.     case '3':
  269.     case '4':
  270.     case '5':
  271.     case '6':
  272.     case '7':
  273.         octv = c - '0';
  274.         for (n = 1; (c = re_next()) >= '0' && c<='7' && n <= 3; n++)
  275.             octv = octv * 010 + c - '0';
  276.         re_back(c);
  277.         return(octv);
  278.     case '\"':
  279.     case '\'':
  280.     default:
  281.         return(c);
  282.     }
  283. }
  284.  
  285. static int re_next()
  286. {
  287.     int     c;
  288.  
  289. renext:
  290.     if (rechar == EOF)
  291.         c = yynext();
  292.     else {
  293.         c = rechar;
  294.         rechar = EOF;
  295.     }
  296.  
  297.     if (c == '\\' && eor == '/') {
  298.         c = yynext();
  299.         if (c == '\n')
  300.             goto renext;
  301.         rechar = c;
  302.         c = '\\';
  303.     }
  304.     return c;
  305.  
  306. static void re_back(int c)
  307. {
  308.     rechar = c;
  309. }
  310.  
  311. void match(FSTR lp, char *pp)
  312. {
  313.     FSTR    mp;
  314.  
  315.     lp++;
  316.     bol = lp;
  317.     rstart = 0;
  318.     rlength = 0;
  319.     for(;;) {
  320.         if ((mp = pmatch(lp, pp)) != NULL) {
  321.             rstart = lp - bol + 1;
  322.             rlength = mp - lp;
  323.             return;
  324.         }
  325.         if (*lp == '\0')
  326.             break;
  327.         lp++;
  328.     }
  329. }
  330.  
  331. FSTR matchp(FSTR bp, FSTR lp, char *pp)
  332. {
  333.     bol = bp;
  334.     lp = pmatch(lp, pp);
  335.     return lp;
  336. }
  337.  
  338. char *fstrnsub(char *dp, FSTR rp, FSTR sp, int n)
  339. {
  340.     int     m;
  341.     char    *tp;
  342.  
  343.     tp = dp;
  344.     dp = (void*)fstrchr(dp, '\0');
  345.     while (*rp != '\0') {
  346.         if (rp[0] == '\\' && rp[1] == '&') {
  347.             rp++;
  348.             *dp++ = *rp++;
  349.         }
  350.         else if (*rp == '&') {
  351.             for (m = 0; m < n; m++)
  352.                 *dp++ = sp[m];
  353.             rp++;
  354.         }
  355.         else
  356.             *dp++ = *rp++;
  357.     }
  358.     *dp = '\0';
  359.     return tp;
  360. }
  361.  
  362. char *subst(int global, FSTR rp, FSTR lp, char *pp)
  363. {
  364.     char    *dp;
  365.     FSTR    mp;
  366.     FSTR    sp;
  367.  
  368.     lp++;
  369.     rp++;
  370.     sp = lp;
  371.     bol = lp;
  372.     rcount = 0;
  373.     dp = code;
  374.     *dp++ = ZSTR;
  375.     *dp = '\0';
  376.     while (*lp != '\0') {
  377.         if ((mp = pmatch(lp, pp)) != NULL) {
  378.             rcount++;
  379.             if (sp != lp)
  380.                 fstrncat(dp, sp, (int)(lp - sp));
  381.             fstrnsub(dp, rp, lp, (int)(mp - lp));
  382.             sp = lp = mp;
  383.             if (global == 0)
  384.                 break;
  385.             else {
  386.                 if (global > 100) {
  387.                     global = 1;
  388.                     kbhit();
  389.                 }
  390.                 else
  391.                     global++;
  392.                 continue;
  393.             }
  394.         }
  395.         lp++;
  396.     }
  397.     fstrcat(dp, sp);
  398.     return code;
  399. }
  400.  
  401. static FSTR pmatch(FSTR lp, char *pp)
  402. {
  403.     int     op;
  404.     FSTR    sp;
  405.     FSTR    ep;
  406.  
  407.     while ((op = *pp) != R_END) {
  408.         pp++;
  409.         switch(op) {
  410.         case R_BOL:
  411.             if (lp != bol)
  412.                 return NULL;
  413.             break;
  414.         case R_EOL:
  415.             if (*lp != '\0')
  416.                 return NULL;
  417.             break;
  418.         case R_ANY:
  419.             if (*lp++ == '\0')
  420.                 return NULL;
  421.             break;
  422.         case R_CHAR:
  423.             if (*lp++ != *pp++)
  424.                 return NULL;
  425.             break;
  426.         case R_CLASS:
  427.             if (classed(pp, *lp++) == 0)
  428.                 return NULL;
  429.             pp += 32;
  430.             break;
  431.         case R_NCLAS:
  432.             if (classed(pp, *lp++) != 0)
  433.                 return NULL;
  434.             pp += 32;
  435.             break;
  436.         case R_BAR:
  437.             ep = pmatch(lp, pp + 5);
  438.             sp = pmatch(lp, reljmp(pp + 3));
  439.             if (ep != NULL) {
  440.                 if (sp != NULL && sp > ep)
  441.                     lp = sp;
  442.                 else
  443.                     lp = ep;
  444.                 pp = reljmp(pp);
  445.                 break;
  446.             }
  447.             else if (sp != NULL) {
  448.                 lp = sp;
  449.                 pp = reljmp(pp);
  450.                 break;
  451.             }
  452.             return NULL;
  453.         case R_QUEST:
  454.             ep = pmatch(lp, pp + 2);
  455.             pp = reljmp(pp);
  456.             if (ep)
  457.                 lp = ep;
  458.             break;
  459.         case R_PLUS:
  460.             if ((lp = pmatch(lp, pp + 2)) == 0)
  461.                 return NULL;
  462.         case R_STAR:
  463.             if ((ep = star(lp, pp + 2, reljmp(pp))) != 0)
  464.                 return ep;
  465.             pp = reljmp(pp);
  466.             break;
  467.         default:
  468.             if ( *lp++ != op)
  469.                 return NULL;
  470.         }
  471.     }
  472.     return lp;
  473. }
  474.  
  475. static FSTR star(FSTR lp, char *pp, char *qq)
  476. {
  477.     FSTR    ep;
  478.     FSTR    fp;
  479.  
  480.     if ((ep = pmatch(lp, pp)) != NULL)
  481.         if ((fp = star(ep, pp, qq)) != NULL)
  482.             return fp;
  483.         else
  484.             return pmatch(ep, qq);
  485.     else
  486.         return pmatch(lp, qq);
  487. }
  488.  
  489. static int classed(char *cc, int ch)
  490. {
  491.     return (cc[(ch>>3)&037]&(1<<(ch&07)));
  492. }
  493.  
  494.