/ Check-in [99b992fa]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Enhance the Lemon parser generator to add SHIFTREDUCE states that reduce the sizes of some of the parser tables.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 99b992fa840707711d99f8d05b62412f7008cd93
User & Date: drh 2015-09-07 20:11:30
Context
2015-09-07
23:40
Minor tweaks to Lemon. check-in: 98667722 user: drh tags: trunk
20:22
Merge parser enhancements and other improvements and bug fixes from trunk. check-in: 9cf3e51b user: drh tags: begin-concurrent
20:11
Enhance the Lemon parser generator to add SHIFTREDUCE states that reduce the sizes of some of the parser tables. check-in: 99b992fa user: drh tags: trunk
20:02
Fix an unreachable branch in the new parse automaton. Closed-Leaf check-in: e9d604b4 user: drh tags: lemon-update
14:22
In the "parse.out" output file from Lemon, show addition the complete text of rules on reduce actions. check-in: b6ffb7e4 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/lempar.c.

    52     52   **                       for base tokens is called "yy0".
    53     53   **    YYSTACKDEPTH       is the maximum depth of the parser's stack.  If
    54     54   **                       zero the stack is dynamically sized using realloc()
    55     55   **    ParseARG_SDECL     A static variable declaration for the %extra_argument
    56     56   **    ParseARG_PDECL     A parameter declaration for the %extra_argument
    57     57   **    ParseARG_STORE     Code to store %extra_argument into yypParser
    58     58   **    ParseARG_FETCH     Code to extract %extra_argument from yypParser
    59         -**    YYNSTATE           the combined number of states.
    60         -**    YYNRULE            the number of rules in the grammar
    61     59   **    YYERRORSYMBOL      is the code number of the error symbol.  If not
    62     60   **                       defined, then do no error processing.
           61  +**    YYNSTATE           the combined number of states.
           62  +**    YYNRULE            the number of rules in the grammar
           63  +**    YY_MAX_SHIFT       Maximum value for shift actions
           64  +**    YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions
           65  +**    YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions
           66  +**    YY_MIN_REDUCE      Maximum value for reduce actions
           67  +**    YY_ERROR_ACTION    The yy_action[] code for syntax error
           68  +**    YY_ACCEPT_ACTION   The yy_action[] code for accept
           69  +**    YY_NO_ACTION       The yy_action[] code for no-op
    63     70   */
    64     71   %%
    65         -#define YY_NO_ACTION      (YYNSTATE+YYNRULE+2)
    66         -#define YY_ACCEPT_ACTION  (YYNSTATE+YYNRULE+1)
    67         -#define YY_ERROR_ACTION   (YYNSTATE+YYNRULE)
    68     72   
    69     73   /* The yyzerominor constant is used to initialize instances of
    70     74   ** YYMINORTYPE objects to zero. */
    71     75   static const YYMINORTYPE yyzerominor = { 0 };
    72     76   
    73     77   /* Define the yytestcase() macro to be a no-op if is not already defined
    74     78   ** otherwise.
................................................................................
    87     91   ** current state and lookahead token.  These tables are used to implement
    88     92   ** functions that take a state number and lookahead value and return an
    89     93   ** action integer.  
    90     94   **
    91     95   ** Suppose the action integer is N.  Then the action is determined as
    92     96   ** follows
    93     97   **
    94         -**   0 <= N < YYNSTATE                  Shift N.  That is, push the lookahead
           98  +**   0 <= N <= YY_MAX_SHIFT             Shift N.  That is, push the lookahead
    95     99   **                                      token onto the stack and goto state N.
    96    100   **
    97         -**   YYNSTATE <= N < YYNSTATE+YYNRULE   Reduce by rule N-YYNSTATE.
          101  +**   N between YY_MIN_SHIFTREDUCE       Shift to an arbitrary state then
          102  +**     and YY_MAX_SHIFTREDUCE           reduce by rule N-YY_MIN_SHIFTREDUCE.
    98    103   **
    99         -**   N == YYNSTATE+YYNRULE              A syntax error has occurred.
          104  +**   N between YY_MIN_REDUCE            Reduce by rule N-YY_MIN_REDUCE
          105  +**     and YY_MAX_REDUCE
          106  +
          107  +**   N == YY_ERROR_ACTION               A syntax error has occurred.
   100    108   **
   101         -**   N == YYNSTATE+YYNRULE+1            The parser accepts its input.
          109  +**   N == YY_ACCEPT_ACTION              The parser accepts its input.
   102    110   **
   103         -**   N == YYNSTATE+YYNRULE+2            No such action.  Denotes unused
          111  +**   N == YY_NO_ACTION                  No such action.  Denotes unused
   104    112   **                                      slots in the yy_action[] table.
   105    113   **
   106    114   ** The action table is constructed as a single large table named yy_action[].
   107    115   ** Given state S and lookahead X, the action is computed as
   108    116   **
   109    117   **      yy_action[ yy_shift_ofst[S] + X ]
   110    118   **
................................................................................
   155    163   **
   156    164   **   +  The value of the token stored at this level of the stack.
   157    165   **      (In other words, the "major" token.)
   158    166   **
   159    167   **   +  The semantic value stored at this level of the stack.  This is
   160    168   **      the information used by the action routines in the grammar.
   161    169   **      It is sometimes called the "minor" token.
          170  +**
          171  +** After the "shift" half of a SHIFTREDUCE action, the stateno field
          172  +** actually contains the reduce action for the second half of the
          173  +** SHIFTREDUCE.
   162    174   */
   163    175   struct yyStackEntry {
   164         -  YYACTIONTYPE stateno;  /* The state-number */
          176  +  YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
   165    177     YYCODETYPE major;      /* The major token value.  This is the code
   166    178                            ** number for the token at this stack level */
   167    179     YYMINORTYPE minor;     /* The user-supplied minor token value.  This
   168    180                            ** is the value of the token  */
   169    181   };
   170    182   typedef struct yyStackEntry yyStackEntry;
   171    183   
................................................................................
   391    403   static int yy_find_shift_action(
   392    404     yyParser *pParser,        /* The parser */
   393    405     YYCODETYPE iLookAhead     /* The look-ahead token */
   394    406   ){
   395    407     int i;
   396    408     int stateno = pParser->yystack[pParser->yyidx].stateno;
   397    409    
   398         -  if( stateno>YY_SHIFT_COUNT
   399         -   || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){
   400         -    return yy_default[stateno];
   401         -  }
          410  +  if( stateno>=YY_MIN_REDUCE ) return stateno;
          411  +  assert( stateno <= YY_SHIFT_COUNT );
          412  +  i = yy_shift_ofst[stateno];
          413  +  if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno];
   402    414     assert( iLookAhead!=YYNOCODE );
   403    415     i += iLookAhead;
   404    416     if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
   405    417       if( iLookAhead>0 ){
   406    418   #ifdef YYFALLBACK
   407    419         YYCODETYPE iFallback;            /* Fallback token */
   408    420         if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
................................................................................
   495    507      /* Here code is inserted which will execute if the parser
   496    508      ** stack every overflows */
   497    509   %%
   498    510      ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
   499    511   }
   500    512   
   501    513   /*
   502         -** Perform a shift action.
          514  +** Print tracing information for a SHIFT action
          515  +*/
          516  +#ifndef NDEBUG
          517  +static void yyTraceShift(yyParser *yypParser, int yyNewState){
          518  +  if( yyTraceFILE ){
          519  +    int i;
          520  +    if( yyNewState<YYNSTATE ){
          521  +      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
          522  +      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
          523  +      for(i=1; i<=yypParser->yyidx; i++)
          524  +        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
          525  +      fprintf(yyTraceFILE,"\n");
          526  +    }else{
          527  +      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
          528  +    }
          529  +  }
          530  +}
          531  +#else
          532  +# define yyTraceShift(X,Y)
          533  +#endif
          534  +
          535  +/*
          536  +** Perform a shift action.  Return the number of errors.
   503    537   */
   504    538   static void yy_shift(
   505    539     yyParser *yypParser,          /* The parser to be shifted */
   506    540     int yyNewState,               /* The new state to shift in */
   507    541     int yyMajor,                  /* The major token to shift in */
   508    542     YYMINORTYPE *yypMinor         /* Pointer to the minor token to shift in */
   509    543   ){
................................................................................
   528    562       }
   529    563     }
   530    564   #endif
   531    565     yytos = &yypParser->yystack[yypParser->yyidx];
   532    566     yytos->stateno = (YYACTIONTYPE)yyNewState;
   533    567     yytos->major = (YYCODETYPE)yyMajor;
   534    568     yytos->minor = *yypMinor;
   535         -#ifndef NDEBUG
   536         -  if( yyTraceFILE && yypParser->yyidx>0 ){
   537         -    int i;
   538         -    fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
   539         -    fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
   540         -    for(i=1; i<=yypParser->yyidx; i++)
   541         -      fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
   542         -    fprintf(yyTraceFILE,"\n");
   543         -  }
   544         -#endif
          569  +  yyTraceShift(yypParser, yyNewState);
   545    570   }
   546    571   
   547    572   /* The following table contains information about every rule that
   548    573   ** is used during the reduce.
   549    574   */
   550    575   static const struct {
   551    576     YYCODETYPE lhs;         /* Symbol on the left-hand side of the rule */
................................................................................
   570    595     yyStackEntry *yymsp;            /* The top of the parser's stack */
   571    596     int yysize;                     /* Amount to pop the stack */
   572    597     ParseARG_FETCH;
   573    598     yymsp = &yypParser->yystack[yypParser->yyidx];
   574    599   #ifndef NDEBUG
   575    600     if( yyTraceFILE && yyruleno>=0 
   576    601           && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){
   577         -    fprintf(yyTraceFILE, "%sReduce [%s].\n", yyTracePrompt,
   578         -      yyRuleName[yyruleno]);
          602  +    yysize = yyRuleInfo[yyruleno].nrhs;
          603  +    fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt,
          604  +      yyRuleName[yyruleno], yymsp[-yysize].stateno);
   579    605     }
   580    606   #endif /* NDEBUG */
   581    607   
   582    608     /* Silence complaints from purify about yygotominor being uninitialized
   583    609     ** in some cases when it is copied into the stack after the following
   584    610     ** switch.  yygotominor is uninitialized when a rule reduces that does
   585    611     ** not set the value of its left-hand side nonterminal.  Leaving the
................................................................................
   609    635   %%
   610    636     };
   611    637     assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) );
   612    638     yygoto = yyRuleInfo[yyruleno].lhs;
   613    639     yysize = yyRuleInfo[yyruleno].nrhs;
   614    640     yypParser->yyidx -= yysize;
   615    641     yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
   616         -  if( yyact < YYNSTATE ){
   617         -#ifdef NDEBUG
   618         -    /* If we are not debugging and the reduce action popped at least
          642  +  if( yyact <= YY_MAX_SHIFTREDUCE ){
          643  +    if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
          644  +    /* If the reduce action popped at least
   619    645       ** one element off the stack, then we can push the new element back
   620    646       ** onto the stack here, and skip the stack overflow test in yy_shift().
   621    647       ** That gives a significant speed improvement. */
   622    648       if( yysize ){
   623    649         yypParser->yyidx++;
   624    650         yymsp -= yysize-1;
   625    651         yymsp->stateno = (YYACTIONTYPE)yyact;
   626    652         yymsp->major = (YYCODETYPE)yygoto;
   627    653         yymsp->minor = yygotominor;
   628         -    }else
   629         -#endif
   630         -    {
          654  +      yyTraceShift(yypParser, yyact);
          655  +    }else{
   631    656         yy_shift(yypParser,yyact,yygoto,&yygotominor);
   632    657       }
   633    658     }else{
   634         -    assert( yyact == YYNSTATE + YYNRULE + 1 );
          659  +    assert( yyact == YY_ACCEPT_ACTION );
   635    660       yy_accept(yypParser);
   636    661     }
   637    662   }
   638    663   
   639    664   /*
   640    665   ** The following code executes when the parse fails
   641    666   */
................................................................................
   751    776     if( yyTraceFILE ){
   752    777       fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
   753    778     }
   754    779   #endif
   755    780   
   756    781     do{
   757    782       yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
   758         -    if( yyact<YYNSTATE ){
          783  +    if( yyact <= YY_MAX_SHIFTREDUCE ){
          784  +      if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   759    785         yy_shift(yypParser,yyact,yymajor,&yyminorunion);
   760    786         yypParser->yyerrcnt--;
   761    787         yymajor = YYNOCODE;
   762         -    }else if( yyact < YYNSTATE + YYNRULE ){
   763         -      yy_reduce(yypParser,yyact-YYNSTATE);
          788  +    }else if( yyact <= YY_MAX_REDUCE ){
          789  +      yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
   764    790       }else{
   765    791         assert( yyact == YY_ERROR_ACTION );
   766    792   #ifdef YYERRORSYMBOL
   767    793         int yymx;
   768    794   #endif
   769    795   #ifndef NDEBUG
   770    796         if( yyTraceFILE ){
................................................................................
   806    832           yymajor = YYNOCODE;
   807    833         }else{
   808    834            while(
   809    835             yypParser->yyidx >= 0 &&
   810    836             yymx != YYERRORSYMBOL &&
   811    837             (yyact = yy_find_reduce_action(
   812    838                           yypParser->yystack[yypParser->yyidx].stateno,
   813         -                        YYERRORSYMBOL)) >= YYNSTATE
          839  +                        YYERRORSYMBOL)) >= YY_MIN_REDUCE
   814    840           ){
   815    841             yy_pop_parser_stack(yypParser);
   816    842           }
   817    843           if( yypParser->yyidx < 0 || yymajor==0 ){
   818    844             yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
   819    845             yy_parse_failed(yypParser);
   820    846             yymajor = YYNOCODE;
................................................................................
   856    882         if( yyendofinput ){
   857    883           yy_parse_failed(yypParser);
   858    884         }
   859    885         yymajor = YYNOCODE;
   860    886   #endif
   861    887       }
   862    888     }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 );
          889  +#ifndef NDEBUG
          890  +  if( yyTraceFILE ){
          891  +    fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt);
          892  +  }
          893  +#endif
   863    894     return;
   864    895   }

Changes to src/tokenize.c.

   399    399     if( db->nVdbeActive==0 ){
   400    400       db->u1.isInterrupted = 0;
   401    401     }
   402    402     pParse->rc = SQLITE_OK;
   403    403     pParse->zTail = zSql;
   404    404     i = 0;
   405    405     assert( pzErrMsg!=0 );
          406  +  /* sqlite3ParserTrace(stdout, "parser: "); */
   406    407     pEngine = sqlite3ParserAlloc(sqlite3Malloc);
   407    408     if( pEngine==0 ){
   408    409       db->mallocFailed = 1;
   409    410       return SQLITE_NOMEM;
   410    411     }
   411    412     assert( pParse->pNewTable==0 );
   412    413     assert( pParse->pNewTrigger==0 );

Changes to tool/lemon.c.

   312    312     REDUCE,
   313    313     ERROR,
   314    314     SSCONFLICT,              /* A shift/shift conflict */
   315    315     SRCONFLICT,              /* Was a reduce, but part of a conflict */
   316    316     RRCONFLICT,              /* Was a reduce, but part of a conflict */
   317    317     SH_RESOLVED,             /* Was a shift.  Precedence resolved conflict */
   318    318     RD_RESOLVED,             /* Was reduce.  Precedence resolved conflict */
   319         -  NOT_USED                 /* Deleted by compression */
          319  +  NOT_USED,                /* Deleted by compression */
          320  +  SHIFTREDUCE              /* Shift first, then reduce */
   320    321   };
   321    322   
   322    323   /* Every shift or reduce operation is stored as one of the following */
   323    324   struct action {
   324    325     struct symbol *sp;       /* The look-ahead symbol */
   325    326     enum e_action type;
   326    327     union {
................................................................................
   336    337   struct state {
   337    338     struct config *bp;       /* The basis configurations for this state */
   338    339     struct config *cfp;      /* All configurations in this set */
   339    340     int statenum;            /* Sequential number for this state */
   340    341     struct action *ap;       /* Array of actions for this state */
   341    342     int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
   342    343     int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
   343         -  int iDflt;               /* Default action is reduce by this rule */
          344  +  int iDfltReduce;         /* Default action is to REDUCE by this rule */
          345  +  struct rule *pDfltReduce;/* The default REDUCE rule. */
          346  +  int autoReduce;          /* True if this is an auto-reduce state */
   344    347   };
   345    348   #define NO_OFFSET (-2147483647)
   346    349   
   347    350   /* A followset propagation link indicates that the contents of one
   348    351   ** configuration followset should be propagated to another whenever
   349    352   ** the first changes. */
   350    353   struct plink {
................................................................................
   356    359   ** follows.  (LEMON uses no global variables and makes little use of
   357    360   ** static variables.  Fields in the following structure can be thought
   358    361   ** of as begin global variables in the program.) */
   359    362   struct lemon {
   360    363     struct state **sorted;   /* Table of states sorted by state number */
   361    364     struct rule *rule;       /* List of all rules */
   362    365     int nstate;              /* Number of states */
          366  +  int nxstate;             /* nstate with tail degenerate states removed */
   363    367     int nrule;               /* Number of rules */
   364    368     int nsymbol;             /* Number of terminal and nonterminal symbols */
   365    369     int nterminal;           /* Number of terminal symbols */
   366    370     struct symbol **symbols; /* Sorted array of pointers to symbols */
   367    371     int errorcnt;            /* Number of errors */
   368    372     struct symbol *errsym;   /* The error symbol */
   369    373     struct symbol *wildcard; /* Token that matches anything */
................................................................................
   480    484     struct action *ap2
   481    485   ){
   482    486     int rc;
   483    487     rc = ap1->sp->index - ap2->sp->index;
   484    488     if( rc==0 ){
   485    489       rc = (int)ap1->type - (int)ap2->type;
   486    490     }
   487         -  if( rc==0 && ap1->type==REDUCE ){
          491  +  if( rc==0 && (ap1->type==REDUCE || ap1->type==SHIFTREDUCE) ){
   488    492       rc = ap1->x.rp->index - ap2->x.rp->index;
   489    493     }
   490    494     if( rc==0 ){
   491    495       rc = (int) (ap2 - ap1);
   492    496     }
   493    497     return rc;
   494    498   }
................................................................................
  1627   1631     }
  1628   1632     if( statistics ){
  1629   1633       printf("Parser statistics:\n");
  1630   1634       stats_line("terminal symbols", lem.nterminal);
  1631   1635       stats_line("non-terminal symbols", lem.nsymbol - lem.nterminal);
  1632   1636       stats_line("total symbols", lem.nsymbol);
  1633   1637       stats_line("rules", lem.nrule);
  1634         -    stats_line("states", lem.nstate);
         1638  +    stats_line("states", lem.nxstate);
  1635   1639       stats_line("conflicts", lem.nconflict);
  1636   1640       stats_line("action table entries", lem.nactiontab);
  1637   1641       stats_line("total table size (bytes)", lem.tablesize);
  1638   1642     }
  1639   1643     if( lem.nconflict > 0 ){
  1640   1644       fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
  1641   1645     }
................................................................................
  3025   3029   
  3026   3030   /* Print an action to the given file descriptor.  Return FALSE if
  3027   3031   ** nothing was actually printed.
  3028   3032   */
  3029   3033   int PrintAction(
  3030   3034     struct action *ap,          /* The action to print */
  3031   3035     FILE *fp,                   /* Print the action here */
  3032         -  int indent,                 /* Indent by this amount */
  3033         -  struct rule **apRule        /* All rules by index */
         3036  +  int indent                  /* Indent by this amount */
  3034   3037   ){
  3035   3038     int result = 1;
  3036   3039     switch( ap->type ){
  3037   3040       case SHIFT: {
  3038   3041         struct state *stp = ap->x.stp;
  3039         -      fprintf(fp,"%*s shift  %-7d",indent,ap->sp->name,stp->statenum);
  3040         -      if( stp->nTknAct==0 && stp->nNtAct==0 && apRule ){
  3041         -        fprintf(fp,"then reduce %d: ", stp->iDflt);
  3042         -        RulePrint(fp, apRule[stp->iDflt], -1);
  3043         -      }
         3042  +      fprintf(fp,"%*s shift        %-7d",indent,ap->sp->name,stp->statenum);
  3044   3043         break;
  3045   3044       }
  3046   3045       case REDUCE: {
  3047   3046         struct rule *rp = ap->x.rp;
  3048         -      fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index);
  3049         -      if( apRule ) RulePrint(fp, apRule[rp->index], -1);
         3047  +      fprintf(fp,"%*s reduce       %-7d",indent,ap->sp->name,rp->index);
         3048  +      RulePrint(fp, rp, -1);
         3049  +      break;
         3050  +    }
         3051  +    case SHIFTREDUCE: {
         3052  +      struct rule *rp = ap->x.rp;
         3053  +      fprintf(fp,"%*s shift-reduce %-7d",indent,ap->sp->name,rp->index);
         3054  +      RulePrint(fp, rp, -1);
  3050   3055         break;
  3051   3056       }
  3052   3057       case ACCEPT:
  3053   3058         fprintf(fp,"%*s accept",indent,ap->sp->name);
  3054   3059         break;
  3055   3060       case ERROR:
  3056   3061         fprintf(fp,"%*s error",indent,ap->sp->name);
  3057   3062         break;
  3058   3063       case SRCONFLICT:
  3059   3064       case RRCONFLICT:
  3060         -      fprintf(fp,"%*s reduce %-7d ** Parsing conflict **",
         3065  +      fprintf(fp,"%*s reduce       %-7d ** Parsing conflict **",
  3061   3066           indent,ap->sp->name,ap->x.rp->index);
  3062   3067         break;
  3063   3068       case SSCONFLICT:
  3064         -      fprintf(fp,"%*s shift  %-7d ** Parsing conflict **", 
         3069  +      fprintf(fp,"%*s shift        %-7d ** Parsing conflict **", 
  3065   3070           indent,ap->sp->name,ap->x.stp->statenum);
  3066   3071         break;
  3067   3072       case SH_RESOLVED:
  3068   3073         if( showPrecedenceConflict ){
  3069         -        fprintf(fp,"%*s shift  %-7d -- dropped by precedence",
         3074  +        fprintf(fp,"%*s shift        %-7d -- dropped by precedence",
  3070   3075                   indent,ap->sp->name,ap->x.stp->statenum);
  3071   3076         }else{
  3072   3077           result = 0;
  3073   3078         }
  3074   3079         break;
  3075   3080       case RD_RESOLVED:
  3076   3081         if( showPrecedenceConflict ){
................................................................................
  3083   3088       case NOT_USED:
  3084   3089         result = 0;
  3085   3090         break;
  3086   3091     }
  3087   3092     return result;
  3088   3093   }
  3089   3094   
  3090         -/* Generate the "y.output" log file */
         3095  +/* Generate the "*.out" log file */
  3091   3096   void ReportOutput(struct lemon *lemp)
  3092   3097   {
  3093   3098     int i;
  3094   3099     struct state *stp;
  3095   3100     struct config *cfp;
  3096   3101     struct action *ap;
  3097   3102     FILE *fp;
  3098         -  struct rule **apRule;
  3099   3103   
  3100         -  apRule = malloc( sizeof(apRule[0])*(lemp->nrule+1) );
  3101         -  if( apRule ){
  3102         -    struct rule *x;
  3103         -    memset(apRule, 0, sizeof(apRule[0])*(lemp->nrule+1) );
  3104         -    for(x=lemp->rule; x; x=x->next){
  3105         -      assert( x->index>=0 && x->index<(lemp->nrule+1) );
  3106         -      apRule[x->index] = x;
  3107         -    }
  3108         -  }
  3109   3104     fp = file_open(lemp,".out","wb");
  3110   3105     if( fp==0 ) return;
  3111         -  for(i=0; i<lemp->nstate; i++){
         3106  +  for(i=0; i<lemp->nxstate; i++){
  3112   3107       stp = lemp->sorted[i];
  3113   3108       fprintf(fp,"State %d:\n",stp->statenum);
  3114   3109       if( lemp->basisflag ) cfp=stp->bp;
  3115   3110       else                  cfp=stp->cfp;
  3116   3111       while( cfp ){
  3117   3112         char buf[20];
  3118   3113         if( cfp->dot==cfp->rp->nrhs ){
................................................................................
  3129   3124         PlinkPrint(fp,cfp->bplp,"From");
  3130   3125   #endif
  3131   3126         if( lemp->basisflag ) cfp=cfp->bp;
  3132   3127         else                  cfp=cfp->next;
  3133   3128       }
  3134   3129       fprintf(fp,"\n");
  3135   3130       for(ap=stp->ap; ap; ap=ap->next){
  3136         -      if( PrintAction(ap,fp,30,apRule) ) fprintf(fp,"\n");
         3131  +      if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
  3137   3132       }
  3138   3133       fprintf(fp,"\n");
  3139   3134     }
  3140   3135     fprintf(fp, "----------------------------------------------------\n");
  3141   3136     fprintf(fp, "Symbols:\n");
  3142   3137     for(i=0; i<lemp->nsymbol; i++){
  3143   3138       int j;
................................................................................
  3155   3150             fprintf(fp, " %s", lemp->symbols[j]->name);
  3156   3151           }
  3157   3152         }
  3158   3153       }
  3159   3154       fprintf(fp, "\n");
  3160   3155     }
  3161   3156     fclose(fp);
  3162         -  free(apRule);
  3163   3157     return;
  3164   3158   }
  3165   3159   
  3166   3160   /* Search for the file "name" which is in the same directory as
  3167   3161   ** the exacutable */
  3168   3162   PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
  3169   3163   {
................................................................................
  3213   3207   ** which is to be put in the action table of the generated machine.
  3214   3208   ** Return negative if no action should be generated.
  3215   3209   */
  3216   3210   PRIVATE int compute_action(struct lemon *lemp, struct action *ap)
  3217   3211   {
  3218   3212     int act;
  3219   3213     switch( ap->type ){
  3220         -    case SHIFT:  act = ap->x.stp->statenum;            break;
  3221         -    case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
  3222         -    case ERROR:  act = lemp->nstate + lemp->nrule;     break;
  3223         -    case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break;
         3214  +    case SHIFT:  act = ap->x.stp->statenum;                        break;
         3215  +    case SHIFTREDUCE: act = ap->x.rp->index + lemp->nstate;        break;
         3216  +    case REDUCE: act = ap->x.rp->index + lemp->nstate+lemp->nrule; break;
         3217  +    case ERROR:  act = lemp->nstate + lemp->nrule*2;               break;
         3218  +    case ACCEPT: act = lemp->nstate + lemp->nrule*2 + 1;           break;
  3224   3219       default:     act = -1; break;
  3225   3220     }
  3226   3221     return act;
  3227   3222   }
  3228   3223   
  3229   3224   #define LINESIZE 1000
  3230   3225   /* The next cluster of routines are for reading the template file
................................................................................
  3839   3834     tplt_xfer(lemp->name,in,out,&lineno);
  3840   3835   
  3841   3836     /* Generate the defines */
  3842   3837     fprintf(out,"#define YYCODETYPE %s\n",
  3843   3838       minimum_size_type(0, lemp->nsymbol+1, &szCodeType)); lineno++;
  3844   3839     fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  3845   3840     fprintf(out,"#define YYACTIONTYPE %s\n",
  3846         -    minimum_size_type(0, lemp->nstate+lemp->nrule+5, &szActionType)); lineno++;
         3841  +    minimum_size_type(0,lemp->nstate+lemp->nrule*2+5,&szActionType)); lineno++;
  3847   3842     if( lemp->wildcard ){
  3848   3843       fprintf(out,"#define YYWILDCARD %d\n",
  3849   3844          lemp->wildcard->index); lineno++;
  3850   3845     }
  3851   3846     print_stack_union(out,lemp,&lineno,mhflag);
  3852   3847     fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;
  3853   3848     if( lemp->stacksize ){
................................................................................
  3875   3870       fprintf(out,"#define %sARG_PDECL\n",name);  lineno++;
  3876   3871       fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
  3877   3872       fprintf(out,"#define %sARG_STORE\n",name); lineno++;
  3878   3873     }
  3879   3874     if( mhflag ){
  3880   3875       fprintf(out,"#endif\n"); lineno++;
  3881   3876     }
  3882         -  fprintf(out,"#define YYNSTATE %d\n",lemp->nstate);  lineno++;
  3883         -  fprintf(out,"#define YYNRULE %d\n",lemp->nrule);  lineno++;
  3884   3877     if( lemp->errsym->useCnt ){
  3885         -    fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index);  lineno++;
  3886         -    fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum);  lineno++;
         3878  +    fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;
         3879  +    fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;
  3887   3880     }
  3888   3881     if( lemp->has_fallback ){
  3889   3882       fprintf(out,"#define YYFALLBACK 1\n");  lineno++;
  3890   3883     }
  3891         -  tplt_xfer(lemp->name,in,out,&lineno);
  3892   3884   
  3893         -  /* Generate the action table and its associates:
  3894         -  **
  3895         -  **  yy_action[]        A single table containing all actions.
  3896         -  **  yy_lookahead[]     A table containing the lookahead for each entry in
  3897         -  **                     yy_action.  Used to detect hash collisions.
  3898         -  **  yy_shift_ofst[]    For each state, the offset into yy_action for
  3899         -  **                     shifting terminals.
  3900         -  **  yy_reduce_ofst[]   For each state, the offset into yy_action for
  3901         -  **                     shifting non-terminals after a reduce.
  3902         -  **  yy_default[]       Default action for each state.
         3885  +  /* Compute the action table, but do not output it yet.  The action
         3886  +  ** table must be computed before generating the YYNSTATE macro because
         3887  +  ** we need to know how many states can be eliminated.
  3903   3888     */
  3904         -
  3905         -  /* Compute the actions on all states and count them up */
  3906         -  ax = (struct axset *) calloc(lemp->nstate*2, sizeof(ax[0]));
         3889  +  ax = (struct axset *) calloc(lemp->nxstate*2, sizeof(ax[0]));
  3907   3890     if( ax==0 ){
  3908   3891       fprintf(stderr,"malloc failed\n");
  3909   3892       exit(1);
  3910   3893     }
  3911         -  for(i=0; i<lemp->nstate; i++){
         3894  +  for(i=0; i<lemp->nxstate; i++){
  3912   3895       stp = lemp->sorted[i];
  3913   3896       ax[i*2].stp = stp;
  3914   3897       ax[i*2].isTkn = 1;
  3915   3898       ax[i*2].nAction = stp->nTknAct;
  3916   3899       ax[i*2+1].stp = stp;
  3917   3900       ax[i*2+1].isTkn = 0;
  3918   3901       ax[i*2+1].nAction = stp->nNtAct;
  3919   3902     }
  3920   3903     mxTknOfst = mnTknOfst = 0;
  3921   3904     mxNtOfst = mnNtOfst = 0;
  3922         -
  3923         -  /* Compute the action table.  In order to try to keep the size of the
  3924         -  ** action table to a minimum, the heuristic of placing the largest action
  3925         -  ** sets first is used.
  3926         -  */
  3927         -  for(i=0; i<lemp->nstate*2; i++) ax[i].iOrder = i;
  3928         -  qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
         3905  +  /* In an effort to minimize the action table size, use the heuristic
         3906  +  ** of placing the largest action sets first */
         3907  +  for(i=0; i<lemp->nxstate*2; i++) ax[i].iOrder = i;
         3908  +  qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare);
  3929   3909     pActtab = acttab_alloc();
  3930         -  for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
         3910  +  for(i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++){
  3931   3911       stp = ax[i].stp;
  3932   3912       if( ax[i].isTkn ){
  3933   3913         for(ap=stp->ap; ap; ap=ap->next){
  3934   3914           int action;
  3935   3915           if( ap->sp->index>=lemp->nterminal ) continue;
  3936   3916           action = compute_action(lemp, ap);
  3937   3917           if( action<0 ) continue;
................................................................................
  3951   3931         }
  3952   3932         stp->iNtOfst = acttab_insert(pActtab);
  3953   3933         if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
  3954   3934         if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
  3955   3935       }
  3956   3936     }
  3957   3937     free(ax);
         3938  +
         3939  +  /* Finish rendering the constants now that the action table has
         3940  +  ** been computed */
         3941  +  fprintf(out,"#define YYNSTATE             %d\n",lemp->nxstate);  lineno++;
         3942  +  fprintf(out,"#define YYNRULE              %d\n",lemp->nrule);  lineno++;
         3943  +  fprintf(out,"#define YY_MAX_SHIFT         %d\n",lemp->nstate-1);  lineno++;
         3944  +  fprintf(out,"#define YY_MIN_SHIFTREDUCE   %d\n",lemp->nstate); lineno++;
         3945  +  i = lemp->nstate + lemp->nrule;
         3946  +  fprintf(out,"#define YY_MAX_SHIFTREDUCE   %d\n", i-1); lineno++;
         3947  +  fprintf(out,"#define YY_MIN_REDUCE        %d\n", i); lineno++;
         3948  +  i = lemp->nstate + lemp->nrule*2;
         3949  +  fprintf(out,"#define YY_MAX_REDUCE        %d\n", i-1); lineno++;
         3950  +  fprintf(out,"#define YY_ERROR_ACTION      %d\n", i); lineno++;
         3951  +  fprintf(out,"#define YY_ACCEPT_ACTION     %d\n", i+1); lineno++;
         3952  +  fprintf(out,"#define YY_NO_ACTION         %d\n", i+2); lineno++;
         3953  +  tplt_xfer(lemp->name,in,out,&lineno);
         3954  +
         3955  +  /* Now output the action table and its associates:
         3956  +  **
         3957  +  **  yy_action[]        A single table containing all actions.
         3958  +  **  yy_lookahead[]     A table containing the lookahead for each entry in
         3959  +  **                     yy_action.  Used to detect hash collisions.
         3960  +  **  yy_shift_ofst[]    For each state, the offset into yy_action for
         3961  +  **                     shifting terminals.
         3962  +  **  yy_reduce_ofst[]   For each state, the offset into yy_action for
         3963  +  **                     shifting non-terminals after a reduce.
         3964  +  **  yy_default[]       Default action for each state.
         3965  +  */
  3958   3966   
  3959   3967     /* Output the yy_action table */
  3960   3968     lemp->nactiontab = n = acttab_size(pActtab);
  3961   3969     lemp->tablesize += n*szActionType;
  3962   3970     fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
  3963   3971     fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
  3964   3972     for(i=j=0; i<n; i++){
................................................................................
  3990   3998         j++;
  3991   3999       }
  3992   4000     }
  3993   4001     fprintf(out, "};\n"); lineno++;
  3994   4002   
  3995   4003     /* Output the yy_shift_ofst[] table */
  3996   4004     fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
  3997         -  n = lemp->nstate;
         4005  +  n = lemp->nxstate;
  3998   4006     while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
  3999   4007     fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;
  4000   4008     fprintf(out, "#define YY_SHIFT_MIN   (%d)\n", mnTknOfst); lineno++;
  4001   4009     fprintf(out, "#define YY_SHIFT_MAX   (%d)\n", mxTknOfst); lineno++;
  4002   4010     fprintf(out, "static const %s yy_shift_ofst[] = {\n", 
  4003   4011             minimum_size_type(mnTknOfst-1, mxTknOfst, &sz)); lineno++;
  4004   4012     lemp->tablesize += n*sz;
................................................................................
  4016   4024         j++;
  4017   4025       }
  4018   4026     }
  4019   4027     fprintf(out, "};\n"); lineno++;
  4020   4028   
  4021   4029     /* Output the yy_reduce_ofst[] table */
  4022   4030     fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
  4023         -  n = lemp->nstate;
         4031  +  n = lemp->nxstate;
  4024   4032     while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
  4025   4033     fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
  4026   4034     fprintf(out, "#define YY_REDUCE_MIN   (%d)\n", mnNtOfst); lineno++;
  4027   4035     fprintf(out, "#define YY_REDUCE_MAX   (%d)\n", mxNtOfst); lineno++;
  4028   4036     fprintf(out, "static const %s yy_reduce_ofst[] = {\n", 
  4029   4037             minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++;
  4030   4038     lemp->tablesize += n*sz;
................................................................................
  4042   4050         j++;
  4043   4051       }
  4044   4052     }
  4045   4053     fprintf(out, "};\n"); lineno++;
  4046   4054   
  4047   4055     /* Output the default action table */
  4048   4056     fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
  4049         -  n = lemp->nstate;
         4057  +  n = lemp->nxstate;
  4050   4058     lemp->tablesize += n*szActionType;
  4051   4059     for(i=j=0; i<n; i++){
  4052   4060       stp = lemp->sorted[i];
  4053   4061       if( j==0 ) fprintf(out," /* %5d */ ", i);
  4054         -    fprintf(out, " %4d,", stp->iDflt+n);
         4062  +    fprintf(out, " %4d,", stp->iDfltReduce+lemp->nstate+lemp->nrule);
  4055   4063       if( j==9 || i==n-1 ){
  4056   4064         fprintf(out, "\n"); lineno++;
  4057   4065         j = 0;
  4058   4066       }else{
  4059   4067         j++;
  4060   4068       }
  4061   4069     }
................................................................................
  4280   4288   ** is a possible look-ahead.
  4281   4289   */
  4282   4290   void CompressTables(struct lemon *lemp)
  4283   4291   {
  4284   4292     struct state *stp;
  4285   4293     struct action *ap, *ap2;
  4286   4294     struct rule *rp, *rp2, *rbest;
  4287         -  int nbest, n;
         4295  +  int nbest, n, nshift;
  4288   4296     int i;
  4289   4297     int usesWildcard;
  4290   4298   
  4291   4299     for(i=0; i<lemp->nstate; i++){
  4292   4300       stp = lemp->sorted[i];
  4293   4301       nbest = 0;
  4294   4302       rbest = 0;
................................................................................
  4328   4336       }
  4329   4337       assert( ap );
  4330   4338       ap->sp = Symbol_new("{default}");
  4331   4339       for(ap=ap->next; ap; ap=ap->next){
  4332   4340         if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
  4333   4341       }
  4334   4342       stp->ap = Action_sort(stp->ap);
         4343  +
         4344  +    for(ap=stp->ap; ap; ap=ap->next){
         4345  +      if( ap->type==SHIFT ) break;
         4346  +      if( ap->type==REDUCE && ap->x.rp!=rbest ) break;
         4347  +    }
         4348  +    if( ap==0 ){
         4349  +      stp->autoReduce = 1;
         4350  +      stp->pDfltReduce = rbest;
         4351  +    }
         4352  +  }
         4353  +
         4354  +  /* Make a second pass over all states and actions.  Convert
         4355  +  ** every action that is a SHIFT to an autoReduce state into
         4356  +  ** a SHIFTREDUCE action.
         4357  +  */
         4358  +  for(i=0; i<lemp->nstate; i++){
         4359  +    stp = lemp->sorted[i];
         4360  +    for(ap=stp->ap; ap; ap=ap->next){
         4361  +      struct state *pNextState;
         4362  +      if( ap->type!=SHIFT ) continue;
         4363  +      pNextState = ap->x.stp;
         4364  +      if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){
         4365  +        ap->type = SHIFTREDUCE;
         4366  +        ap->x.rp = pNextState->pDfltReduce;
         4367  +      }
         4368  +    }
  4335   4369     }
  4336   4370   }
  4337   4371   
  4338   4372   
  4339   4373   /*
  4340   4374   ** Compare two states for sorting purposes.  The smaller state is the
  4341   4375   ** one with the most non-terminal actions.  If they have the same number
................................................................................
  4368   4402     int i;
  4369   4403     struct state *stp;
  4370   4404     struct action *ap;
  4371   4405   
  4372   4406     for(i=0; i<lemp->nstate; i++){
  4373   4407       stp = lemp->sorted[i];
  4374   4408       stp->nTknAct = stp->nNtAct = 0;
  4375         -    stp->iDflt = lemp->nrule;
         4409  +    stp->iDfltReduce = lemp->nrule;  /* Init dflt action to "syntax error" */
  4376   4410       stp->iTknOfst = NO_OFFSET;
  4377   4411       stp->iNtOfst = NO_OFFSET;
  4378   4412       for(ap=stp->ap; ap; ap=ap->next){
  4379         -      if( compute_action(lemp,ap)>=0 ){
         4413  +      int iAction = compute_action(lemp,ap);
         4414  +      if( iAction>=0 ){
  4380   4415           if( ap->sp->index<lemp->nterminal ){
  4381   4416             stp->nTknAct++;
  4382   4417           }else if( ap->sp->index<lemp->nsymbol ){
  4383   4418             stp->nNtAct++;
  4384   4419           }else{
  4385         -          stp->iDflt = compute_action(lemp, ap) - lemp->nstate;
         4420  +          assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp );
         4421  +          stp->iDfltReduce = iAction - lemp->nstate - lemp->nrule;
  4386   4422           }
  4387   4423         }
  4388   4424       }
  4389   4425     }
  4390   4426     qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
  4391   4427           stateResortCompare);
  4392   4428     for(i=0; i<lemp->nstate; i++){
  4393   4429       lemp->sorted[i]->statenum = i;
         4430  +  }
         4431  +  lemp->nxstate = lemp->nstate;
         4432  +  while( lemp->nxstate>1 && lemp->sorted[lemp->nxstate-1]->autoReduce ){
         4433  +    lemp->nxstate--;
  4394   4434     }
  4395   4435   }
  4396   4436   
  4397   4437   
  4398   4438   /***************** From the file "set.c" ************************************/
  4399   4439   /*
  4400   4440   ** Set manipulation routines for the LEMON parser generator.

Changes to tool/lempar.c.

    46     46   **                       for base tokens is called "yy0".
    47     47   **    YYSTACKDEPTH       is the maximum depth of the parser's stack.  If
    48     48   **                       zero the stack is dynamically sized using realloc()
    49     49   **    ParseARG_SDECL     A static variable declaration for the %extra_argument
    50     50   **    ParseARG_PDECL     A parameter declaration for the %extra_argument
    51     51   **    ParseARG_STORE     Code to store %extra_argument into yypParser
    52     52   **    ParseARG_FETCH     Code to extract %extra_argument from yypParser
    53         -**    YYNSTATE           the combined number of states.
    54         -**    YYNRULE            the number of rules in the grammar
    55     53   **    YYERRORSYMBOL      is the code number of the error symbol.  If not
    56     54   **                       defined, then do no error processing.
           55  +**    YYNSTATE           the combined number of states.
           56  +**    YYNRULE            the number of rules in the grammar
           57  +**    YY_MAX_SHIFT       Maximum value for shift actions
           58  +**    YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions
           59  +**    YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions
           60  +**    YY_MIN_REDUCE      Maximum value for reduce actions
           61  +**    YY_ERROR_ACTION    The yy_action[] code for syntax error
           62  +**    YY_ACCEPT_ACTION   The yy_action[] code for accept
           63  +**    YY_NO_ACTION       The yy_action[] code for no-op
    57     64   */
    58     65   %%
    59         -#define YY_NO_ACTION      (YYNSTATE+YYNRULE+2)
    60         -#define YY_ACCEPT_ACTION  (YYNSTATE+YYNRULE+1)
    61         -#define YY_ERROR_ACTION   (YYNSTATE+YYNRULE)
    62     66   
    63     67   /* The yyzerominor constant is used to initialize instances of
    64     68   ** YYMINORTYPE objects to zero. */
    65     69   static const YYMINORTYPE yyzerominor = { 0 };
    66     70   
    67     71   /* Define the yytestcase() macro to be a no-op if is not already defined
    68     72   ** otherwise.
................................................................................
    81     85   ** current state and lookahead token.  These tables are used to implement
    82     86   ** functions that take a state number and lookahead value and return an
    83     87   ** action integer.  
    84     88   **
    85     89   ** Suppose the action integer is N.  Then the action is determined as
    86     90   ** follows
    87     91   **
    88         -**   0 <= N < YYNSTATE                  Shift N.  That is, push the lookahead
           92  +**   0 <= N <= YY_MAX_SHIFT             Shift N.  That is, push the lookahead
    89     93   **                                      token onto the stack and goto state N.
    90     94   **
    91         -**   YYNSTATE <= N < YYNSTATE+YYNRULE   Reduce by rule N-YYNSTATE.
           95  +**   N between YY_MIN_SHIFTREDUCE       Shift to an arbitrary state then
           96  +**     and YY_MAX_SHIFTREDUCE           reduce by rule N-YY_MIN_SHIFTREDUCE.
    92     97   **
    93         -**   N == YYNSTATE+YYNRULE              A syntax error has occurred.
           98  +**   N between YY_MIN_REDUCE            Reduce by rule N-YY_MIN_REDUCE
           99  +**     and YY_MAX_REDUCE
          100  +
          101  +**   N == YY_ERROR_ACTION               A syntax error has occurred.
    94    102   **
    95         -**   N == YYNSTATE+YYNRULE+1            The parser accepts its input.
          103  +**   N == YY_ACCEPT_ACTION              The parser accepts its input.
    96    104   **
    97         -**   N == YYNSTATE+YYNRULE+2            No such action.  Denotes unused
          105  +**   N == YY_NO_ACTION                  No such action.  Denotes unused
    98    106   **                                      slots in the yy_action[] table.
    99    107   **
   100    108   ** The action table is constructed as a single large table named yy_action[].
   101    109   ** Given state S and lookahead X, the action is computed as
   102    110   **
   103    111   **      yy_action[ yy_shift_ofst[S] + X ]
   104    112   **
................................................................................
   149    157   **
   150    158   **   +  The value of the token stored at this level of the stack.
   151    159   **      (In other words, the "major" token.)
   152    160   **
   153    161   **   +  The semantic value stored at this level of the stack.  This is
   154    162   **      the information used by the action routines in the grammar.
   155    163   **      It is sometimes called the "minor" token.
          164  +**
          165  +** After the "shift" half of a SHIFTREDUCE action, the stateno field
          166  +** actually contains the reduce action for the second half of the
          167  +** SHIFTREDUCE.
   156    168   */
   157    169   struct yyStackEntry {
   158         -  YYACTIONTYPE stateno;  /* The state-number */
          170  +  YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
   159    171     YYCODETYPE major;      /* The major token value.  This is the code
   160    172                            ** number for the token at this stack level */
   161    173     YYMINORTYPE minor;     /* The user-supplied minor token value.  This
   162    174                            ** is the value of the token  */
   163    175   };
   164    176   typedef struct yyStackEntry yyStackEntry;
   165    177   
................................................................................
   380    392   */
   381    393   static int yy_find_shift_action(
   382    394     yyParser *pParser,        /* The parser */
   383    395     YYCODETYPE iLookAhead     /* The look-ahead token */
   384    396   ){
   385    397     int i;
   386    398     int stateno = pParser->yystack[pParser->yyidx].stateno;
   387         - 
   388         -  if( stateno>YY_SHIFT_COUNT
   389         -   || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){
   390         -    return yy_default[stateno];
   391         -  }
          399  +
          400  +  if( stateno>=YY_MIN_REDUCE ) return stateno; 
          401  +  assert( stateno <= YY_SHIFT_COUNT );
          402  +  i = yy_shift_ofst[stateno];
          403  +  if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno];
   392    404     assert( iLookAhead!=YYNOCODE );
   393    405     i += iLookAhead;
   394    406     if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
   395    407       if( iLookAhead>0 ){
   396    408   #ifdef YYFALLBACK
   397    409         YYCODETYPE iFallback;            /* Fallback token */
   398    410         if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
................................................................................
   485    497      /* Here code is inserted which will execute if the parser
   486    498      ** stack every overflows */
   487    499   %%
   488    500      ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
   489    501   }
   490    502   
   491    503   /*
   492         -** Perform a shift action.
          504  +** Print tracing information for a SHIFT action
          505  +*/
          506  +#ifndef NDEBUG
          507  +static void yyTraceShift(yyParser *yypParser, int yyNewState){
          508  +  if( yyTraceFILE ){
          509  +    int i;
          510  +    if( yyNewState<YYNSTATE ){
          511  +      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
          512  +      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
          513  +      for(i=1; i<=yypParser->yyidx; i++)
          514  +        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
          515  +      fprintf(yyTraceFILE,"\n");
          516  +    }else{
          517  +      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
          518  +    }
          519  +  }
          520  +}
          521  +#else
          522  +# define yyTraceShift(X,Y)
          523  +#endif
          524  +
          525  +/*
          526  +** Perform a shift action.  Return the number of errors.
   493    527   */
   494    528   static void yy_shift(
   495    529     yyParser *yypParser,          /* The parser to be shifted */
   496    530     int yyNewState,               /* The new state to shift in */
   497    531     int yyMajor,                  /* The major token to shift in */
   498    532     YYMINORTYPE *yypMinor         /* Pointer to the minor token to shift in */
   499    533   ){
................................................................................
   518    552       }
   519    553     }
   520    554   #endif
   521    555     yytos = &yypParser->yystack[yypParser->yyidx];
   522    556     yytos->stateno = (YYACTIONTYPE)yyNewState;
   523    557     yytos->major = (YYCODETYPE)yyMajor;
   524    558     yytos->minor = *yypMinor;
   525         -#ifndef NDEBUG
   526         -  if( yyTraceFILE && yypParser->yyidx>0 ){
   527         -    int i;
   528         -    fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
   529         -    fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
   530         -    for(i=1; i<=yypParser->yyidx; i++)
   531         -      fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
   532         -    fprintf(yyTraceFILE,"\n");
   533         -  }
   534         -#endif
          559  +  yyTraceShift(yypParser, yyNewState);
   535    560   }
   536    561   
   537    562   /* The following table contains information about every rule that
   538    563   ** is used during the reduce.
   539    564   */
   540    565   static const struct {
   541    566     YYCODETYPE lhs;         /* Symbol on the left-hand side of the rule */
................................................................................
   560    585     yyStackEntry *yymsp;            /* The top of the parser's stack */
   561    586     int yysize;                     /* Amount to pop the stack */
   562    587     ParseARG_FETCH;
   563    588     yymsp = &yypParser->yystack[yypParser->yyidx];
   564    589   #ifndef NDEBUG
   565    590     if( yyTraceFILE && yyruleno>=0 
   566    591           && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){
   567         -    fprintf(yyTraceFILE, "%sReduce [%s].\n", yyTracePrompt,
   568         -      yyRuleName[yyruleno]);
          592  +    yysize = yyRuleInfo[yyruleno].nrhs;
          593  +    fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt,
          594  +      yyRuleName[yyruleno], yymsp[-yysize].stateno);
   569    595     }
   570    596   #endif /* NDEBUG */
   571    597   
   572    598     /* Silence complaints from purify about yygotominor being uninitialized
   573    599     ** in some cases when it is copied into the stack after the following
   574    600     ** switch.  yygotominor is uninitialized when a rule reduces that does
   575    601     ** not set the value of its left-hand side nonterminal.  Leaving the
................................................................................
   598    624     */
   599    625   %%
   600    626     };
   601    627     yygoto = yyRuleInfo[yyruleno].lhs;
   602    628     yysize = yyRuleInfo[yyruleno].nrhs;
   603    629     yypParser->yyidx -= yysize;
   604    630     yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
   605         -  if( yyact < YYNSTATE ){
   606         -#ifdef NDEBUG
   607         -    /* If we are not debugging and the reduce action popped at least
          631  +  if( yyact <= YY_MAX_SHIFTREDUCE ){
          632  +    if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
          633  +    /* If the reduce action popped at least
   608    634       ** one element off the stack, then we can push the new element back
   609    635       ** onto the stack here, and skip the stack overflow test in yy_shift().
   610    636       ** That gives a significant speed improvement. */
   611    637       if( yysize ){
   612    638         yypParser->yyidx++;
   613    639         yymsp -= yysize-1;
   614    640         yymsp->stateno = (YYACTIONTYPE)yyact;
   615    641         yymsp->major = (YYCODETYPE)yygoto;
   616    642         yymsp->minor = yygotominor;
   617         -    }else
   618         -#endif
   619         -    {
          643  +      yyTraceShift(yypParser, yyact);
          644  +    }else{
   620    645         yy_shift(yypParser,yyact,yygoto,&yygotominor);
   621    646       }
   622    647     }else{
   623         -    assert( yyact == YYNSTATE + YYNRULE + 1 );
          648  +    assert( yyact == YY_ACCEPT_ACTION );
   624    649       yy_accept(yypParser);
   625    650     }
   626    651   }
   627    652   
   628    653   /*
   629    654   ** The following code executes when the parse fails
   630    655   */
................................................................................
   736    761     if( yyTraceFILE ){
   737    762       fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
   738    763     }
   739    764   #endif
   740    765   
   741    766     do{
   742    767       yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
   743         -    if( yyact<YYNSTATE ){
   744         -      assert( !yyendofinput );  /* Impossible to shift the $ token */
          768  +    if( yyact <= YY_MAX_SHIFTREDUCE ){
          769  +      if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   745    770         yy_shift(yypParser,yyact,yymajor,&yyminorunion);
   746    771         yypParser->yyerrcnt--;
   747    772         yymajor = YYNOCODE;
   748         -    }else if( yyact < YYNSTATE + YYNRULE ){
   749         -      yy_reduce(yypParser,yyact-YYNSTATE);
          773  +    }else if( yyact <= YY_MAX_REDUCE ){
          774  +      yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
   750    775       }else{
   751    776         assert( yyact == YY_ERROR_ACTION );
   752    777   #ifdef YYERRORSYMBOL
   753    778         int yymx;
   754    779   #endif
   755    780   #ifndef NDEBUG
   756    781         if( yyTraceFILE ){
................................................................................
   792    817           yymajor = YYNOCODE;
   793    818         }else{
   794    819            while(
   795    820             yypParser->yyidx >= 0 &&
   796    821             yymx != YYERRORSYMBOL &&
   797    822             (yyact = yy_find_reduce_action(
   798    823                           yypParser->yystack[yypParser->yyidx].stateno,
   799         -                        YYERRORSYMBOL)) >= YYNSTATE
          824  +                        YYERRORSYMBOL)) >= YY_MIN_REDUCE
   800    825           ){
   801    826             yy_pop_parser_stack(yypParser);
   802    827           }
   803    828           if( yypParser->yyidx < 0 || yymajor==0 ){
   804    829             yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
   805    830             yy_parse_failed(yypParser);
   806    831             yymajor = YYNOCODE;
................................................................................
   842    867         if( yyendofinput ){
   843    868           yy_parse_failed(yypParser);
   844    869         }
   845    870         yymajor = YYNOCODE;
   846    871   #endif
   847    872       }
   848    873     }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 );
          874  +#ifndef NDEBUG
          875  +  if( yyTraceFILE ){
          876  +    fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt);
          877  +  }
          878  +#endif
   849    879     return;
   850    880   }