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 **    YY_MAX_SHIFT       Maximum value for shift actions
  76 **    YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions
  77 **    YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions
  78 **    YY_MIN_REDUCE      Minimum value for reduce actions
  79 **    YY_MAX_REDUCE      Maximum value for reduce actions
  80 **    YY_ERROR_ACTION    The yy_action[] code for syntax error
  81 **    YY_ACCEPT_ACTION   The yy_action[] code for accept
  82 **    YY_NO_ACTION       The yy_action[] code for no-op
  83 */
  84 #ifndef INTERFACE
  85 # define INTERFACE 1
  86 #endif
  87 /************* Begin control #defines *****************************************/
  88 %%
  89 /************* End control #defines *******************************************/
  90
  91 /* Define the yytestcase() macro to be a no-op if is not already defined
  92 ** otherwise.
  93 **
  94 ** Applications can choose to define yytestcase() in the %include section
  95 ** to a macro that can assist in verifying code coverage.  For production
  96 ** code the yytestcase() macro should be turned off.  But it is useful
  97 ** for testing.
  98 */
  99 #ifndef yytestcase
 100 # define yytestcase(X)
 101 #endif
 102
 103
 104 /* Next are the tables used to determine what action to take based on the
 105 ** current state and lookahead token.  These tables are used to implement
 106 ** functions that take a state number and lookahead value and return an
 107 ** action integer.
 108 **
 109 ** Suppose the action integer is N.  Then the action is determined as
 110 ** follows
 111 **
 112 **   0 <= N <= YY_MAX_SHIFT             Shift N.  That is, push the lookahead
 113 **                                      token onto the stack and goto state N.
 114 **
 115 **   N between YY_MIN_SHIFTREDUCE       Shift to an arbitrary state then
 116 **     and YY_MAX_SHIFTREDUCE           reduce by rule N-YY_MIN_SHIFTREDUCE.
 117 **
 118 **   N between YY_MIN_REDUCE            Reduce by rule N-YY_MIN_REDUCE
 119 **     and YY_MAX_REDUCE
 120 **
 121 **   N == YY_ERROR_ACTION               A syntax error has occurred.
 122 **
 123 **   N == YY_ACCEPT_ACTION              The parser accepts its input.
 124 **
 125 **   N == YY_NO_ACTION                  No such action.  Denotes unused
 126 **                                      slots in the yy_action[] table.
 127 **
 128 ** The action table is constructed as a single large table named yy_action[].
 129 ** Given state S and lookahead X, the action is computed as either:
 130 **
 131 **    (A)   N = yy_action[ yy_shift_ofst[S] + X ]
 132 **    (B)   N = yy_default[S]
 133 **
 134 ** The (A) formula is preferred.  The B formula is used instead if:
 135 **    (1)  The yy_shift_ofst[S]+X value is out of range, or
 136 **    (2)  yy_lookahead[yy_shift_ofst[S]+X] is not equal to X, or
 137 **    (3)  yy_shift_ofst[S] equal YY_SHIFT_USE_DFLT.
 138 ** (Implementation note: YY_SHIFT_USE_DFLT is chosen so that
 139 ** YY_SHIFT_USE_DFLT+X will be out of range for all possible lookaheads X.
 140 ** Hence only tests (1) and (2) need to be evaluated.)
 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 and YY_REDUCE_USE_DFLT is used in place of
 146 ** YY_SHIFT_USE_DFLT.
 147 **
 148 ** The following are the tables generated in this section:
 149 **
 150 **  yy_action[]        A single table containing all actions.
 151 **  yy_lookahead[]     A table containing the lookahead for each entry in
 152 **                     yy_action.  Used to detect hash collisions.
 153 **  yy_shift_ofst[]    For each state, the offset into yy_action for
 154 **                     shifting terminals.
 155 **  yy_reduce_ofst[]   For each state, the offset into yy_action for
 156 **                     shifting non-terminals after a reduce.
 157 **  yy_default[]       Default action for each state.
 158 **
 159 *********** Begin parsing tables **********************************************/
 160 %%
 161 /********** End of lemon-generated parsing tables *****************************/
 162
 163 /* The next table maps tokens (terminal symbols) into fallback tokens.
 164 ** If a construct like the following:
 165 **
 166 **      %fallback ID X Y Z.
 167 **
 168 ** appears in the grammar, then ID becomes a fallback token for X, Y,
 169 ** and Z.  Whenever one of the tokens X, Y, or Z is input to the parser
 170 ** but it does not parse, the type of the token is changed to ID and
 171 ** the parse is retried before an error is thrown.
 172 **
 173 ** This feature can be used, for example, to cause some keywords in a language
 174 ** to revert to identifiers if they keyword does not apply in the context where
 175 ** it appears.
 176 */
 177 #ifdef YYFALLBACK
 178 static const YYCODETYPE yyFallback[] = {
 179 %%
 180 };
 181 #endif /* YYFALLBACK */
 182
 183 /* The following structure represents a single element of the
 184 ** parser's stack.  Information stored includes:
 185 **
 186 **   +  The state number for the parser at this level of the stack.
 187 **
 188 **   +  The value of the token stored at this level of the stack.
 189 **      (In other words, the "major" token.)
 190 **
 191 **   +  The semantic value stored at this level of the stack.  This is
 192 **      the information used by the action routines in the grammar.
 193 **      It is sometimes called the "minor" token.
 194 **
 195 ** After the "shift" half of a SHIFTREDUCE action, the stateno field
 196 ** actually contains the reduce action for the second half of the
 197 ** SHIFTREDUCE.
 198 */
 199 struct yyStackEntry {
 200   YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
 201   YYCODETYPE major;      /* The major token value.  This is the code
 202                          ** number for the token at this stack level */
 203   YYMINORTYPE minor;     /* The user-supplied minor token value.  This
 204                          ** is the value of the token  */
 205 };
 206 typedef struct yyStackEntry yyStackEntry;
 207
 208 /* The state of the parser is completely contained in an instance of
 209 ** the following structure */
 210 struct yyParser {
 211   yyStackEntry *yytos;          /* Pointer to top element of the stack */
 212 #ifdef YYTRACKMAXSTACKDEPTH
 213   int yyhwm;                    /* High-water mark of the stack */
 214 #endif
 215 #ifndef YYNOERRORRECOVERY
 216   int yyerrcnt;                 /* Shifts left before out of the error */
 217 #endif
 218   ParseARG_SDECL                /* A place to hold %extra_argument */
 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 #ifndef 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 /* 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 *yypParser){
 324   yyParser *pParser = (yyParser*)yypParser;
 325 #ifdef YYTRACKMAXSTACKDEPTH
 326   pParser->yyhwm = 0;
 327 #endif
 328 #if YYSTACKDEPTH<=0
 329   pParser->yytos = NULL;
 330   pParser->yystack = NULL;
 331   pParser->yystksz = 0;
 332   if( yyGrowStack(pParser) ){
 333     pParser->yystack = &pParser->yystk0;
 334     pParser->yystksz = 1;
 335   }
 336 #endif
 337 #ifndef YYNOERRORRECOVERY
 338   pParser->yyerrcnt = -1;
 339 #endif
 340   pParser->yytos = pParser->yystack;
 341   pParser->yystack[0].stateno = 0;
 342   pParser->yystack[0].major = 0;
 343 #if YYSTACKDEPTH>0
 344   pParser->yystackEnd = &pParser->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)){
 362   yyParser *pParser;
 363   pParser = (yyParser*)(*mallocProc)( (YYMALLOCARGTYPE)sizeof(yyParser) );
 364   if( pParser ) ParseInit(pParser);
 365   return pParser;
 366 }
 367 #endif /* Parse_ENGINEALWAYSONSTACK */
 368
 369
 370 /* The following function deletes the "minor type" or semantic value
 371 ** associated with a symbol.  The symbol can be either a terminal
 372 ** or nonterminal. "yymajor" is the symbol code, and "yypminor" is
 373 ** a pointer to the value to be deleted.  The code used to do the
 374 ** deletions is derived from the %destructor and/or %token_destructor
 375 ** directives of the input grammar.
 376 */
 377 static void yy_destructor(
 378   yyParser *yypParser,    /* The parser */
 379   YYCODETYPE yymajor,     /* Type code for object to destroy */
 380   YYMINORTYPE *yypminor   /* The object to be destroyed */
 381 ){
 382   ParseARG_FETCH;
 383   switch( yymajor ){
 384     /* Here is inserted the actions which take place when a
 385     ** terminal or non-terminal is destroyed.  This can happen
 386     ** when the symbol is popped from the stack during a
 387     ** reduce or during error processing or when a parser is
 388     ** being destroyed before it is finished parsing.
 389     **
 390     ** Note: during a reduce, the only symbols destroyed are those
 391     ** which appear on the RHS of the rule, but which are *not* used
 392     ** inside the C code.
 393     */
 394 /********* Begin destructor definitions ***************************************/
 395 %%
 396 /********* End destructor definitions *****************************************/
 397     default:  break;   /* If no destructor action specified: do nothing */
 398   }
 399 }
 400
 401 /*
 402 ** Pop the parser's stack once.
 403 **
 404 ** If there is a destructor routine associated with the token which
 405 ** is popped from the stack, then call it.
 406 */
 407 static void yy_pop_parser_stack(yyParser *pParser){
 408   yyStackEntry *yytos;
 409   assert( pParser->yytos!=0 );
 410   assert( pParser->yytos > pParser->yystack );
 411   yytos = pParser->yytos--;
 412 #ifndef NDEBUG
 413   if( yyTraceFILE ){
 414     fprintf(yyTraceFILE,"%sPopping %s\n",
 415       yyTracePrompt,
 416       yyTokenName[yytos->major]);
 417   }
 418 #endif
 419   yy_destructor(pParser, yytos->major, &yytos->minor);
 420 }
 421
 422 /*
 423 ** Clear all secondary memory allocations from the parser
 424 */
 425 void ParseFinalize(void *p){
 426   yyParser *pParser = (yyParser*)p;
 427   while( pParser->yytos>pParser->yystack ) yy_pop_parser_stack(pParser);
 428 #if YYSTACKDEPTH<=0
 429   if( pParser->yystack!=&pParser->yystk0 ) free(pParser->yystack);
 430 #endif
 431 }
 432
 433 #ifndef Parse_ENGINEALWAYSONSTACK
 434 /*
 435 ** Deallocate and destroy a parser.  Destructors are called for
 436 ** all stack elements before shutting the parser down.
 437 **
 438 ** If the YYPARSEFREENEVERNULL macro exists (for example because it
 439 ** is defined in a %include section of the input grammar) then it is
 440 ** assumed that the input pointer is never NULL.
 441 */
 442 void ParseFree(
 443   void *p,                    /* The parser to be deleted */
 444   void (*freeProc)(void*)     /* Function used to reclaim memory */
 445 ){
 446 #ifndef YYPARSEFREENEVERNULL
 447   if( p==0 ) return;
 448 #endif
 449   ParseFinalize(p);
 450   (*freeProc)(p);
 451 }
 452 #endif /* Parse_ENGINEALWAYSONSTACK */
 453
 454 /*
 455 ** Return the peak depth of the stack for a parser.
 456 */
 457 #ifdef YYTRACKMAXSTACKDEPTH
 458 int ParseStackPeak(void *p){
 459   yyParser *pParser = (yyParser*)p;
 460   return pParser->yyhwm;
 461 }
 462 #endif
 463
 464 /*
 465 ** Find the appropriate action for a parser given the terminal
 466 ** look-ahead token iLookAhead.
 467 */
 468 static unsigned int yy_find_shift_action(
 469   yyParser *pParser,        /* The parser */
 470   YYCODETYPE iLookAhead     /* The look-ahead token */
 471 ){
 472   int i;
 473   int stateno = pParser->yytos->stateno;
 474
 475   if( stateno>=YY_MIN_REDUCE ) return stateno;
 476   assert( stateno <= YY_SHIFT_COUNT );
 477   do{
 478     i = yy_shift_ofst[stateno];
 479     assert( iLookAhead!=YYNOCODE );
 480     i += iLookAhead;
 481     if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
 482 #ifdef YYFALLBACK
 483       YYCODETYPE iFallback;            /* Fallback token */
 484       if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
 485              && (iFallback = yyFallback[iLookAhead])!=0 ){
 486 #ifndef NDEBUG
 487         if( yyTraceFILE ){
 488           fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
 489              yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
 490         }
 491 #endif
 492         assert( yyFallback[iFallback]==0 ); /* Fallback loop must terminate */
 493         iLookAhead = iFallback;
 494         continue;
 495       }
 496 #endif
 497 #ifdef YYWILDCARD
 498       {
 499         int j = i - iLookAhead + YYWILDCARD;
 500         if(
 501 #if YY_SHIFT_MIN+YYWILDCARD<0
 502           j>=0 &&
 503 #endif
 504 #if YY_SHIFT_MAX+YYWILDCARD>=YY_ACTTAB_COUNT
 505           j<YY_ACTTAB_COUNT &&
 506 #endif
 507           yy_lookahead[j]==YYWILDCARD && iLookAhead>0
 508         ){
 509 #ifndef NDEBUG
 510           if( yyTraceFILE ){
 511             fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n",
 512                yyTracePrompt, yyTokenName[iLookAhead],
 513                yyTokenName[YYWILDCARD]);
 514           }
 515 #endif /* NDEBUG */
 516           return yy_action[j];
 517         }
 518       }
 519 #endif /* YYWILDCARD */
 520       return yy_default[stateno];
 521     }else{
 522       return yy_action[i];
 523     }
 524   }while(1);
 525 }
 526
 527 /*
 528 ** Find the appropriate action for a parser given the non-terminal
 529 ** look-ahead token iLookAhead.
 530 */
 531 static int yy_find_reduce_action(
 532   int stateno,              /* Current state number */
 533   YYCODETYPE iLookAhead     /* The look-ahead token */
 534 ){
 535   int i;
 536 #ifdef YYERRORSYMBOL
 537   if( stateno>YY_REDUCE_COUNT ){
 538     return yy_default[stateno];
 539   }
 540 #else
 541   assert( stateno<=YY_REDUCE_COUNT );
 542 #endif
 543   i = yy_reduce_ofst[stateno];
 544   assert( i!=YY_REDUCE_USE_DFLT );
 545   assert( iLookAhead!=YYNOCODE );
 546   i += iLookAhead;
 547 #ifdef YYERRORSYMBOL
 548   if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
 549     return yy_default[stateno];
 550   }
 551 #else
 552   assert( i>=0 && i<YY_ACTTAB_COUNT );
 553   assert( yy_lookahead[i]==iLookAhead );
 554 #endif
 555   return yy_action[i];
 556 }
 557
 558 /*
 559 ** The following routine is called if the stack overflows.
 560 */
 561 static void yyStackOverflow(yyParser *yypParser){
 562    ParseARG_FETCH;
 563 #ifndef NDEBUG
 564    if( yyTraceFILE ){
 565      fprintf(yyTraceFILE,"%sStack Overflow!\n",yyTracePrompt);
 566    }
 567 #endif
 568    while( yypParser->yytos>yypParser->yystack ) yy_pop_parser_stack(yypParser);
 569    /* Here code is inserted which will execute if the parser
 570    ** stack every overflows */
 571 /******** Begin %stack_overflow code ******************************************/
 572 %%
 573 /******** End %stack_overflow code ********************************************/
 574    ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
 575 }
 576
 577 /*
 578 ** Print tracing information for a SHIFT action
 579 */
 580 #ifndef NDEBUG
 581 static void yyTraceShift(yyParser *yypParser, int yyNewState){
 582   if( yyTraceFILE ){
 583     if( yyNewState<YYNSTATE ){
 584       fprintf(yyTraceFILE,"%sShift '%s', go to state %d\n",
 585          yyTracePrompt,yyTokenName[yypParser->yytos->major],
 586          yyNewState);
 587     }else{
 588       fprintf(yyTraceFILE,"%sShift '%s'\n",
 589          yyTracePrompt,yyTokenName[yypParser->yytos->major]);
 590     }
 591   }
 592 }
 593 #else
 594 # define yyTraceShift(X,Y)
 595 #endif
 596
 597 /*
 598 ** Perform a shift action.
 599 */
 600 static void yy_shift(
 601   yyParser *yypParser,          /* The parser to be shifted */
 602   int yyNewState,               /* The new state to shift in */
 603   int yyMajor,                  /* The major token to shift in */
 604   ParseTOKENTYPE yyMinor        /* The minor token to shift in */
 605 ){
 606   yyStackEntry *yytos;
 607   yypParser->yytos++;
 608 #ifdef YYTRACKMAXSTACKDEPTH
 609   if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){
 610     yypParser->yyhwm++;
 611     assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack) );
 612   }
 613 #endif
 614 #if YYSTACKDEPTH>0
 615   if( yypParser->yytos>yypParser->yystackEnd ){
 616     yypParser->yytos--;
 617     yyStackOverflow(yypParser);
 618     return;
 619   }
 620 #else
 621   if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz] ){
 622     if( yyGrowStack(yypParser) ){
 623       yypParser->yytos--;
 624       yyStackOverflow(yypParser);
 625       return;
 626     }
 627   }
 628 #endif
 629   if( yyNewState > YY_MAX_SHIFT ){
 630     yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
 631   }
 632   yytos = yypParser->yytos;
 633   yytos->stateno = (YYACTIONTYPE)yyNewState;
 634   yytos->major = (YYCODETYPE)yyMajor;
 635   yytos->minor.yy0 = yyMinor;
 636   yyTraceShift(yypParser, yyNewState);
 637 }
 638
 639 /* The following table contains information about every rule that
 640 ** is used during the reduce.
 641 */
 642 static const struct {
 643   YYCODETYPE lhs;       /* Symbol on the left-hand side of the rule */
 644   signed char nrhs;     /* Negative of the number of RHS symbols in the rule */
 645 } yyRuleInfo[] = {
 646 %%
 647 };
 648
 649 static void yy_accept(yyParser*);  /* Forward Declaration */
 650
 651 /*
 652 ** Perform a reduce action and the shift that must immediately
 653 ** follow the reduce.
 654 */
 655 static void yy_reduce(
 656   yyParser *yypParser,         /* The parser */
 657   unsigned int yyruleno        /* Number of the rule by which to reduce */
 658 ){
 659   int yygoto;                     /* The next state */
 660   int yyact;                      /* The next action */
 661   yyStackEntry *yymsp;            /* The top of the parser's stack */
 662   int yysize;                     /* Amount to pop the stack */
 663   ParseARG_FETCH;
 664   yymsp = yypParser->yytos;
 665 #ifndef NDEBUG
 666   if( yyTraceFILE && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){
 667     yysize = yyRuleInfo[yyruleno].nrhs;
 668     fprintf(yyTraceFILE, "%sReduce [%s], go to state %d.\n", yyTracePrompt,
 669       yyRuleName[yyruleno], yymsp[yysize].stateno);
 670   }
 671 #endif /* NDEBUG */
 672
 673   /* Check that the stack is large enough to grow by a single entry
 674   ** if the RHS of the rule is empty.  This ensures that there is room
 675   ** enough on the stack to push the LHS value */
 676   if( yyRuleInfo[yyruleno].nrhs==0 ){
 677 #ifdef YYTRACKMAXSTACKDEPTH
 678     if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){
 679       yypParser->yyhwm++;
 680       assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack));
 681     }
 682 #endif
 683 #if YYSTACKDEPTH>0
 684     if( yypParser->yytos>=yypParser->yystackEnd ){
 685       yyStackOverflow(yypParser);
 686       return;
 687     }
 688 #else
 689     if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){
 690       if( yyGrowStack(yypParser) ){
 691         yyStackOverflow(yypParser);
 692         return;
 693       }
 694       yymsp = yypParser->yytos;
 695     }
 696 #endif
 697   }
 698
 699   switch( yyruleno ){
 700   /* Beginning here are the reduction cases.  A typical example
 701   ** follows:
 702   **   case 0:
 703   **  #line <lineno> <grammarfile>
 704   **     { ... }           // User supplied code
 705   **  #line <lineno> <thisfile>
 706   **     break;
 707   */
 708 /********** Begin reduce actions **********************************************/
 709 %%
 710 /********** End reduce actions ************************************************/
 711   };
 712   assert( yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) );
 713   yygoto = yyRuleInfo[yyruleno].lhs;
 714   yysize = yyRuleInfo[yyruleno].nrhs;
 715   yyact = yy_find_reduce_action(yymsp[yysize].stateno,(YYCODETYPE)yygoto);
 716
 717   /* There are no SHIFTREDUCE actions on nonterminals because the table
 718   ** generator has simplified them to pure REDUCE actions. */
 719   assert( !(yyact>YY_MAX_SHIFT && yyact<=YY_MAX_SHIFTREDUCE) );
 720
 721   /* It is not possible for a REDUCE to be followed by an error */
 722   assert( yyact!=YY_ERROR_ACTION );
 723
 724   if( yyact==YY_ACCEPT_ACTION ){
 725     yypParser->yytos += yysize;
 726     yy_accept(yypParser);
 727   }else{
 728     yymsp += yysize+1;
 729     yypParser->yytos = yymsp;
 730     yymsp->stateno = (YYACTIONTYPE)yyact;
 731     yymsp->major = (YYCODETYPE)yygoto;
 732     yyTraceShift(yypParser, yyact);
 733   }
 734 }
 735
 736 /*
 737 ** The following code executes when the parse fails
 738 */
 739 #ifndef YYNOERRORRECOVERY
 740 static void yy_parse_failed(
 741   yyParser *yypParser           /* The parser */
 742 ){
 743   ParseARG_FETCH;
 744 #ifndef NDEBUG
 745   if( yyTraceFILE ){
 746     fprintf(yyTraceFILE,"%sFail!\n",yyTracePrompt);
 747   }
 748 #endif
 749   while( yypParser->yytos>yypParser->yystack ) yy_pop_parser_stack(yypParser);
 750   /* Here code is inserted which will be executed whenever the
 751   ** parser fails */
 752 /************ Begin %parse_failure code ***************************************/
 753 %%
 754 /************ End %parse_failure code *****************************************/
 755   ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */
 756 }
 757 #endif /* YYNOERRORRECOVERY */
 758
 759 /*
 760 ** The following code executes when a syntax error first occurs.
 761 */
 762 static void yy_syntax_error(
 763   yyParser *yypParser,           /* The parser */
 764   int yymajor,                   /* The major type of the error token */
 765   ParseTOKENTYPE yyminor         /* The minor type of the error token */
 766 ){
 767   ParseARG_FETCH;
 768 #define TOKEN yyminor
 769 /************ Begin %syntax_error code ****************************************/
 770 %%
 771 /************ End %syntax_error code ******************************************/
 772   ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */
 773 }
 774
 775 /*
 776 ** The following is executed when the parser accepts
 777 */
 778 static void yy_accept(
 779   yyParser *yypParser           /* The parser */
 780 ){
 781   ParseARG_FETCH;
 782 #ifndef NDEBUG
 783   if( yyTraceFILE ){
 784     fprintf(yyTraceFILE,"%sAccept!\n",yyTracePrompt);
 785   }
 786 #endif
 787 #ifndef YYNOERRORRECOVERY
 788   yypParser->yyerrcnt = -1;
 789 #endif
 790   assert( yypParser->yytos==yypParser->yystack );
 791   /* Here code is inserted which will be executed whenever the
 792   ** parser accepts */
 793 /*********** Begin %parse_accept code *****************************************/
 794 %%
 795 /*********** End %parse_accept code *******************************************/
 796   ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */
 797 }
 798
 799 /* The main parser program.
 800 ** The first argument is a pointer to a structure obtained from
 801 ** "ParseAlloc" which describes the current state of the parser.
 802 ** The second argument is the major token number.  The third is
 803 ** the minor token.  The fourth optional argument is whatever the
 804 ** user wants (and specified in the grammar) and is available for
 805 ** use by the action routines.
 806 **
 807 ** Inputs:
 808 ** <ul>
 809 ** <li> A pointer to the parser (an opaque structure.)
 810 ** <li> The major token number.
 811 ** <li> The minor token number.
 812 ** <li> An option argument of a grammar-specified type.
 813 ** </ul>
 814 **
 815 ** Outputs:
 816 ** None.
 817 */
 818 void Parse(
 819   void *yyp,                   /* The parser */
 820   int yymajor,                 /* The major token code number */
 821   ParseTOKENTYPE yyminor       /* The value for the token */
 822   ParseARG_PDECL               /* Optional %extra_argument parameter */
 823 ){
 824   YYMINORTYPE yyminorunion;
 825   unsigned int yyact;   /* The parser action. */
 826 #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
 827   int yyendofinput;     /* True if we are at the end of input */
 828 #endif
 829 #ifdef YYERRORSYMBOL
 830   int yyerrorhit = 0;   /* True if yymajor has invoked an error */
 831 #endif
 832   yyParser *yypParser;  /* The parser */
 833
 834   yypParser = (yyParser*)yyp;
 835   assert( yypParser->yytos!=0 );
 836 #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
 837   yyendofinput = (yymajor==0);
 838 #endif
 839   ParseARG_STORE;
 840
 841 #ifndef NDEBUG
 842   if( yyTraceFILE ){
 843     fprintf(yyTraceFILE,"%sInput '%s'\n",yyTracePrompt,yyTokenName[yymajor]);
 844   }
 845 #endif
 846
 847   do{
 848     yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
 849     if( yyact <= YY_MAX_SHIFTREDUCE ){
 850       yy_shift(yypParser,yyact,yymajor,yyminor);
 851 #ifndef YYNOERRORRECOVERY
 852       yypParser->yyerrcnt--;
 853 #endif
 854       yymajor = YYNOCODE;
 855     }else if( yyact <= YY_MAX_REDUCE ){
 856       yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
 857     }else{
 858       assert( yyact == YY_ERROR_ACTION );
 859       yyminorunion.yy0 = yyminor;
 860 #ifdef YYERRORSYMBOL
 861       int yymx;
 862 #endif
 863 #ifndef NDEBUG
 864       if( yyTraceFILE ){
 865         fprintf(yyTraceFILE,"%sSyntax Error!\n",yyTracePrompt);
 866       }
 867 #endif
 868 #ifdef YYERRORSYMBOL
 869       /* A syntax error has occurred.
 870       ** The response to an error depends upon whether or not the
 871       ** grammar defines an error token "ERROR".
 872       **
 873       ** This is what we do if the grammar does define ERROR:
 874       **
 875       **  * Call the %syntax_error function.
 876       **
 877       **  * Begin popping the stack until we enter a state where
 878       **    it is legal to shift the error symbol, then shift
 879       **    the error symbol.
 880       **
 881       **  * Set the error count to three.
 882       **
 883       **  * Begin accepting and shifting new tokens.  No new error
 884       **    processing will occur until three tokens have been
 885       **    shifted successfully.
 886       **
 887       */
 888       if( yypParser->yyerrcnt<0 ){
 889         yy_syntax_error(yypParser,yymajor,yyminor);
 890       }
 891       yymx = yypParser->yytos->major;
 892       if( yymx==YYERRORSYMBOL || yyerrorhit ){
 893 #ifndef NDEBUG
 894         if( yyTraceFILE ){
 895           fprintf(yyTraceFILE,"%sDiscard input token %s\n",
 896              yyTracePrompt,yyTokenName[yymajor]);
 897         }
 898 #endif
 899         yy_destructor(yypParser, (YYCODETYPE)yymajor, &yyminorunion);
 900         yymajor = YYNOCODE;
 901       }else{
 902         while( yypParser->yytos >= yypParser->yystack
 903             && yymx != YYERRORSYMBOL
 904             && (yyact = yy_find_reduce_action(
 905                         yypParser->yytos->stateno,
 906                         YYERRORSYMBOL)) >= YY_MIN_REDUCE
 907         ){
 908           yy_pop_parser_stack(yypParser);
 909         }
 910         if( yypParser->yytos < yypParser->yystack || yymajor==0 ){
 911           yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
 912           yy_parse_failed(yypParser);
 913 #ifndef YYNOERRORRECOVERY
 914           yypParser->yyerrcnt = -1;
 915 #endif
 916           yymajor = YYNOCODE;
 917         }else if( yymx!=YYERRORSYMBOL ){
 918           yy_shift(yypParser,yyact,YYERRORSYMBOL,yyminor);
 919         }
 920       }
 921       yypParser->yyerrcnt = 3;
 922       yyerrorhit = 1;
 923 #elif defined(YYNOERRORRECOVERY)
 924       /* If the YYNOERRORRECOVERY macro is defined, then do not attempt to
 925       ** do any kind of error recovery.  Instead, simply invoke the syntax
 926       ** error routine and continue going as if nothing had happened.
 927       **
 928       ** Applications can set this macro (for example inside %include) if
 929       ** they intend to abandon the parse upon the first syntax error seen.
 930       */
 931       yy_syntax_error(yypParser,yymajor, yyminor);
 932       yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
 933       yymajor = YYNOCODE;
 934
 935 #else  /* YYERRORSYMBOL is not defined */
 936       /* This is what we do if the grammar does not define ERROR:
 937       **
 938       **  * Report an error message, and throw away the input token.
 939       **
 940       **  * If the input token is $, then fail the parse.
 941       **
 942       ** As before, subsequent error messages are suppressed until
 943       ** three input tokens have been successfully shifted.
 944       */
 945       if( yypParser->yyerrcnt<=0 ){
 946         yy_syntax_error(yypParser,yymajor, yyminor);
 947       }
 948       yypParser->yyerrcnt = 3;
 949       yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
 950       if( yyendofinput ){
 951         yy_parse_failed(yypParser);
 952 #ifndef YYNOERRORRECOVERY
 953         yypParser->yyerrcnt = -1;
 954 #endif
 955       }
 956       yymajor = YYNOCODE;
 957 #endif
 958     }
 959   }while( yymajor!=YYNOCODE && yypParser->yytos>yypParser->yystack );
 960 #ifndef NDEBUG
 961   if( yyTraceFILE ){
 962     yyStackEntry *i;
 963     char cDiv = '[';
 964     fprintf(yyTraceFILE,"%sReturn. Stack=",yyTracePrompt);
 965     for(i=&yypParser->yystack[1]; i<=yypParser->yytos; i++){
 966       fprintf(yyTraceFILE,"%c%s", cDiv, yyTokenName[i->major]);
 967       cDiv = ' ';
 968     }
 969     fprintf(yyTraceFILE,"]\n");
 970   }
 971 #endif
 972   return;
 973 }