Index: src/lempar.c ================================================================== --- src/lempar.c +++ src/lempar.c @@ -54,19 +54,23 @@ ** zero the stack is dynamically sized using realloc() ** ParseARG_SDECL A static variable declaration for the %extra_argument ** ParseARG_PDECL A parameter declaration for the %extra_argument ** ParseARG_STORE Code to store %extra_argument into yypParser ** ParseARG_FETCH Code to extract %extra_argument from yypParser -** YYNSTATE the combined number of states. -** YYNRULE the number of rules in the grammar ** YYERRORSYMBOL is the code number of the error symbol. If not ** defined, then do no error processing. +** YYNSTATE the combined number of states. +** YYNRULE the number of rules in the grammar +** YY_MAX_SHIFT Maximum value for shift actions +** YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions +** YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions +** YY_MIN_REDUCE Maximum value for reduce actions +** YY_ERROR_ACTION The yy_action[] code for syntax error +** YY_ACCEPT_ACTION The yy_action[] code for accept +** YY_NO_ACTION The yy_action[] code for no-op */ %% -#define YY_NO_ACTION (YYNSTATE+YYNRULE+2) -#define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) -#define YY_ERROR_ACTION (YYNSTATE+YYNRULE) /* The yyzerominor constant is used to initialize instances of ** YYMINORTYPE objects to zero. */ static const YYMINORTYPE yyzerominor = { 0 }; @@ -89,20 +93,24 @@ ** action integer. ** ** Suppose the action integer is N. Then the action is determined as ** follows ** -** 0 <= N < YYNSTATE Shift N. That is, push the lookahead +** 0 <= N <= YY_MAX_SHIFT Shift N. That is, push the lookahead ** token onto the stack and goto state N. ** -** YYNSTATE <= N < YYNSTATE+YYNRULE Reduce by rule N-YYNSTATE. +** N between YY_MIN_SHIFTREDUCE Shift to an arbitrary state then +** and YY_MAX_SHIFTREDUCE reduce by rule N-YY_MIN_SHIFTREDUCE. +** +** N between YY_MIN_REDUCE Reduce by rule N-YY_MIN_REDUCE +** and YY_MAX_REDUCE + +** N == YY_ERROR_ACTION A syntax error has occurred. ** -** N == YYNSTATE+YYNRULE A syntax error has occurred. +** N == YY_ACCEPT_ACTION The parser accepts its input. ** -** N == YYNSTATE+YYNRULE+1 The parser accepts its input. -** -** N == YYNSTATE+YYNRULE+2 No such action. Denotes unused +** N == YY_NO_ACTION No such action. Denotes unused ** slots in the yy_action[] table. ** ** The action table is constructed as a single large table named yy_action[]. ** Given state S and lookahead X, the action is computed as ** @@ -157,13 +165,17 @@ ** (In other words, the "major" token.) ** ** + The semantic value stored at this level of the stack. This is ** the information used by the action routines in the grammar. ** It is sometimes called the "minor" token. +** +** After the "shift" half of a SHIFTREDUCE action, the stateno field +** actually contains the reduce action for the second half of the +** SHIFTREDUCE. */ struct yyStackEntry { - YYACTIONTYPE stateno; /* The state-number */ + YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ YYCODETYPE major; /* The major token value. This is the code ** number for the token at this stack level */ YYMINORTYPE minor; /* The user-supplied minor token value. This ** is the value of the token */ }; @@ -393,14 +405,14 @@ YYCODETYPE iLookAhead /* The look-ahead token */ ){ int i; int stateno = pParser->yystack[pParser->yyidx].stateno; - if( stateno>YY_SHIFT_COUNT - || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){ - return yy_default[stateno]; - } + if( stateno>=YY_MIN_REDUCE ) return stateno; + assert( stateno <= YY_SHIFT_COUNT ); + i = yy_shift_ofst[stateno]; + if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno]; assert( iLookAhead!=YYNOCODE ); i += iLookAhead; if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ if( iLookAhead>0 ){ #ifdef YYFALLBACK @@ -497,11 +509,33 @@ %% ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ } /* -** Perform a shift action. +** Print tracing information for a SHIFT action +*/ +#ifndef NDEBUG +static void yyTraceShift(yyParser *yypParser, int yyNewState){ + if( yyTraceFILE ){ + int i; + if( yyNewStateyyidx; i++) + fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); + fprintf(yyTraceFILE,"\n"); + }else{ + fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); + } + } +} +#else +# define yyTraceShift(X,Y) +#endif + +/* +** Perform a shift action. Return the number of errors. */ 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 */ @@ -530,20 +564,11 @@ #endif yytos = &yypParser->yystack[yypParser->yyidx]; yytos->stateno = (YYACTIONTYPE)yyNewState; yytos->major = (YYCODETYPE)yyMajor; yytos->minor = *yypMinor; -#ifndef NDEBUG - if( yyTraceFILE && yypParser->yyidx>0 ){ - int i; - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); - for(i=1; i<=yypParser->yyidx; i++) - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); - fprintf(yyTraceFILE,"\n"); - } -#endif + yyTraceShift(yypParser, yyNewState); } /* The following table contains information about every rule that ** is used during the reduce. */ @@ -572,12 +597,13 @@ ParseARG_FETCH; yymsp = &yypParser->yystack[yypParser->yyidx]; #ifndef NDEBUG if( yyTraceFILE && yyruleno>=0 && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ - fprintf(yyTraceFILE, "%sReduce [%s].\n", yyTracePrompt, - yyRuleName[yyruleno]); + yysize = yyRuleInfo[yyruleno].nrhs; + fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt, + yyRuleName[yyruleno], yymsp[-yysize].stateno); } #endif /* NDEBUG */ /* Silence complaints from purify about yygotominor being uninitialized ** in some cases when it is copied into the stack after the following @@ -611,29 +637,28 @@ assert( yyruleno>=0 && yyrulenoyyidx -= yysize; yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); - if( yyact < YYNSTATE ){ -#ifdef NDEBUG - /* If we are not debugging and the reduce action popped at least + if( yyact <= YY_MAX_SHIFTREDUCE ){ + if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; + /* If the reduce action popped at least ** one element off the stack, then we can push the new element back ** onto the stack here, and skip the stack overflow test in yy_shift(). ** That gives a significant speed improvement. */ if( yysize ){ yypParser->yyidx++; yymsp -= yysize-1; yymsp->stateno = (YYACTIONTYPE)yyact; yymsp->major = (YYCODETYPE)yygoto; yymsp->minor = yygotominor; - }else -#endif - { + yyTraceShift(yypParser, yyact); + }else{ yy_shift(yypParser,yyact,yygoto,&yygotominor); } }else{ - assert( yyact == YYNSTATE + YYNRULE + 1 ); + assert( yyact == YY_ACCEPT_ACTION ); yy_accept(yypParser); } } /* @@ -753,16 +778,17 @@ } #endif do{ yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); - if( yyact YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; yy_shift(yypParser,yyact,yymajor,&yyminorunion); yypParser->yyerrcnt--; yymajor = YYNOCODE; - }else if( yyact < YYNSTATE + YYNRULE ){ - yy_reduce(yypParser,yyact-YYNSTATE); + }else if( yyact <= YY_MAX_REDUCE ){ + yy_reduce(yypParser,yyact-YY_MIN_REDUCE); }else{ assert( yyact == YY_ERROR_ACTION ); #ifdef YYERRORSYMBOL int yymx; #endif @@ -808,11 +834,11 @@ while( yypParser->yyidx >= 0 && yymx != YYERRORSYMBOL && (yyact = yy_find_reduce_action( yypParser->yystack[yypParser->yyidx].stateno, - YYERRORSYMBOL)) >= YYNSTATE + YYERRORSYMBOL)) >= YY_MIN_REDUCE ){ yy_pop_parser_stack(yypParser); } if( yypParser->yyidx < 0 || yymajor==0 ){ yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); @@ -858,7 +884,12 @@ } yymajor = YYNOCODE; #endif } }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); +#ifndef NDEBUG + if( yyTraceFILE ){ + fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt); + } +#endif return; } Index: src/tokenize.c ================================================================== --- src/tokenize.c +++ src/tokenize.c @@ -401,10 +401,11 @@ } pParse->rc = SQLITE_OK; pParse->zTail = zSql; i = 0; assert( pzErrMsg!=0 ); + /* sqlite3ParserTrace(stdout, "parser: "); */ pEngine = sqlite3ParserAlloc(sqlite3Malloc); if( pEngine==0 ){ db->mallocFailed = 1; return SQLITE_NOMEM; } Index: tool/lemon.c ================================================================== --- tool/lemon.c +++ tool/lemon.c @@ -314,11 +314,12 @@ SSCONFLICT, /* A shift/shift conflict */ SRCONFLICT, /* Was a reduce, but part of a conflict */ RRCONFLICT, /* Was a reduce, but part of a conflict */ SH_RESOLVED, /* Was a shift. Precedence resolved conflict */ RD_RESOLVED, /* Was reduce. Precedence resolved conflict */ - NOT_USED /* Deleted by compression */ + NOT_USED, /* Deleted by compression */ + SHIFTREDUCE /* Shift first, then reduce */ }; /* Every shift or reduce operation is stored as one of the following */ struct action { struct symbol *sp; /* The look-ahead symbol */ @@ -338,11 +339,13 @@ struct config *cfp; /* All configurations in this set */ int statenum; /* Sequential number for this state */ struct action *ap; /* Array of actions for this state */ int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */ int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */ - int iDflt; /* Default action is reduce by this rule */ + int iDfltReduce; /* Default action is to REDUCE by this rule */ + struct rule *pDfltReduce;/* The default REDUCE rule. */ + int autoReduce; /* True if this is an auto-reduce state */ }; #define NO_OFFSET (-2147483647) /* A followset propagation link indicates that the contents of one ** configuration followset should be propagated to another whenever @@ -358,10 +361,11 @@ ** of as begin global variables in the program.) */ struct lemon { struct state **sorted; /* Table of states sorted by state number */ struct rule *rule; /* List of all rules */ int nstate; /* Number of states */ + int nxstate; /* nstate with tail degenerate states removed */ int nrule; /* Number of rules */ int nsymbol; /* Number of terminal and nonterminal symbols */ int nterminal; /* Number of terminal symbols */ struct symbol **symbols; /* Sorted array of pointers to symbols */ int errorcnt; /* Number of errors */ @@ -482,11 +486,11 @@ int rc; rc = ap1->sp->index - ap2->sp->index; if( rc==0 ){ rc = (int)ap1->type - (int)ap2->type; } - if( rc==0 && ap1->type==REDUCE ){ + if( rc==0 && (ap1->type==REDUCE || ap1->type==SHIFTREDUCE) ){ rc = ap1->x.rp->index - ap2->x.rp->index; } if( rc==0 ){ rc = (int) (ap2 - ap1); } @@ -1629,11 +1633,11 @@ printf("Parser statistics:\n"); stats_line("terminal symbols", lem.nterminal); stats_line("non-terminal symbols", lem.nsymbol - lem.nterminal); stats_line("total symbols", lem.nsymbol); stats_line("rules", lem.nrule); - stats_line("states", lem.nstate); + stats_line("states", lem.nxstate); stats_line("conflicts", lem.nconflict); stats_line("action table entries", lem.nactiontab); stats_line("total table size (bytes)", lem.tablesize); } if( lem.nconflict > 0 ){ @@ -3027,28 +3031,29 @@ ** nothing was actually printed. */ int PrintAction( struct action *ap, /* The action to print */ FILE *fp, /* Print the action here */ - int indent, /* Indent by this amount */ - struct rule **apRule /* All rules by index */ + int indent /* Indent by this amount */ ){ int result = 1; switch( ap->type ){ case SHIFT: { struct state *stp = ap->x.stp; - fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum); - if( stp->nTknAct==0 && stp->nNtAct==0 && apRule ){ - fprintf(fp,"then reduce %d: ", stp->iDflt); - RulePrint(fp, apRule[stp->iDflt], -1); - } + fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum); break; } case REDUCE: { struct rule *rp = ap->x.rp; - fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index); - if( apRule ) RulePrint(fp, apRule[rp->index], -1); + fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->index); + RulePrint(fp, rp, -1); + break; + } + case SHIFTREDUCE: { + struct rule *rp = ap->x.rp; + fprintf(fp,"%*s shift-reduce %-7d",indent,ap->sp->name,rp->index); + RulePrint(fp, rp, -1); break; } case ACCEPT: fprintf(fp,"%*s accept",indent,ap->sp->name); break; @@ -3055,20 +3060,20 @@ case ERROR: fprintf(fp,"%*s error",indent,ap->sp->name); break; case SRCONFLICT: case RRCONFLICT: - fprintf(fp,"%*s reduce %-7d ** Parsing conflict **", + fprintf(fp,"%*s reduce %-7d ** Parsing conflict **", indent,ap->sp->name,ap->x.rp->index); break; case SSCONFLICT: - fprintf(fp,"%*s shift %-7d ** Parsing conflict **", + fprintf(fp,"%*s shift %-7d ** Parsing conflict **", indent,ap->sp->name,ap->x.stp->statenum); break; case SH_RESOLVED: if( showPrecedenceConflict ){ - fprintf(fp,"%*s shift %-7d -- dropped by precedence", + fprintf(fp,"%*s shift %-7d -- dropped by precedence", indent,ap->sp->name,ap->x.stp->statenum); }else{ result = 0; } break; @@ -3085,32 +3090,22 @@ break; } return result; } -/* Generate the "y.output" log file */ +/* Generate the "*.out" log file */ void ReportOutput(struct lemon *lemp) { int i; struct state *stp; struct config *cfp; struct action *ap; FILE *fp; - struct rule **apRule; - - apRule = malloc( sizeof(apRule[0])*(lemp->nrule+1) ); - if( apRule ){ - struct rule *x; - memset(apRule, 0, sizeof(apRule[0])*(lemp->nrule+1) ); - for(x=lemp->rule; x; x=x->next){ - assert( x->index>=0 && x->index<(lemp->nrule+1) ); - apRule[x->index] = x; - } - } + fp = file_open(lemp,".out","wb"); if( fp==0 ) return; - for(i=0; instate; i++){ + for(i=0; inxstate; i++){ stp = lemp->sorted[i]; fprintf(fp,"State %d:\n",stp->statenum); if( lemp->basisflag ) cfp=stp->bp; else cfp=stp->cfp; while( cfp ){ @@ -3131,11 +3126,11 @@ if( lemp->basisflag ) cfp=cfp->bp; else cfp=cfp->next; } fprintf(fp,"\n"); for(ap=stp->ap; ap; ap=ap->next){ - if( PrintAction(ap,fp,30,apRule) ) fprintf(fp,"\n"); + if( PrintAction(ap,fp,30) ) fprintf(fp,"\n"); } fprintf(fp,"\n"); } fprintf(fp, "----------------------------------------------------\n"); fprintf(fp, "Symbols:\n"); @@ -3157,11 +3152,10 @@ } } fprintf(fp, "\n"); } fclose(fp); - free(apRule); return; } /* Search for the file "name" which is in the same directory as ** the exacutable */ @@ -3215,14 +3209,15 @@ */ PRIVATE int compute_action(struct lemon *lemp, struct action *ap) { int act; switch( ap->type ){ - case SHIFT: act = ap->x.stp->statenum; break; - case REDUCE: act = ap->x.rp->index + lemp->nstate; break; - case ERROR: act = lemp->nstate + lemp->nrule; break; - case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break; + case SHIFT: act = ap->x.stp->statenum; break; + case SHIFTREDUCE: act = ap->x.rp->index + lemp->nstate; break; + case REDUCE: act = ap->x.rp->index + lemp->nstate+lemp->nrule; break; + case ERROR: act = lemp->nstate + lemp->nrule*2; break; + case ACCEPT: act = lemp->nstate + lemp->nrule*2 + 1; break; default: act = -1; break; } return act; } @@ -3841,11 +3836,11 @@ /* Generate the defines */ fprintf(out,"#define YYCODETYPE %s\n", minimum_size_type(0, lemp->nsymbol+1, &szCodeType)); lineno++; fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++; fprintf(out,"#define YYACTIONTYPE %s\n", - minimum_size_type(0, lemp->nstate+lemp->nrule+5, &szActionType)); lineno++; + minimum_size_type(0,lemp->nstate+lemp->nrule*2+5,&szActionType)); lineno++; if( lemp->wildcard ){ fprintf(out,"#define YYWILDCARD %d\n", lemp->wildcard->index); lineno++; } print_stack_union(out,lemp,&lineno,mhflag); @@ -3877,40 +3872,28 @@ fprintf(out,"#define %sARG_STORE\n",name); lineno++; } if( mhflag ){ fprintf(out,"#endif\n"); lineno++; } - fprintf(out,"#define YYNSTATE %d\n",lemp->nstate); lineno++; - fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++; if( lemp->errsym->useCnt ){ - fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++; - fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++; + fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++; + fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++; } if( lemp->has_fallback ){ fprintf(out,"#define YYFALLBACK 1\n"); lineno++; } - tplt_xfer(lemp->name,in,out,&lineno); - - /* Generate the action table and its associates: - ** - ** yy_action[] A single table containing all actions. - ** yy_lookahead[] A table containing the lookahead for each entry in - ** yy_action. Used to detect hash collisions. - ** yy_shift_ofst[] For each state, the offset into yy_action for - ** shifting terminals. - ** yy_reduce_ofst[] For each state, the offset into yy_action for - ** shifting non-terminals after a reduce. - ** yy_default[] Default action for each state. + + /* Compute the action table, but do not output it yet. The action + ** table must be computed before generating the YYNSTATE macro because + ** we need to know how many states can be eliminated. */ - - /* Compute the actions on all states and count them up */ - ax = (struct axset *) calloc(lemp->nstate*2, sizeof(ax[0])); + ax = (struct axset *) calloc(lemp->nxstate*2, sizeof(ax[0])); if( ax==0 ){ fprintf(stderr,"malloc failed\n"); exit(1); } - for(i=0; instate; i++){ + for(i=0; inxstate; i++){ stp = lemp->sorted[i]; ax[i*2].stp = stp; ax[i*2].isTkn = 1; ax[i*2].nAction = stp->nTknAct; ax[i*2+1].stp = stp; @@ -3917,19 +3900,16 @@ ax[i*2+1].isTkn = 0; ax[i*2+1].nAction = stp->nNtAct; } mxTknOfst = mnTknOfst = 0; mxNtOfst = mnNtOfst = 0; - - /* Compute the action table. In order to try to keep the size of the - ** action table to a minimum, the heuristic of placing the largest action - ** sets first is used. - */ - for(i=0; instate*2; i++) ax[i].iOrder = i; - qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare); + /* In an effort to minimize the action table size, use the heuristic + ** of placing the largest action sets first */ + for(i=0; inxstate*2; i++) ax[i].iOrder = i; + qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare); pActtab = acttab_alloc(); - for(i=0; instate*2 && ax[i].nAction>0; i++){ + for(i=0; inxstate*2 && ax[i].nAction>0; i++){ stp = ax[i].stp; if( ax[i].isTkn ){ for(ap=stp->ap; ap; ap=ap->next){ int action; if( ap->sp->index>=lemp->nterminal ) continue; @@ -3953,10 +3933,38 @@ if( stp->iNtOfstiNtOfst; if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; } } free(ax); + + /* Finish rendering the constants now that the action table has + ** been computed */ + fprintf(out,"#define YYNSTATE %d\n",lemp->nxstate); lineno++; + fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++; + fprintf(out,"#define YY_MAX_SHIFT %d\n",lemp->nstate-1); lineno++; + fprintf(out,"#define YY_MIN_SHIFTREDUCE %d\n",lemp->nstate); lineno++; + i = lemp->nstate + lemp->nrule; + fprintf(out,"#define YY_MAX_SHIFTREDUCE %d\n", i-1); lineno++; + fprintf(out,"#define YY_MIN_REDUCE %d\n", i); lineno++; + i = lemp->nstate + lemp->nrule*2; + fprintf(out,"#define YY_MAX_REDUCE %d\n", i-1); lineno++; + fprintf(out,"#define YY_ERROR_ACTION %d\n", i); lineno++; + fprintf(out,"#define YY_ACCEPT_ACTION %d\n", i+1); lineno++; + fprintf(out,"#define YY_NO_ACTION %d\n", i+2); lineno++; + tplt_xfer(lemp->name,in,out,&lineno); + + /* Now output the action table and its associates: + ** + ** yy_action[] A single table containing all actions. + ** yy_lookahead[] A table containing the lookahead for each entry in + ** yy_action. Used to detect hash collisions. + ** yy_shift_ofst[] For each state, the offset into yy_action for + ** shifting terminals. + ** yy_reduce_ofst[] For each state, the offset into yy_action for + ** shifting non-terminals after a reduce. + ** yy_default[] Default action for each state. + */ /* Output the yy_action table */ lemp->nactiontab = n = acttab_size(pActtab); lemp->tablesize += n*szActionType; fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++; @@ -3992,11 +4000,11 @@ } fprintf(out, "};\n"); lineno++; /* Output the yy_shift_ofst[] table */ fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++; - n = lemp->nstate; + n = lemp->nxstate; while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--; fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++; fprintf(out, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst); lineno++; fprintf(out, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst); lineno++; fprintf(out, "static const %s yy_shift_ofst[] = {\n", @@ -4018,11 +4026,11 @@ } fprintf(out, "};\n"); lineno++; /* Output the yy_reduce_ofst[] table */ fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++; - n = lemp->nstate; + n = lemp->nxstate; while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--; fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++; fprintf(out, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst); lineno++; fprintf(out, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst); lineno++; fprintf(out, "static const %s yy_reduce_ofst[] = {\n", @@ -4044,16 +4052,16 @@ } fprintf(out, "};\n"); lineno++; /* Output the default action table */ fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++; - n = lemp->nstate; + n = lemp->nxstate; lemp->tablesize += n*szActionType; for(i=j=0; isorted[i]; if( j==0 ) fprintf(out," /* %5d */ ", i); - fprintf(out, " %4d,", stp->iDflt+n); + fprintf(out, " %4d,", stp->iDfltReduce+lemp->nstate+lemp->nrule); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; j = 0; }else{ j++; @@ -4282,11 +4290,11 @@ void CompressTables(struct lemon *lemp) { struct state *stp; struct action *ap, *ap2; struct rule *rp, *rp2, *rbest; - int nbest, n; + int nbest, n, nshift; int i; int usesWildcard; for(i=0; instate; i++){ stp = lemp->sorted[i]; @@ -4330,10 +4338,36 @@ ap->sp = Symbol_new("{default}"); for(ap=ap->next; ap; ap=ap->next){ if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED; } stp->ap = Action_sort(stp->ap); + + for(ap=stp->ap; ap; ap=ap->next){ + if( ap->type==SHIFT ) break; + if( ap->type==REDUCE && ap->x.rp!=rbest ) break; + } + if( ap==0 ){ + stp->autoReduce = 1; + stp->pDfltReduce = rbest; + } + } + + /* Make a second pass over all states and actions. Convert + ** every action that is a SHIFT to an autoReduce state into + ** a SHIFTREDUCE action. + */ + for(i=0; instate; i++){ + stp = lemp->sorted[i]; + for(ap=stp->ap; ap; ap=ap->next){ + struct state *pNextState; + if( ap->type!=SHIFT ) continue; + pNextState = ap->x.stp; + if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){ + ap->type = SHIFTREDUCE; + ap->x.rp = pNextState->pDfltReduce; + } + } } } /* @@ -4370,29 +4404,35 @@ struct action *ap; for(i=0; instate; i++){ stp = lemp->sorted[i]; stp->nTknAct = stp->nNtAct = 0; - stp->iDflt = lemp->nrule; + stp->iDfltReduce = lemp->nrule; /* Init dflt action to "syntax error" */ stp->iTknOfst = NO_OFFSET; stp->iNtOfst = NO_OFFSET; for(ap=stp->ap; ap; ap=ap->next){ - if( compute_action(lemp,ap)>=0 ){ + int iAction = compute_action(lemp,ap); + if( iAction>=0 ){ if( ap->sp->indexnterminal ){ stp->nTknAct++; }else if( ap->sp->indexnsymbol ){ stp->nNtAct++; }else{ - stp->iDflt = compute_action(lemp, ap) - lemp->nstate; + assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp ); + stp->iDfltReduce = iAction - lemp->nstate - lemp->nrule; } } } } qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]), stateResortCompare); for(i=0; instate; i++){ lemp->sorted[i]->statenum = i; + } + lemp->nxstate = lemp->nstate; + while( lemp->nxstate>1 && lemp->sorted[lemp->nxstate-1]->autoReduce ){ + lemp->nxstate--; } } /***************** From the file "set.c" ************************************/ Index: tool/lempar.c ================================================================== --- tool/lempar.c +++ tool/lempar.c @@ -48,19 +48,23 @@ ** zero the stack is dynamically sized using realloc() ** ParseARG_SDECL A static variable declaration for the %extra_argument ** ParseARG_PDECL A parameter declaration for the %extra_argument ** ParseARG_STORE Code to store %extra_argument into yypParser ** ParseARG_FETCH Code to extract %extra_argument from yypParser -** YYNSTATE the combined number of states. -** YYNRULE the number of rules in the grammar ** YYERRORSYMBOL is the code number of the error symbol. If not ** defined, then do no error processing. +** YYNSTATE the combined number of states. +** YYNRULE the number of rules in the grammar +** YY_MAX_SHIFT Maximum value for shift actions +** YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions +** YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions +** YY_MIN_REDUCE Maximum value for reduce actions +** YY_ERROR_ACTION The yy_action[] code for syntax error +** YY_ACCEPT_ACTION The yy_action[] code for accept +** YY_NO_ACTION The yy_action[] code for no-op */ %% -#define YY_NO_ACTION (YYNSTATE+YYNRULE+2) -#define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) -#define YY_ERROR_ACTION (YYNSTATE+YYNRULE) /* The yyzerominor constant is used to initialize instances of ** YYMINORTYPE objects to zero. */ static const YYMINORTYPE yyzerominor = { 0 }; @@ -83,20 +87,24 @@ ** action integer. ** ** Suppose the action integer is N. Then the action is determined as ** follows ** -** 0 <= N < YYNSTATE Shift N. That is, push the lookahead +** 0 <= N <= YY_MAX_SHIFT Shift N. That is, push the lookahead ** token onto the stack and goto state N. ** -** YYNSTATE <= N < YYNSTATE+YYNRULE Reduce by rule N-YYNSTATE. +** N between YY_MIN_SHIFTREDUCE Shift to an arbitrary state then +** and YY_MAX_SHIFTREDUCE reduce by rule N-YY_MIN_SHIFTREDUCE. +** +** N between YY_MIN_REDUCE Reduce by rule N-YY_MIN_REDUCE +** and YY_MAX_REDUCE + +** N == YY_ERROR_ACTION A syntax error has occurred. ** -** N == YYNSTATE+YYNRULE A syntax error has occurred. +** N == YY_ACCEPT_ACTION The parser accepts its input. ** -** N == YYNSTATE+YYNRULE+1 The parser accepts its input. -** -** N == YYNSTATE+YYNRULE+2 No such action. Denotes unused +** N == YY_NO_ACTION No such action. Denotes unused ** slots in the yy_action[] table. ** ** The action table is constructed as a single large table named yy_action[]. ** Given state S and lookahead X, the action is computed as ** @@ -151,13 +159,17 @@ ** (In other words, the "major" token.) ** ** + The semantic value stored at this level of the stack. This is ** the information used by the action routines in the grammar. ** It is sometimes called the "minor" token. +** +** After the "shift" half of a SHIFTREDUCE action, the stateno field +** actually contains the reduce action for the second half of the +** SHIFTREDUCE. */ struct yyStackEntry { - YYACTIONTYPE stateno; /* The state-number */ + YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ YYCODETYPE major; /* The major token value. This is the code ** number for the token at this stack level */ YYMINORTYPE minor; /* The user-supplied minor token value. This ** is the value of the token */ }; @@ -382,15 +394,15 @@ yyParser *pParser, /* The parser */ YYCODETYPE iLookAhead /* The look-ahead token */ ){ int i; int stateno = pParser->yystack[pParser->yyidx].stateno; - - if( stateno>YY_SHIFT_COUNT - || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){ - return yy_default[stateno]; - } + + if( stateno>=YY_MIN_REDUCE ) return stateno; + assert( stateno <= YY_SHIFT_COUNT ); + i = yy_shift_ofst[stateno]; + if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno]; assert( iLookAhead!=YYNOCODE ); i += iLookAhead; if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ if( iLookAhead>0 ){ #ifdef YYFALLBACK @@ -487,11 +499,33 @@ %% ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ } /* -** Perform a shift action. +** Print tracing information for a SHIFT action +*/ +#ifndef NDEBUG +static void yyTraceShift(yyParser *yypParser, int yyNewState){ + if( yyTraceFILE ){ + int i; + if( yyNewStateyyidx; i++) + fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); + fprintf(yyTraceFILE,"\n"); + }else{ + fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); + } + } +} +#else +# define yyTraceShift(X,Y) +#endif + +/* +** Perform a shift action. Return the number of errors. */ 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 */ @@ -520,20 +554,11 @@ #endif yytos = &yypParser->yystack[yypParser->yyidx]; yytos->stateno = (YYACTIONTYPE)yyNewState; yytos->major = (YYCODETYPE)yyMajor; yytos->minor = *yypMinor; -#ifndef NDEBUG - if( yyTraceFILE && yypParser->yyidx>0 ){ - int i; - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); - for(i=1; i<=yypParser->yyidx; i++) - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); - fprintf(yyTraceFILE,"\n"); - } -#endif + yyTraceShift(yypParser, yyNewState); } /* The following table contains information about every rule that ** is used during the reduce. */ @@ -562,12 +587,13 @@ ParseARG_FETCH; yymsp = &yypParser->yystack[yypParser->yyidx]; #ifndef NDEBUG if( yyTraceFILE && yyruleno>=0 && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ - fprintf(yyTraceFILE, "%sReduce [%s].\n", yyTracePrompt, - yyRuleName[yyruleno]); + yysize = yyRuleInfo[yyruleno].nrhs; + fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt, + yyRuleName[yyruleno], yymsp[-yysize].stateno); } #endif /* NDEBUG */ /* Silence complaints from purify about yygotominor being uninitialized ** in some cases when it is copied into the stack after the following @@ -600,29 +626,28 @@ }; yygoto = yyRuleInfo[yyruleno].lhs; yysize = yyRuleInfo[yyruleno].nrhs; yypParser->yyidx -= yysize; yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); - if( yyact < YYNSTATE ){ -#ifdef NDEBUG - /* If we are not debugging and the reduce action popped at least + if( yyact <= YY_MAX_SHIFTREDUCE ){ + if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; + /* If the reduce action popped at least ** one element off the stack, then we can push the new element back ** onto the stack here, and skip the stack overflow test in yy_shift(). ** That gives a significant speed improvement. */ if( yysize ){ yypParser->yyidx++; yymsp -= yysize-1; yymsp->stateno = (YYACTIONTYPE)yyact; yymsp->major = (YYCODETYPE)yygoto; yymsp->minor = yygotominor; - }else -#endif - { + yyTraceShift(yypParser, yyact); + }else{ yy_shift(yypParser,yyact,yygoto,&yygotominor); } }else{ - assert( yyact == YYNSTATE + YYNRULE + 1 ); + assert( yyact == YY_ACCEPT_ACTION ); yy_accept(yypParser); } } /* @@ -738,17 +763,17 @@ } #endif do{ yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); - if( yyact YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; yy_shift(yypParser,yyact,yymajor,&yyminorunion); yypParser->yyerrcnt--; yymajor = YYNOCODE; - }else if( yyact < YYNSTATE + YYNRULE ){ - yy_reduce(yypParser,yyact-YYNSTATE); + }else if( yyact <= YY_MAX_REDUCE ){ + yy_reduce(yypParser,yyact-YY_MIN_REDUCE); }else{ assert( yyact == YY_ERROR_ACTION ); #ifdef YYERRORSYMBOL int yymx; #endif @@ -794,11 +819,11 @@ while( yypParser->yyidx >= 0 && yymx != YYERRORSYMBOL && (yyact = yy_find_reduce_action( yypParser->yystack[yypParser->yyidx].stateno, - YYERRORSYMBOL)) >= YYNSTATE + YYERRORSYMBOL)) >= YY_MIN_REDUCE ){ yy_pop_parser_stack(yypParser); } if( yypParser->yyidx < 0 || yymajor==0 ){ yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); @@ -844,7 +869,12 @@ } yymajor = YYNOCODE; #endif } }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); +#ifndef NDEBUG + if( yyTraceFILE ){ + fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt); + } +#endif return; }