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 | 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 | 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 */ |
︙ | |||
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 | 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, |
︙ | |||
2650 2651 2652 2653 2654 2655 2656 | 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 ){ |
︙ | |||
2945 2946 2947 2948 2949 2950 2951 | 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 |
︙ | |||
3008 3009 3010 3011 3012 3013 3014 | 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", |
︙ | |||
3058 3059 3060 3061 3062 3063 3064 | 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); |
︙ | |||
3332 3333 3334 3335 3336 3337 3338 | 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; |
︙ |
Changes to tool/lempar.c.
︙ | |||
54 55 56 57 58 59 60 | 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) |
︙ | |||
308 309 310 311 312 313 314 | 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); } /* |
︙ | |||
443 444 445 446 447 448 449 | 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; |
︙ | |||
555 556 557 558 559 560 561 | 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{ |
︙ | |||
608 609 610 611 612 613 614 | 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 && |
︙ |