/ Check-in [8da0ac9a]
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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:8da0ac9a8bb859377613dd18f4f423eb49c7338b
User & Date: drh 2002-02-23 18:45:13
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: 67a135a0 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: 8da0ac9a 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: 39fed2df user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to tool/lemon.c.

766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
...
844
845
846
847
848
849
850
851
852


853






854
855
856
857
858
859
860
....
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
  /* 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);
      }
    }
  }
................................................................................
      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.
................................................................................
  }
  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;








|







 







|
|
>
>
|
>
>
>
>
>
>







 







|
|





|
|
>





>
>

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

>
>
>
|
>
>
>
>
|

>
|
|
>
>



|




>







766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
...
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
....
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
  /* 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);
      }
    }
  }
................................................................................
      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.
................................................................................
  }
  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;