/ Check-in [1b22b42e]
Login

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

Overview
Comment:Enhance the Lemon parser generator so that it creates a faster parser at the cost of slightly larger parser tables. Add the ability to measure coverage of the generated state machine when compiling with the -DYYCONVERGE option. In SQLite, add the SQLITE_TESTCTRL_PARSER_COVERAGE test-control to query the new parser coverage feature.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 1b22b42e59793af19c69a2e5f6822883cc2687d4a0d9b9280bbff885276c6baa
User & Date: drh 2017-12-27 18:19:06
Context
2017-12-27
22:09
The output of sqlite3_trace() now shows each command of a trigger as it is evaluated. This feature involved major changes to the parser, such as removing the ExprSpan object and replacing it with a new mechanism for capturing the original SQL text of phrases in the input SQL. check-in: 0fdf97ef user: drh tags: trunk
19:27
Merge recent enhancements from trunk. check-in: 76373091 user: drh tags: span-refactor
18:19
Enhance the Lemon parser generator so that it creates a faster parser at the cost of slightly larger parser tables. Add the ability to measure coverage of the generated state machine when compiling with the -DYYCONVERGE option. In SQLite, add the SQLITE_TESTCTRL_PARSER_COVERAGE test-control to query the new parser coverage feature. check-in: 1b22b42e user: drh tags: trunk
17:36
The previous check-in had an error in the coverage reporting logic. Closed-Leaf check-in: ec9b19eb user: drh tags: lemon-improvements
2017-12-26
14:46
Faster and smaller implementation of sqlite3AtoF() based on a suggestion from Cezary H. Noweta. check-in: fd2e0e7a user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to src/main.c.

  3907   3907         db->init.newTnum = va_arg(ap,int);
  3908   3908         if( db->init.busy==0 && db->init.newTnum>0 ){
  3909   3909           sqlite3ResetAllSchemasOfConnection(db);
  3910   3910         }
  3911   3911         sqlite3_mutex_leave(db->mutex);
  3912   3912         break;
  3913   3913       }
         3914  +
         3915  +#if defined(YYCOVERAGE)
         3916  +    /*  sqlite3_test_control(SQLITE_TESTCTRL_PARSER_COVERAGE, FILE *out)
         3917  +    **
         3918  +    ** This test control (only available when SQLite is compiled with
         3919  +    ** -DYYCOVERAGE) writes a report onto "out" that shows all
         3920  +    ** state/lookahead combinations in the parser state machine
         3921  +    ** which are never exercised.  If any state is missed, make the
         3922  +    ** return code SQLITE_ERROR.
         3923  +    */
         3924  +    case SQLITE_TESTCTRL_PARSER_COVERAGE: {
         3925  +      FILE *out = va_arg(ap, FILE*);
         3926  +      if( sqlite3ParserCoverage(out) ) rc = SQLITE_ERROR;
         3927  +      break;
         3928  +    }
         3929  +#endif /* defined(YYCOVERAGE) */
  3914   3930     }
  3915   3931     va_end(ap);
  3916   3932   #endif /* SQLITE_UNTESTABLE */
  3917   3933     return rc;
  3918   3934   }
  3919   3935   
  3920   3936   /*

Changes to src/shell.c.in.

  6104   6104         { "imposter",           SQLITE_TESTCTRL_IMPOSTER,   "SCHEMA ON/OFF ROOTPAGE"},
  6105   6105   #ifdef SQLITE_N_KEYWORD
  6106   6106         { "iskeyword",          SQLITE_TESTCTRL_ISKEYWORD,     "IDENTIFIER"         },
  6107   6107   #endif
  6108   6108         { "localtime_fault",    SQLITE_TESTCTRL_LOCALTIME_FAULT,"BOOLEAN"           },
  6109   6109         { "never_corrupt",      SQLITE_TESTCTRL_NEVER_CORRUPT, "BOOLEAN"            },
  6110   6110         { "optimizations",      SQLITE_TESTCTRL_OPTIMIZATIONS, "DISABLE-MASK"       },
         6111  +#ifdef YYCOVERAGE
         6112  +      { "parser_coverage",    SQLITE_TESTCTRL_PARSER_COVERAGE, ""                 },
         6113  +#endif
  6111   6114         { "pending_byte",       SQLITE_TESTCTRL_PENDING_BYTE,  "OFFSET  "           },
  6112   6115         { "prng_reset",         SQLITE_TESTCTRL_PRNG_RESET,    ""                   },
  6113   6116         { "prng_restore",       SQLITE_TESTCTRL_PRNG_RESTORE,  ""                   },
  6114   6117         { "prng_save",          SQLITE_TESTCTRL_PRNG_SAVE,     ""                   },
  6115   6118         { "reserve",            SQLITE_TESTCTRL_RESERVE,       "BYTES-OF-RESERVE"   },
  6116   6119       };
  6117   6120       int testctrl = -1;
................................................................................
  6229   6232               rc2 = sqlite3_test_control(testctrl, p->db,
  6230   6233                             azArg[2],
  6231   6234                             integerValue(azArg[3]),
  6232   6235                             integerValue(azArg[4]));
  6233   6236               isOk = 3;
  6234   6237             }
  6235   6238             break;
         6239  +
         6240  +#ifdef YYCOVERAGE
         6241  +        case SQLITE_TESTCTRL_PARSER_COVERAGE:
         6242  +          if( nArg==2 ){
         6243  +            sqlite3_test_control(testctrl, p->out);
         6244  +            isOk = 3;
         6245  +          }
         6246  +#endif
  6236   6247         }
  6237   6248       }
  6238   6249       if( isOk==0 && iCtrl>=0 ){
  6239   6250         utf8_printf(p->out, "Usage: .testctrl %s %s\n", zCmd, aCtrl[iCtrl].zUsage);
  6240   6251         rc = 1;
  6241   6252       }else if( isOk==1 ){
  6242   6253         raw_printf(p->out, "%d\n", rc2);

Changes to src/sqlite.h.in.

  7038   7038   #define SQLITE_TESTCTRL_ONCE_RESET_THRESHOLD    19
  7039   7039   #define SQLITE_TESTCTRL_NEVER_CORRUPT           20
  7040   7040   #define SQLITE_TESTCTRL_VDBE_COVERAGE           21
  7041   7041   #define SQLITE_TESTCTRL_BYTEORDER               22
  7042   7042   #define SQLITE_TESTCTRL_ISINIT                  23
  7043   7043   #define SQLITE_TESTCTRL_SORTER_MMAP             24
  7044   7044   #define SQLITE_TESTCTRL_IMPOSTER                25
  7045         -#define SQLITE_TESTCTRL_LAST                    25  /* Largest TESTCTRL */
         7045  +#define SQLITE_TESTCTRL_PARSER_COVERAGE         26
         7046  +#define SQLITE_TESTCTRL_LAST                    26  /* Largest TESTCTRL */
  7046   7047   
  7047   7048   /*
  7048   7049   ** CAPI3REF: SQLite Runtime Status
  7049   7050   **
  7050   7051   ** ^These interfaces are used to retrieve runtime status information
  7051   7052   ** about the performance of SQLite, and optionally to reset various
  7052   7053   ** highwater marks.  ^The first argument is an integer code for

Changes to src/sqliteInt.h.

  4344   4344     #define sqlite3ConnectionUnlocked(x)
  4345   4345     #define sqlite3ConnectionClosed(x)
  4346   4346   #endif
  4347   4347   
  4348   4348   #ifdef SQLITE_DEBUG
  4349   4349     void sqlite3ParserTrace(FILE*, char *);
  4350   4350   #endif
         4351  +#if defined(YYCOVERAGE)
         4352  +  int sqlite3ParserCoverage(FILE*);
         4353  +#endif
  4351   4354   
  4352   4355   /*
  4353   4356   ** If the SQLITE_ENABLE IOTRACE exists then the global variable
  4354   4357   ** sqlite3IoTrace is a pointer to a printf-like routine used to
  4355   4358   ** print I/O tracing messages.
  4356   4359   */
  4357   4360   #ifdef SQLITE_ENABLE_IOTRACE

Changes to tool/lemon.c.

   380    380     struct rule *rule;       /* List of all rules */
   381    381     struct rule *startRule;  /* First rule */
   382    382     int nstate;              /* Number of states */
   383    383     int nxstate;             /* nstate with tail degenerate states removed */
   384    384     int nrule;               /* Number of rules */
   385    385     int nsymbol;             /* Number of terminal and nonterminal symbols */
   386    386     int nterminal;           /* Number of terminal symbols */
          387  +  int minShiftReduce;      /* Minimum shift-reduce action value */
          388  +  int errAction;           /* Error action value */
          389  +  int accAction;           /* Accept action value */
          390  +  int noAction;            /* No-op action value */
          391  +  int minReduce;           /* Minimum reduce action */
          392  +  int maxAction;           /* Maximum action value of any kind */
   387    393     struct symbol **symbols; /* Sorted array of pointers to symbols */
   388    394     int errorcnt;            /* Number of errors */
   389    395     struct symbol *errsym;   /* The error symbol */
   390    396     struct symbol *wildcard; /* Token that matches anything */
   391    397     char *name;              /* Name of the generated parser */
   392    398     char *arg;               /* Declaration of the 3th argument to parser */
   393    399     char *tokentype;         /* Type of terminal symbols in the parser stack */
................................................................................
   403    409     char *tokendest;         /* Code to execute to destroy token data */
   404    410     char *vardest;           /* Code for the default non-terminal destructor */
   405    411     char *filename;          /* Name of the input file */
   406    412     char *outname;           /* Name of the current output file */
   407    413     char *tokenprefix;       /* A prefix added to token names in the .h file */
   408    414     int nconflict;           /* Number of parsing conflicts */
   409    415     int nactiontab;          /* Number of entries in the yy_action[] table */
          416  +  int nlookaheadtab;       /* Number of entries in yy_lookahead[] */
   410    417     int tablesize;           /* Total table size of all tables in bytes */
   411    418     int basisflag;           /* Print only basis configurations */
   412    419     int has_fallback;        /* True if any %fallback is seen in the grammar */
   413    420     int nolinenosflag;       /* True if #line statements should not be printed */
   414    421     char *argv0;             /* Name of the program */
   415    422   };
   416    423   
................................................................................
   579    586       *aAction,                  /* The yy_action[] table under construction */
   580    587       *aLookahead;               /* A single new transaction set */
   581    588     int mnLookahead;             /* Minimum aLookahead[].lookahead */
   582    589     int mnAction;                /* Action associated with mnLookahead */
   583    590     int mxLookahead;             /* Maximum aLookahead[].lookahead */
   584    591     int nLookahead;              /* Used slots in aLookahead[] */
   585    592     int nLookaheadAlloc;         /* Slots allocated in aLookahead[] */
          593  +  int nterminal;               /* Number of terminal symbols */
          594  +  int nsymbol;                 /* total number of symbols */
   586    595   };
   587    596   
   588    597   /* Return the number of entries in the yy_action table */
   589         -#define acttab_size(X) ((X)->nAction)
          598  +#define acttab_lookahead_size(X) ((X)->nAction)
   590    599   
   591    600   /* The value for the N-th entry in yy_action */
   592    601   #define acttab_yyaction(X,N)  ((X)->aAction[N].action)
   593    602   
   594    603   /* The value for the N-th entry in yy_lookahead */
   595    604   #define acttab_yylookahead(X,N)  ((X)->aAction[N].lookahead)
   596    605   
................................................................................
   598    607   void acttab_free(acttab *p){
   599    608     free( p->aAction );
   600    609     free( p->aLookahead );
   601    610     free( p );
   602    611   }
   603    612   
   604    613   /* Allocate a new acttab structure */
   605         -acttab *acttab_alloc(void){
          614  +acttab *acttab_alloc(int nsymbol, int nterminal){
   606    615     acttab *p = (acttab *) calloc( 1, sizeof(*p) );
   607    616     if( p==0 ){
   608    617       fprintf(stderr,"Unable to allocate memory for a new acttab.");
   609    618       exit(1);
   610    619     }
   611    620     memset(p, 0, sizeof(*p));
          621  +  p->nsymbol = nsymbol;
          622  +  p->nterminal = nterminal;
   612    623     return p;
   613    624   }
   614    625   
   615    626   /* Add a new action to the current transaction set.
   616    627   **
   617    628   ** This routine is called once for each lookahead for a particular
   618    629   ** state.
................................................................................
   645    656   
   646    657   /*
   647    658   ** Add the transaction set built up with prior calls to acttab_action()
   648    659   ** into the current action table.  Then reset the transaction set back
   649    660   ** to an empty set in preparation for a new round of acttab_action() calls.
   650    661   **
   651    662   ** Return the offset into the action table of the new transaction.
          663  +**
          664  +** If the makeItSafe parameter is true, then the offset is chosen so that
          665  +** it is impossible to overread the yy_lookaside[] table regardless of
          666  +** the lookaside token.  This is done for the terminal symbols, as they
          667  +** come from external inputs and can contain syntax errors.  When makeItSafe
          668  +** is false, there is more flexibility in selecting offsets, resulting in
          669  +** a smaller table.  For non-terminal symbols, which are never syntax errors,
          670  +** makeItSafe can be false.
   652    671   */
   653         -int acttab_insert(acttab *p){
   654         -  int i, j, k, n;
          672  +int acttab_insert(acttab *p, int makeItSafe){
          673  +  int i, j, k, n, end;
   655    674     assert( p->nLookahead>0 );
   656    675   
   657    676     /* Make sure we have enough space to hold the expanded action table
   658    677     ** in the worst case.  The worst case occurs if the transaction set
   659    678     ** must be appended to the current action table
   660    679     */
   661         -  n = p->mxLookahead + 1;
          680  +  n = p->nsymbol + 1;
   662    681     if( p->nAction + n >= p->nActionAlloc ){
   663    682       int oldAlloc = p->nActionAlloc;
   664    683       p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
   665    684       p->aAction = (struct lookahead_action *) realloc( p->aAction,
   666    685                             sizeof(p->aAction[0])*p->nActionAlloc);
   667    686       if( p->aAction==0 ){
   668    687         fprintf(stderr,"malloc failed\n");
................................................................................
   676    695   
   677    696     /* Scan the existing action table looking for an offset that is a
   678    697     ** duplicate of the current transaction set.  Fall out of the loop
   679    698     ** if and when the duplicate is found.
   680    699     **
   681    700     ** i is the index in p->aAction[] where p->mnLookahead is inserted.
   682    701     */
   683         -  for(i=p->nAction-1; i>=0; i--){
          702  +  end = makeItSafe ? p->mnLookahead : 0;
          703  +  for(i=p->nAction-1; i>=end; i--){
   684    704       if( p->aAction[i].lookahead==p->mnLookahead ){
   685    705         /* All lookaheads and actions in the aLookahead[] transaction
   686    706         ** must match against the candidate aAction[i] entry. */
   687    707         if( p->aAction[i].action!=p->mnAction ) continue;
   688    708         for(j=0; j<p->nLookahead; j++){
   689    709           k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   690    710           if( k<0 || k>=p->nAction ) break;
................................................................................
   706    726       }
   707    727     }
   708    728   
   709    729     /* If no existing offsets exactly match the current transaction, find an
   710    730     ** an empty offset in the aAction[] table in which we can add the
   711    731     ** aLookahead[] transaction.
   712    732     */
   713         -  if( i<0 ){
          733  +  if( i<end ){
   714    734       /* Look for holes in the aAction[] table that fit the current
   715    735       ** aLookahead[] transaction.  Leave i set to the offset of the hole.
   716    736       ** If no holes are found, i is left at p->nAction, which means the
   717    737       ** transaction will be appended. */
   718         -    for(i=0; i<p->nActionAlloc - p->mxLookahead; i++){
          738  +    i = makeItSafe ? p->mnLookahead : 0;
          739  +    for(; i<p->nActionAlloc - p->mxLookahead; i++){
   719    740         if( p->aAction[i].lookahead<0 ){
   720    741           for(j=0; j<p->nLookahead; j++){
   721    742             k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   722    743             if( k<0 ) break;
   723    744             if( p->aAction[k].lookahead>=0 ) break;
   724    745           }
   725    746           if( j<p->nLookahead ) continue;
................................................................................
   729    750           if( j==p->nAction ){
   730    751             break;  /* Fits in empty slots */
   731    752           }
   732    753         }
   733    754       }
   734    755     }
   735    756     /* Insert transaction set at index i. */
          757  +#if 0
          758  +  printf("Acttab:");
          759  +  for(j=0; j<p->nLookahead; j++){
          760  +    printf(" %d", p->aLookahead[j].lookahead);
          761  +  }
          762  +  printf(" inserted at %d\n", i);
          763  +#endif
   736    764     for(j=0; j<p->nLookahead; j++){
   737    765       k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   738    766       p->aAction[k] = p->aLookahead[j];
   739    767       if( k>=p->nAction ) p->nAction = k+1;
   740    768     }
          769  +  if( makeItSafe && i+p->nterminal>=p->nAction ) p->nAction = i+p->nterminal+1;
   741    770     p->nLookahead = 0;
   742    771   
   743    772     /* Return the offset that is added to the lookahead in order to get the
   744    773     ** index into yy_action of the action */
   745    774     return i - p->mnLookahead;
   746    775   }
          776  +
          777  +/*
          778  +** Return the size of the action table without the trailing syntax error
          779  +** entries.
          780  +*/
          781  +int acttab_action_size(acttab *p){
          782  +  int n = p->nAction;
          783  +  while( n>0 && p->aAction[n-1].lookahead<0 ){ n--; }
          784  +  return n;
          785  +}
   747    786   
   748    787   /********************** From the file "build.c" *****************************/
   749    788   /*
   750    789   ** Routines to construction the finite state machine for the LEMON
   751    790   ** parser generator.
   752    791   */
   753    792   
................................................................................
  1714   1753       stats_line("terminal symbols", lem.nterminal);
  1715   1754       stats_line("non-terminal symbols", lem.nsymbol - lem.nterminal);
  1716   1755       stats_line("total symbols", lem.nsymbol);
  1717   1756       stats_line("rules", lem.nrule);
  1718   1757       stats_line("states", lem.nxstate);
  1719   1758       stats_line("conflicts", lem.nconflict);
  1720   1759       stats_line("action table entries", lem.nactiontab);
         1760  +    stats_line("lookahead table entries", lem.nlookaheadtab);
  1721   1761       stats_line("total table size (bytes)", lem.tablesize);
  1722   1762     }
  1723   1763     if( lem.nconflict > 0 ){
  1724   1764       fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
  1725   1765     }
  1726   1766   
  1727   1767     /* return 0 on success, 1 on failure. */
................................................................................
  3015   3055     if( fp==0 && *mode=='w' ){
  3016   3056       fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
  3017   3057       lemp->errorcnt++;
  3018   3058       return 0;
  3019   3059     }
  3020   3060     return fp;
  3021   3061   }
         3062  +
         3063  +/* Print the text of a rule
         3064  +*/
         3065  +void rule_print(FILE *out, struct rule *rp){
         3066  +  int i, j;
         3067  +  fprintf(out, "%s",rp->lhs->name);
         3068  +  /*    if( rp->lhsalias ) fprintf(out,"(%s)",rp->lhsalias); */
         3069  +  fprintf(out," ::=");
         3070  +  for(i=0; i<rp->nrhs; i++){
         3071  +    struct symbol *sp = rp->rhs[i];
         3072  +    if( sp->type==MULTITERMINAL ){
         3073  +      fprintf(out," %s", sp->subsym[0]->name);
         3074  +      for(j=1; j<sp->nsubsym; j++){
         3075  +        fprintf(out,"|%s", sp->subsym[j]->name);
         3076  +      }
         3077  +    }else{
         3078  +      fprintf(out," %s", sp->name);
         3079  +    }
         3080  +    /* if( rp->rhsalias[i] ) fprintf(out,"(%s)",rp->rhsalias[i]); */
         3081  +  }
         3082  +}
  3022   3083   
  3023   3084   /* Duplicate the input file without comments and without actions
  3024   3085   ** on rules */
  3025   3086   void Reprint(struct lemon *lemp)
  3026   3087   {
  3027   3088     struct rule *rp;
  3028   3089     struct symbol *sp;
................................................................................
  3043   3104         sp = lemp->symbols[j];
  3044   3105         assert( sp->index==j );
  3045   3106         printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
  3046   3107       }
  3047   3108       printf("\n");
  3048   3109     }
  3049   3110     for(rp=lemp->rule; rp; rp=rp->next){
  3050         -    printf("%s",rp->lhs->name);
  3051         -    /*    if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
  3052         -    printf(" ::=");
  3053         -    for(i=0; i<rp->nrhs; i++){
  3054         -      sp = rp->rhs[i];
  3055         -      if( sp->type==MULTITERMINAL ){
  3056         -        printf(" %s", sp->subsym[0]->name);
  3057         -        for(j=1; j<sp->nsubsym; j++){
  3058         -          printf("|%s", sp->subsym[j]->name);
  3059         -        }
  3060         -      }else{
  3061         -        printf(" %s", sp->name);
  3062         -      }
  3063         -      /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
  3064         -    }
         3111  +    rule_print(stdout, rp);
  3065   3112       printf(".");
  3066   3113       if( rp->precsym ) printf(" [%s]",rp->precsym->name);
  3067   3114       /* if( rp->code ) printf("\n    %s",rp->code); */
  3068   3115       printf("\n");
  3069   3116     }
  3070   3117   }
  3071   3118   
................................................................................
  3317   3364   */
  3318   3365   PRIVATE int compute_action(struct lemon *lemp, struct action *ap)
  3319   3366   {
  3320   3367     int act;
  3321   3368     switch( ap->type ){
  3322   3369       case SHIFT:  act = ap->x.stp->statenum;                        break;
  3323   3370       case SHIFTREDUCE: {
  3324         -      act = ap->x.rp->iRule + lemp->nstate;
  3325   3371         /* Since a SHIFT is inherient after a prior REDUCE, convert any
  3326   3372         ** SHIFTREDUCE action with a nonterminal on the LHS into a simple
  3327   3373         ** REDUCE action: */
  3328         -      if( ap->sp->index>=lemp->nterminal ) act += lemp->nrule;
         3374  +      if( ap->sp->index>=lemp->nterminal ){
         3375  +        act = lemp->minReduce + ap->x.rp->iRule;
         3376  +      }else{
         3377  +        act = lemp->minShiftReduce + ap->x.rp->iRule;
         3378  +      }
  3329   3379         break;
  3330   3380       }
  3331         -    case REDUCE: act = ap->x.rp->iRule + lemp->nstate+lemp->nrule; break;
  3332         -    case ERROR:  act = lemp->nstate + lemp->nrule*2;               break;
  3333         -    case ACCEPT: act = lemp->nstate + lemp->nrule*2 + 1;           break;
         3381  +    case REDUCE: act = lemp->minReduce + ap->x.rp->iRule;          break;
         3382  +    case ERROR:  act = lemp->errAction;                            break;
         3383  +    case ACCEPT: act = lemp->accAction;                            break;
  3334   3384       default:     act = -1; break;
  3335   3385     }
  3336   3386     return act;
  3337   3387   }
  3338   3388   
  3339   3389   #define LINESIZE 1000
  3340   3390   /* The next cluster of routines are for reading the template file
................................................................................
  4034   4084     int szActionType;     /* sizeof(YYACTIONTYPE) */
  4035   4085     int szCodeType;       /* sizeof(YYCODETYPE)   */
  4036   4086     const char *name;
  4037   4087     int mnTknOfst, mxTknOfst;
  4038   4088     int mnNtOfst, mxNtOfst;
  4039   4089     struct axset *ax;
  4040   4090   
         4091  +  lemp->minShiftReduce = lemp->nstate;
         4092  +  lemp->errAction = lemp->minShiftReduce + lemp->nrule;
         4093  +  lemp->accAction = lemp->errAction + 1;
         4094  +  lemp->noAction = lemp->accAction + 1;
         4095  +  lemp->minReduce = lemp->noAction + 1;
         4096  +  lemp->maxAction = lemp->minReduce + lemp->nrule;
         4097  +
  4041   4098     in = tplt_open(lemp);
  4042   4099     if( in==0 ) return;
  4043   4100     out = file_open(lemp,".c","wb");
  4044   4101     if( out==0 ){
  4045   4102       fclose(in);
  4046   4103       return;
  4047   4104     }
................................................................................
  4072   4129     tplt_xfer(lemp->name,in,out,&lineno);
  4073   4130   
  4074   4131     /* Generate the defines */
  4075   4132     fprintf(out,"#define YYCODETYPE %s\n",
  4076   4133       minimum_size_type(0, lemp->nsymbol+1, &szCodeType)); lineno++;
  4077   4134     fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  4078   4135     fprintf(out,"#define YYACTIONTYPE %s\n",
  4079         -    minimum_size_type(0,lemp->nstate+lemp->nrule*2+5,&szActionType)); lineno++;
         4136  +    minimum_size_type(0,lemp->maxAction,&szActionType)); lineno++;
  4080   4137     if( lemp->wildcard ){
  4081   4138       fprintf(out,"#define YYWILDCARD %d\n",
  4082   4139          lemp->wildcard->index); lineno++;
  4083   4140     }
  4084   4141     print_stack_union(out,lemp,&lineno,mhflag);
  4085   4142     fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;
  4086   4143     if( lemp->stacksize ){
................................................................................
  4140   4197     }
  4141   4198     mxTknOfst = mnTknOfst = 0;
  4142   4199     mxNtOfst = mnNtOfst = 0;
  4143   4200     /* In an effort to minimize the action table size, use the heuristic
  4144   4201     ** of placing the largest action sets first */
  4145   4202     for(i=0; i<lemp->nxstate*2; i++) ax[i].iOrder = i;
  4146   4203     qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare);
  4147         -  pActtab = acttab_alloc();
         4204  +  pActtab = acttab_alloc(lemp->nsymbol, lemp->nterminal);
  4148   4205     for(i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++){
  4149   4206       stp = ax[i].stp;
  4150   4207       if( ax[i].isTkn ){
  4151   4208         for(ap=stp->ap; ap; ap=ap->next){
  4152   4209           int action;
  4153   4210           if( ap->sp->index>=lemp->nterminal ) continue;
  4154   4211           action = compute_action(lemp, ap);
  4155   4212           if( action<0 ) continue;
  4156   4213           acttab_action(pActtab, ap->sp->index, action);
  4157   4214         }
  4158         -      stp->iTknOfst = acttab_insert(pActtab);
         4215  +      stp->iTknOfst = acttab_insert(pActtab, 1);
  4159   4216         if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
  4160   4217         if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
  4161   4218       }else{
  4162   4219         for(ap=stp->ap; ap; ap=ap->next){
  4163   4220           int action;
  4164   4221           if( ap->sp->index<lemp->nterminal ) continue;
  4165   4222           if( ap->sp->index==lemp->nsymbol ) continue;
  4166   4223           action = compute_action(lemp, ap);
  4167   4224           if( action<0 ) continue;
  4168   4225           acttab_action(pActtab, ap->sp->index, action);
  4169   4226         }
  4170         -      stp->iNtOfst = acttab_insert(pActtab);
         4227  +      stp->iNtOfst = acttab_insert(pActtab, 0);
  4171   4228         if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
  4172   4229         if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
  4173   4230       }
  4174   4231   #if 0  /* Uncomment for a trace of how the yy_action[] table fills out */
  4175   4232       { int jj, nn;
  4176   4233         for(jj=nn=0; jj<pActtab->nAction; jj++){
  4177   4234           if( pActtab->aAction[jj].action<0 ) nn++;
................................................................................
  4196   4253       }
  4197   4254     }
  4198   4255   
  4199   4256     /* Finish rendering the constants now that the action table has
  4200   4257     ** been computed */
  4201   4258     fprintf(out,"#define YYNSTATE             %d\n",lemp->nxstate);  lineno++;
  4202   4259     fprintf(out,"#define YYNRULE              %d\n",lemp->nrule);  lineno++;
         4260  +  fprintf(out,"#define YYNTOKEN             %d\n",lemp->nterminal); lineno++;
  4203   4261     fprintf(out,"#define YY_MAX_SHIFT         %d\n",lemp->nxstate-1); lineno++;
  4204         -  fprintf(out,"#define YY_MIN_SHIFTREDUCE   %d\n",lemp->nstate); lineno++;
  4205         -  i = lemp->nstate + lemp->nrule;
         4262  +  i = lemp->minShiftReduce;
         4263  +  fprintf(out,"#define YY_MIN_SHIFTREDUCE   %d\n",i); lineno++;
         4264  +  i += lemp->nrule;
  4206   4265     fprintf(out,"#define YY_MAX_SHIFTREDUCE   %d\n", i-1); lineno++;
  4207         -  fprintf(out,"#define YY_MIN_REDUCE        %d\n", i); lineno++;
  4208         -  i = lemp->nstate + lemp->nrule*2;
         4266  +  fprintf(out,"#define YY_ERROR_ACTION      %d\n", lemp->errAction); lineno++;
         4267  +  fprintf(out,"#define YY_ACCEPT_ACTION     %d\n", lemp->accAction); lineno++;
         4268  +  fprintf(out,"#define YY_NO_ACTION         %d\n", lemp->noAction); lineno++;
         4269  +  fprintf(out,"#define YY_MIN_REDUCE        %d\n", lemp->minReduce); lineno++;
         4270  +  i = lemp->minReduce + lemp->nrule;
  4209   4271     fprintf(out,"#define YY_MAX_REDUCE        %d\n", i-1); lineno++;
  4210         -  fprintf(out,"#define YY_ERROR_ACTION      %d\n", i); lineno++;
  4211         -  fprintf(out,"#define YY_ACCEPT_ACTION     %d\n", i+1); lineno++;
  4212         -  fprintf(out,"#define YY_NO_ACTION         %d\n", i+2); lineno++;
  4213   4272     tplt_xfer(lemp->name,in,out,&lineno);
  4214   4273   
  4215   4274     /* Now output the action table and its associates:
  4216   4275     **
  4217   4276     **  yy_action[]        A single table containing all actions.
  4218   4277     **  yy_lookahead[]     A table containing the lookahead for each entry in
  4219   4278     **                     yy_action.  Used to detect hash collisions.
................................................................................
  4221   4280     **                     shifting terminals.
  4222   4281     **  yy_reduce_ofst[]   For each state, the offset into yy_action for
  4223   4282     **                     shifting non-terminals after a reduce.
  4224   4283     **  yy_default[]       Default action for each state.
  4225   4284     */
  4226   4285   
  4227   4286     /* Output the yy_action table */
  4228         -  lemp->nactiontab = n = acttab_size(pActtab);
         4287  +  lemp->nactiontab = n = acttab_action_size(pActtab);
  4229   4288     lemp->tablesize += n*szActionType;
  4230   4289     fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
  4231   4290     fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
  4232   4291     for(i=j=0; i<n; i++){
  4233   4292       int action = acttab_yyaction(pActtab, i);
  4234         -    if( action<0 ) action = lemp->nstate + lemp->nrule + 2;
         4293  +    if( action<0 ) action = lemp->noAction;
  4235   4294       if( j==0 ) fprintf(out," /* %5d */ ", i);
  4236   4295       fprintf(out, " %4d,", action);
  4237   4296       if( j==9 || i==n-1 ){
  4238   4297         fprintf(out, "\n"); lineno++;
  4239   4298         j = 0;
  4240   4299       }else{
  4241   4300         j++;
  4242   4301       }
  4243   4302     }
  4244   4303     fprintf(out, "};\n"); lineno++;
  4245   4304   
  4246   4305     /* Output the yy_lookahead table */
         4306  +  lemp->nlookaheadtab = n = acttab_lookahead_size(pActtab);
  4247   4307     lemp->tablesize += n*szCodeType;
  4248   4308     fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
  4249   4309     for(i=j=0; i<n; i++){
  4250   4310       int la = acttab_yylookahead(pActtab, i);
  4251   4311       if( la<0 ) la = lemp->nsymbol;
  4252   4312       if( j==0 ) fprintf(out," /* %5d */ ", i);
  4253   4313       fprintf(out, " %4d,", la);
................................................................................
  4259   4319       }
  4260   4320     }
  4261   4321     fprintf(out, "};\n"); lineno++;
  4262   4322   
  4263   4323     /* Output the yy_shift_ofst[] table */
  4264   4324     n = lemp->nxstate;
  4265   4325     while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
  4266         -  fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", lemp->nactiontab); lineno++;
  4267   4326     fprintf(out, "#define YY_SHIFT_COUNT    (%d)\n", n-1); lineno++;
  4268   4327     fprintf(out, "#define YY_SHIFT_MIN      (%d)\n", mnTknOfst); lineno++;
  4269   4328     fprintf(out, "#define YY_SHIFT_MAX      (%d)\n", mxTknOfst); lineno++;
  4270   4329     fprintf(out, "static const %s yy_shift_ofst[] = {\n",
  4271   4330          minimum_size_type(mnTknOfst, lemp->nterminal+lemp->nactiontab, &sz));
  4272   4331          lineno++;
  4273   4332     lemp->tablesize += n*sz;
................................................................................
  4284   4343       }else{
  4285   4344         j++;
  4286   4345       }
  4287   4346     }
  4288   4347     fprintf(out, "};\n"); lineno++;
  4289   4348   
  4290   4349     /* Output the yy_reduce_ofst[] table */
  4291         -  fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
  4292   4350     n = lemp->nxstate;
  4293   4351     while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
  4294   4352     fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
  4295   4353     fprintf(out, "#define YY_REDUCE_MIN   (%d)\n", mnNtOfst); lineno++;
  4296   4354     fprintf(out, "#define YY_REDUCE_MAX   (%d)\n", mxNtOfst); lineno++;
  4297   4355     fprintf(out, "static const %s yy_reduce_ofst[] = {\n",
  4298   4356             minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++;
................................................................................
  4316   4374     /* Output the default action table */
  4317   4375     fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
  4318   4376     n = lemp->nxstate;
  4319   4377     lemp->tablesize += n*szActionType;
  4320   4378     for(i=j=0; i<n; i++){
  4321   4379       stp = lemp->sorted[i];
  4322   4380       if( j==0 ) fprintf(out," /* %5d */ ", i);
  4323         -    fprintf(out, " %4d,", stp->iDfltReduce+lemp->nstate+lemp->nrule);
         4381  +    if( stp->iDfltReduce<0 ){
         4382  +      fprintf(out, " %4d,", lemp->errAction);
         4383  +    }else{
         4384  +      fprintf(out, " %4d,", stp->iDfltReduce + lemp->minReduce);
         4385  +    }
  4324   4386       if( j==9 || i==n-1 ){
  4325   4387         fprintf(out, "\n"); lineno++;
  4326   4388         j = 0;
  4327   4389       }else{
  4328   4390         j++;
  4329   4391       }
  4330   4392     }
................................................................................
  4350   4412     }
  4351   4413     tplt_xfer(lemp->name, in, out, &lineno);
  4352   4414   
  4353   4415     /* Generate a table containing the symbolic name of every symbol
  4354   4416     */
  4355   4417     for(i=0; i<lemp->nsymbol; i++){
  4356   4418       lemon_sprintf(line,"\"%s\",",lemp->symbols[i]->name);
  4357         -    fprintf(out,"  %-15s",line);
  4358         -    if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; }
         4419  +    fprintf(out,"  /* %4d */ \"%s\",\n",i, lemp->symbols[i]->name); lineno++;
  4359   4420     }
  4360         -  if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; }
  4361   4421     tplt_xfer(lemp->name,in,out,&lineno);
  4362   4422   
  4363   4423     /* Generate a table containing a text string that describes every
  4364   4424     ** rule in the rule set of the grammar.  This information is used
  4365   4425     ** when tracing REDUCE actions.
  4366   4426     */
  4367   4427     for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
................................................................................
  4440   4500     tplt_xfer(lemp->name,in,out,&lineno);
  4441   4501   
  4442   4502     /* Generate the table of rule information
  4443   4503     **
  4444   4504     ** Note: This code depends on the fact that rules are number
  4445   4505     ** sequentually beginning with 0.
  4446   4506     */
  4447         -  for(rp=lemp->rule; rp; rp=rp->next){
  4448         -    fprintf(out,"  { %d, %d },\n",rp->lhs->index,-rp->nrhs); lineno++;
         4507  +  for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
         4508  +    fprintf(out,"  { %4d, %4d }, /* (%d) ",rp->lhs->index,-rp->nrhs,i);
         4509  +    rule_print(out, rp);
         4510  +    fprintf(out," */\n"); lineno++;
  4449   4511     }
  4450   4512     tplt_xfer(lemp->name,in,out,&lineno);
  4451   4513   
  4452   4514     /* Generate code which execution during each REDUCE action */
  4453   4515     i = 0;
  4454   4516     for(rp=lemp->rule; rp; rp=rp->next){
  4455   4517       i += translate_code(lemp, rp);
................................................................................
  4707   4769     int i;
  4708   4770     struct state *stp;
  4709   4771     struct action *ap;
  4710   4772   
  4711   4773     for(i=0; i<lemp->nstate; i++){
  4712   4774       stp = lemp->sorted[i];
  4713   4775       stp->nTknAct = stp->nNtAct = 0;
  4714         -    stp->iDfltReduce = lemp->nrule;  /* Init dflt action to "syntax error" */
         4776  +    stp->iDfltReduce = -1; /* Init dflt action to "syntax error" */
  4715   4777       stp->iTknOfst = NO_OFFSET;
  4716   4778       stp->iNtOfst = NO_OFFSET;
  4717   4779       for(ap=stp->ap; ap; ap=ap->next){
  4718   4780         int iAction = compute_action(lemp,ap);
  4719   4781         if( iAction>=0 ){
  4720   4782           if( ap->sp->index<lemp->nterminal ){
  4721   4783             stp->nTknAct++;
  4722   4784           }else if( ap->sp->index<lemp->nsymbol ){
  4723   4785             stp->nNtAct++;
  4724   4786           }else{
  4725   4787             assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp );
  4726         -          stp->iDfltReduce = iAction - lemp->nstate - lemp->nrule;
         4788  +          stp->iDfltReduce = iAction;
  4727   4789           }
  4728   4790         }
  4729   4791       }
  4730   4792     }
  4731   4793     qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
  4732   4794           stateResortCompare);
  4733   4795     for(i=0; i<lemp->nstate; i++){

Changes to tool/lempar.c.

    68     68   **    ParseARG_PDECL     A parameter declaration for the %extra_argument
    69     69   **    ParseARG_STORE     Code to store %extra_argument into yypParser
    70     70   **    ParseARG_FETCH     Code to extract %extra_argument from yypParser
    71     71   **    YYERRORSYMBOL      is the code number of the error symbol.  If not
    72     72   **                       defined, then do no error processing.
    73     73   **    YYNSTATE           the combined number of states.
    74     74   **    YYNRULE            the number of rules in the grammar
           75  +**    YYNTOKEN           Number of terminal symbols
    75     76   **    YY_MAX_SHIFT       Maximum value for shift actions
    76     77   **    YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions
    77     78   **    YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions
    78         -**    YY_MIN_REDUCE      Minimum value for reduce actions
    79         -**    YY_MAX_REDUCE      Maximum value for reduce actions
    80     79   **    YY_ERROR_ACTION    The yy_action[] code for syntax error
    81     80   **    YY_ACCEPT_ACTION   The yy_action[] code for accept
    82     81   **    YY_NO_ACTION       The yy_action[] code for no-op
           82  +**    YY_MIN_REDUCE      Minimum value for reduce actions
           83  +**    YY_MAX_REDUCE      Maximum value for reduce actions
    83     84   */
    84     85   #ifndef INTERFACE
    85     86   # define INTERFACE 1
    86     87   #endif
    87     88   /************* Begin control #defines *****************************************/
    88     89   %%
    89     90   /************* End control #defines *******************************************/
................................................................................
   111    112   **
   112    113   **   0 <= N <= YY_MAX_SHIFT             Shift N.  That is, push the lookahead
   113    114   **                                      token onto the stack and goto state N.
   114    115   **
   115    116   **   N between YY_MIN_SHIFTREDUCE       Shift to an arbitrary state then
   116    117   **     and YY_MAX_SHIFTREDUCE           reduce by rule N-YY_MIN_SHIFTREDUCE.
   117    118   **
   118         -**   N between YY_MIN_REDUCE            Reduce by rule N-YY_MIN_REDUCE
   119         -**     and YY_MAX_REDUCE
   120         -**
   121    119   **   N == YY_ERROR_ACTION               A syntax error has occurred.
   122    120   **
   123    121   **   N == YY_ACCEPT_ACTION              The parser accepts its input.
   124    122   **
   125    123   **   N == YY_NO_ACTION                  No such action.  Denotes unused
   126    124   **                                      slots in the yy_action[] table.
          125  +**
          126  +**   N between YY_MIN_REDUCE            Reduce by rule N-YY_MIN_REDUCE
          127  +**     and YY_MAX_REDUCE
   127    128   **
   128    129   ** The action table is constructed as a single large table named yy_action[].
   129    130   ** Given state S and lookahead X, the action is computed as either:
   130    131   **
   131    132   **    (A)   N = yy_action[ yy_shift_ofst[S] + X ]
   132    133   **    (B)   N = yy_default[S]
   133    134   **
   134         -** The (A) formula is preferred.  The B formula is used instead if:
   135         -**    (1)  The yy_shift_ofst[S]+X value is out of range, or
   136         -**    (2)  yy_lookahead[yy_shift_ofst[S]+X] is not equal to X, or
   137         -**    (3)  yy_shift_ofst[S] equal YY_SHIFT_USE_DFLT.
   138         -** (Implementation note: YY_SHIFT_USE_DFLT is chosen so that
   139         -** YY_SHIFT_USE_DFLT+X will be out of range for all possible lookaheads X.
   140         -** Hence only tests (1) and (2) need to be evaluated.)
          135  +** The (A) formula is preferred.  The B formula is used instead if
          136  +** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X.
   141    137   **
   142    138   ** The formulas above are for computing the action when the lookahead is
   143    139   ** a terminal symbol.  If the lookahead is a non-terminal (as occurs after
   144    140   ** a reduce action) then the yy_reduce_ofst[] array is used in place of
   145         -** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of
   146         -** YY_SHIFT_USE_DFLT.
          141  +** the yy_shift_ofst[] array.
   147    142   **
   148    143   ** The following are the tables generated in this section:
   149    144   **
   150    145   **  yy_action[]        A single table containing all actions.
   151    146   **  yy_lookahead[]     A table containing the lookahead for each entry in
   152    147   **                     yy_action.  Used to detect hash collisions.
   153    148   **  yy_shift_ofst[]    For each state, the offset into yy_action for
................................................................................
   255    250     yyTraceFILE = TraceFILE;
   256    251     yyTracePrompt = zTracePrompt;
   257    252     if( yyTraceFILE==0 ) yyTracePrompt = 0;
   258    253     else if( yyTracePrompt==0 ) yyTraceFILE = 0;
   259    254   }
   260    255   #endif /* NDEBUG */
   261    256   
   262         -#ifndef NDEBUG
          257  +#if defined(YYCOVERAGE) || !defined(NDEBUG)
   263    258   /* For tracing shifts, the names of all terminals and nonterminals
   264    259   ** are required.  The following table supplies these names */
   265    260   static const char *const yyTokenName[] = { 
   266    261   %%
   267    262   };
   268         -#endif /* NDEBUG */
          263  +#endif /* defined(YYCOVERAGE) || !defined(NDEBUG) */
   269    264   
   270    265   #ifndef NDEBUG
   271    266   /* For tracing reduce actions, the names of all rules are required.
   272    267   */
   273    268   static const char *const yyRuleName[] = {
   274    269   %%
   275    270   };
................................................................................
   457    452   #ifdef YYTRACKMAXSTACKDEPTH
   458    453   int ParseStackPeak(void *p){
   459    454     yyParser *pParser = (yyParser*)p;
   460    455     return pParser->yyhwm;
   461    456   }
   462    457   #endif
   463    458   
          459  +/* This array of booleans keeps track of the parser statement
          460  +** coverage.  The element yycoverage[X][Y] is set when the parser
          461  +** is in state X and has a lookahead token Y.  In a well-tested
          462  +** systems, every element of this matrix should end up being set.
          463  +*/
          464  +#if defined(YYCOVERAGE)
          465  +static unsigned char yycoverage[YYNSTATE][YYNTOKEN];
          466  +#endif
          467  +
          468  +/*
          469  +** Write into out a description of every state/lookahead combination that
          470  +**
          471  +**   (1)  has not been used by the parser, and
          472  +**   (2)  is not a syntax error.
          473  +**
          474  +** Return the number of missed state/lookahead combinations.
          475  +*/
          476  +#if defined(YYCOVERAGE)
          477  +int ParseCoverage(FILE *out){
          478  +  int stateno, iLookAhead, i;
          479  +  int nMissed = 0;
          480  +  for(stateno=0; stateno<YYNSTATE; stateno++){
          481  +    i = yy_shift_ofst[stateno];
          482  +    for(iLookAhead=0; iLookAhead<YYNTOKEN; iLookAhead++){
          483  +      if( yy_lookahead[i+iLookAhead]!=iLookAhead ) continue;
          484  +      if( yycoverage[stateno][iLookAhead]==0 ) nMissed++;
          485  +      if( out ){
          486  +        fprintf(out,"State %d lookahead %s %s\n", stateno,
          487  +                yyTokenName[iLookAhead],
          488  +                yycoverage[stateno][iLookAhead] ? "ok" : "missed");
          489  +      }
          490  +    }
          491  +  }
          492  +  return nMissed;
          493  +}
          494  +#endif
          495  +
   464    496   /*
   465    497   ** Find the appropriate action for a parser given the terminal
   466    498   ** look-ahead token iLookAhead.
   467    499   */
   468    500   static unsigned int yy_find_shift_action(
   469    501     yyParser *pParser,        /* The parser */
   470    502     YYCODETYPE iLookAhead     /* The look-ahead token */
   471    503   ){
   472    504     int i;
   473    505     int stateno = pParser->yytos->stateno;
   474    506    
   475         -  if( stateno>=YY_MIN_REDUCE ) return stateno;
          507  +  if( stateno>YY_MAX_SHIFT ) return stateno;
   476    508     assert( stateno <= YY_SHIFT_COUNT );
          509  +#if defined(YYCOVERAGE)
          510  +  yycoverage[stateno][iLookAhead] = 1;
          511  +#endif
   477    512     do{
   478    513       i = yy_shift_ofst[stateno];
          514  +    assert( i>=0 && i+YYNTOKEN<=sizeof(yy_lookahead)/sizeof(yy_lookahead[0]) );
   479    515       assert( iLookAhead!=YYNOCODE );
          516  +    assert( iLookAhead < YYNTOKEN );
   480    517       i += iLookAhead;
   481         -    if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
          518  +    if( yy_lookahead[i]!=iLookAhead ){
   482    519   #ifdef YYFALLBACK
   483    520         YYCODETYPE iFallback;            /* Fallback token */
   484    521         if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
   485    522                && (iFallback = yyFallback[iLookAhead])!=0 ){
   486    523   #ifndef NDEBUG
   487    524           if( yyTraceFILE ){
   488    525             fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
................................................................................
   537    574     if( stateno>YY_REDUCE_COUNT ){
   538    575       return yy_default[stateno];
   539    576     }
   540    577   #else
   541    578     assert( stateno<=YY_REDUCE_COUNT );
   542    579   #endif
   543    580     i = yy_reduce_ofst[stateno];
   544         -  assert( i!=YY_REDUCE_USE_DFLT );
   545    581     assert( iLookAhead!=YYNOCODE );
   546    582     i += iLookAhead;
   547    583   #ifdef YYERRORSYMBOL
   548    584     if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
   549    585       return yy_default[stateno];
   550    586     }
   551    587   #else
................................................................................
   574    610      ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
   575    611   }
   576    612   
   577    613   /*
   578    614   ** Print tracing information for a SHIFT action
   579    615   */
   580    616   #ifndef NDEBUG
   581         -static void yyTraceShift(yyParser *yypParser, int yyNewState){
          617  +static void yyTraceShift(yyParser *yypParser, int yyNewState, const char *zTag){
   582    618     if( yyTraceFILE ){
   583    619       if( yyNewState<YYNSTATE ){
   584         -      fprintf(yyTraceFILE,"%sShift '%s', go to state %d\n",
   585         -         yyTracePrompt,yyTokenName[yypParser->yytos->major],
          620  +      fprintf(yyTraceFILE,"%s%s '%s', go to state %d\n",
          621  +         yyTracePrompt, zTag, yyTokenName[yypParser->yytos->major],
   586    622            yyNewState);
   587    623       }else{
   588         -      fprintf(yyTraceFILE,"%sShift '%s'\n",
   589         -         yyTracePrompt,yyTokenName[yypParser->yytos->major]);
          624  +      fprintf(yyTraceFILE,"%s%s '%s', pending reduce %d\n",
          625  +         yyTracePrompt, zTag, yyTokenName[yypParser->yytos->major],
          626  +         yyNewState - YY_MIN_REDUCE);
   590    627       }
   591    628     }
   592    629   }
   593    630   #else
   594         -# define yyTraceShift(X,Y)
          631  +# define yyTraceShift(X,Y,Z)
   595    632   #endif
   596    633   
   597    634   /*
   598    635   ** Perform a shift action.
   599    636   */
   600    637   static void yy_shift(
   601    638     yyParser *yypParser,          /* The parser to be shifted */
................................................................................
   629    666     if( yyNewState > YY_MAX_SHIFT ){
   630    667       yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   631    668     }
   632    669     yytos = yypParser->yytos;
   633    670     yytos->stateno = (YYACTIONTYPE)yyNewState;
   634    671     yytos->major = (YYCODETYPE)yyMajor;
   635    672     yytos->minor.yy0 = yyMinor;
   636         -  yyTraceShift(yypParser, yyNewState);
          673  +  yyTraceShift(yypParser, yyNewState, "Shift");
   637    674   }
   638    675   
   639    676   /* The following table contains information about every rule that
   640    677   ** is used during the reduce.
   641    678   */
   642    679   static const struct {
   643    680     YYCODETYPE lhs;       /* Symbol on the left-hand side of the rule */
................................................................................
   669    706     yyStackEntry *yymsp;            /* The top of the parser's stack */
   670    707     int yysize;                     /* Amount to pop the stack */
   671    708     ParseARG_FETCH;
   672    709     yymsp = yypParser->yytos;
   673    710   #ifndef NDEBUG
   674    711     if( yyTraceFILE && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){
   675    712       yysize = yyRuleInfo[yyruleno].nrhs;
   676         -    fprintf(yyTraceFILE, "%sReduce [%s], go to state %d.\n", yyTracePrompt,
   677         -      yyRuleName[yyruleno], yymsp[yysize].stateno);
          713  +    if( yysize ){
          714  +      fprintf(yyTraceFILE, "%sReduce %d [%s], go to state %d.\n",
          715  +        yyTracePrompt,
          716  +        yyruleno, yyRuleName[yyruleno], yymsp[yysize].stateno);
          717  +    }else{
          718  +      fprintf(yyTraceFILE, "%sReduce %d [%s].\n",
          719  +        yyTracePrompt, yyruleno, yyRuleName[yyruleno]);
          720  +    }
   678    721     }
   679    722   #endif /* NDEBUG */
   680    723   
   681    724     /* Check that the stack is large enough to grow by a single entry
   682    725     ** if the RHS of the rule is empty.  This ensures that there is room
   683    726     ** enough on the stack to push the LHS value */
   684    727     if( yyRuleInfo[yyruleno].nrhs==0 ){
................................................................................
   725    768     /* There are no SHIFTREDUCE actions on nonterminals because the table
   726    769     ** generator has simplified them to pure REDUCE actions. */
   727    770     assert( !(yyact>YY_MAX_SHIFT && yyact<=YY_MAX_SHIFTREDUCE) );
   728    771   
   729    772     /* It is not possible for a REDUCE to be followed by an error */
   730    773     assert( yyact!=YY_ERROR_ACTION );
   731    774   
   732         -  if( yyact==YY_ACCEPT_ACTION ){
   733         -    yypParser->yytos += yysize;
   734         -    yy_accept(yypParser);
   735         -  }else{
   736    775       yymsp += yysize+1;
   737    776       yypParser->yytos = yymsp;
   738    777       yymsp->stateno = (YYACTIONTYPE)yyact;
   739    778       yymsp->major = (YYCODETYPE)yygoto;
   740         -    yyTraceShift(yypParser, yyact);
   741         -  }
          779  +  yyTraceShift(yypParser, yyact, "... then shift");
   742    780   }
   743    781   
   744    782   /*
   745    783   ** The following code executes when the parse fails
   746    784   */
   747    785   #ifndef YYNOERRORRECOVERY
   748    786   static void yy_parse_failed(
................................................................................
   844    882   #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
   845    883     yyendofinput = (yymajor==0);
   846    884   #endif
   847    885     ParseARG_STORE;
   848    886   
   849    887   #ifndef NDEBUG
   850    888     if( yyTraceFILE ){
   851         -    fprintf(yyTraceFILE,"%sInput '%s'\n",yyTracePrompt,yyTokenName[yymajor]);
          889  +    int stateno = yypParser->yytos->stateno;
          890  +    if( stateno < YY_MIN_REDUCE ){
          891  +      fprintf(yyTraceFILE,"%sInput '%s' in state %d\n",
          892  +              yyTracePrompt,yyTokenName[yymajor],stateno);
          893  +    }else{
          894  +      fprintf(yyTraceFILE,"%sInput '%s' with pending reduce %d\n",
          895  +              yyTracePrompt,yyTokenName[yymajor],stateno-YY_MIN_REDUCE);
          896  +    }
   852    897     }
   853    898   #endif
   854    899   
   855    900     do{
   856    901       yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
   857         -    if( yyact <= YY_MAX_SHIFTREDUCE ){
          902  +    if( yyact >= YY_MIN_REDUCE ){
          903  +      yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor);
          904  +    }else if( yyact <= YY_MAX_SHIFTREDUCE ){
   858    905         yy_shift(yypParser,yyact,yymajor,yyminor);
   859    906   #ifndef YYNOERRORRECOVERY
   860    907         yypParser->yyerrcnt--;
   861    908   #endif
   862    909         yymajor = YYNOCODE;
   863         -    }else if( yyact <= YY_MAX_REDUCE ){
   864         -      yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor);
          910  +    }else if( yyact==YY_ACCEPT_ACTION ){
          911  +      yypParser->yytos--;
          912  +      yy_accept(yypParser);
          913  +      return;
   865    914       }else{
   866    915         assert( yyact == YY_ERROR_ACTION );
   867    916         yyminorunion.yy0 = yyminor;
   868    917   #ifdef YYERRORSYMBOL
   869    918         int yymx;
   870    919   #endif
   871    920   #ifndef NDEBUG