Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch lemon-update Excluding Merge-Ins
This is equivalent to a diff from b6ffb7e4 to e9d604b4
|
2015-09-07
| ||
| 20:11 | Enhance the Lemon parser generator to add SHIFTREDUCE states that reduce the sizes of some of the parser tables. (check-in: 99b992fa user: drh tags: trunk) | |
| 20:02 | Fix an unreachable branch in the new parse automaton. (Closed-Leaf check-in: e9d604b4 user: drh tags: lemon-update) | |
| 19:52 | Change the parser engine so that it (once again) waits for a lookahead token before reducing, even in a SHIFTREDUCE action. (check-in: 2c17a135 user: drh tags: lemon-update) | |
| 18:23 | For the Lemon-generated parser, add a new action type SHIFTREDUCE and use it to further compress the parser tables and improve parser performance. (check-in: 531c3974 user: drh tags: lemon-update) | |
| 14:22 | In the "parse.out" output file from Lemon, show addition the complete text of rules on reduce actions. (check-in: b6ffb7e4 user: drh tags: trunk) | |
| 02:23 | Improved "Parser Statistics" output (the -s option) for the Lemon parser generator. (check-in: 809503e4 user: drh tags: trunk) | |
Changes to src/lempar.c.
52 52 ** for base tokens is called "yy0". 53 53 ** YYSTACKDEPTH is the maximum depth of the parser's stack. If 54 54 ** zero the stack is dynamically sized using realloc() 55 55 ** ParseARG_SDECL A static variable declaration for the %extra_argument 56 56 ** ParseARG_PDECL A parameter declaration for the %extra_argument 57 57 ** ParseARG_STORE Code to store %extra_argument into yypParser 58 58 ** ParseARG_FETCH Code to extract %extra_argument from yypParser 59 -** YYNSTATE the combined number of states. 60 -** YYNRULE the number of rules in the grammar 61 59 ** YYERRORSYMBOL is the code number of the error symbol. If not 62 60 ** defined, then do no error processing. 61 +** YYNSTATE the combined number of states. 62 +** YYNRULE the number of rules in the grammar 63 +** YY_MAX_SHIFT Maximum value for shift actions 64 +** YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions 65 +** YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions 66 +** YY_MIN_REDUCE Maximum value for reduce actions 67 +** YY_ERROR_ACTION The yy_action[] code for syntax error 68 +** YY_ACCEPT_ACTION The yy_action[] code for accept 69 +** YY_NO_ACTION The yy_action[] code for no-op 63 70 */ 64 71 %% 65 -#define YY_NO_ACTION (YYNSTATE+YYNRULE+2) 66 -#define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) 67 -#define YY_ERROR_ACTION (YYNSTATE+YYNRULE) 68 72 69 73 /* The yyzerominor constant is used to initialize instances of 70 74 ** YYMINORTYPE objects to zero. */ 71 75 static const YYMINORTYPE yyzerominor = { 0 }; 72 76 73 77 /* Define the yytestcase() macro to be a no-op if is not already defined 74 78 ** otherwise. ................................................................................ 87 91 ** current state and lookahead token. These tables are used to implement 88 92 ** functions that take a state number and lookahead value and return an 89 93 ** action integer. 90 94 ** 91 95 ** Suppose the action integer is N. Then the action is determined as 92 96 ** follows 93 97 ** 94 -** 0 <= N < YYNSTATE Shift N. That is, push the lookahead 98 +** 0 <= N <= YY_MAX_SHIFT Shift N. That is, push the lookahead 95 99 ** token onto the stack and goto state N. 96 100 ** 97 -** YYNSTATE <= N < YYNSTATE+YYNRULE Reduce by rule N-YYNSTATE. 101 +** N between YY_MIN_SHIFTREDUCE Shift to an arbitrary state then 102 +** and YY_MAX_SHIFTREDUCE reduce by rule N-YY_MIN_SHIFTREDUCE. 98 103 ** 99 -** N == YYNSTATE+YYNRULE A syntax error has occurred. 104 +** N between YY_MIN_REDUCE Reduce by rule N-YY_MIN_REDUCE 105 +** and YY_MAX_REDUCE 106 + 107 +** N == YY_ERROR_ACTION A syntax error has occurred. 100 108 ** 101 -** N == YYNSTATE+YYNRULE+1 The parser accepts its input. 109 +** N == YY_ACCEPT_ACTION The parser accepts its input. 102 110 ** 103 -** N == YYNSTATE+YYNRULE+2 No such action. Denotes unused 111 +** N == YY_NO_ACTION No such action. Denotes unused 104 112 ** slots in the yy_action[] table. 105 113 ** 106 114 ** The action table is constructed as a single large table named yy_action[]. 107 115 ** Given state S and lookahead X, the action is computed as 108 116 ** 109 117 ** yy_action[ yy_shift_ofst[S] + X ] 110 118 ** ................................................................................ 155 163 ** 156 164 ** + The value of the token stored at this level of the stack. 157 165 ** (In other words, the "major" token.) 158 166 ** 159 167 ** + The semantic value stored at this level of the stack. This is 160 168 ** the information used by the action routines in the grammar. 161 169 ** It is sometimes called the "minor" token. 170 +** 171 +** After the "shift" half of a SHIFTREDUCE action, the stateno field 172 +** actually contains the reduce action for the second half of the 173 +** SHIFTREDUCE. 162 174 */ 163 175 struct yyStackEntry { 164 - YYACTIONTYPE stateno; /* The state-number */ 176 + YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ 165 177 YYCODETYPE major; /* The major token value. This is the code 166 178 ** number for the token at this stack level */ 167 179 YYMINORTYPE minor; /* The user-supplied minor token value. This 168 180 ** is the value of the token */ 169 181 }; 170 182 typedef struct yyStackEntry yyStackEntry; 171 183 ................................................................................ 391 403 static int yy_find_shift_action( 392 404 yyParser *pParser, /* The parser */ 393 405 YYCODETYPE iLookAhead /* The look-ahead token */ 394 406 ){ 395 407 int i; 396 408 int stateno = pParser->yystack[pParser->yyidx].stateno; 397 409 398 - if( stateno>YY_SHIFT_COUNT 399 - || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){ 400 - return yy_default[stateno]; 401 - } 410 + if( stateno>=YY_MIN_REDUCE ) return stateno; 411 + assert( stateno <= YY_SHIFT_COUNT ); 412 + i = yy_shift_ofst[stateno]; 413 + if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno]; 402 414 assert( iLookAhead!=YYNOCODE ); 403 415 i += iLookAhead; 404 416 if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ 405 417 if( iLookAhead>0 ){ 406 418 #ifdef YYFALLBACK 407 419 YYCODETYPE iFallback; /* Fallback token */ 408 420 if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0]) ................................................................................ 495 507 /* Here code is inserted which will execute if the parser 496 508 ** stack every overflows */ 497 509 %% 498 510 ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ 499 511 } 500 512 501 513 /* 502 -** Perform a shift action. 514 +** Print tracing information for a SHIFT action 515 +*/ 516 +#ifndef NDEBUG 517 +static void yyTraceShift(yyParser *yypParser, int yyNewState){ 518 + if( yyTraceFILE ){ 519 + int i; 520 + if( yyNewState<YYNSTATE ){ 521 + fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 522 + fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 523 + for(i=1; i<=yypParser->yyidx; i++) 524 + fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 525 + fprintf(yyTraceFILE,"\n"); 526 + }else{ 527 + fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 528 + } 529 + } 530 +} 531 +#else 532 +# define yyTraceShift(X,Y) 533 +#endif 534 + 535 +/* 536 +** Perform a shift action. Return the number of errors. 503 537 */ 504 538 static void yy_shift( 505 539 yyParser *yypParser, /* The parser to be shifted */ 506 540 int yyNewState, /* The new state to shift in */ 507 541 int yyMajor, /* The major token to shift in */ 508 542 YYMINORTYPE *yypMinor /* Pointer to the minor token to shift in */ 509 543 ){ ................................................................................ 528 562 } 529 563 } 530 564 #endif 531 565 yytos = &yypParser->yystack[yypParser->yyidx]; 532 566 yytos->stateno = (YYACTIONTYPE)yyNewState; 533 567 yytos->major = (YYCODETYPE)yyMajor; 534 568 yytos->minor = *yypMinor; 535 -#ifndef NDEBUG 536 - if( yyTraceFILE && yypParser->yyidx>0 ){ 537 - int i; 538 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 539 - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 540 - for(i=1; i<=yypParser->yyidx; i++) 541 - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 542 - fprintf(yyTraceFILE,"\n"); 543 - } 544 -#endif 569 + yyTraceShift(yypParser, yyNewState); 545 570 } 546 571 547 572 /* The following table contains information about every rule that 548 573 ** is used during the reduce. 549 574 */ 550 575 static const struct { 551 576 YYCODETYPE lhs; /* Symbol on the left-hand side of the rule */ ................................................................................ 570 595 yyStackEntry *yymsp; /* The top of the parser's stack */ 571 596 int yysize; /* Amount to pop the stack */ 572 597 ParseARG_FETCH; 573 598 yymsp = &yypParser->yystack[yypParser->yyidx]; 574 599 #ifndef NDEBUG 575 600 if( yyTraceFILE && yyruleno>=0 576 601 && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ 577 - fprintf(yyTraceFILE, "%sReduce [%s].\n", yyTracePrompt, 578 - yyRuleName[yyruleno]); 602 + yysize = yyRuleInfo[yyruleno].nrhs; 603 + fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt, 604 + yyRuleName[yyruleno], yymsp[-yysize].stateno); 579 605 } 580 606 #endif /* NDEBUG */ 581 607 582 608 /* Silence complaints from purify about yygotominor being uninitialized 583 609 ** in some cases when it is copied into the stack after the following 584 610 ** switch. yygotominor is uninitialized when a rule reduces that does 585 611 ** not set the value of its left-hand side nonterminal. Leaving the ................................................................................ 609 635 %% 610 636 }; 611 637 assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); 612 638 yygoto = yyRuleInfo[yyruleno].lhs; 613 639 yysize = yyRuleInfo[yyruleno].nrhs; 614 640 yypParser->yyidx -= yysize; 615 641 yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); 616 - if( yyact < YYNSTATE ){ 617 -#ifdef NDEBUG 618 - /* If we are not debugging and the reduce action popped at least 642 + if( yyact <= YY_MAX_SHIFTREDUCE ){ 643 + if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 644 + /* If the reduce action popped at least 619 645 ** one element off the stack, then we can push the new element back 620 646 ** onto the stack here, and skip the stack overflow test in yy_shift(). 621 647 ** That gives a significant speed improvement. */ 622 648 if( yysize ){ 623 649 yypParser->yyidx++; 624 650 yymsp -= yysize-1; 625 651 yymsp->stateno = (YYACTIONTYPE)yyact; 626 652 yymsp->major = (YYCODETYPE)yygoto; 627 653 yymsp->minor = yygotominor; 628 - }else 629 -#endif 630 - { 654 + yyTraceShift(yypParser, yyact); 655 + }else{ 631 656 yy_shift(yypParser,yyact,yygoto,&yygotominor); 632 657 } 633 658 }else{ 634 - assert( yyact == YYNSTATE + YYNRULE + 1 ); 659 + assert( yyact == YY_ACCEPT_ACTION ); 635 660 yy_accept(yypParser); 636 661 } 637 662 } 638 663 639 664 /* 640 665 ** The following code executes when the parse fails 641 666 */ ................................................................................ 751 776 if( yyTraceFILE ){ 752 777 fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); 753 778 } 754 779 #endif 755 780 756 781 do{ 757 782 yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); 758 - if( yyact<YYNSTATE ){ 783 + if( yyact <= YY_MAX_SHIFTREDUCE ){ 784 + if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 759 785 yy_shift(yypParser,yyact,yymajor,&yyminorunion); 760 786 yypParser->yyerrcnt--; 761 787 yymajor = YYNOCODE; 762 - }else if( yyact < YYNSTATE + YYNRULE ){ 763 - yy_reduce(yypParser,yyact-YYNSTATE); 788 + }else if( yyact <= YY_MAX_REDUCE ){ 789 + yy_reduce(yypParser,yyact-YY_MIN_REDUCE); 764 790 }else{ 765 791 assert( yyact == YY_ERROR_ACTION ); 766 792 #ifdef YYERRORSYMBOL 767 793 int yymx; 768 794 #endif 769 795 #ifndef NDEBUG 770 796 if( yyTraceFILE ){ ................................................................................ 806 832 yymajor = YYNOCODE; 807 833 }else{ 808 834 while( 809 835 yypParser->yyidx >= 0 && 810 836 yymx != YYERRORSYMBOL && 811 837 (yyact = yy_find_reduce_action( 812 838 yypParser->yystack[yypParser->yyidx].stateno, 813 - YYERRORSYMBOL)) >= YYNSTATE 839 + YYERRORSYMBOL)) >= YY_MIN_REDUCE 814 840 ){ 815 841 yy_pop_parser_stack(yypParser); 816 842 } 817 843 if( yypParser->yyidx < 0 || yymajor==0 ){ 818 844 yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 819 845 yy_parse_failed(yypParser); 820 846 yymajor = YYNOCODE; ................................................................................ 856 882 if( yyendofinput ){ 857 883 yy_parse_failed(yypParser); 858 884 } 859 885 yymajor = YYNOCODE; 860 886 #endif 861 887 } 862 888 }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); 889 +#ifndef NDEBUG 890 + if( yyTraceFILE ){ 891 + fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt); 892 + } 893 +#endif 863 894 return; 864 895 }
Changes to src/tokenize.c.
399 399 if( db->nVdbeActive==0 ){ 400 400 db->u1.isInterrupted = 0; 401 401 } 402 402 pParse->rc = SQLITE_OK; 403 403 pParse->zTail = zSql; 404 404 i = 0; 405 405 assert( pzErrMsg!=0 ); 406 + /* sqlite3ParserTrace(stdout, "parser: "); */ 406 407 pEngine = sqlite3ParserAlloc(sqlite3Malloc); 407 408 if( pEngine==0 ){ 408 409 db->mallocFailed = 1; 409 410 return SQLITE_NOMEM; 410 411 } 411 412 assert( pParse->pNewTable==0 ); 412 413 assert( pParse->pNewTrigger==0 );
Changes to tool/lemon.c.
312 312 REDUCE, 313 313 ERROR, 314 314 SSCONFLICT, /* A shift/shift conflict */ 315 315 SRCONFLICT, /* Was a reduce, but part of a conflict */ 316 316 RRCONFLICT, /* Was a reduce, but part of a conflict */ 317 317 SH_RESOLVED, /* Was a shift. Precedence resolved conflict */ 318 318 RD_RESOLVED, /* Was reduce. Precedence resolved conflict */ 319 - NOT_USED /* Deleted by compression */ 319 + NOT_USED, /* Deleted by compression */ 320 + SHIFTREDUCE /* Shift first, then reduce */ 320 321 }; 321 322 322 323 /* Every shift or reduce operation is stored as one of the following */ 323 324 struct action { 324 325 struct symbol *sp; /* The look-ahead symbol */ 325 326 enum e_action type; 326 327 union { ................................................................................ 336 337 struct state { 337 338 struct config *bp; /* The basis configurations for this state */ 338 339 struct config *cfp; /* All configurations in this set */ 339 340 int statenum; /* Sequential number for this state */ 340 341 struct action *ap; /* Array of actions for this state */ 341 342 int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */ 342 343 int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */ 343 - int iDflt; /* Default action is reduce by this rule */ 344 + int iDfltReduce; /* Default action is to REDUCE by this rule */ 345 + struct rule *pDfltReduce;/* The default REDUCE rule. */ 346 + int autoReduce; /* True if this is an auto-reduce state */ 344 347 }; 345 348 #define NO_OFFSET (-2147483647) 346 349 347 350 /* A followset propagation link indicates that the contents of one 348 351 ** configuration followset should be propagated to another whenever 349 352 ** the first changes. */ 350 353 struct plink { ................................................................................ 356 359 ** follows. (LEMON uses no global variables and makes little use of 357 360 ** static variables. Fields in the following structure can be thought 358 361 ** of as begin global variables in the program.) */ 359 362 struct lemon { 360 363 struct state **sorted; /* Table of states sorted by state number */ 361 364 struct rule *rule; /* List of all rules */ 362 365 int nstate; /* Number of states */ 366 + int nxstate; /* nstate with tail degenerate states removed */ 363 367 int nrule; /* Number of rules */ 364 368 int nsymbol; /* Number of terminal and nonterminal symbols */ 365 369 int nterminal; /* Number of terminal symbols */ 366 370 struct symbol **symbols; /* Sorted array of pointers to symbols */ 367 371 int errorcnt; /* Number of errors */ 368 372 struct symbol *errsym; /* The error symbol */ 369 373 struct symbol *wildcard; /* Token that matches anything */ ................................................................................ 480 484 struct action *ap2 481 485 ){ 482 486 int rc; 483 487 rc = ap1->sp->index - ap2->sp->index; 484 488 if( rc==0 ){ 485 489 rc = (int)ap1->type - (int)ap2->type; 486 490 } 487 - if( rc==0 && ap1->type==REDUCE ){ 491 + if( rc==0 && (ap1->type==REDUCE || ap1->type==SHIFTREDUCE) ){ 488 492 rc = ap1->x.rp->index - ap2->x.rp->index; 489 493 } 490 494 if( rc==0 ){ 491 495 rc = (int) (ap2 - ap1); 492 496 } 493 497 return rc; 494 498 } ................................................................................ 1627 1631 } 1628 1632 if( statistics ){ 1629 1633 printf("Parser statistics:\n"); 1630 1634 stats_line("terminal symbols", lem.nterminal); 1631 1635 stats_line("non-terminal symbols", lem.nsymbol - lem.nterminal); 1632 1636 stats_line("total symbols", lem.nsymbol); 1633 1637 stats_line("rules", lem.nrule); 1634 - stats_line("states", lem.nstate); 1638 + stats_line("states", lem.nxstate); 1635 1639 stats_line("conflicts", lem.nconflict); 1636 1640 stats_line("action table entries", lem.nactiontab); 1637 1641 stats_line("total table size (bytes)", lem.tablesize); 1638 1642 } 1639 1643 if( lem.nconflict > 0 ){ 1640 1644 fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict); 1641 1645 } ................................................................................ 3025 3029 3026 3030 /* Print an action to the given file descriptor. Return FALSE if 3027 3031 ** nothing was actually printed. 3028 3032 */ 3029 3033 int PrintAction( 3030 3034 struct action *ap, /* The action to print */ 3031 3035 FILE *fp, /* Print the action here */ 3032 - int indent, /* Indent by this amount */ 3033 - struct rule **apRule /* All rules by index */ 3036 + int indent /* Indent by this amount */ 3034 3037 ){ 3035 3038 int result = 1; 3036 3039 switch( ap->type ){ 3037 3040 case SHIFT: { 3038 3041 struct state *stp = ap->x.stp; 3039 - fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum); 3040 - if( stp->nTknAct==0 && stp->nNtAct==0 && apRule ){ 3041 - fprintf(fp,"then reduce %d: ", stp->iDflt); 3042 - RulePrint(fp, apRule[stp->iDflt], -1); 3043 - } 3042 + fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum); 3044 3043 break; 3045 3044 } 3046 3045 case REDUCE: { 3047 3046 struct rule *rp = ap->x.rp; 3048 - fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index); 3049 - if( apRule ) RulePrint(fp, apRule[rp->index], -1); 3047 + fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index); 3048 + RulePrint(fp, rp, -1); 3049 + break; 3050 + } 3051 + case SHIFTREDUCE: { 3052 + struct rule *rp = ap->x.rp; 3053 + fprintf(fp,"%*s shift-reduce %-7d",indent,ap->sp->name,rp->index); 3054 + RulePrint(fp, rp, -1); 3050 3055 break; 3051 3056 } 3052 3057 case ACCEPT: 3053 3058 fprintf(fp,"%*s accept",indent,ap->sp->name); 3054 3059 break; 3055 3060 case ERROR: 3056 3061 fprintf(fp,"%*s error",indent,ap->sp->name); 3057 3062 break; 3058 3063 case SRCONFLICT: 3059 3064 case RRCONFLICT: 3060 - fprintf(fp,"%*s reduce %-7d ** Parsing conflict **", 3065 + fprintf(fp,"%*s reduce %-7d ** Parsing conflict **", 3061 3066 indent,ap->sp->name,ap->x.rp->index); 3062 3067 break; 3063 3068 case SSCONFLICT: 3064 - fprintf(fp,"%*s shift %-7d ** Parsing conflict **", 3069 + fprintf(fp,"%*s shift %-7d ** Parsing conflict **", 3065 3070 indent,ap->sp->name,ap->x.stp->statenum); 3066 3071 break; 3067 3072 case SH_RESOLVED: 3068 3073 if( showPrecedenceConflict ){ 3069 - fprintf(fp,"%*s shift %-7d -- dropped by precedence", 3074 + fprintf(fp,"%*s shift %-7d -- dropped by precedence", 3070 3075 indent,ap->sp->name,ap->x.stp->statenum); 3071 3076 }else{ 3072 3077 result = 0; 3073 3078 } 3074 3079 break; 3075 3080 case RD_RESOLVED: 3076 3081 if( showPrecedenceConflict ){ ................................................................................ 3083 3088 case NOT_USED: 3084 3089 result = 0; 3085 3090 break; 3086 3091 } 3087 3092 return result; 3088 3093 } 3089 3094 3090 -/* Generate the "y.output" log file */ 3095 +/* Generate the "*.out" log file */ 3091 3096 void ReportOutput(struct lemon *lemp) 3092 3097 { 3093 3098 int i; 3094 3099 struct state *stp; 3095 3100 struct config *cfp; 3096 3101 struct action *ap; 3097 3102 FILE *fp; 3098 - struct rule **apRule; 3099 3103 3100 - apRule = malloc( sizeof(apRule[0])*(lemp->nrule+1) ); 3101 - if( apRule ){ 3102 - struct rule *x; 3103 - memset(apRule, 0, sizeof(apRule[0])*(lemp->nrule+1) ); 3104 - for(x=lemp->rule; x; x=x->next){ 3105 - assert( x->index>=0 && x->index<(lemp->nrule+1) ); 3106 - apRule[x->index] = x; 3107 - } 3108 - } 3109 3104 fp = file_open(lemp,".out","wb"); 3110 3105 if( fp==0 ) return; 3111 - for(i=0; i<lemp->nstate; i++){ 3106 + for(i=0; i<lemp->nxstate; i++){ 3112 3107 stp = lemp->sorted[i]; 3113 3108 fprintf(fp,"State %d:\n",stp->statenum); 3114 3109 if( lemp->basisflag ) cfp=stp->bp; 3115 3110 else cfp=stp->cfp; 3116 3111 while( cfp ){ 3117 3112 char buf[20]; 3118 3113 if( cfp->dot==cfp->rp->nrhs ){ ................................................................................ 3129 3124 PlinkPrint(fp,cfp->bplp,"From"); 3130 3125 #endif 3131 3126 if( lemp->basisflag ) cfp=cfp->bp; 3132 3127 else cfp=cfp->next; 3133 3128 } 3134 3129 fprintf(fp,"\n"); 3135 3130 for(ap=stp->ap; ap; ap=ap->next){ 3136 - if( PrintAction(ap,fp,30,apRule) ) fprintf(fp,"\n"); 3131 + if( PrintAction(ap,fp,30) ) fprintf(fp,"\n"); 3137 3132 } 3138 3133 fprintf(fp,"\n"); 3139 3134 } 3140 3135 fprintf(fp, "----------------------------------------------------\n"); 3141 3136 fprintf(fp, "Symbols:\n"); 3142 3137 for(i=0; i<lemp->nsymbol; i++){ 3143 3138 int j; ................................................................................ 3155 3150 fprintf(fp, " %s", lemp->symbols[j]->name); 3156 3151 } 3157 3152 } 3158 3153 } 3159 3154 fprintf(fp, "\n"); 3160 3155 } 3161 3156 fclose(fp); 3162 - free(apRule); 3163 3157 return; 3164 3158 } 3165 3159 3166 3160 /* Search for the file "name" which is in the same directory as 3167 3161 ** the exacutable */ 3168 3162 PRIVATE char *pathsearch(char *argv0, char *name, int modemask) 3169 3163 { ................................................................................ 3213 3207 ** which is to be put in the action table of the generated machine. 3214 3208 ** Return negative if no action should be generated. 3215 3209 */ 3216 3210 PRIVATE int compute_action(struct lemon *lemp, struct action *ap) 3217 3211 { 3218 3212 int act; 3219 3213 switch( ap->type ){ 3220 - case SHIFT: act = ap->x.stp->statenum; break; 3221 - case REDUCE: act = ap->x.rp->index + lemp->nstate; break; 3222 - case ERROR: act = lemp->nstate + lemp->nrule; break; 3223 - case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break; 3214 + case SHIFT: act = ap->x.stp->statenum; break; 3215 + case SHIFTREDUCE: act = ap->x.rp->index + lemp->nstate; break; 3216 + case REDUCE: act = ap->x.rp->index + lemp->nstate+lemp->nrule; break; 3217 + case ERROR: act = lemp->nstate + lemp->nrule*2; break; 3218 + case ACCEPT: act = lemp->nstate + lemp->nrule*2 + 1; break; 3224 3219 default: act = -1; break; 3225 3220 } 3226 3221 return act; 3227 3222 } 3228 3223 3229 3224 #define LINESIZE 1000 3230 3225 /* The next cluster of routines are for reading the template file ................................................................................ 3839 3834 tplt_xfer(lemp->name,in,out,&lineno); 3840 3835 3841 3836 /* Generate the defines */ 3842 3837 fprintf(out,"#define YYCODETYPE %s\n", 3843 3838 minimum_size_type(0, lemp->nsymbol+1, &szCodeType)); lineno++; 3844 3839 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++; 3845 3840 fprintf(out,"#define YYACTIONTYPE %s\n", 3846 - minimum_size_type(0, lemp->nstate+lemp->nrule+5, &szActionType)); lineno++; 3841 + minimum_size_type(0,lemp->nstate+lemp->nrule*2+5,&szActionType)); lineno++; 3847 3842 if( lemp->wildcard ){ 3848 3843 fprintf(out,"#define YYWILDCARD %d\n", 3849 3844 lemp->wildcard->index); lineno++; 3850 3845 } 3851 3846 print_stack_union(out,lemp,&lineno,mhflag); 3852 3847 fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++; 3853 3848 if( lemp->stacksize ){ ................................................................................ 3875 3870 fprintf(out,"#define %sARG_PDECL\n",name); lineno++; 3876 3871 fprintf(out,"#define %sARG_FETCH\n",name); lineno++; 3877 3872 fprintf(out,"#define %sARG_STORE\n",name); lineno++; 3878 3873 } 3879 3874 if( mhflag ){ 3880 3875 fprintf(out,"#endif\n"); lineno++; 3881 3876 } 3882 - fprintf(out,"#define YYNSTATE %d\n",lemp->nstate); lineno++; 3883 - fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++; 3884 3877 if( lemp->errsym->useCnt ){ 3885 - fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++; 3886 - fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++; 3878 + fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++; 3879 + fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++; 3887 3880 } 3888 3881 if( lemp->has_fallback ){ 3889 3882 fprintf(out,"#define YYFALLBACK 1\n"); lineno++; 3890 3883 } 3891 - tplt_xfer(lemp->name,in,out,&lineno); 3892 3884 3893 - /* Generate the action table and its associates: 3894 - ** 3895 - ** yy_action[] A single table containing all actions. 3896 - ** yy_lookahead[] A table containing the lookahead for each entry in 3897 - ** yy_action. Used to detect hash collisions. 3898 - ** yy_shift_ofst[] For each state, the offset into yy_action for 3899 - ** shifting terminals. 3900 - ** yy_reduce_ofst[] For each state, the offset into yy_action for 3901 - ** shifting non-terminals after a reduce. 3902 - ** yy_default[] Default action for each state. 3885 + /* Compute the action table, but do not output it yet. The action 3886 + ** table must be computed before generating the YYNSTATE macro because 3887 + ** we need to know how many states can be eliminated. 3903 3888 */ 3904 - 3905 - /* Compute the actions on all states and count them up */ 3906 - ax = (struct axset *) calloc(lemp->nstate*2, sizeof(ax[0])); 3889 + ax = (struct axset *) calloc(lemp->nxstate*2, sizeof(ax[0])); 3907 3890 if( ax==0 ){ 3908 3891 fprintf(stderr,"malloc failed\n"); 3909 3892 exit(1); 3910 3893 } 3911 - for(i=0; i<lemp->nstate; i++){ 3894 + for(i=0; i<lemp->nxstate; i++){ 3912 3895 stp = lemp->sorted[i]; 3913 3896 ax[i*2].stp = stp; 3914 3897 ax[i*2].isTkn = 1; 3915 3898 ax[i*2].nAction = stp->nTknAct; 3916 3899 ax[i*2+1].stp = stp; 3917 3900 ax[i*2+1].isTkn = 0; 3918 3901 ax[i*2+1].nAction = stp->nNtAct; 3919 3902 } 3920 3903 mxTknOfst = mnTknOfst = 0; 3921 3904 mxNtOfst = mnNtOfst = 0; 3922 - 3923 - /* Compute the action table. In order to try to keep the size of the 3924 - ** action table to a minimum, the heuristic of placing the largest action 3925 - ** sets first is used. 3926 - */ 3927 - for(i=0; i<lemp->nstate*2; i++) ax[i].iOrder = i; 3928 - qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare); 3905 + /* In an effort to minimize the action table size, use the heuristic 3906 + ** of placing the largest action sets first */ 3907 + for(i=0; i<lemp->nxstate*2; i++) ax[i].iOrder = i; 3908 + qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare); 3929 3909 pActtab = acttab_alloc(); 3930 - for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){ 3910 + for(i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++){ 3931 3911 stp = ax[i].stp; 3932 3912 if( ax[i].isTkn ){ 3933 3913 for(ap=stp->ap; ap; ap=ap->next){ 3934 3914 int action; 3935 3915 if( ap->sp->index>=lemp->nterminal ) continue; 3936 3916 action = compute_action(lemp, ap); 3937 3917 if( action<0 ) continue; ................................................................................ 3951 3931 } 3952 3932 stp->iNtOfst = acttab_insert(pActtab); 3953 3933 if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst; 3954 3934 if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; 3955 3935 } 3956 3936 } 3957 3937 free(ax); 3938 + 3939 + /* Finish rendering the constants now that the action table has 3940 + ** been computed */ 3941 + fprintf(out,"#define YYNSTATE %d\n",lemp->nxstate); lineno++; 3942 + fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++; 3943 + fprintf(out,"#define YY_MAX_SHIFT %d\n",lemp->nstate-1); lineno++; 3944 + fprintf(out,"#define YY_MIN_SHIFTREDUCE %d\n",lemp->nstate); lineno++; 3945 + i = lemp->nstate + lemp->nrule; 3946 + fprintf(out,"#define YY_MAX_SHIFTREDUCE %d\n", i-1); lineno++; 3947 + fprintf(out,"#define YY_MIN_REDUCE %d\n", i); lineno++; 3948 + i = lemp->nstate + lemp->nrule*2; 3949 + fprintf(out,"#define YY_MAX_REDUCE %d\n", i-1); lineno++; 3950 + fprintf(out,"#define YY_ERROR_ACTION %d\n", i); lineno++; 3951 + fprintf(out,"#define YY_ACCEPT_ACTION %d\n", i+1); lineno++; 3952 + fprintf(out,"#define YY_NO_ACTION %d\n", i+2); lineno++; 3953 + tplt_xfer(lemp->name,in,out,&lineno); 3954 + 3955 + /* Now output the action table and its associates: 3956 + ** 3957 + ** yy_action[] A single table containing all actions. 3958 + ** yy_lookahead[] A table containing the lookahead for each entry in 3959 + ** yy_action. Used to detect hash collisions. 3960 + ** yy_shift_ofst[] For each state, the offset into yy_action for 3961 + ** shifting terminals. 3962 + ** yy_reduce_ofst[] For each state, the offset into yy_action for 3963 + ** shifting non-terminals after a reduce. 3964 + ** yy_default[] Default action for each state. 3965 + */ 3958 3966 3959 3967 /* Output the yy_action table */ 3960 3968 lemp->nactiontab = n = acttab_size(pActtab); 3961 3969 lemp->tablesize += n*szActionType; 3962 3970 fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++; 3963 3971 fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++; 3964 3972 for(i=j=0; i<n; i++){ ................................................................................ 3990 3998 j++; 3991 3999 } 3992 4000 } 3993 4001 fprintf(out, "};\n"); lineno++; 3994 4002 3995 4003 /* Output the yy_shift_ofst[] table */ 3996 4004 fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++; 3997 - n = lemp->nstate; 4005 + n = lemp->nxstate; 3998 4006 while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--; 3999 4007 fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++; 4000 4008 fprintf(out, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst); lineno++; 4001 4009 fprintf(out, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst); lineno++; 4002 4010 fprintf(out, "static const %s yy_shift_ofst[] = {\n", 4003 4011 minimum_size_type(mnTknOfst-1, mxTknOfst, &sz)); lineno++; 4004 4012 lemp->tablesize += n*sz; ................................................................................ 4016 4024 j++; 4017 4025 } 4018 4026 } 4019 4027 fprintf(out, "};\n"); lineno++; 4020 4028 4021 4029 /* Output the yy_reduce_ofst[] table */ 4022 4030 fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++; 4023 - n = lemp->nstate; 4031 + n = lemp->nxstate; 4024 4032 while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--; 4025 4033 fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++; 4026 4034 fprintf(out, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst); lineno++; 4027 4035 fprintf(out, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst); lineno++; 4028 4036 fprintf(out, "static const %s yy_reduce_ofst[] = {\n", 4029 4037 minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++; 4030 4038 lemp->tablesize += n*sz; ................................................................................ 4042 4050 j++; 4043 4051 } 4044 4052 } 4045 4053 fprintf(out, "};\n"); lineno++; 4046 4054 4047 4055 /* Output the default action table */ 4048 4056 fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++; 4049 - n = lemp->nstate; 4057 + n = lemp->nxstate; 4050 4058 lemp->tablesize += n*szActionType; 4051 4059 for(i=j=0; i<n; i++){ 4052 4060 stp = lemp->sorted[i]; 4053 4061 if( j==0 ) fprintf(out," /* %5d */ ", i); 4054 - fprintf(out, " %4d,", stp->iDflt+n); 4062 + fprintf(out, " %4d,", stp->iDfltReduce+lemp->nstate+lemp->nrule); 4055 4063 if( j==9 || i==n-1 ){ 4056 4064 fprintf(out, "\n"); lineno++; 4057 4065 j = 0; 4058 4066 }else{ 4059 4067 j++; 4060 4068 } 4061 4069 } ................................................................................ 4280 4288 ** is a possible look-ahead. 4281 4289 */ 4282 4290 void CompressTables(struct lemon *lemp) 4283 4291 { 4284 4292 struct state *stp; 4285 4293 struct action *ap, *ap2; 4286 4294 struct rule *rp, *rp2, *rbest; 4287 - int nbest, n; 4295 + int nbest, n, nshift; 4288 4296 int i; 4289 4297 int usesWildcard; 4290 4298 4291 4299 for(i=0; i<lemp->nstate; i++){ 4292 4300 stp = lemp->sorted[i]; 4293 4301 nbest = 0; 4294 4302 rbest = 0; ................................................................................ 4328 4336 } 4329 4337 assert( ap ); 4330 4338 ap->sp = Symbol_new("{default}"); 4331 4339 for(ap=ap->next; ap; ap=ap->next){ 4332 4340 if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED; 4333 4341 } 4334 4342 stp->ap = Action_sort(stp->ap); 4343 + 4344 + for(ap=stp->ap; ap; ap=ap->next){ 4345 + if( ap->type==SHIFT ) break; 4346 + if( ap->type==REDUCE && ap->x.rp!=rbest ) break; 4347 + } 4348 + if( ap==0 ){ 4349 + stp->autoReduce = 1; 4350 + stp->pDfltReduce = rbest; 4351 + } 4352 + } 4353 + 4354 + /* Make a second pass over all states and actions. Convert 4355 + ** every action that is a SHIFT to an autoReduce state into 4356 + ** a SHIFTREDUCE action. 4357 + */ 4358 + for(i=0; i<lemp->nstate; i++){ 4359 + stp = lemp->sorted[i]; 4360 + for(ap=stp->ap; ap; ap=ap->next){ 4361 + struct state *pNextState; 4362 + if( ap->type!=SHIFT ) continue; 4363 + pNextState = ap->x.stp; 4364 + if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){ 4365 + ap->type = SHIFTREDUCE; 4366 + ap->x.rp = pNextState->pDfltReduce; 4367 + } 4368 + } 4335 4369 } 4336 4370 } 4337 4371 4338 4372 4339 4373 /* 4340 4374 ** Compare two states for sorting purposes. The smaller state is the 4341 4375 ** one with the most non-terminal actions. If they have the same number ................................................................................ 4368 4402 int i; 4369 4403 struct state *stp; 4370 4404 struct action *ap; 4371 4405 4372 4406 for(i=0; i<lemp->nstate; i++){ 4373 4407 stp = lemp->sorted[i]; 4374 4408 stp->nTknAct = stp->nNtAct = 0; 4375 - stp->iDflt = lemp->nrule; 4409 + stp->iDfltReduce = lemp->nrule; /* Init dflt action to "syntax error" */ 4376 4410 stp->iTknOfst = NO_OFFSET; 4377 4411 stp->iNtOfst = NO_OFFSET; 4378 4412 for(ap=stp->ap; ap; ap=ap->next){ 4379 - if( compute_action(lemp,ap)>=0 ){ 4413 + int iAction = compute_action(lemp,ap); 4414 + if( iAction>=0 ){ 4380 4415 if( ap->sp->index<lemp->nterminal ){ 4381 4416 stp->nTknAct++; 4382 4417 }else if( ap->sp->index<lemp->nsymbol ){ 4383 4418 stp->nNtAct++; 4384 4419 }else{ 4385 - stp->iDflt = compute_action(lemp, ap) - lemp->nstate; 4420 + assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp ); 4421 + stp->iDfltReduce = iAction - lemp->nstate - lemp->nrule; 4386 4422 } 4387 4423 } 4388 4424 } 4389 4425 } 4390 4426 qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]), 4391 4427 stateResortCompare); 4392 4428 for(i=0; i<lemp->nstate; i++){ 4393 4429 lemp->sorted[i]->statenum = i; 4430 + } 4431 + lemp->nxstate = lemp->nstate; 4432 + while( lemp->nxstate>1 && lemp->sorted[lemp->nxstate-1]->autoReduce ){ 4433 + lemp->nxstate--; 4394 4434 } 4395 4435 } 4396 4436 4397 4437 4398 4438 /***************** From the file "set.c" ************************************/ 4399 4439 /* 4400 4440 ** Set manipulation routines for the LEMON parser generator.
Changes to tool/lempar.c.
46 46 ** for base tokens is called "yy0". 47 47 ** YYSTACKDEPTH is the maximum depth of the parser's stack. If 48 48 ** zero the stack is dynamically sized using realloc() 49 49 ** ParseARG_SDECL A static variable declaration for the %extra_argument 50 50 ** ParseARG_PDECL A parameter declaration for the %extra_argument 51 51 ** ParseARG_STORE Code to store %extra_argument into yypParser 52 52 ** ParseARG_FETCH Code to extract %extra_argument from yypParser 53 -** YYNSTATE the combined number of states. 54 -** YYNRULE the number of rules in the grammar 55 53 ** YYERRORSYMBOL is the code number of the error symbol. If not 56 54 ** defined, then do no error processing. 55 +** YYNSTATE the combined number of states. 56 +** YYNRULE the number of rules in the grammar 57 +** YY_MAX_SHIFT Maximum value for shift actions 58 +** YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions 59 +** YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions 60 +** YY_MIN_REDUCE Maximum value for reduce actions 61 +** YY_ERROR_ACTION The yy_action[] code for syntax error 62 +** YY_ACCEPT_ACTION The yy_action[] code for accept 63 +** YY_NO_ACTION The yy_action[] code for no-op 57 64 */ 58 65 %% 59 -#define YY_NO_ACTION (YYNSTATE+YYNRULE+2) 60 -#define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) 61 -#define YY_ERROR_ACTION (YYNSTATE+YYNRULE) 62 66 63 67 /* The yyzerominor constant is used to initialize instances of 64 68 ** YYMINORTYPE objects to zero. */ 65 69 static const YYMINORTYPE yyzerominor = { 0 }; 66 70 67 71 /* Define the yytestcase() macro to be a no-op if is not already defined 68 72 ** otherwise. ................................................................................ 81 85 ** current state and lookahead token. These tables are used to implement 82 86 ** functions that take a state number and lookahead value and return an 83 87 ** action integer. 84 88 ** 85 89 ** Suppose the action integer is N. Then the action is determined as 86 90 ** follows 87 91 ** 88 -** 0 <= N < YYNSTATE Shift N. That is, push the lookahead 92 +** 0 <= N <= YY_MAX_SHIFT Shift N. That is, push the lookahead 89 93 ** token onto the stack and goto state N. 90 94 ** 91 -** YYNSTATE <= N < YYNSTATE+YYNRULE Reduce by rule N-YYNSTATE. 95 +** N between YY_MIN_SHIFTREDUCE Shift to an arbitrary state then 96 +** and YY_MAX_SHIFTREDUCE reduce by rule N-YY_MIN_SHIFTREDUCE. 92 97 ** 93 -** N == YYNSTATE+YYNRULE A syntax error has occurred. 98 +** N between YY_MIN_REDUCE Reduce by rule N-YY_MIN_REDUCE 99 +** and YY_MAX_REDUCE 100 + 101 +** N == YY_ERROR_ACTION A syntax error has occurred. 94 102 ** 95 -** N == YYNSTATE+YYNRULE+1 The parser accepts its input. 103 +** N == YY_ACCEPT_ACTION The parser accepts its input. 96 104 ** 97 -** N == YYNSTATE+YYNRULE+2 No such action. Denotes unused 105 +** N == YY_NO_ACTION No such action. Denotes unused 98 106 ** slots in the yy_action[] table. 99 107 ** 100 108 ** The action table is constructed as a single large table named yy_action[]. 101 109 ** Given state S and lookahead X, the action is computed as 102 110 ** 103 111 ** yy_action[ yy_shift_ofst[S] + X ] 104 112 ** ................................................................................ 149 157 ** 150 158 ** + The value of the token stored at this level of the stack. 151 159 ** (In other words, the "major" token.) 152 160 ** 153 161 ** + The semantic value stored at this level of the stack. This is 154 162 ** the information used by the action routines in the grammar. 155 163 ** It is sometimes called the "minor" token. 164 +** 165 +** After the "shift" half of a SHIFTREDUCE action, the stateno field 166 +** actually contains the reduce action for the second half of the 167 +** SHIFTREDUCE. 156 168 */ 157 169 struct yyStackEntry { 158 - YYACTIONTYPE stateno; /* The state-number */ 170 + YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ 159 171 YYCODETYPE major; /* The major token value. This is the code 160 172 ** number for the token at this stack level */ 161 173 YYMINORTYPE minor; /* The user-supplied minor token value. This 162 174 ** is the value of the token */ 163 175 }; 164 176 typedef struct yyStackEntry yyStackEntry; 165 177 ................................................................................ 380 392 */ 381 393 static int yy_find_shift_action( 382 394 yyParser *pParser, /* The parser */ 383 395 YYCODETYPE iLookAhead /* The look-ahead token */ 384 396 ){ 385 397 int i; 386 398 int stateno = pParser->yystack[pParser->yyidx].stateno; 387 - 388 - if( stateno>YY_SHIFT_COUNT 389 - || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){ 390 - return yy_default[stateno]; 391 - } 399 + 400 + if( stateno>=YY_MIN_REDUCE ) return stateno; 401 + assert( stateno <= YY_SHIFT_COUNT ); 402 + i = yy_shift_ofst[stateno]; 403 + if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno]; 392 404 assert( iLookAhead!=YYNOCODE ); 393 405 i += iLookAhead; 394 406 if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ 395 407 if( iLookAhead>0 ){ 396 408 #ifdef YYFALLBACK 397 409 YYCODETYPE iFallback; /* Fallback token */ 398 410 if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0]) ................................................................................ 485 497 /* Here code is inserted which will execute if the parser 486 498 ** stack every overflows */ 487 499 %% 488 500 ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ 489 501 } 490 502 491 503 /* 492 -** Perform a shift action. 504 +** Print tracing information for a SHIFT action 505 +*/ 506 +#ifndef NDEBUG 507 +static void yyTraceShift(yyParser *yypParser, int yyNewState){ 508 + if( yyTraceFILE ){ 509 + int i; 510 + if( yyNewState<YYNSTATE ){ 511 + fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 512 + fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 513 + for(i=1; i<=yypParser->yyidx; i++) 514 + fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 515 + fprintf(yyTraceFILE,"\n"); 516 + }else{ 517 + fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 518 + } 519 + } 520 +} 521 +#else 522 +# define yyTraceShift(X,Y) 523 +#endif 524 + 525 +/* 526 +** Perform a shift action. Return the number of errors. 493 527 */ 494 528 static void yy_shift( 495 529 yyParser *yypParser, /* The parser to be shifted */ 496 530 int yyNewState, /* The new state to shift in */ 497 531 int yyMajor, /* The major token to shift in */ 498 532 YYMINORTYPE *yypMinor /* Pointer to the minor token to shift in */ 499 533 ){ ................................................................................ 518 552 } 519 553 } 520 554 #endif 521 555 yytos = &yypParser->yystack[yypParser->yyidx]; 522 556 yytos->stateno = (YYACTIONTYPE)yyNewState; 523 557 yytos->major = (YYCODETYPE)yyMajor; 524 558 yytos->minor = *yypMinor; 525 -#ifndef NDEBUG 526 - if( yyTraceFILE && yypParser->yyidx>0 ){ 527 - int i; 528 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 529 - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 530 - for(i=1; i<=yypParser->yyidx; i++) 531 - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 532 - fprintf(yyTraceFILE,"\n"); 533 - } 534 -#endif 559 + yyTraceShift(yypParser, yyNewState); 535 560 } 536 561 537 562 /* The following table contains information about every rule that 538 563 ** is used during the reduce. 539 564 */ 540 565 static const struct { 541 566 YYCODETYPE lhs; /* Symbol on the left-hand side of the rule */ ................................................................................ 560 585 yyStackEntry *yymsp; /* The top of the parser's stack */ 561 586 int yysize; /* Amount to pop the stack */ 562 587 ParseARG_FETCH; 563 588 yymsp = &yypParser->yystack[yypParser->yyidx]; 564 589 #ifndef NDEBUG 565 590 if( yyTraceFILE && yyruleno>=0 566 591 && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ 567 - fprintf(yyTraceFILE, "%sReduce [%s].\n", yyTracePrompt, 568 - yyRuleName[yyruleno]); 592 + yysize = yyRuleInfo[yyruleno].nrhs; 593 + fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt, 594 + yyRuleName[yyruleno], yymsp[-yysize].stateno); 569 595 } 570 596 #endif /* NDEBUG */ 571 597 572 598 /* Silence complaints from purify about yygotominor being uninitialized 573 599 ** in some cases when it is copied into the stack after the following 574 600 ** switch. yygotominor is uninitialized when a rule reduces that does 575 601 ** not set the value of its left-hand side nonterminal. Leaving the ................................................................................ 598 624 */ 599 625 %% 600 626 }; 601 627 yygoto = yyRuleInfo[yyruleno].lhs; 602 628 yysize = yyRuleInfo[yyruleno].nrhs; 603 629 yypParser->yyidx -= yysize; 604 630 yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); 605 - if( yyact < YYNSTATE ){ 606 -#ifdef NDEBUG 607 - /* If we are not debugging and the reduce action popped at least 631 + if( yyact <= YY_MAX_SHIFTREDUCE ){ 632 + if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 633 + /* If the reduce action popped at least 608 634 ** one element off the stack, then we can push the new element back 609 635 ** onto the stack here, and skip the stack overflow test in yy_shift(). 610 636 ** That gives a significant speed improvement. */ 611 637 if( yysize ){ 612 638 yypParser->yyidx++; 613 639 yymsp -= yysize-1; 614 640 yymsp->stateno = (YYACTIONTYPE)yyact; 615 641 yymsp->major = (YYCODETYPE)yygoto; 616 642 yymsp->minor = yygotominor; 617 - }else 618 -#endif 619 - { 643 + yyTraceShift(yypParser, yyact); 644 + }else{ 620 645 yy_shift(yypParser,yyact,yygoto,&yygotominor); 621 646 } 622 647 }else{ 623 - assert( yyact == YYNSTATE + YYNRULE + 1 ); 648 + assert( yyact == YY_ACCEPT_ACTION ); 624 649 yy_accept(yypParser); 625 650 } 626 651 } 627 652 628 653 /* 629 654 ** The following code executes when the parse fails 630 655 */ ................................................................................ 736 761 if( yyTraceFILE ){ 737 762 fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); 738 763 } 739 764 #endif 740 765 741 766 do{ 742 767 yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); 743 - if( yyact<YYNSTATE ){ 744 - assert( !yyendofinput ); /* Impossible to shift the $ token */ 768 + if( yyact <= YY_MAX_SHIFTREDUCE ){ 769 + if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 745 770 yy_shift(yypParser,yyact,yymajor,&yyminorunion); 746 771 yypParser->yyerrcnt--; 747 772 yymajor = YYNOCODE; 748 - }else if( yyact < YYNSTATE + YYNRULE ){ 749 - yy_reduce(yypParser,yyact-YYNSTATE); 773 + }else if( yyact <= YY_MAX_REDUCE ){ 774 + yy_reduce(yypParser,yyact-YY_MIN_REDUCE); 750 775 }else{ 751 776 assert( yyact == YY_ERROR_ACTION ); 752 777 #ifdef YYERRORSYMBOL 753 778 int yymx; 754 779 #endif 755 780 #ifndef NDEBUG 756 781 if( yyTraceFILE ){ ................................................................................ 792 817 yymajor = YYNOCODE; 793 818 }else{ 794 819 while( 795 820 yypParser->yyidx >= 0 && 796 821 yymx != YYERRORSYMBOL && 797 822 (yyact = yy_find_reduce_action( 798 823 yypParser->yystack[yypParser->yyidx].stateno, 799 - YYERRORSYMBOL)) >= YYNSTATE 824 + YYERRORSYMBOL)) >= YY_MIN_REDUCE 800 825 ){ 801 826 yy_pop_parser_stack(yypParser); 802 827 } 803 828 if( yypParser->yyidx < 0 || yymajor==0 ){ 804 829 yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 805 830 yy_parse_failed(yypParser); 806 831 yymajor = YYNOCODE; ................................................................................ 842 867 if( yyendofinput ){ 843 868 yy_parse_failed(yypParser); 844 869 } 845 870 yymajor = YYNOCODE; 846 871 #endif 847 872 } 848 873 }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); 874 +#ifndef NDEBUG 875 + if( yyTraceFILE ){ 876 + fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt); 877 + } 878 +#endif 849 879 return; 850 880 }