SQLite

Check-in [4f955c0007]
Login

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

Overview
Comment: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)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 4f955c00076b16166ff837749efb84201eab3c3a
User & Date: drh 2003-10-21 13:16:04.000
Context
2003-10-21
16:34
Fix bugs in lemon associated with the change to a perfect hash table. (CVS 1113) (check-in: c0d1b26966 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: 4f955c0007 user: drh tags: trunk)
2003-10-18
09:37
Add sqlite_progress_handler() API for specifying an progress callback (CVS 1111) (check-in: ddb364635a user: danielk1977 tags: trunk)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to tool/lemon.c.
1
2
3
4
5
6
7
8
9
10
11
12

13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20












+







/*
** This file contains all sources (including headers) to the LEMON
** LALR(1) parser generator.  The sources have been combined into a
** single file to make it easy to include LEMON in the source tree
** and Makefile of another program.
**
** The author of this program disclaims copyright.
*/
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

extern void qsort();
extern double strtod();
extern long strtol();
extern void free();
extern int access();
extern int atoi();
211
212
213
214
215
216
217
218
219
220



221

222
223
224
225
226
227
228
212
213
214
215
216
217
218



219
220
221
222
223
224
225
226
227
228
229
230







-
-
-
+
+
+

+







/* Each state of the generated parser's finite state machine
** is encoded as an instance of the following structure. */
struct state {
  struct config *bp;       /* The basis configurations for this state */
  struct config *cfp;      /* All configurations in this set */
  int index;               /* Sequencial number for this state */
  struct action *ap;       /* Array of actions for this state */
  int naction;             /* Number of actions for this state */
  int tabstart;            /* First index of the action table */
  int tabdfltact;          /* Default action */
  int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
  int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
  int iDflt;               /* Default action */
};
#define NO_OFFSET (-2147483647)

/* A followset propagation link indicates that the contents of one
** configuration followset should be propagated to another whenever
** the first changes. */
struct plink {
  struct config *cfp;      /* The configuration to which linked */
  struct plink *next;      /* The next propagate link */
390
391
392
393
394
395
396


























































































































































397
398
399
400
401
402
403
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
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
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559







+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+







  new->sp = sp;
  if( type==SHIFT ){
    new->x.stp = (struct state *)arg;
  }else{
    new->x.rp = (struct rule *)arg;
  }
}
/********************** New code to implement the "acttab" module ***********/
/*
** This module implements routines use to construct the yy_action[] table.
*/

/*
** The state of the yy_action table under construction is an instance of
** the following structure
*/
typedef struct acttab acttab;
struct acttab {
  int nAction;                 /* Number of used slots in aAction[] */
  int nActionAlloc;            /* Slots allocated for aAction[] */
  struct {
    int lookahead;             /* Value of the lookahead token */
    int action;                /* Action to take on the given lookahead */
  } *aAction,                  /* The yy_action[] table under construction */
    *aLookahead;               /* A single new transaction set */
  int mnLookahead;             /* Minimum aLookahead[].lookahead */
  int mnAction;                /* Action associated with mnLookahead */
  int mxLookahead;             /* Maximum aLookahead[].lookahead */
  int nLookahead;              /* Used slots in aLookahead[] */
  int nLookaheadAlloc;         /* Slots allocated in aLookahead[] */
};

/* Return the number of entries in the yy_action table */
#define acttab_size(X) ((X)->nAction)

/* The value for the N-th entry in yy_action */
#define acttab_yyaction(X,N)  ((X)->aAction[N].action)

/* The value for the N-th entry in yy_lookahead */
#define acttab_yylookahead(X,N)  ((X)->aAction[N].lookahead)

/* Free all memory associated with the given acttab */
void acttab_free(acttab *p){
  free( p->aAction );
  free( p->aLookahead );
  free( p );
}

/* Allocate a new acttab structure */
acttab *acttab_alloc(void){
  acttab *p = malloc( sizeof(*p) );
  if( p==0 ){
    fprintf(stderr,"Unable to allocate memory for a new acttab.");
    exit(1);
  }
  memset(p, 0, sizeof(*p));
  return p;
}

/* Add a new action to the current transaction set
*/
void acttab_action(acttab *p, int lookahead, int action){
  if( p->nLookahead>=p->nLookaheadAlloc ){
    p->nLookaheadAlloc += 25;
    p->aLookahead = realloc( p->aLookahead,
                             sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
    if( p->aLookahead==0 ){
      fprintf(stderr,"malloc failed\n");
      exit(1);
    }
  }
  if( p->nLookahead==0 ){
    p->mxLookahead = lookahead;
    p->mnLookahead = lookahead;
    p->mnAction = action;
  }else{
    if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
    if( p->mnLookahead>lookahead ){
      p->mnLookahead = lookahead;
      p->mnAction = action;
    }
  }
  p->aLookahead[p->nLookahead].lookahead = lookahead;
  p->aLookahead[p->nLookahead].action = action;
  p->nLookahead++;
}

/*
** Add the transaction set built up with prior calls to acttab_action()
** into the current action table.  Then reset the transaction set back
** to an empty set in preparation for a new round of acttab_action() calls.
**
** Return the offset into the action table of the new transaction.
*/
int acttab_insert(acttab *p){
  int i, j, k, n;
  assert( p->nLookahead>0 );

  /* 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
  ** offset is found.  In the worst case, we fall out of the loop when
  ** i reaches p->nAction, which means we append the new transaction set.
  **
  ** i is the index in p->aAction[] where p->mnLookahead is inserted.
  */
  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;
  }
  p->nLookahead = 0;

  /* Return the offset that is added to the lookahead in order to get the
  ** index into yy_action of the action */
  return i - p->mnLookahead;
}

/********************** From the file "assert.c" ****************************/
/*
** A more efficient way of handling assertions.
*/
void myassert(file,line)
char *file;
int line;
1668
1669
1670
1671
1672
1673
1674
1675

1676
1677
1678
1679
1680

1681
1682
1683
1684
1685

1686
1687
1688
1689
1690
1691
1692
1824
1825
1826
1827
1828
1829
1830

1831
1832
1833
1834
1835

1836
1837
1838
1839
1840

1841
1842
1843
1844
1845
1846
1847
1848







-
+




-
+




-
+







      case OPT_FLAG:
      case OPT_FFLAG:
        fprintf(errstream,"  -%-*s  %s\n",max,op[i].label,op[i].message);
        break;
      case OPT_INT:
      case OPT_FINT:
        fprintf(errstream,"  %s=<integer>%*s  %s\n",op[i].label,
          max-strlen(op[i].label)-9,"",op[i].message);
          (int)(max-strlen(op[i].label)-9),"",op[i].message);
        break;
      case OPT_DBL:
      case OPT_FDBL:
        fprintf(errstream,"  %s=<real>%*s  %s\n",op[i].label,
          max-strlen(op[i].label)-6,"",op[i].message);
          (int)(max-strlen(op[i].label)-6),"",op[i].message);
        break;
      case OPT_STR:
      case OPT_FSTR:
        fprintf(errstream,"  %s=<string>%*s  %s\n",op[i].label,
          max-strlen(op[i].label)-8,"",op[i].message);
          (int)(max-strlen(op[i].label)-8),"",op[i].message);
        break;
    }
  }
}
/*********************** From the file "parse.c" ****************************/
/*
** Input file parser for the LEMON parser generator.
2650
2651
2652
2653
2654
2655
2656
2657

2658
2659
2660
2661
2662
2663
2664
2806
2807
2808
2809
2810
2811
2812

2813
2814
2815
2816
2817
2818
2819
2820







-
+







  char buf[1000];
  FILE *in;
  char *tpltname;
  char *cp;

  cp = strrchr(lemp->filename,'.');
  if( cp ){
    sprintf(buf,"%.*s.lt",(unsigned long)cp-(unsigned long)lemp->filename,lemp->filename);
    sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
  }else{
    sprintf(buf,"%s.lt",lemp->filename);
  }
  if( access(buf,004)==0 ){
    tpltname = buf;
  }else if( access(templatename,004)==0 ){
    tpltname = templatename;
2945
2946
2947
2948
2949
2950
2951
2952

2953
2954
2955
2956
2957
2958
2959
2960















2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974

2975

2976
2977


2978
2979
2980
2981
2982
2983
2984
3101
3102
3103
3104
3105
3106
3107

3108
3109







3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139

3140

3141
3142
3143
3144
3145
3146
3147
3148
3149
3150







-
+

-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+














+
-
+
-

+
+







  free(types);
  fprintf(out,"} YYMINORTYPE;\n"); lineno++;
  *plineno = lineno;
}

/*
** Return the name of a C datatype able to represent values between
** 0 and N, inclusive.
** lwr and upr, inclusive.
*/
static const char *minimum_size_type(int N){
  if( N<=255 ){
    return "unsigned char";
  }else if( N<65535 ){
    return "unsigned short int";
  }else{
    return "unsigned int";
static const char *minimum_size_type(int lwr, int upr){
  if( lwr>=0 ){
    if( upr<=255 ){
      return "unsigned char";
    }else if( upr<65535 ){
      return "unsigned short int";
    }else{
      return "unsigned int";
    }
  }else if( lwr>=-127 && upr<=127 ){
    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;
  char line[LINESIZE];
  int  lineno;
  struct state *stp;
  struct action *ap;
  struct rule *rp;
  struct acttab *pActtab;
  int i, j;
  int i, j, n;
  int tablecnt;
  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;
3008
3009
3010
3011
3012
3013
3014
3015

3016
3017
3018

3019
3020
3021
3022
3023
3024
3025
3174
3175
3176
3177
3178
3179
3180

3181
3182
3183

3184
3185
3186
3187
3188
3189
3190
3191







-
+


-
+







    fprintf(out,"#endif\n"); lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the defines */
  fprintf(out,"/* \001 */\n");
  fprintf(out,"#define YYCODETYPE %s\n",
    minimum_size_type(lemp->nsymbol+5)); lineno++;
    minimum_size_type(0, lemp->nsymbol+5)); lineno++;
  fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  fprintf(out,"#define YYACTIONTYPE %s\n",
    minimum_size_type(lemp->nstate+lemp->nrule+5));  lineno++;
    minimum_size_type(0, lemp->nstate+lemp->nrule+5));  lineno++;
  print_stack_union(out,lemp,&lineno,mhflag);
  if( lemp->stacksize ){
    if( atoi(lemp->stacksize)<=0 ){
      ErrorMsg(lemp->filename,0,
"Illegal stack size: [%s].  The stack size should be an integer constant.",
        lemp->stacksize);
      lemp->errorcnt++;
3058
3059
3060
3061
3062
3063
3064
3065

3066
3067
3068


3069
3070
3071
3072
3073






3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084

3085







3086
3087
3088
3089
3090
3091
3092





















3093
3094
3095
3096
3097
3098








3099
3100

3101
3102
3103
3104
3105
3106




3107
3108
3109
3110


3111
3112
3113
3114
3115
3116
3117









3118
3119









3120

3121
3122
3123
3124

3125
3126
3127

3128
3129
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
3165

3166
3167
3168
3169








3170
3171
3172
3173
3174
3175
3176
3224
3225
3226
3227
3228
3229
3230

3231
3232


3233
3234





3235
3236
3237
3238
3239
3240







3241

3242

3243
3244
3245
3246
3247
3248
3249
3250
3251







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

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
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371




3372


3373



3374
3375
3376

3377




3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392







-
+

-
-
+
+
-
-
-
-
-
+
+
+
+
+
+
-
-
-
-
-
-
-

-

-
+

+
+
+
+
+
+
+
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
-
-
+
+
+
+
+
+
+
+
-
-
+
-
-
-
-
-
-
+
+
+
+
-
-
-
-
+
+
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+


+
+
+
+
+
+
+
+
+
-
+
-
-
-
-
+
-
-
-
+
-
-
-
+
+
+
+
+

-
-
-
+
+
+
+
+
+
+
+
+
+
+

+
+
-
-
-
-
+
+
+
+
+
+
-
-
+
+
+
-
-
-
-
+
+
+
+
+
+
+
+

-
-
+
+
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
+
-
-
+
-
-
-
+
+

-
+
-
-
-
-
+
+
+
+
+
+
+
+







  fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index);  lineno++;
  fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum);  lineno++;
  if( lemp->has_fallback ){
    fprintf(out,"#define YYFALLBACK 1\n");  lineno++;
  }
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the action table.
  /* Generate the action table and its associates:
  **
  ** Each entry in the action table is an element of the following 
  ** structure:
  **  yy_action[]        A single table containing all actions.
  **  yy_lookahead[]     A table containing the lookahead for each entry in
  **   struct yyActionEntry {
  **       YYCODETYPE            lookahead;
  **       YYCODETYPE            next;
  **       YYACTIONTYPE          action;
  **   }
  **                     yy_action.  Used to detect hash collisions.
  **  yy_shift_ofst[]    For each state, the offset into yy_action for
  **                     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.
  **
  ** The entries are grouped into hash tables, one hash table for each
  ** parser state.  The hash table has a size which is the number of
  ** entries in that table.  In case of a collision, the "next" value
  ** contains one more than the index into the hash table of the next
  ** entry in the collision chain.  A "next" value of 0 means the end
  ** of the chain has been reached.
  */
  tablecnt = 0;

  /* Loop over parser states */
  /* 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){
      if( compute_action(lemp,ap)>=0 ){
    int tablesize;              /* size of the hash table */
    int j,k;                    /* Loop counter */
    int collide[2048];          /* The collision chain for the table */
    struct action *table[2048]; /* Build the hash table here */

    /* Find the number of actions and initialize the hash table */
    stp = lemp->sorted[i];
        if( ap->sp->index<lemp->nterminal ){
          stp->nTknAct++;
        }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];
    stp->tabstart = tablecnt;
    stp->naction = 0;
    for(ap=stp->ap; ap; ap=ap->next){
      if( ap->sp->index!=lemp->nsymbol && compute_action(lemp,ap)>=0 ){
        stp->naction++;
      }
      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);
        }
    }
    tablesize = stp->naction;
        stp->iTknOfst = acttab_insert(pActtab);
    assert( tablesize<= sizeof(table)/sizeof(table[0]) );
    for(j=0; j<tablesize; j++){
      table[j] = 0;
      collide[j] = -1;
    }

        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) ){
    /* Hash the actions into the hash table */
    stp->tabdfltact = lemp->nstate + lemp->nrule;
    for(ap=stp->ap; ap; ap=ap->next){
      int action = compute_action(lemp,ap);
        for(ap=stp->ap; ap; ap=ap->next){
          int action;
      int h;
      if( ap->sp->index==lemp->nsymbol ){
        stp->tabdfltact = action;
      }else if( action>=0 ){
        h = ap->sp->index % tablesize;
        ap->collide = table[h];
        table[h] = ap;
          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 ){
    /* Resolve collisions */
    for(j=k=0; j<tablesize; j++){
      if( table[j] && table[j]->collide ){
        while( table[k] ) k++;
      fprintf(out, "\n"); lineno++;
        table[k] = table[j]->collide;
        collide[j] = k;
        table[j]->collide = 0;
      j = 0;
        if( k<j ) j = k-1;
      }
    }
    }else{
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;

    /* Print the hash table */
    if( tablesize>0 ){
      fprintf(out,"/* State %d */\n",stp->index); 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++;
    }
  }
  fprintf(out, "};\n"); lineno++;
    for(j=0; j<tablesize; j++){
      assert( table[j]!=0 );
      fprintf(out,"  {%4d,%4d,%4d}, /* %2d: ",
          table[j]->sp->index,

  /* Output the yy_shift_ofst[] table */
  fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
  fprintf(out, "static %s yy_shift_ofst[] = {\n", 
          minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
  n = lemp->nstate;
          collide[j]+1,
          compute_action(lemp,table[j]),
  for(i=j=0; i<n; i++){
    int ofst;
    stp = lemp->sorted[i];
          j+1);
      PrintAction(table[j],out,22);
      fprintf(out," */\n"); 
      lineno++;
    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++;
    }

    /* Update the table count */
  }
  fprintf(out, "};\n"); lineno++;
    tablecnt += tablesize;
  }
  tplt_xfer(lemp->name,in,out,&lineno);
  lemp->tablesize = tablecnt;

  /* Generate the state table

  /* Output the yy_reduce_ofst[] table */
  fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
  fprintf(out, "static %s yy_reduce_ofst[] = {\n", 
          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++;

  **
  ** Each entry is an element of the following structure:
  **    struct yyStateEntry {
  **      struct yyActionEntry *hashtbl;
  /* Output the default action table */
  **      YYCODETYPE nEntry;
  **      YYACTIONTYPE actionDefault;
  fprintf(out, "static YYACTIONTYPE yy_default[] = {\n"); lineno++;
  **    }
  */
  for(i=0; i<lemp->nstate; i++){
  n = lemp->nstate;
  for(i=j=0; i<n; i++){
    stp = lemp->sorted[i];
    fprintf(out,"  { &yyActionTable[%d],%4d,%4d },\n",
    fprintf(out, " %4d,", stp->iDflt);
      stp->tabstart,
      stp->naction,
      stp->tabdfltact); lineno++;
  }
    if( j==9 || i==n-1 ){
      fprintf(out, "\n"); lineno++;
      j = 0;
    }else{
      j++;
    }
  }
  fprintf(out, "};\n"); lineno++;
  tplt_xfer(lemp->name,in,out,&lineno);

  /* Generate the table of fallback tokens.
  */
  if( lemp->has_fallback ){
    for(i=0; i<lemp->nterminal; i++){
      struct symbol *p = lemp->symbols[i];
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3548
3549
3550
3551
3552
3553
3554

3555
3556
3557
3558
3559
3560
3561







-







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){
Changes to tool/lempar.c.
54
55
56
57
58
59
60
61
62
63
64





65
66
67
68
69
70
71






72
73



74
75

76
77
78
79
80
81



82
83
84
85

86
87
88
89

90
91
92
93
94





95
96

97


98
99






100
101
102
103
104
105
106
107
108
109

110
111
112
113
114
115
116
54
55
56
57
58
59
60




61
62
63
64
65
66






67
68
69
70
71
72
73

74
75
76
77

78






79
80
81




82




83



84

85
86
87
88
89
90

91
92
93
94


95
96
97
98
99
100
101







102

103
104
105
106
107
108
109
110







-
-
-
-
+
+
+
+
+

-
-
-
-
-
-
+
+
+
+
+
+

-
+
+
+

-
+
-
-
-
-
-
-
+
+
+
-
-
-
-
+
-
-
-
-
+
-
-
-

-
+
+
+
+
+

-
+

+
+
-
-
+
+
+
+
+
+

-
-
-
-
-
-
-

-
+







**    YYERRORSYMBOL      is the code number of the error symbol.  If not
**                       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 is the action table.  Each entry in this table contains
**
**  +  An integer which is the number representing the look-ahead
**     token

/* 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.  
**
**  +  An integer indicating what action to take.  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
**     rule N-YYNSTATE.  Number YYNSTATE+YYNRULE means that a syntax
**     error has occurred.  Number YYNSTATE+YYNRULE+1 means the parser
**     accepts its input.
** 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
** rule N-YYNSTATE.  Number YYNSTATE+YYNRULE means that a syntax
** error has occurred.  Number YYNSTATE+YYNRULE+1 means the parser
** accepts its input.
**
**  +  A pointer to the next entry with the same hash value.
** The action table is constructed as a single large hash table with
** a perfect hash.  Given state S and lookahead X, the action is computed
** as
**
** The action table is really a series of hash tables.  Each hash
**      yy_action[ yy_shift_ofst[S] + X ]
** table contains a number of entries which is a power of two.  The
** "state" table (which follows) contains information about the starting
** point and size of each hash table.
*/
struct yyActionEntry {
  YYCODETYPE   lookahead;   /* The value of the look-ahead token */
**
** If the index yy_shift_ofst[S]+X is out of range or if the value
** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X or if yy_shift_ofst[S]
  YYCODETYPE   next;        /* Next entry + 1. Zero at end of collision chain */
  YYACTIONTYPE action;      /* Action to take for this look-ahead */
};
typedef struct yyActionEntry yyActionEntry;
** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table
static const yyActionEntry yyActionTable[] = {
%%
};

** and that yy_default[S] should be used instead.  
/* The state table contains information needed to look up the correct
** action in the action table, given the current state of the parser.
** Information needed includes:
**
**  +  A pointer to the start of the action hash table in yyActionTable.
** The formula above is for computing the action when the lookahead is
** a terminal symbol.  If the lookahead is a non-terminal (as occurs after
** a reduce action) then the yy_reduce_ofst[] array is used in place of
** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of
** YY_SHIFT_USE_DFLT.
**
**  +  The number of entries in the action hash table.
** The following are the tables generated in this section:
**
**  yy_action[]        A single table containing all actions.
**  yy_lookahead[]     A table containing the lookahead for each entry in
**  +  The default action.  This is the action to take if no entry for
**     the given look-ahead is found in the action hash table.
**                     yy_action.  Used to detect hash collisions.
**  yy_shift_ofst[]    For each state, the offset into yy_action for
**                     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.
*/
struct yyStateEntry {
  const yyActionEntry *hashtbl;  /* Start of the hash table in yyActionTable */
  YYCODETYPE nEntry;             /* Number of entries in action hash table */
  YYACTIONTYPE actionDefault;    /* Default action if look-ahead not found */
};
typedef struct yyStateEntry yyStateEntry;
static const yyStateEntry yyStateTable[] = {
%%
};
#define YY_SZ_ACTTAB (sizeof(yy_action)/sizeof(yy_action[0]))

/* The next table maps tokens into fallback tokens.  If a construct
** like the following:
** 
**      %fallback ID X Y Z.
**
** appears in the grammer, then ID becomes a fallback token for X, Y,
308
309
310
311
312
313
314
315


316
317
318
319
320
321

322
323

324
325
326
327

328
329
330
331
332
333





334
335
336

337
338
339



340

341
342
343
344
345
346
347
348
349

350
351





352




















353
354




355


356
357
358
359
360
361
362
302
303
304
305
306
307
308

309
310
311
312
313
314
315

316
317

318
319



320
321
322




323
324
325
326
327



328



329
330
331
332
333
334
335
336
337
338
339
340
341

342
343
344
345
346
347
348
349

350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375

376
377
378
379
380
381
382
383
384







-
+
+





-
+

-
+

-
-
-
+


-
-
-
-
+
+
+
+
+
-
-
-
+
-
-
-
+
+
+

+








-
+


+
+
+
+
+
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+


+
+
+
+
-
+
+







  yyParser *pParser = (yyParser*)p;
  if( pParser==0 ) return;
  while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser);
  (*freeProc)((void*)pParser);
}

/*
** Find the appropriate action for a parser given the look-ahead token.
** Find the appropriate action for a parser given the terminal
** look-ahead token iLookAhead.
**
** If the look-ahead token is YYNOCODE, then check to see if the action is
** independent of the look-ahead.  If it is, return the action, otherwise
** return YY_NO_ACTION.
*/
static int yy_find_parser_action(
static int yy_find_shift_action(
  yyParser *pParser,        /* The parser */
  int iLookAhead             /* The look-ahead token */
  int iLookAhead            /* The look-ahead token */
){
  const yyStateEntry *pState;   /* Appropriate entry in the state table */
  const yyActionEntry *pAction; /* Action appropriate for the look-ahead */
  int iFallback;                /* Fallback token */
  int i;
 
  /* if( pParser->yyidx<0 ) return YY_NO_ACTION;  */
  pState = &yyStateTable[pParser->yytop->stateno];
  if( pState->nEntry==0 ){
    return pState->actionDefault;
  }else if( iLookAhead!=YYNOCODE ){
  i = yy_shift_ofst[pParser->yytop->stateno];
  if( i==YY_SHIFT_USE_DFLT ){
    return yy_default[pParser->yytop->stateno];
  }
  if( iLookAhead==YYNOCODE ){
    pAction = &pState->hashtbl[iLookAhead % pState->nEntry];
    while( 1 ){
      if( pAction->lookahead==iLookAhead ) return pAction->action;
    return YY_NO_ACTION;
      if( pAction->next==0 ) break;
      pAction = &pState->hashtbl[pAction->next-1];
    }
  }
  i += iLookAhead;
  if( i<0 || i>=YY_SZ_ACTTAB || yy_lookahead[i]!=iLookAhead ){
#ifdef YYFALLBACK
    int iFallback;            /* Fallback token */
    if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
           && (iFallback = yyFallback[iLookAhead])!=0 ){
#ifndef NDEBUG
      if( yyTraceFILE ){
        fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
           yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
      }
#endif
      return yy_find_parser_action(pParser, iFallback);
      return yy_find_shift_action(pParser, iFallback);
    }
#endif
    return yy_default[pParser->yytop->stateno];
  }else{
    return yy_action[i];
  }
}
  }else if( pState->hashtbl->lookahead!=YYNOCODE ){

/*
** Find the appropriate action for a parser given the non-terminal
** look-ahead token iLookAhead.
**
** If the look-ahead token is YYNOCODE, then check to see if the action is
** independent of the look-ahead.  If it is, return the action, otherwise
** return YY_NO_ACTION.
*/
static int yy_find_reduce_action(
  yyParser *pParser,        /* The parser */
  int iLookAhead            /* The look-ahead token */
){
  int i;
 
  i = yy_reduce_ofst[pParser->yytop->stateno];
  if( i==YY_REDUCE_USE_DFLT ){
    return yy_default[pParser->yytop->stateno];
  }
  if( iLookAhead==YYNOCODE ){
    return YY_NO_ACTION;
  }
  i += iLookAhead;
  if( i<0 || i>=YY_SZ_ACTTAB || yy_lookahead[i]!=iLookAhead ){
    return yy_default[pParser->yytop->stateno];
  }else{
  return pState->actionDefault;
    return yy_action[i];
  }
}

/*
** Perform a shift action.
*/
static void yy_shift(
  yyParser *yypParser,          /* The parser to be shifted */
443
444
445
446
447
448
449
450

451
452
453
454
455
456
457
465
466
467
468
469
470
471

472
473
474
475
476
477
478
479







-
+







  */
%%
  };
  yygoto = yyRuleInfo[yyruleno].lhs;
  yysize = yyRuleInfo[yyruleno].nrhs;
  yypParser->yyidx -= yysize;
  yypParser->yytop -= yysize;
  yyact = yy_find_parser_action(yypParser,yygoto);
  yyact = yy_find_reduce_action(yypParser,yygoto);
  if( yyact < YYNSTATE ){
    yy_shift(yypParser,yyact,yygoto,&yygotominor);
  }else if( yyact == YYNSTATE + YYNRULE + 1 ){
    yy_accept(yypParser);
  }
}

555
556
557
558
559
560
561
562

563
564
565
566
567
568
569
577
578
579
580
581
582
583

584
585
586
587
588
589
590
591







-
+







#ifndef NDEBUG
  if( yyTraceFILE ){
    fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
  }
#endif

  do{
    yyact = yy_find_parser_action(yypParser,yymajor);
    yyact = yy_find_shift_action(yypParser,yymajor);
    if( yyact<YYNSTATE ){
      yy_shift(yypParser,yyact,yymajor,&yyminorunion);
      yypParser->yyerrcnt--;
      if( yyendofinput && yypParser->yyidx>=0 ){
        yymajor = 0;
      }else{
        yymajor = YYNOCODE;
608
609
610
611
612
613
614
615

616
617
618
619
620
621
622
630
631
632
633
634
635
636

637
638
639
640
641
642
643
644







-
+







#endif
        yy_destructor(yymajor,&yyminorunion);
        yymajor = YYNOCODE;
      }else{
         while(
          yypParser->yyidx >= 0 &&
          yypParser->yytop->major != YYERRORSYMBOL &&
          (yyact = yy_find_parser_action(yypParser,YYERRORSYMBOL)) >= YYNSTATE
          (yyact = yy_find_shift_action(yypParser,YYERRORSYMBOL)) >= YYNSTATE
        ){
          yy_pop_parser_stack(yypParser);
        }
        if( yypParser->yyidx < 0 || yymajor==0 ){
          yy_destructor(yymajor,&yyminorunion);
          yy_parse_failed(yypParser);
          yymajor = YYNOCODE;