/ Check-in [0557a179]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Avoid recursion in the yy_find_shift_action() routine of the Lemon-generated parser, so that routine can be inlined, for a size reduction and performance increase.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 0557a179f932296cc1fd5217f9a0d2f74e34ce1d
User & Date: drh 2015-11-09 15:06:26
Context
2015-11-10
12:41
Change all parsers to use the standard "lempar.c" template in the tool/ folder and remove the customized lempar.c from src/, plus other compiler performance and space enhancements. check-in: 0e7fb24a user: drh tags: trunk
2015-11-09
19:33
Change the parser to use the standard "lempar.c" template over in the tool/ folder rather than the customized "lempar.c" found in src/. check-in: 0a72991f user: drh tags: parser-enhancements
15:06
Avoid recursion in the yy_find_shift_action() routine of the Lemon-generated parser, so that routine can be inlined, for a size reduction and performance increase. check-in: 0557a179 user: drh tags: trunk
14:11
Size reduction and performance improvement in the stack-popping logic of the Lemon-generated parser. check-in: 9748c48a user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/lempar.c.

   397    397     YYCODETYPE iLookAhead     /* The look-ahead token */
   398    398   ){
   399    399     int i;
   400    400     int stateno = pParser->yystack[pParser->yyidx].stateno;
   401    401    
   402    402     if( stateno>=YY_MIN_REDUCE ) return stateno;
   403    403     assert( stateno <= YY_SHIFT_COUNT );
   404         -  i = yy_shift_ofst[stateno];
   405         -  if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno];
   406         -  assert( iLookAhead!=YYNOCODE );
   407         -  i += iLookAhead;
   408         -  if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
   409         -    if( iLookAhead>0 ){
          404  +  do{
          405  +    i = yy_shift_ofst[stateno];
          406  +    if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno];
          407  +    assert( iLookAhead!=YYNOCODE );
          408  +    i += iLookAhead;
          409  +    if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
          410  +      if( iLookAhead>0 ){
   410    411   #ifdef YYFALLBACK
   411         -      YYCODETYPE iFallback;            /* Fallback token */
   412         -      if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
   413         -             && (iFallback = yyFallback[iLookAhead])!=0 ){
          412  +        YYCODETYPE iFallback;            /* Fallback token */
          413  +        if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
          414  +               && (iFallback = yyFallback[iLookAhead])!=0 ){
   414    415   #ifndef NDEBUG
   415         -        if( yyTraceFILE ){
   416         -          fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
   417         -             yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
          416  +          if( yyTraceFILE ){
          417  +            fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
          418  +               yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
          419  +          }
          420  +#endif
          421  +          assert( yyFallback[iFallback]==0 ); /* Fallback loop must terminate */
          422  +          iLookAhead = iFallback;
          423  +          continue;
   418    424           }
   419    425   #endif
   420         -        return yy_find_shift_action(pParser, iFallback);
   421         -      }
   422         -#endif
   423    426   #ifdef YYWILDCARD
   424         -      {
   425         -        int j = i - iLookAhead + YYWILDCARD;
   426         -        if( 
          427  +        {
          428  +          int j = i - iLookAhead + YYWILDCARD;
          429  +          if( 
   427    430   #if YY_SHIFT_MIN+YYWILDCARD<0
   428         -          j>=0 &&
          431  +            j>=0 &&
   429    432   #endif
   430    433   #if YY_SHIFT_MAX+YYWILDCARD>=YY_ACTTAB_COUNT
   431         -          j<YY_ACTTAB_COUNT &&
          434  +            j<YY_ACTTAB_COUNT &&
   432    435   #endif
   433         -          yy_lookahead[j]==YYWILDCARD
   434         -        ){
          436  +            yy_lookahead[j]==YYWILDCARD
          437  +          ){
   435    438   #ifndef NDEBUG
   436         -          if( yyTraceFILE ){
   437         -            fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n",
   438         -               yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[YYWILDCARD]);
   439         -          }
          439  +            if( yyTraceFILE ){
          440  +              fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n",
          441  +                 yyTracePrompt, yyTokenName[iLookAhead],
          442  +                 yyTokenName[YYWILDCARD]);
          443  +            }
   440    444   #endif /* NDEBUG */
   441         -          return yy_action[j];
          445  +            return yy_action[j];
          446  +          }
   442    447           }
   443         -      }
   444    448   #endif /* YYWILDCARD */
          449  +      }
          450  +      return yy_default[stateno];
          451  +    }else{
          452  +      return yy_action[i];
   445    453       }
   446         -    return yy_default[stateno];
   447         -  }else{
   448         -    return yy_action[i];
   449         -  }
          454  +  }while(1);
   450    455   }
   451    456   
   452    457   /*
   453    458   ** Find the appropriate action for a parser given the non-terminal
   454    459   ** look-ahead token iLookAhead.
   455    460   **
   456    461   ** If the look-ahead token is YYNOCODE, then check to see if the action is

Changes to tool/lempar.c.

   386    386   */
   387    387   static int yy_find_shift_action(
   388    388     yyParser *pParser,        /* The parser */
   389    389     YYCODETYPE iLookAhead     /* The look-ahead token */
   390    390   ){
   391    391     int i;
   392    392     int stateno = pParser->yystack[pParser->yyidx].stateno;
   393         -
   394         -  if( stateno>=YY_MIN_REDUCE ) return stateno; 
          393  + 
          394  +  if( stateno>=YY_MIN_REDUCE ) return stateno;
   395    395     assert( stateno <= YY_SHIFT_COUNT );
   396         -  i = yy_shift_ofst[stateno];
   397         -  if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno];
   398         -  assert( iLookAhead!=YYNOCODE );
   399         -  i += iLookAhead;
   400         -  if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
   401         -    if( iLookAhead>0 ){
          396  +  do{
          397  +    i = yy_shift_ofst[stateno];
          398  +    if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno];
          399  +    assert( iLookAhead!=YYNOCODE );
          400  +    i += iLookAhead;
          401  +    if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
          402  +      if( iLookAhead>0 ){
   402    403   #ifdef YYFALLBACK
   403         -      YYCODETYPE iFallback;            /* Fallback token */
   404         -      if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
   405         -             && (iFallback = yyFallback[iLookAhead])!=0 ){
          404  +        YYCODETYPE iFallback;            /* Fallback token */
          405  +        if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0])
          406  +               && (iFallback = yyFallback[iLookAhead])!=0 ){
   406    407   #ifndef NDEBUG
   407         -        if( yyTraceFILE ){
   408         -          fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
   409         -             yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
          408  +          if( yyTraceFILE ){
          409  +            fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n",
          410  +               yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]);
          411  +          }
          412  +#endif
          413  +          assert( yyFallback[iFallback]==0 ); /* Fallback loop must terminate */
          414  +          iLookAhead = iFallback;
          415  +          continue;
   410    416           }
   411    417   #endif
   412         -        return yy_find_shift_action(pParser, iFallback);
   413         -      }
   414         -#endif
   415    418   #ifdef YYWILDCARD
   416         -      {
   417         -        int j = i - iLookAhead + YYWILDCARD;
   418         -        if( 
          419  +        {
          420  +          int j = i - iLookAhead + YYWILDCARD;
          421  +          if( 
   419    422   #if YY_SHIFT_MIN+YYWILDCARD<0
   420         -          j>=0 &&
          423  +            j>=0 &&
   421    424   #endif
   422    425   #if YY_SHIFT_MAX+YYWILDCARD>=YY_ACTTAB_COUNT
   423         -          j<YY_ACTTAB_COUNT &&
          426  +            j<YY_ACTTAB_COUNT &&
   424    427   #endif
   425         -          yy_lookahead[j]==YYWILDCARD
   426         -        ){
          428  +            yy_lookahead[j]==YYWILDCARD
          429  +          ){
   427    430   #ifndef NDEBUG
   428         -          if( yyTraceFILE ){
   429         -            fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n",
   430         -               yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[YYWILDCARD]);
   431         -          }
          431  +            if( yyTraceFILE ){
          432  +              fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n",
          433  +                 yyTracePrompt, yyTokenName[iLookAhead],
          434  +                 yyTokenName[YYWILDCARD]);
          435  +            }
   432    436   #endif /* NDEBUG */
   433         -          return yy_action[j];
          437  +            return yy_action[j];
          438  +          }
   434    439           }
   435         -      }
   436    440   #endif /* YYWILDCARD */
          441  +      }
          442  +      return yy_default[stateno];
          443  +    }else{
          444  +      return yy_action[i];
   437    445       }
   438         -    return yy_default[stateno];
   439         -  }else{
   440         -    return yy_action[i];
   441         -  }
          446  +  }while(1);
   442    447   }
   443    448   
   444    449   /*
   445    450   ** Find the appropriate action for a parser given the non-terminal
   446    451   ** look-ahead token iLookAhead.
   447    452   **
   448    453   ** If the look-ahead token is YYNOCODE, then check to see if the action is
................................................................................
   614    619     **  #line <lineno> <grammarfile>
   615    620     **     { ... }           // User supplied code
   616    621     **  #line <lineno> <thisfile>
   617    622     **     break;
   618    623     */
   619    624   %%
   620    625     };
          626  +  assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) );
   621    627     yygoto = yyRuleInfo[yyruleno].lhs;
   622    628     yysize = yyRuleInfo[yyruleno].nrhs;
   623    629     yypParser->yyidx -= yysize;
   624    630     yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
   625    631     if( yyact <= YY_MAX_SHIFTREDUCE ){
   626    632       if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   627    633       /* If the reduce action popped at least
................................................................................
   721    727     void *yyp,                   /* The parser */
   722    728     int yymajor,                 /* The major token code number */
   723    729     ParseTOKENTYPE yyminor       /* The value for the token */
   724    730     ParseARG_PDECL               /* Optional %extra_argument parameter */
   725    731   ){
   726    732     YYMINORTYPE yyminorunion;
   727    733     int yyact;            /* The parser action. */
          734  +#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
   728    735     int yyendofinput;     /* True if we are at the end of input */
          736  +#endif
   729    737   #ifdef YYERRORSYMBOL
   730    738     int yyerrorhit = 0;   /* True if yymajor has invoked an error */
   731    739   #endif
   732    740     yyParser *yypParser;  /* The parser */
   733    741   
   734    742     /* (re)initialize the parser, if necessary */
   735    743     yypParser = (yyParser*)yyp;
................................................................................
   744    752   #endif
   745    753       yypParser->yyidx = 0;
   746    754       yypParser->yyerrcnt = -1;
   747    755       yypParser->yystack[0].stateno = 0;
   748    756       yypParser->yystack[0].major = 0;
   749    757     }
   750    758     yyminorunion.yy0 = yyminor;
          759  +#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
   751    760     yyendofinput = (yymajor==0);
          761  +#endif
   752    762     ParseARG_STORE;
   753    763   
   754    764   #ifndef NDEBUG
   755    765     if( yyTraceFILE ){
   756    766       fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
   757    767     }
   758    768   #endif