Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Performance improvements on the main loop of the LEMON-generated parser. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA3-256: |
fec1ebadeb9d6b55b19a1c159c543fd7 |
| User & Date: | drh 2018-04-21 22:40:08 |
Context
|
2018-04-23
| ||
| 00:25 | Fix an unreachable branch associated with stack overflow in the LEMON-generated parser. (check-in: e3064ba3 user: drh tags: trunk) | |
|
2018-04-21
| ||
| 22:40 | Performance improvements on the main loop of the LEMON-generated parser. (check-in: fec1ebad user: drh tags: trunk) | |
| 20:24 | Enhance LEMON to track which symbols actually carry semantic content. Output the list of symbols that do not carry content at the end of the report, but do not (yet) do anything else with the information. (check-in: dcf2bafc user: drh tags: trunk) | |
Changes
Changes to tool/lempar.c.
501 501 } 502 502 #endif 503 503 504 504 /* 505 505 ** Find the appropriate action for a parser given the terminal 506 506 ** look-ahead token iLookAhead. 507 507 */ 508 -static unsigned int yy_find_shift_action( 509 - yyParser *pParser, /* The parser */ 510 - YYCODETYPE iLookAhead /* The look-ahead token */ 508 +static YYACTIONTYPE yy_find_shift_action( 509 + YYCODETYPE iLookAhead, /* The look-ahead token */ 510 + YYACTIONTYPE stateno /* Current state number */ 511 511 ){ 512 512 int i; 513 - int stateno = pParser->yytos->stateno; 514 - 513 + 515 514 if( stateno>YY_MAX_SHIFT ) return stateno; 516 515 assert( stateno <= YY_SHIFT_COUNT ); 517 516 #if defined(YYCOVERAGE) 518 517 yycoverage[stateno][iLookAhead] = 1; 519 518 #endif 520 519 do{ 521 520 i = yy_shift_ofst[stateno]; ................................................................................ 571 570 } 572 571 573 572 /* 574 573 ** Find the appropriate action for a parser given the non-terminal 575 574 ** look-ahead token iLookAhead. 576 575 */ 577 576 static int yy_find_reduce_action( 578 - int stateno, /* Current state number */ 577 + YYACTIONTYPE stateno, /* Current state number */ 579 578 YYCODETYPE iLookAhead /* The look-ahead token */ 580 579 ){ 581 580 int i; 582 581 #ifdef YYERRORSYMBOL 583 582 if( stateno>YY_REDUCE_COUNT ){ 584 583 return yy_default[stateno]; 585 584 } ................................................................................ 643 642 #endif 644 643 645 644 /* 646 645 ** Perform a shift action. 647 646 */ 648 647 static void yy_shift( 649 648 yyParser *yypParser, /* The parser to be shifted */ 650 - int yyNewState, /* The new state to shift in */ 651 - int yyMajor, /* The major token to shift in */ 649 + YYACTIONTYPE yyNewState, /* The new state to shift in */ 650 + YYCODETYPE yyMajor, /* The major token to shift in */ 652 651 ParseTOKENTYPE yyMinor /* The minor token to shift in */ 653 652 ){ 654 653 yyStackEntry *yytos; 655 654 yypParser->yytos++; 656 655 #ifdef YYTRACKMAXSTACKDEPTH 657 656 if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){ 658 657 yypParser->yyhwm++; ................................................................................ 674 673 } 675 674 } 676 675 #endif 677 676 if( yyNewState > YY_MAX_SHIFT ){ 678 677 yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 679 678 } 680 679 yytos = yypParser->yytos; 681 - yytos->stateno = (YYACTIONTYPE)yyNewState; 682 - yytos->major = (YYCODETYPE)yyMajor; 680 + yytos->stateno = yyNewState; 681 + yytos->major = yyMajor; 683 682 yytos->minor.yy0 = yyMinor; 684 683 yyTraceShift(yypParser, yyNewState, "Shift"); 685 684 } 686 685 687 686 /* The following table contains information about every rule that 688 687 ** is used during the reduce. 689 688 */ ................................................................................ 702 701 ** 703 702 ** The yyLookahead and yyLookaheadToken parameters provide reduce actions 704 703 ** access to the lookahead token (if any). The yyLookahead will be YYNOCODE 705 704 ** if the lookahead token has already been consumed. As this procedure is 706 705 ** only called from one place, optimizing compilers will in-line it, which 707 706 ** means that the extra parameters have no performance impact. 708 707 */ 709 -static void yy_reduce( 708 +static YYACTIONTYPE yy_reduce( 710 709 yyParser *yypParser, /* The parser */ 711 710 unsigned int yyruleno, /* Number of the rule by which to reduce */ 712 711 int yyLookahead, /* Lookahead token, or YYNOCODE if none */ 713 712 ParseTOKENTYPE yyLookaheadToken /* Value of the lookahead token */ 714 713 ParseCTX_PDECL /* %extra_context */ 715 714 ){ 716 715 int yygoto; /* The next state */ ................................................................................ 744 743 yypParser->yyhwm++; 745 744 assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack)); 746 745 } 747 746 #endif 748 747 #if YYSTACKDEPTH>0 749 748 if( yypParser->yytos>=yypParser->yystackEnd ){ 750 749 yyStackOverflow(yypParser); 751 - return; 750 + return YY_ACCEPT_ACTION; 752 751 } 753 752 #else 754 753 if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){ 755 754 if( yyGrowStack(yypParser) ){ 756 755 yyStackOverflow(yypParser); 757 - return; 756 + return YY_ACCEPT_ACTION; 758 757 } 759 758 yymsp = yypParser->yytos; 760 759 } 761 760 #endif 762 761 } 763 762 764 763 switch( yyruleno ){ ................................................................................ 787 786 assert( yyact!=YY_ERROR_ACTION ); 788 787 789 788 yymsp += yysize+1; 790 789 yypParser->yytos = yymsp; 791 790 yymsp->stateno = (YYACTIONTYPE)yyact; 792 791 yymsp->major = (YYCODETYPE)yygoto; 793 792 yyTraceShift(yypParser, yyact, "... then shift"); 793 + return yyact; 794 794 } 795 795 796 796 /* 797 797 ** The following code executes when the parse fails 798 798 */ 799 799 #ifndef YYNOERRORRECOVERY 800 800 static void yy_parse_failed( ................................................................................ 884 884 void Parse( 885 885 void *yyp, /* The parser */ 886 886 int yymajor, /* The major token code number */ 887 887 ParseTOKENTYPE yyminor /* The value for the token */ 888 888 ParseARG_PDECL /* Optional %extra_argument parameter */ 889 889 ){ 890 890 YYMINORTYPE yyminorunion; 891 - unsigned int yyact; /* The parser action. */ 891 + YYACTIONTYPE yyact; /* The parser action. */ 892 892 #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY) 893 893 int yyendofinput; /* True if we are at the end of input */ 894 894 #endif 895 895 #ifdef YYERRORSYMBOL 896 896 int yyerrorhit = 0; /* True if yymajor has invoked an error */ 897 897 #endif 898 898 yyParser *yypParser = (yyParser*)yyp; /* The parser */ ................................................................................ 900 900 ParseARG_STORE 901 901 902 902 assert( yypParser->yytos!=0 ); 903 903 #if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY) 904 904 yyendofinput = (yymajor==0); 905 905 #endif 906 906 907 + yyact = yypParser->yytos->stateno; 907 908 #ifndef NDEBUG 908 909 if( yyTraceFILE ){ 909 - int stateno = yypParser->yytos->stateno; 910 - if( stateno < YY_MIN_REDUCE ){ 910 + if( yyact < YY_MIN_REDUCE ){ 911 911 fprintf(yyTraceFILE,"%sInput '%s' in state %d\n", 912 - yyTracePrompt,yyTokenName[yymajor],stateno); 912 + yyTracePrompt,yyTokenName[yymajor],yyact); 913 913 }else{ 914 914 fprintf(yyTraceFILE,"%sInput '%s' with pending reduce %d\n", 915 - yyTracePrompt,yyTokenName[yymajor],stateno-YY_MIN_REDUCE); 915 + yyTracePrompt,yyTokenName[yymajor],yyact-YY_MIN_REDUCE); 916 916 } 917 917 } 918 918 #endif 919 919 920 920 do{ 921 - yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); 921 + assert( yyact==yypParser->yytos->stateno ); 922 + yyact = yy_find_shift_action(yymajor,yyact); 922 923 if( yyact >= YY_MIN_REDUCE ){ 923 - yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor ParseCTX_PARAM); 924 + yyact = yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor, 925 + yyminor ParseCTX_PARAM); 924 926 }else if( yyact <= YY_MAX_SHIFTREDUCE ){ 925 927 yy_shift(yypParser,yyact,yymajor,yyminor); 926 928 #ifndef YYNOERRORRECOVERY 927 929 yypParser->yyerrcnt--; 928 930 #endif 929 - yymajor = YYNOCODE; 931 + break; 930 932 }else if( yyact==YY_ACCEPT_ACTION ){ 931 - yypParser->yytos--; 932 - yy_accept(yypParser); 933 + /* YY_ACCEPT_ACTION also happens on a stack overflow. We distingush 934 + ** the two cases by observing that on a true accept, there should be 935 + ** a single token left on the stack, whereas on a stack overflow, 936 + ** the stack has been popped (by yyStackOverflow()) to be empty */ 937 + if( yypParser->yytos > yypParser->yystack ){ 938 + yypParser->yytos--; 939 + yy_accept(yypParser); 940 + } 933 941 return; 934 942 }else{ 935 943 assert( yyact == YY_ERROR_ACTION ); 936 944 yyminorunion.yy0 = yyminor; 937 945 #ifdef YYERRORSYMBOL 938 946 int yymx; 939 947 #endif ................................................................................ 993 1001 yymajor = YYNOCODE; 994 1002 }else if( yymx!=YYERRORSYMBOL ){ 995 1003 yy_shift(yypParser,yyact,YYERRORSYMBOL,yyminor); 996 1004 } 997 1005 } 998 1006 yypParser->yyerrcnt = 3; 999 1007 yyerrorhit = 1; 1008 + if( yymajor==YYNOCODE ) break; 1009 + yyact = yypParser->yytos->stateno; 1000 1010 #elif defined(YYNOERRORRECOVERY) 1001 1011 /* If the YYNOERRORRECOVERY macro is defined, then do not attempt to 1002 1012 ** do any kind of error recovery. Instead, simply invoke the syntax 1003 1013 ** error routine and continue going as if nothing had happened. 1004 1014 ** 1005 1015 ** Applications can set this macro (for example inside %include) if 1006 1016 ** they intend to abandon the parse upon the first syntax error seen. 1007 1017 */ 1008 1018 yy_syntax_error(yypParser,yymajor, yyminor); 1009 1019 yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 1010 - yymajor = YYNOCODE; 1011 - 1020 + break; 1012 1021 #else /* YYERRORSYMBOL is not defined */ 1013 1022 /* This is what we do if the grammar does not define ERROR: 1014 1023 ** 1015 1024 ** * Report an error message, and throw away the input token. 1016 1025 ** 1017 1026 ** * If the input token is $, then fail the parse. 1018 1027 ** ................................................................................ 1026 1035 yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 1027 1036 if( yyendofinput ){ 1028 1037 yy_parse_failed(yypParser); 1029 1038 #ifndef YYNOERRORRECOVERY 1030 1039 yypParser->yyerrcnt = -1; 1031 1040 #endif 1032 1041 } 1033 - yymajor = YYNOCODE; 1042 + break; 1034 1043 #endif 1035 1044 } 1036 - }while( yymajor!=YYNOCODE && yypParser->yytos>yypParser->yystack ); 1045 + }while( yypParser->yytos>yypParser->yystack ); 1037 1046 #ifndef NDEBUG 1038 1047 if( yyTraceFILE ){ 1039 1048 yyStackEntry *i; 1040 1049 char cDiv = '['; 1041 1050 fprintf(yyTraceFILE,"%sReturn. Stack=",yyTracePrompt); 1042 1051 for(i=&yypParser->yystack[1]; i<=yypParser->yytos; i++){ 1043 1052 fprintf(yyTraceFILE,"%c%s", cDiv, yyTokenName[i->major]);