home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / expr.zoo / expr.c next >
Encoding:
C/C++ Source or Header  |  1990-04-21  |  15.1 KB  |  769 lines
  1. /* file: expr.c
  2.  * author: Peter S. Housel 07/04/89,07/07/89,07/19/89,7/20/89,08/03/89,
  3.  *               08/26/89,04/21/90
  4.  */
  5. /*
  6.  * (more or less as posted to comp.os.minix, with slight cleanup by the author
  7.  * on the last date noted above)
  8.  */
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <ctype.h>
  12.  
  13. extern char *malloc(/* size_t nbytes */);
  14.  
  15. struct value
  16.  
  17. {
  18.     long    numval;            /* numeric value */
  19.     int    nf_valid;        /* "numeric value field valid" flag */
  20.     char    *strval;        /* string value */
  21.        };
  22.  
  23. #define    numresult(valp,number)             \
  24.         (((valp)->nf_valid = 1),     \
  25.          ((valp)->strval = NULL),    \
  26.          ((valp)->numval = (number)))
  27.  
  28. void invalid(/* char *err */);
  29. char *strvalue(/* struct value *valp */);
  30. int numvalue(/* struct value *valp */);
  31. char *strsave(/* char *string */);
  32. void expr1(/* struct value *valp */),
  33.      expr2(/* struct value *valp */),
  34.      expr3(/* struct value *valp */),
  35.      expr4(/* struct value *valp */),
  36.      expr5(/* struct value *valp */),
  37.      expr6(/* struct value *valp */),
  38.      expr7(/* struct value *valp */);
  39. void docolon(/* struct value *match, struct value *pattern */);
  40.  
  41. char *progname;
  42. char **argp;
  43. char NUMARG[] = "numeric argument required";
  44.  
  45. main(argc, argv)
  46. int argc; char *argv[];
  47. {
  48.  struct value val0;
  49.  
  50.  progname = argv[0];
  51.  
  52.  argp = &argv[1];
  53.  
  54.  expr1(&val0);
  55.  
  56.  if(*argp != NULL)
  57.     invalid("syntax error");
  58.  
  59.  (void) puts(strvalue(&val0));
  60.  
  61.  exit(nullz(&val0));
  62. }
  63.  
  64. /* Yet Another recursive descent parser.
  65.  */
  66. void expr1(valp)
  67. struct value *valp;
  68. {
  69.  struct value val1;
  70.  
  71.  expr2(valp);
  72.  
  73.  while(*argp != NULL)
  74.       {
  75.        if(strcmp(*argp, "|") == 0)
  76.      {
  77.       ++argp;
  78.       expr2(&val1);
  79.       if(nullz(valp))
  80.          *valp = val1;
  81.       else
  82.          ;            /* return the first arg (already in *valp) */
  83.      }
  84.        else
  85.       break;
  86.       }
  87. }
  88.  
  89. void expr2(valp)
  90. struct value *valp;
  91. {
  92.  struct value val1;
  93.  
  94.  expr3(valp);
  95.  
  96.  while(*argp != NULL)
  97.       {
  98.        if(strcmp(*argp, "&") == 0)
  99.      {
  100.       ++argp;
  101.       expr3(&val1);
  102.       if(nullz(valp) && nullz(&val1))
  103.          numresult(valp, 0);
  104.       else
  105.          ;            /* return the first arg (already in *valp) */
  106.      }
  107.        else
  108.       break;
  109.       }
  110. }
  111.  
  112. /* save source code lines but not object code, unfortunately.
  113.  */
  114.  
  115. #define RELOP(OP)                        \
  116.       ++argp;                        \
  117.       expr4(&val1);                        \
  118.       if(numvalue(valp) && numvalue(&val1))            \
  119.          numresult(valp, valp->numval OP val1.numval);    \
  120.       else                            \
  121.          numresult(valp, strcmp(strvalue(valp), strvalue(&val1)) OP 0);
  122.  
  123. void expr3(valp)
  124. struct value *valp;
  125. {
  126.  struct value val1;
  127.  
  128.  expr4(valp);
  129.  
  130.  while(*argp != NULL)
  131.       {
  132.        if(strcmp(*argp, "<") == 0)
  133.      {
  134.       RELOP( < )
  135.      }
  136.        else if(strcmp(*argp, "<=") == 0)
  137.      {
  138.       RELOP( <= )
  139.      }
  140.        else if(strcmp(*argp, "=") == 0)
  141.      {
  142.       RELOP( == )
  143.      }
  144.        else if(strcmp(*argp, "!=") == 0)
  145.      {
  146.       RELOP( != )
  147.      }
  148.        else if(strcmp(*argp, ">=") == 0)
  149.      {
  150.       RELOP( >= )
  151.      }
  152.        else if(strcmp(*argp, ">") == 0)
  153.      {
  154.       RELOP( > )
  155.      }
  156.        else
  157.       break;
  158.       }
  159. }
  160.  
  161. #define BINOP(NEXT,OP)                        \
  162.       ++argp;                        \
  163.       NEXT(&val1);                        \
  164.       if(!numvalue(valp) || !numvalue(&val1))        \
  165.          invalid(NUMARG);                    \
  166.       else                            \
  167.          numresult(valp, valp->numval OP val1.numval);    \
  168.  
  169. void expr4(valp)
  170. struct value *valp;
  171. {
  172.  struct value val1;
  173.  
  174.  expr5(valp);
  175.  
  176.  while(*argp != NULL)
  177.       {
  178.        if(strcmp(*argp, "+") == 0)
  179.      {
  180.       BINOP(expr5, + )
  181.      }
  182.        else if(strcmp(*argp, "-") == 0)
  183.      {
  184.       BINOP(expr5, - )
  185.      }
  186.        else
  187.       break;
  188.       }
  189. }
  190.  
  191. void expr5(valp)
  192. struct value *valp;
  193. {
  194.  struct value val1;
  195.  
  196.  expr6(valp);
  197.  
  198.  while(*argp != NULL)
  199.       {
  200.        if(strcmp(*argp, "*") == 0)
  201.      {
  202.       BINOP(expr6, * )
  203.      }
  204.        else if(strcmp(*argp, "/") == 0)
  205.      {
  206.       ++argp;
  207.       expr6(&val1);
  208.       if(!numvalue(valp) || !numvalue(&val1))
  209.          invalid(NUMARG);
  210.       else
  211.         {
  212.          if(val1.numval == 0)
  213.         invalid("division by zero");
  214.          numresult(valp, valp->numval / val1.numval);
  215.         }
  216.      }
  217.        else if(strcmp(*argp, "%") == 0)
  218.      {
  219.       ++argp;
  220.       expr6(&val1);
  221.       if(!numvalue(valp) || !numvalue(&val1))
  222.          invalid(NUMARG);
  223.       else
  224.         {
  225.          if(val1.numval == 0)
  226.         invalid("division by zero");
  227.          numresult(valp, valp->numval % val1.numval);
  228.         }
  229.      }
  230.        else
  231.       break;
  232.       }
  233. }
  234.  
  235. void expr6(valp)
  236. struct value *valp;
  237. {
  238.  struct value val1;
  239.  
  240.  expr7(valp);
  241.  
  242.  while(*argp != NULL)
  243.       {
  244.        if(strcmp(*argp, ":") == 0)
  245.      {
  246.       ++argp;
  247.       expr7(&val1);
  248. #ifndef NOCOLON
  249.       docolon(valp, &val1);
  250. #else
  251.       valp->nf_valid = 0;
  252.       valp->strval = NULL;
  253. #endif
  254.      }
  255.        else
  256.       break;
  257.       }
  258. }
  259.  
  260. void expr7(valp)
  261. struct value *valp;
  262. {
  263.  if(*argp == NULL)
  264.     invalid("missing argument(s)");
  265.  else if(strcmp(*argp, "(") == 0)
  266.    {
  267.     ++argp;
  268.     expr1(valp);
  269.     if(strcmp(*argp++, ")") != 0)
  270.        invalid("unbalanced parentheses");
  271.    }
  272.  else
  273.    {
  274.     valp->nf_valid = 0;
  275.     valp->strval = *argp++;
  276.    }
  277. }
  278.  
  279. /* return 1 if the argument is zero (numeric) or null (string
  280.  */
  281. int nullz(valp)
  282. struct value *valp;
  283. {
  284.  if(numvalue(valp))
  285.     return (valp->numval == 0);
  286.  
  287.  return (strlen(strvalue(valp)) == 0);
  288. }
  289.  
  290. /* return 1 if the argument is a valid number, insuring that the nf_valid
  291.  * and numval fields are set properly. Does the string-to-number
  292.  * conversion if nf_valid is false.
  293.  */
  294. int numvalue(valp)
  295. struct value *valp;
  296. {
  297.  register char *p;
  298.  int sign = 0, digits = 0;
  299.  unsigned long num = 0;
  300.  
  301.  if(valp->nf_valid)
  302.     return 1;
  303.  
  304.  if((p = valp->strval) == NULL)
  305.     return 0;
  306.  
  307.  if(*p == '-')
  308.    {
  309.     ++p;
  310.     sign = 1;
  311.    }
  312.  while(isdigit(*p))
  313.       {
  314.        num = num * 10 + (*p++ - '0');
  315.        digits = 1;
  316.       }
  317.  
  318.  if(!digits || *p != '\0')
  319.     return 0;
  320.  
  321.  valp->numval = sign ? -num : num;
  322.  valp->nf_valid = 1;
  323.  return 1;
  324. }
  325.  
  326. /* return the string value of the given argument. If there is only a
  327.  * numeric value, convert it to a string
  328.  */
  329. char *strvalue(valp)
  330. struct value *valp;
  331. {
  332.  char numbuf[30];
  333.  register char *p;
  334.  unsigned long num;
  335.  int sign = 0;
  336.  
  337.  if(valp->strval != NULL)
  338.     return valp->strval;        /* already a string */
  339.  else if(!valp->nf_valid)
  340.     return "";                /* NULL but not a number */
  341.  
  342.  p = numbuf + sizeof numbuf;
  343.  *--p = '\0';
  344.  
  345.  if(valp->numval < 0)
  346.    {
  347.     num = -(valp->numval);
  348.     sign = 1;
  349.    }
  350.  else
  351.     num = valp->numval;
  352.  
  353.  do
  354.    {
  355.     *--p = '0' + (num % 10);
  356.     num /= 10;
  357.    } while(num);
  358.  
  359.  if(sign)
  360.     *--p = '-';
  361.  
  362.  return (valp->strval = strsave(p));
  363. }
  364.  
  365. /* save the given string in its own allocated memory and return a pointer
  366.  * to that memory.
  367.  */
  368. char *strsave(string)
  369. char *string;
  370. {
  371.  char *p;
  372.  
  373.  if((p = malloc(strlen(string) + 1)) == NULL)
  374.     invalid("out of memory");
  375.  
  376.  (void) strcpy(p, string);
  377.  
  378.  return p;
  379. }
  380.  
  381. /* print error message and exit.
  382.  */
  383. void invalid(err)
  384. char *err;
  385. {
  386.  (void) fputs(progname, stderr);
  387.  (void) fputs(": ", stderr);
  388.  (void) fputs(err, stderr);
  389.  (void) putc('\n', stderr);
  390.  exit(2);
  391. }
  392.  
  393. #ifndef NOCOLON
  394.  
  395. #include <limits.h>
  396.  
  397. #define RMIN        (UCHAR_MAX-8)    /* >= reserved as opcodes */
  398. #define RESC        (UCHAR_MAX-8)    /* for escaping opcodes */
  399. #define RDOT        (UCHAR_MAX-7)    /* match any character */ 
  400. #define ROPEN        (UCHAR_MAX-6)    /* opening \( */
  401. #define RCLOSE        (UCHAR_MAX-5)    /* closing \) */
  402. #define RSTAR        (UCHAR_MAX-4)    /* Kleene closure */
  403. #define RCLASS        (UCHAR_MAX-3)    /* character class */
  404. #define RBACK        (UCHAR_MAX-2)    /* \digit reference */
  405. #define REND        (UCHAR_MAX-1)    /* end of program */
  406.  
  407. #define    RABEGIN        0x01        /* match anchored at BOL (^) */
  408. #define RAEND        0x02        /* match anchored at EOL ($) */
  409. #define RSELECT        0x04        /* \(...\) selection op used */
  410.  
  411. #define PROGLENGTH    1024        /* bytes reserved for r-programs */
  412.  
  413. #define    CLASS_BYTES    ((CHAR_MAX - CHAR_MIN) / CHAR_BIT)
  414.  
  415. unsigned char rprogram[PROGLENGTH];    /* regexp program storage */
  416. unsigned int rflags = RABEGIN;        /* regexp program context */
  417.  
  418. char *rbegins[10];            /* pointers to \( beginnings */
  419. char *rends[10];            /* pointers to \) endings */
  420. int rlevel;                /* \(...\) level */
  421.  
  422. void rcomp(/* char *regexp */);
  423. void rmatch(/* char *str */);
  424. char *rtry(/* char *str, unsigned char **pcp */);
  425. char *tryone(/* char *str, unsigned char **pcp */);
  426.  
  427. /* compile the regexp, match it against the string, and return the
  428.  * proper result (a string if \(...\) used, and the match length otherwise.
  429.  */
  430. void docolon(match, pattern)
  431. struct value *match, *pattern;
  432. {
  433.  rcomp(strvalue(pattern));
  434.  
  435.  rmatch(strvalue(match));
  436.  
  437.  if(rflags & RSELECT)
  438.    {
  439.     match->nf_valid = 0;
  440.     if(rends[0] == rbegins[0] || rends[1] == NULL)
  441.       {
  442.        match->strval = NULL;
  443.       }
  444.     else
  445.       {
  446.        *(rends[1]) = '\0';            /* semi-nasty */
  447.        match->strval = rbegins[1];
  448.       }
  449.    }
  450.  else
  451.    {
  452.     numresult(match, rends[0] - rbegins[0]);
  453.    }
  454. }
  455.  
  456. /* compile an ed(1)-syntax regular-expression into the rprogram[] array.
  457.  */
  458. void rcomp(regexp)
  459. register char *regexp;
  460. {
  461.  char c;            /* current regexp character */
  462.  char first, last;        /* limits of character class */
  463.  unsigned char *starable;    /* last "starable" variable */
  464.  unsigned char *rpc;        /* pointer to next program storage byte */
  465.  int negate;            /* character class negated */
  466.  int i;                /* loop counter and such */
  467.  int pstack[9];            /* \(...\) nesting stack */
  468.  int pstackp = 0;        /* stack pointer for nesting stack */
  469.  int pclosed[10];        /* flags indicating \(...\) closed */
  470.  
  471.  rpc = &rprogram[0];
  472.  starable = NULL;
  473.  
  474.  for(i = 1; i < 10; ++i)
  475.      pclosed[i] = 0;
  476.  
  477.  if(*regexp == '^')
  478.    {
  479.     rflags |= RABEGIN;            /* not needed, as it turns out */
  480.     ++regexp;
  481.    }
  482.  
  483.  while((c = *regexp++))
  484.       {
  485.        if((rpc - rprogram) >= PROGLENGTH - 2 - CLASS_BYTES)
  486.       invalid("regular expression program too long");
  487.  
  488.        switch(c)
  489.          {
  490.           case '.':
  491.             starable = rpc;
  492.             *rpc++ = RDOT;
  493.             break;
  494.           case '\\':
  495.             if(isdigit(*regexp))
  496.               {
  497.                if(!pclosed[*regexp - '0'])
  498.                   invalid("reference to unclosed/nonexistent \\(...\\) pair");
  499.                starable = NULL;
  500.                *rpc++ = RBACK;
  501.                *rpc++ = *regexp++ - '0';
  502.               }
  503.             else if(*regexp == '(')
  504.               {
  505.                starable = NULL;
  506.                ++regexp;
  507.                rflags |= RSELECT;
  508.                if((i = ++rlevel) > 9)
  509.                   invalid("too many \\(...\\) levels");
  510.                pstack[pstackp++] = i;
  511.                *rpc++ = ROPEN;
  512.                *rpc++ = i;
  513.                break;
  514.               }
  515.             else if(*regexp == ')')
  516.               {
  517.                starable = NULL;
  518.                ++regexp;
  519.                if(pstackp == 0)
  520.                   invalid("\\(...\\) pairs don't balance");
  521.                i = pstack[--pstackp];
  522.                *rpc++ = RCLOSE;
  523.                *rpc++ = i;
  524.                pclosed[i] = 1;
  525.                break;
  526.               }
  527.             else if((unsigned char) *regexp >= RMIN)
  528.               {
  529.                starable = rpc;
  530.                *rpc++ = RESC;
  531.                *rpc++ = *regexp++;
  532.                break;
  533.               }
  534.             else
  535.               {
  536.                starable = rpc;
  537.                *rpc++ = *regexp++;
  538.                break;
  539.               }
  540.           case '$':
  541.             if(*regexp == '\0')
  542.               {
  543.                rflags |= RAEND;
  544.                break;
  545.               }
  546.             else
  547.               {
  548.                starable = rpc;
  549.                *rpc++ = '$';
  550.                break;
  551.               }
  552.           case '*':
  553.             if(starable == NULL)
  554.               {
  555.                starable = rpc;
  556.                *rpc++ = '*';
  557.                break;
  558.               }
  559.             else
  560.               {
  561.                (void) memmove(starable + 1, starable,
  562.                       rpc - starable);
  563.                *starable = RSTAR;
  564.                starable = NULL;
  565.                ++rpc;
  566.                break;
  567.               }
  568.           case '[':
  569.             negate = 0;
  570.             starable = rpc;
  571.             *rpc++ = RCLASS;
  572.             if(*regexp == '^')
  573.               {
  574.                ++regexp;
  575.                negate = 1;
  576.               }
  577.             for(i = 0; i < CLASS_BYTES; ++i)
  578.                 rpc[i] = 0;
  579.             do
  580.               {
  581.                first = *regexp++;
  582.                if(*regexp == '-' && regexp[1] != ']'
  583.                   && regexp[1] > first)
  584.                  {
  585.                   ++regexp;
  586.                   last = *regexp++;
  587.                   for(i = first; i < last; ++i)
  588.                  {
  589.                   rpc[(i - CHAR_MIN) / CHAR_BIT] |=
  590.                     1 << ((i - CHAR_MIN) % CHAR_BIT);
  591.                  }
  592.                  }
  593.                else
  594.                  {
  595.                    rpc[(first - CHAR_MIN) / CHAR_BIT] |=
  596.                  1 << ((first - CHAR_MIN) % CHAR_BIT);
  597.                  }
  598.               } while (*regexp && *regexp != ']');
  599.             if(*regexp != ']')
  600.                invalid("unterminated character class");
  601.             ++regexp;
  602.             if(negate)
  603.                for(i = 0; i < CLASS_BYTES; ++i, ++rpc)
  604.                    *rpc = ~*rpc;
  605.             else
  606.                rpc += CLASS_BYTES;
  607.             break;
  608.           default:
  609.             if((unsigned char) c >= RMIN)
  610.               {
  611.                starable = rpc;
  612.                *rpc++ = RESC;
  613.                *rpc++ = c;
  614.                break;
  615.               }
  616.             else
  617.               {
  618.                starable = rpc;
  619.                *rpc++ = c;
  620.                break;
  621.               }
  622.          }
  623.       }
  624.  if(pstackp != 0)
  625.     invalid("\\(...\\) pairs don't balance");
  626.  *rpc = REND;
  627. }
  628.  
  629. /* It turns out that expr regular expressions have an implicit
  630.  * '^' prepended, and therefore RABEGIN is always on. It seemed
  631.  * a waste to delete the code after discovering this, however.
  632.  */
  633. void rmatch(str)
  634. char *str;
  635. {
  636.  char *end;
  637.  unsigned char *rpc;
  638.  int i;
  639.  
  640.  rends[0] = rbegins[0] = str;
  641.  for(i = 1; i < 10; ++i)
  642.      rends[i] = rbegins[i] = NULL;
  643.  
  644.  if(rflags & RABEGIN)
  645.    {
  646.     rpc = &rprogram[0];
  647.     if((end = rtry(str, &rpc)) != NULL)
  648.        rends[0] = end;
  649.    }
  650.  else
  651.    {
  652.     while(*str)
  653.          {
  654.       rpc = &rprogram[0];
  655.       end = rtry(str, &rpc);
  656.       if(end != NULL && (end - str) > (rends[0] - rbegins[0]))
  657.         {
  658.          rbegins[0] = str;        /* longest match wins */
  659.          rends[0] = end;
  660.         }
  661.       ++str;
  662.      }
  663.    }
  664.       
  665. }
  666.  
  667. /* try to match str to program from *pcp on
  668. */
  669. char *rtry(str, pcp)
  670. char *str;
  671. unsigned char **pcp;
  672. {
  673.  char *nstr;
  674.  
  675.  while(*str && **pcp != REND)
  676.       {
  677.        if((nstr = tryone(str, pcp)) == NULL)
  678.       return NULL;
  679.        str = nstr;
  680.       }
  681.  
  682.  while(**pcp == RCLOSE)
  683.       {
  684.        rends[*(*pcp + 1)] = str;
  685.        *pcp += 2;
  686.       }
  687.  
  688.  if(**pcp != REND)
  689.     return NULL;
  690.  
  691.  if((rflags & RAEND) && *str != '\0')
  692.     return NULL;
  693.  
  694.  return str;
  695. }
  696.  
  697. /* try to match one regular expression operator
  698.  */
  699. char *tryone(str, pcp)
  700. char *str;
  701. unsigned char **pcp;
  702. {
  703.  char *ret = NULL;
  704.  unsigned char *npc;
  705.  char *p, *q;
  706.  
  707. again:
  708.  switch(**pcp)
  709.        {
  710.     case RESC:
  711.             if(*str == *(*pcp + 1))
  712.                ret = str + 1;
  713.             *pcp += 2;
  714.             break;
  715.         default:
  716.             if(*str == **pcp)
  717.                ret = str + 1;
  718.             *pcp += 1;
  719.             break;
  720.     case RDOT:
  721.             if(*str != '\0')
  722.                ret = str + 1;
  723.             *pcp += 1;
  724.             break;
  725.         case RCLASS:
  726.             if(*str != '\0'
  727.                && ((*pcp + 1)[(*str - CHAR_MIN) / CHAR_BIT]
  728.                    & (1 << ((*str - CHAR_MIN) % CHAR_BIT))))
  729.               {
  730.                ret = str + 1;
  731.               }
  732.             *pcp += CLASS_BYTES + 1;
  733.             break;
  734.         case ROPEN:
  735.             rbegins[*(*pcp + 1)] = str;
  736.             *pcp += 2;
  737.             goto again;
  738.         case RCLOSE:
  739.             rends[*(*pcp + 1)] = str;
  740.             *pcp += 2;
  741.             goto again;
  742.         case RBACK:
  743.             p = rbegins[*(*pcp + 1)];
  744.             q = rends[*(*pcp + 1)];
  745.             *pcp += 2;
  746.             while(p < q)
  747.                   if(*p++ != *str++)
  748.                  return NULL;
  749.             ret = str;
  750.             break;
  751.         case RSTAR:
  752.             *pcp += 1;
  753.             p = str;
  754.             while(npc = *pcp, tryone(p, &npc) != NULL)
  755.                   ++p;
  756.             *pcp = npc;
  757.             while(p >= str
  758.                   && (npc = *pcp, (ret = rtry(p, &npc)) == NULL))
  759.                   --p;
  760.             *pcp = npc;
  761.             break;
  762.         case REND:
  763.             ret = str;
  764.        }
  765.  
  766.  return ret;
  767. }
  768. #endif /* !NOCOLON */
  769.