/ Check-in [fec1ebad]
Login

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: fec1ebadeb9d6b55b19a1c159c543fd7ae67b3307c4caee4d2541bd783630e23
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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]);