/ Check-in [c0d1b269]
Login

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

Overview
Comment:Fix bugs in lemon associated with the change to a perfect hash table. (CVS 1113)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:c0d1b26966aeb445fea5792e5a9e93632e758c2a
User & Date: drh 2003-10-21 16:34:42
Context
2003-10-22
22:15
Comment changes to the lemon parser template. Change some sqliteMalloc() calls to sqliteMallocRaw() for speed. Update the website template. (CVS 1114) check-in: c637caf1 user: drh tags: trunk
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
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to tool/lemon.c.

489
490
491
492
493
494
495

496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
...
516
517
518
519
520
521
522





523

524
525
526
527
528
529
530
531
532
533
534
535

536

537

538
539
540
541
542
543
544
....
3120
3121
3122
3123
3124
3125
3126





















3127
3128
3129
3130
3131
3132
3133
....
3137
3138
3139
3140
3141
3142
3143

3144
3145
3146
3147
3148
3149
3150
....
3237
3238
3239
3240
3241
3242
3243





3244
3245
3246
3247
3248
3249
3250
....
3254
3255
3256
3257
3258
3259
3260






3261
3262
3263
3264
3265
3266
3267
3268

3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299

3300
3301
3302
3303
3304
3305
3306

3307
3308
3309
3310
3311
3312
3313
....
3315
3316
3317
3318
3319
3320
3321

3322
3323
3324
3325
3326
3327
3328
....
3335
3336
3337
3338
3339
3340
3341

3342
3343
3344
3345
3346
3347
3348
....
3355
3356
3357
3358
3359
3360
3361

3362
3363
3364
3365
3366
3367
3368
....
3370
3371
3372
3373
3374
3375
3376

3377
3378
3379
3380
3381
3382
3383

  /* Make sure we have enough space to hold the expanded action table
  ** in the worst case.  The worst case occurs if the transaction set
  ** must be appended to the current action table
  */
  n = p->mxLookahead - p->mnLookahead + 1;
  if( p->nAction + n >= p->nActionAlloc ){

    p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
    p->aAction = realloc( p->aAction,
                          sizeof(p->aAction[0])*p->nActionAlloc);
    if( p->aAction==0 ){
      fprintf(stderr,"malloc failed\n");
      exit(1);
    }
    for(i=p->nAction; i<p->nActionAlloc; i++){
      p->aAction[i].lookahead = -1;
      p->aAction[i].action = -1;
    }
  }

  /* Scan the existing action table looking for an offset where we can
  ** insert the current transaction set.  Fall out of the loop when that
................................................................................
  for(i=0; i<p->nAction; i++){
    if( p->aAction[i].lookahead<0 ){
      for(j=0; j<p->nLookahead; j++){
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
        if( k<0 ) break;
        if( p->aAction[k].lookahead>=0 ) break;
      }





      if( j==p->nLookahead ) break;  /* Fits in empty slots */

    }else if( p->aAction[i].lookahead==p->mnLookahead ){
      if( p->aAction[i].action!=p->mnAction ) continue;
      for(j=0; j<p->nLookahead; j++){
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
        if( k<0 || k>=p->nAction ) break;
        if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
        if( p->aLookahead[j].action!=p->aAction[k].action ) break;
      }
      if( j<p->nLookahead ) continue;
      n = 0;
      for(j=0; j<p->nAction; j++){
        if( p->aAction[j].lookahead==j+i-p->mnLookahead ) n++;

      }

      if( n==p->nLookahead ) break;  /* Same as a prior transaction set */

    }
  }
  /* Insert transaction set at index i. */
  for(j=0; j<p->nLookahead; j++){
    k = p->aLookahead[j].lookahead - p->mnLookahead + i;
    p->aAction[k] = p->aLookahead[j];
    if( k>=p->nAction ) p->nAction = k+1;
................................................................................
    return "signed char";
  }else if( lwr>=-32767 && upr<32767 ){
    return "short";
  }else{
    return "int";
  }
}






















/* Generate C source code for the parser */
void ReportTable(lemp, mhflag)
struct lemon *lemp;
int mhflag;     /* Output in makeheaders format if true */
{
  FILE *out, *in;
................................................................................
  struct action *ap;
  struct rule *rp;
  struct acttab *pActtab;
  int i, j, n;
  char *name;
  int mnTknOfst, mxTknOfst;
  int mnNtOfst, mxNtOfst;


  in = tplt_open(lemp);
  if( in==0 ) return;
  out = file_open(lemp,".c","w");
  if( out==0 ){
    fclose(in);
    return;
................................................................................
  **                     shifting terminals.
  **  yy_reduce_ofst[]   For each state, the offset into yy_action for
  **                     shifting non-terminals after a reduce.
  **  yy_default[]       Default action for each state.
  */

  /* Compute the actions on all states and count them up */





  for(i=0; i<lemp->nstate; i++){
    stp = lemp->sorted[i];
    stp->nTknAct = stp->nNtAct = 0;
    stp->iDflt = lemp->nstate + lemp->nrule;
    stp->iTknOfst = NO_OFFSET;
    stp->iNtOfst = NO_OFFSET;
    for(ap=stp->ap; ap; ap=ap->next){
................................................................................
        }else if( ap->sp->index<lemp->nsymbol ){
          stp->nNtAct++;
        }else{
          stp->iDflt = compute_action(lemp, ap);
        }
      }
    }






  }
  mxTknOfst = mnTknOfst = 0;
  mxNtOfst = mnNtOfst = 0;

  /* Compute the action table.  Do this in two passes.  The first
  ** pass does all entries with two or more actions and the second
  ** pass does all states with a single action.
  */

  pActtab = acttab_alloc();
  for(j=0; j<=1; j++){
    for(i=0; i<lemp->nstate; i++){
      stp = lemp->sorted[i];
      if( (j==0 && stp->nTknAct>=2) || (j==1 && stp->nTknAct==1) ){
        for(ap=stp->ap; ap; ap=ap->next){
          int action;
          if( ap->sp->index>=lemp->nterminal ) continue;
          action = compute_action(lemp, ap);
          if( action<0 ) continue;
          acttab_action(pActtab, ap->sp->index, action);
        }
        stp->iTknOfst = acttab_insert(pActtab);
        if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
        if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
      }
      if( (j==0 && stp->nNtAct>=2) || (j==1 && stp->nNtAct==1) ){
        for(ap=stp->ap; ap; ap=ap->next){
          int action;
          if( ap->sp->index<lemp->nterminal ) continue;
          if( ap->sp->index==lemp->nsymbol ) continue;
          action = compute_action(lemp, ap);
          if( action<0 ) continue;
          acttab_action(pActtab, ap->sp->index, action);
        }
        stp->iNtOfst = acttab_insert(pActtab);
        if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
        if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
      }
    }
  }


  /* Output the yy_action table */
  fprintf(out,"static YYACTIONTYPE yy_action[] = {\n"); lineno++;
  n = acttab_size(pActtab);
  for(i=j=0; i<n; i++){
    int action = acttab_yyaction(pActtab, i);
    if( action<0 ) action = lemp->nsymbol + lemp->nrule + 2;

    fprintf(out, " %4d,", action);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
  fprintf(out, "};\n"); lineno++;

  /* Output the yy_lookahead table */
  fprintf(out,"static YYCODETYPE yy_lookahead[] = {\n"); lineno++;
  for(i=j=0; i<n; i++){
    int la = acttab_yylookahead(pActtab, i);
    if( la<0 ) la = lemp->nsymbol;

    fprintf(out, " %4d,", la);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
          minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    int ofst;
    stp = lemp->sorted[i];
    ofst = stp->iTknOfst;
    if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;

    fprintf(out, " %4d,", ofst);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
          minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    int ofst;
    stp = lemp->sorted[i];
    ofst = stp->iNtOfst;
    if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;

    fprintf(out, " %4d,", ofst);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
  fprintf(out, "};\n"); lineno++;

  /* Output the default action table */
  fprintf(out, "static YYACTIONTYPE yy_default[] = {\n"); lineno++;
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    stp = lemp->sorted[i];

    fprintf(out, " %4d,", stp->iDflt);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }







>







|







 







>
>
>
>
>
|
>











|
>

>
|
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>







 







>
>
>
>
>







 







>
>
>
>
>
>




|
|
|

>

<
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<
|
|
|
|
|
|
|
|
|
|
|
|
|
<
>







>







 







>







 







>







 







>







 







>







489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
...
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
....
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
....
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
....
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
....
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313

3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327

3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340

3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
....
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
....
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
....
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
....
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430

  /* Make sure we have enough space to hold the expanded action table
  ** in the worst case.  The worst case occurs if the transaction set
  ** must be appended to the current action table
  */
  n = p->mxLookahead - p->mnLookahead + 1;
  if( p->nAction + n >= p->nActionAlloc ){
    int oldAlloc = p->nActionAlloc;
    p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
    p->aAction = realloc( p->aAction,
                          sizeof(p->aAction[0])*p->nActionAlloc);
    if( p->aAction==0 ){
      fprintf(stderr,"malloc failed\n");
      exit(1);
    }
    for(i=oldAlloc; i<p->nActionAlloc; i++){
      p->aAction[i].lookahead = -1;
      p->aAction[i].action = -1;
    }
  }

  /* Scan the existing action table looking for an offset where we can
  ** insert the current transaction set.  Fall out of the loop when that
................................................................................
  for(i=0; i<p->nAction; i++){
    if( p->aAction[i].lookahead<0 ){
      for(j=0; j<p->nLookahead; j++){
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
        if( k<0 ) break;
        if( p->aAction[k].lookahead>=0 ) break;
      }
      if( j<p->nLookahead ) continue;
      for(j=0; j<p->nAction; j++){
        if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
      }
      if( j==p->nAction ){
        break;  /* Fits in empty slots */
      }
    }else if( p->aAction[i].lookahead==p->mnLookahead ){
      if( p->aAction[i].action!=p->mnAction ) continue;
      for(j=0; j<p->nLookahead; j++){
        k = p->aLookahead[j].lookahead - p->mnLookahead + i;
        if( k<0 || k>=p->nAction ) break;
        if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
        if( p->aLookahead[j].action!=p->aAction[k].action ) break;
      }
      if( j<p->nLookahead ) continue;
      n = 0;
      for(j=0; j<p->nAction; j++){
        if( p->aAction[j].lookahead<0 ) continue;
        if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
      }
      if( n==p->nLookahead ){
        break;  /* Same as a prior transaction set */
      }
    }
  }
  /* Insert transaction set at index i. */
  for(j=0; j<p->nLookahead; j++){
    k = p->aLookahead[j].lookahead - p->mnLookahead + i;
    p->aAction[k] = p->aLookahead[j];
    if( k>=p->nAction ) p->nAction = k+1;
................................................................................
    return "signed char";
  }else if( lwr>=-32767 && upr<32767 ){
    return "short";
  }else{
    return "int";
  }
}

/*
** Each state contains a set of token transaction and a set of
** nonterminal transactions.  Each of these sets makes an instance
** of the following structure.  An array of these structures is used
** to order the creation of entries in the yy_action[] table.
*/
struct axset {
  struct state *stp;   /* A pointer to a state */
  int isTkn;           /* True to use tokens.  False for non-terminals */
  int nAction;         /* Number of actions */
};

/*
** Compare to axset structures for sorting purposes
*/
static int axset_compare(const void *a, const void *b){
  struct axset *p1 = (struct axset*)a;
  struct axset *p2 = (struct axset*)b;
  return p2->nAction - p1->nAction;
}

/* Generate C source code for the parser */
void ReportTable(lemp, mhflag)
struct lemon *lemp;
int mhflag;     /* Output in makeheaders format if true */
{
  FILE *out, *in;
................................................................................
  struct action *ap;
  struct rule *rp;
  struct acttab *pActtab;
  int i, j, n;
  char *name;
  int mnTknOfst, mxTknOfst;
  int mnNtOfst, mxNtOfst;
  struct axset *ax;

  in = tplt_open(lemp);
  if( in==0 ) return;
  out = file_open(lemp,".c","w");
  if( out==0 ){
    fclose(in);
    return;
................................................................................
  **                     shifting terminals.
  **  yy_reduce_ofst[]   For each state, the offset into yy_action for
  **                     shifting non-terminals after a reduce.
  **  yy_default[]       Default action for each state.
  */

  /* Compute the actions on all states and count them up */
  ax = malloc( sizeof(ax[0])*lemp->nstate*2 );
  if( ax==0 ){
    fprintf(stderr,"malloc failed\n");
    exit(1);
  }
  for(i=0; i<lemp->nstate; i++){
    stp = lemp->sorted[i];
    stp->nTknAct = stp->nNtAct = 0;
    stp->iDflt = lemp->nstate + lemp->nrule;
    stp->iTknOfst = NO_OFFSET;
    stp->iNtOfst = NO_OFFSET;
    for(ap=stp->ap; ap; ap=ap->next){
................................................................................
        }else if( ap->sp->index<lemp->nsymbol ){
          stp->nNtAct++;
        }else{
          stp->iDflt = compute_action(lemp, ap);
        }
      }
    }
    ax[i*2].stp = stp;
    ax[i*2].isTkn = 1;
    ax[i*2].nAction = stp->nTknAct;
    ax[i*2+1].stp = stp;
    ax[i*2+1].isTkn = 0;
    ax[i*2+1].nAction = stp->nNtAct;
  }
  mxTknOfst = mnTknOfst = 0;
  mxNtOfst = mnNtOfst = 0;

  /* Compute the action table.  In order to try to keep the size of the
  ** action table to a minimum, the heuristic of placing the largest action
  ** sets first is used.
  */
  qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
  pActtab = acttab_alloc();

  for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
    stp = ax[i].stp;
    if( ax[i].isTkn ){
      for(ap=stp->ap; ap; ap=ap->next){
        int action;
        if( ap->sp->index>=lemp->nterminal ) continue;
        action = compute_action(lemp, ap);
        if( action<0 ) continue;
        acttab_action(pActtab, ap->sp->index, action);
      }
      stp->iTknOfst = acttab_insert(pActtab);
      if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
      if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
    }else{

      for(ap=stp->ap; ap; ap=ap->next){
        int action;
        if( ap->sp->index<lemp->nterminal ) continue;
        if( ap->sp->index==lemp->nsymbol ) continue;
        action = compute_action(lemp, ap);
        if( action<0 ) continue;
        acttab_action(pActtab, ap->sp->index, action);
      }
      stp->iNtOfst = acttab_insert(pActtab);
      if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
      if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
    }
  }

  free(ax);

  /* Output the yy_action table */
  fprintf(out,"static YYACTIONTYPE yy_action[] = {\n"); lineno++;
  n = acttab_size(pActtab);
  for(i=j=0; i<n; i++){
    int action = acttab_yyaction(pActtab, i);
    if( action<0 ) action = lemp->nsymbol + lemp->nrule + 2;
    if( j==0 ) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", action);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
  fprintf(out, "};\n"); lineno++;

  /* Output the yy_lookahead table */
  fprintf(out,"static YYCODETYPE yy_lookahead[] = {\n"); lineno++;
  for(i=j=0; i<n; i++){
    int la = acttab_yylookahead(pActtab, i);
    if( la<0 ) la = lemp->nsymbol;
    if( j==0 ) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", la);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
          minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    int ofst;
    stp = lemp->sorted[i];
    ofst = stp->iTknOfst;
    if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;
    if( j==0 ) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", ofst);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
          minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    int ofst;
    stp = lemp->sorted[i];
    ofst = stp->iNtOfst;
    if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
    if( j==0 ) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", ofst);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
................................................................................
  fprintf(out, "};\n"); lineno++;

  /* Output the default action table */
  fprintf(out, "static YYACTIONTYPE yy_default[] = {\n"); lineno++;
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    stp = lemp->sorted[i];
    if( j==0 ) fprintf(out," /* %5d */ ", i);
    fprintf(out, " %4d,", stp->iDflt);
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }

Changes to tool/lempar.c.

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
**                       defined, then do no error processing.
*/
%%
#define YY_NO_ACTION      (YYNSTATE+YYNRULE+2)
#define YY_ACCEPT_ACTION  (YYNSTATE+YYNRULE+1)
#define YY_ERROR_ACTION   (YYNSTATE+YYNRULE)

/* Next are that ables used to determine what action to take based on the
** current state and lookahead token.  These tables are used to implement
** functions that take a state number and lookahead value and return an
** action integer.  
**
** The action integer is a number N between
** 0 and YYNSTATE-1 mean shift the look-ahead and go to state N.
** Numbers between YYNSTATE and YYNSTATE+YYNRULE-1 mean reduce by







|







55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
**                       defined, then do no error processing.
*/
%%
#define YY_NO_ACTION      (YYNSTATE+YYNRULE+2)
#define YY_ACCEPT_ACTION  (YYNSTATE+YYNRULE+1)
#define YY_ERROR_ACTION   (YYNSTATE+YYNRULE)

/* Next are that tables used to determine what action to take based on the
** current state and lookahead token.  These tables are used to implement
** functions that take a state number and lookahead value and return an
** action integer.  
**
** The action integer is a number N between
** 0 and YYNSTATE-1 mean shift the look-ahead and go to state N.
** Numbers between YYNSTATE and YYNSTATE+YYNRULE-1 mean reduce by