/ Check-in [4f955c00]
Login

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

Overview
Comment:Convert lemon to use a single perfect hash table for storing the actions. This should make the resulting parser both smaller and faster. (CVS 1112)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:4f955c00076b16166ff837749efb84201eab3c3a
User & Date: drh 2003-10-21 13:16:04
Context
2003-10-21
16:34
Fix bugs in lemon associated with the change to a perfect hash table. (CVS 1113) check-in: c0d1b269 user: drh tags: trunk
13:16
Convert lemon to use a single perfect hash table for storing the actions. This should make the resulting parser both smaller and faster. (CVS 1112) check-in: 4f955c00 user: drh tags: trunk
2003-10-18
09:37
Add sqlite_progress_handler() API for specifying an progress callback (CVS 1111) check-in: ddb36463 user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to tool/lemon.c.

     6      6   **
     7      7   ** The author of this program disclaims copyright.
     8      8   */
     9      9   #include <stdio.h>
    10     10   #include <stdarg.h>
    11     11   #include <string.h>
    12     12   #include <ctype.h>
           13  +#include <stdlib.h>
    13     14   
    14     15   extern void qsort();
    15     16   extern double strtod();
    16     17   extern long strtol();
    17     18   extern void free();
    18     19   extern int access();
    19     20   extern int atoi();
................................................................................
   211    212   /* Each state of the generated parser's finite state machine
   212    213   ** is encoded as an instance of the following structure. */
   213    214   struct state {
   214    215     struct config *bp;       /* The basis configurations for this state */
   215    216     struct config *cfp;      /* All configurations in this set */
   216    217     int index;               /* Sequencial number for this state */
   217    218     struct action *ap;       /* Array of actions for this state */
   218         -  int naction;             /* Number of actions for this state */
   219         -  int tabstart;            /* First index of the action table */
   220         -  int tabdfltact;          /* Default action */
          219  +  int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
          220  +  int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
          221  +  int iDflt;               /* Default action */
   221    222   };
          223  +#define NO_OFFSET (-2147483647)
   222    224   
   223    225   /* A followset propagation link indicates that the contents of one
   224    226   ** configuration followset should be propagated to another whenever
   225    227   ** the first changes. */
   226    228   struct plink {
   227    229     struct config *cfp;      /* The configuration to which linked */
   228    230     struct plink *next;      /* The next propagate link */
................................................................................
   390    392     new->sp = sp;
   391    393     if( type==SHIFT ){
   392    394       new->x.stp = (struct state *)arg;
   393    395     }else{
   394    396       new->x.rp = (struct rule *)arg;
   395    397     }
   396    398   }
          399  +/********************** New code to implement the "acttab" module ***********/
          400  +/*
          401  +** This module implements routines use to construct the yy_action[] table.
          402  +*/
          403  +
          404  +/*
          405  +** The state of the yy_action table under construction is an instance of
          406  +** the following structure
          407  +*/
          408  +typedef struct acttab acttab;
          409  +struct acttab {
          410  +  int nAction;                 /* Number of used slots in aAction[] */
          411  +  int nActionAlloc;            /* Slots allocated for aAction[] */
          412  +  struct {
          413  +    int lookahead;             /* Value of the lookahead token */
          414  +    int action;                /* Action to take on the given lookahead */
          415  +  } *aAction,                  /* The yy_action[] table under construction */
          416  +    *aLookahead;               /* A single new transaction set */
          417  +  int mnLookahead;             /* Minimum aLookahead[].lookahead */
          418  +  int mnAction;                /* Action associated with mnLookahead */
          419  +  int mxLookahead;             /* Maximum aLookahead[].lookahead */
          420  +  int nLookahead;              /* Used slots in aLookahead[] */
          421  +  int nLookaheadAlloc;         /* Slots allocated in aLookahead[] */
          422  +};
          423  +
          424  +/* Return the number of entries in the yy_action table */
          425  +#define acttab_size(X) ((X)->nAction)
          426  +
          427  +/* The value for the N-th entry in yy_action */
          428  +#define acttab_yyaction(X,N)  ((X)->aAction[N].action)
          429  +
          430  +/* The value for the N-th entry in yy_lookahead */
          431  +#define acttab_yylookahead(X,N)  ((X)->aAction[N].lookahead)
          432  +
          433  +/* Free all memory associated with the given acttab */
          434  +void acttab_free(acttab *p){
          435  +  free( p->aAction );
          436  +  free( p->aLookahead );
          437  +  free( p );
          438  +}
          439  +
          440  +/* Allocate a new acttab structure */
          441  +acttab *acttab_alloc(void){
          442  +  acttab *p = malloc( sizeof(*p) );
          443  +  if( p==0 ){
          444  +    fprintf(stderr,"Unable to allocate memory for a new acttab.");
          445  +    exit(1);
          446  +  }
          447  +  memset(p, 0, sizeof(*p));
          448  +  return p;
          449  +}
          450  +
          451  +/* Add a new action to the current transaction set
          452  +*/
          453  +void acttab_action(acttab *p, int lookahead, int action){
          454  +  if( p->nLookahead>=p->nLookaheadAlloc ){
          455  +    p->nLookaheadAlloc += 25;
          456  +    p->aLookahead = realloc( p->aLookahead,
          457  +                             sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
          458  +    if( p->aLookahead==0 ){
          459  +      fprintf(stderr,"malloc failed\n");
          460  +      exit(1);
          461  +    }
          462  +  }
          463  +  if( p->nLookahead==0 ){
          464  +    p->mxLookahead = lookahead;
          465  +    p->mnLookahead = lookahead;
          466  +    p->mnAction = action;
          467  +  }else{
          468  +    if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
          469  +    if( p->mnLookahead>lookahead ){
          470  +      p->mnLookahead = lookahead;
          471  +      p->mnAction = action;
          472  +    }
          473  +  }
          474  +  p->aLookahead[p->nLookahead].lookahead = lookahead;
          475  +  p->aLookahead[p->nLookahead].action = action;
          476  +  p->nLookahead++;
          477  +}
          478  +
          479  +/*
          480  +** Add the transaction set built up with prior calls to acttab_action()
          481  +** into the current action table.  Then reset the transaction set back
          482  +** to an empty set in preparation for a new round of acttab_action() calls.
          483  +**
          484  +** Return the offset into the action table of the new transaction.
          485  +*/
          486  +int acttab_insert(acttab *p){
          487  +  int i, j, k, n;
          488  +  assert( p->nLookahead>0 );
          489  +
          490  +  /* Make sure we have enough space to hold the expanded action table
          491  +  ** in the worst case.  The worst case occurs if the transaction set
          492  +  ** must be appended to the current action table
          493  +  */
          494  +  n = p->mxLookahead - p->mnLookahead + 1;
          495  +  if( p->nAction + n >= p->nActionAlloc ){
          496  +    p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
          497  +    p->aAction = realloc( p->aAction,
          498  +                          sizeof(p->aAction[0])*p->nActionAlloc);
          499  +    if( p->aAction==0 ){
          500  +      fprintf(stderr,"malloc failed\n");
          501  +      exit(1);
          502  +    }
          503  +    for(i=p->nAction; i<p->nActionAlloc; i++){
          504  +      p->aAction[i].lookahead = -1;
          505  +      p->aAction[i].action = -1;
          506  +    }
          507  +  }
          508  +
          509  +  /* Scan the existing action table looking for an offset where we can
          510  +  ** insert the current transaction set.  Fall out of the loop when that
          511  +  ** offset is found.  In the worst case, we fall out of the loop when
          512  +  ** i reaches p->nAction, which means we append the new transaction set.
          513  +  **
          514  +  ** i is the index in p->aAction[] where p->mnLookahead is inserted.
          515  +  */
          516  +  for(i=0; i<p->nAction; i++){
          517  +    if( p->aAction[i].lookahead<0 ){
          518  +      for(j=0; j<p->nLookahead; j++){
          519  +        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
          520  +        if( k<0 ) break;
          521  +        if( p->aAction[k].lookahead>=0 ) break;
          522  +      }
          523  +      if( j==p->nLookahead ) break;  /* Fits in empty slots */
          524  +    }else if( p->aAction[i].lookahead==p->mnLookahead ){
          525  +      if( p->aAction[i].action!=p->mnAction ) continue;
          526  +      for(j=0; j<p->nLookahead; j++){
          527  +        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
          528  +        if( k<0 || k>=p->nAction ) break;
          529  +        if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
          530  +        if( p->aLookahead[j].action!=p->aAction[k].action ) break;
          531  +      }
          532  +      if( j<p->nLookahead ) continue;
          533  +      n = 0;
          534  +      for(j=0; j<p->nAction; j++){
          535  +        if( p->aAction[j].lookahead==j+i-p->mnLookahead ) n++;
          536  +      }
          537  +      if( n==p->nLookahead ) break;  /* Same as a prior transaction set */
          538  +    }
          539  +  }
          540  +  /* Insert transaction set at index i. */
          541  +  for(j=0; j<p->nLookahead; j++){
          542  +    k = p->aLookahead[j].lookahead - p->mnLookahead + i;
          543  +    p->aAction[k] = p->aLookahead[j];
          544  +    if( k>=p->nAction ) p->nAction = k+1;
          545  +  }
          546  +  p->nLookahead = 0;
          547  +
          548  +  /* Return the offset that is added to the lookahead in order to get the
          549  +  ** index into yy_action of the action */
          550  +  return i - p->mnLookahead;
          551  +}
          552  +
   397    553   /********************** From the file "assert.c" ****************************/
   398    554   /*
   399    555   ** A more efficient way of handling assertions.
   400    556   */
   401    557   void myassert(file,line)
   402    558   char *file;
   403    559   int line;
................................................................................
  1668   1824         case OPT_FLAG:
  1669   1825         case OPT_FFLAG:
  1670   1826           fprintf(errstream,"  -%-*s  %s\n",max,op[i].label,op[i].message);
  1671   1827           break;
  1672   1828         case OPT_INT:
  1673   1829         case OPT_FINT:
  1674   1830           fprintf(errstream,"  %s=<integer>%*s  %s\n",op[i].label,
  1675         -          max-strlen(op[i].label)-9,"",op[i].message);
         1831  +          (int)(max-strlen(op[i].label)-9),"",op[i].message);
  1676   1832           break;
  1677   1833         case OPT_DBL:
  1678   1834         case OPT_FDBL:
  1679   1835           fprintf(errstream,"  %s=<real>%*s  %s\n",op[i].label,
  1680         -          max-strlen(op[i].label)-6,"",op[i].message);
         1836  +          (int)(max-strlen(op[i].label)-6),"",op[i].message);
  1681   1837           break;
  1682   1838         case OPT_STR:
  1683   1839         case OPT_FSTR:
  1684   1840           fprintf(errstream,"  %s=<string>%*s  %s\n",op[i].label,
  1685         -          max-strlen(op[i].label)-8,"",op[i].message);
         1841  +          (int)(max-strlen(op[i].label)-8),"",op[i].message);
  1686   1842           break;
  1687   1843       }
  1688   1844     }
  1689   1845   }
  1690   1846   /*********************** From the file "parse.c" ****************************/
  1691   1847   /*
  1692   1848   ** Input file parser for the LEMON parser generator.
................................................................................
  2650   2806     char buf[1000];
  2651   2807     FILE *in;
  2652   2808     char *tpltname;
  2653   2809     char *cp;
  2654   2810   
  2655   2811     cp = strrchr(lemp->filename,'.');
  2656   2812     if( cp ){
  2657         -    sprintf(buf,"%.*s.lt",(unsigned long)cp-(unsigned long)lemp->filename,lemp->filename);
         2813  +    sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
  2658   2814     }else{
  2659   2815       sprintf(buf,"%s.lt",lemp->filename);
  2660   2816     }
  2661   2817     if( access(buf,004)==0 ){
  2662   2818       tpltname = buf;
  2663   2819     }else if( access(templatename,004)==0 ){
  2664   2820       tpltname = templatename;
................................................................................
  2945   3101     free(types);
  2946   3102     fprintf(out,"} YYMINORTYPE;\n"); lineno++;
  2947   3103     *plineno = lineno;
  2948   3104   }
  2949   3105   
  2950   3106   /*
  2951   3107   ** Return the name of a C datatype able to represent values between
  2952         -** 0 and N, inclusive.
         3108  +** lwr and upr, inclusive.
  2953   3109   */
  2954         -static const char *minimum_size_type(int N){
  2955         -  if( N<=255 ){
  2956         -    return "unsigned char";
  2957         -  }else if( N<65535 ){
  2958         -    return "unsigned short int";
         3110  +static const char *minimum_size_type(int lwr, int upr){
         3111  +  if( lwr>=0 ){
         3112  +    if( upr<=255 ){
         3113  +      return "unsigned char";
         3114  +    }else if( upr<65535 ){
         3115  +      return "unsigned short int";
         3116  +    }else{
         3117  +      return "unsigned int";
         3118  +    }
         3119  +  }else if( lwr>=-127 && upr<=127 ){
         3120  +    return "signed char";
         3121  +  }else if( lwr>=-32767 && upr<32767 ){
         3122  +    return "short";
  2959   3123     }else{
  2960         -    return "unsigned int";
         3124  +    return "int";
  2961   3125     }
  2962   3126   }
  2963   3127   
  2964   3128   /* Generate C source code for the parser */
  2965   3129   void ReportTable(lemp, mhflag)
  2966   3130   struct lemon *lemp;
  2967   3131   int mhflag;     /* Output in makeheaders format if true */
................................................................................
  2968   3132   {
  2969   3133     FILE *out, *in;
  2970   3134     char line[LINESIZE];
  2971   3135     int  lineno;
  2972   3136     struct state *stp;
  2973   3137     struct action *ap;
  2974   3138     struct rule *rp;
  2975         -  int i, j;
  2976         -  int tablecnt;
         3139  +  struct acttab *pActtab;
         3140  +  int i, j, n;
  2977   3141     char *name;
         3142  +  int mnTknOfst, mxTknOfst;
         3143  +  int mnNtOfst, mxNtOfst;
  2978   3144   
  2979   3145     in = tplt_open(lemp);
  2980   3146     if( in==0 ) return;
  2981   3147     out = file_open(lemp,".c","w");
  2982   3148     if( out==0 ){
  2983   3149       fclose(in);
  2984   3150       return;
................................................................................
  3008   3174       fprintf(out,"#endif\n"); lineno++;
  3009   3175     }
  3010   3176     tplt_xfer(lemp->name,in,out,&lineno);
  3011   3177   
  3012   3178     /* Generate the defines */
  3013   3179     fprintf(out,"/* \001 */\n");
  3014   3180     fprintf(out,"#define YYCODETYPE %s\n",
  3015         -    minimum_size_type(lemp->nsymbol+5)); lineno++;
         3181  +    minimum_size_type(0, lemp->nsymbol+5)); lineno++;
  3016   3182     fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  3017   3183     fprintf(out,"#define YYACTIONTYPE %s\n",
  3018         -    minimum_size_type(lemp->nstate+lemp->nrule+5));  lineno++;
         3184  +    minimum_size_type(0, lemp->nstate+lemp->nrule+5));  lineno++;
  3019   3185     print_stack_union(out,lemp,&lineno,mhflag);
  3020   3186     if( lemp->stacksize ){
  3021   3187       if( atoi(lemp->stacksize)<=0 ){
  3022   3188         ErrorMsg(lemp->filename,0,
  3023   3189   "Illegal stack size: [%s].  The stack size should be an integer constant.",
  3024   3190           lemp->stacksize);
  3025   3191         lemp->errorcnt++;
................................................................................
  3058   3224     fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index);  lineno++;
  3059   3225     fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum);  lineno++;
  3060   3226     if( lemp->has_fallback ){
  3061   3227       fprintf(out,"#define YYFALLBACK 1\n");  lineno++;
  3062   3228     }
  3063   3229     tplt_xfer(lemp->name,in,out,&lineno);
  3064   3230   
  3065         -  /* Generate the action table.
         3231  +  /* Generate the action table and its associates:
  3066   3232     **
  3067         -  ** Each entry in the action table is an element of the following 
  3068         -  ** structure:
  3069         -  **   struct yyActionEntry {
  3070         -  **       YYCODETYPE            lookahead;
  3071         -  **       YYCODETYPE            next;
  3072         -  **       YYACTIONTYPE          action;
  3073         -  **   }
  3074         -  **
  3075         -  ** The entries are grouped into hash tables, one hash table for each
  3076         -  ** parser state.  The hash table has a size which is the number of
  3077         -  ** entries in that table.  In case of a collision, the "next" value
  3078         -  ** contains one more than the index into the hash table of the next
  3079         -  ** entry in the collision chain.  A "next" value of 0 means the end
  3080         -  ** of the chain has been reached.
         3233  +  **  yy_action[]        A single table containing all actions.
         3234  +  **  yy_lookahead[]     A table containing the lookahead for each entry in
         3235  +  **                     yy_action.  Used to detect hash collisions.
         3236  +  **  yy_shift_ofst[]    For each state, the offset into yy_action for
         3237  +  **                     shifting terminals.
         3238  +  **  yy_reduce_ofst[]   For each state, the offset into yy_action for
         3239  +  **                     shifting non-terminals after a reduce.
         3240  +  **  yy_default[]       Default action for each state.
  3081   3241     */
  3082         -  tablecnt = 0;
  3083   3242   
  3084         -  /* Loop over parser states */
         3243  +  /* Compute the actions on all states and count them up */
  3085   3244     for(i=0; i<lemp->nstate; i++){
  3086         -    int tablesize;              /* size of the hash table */
  3087         -    int j,k;                    /* Loop counter */
  3088         -    int collide[2048];          /* The collision chain for the table */
  3089         -    struct action *table[2048]; /* Build the hash table here */
  3090         -
  3091         -    /* Find the number of actions and initialize the hash table */
  3092   3245       stp = lemp->sorted[i];
  3093         -    stp->tabstart = tablecnt;
  3094         -    stp->naction = 0;
         3246  +    stp->nTknAct = stp->nNtAct = 0;
         3247  +    stp->iDflt = lemp->nstate + lemp->nrule;
         3248  +    stp->iTknOfst = NO_OFFSET;
         3249  +    stp->iNtOfst = NO_OFFSET;
  3095   3250       for(ap=stp->ap; ap; ap=ap->next){
  3096         -      if( ap->sp->index!=lemp->nsymbol && compute_action(lemp,ap)>=0 ){
  3097         -        stp->naction++;
         3251  +      if( compute_action(lemp,ap)>=0 ){
         3252  +        if( ap->sp->index<lemp->nterminal ){
         3253  +          stp->nTknAct++;
         3254  +        }else if( ap->sp->index<lemp->nsymbol ){
         3255  +          stp->nNtAct++;
         3256  +        }else{
         3257  +          stp->iDflt = compute_action(lemp, ap);
         3258  +        }
         3259  +      }
         3260  +    }
         3261  +  }
         3262  +  mxTknOfst = mnTknOfst = 0;
         3263  +  mxNtOfst = mnNtOfst = 0;
         3264  +
         3265  +  /* Compute the action table.  Do this in two passes.  The first
         3266  +  ** pass does all entries with two or more actions and the second
         3267  +  ** pass does all states with a single action.
         3268  +  */
         3269  +  pActtab = acttab_alloc();
         3270  +  for(j=0; j<=1; j++){
         3271  +    for(i=0; i<lemp->nstate; i++){
         3272  +      stp = lemp->sorted[i];
         3273  +      if( (j==0 && stp->nTknAct>=2) || (j==1 && stp->nTknAct==1) ){
         3274  +        for(ap=stp->ap; ap; ap=ap->next){
         3275  +          int action;
         3276  +          if( ap->sp->index>=lemp->nterminal ) continue;
         3277  +          action = compute_action(lemp, ap);
         3278  +          if( action<0 ) continue;
         3279  +          acttab_action(pActtab, ap->sp->index, action);
         3280  +        }
         3281  +        stp->iTknOfst = acttab_insert(pActtab);
         3282  +        if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
         3283  +        if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
  3098   3284         }
  3099         -    }
  3100         -    tablesize = stp->naction;
  3101         -    assert( tablesize<= sizeof(table)/sizeof(table[0]) );
  3102         -    for(j=0; j<tablesize; j++){
  3103         -      table[j] = 0;
  3104         -      collide[j] = -1;
  3105         -    }
  3106         -
  3107         -    /* Hash the actions into the hash table */
  3108         -    stp->tabdfltact = lemp->nstate + lemp->nrule;
  3109         -    for(ap=stp->ap; ap; ap=ap->next){
  3110         -      int action = compute_action(lemp,ap);
  3111         -      int h;
  3112         -      if( ap->sp->index==lemp->nsymbol ){
  3113         -        stp->tabdfltact = action;
  3114         -      }else if( action>=0 ){
  3115         -        h = ap->sp->index % tablesize;
  3116         -        ap->collide = table[h];
  3117         -        table[h] = ap;
         3285  +      if( (j==0 && stp->nNtAct>=2) || (j==1 && stp->nNtAct==1) ){
         3286  +        for(ap=stp->ap; ap; ap=ap->next){
         3287  +          int action;
         3288  +          if( ap->sp->index<lemp->nterminal ) continue;
         3289  +          if( ap->sp->index==lemp->nsymbol ) continue;
         3290  +          action = compute_action(lemp, ap);
         3291  +          if( action<0 ) continue;
         3292  +          acttab_action(pActtab, ap->sp->index, action);
         3293  +        }
         3294  +        stp->iNtOfst = acttab_insert(pActtab);
         3295  +        if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
         3296  +        if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
  3118   3297         }
  3119   3298       }
  3120         -
  3121         -    /* Resolve collisions */
  3122         -    for(j=k=0; j<tablesize; j++){
  3123         -      if( table[j] && table[j]->collide ){
  3124         -        while( table[k] ) k++;
  3125         -        table[k] = table[j]->collide;
  3126         -        collide[j] = k;
  3127         -        table[j]->collide = 0;
  3128         -        if( k<j ) j = k-1;
  3129         -      }
  3130         -    }
  3131         -
  3132         -    /* Print the hash table */
  3133         -    if( tablesize>0 ){
  3134         -      fprintf(out,"/* State %d */\n",stp->index); lineno++;
  3135         -    }
  3136         -    for(j=0; j<tablesize; j++){
  3137         -      assert( table[j]!=0 );
  3138         -      fprintf(out,"  {%4d,%4d,%4d}, /* %2d: ",
  3139         -          table[j]->sp->index,
  3140         -          collide[j]+1,
  3141         -          compute_action(lemp,table[j]),
  3142         -          j+1);
  3143         -      PrintAction(table[j],out,22);
  3144         -      fprintf(out," */\n"); 
  3145         -      lineno++;
  3146         -    }
  3147         -
  3148         -    /* Update the table count */
  3149         -    tablecnt += tablesize;
  3150         -  }
  3151         -  tplt_xfer(lemp->name,in,out,&lineno);
  3152         -  lemp->tablesize = tablecnt;
  3153         -
  3154         -  /* Generate the state table
  3155         -  **
  3156         -  ** Each entry is an element of the following structure:
  3157         -  **    struct yyStateEntry {
  3158         -  **      struct yyActionEntry *hashtbl;
  3159         -  **      YYCODETYPE nEntry;
  3160         -  **      YYACTIONTYPE actionDefault;
  3161         -  **    }
  3162         -  */
  3163         -  for(i=0; i<lemp->nstate; i++){
         3299  +  }
         3300  +
         3301  +  /* Output the yy_action table */
         3302  +  fprintf(out,"static YYACTIONTYPE yy_action[] = {\n"); lineno++;
         3303  +  n = acttab_size(pActtab);
         3304  +  for(i=j=0; i<n; i++){
         3305  +    int action = acttab_yyaction(pActtab, i);
         3306  +    if( action<0 ) action = lemp->nsymbol + lemp->nrule + 2;
         3307  +    fprintf(out, " %4d,", action);
         3308  +    if( j==9 || i==n-1 ){
         3309  +      fprintf(out, "\n"); lineno++;
         3310  +      j = 0;
         3311  +    }else{
         3312  +      j++;
         3313  +    }
         3314  +  }
         3315  +  fprintf(out, "};\n"); lineno++;
         3316  +
         3317  +  /* Output the yy_lookahead table */
         3318  +  fprintf(out,"static YYCODETYPE yy_lookahead[] = {\n"); lineno++;
         3319  +  for(i=j=0; i<n; i++){
         3320  +    int la = acttab_yylookahead(pActtab, i);
         3321  +    if( la<0 ) la = lemp->nsymbol;
         3322  +    fprintf(out, " %4d,", la);
         3323  +    if( j==9 || i==n-1 ){
         3324  +      fprintf(out, "\n"); lineno++;
         3325  +      j = 0;
         3326  +    }else{
         3327  +      j++;
         3328  +    }
         3329  +  }
         3330  +  fprintf(out, "};\n"); lineno++;
         3331  +
         3332  +  /* Output the yy_shift_ofst[] table */
         3333  +  fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
         3334  +  fprintf(out, "static %s yy_shift_ofst[] = {\n", 
         3335  +          minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
         3336  +  n = lemp->nstate;
         3337  +  for(i=j=0; i<n; i++){
         3338  +    int ofst;
         3339  +    stp = lemp->sorted[i];
         3340  +    ofst = stp->iTknOfst;
         3341  +    if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;
         3342  +    fprintf(out, " %4d,", ofst);
         3343  +    if( j==9 || i==n-1 ){
         3344  +      fprintf(out, "\n"); lineno++;
         3345  +      j = 0;
         3346  +    }else{
         3347  +      j++;
         3348  +    }
         3349  +  }
         3350  +  fprintf(out, "};\n"); lineno++;
         3351  +
         3352  +  /* Output the yy_reduce_ofst[] table */
         3353  +  fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
         3354  +  fprintf(out, "static %s yy_reduce_ofst[] = {\n", 
         3355  +          minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
         3356  +  n = lemp->nstate;
         3357  +  for(i=j=0; i<n; i++){
         3358  +    int ofst;
         3359  +    stp = lemp->sorted[i];
         3360  +    ofst = stp->iNtOfst;
         3361  +    if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
         3362  +    fprintf(out, " %4d,", ofst);
         3363  +    if( j==9 || i==n-1 ){
         3364  +      fprintf(out, "\n"); lineno++;
         3365  +      j = 0;
         3366  +    }else{
         3367  +      j++;
         3368  +    }
         3369  +  }
         3370  +  fprintf(out, "};\n"); lineno++;
         3371  +
         3372  +  /* Output the default action table */
         3373  +  fprintf(out, "static YYACTIONTYPE yy_default[] = {\n"); lineno++;
         3374  +  n = lemp->nstate;
         3375  +  for(i=j=0; i<n; i++){
  3164   3376       stp = lemp->sorted[i];
  3165         -    fprintf(out,"  { &yyActionTable[%d],%4d,%4d },\n",
  3166         -      stp->tabstart,
  3167         -      stp->naction,
  3168         -      stp->tabdfltact); lineno++;
         3377  +    fprintf(out, " %4d,", stp->iDflt);
         3378  +    if( j==9 || i==n-1 ){
         3379  +      fprintf(out, "\n"); lineno++;
         3380  +      j = 0;
         3381  +    }else{
         3382  +      j++;
         3383  +    }
  3169   3384     }
         3385  +  fprintf(out, "};\n"); lineno++;
  3170   3386     tplt_xfer(lemp->name,in,out,&lineno);
  3171   3387   
  3172   3388     /* Generate the table of fallback tokens.
  3173   3389     */
  3174   3390     if( lemp->has_fallback ){
  3175   3391       for(i=0; i<lemp->nterminal; i++){
  3176   3392         struct symbol *p = lemp->symbols[i];
................................................................................
  3332   3548   struct lemon *lemp;
  3333   3549   {
  3334   3550     struct state *stp;
  3335   3551     struct action *ap, *ap2;
  3336   3552     struct rule *rp, *rp2, *rbest;
  3337   3553     int nbest, n;
  3338   3554     int i;
  3339         -  int cnt;
  3340   3555   
  3341   3556     for(i=0; i<lemp->nstate; i++){
  3342   3557       stp = lemp->sorted[i];
  3343   3558       nbest = 0;
  3344   3559       rbest = 0;
  3345   3560   
  3346   3561       for(ap=stp->ap; ap; ap=ap->next){

Changes to tool/lempar.c.

    54     54   **    YYERRORSYMBOL      is the code number of the error symbol.  If not
    55     55   **                       defined, then do no error processing.
    56     56   */
    57     57   %%
    58     58   #define YY_NO_ACTION      (YYNSTATE+YYNRULE+2)
    59     59   #define YY_ACCEPT_ACTION  (YYNSTATE+YYNRULE+1)
    60     60   #define YY_ERROR_ACTION   (YYNSTATE+YYNRULE)
    61         -/* Next is the action table.  Each entry in this table contains
    62         -**
    63         -**  +  An integer which is the number representing the look-ahead
    64         -**     token
    65         -**
    66         -**  +  An integer indicating what action to take.  Number (N) between
    67         -**     0 and YYNSTATE-1 mean shift the look-ahead and go to state N.
    68         -**     Numbers between YYNSTATE and YYNSTATE+YYNRULE-1 mean reduce by
    69         -**     rule N-YYNSTATE.  Number YYNSTATE+YYNRULE means that a syntax
    70         -**     error has occurred.  Number YYNSTATE+YYNRULE+1 means the parser
    71         -**     accepts its input.
    72         -**
    73         -**  +  A pointer to the next entry with the same hash value.
    74         -**
    75         -** The action table is really a series of hash tables.  Each hash
    76         -** table contains a number of entries which is a power of two.  The
    77         -** "state" table (which follows) contains information about the starting
    78         -** point and size of each hash table.
    79         -*/
    80         -struct yyActionEntry {
    81         -  YYCODETYPE   lookahead;   /* The value of the look-ahead token */
    82         -  YYCODETYPE   next;        /* Next entry + 1. Zero at end of collision chain */
    83         -  YYACTIONTYPE action;      /* Action to take for this look-ahead */
    84         -};
    85         -typedef struct yyActionEntry yyActionEntry;
    86         -static const yyActionEntry yyActionTable[] = {
           61  +
           62  +/* Next are that ables used to determine what action to take based on the
           63  +** current state and lookahead token.  These tables are used to implement
           64  +** functions that take a state number and lookahead value and return an
           65  +** action integer.  
           66  +**
           67  +** The action integer is a number N between
           68  +** 0 and YYNSTATE-1 mean shift the look-ahead and go to state N.
           69  +** Numbers between YYNSTATE and YYNSTATE+YYNRULE-1 mean reduce by
           70  +** rule N-YYNSTATE.  Number YYNSTATE+YYNRULE means that a syntax
           71  +** error has occurred.  Number YYNSTATE+YYNRULE+1 means the parser
           72  +** accepts its input.
           73  +**
           74  +** The action table is constructed as a single large hash table with
           75  +** a perfect hash.  Given state S and lookahead X, the action is computed
           76  +** as
           77  +**
           78  +**      yy_action[ yy_shift_ofst[S] + X ]
           79  +**
           80  +** If the index yy_shift_ofst[S]+X is out of range or if the value
           81  +** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X or if yy_shift_ofst[S]
           82  +** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table
           83  +** and that yy_default[S] should be used instead.  
           84  +**
           85  +** The formula above is for computing the action when the lookahead is
           86  +** a terminal symbol.  If the lookahead is a non-terminal (as occurs after
           87  +** a reduce action) then the yy_reduce_ofst[] array is used in place of
           88  +** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of
           89  +** YY_SHIFT_USE_DFLT.
           90  +**
           91  +** The following are the tables generated in this section:
           92  +**
           93  +**  yy_action[]        A single table containing all actions.
           94  +**  yy_lookahead[]     A table containing the lookahead for each entry in
           95  +**                     yy_action.  Used to detect hash collisions.
           96  +**  yy_shift_ofst[]    For each state, the offset into yy_action for
           97  +**                     shifting terminals.
           98  +**  yy_reduce_ofst[]   For each state, the offset into yy_action for
           99  +**                     shifting non-terminals after a reduce.
          100  +**  yy_default[]       Default action for each state.
          101  +*/
    87    102   %%
    88         -};
    89         -
    90         -/* The state table contains information needed to look up the correct
    91         -** action in the action table, given the current state of the parser.
    92         -** Information needed includes:
    93         -**
    94         -**  +  A pointer to the start of the action hash table in yyActionTable.
    95         -**
    96         -**  +  The number of entries in the action hash table.
    97         -**
    98         -**  +  The default action.  This is the action to take if no entry for
    99         -**     the given look-ahead is found in the action hash table.
   100         -*/
   101         -struct yyStateEntry {
   102         -  const yyActionEntry *hashtbl;  /* Start of the hash table in yyActionTable */
   103         -  YYCODETYPE nEntry;             /* Number of entries in action hash table */
   104         -  YYACTIONTYPE actionDefault;    /* Default action if look-ahead not found */
   105         -};
   106         -typedef struct yyStateEntry yyStateEntry;
   107         -static const yyStateEntry yyStateTable[] = {
   108         -%%
   109         -};
          103  +#define YY_SZ_ACTTAB (sizeof(yy_action)/sizeof(yy_action[0]))
   110    104   
   111    105   /* The next table maps tokens into fallback tokens.  If a construct
   112    106   ** like the following:
   113    107   ** 
   114    108   **      %fallback ID X Y Z.
   115    109   **
   116    110   ** appears in the grammer, then ID becomes a fallback token for X, Y,
................................................................................
   308    302     yyParser *pParser = (yyParser*)p;
   309    303     if( pParser==0 ) return;
   310    304     while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser);
   311    305     (*freeProc)((void*)pParser);
   312    306   }
   313    307   
   314    308   /*
   315         -** Find the appropriate action for a parser given the look-ahead token.
          309  +** Find the appropriate action for a parser given the terminal
          310  +** look-ahead token iLookAhead.
   316    311   **
   317    312   ** If the look-ahead token is YYNOCODE, then check to see if the action is
   318    313   ** independent of the look-ahead.  If it is, return the action, otherwise
   319    314   ** return YY_NO_ACTION.
   320    315   */
   321         -static int yy_find_parser_action(
          316  +static int yy_find_shift_action(
   322    317     yyParser *pParser,        /* The parser */
   323         -  int iLookAhead             /* The look-ahead token */
          318  +  int iLookAhead            /* The look-ahead token */
   324    319   ){
   325         -  const yyStateEntry *pState;   /* Appropriate entry in the state table */
   326         -  const yyActionEntry *pAction; /* Action appropriate for the look-ahead */
   327         -  int iFallback;                /* Fallback token */
          320  +  int i;
   328    321    
   329    322     /* if( pParser->yyidx<0 ) return YY_NO_ACTION;  */
   330         -  pState = &yyStateTable[pParser->yytop->stateno];
   331         -  if( pState->nEntry==0 ){
   332         -    return pState->actionDefault;
   333         -  }else if( iLookAhead!=YYNOCODE ){
   334         -    pAction = &pState->hashtbl[iLookAhead % pState->nEntry];
   335         -    while( 1 ){
   336         -      if( pAction->lookahead==iLookAhead ) return pAction->action;
   337         -      if( pAction->next==0 ) break;
   338         -      pAction = &pState->hashtbl[pAction->next-1];
   339         -    }
          323  +  i = yy_shift_ofst[pParser->yytop->stateno];
          324  +  if( i==YY_SHIFT_USE_DFLT ){
          325  +    return yy_default[pParser->yytop->stateno];
          326  +  }
          327  +  if( iLookAhead==YYNOCODE ){
          328  +    return YY_NO_ACTION;
          329  +  }
          330  +  i += iLookAhead;
          331  +  if( i<0 || i>=YY_SZ_ACTTAB || yy_lookahead[i]!=iLookAhead ){
   340    332   #ifdef YYFALLBACK
          333  +    int iFallback;            /* Fallback token */
   341    334       if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
   342    335              && (iFallback = yyFallback[iLookAhead])!=0 ){
   343    336   #ifndef NDEBUG
   344    337         if( yyTraceFILE ){
   345    338           fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
   346    339              yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
   347    340         }
   348    341   #endif
   349         -      return yy_find_parser_action(pParser, iFallback);
          342  +      return yy_find_shift_action(pParser, iFallback);
   350    343       }
   351    344   #endif
   352         -  }else if( pState->hashtbl->lookahead!=YYNOCODE ){
          345  +    return yy_default[pParser->yytop->stateno];
          346  +  }else{
          347  +    return yy_action[i];
          348  +  }
          349  +}
          350  +
          351  +/*
          352  +** Find the appropriate action for a parser given the non-terminal
          353  +** look-ahead token iLookAhead.
          354  +**
          355  +** If the look-ahead token is YYNOCODE, then check to see if the action is
          356  +** independent of the look-ahead.  If it is, return the action, otherwise
          357  +** return YY_NO_ACTION.
          358  +*/
          359  +static int yy_find_reduce_action(
          360  +  yyParser *pParser,        /* The parser */
          361  +  int iLookAhead            /* The look-ahead token */
          362  +){
          363  +  int i;
          364  + 
          365  +  i = yy_reduce_ofst[pParser->yytop->stateno];
          366  +  if( i==YY_REDUCE_USE_DFLT ){
          367  +    return yy_default[pParser->yytop->stateno];
          368  +  }
          369  +  if( iLookAhead==YYNOCODE ){
   353    370       return YY_NO_ACTION;
   354    371     }
   355         -  return pState->actionDefault;
          372  +  i += iLookAhead;
          373  +  if( i<0 || i>=YY_SZ_ACTTAB || yy_lookahead[i]!=iLookAhead ){
          374  +    return yy_default[pParser->yytop->stateno];
          375  +  }else{
          376  +    return yy_action[i];
          377  +  }
   356    378   }
   357    379   
   358    380   /*
   359    381   ** Perform a shift action.
   360    382   */
   361    383   static void yy_shift(
   362    384     yyParser *yypParser,          /* The parser to be shifted */
................................................................................
   443    465     */
   444    466   %%
   445    467     };
   446    468     yygoto = yyRuleInfo[yyruleno].lhs;
   447    469     yysize = yyRuleInfo[yyruleno].nrhs;
   448    470     yypParser->yyidx -= yysize;
   449    471     yypParser->yytop -= yysize;
   450         -  yyact = yy_find_parser_action(yypParser,yygoto);
          472  +  yyact = yy_find_reduce_action(yypParser,yygoto);
   451    473     if( yyact < YYNSTATE ){
   452    474       yy_shift(yypParser,yyact,yygoto,&yygotominor);
   453    475     }else if( yyact == YYNSTATE + YYNRULE + 1 ){
   454    476       yy_accept(yypParser);
   455    477     }
   456    478   }
   457    479   
................................................................................
   555    577   #ifndef NDEBUG
   556    578     if( yyTraceFILE ){
   557    579       fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
   558    580     }
   559    581   #endif
   560    582   
   561    583     do{
   562         -    yyact = yy_find_parser_action(yypParser,yymajor);
          584  +    yyact = yy_find_shift_action(yypParser,yymajor);
   563    585       if( yyact<YYNSTATE ){
   564    586         yy_shift(yypParser,yyact,yymajor,&yyminorunion);
   565    587         yypParser->yyerrcnt--;
   566    588         if( yyendofinput && yypParser->yyidx>=0 ){
   567    589           yymajor = 0;
   568    590         }else{
   569    591           yymajor = YYNOCODE;
................................................................................
   608    630   #endif
   609    631           yy_destructor(yymajor,&yyminorunion);
   610    632           yymajor = YYNOCODE;
   611    633         }else{
   612    634            while(
   613    635             yypParser->yyidx >= 0 &&
   614    636             yypParser->yytop->major != YYERRORSYMBOL &&
   615         -          (yyact = yy_find_parser_action(yypParser,YYERRORSYMBOL)) >= YYNSTATE
          637  +          (yyact = yy_find_shift_action(yypParser,YYERRORSYMBOL)) >= YYNSTATE
   616    638           ){
   617    639             yy_pop_parser_stack(yypParser);
   618    640           }
   619    641           if( yypParser->yyidx < 0 || yymajor==0 ){
   620    642             yy_destructor(yymajor,&yyminorunion);
   621    643             yy_parse_failed(yypParser);
   622    644             yymajor = YYNOCODE;