Index: src/main.c ================================================================== --- src/main.c +++ src/main.c @@ -3909,10 +3909,26 @@ sqlite3ResetAllSchemasOfConnection(db); } sqlite3_mutex_leave(db->mutex); break; } + +#if defined(YYCOVERAGE) + /* sqlite3_test_control(SQLITE_TESTCTRL_PARSER_COVERAGE, FILE *out) + ** + ** This test control (only available when SQLite is compiled with + ** -DYYCOVERAGE) writes a report onto "out" that shows all + ** state/lookahead combinations in the parser state machine + ** which are never exercised. If any state is missed, make the + ** return code SQLITE_ERROR. + */ + case SQLITE_TESTCTRL_PARSER_COVERAGE: { + FILE *out = va_arg(ap, FILE*); + if( sqlite3ParserCoverage(out) ) rc = SQLITE_ERROR; + break; + } +#endif /* defined(YYCOVERAGE) */ } va_end(ap); #endif /* SQLITE_UNTESTABLE */ return rc; } Index: src/shell.c.in ================================================================== --- src/shell.c.in +++ src/shell.c.in @@ -6106,10 +6106,13 @@ { "iskeyword", SQLITE_TESTCTRL_ISKEYWORD, "IDENTIFIER" }, #endif { "localtime_fault", SQLITE_TESTCTRL_LOCALTIME_FAULT,"BOOLEAN" }, { "never_corrupt", SQLITE_TESTCTRL_NEVER_CORRUPT, "BOOLEAN" }, { "optimizations", SQLITE_TESTCTRL_OPTIMIZATIONS, "DISABLE-MASK" }, +#ifdef YYCOVERAGE + { "parser_coverage", SQLITE_TESTCTRL_PARSER_COVERAGE, "" }, +#endif { "pending_byte", SQLITE_TESTCTRL_PENDING_BYTE, "OFFSET " }, { "prng_reset", SQLITE_TESTCTRL_PRNG_RESET, "" }, { "prng_restore", SQLITE_TESTCTRL_PRNG_RESTORE, "" }, { "prng_save", SQLITE_TESTCTRL_PRNG_SAVE, "" }, { "reserve", SQLITE_TESTCTRL_RESERVE, "BYTES-OF-RESERVE" }, @@ -6231,10 +6234,18 @@ integerValue(azArg[3]), integerValue(azArg[4])); isOk = 3; } break; + +#ifdef YYCOVERAGE + case SQLITE_TESTCTRL_PARSER_COVERAGE: + if( nArg==2 ){ + sqlite3_test_control(testctrl, p->out); + isOk = 3; + } +#endif } } if( isOk==0 && iCtrl>=0 ){ utf8_printf(p->out, "Usage: .testctrl %s %s\n", zCmd, aCtrl[iCtrl].zUsage); rc = 1; Index: src/sqlite.h.in ================================================================== --- src/sqlite.h.in +++ src/sqlite.h.in @@ -7040,11 +7040,12 @@ #define SQLITE_TESTCTRL_VDBE_COVERAGE 21 #define SQLITE_TESTCTRL_BYTEORDER 22 #define SQLITE_TESTCTRL_ISINIT 23 #define SQLITE_TESTCTRL_SORTER_MMAP 24 #define SQLITE_TESTCTRL_IMPOSTER 25 -#define SQLITE_TESTCTRL_LAST 25 /* Largest TESTCTRL */ +#define SQLITE_TESTCTRL_PARSER_COVERAGE 26 +#define SQLITE_TESTCTRL_LAST 26 /* Largest TESTCTRL */ /* ** CAPI3REF: SQLite Runtime Status ** ** ^These interfaces are used to retrieve runtime status information Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -4346,10 +4346,13 @@ #endif #ifdef SQLITE_DEBUG void sqlite3ParserTrace(FILE*, char *); #endif +#if defined(YYCOVERAGE) + int sqlite3ParserCoverage(FILE*); +#endif /* ** If the SQLITE_ENABLE IOTRACE exists then the global variable ** sqlite3IoTrace is a pointer to a printf-like routine used to ** print I/O tracing messages. Index: tool/lemon.c ================================================================== --- tool/lemon.c +++ tool/lemon.c @@ -382,10 +382,16 @@ 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 */ + int minShiftReduce; /* Minimum shift-reduce action value */ + int errAction; /* Error action value */ + int accAction; /* Accept action value */ + int noAction; /* No-op action value */ + int minReduce; /* Minimum reduce action */ + int maxAction; /* Maximum action value of any kind */ struct symbol **symbols; /* Sorted array of pointers to symbols */ int errorcnt; /* Number of errors */ struct symbol *errsym; /* The error symbol */ struct symbol *wildcard; /* Token that matches anything */ char *name; /* Name of the generated parser */ @@ -405,10 +411,11 @@ char *filename; /* Name of the input file */ char *outname; /* Name of the current output file */ char *tokenprefix; /* A prefix added to token names in the .h file */ int nconflict; /* Number of parsing conflicts */ int nactiontab; /* Number of entries in the yy_action[] table */ + int nlookaheadtab; /* Number of entries in yy_lookahead[] */ int tablesize; /* Total table size of all tables in bytes */ int basisflag; /* Print only basis configurations */ int has_fallback; /* True if any %fallback is seen in the grammar */ int nolinenosflag; /* True if #line statements should not be printed */ char *argv0; /* Name of the program */ @@ -581,14 +588,16 @@ int mnLookahead; /* Minimum aLookahead[].lookahead */ int mnAction; /* Action associated with mnLookahead */ int mxLookahead; /* Maximum aLookahead[].lookahead */ int nLookahead; /* Used slots in aLookahead[] */ int nLookaheadAlloc; /* Slots allocated in aLookahead[] */ + int nterminal; /* Number of terminal symbols */ + int nsymbol; /* total number of symbols */ }; /* Return the number of entries in the yy_action table */ -#define acttab_size(X) ((X)->nAction) +#define acttab_lookahead_size(X) ((X)->nAction) /* The value for the N-th entry in yy_action */ #define acttab_yyaction(X,N) ((X)->aAction[N].action) /* The value for the N-th entry in yy_lookahead */ @@ -600,17 +609,19 @@ free( p->aLookahead ); free( p ); } /* Allocate a new acttab structure */ -acttab *acttab_alloc(void){ +acttab *acttab_alloc(int nsymbol, int nterminal){ acttab *p = (acttab *) calloc( 1, sizeof(*p) ); if( p==0 ){ fprintf(stderr,"Unable to allocate memory for a new acttab."); exit(1); } memset(p, 0, sizeof(*p)); + p->nsymbol = nsymbol; + p->nterminal = nterminal; return p; } /* Add a new action to the current transaction set. ** @@ -647,20 +658,28 @@ ** Add the transaction set built up with prior calls to acttab_action() ** into the current action table. Then reset the transaction set back ** to an empty set in preparation for a new round of acttab_action() calls. ** ** Return the offset into the action table of the new transaction. +** +** If the makeItSafe parameter is true, then the offset is chosen so that +** it is impossible to overread the yy_lookaside[] table regardless of +** the lookaside token. This is done for the terminal symbols, as they +** come from external inputs and can contain syntax errors. When makeItSafe +** is false, there is more flexibility in selecting offsets, resulting in +** a smaller table. For non-terminal symbols, which are never syntax errors, +** makeItSafe can be false. */ -int acttab_insert(acttab *p){ - int i, j, k, n; +int acttab_insert(acttab *p, int makeItSafe){ + int i, j, k, n, end; assert( p->nLookahead>0 ); /* Make sure we have enough space to hold the expanded action table ** in the worst case. The worst case occurs if the transaction set ** must be appended to the current action table */ - n = p->mxLookahead + 1; + n = p->nsymbol + 1; if( p->nAction + n >= p->nActionAlloc ){ int oldAlloc = p->nActionAlloc; p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20; p->aAction = (struct lookahead_action *) realloc( p->aAction, sizeof(p->aAction[0])*p->nActionAlloc); @@ -678,11 +697,12 @@ ** duplicate of the current transaction set. Fall out of the loop ** if and when the duplicate is found. ** ** i is the index in p->aAction[] where p->mnLookahead is inserted. */ - for(i=p->nAction-1; i>=0; i--){ + end = makeItSafe ? p->mnLookahead : 0; + for(i=p->nAction-1; i>=end; i--){ if( p->aAction[i].lookahead==p->mnLookahead ){ /* All lookaheads and actions in the aLookahead[] transaction ** must match against the candidate aAction[i] entry. */ if( p->aAction[i].action!=p->mnAction ) continue; for(j=0; jnLookahead; j++){ @@ -708,16 +728,17 @@ /* If no existing offsets exactly match the current transaction, find an ** an empty offset in the aAction[] table in which we can add the ** aLookahead[] transaction. */ - if( i<0 ){ + if( inAction, which means the ** transaction will be appended. */ - for(i=0; inActionAlloc - p->mxLookahead; i++){ + i = makeItSafe ? p->mnLookahead : 0; + for(; inActionAlloc - p->mxLookahead; i++){ if( p->aAction[i].lookahead<0 ){ for(j=0; jnLookahead; j++){ k = p->aLookahead[j].lookahead - p->mnLookahead + i; if( k<0 ) break; if( p->aAction[k].lookahead>=0 ) break; @@ -731,21 +752,39 @@ } } } } /* Insert transaction set at index i. */ +#if 0 + printf("Acttab:"); + for(j=0; jnLookahead; j++){ + printf(" %d", p->aLookahead[j].lookahead); + } + printf(" inserted at %d\n", i); +#endif for(j=0; jnLookahead; j++){ k = p->aLookahead[j].lookahead - p->mnLookahead + i; p->aAction[k] = p->aLookahead[j]; if( k>=p->nAction ) p->nAction = k+1; } + if( makeItSafe && i+p->nterminal>=p->nAction ) p->nAction = i+p->nterminal+1; p->nLookahead = 0; /* Return the offset that is added to the lookahead in order to get the ** index into yy_action of the action */ return i - p->mnLookahead; } + +/* +** Return the size of the action table without the trailing syntax error +** entries. +*/ +int acttab_action_size(acttab *p){ + int n = p->nAction; + while( n>0 && p->aAction[n-1].lookahead<0 ){ n--; } + return n; +} /********************** From the file "build.c" *****************************/ /* ** Routines to construction the finite state machine for the LEMON ** parser generator. @@ -1716,10 +1755,11 @@ stats_line("total symbols", lem.nsymbol); stats_line("rules", lem.nrule); stats_line("states", lem.nxstate); stats_line("conflicts", lem.nconflict); stats_line("action table entries", lem.nactiontab); + stats_line("lookahead table entries", lem.nlookaheadtab); stats_line("total table size (bytes)", lem.tablesize); } if( lem.nconflict > 0 ){ fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict); } @@ -3017,10 +3057,31 @@ lemp->errorcnt++; return 0; } return fp; } + +/* Print the text of a rule +*/ +void rule_print(FILE *out, struct rule *rp){ + int i, j; + fprintf(out, "%s",rp->lhs->name); + /* if( rp->lhsalias ) fprintf(out,"(%s)",rp->lhsalias); */ + fprintf(out," ::="); + for(i=0; inrhs; i++){ + struct symbol *sp = rp->rhs[i]; + if( sp->type==MULTITERMINAL ){ + fprintf(out," %s", sp->subsym[0]->name); + for(j=1; jnsubsym; j++){ + fprintf(out,"|%s", sp->subsym[j]->name); + } + }else{ + fprintf(out," %s", sp->name); + } + /* if( rp->rhsalias[i] ) fprintf(out,"(%s)",rp->rhsalias[i]); */ + } +} /* Duplicate the input file without comments and without actions ** on rules */ void Reprint(struct lemon *lemp) { @@ -3045,25 +3106,11 @@ printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name); } printf("\n"); } for(rp=lemp->rule; rp; rp=rp->next){ - printf("%s",rp->lhs->name); - /* if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */ - printf(" ::="); - for(i=0; inrhs; i++){ - sp = rp->rhs[i]; - if( sp->type==MULTITERMINAL ){ - printf(" %s", sp->subsym[0]->name); - for(j=1; jnsubsym; j++){ - printf("|%s", sp->subsym[j]->name); - } - }else{ - printf(" %s", sp->name); - } - /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */ - } + rule_print(stdout, rp); printf("."); if( rp->precsym ) printf(" [%s]",rp->precsym->name); /* if( rp->code ) printf("\n %s",rp->code); */ printf("\n"); } @@ -3319,20 +3366,23 @@ { int act; switch( ap->type ){ case SHIFT: act = ap->x.stp->statenum; break; case SHIFTREDUCE: { - act = ap->x.rp->iRule + lemp->nstate; /* Since a SHIFT is inherient after a prior REDUCE, convert any ** SHIFTREDUCE action with a nonterminal on the LHS into a simple ** REDUCE action: */ - if( ap->sp->index>=lemp->nterminal ) act += lemp->nrule; + if( ap->sp->index>=lemp->nterminal ){ + act = lemp->minReduce + ap->x.rp->iRule; + }else{ + act = lemp->minShiftReduce + ap->x.rp->iRule; + } break; } - case REDUCE: act = ap->x.rp->iRule + lemp->nstate+lemp->nrule; break; - case ERROR: act = lemp->nstate + lemp->nrule*2; break; - case ACCEPT: act = lemp->nstate + lemp->nrule*2 + 1; break; + case REDUCE: act = lemp->minReduce + ap->x.rp->iRule; break; + case ERROR: act = lemp->errAction; break; + case ACCEPT: act = lemp->accAction; break; default: act = -1; break; } return act; } @@ -4036,10 +4086,17 @@ const char *name; int mnTknOfst, mxTknOfst; int mnNtOfst, mxNtOfst; struct axset *ax; + lemp->minShiftReduce = lemp->nstate; + lemp->errAction = lemp->minShiftReduce + lemp->nrule; + lemp->accAction = lemp->errAction + 1; + lemp->noAction = lemp->accAction + 1; + lemp->minReduce = lemp->noAction + 1; + lemp->maxAction = lemp->minReduce + lemp->nrule; + in = tplt_open(lemp); if( in==0 ) return; out = file_open(lemp,".c","wb"); if( out==0 ){ fclose(in); @@ -4074,11 +4131,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*2+5,&szActionType)); lineno++; + minimum_size_type(0,lemp->maxAction,&szActionType)); lineno++; if( lemp->wildcard ){ fprintf(out,"#define YYWILDCARD %d\n", lemp->wildcard->index); lineno++; } print_stack_union(out,lemp,&lineno,mhflag); @@ -4142,11 +4199,11 @@ mxNtOfst = mnNtOfst = 0; /* 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(); + pActtab = acttab_alloc(lemp->nsymbol, lemp->nterminal); 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; @@ -4153,11 +4210,11 @@ if( ap->sp->index>=lemp->nterminal ) continue; action = compute_action(lemp, ap); if( action<0 ) continue; acttab_action(pActtab, ap->sp->index, action); } - stp->iTknOfst = acttab_insert(pActtab); + stp->iTknOfst = acttab_insert(pActtab, 1); if( stp->iTknOfstiTknOfst; if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst; }else{ for(ap=stp->ap; ap; ap=ap->next){ int action; @@ -4165,11 +4222,11 @@ if( ap->sp->index==lemp->nsymbol ) continue; action = compute_action(lemp, ap); if( action<0 ) continue; acttab_action(pActtab, ap->sp->index, action); } - stp->iNtOfst = acttab_insert(pActtab); + stp->iNtOfst = acttab_insert(pActtab, 0); if( stp->iNtOfstiNtOfst; if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; } #if 0 /* Uncomment for a trace of how the yy_action[] table fills out */ { int jj, nn; @@ -4198,20 +4255,22 @@ /* 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 YYNTOKEN %d\n",lemp->nterminal); lineno++; fprintf(out,"#define YY_MAX_SHIFT %d\n",lemp->nxstate-1); lineno++; - fprintf(out,"#define YY_MIN_SHIFTREDUCE %d\n",lemp->nstate); lineno++; - i = lemp->nstate + lemp->nrule; + i = lemp->minShiftReduce; + fprintf(out,"#define YY_MIN_SHIFTREDUCE %d\n",i); lineno++; + i += 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_ERROR_ACTION %d\n", lemp->errAction); lineno++; + fprintf(out,"#define YY_ACCEPT_ACTION %d\n", lemp->accAction); lineno++; + fprintf(out,"#define YY_NO_ACTION %d\n", lemp->noAction); lineno++; + fprintf(out,"#define YY_MIN_REDUCE %d\n", lemp->minReduce); lineno++; + i = lemp->minReduce + lemp->nrule; 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. @@ -4223,17 +4282,17 @@ ** 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->nactiontab = n = acttab_action_size(pActtab); lemp->tablesize += n*szActionType; fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++; fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++; for(i=j=0; instate + lemp->nrule + 2; + if( action<0 ) action = lemp->noAction; if( j==0 ) fprintf(out," /* %5d */ ", i); fprintf(out, " %4d,", action); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; j = 0; @@ -4242,10 +4301,11 @@ } } fprintf(out, "};\n"); lineno++; /* Output the yy_lookahead table */ + lemp->nlookaheadtab = n = acttab_lookahead_size(pActtab); lemp->tablesize += n*szCodeType; fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++; for(i=j=0; insymbol; @@ -4261,11 +4321,10 @@ fprintf(out, "};\n"); lineno++; /* Output the yy_shift_ofst[] table */ n = lemp->nxstate; while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--; - fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", lemp->nactiontab); lineno++; 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", minimum_size_type(mnTknOfst, lemp->nterminal+lemp->nactiontab, &sz)); @@ -4286,11 +4345,10 @@ } } fprintf(out, "};\n"); lineno++; /* Output the yy_reduce_ofst[] table */ - fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++; 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++; @@ -4318,11 +4376,15 @@ n = lemp->nxstate; lemp->tablesize += n*szActionType; for(i=j=0; isorted[i]; if( j==0 ) fprintf(out," /* %5d */ ", i); - fprintf(out, " %4d,", stp->iDfltReduce+lemp->nstate+lemp->nrule); + if( stp->iDfltReduce<0 ){ + fprintf(out, " %4d,", lemp->errAction); + }else{ + fprintf(out, " %4d,", stp->iDfltReduce + lemp->minReduce); + } if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; j = 0; }else{ j++; @@ -4352,14 +4414,12 @@ /* Generate a table containing the symbolic name of every symbol */ for(i=0; insymbol; i++){ lemon_sprintf(line,"\"%s\",",lemp->symbols[i]->name); - fprintf(out," %-15s",line); - if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; } + fprintf(out," /* %4d */ \"%s\",\n",i, lemp->symbols[i]->name); lineno++; } - if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; } tplt_xfer(lemp->name,in,out,&lineno); /* Generate a table containing a text string that describes every ** rule in the rule set of the grammar. This information is used ** when tracing REDUCE actions. @@ -4399,11 +4459,11 @@ for(i=0; insymbol; i++){ struct symbol *sp = lemp->symbols[i]; if( sp==0 || sp->type==TERMINAL || sp->index<=0 || sp->destructor!=0 ) continue; if( once ){ - fprintf(out, " /* Default NON-TERMINAL Destructor */\n"); lineno++; + fprintf(out, " /* Default NON-TERMINAL Destructor */\n");lineno++; once = 0; } fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++; dflt_sp = sp; } @@ -4442,12 +4502,14 @@ /* Generate the table of rule information ** ** Note: This code depends on the fact that rules are number ** sequentually beginning with 0. */ - for(rp=lemp->rule; rp; rp=rp->next){ - fprintf(out," { %d, %d },\n",rp->lhs->index,-rp->nrhs); lineno++; + for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){ + fprintf(out," { %4d, %4d }, /* (%d) ",rp->lhs->index,-rp->nrhs,i); + rule_print(out, rp); + fprintf(out," */\n"); lineno++; } tplt_xfer(lemp->name,in,out,&lineno); /* Generate code which execution during each REDUCE action */ i = 0; @@ -4709,11 +4771,11 @@ struct action *ap; for(i=0; instate; i++){ stp = lemp->sorted[i]; stp->nTknAct = stp->nNtAct = 0; - stp->iDfltReduce = lemp->nrule; /* Init dflt action to "syntax error" */ + stp->iDfltReduce = -1; /* Init dflt action to "syntax error" */ stp->iTknOfst = NO_OFFSET; stp->iNtOfst = NO_OFFSET; for(ap=stp->ap; ap; ap=ap->next){ int iAction = compute_action(lemp,ap); if( iAction>=0 ){ @@ -4721,11 +4783,11 @@ stp->nTknAct++; }else if( ap->sp->indexnsymbol ){ stp->nNtAct++; }else{ assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp ); - stp->iDfltReduce = iAction - lemp->nstate - lemp->nrule; + stp->iDfltReduce = iAction; } } } } qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]), Index: tool/lempar.c ================================================================== --- tool/lempar.c +++ tool/lempar.c @@ -70,18 +70,19 @@ ** ParseARG_FETCH Code to extract %extra_argument from yypParser ** 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 +** YYNTOKEN Number of terminal symbols ** 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 Minimum value for reduce actions -** YY_MAX_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 +** YY_MIN_REDUCE Minimum value for reduce actions +** YY_MAX_REDUCE Maximum value for reduce actions */ #ifndef INTERFACE # define INTERFACE 1 #endif /************* Begin control #defines *****************************************/ @@ -113,39 +114,33 @@ ** token onto the stack and goto state N. ** ** 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 == YY_ACCEPT_ACTION The parser accepts its input. ** ** N == YY_NO_ACTION No such action. Denotes unused ** slots in the yy_action[] table. +** +** N between YY_MIN_REDUCE Reduce by rule N-YY_MIN_REDUCE +** and YY_MAX_REDUCE ** ** The action table is constructed as a single large table named yy_action[]. ** Given state S and lookahead X, the action is computed as either: ** ** (A) N = yy_action[ yy_shift_ofst[S] + X ] ** (B) N = yy_default[S] ** -** The (A) formula is preferred. The B formula is used instead if: -** (1) The yy_shift_ofst[S]+X value is out of range, or -** (2) yy_lookahead[yy_shift_ofst[S]+X] is not equal to X, or -** (3) yy_shift_ofst[S] equal YY_SHIFT_USE_DFLT. -** (Implementation note: YY_SHIFT_USE_DFLT is chosen so that -** YY_SHIFT_USE_DFLT+X will be out of range for all possible lookaheads X. -** Hence only tests (1) and (2) need to be evaluated.) +** The (A) formula is preferred. The B formula is used instead if +** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X. ** ** The formulas above are for computing the action when the lookahead is ** a terminal symbol. If the lookahead is a non-terminal (as occurs after ** a reduce action) then the yy_reduce_ofst[] array is used in place of -** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of -** YY_SHIFT_USE_DFLT. +** the yy_shift_ofst[] array. ** ** The following are the tables generated in this section: ** ** yy_action[] A single table containing all actions. ** yy_lookahead[] A table containing the lookahead for each entry in @@ -257,17 +252,17 @@ if( yyTraceFILE==0 ) yyTracePrompt = 0; else if( yyTracePrompt==0 ) yyTraceFILE = 0; } #endif /* NDEBUG */ -#ifndef NDEBUG +#if defined(YYCOVERAGE) || !defined(NDEBUG) /* For tracing shifts, the names of all terminals and nonterminals ** are required. The following table supplies these names */ static const char *const yyTokenName[] = { %% }; -#endif /* NDEBUG */ +#endif /* defined(YYCOVERAGE) || !defined(NDEBUG) */ #ifndef NDEBUG /* For tracing reduce actions, the names of all rules are required. */ static const char *const yyRuleName[] = { @@ -459,10 +454,47 @@ yyParser *pParser = (yyParser*)p; return pParser->yyhwm; } #endif +/* This array of booleans keeps track of the parser statement +** coverage. The element yycoverage[X][Y] is set when the parser +** is in state X and has a lookahead token Y. In a well-tested +** systems, every element of this matrix should end up being set. +*/ +#if defined(YYCOVERAGE) +static unsigned char yycoverage[YYNSTATE][YYNTOKEN]; +#endif + +/* +** Write into out a description of every state/lookahead combination that +** +** (1) has not been used by the parser, and +** (2) is not a syntax error. +** +** Return the number of missed state/lookahead combinations. +*/ +#if defined(YYCOVERAGE) +int ParseCoverage(FILE *out){ + int stateno, iLookAhead, i; + int nMissed = 0; + for(stateno=0; statenoyytos->stateno; - if( stateno>=YY_MIN_REDUCE ) return 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]; + assert( i>=0 && i+YYNTOKEN<=sizeof(yy_lookahead)/sizeof(yy_lookahead[0]) ); assert( iLookAhead!=YYNOCODE ); + assert( iLookAhead < YYNTOKEN ); i += iLookAhead; - if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ + if( yy_lookahead[i]!=iLookAhead ){ #ifdef YYFALLBACK YYCODETYPE iFallback; /* Fallback token */ if( iLookAhead=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ return yy_default[stateno]; @@ -576,24 +612,25 @@ /* ** Print tracing information for a SHIFT action */ #ifndef NDEBUG -static void yyTraceShift(yyParser *yypParser, int yyNewState){ +static void yyTraceShift(yyParser *yypParser, int yyNewState, const char *zTag){ if( yyTraceFILE ){ if( yyNewStateyytos->major], + fprintf(yyTraceFILE,"%s%s '%s', go to state %d\n", + yyTracePrompt, zTag, yyTokenName[yypParser->yytos->major], yyNewState); }else{ - fprintf(yyTraceFILE,"%sShift '%s'\n", - yyTracePrompt,yyTokenName[yypParser->yytos->major]); + fprintf(yyTraceFILE,"%s%s '%s', pending reduce %d\n", + yyTracePrompt, zTag, yyTokenName[yypParser->yytos->major], + yyNewState - YY_MIN_REDUCE); } } } #else -# define yyTraceShift(X,Y) +# define yyTraceShift(X,Y,Z) #endif /* ** Perform a shift action. */ @@ -631,11 +668,11 @@ } yytos = yypParser->yytos; yytos->stateno = (YYACTIONTYPE)yyNewState; yytos->major = (YYCODETYPE)yyMajor; yytos->minor.yy0 = yyMinor; - yyTraceShift(yypParser, yyNewState); + yyTraceShift(yypParser, yyNewState, "Shift"); } /* The following table contains information about every rule that ** is used during the reduce. */ @@ -671,12 +708,18 @@ ParseARG_FETCH; yymsp = yypParser->yytos; #ifndef NDEBUG if( yyTraceFILE && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ yysize = yyRuleInfo[yyruleno].nrhs; - fprintf(yyTraceFILE, "%sReduce [%s], go to state %d.\n", yyTracePrompt, - yyRuleName[yyruleno], yymsp[yysize].stateno); + if( yysize ){ + fprintf(yyTraceFILE, "%sReduce %d [%s], go to state %d.\n", + yyTracePrompt, + yyruleno, yyRuleName[yyruleno], yymsp[yysize].stateno); + }else{ + fprintf(yyTraceFILE, "%sReduce %d [%s].\n", + yyTracePrompt, yyruleno, yyRuleName[yyruleno]); + } } #endif /* NDEBUG */ /* Check that the stack is large enough to grow by a single entry ** if the RHS of the rule is empty. This ensures that there is room @@ -727,20 +770,15 @@ assert( !(yyact>YY_MAX_SHIFT && yyact<=YY_MAX_SHIFTREDUCE) ); /* It is not possible for a REDUCE to be followed by an error */ assert( yyact!=YY_ERROR_ACTION ); - if( yyact==YY_ACCEPT_ACTION ){ - yypParser->yytos += yysize; - yy_accept(yypParser); - }else{ - yymsp += yysize+1; - yypParser->yytos = yymsp; - yymsp->stateno = (YYACTIONTYPE)yyact; - yymsp->major = (YYCODETYPE)yygoto; - yyTraceShift(yypParser, yyact); - } + yymsp += yysize+1; + yypParser->yytos = yymsp; + yymsp->stateno = (YYACTIONTYPE)yyact; + yymsp->major = (YYCODETYPE)yygoto; + yyTraceShift(yypParser, yyact, "... then shift"); } /* ** The following code executes when the parse fails */ @@ -846,24 +884,35 @@ #endif ParseARG_STORE; #ifndef NDEBUG if( yyTraceFILE ){ - fprintf(yyTraceFILE,"%sInput '%s'\n",yyTracePrompt,yyTokenName[yymajor]); + int stateno = yypParser->yytos->stateno; + if( stateno < YY_MIN_REDUCE ){ + fprintf(yyTraceFILE,"%sInput '%s' in state %d\n", + yyTracePrompt,yyTokenName[yymajor],stateno); + }else{ + fprintf(yyTraceFILE,"%sInput '%s' with pending reduce %d\n", + yyTracePrompt,yyTokenName[yymajor],stateno-YY_MIN_REDUCE); + } } #endif do{ yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); - if( yyact <= YY_MAX_SHIFTREDUCE ){ + if( yyact >= YY_MIN_REDUCE ){ + yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor); + }else if( yyact <= YY_MAX_SHIFTREDUCE ){ yy_shift(yypParser,yyact,yymajor,yyminor); #ifndef YYNOERRORRECOVERY yypParser->yyerrcnt--; #endif yymajor = YYNOCODE; - }else if( yyact <= YY_MAX_REDUCE ){ - yy_reduce(yypParser,yyact-YY_MIN_REDUCE,yymajor,yyminor); + }else if( yyact==YY_ACCEPT_ACTION ){ + yypParser->yytos--; + yy_accept(yypParser); + return; }else{ assert( yyact == YY_ERROR_ACTION ); yyminorunion.yy0 = yyminor; #ifdef YYERRORSYMBOL int yymx;