tool/lempar.c

   1 /*
   2 ** 2000-05-29
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** Driver template for the LEMON parser generator.
  13 **
  14 ** The "lemon" program processes an LALR(1) input grammar file, then uses
  15 ** this template to construct a parser.  The "lemon" program inserts text
  16 ** at each "%%" line.  Also, any "P-a-r-s-e" identifer prefix (without the
  17 ** interstitial "-" characters) contained in this template is changed into
  18 ** the value of the %name directive from the grammar.  Otherwise, the content
  19 ** of this template is copied straight through into the generate parser
  20 ** source file.
  21 **
  22 ** The following is the concatenation of all %include directives from the
  23 ** input grammar file:
  24 */
  25 #include <stdio.h>
  26 /************ Begin %include sections from the grammar ************************/
  27 %%
  28 /**************** End of %include directives **********************************/
  29 /* These constants specify the various numeric values for terminal symbols
  30 ** in a format understandable to "makeheaders".  This section is blank unless
  31 ** "lemon" is run with the "-m" command-line option.
  32 ***************** Begin makeheaders token definitions *************************/
  33 %%
  34 /**************** End makeheaders token definitions ***************************/
  35
  36 /* The next sections is a series of control #defines.
  37 ** various aspects of the generated parser.
  38 **    YYCODETYPE         is the data type used to store the integer codes
  39 **                       that represent terminal and non-terminal symbols.
  40 **                       "unsigned char" is used if there are fewer than
  41 **                       256 symbols.  Larger types otherwise.
  42 **    YYNOCODE           is a number of type YYCODETYPE that is not used for
  43 **                       any terminal or nonterminal symbol.
  44 **    YYFALLBACK         If defined, this indicates that one or more tokens
  45 **                       (also known as: "terminal symbols") have fall-back
  46 **                       values which should be used if the original symbol
  47 **                       would not parse.  This permits keywords to sometimes
  48 **                       be used as identifiers, for example.
  49 **    YYACTIONTYPE       is the data type used for "action codes" - numbers
  50 **                       that indicate what to do in response to the next
  51 **                       token.
  52 **    ParseTOKENTYPE     is the data type used for minor type for terminal
  53 **                       symbols.  Background: A "minor type" is a semantic
  54 **                       value associated with a terminal or non-terminal
  55 **                       symbols.  For example, for an "ID" terminal symbol,
  56 **                       the minor type might be the name of the identifier.
  57 **                       Each non-terminal can have a different minor type.
  58 **                       Terminal symbols all have the same minor type, though.
  59 **                       This macros defines the minor type for terminal
  60 **                       symbols.
  61 **    YYMINORTYPE        is the data type used for all minor types.
  62 **                       This is typically a union of many types, one of
  63 **                       which is ParseTOKENTYPE.  The entry in the union
  64 **                       for terminal symbols is called "yy0".
  65 **    YYSTACKDEPTH       is the maximum depth of the parser's stack.  If
  66 **                       zero the stack is dynamically sized using realloc()
  67 **    ParseARG_SDECL     A static variable declaration for the %extra_argument
  68 **    ParseARG_PDECL     A parameter declaration for the %extra_argument
  69 **    ParseARG_STORE     Code to store %extra_argument into yypParser
  70 **    ParseARG_FETCH     Code to extract %extra_argument from yypParser
  71 **    YYERRORSYMBOL      is the code number of the error symbol.  If not
  72 **                       defined, then do no error processing.
  73 **    YYNSTATE           the combined number of states.
  74 **    YYNRULE            the number of rules in the grammar
  75 **    YYNTOKEN           Number of terminal symbols
  76 **    YY_MAX_SHIFT       Maximum value for shift actions
  77 **    YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions
  78 **    YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions
  79 **    YY_ERROR_ACTION    The yy_action[] code for syntax error
  80 **    YY_ACCEPT_ACTION   The yy_action[] code for accept
  81 **    YY_NO_ACTION       The yy_action[] code for no-op
  82 **    YY_MIN_REDUCE      Minimum value for reduce actions
  83 **    YY_MAX_REDUCE      Maximum value for reduce actions
  84 */
  85 #ifndef INTERFACE
  86 # define INTERFACE 1
  87 #endif
  88 /************* Begin control #defines *****************************************/
  89 %%
  90 /************* End control #defines *******************************************/
  91
  92 /* Define the yytestcase() macro to be a no-op if is not already defined
  93 ** otherwise.
  94 **
  95 ** Applications can choose to define yytestcase() in the %include section
  96 ** to a macro that can assist in verifying code coverage.  For production
  97 ** code the yytestcase() macro should be turned off.  But it is useful
  98 ** for testing.
  99 */
 100 #ifndef yytestcase
 101 # define yytestcase(X)
 102 #endif
 103
 104
 105 /* Next are the tables used to determine what action to take based on the
 106 ** current state and lookahead token.  These tables are used to implement
 107 ** functions that take a state number and lookahead value and return an
 108 ** action integer.
 109 **
 110 ** Suppose the action integer is N.  Then the action is determined as
 111 ** follows
 112 **
 113 **   0 <= N <= YY_MAX_SHIFT             Shift N.  That is, push the lookahead
 114 **                                      token onto the stack and goto state N.
 115 **
 116 **   N between YY_MIN_SHIFTREDUCE       Shift to an arbitrary state then
 117 **     and YY_MAX_SHIFTREDUCE           reduce by rule N-YY_MIN_SHIFTREDUCE.
 118 **
 119 **   N == YY_ERROR_ACTION               A syntax error has occurred.
 120 **
 121 **   N == YY_ACCEPT_ACTION              The parser accepts its input.
 122 **
 123 **   N == YY_NO_ACTION                  No such action.  Denotes unused
 124 **                                      slots in the yy_action[] table.
 125 **
 126 **   N between YY_MIN_REDUCE            Reduce by rule N-YY_MIN_REDUCE
 127 **     and YY_MAX_REDUCE
 128 **
 129 ** The action table is constructed as a single large table named yy_action[].
 130 ** Given state S and lookahead X, the action is computed as either:
 131 **
 132 **    (A)   N = yy_action[ yy_shift_ofst[S] + X ]
 133 **    (B)   N = yy_default[S]
 134 **
 135 ** The (A) formula is preferred.  The B formula is used instead if
 136 ** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X.
 137 **
 138 ** The formulas above are for computing the action when the lookahead is
 139 ** a terminal symbol.  If the lookahead is a non-terminal (as occurs after
 140 ** a reduce action) then the yy_reduce_ofst[] array is used in place of
 141 ** the yy_shift_ofst[] array.
 142 **
 143 ** The following are the tables generated in this section:
 144 **
 145 **  yy_action[]        A single table containing all actions.
 146 **  yy_lookahead[]     A table containing the lookahead for each entry in
 147 **                     yy_action.  Used to detect hash collisions.
 148 **  yy_shift_ofst[]    For each state, the offset into yy_action for
 149 **                     shifting terminals.
 150 **  yy_reduce_ofst[]   For each state, the offset into yy_action for
 151 **                     shifting non-terminals after a reduce.
 152 **  yy_default[]       Default action for each state.
 153 **
 154 *********** Begin parsing tables **********************************************/
 155 %%
 156 /********** End of lemon-generated parsing tables *****************************/
 157
 158 /* The next table maps tokens (terminal symbols) into fallback tokens.
 159 ** If a construct like the following:
 160 **
 161 **      %fallback ID X Y Z.
 162 **
 163 ** appears in the grammar, then ID becomes a fallback token for X, Y,
 164 ** and Z.  Whenever one of the tokens X, Y, or Z is input to the parser
 165 ** but it does not parse, the type of the token is changed to ID and
 166 ** the parse is retried before an error is thrown.
 167 **
 168 ** This feature can be used, for example, to cause some keywords in a language
 169 ** to revert to identifiers if they keyword does not apply in the context where
 170 ** it appears.
 171 */
 172 #ifdef YYFALLBACK
 173 static const YYCODETYPE yyFallback[] = {
 174 %%
 175 };
 176 #endif /* YYFALLBACK */
 177
 178 /* The following structure represents a single element of the
 179 ** parser's stack.  Information stored includes:
 180 **
 181 **   +  The state number for the parser at this level of the stack.
 182 **
 183 **   +  The value of the token stored at this level of the stack.
 184 **      (In other words, the "major" token.)
 185 **
 186 **   +  The semantic value stored at this level of the stack.  This is
 187 **      the information used by the action routines in the grammar.
 188 **      It is sometimes called the "minor" token.
 189 **
 190 ** After the "shift" half of a SHIFTREDUCE action, the stateno field
 191 ** actually contains the reduce action for the second half of the
 192 ** SHIFTREDUCE.
 193 */
 194 struct yyStackEntry {
 195   YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
 196   YYCODETYPE major;      /* The major token value.  This is the code
 197                          ** number for the token at this stack level */
 198   YYMINORTYPE minor;     /* The user-supplied minor token value.  This
 199                          ** is the value of the token  */
 200 };
 201 typedef struct yyStackEntry yyStackEntry;
 202
 203 /* The state of the parser is completely contained in an instance of
 204 ** the following structure */
 205 struct yyParser {
 206   yyStackEntry *yytos;          /* Pointer to top element of the stack */
 207 #ifdef YYTRACKMAXSTACKDEPTH
 208   int yyhwm;                    /* High-water mark of the stack */
 209 #endif
 210 #ifndef YYNOERRORRECOVERY
 211   int yyerrcnt;                 /* Shifts left before out of the error */
 212 #endif
 213   ParseARG_SDECL                /* A place to hold %extra_argument */
 214 #if YYSTACKDEPTH<=0
 215   int yystksz;                  /* Current side of the stack */
 216   yyStackEntry *yystack;        /* The parser's stack */
 217   yyStackEntry yystk0;          /* First stack entry */
 218 #else
 219   yyStackEntry yystack[YYSTACKDEPTH];  /* The parser's stack */
 220   yyStackEntry *yystackEnd;            /* Last entry in the stack */
 221 #endif
 222 };
 223 typedef struct yyParser yyParser;
 224
 225 #ifndef NDEBUG
 226 #include <stdio.h>
 227 static FILE *yyTraceFILE = 0;
 228 static char *yyTracePrompt = 0;
 229 #endif /* NDEBUG */
 230
 231 #ifndef NDEBUG
 232 /*
 233 ** Turn parser tracing on by giving a stream to which to write the trace
 234 ** and a prompt to preface each trace message.  Tracing is turned off
 235 ** by making either argument NULL
 236 **
 237 ** Inputs:
 238 ** <ul>
 239 ** <li> A FILE* to which trace output should be written.
 240 **      If NULL, then tracing is turned off.
 241 ** <li> A prefix string written at the beginning of every
 242 **      line of trace output.  If NULL, then tracing is
 243 **      turned off.
 244 ** </ul>
 245 **
 246 ** Outputs:
 247 ** None.
 248 */
 249 void ParseTrace(FILE *TraceFILE, char *zTracePrompt){
 250   yyTraceFILE = TraceFILE;
 251   yyTracePrompt = zTracePrompt;
 252   if( yyTraceFILE==0 ) yyTracePrompt = 0;
 253   else if( yyTracePrompt==0 ) yyTraceFILE = 0;
 254 }
 255 #endif /* NDEBUG */
 256
 257 #if defined(YYCOVERAGE) || !defined(NDEBUG)
 258 /* For tracing shifts, the names of all terminals and nonterminals
 259 ** are required.  The following table supplies these names */
 260 static const char *const yyTokenName[] = {
 261 %%
 262 };
 263 #endif /* defined(YYCOVERAGE) || !defined(NDEBUG) */
 264
 265 #ifndef NDEBUG
 266 /* For tracing reduce actions, the names of all rules are required.
 267 */
 268 static const char *const yyRuleName[] = {
 269 %%
 270 };
 271 #endif /* NDEBUG */
 272
 273
 274 #if YYSTACKDEPTH<=0
 275 /*
 276 ** Try to increase the size of the parser stack.  Return the number
 277 ** of errors.  Return 0 on success.
 278 */
 279 static int yyGrowStack(yyParser *p){
 280   int newSize;
 281   int idx;
 282   yyStackEntry *pNew;
 283
 284   newSize = p->yystksz*2 + 100;
 285   idx = p->yytos ? (int)(p->yytos - p->yystack) : 0;
 286   if( p->yystack==&p->yystk0 ){
 287     pNew = malloc(newSize*sizeof(pNew[0]));
 288     if( pNew ) pNew[0] = p->yystk0;
 289   }else{
 290     pNew = realloc(p->yystack, newSize*sizeof(pNew[0]));
 291   }
 292   if( pNew ){
 293     p->yystack = pNew;
 294     p->yytos = &p->yystack[idx];
 295 #ifndef NDEBUG
 296     if( yyTraceFILE ){
 297       fprintf(yyTraceFILE,"%sStack grows from %d to %d entries.\n",
 298               yyTracePrompt, p->yystksz, newSize);
 299     }
 300 #endif
 301     p->yystksz = newSize;
 302   }
 303   return pNew==0;
 304 }
 305 #endif
 306
 307 /* Datatype of the argument to the memory allocated passed as the
 308 ** second argument to ParseAlloc() below.  This can be changed by
 309 ** putting an appropriate #define in the %include section of the input
 310 ** grammar.
 311 */
 312 #ifndef YYMALLOCARGTYPE
 313 # define YYMALLOCARGTYPE size_t
 314 #endif
 315
 316 /* Initialize a new parser that has already been allocated.
 317 */
 318 void ParseInit(void *yypParser){
 319   yyParser *pParser = (yyParser*)yypParser;
 320 #ifdef YYTRACKMAXSTACKDEPTH
 321   pParser->yyhwm = 0;
 322 #endif
 323 #if YYSTACKDEPTH<=0
 324   pParser->yytos = NULL;
 325   pParser->yystack = NULL;
 326   pParser->yystksz = 0;
 327   if( yyGrowStack(pParser) ){
 328     pParser->yystack = &pParser->yystk0;
 329     pParser->yystksz = 1;
 330   }
 331 #endif
 332 #ifndef YYNOERRORRECOVERY
 333   pParser->yyerrcnt = -1;
 334 #endif
 335   pParser->yytos = pParser->yystack;
 336   pParser->yystack[0].stateno = 0;
 337   pParser->yystack[0].major = 0;
 338 #if YYSTACKDEPTH>0
 339   pParser->yystackEnd = &pParser->yystack[YYSTACKDEPTH-1];
 340 #endif
 341 }
 342
 343 #ifndef Parse_ENGINEALWAYSONSTACK
 344 /*
 345 ** This function allocates a new parser.
 346 ** The only argument is a pointer to a function which works like
 347 ** malloc.
 348 **
 349 ** Inputs:
 350 ** A pointer to the function used to allocate memory.
 351 **
 352 ** Outputs:
 353 ** A pointer to a parser.  This pointer is used in subsequent calls
 354 ** to Parse and ParseFree.
 355 */
 356 void *ParseAlloc(void *(*mallocProc)(YYMALLOCARGTYPE)){
 357   yyParser *pParser;
 358   pParser = (yyParser*)(*mallocProc)( (YYMALLOCARGTYPE)sizeof(yyParser) );
 359   if( pParser ) ParseInit(pParser);
 360   return pParser;
 361 }
 362 #endif /* Parse_ENGINEALWAYSONSTACK */
 363
 364
 365 /* The following function deletes the "minor type" or semantic value
 366 ** associated with a symbol.  The symbol can be either a terminal
 367 ** or nonterminal. "yymajor" is the symbol code, and "yypminor" is
 368 ** a pointer to the value to be deleted.  The code used to do the
 369 ** deletions is derived from the %destructor and/or %token_destructor
 370 ** directives of the input grammar.
 371 */
 372 static void yy_destructor(
 373   yyParser *yypParser,    /* The parser */
 374   YYCODETYPE yymajor,     /* Type code for object to destroy */
 375   YYMINORTYPE *yypminor   /* The object to be destroyed */
 376 ){
 377   ParseARG_FETCH;
 378   switch( yymajor ){
 379     /* Here is inserted the actions which take place when a
 380     ** terminal or non-terminal is destroyed.  This can happen
 381     ** when the symbol is popped from the stack during a
 382     ** reduce or during error processing or when a parser is
 383     ** being destroyed before it is finished parsing.
 384     **
 385     ** Note: during a reduce, the only symbols destroyed are those
 386     ** which appear on the RHS of the rule, but which are *not* used
 387     ** inside the C code.
 388     */
 389 /********* Begin destructor definitions ***************************************/
 390 %%
 391 /********* End destructor definitions *****************************************/
 392     default:  break;   /* If no destructor action specified: do nothing */
 393   }
 394 }
 395
 396 /*
 397 ** Pop the parser's stack once.
 398 **
 399 ** If there is a destructor routine associated with the token which
 400 ** is popped from the stack, then call it.
 401 */
 402 static void yy_pop_parser_stack(yyParser *pParser){
 403   yyStackEntry *yytos;
 404   assert( pParser->yytos!=0 );
 405   assert( pParser->yytos > pParser->yystack );
 406   yytos = pParser->yytos--;
 407 #ifndef NDEBUG
 408   if( yyTraceFILE ){
 409     fprintf(yyTraceFILE,"%sPopping %s\n",
 410       yyTracePrompt,
 411       yyTokenName[yytos->major]);
 412   }
 413 #endif
 414   yy_destructor(pParser, yytos->major, &yytos->minor);
 415 }
 416
 417 /*
 418 ** Clear all secondary memory allocations from the parser
 419 */
 420 void ParseFinalize(void *p){
 421   yyParser *pParser = (yyParser*)p;
 422   while( pParser->yytos>pParser->yystack ) yy_pop_parser_stack(pParser);
 423 #if YYSTACKDEPTH<=0
 424   if( pParser->yystack!=&pParser->yystk0 ) free(pParser->yystack);
 425 #endif
 426 }
 427
 428 #ifndef Parse_ENGINEALWAYSONSTACK
 429 /*
 430 ** Deallocate and destroy a parser.  Destructors are called for
 431 ** all stack elements before shutting the parser down.
 432 **
 433 ** If the YYPARSEFREENEVERNULL macro exists (for example because it
 434 ** is defined in a %include section of the input grammar) then it is
 435 ** assumed that the input pointer is never NULL.
 436 */
 437 void ParseFree(
 438   void *p,                    /* The parser to be deleted */
 439   void (*freeProc)(void*)     /* Function used to reclaim memory */
 440 ){
 441 #ifndef YYPARSEFREENEVERNULL
 442   if( p==0 ) return;
 443 #endif
 444   ParseFinalize(p);
 445   (*freeProc)(p);
 446 }
 447 #endif /* Parse_ENGINEALWAYSONSTACK */
 448
 449 /*
 450 ** Return the peak depth of the stack for a parser.
 451 */
 452 #ifdef YYTRACKMAXSTACKDEPTH
 453 int ParseStackPeak(void *p){
 454   yyParser *pParser = (yyParser*)p;
 455   return pParser->yyhwm;
 456 }
 457 #endif
 458
 459 /* This array of booleans keeps track of the parser statement
 460 ** coverage.  The element yycoverage[X][Y] is set when the parser
 461 ** is in state X and has a lookahead token Y.  In a well-tested
 462 ** systems, every element of this matrix should end up being set.
 463 */
 464 #if defined(YYCOVERAGE)
 465 static unsigned char yycoverage[YYNSTATE][YYNTOKEN];
 466 #endif
 467
 468 /*
 469 ** Write into out a description of every state/lookahead combination that
 470 **
 471 **   (1)  has not been used by the parser, and
 472 **   (2)  is not a syntax error.
 473 **
 474 ** Return the number of missed state/lookahead combinations.
 475 */
 476 #if defined(YYCOVERAGE)
 477 int ParseCoverage(FILE *out){
 478   int stateno, iLookAhead, i;
 479   int nMissed = 0;
 480   for(stateno=0; stateno<YYNSTATE; stateno++){
 481     i = yy_shift_ofst[stateno];
 482     for(iLookAhead=0; iLookAhead<YYNTOKEN; iLookAhead++){
 483       if( yy_lookahead[i+iLookAhead]!=iLookAhead ) continue;
 484       if( yycoverage[stateno][iLookAhead]==0 ) nMissed++;
 485       if( out ){
 486         fprintf(out,"State %d lookahead %s %s\n", stateno,
 487                 yyTokenName[iLookAhead],
 488                 yycoverage[stateno][iLookAhead] ? "ok" : "missed");
 489       }
 490     }
 491   }
 492   return nMissed;
 493 }
 494 #endif
 495
 496 /*
 497 ** Find the appropriate action for a parser given the terminal
 498 ** look-ahead token iLookAhead.
 499 */
 500 static unsigned int yy_find_shift_action(
 501   yyParser *pParser,        /* The parser */
 502   YYCODETYPE iLookAhead     /* The look-ahead token */
 503 ){
 504   int i;
 505   int stateno = pParser->yytos->stateno;
 506
 507   if( stateno>YY_MAX_SHIFT ) return stateno;
 508   assert( stateno <= YY_SHIFT_COUNT );
 509 #if defined(YYCOVERAGE)
 510   yycoverage[stateno][iLookAhead] = 1;
 511 #endif
 512   do{
 513     i = yy_shift_ofst[stateno];
 514     assert( i>=0 && i+YYNTOKEN<=sizeof(yy_lookahead)/sizeof(yy_lookahead[0]) );
 515     assert( iLookAhead!=YYNOCODE );
 516     assert( iLookAhead < YYNTOKEN );
 517     i += iLookAhead;
 518     if( yy_lookahead[i]!=iLookAhead ){
 519 #ifdef YYFALLBACK
 520       YYCODETYPE iFallback;            /* Fallback token */
 521       if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
 522              && (iFallback = yyFallback[iLookAhead])!=0 ){
 523 #ifndef NDEBUG
 524         if( yyTraceFILE ){
 525           fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
 526              yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
 527         }
 528 #endif
 529         assert( yyFallback[iFallback]==0 ); /* Fallback loop must terminate */
 530         iLookAhead = iFallback;
 531         continue;
 532       }
 533 #endif
 534 #ifdef YYWILDCARD
 535       {
 536         int j = i - iLookAhead + YYWILDCARD;
 537         if(
 538 #if YY_SHIFT_MIN+YYWILDCARD<0
 539           j>=0 &&
 540 #endif
 541 #if YY_SHIFT_MAX+YYWILDCARD>=YY_ACTTAB_COUNT
 542           j<YY_ACTTAB_COUNT &&
 543 #endif
 544           yy_lookahead[j]==YYWILDCARD && iLookAhead>0
 545         ){
 546 #ifndef NDEBUG
 547           if( yyTraceFILE ){
 548             fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n",
 549                yyTracePrompt, yyTokenName[iLookAhead],
 550                yyTokenName[YYWILDCARD]);
 551           }
 552 #endif /* NDEBUG */
 553           return yy_action[j];
 554         }
 555       }
 556 #endif /* YYWILDCARD */
 557       return yy_default[stateno];
 558     }else{
 559       return yy_action[i];
 560     }
 561   }while(1);
 562 }
 563
 564 /*
 565 ** Find the appropriate action for a parser given the non-terminal
 566 ** look-ahead token iLookAhead.
 567 */
 568 static int yy_find_reduce_action(
 569   int stateno,              /* Current state number */
 570   YYCODETYPE iLookAhead     /* The look-ahead token */
 571 ){
 572   int i;
 573 #ifdef YYERRORSYMBOL
 574   if( stateno>YY_REDUCE_COUNT ){
 575     return yy_default[stateno];
 576   }
 577 #else
 578   assert( stateno<=YY_REDUCE_COUNT );
 579 #endif
 580   i = yy_reduce_ofst[stateno];
 581   assert( iLookAhead!=YYNOCODE );
 582   i += iLookAhead;
 583 #ifdef YYERRORSYMBOL
 584   if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
 585     return yy_default[stateno];
 586   }
 587 #else
 588   assert( i>=0 && i<YY_ACTTAB_COUNT );
 589   assert( yy_lookahead[i]==iLookAhead );
 590 #endif
 591   return yy_action[i];
 592 }
 593
 594 /*
 595 ** The following routine is called if the stack overflows.
 596 */
 597 static void yyStackOverflow(yyParser *yypParser){
 598    ParseARG_FETCH;
 599 #ifndef NDEBUG
 600    if( yyTraceFILE ){
 601      fprintf(yyTraceFILE,"%sStack Overflow!\n",yyTracePrompt);
 602    }
 603 #endif
 604    while( yypParser->yytos>yypParser->yystack ) yy_pop_parser_stack(yypParser);
 605    /* Here code is inserted which will execute if the parser
 606    ** stack every overflows */
 607 /******** Begin %stack_overflow code ******************************************/
 608 %%
 609 /******** End %stack_overflow code ********************************************/
 610    ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
 611 }
 612
 613 /*
 614 ** Print tracing information for a SHIFT action
 615 */
 616 #ifndef NDEBUG
 617 static void yyTraceShift(yyParser *yypParser, int yyNewState, const char *zTag){
 618   if( yyTraceFILE ){
 619     if( yyNewState<YYNSTATE ){
 620       fprintf(yyTraceFILE,"%s%s '%s', go to state %d\n",
 621          yyTracePrompt, zTag, yyTokenName[yypParser->yytos->major],
 622          yyNewState);
 623     }else{
 624       fprintf(yyTraceFILE,"%s%s '%s', pending reduce %d\n",
 625          yyTracePrompt, zTag, yyTokenName[yypParser->yytos->major],
 626          yyNewState - YY_MIN_REDUCE);
 627     }
 628   }
 629 }
 630 #else
 631 # define yyTraceShift(X,Y,Z)
 632 #endif
 633
 634 /*
 635 ** Perform a shift action.
 636 */
 637 static void yy_shift(
 638   yyParser *yypParser,          /* The parser to be shifted */
 639   int yyNewState,               /* The new state to shift in */
 640   int yyMajor,                  /* The major token to shift in */
 641   ParseTOKENTYPE yyMinor        /* The minor token to shift in */
 642 ){
 643   yyStackEntry *yytos;
 644   yypParser->yytos++;
 645 #ifdef YYTRACKMAXSTACKDEPTH
 646   if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){
 647     yypParser->yyhwm++;
 648     assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack) );
 649   }
 650 #endif
 651 #if YYSTACKDEPTH>0
 652   if( yypParser->yytos>yypParser->yystackEnd ){
 653     yypParser->yytos--;
 654     yyStackOverflow(yypParser);
 655     return;
 656   }
 657 #else
 658   if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz] ){
 659     if( yyGrowStack(yypParser) ){
 660       yypParser->yytos--;
 661       yyStackOverflow(yypParser);
 662       return;
 663     }
 664   }
 665 #endif
 666   if( yyNewState > YY_MAX_SHIFT ){
 667     yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
 668   }
 669   yytos = yypParser->yytos;
 670   yytos->stateno = (YYACTIONTYPE)yyNewState;
 671   yytos->major = (YYCODETYPE)yyMajor;
 672   yytos->minor.yy0 = yyMinor;
 673   yyTraceShift(yypParser, yyNewState, "Shift");
 674 }
 675
 676 /* The following table contains information about every rule that
 677 ** is used during the reduce.
 678 */
 679 static const struct {
 680   YYCODETYPE lhs;       /* Symbol on the left-hand side of the rule */
 681   signed char nrhs;     /* Negative of the number of RHS symbols in the rule */
 682 } yyRuleInfo[] = {
 683 %%
 684 };
 685
 686 static void yy_accept(yyParser*);  /* Forward Declaration */
 687
 688 /*
 689 ** Perform a reduce action and the shift that must immediately
 690 ** follow the reduce.
 691 **
 692 ** The yyLookahead and yyLookaheadToken parameters provide reduce actions
 693 ** access to the lookahead token (if any).  The yyLookahead will be YYNOCODE
 694 ** if the lookahead token has already been consumed.  As this procedure is
 695 ** only called from one place, optimizing compilers will in-line it, which
 696 ** means that the extra parameters have no performance impact.
 697 */
 698 static void yy_reduce(
 699   yyParser *yypParser,         /* The parser */
 700   unsigned int yyruleno,       /* Number of the rule by which to reduce */
 701   int yyLookahead,             /* Lookahead token, or YYNOCODE if none */
 702   ParseTOKENTYPE yyLookaheadToken  /* Value of the lookahead token */
 703 ){
 704   int yygoto;                     /* The next state */
 705   int yyact;                      /* The next action */
 706   yyStackEntry *yymsp;            /* The top of the parser's stack */
 707   int yysize;                     /* Amount to pop the stack */
 708   ParseARG_FETCH;
 709   yymsp = yypParser->yytos;
 710 #ifndef NDEBUG
 711   if( yyTraceFILE && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){
 712     yysize = yyRuleInfo[yyruleno].nrhs;
 713     if( yysize ){
 714       fprintf(yyTraceFILE, "%sReduce %d [%s], go to state %d.\n",
 715         yyTracePrompt,
 716         yyruleno, yyRuleName[yyruleno], yymsp[yysize].stateno);
 717     }else{
 718       fprintf(yyTraceFILE, "%sReduce %d [%s].\n",
 719         yyTracePrompt, yyruleno, yyRuleName[yyruleno]);
 720     }
 721   }
 722 #endif /* NDEBUG */
 723
 724   /* Check that the stack is large enough to grow by a single entry
 725   ** if the RHS of the rule is empty.  This ensures that there is room
 726   ** enough on the stack to push the LHS value */
 727   if( yyRuleInfo[yyruleno].nrhs==0 ){
 728 #ifdef YYTRACKMAXSTACKDEPTH
 729     if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){
 730       yypParser->yyhwm++;
 731       assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack));
 732     }
 733 #endif
 734 #if YYSTACKDEPTH>0
 735     if( yypParser->yytos>=yypParser->yystackEnd ){
 736       yyStackOverflow(yypParser);
 737       return;
 738     }
 739 #else
 740     if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){
 741       if( yyGrowStack(yypParser) ){
 742         yyStackOverflow(yypParser);
 743         return;
 744       }
 745       yymsp = yypParser->yytos;
 746     }
 747 #endif
 748   }
 749
 750   switch( yyruleno ){
 751   /* Beginning here are the reduction cases.  A typical example
 752   ** follows:
 753   **   case 0:
 754   **  #line <lineno> <grammarfile>
 755   **     { ... }           // User supplied code
 756   **  #line <lineno> <thisfile>
 757   **     break;
 758   */
 759 /********** Begin reduce actions **********************************************/
 760 %%
 761 /********** End reduce actions ************************************************/
 762   };
 763   assert( yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) );
 764   yygoto = yyRuleInfo[yyruleno].lhs;
 765   yysize = yyRuleInfo[yyruleno].nrhs;
 766   yyact = yy_find_reduce_action(yymsp[yysize].stateno,(YYCODETYPE)yygoto);
 767
 768   /* There are no SHIFTREDUCE actions on nonterminals because the table
 769   ** generator has simplified them to pure REDUCE actions. */
 770   assert( !(yyact>YY_MAX_SHIFT && yyact<=YY_MAX_SHIFTREDUCE) );
 771
 772   /* It is not possible for a REDUCE to be followed by an error */
 773   assert( yyact!=YY_ERROR_ACTION );
 774
 775   yymsp += yysize+1;
 776   yypParser->yytos = yymsp;
 777   yymsp->stateno = (YYACTIONTYPE)yyact;
 778   yymsp->major = (YYCODETYPE)yygoto;
 779   yyTraceShift(yypParser, yyact, "... then shift");
 780 }
 781
 782 /*
 783 ** The following code executes when the parse fails
 784 */
 785 #ifndef YYNOERRORRECOVERY
 786 static void yy_parse_failed(
 787   yyParser *yypParser           /* The parser */
 788 ){
 789   ParseARG_FETCH;
 790 #ifndef NDEBUG
 791   if( yyTraceFILE ){
 792     fprintf(yyTraceFILE,"%sFail!\n",yyTracePrompt);
 793   }
 794 #endif
 795   while( yypParser->yytos>yypParser->yystack ) yy_pop_parser_stack(yypParser);
 796   /* Here code is inserted which will be executed whenever the
 797   ** parser fails */
 798 /************ Begin %parse_failure code ***************************************/
 799 %%
 800 /************ End %parse_failure code *****************************************/
 801   ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */
 802 }
 803 #endif /* YYNOERRORRECOVERY */
 804
 805 /*
 806 ** The following code executes when a syntax error first occurs.
 807 */
 808 static void yy_syntax_error(
 809   yyParser *yypParser,           /* The parser */
 810   int yymajor,                   /* The major type of the error token */
 811   ParseTOKENTYPE yyminor         /* The minor type of the error token */
 812 ){
 813   ParseARG_FETCH;
 814 #define TOKEN yyminor
 815 /************ Begin %syntax_error code ****************************************/
 816 %%
 817 /************ End %syntax_error code ******************************************/
 818   ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */
 819 }
 820
 821 /*
 822 ** The following is executed when the parser accepts
 823 */
 824 static void yy_accept(
 825   yyParser *yypParser           /* The parser */
 826 ){
 827   ParseARG_FETCH;
 828 #ifndef NDEBUG
 829   if( yyTraceFILE ){
 830     fprintf(yyTraceFILE,"%sAccept!\n",yyTracePrompt);
 831   }
 832 #endif
 833 #ifndef YYNOERRORRECOVERY
 834   yypParser->yyerrcnt = -1;
 835 #endif
 836   assert( yypParser->yytos==yypParser->yystack );
 837   /* Here code is inserted which will be executed whenever the
 838   ** parser accepts */
 839 /*********** Begin %parse_accept code *****************************************/
 840 %%
 841 /*********** End %parse_accept code *******************************************/
 842   ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */
 843 }
 844
 845 /* The main parser program.
 846 ** The first argument is a pointer to a structure obtained from
 847 ** "ParseAlloc" which describes the current state of the parser.
 848 ** The second argument is the major token number.  The third is
 849 ** the minor token.  The fourth optional argument is whatever the
 850 ** user wants (and specified in the grammar) and is available for
 851 ** use by the action routines.
 852 **
 853 ** Inputs:
 854 ** <ul>
 855 ** <li> A pointer to the parser (an opaque structure.)
 856 ** <li> The major token number.
 857 ** <li> The minor token number.
 858 ** <li> An option argument of a grammar-specified type.
 859 ** </ul>
 860 **
 861 ** Outputs:
 862 ** None.
 863 */
 864 void Parse(
 865   void *yyp,                   /* The parser */
 866   int yymajor,                 /* The major token code number */
 867   ParseTOKENTYPE yyminor       /* The value for the token */
 868   ParseARG_PDECL               /* Optional %extra_argument parameter */
 869 ){
 870   YYMINORTYPE yyminorunion;
 871   unsigned int yyact;   /* The parser action. */
 872 #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
 873   int yyendofinput;     /* True if we are at the end of input */
 874 #endif
 875 #ifdef YYERRORSYMBOL
 876   int yyerrorhit = 0;   /* True if yymajor has invoked an error */
 877 #endif
 878   yyParser *yypParser;  /* The parser */
 879
 880   yypParser = (yyParser*)yyp;
 881   assert( yypParser->yytos!=0 );
 882 #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
 883   yyendofinput = (yymajor==0);
 884 #endif
 885   ParseARG_STORE;
 886
 887 #ifndef NDEBUG
 888   if( yyTraceFILE ){
 889     int stateno = yypParser->yytos->stateno;
 890     if( stateno < YY_MIN_REDUCE ){
 891       fprintf(yyTraceFILE,"%sInput '%s' in state %d\n",
 892               yyTracePrompt,yyTokenName[yymajor],stateno);
 893     }else{
 894       fprintf(yyTraceFILE,"%sInput '%s' with pending reduce %d\n",
 895               yyTracePrompt,yyTokenName[yymajor],stateno-YY_MIN_REDUCE);
 896     }
 897   }
 898 #endif
 899
 900   do{
 901     yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
 902     if( yyact >= YY_MIN_REDUCE ){
 903       yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor);
 904     }else if( yyact <= YY_MAX_SHIFTREDUCE ){
 905       yy_shift(yypParser,yyact,yymajor,yyminor);
 906 #ifndef YYNOERRORRECOVERY
 907       yypParser->yyerrcnt--;
 908 #endif
 909       yymajor = YYNOCODE;
 910     }else if( yyact==YY_ACCEPT_ACTION ){
 911       yypParser->yytos--;
 912       yy_accept(yypParser);
 913       return;
 914     }else{
 915       assert( yyact == YY_ERROR_ACTION );
 916       yyminorunion.yy0 = yyminor;
 917 #ifdef YYERRORSYMBOL
 918       int yymx;
 919 #endif
 920 #ifndef NDEBUG
 921       if( yyTraceFILE ){
 922         fprintf(yyTraceFILE,"%sSyntax Error!\n",yyTracePrompt);
 923       }
 924 #endif
 925 #ifdef YYERRORSYMBOL
 926       /* A syntax error has occurred.
 927       ** The response to an error depends upon whether or not the
 928       ** grammar defines an error token "ERROR".
 929       **
 930       ** This is what we do if the grammar does define ERROR:
 931       **
 932       **  * Call the %syntax_error function.
 933       **
 934       **  * Begin popping the stack until we enter a state where
 935       **    it is legal to shift the error symbol, then shift
 936       **    the error symbol.
 937       **
 938       **  * Set the error count to three.
 939       **
 940       **  * Begin accepting and shifting new tokens.  No new error
 941       **    processing will occur until three tokens have been
 942       **    shifted successfully.
 943       **
 944       */
 945       if( yypParser->yyerrcnt<0 ){
 946         yy_syntax_error(yypParser,yymajor,yyminor);
 947       }
 948       yymx = yypParser->yytos->major;
 949       if( yymx==YYERRORSYMBOL || yyerrorhit ){
 950 #ifndef NDEBUG
 951         if( yyTraceFILE ){
 952           fprintf(yyTraceFILE,"%sDiscard input token %s\n",
 953              yyTracePrompt,yyTokenName[yymajor]);
 954         }
 955 #endif
 956         yy_destructor(yypParser, (YYCODETYPE)yymajor, &yyminorunion);
 957         yymajor = YYNOCODE;
 958       }else{
 959         while( yypParser->yytos >= yypParser->yystack
 960             && yymx != YYERRORSYMBOL
 961             && (yyact = yy_find_reduce_action(
 962                         yypParser->yytos->stateno,
 963                         YYERRORSYMBOL)) >= YY_MIN_REDUCE
 964         ){
 965           yy_pop_parser_stack(yypParser);
 966         }
 967         if( yypParser->yytos < yypParser->yystack || yymajor==0 ){
 968           yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
 969           yy_parse_failed(yypParser);
 970 #ifndef YYNOERRORRECOVERY
 971           yypParser->yyerrcnt = -1;
 972 #endif
 973           yymajor = YYNOCODE;
 974         }else if( yymx!=YYERRORSYMBOL ){
 975           yy_shift(yypParser,yyact,YYERRORSYMBOL,yyminor);
 976         }
 977       }
 978       yypParser->yyerrcnt = 3;
 979       yyerrorhit = 1;
 980 #elif defined(YYNOERRORRECOVERY)
 981       /* If the YYNOERRORRECOVERY macro is defined, then do not attempt to
 982       ** do any kind of error recovery.  Instead, simply invoke the syntax
 983       ** error routine and continue going as if nothing had happened.
 984       **
 985       ** Applications can set this macro (for example inside %include) if
 986       ** they intend to abandon the parse upon the first syntax error seen.
 987       */
 988       yy_syntax_error(yypParser,yymajor, yyminor);
 989       yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
 990       yymajor = YYNOCODE;
 991
 992 #else  /* YYERRORSYMBOL is not defined */
 993       /* This is what we do if the grammar does not define ERROR:
 994       **
 995       **  * Report an error message, and throw away the input token.
 996       **
 997       **  * If the input token is $, then fail the parse.
 998       **
 999       ** As before, subsequent error messages are suppressed until
1000       ** three input tokens have been successfully shifted.
1001       */
1002       if( yypParser->yyerrcnt<=0 ){
1003         yy_syntax_error(yypParser,yymajor, yyminor);
1004       }
1005       yypParser->yyerrcnt = 3;
1006       yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
1007       if( yyendofinput ){
1008         yy_parse_failed(yypParser);
1009 #ifndef YYNOERRORRECOVERY
1010         yypParser->yyerrcnt = -1;
1011 #endif
1012       }
1013       yymajor = YYNOCODE;
1014 #endif
1015     }
1016   }while( yymajor!=YYNOCODE && yypParser->yytos>yypParser->yystack );
1017 #ifndef NDEBUG
1018   if( yyTraceFILE ){
1019     yyStackEntry *i;
1020     char cDiv = '[';
1021     fprintf(yyTraceFILE,"%sReturn. Stack=",yyTracePrompt);
1022     for(i=&yypParser->yystack[1]; i<=yypParser->yytos; i++){
1023       fprintf(yyTraceFILE,"%c%s", cDiv, yyTokenName[i->major]);
1024       cDiv = ' ';
1025     }
1026     fprintf(yyTraceFILE,"]\n");
1027   }
1028 #endif
1029   return;
1030 }