Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Change the parser engine so that it (once again) waits for a lookahead token before reducing, even in a SHIFTREDUCE action. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | lemon-update |
| Files: | files | file ages | folders |
| SHA1: |
2c17a1358353a0845b039283be79353f |
| User & Date: | drh 2015-09-07 19:52:55 |
Context
|
2015-09-07
| ||
| 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 | |
Changes
Changes to src/lempar.c.
163 163 ** 164 164 ** + The value of the token stored at this level of the stack. 165 165 ** (In other words, the "major" token.) 166 166 ** 167 167 ** + The semantic value stored at this level of the stack. This is 168 168 ** the information used by the action routines in the grammar. 169 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. 170 174 */ 171 175 struct yyStackEntry { 172 - YYACTIONTYPE stateno; /* The state-number */ 176 + YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ 173 177 YYCODETYPE major; /* The major token value. This is the code 174 178 ** number for the token at this stack level */ 175 179 YYMINORTYPE minor; /* The user-supplied minor token value. This 176 180 ** is the value of the token */ 177 181 }; 178 182 typedef struct yyStackEntry yyStackEntry; 179 183 ................................................................................ 399 403 static int yy_find_shift_action( 400 404 yyParser *pParser, /* The parser */ 401 405 YYCODETYPE iLookAhead /* The look-ahead token */ 402 406 ){ 403 407 int i; 404 408 int stateno = pParser->yystack[pParser->yyidx].stateno; 405 409 410 + if( stateno>=YY_MIN_REDUCE ) return stateno; 406 411 if( stateno>YY_SHIFT_COUNT 407 412 || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){ 408 413 return yy_default[stateno]; 409 414 } 410 415 assert( iLookAhead!=YYNOCODE ); 411 416 i += iLookAhead; 412 417 if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ ................................................................................ 502 507 while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 503 508 /* Here code is inserted which will execute if the parser 504 509 ** stack every overflows */ 505 510 %% 506 511 ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ 507 512 } 508 513 514 +/* 515 +** Print tracing information for a SHIFT action 516 +*/ 517 +#ifndef NDEBUG 518 +static void yyTraceShift(yyParser *yypParser, int yyNewState){ 519 + if( yyTraceFILE ){ 520 + int i; 521 + if( yyNewState<YYNSTATE ){ 522 + fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 523 + fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 524 + for(i=1; i<=yypParser->yyidx; i++) 525 + fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 526 + fprintf(yyTraceFILE,"\n"); 527 + }else{ 528 + fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 529 + } 530 + } 531 +} 532 +#else 533 +# define yyTraceShift(X,Y) 534 +#endif 535 + 509 536 /* 510 537 ** Perform a shift action. Return the number of errors. 511 538 */ 512 -static int yy_shift( 539 +static void yy_shift( 513 540 yyParser *yypParser, /* The parser to be shifted */ 514 541 int yyNewState, /* The new state to shift in */ 515 542 int yyMajor, /* The major token to shift in */ 516 543 YYMINORTYPE *yypMinor /* Pointer to the minor token to shift in */ 517 544 ){ 518 545 yyStackEntry *yytos; 519 546 yypParser->yyidx++; ................................................................................ 521 548 if( yypParser->yyidx>yypParser->yyidxMax ){ 522 549 yypParser->yyidxMax = yypParser->yyidx; 523 550 } 524 551 #endif 525 552 #if YYSTACKDEPTH>0 526 553 if( yypParser->yyidx>=YYSTACKDEPTH ){ 527 554 yyStackOverflow(yypParser, yypMinor); 528 - return 1; 555 + return; 529 556 } 530 557 #else 531 558 if( yypParser->yyidx>=yypParser->yystksz ){ 532 559 yyGrowStack(yypParser); 533 560 if( yypParser->yyidx>=yypParser->yystksz ){ 534 561 yyStackOverflow(yypParser, yypMinor); 535 - return 1; 562 + return; 536 563 } 537 564 } 538 565 #endif 539 566 yytos = &yypParser->yystack[yypParser->yyidx]; 540 567 yytos->stateno = (YYACTIONTYPE)yyNewState; 541 568 yytos->major = (YYCODETYPE)yyMajor; 542 569 yytos->minor = *yypMinor; 543 -#ifndef NDEBUG 544 - if( yyTraceFILE && yypParser->yyidx>0 ){ 545 - int i; 546 - if( yyNewState<YYNSTATE ){ 547 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 548 - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 549 - for(i=1; i<=yypParser->yyidx; i++) 550 - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 551 - fprintf(yyTraceFILE,"\n"); 552 - }else{ 553 - fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 554 - } 555 - } 556 -#endif 557 - return 0; 570 + yyTraceShift(yypParser, yyNewState); 558 571 } 559 572 560 573 /* The following table contains information about every rule that 561 574 ** is used during the reduce. 562 575 */ 563 576 static const struct { 564 577 YYCODETYPE lhs; /* Symbol on the left-hand side of the rule */ ................................................................................ 624 637 }; 625 638 assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); 626 639 yygoto = yyRuleInfo[yyruleno].lhs; 627 640 yysize = yyRuleInfo[yyruleno].nrhs; 628 641 yypParser->yyidx -= yysize; 629 642 yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); 630 643 if( yyact <= YY_MAX_SHIFTREDUCE ){ 644 + if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 631 645 /* If the reduce action popped at least 632 646 ** one element off the stack, then we can push the new element back 633 647 ** onto the stack here, and skip the stack overflow test in yy_shift(). 634 648 ** That gives a significant speed improvement. */ 635 649 if( yysize ){ 636 650 yypParser->yyidx++; 637 651 yymsp -= yysize-1; 638 652 yymsp->stateno = (YYACTIONTYPE)yyact; 639 653 yymsp->major = (YYCODETYPE)yygoto; 640 654 yymsp->minor = yygotominor; 641 -#ifndef NDEBUG 642 - if( yyTraceFILE ){ 643 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyact); 644 - } 645 -#endif 655 + yyTraceShift(yypParser, yyact); 646 656 }else{ 647 - if( yy_shift(yypParser,yyact,yygoto,&yygotominor) ) yyact = 0; 648 - } 649 - if( yyact>=YY_MIN_SHIFTREDUCE ){ 650 - yy_reduce(yypParser, yyact - YY_MIN_SHIFTREDUCE); 657 + yy_shift(yypParser,yyact,yygoto,&yygotominor); 651 658 } 652 659 }else{ 653 660 assert( yyact == YY_ACCEPT_ACTION ); 654 661 yy_accept(yypParser); 655 662 } 656 663 } 657 664 ................................................................................ 771 778 fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); 772 779 } 773 780 #endif 774 781 775 782 do{ 776 783 yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); 777 784 if( yyact <= YY_MAX_SHIFTREDUCE ){ 778 - if( yy_shift(yypParser,yyact,yymajor,&yyminorunion)==0 ){ 779 - yypParser->yyerrcnt--; 780 - yymajor = YYNOCODE; 781 - if( yyact > YY_MAX_SHIFT ){ 782 - yy_reduce(yypParser, yyact-YY_MIN_SHIFTREDUCE); 783 - } 784 - } 785 + if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 786 + yy_shift(yypParser,yyact,yymajor,&yyminorunion); 787 + yypParser->yyerrcnt--; 788 + yymajor = YYNOCODE; 785 789 }else if( yyact <= YY_MAX_REDUCE ){ 786 790 yy_reduce(yypParser,yyact-YY_MIN_REDUCE); 787 791 }else{ 788 792 assert( yyact == YY_ERROR_ACTION ); 789 793 #ifdef YYERRORSYMBOL 790 794 int yymx; 791 795 #endif ................................................................................ 879 883 if( yyendofinput ){ 880 884 yy_parse_failed(yypParser); 881 885 } 882 886 yymajor = YYNOCODE; 883 887 #endif 884 888 } 885 889 }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); 886 -#ifdef SQLITE_DEBUG 890 +#ifndef NDEBUG 887 891 if( yyTraceFILE ){ 888 892 fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt); 889 893 } 890 894 #endif 891 895 return; 892 896 }
Changes to src/parse.y.
583 583 } 584 584 585 585 // "seltablist" is a "Select Table List" - the content of the FROM clause 586 586 // in a SELECT statement. "stl_prefix" is a prefix of this list. 587 587 // 588 588 stl_prefix(A) ::= seltablist(X) joinop(Y). { 589 589 A = X; 590 - if( A && A->nSrc>0 ) A->a[A->nSrc-1].fg.jointype = (u8)Y; 590 + if( ALWAYS(A && A->nSrc>0) ) A->a[A->nSrc-1].fg.jointype = (u8)Y; 591 591 } 592 592 stl_prefix(A) ::= . {A = 0;} 593 593 seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) indexed_opt(I) 594 594 on_opt(N) using_opt(U). { 595 595 A = sqlite3SrcListAppendFromTerm(pParse,X,&Y,&D,&Z,0,N,U); 596 596 sqlite3SrcListIndexedBy(pParse, A, &I); 597 597 }
Changes to src/tokenize.c.
455 455 } 456 456 abort_parse: 457 457 assert( nErr==0 ); 458 458 if( pParse->rc==SQLITE_OK && db->mallocFailed==0 ){ 459 459 assert( zSql[i]==0 ); 460 460 if( lastTokenParsed!=TK_SEMI ){ 461 461 sqlite3Parser(pEngine, TK_SEMI, pParse->sLastToken, pParse); 462 + pParse->zTail = &zSql[i]; 462 463 } 463 464 if( pParse->rc==SQLITE_OK && db->mallocFailed==0 ){ 464 465 sqlite3Parser(pEngine, 0, pParse->sLastToken, pParse); 465 466 } 466 467 } 467 - pParse->zTail = &zSql[i]; 468 468 #ifdef YYTRACKMAXSTACKDEPTH 469 469 sqlite3_mutex_enter(sqlite3MallocMutex()); 470 470 sqlite3StatusSet(SQLITE_STATUS_PARSER_STACK, 471 471 sqlite3ParserStackPeak(pEngine) 472 472 ); 473 473 sqlite3_mutex_leave(sqlite3MallocMutex()); 474 474 #endif /* YYDEBUG */
Changes to test/misc1.test.
642 642 # 2015-03-22: NULL pointer dereference after a syntax error 643 643 # 644 644 do_catchsql_test misc1-21.1 { 645 645 select''like''like''like#0; 646 646 } {1 {near "#0": syntax error}} 647 647 do_catchsql_test misc1-21.2 { 648 648 VALUES(0,0x0MATCH#0; 649 -} {1 {near "#0": syntax error}} 649 +} {1 {near ";": syntax error}} 650 650 651 651 # 2015-04-15 652 652 do_execsql_test misc1-22.1 { 653 653 SELECT ""+3 FROM (SELECT ""+5); 654 654 } {3} 655 655 656 656 # 2015-04-19: NULL pointer dereference on a corrupt schema
Changes to tool/lempar.c.
157 157 ** 158 158 ** + The value of the token stored at this level of the stack. 159 159 ** (In other words, the "major" token.) 160 160 ** 161 161 ** + The semantic value stored at this level of the stack. This is 162 162 ** the information used by the action routines in the grammar. 163 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. 164 168 */ 165 169 struct yyStackEntry { 166 - YYACTIONTYPE stateno; /* The state-number */ 170 + YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ 167 171 YYCODETYPE major; /* The major token value. This is the code 168 172 ** number for the token at this stack level */ 169 173 YYMINORTYPE minor; /* The user-supplied minor token value. This 170 174 ** is the value of the token */ 171 175 }; 172 176 typedef struct yyStackEntry yyStackEntry; 173 177 ................................................................................ 388 392 */ 389 393 static int yy_find_shift_action( 390 394 yyParser *pParser, /* The parser */ 391 395 YYCODETYPE iLookAhead /* The look-ahead token */ 392 396 ){ 393 397 int i; 394 398 int stateno = pParser->yystack[pParser->yyidx].stateno; 395 - 399 + 400 + if( stateno>=YY_MIN_REDUCE ) return stateno; 396 401 if( stateno>YY_SHIFT_COUNT 397 402 || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){ 398 403 return yy_default[stateno]; 399 404 } 400 405 assert( iLookAhead!=YYNOCODE ); 401 406 i += iLookAhead; 402 407 if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ ................................................................................ 492 497 while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 493 498 /* Here code is inserted which will execute if the parser 494 499 ** stack every overflows */ 495 500 %% 496 501 ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ 497 502 } 498 503 504 +/* 505 +** Print tracing information for a SHIFT action 506 +*/ 507 +#ifndef NDEBUG 508 +static void yyTraceShift(yyParser *yypParser, int yyNewState){ 509 + if( yyTraceFILE ){ 510 + int i; 511 + if( yyNewState<YYNSTATE ){ 512 + fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 513 + fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 514 + for(i=1; i<=yypParser->yyidx; i++) 515 + fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 516 + fprintf(yyTraceFILE,"\n"); 517 + }else{ 518 + fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 519 + } 520 + } 521 +} 522 +#else 523 +# define yyTraceShift(X,Y) 524 +#endif 525 + 499 526 /* 500 527 ** Perform a shift action. Return the number of errors. 501 528 */ 502 -static int yy_shift( 529 +static void yy_shift( 503 530 yyParser *yypParser, /* The parser to be shifted */ 504 531 int yyNewState, /* The new state to shift in */ 505 532 int yyMajor, /* The major token to shift in */ 506 533 YYMINORTYPE *yypMinor /* Pointer to the minor token to shift in */ 507 534 ){ 508 535 yyStackEntry *yytos; 509 536 yypParser->yyidx++; ................................................................................ 511 538 if( yypParser->yyidx>yypParser->yyidxMax ){ 512 539 yypParser->yyidxMax = yypParser->yyidx; 513 540 } 514 541 #endif 515 542 #if YYSTACKDEPTH>0 516 543 if( yypParser->yyidx>=YYSTACKDEPTH ){ 517 544 yyStackOverflow(yypParser, yypMinor); 518 - return 1; 545 + return; 519 546 } 520 547 #else 521 548 if( yypParser->yyidx>=yypParser->yystksz ){ 522 549 yyGrowStack(yypParser); 523 550 if( yypParser->yyidx>=yypParser->yystksz ){ 524 551 yyStackOverflow(yypParser, yypMinor); 525 - return 1; 552 + return; 526 553 } 527 554 } 528 555 #endif 529 556 yytos = &yypParser->yystack[yypParser->yyidx]; 530 557 yytos->stateno = (YYACTIONTYPE)yyNewState; 531 558 yytos->major = (YYCODETYPE)yyMajor; 532 559 yytos->minor = *yypMinor; 533 -#ifndef NDEBUG 534 - if( yyTraceFILE && yypParser->yyidx>0 ){ 535 - int i; 536 - if( yyNewState<YYNSTATE ){ 537 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 538 - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 539 - for(i=1; i<=yypParser->yyidx; i++) 540 - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 541 - fprintf(yyTraceFILE,"\n"); 542 - }else{ 543 - fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 544 - } 545 - } 546 -#endif 547 - return 0; 560 + yyTraceShift(yypParser, yyNewState); 548 561 } 549 562 550 563 /* The following table contains information about every rule that 551 564 ** is used during the reduce. 552 565 */ 553 566 static const struct { 554 567 YYCODETYPE lhs; /* Symbol on the left-hand side of the rule */ ................................................................................ 612 625 */ 613 626 %% 614 627 }; 615 628 yygoto = yyRuleInfo[yyruleno].lhs; 616 629 yysize = yyRuleInfo[yyruleno].nrhs; 617 630 yypParser->yyidx -= yysize; 618 631 yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); 619 - if( yyact < YY_MAX_SHIFTREDUCE ){ 632 + if( yyact <= YY_MAX_SHIFTREDUCE ){ 633 + if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 620 634 /* If the reduce action popped at least 621 635 ** one element off the stack, then we can push the new element back 622 636 ** onto the stack here, and skip the stack overflow test in yy_shift(). 623 637 ** That gives a significant speed improvement. */ 624 638 if( yysize ){ 625 639 yypParser->yyidx++; 626 640 yymsp -= yysize-1; 627 641 yymsp->stateno = (YYACTIONTYPE)yyact; 628 642 yymsp->major = (YYCODETYPE)yygoto; 629 643 yymsp->minor = yygotominor; 630 -#ifndef NDEBUG 631 - if( yyTraceFILE ){ 632 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyact); 633 - } 634 -#endif 644 + yyTraceShift(yypParser, yyact); 635 645 }else{ 636 - if( yy_shift(yypParser,yyact,yygoto,&yygotominor) ) yyact = 0; 637 - } 638 - if( yyact>=YY_MIN_SHIFTREDUCE ){ 639 - yy_reduce(yypParser, yyact - YY_MIN_SHIFTREDUCE); 646 + yy_shift(yypParser,yyact,yygoto,&yygotominor); 640 647 } 641 648 }else{ 642 649 assert( yyact == YY_ACCEPT_ACTION ); 643 650 yy_accept(yypParser); 644 651 } 645 652 } 646 653 ................................................................................ 756 763 fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); 757 764 } 758 765 #endif 759 766 760 767 do{ 761 768 yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); 762 769 if( yyact <= YY_MAX_SHIFTREDUCE ){ 763 - if( yy_shift(yypParser,yyact,yymajor,&yyminorunion)==0 ){ 764 - yypParser->yyerrcnt--; 765 - yymajor = YYNOCODE; 766 - if( yyact > YY_MAX_SHIFT ){ 767 - yy_reduce(yypParser, yyact-YY_MIN_SHIFTREDUCE); 768 - } 769 - } 770 + if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 771 + yy_shift(yypParser,yyact,yymajor,&yyminorunion); 772 + yypParser->yyerrcnt--; 773 + yymajor = YYNOCODE; 770 774 }else if( yyact <= YY_MAX_REDUCE ){ 771 775 yy_reduce(yypParser,yyact-YY_MIN_REDUCE); 772 776 }else{ 773 777 assert( yyact == YY_ERROR_ACTION ); 774 778 #ifdef YYERRORSYMBOL 775 779 int yymx; 776 780 #endif