/ Check-in [a86e782a]
Login

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

Overview
Comment:Lemon enhancement: avoid unnecessary reduce actions that convert one non-terminal into another but have no side effects.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: a86e782ad1aa6f5a8b2c54f9dcf0fa61960843f3
User & Date: drh 2016-05-23 16:15:02
Context
2016-05-23
16:16
Improve the error messages generated by the rtree module when a constraint fails. check-in: 3ad2531e user: dan tags: trunk
16:15
Lemon enhancement: avoid unnecessary reduce actions that convert one non-terminal into another but have no side effects. check-in: a86e782a user: drh tags: trunk
14:24
Fix comment typos and improve clarity of presention in Lemon. The output should be identical. check-in: b91a5b82 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to tool/lemon.c.

   337    337   struct action {
   338    338     struct symbol *sp;       /* The look-ahead symbol */
   339    339     enum e_action type;
   340    340     union {
   341    341       struct state *stp;     /* The new state, if a shift */
   342    342       struct rule *rp;       /* The rule, if a reduce */
   343    343     } x;
          344  +  struct symbol *spOpt;    /* SHIFTREDUCE optimization to this symbol */
   344    345     struct action *next;     /* Next action for this state */
   345    346     struct action *collide;  /* Next action with the same hash */
   346    347   };
   347    348   
   348    349   /* Each state of the generated parser's finite state machine
   349    350   ** is encoded as an instance of the following structure. */
   350    351   struct state {
................................................................................
   528    529   ){
   529    530     struct action *newaction;
   530    531     newaction = Action_new();
   531    532     newaction->next = *app;
   532    533     *app = newaction;
   533    534     newaction->type = type;
   534    535     newaction->sp = sp;
          536  +  newaction->spOpt = 0;
   535    537     if( type==SHIFT ){
   536    538       newaction->x.stp = (struct state *)arg;
   537    539     }else{
   538    540       newaction->x.rp = (struct rule *)arg;
   539    541     }
   540    542   }
   541    543   /********************** New code to implement the "acttab" module ***********/
................................................................................
  3163   3165           result = 0;
  3164   3166         }
  3165   3167         break;
  3166   3168       case NOT_USED:
  3167   3169         result = 0;
  3168   3170         break;
  3169   3171     }
         3172  +  if( result && ap->spOpt ){
         3173  +    fprintf(fp,"  /* because %s==%s */", ap->sp->name, ap->spOpt->name);
         3174  +  }
  3170   3175     return result;
  3171   3176   }
  3172   3177   
  3173   3178   /* Generate the "*.out" log file */
  3174   3179   void ReportOutput(struct lemon *lemp)
  3175   3180   {
  3176   3181     int i;
................................................................................
  4505   4510   ** In this version, we take the most frequent REDUCE action and make
  4506   4511   ** it the default.  Except, there is no default if the wildcard token
  4507   4512   ** is a possible look-ahead.
  4508   4513   */
  4509   4514   void CompressTables(struct lemon *lemp)
  4510   4515   {
  4511   4516     struct state *stp;
  4512         -  struct action *ap, *ap2;
         4517  +  struct action *ap, *ap2, *nextap;
  4513   4518     struct rule *rp, *rp2, *rbest;
  4514   4519     int nbest, n;
  4515   4520     int i;
  4516   4521     int usesWildcard;
  4517   4522   
  4518   4523     for(i=0; i<lemp->nstate; i++){
  4519   4524       stp = lemp->sorted[i];
................................................................................
  4582   4587         pNextState = ap->x.stp;
  4583   4588         if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){
  4584   4589           ap->type = SHIFTREDUCE;
  4585   4590           ap->x.rp = pNextState->pDfltReduce;
  4586   4591         }
  4587   4592       }
  4588   4593     }
         4594  +
         4595  +  /* If a SHIFTREDUCE action specifies a rule that has a single RHS term
         4596  +  ** (meaning that the SHIFTREDUCE will land back in the state where it
         4597  +  ** started) and if there is no C-code associated with the reduce action,
         4598  +  ** then we can go ahead and convert the action to be the same as the
         4599  +  ** action for the RHS of the rule.
         4600  +  */
         4601  +  for(i=0; i<lemp->nstate; i++){
         4602  +    stp = lemp->sorted[i];
         4603  +    for(ap=stp->ap; ap; ap=nextap){
         4604  +      nextap = ap->next;
         4605  +      if( ap->type!=SHIFTREDUCE ) continue;
         4606  +      rp = ap->x.rp;
         4607  +      if( rp->noCode==0 ) continue;
         4608  +      if( rp->nrhs!=1 ) continue;
         4609  +#if 1
         4610  +      /* Only apply this optimization to non-terminals.  It would be OK to
         4611  +      ** apply it to terminal symbols too, but that makes the parser tables
         4612  +      ** larger. */
         4613  +      if( ap->sp->index<lemp->nterminal ) continue;
         4614  +#endif
         4615  +      /* If we reach this point, it means the optimization can be applied */
         4616  +      nextap = ap;
         4617  +      for(ap2=stp->ap; ap2 && (ap2==ap || ap2->sp!=rp->lhs); ap2=ap2->next){}
         4618  +      assert( ap2!=0 );
         4619  +      ap->spOpt = ap2->sp;
         4620  +      ap->type = ap2->type;
         4621  +      ap->x = ap2->x;
         4622  +    }
         4623  +  }
  4589   4624   }
  4590   4625   
  4591   4626   
  4592   4627   /*
  4593   4628   ** Compare two states for sorting purposes.  The smaller state is the
  4594   4629   ** one with the most non-terminal actions.  If they have the same number
  4595   4630   ** of non-terminal actions, then the smaller is the one with the most