From:	MERC::"uunet!WKUVX1.BITNET!FILESERV-Mgr" 12-JUN-1992 15:22:36.67
To:	galaxy::gleeve
CC:	
Subj:	GREP.02_OF_12

-+-+-+-+-+-+-+-+ START OF PART 2 -+-+-+-+-+-+-+-+
Xwith the Program (or with a work based on the Program) on a volume of
Xa storage or distribution medium does not bring the other work under
Xthe scope of this License.
X
X  3. You may copy and distribute the Program (or a work based on it,
Xunder Section 2) in object code or executable form under the terms of
XSections 1 and 2 above provided that you also do one of the following:
X
X    a) Accompany it with the complete corresponding machine-readable
X    source code, which must be distributed under the terms of Sections
X    1 and 2 above on a medium customarily used for software interchange; or,
X
X    b) Accompany it with a written offer, valid for at least three
X    years, to give any third party, for a charge no more than your
X    cost of physically performing source distribution, a complete
X    machine-readable copy of the corresponding source code, to be
X    distributed under the terms of Sections 1 and 2 above on a medium
X    customarily used for software interchange; or,
X
X    c) Accompany it with the information you received as to the offer
X    to distribute corresponding source code.  (This alternative is
X    allowed only for noncommercial distribution and only if you
X    received the program in object code or executable form with such
X    an offer, in accord with Subsection b above.)
X
XThe source code for a work means the preferred form of the work for
Xmaking modifications to it.  For an executable work, complete source
Xcode means all the source code for all modules it contains, plus any
Xassociated interface definition files, plus the scripts used to
Xcontrol compilation and installation of the executable.  However, as a
Xspecial exception, the source code distributed need not include
Xanything that is normally distributed (in either source or binary
Xform) with the major components (compiler, kernel, and so on) of the
Xoperating system on which the executable runs, unless that component
Xitself accompanies the executable.
X
XIf distribution of executable or object code is made by offering
Xaccess to copy from a designated place, then offering equivalent
Xaccess to copy the source code from the same place counts as
Xdistribution of the source code, even though third parties are not
Xcompelled to copy the source along with the object code.
X`0C
X  4. You may not copy, modify, sublicense, or distribute the Program
Xexcept as expressly provided under this License.  Any attempt
Xotherwise to copy, modify, sublicense or distribute the Program is
Xvoid, and will automatically terminate your rights under this License.
XHowever, parties who have received copies, or rights, from you under
Xthis License will not have their licenses terminated so long as such
Xparties remain in full compliance.
X
X  5. You are not required to accept this License, since you have not
Xsigned it.  However, nothing else grants you permission to modify or
Xdistribute the Program or its derivative works.  These actions are
Xprohibited by law if you do not accept this License.  Therefore, by
Xmodifying or distributing the Program (or any work based on the
XProgram), you indicate your acceptance of this License to do so, and
Xall its terms and conditions for copying, distributing or modifying
Xthe Program or works based on it.
X
X  6. Each time you redistribute the Program (or any work based on the
XProgram), the recipient automatically receives a license from the
Xoriginal licensor to copy, distribute or modify the Program subject to
Xthese terms and conditions.  You may not impose any further
Xrestrictions on the recipients' exercise of the rights granted herein.
XYou are not responsible for enforcing compliance by third parties to
Xthis License.
X
X  7. If, as a consequence of a court judgment or allegation of patent
Xinfringement or for any other reason (not limited to patent issues),
Xconditions are imposed on you (whether by court order, agreement or
Xotherwise) that contradict the conditions of this License, they do not
Xexcuse you from the conditions of this License.  If you cannot
Xdistribute so as to satisfy simultaneously your obligations under this
XLicense and any other pertinent obligations, then as a consequence you
Xmay not distribute the Program at all.  For example, if a patent
Xlicense would not permit royalty-free redistribution of the Program by
Xall those who receive copies directly or indirectly through you, then
Xthe only way you could satisfy both it and this License would be to
Xrefrain entirely from distribution of the Program.
X
XIf any portion of this section is held invalid or unenforceable under
Xany particular circumstance, the balance of the section is intended to
Xapply and the section as a whole is intended to apply in other
Xcircumstances.
X
XIt is not the purpose of this section to induce you to infringe any
Xpatents or other property right claims or to contest validity of any
Xsuch claims; this section has the sole purpose of protecting the
Xintegrity of the free software distribution system, which is
Ximplemented by public license practices.  Many people have made
Xgenerous contributions to the wide range of software distributed
Xthrough that system in reliance on consistent application of that
Xsystem; it is up to the author/donor to decide if he or she is willing
Xto distribute software through any other system and a licensee cannot
Ximpose that choice.
X
XThis section is intended to make thoroughly clear what is believed to
Xbe a consequence of the rest of this License.
X`0C
X  8. If the distribution and/or use of the Program is restricted in
Xcertain countries either by patents or by copyrighted interfaces, the
Xoriginal copyright holder who places the Program under this License
Xmay add an explicit geographical distribution limitation excluding
Xthose countries, so that distribution is permitted only in or among
Xcountries not thus excluded.  In such case, this License incorporates
Xthe limitation as if written in the body of this License.
X
X  9. The Free Software Foundation may publish revised and/or new versions
Xof the General Public License from time to time.  Such new versions will
Xbe similar in spirit to the present version, but may differ in detail to
Xaddress new problems or concerns.
X
XEach version is given a distinguishing version number.  If the Program
Xspecifies a version number of this License which applies to it and "any
Xlater version", you have the option of following the terms and conditions
Xeither of that version or of any later version published by the Free
XSoftware Foundation.  If the Program does not specify a version number of
Xthis License, you may choose any version ever published by the Free Software
XFoundation.
X
X  10. If you wish to incorporate parts of the Program into other free
Xprograms whose distribution conditions are different, write to the author
Xto ask for permission.  For software which is copyrighted by the Free
XSoftware Foundation, write to the Free Software Foundation; we sometimes
Xmake exceptions for this.  Our decision will be guided by the two goals
Xof preserving the free status of all derivatives of our free software and
Xof promoting the sharing and reuse of software generally.
X
X`09`09`09    NO WARRANTY
X
X  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
XFOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
XOTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
XPROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
XOR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
XMERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
XTO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
XPROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
XREPAIR OR CORRECTION.
X
X  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
XWILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
XREDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
XINCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
XOUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
XTO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
XYOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
XPROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
XPOSSIBILITY OF SUCH DAMAGES.
X
X`09`09     END OF TERMS AND CONDITIONS
X`0C
X`09Appendix: How to Apply These Terms to Your New Programs
X
X  If you develop a new program, and you want it to be of the greatest
Xpossible use to the public, the best way to achieve this is to make it
Xfree software which everyone can redistribute and change under these terms.
X
X  To do so, attach the following notices to the program.  It is safest
Xto attach them to the start of each source file to most effectively
Xconvey the exclusion of warranty; and each file should have at least
Xthe "copyright" line and a pointer to where the full notice is found.
X
X    <one line to give the program's name and a brief idea of what it does.>
X    Copyright (C) 19yy  <name of author>
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 of the License, or
X    (at your option) 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
XAlso add information on how to contact you by electronic and paper mail.
X
XIf the program is interactive, make it output a short notice like this
Xwhen it starts in an interactive mode:
X
X    Gnomovision version 69, Copyright (C) 19yy name of author
X    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `60show
V w'.
X    This is free software, and you are welcome to redistribute it
X    under certain conditions; type `60show c' for details.
X
XThe hypothetical commands `60show w' and `60show c' should show the appropri
Vate
Xparts of the General Public License.  Of course, the commands you use may
Xbe called something other than `60show w' and `60show c'; they could even be
Xmouse-clicks or menu items--whatever suits your program.
X
XYou should also get your employer (if you work as a programmer) or your
Xschool, if any, to sign a "copyright disclaimer" for the program, if
Xnecessary.  Here is a sample; alter the names:
X
X  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
X  `60Gnomovision' (which makes passes at compilers) written by James Hacker.
X
X  <signature of Ty Coon>, 1 April 1989
X  Ty Coon, President of Vice
X
XThis General Public License does not permit incorporating your program into
Xproprietary programs.  If your program is a subroutine library, you may
Xconsider it more useful to permit linking proprietary applications with the
Xlibrary.  If this is what you want to do, use the GNU Library General
XPublic License instead of this License.
$ CALL UNPACK [.GREP016]COPYING.;1 2085147919
$ create 'f'
X!++
X! MMS file for GNU e?grep
X!
X! Hunter Goatley
X!
X! Based on MMS file by Henrik Tougaard,  ht@datani.dk
X!--
X!
X!  Uncomment the following line to compile using GNU C
X!
X!GNU_C = TRUE
X
X
XMAKEFILE = DESCRIP.MMS
XLIBS = SYS$SHARE:VAXCRTL.EXE/SHARE
X
X.IFDEF GNU_C
XCC = GCC
XOPTIONS = GNU_CC:`5B000000`5DOPTIONS.OPT/OPTIONS
X.ELSE
XOPTIONS = GREP.OPT/OPTIONS
X.ENDIF
X
XCFLAGS = /NODEBUG
XLINKFLAGS = /NOTRACE/NODEBUG/NOMAP
X
XOBJS = shell_mung.obj, dfa.obj, regex.obj, getopt.obj, alloca.obj
XGOBJ = grep.obj
XEOBJ = egrep.obj
X
Xgrep : grep.exe, egrep.exe, grep.hlp
X`09!grep and egrep build complete
X
Xgrep.exe : $(OBJS), $(XALLOCOBJ), $(GOBJ), grep.opt
X`09$(LINK) $(LINKFLAGS) $(GOBJ), $(OBJS), $(OPTIONS)
X
Xgrep.opt : $(MAKEFILE)
X`09open/write opt grep.opt
X`09write opt "! GNU e?grep linker options file"
X      @ write opt "$(LIBS)"
X`09close opt
X
Xclean :
X`09delete/noconfirm grep.exe;*, egrep.*;*, *.obj;*, grep.hlp;
X
Xegrep.exe : $(OBJS), $(EOBJ), grep.opt
X`09$(LINK) $(LINKFLAGS) $(EOBJ), $(OBJS), $(OPTIONS)
X
Xgrep.hlp : grep.rnh
X`09RUNOFF GREP.RNH
X
Xegrep.obj : grep.c
X`09copy/nolog grep.c egrep.c
X`09$(CC) $(CFLAGS) /define=EGREP egrep.c
X`09delete/nolog/noconfirm egrep.c;*
X
Xdfa.obj egrep.obj grep.obj : dfa.h
Xegrep.obj grep.obj regex.obj : regex.h
$ CALL UNPACK [.GREP016]DESCRIP.MMS;1 1635401951
$ create 'f'
X/* dfa.c - determinisitic extended regexp routines for GNU
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   Modified July, 1988 by Arthur David Olson to assist BMG speedups  */
X`0C
X#include <stdio.h>
X#include <assert.h>
X
X#if defined(USG) `7C`7C defined(STDC_HEADERS) `7C`7C defined(VMS)
X#include <string.h>
X#ifndef index
X#define index strchr
X#endif
X#else
X#include <strings.h>
X#endif
X
X#include "dfa.h"
X
X#if __STDC__
Xtypedef void *ptr_t;
X#else
Xtypedef char *ptr_t;
X#endif
X
Xstatic void`09regmust();
X
Xstatic ptr_t
Xxcalloc(n, s)
X     int n;
X     size_t s;
X`7B
X  ptr_t r = calloc(n, s);
X
X  if (!r)
X    regerror("Memory exhausted");
X  return r;
X`7D
X
Xptr_t`09`09`09`09/* Not static, so alloca.o can use it.  */
Xxmalloc(n)
X     size_t n;
X`7B
X  ptr_t r = malloc(n);
X
X  assert(n != 0);
X  if (!r)
X    regerror("Memory exhausted");
X  return r;
X`7D
X
X#ifdef VMS
Xptr_t`09`09`09`09/* Not static, so shell_mung can use it. */
X#else
Xstatic ptr_t
X#endif
Xxrealloc(p, n)
X     ptr_t p;
X     size_t n;
X`7B
X  ptr_t r = realloc(p, n);
X
X  assert(n != 0);
X  if (!r)
X    regerror("Memory exhausted");
X  return r;
X`7D
X
X#define CALLOC(p, t, n) ((p) = (t *) xcalloc((n), sizeof (t)))
X#define MALLOC(p, t, n) ((p) = (t *) xmalloc((n) * sizeof (t)))
X#define REALLOC(p, t, n) ((p) = (t *) xrealloc((ptr_t) (p), (n) * sizeof (t)
V))
X
X/* Reallocate an array of type t if nalloc is too small for index. */
X#define REALLOC_IF_NECESSARY(p, t, nalloc, index) \
X  if ((index) >= (nalloc))`09`09`09  \
X    `7B`09`09`09`09`09`09  \
X      while ((index) >= (nalloc))`09`09  \
X`09(nalloc) *= 2;`09`09`09`09  \
X      REALLOC(p, t, nalloc);`09`09`09  \
X    `7D
X`0C
X#ifdef DEBUG
X#include <stdio.h>
X
Xstatic void
Xprtok(t)
X     _token t;
X`7B
X  char *s;
X
X  if (t < 0)
X    fprintf(stderr, "END");
X  else if (t < _NOTCHAR)
X    fprintf(stderr, "%c", t);
X  else
X    `7B
X      switch (t)
X`09`7B
X`09case _EMPTY: s = "EMPTY"; break;
X`09case _BACKREF: s = "BACKREF"; break;
X`09case _BEGLINE: s = "BEGLINE"; break;
X`09case _ALLBEGLINE: s = "ALLBEGLINE"; break;
X`09case _ENDLINE: s = "ENDLINE"; break;
X`09case _ALLENDLINE: s = "ALLENDLINE"; break;
X`09case _BEGWORD: s = "BEGWORD"; break;
X`09case _ENDWORD: s = "ENDWORD"; break;
X`09case _LIMWORD: s = "LIMWORD"; break;
X`09case _NOTLIMWORD: s = "NOTLIMWORD"; break;
X`09case _QMARK: s = "QMARK"; break;
X`09case _STAR: s = "STAR"; break;
X`09case _PLUS: s = "PLUS"; break;
X`09case _CAT: s = "CAT"; break;
X`09case _OR: s = "OR"; break;
X`09case _LPAREN: s = "LPAREN"; break;
X`09case _RPAREN: s = "RPAREN"; break;
X`09default: s = "SET"; break;
X`09`7D
X      fprintf(stderr, "%s", s);
X    `7D
X`7D
X#endif /* DEBUG */
X
X/* Stuff pertaining to charsets. */
X
Xstatic int
Xtstbit(b, c)
X     int b;
X     _charset c;
X`7B
X  return c`5Bb / INTBITS`5D & 1 << b % INTBITS;
X`7D
X
Xstatic void
Xsetbit(b, c)
X     int b;
X     _charset c;
X`7B
X  c`5Bb / INTBITS`5D `7C= 1 << b % INTBITS;
X`7D
X
Xstatic void
Xclrbit(b, c)
X     int b;
X     _charset c;
X`7B
X  c`5Bb / INTBITS`5D &= `7E(1 << b % INTBITS);
X`7D
X
Xstatic void
Xcopyset(src, dst)
X     const _charset src;
X     _charset dst;
X`7B
X  int i;
X
X  for (i = 0; i < _CHARSET_INTS; ++i)
X    dst`5Bi`5D = src`5Bi`5D;
X`7D
X
Xstatic void
Xzeroset(s)
X     _charset s;
X`7B
X  int i;
X
X  for (i = 0; i < _CHARSET_INTS; ++i)
X    s`5Bi`5D = 0;
X`7D
X
Xstatic void
Xnotset(s)
X     _charset s;
X`7B
X  int i;
X
X  for (i = 0; i < _CHARSET_INTS; ++i)
X    s`5Bi`5D = `7Es`5Bi`5D;
X`7D
X
Xstatic int
Xequal(s1, s2)
X     const _charset s1;
X     const _charset s2;
X`7B
X  int i;
X
X  for (i = 0; i < _CHARSET_INTS; ++i)
X    if (s1`5Bi`5D != s2`5Bi`5D)
X      return 0;
X  return 1;
X`7D
X`0C
X/* A pointer to the current regexp is kept here during parsing. */
Xstatic struct regexp *reg;
X
X/* Find the index of charset s in reg->charsets, or allocate a new charset.
V */
Xstatic int
Xcharset_index(s)
X     const _charset s;
X`7B
X  int i;
X
X  for (i = 0; i < reg->cindex; ++i)
X    if (equal(s, reg->charsets`5Bi`5D))
X      return i;
X  REALLOC_IF_NECESSARY(reg->charsets, _charset, reg->calloc, reg->cindex);
X  ++reg->cindex;
X  copyset(s, reg->charsets`5Bi`5D);
X  return i;
X`7D
X
X/* Syntax bits controlling the behavior of the lexical analyzer. */
Xstatic syntax_bits, syntax_bits_set;
X
X/* Flag for case-folding letters into sets. */
Xstatic case_fold;
X
X/* Entry point to set syntax options. */
Xvoid
Xregsyntax(bits, fold)
X     int bits;
X     int fold;
X`7B
X  syntax_bits_set = 1;
X  syntax_bits = bits;
X  case_fold = fold;
X`7D
X
X/* Lexical analyzer. */
Xstatic const char *lexstart;`09/* Pointer to beginning of input string. */
Xstatic const char *lexptr;`09/* Pointer to next input character. */
Xstatic lexleft;`09`09`09/* Number of characters remaining. */
Xstatic caret_allowed;`09`09/* True if backward context allows `5E
X`09`09`09`09   (meaningful only if RE_CONTEXT_INDEP_OPS
X`09`09`09`09   is turned off). */
Xstatic closure_allowed;`09`09/* True if backward context allows closures
X`09`09`09`09   (meaningful only if RE_CONTEXT_INDEP_OPS
X`09`09`09`09   is turned off). */
X
X/* Note that characters become unsigned here. */
X#define FETCH(c, eoferr)   `09      \
X  `7B`09`09`09   `09      \
X    if (! lexleft)`09   `09      \
X      if (eoferr)`09   `09      \
X`09regerror(eoferr);  `09      \
X      else`09`09   `09      \
X`09return _END;`09   `09      \
X    (c) = (unsigned char) *lexptr++;  \
X    --lexleft;`09`09   `09      \
X  `7D
X
Xstatic _token
Xlex()
X`7B
X  _token c, c2;
X  int invert;
X  _charset cset;
X
X  FETCH(c, (char *) 0);
X  switch (c)
X    `7B
X    case '`5E':
X      if (! (syntax_bits & RE_CONTEXT_INDEP_OPS)
X`09  && (!caret_allowed `7C`7C
X`09      (syntax_bits & RE_TIGHT_VBAR) && lexptr - 1 != lexstart))
X`09goto normal_char;
X      caret_allowed = 0;
X      return syntax_bits & RE_TIGHT_VBAR ? _ALLBEGLINE : _BEGLINE;
X
X    case '$':
X      if (syntax_bits & RE_CONTEXT_INDEP_OPS `7C`7C !lexleft
X`09  `7C`7C (! (syntax_bits & RE_TIGHT_VBAR)
X`09      && ((syntax_bits & RE_NO_BK_PARENS
X`09`09   ? lexleft > 0 && *lexptr == ')'
X`09`09   : lexleft > 1 && *lexptr == '\\' && lexptr`5B1`5D == ')')
X`09`09  `7C`7C (syntax_bits & RE_NO_BK_VBAR
X`09`09      ? lexleft > 0 && *lexptr == '`7C'
X`09`09      : lexleft > 1 && *lexptr == '\\' && lexptr`5B1`5D == '`7C'))))
X`09return syntax_bits & RE_TIGHT_VBAR ? _ALLENDLINE : _ENDLINE;
X      goto normal_char;
X
X    case '\\':
X      FETCH(c, "Unfinished \\ quote");
X      switch (c)
X`09`7B
X`09case '1':
X`09case '2':
X`09case '3':
X`09case '4':
X`09case '5':
X`09case '6':
X`09case '7':
X`09case '8':
X`09case '9':
X`09  caret_allowed = 0;
X`09  closure_allowed = 1;
X`09  return _BACKREF;
X
X`09case '<':
X`09  caret_allowed = 0;
X`09  return _BEGWORD;
X
X`09case '>':
X`09  caret_allowed = 0;
X`09  return _ENDWORD;
X
X`09case 'b':
X`09  caret_allowed = 0;
X`09  return _LIMWORD;
X
X`09case 'B':
X`09  caret_allowed = 0;
X`09  return _NOTLIMWORD;
X
X`09case 'w':
X`09case 'W':
X`09  zeroset(cset);
X`09  for (c2 = 0; c2 < _NOTCHAR; ++c2)
X`09    if (ISALNUM(c2))
X`09      setbit(c2, cset);
X`09  if (c == 'W')
X`09    notset(cset);
X`09  caret_allowed = 0;
X`09  closure_allowed = 1;
X`09  return _SET + charset_index(cset);
X
X`09case '?':
X`09  if (syntax_bits & RE_BK_PLUS_QM)
X`09    goto qmark;
X`09  goto normal_char;
X
X`09case '+':
X`09  if (syntax_bits & RE_BK_PLUS_QM)
X`09    goto plus;
X`09  goto normal_char;
X
X`09case '`7C':
X`09  if (! (syntax_bits & RE_NO_BK_VBAR))
X`09    goto or;
X`09  goto normal_char;
X
X`09case '(':
X`09  if (! (syntax_bits & RE_NO_BK_PARENS))
X`09    goto lparen;
X`09  goto normal_char;
X
X`09case ')':
X`09  if (! (syntax_bits & RE_NO_BK_PARENS))
X`09    goto rparen;
X`09  goto normal_char;
X
X`09default:
X`09  goto normal_char;
X`09`7D
X
X    case '?':
X      if (syntax_bits & RE_BK_PLUS_QM)
X`09goto normal_char;
X    qmark:
X      if (! (syntax_bits & RE_CONTEXT_INDEP_OPS) && !closure_allowed)
X`09goto normal_char;
X      return _QMARK;
X
X    case '*':
X      if (! (syntax_bits & RE_CONTEXT_INDEP_OPS) && !closure_allowed)
X`09goto normal_char;
X      return _STAR;
X
X    case '+':
X      if (syntax_bits & RE_BK_PLUS_QM)
X`09goto normal_char;
X    plus:
X      if (! (syntax_bits & RE_CONTEXT_INDEP_OPS) && !closure_allowed)
X`09goto normal_char;
X      return _PLUS;
X
X    case '`7C':
X      if (! (syntax_bits & RE_NO_BK_VBAR))
X`09goto normal_char;
X    or:
X      caret_allowed = 1;
X      closure_allowed = 0;
X      return _OR;
X
X    case '\n':
X      if (! (syntax_bits & RE_NEWLINE_OR))
X`09goto normal_char;
X      goto or;
X
X    case '(':
X      if (! (syntax_bits & RE_NO_BK_PARENS))
X`09goto normal_char;
X    lparen:
X      caret_allowed = 1;
X      closure_allowed = 0;
X      return _LPAREN;
X
X    case ')':
X      if (! (syntax_bits & RE_NO_BK_PARENS))
X`09goto normal_char;
X    rparen:
X      caret_allowed = 0;
X      closure_allowed = 1;
X      return _RPAREN;
X
X    case '.':
X      zeroset(cset);
X      notset(cset);
X      clrbit('\n', cset);
X      caret_allowed = 0;
X      closure_allowed = 1;
X      return _SET + charset_index(cset);
X
X    case '`5B':
X      zeroset(cset);
X      FETCH(c, "Unbalanced `5B");
X      if (c == '`5E')
X`09`7B
X`09  FETCH(c, "Unbalanced `5B");
X`09  invert = 1;
X`09`7D
X      else
X`09invert = 0;
X      do
X`09`7B
X`09  FETCH(c2, "Unbalanced `5B");
X`09  if (c2 == '-')
X`09    `7B
X`09      FETCH(c2, "Unbalanced `5B");
X`09      while (c <= c2)
X`09`09`7B
X`09`09  setbit(c, cset);
X`09`09  if (case_fold)
X`09`09    if (ISUPPER(c))
X`09`09      setbit(tolower(c), cset);
X`09`09    else if (ISLOWER(c))
X`09`09      setbit(toupper(c), cset);
X`09`09  ++c;
X`09`09`7D
X`09      FETCH(c, "Unbalanced `5B");
X`09    `7D
X`09  else
X`09    `7B
X`09      setbit(c, cset);
X`09      if (case_fold)
X`09`09if (ISUPPER(c))
X`09`09  setbit(tolower(c), cset);
X`09`09else if (ISLOWER(c))
X`09`09  setbit(toupper(c), cset);
X`09      c = c2;
X`09    `7D
X`09`7D
X      while (c != '`5D');
X      if (invert)
X`09notset(cset);
X      caret_allowed = 0;
X      closure_allowed = 1;
X      return _SET + charset_index(cset);
X
X    default:
X    normal_char:
X      caret_allowed = 0;
X      closure_allowed = 1;
X      if (case_fold && ISALPHA(c))
X`09`7B
X`09  zeroset(cset);
X`09  if (isupper(c))
X`09    c = tolower(c);
X`09  setbit(c, cset);
X`09  setbit(toupper(c), cset);
X`09  return _SET + charset_index(cset);
X`09`7D
X      return c;
X    `7D
X`7D
X`0C
X/* Recursive descent parser for regular expressions. */
X
Xstatic _token tok;`09`09/* Lookahead token. */
Xstatic depth;`09`09`09/* Current depth of a hypothetical stack
X`09`09`09`09   holding deferred productions.  This is
X`09`09`09`09   used to determine the depth that will be
X`09`09`09`09   required of the real stack later on in
X`09`09`09`09   reganalyze(). */
X
X/* Add the given token to the parse tree, maintaining the depth count and
X   updating the maximum depth if necessary. */
Xstatic void
Xaddtok(t)
X     _token t;
X`7B
X  REALLOC_IF_NECESSARY(reg->tokens, _token, reg->talloc, reg->tindex);
X  reg->tokens`5Breg->tindex++`5D = t;
X
X  switch (t)
X    `7B
X    case _QMARK:
X    case _STAR:
X    case _PLUS:
X      break;
X
X    case _CAT:
X    case _OR:
X      --depth;
X      break;
X
X    default:
X      ++reg->nleaves;
X    case _EMPTY:
X      ++depth;
X      break;
X    `7D
X  if (depth > reg->depth)
X    reg->depth = depth;
X`7D
X
X/* The grammar understood by the parser is as follows.
X
X   start:
X     regexp
X     _ALLBEGLINE regexp
X     regexp _ALLENDLINE
X     _ALLBEGLINE regexp _ALLENDLINE
X
X   regexp:
X     regexp _OR branch
X     branch
X
X   branch:
X     branch closure
X     closure
X
X   closure:
X     closure _QMARK
X     closure _STAR
X     closure _PLUS
X     atom
X
X   atom:
X     <normal character>
X     _SET
X     _BACKREF
X     _BEGLINE
X     _ENDLINE
X     _BEGWORD
X     _ENDWORD
X     _LIMWORD
X     _NOTLIMWORD
X     <empty>
X
X   The parser builds a parse tree in postfix form in an array of tokens. */
X
X#if __STDC__
Xstatic void regexp(void);
X#else
Xstatic void regexp();
X#endif
X
Xstatic void
Xatom()
X`7B
X  if (tok >= 0 && tok < _NOTCHAR `7C`7C tok >= _SET `7C`7C tok == _BACKREF
X      `7C`7C tok == _BEGLINE `7C`7C tok == _ENDLINE `7C`7C tok == _BEGWORD
X      `7C`7C tok == _ENDWORD `7C`7C tok == _LIMWORD `7C`7C tok == _NOTLIMWOR
VD)
X    `7B
X      addtok(tok);
X      tok = lex();
X    `7D
X  else if (tok == _LPAREN)
X    `7B
X      tok = lex();
X      regexp();
X      if (tok != _RPAREN)
X`09regerror("Unbalanced (");
X      tok = lex();
X    `7D
X  else
X    addtok(_EMPTY);
X`7D
X
Xstatic void
Xclosure()
X`7B
X  atom();
X  while (tok == _QMARK `7C`7C tok == _STAR `7C`7C tok == _PLUS)
X    `7B
X      addtok(tok);
X      tok = lex();
X    `7D
X`7D
X
Xstatic void
Xbranch()
X`7B
X  closure();
X  while (tok != _RPAREN && tok != _OR && tok != _ALLENDLINE && tok >= 0)
X    `7B
X      closure();
X      addtok(_CAT);
X    `7D
X`7D
X
Xstatic void
Xregexp()
X`7B
X  branch();
X  while (tok == _OR)
X    `7B
X      tok = lex();
X      branch();
X      addtok(_OR);
X    `7D
X`7D
X
X/* Main entry point for the parser.  S is a string to be parsed, len is the
X   length of the string, so s can include NUL characters.  R is a pointer to
X   the struct regexp to parse into. */
Xvoid
Xregparse(s, len, r)
X     const char *s;
X     size_t len;
X     struct regexp *r;
X`7B
X  reg = r;
X  lexstart = lexptr = s;
X  lexleft = len;
X  caret_allowed = 1;
X  closure_allowed = 0;
X
X  if (! syntax_bits_set)
X    regerror("No syntax specified");
X
X  tok = lex();
X  depth = r->depth;
X
X  if (tok == _ALLBEGLINE)
X    `7B
X      addtok(_BEGLINE);
X      tok = lex();
X      regexp();
X      addtok(_CAT);
X    `7D
X  else
X    regexp();
X
X  if (tok == _ALLENDLINE)
X    `7B
X      addtok(_ENDLINE);
X      addtok(_CAT);
X      tok = lex();
X    `7D
X
X  if (tok != _END)
X    regerror("Unbalanced )");
X
X  addtok(_END - r->nregexps);
X  addtok(_CAT);
X
X  if (r->nregexps)
X    addtok(_OR);
X
X  ++r->nregexps;
X`7D
X`0C
X/* Some primitives for operating on sets of positions. */
X
X/* Copy one set to another; the destination must be large enough. */
Xstatic void
Xcopy(src, dst)
X     const _position_set *src;
X     _position_set *dst;
X`7B
X  int i;
X
X  for (i = 0; i < src->nelem; ++i)
X    dst->elems`5Bi`5D = src->elems`5Bi`5D;
X  dst->nelem = src->nelem;
X`7D
X
X/* Insert a position in a set.  Position sets are maintained in sorted
X   order according to index.  If position already exists in the set with
X   the same index then their constraints are logically or'd together.
X   S->elems must point to an array large enough to hold the resulting set. *
V/
Xstatic void
Xinsert(p, s)
X     _position p;
X     _position_set *s;
X`7B
X  int i;
X  _position t1, t2;
X
X  for (i = 0; i < s->nelem && p.index < s->elems`5Bi`5D.index; ++i)
X    ;
+-+-+-+-+-+-+-+-  END  OF PART 2 +-+-+-+-+-+-+-+-
