From:	MERC::"uunet!WKUVX1.BITNET!FILESERV-Mgr" 12-JUN-1992 15:52:49.09
To:	galaxy::gleeve
CC:	
Subj:	GREP.04_OF_12

-+-+-+-+-+-+-+-+ START OF PART 4 -+-+-+-+-+-+-+-+
X`09int oldalloc = r->tralloc;
X
X`09while (trans`5Bi`5D >= r->tralloc)
X`09  r->tralloc *= 2;
X`09REALLOC(r->realtrans, int *, r->tralloc + 1);
X`09r->trans = r->realtrans + 1;
X`09REALLOC(r->fails, int *, r->tralloc);
X`09REALLOC(r->success, int, r->tralloc);
X`09REALLOC(r->newlines, int, r->tralloc);
X`09while (oldalloc < r->tralloc)
X`09  `7B
X`09    r->trans`5Boldalloc`5D = NULL;
X`09    r->fails`5Boldalloc++`5D = NULL;
X`09  `7D
X      `7D
X
X  /* Keep the newline transition in a special place so we can use it as
X     a sentinel. */
X  r->newlines`5Bs`5D = trans`5B'\n'`5D;
X  trans`5B'\n'`5D = -1;
X
X  if (ACCEPTING(s, *r))
X    r->fails`5Bs`5D = trans;
X  else
X    r->trans`5Bs`5D = trans;
X`7D
X
Xstatic void
Xbuild_state_zero(r)
X     struct regexp *r;
X`7B
X  r->tralloc = 1;
X  r->trcount = 0;
X  CALLOC(r->realtrans, int *, r->tralloc + 1);
X  r->trans = r->realtrans + 1;
X  CALLOC(r->fails, int *, r->tralloc);
X  MALLOC(r->success, int, r->tralloc);
X  MALLOC(r->newlines, int, r->tralloc);
X  build_state(0, r);
X`7D
X`0C
X/* Search through a buffer looking for a match to the given struct regexp.
X   Find the first occurrence of a string matching the regexp in the buffer,
X   and the shortest possible version thereof.  Return a pointer to the first
X   character after the match, or NULL if none is found.  Begin points to
X   the beginning of the buffer, and end points to the first character after
X   its end.  We store a newline in *end to act as a sentinel, so end had
X   better point somewhere valid.  Newline is a flag indicating whether to
X   allow newlines to be in the matching string.  If count is non-
X   NULL it points to a place we're supposed to increment every time we
X   see a newline.  Finally, if backref is non-NULL it points to a place
X   where we're supposed to store a 1 if backreferencing happened and the
X   match needs to be verified by a backtracking matcher.  Otherwise
X   we store a 0 in *backref. */
Xchar *
Xregexecute(r, begin, end, newline, count, backref)
X     struct regexp *r;
X     char *begin;
X     char *end;
X     int newline;
X     int *count;
X     int *backref;
X`7B
X  register s, s1, tmp;`09`09/* Current state. */
X  register unsigned char *p;`09/* Current input character. */
X  register **trans, *t;`09`09/* Copy of r->trans so it can be optimized
X`09`09`09`09   into a register. */
X  static sbit`5B_NOTCHAR`5D;`09/* Table for anding with r->success. */
X  static sbit_init;
X
X  if (! sbit_init)
X    `7B
X      int i;
X
X      sbit_init = 1;
X      for (i = 0; i < _NOTCHAR; ++i)
X`09if (i == '\n')
X`09  sbit`5Bi`5D = 4;
X`09else if (ISALNUM(i))
X`09  sbit`5Bi`5D = 2;
X`09else
X`09  sbit`5Bi`5D = 1;
X    `7D
X
X  if (! r->tralloc)
X    build_state_zero(r);
X
X  s = 0;
X  p = (unsigned char *) begin;
X  trans = r->trans;
X  *end = '\n';
X
X  for (;;)
X    `7B
X      /* The dreaded inner loop. */
X      if (t = trans`5Bs`5D)
X`09do
X`09  `7B
X`09    s1 = t`5B*p++`5D;
X`09    if (! (t = trans`5Bs1`5D))
X`09      goto last_was_s;
X`09    s = t`5B*p++`5D;
X`09  `7D
X        while (t = trans`5Bs`5D);
X      goto last_was_s1;
X    last_was_s:
X      tmp = s, s = s1, s1 = tmp;
X    last_was_s1:
X
X      if (s >= 0 && p <= (unsigned char *) end && r->fails`5Bs`5D)
X`09`7B
X`09  if (r->success`5Bs`5D & sbit`5B*p`5D)
X`09    `7B
X`09      if (backref)
X`09`09if (r->states`5Bs`5D.backref)
X`09`09  *backref = 1;
X`09`09else
X`09`09  *backref = 0;
X`09      return (char *) p;
X`09    `7D
X
X`09  s1 = s;
X`09  s = r->fails`5Bs`5D`5B*p++`5D;
X`09  continue;
X`09`7D
X
X      /* If the previous character was a newline, count it. */
X      if (count && (char *) p <= end && p`5B-1`5D == '\n')
X`09++*count;
X
X      /* Check if we've run off the end of the buffer. */
X      if ((char *) p >= end)
X`09return NULL;
X
X      if (s >= 0)
X`09`7B
X`09  build_state(s, r);
X`09  trans = r->trans;
X`09  continue;
X`09`7D
X
X      if (p`5B-1`5D == '\n' && newline)
X`09`7B
X`09  s = r->newlines`5Bs1`5D;
X`09  continue;
X`09`7D
X
X      s = 0;
X    `7D
X`7D
X`0C
X/* Initialize the components of a regexp that the other routines don't
X   initialize for themselves. */
Xvoid
Xreginit(r)
X     struct regexp *r;
X`7B
X  r->calloc = 1;
X  MALLOC(r->charsets, _charset, r->calloc);
X  r->cindex = 0;
X
X  r->talloc = 1;
X  MALLOC(r->tokens, _token, r->talloc);
X  r->tindex = r->depth = r->nleaves = r->nregexps = 0;
X
X  r->searchflag = 0;
X  r->tralloc = 0;
X`7D
X
X/* Parse and analyze a single string of the given length. */
Xvoid
Xregcompile(s, len, r, searchflag)
X     const char *s;
X     size_t len;
X     struct regexp *r;
X     int searchflag;
X`7B
X  if (case_fold)`09/* dummy folding in service of regmust() */
X    `7B
X      char *copy;
X      int i;
X
X      copy = malloc(len);
X      if (!copy)
X`09regerror("out of memory");
X     `20
X      /* This is a complete kludge and could potentially break
X`09 \<letter> escapes . . . */
X      case_fold = 0;
X      for (i = 0; i < len; ++i)
X`09if (ISUPPER(s`5Bi`5D))
X`09  copy`5Bi`5D = tolower(s`5Bi`5D);
X`09else
X`09  copy`5Bi`5D = s`5Bi`5D;
X
X      reginit(r);
X      r->mustn = 0;
X      r->must`5B0`5D = '\0';
X      regparse(copy, len, r);
X      free(copy);
X      regmust(r);
X      reganalyze(r, searchflag);
X      case_fold = 1;
X      reginit(r);
X      regparse(s, len, r);
X      reganalyze(r, searchflag);
X    `7D
X  else
X    `7B
X        reginit(r);
X        regparse(s, len, r);
X        regmust(r);
X        reganalyze(r, searchflag);
X    `7D
X`7D
X
X/* Free the storage held by the components of a regexp. */
Xvoid
Xregfree(r)
X     struct regexp *r;
X`7B
X  int i;
X
X  free((ptr_t) r->charsets);
X  free((ptr_t) r->tokens);
X  for (i = 0; i < r->sindex; ++i)
X    free((ptr_t) r->states`5Bi`5D.elems.elems);
X  free((ptr_t) r->states);
X  for (i = 0; i < r->tindex; ++i)
X    if (r->follows`5Bi`5D.elems)
X      free((ptr_t) r->follows`5Bi`5D.elems);
X  free((ptr_t) r->follows);
X  for (i = 0; i < r->tralloc; ++i)
X    if (r->trans`5Bi`5D)
X      free((ptr_t) r->trans`5Bi`5D);
X    else if (r->fails`5Bi`5D)
X      free((ptr_t) r->fails`5Bi`5D);
X  free((ptr_t) r->realtrans);
X  free((ptr_t) r->fails);
X  free((ptr_t) r->newlines);
X`7D
X
X/*
XHaving found the postfix representation of the regular expression,
Xtry to find a long sequence of characters that must appear in any line
Xcontaining the r.e.
XFinding a "longest" sequence is beyond the scope here;
Xwe take an easy way out and hope for the best.
X(Take "(ab`7Ca)b"--please.)
X
XWe do a bottom-up calculation of sequences of characters that must appear
Xin matches of r.e.'s represented by trees rooted at the nodes of the postfix
Xrepresentation:
X`09sequences that must appear at the left of the match ("left")
X`09sequences that must appear at the right of the match ("right")
X`09lists of sequences that must appear somewhere in the match ("in")
X`09sequences that must constitute the match ("is")
XWhen we get to the root of the tree, we use one of the longest of its
Xcalculated "in" sequences as our answer.  The sequence we find is returned i
Vn
Xr->must (where "r" is the single argument passed to "regmust");
Xthe length of the sequence is returned in r->mustn.
X
XThe sequences calculated for the various types of node (in pseudo ANSI c)
Xare shown below.  "p" is the operand of unary operators (and the left-hand
Xoperand of binary operators); "q" is the right-hand operand of binary operat
Vors
X.
X"ZERO" means "a zero-length sequence" below.
X
XType`09left`09`09right`09`09is`09`09in
X----`09----`09`09-----`09`09--`09`09--
Xchar c`09# c`09`09# c`09`09# c`09`09# c
X
XSET`09ZERO`09`09ZERO`09`09ZERO`09`09ZERO
X
XSTAR`09ZERO`09`09ZERO`09`09ZERO`09`09ZERO
X
XQMARK`09ZERO`09`09ZERO`09`09ZERO`09`09ZERO
X
XPLUS`09p->left`09`09p->right`09ZERO`09`09p->in
X
XCAT`09(p->is==ZERO)?`09(q->is==ZERO)?`09(p->is!=ZERO &&`09p->in plus
X`09p->left :`09q->right :`09q->is!=ZERO) ?`09q->in plus
X`09p->is##q->left`09p->right##q->is`09p->is##q->is :`09p->right##q->left
X`09`09`09`09`09ZERO
X
XOR`09longest common`09longest common`09(do p->is and`09substrings common to
X`09leading`09`09trailing`09q->is have same`09p->in and q->in
X`09(sub)sequence`09(sub)sequence`09length and`09
X`09of p->left`09of p->right`09content) ?`09
X`09and q->left`09and q->right`09p->is : NULL`09
X
XIf there's anything else we recognize in the tree, all four sequences get se
Vt
Xto zero-length sequences.  If there's something we don't recognize in the tr
Vee,
Xwe just return a zero-length sequence.
X
XBreak ties in favor of infrequent letters (choosing 'zzz' in preference to
X'aaa')?
X
XAnd. . .is it here or someplace that we might ponder "optimizations" such as
X`09egrep 'psi`7Cepsilon'`09->`09egrep 'psi'
X`09egrep 'pepsi`7Cepsilon'`09->`09egrep 'epsi'
X`09`09`09`09`09(Yes, we now find "epsi" as a "string
X`09`09`09`09`09that must occur", but we might also
X`09`09`09`09`09simplify the *entire* r.e. being sought
X)
X`09grep '`5Bc`5D'`09`09->`09grep 'c'
X`09grep '(ab`7Ca)b'`09`09->`09grep 'ab'
X`09grep 'ab*'`09`09->`09grep 'a'
X`09grep 'a*b'`09`09->`09grep 'b'
XThere are several issues:
X`09Is optimization easy (enough)?
X
X`09Does optimization actually accomplish anything,
X`09or is the automaton you get from "psi`7Cepsilon" (for example)
X`09the same as the one you get from "psi" (for example)?
X
X`09Are optimizable r.e.'s likely to be used in real-life situations
X`09(something like 'ab*' is probably unlikely; something like is
X`09'psi`7Cepsilon' is likelier)?
X*/
X
Xstatic char *
Xicatalloc(old, new)
Xchar *`09old;
Xchar *`09new;
X`7B
X`09register char *`09result;
X`09register int`09oldsize, newsize;
X
X`09newsize = (new == NULL) ? 0 : strlen(new);
X`09if (old == NULL)
X`09`09oldsize = 0;
X`09else if (newsize == 0)
X`09`09return old;
X`09else`09oldsize = strlen(old);
X`09if (old == NULL)
X`09`09result = (char *) malloc(newsize + 1);
X`09else`09result = (char *) realloc((void *) old, oldsize + newsize + 1);
X`09if (result != NULL && new != NULL)
X`09`09(void) strcpy(result + oldsize, new);
X`09return result;
X`7D
X
Xstatic char *
Xicpyalloc(string)
Xconst char *`09string;
X`7B
X`09return icatalloc((char *) NULL, string);
X`7D
X
Xstatic char *
Xistrstr(lookin, lookfor)
Xchar *`09`09lookin;
Xregister char *`09lookfor;
X`7B
X`09register char *`09cp;
X`09register int`09len;
X
X`09len = strlen(lookfor);
X`09for (cp = lookin; *cp != '\0'; ++cp)
X`09`09if (strncmp(cp, lookfor, len) == 0)
X`09`09`09return cp;
X`09return NULL;
X`7D
X
Xstatic void
Xifree(cp)
Xchar *`09cp;
X`7B
X`09if (cp != NULL)
X`09`09free(cp);
X`7D
X
Xstatic void
Xfreelist(cpp)
Xregister char **`09cpp;
X`7B
X`09register int`09i;
X
X`09if (cpp == NULL)
X`09`09return;
X`09for (i = 0; cpp`5Bi`5D != NULL; ++i) `7B
X`09`09free(cpp`5Bi`5D);
X`09`09cpp`5Bi`5D = NULL;
X`09`7D
X`7D
X
Xstatic char **
Xenlist(cpp, new, len)
Xregister char **`09cpp;
Xregister char *`09`09new;
Xint len;
X`7B
X`09register int`09i, j;
X
X`09if (cpp == NULL)
X`09`09return NULL;
X`09if ((new = icpyalloc(new)) == NULL) `7B
X`09`09freelist(cpp);
X`09`09return NULL;
X`09`7D
X`09new`5Blen`5D = '\0';
X`09/*
X`09** Is there already something in the list that's new (or longer)?
X`09*/
X`09for (i = 0; cpp`5Bi`5D != NULL; ++i)
X`09`09if (istrstr(cpp`5Bi`5D, new) != NULL) `7B
X`09`09`09free(new);
X`09`09`09return cpp;
X`09`09`7D
X`09/*
X`09** Eliminate any obsoleted strings.
X`09*/
X`09j = 0;
X`09while (cpp`5Bj`5D != NULL)
X`09`09if (istrstr(new, cpp`5Bj`5D) == NULL)
X`09`09`09++j;
X`09`09else `7B
X`09`09`09free(cpp`5Bj`5D);
X`09`09`09if (--i == j)
X`09`09`09`09break;
X`09`09`09cpp`5Bj`5D = cpp`5Bi`5D;
X`09`09`7D
X`09/*
X`09** Add the new string.
X`09*/
X`09cpp = (char **) realloc((char *) cpp, (i + 2) * sizeof *cpp);
X`09if (cpp == NULL)
X`09`09return NULL;
X`09cpp`5Bi`5D = new;
X`09cpp`5Bi + 1`5D = NULL;
X`09return cpp;
X`7D
X
X/*
X** Given pointers to two strings,
X** return a pointer to an allocated list of their distinct common substrings
V.
X** Return NULL if something seems wild.
X*/
X
Xstatic char **
Xcomsubs(left, right)
Xchar *`09left;
Xchar *`09right;
X`7B
X`09register char **`09cpp;
X`09register char *`09`09lcp;
X`09register char *`09`09rcp;
X`09register int`09`09i, len;
X
X`09if (left == NULL `7C`7C right == NULL)
X`09`09return NULL;
X`09cpp = (char **) malloc(sizeof *cpp);
X`09if (cpp == NULL)
X`09`09return NULL;
X`09cpp`5B0`5D = NULL;
X`09for (lcp = left; *lcp != '\0'; ++lcp) `7B
X`09`09len = 0;
X`09`09rcp = (char *) index(right, *lcp);
X`09`09while (rcp != NULL) `7B
X`09`09`09for (i = 1; lcp`5Bi`5D != '\0' && lcp`5Bi`5D == rcp`5Bi`5D; ++i)
X`09`09`09`09;
X`09`09`09if (i > len)
X`09`09`09`09len = i;
X`09`09`09rcp = (char *) index(rcp + 1, *lcp);
X`09`09`7D
X`09`09if (len == 0)
X`09`09`09continue;
X`09`09if ((cpp = enlist(cpp, lcp, len)) == NULL)
X`09`09`09break;
X`09`7D
X`09return cpp;
X`7D
X
Xstatic char **
Xaddlists(old, new)
Xchar **`09old;
Xchar **`09new;
X`7B
X`09register int`09i;
X
X`09if (old == NULL `7C`7C new == NULL)
X`09`09return NULL;
X`09for (i = 0; new`5Bi`5D != NULL; ++i) `7B
X`09`09old = enlist(old, new`5Bi`5D, strlen(new`5Bi`5D));
X`09`09if (old == NULL)
X`09`09`09break;
X`09`7D
X`09return old;
X`7D
X
X/*
X** Given two lists of substrings,
X** return a new list giving substrings common to both.
X*/
X
Xstatic char **
Xinboth(left, right)
Xchar **`09left;
Xchar **`09right;
X`7B
X`09register char **`09both;
X`09register char **`09temp;
X`09register int`09`09lnum, rnum;
X
X`09if (left == NULL `7C`7C right == NULL)
X`09`09return NULL;
X`09both = (char **) malloc(sizeof *both);
X`09if (both == NULL)
X`09`09return NULL;
X`09both`5B0`5D = NULL;
X`09for (lnum = 0; left`5Blnum`5D != NULL; ++lnum) `7B
X`09`09for (rnum = 0; right`5Brnum`5D != NULL; ++rnum) `7B
X`09`09`09temp = comsubs(left`5Blnum`5D, right`5Brnum`5D);
X`09`09`09if (temp == NULL) `7B
X`09`09`09`09freelist(both);
X`09`09`09`09return NULL;
X`09`09`09`7D
X`09`09`09both = addlists(both, temp);
X`09`09`09freelist(temp);
X`09`09`09if (both == NULL)
X`09`09`09`09return NULL;
X`09`09`7D
X`09`7D
X`09return both;
X`7D
X
Xtypedef struct `7B
X`09char **`09in;
X`09char *`09left;
X`09char *`09right;
X`09char *`09is;
X`7D must;
X
Xstatic void
Xresetmust(mp)
Xregister must *`09mp;
X`7B
X`09mp->left`5B0`5D = mp->right`5B0`5D = mp->is`5B0`5D = '\0';
X`09freelist(mp->in);
X`7D
X
Xstatic void
Xregmust(reg)
Xregister struct regexp *`09reg;
X`7B
X`09register must *`09`09musts;
X`09register must *`09`09mp;
X`09register char *`09`09result;
X`09register int`09`09ri;
X`09register int`09`09i;
X`09register _token`09`09t;
X`09static must`09`09must0;
X
X`09reg->mustn = 0;
X`09reg->must`5B0`5D = '\0';
X`09musts = (must *) malloc((reg->tindex + 1) * sizeof *musts);
X`09if (musts == NULL)
X`09`09return;
X`09mp = musts;
X`09for (i = 0; i <= reg->tindex; ++i)
X`09`09mp`5Bi`5D = must0;
X`09for (i = 0; i <= reg->tindex; ++i) `7B
X`09`09mp`5Bi`5D.in = (char **) malloc(sizeof *mp`5Bi`5D.in);
X`09`09mp`5Bi`5D.left = malloc(2);
X`09`09mp`5Bi`5D.right = malloc(2);
X`09`09mp`5Bi`5D.is = malloc(2);
X`09`09if (mp`5Bi`5D.in == NULL `7C`7C mp`5Bi`5D.left == NULL `7C`7C
X`09`09`09mp`5Bi`5D.right == NULL `7C`7C mp`5Bi`5D.is == NULL)
X`09`09`09`09goto done;
X`09`09mp`5Bi`5D.left`5B0`5D = mp`5Bi`5D.right`5B0`5D = mp`5Bi`5D.is`5B0`5D =
V '\0';
X`09`09mp`5Bi`5D.in`5B0`5D = NULL;
X`09`7D
X`09result = "";
X#ifdef DEBUG
X`09fprintf(stderr, "regmust:\n");
X`09for (i = 0; i < reg->tindex; ++i) `7B
X`09`09fprintf(stderr, " %d:", i);
X`09`09prtok(reg->tokens`5Bi`5D);
X`09`7D
X`09putc('\n', stderr);
X#endif
X`09for (ri = 0; ri < reg->tindex; ++ri) `7B
X`09`09switch (t = reg->tokens`5Bri`5D) `7B
X`09`09case _ALLBEGLINE:
X`09`09case _ALLENDLINE:
X`09`09case _LPAREN:
X`09`09case _RPAREN:
X`09`09`09goto done;`09`09/* "cannot happen" */
X`09`09case _EMPTY:
X`09`09case _BEGLINE:
X`09`09case _ENDLINE:
X`09`09case _BEGWORD:
X`09`09case _ENDWORD:
X`09`09case _LIMWORD:
X`09`09case _NOTLIMWORD:
X`09`09case _BACKREF:
X`09`09`09resetmust(mp);
X`09`09`09break;
X`09`09case _STAR:
X`09`09case _QMARK:
X`09`09`09if (mp <= musts)
X`09`09`09`09goto done;`09/* "cannot happen" */
X`09`09`09--mp;
X`09`09`09resetmust(mp);
X`09`09`09break;
X`09`09case _OR:
X`09`09`09if (mp < &musts`5B2`5D)
X`09`09`09`09goto done;`09/* "cannot happen" */
X`09`09`09`7B
X`09`09`09`09register char **`09new;
X`09`09`09`09register must *`09`09lmp;
X`09`09`09`09register must *`09`09rmp;
X`09`09`09`09register int`09`09j, ln, rn, n;
X
X`09`09`09`09rmp = --mp;
X`09`09`09`09lmp = --mp;
X`09`09`09`09/* Guaranteed to be.  Unlikely, but. . . */
X`09`09`09`09if (strcmp(lmp->is, rmp->is) != 0)
X`09`09`09`09`09lmp->is`5B0`5D = '\0';
X`09`09`09`09/* Left side--easy */
X`09`09`09`09i = 0;
X`09`09`09`09while (lmp->left`5Bi`5D != '\0' &&
X`09`09`09`09`09lmp->left`5Bi`5D == rmp->left`5Bi`5D)
X`09`09`09`09`09`09++i;
X`09`09`09`09lmp->left`5Bi`5D = '\0';
X`09`09`09`09/* Right side */
X`09`09`09`09ln = strlen(lmp->right);
X`09`09`09`09rn = strlen(rmp->right);
X`09`09`09`09n = ln;
X`09`09`09`09if (n > rn)
X`09`09`09`09`09n = rn;
X`09`09`09`09for (i = 0; i < n; ++i)
X`09`09`09`09`09if (lmp->right`5Bln - i - 1`5D !=
X`09`09`09`09`09    rmp->right`5Brn - i - 1`5D)
X`09`09`09`09`09`09break;
X`09`09`09`09for (j = 0; j < i; ++j)
X`09`09`09`09`09lmp->right`5Bj`5D =
X`09`09`09`09`09`09lmp->right`5B(ln - i) + j`5D;
X`09`09`09`09lmp->right`5Bj`5D = '\0';
X`09`09`09`09new = inboth(lmp->in, rmp->in);
X`09`09`09`09if (new == NULL)
X`09`09`09`09`09goto done;
X`09`09`09`09freelist(lmp->in);
X`09`09`09`09free((char *) lmp->in);
X`09`09`09`09lmp->in = new;
X`09`09`09`7D
X`09`09`09break;
X`09`09case _PLUS:
X`09`09`09if (mp <= musts)
X`09`09`09`09goto done;`09/* "cannot happen" */
X`09`09`09--mp;
X`09`09`09mp->is`5B0`5D = '\0';
X`09`09`09break;
X`09`09case _END:
X`09`09`09if (mp != &musts`5B1`5D)
X`09`09`09`09goto done;`09/* "cannot happen" */
X`09`09`09for (i = 0; musts`5B0`5D.in`5Bi`5D != NULL; ++i)
X`09`09`09`09if (strlen(musts`5B0`5D.in`5Bi`5D) > strlen(result))
X`09`09`09`09`09result = musts`5B0`5D.in`5Bi`5D;
X`09`09`09goto done;
X`09`09case _CAT:
X`09`09`09if (mp < &musts`5B2`5D)
X`09`09`09`09goto done;`09/* "cannot happen" */
X`09`09`09`7B
X`09`09`09`09register must *`09lmp;
X`09`09`09`09register must *`09rmp;
X
X`09`09`09`09rmp = --mp;
X`09`09`09`09lmp = --mp;
X`09`09`09`09/*
X`09`09`09`09** In.  Everything in left, plus everything in
X`09`09`09`09** right, plus catenation of
X`09`09`09`09** left's right and right's left.
X`09`09`09`09*/
X`09`09`09`09lmp->in = addlists(lmp->in, rmp->in);
X`09`09`09`09if (lmp->in == NULL)
X`09`09`09`09`09goto done;
X`09`09`09`09if (lmp->right`5B0`5D != '\0' &&
X`09`09`09`09`09rmp->left`5B0`5D != '\0') `7B
X`09`09`09`09`09`09register char *`09tp;
X
X`09`09`09`09`09`09tp = icpyalloc(lmp->right);
X`09`09`09`09`09`09if (tp == NULL)
X`09`09`09`09`09`09`09goto done;
X`09`09`09`09`09`09tp = icatalloc(tp, rmp->left);
X`09`09`09`09`09`09if (tp == NULL)
X`09`09`09`09`09`09`09goto done;
X`09`09`09`09`09`09lmp->in = enlist(lmp->in, tp,
X`09`09`09`09`09`09`09strlen(tp));
X`09`09`09`09`09`09free(tp);
X`09`09`09`09`09`09if (lmp->in == NULL)
X`09`09`09`09`09`09`09goto done;
X`09`09`09`09`7D
X`09`09`09`09/* Left-hand */
X`09`09`09`09if (lmp->is`5B0`5D != '\0') `7B
X`09`09`09`09`09lmp->left = icatalloc(lmp->left,
X`09`09`09`09`09`09rmp->left);
X`09`09`09`09`09if (lmp->left == NULL)
X`09`09`09`09`09`09goto done;
X`09`09`09`09`7D
X`09`09`09`09/* Right-hand */
X`09`09`09`09if (rmp->is`5B0`5D == '\0')
X`09`09`09`09`09lmp->right`5B0`5D = '\0';
X`09`09`09`09lmp->right = icatalloc(lmp->right, rmp->right);
X`09`09`09`09if (lmp->right == NULL)
X`09`09`09`09`09goto done;
X`09`09`09`09/* Guaranteed to be */
X`09`09`09`09if (lmp->is`5B0`5D != '\0' && rmp->is`5B0`5D != '\0') `7B
X`09`09`09`09`09lmp->is = icatalloc(lmp->is, rmp->is);
X`09`09`09`09`09if (lmp->is == NULL)
X`09`09`09`09`09`09goto done;
X`09`09`09`09`7D else
X`09`09`09`09`09lmp->is`5B0`5D = '\0';
X`09`09`09`7D
X`09`09`09break;
X`09`09default:
X`09`09`09if (t < _END) `7B
X`09`09`09`09/* "cannot happen" */
X`09`09`09`09goto done;
X`09`09`09`7D else if (t == '\0') `7B
X`09`09`09`09/* not on *my* shift */
X`09`09`09`09goto done;
X`09`09`09`7D else if (t >= _SET) `7B
X`09`09`09`09/* easy enough */
X`09`09`09`09resetmust(mp);
X`09`09`09`7D else `7B
X`09`09`09`09/* plain character */
X`09`09`09`09resetmust(mp);
X`09`09`09`09mp->is`5B0`5D = mp->left`5B0`5D = mp->right`5B0`5D = t;
X`09`09`09`09mp->is`5B1`5D = mp->left`5B1`5D = mp->right`5B1`5D = '\0';
X`09`09`09`09mp->in = enlist(mp->in, mp->is, 1);
X`09`09`09`09if (mp->in == NULL)
X`09`09`09`09`09goto done;
X`09`09`09`7D
X`09`09`09break;
X`09`09`7D
X#ifdef DEBUG
X`09`09fprintf(stderr, " node: %d:", ri);
X`09`09prtok(reg->tokens`5Bri`5D);
X`09`09fprintf(stderr, "\n  in:");
X`09`09for (i = 0; mp->in`5Bi`5D; ++i)
X`09`09`09fprintf(stderr, " \"%s\"", mp->in`5Bi`5D);
X`09`09fprintf(stderr, "\n  is: \"%s\"\n", mp->is);
X`09`09fprintf(stderr, "  left: \"%s\"\n", mp->left);
X`09`09fprintf(stderr, "  right: \"%s\"\n", mp->right);
X#endif
X`09`09++mp;
X`09`7D
Xdone:
X`09(void) strncpy(reg->must, result, MUST_MAX - 1);
X`09reg->must`5BMUST_MAX - 1`5D = '\0';
X`09reg->mustn = strlen(reg->must);
X`09mp = musts;
X`09for (i = 0; i <= reg->tindex; ++i) `7B
X`09`09freelist(mp`5Bi`5D.in);
X`09`09ifree((char *) mp`5Bi`5D.in);
X`09`09ifree(mp`5Bi`5D.left);
X`09`09ifree(mp`5Bi`5D.right);
X`09`09ifree(mp`5Bi`5D.is);
X`09`7D
X`09free((char *) mp);
X`7D
$ CALL UNPACK [.GREP016]DFA.C;1 1400764645
$ create 'f'
X/* dfa.h - declarations for GNU deterministic regexp compiler
X   Copyright (C) 1988 Free Software Foundation, Inc.
X
X   This program is free software; you can redistribute it and/or modify
X   it under the terms of the GNU General Public License as published by
X   the Free Software Foundation; either version 2, or (at your option)
X   any later version.
X
X   This program is distributed in the hope that it will be useful,
X   but WITHOUT ANY WARRANTY; without even the implied warranty of
X   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
X   GNU General Public License for more details.
X
X   You should have received a copy of the GNU General Public License
X   along with this program; if not, write to the Free Software
X   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
X
X/* Written June, 1988 by Mike Haertel */
X`0C
X#ifdef STDC_HEADERS
X
X#include <stddef.h>
X#include <stdlib.h>
X
X#else /* !STDC_HEADERS */
X
X#define const
X#ifdef VAXC
X#include <types.h>
X#else
X#include <sys/types.h>`09`09/* For size_t.  */
X#endif /* VAXC */
Xextern char *calloc(), *malloc(), *realloc();
Xextern void free();
X
X#ifndef NULL
X#define NULL 0
X#endif
X
X#endif /* ! STDC_HEADERS */
X
X#include <ctype.h>
X#ifndef isascii
X#define ISALNUM(c) isalnum(c)
X#define ISALPHA(c) isalpha(c)
X#define ISUPPER(c) isupper(c)
X#define ISLOWER(c) islower(c)
X#else
X#define ISALNUM(c) (isascii(c) && isalnum(c))
X#define ISALPHA(c) (isascii(c) && isalpha(c))
X#define ISUPPER(c) (isascii(c) && isupper(c))
X#define ISLOWER(c) (isascii(c) && islower(c))
X#endif
X
X/* 1 means plain parentheses serve as grouping, and backslash
X     parentheses are needed for literal searching.
X   0 means backslash-parentheses are grouping, and plain parentheses
X     are for literal searching.  */
X#define RE_NO_BK_PARENS 1
X
X/* 1 means plain `7C serves as the "or"-operator, and \`7C is a literal.
X   0 means \`7C serves as the "or"-operator, and `7C is a literal.  */
X#define RE_NO_BK_VBAR 2
X
X/* 0 means plain + or ? serves as an operator, and \+, \? are literals.
X   1 means \+, \? are operators and plain +, ? are literals.  */
X#define RE_BK_PLUS_QM 4
X
X/* 1 means `7C binds tighter than `5E or $.
X   0 means the contrary.  */
X#define RE_TIGHT_VBAR 8
X
X/* 1 means treat \n as an _OR operator
X   0 means treat it as a normal character */
X#define RE_NEWLINE_OR 16
X
X/* 0 means that a special characters (such as *, `5E, and $) always have
X     their special meaning regardless of the surrounding context.
X   1 means that special characters may act as normal characters in some
X     contexts.  Specifically, this applies to:
X`09`5E - only special at the beginning, or after ( or `7C
X`09$ - only special at the end, or before ) or `7C
X`09*, +, ? - only special when not after the beginning, (, or `7C */
X#define RE_CONTEXT_INDEP_OPS 32
X
X/* Now define combinations of bits for the standard possibilities.  */
X#define RE_SYNTAX_AWK (RE_NO_BK_PARENS `7C RE_NO_BK_VBAR `7C RE_CONTEXT_INDE
VP_OPS)
X#define RE_SYNTAX_EGREP (RE_SYNTAX_AWK `7C RE_NEWLINE_OR)
X#define RE_SYNTAX_GREP (RE_BK_PLUS_QM `7C RE_NEWLINE_OR)
X#define RE_SYNTAX_EMACS 0
X
X/* Number of bits in an unsigned char. */
X#define CHARBITS 8
X
X/* First integer value that is greater than any character code. */
X#define _NOTCHAR (1 << CHARBITS)
X
X/* INTBITS need not be exact, just a lower bound. */
X#define INTBITS (CHARBITS * sizeof (int))
X
X/* Number of ints required to hold a bit for every character. */
X#define _CHARSET_INTS ((_NOTCHAR + INTBITS - 1) / INTBITS)
X
X/* Sets of unsigned characters are stored as bit vectors in arrays of ints.
V */
Xtypedef int _charset`5B_CHARSET_INTS`5D;
X
X/* The regexp is parsed into an array of tokens in postfix form.  Some token
Vs
X   are operators and others are terminal symbols.  Most (but not all) of the
Vse
X   codes are returned by the lexical analyzer. */
X#if __STDC__
X
Xtypedef enum
X`7B
X  _END = -1,`09`09`09/* _END is a terminal symbol that matches the
X`09`09`09`09   end of input; any value of _END or less in
X`09`09`09`09   the parse tree is such a symbol.  Accepting
X`09`09`09`09   states of the DFA are those that would have
X`09`09`09`09   a transition on _END. */
X
X  /* Ordinary character values are terminal symbols that match themselves. *
V/
X
X  _EMPTY = _NOTCHAR,`09`09/* _EMPTY is a terminal symbol that matches
X`09`09`09`09   the empty string. */
X
X  _BACKREF,`09`09`09/* _BACKREF is generated by \<digit>; it
X`09`09`09`09   it not completely handled.  If the scanner
X`09`09`09`09   detects a transition on backref, it returns
X`09`09`09`09   a kind of "semi-success" indicating that
X`09`09`09`09   the match will have to be verified with
X`09`09`09`09   a backtracking matcher. */
X
X  _BEGLINE,`09`09`09/* _BEGLINE is a terminal symbol that matches
X`09`09`09`09   the empty string if it is at the beginning
X`09`09`09`09   of a line. */
X
X  _ALLBEGLINE,`09`09`09/* _ALLBEGLINE is a terminal symbol that
X`09`09`09`09   matches the empty string if it is at the
X`09`09`09`09   beginning of a line; _ALLBEGLINE applies
X`09`09`09`09   to the entire regexp and can only occur
X`09`09`09`09   as the first token thereof.  _ALLBEGLINE
X`09`09`09`09   never appears in the parse tree; a _BEGLINE
X`09`09`09`09   is prepended with _CAT to the entire
X`09`09`09`09   regexp instead. */
X
X  _ENDLINE,`09`09`09/* _ENDLINE is a terminal symbol that matches
X`09`09`09`09   the empty string if it is at the end of
X`09`09`09`09   a line. */
X
X  _ALLENDLINE,`09`09`09/* _ALLENDLINE is to _ENDLINE as _ALLBEGLINE
X`09`09`09`09   is to _BEGLINE. */
X
X  _BEGWORD,`09`09`09/* _BEGWORD is a terminal symbol that matches
X`09`09`09`09   the empty string if it is at the beginning
X`09`09`09`09   of a word. */
X
X  _ENDWORD,`09`09`09/* _ENDWORD is a terminal symbol that matches
X`09`09`09`09   the empty string if it is at the end of
X`09`09`09`09   a word. */
X
X  _LIMWORD,`09`09`09/* _LIMWORD is a terminal symbol that matches
X`09`09`09`09   the empty string if it is at the beginning
X`09`09`09`09   or the end of a word. */
X
X  _NOTLIMWORD,`09`09`09/* _NOTLIMWORD is a terminal symbol that
X`09`09`09`09   matches the empty string if it is not at
X`09`09`09`09   the beginning or end of a word. */
X
X  _QMARK,`09`09`09/* _QMARK is an operator of one argument that
X`09`09`09`09   matches zero or one occurences of its
X`09`09`09`09   argument. */
X
X  _STAR,`09`09`09/* _STAR is an operator of one argument that
X`09`09`09`09   matches the Kleene closure (zero or more
X`09`09`09`09   occurrences) of its argument. */
X
X  _PLUS,`09`09`09/* _PLUS is an operator of one argument that
X`09`09`09`09   matches the positive closure (one or more
X`09`09`09`09   occurrences) of its argument. */
X
X  _CAT,`09`09`09`09/* _CAT is an operator of two arguments that
X`09`09`09`09   matches the concatenation of its
X`09`09`09`09   arguments.  _CAT is never returned by the
X`09`09`09`09   lexical analyzer. */
X
X  _OR,`09`09`09`09/* _OR is an operator of two arguments that
X`09`09`09`09   matches either of its arguments. */
X
X  _LPAREN,`09`09`09/* _LPAREN never appears in the parse tree,
+-+-+-+-+-+-+-+-  END  OF PART 4 +-+-+-+-+-+-+-+-
