src/egrep.c

   1 /* A Bison parser, made by GNU Bison 2.4.2.  */
   2
   3 /* Skeleton implementation for Bison's Yacc-like parsers in C
   4
   5       Copyright (C) 1984, 1989-1990, 2000-2006, 2009-2010 Free Software
   6    Foundation, Inc.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 /* As a special exception, you may create a larger work that contains
  22    part or all of the Bison parser skeleton and distribute that work
  23    under terms of your choice, so long as that work isn't itself a
  24    parser generator using the skeleton or a modified version thereof
  25    as a parser skeleton.  Alternatively, if you modify or redistribute
  26    the parser skeleton itself, you may (at your option) remove this
  27    special exception, which will cause the skeleton and the resulting
  28    Bison output files to be licensed under the GNU General Public
  29    License without this special exception.
  30
  31    This special exception was added by the Free Software Foundation in
  32    version 2.2 of Bison.  */
  33
  34 /* C LALR(1) parser skeleton written by Richard Stallman, by
  35    simplifying the original so-called "semantic" parser.  */
  36
  37 /* All symbols defined below should begin with yy or YY, to avoid
  38    infringing on user name space.  This should be done even for local
  39    variables, as they might otherwise be expanded by user macros.
  40    There are some unavoidable exceptions within include files to
  41    define necessary library symbols; they are noted "INFRINGES ON
  42    USER NAME SPACE" below.  */
  43
  44 /* Identify Bison output.  */
  45 #define YYBISON 1
  46
  47 /* Bison version.  */
  48 #define YYBISON_VERSION "2.4.2"
  49
  50 /* Skeleton name.  */
  51 #define YYSKELETON_NAME "yacc.c"
  52
  53 /* Pure parsers.  */
  54 #define YYPURE 0
  55
  56 /* Push parsers.  */
  57 #define YYPUSH 0
  58
  59 /* Pull parsers.  */
  60 #define YYPULL 1
  61
  62 /* Using locations.  */
  63 #define YYLSP_NEEDED 0
  64
  65
  66
  67 /* Copy the first part of user declarations.  */
  68
  69 /* Line 189 of yacc.c  */
  70 #line 1 "egrep.y"
  71
  72 /*===========================================================================
  73  Copyright (c) 1998-2000, The Santa Cruz Operation
  74  All rights reserved.
  75
  76  Redistribution and use in source and binary forms, with or without
  77  modification, are permitted provided that the following conditions are met:
  78
  79  *Redistributions of source code must retain the above copyright notice,
  80  this list of conditions and the following disclaimer.
  81
  82  *Redistributions in binary form must reproduce the above copyright notice,
  83  this list of conditions and the following disclaimer in the documentation
  84  and/or other materials provided with the distribution.
  85
  86  *Neither name of The Santa Cruz Operation nor the names of its contributors
  87  may be used to endorse or promote products derived from this software
  88  without specific prior written permission.
  89
  90  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS
  91  IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  92  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  93  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  94  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  95  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  96  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  97  INTERRUPTION)
  98  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  99  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 100  OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
 101  DAMAGE.
 102  =========================================================================*/
 103
 104 /* $Id: egrep.y,v 1.11 2006/04/21 10:45:48 broeker Exp $ */
 105
 106 /*
 107  * egrep -- fine lines containing a regular expression
 108  */
 109
 110 /* Line 189 of yacc.c  */
 111 #line 47 "egrep.y"
 112
 113 #include "global.h"
 114 #include <ctype.h>
 115 #include <stdio.h>
 116
 117 #include <setjmp.h>     /* jmp_buf */
 118
 119 #define nextch()        (*input++)
 120
 121 #define MAXLIN 350
 122 #define MAXPOS 4000
 123 #define NCHARS 256
 124 #define NSTATES 128
 125 #define FINAL -1
 126 static  char gotofn[NSTATES][NCHARS];
 127 static  int state[NSTATES];
 128 static  char out[NSTATES];
 129 static  unsigned int line;
 130 static  int name[MAXLIN];
 131 static  unsigned int left[MAXLIN];
 132 static  unsigned int right[MAXLIN];
 133 static  unsigned int parent[MAXLIN];
 134 static  int foll[MAXLIN];
 135 static  int positions[MAXPOS];
 136 static  char chars[MAXLIN];
 137 static  int nxtpos;
 138 static  int nxtchar;
 139 static  int tmpstat[MAXLIN];
 140 static  int initstat[MAXLIN];
 141 static  int xstate;
 142 static  int count;
 143 static  int icount;
 144 static  char *input;
 145 static  long lnum;
 146 static  int iflag;
 147 static  jmp_buf env;    /* setjmp/longjmp buffer */
 148 static  char *message;  /* error message */
 149
 150 /* Internal prototypes: */
 151 static  void cfoll(int v);
 152 static  void cgotofn(void);
 153 static  int cstate(int v);
 154 static  int member(int symb, int set, int torf);
 155 static  int notin(int n);
 156 static  void synerror(void);
 157 static  void overflo(void);
 158 static  void add(int *array, int n);
 159 static  void follow(unsigned int v);
 160 static  int unary(int x, int d);
 161 static  int node(int x, int l, int r);
 162 static  unsigned int cclenter(int x);
 163 static  unsigned int enter(int x);
 164
 165 static int yylex(void);
 166 static int yyerror(char *);
 167
 168
 169 /* Line 189 of yacc.c  */
 170 #line 171 "egrep.c"
 171
 172 /* Enabling traces.  */
 173 #ifndef YYDEBUG
 174 # define YYDEBUG 0
 175 #endif
 176
 177 /* Enabling verbose error messages.  */
 178 #ifdef YYERROR_VERBOSE
 179 # undef YYERROR_VERBOSE
 180 # define YYERROR_VERBOSE 1
 181 #else
 182 # define YYERROR_VERBOSE 0
 183 #endif
 184
 185 /* Enabling the token table.  */
 186 #ifndef YYTOKEN_TABLE
 187 # define YYTOKEN_TABLE 0
 188 #endif
 189
 190
 191 /* Tokens.  */
 192 #ifndef YYTOKENTYPE
 193 # define YYTOKENTYPE
 194    /* Put the tokens into the symbol table, so that GDB and other debuggers
 195       know about them.  */
 196    enum yytokentype {
 197      CHAR = 258,
 198      DOT = 259,
 199      CCL = 260,
 200      NCCL = 261,
 201      OR = 262,
 202      CAT = 263,
 203      STAR = 264,
 204      PLUS = 265,
 205      QUEST = 266
 206    };
 207 #endif
 208 /* Tokens.  */
 209 #define CHAR 258
 210 #define DOT 259
 211 #define CCL 260
 212 #define NCCL 261
 213 #define OR 262
 214 #define CAT 263
 215 #define STAR 264
 216 #define PLUS 265
 217 #define QUEST 266
 218
 219
 220
 221
 222 #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
 223 typedef int YYSTYPE;
 224 # define YYSTYPE_IS_TRIVIAL 1
 225 # define yystype YYSTYPE /* obsolescent; will be withdrawn */
 226 # define YYSTYPE_IS_DECLARED 1
 227 #endif
 228
 229
 230 /* Copy the second part of user declarations.  */
 231
 232
 233 /* Line 264 of yacc.c  */
 234 #line 235 "egrep.c"
 235
 236 #ifdef short
 237 # undef short
 238 #endif
 239
 240 #ifdef YYTYPE_UINT8
 241 typedef YYTYPE_UINT8 yytype_uint8;
 242 #else
 243 typedef unsigned char yytype_uint8;
 244 #endif
 245
 246 #ifdef YYTYPE_INT8
 247 typedef YYTYPE_INT8 yytype_int8;
 248 #elif (defined __STDC__ || defined __C99__FUNC__ \
 249      || defined __cplusplus || defined _MSC_VER)
 250 typedef signed char yytype_int8;
 251 #else
 252 typedef short int yytype_int8;
 253 #endif
 254
 255 #ifdef YYTYPE_UINT16
 256 typedef YYTYPE_UINT16 yytype_uint16;
 257 #else
 258 typedef unsigned short int yytype_uint16;
 259 #endif
 260
 261 #ifdef YYTYPE_INT16
 262 typedef YYTYPE_INT16 yytype_int16;
 263 #else
 264 typedef short int yytype_int16;
 265 #endif
 266
 267 #ifndef YYSIZE_T
 268 # ifdef __SIZE_TYPE__
 269 #  define YYSIZE_T __SIZE_TYPE__
 270 # elif defined size_t
 271 #  define YYSIZE_T size_t
 272 # elif ! defined YYSIZE_T && (defined __STDC__ || defined __C99__FUNC__ \
 273      || defined __cplusplus || defined _MSC_VER)
 274 #  include <stddef.h> /* INFRINGES ON USER NAME SPACE */
 275 #  define YYSIZE_T size_t
 276 # else
 277 #  define YYSIZE_T unsigned int
 278 # endif
 279 #endif
 280
 281 #define YYSIZE_MAXIMUM ((YYSIZE_T) -1)
 282
 283 #ifndef YY_
 284 # if defined YYENABLE_NLS && YYENABLE_NLS
 285 #  if ENABLE_NLS
 286 #   include <libintl.h> /* INFRINGES ON USER NAME SPACE */
 287 #   define YY_(msgid) dgettext ("bison-runtime", msgid)
 288 #  endif
 289 # endif
 290 # ifndef YY_
 291 #  define YY_(msgid) msgid
 292 # endif
 293 #endif
 294
 295 /* Suppress unused-variable warnings by "using" E.  */
 296 #if ! defined lint || defined __GNUC__
 297 # define YYUSE(e) ((void) (e))
 298 #else
 299 # define YYUSE(e) /* empty */
 300 #endif
 301
 302 /* Identity function, used to suppress warnings about constant conditions.  */
 303 #ifndef lint
 304 # define YYID(n) (n)
 305 #else
 306 #if (defined __STDC__ || defined __C99__FUNC__ \
 307      || defined __cplusplus || defined _MSC_VER)
 308 static int
 309 YYID (int yyi)
 310 #else
 311 static int
 312 YYID (yyi)
 313     int yyi;
 314 #endif
 315 {
 316   return yyi;
 317 }
 318 #endif
 319
 320 #if ! defined yyoverflow || YYERROR_VERBOSE
 321
 322 /* The parser invokes alloca or malloc; define the necessary symbols.  */
 323
 324 # ifdef YYSTACK_USE_ALLOCA
 325 #  if YYSTACK_USE_ALLOCA
 326 #   ifdef __GNUC__
 327 #    define YYSTACK_ALLOC __builtin_alloca
 328 #   elif defined __BUILTIN_VA_ARG_INCR
 329 #    include <alloca.h> /* INFRINGES ON USER NAME SPACE */
 330 #   elif defined _AIX
 331 #    define YYSTACK_ALLOC __alloca
 332 #   elif defined _MSC_VER
 333 #    include <malloc.h> /* INFRINGES ON USER NAME SPACE */
 334 #    define alloca _alloca
 335 #   else
 336 #    define YYSTACK_ALLOC alloca
 337 #    if ! defined _ALLOCA_H && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \
 338      || defined __cplusplus || defined _MSC_VER)
 339 #     include <stdlib.h> /* INFRINGES ON USER NAME SPACE */
 340 #     ifndef _STDLIB_H
 341 #      define _STDLIB_H 1
 342 #     endif
 343 #    endif
 344 #   endif
 345 #  endif
 346 # endif
 347
 348 # ifdef YYSTACK_ALLOC
 349    /* Pacify GCC's `empty if-body' warning.  */
 350 #  define YYSTACK_FREE(Ptr) do { /* empty */; } while (YYID (0))
 351 #  ifndef YYSTACK_ALLOC_MAXIMUM
 352     /* The OS might guarantee only one guard page at the bottom of the stack,
 353        and a page size can be as small as 4096 bytes.  So we cannot safely
 354        invoke alloca (N) if N exceeds 4096.  Use a slightly smaller number
 355        to allow for a few compiler-allocated temporary stack slots.  */
 356 #   define YYSTACK_ALLOC_MAXIMUM 4032 /* reasonable circa 2006 */
 357 #  endif
 358 # else
 359 #  define YYSTACK_ALLOC YYMALLOC
 360 #  define YYSTACK_FREE YYFREE
 361 #  ifndef YYSTACK_ALLOC_MAXIMUM
 362 #   define YYSTACK_ALLOC_MAXIMUM YYSIZE_MAXIMUM
 363 #  endif
 364 #  if (defined __cplusplus && ! defined _STDLIB_H \
 365        && ! ((defined YYMALLOC || defined malloc) \
 366              && (defined YYFREE || defined free)))
 367 #   include <stdlib.h> /* INFRINGES ON USER NAME SPACE */
 368 #   ifndef _STDLIB_H
 369 #    define _STDLIB_H 1
 370 #   endif
 371 #  endif
 372 #  ifndef YYMALLOC
 373 #   define YYMALLOC malloc
 374 #   if ! defined malloc && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \
 375      || defined __cplusplus || defined _MSC_VER)
 376 void *malloc (YYSIZE_T); /* INFRINGES ON USER NAME SPACE */
 377 #   endif
 378 #  endif
 379 #  ifndef YYFREE
 380 #   define YYFREE free
 381 #   if ! defined free && ! defined _STDLIB_H && (defined __STDC__ || defined __C99__FUNC__ \
 382      || defined __cplusplus || defined _MSC_VER)
 383 void free (void *); /* INFRINGES ON USER NAME SPACE */
 384 #   endif
 385 #  endif
 386 # endif
 387 #endif /* ! defined yyoverflow || YYERROR_VERBOSE */
 388
 389
 390 #if (! defined yyoverflow \
 391      && (! defined __cplusplus \
 392          || (defined YYSTYPE_IS_TRIVIAL && YYSTYPE_IS_TRIVIAL)))
 393
 394 /* A type that is properly aligned for any stack member.  */
 395 union yyalloc
 396 {
 397   yytype_int16 yyss_alloc;
 398   YYSTYPE yyvs_alloc;
 399 };
 400
 401 /* The size of the maximum gap between one aligned stack and the next.  */
 402 # define YYSTACK_GAP_MAXIMUM (sizeof (union yyalloc) - 1)
 403
 404 /* The size of an array large to enough to hold all stacks, each with
 405    N elements.  */
 406 # define YYSTACK_BYTES(N) \
 407      ((N) * (sizeof (yytype_int16) + sizeof (YYSTYPE)) \
 408       + YYSTACK_GAP_MAXIMUM)
 409
 410 /* Copy COUNT objects from FROM to TO.  The source and destination do
 411    not overlap.  */
 412 # ifndef YYCOPY
 413 #  if defined __GNUC__ && 1 < __GNUC__
 414 #   define YYCOPY(To, From, Count) \
 415       __builtin_memcpy (To, From, (Count) * sizeof (*(From)))
 416 #  else
 417 #   define YYCOPY(To, From, Count)              \
 418       do                                        \
 419         {                                       \
 420           YYSIZE_T yyi;                         \
 421           for (yyi = 0; yyi < (Count); yyi++)   \
 422             (To)[yyi] = (From)[yyi];            \
 423         }                                       \
 424       while (YYID (0))
 425 #  endif
 426 # endif
 427
 428 /* Relocate STACK from its old location to the new one.  The
 429    local variables YYSIZE and YYSTACKSIZE give the old and new number of
 430    elements in the stack, and YYPTR gives the new location of the
 431    stack.  Advance YYPTR to a properly aligned location for the next
 432    stack.  */
 433 # define YYSTACK_RELOCATE(Stack_alloc, Stack)                           \
 434     do                                                                  \
 435       {                                                                 \
 436         YYSIZE_T yynewbytes;                                            \
 437         YYCOPY (&yyptr->Stack_alloc, Stack, yysize);                    \
 438         Stack = &yyptr->Stack_alloc;                                    \
 439         yynewbytes = yystacksize * sizeof (*Stack) + YYSTACK_GAP_MAXIMUM; \
 440         yyptr += yynewbytes / sizeof (*yyptr);                          \
 441       }                                                                 \
 442     while (YYID (0))
 443
 444 #endif
 445
 446 /* YYFINAL -- State number of the termination state.  */
 447 #define YYFINAL  6
 448 /* YYLAST -- Last index in YYTABLE.  */
 449 #define YYLAST   108
 450
 451 /* YYNTOKENS -- Number of terminals.  */
 452 #define YYNTOKENS  14
 453 /* YYNNTS -- Number of nonterminals.  */
 454 #define YYNNTS  5
 455 /* YYNRULES -- Number of rules.  */
 456 #define YYNRULES  18
 457 /* YYNRULES -- Number of states.  */
 458 #define YYNSTATES  25
 459
 460 /* YYTRANSLATE(YYLEX) -- Bison symbol number corresponding to YYLEX.  */
 461 #define YYUNDEFTOK  2
 462 #define YYMAXUTOK   266
 463
 464 #define YYTRANSLATE(YYX)                                                \
 465   ((unsigned int) (YYX) <= YYMAXUTOK ? yytranslate[YYX] : YYUNDEFTOK)
 466
 467 /* YYTRANSLATE[YYLEX] -- Bison symbol number corresponding to YYLEX.  */
 468 static const yytype_uint8 yytranslate[] =
 469 {
 470        0,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 471        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 472        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 473        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 474       12,    13,     2,     2,     2,     2,     2,     2,     2,     2,
 475        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 476        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 477        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 478        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 479        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 480        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 481        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 482        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 483        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 484        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 485        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 486        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 487        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 488        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 489        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 490        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 491        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 492        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 493        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 494        2,     2,     2,     2,     2,     2,     2,     2,     2,     2,
 495        2,     2,     2,     2,     2,     2,     1,     2,     3,     4,
 496        5,     6,     7,     8,     9,    10,    11
 497 };
 498
 499 #if YYDEBUG
 500 /* YYPRHS[YYN] -- Index of the first RHS symbol of rule number YYN in
 501    YYRHS.  */
 502 static const yytype_uint8 yyprhs[] =
 503 {
 504        0,     0,     3,     5,     8,    13,    17,    21,    22,    24,
 505       26,    28,    30,    34,    37,    40,    43,    46,    50
 506 };
 507
 508 /* YYRHS -- A `-1'-separated list of the rules' RHS.  */
 509 static const yytype_int8 yyrhs[] =
 510 {
 511       15,     0,    -1,    16,    -1,    17,    18,    -1,     7,    17,
 512       18,     7,    -1,     7,    17,    18,    -1,    17,    18,     7,
 513       -1,    -1,     3,    -1,     4,    -1,     5,    -1,     6,    -1,
 514       18,     7,    18,    -1,    18,    18,    -1,    18,     9,    -1,
 515       18,    10,    -1,    18,    11,    -1,    12,    18,    13,    -1,
 516        1,    -1
 517 };
 518
 519 /* YYRLINE[YYN] -- source line where rule number YYN was defined.  */
 520 static const yytype_uint8 yyrline[] =
 521 {
 522        0,   105,   105,   110,   112,   114,   116,   120,   123,   125,
 523      127,   129,   133,   135,   137,   139,   141,   143,   145
 524 };
 525 #endif
 526
 527 #if YYDEBUG || YYERROR_VERBOSE || YYTOKEN_TABLE
 528 /* YYTNAME[SYMBOL-NUM] -- String name of the symbol SYMBOL-NUM.
 529    First, the terminals, then, starting at YYNTOKENS, nonterminals.  */
 530 static const char *const yytname[] =
 531 {
 532   "$end", "error", "$undefined", "CHAR", "DOT", "CCL", "NCCL", "OR",
 533   "CAT", "STAR", "PLUS", "QUEST", "'('", "')'", "$accept", "s", "t", "b",
 534   "r", 0
 535 };
 536 #endif
 537
 538 # ifdef YYPRINT
 539 /* YYTOKNUM[YYLEX-NUM] -- Internal token number corresponding to
 540    token YYLEX-NUM.  */
 541 static const yytype_uint16 yytoknum[] =
 542 {
 543        0,   256,   257,   258,   259,   260,   261,   262,   263,   264,
 544      265,   266,    40,    41
 545 };
 546 # endif
 547
 548 /* YYR1[YYN] -- Symbol number of symbol that rule YYN derives.  */
 549 static const yytype_uint8 yyr1[] =
 550 {
 551        0,    14,    15,    16,    16,    16,    16,    17,    18,    18,
 552       18,    18,    18,    18,    18,    18,    18,    18,    18
 553 };
 554
 555 /* YYR2[YYN] -- Number of symbols composing right hand side of rule YYN.  */
 556 static const yytype_uint8 yyr2[] =
 557 {
 558        0,     2,     1,     2,     4,     3,     3,     0,     1,     1,
 559        1,     1,     3,     2,     2,     2,     2,     3,     1
 560 };
 561
 562 /* YYDEFACT[STATE-NAME] -- Default rule to reduce with in state
 563    STATE-NUM when YYTABLE doesn't specify something else to do.  Zero
 564    means the default is an error.  */
 565 static const yytype_uint8 yydefact[] =
 566 {
 567        7,     7,     0,     2,     0,     0,     1,    18,     8,     9,
 568       10,    11,     0,     0,     0,     0,     0,    14,    15,    16,
 569        0,     0,     0,    17,     0
 570 };
 571
 572 /* YYDEFGOTO[NTERM-NUM].  */
 573 static const yytype_int8 yydefgoto[] =
 574 {
 575       -1,     2,     3,     4,    20
 576 };
 577
 578 /* YYPACT[STATE-NUM] -- Index in YYTABLE of the portion describing
 579    STATE-NUM.  */
 580 #define YYPACT_NINF -5
 581 static const yytype_int8 yypact[] =
 582 {
 583        2,    -5,     3,    -5,     1,     1,    -5,    -5,    -5,    -5,
 584       -5,    -5,     1,    47,    60,    72,    86,    -5,    -5,    -5,
 585       19,    96,     1,    -5,    33
 586 };
 587
 588 /* YYPGOTO[NTERM-NUM].  */
 589 static const yytype_int8 yypgoto[] =
 590 {
 591       -5,    -5,    -5,     9,    -4
 592 };
 593
 594 /* YYTABLE[YYPACT[STATE-NUM]].  What to do in state STATE-NUM.  If
 595    positive, shift that token.  If negative, reduce the rule which
 596    number is the opposite.  If zero, do what YYDEFACT says.
 597    If YYTABLE_NINF, syntax error.  */
 598 #define YYTABLE_NINF -14
 599 static const yytype_int8 yytable[] =
 600 {
 601       13,    14,     7,     6,     8,     9,    10,    11,    15,     1,
 602        5,     0,    24,    12,     0,     0,     0,    24,    24,   -13,
 603        7,     0,   -13,   -13,   -13,   -13,   -13,     0,    17,    18,
 604       19,   -13,   -13,   -12,     7,     0,     8,     9,    10,    11,
 605      -12,     0,    17,    18,    19,    12,   -12,    -3,     7,     0,
 606        8,     9,    10,    11,    16,     0,    17,    18,    19,    12,
 607       -5,     7,     0,     8,     9,    10,    11,    21,     0,    17,
 608       18,    19,    12,     7,     0,     8,     9,    10,    11,    22,
 609        0,    17,    18,    19,    12,    23,    -6,     7,     0,     8,
 610        9,    10,    11,     0,     0,     0,    -4,     7,    12,     8,
 611        9,    10,    11,     0,     0,     0,     0,     0,    12
 612 };
 613
 614 static const yytype_int8 yycheck[] =
 615 {
 616        4,     5,     1,     0,     3,     4,     5,     6,    12,     7,
 617        1,    -1,    16,    12,    -1,    -1,    -1,    21,    22,     0,
 618        1,    -1,     3,     4,     5,     6,     7,    -1,     9,    10,
 619       11,    12,    13,     0,     1,    -1,     3,     4,     5,     6,
 620        7,    -1,     9,    10,    11,    12,    13,     0,     1,    -1,
 621        3,     4,     5,     6,     7,    -1,     9,    10,    11,    12,
 622        0,     1,    -1,     3,     4,     5,     6,     7,    -1,     9,
 623       10,    11,    12,     1,    -1,     3,     4,     5,     6,     7,
 624       -1,     9,    10,    11,    12,    13,     0,     1,    -1,     3,
 625        4,     5,     6,    -1,    -1,    -1,     0,     1,    12,     3,
 626        4,     5,     6,    -1,    -1,    -1,    -1,    -1,    12
 627 };
 628
 629 /* YYSTOS[STATE-NUM] -- The (internal number of the) accessing
 630    symbol of state STATE-NUM.  */
 631 static const yytype_uint8 yystos[] =
 632 {
 633        0,     7,    15,    16,    17,    17,     0,     1,     3,     4,
 634        5,     6,    12,    18,    18,    18,     7,     9,    10,    11,
 635       18,     7,     7,    13,    18
 636 };
 637
 638 #define yyerrok         (yyerrstatus = 0)
 639 #define yyclearin       (yychar = YYEMPTY)
 640 #define YYEMPTY         (-2)
 641 #define YYEOF           0
 642
 643 #define YYACCEPT        goto yyacceptlab
 644 #define YYABORT         goto yyabortlab
 645 #define YYERROR         goto yyerrorlab
 646
 647
 648 /* Like YYERROR except do call yyerror.  This remains here temporarily
 649    to ease the transition to the new meaning of YYERROR, for GCC.
 650    Once GCC version 2 has supplanted version 1, this can go.  However,
 651    YYFAIL appears to be in use.  Nevertheless, it is formally deprecated
 652    in Bison 2.4.2's NEWS entry, where a plan to phase it out is
 653    discussed.  */
 654
 655 #define YYFAIL          goto yyerrlab
 656 #if defined YYFAIL
 657   /* This is here to suppress warnings from the GCC cpp's
 658      -Wunused-macros.  Normally we don't worry about that warning, but
 659      some users do, and we want to make it easy for users to remove
 660      YYFAIL uses, which will produce warnings from Bison 2.5.  */
 661 #endif
 662
 663 #define YYRECOVERING()  (!!yyerrstatus)
 664
 665 #define YYBACKUP(Token, Value)                                  \
 666 do                                                              \
 667   if (yychar == YYEMPTY && yylen == 1)                          \
 668     {                                                           \
 669       yychar = (Token);                                         \
 670       yylval = (Value);                                         \
 671       yytoken = YYTRANSLATE (yychar);                           \
 672       YYPOPSTACK (1);                                           \
 673       goto yybackup;                                            \
 674     }                                                           \
 675   else                                                          \
 676     {                                                           \
 677       yyerror (YY_("syntax error: cannot back up")); \
 678       YYERROR;                                                  \
 679     }                                                           \
 680 while (YYID (0))
 681
 682
 683 #define YYTERROR        1
 684 #define YYERRCODE       256
 685
 686
 687 /* YYLLOC_DEFAULT -- Set CURRENT to span from RHS[1] to RHS[N].
 688    If N is 0, then set CURRENT to the empty location which ends
 689    the previous symbol: RHS[0] (always defined).  */
 690
 691 #define YYRHSLOC(Rhs, K) ((Rhs)[K])
 692 #ifndef YYLLOC_DEFAULT
 693 # define YYLLOC_DEFAULT(Current, Rhs, N)                                \
 694     do                                                                  \
 695       if (YYID (N))                                                    \
 696         {                                                               \
 697           (Current).first_line   = YYRHSLOC (Rhs, 1).first_line;        \
 698           (Current).first_column = YYRHSLOC (Rhs, 1).first_column;      \
 699           (Current).last_line    = YYRHSLOC (Rhs, N).last_line;         \
 700           (Current).last_column  = YYRHSLOC (Rhs, N).last_column;       \
 701         }                                                               \
 702       else                                                              \
 703         {                                                               \
 704           (Current).first_line   = (Current).last_line   =              \
 705             YYRHSLOC (Rhs, 0).last_line;                                \
 706           (Current).first_column = (Current).last_column =              \
 707             YYRHSLOC (Rhs, 0).last_column;                              \
 708         }                                                               \
 709     while (YYID (0))
 710 #endif
 711
 712
 713 /* YY_LOCATION_PRINT -- Print the location on the stream.
 714    This macro was not mandated originally: define only if we know
 715    we won't break user code: when these are the locations we know.  */
 716
 717 #ifndef YY_LOCATION_PRINT
 718 # if defined YYLTYPE_IS_TRIVIAL && YYLTYPE_IS_TRIVIAL
 719 #  define YY_LOCATION_PRINT(File, Loc)                  \
 720      fprintf (File, "%d.%d-%d.%d",                      \
 721               (Loc).first_line, (Loc).first_column,     \
 722               (Loc).last_line,  (Loc).last_column)
 723 # else
 724 #  define YY_LOCATION_PRINT(File, Loc) ((void) 0)
 725 # endif
 726 #endif
 727
 728
 729 /* YYLEX -- calling `yylex' with the right arguments.  */
 730
 731 #ifdef YYLEX_PARAM
 732 # define YYLEX yylex (YYLEX_PARAM)
 733 #else
 734 # define YYLEX yylex ()
 735 #endif
 736
 737 /* Enable debugging if requested.  */
 738 #if YYDEBUG
 739
 740 # ifndef YYFPRINTF
 741 #  include <stdio.h> /* INFRINGES ON USER NAME SPACE */
 742 #  define YYFPRINTF fprintf
 743 # endif
 744
 745 # define YYDPRINTF(Args)                        \
 746 do {                                            \
 747   if (yydebug)                                  \
 748     YYFPRINTF Args;                             \
 749 } while (YYID (0))
 750
 751 # define YY_SYMBOL_PRINT(Title, Type, Value, Location)                    \
 752 do {                                                                      \
 753   if (yydebug)                                                            \
 754     {                                                                     \
 755       YYFPRINTF (stderr, "%s ", Title);                                   \
 756       yy_symbol_print (stderr,                                            \
 757                   Type, Value); \
 758       YYFPRINTF (stderr, "\n");                                           \
 759     }                                                                     \
 760 } while (YYID (0))
 761
 762
 763 /*--------------------------------.
 764 | Print this symbol on YYOUTPUT.  |
 765 `--------------------------------*/
 766
 767 /*ARGSUSED*/
 768 #if (defined __STDC__ || defined __C99__FUNC__ \
 769      || defined __cplusplus || defined _MSC_VER)
 770 static void
 771 yy_symbol_value_print (FILE *yyoutput, int yytype, YYSTYPE const * const yyvaluep)
 772 #else
 773 static void
 774 yy_symbol_value_print (yyoutput, yytype, yyvaluep)
 775     FILE *yyoutput;
 776     int yytype;
 777     YYSTYPE const * const yyvaluep;
 778 #endif
 779 {
 780   if (!yyvaluep)
 781     return;
 782 # ifdef YYPRINT
 783   if (yytype < YYNTOKENS)
 784     YYPRINT (yyoutput, yytoknum[yytype], *yyvaluep);
 785 # else
 786   YYUSE (yyoutput);
 787 # endif
 788   switch (yytype)
 789     {
 790       default:
 791         break;
 792     }
 793 }
 794
 795
 796 /*--------------------------------.
 797 | Print this symbol on YYOUTPUT.  |
 798 `--------------------------------*/
 799
 800 #if (defined __STDC__ || defined __C99__FUNC__ \
 801      || defined __cplusplus || defined _MSC_VER)
 802 static void
 803 yy_symbol_print (FILE *yyoutput, int yytype, YYSTYPE const * const yyvaluep)
 804 #else
 805 static void
 806 yy_symbol_print (yyoutput, yytype, yyvaluep)
 807     FILE *yyoutput;
 808     int yytype;
 809     YYSTYPE const * const yyvaluep;
 810 #endif
 811 {
 812   if (yytype < YYNTOKENS)
 813     YYFPRINTF (yyoutput, "token %s (", yytname[yytype]);
 814   else
 815     YYFPRINTF (yyoutput, "nterm %s (", yytname[yytype]);
 816
 817   yy_symbol_value_print (yyoutput, yytype, yyvaluep);
 818   YYFPRINTF (yyoutput, ")");
 819 }
 820
 821 /*------------------------------------------------------------------.
 822 | yy_stack_print -- Print the state stack from its BOTTOM up to its |
 823 | TOP (included).                                                   |
 824 `------------------------------------------------------------------*/
 825
 826 #if (defined __STDC__ || defined __C99__FUNC__ \
 827      || defined __cplusplus || defined _MSC_VER)
 828 static void
 829 yy_stack_print (yytype_int16 *yybottom, yytype_int16 *yytop)
 830 #else
 831 static void
 832 yy_stack_print (yybottom, yytop)
 833     yytype_int16 *yybottom;
 834     yytype_int16 *yytop;
 835 #endif
 836 {
 837   YYFPRINTF (stderr, "Stack now");
 838   for (; yybottom <= yytop; yybottom++)
 839     {
 840       int yybot = *yybottom;
 841       YYFPRINTF (stderr, " %d", yybot);
 842     }
 843   YYFPRINTF (stderr, "\n");
 844 }
 845
 846 # define YY_STACK_PRINT(Bottom, Top)                            \
 847 do {                                                            \
 848   if (yydebug)                                                  \
 849     yy_stack_print ((Bottom), (Top));                           \
 850 } while (YYID (0))
 851
 852
 853 /*------------------------------------------------.
 854 | Report that the YYRULE is going to be reduced.  |
 855 `------------------------------------------------*/
 856
 857 #if (defined __STDC__ || defined __C99__FUNC__ \
 858      || defined __cplusplus || defined _MSC_VER)
 859 static void
 860 yy_reduce_print (YYSTYPE *yyvsp, int yyrule)
 861 #else
 862 static void
 863 yy_reduce_print (yyvsp, yyrule)
 864     YYSTYPE *yyvsp;
 865     int yyrule;
 866 #endif
 867 {
 868   int yynrhs = yyr2[yyrule];
 869   int yyi;
 870   unsigned long int yylno = yyrline[yyrule];
 871   YYFPRINTF (stderr, "Reducing stack by rule %d (line %lu):\n",
 872              yyrule - 1, yylno);
 873   /* The symbols being reduced.  */
 874   for (yyi = 0; yyi < yynrhs; yyi++)
 875     {
 876       YYFPRINTF (stderr, "   $%d = ", yyi + 1);
 877       yy_symbol_print (stderr, yyrhs[yyprhs[yyrule] + yyi],
 878                        &(yyvsp[(yyi + 1) - (yynrhs)])
 879                                        );
 880       YYFPRINTF (stderr, "\n");
 881     }
 882 }
 883
 884 # define YY_REDUCE_PRINT(Rule)          \
 885 do {                                    \
 886   if (yydebug)                          \
 887     yy_reduce_print (yyvsp, Rule); \
 888 } while (YYID (0))
 889
 890 /* Nonzero means print parse trace.  It is left uninitialized so that
 891    multiple parsers can coexist.  */
 892 int yydebug;
 893 #else /* !YYDEBUG */
 894 # define YYDPRINTF(Args)
 895 # define YY_SYMBOL_PRINT(Title, Type, Value, Location)
 896 # define YY_STACK_PRINT(Bottom, Top)
 897 # define YY_REDUCE_PRINT(Rule)
 898 #endif /* !YYDEBUG */
 899
 900
 901 /* YYINITDEPTH -- initial size of the parser's stacks.  */
 902 #ifndef YYINITDEPTH
 903 # define YYINITDEPTH 200
 904 #endif
 905
 906 /* YYMAXDEPTH -- maximum size the stacks can grow to (effective only
 907    if the built-in stack extension method is used).
 908
 909    Do not make this value too large; the results are undefined if
 910    YYSTACK_ALLOC_MAXIMUM < YYSTACK_BYTES (YYMAXDEPTH)
 911    evaluated with infinite-precision integer arithmetic.  */
 912
 913 #ifndef YYMAXDEPTH
 914 # define YYMAXDEPTH 10000
 915 #endif
 916
 917 \f
 918
 919 #if YYERROR_VERBOSE
 920
 921 # ifndef yystrlen
 922 #  if defined __GLIBC__ && defined _STRING_H
 923 #   define yystrlen strlen
 924 #  else
 925 /* Return the length of YYSTR.  */
 926 #if (defined __STDC__ || defined __C99__FUNC__ \
 927      || defined __cplusplus || defined _MSC_VER)
 928 static YYSIZE_T
 929 yystrlen (const char *yystr)
 930 #else
 931 static YYSIZE_T
 932 yystrlen (yystr)
 933     const char *yystr;
 934 #endif
 935 {
 936   YYSIZE_T yylen;
 937   for (yylen = 0; yystr[yylen]; yylen++)
 938     continue;
 939   return yylen;
 940 }
 941 #  endif
 942 # endif
 943
 944 # ifndef yystpcpy
 945 #  if defined __GLIBC__ && defined _STRING_H && defined _GNU_SOURCE
 946 #   define yystpcpy stpcpy
 947 #  else
 948 /* Copy YYSRC to YYDEST, returning the address of the terminating '\0' in
 949    YYDEST.  */
 950 #if (defined __STDC__ || defined __C99__FUNC__ \
 951      || defined __cplusplus || defined _MSC_VER)
 952 static char *
 953 yystpcpy (char *yydest, const char *yysrc)
 954 #else
 955 static char *
 956 yystpcpy (yydest, yysrc)
 957     char *yydest;
 958     const char *yysrc;
 959 #endif
 960 {
 961   char *yyd = yydest;
 962   const char *yys = yysrc;
 963
 964   while ((*yyd++ = *yys++) != '\0')
 965     continue;
 966
 967   return yyd - 1;
 968 }
 969 #  endif
 970 # endif
 971
 972 # ifndef yytnamerr
 973 /* Copy to YYRES the contents of YYSTR after stripping away unnecessary
 974    quotes and backslashes, so that it's suitable for yyerror.  The
 975    heuristic is that double-quoting is unnecessary unless the string
 976    contains an apostrophe, a comma, or backslash (other than
 977    backslash-backslash).  YYSTR is taken from yytname.  If YYRES is
 978    null, do not copy; instead, return the length of what the result
 979    would have been.  */
 980 static YYSIZE_T
 981 yytnamerr (char *yyres, const char *yystr)
 982 {
 983   if (*yystr == '"')
 984     {
 985       YYSIZE_T yyn = 0;
 986       char const *yyp = yystr;
 987
 988       for (;;)
 989         switch (*++yyp)
 990           {
 991           case '\'':
 992           case ',':
 993             goto do_not_strip_quotes;
 994
 995           case '\\':
 996             if (*++yyp != '\\')
 997               goto do_not_strip_quotes;
 998             /* Fall through.  */
 999           default:
1000             if (yyres)
1001               yyres[yyn] = *yyp;
1002             yyn++;
1003             break;
1004
1005           case '"':
1006             if (yyres)
1007               yyres[yyn] = '\0';
1008             return yyn;
1009           }
1010     do_not_strip_quotes: ;
1011     }
1012
1013   if (! yyres)
1014     return yystrlen (yystr);
1015
1016   return yystpcpy (yyres, yystr) - yyres;
1017 }
1018 # endif
1019
1020 /* Copy into YYRESULT an error message about the unexpected token
1021    YYCHAR while in state YYSTATE.  Return the number of bytes copied,
1022    including the terminating null byte.  If YYRESULT is null, do not
1023    copy anything; just return the number of bytes that would be
1024    copied.  As a special case, return 0 if an ordinary "syntax error"
1025    message will do.  Return YYSIZE_MAXIMUM if overflow occurs during
1026    size calculation.  */
1027 static YYSIZE_T
1028 yysyntax_error (char *yyresult, int yystate, int yychar)
1029 {
1030   int yyn = yypact[yystate];
1031
1032   if (! (YYPACT_NINF < yyn && yyn <= YYLAST))
1033     return 0;
1034   else
1035     {
1036       int yytype = YYTRANSLATE (yychar);
1037       YYSIZE_T yysize0 = yytnamerr (0, yytname[yytype]);
1038       YYSIZE_T yysize = yysize0;
1039       YYSIZE_T yysize1;
1040       int yysize_overflow = 0;
1041       enum { YYERROR_VERBOSE_ARGS_MAXIMUM = 5 };
1042       char const *yyarg[YYERROR_VERBOSE_ARGS_MAXIMUM];
1043       int yyx;
1044
1045 # if 0
1046       /* This is so xgettext sees the translatable formats that are
1047          constructed on the fly.  */
1048       YY_("syntax error, unexpected %s");
1049       YY_("syntax error, unexpected %s, expecting %s");
1050       YY_("syntax error, unexpected %s, expecting %s or %s");
1051       YY_("syntax error, unexpected %s, expecting %s or %s or %s");
1052       YY_("syntax error, unexpected %s, expecting %s or %s or %s or %s");
1053 # endif
1054       char *yyfmt;
1055       char const *yyf;
1056       static char const yyunexpected[] = "syntax error, unexpected %s";
1057       static char const yyexpecting[] = ", expecting %s";
1058       static char const yyor[] = " or %s";
1059       char yyformat[sizeof yyunexpected
1060                     + sizeof yyexpecting - 1
1061                     + ((YYERROR_VERBOSE_ARGS_MAXIMUM - 2)
1062                        * (sizeof yyor - 1))];
1063       char const *yyprefix = yyexpecting;
1064
1065       /* Start YYX at -YYN if negative to avoid negative indexes in
1066          YYCHECK.  */
1067       int yyxbegin = yyn < 0 ? -yyn : 0;
1068
1069       /* Stay within bounds of both yycheck and yytname.  */
1070       int yychecklim = YYLAST - yyn + 1;
1071       int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;
1072       int yycount = 1;
1073
1074       yyarg[0] = yytname[yytype];
1075       yyfmt = yystpcpy (yyformat, yyunexpected);
1076
1077       for (yyx = yyxbegin; yyx < yyxend; ++yyx)
1078         if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR)
1079           {
1080             if (yycount == YYERROR_VERBOSE_ARGS_MAXIMUM)
1081               {
1082                 yycount = 1;
1083                 yysize = yysize0;
1084                 yyformat[sizeof yyunexpected - 1] = '\0';
1085                 break;
1086               }
1087             yyarg[yycount++] = yytname[yyx];
1088             yysize1 = yysize + yytnamerr (0, yytname[yyx]);
1089             yysize_overflow |= (yysize1 < yysize);
1090             yysize = yysize1;
1091             yyfmt = yystpcpy (yyfmt, yyprefix);
1092             yyprefix = yyor;
1093           }
1094
1095       yyf = YY_(yyformat);
1096       yysize1 = yysize + yystrlen (yyf);
1097       yysize_overflow |= (yysize1 < yysize);
1098       yysize = yysize1;
1099
1100       if (yysize_overflow)
1101         return YYSIZE_MAXIMUM;
1102
1103       if (yyresult)
1104         {
1105           /* Avoid sprintf, as that infringes on the user's name space.
1106              Don't have undefined behavior even if the translation
1107              produced a string with the wrong number of "%s"s.  */
1108           char *yyp = yyresult;
1109           int yyi = 0;
1110           while ((*yyp = *yyf) != '\0')
1111             {
1112               if (*yyp == '%' && yyf[1] == 's' && yyi < yycount)
1113                 {
1114                   yyp += yytnamerr (yyp, yyarg[yyi++]);
1115                   yyf += 2;
1116                 }
1117               else
1118                 {
1119                   yyp++;
1120                   yyf++;
1121                 }
1122             }
1123         }
1124       return yysize;
1125     }
1126 }
1127 #endif /* YYERROR_VERBOSE */
1128 \f
1129
1130 /*-----------------------------------------------.
1131 | Release the memory associated to this symbol.  |
1132 `-----------------------------------------------*/
1133
1134 /*ARGSUSED*/
1135 #if (defined __STDC__ || defined __C99__FUNC__ \
1136      || defined __cplusplus || defined _MSC_VER)
1137 static void
1138 yydestruct (const char *yymsg, int yytype, YYSTYPE *yyvaluep)
1139 #else
1140 static void
1141 yydestruct (yymsg, yytype, yyvaluep)
1142     const char *yymsg;
1143     int yytype;
1144     YYSTYPE *yyvaluep;
1145 #endif
1146 {
1147   YYUSE (yyvaluep);
1148
1149   if (!yymsg)
1150     yymsg = "Deleting";
1151   YY_SYMBOL_PRINT (yymsg, yytype, yyvaluep, yylocationp);
1152
1153   switch (yytype)
1154     {
1155
1156       default:
1157         break;
1158     }
1159 }
1160
1161 /* Prevent warnings from -Wmissing-prototypes.  */
1162 #ifdef YYPARSE_PARAM
1163 #if defined __STDC__ || defined __cplusplus
1164 int yyparse (void *YYPARSE_PARAM);
1165 #else
1166 int yyparse ();
1167 #endif
1168 #else /* ! YYPARSE_PARAM */
1169 #if defined __STDC__ || defined __cplusplus
1170 int yyparse (void);
1171 #else
1172 int yyparse ();
1173 #endif
1174 #endif /* ! YYPARSE_PARAM */
1175
1176
1177 /* The lookahead symbol.  */
1178 int yychar;
1179
1180 /* The semantic value of the lookahead symbol.  */
1181 YYSTYPE yylval;
1182
1183 /* Number of syntax errors so far.  */
1184 int yynerrs;
1185
1186
1187
1188 /*-------------------------.
1189 | yyparse or yypush_parse.  |
1190 `-------------------------*/
1191
1192 #ifdef YYPARSE_PARAM
1193 #if (defined __STDC__ || defined __C99__FUNC__ \
1194      || defined __cplusplus || defined _MSC_VER)
1195 int
1196 yyparse (void *YYPARSE_PARAM)
1197 #else
1198 int
1199 yyparse (YYPARSE_PARAM)
1200     void *YYPARSE_PARAM;
1201 #endif
1202 #else /* ! YYPARSE_PARAM */
1203 #if (defined __STDC__ || defined __C99__FUNC__ \
1204      || defined __cplusplus || defined _MSC_VER)
1205 int
1206 yyparse (void)
1207 #else
1208 int
1209 yyparse ()
1210
1211 #endif
1212 #endif
1213 {
1214
1215
1216     int yystate;
1217     /* Number of tokens to shift before error messages enabled.  */
1218     int yyerrstatus;
1219
1220     /* The stacks and their tools:
1221        `yyss': related to states.
1222        `yyvs': related to semantic values.
1223
1224        Refer to the stacks thru separate pointers, to allow yyoverflow
1225        to reallocate them elsewhere.  */
1226
1227     /* The state stack.  */
1228     yytype_int16 yyssa[YYINITDEPTH];
1229     yytype_int16 *yyss;
1230     yytype_int16 *yyssp;
1231
1232     /* The semantic value stack.  */
1233     YYSTYPE yyvsa[YYINITDEPTH];
1234     YYSTYPE *yyvs;
1235     YYSTYPE *yyvsp;
1236
1237     YYSIZE_T yystacksize;
1238
1239   int yyn;
1240   int yyresult;
1241   /* Lookahead token as an internal (translated) token number.  */
1242   int yytoken;
1243   /* The variables used to return semantic value and location from the
1244      action routines.  */
1245   YYSTYPE yyval;
1246
1247 #if YYERROR_VERBOSE
1248   /* Buffer for error messages, and its allocated size.  */
1249   char yymsgbuf[128];
1250   char *yymsg = yymsgbuf;
1251   YYSIZE_T yymsg_alloc = sizeof yymsgbuf;
1252 #endif
1253
1254 #define YYPOPSTACK(N)   (yyvsp -= (N), yyssp -= (N))
1255
1256   /* The number of symbols on the RHS of the reduced rule.
1257      Keep to zero when no symbol should be popped.  */
1258   int yylen = 0;
1259
1260   yytoken = 0;
1261   yyss = yyssa;
1262   yyvs = yyvsa;
1263   yystacksize = YYINITDEPTH;
1264
1265   YYDPRINTF ((stderr, "Starting parse\n"));
1266
1267   yystate = 0;
1268   yyerrstatus = 0;
1269   yynerrs = 0;
1270   yychar = YYEMPTY; /* Cause a token to be read.  */
1271
1272   /* Initialize stack pointers.
1273      Waste one element of value and location stack
1274      so that they stay on the same level as the state stack.
1275      The wasted elements are never initialized.  */
1276   yyssp = yyss;
1277   yyvsp = yyvs;
1278
1279   goto yysetstate;
1280
1281 /*------------------------------------------------------------.
1282 | yynewstate -- Push a new state, which is found in yystate.  |
1283 `------------------------------------------------------------*/
1284  yynewstate:
1285   /* In all cases, when you get here, the value and location stacks
1286      have just been pushed.  So pushing a state here evens the stacks.  */
1287   yyssp++;
1288
1289  yysetstate:
1290   *yyssp = yystate;
1291
1292   if (yyss + yystacksize - 1 <= yyssp)
1293     {
1294       /* Get the current used size of the three stacks, in elements.  */
1295       YYSIZE_T yysize = yyssp - yyss + 1;
1296
1297 #ifdef yyoverflow
1298       {
1299         /* Give user a chance to reallocate the stack.  Use copies of
1300            these so that the &'s don't force the real ones into
1301            memory.  */
1302         YYSTYPE *yyvs1 = yyvs;
1303         yytype_int16 *yyss1 = yyss;
1304
1305         /* Each stack pointer address is followed by the size of the
1306            data in use in that stack, in bytes.  This used to be a
1307            conditional around just the two extra args, but that might
1308            be undefined if yyoverflow is a macro.  */
1309         yyoverflow (YY_("memory exhausted"),
1310                     &yyss1, yysize * sizeof (*yyssp),
1311                     &yyvs1, yysize * sizeof (*yyvsp),
1312                     &yystacksize);
1313
1314         yyss = yyss1;
1315         yyvs = yyvs1;
1316       }
1317 #else /* no yyoverflow */
1318 # ifndef YYSTACK_RELOCATE
1319       goto yyexhaustedlab;
1320 # else
1321       /* Extend the stack our own way.  */
1322       if (YYMAXDEPTH <= yystacksize)
1323         goto yyexhaustedlab;
1324       yystacksize *= 2;
1325       if (YYMAXDEPTH < yystacksize)
1326         yystacksize = YYMAXDEPTH;
1327
1328       {
1329         yytype_int16 *yyss1 = yyss;
1330         union yyalloc *yyptr =
1331           (union yyalloc *) YYSTACK_ALLOC (YYSTACK_BYTES (yystacksize));
1332         if (! yyptr)
1333           goto yyexhaustedlab;
1334         YYSTACK_RELOCATE (yyss_alloc, yyss);
1335         YYSTACK_RELOCATE (yyvs_alloc, yyvs);
1336 #  undef YYSTACK_RELOCATE
1337         if (yyss1 != yyssa)
1338           YYSTACK_FREE (yyss1);
1339       }
1340 # endif
1341 #endif /* no yyoverflow */
1342
1343       yyssp = yyss + yysize - 1;
1344       yyvsp = yyvs + yysize - 1;
1345
1346       YYDPRINTF ((stderr, "Stack size increased to %lu\n",
1347                   (unsigned long int) yystacksize));
1348
1349       if (yyss + yystacksize - 1 <= yyssp)
1350         YYABORT;
1351     }
1352
1353   YYDPRINTF ((stderr, "Entering state %d\n", yystate));
1354
1355   if (yystate == YYFINAL)
1356     YYACCEPT;
1357
1358   goto yybackup;
1359
1360 /*-----------.
1361 | yybackup.  |
1362 `-----------*/
1363 yybackup:
1364
1365   /* Do appropriate processing given the current state.  Read a
1366      lookahead token if we need one and don't already have one.  */
1367
1368   /* First try to decide what to do without reference to lookahead token.  */
1369   yyn = yypact[yystate];
1370   if (yyn == YYPACT_NINF)
1371     goto yydefault;
1372
1373   /* Not known => get a lookahead token if don't already have one.  */
1374
1375   /* YYCHAR is either YYEMPTY or YYEOF or a valid lookahead symbol.  */
1376   if (yychar == YYEMPTY)
1377     {
1378       YYDPRINTF ((stderr, "Reading a token: "));
1379       yychar = YYLEX;
1380     }
1381
1382   if (yychar <= YYEOF)
1383     {
1384       yychar = yytoken = YYEOF;
1385       YYDPRINTF ((stderr, "Now at end of input.\n"));
1386     }
1387   else
1388     {
1389       yytoken = YYTRANSLATE (yychar);
1390       YY_SYMBOL_PRINT ("Next token is", yytoken, &yylval, &yylloc);
1391     }
1392
1393   /* If the proper action on seeing token YYTOKEN is to reduce or to
1394      detect an error, take that action.  */
1395   yyn += yytoken;
1396   if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken)
1397     goto yydefault;
1398   yyn = yytable[yyn];
1399   if (yyn <= 0)
1400     {
1401       if (yyn == 0 || yyn == YYTABLE_NINF)
1402         goto yyerrlab;
1403       yyn = -yyn;
1404       goto yyreduce;
1405     }
1406
1407   /* Count tokens shifted since error; after three, turn off error
1408      status.  */
1409   if (yyerrstatus)
1410     yyerrstatus--;
1411
1412   /* Shift the lookahead token.  */
1413   YY_SYMBOL_PRINT ("Shifting", yytoken, &yylval, &yylloc);
1414
1415   /* Discard the shifted token.  */
1416   yychar = YYEMPTY;
1417
1418   yystate = yyn;
1419   *++yyvsp = yylval;
1420
1421   goto yynewstate;
1422
1423
1424 /*-----------------------------------------------------------.
1425 | yydefault -- do the default action for the current state.  |
1426 `-----------------------------------------------------------*/
1427 yydefault:
1428   yyn = yydefact[yystate];
1429   if (yyn == 0)
1430     goto yyerrlab;
1431   goto yyreduce;
1432
1433
1434 /*-----------------------------.
1435 | yyreduce -- Do a reduction.  |
1436 `-----------------------------*/
1437 yyreduce:
1438   /* yyn is the number of a rule to reduce with.  */
1439   yylen = yyr2[yyn];
1440
1441   /* If YYLEN is nonzero, implement the default value of the action:
1442      `$$ = $1'.
1443
1444      Otherwise, the following line sets YYVAL to garbage.
1445      This behavior is undocumented and Bison
1446      users should not rely upon it.  Assigning to YYVAL
1447      unconditionally makes the parser a bit smaller, and it avoids a
1448      GCC warning that YYVAL may be used uninitialized.  */
1449   yyval = yyvsp[1-yylen];
1450
1451
1452   YY_REDUCE_PRINT (yyn);
1453   switch (yyn)
1454     {
1455         case 2:
1456
1457 /* Line 1464 of yacc.c  */
1458 #line 106 "egrep.y"
1459     { unary(FINAL, (yyvsp[(1) - (1)]));
1460                   line--;
1461                 }
1462     break;
1463
1464   case 3:
1465
1466 /* Line 1464 of yacc.c  */
1467 #line 111 "egrep.y"
1468     { (yyval) = node(CAT, (yyvsp[(1) - (2)]), (yyvsp[(2) - (2)])); }
1469     break;
1470
1471   case 4:
1472
1473 /* Line 1464 of yacc.c  */
1474 #line 113 "egrep.y"
1475     { (yyval) = node(CAT, (yyvsp[(2) - (4)]), (yyvsp[(3) - (4)])); }
1476     break;
1477
1478   case 5:
1479
1480 /* Line 1464 of yacc.c  */
1481 #line 115 "egrep.y"
1482     { (yyval) = node(CAT, (yyvsp[(2) - (3)]), (yyvsp[(3) - (3)])); }
1483     break;
1484
1485   case 6:
1486
1487 /* Line 1464 of yacc.c  */
1488 #line 117 "egrep.y"
1489     { (yyval) = node(CAT, (yyvsp[(1) - (3)]), (yyvsp[(2) - (3)])); }
1490     break;
1491
1492   case 7:
1493
1494 /* Line 1464 of yacc.c  */
1495 #line 120 "egrep.y"
1496     { (yyval) = enter(DOT);
1497                    (yyval) = unary(STAR, (yyval)); }
1498     break;
1499
1500   case 8:
1501
1502 /* Line 1464 of yacc.c  */
1503 #line 124 "egrep.y"
1504     { (yyval) = enter((yyvsp[(1) - (1)])); }
1505     break;
1506
1507   case 9:
1508
1509 /* Line 1464 of yacc.c  */
1510 #line 126 "egrep.y"
1511     { (yyval) = enter(DOT); }
1512     break;
1513
1514   case 10:
1515
1516 /* Line 1464 of yacc.c  */
1517 #line 128 "egrep.y"
1518     { (yyval) = cclenter(CCL); }
1519     break;
1520
1521   case 11:
1522
1523 /* Line 1464 of yacc.c  */
1524 #line 130 "egrep.y"
1525     { (yyval) = cclenter(NCCL); }
1526     break;
1527
1528   case 12:
1529
1530 /* Line 1464 of yacc.c  */
1531 #line 134 "egrep.y"
1532     { (yyval) = node(OR, (yyvsp[(1) - (3)]), (yyvsp[(3) - (3)])); }
1533     break;
1534
1535   case 13:
1536
1537 /* Line 1464 of yacc.c  */
1538 #line 136 "egrep.y"
1539     { (yyval) = node(CAT, (yyvsp[(1) - (2)]), (yyvsp[(2) - (2)])); }
1540     break;
1541
1542   case 14:
1543
1544 /* Line 1464 of yacc.c  */
1545 #line 138 "egrep.y"
1546     { (yyval) = unary(STAR, (yyvsp[(1) - (2)])); }
1547     break;
1548
1549   case 15:
1550
1551 /* Line 1464 of yacc.c  */
1552 #line 140 "egrep.y"
1553     { (yyval) = unary(PLUS, (yyvsp[(1) - (2)])); }
1554     break;
1555
1556   case 16:
1557
1558 /* Line 1464 of yacc.c  */
1559 #line 142 "egrep.y"
1560     { (yyval) = unary(QUEST, (yyvsp[(1) - (2)])); }
1561     break;
1562
1563   case 17:
1564
1565 /* Line 1464 of yacc.c  */
1566 #line 144 "egrep.y"
1567     { (yyval) = (yyvsp[(2) - (3)]); }
1568     break;
1569
1570
1571
1572 /* Line 1464 of yacc.c  */
1573 #line 1574 "egrep.c"
1574       default: break;
1575     }
1576   YY_SYMBOL_PRINT ("-> $$ =", yyr1[yyn], &yyval, &yyloc);
1577
1578   YYPOPSTACK (yylen);
1579   yylen = 0;
1580   YY_STACK_PRINT (yyss, yyssp);
1581
1582   *++yyvsp = yyval;
1583
1584   /* Now `shift' the result of the reduction.  Determine what state
1585      that goes to, based on the state we popped back to and the rule
1586      number reduced by.  */
1587
1588   yyn = yyr1[yyn];
1589
1590   yystate = yypgoto[yyn - YYNTOKENS] + *yyssp;
1591   if (0 <= yystate && yystate <= YYLAST && yycheck[yystate] == *yyssp)
1592     yystate = yytable[yystate];
1593   else
1594     yystate = yydefgoto[yyn - YYNTOKENS];
1595
1596   goto yynewstate;
1597
1598
1599 /*------------------------------------.
1600 | yyerrlab -- here on detecting error |
1601 `------------------------------------*/
1602 yyerrlab:
1603   /* If not already recovering from an error, report this error.  */
1604   if (!yyerrstatus)
1605     {
1606       ++yynerrs;
1607 #if ! YYERROR_VERBOSE
1608       yyerror (YY_("syntax error"));
1609 #else
1610       {
1611         YYSIZE_T yysize = yysyntax_error (0, yystate, yychar);
1612         if (yymsg_alloc < yysize && yymsg_alloc < YYSTACK_ALLOC_MAXIMUM)
1613           {
1614             YYSIZE_T yyalloc = 2 * yysize;
1615             if (! (yysize <= yyalloc && yyalloc <= YYSTACK_ALLOC_MAXIMUM))
1616               yyalloc = YYSTACK_ALLOC_MAXIMUM;
1617             if (yymsg != yymsgbuf)
1618               YYSTACK_FREE (yymsg);
1619             yymsg = (char *) YYSTACK_ALLOC (yyalloc);
1620             if (yymsg)
1621               yymsg_alloc = yyalloc;
1622             else
1623               {
1624                 yymsg = yymsgbuf;
1625                 yymsg_alloc = sizeof yymsgbuf;
1626               }
1627           }
1628
1629         if (0 < yysize && yysize <= yymsg_alloc)
1630           {
1631             (void) yysyntax_error (yymsg, yystate, yychar);
1632             yyerror (yymsg);
1633           }
1634         else
1635           {
1636             yyerror (YY_("syntax error"));
1637             if (yysize != 0)
1638               goto yyexhaustedlab;
1639           }
1640       }
1641 #endif
1642     }
1643
1644
1645
1646   if (yyerrstatus == 3)
1647     {
1648       /* If just tried and failed to reuse lookahead token after an
1649          error, discard it.  */
1650
1651       if (yychar <= YYEOF)
1652         {
1653           /* Return failure if at end of input.  */
1654           if (yychar == YYEOF)
1655             YYABORT;
1656         }
1657       else
1658         {
1659           yydestruct ("Error: discarding",
1660                       yytoken, &yylval);
1661           yychar = YYEMPTY;
1662         }
1663     }
1664
1665   /* Else will try to reuse lookahead token after shifting the error
1666      token.  */
1667   goto yyerrlab1;
1668
1669
1670 /*---------------------------------------------------.
1671 | yyerrorlab -- error raised explicitly by YYERROR.  |
1672 `---------------------------------------------------*/
1673 yyerrorlab:
1674
1675   /* Pacify compilers like GCC when the user code never invokes
1676      YYERROR and the label yyerrorlab therefore never appears in user
1677      code.  */
1678   if (/*CONSTCOND*/ 0)
1679      goto yyerrorlab;
1680
1681   /* Do not reclaim the symbols of the rule which action triggered
1682      this YYERROR.  */
1683   YYPOPSTACK (yylen);
1684   yylen = 0;
1685   YY_STACK_PRINT (yyss, yyssp);
1686   yystate = *yyssp;
1687   goto yyerrlab1;
1688
1689
1690 /*-------------------------------------------------------------.
1691 | yyerrlab1 -- common code for both syntax error and YYERROR.  |
1692 `-------------------------------------------------------------*/
1693 yyerrlab1:
1694   yyerrstatus = 3;      /* Each real token shifted decrements this.  */
1695
1696   for (;;)
1697     {
1698       yyn = yypact[yystate];
1699       if (yyn != YYPACT_NINF)
1700         {
1701           yyn += YYTERROR;
1702           if (0 <= yyn && yyn <= YYLAST && yycheck[yyn] == YYTERROR)
1703             {
1704               yyn = yytable[yyn];
1705               if (0 < yyn)
1706                 break;
1707             }
1708         }
1709
1710       /* Pop the current state because it cannot handle the error token.  */
1711       if (yyssp == yyss)
1712         YYABORT;
1713
1714
1715       yydestruct ("Error: popping",
1716                   yystos[yystate], yyvsp);
1717       YYPOPSTACK (1);
1718       yystate = *yyssp;
1719       YY_STACK_PRINT (yyss, yyssp);
1720     }
1721
1722   *++yyvsp = yylval;
1723
1724
1725   /* Shift the error token.  */
1726   YY_SYMBOL_PRINT ("Shifting", yystos[yyn], yyvsp, yylsp);
1727
1728   yystate = yyn;
1729   goto yynewstate;
1730
1731
1732 /*-------------------------------------.
1733 | yyacceptlab -- YYACCEPT comes here.  |
1734 `-------------------------------------*/
1735 yyacceptlab:
1736   yyresult = 0;
1737   goto yyreturn;
1738
1739 /*-----------------------------------.
1740 | yyabortlab -- YYABORT comes here.  |
1741 `-----------------------------------*/
1742 yyabortlab:
1743   yyresult = 1;
1744   goto yyreturn;
1745
1746 #if !defined(yyoverflow) || YYERROR_VERBOSE
1747 /*-------------------------------------------------.
1748 | yyexhaustedlab -- memory exhaustion comes here.  |
1749 `-------------------------------------------------*/
1750 yyexhaustedlab:
1751   yyerror (YY_("memory exhausted"));
1752   yyresult = 2;
1753   /* Fall through.  */
1754 #endif
1755
1756 yyreturn:
1757   if (yychar != YYEMPTY)
1758      yydestruct ("Cleanup: discarding lookahead",
1759                  yytoken, &yylval);
1760   /* Do not reclaim the symbols of the rule which action triggered
1761      this YYABORT or YYACCEPT.  */
1762   YYPOPSTACK (yylen);
1763   YY_STACK_PRINT (yyss, yyssp);
1764   while (yyssp != yyss)
1765     {
1766       yydestruct ("Cleanup: popping",
1767                   yystos[*yyssp], yyvsp);
1768       YYPOPSTACK (1);
1769     }
1770 #ifndef yyoverflow
1771   if (yyss != yyssa)
1772     YYSTACK_FREE (yyss);
1773 #endif
1774 #if YYERROR_VERBOSE
1775   if (yymsg != yymsgbuf)
1776     YYSTACK_FREE (yymsg);
1777 #endif
1778   /* Make sure YYID is used.  */
1779   return YYID (yyresult);
1780 }
1781
1782
1783
1784 /* Line 1684 of yacc.c  */
1785 #line 148 "egrep.y"
1786
1787 static int
1788 yyerror(char *s)
1789 {
1790         message = s;
1791         longjmp(env, 1);
1792         return 1;               /* silence a warning */
1793 }
1794
1795 static int
1796 yylex(void)
1797 {
1798     int cclcnt, x;
1799     char c, d;
1800
1801     switch(c = nextch()) {
1802     case '|':
1803         return (OR);
1804     case '*':
1805         return (STAR);
1806     case '+':
1807         return (PLUS);
1808     case '?':
1809         return (QUEST);
1810     case '(':
1811         return (c);
1812     case ')':
1813         return (c);
1814     case '.':
1815         return (DOT);
1816     case '\0':
1817         return (0);
1818     case '\n':
1819         return (OR);
1820     case '[':
1821         x = CCL;
1822         cclcnt = 0;
1823         count = nxtchar++;
1824         if ((c = nextch()) == '^') {
1825             x = NCCL;
1826             c = nextch();
1827         }
1828         do {
1829             if (c == '\0')
1830                 synerror();
1831             if (c == '-'
1832                 && cclcnt > 0
1833                 && chars[nxtchar-1] != 0) {
1834                 if ((d = nextch()) != 0) {
1835                     c = chars[nxtchar-1];
1836                     while ((unsigned int)c < (unsigned int)d) {
1837                         if (nxtchar >= MAXLIN)
1838                             overflo();
1839                         chars[nxtchar++] = ++c;
1840                         cclcnt++;
1841                     }
1842                     continue;
1843                 } /* if() */
1844             } /* if() */
1845             if (nxtchar >= MAXLIN)
1846                 overflo();
1847             chars[nxtchar++] = c;
1848             cclcnt++;
1849         } while ((c = nextch()) != ']');
1850         chars[count] = cclcnt;
1851         return (x);
1852     case '\\':
1853         if ((c = nextch()) == '\0')
1854             synerror();
1855         /* not reached */
1856     case '$':
1857     case '^':
1858         c = '\n';
1859         /* fall through */
1860     default:
1861         yylval = c;
1862         return (CHAR);
1863     }
1864 }
1865
1866 static void
1867 synerror(void)
1868 {
1869     yyerror("Syntax error");
1870 }
1871
1872 static unsigned int
1873 enter(int x)
1874 {
1875     if(line >= MAXLIN)
1876         overflo();
1877     name[line] = x;
1878     left[line] = 0;
1879     right[line] = 0;
1880     return(line++);
1881 }
1882
1883 static unsigned int
1884 cclenter(int x)
1885 {
1886     unsigned int linno;
1887
1888     linno = enter(x);
1889     right[linno] = count;
1890     return (linno);
1891 }
1892
1893 static int
1894 node(int x, int l, int r)
1895 {
1896     if(line >= MAXLIN)
1897         overflo();
1898     name[line] = x;
1899     left[line] = l;
1900     right[line] = r;
1901     parent[l] = line;
1902     parent[r] = line;
1903     return(line++);
1904 }
1905
1906 static int
1907 unary(int x, int d)
1908 {
1909     if(line >= MAXLIN)
1910         overflo();
1911     name[line] = x;
1912     left[line] = d;
1913     right[line] = 0;
1914     parent[d] = line;
1915     return(line++);
1916 }
1917
1918 static void
1919 overflo(void)
1920 {
1921     yyerror("internal table overflow");
1922 }
1923
1924 static void
1925 cfoll(int v)
1926 {
1927     unsigned int i;
1928
1929     if (left[v] == 0) {
1930         count = 0;
1931         for (i = 1; i <= line; i++)
1932             tmpstat[i] = 0;
1933         follow(v);
1934         add(foll, v);
1935     } else if (right[v] == 0)
1936         cfoll(left[v]);
1937     else {
1938         cfoll(left[v]);
1939         cfoll(right[v]);
1940     }
1941 }
1942
1943 static void
1944 cgotofn(void)
1945 {
1946     unsigned int i, n, s;
1947     int c, k;
1948     char symbol[NCHARS];
1949     unsigned int j, l, pc, pos;
1950     unsigned int nc;
1951     int curpos;
1952     unsigned int num, number, newpos;
1953
1954     count = 0;
1955     for (n=3; n<=line; n++)
1956         tmpstat[n] = 0;
1957     if (cstate(line-1)==0) {
1958         tmpstat[line] = 1;
1959         count++;
1960         out[0] = 1;
1961     }
1962     for (n=3; n<=line; n++)
1963         initstat[n] = tmpstat[n];
1964     count--;            /*leave out position 1 */
1965     icount = count;
1966     tmpstat[1] = 0;
1967     add(state, 0);
1968     n = 0;
1969     for (s = 0; s <= n; s++)  {
1970         if (out[s] == 1)
1971             continue;
1972         for (i = 0; i < NCHARS; i++)
1973             symbol[i] = 0;
1974         num = positions[state[s]];
1975         count = icount;
1976         for (i = 3; i <= line; i++)
1977             tmpstat[i] = initstat[i];
1978         pos = state[s] + 1;
1979         for (i = 0; i < num; i++) {
1980             curpos = positions[pos];
1981             if ((c = name[curpos]) >= 0) {
1982                 if (c < NCHARS) {
1983                     symbol[c] = 1;
1984                 } else if (c == DOT) {
1985                     for (k = 0; k < NCHARS; k++)
1986                         if (k != '\n')
1987                             symbol[k] = 1;
1988                 } else if (c == CCL) {
1989                     nc = chars[right[curpos]];
1990                     pc = right[curpos] + 1;
1991                     for (j = 0; j < nc; j++)
1992                         symbol[(unsigned char)(chars[pc++])] = 1;
1993                 } else if (c == NCCL) {
1994                     nc = chars[right[curpos]];
1995                     for (j = 0; j < NCHARS; j++) {
1996                         pc = right[curpos] + 1;
1997                         for (l = 0; l < nc; l++)
1998                             if (j==(unsigned char)(chars[pc++]))
1999                                 goto cont;
2000                         if (j != '\n')
2001                             symbol[j] = 1;
2002                     cont:
2003                         ;
2004                     }
2005                 }
2006             }
2007             pos++;
2008         } /* for (i) */
2009         for (c=0; c<NCHARS; c++) {
2010             if (symbol[c] == 1) {
2011                 /* nextstate(s,c) */
2012                 count = icount;
2013                 for (i=3; i <= line; i++)
2014                     tmpstat[i] = initstat[i];
2015                 pos = state[s] + 1;
2016                 for (i=0; i<num; i++) {
2017                     curpos = positions[pos];
2018                     if ((k = name[curpos]) >= 0)
2019                         if ((k == c)
2020                             || (k == DOT)
2021                             || (k == CCL && member(c, right[curpos], 1))
2022                             || (k == NCCL && member(c, right[curpos], 0))
2023                             ) {
2024                             number = positions[foll[curpos]];
2025                             newpos = foll[curpos] + 1;
2026                             for (j = 0; j < number; j++) {
2027                                 if (tmpstat[positions[newpos]] != 1) {
2028                                     tmpstat[positions[newpos]] = 1;
2029                                     count++;
2030                                 }
2031                                 newpos++;
2032                             }
2033                         }
2034                     pos++;
2035                 } /* end nextstate */
2036                 if (notin(n)) {
2037                     if (n >= NSTATES)
2038                         overflo();
2039                     add(state, ++n);
2040                     if (tmpstat[line] == 1)
2041                         out[n] = 1;
2042                     gotofn[s][c] = n;
2043                 } else {
2044                     gotofn[s][c] = xstate;
2045                 }
2046             } /* if (symbol) */
2047         } /* for(c) */
2048     } /* for(s) */
2049 }
2050
2051 static int
2052 cstate(int v)
2053 {
2054         int b;
2055         if (left[v] == 0) {
2056                 if (tmpstat[v] != 1) {
2057                         tmpstat[v] = 1;
2058                         count++;
2059                 }
2060                 return(1);
2061         }
2062         else if (right[v] == 0) {
2063                 if (cstate(left[v]) == 0) return (0);
2064                 else if (name[v] == PLUS) return (1);
2065                 else return (0);
2066         }
2067         else if (name[v] == CAT) {
2068                 if (cstate(left[v]) == 0 && cstate(right[v]) == 0) return (0);
2069                 else return (1);
2070         }
2071         else { /* name[v] == OR */
2072                 b = cstate(right[v]);
2073                 if (cstate(left[v]) == 0 || b == 0) return (0);
2074                 else return (1);
2075         }
2076 }
2077
2078 static int
2079 member(int symb, int set, int torf)
2080 {
2081     unsigned int i, num, pos;
2082
2083     num = chars[set];
2084     pos = set + 1;
2085     for (i = 0; i < num; i++)
2086         if (symb == (unsigned char)(chars[pos++]))
2087             return (torf);
2088     return (!torf);
2089 }
2090
2091 static int
2092 notin(int n)
2093 {
2094         int i, j, pos;
2095         for (i=0; i<=n; i++) {
2096                 if (positions[state[i]] == count) {
2097                         pos = state[i] + 1;
2098                         for (j=0; j < count; j++)
2099                                 if (tmpstat[positions[pos++]] != 1) goto nxt;
2100                         xstate = i;
2101                         return (0);
2102                 }
2103                 nxt: ;
2104         }
2105         return (1);
2106 }
2107
2108 static void
2109 add(int *array, int n)
2110 {
2111     unsigned int i;
2112
2113     if (nxtpos + count > MAXPOS)
2114         overflo();
2115     array[n] = nxtpos;
2116     positions[nxtpos++] = count;
2117     for (i=3; i <= line; i++) {
2118         if (tmpstat[i] == 1) {
2119             positions[nxtpos++] = i;
2120         }
2121     }
2122 }
2123
2124 static void
2125 follow(unsigned int v)
2126 {
2127     unsigned int p;
2128
2129     if (v == line)
2130         return;
2131     p = parent[v];
2132     switch(name[p]) {
2133     case STAR:
2134     case PLUS:  cstate(v);
2135         follow(p);
2136         return;
2137
2138     case OR:
2139     case QUEST: follow(p);
2140         return;
2141
2142     case CAT:
2143         if (v == left[p]) {
2144             if (cstate(right[p]) == 0) {
2145                 follow(p);
2146                 return;
2147             }
2148         } else
2149             follow(p);
2150         return;
2151     case FINAL:
2152         if (tmpstat[line] != 1) {
2153             tmpstat[line] = 1;
2154             count++;
2155         }
2156         return;
2157     }
2158 }
2159
2160 char *
2161 egrepinit(char *egreppat)
2162 {
2163     /* initialize the global data */
2164     memset(gotofn, 0, sizeof(gotofn));
2165     memset(state, 0, sizeof(state));
2166     memset(out, 0, sizeof(out));
2167     line = 1;
2168     memset(name, 0, sizeof(name));
2169     memset(left, 0, sizeof(left));
2170     memset(right, 0, sizeof(right));
2171     memset(parent, 0, sizeof(parent));
2172     memset(foll, 0, sizeof(foll));
2173     memset(positions, 0, sizeof(positions));
2174     memset(chars, 0, sizeof(chars));
2175     nxtpos = 0;
2176     nxtchar = 0;
2177     memset(tmpstat, 0, sizeof(tmpstat));
2178     memset(initstat, 0, sizeof(initstat));
2179     xstate = 0;
2180     count = 0;
2181     icount = 0;
2182     input = egreppat;
2183     message = NULL;
2184     if (setjmp(env) == 0) {
2185         yyparse();
2186         cfoll(line-1);
2187         cgotofn();
2188     }
2189     return(message);
2190 }
2191
2192 int
2193 egrep(char *file, FILE *output, char *format)
2194 {
2195     char *p;
2196     unsigned int cstat;
2197     int ccount;
2198     char buf[2*BUFSIZ];
2199     char *nlp;
2200     unsigned int istat;
2201     int in_line;
2202     FILE *fptr;
2203
2204     if ((fptr = myfopen(file, "r")) == NULL)
2205         return(-1);
2206
2207     ccount = 0;
2208     lnum = 1;
2209     in_line = 0;
2210     p = buf;
2211     nlp = p;
2212     if ((ccount = fread(p, sizeof(char), BUFSIZ, fptr)) <= 0)
2213         goto done;
2214     in_line = 1;
2215     istat = cstat = (unsigned int) gotofn[0]['\n'];
2216     if (out[cstat])
2217         goto found;
2218     for (;;) {
2219         if (!iflag)
2220             cstat = (unsigned int) gotofn[cstat][(unsigned int)*p&0377];
2221         /* all input chars made positive */
2222         else
2223             cstat = (unsigned int) gotofn[cstat][tolower((int)*p&0377)];
2224         /* for -i option*/
2225         if (out[cstat]) {
2226         found:
2227             for(;;) {
2228                 if (*p++ == '\n') {
2229                     in_line = 0;
2230                 succeed:
2231                     fprintf(output, format, file, lnum);
2232                     if (p <= nlp) {
2233                         while (nlp < &buf[2*BUFSIZ])
2234                             putc(*nlp++, output);
2235                         nlp = buf;
2236                     }
2237                     while (nlp < p)
2238                         putc(*nlp++, output);
2239                     lnum++;
2240                     nlp = p;
2241                     if ((out[(cstat=istat)]) == 0)
2242                         goto brk2;
2243                 } /* if (p++ == \n) */
2244             cfound:
2245                 if (--ccount <= 0) {
2246                     if (p <= &buf[BUFSIZ]) {
2247                         ccount = fread(p, sizeof(char), BUFSIZ, fptr);
2248                     } else if (p == &buf[2*BUFSIZ]) {
2249                         p = buf;
2250                         ccount = fread(p, sizeof(char), BUFSIZ, fptr);
2251                     } else {
2252                         ccount = fread(p, sizeof(char), &buf[2*BUFSIZ] - p,
2253                                        fptr);
2254                     }
2255                     if (ccount <= 0) {
2256                         if (in_line) {
2257                             in_line = 0;
2258                             goto succeed;
2259                         }
2260                         goto done;
2261                     }
2262                 } /* if(ccount <= 0) */
2263                 in_line = 1;
2264             } /* for(ever) */
2265         } /* if(out[cstat]) */
2266
2267         if (*p++ == '\n') {
2268             in_line = 0;
2269             lnum++;
2270             nlp = p;
2271             if (out[(cstat=istat)])
2272                 goto cfound;
2273         }
2274     brk2:
2275         if (--ccount <= 0) {
2276             if (p <= &buf[BUFSIZ]) {
2277                 ccount = fread(p, sizeof(char), BUFSIZ, fptr);
2278             } else if (p == &buf[2*BUFSIZ]) {
2279                 p = buf;
2280                 ccount = fread(p, sizeof(char), BUFSIZ, fptr);
2281             } else {
2282                 ccount = fread(p, sizeof(char), &buf[2*BUFSIZ] - p, fptr);
2283             }
2284             if (ccount <= 0)
2285                 break;
2286         }
2287         in_line = 1;
2288     }
2289 done:
2290     fclose(fptr);
2291     return(0);
2292 }
2293
2294 /* FIXME HBB: should export this to a separate file and use
2295  * AC_REPLACE_FUNCS() */
2296 #if !STDC_HEADERS && !defined(HAVE_MEMSET) && !defined(HAVE_MEMORY_H)
2297 /*LINTLIBRARY*/
2298 /*
2299  * Set an array of n chars starting at sp to the character c.
2300  * Return sp.
2301  */
2302 char *
2303 memset(char *sp, char c, int n)
2304 {
2305         char *sp0 = sp;
2306
2307         while (--n >= 0)
2308                 *sp++ = c;
2309         return (sp0);
2310 }
2311 #endif
2312
2313 void
2314 egrepcaseless(int i)
2315 {
2316         iflag = i;      /* simulate "egrep -i" */
2317 }
2318