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