SQLite

Check-in [fec1ebadeb]
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
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: fec1ebadeb9d6b55b19a1c159c543fd7ae67b3307c4caee4d2541bd783630e23
User & Date: drh 2018-04-21 22:40:08.247
Context
2018-04-23
00:25
Fix an unreachable branch associated with stack overflow in the LEMON-generated parser. (check-in: e3064ba3b6 user: drh tags: trunk)
2018-04-21
22:40
Performance improvements on the main loop of the LEMON-generated parser. (check-in: fec1ebadeb 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: dcf2bafc15 user: drh tags: trunk)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to tool/lempar.c.
501
502
503
504
505
506
507
508

509
510


511
512
513
514

515
516
517
518
519
520
521
501
502
503
504
505
506
507

508


509
510
511
512


513
514
515
516
517
518
519
520







-
+
-
-
+
+


-
-
+







}
#endif

/*
** Find the appropriate action for a parser given the terminal
** look-ahead token iLookAhead.
*/
static unsigned int yy_find_shift_action(
static YYACTIONTYPE yy_find_shift_action(
  yyParser *pParser,        /* The parser */
  YYCODETYPE iLookAhead     /* The look-ahead token */
  YYCODETYPE iLookAhead,    /* The look-ahead token */
  YYACTIONTYPE stateno      /* Current state number */
){
  int i;
  int stateno = pParser->yytos->stateno;
 

  if( stateno>YY_MAX_SHIFT ) return stateno;
  assert( stateno <= YY_SHIFT_COUNT );
#if defined(YYCOVERAGE)
  yycoverage[stateno][iLookAhead] = 1;
#endif
  do{
    i = yy_shift_ofst[stateno];
571
572
573
574
575
576
577
578

579
580
581
582
583
584
585
570
571
572
573
574
575
576

577
578
579
580
581
582
583
584







-
+







}

/*
** Find the appropriate action for a parser given the non-terminal
** look-ahead token iLookAhead.
*/
static int yy_find_reduce_action(
  int stateno,              /* Current state number */
  YYACTIONTYPE stateno,     /* Current state number */
  YYCODETYPE iLookAhead     /* The look-ahead token */
){
  int i;
#ifdef YYERRORSYMBOL
  if( stateno>YY_REDUCE_COUNT ){
    return yy_default[stateno];
  }
643
644
645
646
647
648
649
650
651


652
653
654
655
656
657
658
642
643
644
645
646
647
648


649
650
651
652
653
654
655
656
657







-
-
+
+







#endif

/*
** Perform a shift action.
*/
static void yy_shift(
  yyParser *yypParser,          /* The parser to be shifted */
  int yyNewState,               /* The new state to shift in */
  int yyMajor,                  /* The major token to shift in */
  YYACTIONTYPE yyNewState,      /* The new state to shift in */
  YYCODETYPE yyMajor,           /* The major token to shift in */
  ParseTOKENTYPE yyMinor        /* The minor token to shift in */
){
  yyStackEntry *yytos;
  yypParser->yytos++;
#ifdef YYTRACKMAXSTACKDEPTH
  if( (int)(yypParser->yytos - yypParser->yystack)>yypParser->yyhwm ){
    yypParser->yyhwm++;
674
675
676
677
678
679
680
681
682


683
684
685
686
687
688
689
673
674
675
676
677
678
679


680
681
682
683
684
685
686
687
688







-
-
+
+







    }
  }
#endif
  if( yyNewState > YY_MAX_SHIFT ){
    yyNewState += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
  }
  yytos = yypParser->yytos;
  yytos->stateno = (YYACTIONTYPE)yyNewState;
  yytos->major = (YYCODETYPE)yyMajor;
  yytos->stateno = yyNewState;
  yytos->major = yyMajor;
  yytos->minor.yy0 = yyMinor;
  yyTraceShift(yypParser, yyNewState, "Shift");
}

/* The following table contains information about every rule that
** is used during the reduce.
*/
702
703
704
705
706
707
708
709

710
711
712
713
714
715
716
701
702
703
704
705
706
707

708
709
710
711
712
713
714
715







-
+







**
** The yyLookahead and yyLookaheadToken parameters provide reduce actions
** access to the lookahead token (if any).  The yyLookahead will be YYNOCODE
** if the lookahead token has already been consumed.  As this procedure is
** only called from one place, optimizing compilers will in-line it, which
** means that the extra parameters have no performance impact.
*/
static void yy_reduce(
static YYACTIONTYPE yy_reduce(
  yyParser *yypParser,         /* The parser */
  unsigned int yyruleno,       /* Number of the rule by which to reduce */
  int yyLookahead,             /* Lookahead token, or YYNOCODE if none */
  ParseTOKENTYPE yyLookaheadToken  /* Value of the lookahead token */
  ParseCTX_PDECL                   /* %extra_context */
){
  int yygoto;                     /* The next state */
744
745
746
747
748
749
750
751

752
753
754
755
756
757

758
759
760
761
762
763
764
743
744
745
746
747
748
749

750
751
752
753
754
755

756
757
758
759
760
761
762
763







-
+





-
+







      yypParser->yyhwm++;
      assert( yypParser->yyhwm == (int)(yypParser->yytos - yypParser->yystack));
    }
#endif
#if YYSTACKDEPTH>0 
    if( yypParser->yytos>=yypParser->yystackEnd ){
      yyStackOverflow(yypParser);
      return;
      return YY_ACCEPT_ACTION;
    }
#else
    if( yypParser->yytos>=&yypParser->yystack[yypParser->yystksz-1] ){
      if( yyGrowStack(yypParser) ){
        yyStackOverflow(yypParser);
        return;
        return YY_ACCEPT_ACTION;
      }
      yymsp = yypParser->yytos;
    }
#endif
  }

  switch( yyruleno ){
787
788
789
790
791
792
793

794
795
796
797
798
799
800
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800







+







  assert( yyact!=YY_ERROR_ACTION );

  yymsp += yysize+1;
  yypParser->yytos = yymsp;
  yymsp->stateno = (YYACTIONTYPE)yyact;
  yymsp->major = (YYCODETYPE)yygoto;
  yyTraceShift(yypParser, yyact, "... then shift");
  return yyact;
}

/*
** The following code executes when the parse fails
*/
#ifndef YYNOERRORRECOVERY
static void yy_parse_failed(
884
885
886
887
888
889
890
891

892
893
894
895
896
897
898
899
900
901
902
903
904
905
906

907
908
909
910

911
912

913
914
915

916
917
918
919
920

921

922
923


924
925
926
927
928
929

930





931
932



933
934
935
936
937
938
939
884
885
886
887
888
889
890

891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909


910
911

912
913
914

915
916
917
918
919
920
921

922
923

924
925
926
927
928
929
930

931
932
933
934
935
936
937


938
939
940
941
942
943
944
945
946
947







-
+















+


-
-
+

-
+


-
+





+
-
+

-
+
+





-
+

+
+
+
+
+
-
-
+
+
+







void Parse(
  void *yyp,                   /* The parser */
  int yymajor,                 /* The major token code number */
  ParseTOKENTYPE yyminor       /* The value for the token */
  ParseARG_PDECL               /* Optional %extra_argument parameter */
){
  YYMINORTYPE yyminorunion;
  unsigned int yyact;   /* The parser action. */
  YYACTIONTYPE yyact;   /* The parser action. */
#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
  int yyendofinput;     /* True if we are at the end of input */
#endif
#ifdef YYERRORSYMBOL
  int yyerrorhit = 0;   /* True if yymajor has invoked an error */
#endif
  yyParser *yypParser = (yyParser*)yyp;  /* The parser */
  ParseCTX_FETCH
  ParseARG_STORE

  assert( yypParser->yytos!=0 );
#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY)
  yyendofinput = (yymajor==0);
#endif

  yyact = yypParser->yytos->stateno;
#ifndef NDEBUG
  if( yyTraceFILE ){
    int stateno = yypParser->yytos->stateno;
    if( stateno < YY_MIN_REDUCE ){
    if( yyact < YY_MIN_REDUCE ){
      fprintf(yyTraceFILE,"%sInput '%s' in state %d\n",
              yyTracePrompt,yyTokenName[yymajor],stateno);
              yyTracePrompt,yyTokenName[yymajor],yyact);
    }else{
      fprintf(yyTraceFILE,"%sInput '%s' with pending reduce %d\n",
              yyTracePrompt,yyTokenName[yymajor],stateno-YY_MIN_REDUCE);
              yyTracePrompt,yyTokenName[yymajor],yyact-YY_MIN_REDUCE);
    }
  }
#endif

  do{
    assert( yyact==yypParser->yytos->stateno );
    yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
    yyact = yy_find_shift_action(yymajor,yyact);
    if( yyact >= YY_MIN_REDUCE ){
      yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor ParseCTX_PARAM);
      yyact = yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,
                        yyminor ParseCTX_PARAM);
    }else if( yyact <= YY_MAX_SHIFTREDUCE ){
      yy_shift(yypParser,yyact,yymajor,yyminor);
#ifndef YYNOERRORRECOVERY
      yypParser->yyerrcnt--;
#endif
      yymajor = YYNOCODE;
      break;
    }else if( yyact==YY_ACCEPT_ACTION ){
      /* YY_ACCEPT_ACTION also happens on a stack overflow.  We distingush
      ** the two cases by observing that on a true accept, there should be
      ** a single token left on the stack, whereas on a stack overflow,
      ** the stack has been popped (by yyStackOverflow()) to be empty */
      if( yypParser->yytos > yypParser->yystack ){
      yypParser->yytos--;
      yy_accept(yypParser);
        yypParser->yytos--;
        yy_accept(yypParser);
      }
      return;
    }else{
      assert( yyact == YY_ERROR_ACTION );
      yyminorunion.yy0 = yyminor;
#ifdef YYERRORSYMBOL
      int yymx;
#endif
993
994
995
996
997
998
999


1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011

1012
1013
1014
1015
1016
1017
1018
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019


1020
1021
1022
1023
1024
1025
1026
1027







+
+










-
-
+







          yymajor = YYNOCODE;
        }else if( yymx!=YYERRORSYMBOL ){
          yy_shift(yypParser,yyact,YYERRORSYMBOL,yyminor);
        }
      }
      yypParser->yyerrcnt = 3;
      yyerrorhit = 1;
      if( yymajor==YYNOCODE ) break;
      yyact = yypParser->yytos->stateno;
#elif defined(YYNOERRORRECOVERY)
      /* If the YYNOERRORRECOVERY macro is defined, then do not attempt to
      ** do any kind of error recovery.  Instead, simply invoke the syntax
      ** error routine and continue going as if nothing had happened.
      **
      ** Applications can set this macro (for example inside %include) if
      ** they intend to abandon the parse upon the first syntax error seen.
      */
      yy_syntax_error(yypParser,yymajor, yyminor);
      yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
      yymajor = YYNOCODE;
      
      break;
#else  /* YYERRORSYMBOL is not defined */
      /* This is what we do if the grammar does not define ERROR:
      **
      **  * Report an error message, and throw away the input token.
      **
      **  * If the input token is $, then fail the parse.
      **
1026
1027
1028
1029
1030
1031
1032
1033

1034
1035
1036

1037
1038
1039
1040
1041
1042
1043
1035
1036
1037
1038
1039
1040
1041

1042
1043
1044

1045
1046
1047
1048
1049
1050
1051
1052







-
+


-
+







      yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion);
      if( yyendofinput ){
        yy_parse_failed(yypParser);
#ifndef YYNOERRORRECOVERY
        yypParser->yyerrcnt = -1;
#endif
      }
      yymajor = YYNOCODE;
      break;
#endif
    }
  }while( yymajor!=YYNOCODE && yypParser->yytos>yypParser->yystack );
  }while( yypParser->yytos>yypParser->yystack );
#ifndef NDEBUG
  if( yyTraceFILE ){
    yyStackEntry *i;
    char cDiv = '[';
    fprintf(yyTraceFILE,"%sReturn. Stack=",yyTracePrompt);
    for(i=&yypParser->yystack[1]; i<=yypParser->yytos; i++){
      fprintf(yyTraceFILE,"%c%s", cDiv, yyTokenName[i->major]);