Index: tool/lemon.c
==================================================================
--- tool/lemon.c
+++ tool/lemon.c
@@ -47,10 +47,111 @@
 ** Compilers are getting increasingly pedantic about type conversions
 ** as C evolves ever closer to Ada....  To work around the latest problems
 ** we have to define the following variant of strlen().
 */
 #define lemonStrlen(X)   ((int)strlen(X))
+
+/*
+** Compilers are starting to complain about the use of sprintf() and strcpy(),
+** 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().
+** 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.
+**
+** The string formatter is a minimal subset of stdlib sprintf() supporting only
+** a few simply conversions:
+**
+**   %d
+**   %s
+**   %.*s
+**
+*/
+static void lemon_addtext(
+  char *zBuf,           /* The buffer to which text is added */
+  int *pnUsed,          /* Slots of the buffer used so far */
+  const char *zIn,      /* Text to add */
+  int nIn,              /* Bytes of text to add.  -1 to use strlen() */
+  int iWidth            /* Field width.  Negative to left justify */
+){
+  if( nIn<0 ) for(nIn=0; zIn[nIn]; nIn++){}
+  while( iWidth>nIn ){ zBuf[*(pnUsed++)] = ' '; iWidth--; }
+  if( nIn==0 ) return;
+  memcpy(&zBuf[*pnUsed], zIn, nIn);
+  *pnUsed += nIn;
+  while( (-iWidth)>nIn ){ zBuf[*(pnUsed++)] = ' '; iWidth++; }
+  zBuf[*pnUsed] = 0;
+}
+static int lemon_vsprintf(char *str, const char *zFormat, va_list ap){
+  int i, j, k, c, size;
+  int nUsed = 0;
+  const char *z;
+  char zTemp[50];
+  str[0] = 0;
+  for(i=j=0; (c = zFormat[i])!=0; i++){
+    if( c=='%' ){
+      int iWidth = 0;
+      lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0);
+      c = zFormat[++i];
+      if( isdigit(c) || (c=='-' && isdigit(zFormat[i+1])) ){
+        if( c=='-' ) i++;
+        while( isdigit(zFormat[i]) ) iWidth = iWidth*10 + zFormat[i++] - '0';
+        if( c=='-' ) iWidth = -iWidth;
+        c = zFormat[i];
+      }
+      if( c=='d' ){
+        int v = va_arg(ap, int);
+        if( v<0 ){
+          lemon_addtext(str, &nUsed, "-", 1, iWidth);
+          v = -v;
+        }else if( v==0 ){
+          lemon_addtext(str, &nUsed, "0", 1, iWidth);
+        }
+        k = 0;
+        while( v>0 ){
+          k++;
+          zTemp[sizeof(zTemp)-k] = (v%10) + '0';
+          v /= 10;
+        }
+        lemon_addtext(str, &nUsed, &zTemp[sizeof(zTemp)-k], k, iWidth);
+      }else if( c=='s' ){
+        z = va_arg(ap, const char*);
+        lemon_addtext(str, &nUsed, z, -1, iWidth);
+      }else if( c=='.' && memcmp(&zFormat[i], ".*s", 3)==0 ){
+        i += 2;
+        k = va_arg(ap, int);
+        z = va_arg(ap, const char*);
+        lemon_addtext(str, &nUsed, z, k, iWidth);
+      }else if( c=='%' ){
+        lemon_addtext(str, &nUsed, "%", 1, 0);
+      }else{
+        fprintf(stderr, "illegal format\n");
+        exit(1);
+      }
+      j = i+1;
+    }
+  }
+  lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0);
+  return nUsed;
+}
+static int lemon_sprintf(char *str, const char *format, ...){
+  va_list ap;
+  int rc;
+  va_start(ap, format);
+  rc = lemon_vsprintf(str, format, ap);
+  va_end(ap);
+  return rc;
+}
+static void lemon_strcpy(char *dest, const char *src){
+  while( (*(dest++) = *(src++))!=0 ){}
+}
+static void lemon_strcat(char *dest, const char *src){
+  while( *dest ) dest++;
+  lemon_strcpy(dest, src);
+}
+
 
 /* a few forward declarations... */
 struct rule;
 struct lemon;
 struct action;
@@ -1365,11 +1466,11 @@
   *paz = (char *) malloc( lemonStrlen(z)+1 );
   if( *paz==0 ){
     fprintf(stderr,"out of memory\n");
     exit(1);
   }
-  strcpy(*paz, z);
+  lemon_strcpy(*paz, z);
   for(z=*paz; *z && *z!='='; z++){}
   *z = 0;
 }
 
 static char *user_templatename = NULL;
@@ -1376,11 +1477,11 @@
 static void handle_T_option(char *z){
   user_templatename = (char *) malloc( lemonStrlen(z)+1 );
   if( user_templatename==0 ){
     memory_error();
   }
-  strcpy(user_templatename, z);
+  lemon_strcpy(user_templatename, z);
 }
 
 /* The main program.  Parse the command line and do it... */
 int main(int argc, char **argv)
 {
@@ -1445,16 +1546,19 @@
     fprintf(stderr,"Empty grammar.\n");
     exit(1);
   }
 
   /* Count and index the symbols of the grammar */
-  lem.nsymbol = Symbol_count();
   Symbol_new("{default}");
+  lem.nsymbol = Symbol_count();
   lem.symbols = Symbol_arrayof();
-  for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
-  qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*), Symbolcmpp);
-  for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
+  for(i=0; i<lem.nsymbol; i++) lem.symbols[i]->index = i;
+  qsort(lem.symbols,lem.nsymbol,sizeof(struct symbol*), Symbolcmpp);
+  for(i=0; i<lem.nsymbol; i++) lem.symbols[i]->index = i;
+  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++);
   lem.nterminal = i;
 
   /* Generate a reprint of the grammar, if requested on the command line */
   if( rpflag ){
@@ -1938,20 +2042,23 @@
   RESYNC_AFTER_RULE_ERROR,
   RESYNC_AFTER_DECL_ERROR,
   WAITING_FOR_DESTRUCTOR_SYMBOL,
   WAITING_FOR_DATATYPE_SYMBOL,
   WAITING_FOR_FALLBACK_ID,
-  WAITING_FOR_WILDCARD_ID
+  WAITING_FOR_WILDCARD_ID,
+  WAITING_FOR_CLASS_ID,
+  WAITING_FOR_CLASS_TOKEN
 };
 struct pstate {
   char *filename;       /* Name of the input file */
   int tokenlineno;      /* Linenumber at which current token starts */
   int errorcnt;         /* Number of errors so far */
   char *tokenstart;     /* Text of current token */
   struct lemon *gp;     /* Global state vector */
   enum e_state state;        /* The state of the parser */
   struct symbol *fallback;   /* The fallback token */
+  struct symbol *tkclass;    /* Token class symbol */
   struct symbol *lhs;        /* Left-hand side of current rule */
   const char *lhsalias;      /* Alias for the LHS */
   int nrhs;                  /* Number of right-hand side symbols seen */
   struct symbol *rhs[MAXRHS];  /* RHS symbols */
   const char *alias[MAXRHS]; /* Aliases for each RHS symbol (or NULL) */
@@ -2252,10 +2359,12 @@
         }else if( strcmp(x,"fallback")==0 ){
           psp->fallback = 0;
           psp->state = WAITING_FOR_FALLBACK_ID;
         }else if( strcmp(x,"wildcard")==0 ){
           psp->state = WAITING_FOR_WILDCARD_ID;
+        }else if( strcmp(x,"token_class")==0 ){
+          psp->state = WAITING_FOR_CLASS_ID;
         }else{
           ErrorMsg(psp->filename,psp->tokenlineno,
             "Unknown declaration keyword: \"%%%s\".",x);
           psp->errorcnt++;
           psp->state = RESYNC_AFTER_DECL_ERROR;
@@ -2345,11 +2454,11 @@
                         (psp->decllinenoslot==0 || psp->decllinenoslot[0]!=0);
         if( addLineMacro ){
           for(z=psp->filename, nBack=0; *z; z++){
             if( *z=='\\' ) nBack++;
           }
-          sprintf(zLine, "#line %d ", psp->tokenlineno);
+          lemon_sprintf(zLine, "#line %d ", psp->tokenlineno);
           nLine = lemonStrlen(zLine);
           n += nLine + lemonStrlen(psp->filename) + nBack;
         }
         *psp->declargslot = (char *) realloc(*psp->declargslot, n);
         zBuf = *psp->declargslot + nOld;
@@ -2419,10 +2528,44 @@
           ErrorMsg(psp->filename, psp->tokenlineno,
             "Extra wildcard to token: %s", x);
           psp->errorcnt++;
         }
       }
+      break;
+    case WAITING_FOR_CLASS_ID:
+      if( !islower(x[0]) ){
+        ErrorMsg(psp->filename, psp->tokenlineno,
+          "%%token_class must be followed by an identifier: ", x);
+        psp->errorcnt++;
+        psp->state = RESYNC_AFTER_DECL_ERROR;
+     }else if( Symbol_find(x) ){
+        ErrorMsg(psp->filename, psp->tokenlineno,
+          "Symbol \"%s\" already used", x);
+        psp->errorcnt++;
+        psp->state = RESYNC_AFTER_DECL_ERROR;
+      }else{
+        psp->tkclass = Symbol_new(x);
+        psp->tkclass->type = MULTITERMINAL;
+        psp->state = WAITING_FOR_CLASS_TOKEN;
+      }
+      break;
+    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])) ){
+        struct symbol *msp = psp->tkclass;
+        msp->nsubsym++;
+        msp->subsym = (struct symbol **) realloc(msp->subsym,
+          sizeof(struct symbol*)*msp->nsubsym);
+        if( !isupper(x[0]) ) x++;
+        msp->subsym[msp->nsubsym-1] = Symbol_new(x);
+      }else{
+        ErrorMsg(psp->filename, psp->tokenlineno,
+          "%%token_class argument \"%s\" should be a token", x);
+        psp->errorcnt++;
+        psp->state = RESYNC_AFTER_DECL_ERROR;
+      }
       break;
     case RESYNC_AFTER_RULE_ERROR:
 /*      if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
 **      break; */
     case RESYNC_AFTER_DECL_ERROR:
@@ -2714,14 +2857,14 @@
   name = (char*)malloc( lemonStrlen(lemp->filename) + lemonStrlen(suffix) + 5 );
   if( name==0 ){
     fprintf(stderr,"Can't allocate space for a filename.\n");
     exit(1);
   }
-  strcpy(name,lemp->filename);
+  lemon_strcpy(name,lemp->filename);
   cp = strrchr(name,'.');
   if( cp ) *cp = 0;
-  strcat(name,suffix);
+  lemon_strcat(name,suffix);
   return name;
 }
 
 /* Open a file with a name based on the name of the input file,
 ** but with a different (specified) suffix, and return a pointer
@@ -2774,15 +2917,17 @@
     printf("%s",rp->lhs->name);
     /*    if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
     printf(" ::=");
     for(i=0; i<rp->nrhs; i++){
       sp = rp->rhs[i];
-      printf(" %s", sp->name);
       if( sp->type==MULTITERMINAL ){
+        printf(" %s", sp->subsym[0]->name);
         for(j=1; j<sp->nsubsym; j++){
           printf("|%s", sp->subsym[j]->name);
         }
+      }else{
+        printf(" %s", sp->name);
       }
       /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
     }
     printf(".");
     if( rp->precsym ) printf(" [%s]",rp->precsym->name);
@@ -2800,15 +2945,17 @@
   fprintf(fp,"%s ::=",rp->lhs->name);
   for(i=0; i<=rp->nrhs; i++){
     if( i==cfp->dot ) fprintf(fp," *");
     if( i==rp->nrhs ) break;
     sp = rp->rhs[i];
-    fprintf(fp," %s", sp->name);
     if( sp->type==MULTITERMINAL ){
+      fprintf(fp," %s", sp->subsym[0]->name);
       for(j=1; j<sp->nsubsym; j++){
         fprintf(fp,"|%s",sp->subsym[j]->name);
       }
+    }else{
+      fprintf(fp," %s", sp->name);
     }
   }
 }
 
 /* #define TEST */
@@ -2914,11 +3061,11 @@
     if( lemp->basisflag ) cfp=stp->bp;
     else                  cfp=stp->cfp;
     while( cfp ){
       char buf[20];
       if( cfp->dot==cfp->rp->nrhs ){
-        sprintf(buf,"(%d)",cfp->rp->index);
+        lemon_sprintf(buf,"(%d)",cfp->rp->index);
         fprintf(fp,"    %5s ",buf);
       }else{
         fprintf(fp,"          ");
       }
       ConfigPrint(fp,cfp);
@@ -2979,26 +3126,26 @@
 #endif
   if( cp ){
     c = *cp;
     *cp = 0;
     path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2 );
-    if( path ) sprintf(path,"%s/%s",argv0,name);
+    if( path ) lemon_sprintf(path,"%s/%s",argv0,name);
     *cp = c;
   }else{
     pathlist = getenv("PATH");
     if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
     pathbuf = (char *) malloc( lemonStrlen(pathlist) + 1 );
     path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
     if( (pathbuf != 0) && (path!=0) ){
       pathbufptr = pathbuf;
-      strcpy(pathbuf, pathlist);
+      lemon_strcpy(pathbuf, pathlist);
       while( *pathbuf ){
         cp = strchr(pathbuf,':');
         if( cp==0 ) cp = &pathbuf[lemonStrlen(pathbuf)];
         c = *cp;
         *cp = 0;
-        sprintf(path,"%s/%s",pathbuf,name);
+        lemon_sprintf(path,"%s/%s",pathbuf,name);
         *cp = c;
         if( c==0 ) pathbuf[0] = 0;
         else pathbuf = &cp[1];
         if( access(path,modemask)==0 ) break;
       }
@@ -3085,13 +3232,13 @@
     return in;
   }
 
   cp = strrchr(lemp->filename,'.');
   if( cp ){
-    sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
+    lemon_sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
   }else{
-    sprintf(buf,"%s.lt",lemp->filename);
+    lemon_sprintf(buf,"%s.lt",lemp->filename);
   }
   if( access(buf,004)==0 ){
     tpltname = buf;
   }else if( access(templatename,004)==0 ){
     tpltname = templatename;
@@ -3238,13 +3385,13 @@
   }
   if( z==0 ) return empty;
   while( n-- > 0 ){
     c = *(zText++);
     if( c=='%' && n>0 && zText[0]=='d' ){
-      sprintf(zInt, "%d", p1);
+      lemon_sprintf(zInt, "%d", p1);
       p1 = p2;
-      strcpy(&z[used], zInt);
+      lemon_strcpy(&z[used], zInt);
       used += lemonStrlen(&z[used]);
       zText++;
       n--;
     }else{
       z[used++] = c;
@@ -3465,11 +3612,11 @@
       types[hash] = (char*)malloc( lemonStrlen(stddt)+1 );
       if( types[hash]==0 ){
         fprintf(stderr,"Out of memory.\n");
         exit(1);
       }
-      strcpy(types[hash],stddt);
+      lemon_strcpy(types[hash],stddt);
     }
   }
 
   /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
   name = lemp->name ? lemp->name : "Parse";
@@ -3551,13 +3698,15 @@
 static void writeRuleText(FILE *out, struct rule *rp){
   int j;
   fprintf(out,"%s ::=", rp->lhs->name);
   for(j=0; j<rp->nrhs; j++){
     struct symbol *sp = rp->rhs[j];
-    fprintf(out," %s", sp->name);
-    if( sp->type==MULTITERMINAL ){
+    if( sp->type!=MULTITERMINAL ){
+      fprintf(out," %s", sp->name);
+    }else{
       int k;
+      fprintf(out," %s", sp->subsym[0]->name);
       for(k=1; k<sp->nsubsym; k++){
         fprintf(out,"|%s",sp->subsym[k]->name);
       }
     }
   }
@@ -3854,11 +4003,11 @@
   tplt_xfer(lemp->name, in, out, &lineno);
 
   /* Generate a table containing the symbolic name of every symbol
   */
   for(i=0; i<lemp->nsymbol; i++){
-    sprintf(line,"\"%s\",",lemp->symbols[i]->name);
+    lemon_sprintf(line,"\"%s\",",lemp->symbols[i]->name);
     fprintf(out,"  %-15s",line);
     if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; }
   }
   if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; }
   tplt_xfer(lemp->name,in,out,&lineno);
@@ -4021,11 +4170,12 @@
   else                    prefix = "";
   in = file_open(lemp,".h","rb");
   if( in ){
     int nextChar;
     for(i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++){
-      sprintf(pattern,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
+      lemon_sprintf(pattern,"#define %s%-30s %3d\n",
+                    prefix,lemp->symbols[i]->name,i);
       if( strcmp(line,pattern) ) break;
     }
     nextChar = fgetc(in);
     fclose(in);
     if( i==lemp->nterminal && nextChar==EOF ){
@@ -4034,11 +4184,11 @@
     }
   }
   out = file_open(lemp,".h","wb");
   if( out ){
     for(i=1; i<lemp->nterminal; i++){
-      fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
+      fprintf(out,"#define %s%-30s %3d\n",prefix,lemp->symbols[i]->name,i);
     }
     fclose(out);  
   }
   return;
 }
@@ -4251,11 +4401,11 @@
   char *cpy;
 
   if( y==0 ) return 0;
   z = Strsafe_find(y);
   if( z==0 && (cpy=(char *)malloc( lemonStrlen(y)+1 ))!=0 ){
-    strcpy(cpy,y);
+    lemon_strcpy(cpy,y);
     z = cpy;
     Strsafe_insert(z);
   }
   MemoryCheck(z);
   return z;
@@ -4404,28 +4554,31 @@
   }
   sp->useCnt++;
   return sp;
 }
 
-/* Compare two symbols for working purposes
+/* Compare two symbols for sorting purposes.  Return negative,
+** zero, or positive if a is less then, equal to, or greater
+** than b.
 **
 ** Symbols that begin with upper case letters (terminals or tokens)
 ** must sort before symbols that begin with lower case letters
-** (non-terminals).  Other than that, the order does not matter.
+** (non-terminals).  And MULTITERMINAL symbols (created using the
+** %token_class directive) must sort at the very end. Other than
+** that, the order does not matter.
 **
 ** We find experimentally that leaving the symbols in their original
 ** order (the order they appeared in the grammar file) gives the
 ** smallest parser tables in SQLite.
 */
 int Symbolcmpp(const void *_a, const void *_b)
 {
-  const struct symbol **a = (const struct symbol **) _a;
-  const struct symbol **b = (const struct symbol **) _b;
-  int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
-  int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
-  assert( i1!=i2 || strcmp((**a).name,(**b).name)==0 );
-  return i1-i2;
+  const struct symbol *a = *(const struct symbol **) _a;
+  const struct symbol *b = *(const struct symbol **) _b;
+  int i1 = a->type==MULTITERMINAL ? 3 : a->name[0]>'Z' ? 2 : 1;
+  int i2 = b->type==MULTITERMINAL ? 3 : b->name[0]>'Z' ? 2 : 1;
+  return i1==i2 ? a->index - b->index : i1 - i2;
 }
 
 /* There is one instance of the following structure for each
 ** associative array of type "x2".
 */