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 | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: | 4f955c00076b16166ff837749efb8420 |
| User & Date: | drh 2003-10-21 13:16:04 |
Context
|
2003-10-21
| ||
| 16:34 | Fix bugs in lemon associated with the change to a perfect hash table. (CVS 1113) check-in: c0d1b269 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: 4f955c00 user: drh tags: trunk | |
|
2003-10-18
| ||
| 09:37 | Add sqlite_progress_handler() API for specifying an progress callback (CVS 1111) check-in: ddb36463 user: danielk1977 tags: trunk | |
Changes
Changes to tool/lemon.c.
6 6 ** 7 7 ** The author of this program disclaims copyright. 8 8 */ 9 9 #include <stdio.h> 10 10 #include <stdarg.h> 11 11 #include <string.h> 12 12 #include <ctype.h> 13 +#include <stdlib.h> 13 14 14 15 extern void qsort(); 15 16 extern double strtod(); 16 17 extern long strtol(); 17 18 extern void free(); 18 19 extern int access(); 19 20 extern int atoi(); ................................................................................ 211 212 /* Each state of the generated parser's finite state machine 212 213 ** is encoded as an instance of the following structure. */ 213 214 struct state { 214 215 struct config *bp; /* The basis configurations for this state */ 215 216 struct config *cfp; /* All configurations in this set */ 216 217 int index; /* Sequencial number for this state */ 217 218 struct action *ap; /* Array of actions for this state */ 218 - int naction; /* Number of actions for this state */ 219 - int tabstart; /* First index of the action table */ 220 - int tabdfltact; /* Default action */ 219 + int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */ 220 + int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */ 221 + int iDflt; /* Default action */ 221 222 }; 223 +#define NO_OFFSET (-2147483647) 222 224 223 225 /* A followset propagation link indicates that the contents of one 224 226 ** configuration followset should be propagated to another whenever 225 227 ** the first changes. */ 226 228 struct plink { 227 229 struct config *cfp; /* The configuration to which linked */ 228 230 struct plink *next; /* The next propagate link */ ................................................................................ 390 392 new->sp = sp; 391 393 if( type==SHIFT ){ 392 394 new->x.stp = (struct state *)arg; 393 395 }else{ 394 396 new->x.rp = (struct rule *)arg; 395 397 } 396 398 } 399 +/********************** New code to implement the "acttab" module ***********/ 400 +/* 401 +** This module implements routines use to construct the yy_action[] table. 402 +*/ 403 + 404 +/* 405 +** The state of the yy_action table under construction is an instance of 406 +** the following structure 407 +*/ 408 +typedef struct acttab acttab; 409 +struct acttab { 410 + int nAction; /* Number of used slots in aAction[] */ 411 + int nActionAlloc; /* Slots allocated for aAction[] */ 412 + struct { 413 + int lookahead; /* Value of the lookahead token */ 414 + int action; /* Action to take on the given lookahead */ 415 + } *aAction, /* The yy_action[] table under construction */ 416 + *aLookahead; /* A single new transaction set */ 417 + int mnLookahead; /* Minimum aLookahead[].lookahead */ 418 + int mnAction; /* Action associated with mnLookahead */ 419 + int mxLookahead; /* Maximum aLookahead[].lookahead */ 420 + int nLookahead; /* Used slots in aLookahead[] */ 421 + int nLookaheadAlloc; /* Slots allocated in aLookahead[] */ 422 +}; 423 + 424 +/* Return the number of entries in the yy_action table */ 425 +#define acttab_size(X) ((X)->nAction) 426 + 427 +/* The value for the N-th entry in yy_action */ 428 +#define acttab_yyaction(X,N) ((X)->aAction[N].action) 429 + 430 +/* The value for the N-th entry in yy_lookahead */ 431 +#define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead) 432 + 433 +/* Free all memory associated with the given acttab */ 434 +void acttab_free(acttab *p){ 435 + free( p->aAction ); 436 + free( p->aLookahead ); 437 + free( p ); 438 +} 439 + 440 +/* Allocate a new acttab structure */ 441 +acttab *acttab_alloc(void){ 442 + acttab *p = malloc( sizeof(*p) ); 443 + if( p==0 ){ 444 + fprintf(stderr,"Unable to allocate memory for a new acttab."); 445 + exit(1); 446 + } 447 + memset(p, 0, sizeof(*p)); 448 + return p; 449 +} 450 + 451 +/* Add a new action to the current transaction set 452 +*/ 453 +void acttab_action(acttab *p, int lookahead, int action){ 454 + if( p->nLookahead>=p->nLookaheadAlloc ){ 455 + p->nLookaheadAlloc += 25; 456 + p->aLookahead = realloc( p->aLookahead, 457 + sizeof(p->aLookahead[0])*p->nLookaheadAlloc ); 458 + if( p->aLookahead==0 ){ 459 + fprintf(stderr,"malloc failed\n"); 460 + exit(1); 461 + } 462 + } 463 + if( p->nLookahead==0 ){ 464 + p->mxLookahead = lookahead; 465 + p->mnLookahead = lookahead; 466 + p->mnAction = action; 467 + }else{ 468 + if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead; 469 + if( p->mnLookahead>lookahead ){ 470 + p->mnLookahead = lookahead; 471 + p->mnAction = action; 472 + } 473 + } 474 + p->aLookahead[p->nLookahead].lookahead = lookahead; 475 + p->aLookahead[p->nLookahead].action = action; 476 + p->nLookahead++; 477 +} 478 + 479 +/* 480 +** Add the transaction set built up with prior calls to acttab_action() 481 +** into the current action table. Then reset the transaction set back 482 +** to an empty set in preparation for a new round of acttab_action() calls. 483 +** 484 +** Return the offset into the action table of the new transaction. 485 +*/ 486 +int acttab_insert(acttab *p){ 487 + int i, j, k, n; 488 + assert( p->nLookahead>0 ); 489 + 490 + /* Make sure we have enough space to hold the expanded action table 491 + ** in the worst case. The worst case occurs if the transaction set 492 + ** must be appended to the current action table 493 + */ 494 + n = p->mxLookahead - p->mnLookahead + 1; 495 + if( p->nAction + n >= p->nActionAlloc ){ 496 + p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20; 497 + p->aAction = realloc( p->aAction, 498 + sizeof(p->aAction[0])*p->nActionAlloc); 499 + if( p->aAction==0 ){ 500 + fprintf(stderr,"malloc failed\n"); 501 + exit(1); 502 + } 503 + for(i=p->nAction; i<p->nActionAlloc; i++){ 504 + p->aAction[i].lookahead = -1; 505 + p->aAction[i].action = -1; 506 + } 507 + } 508 + 509 + /* Scan the existing action table looking for an offset where we can 510 + ** insert the current transaction set. Fall out of the loop when that 511 + ** offset is found. In the worst case, we fall out of the loop when 512 + ** i reaches p->nAction, which means we append the new transaction set. 513 + ** 514 + ** i is the index in p->aAction[] where p->mnLookahead is inserted. 515 + */ 516 + for(i=0; i<p->nAction; i++){ 517 + if( p->aAction[i].lookahead<0 ){ 518 + for(j=0; j<p->nLookahead; j++){ 519 + k = p->aLookahead[j].lookahead - p->mnLookahead + i; 520 + if( k<0 ) break; 521 + if( p->aAction[k].lookahead>=0 ) break; 522 + } 523 + if( j==p->nLookahead ) break; /* Fits in empty slots */ 524 + }else if( p->aAction[i].lookahead==p->mnLookahead ){ 525 + if( p->aAction[i].action!=p->mnAction ) continue; 526 + for(j=0; j<p->nLookahead; j++){ 527 + k = p->aLookahead[j].lookahead - p->mnLookahead + i; 528 + if( k<0 || k>=p->nAction ) break; 529 + if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break; 530 + if( p->aLookahead[j].action!=p->aAction[k].action ) break; 531 + } 532 + if( j<p->nLookahead ) continue; 533 + n = 0; 534 + for(j=0; j<p->nAction; j++){ 535 + if( p->aAction[j].lookahead==j+i-p->mnLookahead ) n++; 536 + } 537 + if( n==p->nLookahead ) break; /* Same as a prior transaction set */ 538 + } 539 + } 540 + /* Insert transaction set at index i. */ 541 + for(j=0; j<p->nLookahead; j++){ 542 + k = p->aLookahead[j].lookahead - p->mnLookahead + i; 543 + p->aAction[k] = p->aLookahead[j]; 544 + if( k>=p->nAction ) p->nAction = k+1; 545 + } 546 + p->nLookahead = 0; 547 + 548 + /* Return the offset that is added to the lookahead in order to get the 549 + ** index into yy_action of the action */ 550 + return i - p->mnLookahead; 551 +} 552 + 397 553 /********************** From the file "assert.c" ****************************/ 398 554 /* 399 555 ** A more efficient way of handling assertions. 400 556 */ 401 557 void myassert(file,line) 402 558 char *file; 403 559 int line; ................................................................................ 1668 1824 case OPT_FLAG: 1669 1825 case OPT_FFLAG: 1670 1826 fprintf(errstream," -%-*s %s\n",max,op[i].label,op[i].message); 1671 1827 break; 1672 1828 case OPT_INT: 1673 1829 case OPT_FINT: 1674 1830 fprintf(errstream," %s=<integer>%*s %s\n",op[i].label, 1675 - max-strlen(op[i].label)-9,"",op[i].message); 1831 + (int)(max-strlen(op[i].label)-9),"",op[i].message); 1676 1832 break; 1677 1833 case OPT_DBL: 1678 1834 case OPT_FDBL: 1679 1835 fprintf(errstream," %s=<real>%*s %s\n",op[i].label, 1680 - max-strlen(op[i].label)-6,"",op[i].message); 1836 + (int)(max-strlen(op[i].label)-6),"",op[i].message); 1681 1837 break; 1682 1838 case OPT_STR: 1683 1839 case OPT_FSTR: 1684 1840 fprintf(errstream," %s=<string>%*s %s\n",op[i].label, 1685 - max-strlen(op[i].label)-8,"",op[i].message); 1841 + (int)(max-strlen(op[i].label)-8),"",op[i].message); 1686 1842 break; 1687 1843 } 1688 1844 } 1689 1845 } 1690 1846 /*********************** From the file "parse.c" ****************************/ 1691 1847 /* 1692 1848 ** Input file parser for the LEMON parser generator. ................................................................................ 2650 2806 char buf[1000]; 2651 2807 FILE *in; 2652 2808 char *tpltname; 2653 2809 char *cp; 2654 2810 2655 2811 cp = strrchr(lemp->filename,'.'); 2656 2812 if( cp ){ 2657 - sprintf(buf,"%.*s.lt",(unsigned long)cp-(unsigned long)lemp->filename,lemp->filename); 2813 + sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename); 2658 2814 }else{ 2659 2815 sprintf(buf,"%s.lt",lemp->filename); 2660 2816 } 2661 2817 if( access(buf,004)==0 ){ 2662 2818 tpltname = buf; 2663 2819 }else if( access(templatename,004)==0 ){ 2664 2820 tpltname = templatename; ................................................................................ 2945 3101 free(types); 2946 3102 fprintf(out,"} YYMINORTYPE;\n"); lineno++; 2947 3103 *plineno = lineno; 2948 3104 } 2949 3105 2950 3106 /* 2951 3107 ** Return the name of a C datatype able to represent values between 2952 -** 0 and N, inclusive. 3108 +** lwr and upr, inclusive. 2953 3109 */ 2954 -static const char *minimum_size_type(int N){ 2955 - if( N<=255 ){ 2956 - return "unsigned char"; 2957 - }else if( N<65535 ){ 2958 - return "unsigned short int"; 3110 +static const char *minimum_size_type(int lwr, int upr){ 3111 + if( lwr>=0 ){ 3112 + if( upr<=255 ){ 3113 + return "unsigned char"; 3114 + }else if( upr<65535 ){ 3115 + return "unsigned short int"; 3116 + }else{ 3117 + return "unsigned int"; 3118 + } 3119 + }else if( lwr>=-127 && upr<=127 ){ 3120 + return "signed char"; 3121 + }else if( lwr>=-32767 && upr<32767 ){ 3122 + return "short"; 2959 3123 }else{ 2960 - return "unsigned int"; 3124 + return "int"; 2961 3125 } 2962 3126 } 2963 3127 2964 3128 /* Generate C source code for the parser */ 2965 3129 void ReportTable(lemp, mhflag) 2966 3130 struct lemon *lemp; 2967 3131 int mhflag; /* Output in makeheaders format if true */ ................................................................................ 2968 3132 { 2969 3133 FILE *out, *in; 2970 3134 char line[LINESIZE]; 2971 3135 int lineno; 2972 3136 struct state *stp; 2973 3137 struct action *ap; 2974 3138 struct rule *rp; 2975 - int i, j; 2976 - int tablecnt; 3139 + struct acttab *pActtab; 3140 + int i, j, n; 2977 3141 char *name; 3142 + int mnTknOfst, mxTknOfst; 3143 + int mnNtOfst, mxNtOfst; 2978 3144 2979 3145 in = tplt_open(lemp); 2980 3146 if( in==0 ) return; 2981 3147 out = file_open(lemp,".c","w"); 2982 3148 if( out==0 ){ 2983 3149 fclose(in); 2984 3150 return; ................................................................................ 3008 3174 fprintf(out,"#endif\n"); lineno++; 3009 3175 } 3010 3176 tplt_xfer(lemp->name,in,out,&lineno); 3011 3177 3012 3178 /* Generate the defines */ 3013 3179 fprintf(out,"/* \001 */\n"); 3014 3180 fprintf(out,"#define YYCODETYPE %s\n", 3015 - minimum_size_type(lemp->nsymbol+5)); lineno++; 3181 + minimum_size_type(0, lemp->nsymbol+5)); lineno++; 3016 3182 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++; 3017 3183 fprintf(out,"#define YYACTIONTYPE %s\n", 3018 - minimum_size_type(lemp->nstate+lemp->nrule+5)); lineno++; 3184 + minimum_size_type(0, lemp->nstate+lemp->nrule+5)); lineno++; 3019 3185 print_stack_union(out,lemp,&lineno,mhflag); 3020 3186 if( lemp->stacksize ){ 3021 3187 if( atoi(lemp->stacksize)<=0 ){ 3022 3188 ErrorMsg(lemp->filename,0, 3023 3189 "Illegal stack size: [%s]. The stack size should be an integer constant.", 3024 3190 lemp->stacksize); 3025 3191 lemp->errorcnt++; ................................................................................ 3058 3224 fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++; 3059 3225 fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++; 3060 3226 if( lemp->has_fallback ){ 3061 3227 fprintf(out,"#define YYFALLBACK 1\n"); lineno++; 3062 3228 } 3063 3229 tplt_xfer(lemp->name,in,out,&lineno); 3064 3230 3065 - /* Generate the action table. 3231 + /* Generate the action table and its associates: 3066 3232 ** 3067 - ** Each entry in the action table is an element of the following 3068 - ** structure: 3069 - ** struct yyActionEntry { 3070 - ** YYCODETYPE lookahead; 3071 - ** YYCODETYPE next; 3072 - ** YYACTIONTYPE action; 3073 - ** } 3074 - ** 3075 - ** The entries are grouped into hash tables, one hash table for each 3076 - ** parser state. The hash table has a size which is the number of 3077 - ** entries in that table. In case of a collision, the "next" value 3078 - ** contains one more than the index into the hash table of the next 3079 - ** entry in the collision chain. A "next" value of 0 means the end 3080 - ** of the chain has been reached. 3233 + ** yy_action[] A single table containing all actions. 3234 + ** yy_lookahead[] A table containing the lookahead for each entry in 3235 + ** yy_action. Used to detect hash collisions. 3236 + ** yy_shift_ofst[] For each state, the offset into yy_action for 3237 + ** shifting terminals. 3238 + ** yy_reduce_ofst[] For each state, the offset into yy_action for 3239 + ** shifting non-terminals after a reduce. 3240 + ** yy_default[] Default action for each state. 3081 3241 */ 3082 - tablecnt = 0; 3083 3242 3084 - /* Loop over parser states */ 3243 + /* Compute the actions on all states and count them up */ 3085 3244 for(i=0; i<lemp->nstate; i++){ 3086 - int tablesize; /* size of the hash table */ 3087 - int j,k; /* Loop counter */ 3088 - int collide[2048]; /* The collision chain for the table */ 3089 - struct action *table[2048]; /* Build the hash table here */ 3090 - 3091 - /* Find the number of actions and initialize the hash table */ 3092 3245 stp = lemp->sorted[i]; 3093 - stp->tabstart = tablecnt; 3094 - stp->naction = 0; 3246 + stp->nTknAct = stp->nNtAct = 0; 3247 + stp->iDflt = lemp->nstate + lemp->nrule; 3248 + stp->iTknOfst = NO_OFFSET; 3249 + stp->iNtOfst = NO_OFFSET; 3095 3250 for(ap=stp->ap; ap; ap=ap->next){ 3096 - if( ap->sp->index!=lemp->nsymbol && compute_action(lemp,ap)>=0 ){ 3097 - stp->naction++; 3251 + if( compute_action(lemp,ap)>=0 ){ 3252 + if( ap->sp->index<lemp->nterminal ){ 3253 + stp->nTknAct++; 3254 + }else if( ap->sp->index<lemp->nsymbol ){ 3255 + stp->nNtAct++; 3256 + }else{ 3257 + stp->iDflt = compute_action(lemp, ap); 3258 + } 3259 + } 3260 + } 3261 + } 3262 + mxTknOfst = mnTknOfst = 0; 3263 + mxNtOfst = mnNtOfst = 0; 3264 + 3265 + /* Compute the action table. Do this in two passes. The first 3266 + ** pass does all entries with two or more actions and the second 3267 + ** pass does all states with a single action. 3268 + */ 3269 + pActtab = acttab_alloc(); 3270 + for(j=0; j<=1; j++){ 3271 + for(i=0; i<lemp->nstate; i++){ 3272 + stp = lemp->sorted[i]; 3273 + if( (j==0 && stp->nTknAct>=2) || (j==1 && stp->nTknAct==1) ){ 3274 + for(ap=stp->ap; ap; ap=ap->next){ 3275 + int action; 3276 + if( ap->sp->index>=lemp->nterminal ) continue; 3277 + action = compute_action(lemp, ap); 3278 + if( action<0 ) continue; 3279 + acttab_action(pActtab, ap->sp->index, action); 3280 + } 3281 + stp->iTknOfst = acttab_insert(pActtab); 3282 + if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst; 3283 + if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst; 3098 3284 } 3099 - } 3100 - tablesize = stp->naction; 3101 - assert( tablesize<= sizeof(table)/sizeof(table[0]) ); 3102 - for(j=0; j<tablesize; j++){ 3103 - table[j] = 0; 3104 - collide[j] = -1; 3105 - } 3106 - 3107 - /* Hash the actions into the hash table */ 3108 - stp->tabdfltact = lemp->nstate + lemp->nrule; 3109 - for(ap=stp->ap; ap; ap=ap->next){ 3110 - int action = compute_action(lemp,ap); 3111 - int h; 3112 - if( ap->sp->index==lemp->nsymbol ){ 3113 - stp->tabdfltact = action; 3114 - }else if( action>=0 ){ 3115 - h = ap->sp->index % tablesize; 3116 - ap->collide = table[h]; 3117 - table[h] = ap; 3285 + if( (j==0 && stp->nNtAct>=2) || (j==1 && stp->nNtAct==1) ){ 3286 + for(ap=stp->ap; ap; ap=ap->next){ 3287 + int action; 3288 + if( ap->sp->index<lemp->nterminal ) continue; 3289 + if( ap->sp->index==lemp->nsymbol ) continue; 3290 + action = compute_action(lemp, ap); 3291 + if( action<0 ) continue; 3292 + acttab_action(pActtab, ap->sp->index, action); 3293 + } 3294 + stp->iNtOfst = acttab_insert(pActtab); 3295 + if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst; 3296 + if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; 3118 3297 } 3119 3298 } 3120 - 3121 - /* Resolve collisions */ 3122 - for(j=k=0; j<tablesize; j++){ 3123 - if( table[j] && table[j]->collide ){ 3124 - while( table[k] ) k++; 3125 - table[k] = table[j]->collide; 3126 - collide[j] = k; 3127 - table[j]->collide = 0; 3128 - if( k<j ) j = k-1; 3129 - } 3130 - } 3131 - 3132 - /* Print the hash table */ 3133 - if( tablesize>0 ){ 3134 - fprintf(out,"/* State %d */\n",stp->index); lineno++; 3135 - } 3136 - for(j=0; j<tablesize; j++){ 3137 - assert( table[j]!=0 ); 3138 - fprintf(out," {%4d,%4d,%4d}, /* %2d: ", 3139 - table[j]->sp->index, 3140 - collide[j]+1, 3141 - compute_action(lemp,table[j]), 3142 - j+1); 3143 - PrintAction(table[j],out,22); 3144 - fprintf(out," */\n"); 3145 - lineno++; 3146 - } 3147 - 3148 - /* Update the table count */ 3149 - tablecnt += tablesize; 3150 - } 3151 - tplt_xfer(lemp->name,in,out,&lineno); 3152 - lemp->tablesize = tablecnt; 3153 - 3154 - /* Generate the state table 3155 - ** 3156 - ** Each entry is an element of the following structure: 3157 - ** struct yyStateEntry { 3158 - ** struct yyActionEntry *hashtbl; 3159 - ** YYCODETYPE nEntry; 3160 - ** YYACTIONTYPE actionDefault; 3161 - ** } 3162 - */ 3163 - for(i=0; i<lemp->nstate; i++){ 3299 + } 3300 + 3301 + /* Output the yy_action table */ 3302 + fprintf(out,"static YYACTIONTYPE yy_action[] = {\n"); lineno++; 3303 + n = acttab_size(pActtab); 3304 + for(i=j=0; i<n; i++){ 3305 + int action = acttab_yyaction(pActtab, i); 3306 + if( action<0 ) action = lemp->nsymbol + lemp->nrule + 2; 3307 + fprintf(out, " %4d,", action); 3308 + if( j==9 || i==n-1 ){ 3309 + fprintf(out, "\n"); lineno++; 3310 + j = 0; 3311 + }else{ 3312 + j++; 3313 + } 3314 + } 3315 + fprintf(out, "};\n"); lineno++; 3316 + 3317 + /* Output the yy_lookahead table */ 3318 + fprintf(out,"static YYCODETYPE yy_lookahead[] = {\n"); lineno++; 3319 + for(i=j=0; i<n; i++){ 3320 + int la = acttab_yylookahead(pActtab, i); 3321 + if( la<0 ) la = lemp->nsymbol; 3322 + fprintf(out, " %4d,", la); 3323 + if( j==9 || i==n-1 ){ 3324 + fprintf(out, "\n"); lineno++; 3325 + j = 0; 3326 + }else{ 3327 + j++; 3328 + } 3329 + } 3330 + fprintf(out, "};\n"); lineno++; 3331 + 3332 + /* Output the yy_shift_ofst[] table */ 3333 + fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++; 3334 + fprintf(out, "static %s yy_shift_ofst[] = {\n", 3335 + minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++; 3336 + n = lemp->nstate; 3337 + for(i=j=0; i<n; i++){ 3338 + int ofst; 3339 + stp = lemp->sorted[i]; 3340 + ofst = stp->iTknOfst; 3341 + if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1; 3342 + fprintf(out, " %4d,", ofst); 3343 + if( j==9 || i==n-1 ){ 3344 + fprintf(out, "\n"); lineno++; 3345 + j = 0; 3346 + }else{ 3347 + j++; 3348 + } 3349 + } 3350 + fprintf(out, "};\n"); lineno++; 3351 + 3352 + /* Output the yy_reduce_ofst[] table */ 3353 + fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++; 3354 + fprintf(out, "static %s yy_reduce_ofst[] = {\n", 3355 + minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++; 3356 + n = lemp->nstate; 3357 + for(i=j=0; i<n; i++){ 3358 + int ofst; 3359 + stp = lemp->sorted[i]; 3360 + ofst = stp->iNtOfst; 3361 + if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1; 3362 + fprintf(out, " %4d,", ofst); 3363 + if( j==9 || i==n-1 ){ 3364 + fprintf(out, "\n"); lineno++; 3365 + j = 0; 3366 + }else{ 3367 + j++; 3368 + } 3369 + } 3370 + fprintf(out, "};\n"); lineno++; 3371 + 3372 + /* Output the default action table */ 3373 + fprintf(out, "static YYACTIONTYPE yy_default[] = {\n"); lineno++; 3374 + n = lemp->nstate; 3375 + for(i=j=0; i<n; i++){ 3164 3376 stp = lemp->sorted[i]; 3165 - fprintf(out," { &yyActionTable[%d],%4d,%4d },\n", 3166 - stp->tabstart, 3167 - stp->naction, 3168 - stp->tabdfltact); lineno++; 3377 + fprintf(out, " %4d,", stp->iDflt); 3378 + if( j==9 || i==n-1 ){ 3379 + fprintf(out, "\n"); lineno++; 3380 + j = 0; 3381 + }else{ 3382 + j++; 3383 + } 3169 3384 } 3385 + fprintf(out, "};\n"); lineno++; 3170 3386 tplt_xfer(lemp->name,in,out,&lineno); 3171 3387 3172 3388 /* Generate the table of fallback tokens. 3173 3389 */ 3174 3390 if( lemp->has_fallback ){ 3175 3391 for(i=0; i<lemp->nterminal; i++){ 3176 3392 struct symbol *p = lemp->symbols[i]; ................................................................................ 3332 3548 struct lemon *lemp; 3333 3549 { 3334 3550 struct state *stp; 3335 3551 struct action *ap, *ap2; 3336 3552 struct rule *rp, *rp2, *rbest; 3337 3553 int nbest, n; 3338 3554 int i; 3339 - int cnt; 3340 3555 3341 3556 for(i=0; i<lemp->nstate; i++){ 3342 3557 stp = lemp->sorted[i]; 3343 3558 nbest = 0; 3344 3559 rbest = 0; 3345 3560 3346 3561 for(ap=stp->ap; ap; ap=ap->next){
Changes to tool/lempar.c.
54 54 ** YYERRORSYMBOL is the code number of the error symbol. If not 55 55 ** defined, then do no error processing. 56 56 */ 57 57 %% 58 58 #define YY_NO_ACTION (YYNSTATE+YYNRULE+2) 59 59 #define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) 60 60 #define YY_ERROR_ACTION (YYNSTATE+YYNRULE) 61 -/* Next is the action table. Each entry in this table contains 62 -** 63 -** + An integer which is the number representing the look-ahead 64 -** token 65 -** 66 -** + An integer indicating what action to take. Number (N) between 67 -** 0 and YYNSTATE-1 mean shift the look-ahead and go to state N. 68 -** Numbers between YYNSTATE and YYNSTATE+YYNRULE-1 mean reduce by 69 -** rule N-YYNSTATE. Number YYNSTATE+YYNRULE means that a syntax 70 -** error has occurred. Number YYNSTATE+YYNRULE+1 means the parser 71 -** accepts its input. 72 -** 73 -** + A pointer to the next entry with the same hash value. 74 -** 75 -** The action table is really a series of hash tables. Each hash 76 -** table contains a number of entries which is a power of two. The 77 -** "state" table (which follows) contains information about the starting 78 -** point and size of each hash table. 79 -*/ 80 -struct yyActionEntry { 81 - YYCODETYPE lookahead; /* The value of the look-ahead token */ 82 - YYCODETYPE next; /* Next entry + 1. Zero at end of collision chain */ 83 - YYACTIONTYPE action; /* Action to take for this look-ahead */ 84 -}; 85 -typedef struct yyActionEntry yyActionEntry; 86 -static const yyActionEntry yyActionTable[] = { 61 + 62 +/* Next are that ables used to determine what action to take based on the 63 +** current state and lookahead token. These tables are used to implement 64 +** functions that take a state number and lookahead value and return an 65 +** action integer. 66 +** 67 +** The action integer is a number N between 68 +** 0 and YYNSTATE-1 mean shift the look-ahead and go to state N. 69 +** Numbers between YYNSTATE and YYNSTATE+YYNRULE-1 mean reduce by 70 +** rule N-YYNSTATE. Number YYNSTATE+YYNRULE means that a syntax 71 +** error has occurred. Number YYNSTATE+YYNRULE+1 means the parser 72 +** accepts its input. 73 +** 74 +** The action table is constructed as a single large hash table with 75 +** a perfect hash. Given state S and lookahead X, the action is computed 76 +** as 77 +** 78 +** yy_action[ yy_shift_ofst[S] + X ] 79 +** 80 +** If the index yy_shift_ofst[S]+X is out of range or if the value 81 +** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X or if yy_shift_ofst[S] 82 +** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table 83 +** and that yy_default[S] should be used instead. 84 +** 85 +** The formula above is for computing the action when the lookahead is 86 +** a terminal symbol. If the lookahead is a non-terminal (as occurs after 87 +** a reduce action) then the yy_reduce_ofst[] array is used in place of 88 +** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of 89 +** YY_SHIFT_USE_DFLT. 90 +** 91 +** The following are the tables generated in this section: 92 +** 93 +** yy_action[] A single table containing all actions. 94 +** yy_lookahead[] A table containing the lookahead for each entry in 95 +** yy_action. Used to detect hash collisions. 96 +** yy_shift_ofst[] For each state, the offset into yy_action for 97 +** shifting terminals. 98 +** yy_reduce_ofst[] For each state, the offset into yy_action for 99 +** shifting non-terminals after a reduce. 100 +** yy_default[] Default action for each state. 101 +*/ 87 102 %% 88 -}; 89 - 90 -/* The state table contains information needed to look up the correct 91 -** action in the action table, given the current state of the parser. 92 -** Information needed includes: 93 -** 94 -** + A pointer to the start of the action hash table in yyActionTable. 95 -** 96 -** + The number of entries in the action hash table. 97 -** 98 -** + The default action. This is the action to take if no entry for 99 -** the given look-ahead is found in the action hash table. 100 -*/ 101 -struct yyStateEntry { 102 - const yyActionEntry *hashtbl; /* Start of the hash table in yyActionTable */ 103 - YYCODETYPE nEntry; /* Number of entries in action hash table */ 104 - YYACTIONTYPE actionDefault; /* Default action if look-ahead not found */ 105 -}; 106 -typedef struct yyStateEntry yyStateEntry; 107 -static const yyStateEntry yyStateTable[] = { 108 -%% 109 -}; 103 +#define YY_SZ_ACTTAB (sizeof(yy_action)/sizeof(yy_action[0])) 110 104 111 105 /* The next table maps tokens into fallback tokens. If a construct 112 106 ** like the following: 113 107 ** 114 108 ** %fallback ID X Y Z. 115 109 ** 116 110 ** appears in the grammer, then ID becomes a fallback token for X, Y, ................................................................................ 308 302 yyParser *pParser = (yyParser*)p; 309 303 if( pParser==0 ) return; 310 304 while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser); 311 305 (*freeProc)((void*)pParser); 312 306 } 313 307 314 308 /* 315 -** Find the appropriate action for a parser given the look-ahead token. 309 +** Find the appropriate action for a parser given the terminal 310 +** look-ahead token iLookAhead. 316 311 ** 317 312 ** If the look-ahead token is YYNOCODE, then check to see if the action is 318 313 ** independent of the look-ahead. If it is, return the action, otherwise 319 314 ** return YY_NO_ACTION. 320 315 */ 321 -static int yy_find_parser_action( 316 +static int yy_find_shift_action( 322 317 yyParser *pParser, /* The parser */ 323 - int iLookAhead /* The look-ahead token */ 318 + int iLookAhead /* The look-ahead token */ 324 319 ){ 325 - const yyStateEntry *pState; /* Appropriate entry in the state table */ 326 - const yyActionEntry *pAction; /* Action appropriate for the look-ahead */ 327 - int iFallback; /* Fallback token */ 320 + int i; 328 321 329 322 /* if( pParser->yyidx<0 ) return YY_NO_ACTION; */ 330 - pState = &yyStateTable[pParser->yytop->stateno]; 331 - if( pState->nEntry==0 ){ 332 - return pState->actionDefault; 333 - }else if( iLookAhead!=YYNOCODE ){ 334 - pAction = &pState->hashtbl[iLookAhead % pState->nEntry]; 335 - while( 1 ){ 336 - if( pAction->lookahead==iLookAhead ) return pAction->action; 337 - if( pAction->next==0 ) break; 338 - pAction = &pState->hashtbl[pAction->next-1]; 339 - } 323 + i = yy_shift_ofst[pParser->yytop->stateno]; 324 + if( i==YY_SHIFT_USE_DFLT ){ 325 + return yy_default[pParser->yytop->stateno]; 326 + } 327 + if( iLookAhead==YYNOCODE ){ 328 + return YY_NO_ACTION; 329 + } 330 + i += iLookAhead; 331 + if( i<0 || i>=YY_SZ_ACTTAB || yy_lookahead[i]!=iLookAhead ){ 340 332 #ifdef YYFALLBACK 333 + int iFallback; /* Fallback token */ 341 334 if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0]) 342 335 && (iFallback = yyFallback[iLookAhead])!=0 ){ 343 336 #ifndef NDEBUG 344 337 if( yyTraceFILE ){ 345 338 fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n", 346 339 yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]); 347 340 } 348 341 #endif 349 - return yy_find_parser_action(pParser, iFallback); 342 + return yy_find_shift_action(pParser, iFallback); 350 343 } 351 344 #endif 352 - }else if( pState->hashtbl->lookahead!=YYNOCODE ){ 345 + return yy_default[pParser->yytop->stateno]; 346 + }else{ 347 + return yy_action[i]; 348 + } 349 +} 350 + 351 +/* 352 +** Find the appropriate action for a parser given the non-terminal 353 +** look-ahead token iLookAhead. 354 +** 355 +** If the look-ahead token is YYNOCODE, then check to see if the action is 356 +** independent of the look-ahead. If it is, return the action, otherwise 357 +** return YY_NO_ACTION. 358 +*/ 359 +static int yy_find_reduce_action( 360 + yyParser *pParser, /* The parser */ 361 + int iLookAhead /* The look-ahead token */ 362 +){ 363 + int i; 364 + 365 + i = yy_reduce_ofst[pParser->yytop->stateno]; 366 + if( i==YY_REDUCE_USE_DFLT ){ 367 + return yy_default[pParser->yytop->stateno]; 368 + } 369 + if( iLookAhead==YYNOCODE ){ 353 370 return YY_NO_ACTION; 354 371 } 355 - return pState->actionDefault; 372 + i += iLookAhead; 373 + if( i<0 || i>=YY_SZ_ACTTAB || yy_lookahead[i]!=iLookAhead ){ 374 + return yy_default[pParser->yytop->stateno]; 375 + }else{ 376 + return yy_action[i]; 377 + } 356 378 } 357 379 358 380 /* 359 381 ** Perform a shift action. 360 382 */ 361 383 static void yy_shift( 362 384 yyParser *yypParser, /* The parser to be shifted */ ................................................................................ 443 465 */ 444 466 %% 445 467 }; 446 468 yygoto = yyRuleInfo[yyruleno].lhs; 447 469 yysize = yyRuleInfo[yyruleno].nrhs; 448 470 yypParser->yyidx -= yysize; 449 471 yypParser->yytop -= yysize; 450 - yyact = yy_find_parser_action(yypParser,yygoto); 472 + yyact = yy_find_reduce_action(yypParser,yygoto); 451 473 if( yyact < YYNSTATE ){ 452 474 yy_shift(yypParser,yyact,yygoto,&yygotominor); 453 475 }else if( yyact == YYNSTATE + YYNRULE + 1 ){ 454 476 yy_accept(yypParser); 455 477 } 456 478 } 457 479 ................................................................................ 555 577 #ifndef NDEBUG 556 578 if( yyTraceFILE ){ 557 579 fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); 558 580 } 559 581 #endif 560 582 561 583 do{ 562 - yyact = yy_find_parser_action(yypParser,yymajor); 584 + yyact = yy_find_shift_action(yypParser,yymajor); 563 585 if( yyact<YYNSTATE ){ 564 586 yy_shift(yypParser,yyact,yymajor,&yyminorunion); 565 587 yypParser->yyerrcnt--; 566 588 if( yyendofinput && yypParser->yyidx>=0 ){ 567 589 yymajor = 0; 568 590 }else{ 569 591 yymajor = YYNOCODE; ................................................................................ 608 630 #endif 609 631 yy_destructor(yymajor,&yyminorunion); 610 632 yymajor = YYNOCODE; 611 633 }else{ 612 634 while( 613 635 yypParser->yyidx >= 0 && 614 636 yypParser->yytop->major != YYERRORSYMBOL && 615 - (yyact = yy_find_parser_action(yypParser,YYERRORSYMBOL)) >= YYNSTATE 637 + (yyact = yy_find_shift_action(yypParser,YYERRORSYMBOL)) >= YYNSTATE 616 638 ){ 617 639 yy_pop_parser_stack(yypParser); 618 640 } 619 641 if( yypParser->yyidx < 0 || yymajor==0 ){ 620 642 yy_destructor(yymajor,&yyminorunion); 621 643 yy_parse_failed(yypParser); 622 644 yymajor = YYNOCODE;