diff options
| -rwxr-xr-x | tools/checklicenses.py | 3 | ||||
| -rw-r--r-- | tools/lemon/lemon.c | 381 | ||||
| -rw-r--r-- | tools/lemon/lempar.c | 394 |
3 files changed, 492 insertions, 286 deletions
diff --git a/tools/checklicenses.py b/tools/checklicenses.py index 1ba939fb95..39b1b6dfa2 100755 --- a/tools/checklicenses.py +++ b/tools/checklicenses.py @@ -177,6 +177,9 @@ PATH_SPECIFIC_WHITELISTED_LICENSES = { 'epan/dfilter/grammar.h': [ 'UNKNOWN', ], + 'epan/dfilter/grammar.c': [ + 'UNKNOWN', + ], 'plugins/mate/mate_grammar.h': [ 'UNKNOWN', ], diff --git a/tools/lemon/lemon.c b/tools/lemon/lemon.c index 9dd33d6c50..a5030d68dc 100644 --- a/tools/lemon/lemon.c +++ b/tools/lemon/lemon.c @@ -16,6 +16,14 @@ #include <stdlib.h> #include <assert.h> +#define ISSPACE(X) isspace((unsigned char)(X)) +#define ISDIGIT(X) isdigit((unsigned char)(X)) +#define ISALNUM(X) isalnum((unsigned char)(X)) +#define ISALPHA(X) isalpha((unsigned char)(X)) +#define ISUPPER(X) isupper((unsigned char)(X)) +#define ISLOWER(X) islower((unsigned char)(X)) + + #ifndef __WIN32__ # if defined(_WIN32) || defined(WIN32) # define __WIN32__ @@ -58,7 +66,7 @@ static char *msort(char*,char**,int(*)(const char*,const char*)); ** saying they are unsafe. So we define our own versions of those routines too. ** ** There are three routines here: lemon_sprintf(), lemon_vsprintf(), and -** lemon_addtext(). The first two are replacements for sprintf() and vsprintf(). +** lemon_addtext(). The first two are replacements for sprintf() and vsprintf(). ** The third is a helper routine for vsnprintf() that adds texts to the end of a ** buffer, making sure the buffer is always zero-terminated. ** @@ -96,9 +104,9 @@ static int lemon_vsprintf(char *str, const char *zFormat, va_list ap){ int iWidth = 0; lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0); c = zFormat[++i]; - if( isdigit(c) || (c=='-' && isdigit(zFormat[i+1])) ){ + if( ISDIGIT(c) || (c=='-' && ISDIGIT(zFormat[i+1])) ){ if( c=='-' ) i++; - while( isdigit(zFormat[i]) ) iWidth = iWidth*10 + zFormat[i++] - '0'; + while( ISDIGIT(zFormat[i]) ) iWidth = iWidth*10 + zFormat[i++] - '0'; if( c=='-' ) iWidth = -iWidth; c = zFormat[i]; } @@ -322,7 +330,8 @@ enum e_action { 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 */ @@ -346,7 +355,9 @@ struct 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 */ + 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) @@ -366,6 +377,7 @@ 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 */ @@ -392,7 +404,8 @@ struct lemon { 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 tablesize; /* Size of the parse tables */ + int nactiontab; /* Number of entries in the yy_action[] table */ + 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 */ @@ -490,7 +503,7 @@ static int actioncmp( 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 ){ @@ -1394,14 +1407,16 @@ void Configlist_closure(struct lemon *lemp) /* Sort the configuration list */ void Configlist_sort(void){ - current = (struct config *)msort((char *)current,(char **)&(current->next),Configcmp); + current = (struct config*)msort((char*)current,(char**)&(current->next), + Configcmp); currentend = 0; return; } /* Sort the basis configuration list */ void Configlist_sortbasis(void){ - basis = (struct config *)msort((char *)current,(char **)&(current->bp),Configcmp); + basis = (struct config*)msort((char*)current,(char**)&(current->bp), + Configcmp); basisend = 0; return; } @@ -1536,6 +1551,18 @@ static void handle_T_option(void *arg){ lemon_strcpy(user_templatename, z); } +/* forward reference */ +static const char *minimum_size_type(int lwr, int upr, int *pnByte); + +/* Print a single line of the "Parser Stats" output +*/ +static void stats_line(const char *zLabel, int iValue){ + int nLabel = lemonStrlen(zLabel); + printf(" %s%.*s %5d\n", zLabel, + 35-nLabel, "................................", + iValue); +} + /* The main program. Parse the command line and do it... */ int main(int argc _U_, char **argv) { @@ -1618,7 +1645,7 @@ int main(int argc _U_, char **argv) while( lem.symbols[i-1]->type==MULTITERMINAL ){ i--; } assert( strcmp(lem.symbols[i-1]->name,"{default}")==0 ); lem.nsymbol = i - 1; - for(i=1; isupper(lem.symbols[i]->name[0]); i++); + for(i=1; ISUPPER(lem.symbols[i]->name[0]); i++); lem.nterminal = i; /* Generate a reprint of the grammar, if requested on the command line */ @@ -1670,10 +1697,15 @@ int main(int argc _U_, char **argv) if( !mhflag ) ReportHeader(&lem); } if( statistics ){ - printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n", - lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule); - printf(" %d states, %d parser table entries, %d conflicts\n", - lem.nstate, lem.tablesize, lem.nconflict); + 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.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 ){ fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict); @@ -1932,7 +1964,8 @@ static int handleswitch(int i, FILE *err) dv = strtod(cp,&end); if( *end ){ if( err ){ - fprintf(err,"%sillegal character in floating-point argument.\n",emsg); + fprintf(err, + "%sillegal character in floating-point argument.\n",emsg); errline(i,(int)((char*)end-(char*)argv[i]),err); } errcnt++; @@ -2155,7 +2188,7 @@ static void parseonetoken(struct pstate *psp) case WAITING_FOR_DECL_OR_RULE: if( x[0]=='%' ){ psp->state = WAITING_FOR_DECL_KEYWORD; - }else if( islower(x[0]) ){ + }else if( ISLOWER(x[0]) ){ psp->lhs = Symbol_new(x); psp->nrhs = 0; psp->lhsalias = 0; @@ -2185,7 +2218,7 @@ to follow the previous rule."); } break; case PRECEDENCE_MARK_1: - if( !isupper(x[0]) ){ + if( !ISUPPER(x[0]) ){ ErrorMsg(psp->filename,psp->tokenlineno, "The precedence symbol must be a terminal."); psp->errorcnt++; @@ -2225,7 +2258,7 @@ to follow the previous rule."); } break; case LHS_ALIAS_1: - if( isalpha(x[0]) ){ + if( ISALPHA(x[0]) ){ psp->lhsalias = x; psp->state = LHS_ALIAS_2; }else{ @@ -2294,7 +2327,7 @@ to follow the previous rule."); psp->prevrule = rp; } psp->state = WAITING_FOR_DECL_OR_RULE; - }else if( isalpha(x[0]) ){ + }else if( ISALPHA(x[0]) ){ if( psp->nrhs>=MAXRHS ){ ErrorMsg(psp->filename,psp->tokenlineno, "Too many symbols on RHS of rule beginning at \"%s\".", @@ -2323,7 +2356,7 @@ to follow the previous rule."); msp->subsym = (struct symbol **) realloc(msp->subsym, sizeof(struct symbol*)*msp->nsubsym); msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]); - if( islower(x[1]) || islower(msp->subsym[0]->name[0]) ){ + if( ISLOWER(x[1]) || ISLOWER(msp->subsym[0]->name[0]) ){ ErrorMsg(psp->filename,psp->tokenlineno, "Cannot form a compound containing a non-terminal"); psp->errorcnt++; @@ -2338,7 +2371,7 @@ to follow the previous rule."); } break; case RHS_ALIAS_1: - if( isalpha(x[0]) ){ + if( ISALPHA(x[0]) ){ psp->alias[psp->nrhs-1] = x; psp->state = RHS_ALIAS_2; }else{ @@ -2360,7 +2393,7 @@ to follow the previous rule."); } break; case WAITING_FOR_DECL_KEYWORD: - if( isalpha(x[0]) ){ + if( ISALPHA(x[0]) ){ psp->declkeyword = x; psp->declargslot = 0; psp->decllinenoslot = 0; @@ -2440,7 +2473,7 @@ to follow the previous rule."); } break; case WAITING_FOR_DESTRUCTOR_SYMBOL: - if( !isalpha(x[0]) ){ + if( !ISALPHA(x[0]) ){ ErrorMsg(psp->filename,psp->tokenlineno, "Symbol name missing after %%destructor keyword"); psp->errorcnt++; @@ -2454,7 +2487,7 @@ to follow the previous rule."); } break; case WAITING_FOR_DATATYPE_SYMBOL: - if( !isalpha(x[0]) ){ + if( !ISALPHA(x[0]) ){ ErrorMsg(psp->filename,psp->tokenlineno, "Symbol name missing after %%type keyword"); psp->errorcnt++; @@ -2479,7 +2512,7 @@ to follow the previous rule."); case WAITING_FOR_PRECEDENCE_SYMBOL: if( x[0]=='.' ){ psp->state = WAITING_FOR_DECL_OR_RULE; - }else if( isupper(x[0]) ){ + }else if( ISUPPER(x[0]) ){ struct symbol *sp; sp = Symbol_new(x); if( sp->prec>=0 ){ @@ -2497,7 +2530,7 @@ to follow the previous rule."); } break; case WAITING_FOR_DECL_ARG: - if( x[0]=='{' || x[0]=='\"' || isalnum(x[0]) ){ + if( x[0]=='{' || x[0]=='\"' || ISALNUM(x[0]) ){ const char *zOld, *zNew; char *zBuf, *z; int nOld, n, nLine = 0, nNew, nBack; @@ -2558,7 +2591,7 @@ to follow the previous rule."); case WAITING_FOR_FALLBACK_ID: if( x[0]=='.' ){ psp->state = WAITING_FOR_DECL_OR_RULE; - }else if( !isupper(x[0]) ){ + }else if( !ISUPPER(x[0]) ){ ErrorMsg(psp->filename, psp->tokenlineno, "%%fallback argument \"%s\" should be a token", x); psp->errorcnt++; @@ -2579,7 +2612,7 @@ to follow the previous rule."); case WAITING_FOR_WILDCARD_ID: if( x[0]=='.' ){ psp->state = WAITING_FOR_DECL_OR_RULE; - }else if( !isupper(x[0]) ){ + }else if( !ISUPPER(x[0]) ){ ErrorMsg(psp->filename, psp->tokenlineno, "%%wildcard argument \"%s\" should be a token", x); psp->errorcnt++; @@ -2595,7 +2628,7 @@ to follow the previous rule."); } break; case WAITING_FOR_CLASS_ID: - if( !islower(x[0]) ){ + if( !ISLOWER(x[0]) ){ ErrorMsg(psp->filename, psp->tokenlineno, "%%token_class must be followed by an identifier: ", x); psp->errorcnt++; @@ -2614,12 +2647,12 @@ to follow the previous rule."); case WAITING_FOR_CLASS_TOKEN: if( x[0]=='.' ){ psp->state = WAITING_FOR_DECL_OR_RULE; - }else if( isupper(x[0]) || ((x[0]=='|' || x[0]=='/') && isupper(x[1])) ){ + }else if( ISUPPER(x[0]) || ((x[0]=='|' || x[0]=='/') && ISUPPER(x[1])) ){ struct symbol *msp = psp->tkclass; msp->nsubsym++; msp->subsym = (struct symbol **) realloc(msp->subsym, sizeof(struct symbol*)*msp->nsubsym); - if( !isupper(x[0]) ) x++; + if( !ISUPPER(x[0]) ) x++; msp->subsym[msp->nsubsym-1] = Symbol_new(x); }else{ ErrorMsg(psp->filename, psp->tokenlineno, @@ -2652,7 +2685,7 @@ static void preprocess_input(char *z){ for(i=0; z[i]; i++){ if( z[i]=='\n' ) lineno++; if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue; - if( strncmp(&z[i],"%endif",6)==0 && isspace(z[i+6]) ){ + if( strncmp(&z[i],"%endif",6)==0 && ISSPACE(z[i+6]) ){ if( exclude ){ exclude--; if( exclude==0 ){ @@ -2660,13 +2693,13 @@ static void preprocess_input(char *z){ } } for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' '; - }else if( (strncmp(&z[i],"%ifdef",6)==0 && isspace(z[i+6])) - || (strncmp(&z[i],"%ifndef",7)==0 && isspace(z[i+7])) ){ + }else if( (strncmp(&z[i],"%ifdef",6)==0 && ISSPACE(z[i+6])) + || (strncmp(&z[i],"%ifndef",7)==0 && ISSPACE(z[i+7])) ){ if( exclude ){ exclude++; }else{ - for(j=i+7; isspace(z[j]); j++){} - for(n=0; z[j+n] && !isspace(z[j+n]); n++){} + for(j=i+7; ISSPACE(z[j]); j++){} + for(n=0; z[j+n] && !ISSPACE(z[j+n]); n++){} exclude = 1; for(k=0; k<nDefine; k++){ if( strncmp(azDefine[k],&z[j],n)==0 && lemonStrlen(azDefine[k])==n ){ @@ -2747,7 +2780,7 @@ void Parse(struct lemon *gp) lineno = 1; for(cp=filebuf; (c= *cp)!=0; ){ if( c=='\n' ) lineno++; /* Keep track of the line number */ - if( isspace(c) ){ cp++; continue; } /* Skip all white space */ + if( ISSPACE(c) ){ cp++; continue; } /* Skip all white space */ if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments */ cp+=2; while( (c= *cp)!=0 && c!='\n' ) cp++; @@ -2817,15 +2850,15 @@ void Parse(struct lemon *gp) }else{ nextcp = cp+1; } - }else if( isalnum(c) ){ /* Identifiers */ - while( (c= *cp)!=0 && (isalnum(c) || c=='_') ) cp++; + }else if( ISALNUM(c) ){ /* Identifiers */ + while( (c= *cp)!=0 && (ISALNUM(c) || c=='_') ) cp++; nextcp = cp; }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */ cp += 3; nextcp = cp; - }else if( (c=='/' || c=='|') && isalpha(cp[1]) ){ + }else if( (c=='/' || c=='|') && ISALPHA(cp[1]) ){ cp += 2; - while( (c = *cp)!=0 && (isalnum(c) || c=='_') ) cp++; + while( (c = *cp)!=0 && (ISALNUM(c) || c=='_') ) cp++; nextcp = cp; }else{ /* All other (one character) operators */ cp++; @@ -3011,15 +3044,14 @@ void Reprint(struct lemon *lemp) } } -PRIVATE void ConfigPrint(FILE *fp, struct config *cfp) -{ - struct rule *rp; +/* Print a single rule. +*/ +PRIVATE void RulePrint(FILE *fp, struct rule *rp, int iCursor){ struct symbol *sp; int i, j; - rp = cfp->rp; fprintf(fp,"%s ::=",rp->lhs->name); for(i=0; i<=rp->nrhs; i++){ - if( i==cfp->dot ) fprintf(fp," *"); + if( i==iCursor ) fprintf(fp," *"); if( i==rp->nrhs ) break; sp = rp->rhs[i]; if( sp->type==MULTITERMINAL ){ @@ -3033,6 +3065,12 @@ PRIVATE void ConfigPrint(FILE *fp, struct config *cfp) } } +/* Print the rule for a configuration. +*/ +PRIVATE void ConfigPrint(FILE *fp, struct config *cfp){ + RulePrint(fp, cfp->rp, cfp->dot); +} + /* #define TEST */ #if 0 /* Print a set */ @@ -3072,15 +3110,30 @@ char *tag; /* Print an action to the given file descriptor. Return FALSE if ** nothing was actually printed. */ -PRIVATE int PrintAction(struct action *ap, FILE *fp, int indent){ +PRIVATE int PrintAction( + struct action *ap, /* The action to print */ + FILE *fp, /* Print the action here */ + int indent /* Indent by this amount */ +){ int result = 1; switch( ap->type ){ - case SHIFT: - fprintf(fp,"%*s shift %d",indent,ap->sp->name,ap->x.stp->statenum); + case SHIFT: { + struct state *stp = ap->x.stp; + fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum); break; - case REDUCE: - fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index); + } + case REDUCE: { + struct rule *rp = ap->x.rp; + 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; @@ -3089,16 +3142,16 @@ PRIVATE int PrintAction(struct action *ap, FILE *fp, int indent){ break; case SRCONFLICT: case RRCONFLICT: - fprintf(fp,"%*s reduce %-3d ** Parsing conflict **", + fprintf(fp,"%*s reduce %-7d ** Parsing conflict **", indent,ap->sp->name,ap->x.rp->index); break; case SSCONFLICT: - fprintf(fp,"%*s shift %-3d ** 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 %-3d -- dropped by precedence", + fprintf(fp,"%*s shift %-7d -- dropped by precedence", indent,ap->sp->name,ap->x.stp->statenum); }else{ result = 0; @@ -3106,7 +3159,7 @@ PRIVATE int PrintAction(struct action *ap, FILE *fp, int indent){ break; case RD_RESOLVED: if( showPrecedenceConflict ){ - fprintf(fp,"%*s reduce %-3d -- dropped by precedence", + fprintf(fp,"%*s reduce %-7d -- dropped by precedence", indent,ap->sp->name,ap->x.rp->index); }else{ result = 0; @@ -3119,7 +3172,7 @@ PRIVATE int PrintAction(struct action *ap, FILE *fp, int indent){ return result; } -/* Generate the "y.output" log file */ +/* Generate the "*.out" log file */ void ReportOutput(struct lemon *lemp) { int i; @@ -3130,7 +3183,7 @@ void ReportOutput(struct lemon *lemp) fp = file_open(lemp,".out","wb"); if( fp==0 ) return; - for(i=0; i<lemp->nstate; i++){ + for(i=0; i<lemp->nxstate; i++){ stp = lemp->sorted[i]; fprintf(fp,"State %d:\n",stp->statenum); if( lemp->basisflag ) cfp=stp->bp; @@ -3240,10 +3293,11 @@ 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; @@ -3269,7 +3323,7 @@ PRIVATE void tplt_xfer(char *name, FILE *in, FILE *out, int *lineno) if( name ){ for(i=0; line[i]; i++){ if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0 - && (i==0 || !isalpha(line[i-1])) + && (i==0 || !ISALPHA(line[i-1])) ){ if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]); fprintf(out,"%s",name); @@ -3302,7 +3356,8 @@ PRIVATE FILE *tplt_open(struct lemon *lemp) } in = fopen(user_templatename,"rb"); if( in==0 ){ - fprintf(stderr,"Can't open the template file \"%s\".\n",user_templatename); + fprintf(stderr,"Can't open the template file \"%s\".\n", + user_templatename); lemp->errorcnt++; return 0; } @@ -3387,7 +3442,10 @@ PRIVATE void emit_destructor_code( }else if( sp->destructor ){ cp = sp->destructor; fprintf(out,"{\n"); (*lineno)++; - if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,sp->destLineno,lemp->filename); } + if( !lemp->nolinenosflag ){ + (*lineno)++; + tplt_linedir(out,sp->destLineno,lemp->filename); + } }else if( lemp->vardest ){ cp = lemp->vardest; if( cp==0 ) return; @@ -3502,9 +3560,9 @@ PRIVATE void translate_code(struct lemon *lemp, struct rule *rp){ /* This const cast is wrong but harmless, if we're careful. */ for(cp=(char *)rp->code; *cp; cp++){ - if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){ + if( ISALPHA(*cp) && (cp==rp->code || (!ISALNUM(cp[-1]) && cp[-1]!='_')) ){ char saved; - for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++); + for(xp= &cp[1]; ISALNUM(*xp) || *xp=='_'; xp++); saved = *xp; *xp = 0; if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){ @@ -3584,13 +3642,19 @@ PRIVATE void emit_code( /* Generate code to do the reduce action */ if( rp->code ){ - if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,rp->line,lemp->filename); } + if( !lemp->nolinenosflag ){ + (*lineno)++; + tplt_linedir(out,rp->line,lemp->filename); + } fprintf(out,"{%s",rp->code); for(cp=rp->code; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; } /* End loop */ fprintf(out,"}\n"); (*lineno)++; - if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,*lineno,lemp->outname); } + if( !lemp->nolinenosflag ){ + (*lineno)++; + tplt_linedir(out,*lineno,lemp->outname); + } } /* End if( rp->code ) */ return; @@ -3663,9 +3727,9 @@ PRIVATE void print_stack_union( cp = sp->datatype; if( cp==0 ) cp = lemp->vartype; j = 0; - while( isspace(*cp) ) cp++; + while( ISSPACE(*cp) ) cp++; while( *cp ) stddt[j++] = *cp++; - while( j>0 && isspace(stddt[j-1]) ) j--; + while( j>0 && ISSPACE(stddt[j-1]) ) j--; stddt[j] = 0; if( lemp->tokentype && strcmp(stddt, lemp->tokentype)==0 ){ sp->dtnum = 0; @@ -3720,24 +3784,32 @@ PRIVATE void print_stack_union( /* ** Return the name of a C datatype able to represent values between -** lwr and upr, inclusive. +** lwr and upr, inclusive. If pnByte!=NULL then also write the sizeof +** for that type (1, 2, or 4) into *pnByte. */ -static const char *minimum_size_type(int lwr, int upr){ +static const char *minimum_size_type(int lwr, int upr, int *pnByte){ + const char *zType = "int"; + int nByte = 4; if( lwr>=0 ){ if( upr<=255 ){ - return "unsigned char"; + zType = "unsigned char"; + nByte = 1; }else if( upr<65535 ){ - return "unsigned short int"; + zType = "unsigned short int"; + nByte = 2; }else{ - return "unsigned int"; + zType = "unsigned int"; + nByte = 4; } }else if( lwr>=-127 && upr<=127 ){ - return "signed char"; + zType = "signed char"; + nByte = 1; }else if( lwr>=-32767 && upr<32767 ){ - return "short"; - }else{ - return "int"; + zType = "short"; + nByte = 2; } + if( pnByte ) *pnByte = nByte; + return zType; } /* @@ -3762,7 +3834,7 @@ static int axset_compare(const void *a, const void *b){ int c; c = p2->nAction - p1->nAction; if( c==0 ){ - c = p2->iOrder - p1->iOrder; + c = p1->iOrder - p2->iOrder; } assert( c!=0 || p1==p2 ); return c; @@ -3801,7 +3873,9 @@ void ReportTable( struct action *ap; struct rule *rp; struct acttab *pActtab; - int i, j, n; + int i, j, n, sz; + int szActionType; /* sizeof(YYACTIONTYPE) */ + int szCodeType; /* sizeof(YYCODETYPE) */ const char *name; int mnTknOfst, mxTknOfst; int mnNtOfst, mxNtOfst; @@ -3842,10 +3916,10 @@ void ReportTable( /* Generate the defines */ fprintf(out,"#define YYCODETYPE %s\n", - minimum_size_type(0, lemp->nsymbol+1)); lineno++; + 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)); 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++; @@ -3864,8 +3938,8 @@ void ReportTable( name = lemp->name ? lemp->name : "Parse"; if( lemp->arg && lemp->arg[0] ){ i = lemonStrlen(lemp->arg); - while( i>=1 && isspace(lemp->arg[i-1]) ) i--; - while( i>=1 && (isalnum(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--; + while( i>=1 && ISSPACE(lemp->arg[i-1]) ) i--; + while( i>=1 && (ISALNUM(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--; fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg); lineno++; fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg); lineno++; fprintf(out,"#define %sARG_FETCH %s = yypParser->%s\n", @@ -3881,36 +3955,24 @@ void ReportTable( 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; i<lemp->nstate; i++){ + for(i=0; i<lemp->nxstate; i++){ stp = lemp->sorted[i]; ax[i*2].stp = stp; ax[i*2].isTkn = 1; @@ -3921,15 +3983,12 @@ void ReportTable( } 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; i<lemp->nstate*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; i<lemp->nxstate*2; i++) ax[i].iOrder = i; + qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare); pActtab = acttab_alloc(); - for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){ + for(i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++){ stp = ax[i].stp; if( ax[i].isTkn ){ for(ap=stp->ap; ap; ap=ap->next){ @@ -3955,11 +4014,50 @@ void ReportTable( if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst; if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst; } +#if 0 /* Uncomment for a trace of how the yy_action[] table fills out */ + { int jj, nn; + for(jj=nn=0; jj<pActtab->nAction; jj++){ + if( pActtab->aAction[jj].action<0 ) nn++; + } + printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n", + i, stp->statenum, ax[i].isTkn ? "Token" : "Var ", + ax[i].nAction, pActtab->nAction, nn); + } +#endif } 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->nxstate-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 */ - n = acttab_size(pActtab); + lemp->nactiontab = n = acttab_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; i<n; i++){ @@ -3977,6 +4075,7 @@ void ReportTable( fprintf(out, "};\n"); lineno++; /* Output the yy_lookahead table */ + lemp->tablesize += n*szCodeType; fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++; for(i=j=0; i<n; i++){ int la = acttab_yylookahead(pActtab, i); @@ -3994,13 +4093,14 @@ void ReportTable( /* 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", - minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++; + minimum_size_type(mnTknOfst-1, mxTknOfst, &sz)); lineno++; + lemp->tablesize += n*sz; for(i=j=0; i<n; i++){ int ofst; stp = lemp->sorted[i]; @@ -4019,13 +4119,14 @@ void ReportTable( /* 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", - minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++; + minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++; + lemp->tablesize += n*sz; for(i=j=0; i<n; i++){ int ofst; stp = lemp->sorted[i]; @@ -4044,11 +4145,12 @@ void ReportTable( /* 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; i<n; i++){ stp = lemp->sorted[i]; if( j==0 ) fprintf(out," /* %5d */ ", i); - fprintf(out, " %4d,", stp->iDflt); + fprintf(out, " %4d,", stp->iDfltReduce+lemp->nstate+lemp->nrule); if( j==9 || i==n-1 ){ fprintf(out, "\n"); lineno++; j = 0; @@ -4064,6 +4166,7 @@ void ReportTable( if( lemp->has_fallback ){ int mx = lemp->nterminal - 1; while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; } + lemp->tablesize += (mx+1)*szCodeType; for(i=0; i<=mx; i++){ struct symbol *p = lemp->symbols[i]; if( p->fallback==0 ){ @@ -4328,6 +4431,32 @@ void CompressTables(struct lemon *lemp) 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; i<lemp->nstate; 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; + } + } } } @@ -4368,17 +4497,19 @@ void ResortStates(struct lemon *lemp) for(i=0; i<lemp->nstate; i++){ stp = lemp->sorted[i]; stp->nTknAct = stp->nNtAct = 0; - stp->iDflt = lemp->nstate + 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->index<lemp->nterminal ){ stp->nTknAct++; }else if( ap->sp->index<lemp->nsymbol ){ stp->nNtAct++; }else{ - stp->iDflt = compute_action(lemp, ap); + assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp ); + stp->iDfltReduce = iAction - lemp->nstate - lemp->nrule; } } } @@ -4388,6 +4519,10 @@ void ResortStates(struct lemon *lemp) for(i=0; i<lemp->nstate; i++){ lemp->sorted[i]->statenum = i; } + lemp->nxstate = lemp->nstate; + while( lemp->nxstate>1 && lemp->sorted[lemp->nxstate-1]->autoReduce ){ + lemp->nxstate--; + } } @@ -4611,7 +4746,7 @@ struct symbol *Symbol_new(const char *x) sp = (struct symbol *)calloc(1, sizeof(struct symbol) ); MemoryCheck(sp); sp->name = Strsafe(x); - sp->type = isupper(*x) ? TERMINAL : NONTERMINAL; + sp->type = ISUPPER(*x) ? TERMINAL : NONTERMINAL; sp->rule = 0; sp->fallback = 0; sp->prec = -1; diff --git a/tools/lemon/lempar.c b/tools/lemon/lempar.c index f560dce69d..f945261255 100644 --- a/tools/lemon/lempar.c +++ b/tools/lemon/lempar.c @@ -1,64 +1,91 @@ -/* Driver template for the LEMON parser generator. -** The author disclaims copyright to this source code. -*/ -/* First off, code is included that follows the "include" declaration -** in the input grammar file. */ -#include <stdio.h> -%% -/* Next is all token values, in a form suitable for use by makeheaders. -** This section will be null unless lemon is run with the -m switch. -*/ /* -** These constants (all generated automatically by the parser generator) -** specify the various kinds of tokens (terminals) that the parser -** understands. +** 2000-05-29 +** +** The author disclaims copyright to this source code. In place of +** a legal notice, here is a blessing: +** +** May you do good and not evil. +** May you find forgiveness for yourself and forgive others. +** May you share freely, never taking more than you give. ** -** Each symbol here is a terminal symbol in the grammar. +************************************************************************* +** Driver template for the LEMON parser generator. +** +** The "lemon" program processes an LALR(1) input grammar file, then uses +** this template to construct a parser. The "lemon" program inserts text +** at each "%%" line. Also, any "P-a-r-s-e" identifer prefix (without the +** interstitial "-" characters) contained in this template is changed into +** the value of the %name directive from the grammar. Otherwise, the content +** of this template is copied straight through into the generate parser +** source file. +** +** The following is the concatenation of all %include directives from the +** input grammar file: */ +#include <stdio.h> +/************ Begin %include sections from the grammar ************************/ %% -/* Make sure the INTERFACE macro is defined. -*/ -#ifndef INTERFACE -# define INTERFACE 1 -#endif -/* The next thing included is series of defines which control +/**************** End of %include directives **********************************/ +/* These constants specify the various numeric values for terminal symbols +** in a format understandable to "makeheaders". This section is blank unless +** "lemon" is run with the "-m" command-line option. +***************** Begin makeheaders token definitions *************************/ +%% +/**************** End makeheaders token definitions ***************************/ + +/* The next sections is a series of control #defines. ** various aspects of the generated parser. -** YYCODETYPE is the data type used for storing terminal -** and nonterminal numbers. "unsigned char" is -** used if there are fewer than 250 terminals -** and nonterminals. "int" is used otherwise. -** YYNOCODE is a number of type YYCODETYPE which corresponds -** to no legal terminal or nonterminal number. This -** number is used to fill in empty slots of the hash -** table. +** YYCODETYPE is the data type used to store the integer codes +** that represent terminal and non-terminal symbols. +** "unsigned char" is used if there are fewer than +** 256 symbols. Larger types otherwise. +** YYNOCODE is a number of type YYCODETYPE that is not used for +** any terminal or nonterminal symbol. ** YYFALLBACK If defined, this indicates that one or more tokens -** have fall-back values which should be used if the -** original value of the token will not parse. -** YYACTIONTYPE is the data type used for storing terminal -** and nonterminal numbers. "unsigned char" is -** used if there are fewer than 250 rules and -** states combined. "int" is used otherwise. -** ParseTOKENTYPE is the data type used for minor tokens given -** directly to the parser from the tokenizer. -** YYMINORTYPE is the data type used for all minor tokens. +** (also known as: "terminal symbols") have fall-back +** values which should be used if the original symbol +** would not parse. This permits keywords to sometimes +** be used as identifiers, for example. +** YYACTIONTYPE is the data type used for "action codes" - numbers +** that indicate what to do in response to the next +** token. +** ParseTOKENTYPE is the data type used for minor type for terminal +** symbols. Background: A "minor type" is a semantic +** value associated with a terminal or non-terminal +** symbols. For example, for an "ID" terminal symbol, +** the minor type might be the name of the identifier. +** Each non-terminal can have a different minor type. +** Terminal symbols all have the same minor type, though. +** This macros defines the minor type for terminal +** symbols. +** YYMINORTYPE is the data type used for all minor types. ** This is typically a union of many types, one of ** which is ParseTOKENTYPE. The entry in the union -** for base tokens is called "yy0". +** for terminal symbols is called "yy0". ** YYSTACKDEPTH is the maximum depth of the parser's stack. If ** 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 */ +#ifndef INTERFACE +# define INTERFACE 1 +#endif +/************* Begin control #defines *****************************************/ %% -#define YY_NO_ACTION (YYNSTATE+YYNRULE+2) -#define YY_ACCEPT_ACTION (YYNSTATE+YYNRULE+1) -#define YY_ERROR_ACTION (YYNSTATE+YYNRULE) +/************* End control #defines *******************************************/ /* The yyzerominor constant is used to initialize instances of ** YYMINORTYPE objects to zero. */ @@ -85,16 +112,20 @@ static const YYMINORTYPE yyzerominor = { 0 }; ** 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 == YYNSTATE+YYNRULE A syntax error has occurred. +** 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+1 The parser accepts its input. +** N == YY_ACCEPT_ACTION 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[]. @@ -123,11 +154,13 @@ static const YYMINORTYPE yyzerominor = { 0 }; ** 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. -*/ +** +*********** Begin parsing tables **********************************************/ %% +/********** End of lemon-generated parsing tables *****************************/ -/* The next table maps tokens into fallback tokens. If a construct -** like the following: +/* The next table maps tokens (terminal symbols) into fallback tokens. +** If a construct like the following: ** ** %fallback ID X Y Z. ** @@ -135,6 +168,10 @@ static const YYMINORTYPE yyzerominor = { 0 }; ** and Z. Whenever one of the tokens X, Y, or Z is input to the parser ** but it does not parse, the type of the token is changed to ID and ** the parse is retried before an error is thrown. +** +** This feature can be used, for example, to cause some keywords in a language +** to revert to identifiers if they keyword does not apply in the context where +** it appears. */ #ifdef YYFALLBACK static const YYCODETYPE yyFallback[] = { @@ -153,9 +190,13 @@ static const YYCODETYPE yyFallback[] = { ** + 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 @@ -253,6 +294,15 @@ static void yyGrowStack(yyParser *p){ } #endif +/* Datatype of the argument to the memory allocated passed as the +** second argument to ParseAlloc() below. This can be changed by +** putting an appropriate #define in the %include section of the input +** grammar. +*/ +#ifndef YYMALLOCARGTYPE +# define YYMALLOCARGTYPE size_t +#endif + /* ** This function allocates a new parser. ** The only argument is a pointer to a function which works like @@ -265,9 +315,9 @@ static void yyGrowStack(yyParser *p){ ** A pointer to a parser. This pointer is used in subsequent calls ** to Parse and ParseFree. */ -void *ParseAlloc(void *(*mallocProc)(size_t)){ +void *ParseAlloc(void *(*mallocProc)(YYMALLOCARGTYPE)){ yyParser *pParser; - pParser = (yyParser*)(*mallocProc)( (size_t)sizeof(yyParser) ); + pParser = (yyParser*)(*mallocProc)( (YYMALLOCARGTYPE)sizeof(yyParser) ); if( pParser ){ pParser->yyidx = -1; #ifdef YYTRACKMAXSTACKDEPTH @@ -282,10 +332,12 @@ void *ParseAlloc(void *(*mallocProc)(size_t)){ return pParser; } -/* The following function deletes the value associated with a -** symbol. The symbol can be either a terminal or nonterminal. -** "yymajor" is the symbol code, and "yypminor" is a pointer to -** the value. +/* The following function deletes the "minor type" or semantic value +** associated with a symbol. The symbol can be either a terminal +** or nonterminal. "yymajor" is the symbol code, and "yypminor" is +** a pointer to the value to be deleted. The code used to do the +** deletions is derived from the %destructor and/or %token_destructor +** directives of the input grammar. */ static void yy_destructor( yyParser *yypParser, /* The parser */ @@ -301,10 +353,12 @@ static void yy_destructor( ** being destroyed before it is finished parsing. ** ** Note: during a reduce, the only symbols destroyed are those - ** which appear on the RHS of the rule, but which are not used + ** which appear on the RHS of the rule, but which are *not* used ** inside the C code. */ +/********* Begin destructor definitions ***************************************/ %% +/********* End destructor definitions *****************************************/ default: break; /* If no destructor action specified: do nothing */ } } @@ -314,45 +368,37 @@ static void yy_destructor( ** ** If there is a destructor routine associated with the token which ** is popped from the stack, then call it. -** -** Return the major token number for the symbol popped. */ -static int yy_pop_parser_stack(yyParser *pParser){ - YYCODETYPE yymajor; - yyStackEntry *yytos = &pParser->yystack[pParser->yyidx]; - - if( pParser->yyidx<0 ) return 0; +static void yy_pop_parser_stack(yyParser *pParser){ + yyStackEntry *yytos; + assert( pParser->yyidx>=0 ); + yytos = &pParser->yystack[pParser->yyidx--]; #ifndef NDEBUG - if( yyTraceFILE && pParser->yyidx>=0 ){ + if( yyTraceFILE ){ fprintf(yyTraceFILE,"%sPopping %s\n", yyTracePrompt, yyTokenName[yytos->major]); } #endif - yymajor = yytos->major; - yy_destructor(pParser, yymajor, &yytos->minor); - pParser->yyidx--; - return yymajor; + yy_destructor(pParser, yytos->major, &yytos->minor); } /* -** Deallocate and destroy a parser. Destructors are all called for +** Deallocate and destroy a parser. Destructors are called for ** all stack elements before shutting the parser down. ** -** Inputs: -** <ul> -** <li> A pointer to the parser. This should be a pointer -** obtained from ParseAlloc. -** <li> A pointer to a function used to reclaim memory obtained -** from malloc. -** </ul> +** If the YYPARSEFREENEVERNULL macro exists (for example because it +** is defined in a %include section of the input grammar) then it is +** assumed that the input pointer is never NULL. */ void ParseFree( void *p, /* The parser to be deleted */ void (*freeProc)(void*) /* Function used to reclaim memory */ ){ yyParser *pParser = (yyParser*)p; +#ifndef YYPARSEFREENEVERNULL if( pParser==0 ) return; +#endif while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser); #if YYSTACKDEPTH<=0 free(pParser->yystack); @@ -373,10 +419,6 @@ int ParseStackPeak(void *p){ /* ** Find the appropriate action for a parser given the terminal ** look-ahead token iLookAhead. -** -** If the look-ahead token is YYNOCODE, then check to see if the action is -** independent of the look-ahead. If it is, return the action, otherwise -** return YY_NO_ACTION. */ static int yy_find_shift_action( yyParser *pParser, /* The parser */ @@ -385,63 +427,64 @@ static int yy_find_shift_action( 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]; - } - assert( iLookAhead!=YYNOCODE ); - i += iLookAhead; - if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ - if( iLookAhead>0 ){ + if( stateno>=YY_MIN_REDUCE ) return stateno; + assert( stateno <= YY_SHIFT_COUNT ); + do{ + 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 - YYCODETYPE iFallback; /* Fallback token */ - if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0]) - && (iFallback = yyFallback[iLookAhead])!=0 ){ + YYCODETYPE iFallback; /* Fallback token */ + if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0]) + && (iFallback = yyFallback[iLookAhead])!=0 ){ #ifndef NDEBUG - if( yyTraceFILE ){ - fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n", - yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]); - } + if( yyTraceFILE ){ + fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n", + yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]); + } #endif - return yy_find_shift_action(pParser, iFallback); - } + assert( yyFallback[iFallback]==0 ); /* Fallback loop must terminate */ + iLookAhead = iFallback; + continue; + } #endif #ifdef YYWILDCARD - { - int j = i - iLookAhead + YYWILDCARD; - if( + { + int j = i - iLookAhead + YYWILDCARD; + if( #if YY_SHIFT_MIN+YYWILDCARD<0 - j>=0 && + j>=0 && #endif #if YY_SHIFT_MAX+YYWILDCARD>=YY_ACTTAB_COUNT - j<YY_ACTTAB_COUNT && + j<YY_ACTTAB_COUNT && #endif - yy_lookahead[j]==YYWILDCARD - ){ + yy_lookahead[j]==YYWILDCARD + ){ #ifndef NDEBUG - if( yyTraceFILE ){ - fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n", - yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[YYWILDCARD]); - } + if( yyTraceFILE ){ + fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n", + yyTracePrompt, yyTokenName[iLookAhead], + yyTokenName[YYWILDCARD]); + } #endif /* NDEBUG */ - return yy_action[j]; + return yy_action[j]; + } } - } #endif /* YYWILDCARD */ + } + return yy_default[stateno]; + }else{ + return yy_action[i]; } - return yy_default[stateno]; - }else{ - return yy_action[i]; - } + }while(1); } /* ** Find the appropriate action for a parser given the non-terminal ** look-ahead token iLookAhead. -** -** If the look-ahead token is YYNOCODE, then check to see if the action is -** independent of the look-ahead. If it is, return the action, otherwise -** return YY_NO_ACTION. */ static int yy_find_reduce_action( int stateno, /* Current state number */ @@ -484,11 +527,33 @@ static void yyStackOverflow(yyParser *yypParser, YYMINORTYPE *yypMinor _U_){ while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); /* Here code is inserted which will execute if the parser ** stack every overflows */ +/******** Begin %stack_overflow code ******************************************/ %% +/******** End %stack_overflow code ********************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ } /* +** Print tracing information for a SHIFT action +*/ +#ifndef NDEBUG +static void yyTraceShift(yyParser *yypParser, int yyNewState){ + if( yyTraceFILE ){ + if( yyNewState<YYNSTATE ){ + fprintf(yyTraceFILE,"%sShift '%s', go to state %d\n", + yyTracePrompt,yyTokenName[yypParser->yystack[yypParser->yyidx].major], + yyNewState); + }else{ + fprintf(yyTraceFILE,"%sShift '%s'\n", + yyTracePrompt,yyTokenName[yypParser->yystack[yypParser->yyidx].major]); + } + } +} +#else +# define yyTraceShift(X,Y) +#endif + +/* ** Perform a shift action. */ static void yy_shift( @@ -522,16 +587,7 @@ static void yy_shift( 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 @@ -564,29 +620,13 @@ static void yy_reduce( #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], go to 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 - ** switch. yygotominor is uninitialized when a rule reduces that does - ** not set the value of its left-hand side nonterminal. Leaving the - ** value of the nonterminal uninitialized is utterly harmless as long - ** as the value is never used. So really the only thing this code - ** accomplishes is to quieten purify. - ** - ** 2007-01-16: The wireshark project (www.wireshark.org) reports that - ** without this code, their parser segfaults. I'm not sure what there - ** parser is doing to make this happen. This is the second bug report - ** from wireshark this week. Clearly they are stressing Lemon in ways - ** that it has not been previously stressed... (SQLite ticket #2172) - */ - /*memset(&yygotominor, 0, sizeof(yygotominor));*/ yygotominor = yyzerominor; - switch( yyruleno ){ /* Beginning here are the reduction cases. A typical example ** follows: @@ -596,15 +636,18 @@ static void yy_reduce( ** #line <lineno> <thisfile> ** break; */ +/********** Begin reduce actions **********************************************/ %% +/********** End reduce actions ************************************************/ }; + assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); 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. */ @@ -614,13 +657,12 @@ static void yy_reduce( 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); } } @@ -641,7 +683,9 @@ static void yy_parse_failed( while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); /* Here code is inserted which will be executed whenever the ** parser fails */ +/************ Begin %parse_failure code ***************************************/ %% +/************ End %parse_failure code *****************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ } #endif /* YYNOERRORRECOVERY */ @@ -656,7 +700,9 @@ static void yy_syntax_error( ){ ParseARG_FETCH; #define TOKEN (yyminor.yy0) +/************ Begin %syntax_error code ****************************************/ %% +/************ End %syntax_error code ******************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ } @@ -675,7 +721,9 @@ static void yy_accept( while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); /* Here code is inserted which will be executed whenever the ** parser accepts */ +/*********** Begin %parse_accept code *****************************************/ %% +/*********** End %parse_accept code *******************************************/ ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ } @@ -706,7 +754,9 @@ void Parse( ){ YYMINORTYPE yyminorunion; int 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 @@ -727,26 +777,34 @@ void Parse( yypParser->yyerrcnt = -1; yypParser->yystack[0].stateno = 0; yypParser->yystack[0].major = 0; +#ifndef NDEBUG + if( yyTraceFILE ){ + fprintf(yyTraceFILE,"%sInitialize. Empty stack. State 0\n", + yyTracePrompt); + } +#endif } yyminorunion.yy0 = yyminor; +#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY) yyendofinput = (yymajor==0); +#endif ParseARG_STORE; #ifndef NDEBUG if( yyTraceFILE ){ - fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); + fprintf(yyTraceFILE,"%sInput '%s'\n",yyTracePrompt,yyTokenName[yymajor]); } #endif do{ yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); - if( yyact<YYNSTATE ){ - assert( !yyendofinput ); /* Impossible to shift the $ token */ + if( yyact <= YY_MAX_SHIFTREDUCE ){ + 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 @@ -796,7 +854,7 @@ void Parse( yymx != YYERRORSYMBOL && (yyact = yy_find_reduce_action( yypParser->yystack[yypParser->yyidx].stateno, - YYERRORSYMBOL)) >= YYNSTATE + YYERRORSYMBOL)) >= YY_MIN_REDUCE ){ yy_pop_parser_stack(yypParser); } @@ -846,5 +904,15 @@ void Parse( #endif } }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); +#ifndef NDEBUG + if( yyTraceFILE ){ + int i; + fprintf(yyTraceFILE,"%sReturn. Stack=",yyTracePrompt); + for(i=1; i<=yypParser->yyidx; i++) + fprintf(yyTraceFILE,"%c%s", i==1 ? '[' : ' ', + yyTokenName[yypParser->yystack[i].major]); + fprintf(yyTraceFILE,"]\n"); + } +#endif return; } |