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