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