/ Check-in [b6ffb7e4]
Login

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

Overview
Comment:In the "parse.out" output file from Lemon, show addition the complete text of rules on reduce actions.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b6ffb7e471e51ff69668154ad2c8790e466c9d37
User & Date: drh 2015-09-07 14:22:24
Context
2015-09-07
20:11
Enhance the Lemon parser generator to add SHIFTREDUCE states that reduce the sizes of some of the parser tables. check-in: 99b992fa user: drh tags: trunk
18:23
For the Lemon-generated parser, add a new action type SHIFTREDUCE and use it to further compress the parser tables and improve parser performance. check-in: 531c3974 user: drh tags: lemon-update
14:22
In the "parse.out" output file from Lemon, show addition the complete text of rules on reduce actions. check-in: b6ffb7e4 user: drh tags: trunk
02:23
Improved "Parser Statistics" output (the -s option) for the Lemon parser generator. check-in: 809503e4 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to main.mk.

   578    578   # Rules to build parse.c and parse.h - the outputs of lemon.
   579    579   #
   580    580   parse.h:	parse.c
   581    581   
   582    582   parse.c:	$(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk
   583    583   	cp $(TOP)/src/parse.y .
   584    584   	rm -f parse.h
   585         -	./lemon $(OPTS) parse.y
          585  +	./lemon -s $(OPTS) parse.y
   586    586   	mv parse.h parse.h.temp
   587    587   	$(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h
   588    588   
   589    589   sqlite3.h:	$(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION $(TOP)/ext/rtree/sqlite3rtree.h
   590    590   	tclsh $(TOP)/tool/mksqlite3h.tcl $(TOP) >sqlite3.h
   591    591   
   592    592   keywordhash.h:	$(TOP)/tool/mkkeywordhash.c

Changes to tool/lemon.c.

   336    336   struct state {
   337    337     struct config *bp;       /* The basis configurations for this state */
   338    338     struct config *cfp;      /* All configurations in this set */
   339    339     int statenum;            /* Sequential number for this state */
   340    340     struct action *ap;       /* Array of actions for this state */
   341    341     int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
   342    342     int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
   343         -  int iDflt;               /* Default action */
          343  +  int iDflt;               /* Default action is reduce by this rule */
   344    344   };
   345    345   #define NO_OFFSET (-2147483647)
   346    346   
   347    347   /* A followset propagation link indicates that the contents of one
   348    348   ** configuration followset should be propagated to another whenever
   349    349   ** the first changes. */
   350    350   struct plink {
................................................................................
  2956   2956       printf(".");
  2957   2957       if( rp->precsym ) printf(" [%s]",rp->precsym->name);
  2958   2958       /* if( rp->code ) printf("\n    %s",rp->code); */
  2959   2959       printf("\n");
  2960   2960     }
  2961   2961   }
  2962   2962   
  2963         -void ConfigPrint(FILE *fp, struct config *cfp)
  2964         -{
  2965         -  struct rule *rp;
         2963  +/* Print a single rule.
         2964  +*/
         2965  +void RulePrint(FILE *fp, struct rule *rp, int iCursor){
  2966   2966     struct symbol *sp;
  2967   2967     int i, j;
  2968         -  rp = cfp->rp;
  2969   2968     fprintf(fp,"%s ::=",rp->lhs->name);
  2970   2969     for(i=0; i<=rp->nrhs; i++){
  2971         -    if( i==cfp->dot ) fprintf(fp," *");
         2970  +    if( i==iCursor ) fprintf(fp," *");
  2972   2971       if( i==rp->nrhs ) break;
  2973   2972       sp = rp->rhs[i];
  2974   2973       if( sp->type==MULTITERMINAL ){
  2975   2974         fprintf(fp," %s", sp->subsym[0]->name);
  2976   2975         for(j=1; j<sp->nsubsym; j++){
  2977   2976           fprintf(fp,"|%s",sp->subsym[j]->name);
  2978   2977         }
  2979   2978       }else{
  2980   2979         fprintf(fp," %s", sp->name);
  2981   2980       }
  2982   2981     }
  2983   2982   }
         2983  +
         2984  +/* Print the rule for a configuration.
         2985  +*/
         2986  +void ConfigPrint(FILE *fp, struct config *cfp){
         2987  +  RulePrint(fp, cfp->rp, cfp->dot);
         2988  +}
  2984   2989   
  2985   2990   /* #define TEST */
  2986   2991   #if 0
  2987   2992   /* Print a set */
  2988   2993   PRIVATE void SetPrint(out,set,lemp)
  2989   2994   FILE *out;
  2990   2995   char *set;
................................................................................
  3017   3022     }
  3018   3023   }
  3019   3024   #endif
  3020   3025   
  3021   3026   /* Print an action to the given file descriptor.  Return FALSE if
  3022   3027   ** nothing was actually printed.
  3023   3028   */
  3024         -int PrintAction(struct action *ap, FILE *fp, int indent){
         3029  +int PrintAction(
         3030  +  struct action *ap,          /* The action to print */
         3031  +  FILE *fp,                   /* Print the action here */
         3032  +  int indent,                 /* Indent by this amount */
         3033  +  struct rule **apRule        /* All rules by index */
         3034  +){
  3025   3035     int result = 1;
  3026   3036     switch( ap->type ){
  3027         -    case SHIFT:
  3028         -      fprintf(fp,"%*s shift  %d",indent,ap->sp->name,ap->x.stp->statenum);
         3037  +    case SHIFT: {
         3038  +      struct state *stp = ap->x.stp;
         3039  +      fprintf(fp,"%*s shift  %-7d",indent,ap->sp->name,stp->statenum);
         3040  +      if( stp->nTknAct==0 && stp->nNtAct==0 && apRule ){
         3041  +        fprintf(fp,"then reduce %d: ", stp->iDflt);
         3042  +        RulePrint(fp, apRule[stp->iDflt], -1);
         3043  +      }
  3029   3044         break;
  3030         -    case REDUCE:
  3031         -      fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
         3045  +    }
         3046  +    case REDUCE: {
         3047  +      struct rule *rp = ap->x.rp;
         3048  +      fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index);
         3049  +      if( apRule ) RulePrint(fp, apRule[rp->index], -1);
  3032   3050         break;
         3051  +    }
  3033   3052       case ACCEPT:
  3034   3053         fprintf(fp,"%*s accept",indent,ap->sp->name);
  3035   3054         break;
  3036   3055       case ERROR:
  3037   3056         fprintf(fp,"%*s error",indent,ap->sp->name);
  3038   3057         break;
  3039   3058       case SRCONFLICT:
  3040   3059       case RRCONFLICT:
  3041         -      fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
         3060  +      fprintf(fp,"%*s reduce %-7d ** Parsing conflict **",
  3042   3061           indent,ap->sp->name,ap->x.rp->index);
  3043   3062         break;
  3044   3063       case SSCONFLICT:
  3045         -      fprintf(fp,"%*s shift  %-3d ** Parsing conflict **", 
         3064  +      fprintf(fp,"%*s shift  %-7d ** Parsing conflict **", 
  3046   3065           indent,ap->sp->name,ap->x.stp->statenum);
  3047   3066         break;
  3048   3067       case SH_RESOLVED:
  3049   3068         if( showPrecedenceConflict ){
  3050         -        fprintf(fp,"%*s shift  %-3d -- dropped by precedence",
         3069  +        fprintf(fp,"%*s shift  %-7d -- dropped by precedence",
  3051   3070                   indent,ap->sp->name,ap->x.stp->statenum);
  3052   3071         }else{
  3053   3072           result = 0;
  3054   3073         }
  3055   3074         break;
  3056   3075       case RD_RESOLVED:
  3057   3076         if( showPrecedenceConflict ){
  3058         -        fprintf(fp,"%*s reduce %-3d -- dropped by precedence",
         3077  +        fprintf(fp,"%*s reduce %-7d -- dropped by precedence",
  3059   3078                   indent,ap->sp->name,ap->x.rp->index);
  3060   3079         }else{
  3061   3080           result = 0;
  3062   3081         }
  3063   3082         break;
  3064   3083       case NOT_USED:
  3065   3084         result = 0;
................................................................................
  3072   3091   void ReportOutput(struct lemon *lemp)
  3073   3092   {
  3074   3093     int i;
  3075   3094     struct state *stp;
  3076   3095     struct config *cfp;
  3077   3096     struct action *ap;
  3078   3097     FILE *fp;
         3098  +  struct rule **apRule;
  3079   3099   
         3100  +  apRule = malloc( sizeof(apRule[0])*(lemp->nrule+1) );
         3101  +  if( apRule ){
         3102  +    struct rule *x;
         3103  +    memset(apRule, 0, sizeof(apRule[0])*(lemp->nrule+1) );
         3104  +    for(x=lemp->rule; x; x=x->next){
         3105  +      assert( x->index>=0 && x->index<(lemp->nrule+1) );
         3106  +      apRule[x->index] = x;
         3107  +    }
         3108  +  }
  3080   3109     fp = file_open(lemp,".out","wb");
  3081   3110     if( fp==0 ) return;
  3082   3111     for(i=0; i<lemp->nstate; i++){
  3083   3112       stp = lemp->sorted[i];
  3084   3113       fprintf(fp,"State %d:\n",stp->statenum);
  3085   3114       if( lemp->basisflag ) cfp=stp->bp;
  3086   3115       else                  cfp=stp->cfp;
................................................................................
  3100   3129         PlinkPrint(fp,cfp->bplp,"From");
  3101   3130   #endif
  3102   3131         if( lemp->basisflag ) cfp=cfp->bp;
  3103   3132         else                  cfp=cfp->next;
  3104   3133       }
  3105   3134       fprintf(fp,"\n");
  3106   3135       for(ap=stp->ap; ap; ap=ap->next){
  3107         -      if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
         3136  +      if( PrintAction(ap,fp,30,apRule) ) fprintf(fp,"\n");
  3108   3137       }
  3109   3138       fprintf(fp,"\n");
  3110   3139     }
  3111   3140     fprintf(fp, "----------------------------------------------------\n");
  3112   3141     fprintf(fp, "Symbols:\n");
  3113   3142     for(i=0; i<lemp->nsymbol; i++){
  3114   3143       int j;
................................................................................
  3126   3155             fprintf(fp, " %s", lemp->symbols[j]->name);
  3127   3156           }
  3128   3157         }
  3129   3158       }
  3130   3159       fprintf(fp, "\n");
  3131   3160     }
  3132   3161     fclose(fp);
         3162  +  free(apRule);
  3133   3163     return;
  3134   3164   }
  3135   3165   
  3136   3166   /* Search for the file "name" which is in the same directory as
  3137   3167   ** the exacutable */
  3138   3168   PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
  3139   3169   {
................................................................................
  4017   4047     /* Output the default action table */
  4018   4048     fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
  4019   4049     n = lemp->nstate;
  4020   4050     lemp->tablesize += n*szActionType;
  4021   4051     for(i=j=0; i<n; i++){
  4022   4052       stp = lemp->sorted[i];
  4023   4053       if( j==0 ) fprintf(out," /* %5d */ ", i);
  4024         -    fprintf(out, " %4d,", stp->iDflt);
         4054  +    fprintf(out, " %4d,", stp->iDflt+n);
  4025   4055       if( j==9 || i==n-1 ){
  4026   4056         fprintf(out, "\n"); lineno++;
  4027   4057         j = 0;
  4028   4058       }else{
  4029   4059         j++;
  4030   4060       }
  4031   4061     }
................................................................................
  4338   4368     int i;
  4339   4369     struct state *stp;
  4340   4370     struct action *ap;
  4341   4371   
  4342   4372     for(i=0; i<lemp->nstate; i++){
  4343   4373       stp = lemp->sorted[i];
  4344   4374       stp->nTknAct = stp->nNtAct = 0;
  4345         -    stp->iDflt = lemp->nstate + lemp->nrule;
         4375  +    stp->iDflt = lemp->nrule;
  4346   4376       stp->iTknOfst = NO_OFFSET;
  4347   4377       stp->iNtOfst = NO_OFFSET;
  4348   4378       for(ap=stp->ap; ap; ap=ap->next){
  4349   4379         if( compute_action(lemp,ap)>=0 ){
  4350   4380           if( ap->sp->index<lemp->nterminal ){
  4351   4381             stp->nTknAct++;
  4352   4382           }else if( ap->sp->index<lemp->nsymbol ){
  4353   4383             stp->nNtAct++;
  4354   4384           }else{
  4355         -          stp->iDflt = compute_action(lemp, ap);
         4385  +          stp->iDflt = compute_action(lemp, ap) - lemp->nstate;
  4356   4386           }
  4357   4387         }
  4358   4388       }
  4359   4389     }
  4360   4390     qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
  4361   4391           stateResortCompare);
  4362   4392     for(i=0; i<lemp->nstate; i++){