expr.c

操作系统源代码

/* expr  - expression evaluator for shell	Author: Peter S. Housel */

#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>

struct value {
  long numval;			/* numeric value */
  int nf_valid;			/* "numeric value field valid" flag */
  char *strval;			/* string value */
};

#define	numresult(valp,number) 			\
	(((valp)->nf_valid = 1), 		\
	 ((valp)->strval = NULL),		\
	 ((valp)->numval = (number)))

_PROTOTYPE(int main, (int argc, char **argv));
_PROTOTYPE(void expr1, (struct value *valp));
_PROTOTYPE(void expr2, (struct value *valp));
_PROTOTYPE(void expr3, (struct value *valp));
_PROTOTYPE(void expr4, (struct value *valp));
_PROTOTYPE(void expr5, (struct value *valp));
_PROTOTYPE(void expr6, (struct value *valp));
_PROTOTYPE(void expr7, (struct value *valp));
_PROTOTYPE(int nullz, (struct value *valp));
_PROTOTYPE(int numvalue, (struct value *valp));
_PROTOTYPE(char *strvalue, (struct value *valp));
_PROTOTYPE(char *strsave, (char *string));
_PROTOTYPE(void invalid, (char *err));
_PROTOTYPE(void docolon, (struct value *match, struct value *pattern));
_PROTOTYPE(void rcomp, (char *regexp));
_PROTOTYPE(void rmatch, (char *str));
_PROTOTYPE(char *rtry, (char *str, unsigned char **pcp));
_PROTOTYPE(char *tryone, (char *str, unsigned char **pcp));

char *progname;
char **argp;
char NUMARG[] = "numeric argument required";

int main(argc, argv)
int argc;
char *argv[];
{
  struct value val0;

  progname = argv[0];
  argp = &argv[1];
  expr1(&val0);
  if (*argp != NULL) invalid("syntax error");
  (void) puts(strvalue(&val0));
  return(nullz(&val0));
}

/* Yet Another recursive descent parser. */
void expr1(valp)
struct value *valp;
{
  struct value val1;

  expr2(valp);

  while (*argp != NULL) {
	if (strcmp(*argp, "|") == 0) {
		++argp;
		expr2(&val1);
		if (nullz(valp))
			*valp = val1;
		else;		/* return the first arg (already in *valp) */
	} else
		break;
  }
}

void expr2(valp)
struct value *valp;
{
  struct value val1;

  expr3(valp);

  while (*argp != NULL) {
	if (strcmp(*argp, "&") == 0) {
		++argp;
		expr3(&val1);
		if (nullz(valp) && nullz(&val1))
			numresult(valp, 0);
		else;		/* return the first arg (already in *valp) */
	} else
		break;
  }
}

/* Save source code lines but not object code, unfortunately. */

#define RELOP(OP)						\
    ++argp;						\
    expr4(&val1);						\
    if(numvalue(valp) && numvalue(&val1))			\
       numresult(valp, valp->numval OP val1.numval);	\
    else							\
       numresult(valp, strcmp(strvalue(valp), strvalue(&val1)) OP 0);

void expr3(valp)
struct value *valp;
{
  struct value val1;

  expr4(valp);

  while (*argp != NULL) {
	if (strcmp(*argp, "<") == 0) {
		RELOP(<)
	} else if (strcmp(*argp, "<=") == 0) {
		RELOP(<=)
	} else if (strcmp(*argp, "=") == 0) {
		RELOP(==)
	} else if (strcmp(*argp, "!=") == 0) {
		RELOP(!=)
	} else if (strcmp(*argp, ">=") == 0) {
		RELOP(>=)
	} else if (strcmp(*argp, ">") == 0) {
		RELOP(>)
	} else
		break;
  }
}

#define BINOP(NEXT,OP)						\
    ++argp;						\
    NEXT(&val1);						\
    if(!numvalue(valp) || !numvalue(&val1))		\
       invalid(NUMARG);					\
    else							\
       numresult(valp, valp->numval OP val1.numval);	\

void expr4(valp)
struct value *valp;
{
  struct value val1;

  expr5(valp);

  while (*argp != NULL) {
	if (strcmp(*argp, "+") == 0) {
		BINOP(expr5, +)
	} else if (strcmp(*argp, "-") == 0) {
		BINOP(expr5, -)
	} else
		break;
  }
}

void expr5(valp)
struct value *valp;
{
  struct value val1;

  expr6(valp);

  while (*argp != NULL) {
	if (strcmp(*argp, "*") == 0) {
		BINOP(expr6, *)
	} else if (strcmp(*argp, "/") == 0) {
		++argp;
		expr6(&val1);
		if (!numvalue(valp) || !numvalue(&val1))
			invalid(NUMARG);
		else {
			if (val1.numval == 0) invalid("division by zero");
			numresult(valp, valp->numval / val1.numval);
		}
	} else if (strcmp(*argp, "%") == 0) {
		++argp;
		expr6(&val1);
		if (!numvalue(valp) || !numvalue(&val1))
			invalid(NUMARG);
		else {
			if (val1.numval == 0) invalid("division by zero");
			numresult(valp, valp->numval % val1.numval);
		}
	} else
		break;
  }
}

void expr6(valp)
struct value *valp;
{
  struct value val1;

  expr7(valp);

  while (*argp != NULL) {
	if (strcmp(*argp, ":") == 0) {
		++argp;
		expr7(&val1);
#ifndef NOCOLON
		docolon(valp, &val1);
#else
		valp->nf_valid = 0;
		valp->strval = NULL;
#endif
	} else
		break;
  }
}

void expr7(valp)
struct value *valp;
{
  if (*argp == NULL)
	invalid("missing argument(s)");
  else if (strcmp(*argp, "(") == 0) {
	++argp;
	expr1(valp);
	if (strcmp(*argp++, ")") != 0) invalid("unbalanced parentheses");
  } else {
	valp->nf_valid = 0;
	valp->strval = *argp++;
  }
}

/* Return 1 if the argument is zero (numeric) or null (string */
int nullz(valp)
struct value *valp;
{
  if (numvalue(valp)) return(valp->numval == 0);

  return(strlen(strvalue(valp)) == 0);
}

/* Return 1 if the argument is a valid number, insuring that the nf_valid
 * and numval fields are set properly. Does the string-to-number
 * conversion if nf_valid is false.
 */
int numvalue(valp)
struct value *valp;
{
  register char *p;
  int sign = 0, digits = 0;
  unsigned long num = 0;

  if (valp->nf_valid) return 1;

  if ((p = valp->strval) == NULL) return 0;

  if (*p == '-') {
	++p;
	sign = 1;
  }
  while (isdigit(*p)) {
	num = num * 10 + (*p++ - '0');
	digits = 1;
  }

  if (!digits || *p != '\0') return 0;

  valp->numval = sign ? -num : num;
  valp->nf_valid = 1;
  return 1;
}

/* Return the string value of the given argument. If there is only a
 * numeric value, convert it to a string
 */
char *strvalue(valp)
struct value *valp;
{
  char numbuf[30];
  register char *p;
  unsigned long num;
  int sign = 0;

  if (!valp->nf_valid) return(valp->strval != NULL) ? valp->strval : "";

  p = numbuf + sizeof numbuf;
  *--p = '\0';

  if (valp->numval < 0) {
	num = -(valp->numval);
	sign = 1;
  } else
	num = valp->numval;

  do {
	*--p = '0' + (num % 10);
	num /= 10;
  } while (num);

  if (sign) *--p = '-';

  return(valp->strval = strsave(p));
}

/* Save the given string in its own allocated memory and return a pointer
 * to that memory.
 */
char *strsave(string)
char *string;
{
  char *p;

  if ((p = (char *)malloc(strlen(string) + 1)) == NULL) invalid("out of memory");

  (void) strcpy(p, string);

  return p;
}

/* Print error message and exit. */
void invalid(err)
char *err;
{
  (void) fputs(progname, stderr);
  (void) fputs(": ", stderr);
  (void) fputs(err, stderr);
  (void) putc('\n', stderr);
  exit(2);
}

#ifndef NOCOLON

#include <limits.h>

#define RMIN		(UCHAR_MAX-8)	/* >= reserved as opcodes */
#define RESC		(UCHAR_MAX-8)	/* for escaping opcodes */
#define RDOT		(UCHAR_MAX-7)	/* match any character */
#define ROPEN		(UCHAR_MAX-6)	/* opening \( */
#define RCLOSE		(UCHAR_MAX-5)	/* closing \) */
#define RSTAR		(UCHAR_MAX-4)	/* Kleene closure */
#define RCLASS		(UCHAR_MAX-3)	/* character class */
#define RBACK		(UCHAR_MAX-2)	/* \digit reference */
#define REND		(UCHAR_MAX-1)	/* end of program */

#define	RABEGIN		0x01	/* match anchored at BOL (^) */
#define RAEND		0x02	/* match anchored at EOL ($) */
#define RSELECT		0x04	/* \(...\) selection op used */

#define PROGLENGTH	1024	/* bytes reserved for r-programs */

#define	CLASS_BYTES	((CHAR_MAX - CHAR_MIN + 1 + CHAR_BIT-1) / CHAR_BIT)

unsigned char rprogram[PROGLENGTH];	/* regexp program storage */
unsigned int rflags = RABEGIN;	/* regexp program context */

char *rbegins[10];		/* pointers to \( beginnings */
char *rends[10];		/* pointers to \) endings */
int rlevel;			/* \(...\) level */

/* Compile the regexp, match it against the string, and return the
 * proper result (a string if \(...\) used, and the match length otherwise.
 */
void docolon(match, pattern)
struct value *match, *pattern;
{
  rcomp(strvalue(pattern));

  rmatch(strvalue(match));

  if (rflags & RSELECT) {
	match->nf_valid = 0;
	if (rends[0] == rbegins[0] || rends[1] == NULL) {
		match->strval = NULL;
	} else {
		*(rends[1]) = '\0';	/* semi-nasty */
		match->strval = rbegins[1];
	}
  } else {
	numresult(match, rends[0] - rbegins[0]);
  }
}

/* Compile an ed(1)-syntax regular-expression into the rprogram[] array. */
void rcomp(regexp)
register char *regexp;
{
  char c;			/* current regexp character */
  char first, last;		/* limits of character class */
  unsigned char *starable;	/* last "starable" variable */
  unsigned char *rpc;		/* pointer to next program storage byte */
  int negate;			/* character class negated */
  int i;			/* loop counter and such */
  int pstack[9];		/* \(...\) nesting stack */
  int pstackp = 0;		/* stack pointer for nesting stack */
  int pclosed[10];		/* flags indicating \(...\) closed */

  rpc = &rprogram[0];
  starable = NULL;

  for (i = 1; i < 10; ++i) pclosed[i] = 0;

  if (*regexp == '^') {
	rflags |= RABEGIN;	/* not needed, as it turns out */
	++regexp;
  }
  while ((c = *regexp++)) {
	if ((rpc - rprogram) >= PROGLENGTH - 2 - CLASS_BYTES)
		invalid("regular expression program too long");

	switch (c) {
	    case '.':
		starable = rpc;
		*rpc++ = RDOT;
		break;
	    case '\\':
		if (isdigit(*regexp)) {
			if (!pclosed[*regexp - '0'])
				invalid("reference to unclosed/nonexistent \\(...\\) pair");
			starable = NULL;
			*rpc++ = RBACK;
			*rpc++ = *regexp++ - '0';
		} else if (*regexp == '(') {
			starable = NULL;
			++regexp;
			rflags |= RSELECT;
			if ((i = ++rlevel) > 9)
				invalid("too many \\(...\\) levels");
			pstack[pstackp++] = i;
			*rpc++ = ROPEN;
			*rpc++ = i;
			break;
		} else if (*regexp == ')') {
			starable = NULL;
			++regexp;
			if (pstackp == 0)
				invalid("\\(...\\) pairs don't balance");
			i = pstack[--pstackp];
			*rpc++ = RCLOSE;
			*rpc++ = i;
			pclosed[i] = 1;
			break;
		} else if ((unsigned char) *regexp >= RMIN) {
			starable = rpc;
			*rpc++ = RESC;
			*rpc++ = *regexp++;
			break;
		} else {
			starable = rpc;
			*rpc++ = *regexp++;
			break;
		}
	    case '$':
		if (*regexp == '\0') {
			rflags |= RAEND;
			break;
		} else {
			starable = rpc;
			*rpc++ = '$';
			break;
		}
	    case '*':
		if (starable == NULL) {
			starable = rpc;
			*rpc++ = '*';
			break;
		} else {
			memmove(starable + 1, starable, (size_t)(rpc - starable));
			*starable = RSTAR;
			starable = NULL;
			++rpc;
			break;
		}
	    case '[':
		negate = 0;
		starable = rpc;
		*rpc++ = RCLASS;
		if (*regexp == '^') {
			++regexp;
			negate = 1;
		}
		for (i = 0; i < CLASS_BYTES; ++i) rpc[i] = 0;
		do {
			first = *regexp++;
			if (*regexp == '-' && regexp[1] != ']'
			    && regexp[1] > first) {
				++regexp;
				last = *regexp++;
				for (i = first; i <= last; ++i) {
					rpc[(i - CHAR_MIN) / CHAR_BIT] |=
						1 << ((i - CHAR_MIN) % CHAR_BIT);
				}
			} else {
				rpc[(first - CHAR_MIN) / CHAR_BIT] |=
					1 << ((first - CHAR_MIN) % CHAR_BIT);
			}
		} while (*regexp && *regexp != ']');
		if (*regexp != ']') invalid("unterminated character class");
		++regexp;
		if (negate) for (i = 0; i < CLASS_BYTES; ++i, ++rpc)
				*rpc = ~*rpc;
		else
			rpc += CLASS_BYTES;
		break;
	    default:
		if ((unsigned char) c >= RMIN) {
			starable = rpc;
			*rpc++ = RESC;
			*rpc++ = c;
			break;
		} else {
			starable = rpc;
			*rpc++ = c;
			break;
		}
	}
  }
  if (pstackp != 0) invalid("\\(...\\) pairs don't balance");
  *rpc = REND;
}

/* It turns out that expr regular expressions have an implicit
 * '^' prepended, and therefore RABEGIN is always on. It seemed
 * a waste to delete the code after discovering this, however.
 */
void rmatch(str)
char *str;
{
  char *end;
  unsigned char *rpc;

  rends[0] = rbegins[0] = str;

  if (rflags & RABEGIN) {
	rpc = &rprogram[0];
	if ((end = rtry(str, &rpc)) != NULL) rends[0] = end;
  } else {
	while (*str) {
		rpc = &rprogram[0];
		end = rtry(str, &rpc);
		if (end != NULL && (end - str) > (rends[0] - rbegins[0])) {
			rbegins[0] = str;	/* longest match wins */
			rends[0] = end;
		}
		++str;
	}
  }

}

/* Try to match str to program from *pcp on */
char *rtry(str, pcp)
char *str;
unsigned char **pcp;
{
  char *nstr;

  while (*str && **pcp != REND) {
	if ((nstr = tryone(str, pcp)) == NULL) return NULL;
	str = nstr;
  }

  while (**pcp == RCLOSE) {
	rends[*(*pcp + 1)] = str;
	*pcp += 2;
  }

  if (**pcp != REND) return NULL;

  if ((rflags & RAEND) && *str != '\0') return NULL;

  return str;
}

/* Try to match one regular expression operator */
char *tryone(str, pcp)
char *str;
unsigned char **pcp;
{
  char *ret = NULL;
  unsigned char *npc;
  char *p, *q;

again:
  switch (**pcp) {
      case RESC:
	if (*str == *(*pcp + 1)) ret = str + 1;
	*pcp += 2;
	break;
      default:
	if (*str == **pcp) ret = str + 1;
	*pcp += 1;
	break;
      case RDOT:
	if (*str != '\0') ret = str + 1;
	*pcp += 1;
	break;
      case RCLASS:
	if (*str != '\0'
	    && ((*pcp + 1)[(*str - CHAR_MIN) / CHAR_BIT]
		& (1 << ((*str - CHAR_MIN) % CHAR_BIT)))) {
		ret = str + 1;
	}
	*pcp += CLASS_BYTES + 1;
	break;
      case ROPEN:
	rbegins[*(*pcp + 1)] = str;
	*pcp += 2;
	goto again;
      case RCLOSE:
	rends[*(*pcp + 1)] = str;
	*pcp += 2;
	goto again;
      case RBACK:
	p = rbegins[*(*pcp + 1)];
	q = rends[*(*pcp + 1)];
	*pcp += 2;
	while (p < q)
		if (*p++ != *str++) return NULL;
	ret = str;
	break;
      case RSTAR:
	*pcp += 1;
	p = str;
	while (npc = *pcp, tryone(p, &npc) != NULL) ++p;
	*pcp = npc;
	while (p >= str
	       && (npc = *pcp, (ret = rtry(p, &npc)) == NULL))
		--p;
	*pcp = npc;
	break;
      case REND:	ret = str;
}

  return ret;
}

#endif				/* !NOCOLON */