SQLite

Check-in [8da0ac9a8b]
Login

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

Overview
Comment:Bug fix in lemon: 3-way conflicts (SHIFT/REDUCE/REDUCE) were not detected or resolved. This is now fixed. Also, table compression works a little better. (CVS 388)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 8da0ac9a8bb859377613dd18f4f423eb49c7338b
User & Date: drh 2002-02-23 18:45:13.000
Context
2002-02-23
19:39
Modify lemon to use much less memory for its parser tables. This reduces the size of the library by 50K, which is important for an embedded library. (CVS 389) (check-in: 67a135a051 user: drh tags: trunk)
18:45
Bug fix in lemon: 3-way conflicts (SHIFT/REDUCE/REDUCE) were not detected or resolved. This is now fixed. Also, table compression works a little better. (CVS 388) (check-in: 8da0ac9a8b user: drh tags: trunk)
02:32
Code to implement CREATE VIEW is in place. A quick smoke test shows that it works, but there are probably still many bugs. (CVS 387) (check-in: 39fed2df11 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to tool/lemon.c.
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
  /* Resolve conflicts */
  for(i=0; i<lemp->nstate; i++){
    struct action *ap, *nap;
    struct state *stp;
    stp = lemp->sorted[i];
    assert( stp->ap );
    stp->ap = Action_sort(stp->ap);
    for(ap=stp->ap; ap && ap->next; ap=nap){
      for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
         /* The two actions "ap" and "nap" have the same lookahead.
         ** Figure out which one should be used */
         lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
      }
    }
  }







|







766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
  /* Resolve conflicts */
  for(i=0; i<lemp->nstate; i++){
    struct action *ap, *nap;
    struct state *stp;
    stp = lemp->sorted[i];
    assert( stp->ap );
    stp->ap = Action_sort(stp->ap);
    for(ap=stp->ap; ap && ap->next; ap=ap->next){
      for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
         /* The two actions "ap" and "nap" have the same lookahead.
         ** Figure out which one should be used */
         lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
      }
    }
  }
844
845
846
847
848
849
850
851

852

853






854
855
856
857
858
859
860
      errcnt++;
    }else if( spx->prec>spy->prec ){
      apy->type = RD_RESOLVED;
    }else if( spx->prec<spy->prec ){
      apx->type = RD_RESOLVED;
    }
  }else{
    /* Can't happen.  Shifts have to come before Reduces on the

    ** list because the reduces were added last.  Hence, if apx->type==REDUCE

    ** then it is impossible for apy->type==SHIFT */






  }
  return errcnt;
}
/********************* From the file "configlist.c" *************************/
/*
** Routines to processing a configuration list and building a state
** in the LEMON parser generator.







|
>
|
>
|
>
>
>
>
>
>







844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
      errcnt++;
    }else if( spx->prec>spy->prec ){
      apy->type = RD_RESOLVED;
    }else if( spx->prec<spy->prec ){
      apx->type = RD_RESOLVED;
    }
  }else{
    assert( 
      apx->type==SH_RESOLVED ||
      apx->type==RD_RESOLVED ||
      apx->type==CONFLICT ||
      apy->type==SH_RESOLVED ||
      apy->type==RD_RESOLVED ||
      apy->type==CONFLICT
    );
    /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
    ** REDUCEs on the list.  If we reach this point it must be because
    ** the parser conflict had already been resolved. */
  }
  return errcnt;
}
/********************* From the file "configlist.c" *************************/
/*
** Routines to processing a configuration list and building a state
** in the LEMON parser generator.
3252
3253
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
  }
  return;
}

/* Reduce the size of the action tables, if possible, by making use
** of defaults.
**
** In this version, if all REDUCE actions use the same rule, make
** them the default.  Only default them if there are more than one.
*/
void CompressTables(lemp)
struct lemon *lemp;
{
  struct state *stp;
  struct action *ap;
  struct rule *rp;

  int i;
  int cnt;

  for(i=0; i<lemp->nstate; i++){
    stp = lemp->sorted[i];



    /* Find the first REDUCE action */
    for(ap=stp->ap; ap && ap->type!=REDUCE; ap=ap->next);
    if( ap==0 ) continue;

    /* Remember the rule used */
    rp = ap->x.rp;

    /* See if all other REDUCE acitons use the same rule */
    cnt = 1;
    for(ap=ap->next; ap; ap=ap->next){
      if( ap->type==REDUCE ){
        if( ap->x.rp!=rp ) break;

        cnt++;
      }



    }




    if( ap || cnt==1 ) continue;


    /* Combine all REDUCE actions into a single default */
    for(ap=stp->ap; ap && ap->type!=REDUCE; ap=ap->next);


    assert( ap );
    ap->sp = Symbol_new("{default}");
    for(ap=ap->next; ap; ap=ap->next){
      if( ap->type==REDUCE ) ap->type = NOT_USED;
    }
    stp->ap = Action_sort(stp->ap);
  }
}

/***************** From the file "set.c" ************************************/
/*
** Set manipulation routines for the LEMON parser generator.
*/

static int size = 0;








|
|





|
|
>





>
>

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

>
>
>
|
>
>
>
>
|

>
|
|
>
>



|




>







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
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
  }
  return;
}

/* Reduce the size of the action tables, if possible, by making use
** of defaults.
**
** In this version, we take the most frequent REDUCE action and make
** it the default.  Only default a reduce if there are more than one.
*/
void CompressTables(lemp)
struct lemon *lemp;
{
  struct state *stp;
  struct action *ap, *ap2;
  struct rule *rp, *rp2, *rbest;
  int nbest, n;
  int i;
  int cnt;

  for(i=0; i<lemp->nstate; i++){
    stp = lemp->sorted[i];
    nbest = 0;
    rbest = 0;


    for(ap=stp->ap; ap; ap=ap->next){
      if( ap->type!=REDUCE ) continue;


      rp = ap->x.rp;
      if( rp==rbest ) continue;

      n = 1;
      for(ap2=ap->next; ap2; ap2=ap2->next){
        if( ap2->type!=REDUCE ) continue;
        rp2 = ap2->x.rp;
        if( rp2==rbest ) continue;
        if( rp2==rp ) n++;
      }
      if( n>nbest ){
        nbest = n;
        rbest = rp;
      }
    }
 
    /* Do not make a default if the number of rules to default
    ** is not at least 2 */
    if( nbest<2 ) continue;


    /* Combine matching REDUCE actions into a single default */
    for(ap=stp->ap; ap; ap=ap->next){
      if( ap->type==REDUCE && ap->x.rp==rbest ) break;
    }
    assert( ap );
    ap->sp = Symbol_new("{default}");
    for(ap=ap->next; ap; ap=ap->next){
      if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
    }
    stp->ap = Action_sort(stp->ap);
  }
}

/***************** From the file "set.c" ************************************/
/*
** Set manipulation routines for the LEMON parser generator.
*/

static int size = 0;