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.  
  307. static void re_back(int c)
  308. {
  309.     rechar = c;
  310. }
  311.  
  312. void match(FSTR lp, char *pp)
  313. {
  314.     FSTR    mp;
  315.  
  316.     lp++;
  317.     bol = lp;
  318.     rstart = 0;
  319.     rlength = 0;
  320.     for(;;) {
  321.         if ((mp = pmatch(lp, pp)) != NULL) {
  322.             rstart = lp - bol + 1;
  323.             rlength = mp - lp;
  324.             return;
  325.         }
  326.         if (*lp == '\0')
  327.             break;
  328.         lp++;
  329.     }
  330. }
  331.  
  332. FSTR matchp(FSTR bp, FSTR lp, char *pp)
  333. {
  334.     bol = bp;
  335.     lp = pmatch(lp, pp);
  336.     return lp;
  337. }
  338.  
  339. char *fstrnsub(char *dp, FSTR rp, FSTR sp, int n)
  340. {
  341.     int     m;
  342.     char    *tp;
  343.  
  344.     tp = dp;
  345.     dp = (void*)fstrchr(dp, '\0');
  346.     while (*rp != '\0') {
  347.         if (rp[0] == '\\' && rp[1] == '&') {
  348.             rp++;
  349.             *dp++ = *rp++;
  350.         }
  351.         else if (*rp == '&') {
  352.             for (m = 0; m < n; m++)
  353.                 *dp++ = sp[m];
  354.             rp++;
  355.         }
  356.         else
  357.             *dp++ = *rp++;
  358.     }
  359.     *dp = '\0';
  360.     return tp;
  361. }
  362.  
  363. char *subst(int global, FSTR rp, FSTR lp, char *pp)
  364. {
  365.     char    *dp;
  366.     FSTR    mp;
  367.     FSTR    sp;
  368.  
  369.     lp++;
  370.     rp++;
  371.     sp = lp;
  372.     bol = lp;
  373.     rcount = 0;
  374.     dp = code;
  375.     *dp++ = ZSTR;
  376.     *dp = '\0';
  377.     while (*lp != '\0') {
  378.         if ((mp = pmatch(lp, pp)) != NULL) {
  379.             rcount++;
  380.             if (sp != lp)
  381.                 fstrncat(dp, sp, (int)(lp - sp));
  382.             fstrnsub(dp, rp, lp, (int)(mp - lp));
  383.             sp = lp = mp;
  384.             if (global == 0)
  385.                 break;
  386.             else {
  387.                 if (global > 100) {
  388.                     global = 1;
  389.                     kbhit();
  390.                 }
  391.                 else
  392.                     global++;
  393.                 continue;
  394.             }
  395.         }
  396.         lp++;
  397.     }
  398.     fstrcat(dp, sp);
  399.     return code;
  400. }
  401.  
  402. static FSTR pmatch(FSTR lp, char *pp)
  403. {
  404.     int     op;
  405.     FSTR    sp;
  406.     FSTR    ep;
  407.  
  408.     while ((op = *pp) != R_END) {
  409.         pp++;
  410.         switch(op) {
  411.         case R_BOL:
  412.             if (lp != bol)
  413.                 return NULL;
  414.             break;
  415.         case R_EOL:
  416.             if (*lp != '\0')
  417.                 return NULL;
  418.             break;
  419.         case R_ANY:
  420.             if (*lp++ == '\0')
  421.                 return NULL;
  422.             break;
  423.         case R_CHAR:
  424.             if (*lp++ != *pp++)
  425.                 return NULL;
  426.             break;
  427.         case R_CLASS:
  428.             if (classed(pp, *lp++) == 0)
  429.                 return NULL;
  430.             pp += 32;
  431.             break;
  432.         case R_NCLAS:
  433.             if (classed(pp, *lp++) != 0)
  434.                 return NULL;
  435.             pp += 32;
  436.             break;
  437.         case R_BAR:
  438.             ep = pmatch(lp, pp + 5);
  439.             sp = pmatch(lp, reljmp(pp + 3));
  440.             if (ep != NULL) {
  441.                 if (sp != NULL && sp > ep)
  442.                     lp = sp;
  443.                 else
  444.                     lp = ep;
  445.                 pp = reljmp(pp);
  446.                 break;
  447.             }
  448.             else if (sp != NULL) {
  449.                 lp = sp;
  450.                 pp = reljmp(pp);
  451.                 break;
  452.             }
  453.             return NULL;
  454.         case R_QUEST:
  455.             ep = pmatch(lp, pp + 2);
  456.             pp = reljmp(pp);
  457.             if (ep)
  458.                 lp = ep;
  459.             break;
  460.         case R_PLUS:
  461.             if ((lp = pmatch(lp, pp + 2)) == 0)
  462.                 return NULL;
  463.         case R_STAR:
  464.             if ((ep = star(lp, pp + 2, reljmp(pp))) != 0)
  465.                 return ep;
  466.             pp = reljmp(pp);
  467.             break;
  468.         default:
  469.             if ( *lp++ != op)
  470.                 return NULL;
  471.         }
  472.     }
  473.     return lp;
  474. }
  475.  
  476. static FSTR star(FSTR lp, char *pp, char *qq)
  477. {
  478.     FSTR    ep;
  479.     FSTR    fp;
  480.  
  481.     if ((ep = pmatch(lp, pp)) != NULL)
  482.         if ((fp = star(ep, pp, qq)) != NULL)
  483.             return fp;
  484.         else
  485.             return pmatch(ep, qq);
  486.     else
  487.         return pmatch(lp, qq);
  488. }
  489.  
  490. static int classed(char *cc, int ch)
  491. {
  492.     return (cc[(ch>>3)&037]&(1<<(ch&07)));
  493. }
  494.  
  495.