diff options
author | Anders Broman <anders.broman@ericsson.com> | 2006-03-19 13:59:44 +0000 |
---|---|---|
committer | Anders Broman <anders.broman@ericsson.com> | 2006-03-19 13:59:44 +0000 |
commit | 5d20a3ba367bfd50e6ee40c74b983ea9768c7f67 (patch) | |
tree | cb1aa24642bd9f2d1c02eff3a0ed157f46d55b32 /tools | |
parent | 0050f4e68d00bc7c30a765e68ed0eeeddd41b04b (diff) |
Sqlite lemon 1.8 ( 1.7 Make lemon 64-bit clean skipped) :
Bugfix Check-in [388] : Bug fix in lemon: 3-way conflicts (SHIFT/REDUCE/REDUCE) were not detected or resolved. This is now fixed. Also, table compression works a little better. By drh. (diff)
http://www.sqlite.org/cvstrac/rlog?f=sqlite/tool/lemon.c
svn path=/trunk/; revision=17668
Diffstat (limited to 'tools')
-rw-r--r-- | tools/lemon/lemon.c | 69 | ||||
-rw-r--r-- | tools/lemon/lempar.c | 4 |
2 files changed, 48 insertions, 25 deletions
diff --git a/tools/lemon/lemon.c b/tools/lemon/lemon.c index 8020a0016e..8f408343a2 100644 --- a/tools/lemon/lemon.c +++ b/tools/lemon/lemon.c @@ -792,7 +792,7 @@ void FindActions(struct lemon *lemp) stp = lemp->sorted[i]; assert( stp->ap ); stp->ap = Action_sort(stp->ap); - for(ap=stp->ap; ap && ap->next; ap=nap){ + for(ap=stp->ap; ap && ap->next; ap=ap->next){ for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){ /* The two actions "ap" and "nap" have the same lookahead. ** Figure out which one should be used */ @@ -869,9 +869,17 @@ static int resolve_conflict( apx->type = RD_RESOLVED; } }else{ - /* Can't happen. Shifts have to come before Reduces on the - ** list because the reduces were added last. Hence, if apx->type==REDUCE - ** then it is impossible for apy->type==SHIFT */ + assert( + apx->type==SH_RESOLVED || + apx->type==RD_RESOLVED || + apx->type==CONFLICT || + apy->type==SH_RESOLVED || + apy->type==RD_RESOLVED || + apy->type==CONFLICT + ); + /* The REDUCE/SHIFT case cannot happen because SHIFTs come before + ** REDUCEs on the list. If we reach this point it must be because + ** the parser conflict had already been resolved. */ } return errcnt; } @@ -3294,47 +3302,58 @@ void ReportHeader(struct lemon *lemp) /* Reduce the size of the action tables, if possible, by making use ** of defaults. ** -** In this version, if all REDUCE actions use the same rule, make -** them the default. Only default them if there are more than one. +** In this version, we take the most frequent REDUCE action and make +** it the default. Only default a reduce if there are more than one. + */ void CompressTables(struct lemon *lemp) { struct state *stp; - struct action *ap; - struct rule *rp; + struct action *ap, *ap2; + struct rule *rp, *rp2, *rbest; + int nbest, n; int i; int cnt; for(i=0; i<lemp->nstate; i++){ stp = lemp->sorted[i]; + nbest = 0; + rbest = 0; - /* Find the first REDUCE action */ - for(ap=stp->ap; ap && ap->type!=REDUCE; ap=ap->next); - if( ap==0 ) continue; - - /* Remember the rule used */ - rp = ap->x.rp; - - /* See if all other REDUCE acitons use the same rule */ - cnt = 1; - for(ap=ap->next; ap; ap=ap->next){ - if( ap->type==REDUCE ){ - if( ap->x.rp!=rp ) break; - cnt++; + for(ap=stp->ap; ap; ap=ap->next){ + if( ap->type!=REDUCE ) continue; + rp = ap->x.rp; + if( rp==rbest ) continue; + n = 1; + for(ap2=ap->next; ap2; ap2=ap2->next){ + if( ap2->type!=REDUCE ) continue; + rp2 = ap2->x.rp; + if( rp2==rbest ) continue; + if( rp2==rp ) n++; + } + if( n>nbest ){ + nbest = n; + rbest = rp; } } - if( ap || cnt==1 ) continue; + + /* Do not make a default if the number of rules to default + ** is not at least 2 */ + if( nbest<2 ) continue; - /* Combine all REDUCE actions into a single default */ - for(ap=stp->ap; ap && ap->type!=REDUCE; ap=ap->next); + /* Combine matching REDUCE actions into a single default */ + for(ap=stp->ap; ap; ap=ap->next){ + if( ap->type==REDUCE && ap->x.rp==rbest ) break; + } assert( ap ); ap->sp = Symbol_new("{default}"); for(ap=ap->next; ap; ap=ap->next){ - if( ap->type==REDUCE ) ap->type = NOT_USED; + if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED; } stp->ap = Action_sort(stp->ap); } } + /***************** From the file "set.c" ************************************/ /* ** Set manipulation routines for the LEMON parser generator. diff --git a/tools/lemon/lempar.c b/tools/lemon/lempar.c index f13df53688..e7aaa46497 100644 --- a/tools/lemon/lempar.c +++ b/tools/lemon/lempar.c @@ -195,11 +195,15 @@ static const char *yyTokenName[] = { ** value. */ const char *ParseTokenName(int tokenType){ +#ifndef NDEBUG if( tokenType>0 && tokenType<(sizeof(yyTokenName)/sizeof(yyTokenName[0])) ){ return yyTokenName[tokenType]; }else{ return "Unknown"; } +#else + return ""; +#endif } |