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

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
 }