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: |
4f955c00076b16166ff837749efb8420 |
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
Changes to tool/lemon.c.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 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> extern void qsort(); extern double strtod(); extern long strtol(); extern void free(); extern int access(); extern int atoi(); | > | 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 | /* 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 */ | | | | > | 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 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 | new->sp = sp; if( type==SHIFT ){ new->x.stp = (struct state *)arg; }else{ new->x.rp = (struct rule *)arg; } } /********************** From the file "assert.c" ****************************/ /* ** A more efficient way of handling assertions. */ void myassert(file,line) char *file; int line; | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | 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, | | | | | 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, (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, (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, (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 | char buf[1000]; FILE *in; char *tpltname; char *cp; cp = strrchr(lemp->filename,'.'); if( cp ){ | | | 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",(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 | free(types); fprintf(out,"} YYMINORTYPE;\n"); lineno++; *plineno = lineno; } /* ** Return the name of a C datatype able to represent values between | | | > | | | | | | > > > > > > > > | < > > | 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 ** lwr and upr, inclusive. */ 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, n; 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 | 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", | | | | 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(0, lemp->nsymbol+5)); lineno++; fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++; fprintf(out,"#define YYACTIONTYPE %s\n", 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 | 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); | | | | < | > | > | | < < < < < < < < < > > > > > > > > | | > > > > > > > > > > | | > > > | | > | < | | > > | | > | < | < < | | | | < < | | < > | | | | > | > | > > > > > > > > > | < < < | < < | < > > | | > | > > > > > | | > > > > > | | > | > | < > > | < > > | > | > > | | | < | > > > > | > > | > > > > > > > > | > > | < < < | < | < < | > | < < > | > > > | > > | 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 and its associates: ** ** yy_action[] A single table containing all actions. ** yy_lookahead[] A table containing the lookahead for each entry in ** 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. */ /* 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 ){ 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]; 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); } stp->iTknOfst = acttab_insert(pActtab); 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) ){ for(ap=stp->ap; ap; ap=ap->next){ int action; 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 ){ fprintf(out, "\n"); lineno++; j = 0; }else{ j++; } } fprintf(out, "};\n"); 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++; /* 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; for(i=j=0; i<n; i++){ int ofst; stp = lemp->sorted[i]; 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++; } } fprintf(out, "};\n"); lineno++; /* 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++; /* Output the default action table */ fprintf(out, "static YYACTIONTYPE yy_default[] = {\n"); lineno++; n = lemp->nstate; for(i=j=0; i<n; i++){ stp = lemp->sorted[i]; fprintf(out, " %4d,", stp->iDflt); 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 | struct lemon *lemp; { struct state *stp; struct action *ap, *ap2; struct rule *rp, *rp2, *rbest; int nbest, n; int i; | < | 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; 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 | ** 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) | | | | > | | | | | | | < > > > | < < < | | | < < < | < < < | < < < | > > > > < > > > | > | > > > < < < < < < < < > | 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 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. ** ** 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. ** ** 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 ** ** yy_action[ yy_shift_ofst[S] + X ] ** ** 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] ** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table ** and that yy_default[S] should be used instead. ** ** 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 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 ** 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. */ %% #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 | yyParser *pParser = (yyParser*)p; if( pParser==0 ) return; while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser); (*freeProc)((void*)pParser); } /* | | > | | < < | | | | > | < < | < < | > > > | > > > > > | > > > > > > > > > > > > > > > > > > > > > > > | > | 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 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_shift_action( yyParser *pParser, /* The parser */ int iLookAhead /* The look-ahead token */ ){ int i; /* if( pParser->yyidx<0 ) return YY_NO_ACTION; */ i = yy_shift_ofst[pParser->yytop->stateno]; if( i==YY_SHIFT_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 ){ #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_shift_action(pParser, iFallback); } #endif return yy_default[pParser->yytop->stateno]; }else{ return yy_action[i]; } } /* ** 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 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 | */ %% }; yygoto = yyRuleInfo[yyruleno].lhs; yysize = yyRuleInfo[yyruleno].nrhs; yypParser->yyidx -= yysize; yypParser->yytop -= yysize; | | | 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_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 | #ifndef NDEBUG if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); } #endif do{ | | | 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_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 | #endif yy_destructor(yymajor,&yyminorunion); yymajor = YYNOCODE; }else{ while( yypParser->yyidx >= 0 && yypParser->yytop->major != YYERRORSYMBOL && | | | 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_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; |
︙ | ︙ |