tools/lemon.c

   1 /*
   2 ** This file contains all sources (including headers) to the LEMON
   3 ** LALR(1) parser generator.  The sources have been combined into a
   4 ** single file to make it easy to include LEMON in the source tree
   5 ** and Makefile of another program.
   6 **
   7 ** The author of this program disclaims copyright.
   8 */
   9 #include <stdio.h>
  10 #include <stdarg.h>
  11 #include <string.h>
  12 #include <ctype.h>
  13 #include <stdlib.h>
  14
  15 #ifndef __WIN32__
  16 #   if defined(_WIN32) || defined(WIN32)
  17 #       define __WIN32__
  18 #   endif
  19 #endif
  20
  21 /* #define PRIVATE static */
  22 #define PRIVATE
  23
  24 #ifdef TEST
  25 #define MAXRHS 5       /* Set low to exercise exception code */
  26 #else
  27 #define MAXRHS 1000
  28 #endif
  29
  30 char *msort();
  31 extern void *malloc();
  32
  33 /******** From the file "action.h" *************************************/
  34 struct action *Action_new();
  35 struct action *Action_sort();
  36
  37 /********* From the file "assert.h" ************************************/
  38 void myassert();
  39 #ifndef NDEBUG
  40 #  define assert(X) if(!(X))myassert(__FILE__,__LINE__)
  41 #else
  42 #  define assert(X)
  43 #endif
  44
  45 /********** From the file "build.h" ************************************/
  46 void FindRulePrecedences();
  47 void FindFirstSets();
  48 void FindStates();
  49 void FindLinks();
  50 void FindFollowSets();
  51 void FindActions();
  52
  53 /********* From the file "configlist.h" *********************************/
  54 void Configlist_init(/* void */);
  55 struct config *Configlist_add(/* struct rule *, int */);
  56 struct config *Configlist_addbasis(/* struct rule *, int */);
  57 void Configlist_closure(/* void */);
  58 void Configlist_sort(/* void */);
  59 void Configlist_sortbasis(/* void */);
  60 struct config *Configlist_return(/* void */);
  61 struct config *Configlist_basis(/* void */);
  62 void Configlist_eat(/* struct config * */);
  63 void Configlist_reset(/* void */);
  64
  65 /********* From the file "error.h" ***************************************/
  66 void ErrorMsg(const char *, int,const char *, ...);
  67
  68 /****** From the file "option.h" ******************************************/
  69 struct s_options {
  70   enum { OPT_FLAG=1,  OPT_INT,  OPT_DBL,  OPT_STR,
  71          OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;
  72   char *label;
  73   char *arg;
  74   char *message;
  75 };
  76 int    OptInit(/* char**,struct s_options*,FILE* */);
  77 int    OptNArgs(/* void */);
  78 char  *OptArg(/* int */);
  79 void   OptErr(/* int */);
  80 void   OptPrint(/* void */);
  81
  82 /******** From the file "parse.h" *****************************************/
  83 void Parse(/* struct lemon *lemp */);
  84
  85 /********* From the file "plink.h" ***************************************/
  86 struct plink *Plink_new(/* void */);
  87 void Plink_add(/* struct plink **, struct config * */);
  88 void Plink_copy(/* struct plink **, struct plink * */);
  89 void Plink_delete(/* struct plink * */);
  90
  91 /********** From the file "report.h" *************************************/
  92 void Reprint(/* struct lemon * */);
  93 void ReportOutput(/* struct lemon * */);
  94 void ReportTable(/* struct lemon * */);
  95 void ReportHeader(/* struct lemon * */);
  96 void CompressTables(/* struct lemon * */);
  97 void ResortStates(/* struct lemon * */);
  98
  99 /********** From the file "set.h" ****************************************/
 100 void  SetSize(/* int N */);             /* All sets will be of size N */
 101 char *SetNew(/* void */);               /* A new set for element 0..N */
 102 void  SetFree(/* char* */);             /* Deallocate a set */
 103
 104 int SetAdd(/* char*,int */);            /* Add element to a set */
 105 int SetUnion(/* char *A,char *B */);    /* A <- A U B, thru element N */
 106
 107 #define SetFind(X,Y) (X[Y])       /* True if Y is in set X */
 108
 109 /********** From the file "struct.h" *************************************/
 110 /*
 111 ** Principal data structures for the LEMON parser generator.
 112 */
 113
 114 typedef enum {B_FALSE=0, B_TRUE} Boolean;
 115
 116 /* Symbols (terminals and nonterminals) of the grammar are stored
 117 ** in the following: */
 118 struct symbol {
 119   char *name;              /* Name of the symbol */
 120   int index;               /* Index number for this symbol */
 121   enum {
 122     TERMINAL,
 123     NONTERMINAL,
 124     MULTITERMINAL
 125   } type;                  /* Symbols are all either TERMINALS or NTs */
 126   struct rule *rule;       /* Linked list of rules of this (if an NT) */
 127   struct symbol *fallback; /* fallback token in case this token doesn't parse */
 128   int prec;                /* Precedence if defined (-1 otherwise) */
 129   enum e_assoc {
 130     LEFT,
 131     RIGHT,
 132     NONE,
 133     UNK
 134   } assoc;                 /* Associativity if predecence is defined */
 135   char *firstset;          /* First-set for all rules of this symbol */
 136   Boolean lambda;          /* True if NT and can generate an empty string */
 137   char *destructor;        /* Code which executes whenever this symbol is
 138                            ** popped from the stack during error processing */
 139   int destructorln;        /* Line number of destructor code */
 140   char *datatype;          /* The data type of information held by this
 141                            ** object. Only used if type==NONTERMINAL */
 142   int dtnum;               /* The data type number.  In the parser, the value
 143                            ** stack is a union.  The .yy%d element of this
 144                            ** union is the correct data type for this object */
 145   /* The following fields are used by MULTITERMINALs only */
 146   int nsubsym;             /* Number of constituent symbols in the MULTI */
 147   struct symbol **subsym;  /* Array of constituent symbols */
 148 };
 149
 150 /* Each production rule in the grammar is stored in the following
 151 ** structure.  */
 152 struct rule {
 153   struct symbol *lhs;      /* Left-hand side of the rule */
 154   char *lhsalias;          /* Alias for the LHS (NULL if none) */
 155   int ruleline;            /* Line number for the rule */
 156   int nrhs;                /* Number of RHS symbols */
 157   struct symbol **rhs;     /* The RHS symbols */
 158   char **rhsalias;         /* An alias for each RHS symbol (NULL if none) */
 159   int line;                /* Line number at which code begins */
 160   char *code;              /* The code executed when this rule is reduced */
 161   struct symbol *precsym;  /* Precedence symbol for this rule */
 162   int index;               /* An index number for this rule */
 163   Boolean canReduce;       /* True if this rule is ever reduced */
 164   struct rule *nextlhs;    /* Next rule with the same LHS */
 165   struct rule *next;       /* Next rule in the global list */
 166 };
 167
 168 /* A configuration is a production rule of the grammar together with
 169 ** a mark (dot) showing how much of that rule has been processed so far.
 170 ** Configurations also contain a follow-set which is a list of terminal
 171 ** symbols which are allowed to immediately follow the end of the rule.
 172 ** Every configuration is recorded as an instance of the following: */
 173 struct config {
 174   struct rule *rp;         /* The rule upon which the configuration is based */
 175   int dot;                 /* The parse point */
 176   char *fws;               /* Follow-set for this configuration only */
 177   struct plink *fplp;      /* Follow-set forward propagation links */
 178   struct plink *bplp;      /* Follow-set backwards propagation links */
 179   struct state *stp;       /* Pointer to state which contains this */
 180   enum {
 181     COMPLETE,              /* The status is used during followset and */
 182     INCOMPLETE             /*    shift computations */
 183   } status;
 184   struct config *next;     /* Next configuration in the state */
 185   struct config *bp;       /* The next basis configuration */
 186 };
 187
 188 /* Every shift or reduce operation is stored as one of the following */
 189 struct action {
 190   struct symbol *sp;       /* The look-ahead symbol */
 191   enum e_action {
 192     SHIFT,
 193     ACCEPT,
 194     REDUCE,
 195     ERROR,
 196     CONFLICT,                /* Was a reduce, but part of a conflict */
 197     SH_RESOLVED,             /* Was a shift.  Precedence resolved conflict */
 198     RD_RESOLVED,             /* Was reduce.  Precedence resolved conflict */
 199     NOT_USED                 /* Deleted by compression */
 200   } type;
 201   union {
 202     struct state *stp;     /* The new state, if a shift */
 203     struct rule *rp;       /* The rule, if a reduce */
 204   } x;
 205   struct action *next;     /* Next action for this state */
 206   struct action *collide;  /* Next action with the same hash */
 207 };
 208
 209 /* Each state of the generated parser's finite state machine
 210 ** is encoded as an instance of the following structure. */
 211 struct state {
 212   struct config *bp;       /* The basis configurations for this state */
 213   struct config *cfp;      /* All configurations in this set */
 214   int statenum;            /* Sequencial number for this state */
 215   struct action *ap;       /* Array of actions for this state */
 216   int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
 217   int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
 218   int iDflt;               /* Default action */
 219 };
 220 #define NO_OFFSET (-2147483647)
 221
 222 /* A followset propagation link indicates that the contents of one
 223 ** configuration followset should be propagated to another whenever
 224 ** the first changes. */
 225 struct plink {
 226   struct config *cfp;      /* The configuration to which linked */
 227   struct plink *next;      /* The next propagate link */
 228 };
 229
 230 /* The state vector for the entire parser generator is recorded as
 231 ** follows.  (LEMON uses no global variables and makes little use of
 232 ** static variables.  Fields in the following structure can be thought
 233 ** of as begin global variables in the program.) */
 234 struct lemon {
 235   struct state **sorted;   /* Table of states sorted by state number */
 236   struct rule *rule;       /* List of all rules */
 237   int nstate;              /* Number of states */
 238   int nrule;               /* Number of rules */
 239   int nsymbol;             /* Number of terminal and nonterminal symbols */
 240   int nterminal;           /* Number of terminal symbols */
 241   struct symbol **symbols; /* Sorted array of pointers to symbols */
 242   int errorcnt;            /* Number of errors */
 243   struct symbol *errsym;   /* The error symbol */
 244   struct symbol *wildcard; /* Token that matches anything */
 245   char *name;              /* Name of the generated parser */
 246   char *arg;               /* Declaration of the 3th argument to parser */
 247   char *tokentype;         /* Type of terminal symbols in the parser stack */
 248   char *vartype;           /* The default type of non-terminal symbols */
 249   char *start;             /* Name of the start symbol for the grammar */
 250   char *stacksize;         /* Size of the parser stack */
 251   char *include;           /* Code to put at the start of the C file */
 252   int  includeln;          /* Line number for start of include code */
 253   char *error;             /* Code to execute when an error is seen */
 254   int  errorln;            /* Line number for start of error code */
 255   char *overflow;          /* Code to execute on a stack overflow */
 256   int  overflowln;         /* Line number for start of overflow code */
 257   char *failure;           /* Code to execute on parser failure */
 258   int  failureln;          /* Line number for start of failure code */
 259   char *accept;            /* Code to execute when the parser excepts */
 260   int  acceptln;           /* Line number for the start of accept code */
 261   char *extracode;         /* Code appended to the generated file */
 262   int  extracodeln;        /* Line number for the start of the extra code */
 263   char *tokendest;         /* Code to execute to destroy token data */
 264   int  tokendestln;        /* Line number for token destroyer code */
 265   char *vardest;           /* Code for the default non-terminal destructor */
 266   int  vardestln;          /* Line number for default non-term destructor code*/
 267   char *filename;          /* Name of the input file */
 268   char *outname;           /* Name of the current output file */
 269   char *tokenprefix;       /* A prefix added to token names in the .h file */
 270   int nconflict;           /* Number of parsing conflicts */
 271   int tablesize;           /* Size of the parse tables */
 272   int basisflag;           /* Print only basis configurations */
 273   int has_fallback;        /* True if any %fallback is seen in the grammer */
 274   char *argv0;             /* Name of the program */
 275 };
 276
 277 #define MemoryCheck(X) if((X)==0){ \
 278   extern void memory_error(); \
 279   memory_error(); \
 280 }
 281
 282 /**************** From the file "table.h" *********************************/
 283 /*
 284 ** All code in this file has been automatically generated
 285 ** from a specification in the file
 286 **              "table.q"
 287 ** by the associative array code building program "aagen".
 288 ** Do not edit this file!  Instead, edit the specification
 289 ** file, then rerun aagen.
 290 */
 291 /*
 292 ** Code for processing tables in the LEMON parser generator.
 293 */
 294
 295 /* Routines for handling a strings */
 296
 297 char *Strsafe();
 298
 299 void Strsafe_init(/* void */);
 300 int Strsafe_insert(/* char * */);
 301 char *Strsafe_find(/* char * */);
 302
 303 /* Routines for handling symbols of the grammar */
 304
 305 struct symbol *Symbol_new();
 306 int Symbolcmpp(/* struct symbol **, struct symbol ** */);
 307 void Symbol_init(/* void */);
 308 int Symbol_insert(/* struct symbol *, char * */);
 309 struct symbol *Symbol_find(/* char * */);
 310 struct symbol *Symbol_Nth(/* int */);
 311 int Symbol_count(/*  */);
 312 struct symbol **Symbol_arrayof(/*  */);
 313
 314 /* Routines to manage the state table */
 315
 316 int Configcmp(/* struct config *, struct config * */);
 317 struct state *State_new();
 318 void State_init(/* void */);
 319 int State_insert(/* struct state *, struct config * */);
 320 struct state *State_find(/* struct config * */);
 321 struct state **State_arrayof(/*  */);
 322
 323 /* Routines used for efficiency in Configlist_add */
 324
 325 void Configtable_init(/* void */);
 326 int Configtable_insert(/* struct config * */);
 327 struct config *Configtable_find(/* struct config * */);
 328 void Configtable_clear(/* int(*)(struct config *) */);
 329 /****************** From the file "action.c" *******************************/
 330 /*
 331 ** Routines processing parser actions in the LEMON parser generator.
 332 */
 333
 334 /* Allocate a new parser action */
 335 struct action *Action_new(){
 336   static struct action *freelist = 0;
 337   struct action *new;
 338
 339   if( freelist==0 ){
 340     int i;
 341     int amt = 100;
 342     freelist = (struct action *)malloc( sizeof(struct action)*amt );
 343     if( freelist==0 ){
 344       fprintf(stderr,"Unable to allocate memory for a new parser action.");
 345       exit(1);
 346     }
 347     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
 348     freelist[amt-1].next = 0;
 349   }
 350   new = freelist;
 351   freelist = freelist->next;
 352   return new;
 353 }
 354
 355 /* Compare two actions */
 356 static int actioncmp(ap1,ap2)
 357 struct action *ap1;
 358 struct action *ap2;
 359 {
 360   int rc;
 361   rc = ap1->sp->index - ap2->sp->index;
 362   if( rc==0 ) rc = (int)ap1->type - (int)ap2->type;
 363   if( rc==0 ){
 364     assert( ap1->type==REDUCE || ap1->type==RD_RESOLVED || ap1->type==CONFLICT);
 365     assert( ap2->type==REDUCE || ap2->type==RD_RESOLVED || ap2->type==CONFLICT);
 366     rc = ap1->x.rp->index - ap2->x.rp->index;
 367   }
 368   return rc;
 369 }
 370
 371 /* Sort parser actions */
 372 struct action *Action_sort(ap)
 373 struct action *ap;
 374 {
 375   ap = (struct action *)msort((char *)ap,(char **)&ap->next,actioncmp);
 376   return ap;
 377 }
 378
 379 void Action_add(app,type,sp,arg)
 380 struct action **app;
 381 enum e_action type;
 382 struct symbol *sp;
 383 char *arg;
 384 {
 385   struct action *new;
 386   new = Action_new();
 387   new->next = *app;
 388   *app = new;
 389   new->type = type;
 390   new->sp = sp;
 391   if( type==SHIFT ){
 392     new->x.stp = (struct state *)arg;
 393   }else{
 394     new->x.rp = (struct rule *)arg;
 395   }
 396 }
 397 /********************** New code to implement the "acttab" module ***********/
 398 /*
 399 ** This module implements routines use to construct the yy_action[] table.
 400 */
 401
 402 /*
 403 ** The state of the yy_action table under construction is an instance of
 404 ** the following structure
 405 */
 406 typedef struct acttab acttab;
 407 struct acttab {
 408   int nAction;                 /* Number of used slots in aAction[] */
 409   int nActionAlloc;            /* Slots allocated for aAction[] */
 410   struct {
 411     int lookahead;             /* Value of the lookahead token */
 412     int action;                /* Action to take on the given lookahead */
 413   } *aAction,                  /* The yy_action[] table under construction */
 414     *aLookahead;               /* A single new transaction set */
 415   int mnLookahead;             /* Minimum aLookahead[].lookahead */
 416   int mnAction;                /* Action associated with mnLookahead */
 417   int mxLookahead;             /* Maximum aLookahead[].lookahead */
 418   int nLookahead;              /* Used slots in aLookahead[] */
 419   int nLookaheadAlloc;         /* Slots allocated in aLookahead[] */
 420 };
 421
 422 /* Return the number of entries in the yy_action table */
 423 #define acttab_size(X) ((X)->nAction)
 424
 425 /* The value for the N-th entry in yy_action */
 426 #define acttab_yyaction(X,N)  ((X)->aAction[N].action)
 427
 428 /* The value for the N-th entry in yy_lookahead */
 429 #define acttab_yylookahead(X,N)  ((X)->aAction[N].lookahead)
 430
 431 /* Free all memory associated with the given acttab */
 432 void acttab_free(acttab *p){
 433   free( p->aAction );
 434   free( p->aLookahead );
 435   free( p );
 436 }
 437
 438 /* Allocate a new acttab structure */
 439 acttab *acttab_alloc(void){
 440   acttab *p = malloc( sizeof(*p) );
 441   if( p==0 ){
 442     fprintf(stderr,"Unable to allocate memory for a new acttab.");
 443     exit(1);
 444   }
 445   memset(p, 0, sizeof(*p));
 446   return p;
 447 }
 448
 449 /* Add a new action to the current transaction set
 450 */
 451 void acttab_action(acttab *p, int lookahead, int action){
 452   if( p->nLookahead>=p->nLookaheadAlloc ){
 453     p->nLookaheadAlloc += 25;
 454     p->aLookahead = realloc( p->aLookahead,
 455                              sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
 456     if( p->aLookahead==0 ){
 457       fprintf(stderr,"malloc failed\n");
 458       exit(1);
 459     }
 460   }
 461   if( p->nLookahead==0 ){
 462     p->mxLookahead = lookahead;
 463     p->mnLookahead = lookahead;
 464     p->mnAction = action;
 465   }else{
 466     if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
 467     if( p->mnLookahead>lookahead ){
 468       p->mnLookahead = lookahead;
 469       p->mnAction = action;
 470     }
 471   }
 472   p->aLookahead[p->nLookahead].lookahead = lookahead;
 473   p->aLookahead[p->nLookahead].action = action;
 474   p->nLookahead++;
 475 }
 476
 477 /*
 478 ** Add the transaction set built up with prior calls to acttab_action()
 479 ** into the current action table.  Then reset the transaction set back
 480 ** to an empty set in preparation for a new round of acttab_action() calls.
 481 **
 482 ** Return the offset into the action table of the new transaction.
 483 */
 484 int acttab_insert(acttab *p){
 485   int i, j, k, n;
 486   assert( p->nLookahead>0 );
 487
 488   /* Make sure we have enough space to hold the expanded action table
 489   ** in the worst case.  The worst case occurs if the transaction set
 490   ** must be appended to the current action table
 491   */
 492   n = p->mxLookahead + 1;
 493   if( p->nAction + n >= p->nActionAlloc ){
 494     int oldAlloc = p->nActionAlloc;
 495     p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
 496     p->aAction = realloc( p->aAction,
 497                           sizeof(p->aAction[0])*p->nActionAlloc);
 498     if( p->aAction==0 ){
 499       fprintf(stderr,"malloc failed\n");
 500       exit(1);
 501     }
 502     for(i=oldAlloc; i<p->nActionAlloc; i++){
 503       p->aAction[i].lookahead = -1;
 504       p->aAction[i].action = -1;
 505     }
 506   }
 507
 508   /* Scan the existing action table looking for an offset where we can
 509   ** insert the current transaction set.  Fall out of the loop when that
 510   ** offset is found.  In the worst case, we fall out of the loop when
 511   ** i reaches p->nAction, which means we append the new transaction set.
 512   **
 513   ** i is the index in p->aAction[] where p->mnLookahead is inserted.
 514   */
 515   for(i=0; i<p->nAction+p->mnLookahead; i++){
 516     if( p->aAction[i].lookahead<0 ){
 517       for(j=0; j<p->nLookahead; j++){
 518         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
 519         if( k<0 ) break;
 520         if( p->aAction[k].lookahead>=0 ) break;
 521       }
 522       if( j<p->nLookahead ) continue;
 523       for(j=0; j<p->nAction; j++){
 524         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
 525       }
 526       if( j==p->nAction ){
 527         break;  /* Fits in empty slots */
 528       }
 529     }else if( p->aAction[i].lookahead==p->mnLookahead ){
 530       if( p->aAction[i].action!=p->mnAction ) continue;
 531       for(j=0; j<p->nLookahead; j++){
 532         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
 533         if( k<0 || k>=p->nAction ) break;
 534         if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
 535         if( p->aLookahead[j].action!=p->aAction[k].action ) break;
 536       }
 537       if( j<p->nLookahead ) continue;
 538       n = 0;
 539       for(j=0; j<p->nAction; j++){
 540         if( p->aAction[j].lookahead<0 ) continue;
 541         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
 542       }
 543       if( n==p->nLookahead ){
 544         break;  /* Same as a prior transaction set */
 545       }
 546     }
 547   }
 548   /* Insert transaction set at index i. */
 549   for(j=0; j<p->nLookahead; j++){
 550     k = p->aLookahead[j].lookahead - p->mnLookahead + i;
 551     p->aAction[k] = p->aLookahead[j];
 552     if( k>=p->nAction ) p->nAction = k+1;
 553   }
 554   p->nLookahead = 0;
 555
 556   /* Return the offset that is added to the lookahead in order to get the
 557   ** index into yy_action of the action */
 558   return i - p->mnLookahead;
 559 }
 560
 561 /********************** From the file "assert.c" ****************************/
 562 /*
 563 ** A more efficient way of handling assertions.
 564 */
 565 void myassert(file,line)
 566 char *file;
 567 int line;
 568 {
 569   fprintf(stderr,"Assertion failed on line %d of file \"%s\"\n",line,file);
 570   exit(1);
 571 }
 572 /********************** From the file "build.c" *****************************/
 573 /*
 574 ** Routines to construction the finite state machine for the LEMON
 575 ** parser generator.
 576 */
 577
 578 /* Find a precedence symbol of every rule in the grammar.
 579 **
 580 ** Those rules which have a precedence symbol coded in the input
 581 ** grammar using the "[symbol]" construct will already have the
 582 ** rp->precsym field filled.  Other rules take as their precedence
 583 ** symbol the first RHS symbol with a defined precedence.  If there
 584 ** are not RHS symbols with a defined precedence, the precedence
 585 ** symbol field is left blank.
 586 */
 587 void FindRulePrecedences(xp)
 588 struct lemon *xp;
 589 {
 590   struct rule *rp;
 591   for(rp=xp->rule; rp; rp=rp->next){
 592     if( rp->precsym==0 ){
 593       int i, j;
 594       for(i=0; i<rp->nrhs && rp->precsym==0; i++){
 595         struct symbol *sp = rp->rhs[i];
 596         if( sp->type==MULTITERMINAL ){
 597           for(j=0; j<sp->nsubsym; j++){
 598             if( sp->subsym[j]->prec>=0 ){
 599               rp->precsym = sp->subsym[j];
 600               break;
 601             }
 602           }
 603         }else if( sp->prec>=0 ){
 604           rp->precsym = rp->rhs[i];
 605         }
 606       }
 607     }
 608   }
 609   return;
 610 }
 611
 612 /* Find all nonterminals which will generate the empty string.
 613 ** Then go back and compute the first sets of every nonterminal.
 614 ** The first set is the set of all terminal symbols which can begin
 615 ** a string generated by that nonterminal.
 616 */
 617 void FindFirstSets(lemp)
 618 struct lemon *lemp;
 619 {
 620   int i, j;
 621   struct rule *rp;
 622   int progress;
 623
 624   for(i=0; i<lemp->nsymbol; i++){
 625     lemp->symbols[i]->lambda = B_FALSE;
 626   }
 627   for(i=lemp->nterminal; i<lemp->nsymbol; i++){
 628     lemp->symbols[i]->firstset = SetNew();
 629   }
 630
 631   /* First compute all lambdas */
 632   do{
 633     progress = 0;
 634     for(rp=lemp->rule; rp; rp=rp->next){
 635       if( rp->lhs->lambda ) continue;
 636       for(i=0; i<rp->nrhs; i++){
 637          struct symbol *sp = rp->rhs[i];
 638          if( sp->type!=TERMINAL || sp->lambda==B_FALSE ) break;
 639       }
 640       if( i==rp->nrhs ){
 641         rp->lhs->lambda = B_TRUE;
 642         progress = 1;
 643       }
 644     }
 645   }while( progress );
 646
 647   /* Now compute all first sets */
 648   do{
 649     struct symbol *s1, *s2;
 650     progress = 0;
 651     for(rp=lemp->rule; rp; rp=rp->next){
 652       s1 = rp->lhs;
 653       for(i=0; i<rp->nrhs; i++){
 654         s2 = rp->rhs[i];
 655         if( s2->type==TERMINAL ){
 656           progress += SetAdd(s1->firstset,s2->index);
 657           break;
 658         }else if( s2->type==MULTITERMINAL ){
 659           for(j=0; j<s2->nsubsym; j++){
 660             progress += SetAdd(s1->firstset,s2->subsym[j]->index);
 661           }
 662           break;
 663         }else if( s1==s2 ){
 664           if( s1->lambda==B_FALSE ) break;
 665         }else{
 666           progress += SetUnion(s1->firstset,s2->firstset);
 667           if( s2->lambda==B_FALSE ) break;
 668         }
 669       }
 670     }
 671   }while( progress );
 672   return;
 673 }
 674
 675 /* Compute all LR(0) states for the grammar.  Links
 676 ** are added to between some states so that the LR(1) follow sets
 677 ** can be computed later.
 678 */
 679 PRIVATE struct state *getstate(/* struct lemon * */);  /* forward reference */
 680 void FindStates(lemp)
 681 struct lemon *lemp;
 682 {
 683   struct symbol *sp;
 684   struct rule *rp;
 685
 686   Configlist_init();
 687
 688   /* Find the start symbol */
 689   if( lemp->start ){
 690     sp = Symbol_find(lemp->start);
 691     if( sp==0 ){
 692       ErrorMsg(lemp->filename,0,
 693 "The specified start symbol \"%s\" is not \
 694 in a nonterminal of the grammar.  \"%s\" will be used as the start \
 695 symbol instead.",lemp->start,lemp->rule->lhs->name);
 696       lemp->errorcnt++;
 697       sp = lemp->rule->lhs;
 698     }
 699   }else{
 700     sp = lemp->rule->lhs;
 701   }
 702
 703   /* Make sure the start symbol doesn't occur on the right-hand side of
 704   ** any rule.  Report an error if it does.  (YACC would generate a new
 705   ** start symbol in this case.) */
 706   for(rp=lemp->rule; rp; rp=rp->next){
 707     int i;
 708     for(i=0; i<rp->nrhs; i++){
 709       if( rp->rhs[i]==sp ){   /* FIX ME:  Deal with multiterminals */
 710         ErrorMsg(lemp->filename,0,
 711 "The start symbol \"%s\" occurs on the \
 712 right-hand side of a rule. This will result in a parser which \
 713 does not work properly.",sp->name);
 714         lemp->errorcnt++;
 715       }
 716     }
 717   }
 718
 719   /* The basis configuration set for the first state
 720   ** is all rules which have the start symbol as their
 721   ** left-hand side */
 722   for(rp=sp->rule; rp; rp=rp->nextlhs){
 723     struct config *newcfp;
 724     newcfp = Configlist_addbasis(rp,0);
 725     SetAdd(newcfp->fws,0);
 726   }
 727
 728   /* Compute the first state.  All other states will be
 729   ** computed automatically during the computation of the first one.
 730   ** The returned pointer to the first state is not used. */
 731   (void)getstate(lemp);
 732   return;
 733 }
 734
 735 /* Return a pointer to a state which is described by the configuration
 736 ** list which has been built from calls to Configlist_add.
 737 */
 738 PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */
 739 PRIVATE struct state *getstate(lemp)
 740 struct lemon *lemp;
 741 {
 742   struct config *cfp, *bp;
 743   struct state *stp;
 744
 745   /* Extract the sorted basis of the new state.  The basis was constructed
 746   ** by prior calls to "Configlist_addbasis()". */
 747   Configlist_sortbasis();
 748   bp = Configlist_basis();
 749
 750   /* Get a state with the same basis */
 751   stp = State_find(bp);
 752   if( stp ){
 753     /* A state with the same basis already exists!  Copy all the follow-set
 754     ** propagation links from the state under construction into the
 755     ** preexisting state, then return a pointer to the preexisting state */
 756     struct config *x, *y;
 757     for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
 758       Plink_copy(&y->bplp,x->bplp);
 759       Plink_delete(x->fplp);
 760       x->fplp = x->bplp = 0;
 761     }
 762     cfp = Configlist_return();
 763     Configlist_eat(cfp);
 764   }else{
 765     /* This really is a new state.  Construct all the details */
 766     Configlist_closure(lemp);    /* Compute the configuration closure */
 767     Configlist_sort();           /* Sort the configuration closure */
 768     cfp = Configlist_return();   /* Get a pointer to the config list */
 769     stp = State_new();           /* A new state structure */
 770     MemoryCheck(stp);
 771     stp->bp = bp;                /* Remember the configuration basis */
 772     stp->cfp = cfp;              /* Remember the configuration closure */
 773     stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
 774     stp->ap = 0;                 /* No actions, yet. */
 775     State_insert(stp,stp->bp);   /* Add to the state table */
 776     buildshifts(lemp,stp);       /* Recursively compute successor states */
 777   }
 778   return stp;
 779 }
 780
 781 /*
 782 ** Return true if two symbols are the same.
 783 */
 784 int same_symbol(a,b)
 785 struct symbol *a;
 786 struct symbol *b;
 787 {
 788   int i;
 789   if( a==b ) return 1;
 790   if( a->type!=MULTITERMINAL ) return 0;
 791   if( b->type!=MULTITERMINAL ) return 0;
 792   if( a->nsubsym!=b->nsubsym ) return 0;
 793   for(i=0; i<a->nsubsym; i++){
 794     if( a->subsym[i]!=b->subsym[i] ) return 0;
 795   }
 796   return 1;
 797 }
 798
 799 /* Construct all successor states to the given state.  A "successor"
 800 ** state is any state which can be reached by a shift action.
 801 */
 802 PRIVATE void buildshifts(lemp,stp)
 803 struct lemon *lemp;
 804 struct state *stp;     /* The state from which successors are computed */
 805 {
 806   struct config *cfp;  /* For looping thru the config closure of "stp" */
 807   struct config *bcfp; /* For the inner loop on config closure of "stp" */
 808   struct config *new;  /* */
 809   struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */
 810   struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */
 811   struct state *newstp; /* A pointer to a successor state */
 812
 813   /* Each configuration becomes complete after it contibutes to a successor
 814   ** state.  Initially, all configurations are incomplete */
 815   for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
 816
 817   /* Loop through all configurations of the state "stp" */
 818   for(cfp=stp->cfp; cfp; cfp=cfp->next){
 819     if( cfp->status==COMPLETE ) continue;    /* Already used by inner loop */
 820     if( cfp->dot>=cfp->rp->nrhs ) continue;  /* Can't shift this config */
 821     Configlist_reset();                      /* Reset the new config set */
 822     sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */
 823
 824     /* For every configuration in the state "stp" which has the symbol "sp"
 825     ** following its dot, add the same configuration to the basis set under
 826     ** construction but with the dot shifted one symbol to the right. */
 827     for(bcfp=cfp; bcfp; bcfp=bcfp->next){
 828       if( bcfp->status==COMPLETE ) continue;    /* Already used */
 829       if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
 830       bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
 831       if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */
 832       bcfp->status = COMPLETE;                  /* Mark this config as used */
 833       new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
 834       Plink_add(&new->bplp,bcfp);
 835     }
 836
 837     /* Get a pointer to the state described by the basis configuration set
 838     ** constructed in the preceding loop */
 839     newstp = getstate(lemp);
 840
 841     /* The state "newstp" is reached from the state "stp" by a shift action
 842     ** on the symbol "sp" */
 843     if( sp->type==MULTITERMINAL ){
 844       int i;
 845       for(i=0; i<sp->nsubsym; i++){
 846         Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
 847       }
 848     }else{
 849       Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
 850     }
 851   }
 852 }
 853
 854 /*
 855 ** Construct the propagation links
 856 */
 857 void FindLinks(lemp)
 858 struct lemon *lemp;
 859 {
 860   int i;
 861   struct config *cfp, *other;
 862   struct state *stp;
 863   struct plink *plp;
 864
 865   /* Housekeeping detail:
 866   ** Add to every propagate link a pointer back to the state to
 867   ** which the link is attached. */
 868   for(i=0; i<lemp->nstate; i++){
 869     stp = lemp->sorted[i];
 870     for(cfp=stp->cfp; cfp; cfp=cfp->next){
 871       cfp->stp = stp;
 872     }
 873   }
 874
 875   /* Convert all backlinks into forward links.  Only the forward
 876   ** links are used in the follow-set computation. */
 877   for(i=0; i<lemp->nstate; i++){
 878     stp = lemp->sorted[i];
 879     for(cfp=stp->cfp; cfp; cfp=cfp->next){
 880       for(plp=cfp->bplp; plp; plp=plp->next){
 881         other = plp->cfp;
 882         Plink_add(&other->fplp,cfp);
 883       }
 884     }
 885   }
 886 }
 887
 888 /* Compute all followsets.
 889 **
 890 ** A followset is the set of all symbols which can come immediately
 891 ** after a configuration.
 892 */
 893 void FindFollowSets(lemp)
 894 struct lemon *lemp;
 895 {
 896   int i;
 897   struct config *cfp;
 898   struct plink *plp;
 899   int progress;
 900   int change;
 901
 902   for(i=0; i<lemp->nstate; i++){
 903     for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
 904       cfp->status = INCOMPLETE;
 905     }
 906   }
 907
 908   do{
 909     progress = 0;
 910     for(i=0; i<lemp->nstate; i++){
 911       for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
 912         if( cfp->status==COMPLETE ) continue;
 913         for(plp=cfp->fplp; plp; plp=plp->next){
 914           change = SetUnion(plp->cfp->fws,cfp->fws);
 915           if( change ){
 916             plp->cfp->status = INCOMPLETE;
 917             progress = 1;
 918           }
 919         }
 920         cfp->status = COMPLETE;
 921       }
 922     }
 923   }while( progress );
 924 }
 925
 926 static int resolve_conflict();
 927
 928 /* Compute the reduce actions, and resolve conflicts.
 929 */
 930 void FindActions(lemp)
 931 struct lemon *lemp;
 932 {
 933   int i,j;
 934   struct config *cfp;
 935   struct state *stp;
 936   struct symbol *sp;
 937   struct rule *rp;
 938
 939   /* Add all of the reduce actions
 940   ** A reduce action is added for each element of the followset of
 941   ** a configuration which has its dot at the extreme right.
 942   */
 943   for(i=0; i<lemp->nstate; i++){   /* Loop over all states */
 944     stp = lemp->sorted[i];
 945     for(cfp=stp->cfp; cfp; cfp=cfp->next){  /* Loop over all configurations */
 946       if( cfp->rp->nrhs==cfp->dot ){        /* Is dot at extreme right? */
 947         for(j=0; j<lemp->nterminal; j++){
 948           if( SetFind(cfp->fws,j) ){
 949             /* Add a reduce action to the state "stp" which will reduce by the
 950             ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
 951             Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
 952           }
 953         }
 954       }
 955     }
 956   }
 957
 958   /* Add the accepting token */
 959   if( lemp->start ){
 960     sp = Symbol_find(lemp->start);
 961     if( sp==0 ) sp = lemp->rule->lhs;
 962   }else{
 963     sp = lemp->rule->lhs;
 964   }
 965   /* Add to the first state (which is always the starting state of the
 966   ** finite state machine) an action to ACCEPT if the lookahead is the
 967   ** start nonterminal.  */
 968   Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
 969
 970   /* Resolve conflicts */
 971   for(i=0; i<lemp->nstate; i++){
 972     struct action *ap, *nap;
 973     struct state *stp;
 974     stp = lemp->sorted[i];
 975     assert( stp->ap );
 976     stp->ap = Action_sort(stp->ap);
 977     for(ap=stp->ap; ap && ap->next; ap=ap->next){
 978       for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
 979          /* The two actions "ap" and "nap" have the same lookahead.
 980          ** Figure out which one should be used */
 981          lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
 982       }
 983     }
 984   }
 985
 986   /* Report an error for each rule that can never be reduced. */
 987   for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = B_FALSE;
 988   for(i=0; i<lemp->nstate; i++){
 989     struct action *ap;
 990     for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
 991       if( ap->type==REDUCE ) ap->x.rp->canReduce = B_TRUE;
 992     }
 993   }
 994   for(rp=lemp->rule; rp; rp=rp->next){
 995     if( rp->canReduce ) continue;
 996     ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
 997     lemp->errorcnt++;
 998   }
 999 }
1000
1001 /* Resolve a conflict between the two given actions.  If the
1002 ** conflict can't be resolve, return non-zero.
1003 **
1004 ** NO LONGER TRUE:
1005 **   To resolve a conflict, first look to see if either action
1006 **   is on an error rule.  In that case, take the action which
1007 **   is not associated with the error rule.  If neither or both
1008 **   actions are associated with an error rule, then try to
1009 **   use precedence to resolve the conflict.
1010 **
1011 ** If either action is a SHIFT, then it must be apx.  This
1012 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1013 */
1014 static int resolve_conflict(apx,apy,errsym)
1015 struct action *apx;
1016 struct action *apy;
1017 struct symbol *errsym;   /* The error symbol (if defined.  NULL otherwise) */
1018 {
1019   struct symbol *spx, *spy;
1020   int errcnt = 0;
1021   assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
1022   if( apx->type==SHIFT && apy->type==REDUCE ){
1023     spx = apx->sp;
1024     spy = apy->x.rp->precsym;
1025     if( spy==0 || spx->prec<0 || spy->prec<0 ){
1026       /* Not enough precedence information. */
1027       apy->type = CONFLICT;
1028       errcnt++;
1029     }else if( spx->prec>spy->prec ){    /* Lower precedence wins */
1030       apy->type = RD_RESOLVED;
1031     }else if( spx->prec<spy->prec ){
1032       apx->type = SH_RESOLVED;
1033     }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
1034       apy->type = RD_RESOLVED;                             /* associativity */
1035     }else if( spx->prec==spy->prec && spx->assoc==LEFT ){  /* to break tie */
1036       apx->type = SH_RESOLVED;
1037     }else{
1038       assert( spx->prec==spy->prec && spx->assoc==NONE );
1039       apy->type = CONFLICT;
1040       errcnt++;
1041     }
1042   }else if( apx->type==REDUCE && apy->type==REDUCE ){
1043     spx = apx->x.rp->precsym;
1044     spy = apy->x.rp->precsym;
1045     if( spx==0 || spy==0 || spx->prec<0 ||
1046     spy->prec<0 || spx->prec==spy->prec ){
1047       apy->type = CONFLICT;
1048       errcnt++;
1049     }else if( spx->prec>spy->prec ){
1050       apy->type = RD_RESOLVED;
1051     }else if( spx->prec<spy->prec ){
1052       apx->type = RD_RESOLVED;
1053     }
1054   }else{
1055     assert(
1056       apx->type==SH_RESOLVED ||
1057       apx->type==RD_RESOLVED ||
1058       apx->type==CONFLICT ||
1059       apy->type==SH_RESOLVED ||
1060       apy->type==RD_RESOLVED ||
1061       apy->type==CONFLICT
1062     );
1063     /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1064     ** REDUCEs on the list.  If we reach this point it must be because
1065     ** the parser conflict had already been resolved. */
1066   }
1067   return errcnt;
1068 }
1069 /********************* From the file "configlist.c" *************************/
1070 /*
1071 ** Routines to processing a configuration list and building a state
1072 ** in the LEMON parser generator.
1073 */
1074
1075 static struct config *freelist = 0;      /* List of free configurations */
1076 static struct config *current = 0;       /* Top of list of configurations */
1077 static struct config **currentend = 0;   /* Last on list of configs */
1078 static struct config *basis = 0;         /* Top of list of basis configs */
1079 static struct config **basisend = 0;     /* End of list of basis configs */
1080
1081 /* Return a pointer to a new configuration */
1082 PRIVATE struct config *newconfig(){
1083   struct config *new;
1084   if( freelist==0 ){
1085     int i;
1086     int amt = 3;
1087     freelist = (struct config *)malloc( sizeof(struct config)*amt );
1088     if( freelist==0 ){
1089       fprintf(stderr,"Unable to allocate memory for a new configuration.");
1090       exit(1);
1091     }
1092     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
1093     freelist[amt-1].next = 0;
1094   }
1095   new = freelist;
1096   freelist = freelist->next;
1097   return new;
1098 }
1099
1100 /* The configuration "old" is no longer used */
1101 PRIVATE void deleteconfig(old)
1102 struct config *old;
1103 {
1104   old->next = freelist;
1105   freelist = old;
1106 }
1107
1108 /* Initialized the configuration list builder */
1109 void Configlist_init(){
1110   current = 0;
1111   currentend = &current;
1112   basis = 0;
1113   basisend = &basis;
1114   Configtable_init();
1115   return;
1116 }
1117
1118 /* Initialized the configuration list builder */
1119 void Configlist_reset(){
1120   current = 0;
1121   currentend = &current;
1122   basis = 0;
1123   basisend = &basis;
1124   Configtable_clear(0);
1125   return;
1126 }
1127
1128 /* Add another configuration to the configuration list */
1129 struct config *Configlist_add(rp,dot)
1130 struct rule *rp;    /* The rule */
1131 int dot;            /* Index into the RHS of the rule where the dot goes */
1132 {
1133   struct config *cfp, model;
1134
1135   assert( currentend!=0 );
1136   model.rp = rp;
1137   model.dot = dot;
1138   cfp = Configtable_find(&model);
1139   if( cfp==0 ){
1140     cfp = newconfig();
1141     cfp->rp = rp;
1142     cfp->dot = dot;
1143     cfp->fws = SetNew();
1144     cfp->stp = 0;
1145     cfp->fplp = cfp->bplp = 0;
1146     cfp->next = 0;
1147     cfp->bp = 0;
1148     *currentend = cfp;
1149     currentend = &cfp->next;
1150     Configtable_insert(cfp);
1151   }
1152   return cfp;
1153 }
1154
1155 /* Add a basis configuration to the configuration list */
1156 struct config *Configlist_addbasis(rp,dot)
1157 struct rule *rp;
1158 int dot;
1159 {
1160   struct config *cfp, model;
1161
1162   assert( basisend!=0 );
1163   assert( currentend!=0 );
1164   model.rp = rp;
1165   model.dot = dot;
1166   cfp = Configtable_find(&model);
1167   if( cfp==0 ){
1168     cfp = newconfig();
1169     cfp->rp = rp;
1170     cfp->dot = dot;
1171     cfp->fws = SetNew();
1172     cfp->stp = 0;
1173     cfp->fplp = cfp->bplp = 0;
1174     cfp->next = 0;
1175     cfp->bp = 0;
1176     *currentend = cfp;
1177     currentend = &cfp->next;
1178     *basisend = cfp;
1179     basisend = &cfp->bp;
1180     Configtable_insert(cfp);
1181   }
1182   return cfp;
1183 }
1184
1185 /* Compute the closure of the configuration list */
1186 void Configlist_closure(lemp)
1187 struct lemon *lemp;
1188 {
1189   struct config *cfp, *newcfp;
1190   struct rule *rp, *newrp;
1191   struct symbol *sp, *xsp;
1192   int i, dot;
1193
1194   assert( currentend!=0 );
1195   for(cfp=current; cfp; cfp=cfp->next){
1196     rp = cfp->rp;
1197     dot = cfp->dot;
1198     if( dot>=rp->nrhs ) continue;
1199     sp = rp->rhs[dot];
1200     if( sp->type==NONTERMINAL ){
1201       if( sp->rule==0 && sp!=lemp->errsym ){
1202         ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",
1203           sp->name);
1204         lemp->errorcnt++;
1205       }
1206       for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
1207         newcfp = Configlist_add(newrp,0);
1208         for(i=dot+1; i<rp->nrhs; i++){
1209           xsp = rp->rhs[i];
1210           if( xsp->type==TERMINAL ){
1211             SetAdd(newcfp->fws,xsp->index);
1212             break;
1213           }else if( xsp->type==MULTITERMINAL ){
1214             int k;
1215             for(k=0; k<xsp->nsubsym; k++){
1216               SetAdd(newcfp->fws, xsp->subsym[k]->index);
1217             }
1218             break;
1219           }else{
1220             SetUnion(newcfp->fws,xsp->firstset);
1221             if( xsp->lambda==B_FALSE ) break;
1222           }
1223         }
1224         if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);
1225       }
1226     }
1227   }
1228   return;
1229 }
1230
1231 /* Sort the configuration list */
1232 void Configlist_sort(){
1233   current = (struct config *)msort((char *)current,(char **)&(current->next),Configcmp);
1234   currentend = 0;
1235   return;
1236 }
1237
1238 /* Sort the basis configuration list */
1239 void Configlist_sortbasis(){
1240   basis = (struct config *)msort((char *)current,(char **)&(current->bp),Configcmp);
1241   basisend = 0;
1242   return;
1243 }
1244
1245 /* Return a pointer to the head of the configuration list and
1246 ** reset the list */
1247 struct config *Configlist_return(){
1248   struct config *old;
1249   old = current;
1250   current = 0;
1251   currentend = 0;
1252   return old;
1253 }
1254
1255 /* Return a pointer to the head of the configuration list and
1256 ** reset the list */
1257 struct config *Configlist_basis(){
1258   struct config *old;
1259   old = basis;
1260   basis = 0;
1261   basisend = 0;
1262   return old;
1263 }
1264
1265 /* Free all elements of the given configuration list */
1266 void Configlist_eat(cfp)
1267 struct config *cfp;
1268 {
1269   struct config *nextcfp;
1270   for(; cfp; cfp=nextcfp){
1271     nextcfp = cfp->next;
1272     assert( cfp->fplp==0 );
1273     assert( cfp->bplp==0 );
1274     if( cfp->fws ) SetFree(cfp->fws);
1275     deleteconfig(cfp);
1276   }
1277   return;
1278 }
1279 /***************** From the file "error.c" *********************************/
1280 /*
1281 ** Code for printing error message.
1282 */
1283
1284 /* Find a good place to break "msg" so that its length is at least "min"
1285 ** but no more than "max".  Make the point as close to max as possible.
1286 */
1287 static int findbreak(msg,min,max)
1288 char *msg;
1289 int min;
1290 int max;
1291 {
1292   int i,spot;
1293   char c;
1294   for(i=spot=min; i<=max; i++){
1295     c = msg[i];
1296     if( c=='\t' ) msg[i] = ' ';
1297     if( c=='\n' ){ msg[i] = ' '; spot = i; break; }
1298     if( c==0 ){ spot = i; break; }
1299     if( c=='-' && i<max-1 ) spot = i+1;
1300     if( c==' ' ) spot = i;
1301   }
1302   return spot;
1303 }
1304
1305 /*
1306 ** The error message is split across multiple lines if necessary.  The
1307 ** splits occur at a space, if there is a space available near the end
1308 ** of the line.
1309 */
1310 #define ERRMSGSIZE  10000 /* Hope this is big enough.  No way to error check */
1311 #define LINEWIDTH      79 /* Max width of any output line */
1312 #define PREFIXLIMIT    30 /* Max width of the prefix on each line */
1313 void ErrorMsg(const char *filename, int lineno, const char *format, ...){
1314   char errmsg[ERRMSGSIZE];
1315   char prefix[PREFIXLIMIT+10];
1316   int errmsgsize;
1317   int prefixsize;
1318   int availablewidth;
1319   va_list ap;
1320   int end, restart, base;
1321
1322   va_start(ap, format);
1323   /* Prepare a prefix to be prepended to every output line */
1324   if( lineno>0 ){
1325     sprintf(prefix,"%.*s:%d: ",PREFIXLIMIT-10,filename,lineno);
1326   }else{
1327     sprintf(prefix,"%.*s: ",PREFIXLIMIT-10,filename);
1328   }
1329   prefixsize = strlen(prefix);
1330   availablewidth = LINEWIDTH - prefixsize;
1331
1332   /* Generate the error message */
1333   vsprintf(errmsg,format,ap);
1334   va_end(ap);
1335   errmsgsize = strlen(errmsg);
1336   /* Remove trailing '\n's from the error message. */
1337   while( errmsgsize>0 && errmsg[errmsgsize-1]=='\n' ){
1338      errmsg[--errmsgsize] = 0;
1339   }
1340
1341   /* Print the error message */
1342   base = 0;
1343   while( errmsg[base]!=0 ){
1344     end = restart = findbreak(&errmsg[base],0,availablewidth);
1345     restart += base;
1346     while( errmsg[restart]==' ' ) restart++;
1347     fprintf(stdout,"%s%.*s\n",prefix,end,&errmsg[base]);
1348     base = restart;
1349   }
1350 }
1351 /**************** From the file "main.c" ************************************/
1352 /*
1353 ** Main program file for the LEMON parser generator.
1354 */
1355
1356 /* Report an out-of-memory condition and abort.  This function
1357 ** is used mostly by the "MemoryCheck" macro in struct.h
1358 */
1359 void memory_error(){
1360   fprintf(stderr,"Out of memory.  Aborting...\n");
1361   exit(1);
1362 }
1363
1364 static int nDefine = 0;      /* Number of -D options on the command line */
1365 static char **azDefine = 0;  /* Name of the -D macros */
1366
1367 /* This routine is called with the argument to each -D command-line option.
1368 ** Add the macro defined to the azDefine array.
1369 */
1370 static void handle_D_option(char *z){
1371   char **paz;
1372   nDefine++;
1373   azDefine = realloc(azDefine, sizeof(azDefine[0])*nDefine);
1374   if( azDefine==0 ){
1375     fprintf(stderr,"out of memory\n");
1376     exit(1);
1377   }
1378   paz = &azDefine[nDefine-1];
1379   *paz = malloc( strlen(z)+1 );
1380   if( *paz==0 ){
1381     fprintf(stderr,"out of memory\n");
1382     exit(1);
1383   }
1384   strcpy(*paz, z);
1385   for(z=*paz; *z && *z!='='; z++){}
1386   *z = 0;
1387 }
1388
1389
1390 /* The main program.  Parse the command line and do it... */
1391 int main(argc,argv)
1392 int argc;
1393 char **argv;
1394 {
1395   static int version = 0;
1396   static int rpflag = 0;
1397   static int basisflag = 0;
1398   static int compress = 0;
1399   static int quiet = 0;
1400   static int statistics = 0;
1401   static int mhflag = 0;
1402   static struct s_options options[] = {
1403     {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
1404     {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
1405     {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
1406     {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
1407     {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file"},
1408     {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
1409     {OPT_FLAG, "s", (char*)&statistics,
1410                                    "Print parser stats to standard output."},
1411     {OPT_FLAG, "x", (char*)&version, "Print the version number."},
1412     {OPT_FLAG,0,0,0}
1413   };
1414   int i;
1415   struct lemon lem;
1416
1417   OptInit(argv,options,stderr);
1418   if( version ){
1419      printf("Lemon version 1.0\n");
1420      exit(0);
1421   }
1422   if( OptNArgs()!=1 ){
1423     fprintf(stderr,"Exactly one filename argument is required.\n");
1424     exit(1);
1425   }
1426   memset(&lem, 0, sizeof(lem));
1427   lem.errorcnt = 0;
1428
1429   /* Initialize the machine */
1430   Strsafe_init();
1431   Symbol_init();
1432   State_init();
1433   lem.argv0 = argv[0];
1434   lem.filename = OptArg(0);
1435   lem.basisflag = basisflag;
1436   Symbol_new("$");
1437   lem.errsym = Symbol_new("error");
1438
1439   /* Parse the input file */
1440   Parse(&lem);
1441   if( lem.errorcnt ) exit(lem.errorcnt);
1442   if( lem.nrule==0 ){
1443     fprintf(stderr,"Empty grammar.\n");
1444     exit(1);
1445   }
1446
1447   /* Count and index the symbols of the grammar */
1448   lem.nsymbol = Symbol_count();
1449   Symbol_new("{default}");
1450   lem.symbols = Symbol_arrayof();
1451   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
1452   qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*),
1453         (int(*)())Symbolcmpp);
1454   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
1455   for(i=1; isupper(lem.symbols[i]->name[0]); i++);
1456   lem.nterminal = i;
1457
1458   /* Generate a reprint of the grammar, if requested on the command line */
1459   if( rpflag ){
1460     Reprint(&lem);
1461   }else{
1462     /* Initialize the size for all follow and first sets */
1463     SetSize(lem.nterminal);
1464
1465     /* Find the precedence for every production rule (that has one) */
1466     FindRulePrecedences(&lem);
1467
1468     /* Compute the lambda-nonterminals and the first-sets for every
1469     ** nonterminal */
1470     FindFirstSets(&lem);
1471
1472     /* Compute all LR(0) states.  Also record follow-set propagation
1473     ** links so that the follow-set can be computed later */
1474     lem.nstate = 0;
1475     FindStates(&lem);
1476     lem.sorted = State_arrayof();
1477
1478     /* Tie up loose ends on the propagation links */
1479     FindLinks(&lem);
1480
1481     /* Compute the follow set of every reducible configuration */
1482     FindFollowSets(&lem);
1483
1484     /* Compute the action tables */
1485     FindActions(&lem);
1486
1487     /* Compress the action tables */
1488     if( compress==0 ) CompressTables(&lem);
1489
1490     /* Reorder and renumber the states so that states with fewer choices
1491     ** occur at the end. */
1492     ResortStates(&lem);
1493
1494     /* Generate a report of the parser generated.  (the "y.output" file) */
1495     if( !quiet ) ReportOutput(&lem);
1496
1497     /* Generate the source code for the parser */
1498     ReportTable(&lem, mhflag);
1499
1500     /* Produce a header file for use by the scanner.  (This step is
1501     ** omitted if the "-m" option is used because makeheaders will
1502     ** generate the file for us.) */
1503     if( !mhflag ) ReportHeader(&lem);
1504   }
1505   if( statistics ){
1506     printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
1507       lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
1508     printf("                   %d states, %d parser table entries, %d conflicts\n",
1509       lem.nstate, lem.tablesize, lem.nconflict);
1510   }
1511   if( lem.nconflict ){
1512     fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
1513   }
1514   exit(lem.errorcnt + lem.nconflict);
1515   return (lem.errorcnt + lem.nconflict);
1516 }
1517 /******************** From the file "msort.c" *******************************/
1518 /*
1519 ** A generic merge-sort program.
1520 **
1521 ** USAGE:
1522 ** Let "ptr" be a pointer to some structure which is at the head of
1523 ** a null-terminated list.  Then to sort the list call:
1524 **
1525 **     ptr = msort(ptr,&(ptr->next),cmpfnc);
1526 **
1527 ** In the above, "cmpfnc" is a pointer to a function which compares
1528 ** two instances of the structure and returns an integer, as in
1529 ** strcmp.  The second argument is a pointer to the pointer to the
1530 ** second element of the linked list.  This address is used to compute
1531 ** the offset to the "next" field within the structure.  The offset to
1532 ** the "next" field must be constant for all structures in the list.
1533 **
1534 ** The function returns a new pointer which is the head of the list
1535 ** after sorting.
1536 **
1537 ** ALGORITHM:
1538 ** Merge-sort.
1539 */
1540
1541 /*
1542 ** Return a pointer to the next structure in the linked list.
1543 */
1544 #define NEXT(A) (*(char**)(((unsigned long)A)+offset))
1545
1546 /*
1547 ** Inputs:
1548 **   a:       A sorted, null-terminated linked list.  (May be null).
1549 **   b:       A sorted, null-terminated linked list.  (May be null).
1550 **   cmp:     A pointer to the comparison function.
1551 **   offset:  Offset in the structure to the "next" field.
1552 **
1553 ** Return Value:
1554 **   A pointer to the head of a sorted list containing the elements
1555 **   of both a and b.
1556 **
1557 ** Side effects:
1558 **   The "next" pointers for elements in the lists a and b are
1559 **   changed.
1560 */
1561 static char *merge(a,b,cmp,offset)
1562 char *a;
1563 char *b;
1564 int (*cmp)();
1565 int offset;
1566 {
1567   char *ptr, *head;
1568
1569   if( a==0 ){
1570     head = b;
1571   }else if( b==0 ){
1572     head = a;
1573   }else{
1574     if( (*cmp)(a,b)<0 ){
1575       ptr = a;
1576       a = NEXT(a);
1577     }else{
1578       ptr = b;
1579       b = NEXT(b);
1580     }
1581     head = ptr;
1582     while( a && b ){
1583       if( (*cmp)(a,b)<0 ){
1584         NEXT(ptr) = a;
1585         ptr = a;
1586         a = NEXT(a);
1587       }else{
1588         NEXT(ptr) = b;
1589         ptr = b;
1590         b = NEXT(b);
1591       }
1592     }
1593     if( a ) NEXT(ptr) = a;
1594     else    NEXT(ptr) = b;
1595   }
1596   return head;
1597 }
1598
1599 /*
1600 ** Inputs:
1601 **   list:      Pointer to a singly-linked list of structures.
1602 **   next:      Pointer to pointer to the second element of the list.
1603 **   cmp:       A comparison function.
1604 **
1605 ** Return Value:
1606 **   A pointer to the head of a sorted list containing the elements
1607 **   orginally in list.
1608 **
1609 ** Side effects:
1610 **   The "next" pointers for elements in list are changed.
1611 */
1612 #define LISTSIZE 30
1613 char *msort(list,next,cmp)
1614 char *list;
1615 char **next;
1616 int (*cmp)();
1617 {
1618   unsigned long offset;
1619   char *ep;
1620   char *set[LISTSIZE];
1621   int i;
1622   offset = (unsigned long)next - (unsigned long)list;
1623   for(i=0; i<LISTSIZE; i++) set[i] = 0;
1624   while( list ){
1625     ep = list;
1626     list = NEXT(list);
1627     NEXT(ep) = 0;
1628     for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
1629       ep = merge(ep,set[i],cmp,offset);
1630       set[i] = 0;
1631     }
1632     set[i] = ep;
1633   }
1634   ep = 0;
1635   for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(ep,set[i],cmp,offset);
1636   return ep;
1637 }
1638 /************************ From the file "option.c" **************************/
1639 static char **argv;
1640 static struct s_options *op;
1641 static FILE *errstream;
1642
1643 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1644
1645 /*
1646 ** Print the command line with a carrot pointing to the k-th character
1647 ** of the n-th field.
1648 */
1649 static void errline(n,k,err)
1650 int n;
1651 int k;
1652 FILE *err;
1653 {
1654   int spcnt, i;
1655   if( argv[0] ) fprintf(err,"%s",argv[0]);
1656   spcnt = strlen(argv[0]) + 1;
1657   for(i=1; i<n && argv[i]; i++){
1658     fprintf(err," %s",argv[i]);
1659     spcnt += strlen(argv[i])+1;
1660   }
1661   spcnt += k;
1662   for(; argv[i]; i++) fprintf(err," %s",argv[i]);
1663   if( spcnt<20 ){
1664     fprintf(err,"\n%*s^-- here\n",spcnt,"");
1665   }else{
1666     fprintf(err,"\n%*shere --^\n",spcnt-7,"");
1667   }
1668 }
1669
1670 /*
1671 ** Return the index of the N-th non-switch argument.  Return -1
1672 ** if N is out of range.
1673 */
1674 static int argindex(n)
1675 int n;
1676 {
1677   int i;
1678   int dashdash = 0;
1679   if( argv!=0 && *argv!=0 ){
1680     for(i=1; argv[i]; i++){
1681       if( dashdash || !ISOPT(argv[i]) ){
1682         if( n==0 ) return i;
1683         n--;
1684       }
1685       if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1686     }
1687   }
1688   return -1;
1689 }
1690
1691 static char emsg[] = "Command line syntax error: ";
1692
1693 /*
1694 ** Process a flag command line argument.
1695 */
1696 static int handleflags(i,err)
1697 int i;
1698 FILE *err;
1699 {
1700   int v;
1701   int errcnt = 0;
1702   int j;
1703   for(j=0; op[j].label; j++){
1704     if( strncmp(&argv[i][1],op[j].label,strlen(op[j].label))==0 ) break;
1705   }
1706   v = argv[i][0]=='-' ? 1 : 0;
1707   if( op[j].label==0 ){
1708     if( err ){
1709       fprintf(err,"%sundefined option.\n",emsg);
1710       errline(i,1,err);
1711     }
1712     errcnt++;
1713   }else if( op[j].type==OPT_FLAG ){
1714     *((int*)op[j].arg) = v;
1715   }else if( op[j].type==OPT_FFLAG ){
1716     (*(void(*)())(op[j].arg))(v);
1717   }else if( op[j].type==OPT_FSTR ){
1718     (*(void(*)())(op[j].arg))(&argv[i][2]);
1719   }else{
1720     if( err ){
1721       fprintf(err,"%smissing argument on switch.\n",emsg);
1722       errline(i,1,err);
1723     }
1724     errcnt++;
1725   }
1726   return errcnt;
1727 }
1728
1729 /*
1730 ** Process a command line switch which has an argument.
1731 */
1732 static int handleswitch(i,err)
1733 int i;
1734 FILE *err;
1735 {
1736   int lv = 0;
1737   double dv = 0.0;
1738   char *sv = 0, *end;
1739   char *cp;
1740   int j;
1741   int errcnt = 0;
1742   cp = strchr(argv[i],'=');
1743   assert( cp!=0 );
1744   *cp = 0;
1745   for(j=0; op[j].label; j++){
1746     if( strcmp(argv[i],op[j].label)==0 ) break;
1747   }
1748   *cp = '=';
1749   if( op[j].label==0 ){
1750     if( err ){
1751       fprintf(err,"%sundefined option.\n",emsg);
1752       errline(i,0,err);
1753     }
1754     errcnt++;
1755   }else{
1756     cp++;
1757     switch( op[j].type ){
1758       case OPT_FLAG:
1759       case OPT_FFLAG:
1760         if( err ){
1761           fprintf(err,"%soption requires an argument.\n",emsg);
1762           errline(i,0,err);
1763         }
1764         errcnt++;
1765         break;
1766       case OPT_DBL:
1767       case OPT_FDBL:
1768         dv = strtod(cp,&end);
1769         if( *end ){
1770           if( err ){
1771             fprintf(err,"%sillegal character in floating-point argument.\n",emsg);
1772             errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
1773           }
1774           errcnt++;
1775         }
1776         break;
1777       case OPT_INT:
1778       case OPT_FINT:
1779         lv = strtol(cp,&end,0);
1780         if( *end ){
1781           if( err ){
1782             fprintf(err,"%sillegal character in integer argument.\n",emsg);
1783             errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
1784           }
1785           errcnt++;
1786         }
1787         break;
1788       case OPT_STR:
1789       case OPT_FSTR:
1790         sv = cp;
1791         break;
1792     }
1793     switch( op[j].type ){
1794       case OPT_FLAG:
1795       case OPT_FFLAG:
1796         break;
1797       case OPT_DBL:
1798         *(double*)(op[j].arg) = dv;
1799         break;
1800       case OPT_FDBL:
1801         (*(void(*)())(op[j].arg))(dv);
1802         break;
1803       case OPT_INT:
1804         *(int*)(op[j].arg) = lv;
1805         break;
1806       case OPT_FINT:
1807         (*(void(*)())(op[j].arg))((int)lv);
1808         break;
1809       case OPT_STR:
1810         *(char**)(op[j].arg) = sv;
1811         break;
1812       case OPT_FSTR:
1813         (*(void(*)())(op[j].arg))(sv);
1814         break;
1815     }
1816   }
1817   return errcnt;
1818 }
1819
1820 int OptInit(a,o,err)
1821 char **a;
1822 struct s_options *o;
1823 FILE *err;
1824 {
1825   int errcnt = 0;
1826   argv = a;
1827   op = o;
1828   errstream = err;
1829   if( argv && *argv && op ){
1830     int i;
1831     for(i=1; argv[i]; i++){
1832       if( argv[i][0]=='+' || argv[i][0]=='-' ){
1833         errcnt += handleflags(i,err);
1834       }else if( strchr(argv[i],'=') ){
1835         errcnt += handleswitch(i,err);
1836       }
1837     }
1838   }
1839   if( errcnt>0 ){
1840     fprintf(err,"Valid command line options for \"%s\" are:\n",*a);
1841     OptPrint();
1842     exit(1);
1843   }
1844   return 0;
1845 }
1846
1847 int OptNArgs(){
1848   int cnt = 0;
1849   int dashdash = 0;
1850   int i;
1851   if( argv!=0 && argv[0]!=0 ){
1852     for(i=1; argv[i]; i++){
1853       if( dashdash || !ISOPT(argv[i]) ) cnt++;
1854       if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1855     }
1856   }
1857   return cnt;
1858 }
1859
1860 char *OptArg(n)
1861 int n;
1862 {
1863   int i;
1864   i = argindex(n);
1865   return i>=0 ? argv[i] : 0;
1866 }
1867
1868 void OptErr(n)
1869 int n;
1870 {
1871   int i;
1872   i = argindex(n);
1873   if( i>=0 ) errline(i,0,errstream);
1874 }
1875
1876 void OptPrint(){
1877   int i;
1878   int max, len;
1879   max = 0;
1880   for(i=0; op[i].label; i++){
1881     len = strlen(op[i].label) + 1;
1882     switch( op[i].type ){
1883       case OPT_FLAG:
1884       case OPT_FFLAG:
1885         break;
1886       case OPT_INT:
1887       case OPT_FINT:
1888         len += 9;       /* length of "<integer>" */
1889         break;
1890       case OPT_DBL:
1891       case OPT_FDBL:
1892         len += 6;       /* length of "<real>" */
1893         break;
1894       case OPT_STR:
1895       case OPT_FSTR:
1896         len += 8;       /* length of "<string>" */
1897         break;
1898     }
1899     if( len>max ) max = len;
1900   }
1901   for(i=0; op[i].label; i++){
1902     switch( op[i].type ){
1903       case OPT_FLAG:
1904       case OPT_FFLAG:
1905         fprintf(errstream,"  -%-*s  %s\n",max,op[i].label,op[i].message);
1906         break;
1907       case OPT_INT:
1908       case OPT_FINT:
1909         fprintf(errstream,"  %s=<integer>%*s  %s\n",op[i].label,
1910           (int)(max-strlen(op[i].label)-9),"",op[i].message);
1911         break;
1912       case OPT_DBL:
1913       case OPT_FDBL:
1914         fprintf(errstream,"  %s=<real>%*s  %s\n",op[i].label,
1915           (int)(max-strlen(op[i].label)-6),"",op[i].message);
1916         break;
1917       case OPT_STR:
1918       case OPT_FSTR:
1919         fprintf(errstream,"  %s=<string>%*s  %s\n",op[i].label,
1920           (int)(max-strlen(op[i].label)-8),"",op[i].message);
1921         break;
1922     }
1923   }
1924 }
1925 /*********************** From the file "parse.c" ****************************/
1926 /*
1927 ** Input file parser for the LEMON parser generator.
1928 */
1929
1930 /* The state of the parser */
1931 struct pstate {
1932   char *filename;       /* Name of the input file */
1933   int tokenlineno;      /* Linenumber at which current token starts */
1934   int errorcnt;         /* Number of errors so far */
1935   char *tokenstart;     /* Text of current token */
1936   struct lemon *gp;     /* Global state vector */
1937   enum e_state {
1938     INITIALIZE,
1939     WAITING_FOR_DECL_OR_RULE,
1940     WAITING_FOR_DECL_KEYWORD,
1941     WAITING_FOR_DECL_ARG,
1942     WAITING_FOR_PRECEDENCE_SYMBOL,
1943     WAITING_FOR_ARROW,
1944     IN_RHS,
1945     LHS_ALIAS_1,
1946     LHS_ALIAS_2,
1947     LHS_ALIAS_3,
1948     RHS_ALIAS_1,
1949     RHS_ALIAS_2,
1950     PRECEDENCE_MARK_1,
1951     PRECEDENCE_MARK_2,
1952     RESYNC_AFTER_RULE_ERROR,
1953     RESYNC_AFTER_DECL_ERROR,
1954     WAITING_FOR_DESTRUCTOR_SYMBOL,
1955     WAITING_FOR_DATATYPE_SYMBOL,
1956     WAITING_FOR_FALLBACK_ID,
1957     WAITING_FOR_WILDCARD_ID
1958   } state;                   /* The state of the parser */
1959   struct symbol *fallback;   /* The fallback token */
1960   struct symbol *lhs;        /* Left-hand side of current rule */
1961   char *lhsalias;            /* Alias for the LHS */
1962   int nrhs;                  /* Number of right-hand side symbols seen */
1963   struct symbol *rhs[MAXRHS];  /* RHS symbols */
1964   char *alias[MAXRHS];       /* Aliases for each RHS symbol (or NULL) */
1965   struct rule *prevrule;     /* Previous rule parsed */
1966   char *declkeyword;         /* Keyword of a declaration */
1967   char **declargslot;        /* Where the declaration argument should be put */
1968   int *decllnslot;           /* Where the declaration linenumber is put */
1969   enum e_assoc declassoc;    /* Assign this association to decl arguments */
1970   int preccounter;           /* Assign this precedence to decl arguments */
1971   struct rule *firstrule;    /* Pointer to first rule in the grammar */
1972   struct rule *lastrule;     /* Pointer to the most recently parsed rule */
1973 };
1974
1975 /* Parse a single token */
1976 static void parseonetoken(psp)
1977 struct pstate *psp;
1978 {
1979   char *x;
1980   x = Strsafe(psp->tokenstart);     /* Save the token permanently */
1981 #if 0
1982   printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
1983     x,psp->state);
1984 #endif
1985   switch( psp->state ){
1986     case INITIALIZE:
1987       psp->prevrule = 0;
1988       psp->preccounter = 0;
1989       psp->firstrule = psp->lastrule = 0;
1990       psp->gp->nrule = 0;
1991       /* Fall thru to next case */
1992     case WAITING_FOR_DECL_OR_RULE:
1993       if( x[0]=='%' ){
1994         psp->state = WAITING_FOR_DECL_KEYWORD;
1995       }else if( islower(x[0]) ){
1996         psp->lhs = Symbol_new(x);
1997         psp->nrhs = 0;
1998         psp->lhsalias = 0;
1999         psp->state = WAITING_FOR_ARROW;
2000       }else if( x[0]=='{' ){
2001         if( psp->prevrule==0 ){
2002           ErrorMsg(psp->filename,psp->tokenlineno,
2003 "There is not prior rule opon which to attach the code \
2004 fragment which begins on this line.");
2005           psp->errorcnt++;
2006         }else if( psp->prevrule->code!=0 ){
2007           ErrorMsg(psp->filename,psp->tokenlineno,
2008 "Code fragment beginning on this line is not the first \
2009 to follow the previous rule.");
2010           psp->errorcnt++;
2011         }else{
2012           psp->prevrule->line = psp->tokenlineno;
2013           psp->prevrule->code = &x[1];
2014         }
2015       }else if( x[0]=='[' ){
2016         psp->state = PRECEDENCE_MARK_1;
2017       }else{
2018         ErrorMsg(psp->filename,psp->tokenlineno,
2019           "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2020           x);
2021         psp->errorcnt++;
2022       }
2023       break;
2024     case PRECEDENCE_MARK_1:
2025       if( !isupper(x[0]) ){
2026         ErrorMsg(psp->filename,psp->tokenlineno,
2027           "The precedence symbol must be a terminal.");
2028         psp->errorcnt++;
2029       }else if( psp->prevrule==0 ){
2030         ErrorMsg(psp->filename,psp->tokenlineno,
2031           "There is no prior rule to assign precedence \"[%s]\".",x);
2032         psp->errorcnt++;
2033       }else if( psp->prevrule->precsym!=0 ){
2034         ErrorMsg(psp->filename,psp->tokenlineno,
2035 "Precedence mark on this line is not the first \
2036 to follow the previous rule.");
2037         psp->errorcnt++;
2038       }else{
2039         psp->prevrule->precsym = Symbol_new(x);
2040       }
2041       psp->state = PRECEDENCE_MARK_2;
2042       break;
2043     case PRECEDENCE_MARK_2:
2044       if( x[0]!=']' ){
2045         ErrorMsg(psp->filename,psp->tokenlineno,
2046           "Missing \"]\" on precedence mark.");
2047         psp->errorcnt++;
2048       }
2049       psp->state = WAITING_FOR_DECL_OR_RULE;
2050       break;
2051     case WAITING_FOR_ARROW:
2052       if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2053         psp->state = IN_RHS;
2054       }else if( x[0]=='(' ){
2055         psp->state = LHS_ALIAS_1;
2056       }else{
2057         ErrorMsg(psp->filename,psp->tokenlineno,
2058           "Expected to see a \":\" following the LHS symbol \"%s\".",
2059           psp->lhs->name);
2060         psp->errorcnt++;
2061         psp->state = RESYNC_AFTER_RULE_ERROR;
2062       }
2063       break;
2064     case LHS_ALIAS_1:
2065       if( isalpha(x[0]) ){
2066         psp->lhsalias = x;
2067         psp->state = LHS_ALIAS_2;
2068       }else{
2069         ErrorMsg(psp->filename,psp->tokenlineno,
2070           "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2071           x,psp->lhs->name);
2072         psp->errorcnt++;
2073         psp->state = RESYNC_AFTER_RULE_ERROR;
2074       }
2075       break;
2076     case LHS_ALIAS_2:
2077       if( x[0]==')' ){
2078         psp->state = LHS_ALIAS_3;
2079       }else{
2080         ErrorMsg(psp->filename,psp->tokenlineno,
2081           "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2082         psp->errorcnt++;
2083         psp->state = RESYNC_AFTER_RULE_ERROR;
2084       }
2085       break;
2086     case LHS_ALIAS_3:
2087       if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2088         psp->state = IN_RHS;
2089       }else{
2090         ErrorMsg(psp->filename,psp->tokenlineno,
2091           "Missing \"->\" following: \"%s(%s)\".",
2092            psp->lhs->name,psp->lhsalias);
2093         psp->errorcnt++;
2094         psp->state = RESYNC_AFTER_RULE_ERROR;
2095       }
2096       break;
2097     case IN_RHS:
2098       if( x[0]=='.' ){
2099         struct rule *rp;
2100         rp = (struct rule *)malloc( sizeof(struct rule) +
2101              sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs );
2102         if( rp==0 ){
2103           ErrorMsg(psp->filename,psp->tokenlineno,
2104             "Can't allocate enough memory for this rule.");
2105           psp->errorcnt++;
2106           psp->prevrule = 0;
2107         }else{
2108           int i;
2109           rp->ruleline = psp->tokenlineno;
2110           rp->rhs = (struct symbol**)&rp[1];
2111           rp->rhsalias = (char**)&(rp->rhs[psp->nrhs]);
2112           for(i=0; i<psp->nrhs; i++){
2113             rp->rhs[i] = psp->rhs[i];
2114             rp->rhsalias[i] = psp->alias[i];
2115           }
2116           rp->lhs = psp->lhs;
2117           rp->lhsalias = psp->lhsalias;
2118           rp->nrhs = psp->nrhs;
2119           rp->code = 0;
2120           rp->precsym = 0;
2121           rp->index = psp->gp->nrule++;
2122           rp->nextlhs = rp->lhs->rule;
2123           rp->lhs->rule = rp;
2124           rp->next = 0;
2125           if( psp->firstrule==0 ){
2126             psp->firstrule = psp->lastrule = rp;
2127           }else{
2128             psp->lastrule->next = rp;
2129             psp->lastrule = rp;
2130           }
2131           psp->prevrule = rp;
2132         }
2133         psp->state = WAITING_FOR_DECL_OR_RULE;
2134       }else if( isalpha(x[0]) ){
2135         if( psp->nrhs>=MAXRHS ){
2136           ErrorMsg(psp->filename,psp->tokenlineno,
2137             "Too many symbols on RHS or rule beginning at \"%s\".",
2138             x);
2139           psp->errorcnt++;
2140           psp->state = RESYNC_AFTER_RULE_ERROR;
2141         }else{
2142           psp->rhs[psp->nrhs] = Symbol_new(x);
2143           psp->alias[psp->nrhs] = 0;
2144           psp->nrhs++;
2145         }
2146       }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 ){
2147         struct symbol *msp = psp->rhs[psp->nrhs-1];
2148         if( msp->type!=MULTITERMINAL ){
2149           struct symbol *origsp = msp;
2150           msp = malloc(sizeof(*msp));
2151           memset(msp, 0, sizeof(*msp));
2152           msp->type = MULTITERMINAL;
2153           msp->nsubsym = 1;
2154           msp->subsym = malloc(sizeof(struct symbol*));
2155           msp->subsym[0] = origsp;
2156           msp->name = origsp->name;
2157           psp->rhs[psp->nrhs-1] = msp;
2158         }
2159         msp->nsubsym++;
2160         msp->subsym = realloc(msp->subsym, sizeof(struct symbol*)*msp->nsubsym);
2161         msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);
2162         if( islower(x[1]) || islower(msp->subsym[0]->name[0]) ){
2163           ErrorMsg(psp->filename,psp->tokenlineno,
2164             "Cannot form a compound containing a non-terminal");
2165           psp->errorcnt++;
2166         }
2167       }else if( x[0]=='(' && psp->nrhs>0 ){
2168         psp->state = RHS_ALIAS_1;
2169       }else{
2170         ErrorMsg(psp->filename,psp->tokenlineno,
2171           "Illegal character on RHS of rule: \"%s\".",x);
2172         psp->errorcnt++;
2173         psp->state = RESYNC_AFTER_RULE_ERROR;
2174       }
2175       break;
2176     case RHS_ALIAS_1:
2177       if( isalpha(x[0]) ){
2178         psp->alias[psp->nrhs-1] = x;
2179         psp->state = RHS_ALIAS_2;
2180       }else{
2181         ErrorMsg(psp->filename,psp->tokenlineno,
2182           "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2183           x,psp->rhs[psp->nrhs-1]->name);
2184         psp->errorcnt++;
2185         psp->state = RESYNC_AFTER_RULE_ERROR;
2186       }
2187       break;
2188     case RHS_ALIAS_2:
2189       if( x[0]==')' ){
2190         psp->state = IN_RHS;
2191       }else{
2192         ErrorMsg(psp->filename,psp->tokenlineno,
2193           "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2194         psp->errorcnt++;
2195         psp->state = RESYNC_AFTER_RULE_ERROR;
2196       }
2197       break;
2198     case WAITING_FOR_DECL_KEYWORD:
2199       if( isalpha(x[0]) ){
2200         psp->declkeyword = x;
2201         psp->declargslot = 0;
2202         psp->decllnslot = 0;
2203         psp->state = WAITING_FOR_DECL_ARG;
2204         if( strcmp(x,"name")==0 ){
2205           psp->declargslot = &(psp->gp->name);
2206         }else if( strcmp(x,"include")==0 ){
2207           psp->declargslot = &(psp->gp->include);
2208           psp->decllnslot = &psp->gp->includeln;
2209         }else if( strcmp(x,"code")==0 ){
2210           psp->declargslot = &(psp->gp->extracode);
2211           psp->decllnslot = &psp->gp->extracodeln;
2212         }else if( strcmp(x,"token_destructor")==0 ){
2213           psp->declargslot = &psp->gp->tokendest;
2214           psp->decllnslot = &psp->gp->tokendestln;
2215         }else if( strcmp(x,"default_destructor")==0 ){
2216           psp->declargslot = &psp->gp->vardest;
2217           psp->decllnslot = &psp->gp->vardestln;
2218         }else if( strcmp(x,"token_prefix")==0 ){
2219           psp->declargslot = &psp->gp->tokenprefix;
2220         }else if( strcmp(x,"syntax_error")==0 ){
2221           psp->declargslot = &(psp->gp->error);
2222           psp->decllnslot = &psp->gp->errorln;
2223         }else if( strcmp(x,"parse_accept")==0 ){
2224           psp->declargslot = &(psp->gp->accept);
2225           psp->decllnslot = &psp->gp->acceptln;
2226         }else if( strcmp(x,"parse_failure")==0 ){
2227           psp->declargslot = &(psp->gp->failure);
2228           psp->decllnslot = &psp->gp->failureln;
2229         }else if( strcmp(x,"stack_overflow")==0 ){
2230           psp->declargslot = &(psp->gp->overflow);
2231           psp->decllnslot = &psp->gp->overflowln;
2232         }else if( strcmp(x,"extra_argument")==0 ){
2233           psp->declargslot = &(psp->gp->arg);
2234         }else if( strcmp(x,"token_type")==0 ){
2235           psp->declargslot = &(psp->gp->tokentype);
2236         }else if( strcmp(x,"default_type")==0 ){
2237           psp->declargslot = &(psp->gp->vartype);
2238         }else if( strcmp(x,"stack_size")==0 ){
2239           psp->declargslot = &(psp->gp->stacksize);
2240         }else if( strcmp(x,"start_symbol")==0 ){
2241           psp->declargslot = &(psp->gp->start);
2242         }else if( strcmp(x,"left")==0 ){
2243           psp->preccounter++;
2244           psp->declassoc = LEFT;
2245           psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2246         }else if( strcmp(x,"right")==0 ){
2247           psp->preccounter++;
2248           psp->declassoc = RIGHT;
2249           psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2250         }else if( strcmp(x,"nonassoc")==0 ){
2251           psp->preccounter++;
2252           psp->declassoc = NONE;
2253           psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2254         }else if( strcmp(x,"destructor")==0 ){
2255           psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;
2256         }else if( strcmp(x,"type")==0 ){
2257           psp->state = WAITING_FOR_DATATYPE_SYMBOL;
2258         }else if( strcmp(x,"fallback")==0 ){
2259           psp->fallback = 0;
2260           psp->state = WAITING_FOR_FALLBACK_ID;
2261         }else if( strcmp(x,"wildcard")==0 ){
2262           psp->state = WAITING_FOR_WILDCARD_ID;
2263         }else{
2264           ErrorMsg(psp->filename,psp->tokenlineno,
2265             "Unknown declaration keyword: \"%%%s\".",x);
2266           psp->errorcnt++;
2267           psp->state = RESYNC_AFTER_DECL_ERROR;
2268         }
2269       }else{
2270         ErrorMsg(psp->filename,psp->tokenlineno,
2271           "Illegal declaration keyword: \"%s\".",x);
2272         psp->errorcnt++;
2273         psp->state = RESYNC_AFTER_DECL_ERROR;
2274       }
2275       break;
2276     case WAITING_FOR_DESTRUCTOR_SYMBOL:
2277       if( !isalpha(x[0]) ){
2278         ErrorMsg(psp->filename,psp->tokenlineno,
2279           "Symbol name missing after %destructor keyword");
2280         psp->errorcnt++;
2281         psp->state = RESYNC_AFTER_DECL_ERROR;
2282       }else{
2283         struct symbol *sp = Symbol_new(x);
2284         psp->declargslot = &sp->destructor;
2285         psp->decllnslot = &sp->destructorln;
2286         psp->state = WAITING_FOR_DECL_ARG;
2287       }
2288       break;
2289     case WAITING_FOR_DATATYPE_SYMBOL:
2290       if( !isalpha(x[0]) ){
2291         ErrorMsg(psp->filename,psp->tokenlineno,
2292           "Symbol name missing after %destructor keyword");
2293         psp->errorcnt++;
2294         psp->state = RESYNC_AFTER_DECL_ERROR;
2295       }else{
2296         struct symbol *sp = Symbol_new(x);
2297         psp->declargslot = &sp->datatype;
2298         psp->decllnslot = 0;
2299         psp->state = WAITING_FOR_DECL_ARG;
2300       }
2301       break;
2302     case WAITING_FOR_PRECEDENCE_SYMBOL:
2303       if( x[0]=='.' ){
2304         psp->state = WAITING_FOR_DECL_OR_RULE;
2305       }else if( isupper(x[0]) ){
2306         struct symbol *sp;
2307         sp = Symbol_new(x);
2308         if( sp->prec>=0 ){
2309           ErrorMsg(psp->filename,psp->tokenlineno,
2310             "Symbol \"%s\" has already be given a precedence.",x);
2311           psp->errorcnt++;
2312         }else{
2313           sp->prec = psp->preccounter;
2314           sp->assoc = psp->declassoc;
2315         }
2316       }else{
2317         ErrorMsg(psp->filename,psp->tokenlineno,
2318           "Can't assign a precedence to \"%s\".",x);
2319         psp->errorcnt++;
2320       }
2321       break;
2322     case WAITING_FOR_DECL_ARG:
2323       if( (x[0]=='{' || x[0]=='\"' || isalnum(x[0])) ){
2324         if( *(psp->declargslot)!=0 ){
2325           ErrorMsg(psp->filename,psp->tokenlineno,
2326             "The argument \"%s\" to declaration \"%%%s\" is not the first.",
2327             x[0]=='\"' ? &x[1] : x,psp->declkeyword);
2328           psp->errorcnt++;
2329           psp->state = RESYNC_AFTER_DECL_ERROR;
2330         }else{
2331           *(psp->declargslot) = (x[0]=='\"' || x[0]=='{') ? &x[1] : x;
2332           if( psp->decllnslot ) *psp->decllnslot = psp->tokenlineno;
2333           psp->state = WAITING_FOR_DECL_OR_RULE;
2334         }
2335       }else{
2336         ErrorMsg(psp->filename,psp->tokenlineno,
2337           "Illegal argument to %%%s: %s",psp->declkeyword,x);
2338         psp->errorcnt++;
2339         psp->state = RESYNC_AFTER_DECL_ERROR;
2340       }
2341       break;
2342     case WAITING_FOR_FALLBACK_ID:
2343       if( x[0]=='.' ){
2344         psp->state = WAITING_FOR_DECL_OR_RULE;
2345       }else if( !isupper(x[0]) ){
2346         ErrorMsg(psp->filename, psp->tokenlineno,
2347           "%%fallback argument \"%s\" should be a token", x);
2348         psp->errorcnt++;
2349       }else{
2350         struct symbol *sp = Symbol_new(x);
2351         if( psp->fallback==0 ){
2352           psp->fallback = sp;
2353         }else if( sp->fallback ){
2354           ErrorMsg(psp->filename, psp->tokenlineno,
2355             "More than one fallback assigned to token %s", x);
2356           psp->errorcnt++;
2357         }else{
2358           sp->fallback = psp->fallback;
2359           psp->gp->has_fallback = 1;
2360         }
2361       }
2362       break;
2363     case WAITING_FOR_WILDCARD_ID:
2364       if( x[0]=='.' ){
2365         psp->state = WAITING_FOR_DECL_OR_RULE;
2366       }else if( !isupper(x[0]) ){
2367         ErrorMsg(psp->filename, psp->tokenlineno,
2368           "%%wildcard argument \"%s\" should be a token", x);
2369         psp->errorcnt++;
2370       }else{
2371         struct symbol *sp = Symbol_new(x);
2372         if( psp->gp->wildcard==0 ){
2373           psp->gp->wildcard = sp;
2374         }else{
2375           ErrorMsg(psp->filename, psp->tokenlineno,
2376             "Extra wildcard to token: %s", x);
2377           psp->errorcnt++;
2378         }
2379       }
2380       break;
2381     case RESYNC_AFTER_RULE_ERROR:
2382 /*      if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2383 **      break; */
2384     case RESYNC_AFTER_DECL_ERROR:
2385       if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2386       if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;
2387       break;
2388   }
2389 }
2390
2391 /* Run the proprocessor over the input file text.  The global variables
2392 ** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2393 ** macros.  This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2394 ** comments them out.  Text in between is also commented out as appropriate.
2395 */
2396 static void preprocess_input(char *z){
2397   int i, j, k, n;
2398   int exclude = 0;
2399   int start;
2400   int lineno = 1;
2401   int start_lineno;
2402   for(i=0; z[i]; i++){
2403     if( z[i]=='\n' ) lineno++;
2404     if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue;
2405     if( strncmp(&z[i],"%endif",6)==0 && isspace(z[i+6]) ){
2406       if( exclude ){
2407         exclude--;
2408         if( exclude==0 ){
2409           for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';
2410         }
2411       }
2412       for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2413     }else if( (strncmp(&z[i],"%ifdef",6)==0 && isspace(z[i+6]))
2414           || (strncmp(&z[i],"%ifndef",7)==0 && isspace(z[i+7])) ){
2415       if( exclude ){
2416         exclude++;
2417       }else{
2418         for(j=i+7; isspace(z[j]); j++){}
2419         for(n=0; z[j+n] && !isspace(z[j+n]); n++){}
2420         exclude = 1;
2421         for(k=0; k<nDefine; k++){
2422           if( strncmp(azDefine[k],&z[j],n)==0 && strlen(azDefine[k])==n ){
2423             exclude = 0;
2424             break;
2425           }
2426         }
2427         if( z[i+3]=='n' ) exclude = !exclude;
2428         if( exclude ){
2429           start = i;
2430           start_lineno = lineno;
2431         }
2432       }
2433       for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2434     }
2435   }
2436   if( exclude ){
2437     fprintf(stderr,"unterminated %%ifdef starting on line %d\n", start_lineno);
2438     exit(1);
2439   }
2440 }
2441
2442 /* In spite of its name, this function is really a scanner.  It read
2443 ** in the entire input file (all at once) then tokenizes it.  Each
2444 ** token is passed to the function "parseonetoken" which builds all
2445 ** the appropriate data structures in the global state vector "gp".
2446 */
2447 void Parse(gp)
2448 struct lemon *gp;
2449 {
2450   struct pstate ps;
2451   FILE *fp;
2452   char *filebuf;
2453   int filesize;
2454   int lineno;
2455   int c;
2456   char *cp, *nextcp;
2457   int startline = 0;
2458
2459   ps.gp = gp;
2460   ps.filename = gp->filename;
2461   ps.errorcnt = 0;
2462   ps.state = INITIALIZE;
2463
2464   /* Begin by reading the input file */
2465   fp = fopen(ps.filename,"rb");
2466   if( fp==0 ){
2467     ErrorMsg(ps.filename,0,"Can't open this file for reading.");
2468     gp->errorcnt++;
2469     return;
2470   }
2471   fseek(fp,0,2);
2472   filesize = ftell(fp);
2473   rewind(fp);
2474   filebuf = (char *)malloc( filesize+1 );
2475   if( filebuf==0 ){
2476     ErrorMsg(ps.filename,0,"Can't allocate %d of memory to hold this file.",
2477       filesize+1);
2478     gp->errorcnt++;
2479     return;
2480   }
2481   if( fread(filebuf,1,filesize,fp)!=filesize ){
2482     ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",
2483       filesize);
2484     free(filebuf);
2485     gp->errorcnt++;
2486     return;
2487   }
2488   fclose(fp);
2489   filebuf[filesize] = 0;
2490
2491   /* Make an initial pass through the file to handle %ifdef and %ifndef */
2492   preprocess_input(filebuf);
2493
2494   /* Now scan the text of the input file */
2495   lineno = 1;
2496   for(cp=filebuf; (c= *cp)!=0; ){
2497     if( c=='\n' ) lineno++;              /* Keep track of the line number */
2498     if( isspace(c) ){ cp++; continue; }  /* Skip all white space */
2499     if( c=='/' && cp[1]=='/' ){          /* Skip C++ style comments */
2500       cp+=2;
2501       while( (c= *cp)!=0 && c!='\n' ) cp++;
2502       continue;
2503     }
2504     if( c=='/' && cp[1]=='*' ){          /* Skip C style comments */
2505       cp+=2;
2506       while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){
2507         if( c=='\n' ) lineno++;
2508         cp++;
2509       }
2510       if( c ) cp++;
2511       continue;
2512     }
2513     ps.tokenstart = cp;                /* Mark the beginning of the token */
2514     ps.tokenlineno = lineno;           /* Linenumber on which token begins */
2515     if( c=='\"' ){                     /* String literals */
2516       cp++;
2517       while( (c= *cp)!=0 && c!='\"' ){
2518         if( c=='\n' ) lineno++;
2519         cp++;
2520       }
2521       if( c==0 ){
2522         ErrorMsg(ps.filename,startline,
2523 "String starting on this line is not terminated before the end of the file.");
2524         ps.errorcnt++;
2525         nextcp = cp;
2526       }else{
2527         nextcp = cp+1;
2528       }
2529     }else if( c=='{' ){               /* A block of C code */
2530       int level;
2531       cp++;
2532       for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){
2533         if( c=='\n' ) lineno++;
2534         else if( c=='{' ) level++;
2535         else if( c=='}' ) level--;
2536         else if( c=='/' && cp[1]=='*' ){  /* Skip comments */
2537           int prevc;
2538           cp = &cp[2];
2539           prevc = 0;
2540           while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){
2541             if( c=='\n' ) lineno++;
2542             prevc = c;
2543             cp++;
2544           }
2545         }else if( c=='/' && cp[1]=='/' ){  /* Skip C++ style comments too */
2546           cp = &cp[2];
2547           while( (c= *cp)!=0 && c!='\n' ) cp++;
2548           if( c ) lineno++;
2549         }else if( c=='\'' || c=='\"' ){    /* String a character literals */
2550           int startchar, prevc;
2551           startchar = c;
2552           prevc = 0;
2553           for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){
2554             if( c=='\n' ) lineno++;
2555             if( prevc=='\\' ) prevc = 0;
2556             else              prevc = c;
2557           }
2558         }
2559       }
2560       if( c==0 ){
2561         ErrorMsg(ps.filename,ps.tokenlineno,
2562 "C code starting on this line is not terminated before the end of the file.");
2563         ps.errorcnt++;
2564         nextcp = cp;
2565       }else{
2566         nextcp = cp+1;
2567       }
2568     }else if( isalnum(c) ){          /* Identifiers */
2569       while( (c= *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2570       nextcp = cp;
2571     }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */
2572       cp += 3;
2573       nextcp = cp;
2574     }else if( (c=='/' || c=='|') && isalpha(cp[1]) ){
2575       cp += 2;
2576       while( (c = *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2577       nextcp = cp;
2578     }else{                          /* All other (one character) operators */
2579       cp++;
2580       nextcp = cp;
2581     }
2582     c = *cp;
2583     *cp = 0;                        /* Null terminate the token */
2584     parseonetoken(&ps);             /* Parse the token */
2585     *cp = c;                        /* Restore the buffer */
2586     cp = nextcp;
2587   }
2588   free(filebuf);                    /* Release the buffer after parsing */
2589   gp->rule = ps.firstrule;
2590   gp->errorcnt = ps.errorcnt;
2591 }
2592 /*************************** From the file "plink.c" *********************/
2593 /*
2594 ** Routines processing configuration follow-set propagation links
2595 ** in the LEMON parser generator.
2596 */
2597 static struct plink *plink_freelist = 0;
2598
2599 /* Allocate a new plink */
2600 struct plink *Plink_new(){
2601   struct plink *new;
2602
2603   if( plink_freelist==0 ){
2604     int i;
2605     int amt = 100;
2606     plink_freelist = (struct plink *)malloc( sizeof(struct plink)*amt );
2607     if( plink_freelist==0 ){
2608       fprintf(stderr,
2609       "Unable to allocate memory for a new follow-set propagation link.\n");
2610       exit(1);
2611     }
2612     for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
2613     plink_freelist[amt-1].next = 0;
2614   }
2615   new = plink_freelist;
2616   plink_freelist = plink_freelist->next;
2617   return new;
2618 }
2619
2620 /* Add a plink to a plink list */
2621 void Plink_add(plpp,cfp)
2622 struct plink **plpp;
2623 struct config *cfp;
2624 {
2625   struct plink *new;
2626   new = Plink_new();
2627   new->next = *plpp;
2628   *plpp = new;
2629   new->cfp = cfp;
2630 }
2631
2632 /* Transfer every plink on the list "from" to the list "to" */
2633 void Plink_copy(to,from)
2634 struct plink **to;
2635 struct plink *from;
2636 {
2637   struct plink *nextpl;
2638   while( from ){
2639     nextpl = from->next;
2640     from->next = *to;
2641     *to = from;
2642     from = nextpl;
2643   }
2644 }
2645
2646 /* Delete every plink on the list */
2647 void Plink_delete(plp)
2648 struct plink *plp;
2649 {
2650   struct plink *nextpl;
2651
2652   while( plp ){
2653     nextpl = plp->next;
2654     plp->next = plink_freelist;
2655     plink_freelist = plp;
2656     plp = nextpl;
2657   }
2658 }
2659 /*********************** From the file "report.c" **************************/
2660 /*
2661 ** Procedures for generating reports and tables in the LEMON parser generator.
2662 */
2663
2664 /* Generate a filename with the given suffix.  Space to hold the
2665 ** name comes from malloc() and must be freed by the calling
2666 ** function.
2667 */
2668 PRIVATE char *file_makename(lemp,suffix)
2669 struct lemon *lemp;
2670 char *suffix;
2671 {
2672   char *name;
2673   char *cp;
2674
2675   name = malloc( strlen(lemp->filename) + strlen(suffix) + 5 );
2676   if( name==0 ){
2677     fprintf(stderr,"Can't allocate space for a filename.\n");
2678     exit(1);
2679   }
2680   strcpy(name,lemp->filename);
2681   cp = strrchr(name,'.');
2682   if( cp ) *cp = 0;
2683   strcat(name,suffix);
2684   return name;
2685 }
2686
2687 /* Open a file with a name based on the name of the input file,
2688 ** but with a different (specified) suffix, and return a pointer
2689 ** to the stream */
2690 PRIVATE FILE *file_open(lemp,suffix,mode)
2691 struct lemon *lemp;
2692 char *suffix;
2693 char *mode;
2694 {
2695   FILE *fp;
2696
2697   if( lemp->outname ) free(lemp->outname);
2698   lemp->outname = file_makename(lemp, suffix);
2699   fp = fopen(lemp->outname,mode);
2700   if( fp==0 && *mode=='w' ){
2701     fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
2702     lemp->errorcnt++;
2703     return 0;
2704   }
2705   return fp;
2706 }
2707
2708 /* Duplicate the input file without comments and without actions
2709 ** on rules */
2710 void Reprint(lemp)
2711 struct lemon *lemp;
2712 {
2713   struct rule *rp;
2714   struct symbol *sp;
2715   int i, j, maxlen, len, ncolumns, skip;
2716   printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
2717   maxlen = 10;
2718   for(i=0; i<lemp->nsymbol; i++){
2719     sp = lemp->symbols[i];
2720     len = strlen(sp->name);
2721     if( len>maxlen ) maxlen = len;
2722   }
2723   ncolumns = 76/(maxlen+5);
2724   if( ncolumns<1 ) ncolumns = 1;
2725   skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
2726   for(i=0; i<skip; i++){
2727     printf("//");
2728     for(j=i; j<lemp->nsymbol; j+=skip){
2729       sp = lemp->symbols[j];
2730       assert( sp->index==j );
2731       printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
2732     }
2733     printf("\n");
2734   }
2735   for(rp=lemp->rule; rp; rp=rp->next){
2736     printf("%s",rp->lhs->name);
2737     /*    if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
2738     printf(" ::=");
2739     for(i=0; i<rp->nrhs; i++){
2740       sp = rp->rhs[i];
2741       printf(" %s", sp->name);
2742       if( sp->type==MULTITERMINAL ){
2743         for(j=1; j<sp->nsubsym; j++){
2744           printf("|%s", sp->subsym[j]->name);
2745         }
2746       }
2747       /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
2748     }
2749     printf(".");
2750     if( rp->precsym ) printf(" [%s]",rp->precsym->name);
2751     /* if( rp->code ) printf("\n    %s",rp->code); */
2752     printf("\n");
2753   }
2754 }
2755
2756 void ConfigPrint(fp,cfp)
2757 FILE *fp;
2758 struct config *cfp;
2759 {
2760   struct rule *rp;
2761   struct symbol *sp;
2762   int i, j;
2763   rp = cfp->rp;
2764   fprintf(fp,"%s ::=",rp->lhs->name);
2765   for(i=0; i<=rp->nrhs; i++){
2766     if( i==cfp->dot ) fprintf(fp," *");
2767     if( i==rp->nrhs ) break;
2768     sp = rp->rhs[i];
2769     fprintf(fp," %s", sp->name);
2770     if( sp->type==MULTITERMINAL ){
2771       for(j=1; j<sp->nsubsym; j++){
2772         fprintf(fp,"|%s",sp->subsym[j]->name);
2773       }
2774     }
2775   }
2776 }
2777
2778 /* #define TEST */
2779 #if 0
2780 /* Print a set */
2781 PRIVATE void SetPrint(out,set,lemp)
2782 FILE *out;
2783 char *set;
2784 struct lemon *lemp;
2785 {
2786   int i;
2787   char *spacer;
2788   spacer = "";
2789   fprintf(out,"%12s[","");
2790   for(i=0; i<lemp->nterminal; i++){
2791     if( SetFind(set,i) ){
2792       fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
2793       spacer = " ";
2794     }
2795   }
2796   fprintf(out,"]\n");
2797 }
2798
2799 /* Print a plink chain */
2800 PRIVATE void PlinkPrint(out,plp,tag)
2801 FILE *out;
2802 struct plink *plp;
2803 char *tag;
2804 {
2805   while( plp ){
2806     fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->statenum);
2807     ConfigPrint(out,plp->cfp);
2808     fprintf(out,"\n");
2809     plp = plp->next;
2810   }
2811 }
2812 #endif
2813
2814 /* Print an action to the given file descriptor.  Return FALSE if
2815 ** nothing was actually printed.
2816 */
2817 int PrintAction(struct action *ap, FILE *fp, int indent){
2818   int result = 1;
2819   switch( ap->type ){
2820     case SHIFT:
2821       fprintf(fp,"%*s shift  %d",indent,ap->sp->name,ap->x.stp->statenum);
2822       break;
2823     case REDUCE:
2824       fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
2825       break;
2826     case ACCEPT:
2827       fprintf(fp,"%*s accept",indent,ap->sp->name);
2828       break;
2829     case ERROR:
2830       fprintf(fp,"%*s error",indent,ap->sp->name);
2831       break;
2832     case CONFLICT:
2833       fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
2834         indent,ap->sp->name,ap->x.rp->index);
2835       break;
2836     case SH_RESOLVED:
2837     case RD_RESOLVED:
2838     case NOT_USED:
2839       result = 0;
2840       break;
2841   }
2842   return result;
2843 }
2844
2845 /* Generate the "y.output" log file */
2846 void ReportOutput(lemp)
2847 struct lemon *lemp;
2848 {
2849   int i;
2850   struct state *stp;
2851   struct config *cfp;
2852   struct action *ap;
2853   FILE *fp;
2854
2855   fp = file_open(lemp,".out","wb");
2856   if( fp==0 ) return;
2857   fprintf(fp," \b");
2858   for(i=0; i<lemp->nstate; i++){
2859     stp = lemp->sorted[i];
2860     fprintf(fp,"State %d:\n",stp->statenum);
2861     if( lemp->basisflag ) cfp=stp->bp;
2862     else                  cfp=stp->cfp;
2863     while( cfp ){
2864       char buf[20];
2865       if( cfp->dot==cfp->rp->nrhs ){
2866         sprintf(buf,"(%d)",cfp->rp->index);
2867         fprintf(fp,"    %5s ",buf);
2868       }else{
2869         fprintf(fp,"          ");
2870       }
2871       ConfigPrint(fp,cfp);
2872       fprintf(fp,"\n");
2873 #if 0
2874       SetPrint(fp,cfp->fws,lemp);
2875       PlinkPrint(fp,cfp->fplp,"To  ");
2876       PlinkPrint(fp,cfp->bplp,"From");
2877 #endif
2878       if( lemp->basisflag ) cfp=cfp->bp;
2879       else                  cfp=cfp->next;
2880     }
2881     fprintf(fp,"\n");
2882     for(ap=stp->ap; ap; ap=ap->next){
2883       if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
2884     }
2885     fprintf(fp,"\n");
2886   }
2887   fclose(fp);
2888   return;
2889 }
2890
2891 /* Search for the file "name" which is in the same directory as
2892 ** the exacutable */
2893 PRIVATE char *pathsearch(argv0,name,modemask)
2894 char *argv0;
2895 char *name;
2896 int modemask;
2897 {
2898   char *pathlist;
2899   char *path,*cp;
2900   char c;
2901   extern int access();
2902
2903 #ifdef __WIN32__
2904   cp = strrchr(argv0,'\\');
2905 #else
2906   cp = strrchr(argv0,'/');
2907 #endif
2908   if( cp ){
2909     c = *cp;
2910     *cp = 0;
2911     path = (char *)malloc( strlen(argv0) + strlen(name) + 2 );
2912     if( path ) sprintf(path,"%s/%s",argv0,name);
2913     *cp = c;
2914   }else{
2915     extern char *getenv();
2916     pathlist = getenv("PATH");
2917     if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
2918     path = (char *)malloc( strlen(pathlist)+strlen(name)+2 );
2919     if( path!=0 ){
2920       while( *pathlist ){
2921         cp = strchr(pathlist,':');
2922         if( cp==0 ) cp = &pathlist[strlen(pathlist)];
2923         c = *cp;
2924         *cp = 0;
2925         sprintf(path,"%s/%s",pathlist,name);
2926         *cp = c;
2927         if( c==0 ) pathlist = "";
2928         else pathlist = &cp[1];
2929         if( access(path,modemask)==0 ) break;
2930       }
2931     }
2932   }
2933   return path;
2934 }
2935
2936 /* Given an action, compute the integer value for that action
2937 ** which is to be put in the action table of the generated machine.
2938 ** Return negative if no action should be generated.
2939 */
2940 PRIVATE int compute_action(lemp,ap)
2941 struct lemon *lemp;
2942 struct action *ap;
2943 {
2944   int act;
2945   switch( ap->type ){
2946     case SHIFT:  act = ap->x.stp->statenum;            break;
2947     case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
2948     case ERROR:  act = lemp->nstate + lemp->nrule;     break;
2949     case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break;
2950     default:     act = -1; break;
2951   }
2952   return act;
2953 }
2954
2955 #define LINESIZE 1000
2956 /* The next cluster of routines are for reading the template file
2957 ** and writing the results to the generated parser */
2958 /* The first function transfers data from "in" to "out" until
2959 ** a line is seen which begins with "%%".  The line number is
2960 ** tracked.
2961 **
2962 ** if name!=0, then any word that begin with "Parse" is changed to
2963 ** begin with *name instead.
2964 */
2965 PRIVATE void tplt_xfer(name,in,out,lineno)
2966 char *name;
2967 FILE *in;
2968 FILE *out;
2969 int *lineno;
2970 {
2971   int i, iStart;
2972   char line[LINESIZE];
2973   while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
2974     (*lineno)++;
2975     iStart = 0;
2976     if( name ){
2977       for(i=0; line[i]; i++){
2978         if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0
2979           && (i==0 || !isalpha(line[i-1]))
2980         ){
2981           if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);
2982           fprintf(out,"%s",name);
2983           i += 4;
2984           iStart = i+1;
2985         }
2986       }
2987     }
2988     fprintf(out,"%s",&line[iStart]);
2989   }
2990 }
2991
2992 /* The next function finds the template file and opens it, returning
2993 ** a pointer to the opened file. */
2994 PRIVATE FILE *tplt_open(lemp)
2995 struct lemon *lemp;
2996 {
2997   static char templatename[] = "lempar.c";
2998   char buf[1000];
2999   FILE *in;
3000   char *tpltname;
3001   char *cp;
3002
3003   cp = strrchr(lemp->filename,'.');
3004   if( cp ){
3005     sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
3006   }else{
3007     sprintf(buf,"%s.lt",lemp->filename);
3008   }
3009   if( access(buf,004)==0 ){
3010     tpltname = buf;
3011   }else if( access(templatename,004)==0 ){
3012     tpltname = templatename;
3013   }else{
3014     tpltname = pathsearch(lemp->argv0,templatename,0);
3015   }
3016   if( tpltname==0 ){
3017     fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3018     templatename);
3019     lemp->errorcnt++;
3020     return 0;
3021   }
3022   in = fopen(tpltname,"rb");
3023   if( in==0 ){
3024     fprintf(stderr,"Can't open the template file \"%s\".\n",templatename);
3025     lemp->errorcnt++;
3026     return 0;
3027   }
3028   return in;
3029 }
3030
3031 /* Print a #line directive line to the output file. */
3032 PRIVATE void tplt_linedir(out,lineno,filename)
3033 FILE *out;
3034 int lineno;
3035 char *filename;
3036 {
3037   fprintf(out,"#line %d \"",lineno);
3038   while( *filename ){
3039     if( *filename == '\\' ) putc('\\',out);
3040     putc(*filename,out);
3041     filename++;
3042   }
3043   fprintf(out,"\"\n");
3044 }
3045
3046 /* Print a string to the file and keep the linenumber up to date */
3047 PRIVATE void tplt_print(out,lemp,str,strln,lineno)
3048 FILE *out;
3049 struct lemon *lemp;
3050 char *str;
3051 int strln;
3052 int *lineno;
3053 {
3054   if( str==0 ) return;
3055   tplt_linedir(out,strln,lemp->filename);
3056   (*lineno)++;
3057   while( *str ){
3058     if( *str=='\n' ) (*lineno)++;
3059     putc(*str,out);
3060     str++;
3061   }
3062   if( str[-1]!='\n' ){
3063     putc('\n',out);
3064     (*lineno)++;
3065   }
3066   tplt_linedir(out,*lineno+2,lemp->outname);
3067   (*lineno)+=2;
3068   return;
3069 }
3070
3071 /*
3072 ** The following routine emits code for the destructor for the
3073 ** symbol sp
3074 */
3075 void emit_destructor_code(out,sp,lemp,lineno)
3076 FILE *out;
3077 struct symbol *sp;
3078 struct lemon *lemp;
3079 int *lineno;
3080 {
3081  char *cp = 0;
3082
3083  int linecnt = 0;
3084  if( sp->type==TERMINAL ){
3085    cp = lemp->tokendest;
3086    if( cp==0 ) return;
3087    tplt_linedir(out,lemp->tokendestln,lemp->filename);
3088    fprintf(out,"{");
3089  }else if( sp->destructor ){
3090    cp = sp->destructor;
3091    tplt_linedir(out,sp->destructorln,lemp->filename);
3092    fprintf(out,"{");
3093  }else if( lemp->vardest ){
3094    cp = lemp->vardest;
3095    if( cp==0 ) return;
3096    tplt_linedir(out,lemp->vardestln,lemp->filename);
3097    fprintf(out,"{");
3098  }else{
3099    assert( 0 );  /* Cannot happen */
3100  }
3101  for(; *cp; cp++){
3102    if( *cp=='$' && cp[1]=='$' ){
3103      fprintf(out,"(yypminor->yy%d)",sp->dtnum);
3104      cp++;
3105      continue;
3106    }
3107    if( *cp=='\n' ) linecnt++;
3108    fputc(*cp,out);
3109  }
3110  (*lineno) += 3 + linecnt;
3111  fprintf(out,"}\n");
3112  tplt_linedir(out,*lineno,lemp->outname);
3113  return;
3114 }
3115
3116 /*
3117 ** Return TRUE (non-zero) if the given symbol has a destructor.
3118 */
3119 int has_destructor(sp, lemp)
3120 struct symbol *sp;
3121 struct lemon *lemp;
3122 {
3123   int ret;
3124   if( sp->type==TERMINAL ){
3125     ret = lemp->tokendest!=0;
3126   }else{
3127     ret = lemp->vardest!=0 || sp->destructor!=0;
3128   }
3129   return ret;
3130 }
3131
3132 /*
3133 ** Append text to a dynamically allocated string.  If zText is 0 then
3134 ** reset the string to be empty again.  Always return the complete text
3135 ** of the string (which is overwritten with each call).
3136 **
3137 ** n bytes of zText are stored.  If n==0 then all of zText up to the first
3138 ** \000 terminator is stored.  zText can contain up to two instances of
3139 ** %d.  The values of p1 and p2 are written into the first and second
3140 ** %d.
3141 **
3142 ** If n==-1, then the previous character is overwritten.
3143 */
3144 PRIVATE char *append_str(char *zText, int n, int p1, int p2){
3145   static char *z = 0;
3146   static int alloced = 0;
3147   static int used = 0;
3148   int c;
3149   char zInt[40];
3150
3151   if( zText==0 ){
3152     used = 0;
3153     return z;
3154   }
3155   if( n<=0 ){
3156     if( n<0 ){
3157       used += n;
3158       assert( used>=0 );
3159     }
3160     n = strlen(zText);
3161   }
3162   if( n+sizeof(zInt)*2+used >= alloced ){
3163     alloced = n + sizeof(zInt)*2 + used + 200;
3164     z = realloc(z,  alloced);
3165   }
3166   if( z==0 ) return "";
3167   while( n-- > 0 ){
3168     c = *(zText++);
3169     if( c=='%' && zText[0]=='d' ){
3170       sprintf(zInt, "%d", p1);
3171       p1 = p2;
3172       strcpy(&z[used], zInt);
3173       used += strlen(&z[used]);
3174       zText++;
3175       n--;
3176     }else{
3177       z[used++] = c;
3178     }
3179   }
3180   z[used] = 0;
3181   return z;
3182 }
3183
3184 /*
3185 ** zCode is a string that is the action associated with a rule.  Expand
3186 ** the symbols in this string so that the refer to elements of the parser
3187 ** stack.
3188 */
3189 PRIVATE void translate_code(struct lemon *lemp, struct rule *rp){
3190   char *cp, *xp;
3191   int i;
3192   char lhsused = 0;    /* True if the LHS element has been used */
3193   char used[MAXRHS];   /* True for each RHS element which is used */
3194
3195   for(i=0; i<rp->nrhs; i++) used[i] = 0;
3196   lhsused = 0;
3197
3198   append_str(0,0,0,0);
3199   for(cp=rp->code; *cp; cp++){
3200     if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
3201       char saved;
3202       for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
3203       saved = *xp;
3204       *xp = 0;
3205       if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
3206         append_str("yygotominor.yy%d",0,rp->lhs->dtnum,0);
3207         cp = xp;
3208         lhsused = 1;
3209       }else{
3210         for(i=0; i<rp->nrhs; i++){
3211           if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
3212             if( cp!=rp->code && cp[-1]=='@' ){
3213               /* If the argument is of the form @X then substituted
3214               ** the token number of X, not the value of X */
3215               append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);
3216             }else{
3217               struct symbol *sp = rp->rhs[i];
3218               int dtnum;
3219               if( sp->type==MULTITERMINAL ){
3220                 dtnum = sp->subsym[0]->dtnum;
3221               }else{
3222                 dtnum = sp->dtnum;
3223               }
3224               append_str("yymsp[%d].minor.yy%d",0,i-rp->nrhs+1, dtnum);
3225             }
3226             cp = xp;
3227             used[i] = 1;
3228             break;
3229           }
3230         }
3231       }
3232       *xp = saved;
3233     }
3234     append_str(cp, 1, 0, 0);
3235   } /* End loop */
3236
3237   /* Check to make sure the LHS has been used */
3238   if( rp->lhsalias && !lhsused ){
3239     ErrorMsg(lemp->filename,rp->ruleline,
3240       "Label \"%s\" for \"%s(%s)\" is never used.",
3241         rp->lhsalias,rp->lhs->name,rp->lhsalias);
3242     lemp->errorcnt++;
3243   }
3244
3245   /* Generate destructor code for RHS symbols which are not used in the
3246   ** reduce code */
3247   for(i=0; i<rp->nrhs; i++){
3248     if( rp->rhsalias[i] && !used[i] ){
3249       ErrorMsg(lemp->filename,rp->ruleline,
3250         "Label %s for \"%s(%s)\" is never used.",
3251         rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
3252       lemp->errorcnt++;
3253     }else if( rp->rhsalias[i]==0 ){
3254       if( has_destructor(rp->rhs[i],lemp) ){
3255         append_str("  yy_destructor(%d,&yymsp[%d].minor);\n", 0,
3256            rp->rhs[i]->index,i-rp->nrhs+1);
3257       }else{
3258         /* No destructor defined for this term */
3259       }
3260     }
3261   }
3262   cp = append_str(0,0,0,0);
3263   rp->code = Strsafe(cp);
3264 }
3265
3266 /*
3267 ** Generate code which executes when the rule "rp" is reduced.  Write
3268 ** the code to "out".  Make sure lineno stays up-to-date.
3269 */
3270 PRIVATE void emit_code(out,rp,lemp,lineno)
3271 FILE *out;
3272 struct rule *rp;
3273 struct lemon *lemp;
3274 int *lineno;
3275 {
3276  char *cp;
3277  int linecnt = 0;
3278
3279  /* Generate code to do the reduce action */
3280  if( rp->code ){
3281    tplt_linedir(out,rp->line,lemp->filename);
3282    fprintf(out,"{%s",rp->code);
3283    for(cp=rp->code; *cp; cp++){
3284      if( *cp=='\n' ) linecnt++;
3285    } /* End loop */
3286    (*lineno) += 3 + linecnt;
3287    fprintf(out,"}\n");
3288    tplt_linedir(out,*lineno,lemp->outname);
3289  } /* End if( rp->code ) */
3290
3291  return;
3292 }
3293
3294 /*
3295 ** Print the definition of the union used for the parser's data stack.
3296 ** This union contains fields for every possible data type for tokens
3297 ** and nonterminals.  In the process of computing and printing this
3298 ** union, also set the ".dtnum" field of every terminal and nonterminal
3299 ** symbol.
3300 */
3301 void print_stack_union(out,lemp,plineno,mhflag)
3302 FILE *out;                  /* The output stream */
3303 struct lemon *lemp;         /* The main info structure for this parser */
3304 int *plineno;               /* Pointer to the line number */
3305 int mhflag;                 /* True if generating makeheaders output */
3306 {
3307   int lineno = *plineno;    /* The line number of the output */
3308   char **types;             /* A hash table of datatypes */
3309   int arraysize;            /* Size of the "types" array */
3310   int maxdtlength;          /* Maximum length of any ".datatype" field. */
3311   char *stddt;              /* Standardized name for a datatype */
3312   int i,j;                  /* Loop counters */
3313   int hash;                 /* For hashing the name of a type */
3314   char *name;               /* Name of the parser */
3315
3316   /* Allocate and initialize types[] and allocate stddt[] */
3317   arraysize = lemp->nsymbol * 2;
3318   types = (char**)malloc( arraysize * sizeof(char*) );
3319   for(i=0; i<arraysize; i++) types[i] = 0;
3320   maxdtlength = 0;
3321   if( lemp->vartype ){
3322     maxdtlength = strlen(lemp->vartype);
3323   }
3324   for(i=0; i<lemp->nsymbol; i++){
3325     int len;
3326     struct symbol *sp = lemp->symbols[i];
3327     if( sp->datatype==0 ) continue;
3328     len = strlen(sp->datatype);
3329     if( len>maxdtlength ) maxdtlength = len;
3330   }
3331   stddt = (char*)malloc( maxdtlength*2 + 1 );
3332   if( types==0 || stddt==0 ){
3333     fprintf(stderr,"Out of memory.\n");
3334     exit(1);
3335   }
3336
3337   /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3338   ** is filled in with the hash index plus 1.  A ".dtnum" value of 0 is
3339   ** used for terminal symbols.  If there is no %default_type defined then
3340   ** 0 is also used as the .dtnum value for nonterminals which do not specify
3341   ** a datatype using the %type directive.
3342   */
3343   for(i=0; i<lemp->nsymbol; i++){
3344     struct symbol *sp = lemp->symbols[i];
3345     char *cp;
3346     if( sp==lemp->errsym ){
3347       sp->dtnum = arraysize+1;
3348       continue;
3349     }
3350     if( sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0) ){
3351       sp->dtnum = 0;
3352       continue;
3353     }
3354     cp = sp->datatype;
3355     if( cp==0 ) cp = lemp->vartype;
3356     j = 0;
3357     while( isspace(*cp) ) cp++;
3358     while( *cp ) stddt[j++] = *cp++;
3359     while( j>0 && isspace(stddt[j-1]) ) j--;
3360     stddt[j] = 0;
3361     hash = 0;
3362     for(j=0; stddt[j]; j++){
3363       hash = hash*53 + stddt[j];
3364     }
3365     hash = (hash & 0x7fffffff)%arraysize;
3366     while( types[hash] ){
3367       if( strcmp(types[hash],stddt)==0 ){
3368         sp->dtnum = hash + 1;
3369         break;
3370       }
3371       hash++;
3372       if( hash>=arraysize ) hash = 0;
3373     }
3374     if( types[hash]==0 ){
3375       sp->dtnum = hash + 1;
3376       types[hash] = (char*)malloc( strlen(stddt)+1 );
3377       if( types[hash]==0 ){
3378         fprintf(stderr,"Out of memory.\n");
3379         exit(1);
3380       }
3381       strcpy(types[hash],stddt);
3382     }
3383   }
3384
3385   /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3386   name = lemp->name ? lemp->name : "Parse";
3387   lineno = *plineno;
3388   if( mhflag ){ fprintf(out,"#if INTERFACE\n"); lineno++; }
3389   fprintf(out,"#define %sTOKENTYPE %s\n",name,
3390     lemp->tokentype?lemp->tokentype:"void*");  lineno++;
3391   if( mhflag ){ fprintf(out,"#endif\n"); lineno++; }
3392   fprintf(out,"typedef union {\n"); lineno++;
3393   fprintf(out,"  %sTOKENTYPE yy0;\n",name); lineno++;
3394   for(i=0; i<arraysize; i++){
3395     if( types[i]==0 ) continue;
3396     fprintf(out,"  %s yy%d;\n",types[i],i+1); lineno++;
3397     free(types[i]);
3398   }
3399   fprintf(out,"  int yy%d;\n",lemp->errsym->dtnum); lineno++;
3400   free(stddt);
3401   free(types);
3402   fprintf(out,"} YYMINORTYPE;\n"); lineno++;
3403   *plineno = lineno;
3404 }
3405
3406 /*
3407 ** Return the name of a C datatype able to represent values between
3408 ** lwr and upr, inclusive.
3409 */
3410 static const char *minimum_size_type(int lwr, int upr){
3411   if( lwr>=0 ){
3412     if( upr<=255 ){
3413       return "unsigned char";
3414     }else if( upr<65535 ){
3415       return "unsigned short int";
3416     }else{
3417       return "unsigned int";
3418     }
3419   }else if( lwr>=-127 && upr<=127 ){
3420     return "signed char";
3421   }else if( lwr>=-32767 && upr<32767 ){
3422     return "short";
3423   }else{
3424     return "int";
3425   }
3426 }
3427
3428 /*
3429 ** Each state contains a set of token transaction and a set of
3430 ** nonterminal transactions.  Each of these sets makes an instance
3431 ** of the following structure.  An array of these structures is used
3432 ** to order the creation of entries in the yy_action[] table.
3433 */
3434 struct axset {
3435   struct state *stp;   /* A pointer to a state */
3436   int isTkn;           /* True to use tokens.  False for non-terminals */
3437   int nAction;         /* Number of actions */
3438 };
3439
3440 /*
3441 ** Compare to axset structures for sorting purposes
3442 */
3443 static int axset_compare(const void *a, const void *b){
3444   struct axset *p1 = (struct axset*)a;
3445   struct axset *p2 = (struct axset*)b;
3446   return p2->nAction - p1->nAction;
3447 }
3448
3449 /* Generate C source code for the parser */
3450 void ReportTable(lemp, mhflag)
3451 struct lemon *lemp;
3452 int mhflag;     /* Output in makeheaders format if true */
3453 {
3454   FILE *out, *in;
3455   char line[LINESIZE];
3456   int  lineno;
3457   struct state *stp;
3458   struct action *ap;
3459   struct rule *rp;
3460   struct acttab *pActtab;
3461   int i, j, n;
3462   char *name;
3463   int mnTknOfst, mxTknOfst;
3464   int mnNtOfst, mxNtOfst;
3465   struct axset *ax;
3466
3467   in = tplt_open(lemp);
3468   if( in==0 ) return;
3469   out = file_open(lemp,".c","wb");
3470   if( out==0 ){
3471     fclose(in);
3472     return;
3473   }
3474   lineno = 1;
3475   tplt_xfer(lemp->name,in,out,&lineno);
3476
3477   /* Generate the include code, if any */
3478   tplt_print(out,lemp,lemp->include,lemp->includeln,&lineno);
3479   if( mhflag ){
3480     char *name = file_makename(lemp, ".h");
3481     fprintf(out,"#include \"%s\"\n", name); lineno++;
3482     free(name);
3483   }
3484   tplt_xfer(lemp->name,in,out,&lineno);
3485
3486   /* Generate #defines for all tokens */
3487   if( mhflag ){
3488     char *prefix;
3489     fprintf(out,"#if INTERFACE\n"); lineno++;
3490     if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
3491     else                    prefix = "";
3492     for(i=1; i<lemp->nterminal; i++){
3493       fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
3494       lineno++;
3495     }
3496     fprintf(out,"#endif\n"); lineno++;
3497   }
3498   tplt_xfer(lemp->name,in,out,&lineno);
3499
3500   /* Generate the defines */
3501   fprintf(out,"#define YYCODETYPE %s\n",
3502     minimum_size_type(0, lemp->nsymbol+5)); lineno++;
3503   fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
3504   fprintf(out,"#define YYACTIONTYPE %s\n",
3505     minimum_size_type(0, lemp->nstate+lemp->nrule+5));  lineno++;
3506   if( lemp->wildcard ){
3507     fprintf(out,"#define YYWILDCARD %d\n",
3508        lemp->wildcard->index); lineno++;
3509   }
3510   print_stack_union(out,lemp,&lineno,mhflag);
3511   if( lemp->stacksize ){
3512     if( atoi(lemp->stacksize)<=0 ){
3513       ErrorMsg(lemp->filename,0,
3514 "Illegal stack size: [%s].  The stack size should be an integer constant.",
3515         lemp->stacksize);
3516       lemp->errorcnt++;
3517       lemp->stacksize = "100";
3518     }
3519     fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize);  lineno++;
3520   }else{
3521     fprintf(out,"#define YYSTACKDEPTH 100\n");  lineno++;
3522   }
3523   if( mhflag ){
3524     fprintf(out,"#if INTERFACE\n"); lineno++;
3525   }
3526   name = lemp->name ? lemp->name : "Parse";
3527   if( lemp->arg && lemp->arg[0] ){
3528     int i;
3529     i = strlen(lemp->arg);
3530     while( i>=1 && isspace(lemp->arg[i-1]) ) i--;
3531     while( i>=1 && (isalnum(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--;
3532     fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg);  lineno++;
3533     fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg);  lineno++;
3534     fprintf(out,"#define %sARG_FETCH %s = yypParser->%s\n",
3535                  name,lemp->arg,&lemp->arg[i]);  lineno++;
3536     fprintf(out,"#define %sARG_STORE yypParser->%s = %s\n",
3537                  name,&lemp->arg[i],&lemp->arg[i]);  lineno++;
3538   }else{
3539     fprintf(out,"#define %sARG_SDECL\n",name);  lineno++;
3540     fprintf(out,"#define %sARG_PDECL\n",name);  lineno++;
3541     fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
3542     fprintf(out,"#define %sARG_STORE\n",name); lineno++;
3543   }
3544   if( mhflag ){
3545     fprintf(out,"#endif\n"); lineno++;
3546   }
3547   fprintf(out,"#define YYNSTATE %d\n",lemp->nstate);  lineno++;
3548   fprintf(out,"#define YYNRULE %d\n",lemp->nrule);  lineno++;
3549   fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index);  lineno++;
3550   fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum);  lineno++;
3551   if( lemp->has_fallback ){
3552     fprintf(out,"#define YYFALLBACK 1\n");  lineno++;
3553   }
3554   tplt_xfer(lemp->name,in,out,&lineno);
3555
3556   /* Generate the action table and its associates:
3557   **
3558   **  yy_action[]        A single table containing all actions.
3559   **  yy_lookahead[]     A table containing the lookahead for each entry in
3560   **                     yy_action.  Used to detect hash collisions.
3561   **  yy_shift_ofst[]    For each state, the offset into yy_action for
3562   **                     shifting terminals.
3563   **  yy_reduce_ofst[]   For each state, the offset into yy_action for
3564   **                     shifting non-terminals after a reduce.
3565   **  yy_default[]       Default action for each state.
3566   */
3567
3568   /* Compute the actions on all states and count them up */
3569   ax = malloc( sizeof(ax[0])*lemp->nstate*2 );
3570   if( ax==0 ){
3571     fprintf(stderr,"malloc failed\n");
3572     exit(1);
3573   }
3574   for(i=0; i<lemp->nstate; i++){
3575     stp = lemp->sorted[i];
3576     ax[i*2].stp = stp;
3577     ax[i*2].isTkn = 1;
3578     ax[i*2].nAction = stp->nTknAct;
3579     ax[i*2+1].stp = stp;
3580     ax[i*2+1].isTkn = 0;
3581     ax[i*2+1].nAction = stp->nNtAct;
3582   }
3583   mxTknOfst = mnTknOfst = 0;
3584   mxNtOfst = mnNtOfst = 0;
3585
3586   /* Compute the action table.  In order to try to keep the size of the
3587   ** action table to a minimum, the heuristic of placing the largest action
3588   ** sets first is used.
3589   */
3590   qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
3591   pActtab = acttab_alloc();
3592   for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
3593     stp = ax[i].stp;
3594     if( ax[i].isTkn ){
3595       for(ap=stp->ap; ap; ap=ap->next){
3596         int action;
3597         if( ap->sp->index>=lemp->nterminal ) continue;
3598         action = compute_action(lemp, ap);
3599         if( action<0 ) continue;
3600         acttab_action(pActtab, ap->sp->index, action);
3601       }
3602       stp->iTknOfst = acttab_insert(pActtab);
3603       if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
3604       if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
3605     }else{
3606       for(ap=stp->ap; ap; ap=ap->next){
3607         int action;
3608         if( ap->sp->index<lemp->nterminal ) continue;
3609         if( ap->sp->index==lemp->nsymbol ) continue;
3610         action = compute_action(lemp, ap);
3611         if( action<0 ) continue;
3612         acttab_action(pActtab, ap->sp->index, action);
3613       }
3614       stp->iNtOfst = acttab_insert(pActtab);
3615       if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
3616       if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
3617     }
3618   }
3619   free(ax);
3620
3621   /* Output the yy_action table */
3622   fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
3623   n = acttab_size(pActtab);
3624   for(i=j=0; i<n; i++){
3625     int action = acttab_yyaction(pActtab, i);
3626     if( action<0 ) action = lemp->nsymbol + lemp->nrule + 2;
3627     if( j==0 ) fprintf(out," /* %5d */ ", i);
3628     fprintf(out, " %4d,", action);
3629     if( j==9 || i==n-1 ){
3630       fprintf(out, "\n"); lineno++;
3631       j = 0;
3632     }else{
3633       j++;
3634     }
3635   }
3636   fprintf(out, "};\n"); lineno++;
3637
3638   /* Output the yy_lookahead table */
3639   fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
3640   for(i=j=0; i<n; i++){
3641     int la = acttab_yylookahead(pActtab, i);
3642     if( la<0 ) la = lemp->nsymbol;
3643     if( j==0 ) fprintf(out," /* %5d */ ", i);
3644     fprintf(out, " %4d,", la);
3645     if( j==9 || i==n-1 ){
3646       fprintf(out, "\n"); lineno++;
3647       j = 0;
3648     }else{
3649       j++;
3650     }
3651   }
3652   fprintf(out, "};\n"); lineno++;
3653
3654   /* Output the yy_shift_ofst[] table */
3655   fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
3656   n = lemp->nstate;
3657   while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
3658   fprintf(out, "#define YY_SHIFT_MAX %d\n", n-1); lineno++;
3659   fprintf(out, "static const %s yy_shift_ofst[] = {\n",
3660           minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
3661   for(i=j=0; i<n; i++){
3662     int ofst;
3663     stp = lemp->sorted[i];
3664     ofst = stp->iTknOfst;
3665     if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;
3666     if( j==0 ) fprintf(out," /* %5d */ ", i);
3667     fprintf(out, " %4d,", ofst);
3668     if( j==9 || i==n-1 ){
3669       fprintf(out, "\n"); lineno++;
3670       j = 0;
3671     }else{
3672       j++;
3673     }
3674   }
3675   fprintf(out, "};\n"); lineno++;
3676
3677   /* Output the yy_reduce_ofst[] table */
3678   fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
3679   n = lemp->nstate;
3680   while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
3681   fprintf(out, "#define YY_REDUCE_MAX %d\n", n-1); lineno++;
3682   fprintf(out, "static const %s yy_reduce_ofst[] = {\n",
3683           minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
3684   for(i=j=0; i<n; i++){
3685     int ofst;
3686     stp = lemp->sorted[i];
3687     ofst = stp->iNtOfst;
3688     if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
3689     if( j==0 ) fprintf(out," /* %5d */ ", i);
3690     fprintf(out, " %4d,", ofst);
3691     if( j==9 || i==n-1 ){
3692       fprintf(out, "\n"); lineno++;
3693       j = 0;
3694     }else{
3695       j++;
3696     }
3697   }
3698   fprintf(out, "};\n"); lineno++;
3699
3700   /* Output the default action table */
3701   fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
3702   n = lemp->nstate;
3703   for(i=j=0; i<n; i++){
3704     stp = lemp->sorted[i];
3705     if( j==0 ) fprintf(out," /* %5d */ ", i);
3706     fprintf(out, " %4d,", stp->iDflt);
3707     if( j==9 || i==n-1 ){
3708       fprintf(out, "\n"); lineno++;
3709       j = 0;
3710     }else{
3711       j++;
3712     }
3713   }
3714   fprintf(out, "};\n"); lineno++;
3715   tplt_xfer(lemp->name,in,out,&lineno);
3716
3717   /* Generate the table of fallback tokens.
3718   */
3719   if( lemp->has_fallback ){
3720     for(i=0; i<lemp->nterminal; i++){
3721       struct symbol *p = lemp->symbols[i];
3722       if( p->fallback==0 ){
3723         fprintf(out, "    0,  /* %10s => nothing */\n", p->name);
3724       }else{
3725         fprintf(out, "  %3d,  /* %10s => %s */\n", p->fallback->index,
3726           p->name, p->fallback->name);
3727       }
3728       lineno++;
3729     }
3730   }
3731   tplt_xfer(lemp->name, in, out, &lineno);
3732
3733   /* Generate a table containing the symbolic name of every symbol
3734   */
3735   for(i=0; i<lemp->nsymbol; i++){
3736     sprintf(line,"\"%s\",",lemp->symbols[i]->name);
3737     fprintf(out,"  %-15s",line);
3738     if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; }
3739   }
3740   if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; }
3741   tplt_xfer(lemp->name,in,out,&lineno);
3742
3743   /* Generate a table containing a text string that describes every
3744   ** rule in the rule set of the grammer.  This information is used
3745   ** when tracing REDUCE actions.
3746   */
3747   for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
3748     assert( rp->index==i );
3749     fprintf(out," /* %3d */ \"%s ::=", i, rp->lhs->name);
3750     for(j=0; j<rp->nrhs; j++){
3751       struct symbol *sp = rp->rhs[j];
3752       fprintf(out," %s", sp->name);
3753       if( sp->type==MULTITERMINAL ){
3754         int k;
3755         for(k=1; k<sp->nsubsym; k++){
3756           fprintf(out,"|%s",sp->subsym[k]->name);
3757         }
3758       }
3759     }
3760     fprintf(out,"\",\n"); lineno++;
3761   }
3762   tplt_xfer(lemp->name,in,out,&lineno);
3763
3764   /* Generate code which executes every time a symbol is popped from
3765   ** the stack while processing errors or while destroying the parser.
3766   ** (In other words, generate the %destructor actions)
3767   */
3768   if( lemp->tokendest ){
3769     for(i=0; i<lemp->nsymbol; i++){
3770       struct symbol *sp = lemp->symbols[i];
3771       if( sp==0 || sp->type!=TERMINAL ) continue;
3772       fprintf(out,"    case %d:\n",sp->index); lineno++;
3773     }
3774     for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
3775     if( i<lemp->nsymbol ){
3776       emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
3777       fprintf(out,"      break;\n"); lineno++;
3778     }
3779   }
3780   if( lemp->vardest ){
3781     struct symbol *dflt_sp = 0;
3782     for(i=0; i<lemp->nsymbol; i++){
3783       struct symbol *sp = lemp->symbols[i];
3784       if( sp==0 || sp->type==TERMINAL ||
3785           sp->index<=0 || sp->destructor!=0 ) continue;
3786       fprintf(out,"    case %d:\n",sp->index); lineno++;
3787       dflt_sp = sp;
3788     }
3789     if( dflt_sp!=0 ){
3790       emit_destructor_code(out,dflt_sp,lemp,&lineno);
3791       fprintf(out,"      break;\n"); lineno++;
3792     }
3793   }
3794   for(i=0; i<lemp->nsymbol; i++){
3795     struct symbol *sp = lemp->symbols[i];
3796     if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
3797     fprintf(out,"    case %d:\n",sp->index); lineno++;
3798
3799     /* Combine duplicate destructors into a single case */
3800     for(j=i+1; j<lemp->nsymbol; j++){
3801       struct symbol *sp2 = lemp->symbols[j];
3802       if( sp2 && sp2->type!=TERMINAL && sp2->destructor
3803           && sp2->dtnum==sp->dtnum
3804           && strcmp(sp->destructor,sp2->destructor)==0 ){
3805          fprintf(out,"    case %d:\n",sp2->index); lineno++;
3806          sp2->destructor = 0;
3807       }
3808     }
3809
3810     emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
3811     fprintf(out,"      break;\n"); lineno++;
3812   }
3813   tplt_xfer(lemp->name,in,out,&lineno);
3814
3815   /* Generate code which executes whenever the parser stack overflows */
3816   tplt_print(out,lemp,lemp->overflow,lemp->overflowln,&lineno);
3817   tplt_xfer(lemp->name,in,out,&lineno);
3818
3819   /* Generate the table of rule information
3820   **
3821   ** Note: This code depends on the fact that rules are number
3822   ** sequentually beginning with 0.
3823   */
3824   for(rp=lemp->rule; rp; rp=rp->next){
3825     fprintf(out,"  { %d, %d },\n",rp->lhs->index,rp->nrhs); lineno++;
3826   }
3827   tplt_xfer(lemp->name,in,out,&lineno);
3828
3829   /* Generate code which execution during each REDUCE action */
3830   for(rp=lemp->rule; rp; rp=rp->next){
3831     if( rp->code ) translate_code(lemp, rp);
3832   }
3833   for(rp=lemp->rule; rp; rp=rp->next){
3834     struct rule *rp2;
3835     if( rp->code==0 ) continue;
3836     fprintf(out,"      case %d:\n",rp->index); lineno++;
3837     for(rp2=rp->next; rp2; rp2=rp2->next){
3838       if( rp2->code==rp->code ){
3839         fprintf(out,"      case %d:\n",rp2->index); lineno++;
3840         rp2->code = 0;
3841       }
3842     }
3843     emit_code(out,rp,lemp,&lineno);
3844     fprintf(out,"        break;\n"); lineno++;
3845   }
3846   tplt_xfer(lemp->name,in,out,&lineno);
3847
3848   /* Generate code which executes if a parse fails */
3849   tplt_print(out,lemp,lemp->failure,lemp->failureln,&lineno);
3850   tplt_xfer(lemp->name,in,out,&lineno);
3851
3852   /* Generate code which executes when a syntax error occurs */
3853   tplt_print(out,lemp,lemp->error,lemp->errorln,&lineno);
3854   tplt_xfer(lemp->name,in,out,&lineno);
3855
3856   /* Generate code which executes when the parser accepts its input */
3857   tplt_print(out,lemp,lemp->accept,lemp->acceptln,&lineno);
3858   tplt_xfer(lemp->name,in,out,&lineno);
3859
3860   /* Append any addition code the user desires */
3861   tplt_print(out,lemp,lemp->extracode,lemp->extracodeln,&lineno);
3862
3863   fclose(in);
3864   fclose(out);
3865   return;
3866 }
3867
3868 /* Generate a header file for the parser */
3869 void ReportHeader(lemp)
3870 struct lemon *lemp;
3871 {
3872   FILE *out, *in;
3873   char *prefix;
3874   char line[LINESIZE];
3875   char pattern[LINESIZE];
3876   int i;
3877
3878   if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
3879   else                    prefix = "";
3880   in = file_open(lemp,".h","rb");
3881   if( in ){
3882     for(i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++){
3883       sprintf(pattern,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
3884       if( strcmp(line,pattern) ) break;
3885     }
3886     fclose(in);
3887     if( i==lemp->nterminal ){
3888       /* No change in the file.  Don't rewrite it. */
3889       return;
3890     }
3891   }
3892   out = file_open(lemp,".h","wb");
3893   if( out ){
3894     for(i=1; i<lemp->nterminal; i++){
3895       fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
3896     }
3897     fclose(out);
3898   }
3899   return;
3900 }
3901
3902 /* Reduce the size of the action tables, if possible, by making use
3903 ** of defaults.
3904 **
3905 ** In this version, we take the most frequent REDUCE action and make
3906 ** it the default.  Except, there is no default if the wildcard token
3907 ** is a possible look-ahead.
3908 */
3909 void CompressTables(lemp)
3910 struct lemon *lemp;
3911 {
3912   struct state *stp;
3913   struct action *ap, *ap2;
3914   struct rule *rp, *rp2, *rbest;
3915   int nbest, n;
3916   int i;
3917   int usesWildcard;
3918
3919   for(i=0; i<lemp->nstate; i++){
3920     stp = lemp->sorted[i];
3921     nbest = 0;
3922     rbest = 0;
3923     usesWildcard = 0;
3924
3925     for(ap=stp->ap; ap; ap=ap->next){
3926       if( ap->type==SHIFT && ap->sp==lemp->wildcard ){
3927         usesWildcard = 1;
3928       }
3929       if( ap->type!=REDUCE ) continue;
3930       rp = ap->x.rp;
3931       if( rp==rbest ) continue;
3932       n = 1;
3933       for(ap2=ap->next; ap2; ap2=ap2->next){
3934         if( ap2->type!=REDUCE ) continue;
3935         rp2 = ap2->x.rp;
3936         if( rp2==rbest ) continue;
3937         if( rp2==rp ) n++;
3938       }
3939       if( n>nbest ){
3940         nbest = n;
3941         rbest = rp;
3942       }
3943     }
3944
3945     /* Do not make a default if the number of rules to default
3946     ** is not at least 1 or if the wildcard token is a possible
3947     ** lookahead.
3948     */
3949     if( nbest<1 || usesWildcard ) continue;
3950
3951
3952     /* Combine matching REDUCE actions into a single default */
3953     for(ap=stp->ap; ap; ap=ap->next){
3954       if( ap->type==REDUCE && ap->x.rp==rbest ) break;
3955     }
3956     assert( ap );
3957     ap->sp = Symbol_new("{default}");
3958     for(ap=ap->next; ap; ap=ap->next){
3959       if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
3960     }
3961     stp->ap = Action_sort(stp->ap);
3962   }
3963 }
3964
3965
3966 /*
3967 ** Compare two states for sorting purposes.  The smaller state is the
3968 ** one with the most non-terminal actions.  If they have the same number
3969 ** of non-terminal actions, then the smaller is the one with the most
3970 ** token actions.
3971 */
3972 static int stateResortCompare(const void *a, const void *b){
3973   const struct state *pA = *(const struct state**)a;
3974   const struct state *pB = *(const struct state**)b;
3975   int n;
3976
3977   n = pB->nNtAct - pA->nNtAct;
3978   if( n==0 ){
3979     n = pB->nTknAct - pA->nTknAct;
3980   }
3981   return n;
3982 }
3983
3984
3985 /*
3986 ** Renumber and resort states so that states with fewer choices
3987 ** occur at the end.  Except, keep state 0 as the first state.
3988 */
3989 void ResortStates(lemp)
3990 struct lemon *lemp;
3991 {
3992   int i;
3993   struct state *stp;
3994   struct action *ap;
3995
3996   for(i=0; i<lemp->nstate; i++){
3997     stp = lemp->sorted[i];
3998     stp->nTknAct = stp->nNtAct = 0;
3999     stp->iDflt = lemp->nstate + lemp->nrule;
4000     stp->iTknOfst = NO_OFFSET;
4001     stp->iNtOfst = NO_OFFSET;
4002     for(ap=stp->ap; ap; ap=ap->next){
4003       if( compute_action(lemp,ap)>=0 ){
4004         if( ap->sp->index<lemp->nterminal ){
4005           stp->nTknAct++;
4006         }else if( ap->sp->index<lemp->nsymbol ){
4007           stp->nNtAct++;
4008         }else{
4009           stp->iDflt = compute_action(lemp, ap);
4010         }
4011       }
4012     }
4013   }
4014   qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
4015         stateResortCompare);
4016   for(i=0; i<lemp->nstate; i++){
4017     lemp->sorted[i]->statenum = i;
4018   }
4019 }
4020
4021
4022 /***************** From the file "set.c" ************************************/
4023 /*
4024 ** Set manipulation routines for the LEMON parser generator.
4025 */
4026
4027 static int size = 0;
4028
4029 /* Set the set size */
4030 void SetSize(n)
4031 int n;
4032 {
4033   size = n+1;
4034 }
4035
4036 /* Allocate a new set */
4037 char *SetNew(){
4038   char *s;
4039   int i;
4040   s = (char*)malloc( size );
4041   if( s==0 ){
4042     extern void memory_error();
4043     memory_error();
4044   }
4045   for(i=0; i<size; i++) s[i] = 0;
4046   return s;
4047 }
4048
4049 /* Deallocate a set */
4050 void SetFree(s)
4051 char *s;
4052 {
4053   free(s);
4054 }
4055
4056 /* Add a new element to the set.  Return TRUE if the element was added
4057 ** and FALSE if it was already there. */
4058 int SetAdd(s,e)
4059 char *s;
4060 int e;
4061 {
4062   int rv;
4063   rv = s[e];
4064   s[e] = 1;
4065   return !rv;
4066 }
4067
4068 /* Add every element of s2 to s1.  Return TRUE if s1 changes. */
4069 int SetUnion(s1,s2)
4070 char *s1;
4071 char *s2;
4072 {
4073   int i, progress;
4074   progress = 0;
4075   for(i=0; i<size; i++){
4076     if( s2[i]==0 ) continue;
4077     if( s1[i]==0 ){
4078       progress = 1;
4079       s1[i] = 1;
4080     }
4081   }
4082   return progress;
4083 }
4084 /********************** From the file "table.c" ****************************/
4085 /*
4086 ** All code in this file has been automatically generated
4087 ** from a specification in the file
4088 **              "table.q"
4089 ** by the associative array code building program "aagen".
4090 ** Do not edit this file!  Instead, edit the specification
4091 ** file, then rerun aagen.
4092 */
4093 /*
4094 ** Code for processing tables in the LEMON parser generator.
4095 */
4096
4097 PRIVATE int strhash(x)
4098 char *x;
4099 {
4100   int h = 0;
4101   while( *x) h = h*13 + *(x++);
4102   return h;
4103 }
4104
4105 /* Works like strdup, sort of.  Save a string in malloced memory, but
4106 ** keep strings in a table so that the same string is not in more
4107 ** than one place.
4108 */
4109 char *Strsafe(y)
4110 char *y;
4111 {
4112   char *z;
4113
4114   if( y==0 ) return 0;
4115   z = Strsafe_find(y);
4116   if( z==0 && (z=malloc( strlen(y)+1 ))!=0 ){
4117     strcpy(z,y);
4118     Strsafe_insert(z);
4119   }
4120   MemoryCheck(z);
4121   return z;
4122 }
4123
4124 /* There is one instance of the following structure for each
4125 ** associative array of type "x1".
4126 */
4127 struct s_x1 {
4128   int size;               /* The number of available slots. */
4129                           /*   Must be a power of 2 greater than or */
4130                           /*   equal to 1 */
4131   int count;              /* Number of currently slots filled */
4132   struct s_x1node *tbl;  /* The data stored here */
4133   struct s_x1node **ht;  /* Hash table for lookups */
4134 };
4135
4136 /* There is one instance of this structure for every data element
4137 ** in an associative array of type "x1".
4138 */
4139 typedef struct s_x1node {
4140   char *data;                  /* The data */
4141   struct s_x1node *next;   /* Next entry with the same hash */
4142   struct s_x1node **from;  /* Previous link */
4143 } x1node;
4144
4145 /* There is only one instance of the array, which is the following */
4146 static struct s_x1 *x1a;
4147
4148 /* Allocate a new associative array */
4149 void Strsafe_init(){
4150   if( x1a ) return;
4151   x1a = (struct s_x1*)malloc( sizeof(struct s_x1) );
4152   if( x1a ){
4153     x1a->size = 1024;
4154     x1a->count = 0;
4155     x1a->tbl = (x1node*)malloc(
4156       (sizeof(x1node) + sizeof(x1node*))*1024 );
4157     if( x1a->tbl==0 ){
4158       free(x1a);
4159       x1a = 0;
4160     }else{
4161       int i;
4162       x1a->ht = (x1node**)&(x1a->tbl[1024]);
4163       for(i=0; i<1024; i++) x1a->ht[i] = 0;
4164     }
4165   }
4166 }
4167 /* Insert a new record into the array.  Return TRUE if successful.
4168 ** Prior data with the same key is NOT overwritten */
4169 int Strsafe_insert(data)
4170 char *data;
4171 {
4172   x1node *np;
4173   int h;
4174   int ph;
4175
4176   if( x1a==0 ) return 0;
4177   ph = strhash(data);
4178   h = ph & (x1a->size-1);
4179   np = x1a->ht[h];
4180   while( np ){
4181     if( strcmp(np->data,data)==0 ){
4182       /* An existing entry with the same key is found. */
4183       /* Fail because overwrite is not allows. */
4184       return 0;
4185     }
4186     np = np->next;
4187   }
4188   if( x1a->count>=x1a->size ){
4189     /* Need to make the hash table bigger */
4190     int i,size;
4191     struct s_x1 array;
4192     array.size = size = x1a->size*2;
4193     array.count = x1a->count;
4194     array.tbl = (x1node*)malloc(
4195       (sizeof(x1node) + sizeof(x1node*))*size );
4196     if( array.tbl==0 ) return 0;  /* Fail due to malloc failure */
4197     array.ht = (x1node**)&(array.tbl[size]);
4198     for(i=0; i<size; i++) array.ht[i] = 0;
4199     for(i=0; i<x1a->count; i++){
4200       x1node *oldnp, *newnp;
4201       oldnp = &(x1a->tbl[i]);
4202       h = strhash(oldnp->data) & (size-1);
4203       newnp = &(array.tbl[i]);
4204       if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4205       newnp->next = array.ht[h];
4206       newnp->data = oldnp->data;
4207       newnp->from = &(array.ht[h]);
4208       array.ht[h] = newnp;
4209     }
4210     free(x1a->tbl);
4211     *x1a = array;
4212   }
4213   /* Insert the new data */
4214   h = ph & (x1a->size-1);
4215   np = &(x1a->tbl[x1a->count++]);
4216   np->data = data;
4217   if( x1a->ht[h] ) x1a->ht[h]->from = &(np->next);
4218   np->next = x1a->ht[h];
4219   x1a->ht[h] = np;
4220   np->from = &(x1a->ht[h]);
4221   return 1;
4222 }
4223
4224 /* Return a pointer to data assigned to the given key.  Return NULL
4225 ** if no such key. */
4226 char *Strsafe_find(key)
4227 char *key;
4228 {
4229   int h;
4230   x1node *np;
4231
4232   if( x1a==0 ) return 0;
4233   h = strhash(key) & (x1a->size-1);
4234   np = x1a->ht[h];
4235   while( np ){
4236     if( strcmp(np->data,key)==0 ) break;
4237     np = np->next;
4238   }
4239   return np ? np->data : 0;
4240 }
4241
4242 /* Return a pointer to the (terminal or nonterminal) symbol "x".
4243 ** Create a new symbol if this is the first time "x" has been seen.
4244 */
4245 struct symbol *Symbol_new(x)
4246 char *x;
4247 {
4248   struct symbol *sp;
4249
4250   sp = Symbol_find(x);
4251   if( sp==0 ){
4252     sp = (struct symbol *)malloc( sizeof(struct symbol) );
4253     MemoryCheck(sp);
4254     sp->name = Strsafe(x);
4255     sp->type = isupper(*x) ? TERMINAL : NONTERMINAL;
4256     sp->rule = 0;
4257     sp->fallback = 0;
4258     sp->prec = -1;
4259     sp->assoc = UNK;
4260     sp->firstset = 0;
4261     sp->lambda = B_FALSE;
4262     sp->destructor = 0;
4263     sp->datatype = 0;
4264     Symbol_insert(sp,sp->name);
4265   }
4266   return sp;
4267 }
4268
4269 /* Compare two symbols for working purposes
4270 **
4271 ** Symbols that begin with upper case letters (terminals or tokens)
4272 ** must sort before symbols that begin with lower case letters
4273 ** (non-terminals).  Other than that, the order does not matter.
4274 **
4275 ** We find experimentally that leaving the symbols in their original
4276 ** order (the order they appeared in the grammar file) gives the
4277 ** smallest parser tables in SQLite.
4278 */
4279 int Symbolcmpp(struct symbol **a, struct symbol **b){
4280   int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
4281   int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
4282   return i1-i2;
4283 }
4284
4285 /* There is one instance of the following structure for each
4286 ** associative array of type "x2".
4287 */
4288 struct s_x2 {
4289   int size;               /* The number of available slots. */
4290                           /*   Must be a power of 2 greater than or */
4291                           /*   equal to 1 */
4292   int count;              /* Number of currently slots filled */
4293   struct s_x2node *tbl;  /* The data stored here */
4294   struct s_x2node **ht;  /* Hash table for lookups */
4295 };
4296
4297 /* There is one instance of this structure for every data element
4298 ** in an associative array of type "x2".
4299 */
4300 typedef struct s_x2node {
4301   struct symbol *data;                  /* The data */
4302   char *key;                   /* The key */
4303   struct s_x2node *next;   /* Next entry with the same hash */
4304   struct s_x2node **from;  /* Previous link */
4305 } x2node;
4306
4307 /* There is only one instance of the array, which is the following */
4308 static struct s_x2 *x2a;
4309
4310 /* Allocate a new associative array */
4311 void Symbol_init(){
4312   if( x2a ) return;
4313   x2a = (struct s_x2*)malloc( sizeof(struct s_x2) );
4314   if( x2a ){
4315     x2a->size = 128;
4316     x2a->count = 0;
4317     x2a->tbl = (x2node*)malloc(
4318       (sizeof(x2node) + sizeof(x2node*))*128 );
4319     if( x2a->tbl==0 ){
4320       free(x2a);
4321       x2a = 0;
4322     }else{
4323       int i;
4324       x2a->ht = (x2node**)&(x2a->tbl[128]);
4325       for(i=0; i<128; i++) x2a->ht[i] = 0;
4326     }
4327   }
4328 }
4329 /* Insert a new record into the array.  Return TRUE if successful.
4330 ** Prior data with the same key is NOT overwritten */
4331 int Symbol_insert(data,key)
4332 struct symbol *data;
4333 char *key;
4334 {
4335   x2node *np;
4336   int h;
4337   int ph;
4338
4339   if( x2a==0 ) return 0;
4340   ph = strhash(key);
4341   h = ph & (x2a->size-1);
4342   np = x2a->ht[h];
4343   while( np ){
4344     if( strcmp(np->key,key)==0 ){
4345       /* An existing entry with the same key is found. */
4346       /* Fail because overwrite is not allows. */
4347       return 0;
4348     }
4349     np = np->next;
4350   }
4351   if( x2a->count>=x2a->size ){
4352     /* Need to make the hash table bigger */
4353     int i,size;
4354     struct s_x2 array;
4355     array.size = size = x2a->size*2;
4356     array.count = x2a->count;
4357     array.tbl = (x2node*)malloc(
4358       (sizeof(x2node) + sizeof(x2node*))*size );
4359     if( array.tbl==0 ) return 0;  /* Fail due to malloc failure */
4360     array.ht = (x2node**)&(array.tbl[size]);
4361     for(i=0; i<size; i++) array.ht[i] = 0;
4362     for(i=0; i<x2a->count; i++){
4363       x2node *oldnp, *newnp;
4364       oldnp = &(x2a->tbl[i]);
4365       h = strhash(oldnp->key) & (size-1);
4366       newnp = &(array.tbl[i]);
4367       if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4368       newnp->next = array.ht[h];
4369       newnp->key = oldnp->key;
4370       newnp->data = oldnp->data;
4371       newnp->from = &(array.ht[h]);
4372       array.ht[h] = newnp;
4373     }
4374     free(x2a->tbl);
4375     *x2a = array;
4376   }
4377   /* Insert the new data */
4378   h = ph & (x2a->size-1);
4379   np = &(x2a->tbl[x2a->count++]);
4380   np->key = key;
4381   np->data = data;
4382   if( x2a->ht[h] ) x2a->ht[h]->from = &(np->next);
4383   np->next = x2a->ht[h];
4384   x2a->ht[h] = np;
4385   np->from = &(x2a->ht[h]);
4386   return 1;
4387 }
4388
4389 /* Return a pointer to data assigned to the given key.  Return NULL
4390 ** if no such key. */
4391 struct symbol *Symbol_find(key)
4392 char *key;
4393 {
4394   int h;
4395   x2node *np;
4396
4397   if( x2a==0 ) return 0;
4398   h = strhash(key) & (x2a->size-1);
4399   np = x2a->ht[h];
4400   while( np ){
4401     if( strcmp(np->key,key)==0 ) break;
4402     np = np->next;
4403   }
4404   return np ? np->data : 0;
4405 }
4406
4407 /* Return the n-th data.  Return NULL if n is out of range. */
4408 struct symbol *Symbol_Nth(n)
4409 int n;
4410 {
4411   struct symbol *data;
4412   if( x2a && n>0 && n<=x2a->count ){
4413     data = x2a->tbl[n-1].data;
4414   }else{
4415     data = 0;
4416   }
4417   return data;
4418 }
4419
4420 /* Return the size of the array */
4421 int Symbol_count()
4422 {
4423   return x2a ? x2a->count : 0;
4424 }
4425
4426 /* Return an array of pointers to all data in the table.
4427 ** The array is obtained from malloc.  Return NULL if memory allocation
4428 ** problems, or if the array is empty. */
4429 struct symbol **Symbol_arrayof()
4430 {
4431   struct symbol **array;
4432   int i,size;
4433   if( x2a==0 ) return 0;
4434   size = x2a->count;
4435   array = (struct symbol **)malloc( sizeof(struct symbol *)*size );
4436   if( array ){
4437     for(i=0; i<size; i++) array[i] = x2a->tbl[i].data;
4438   }
4439   return array;
4440 }
4441
4442 /* Compare two configurations */
4443 int Configcmp(a,b)
4444 struct config *a;
4445 struct config *b;
4446 {
4447   int x;
4448   x = a->rp->index - b->rp->index;
4449   if( x==0 ) x = a->dot - b->dot;
4450   return x;
4451 }
4452
4453 /* Compare two states */
4454 PRIVATE int statecmp(a,b)
4455 struct config *a;
4456 struct config *b;
4457 {
4458   int rc;
4459   for(rc=0; rc==0 && a && b;  a=a->bp, b=b->bp){
4460     rc = a->rp->index - b->rp->index;
4461     if( rc==0 ) rc = a->dot - b->dot;
4462   }
4463   if( rc==0 ){
4464     if( a ) rc = 1;
4465     if( b ) rc = -1;
4466   }
4467   return rc;
4468 }
4469
4470 /* Hash a state */
4471 PRIVATE int statehash(a)
4472 struct config *a;
4473 {
4474   int h=0;
4475   while( a ){
4476     h = h*571 + a->rp->index*37 + a->dot;
4477     a = a->bp;
4478   }
4479   return h;
4480 }
4481
4482 /* Allocate a new state structure */
4483 struct state *State_new()
4484 {
4485   struct state *new;
4486   new = (struct state *)malloc( sizeof(struct state) );
4487   MemoryCheck(new);
4488   return new;
4489 }
4490
4491 /* There is one instance of the following structure for each
4492 ** associative array of type "x3".
4493 */
4494 struct s_x3 {
4495   int size;               /* The number of available slots. */
4496                           /*   Must be a power of 2 greater than or */
4497                           /*   equal to 1 */
4498   int count;              /* Number of currently slots filled */
4499   struct s_x3node *tbl;  /* The data stored here */
4500   struct s_x3node **ht;  /* Hash table for lookups */
4501 };
4502
4503 /* There is one instance of this structure for every data element
4504 ** in an associative array of type "x3".
4505 */
4506 typedef struct s_x3node {
4507   struct state *data;                  /* The data */
4508   struct config *key;                   /* The key */
4509   struct s_x3node *next;   /* Next entry with the same hash */
4510   struct s_x3node **from;  /* Previous link */
4511 } x3node;
4512
4513 /* There is only one instance of the array, which is the following */
4514 static struct s_x3 *x3a;
4515
4516 /* Allocate a new associative array */
4517 void State_init(){
4518   if( x3a ) return;
4519   x3a = (struct s_x3*)malloc( sizeof(struct s_x3) );
4520   if( x3a ){
4521     x3a->size = 128;
4522     x3a->count = 0;
4523     x3a->tbl = (x3node*)malloc(
4524       (sizeof(x3node) + sizeof(x3node*))*128 );
4525     if( x3a->tbl==0 ){
4526       free(x3a);
4527       x3a = 0;
4528     }else{
4529       int i;
4530       x3a->ht = (x3node**)&(x3a->tbl[128]);
4531       for(i=0; i<128; i++) x3a->ht[i] = 0;
4532     }
4533   }
4534 }
4535 /* Insert a new record into the array.  Return TRUE if successful.
4536 ** Prior data with the same key is NOT overwritten */
4537 int State_insert(data,key)
4538 struct state *data;
4539 struct config *key;
4540 {
4541   x3node *np;
4542   int h;
4543   int ph;
4544
4545   if( x3a==0 ) return 0;
4546   ph = statehash(key);
4547   h = ph & (x3a->size-1);
4548   np = x3a->ht[h];
4549   while( np ){
4550     if( statecmp(np->key,key)==0 ){
4551       /* An existing entry with the same key is found. */
4552       /* Fail because overwrite is not allows. */
4553       return 0;
4554     }
4555     np = np->next;
4556   }
4557   if( x3a->count>=x3a->size ){
4558     /* Need to make the hash table bigger */
4559     int i,size;
4560     struct s_x3 array;
4561     array.size = size = x3a->size*2;
4562     array.count = x3a->count;
4563     array.tbl = (x3node*)malloc(
4564       (sizeof(x3node) + sizeof(x3node*))*size );
4565     if( array.tbl==0 ) return 0;  /* Fail due to malloc failure */
4566     array.ht = (x3node**)&(array.tbl[size]);
4567     for(i=0; i<size; i++) array.ht[i] = 0;
4568     for(i=0; i<x3a->count; i++){
4569       x3node *oldnp, *newnp;
4570       oldnp = &(x3a->tbl[i]);
4571       h = statehash(oldnp->key) & (size-1);
4572       newnp = &(array.tbl[i]);
4573       if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4574       newnp->next = array.ht[h];
4575       newnp->key = oldnp->key;
4576       newnp->data = oldnp->data;
4577       newnp->from = &(array.ht[h]);
4578       array.ht[h] = newnp;
4579     }
4580     free(x3a->tbl);
4581     *x3a = array;
4582   }
4583   /* Insert the new data */
4584   h = ph & (x3a->size-1);
4585   np = &(x3a->tbl[x3a->count++]);
4586   np->key = key;
4587   np->data = data;
4588   if( x3a->ht[h] ) x3a->ht[h]->from = &(np->next);
4589   np->next = x3a->ht[h];
4590   x3a->ht[h] = np;
4591   np->from = &(x3a->ht[h]);
4592   return 1;
4593 }
4594
4595 /* Return a pointer to data assigned to the given key.  Return NULL
4596 ** if no such key. */
4597 struct state *State_find(key)
4598 struct config *key;
4599 {
4600   int h;
4601   x3node *np;
4602
4603   if( x3a==0 ) return 0;
4604   h = statehash(key) & (x3a->size-1);
4605   np = x3a->ht[h];
4606   while( np ){
4607     if( statecmp(np->key,key)==0 ) break;
4608     np = np->next;
4609   }
4610   return np ? np->data : 0;
4611 }
4612
4613 /* Return an array of pointers to all data in the table.
4614 ** The array is obtained from malloc.  Return NULL if memory allocation
4615 ** problems, or if the array is empty. */
4616 struct state **State_arrayof()
4617 {
4618   struct state **array;
4619   int i,size;
4620   if( x3a==0 ) return 0;
4621   size = x3a->count;
4622   array = (struct state **)malloc( sizeof(struct state *)*size );
4623   if( array ){
4624     for(i=0; i<size; i++) array[i] = x3a->tbl[i].data;
4625   }
4626   return array;
4627 }
4628
4629 /* Hash a configuration */
4630 PRIVATE int confighash(a)
4631 struct config *a;
4632 {
4633   int h=0;
4634   h = h*571 + a->rp->index*37 + a->dot;
4635   return h;
4636 }
4637
4638 /* There is one instance of the following structure for each
4639 ** associative array of type "x4".
4640 */
4641 struct s_x4 {
4642   int size;               /* The number of available slots. */
4643                           /*   Must be a power of 2 greater than or */
4644                           /*   equal to 1 */
4645   int count;              /* Number of currently slots filled */
4646   struct s_x4node *tbl;  /* The data stored here */
4647   struct s_x4node **ht;  /* Hash table for lookups */
4648 };
4649
4650 /* There is one instance of this structure for every data element
4651 ** in an associative array of type "x4".
4652 */
4653 typedef struct s_x4node {
4654   struct config *data;                  /* The data */
4655   struct s_x4node *next;   /* Next entry with the same hash */
4656   struct s_x4node **from;  /* Previous link */
4657 } x4node;
4658
4659 /* There is only one instance of the array, which is the following */
4660 static struct s_x4 *x4a;
4661
4662 /* Allocate a new associative array */
4663 void Configtable_init(){
4664   if( x4a ) return;
4665   x4a = (struct s_x4*)malloc( sizeof(struct s_x4) );
4666   if( x4a ){
4667     x4a->size = 64;
4668     x4a->count = 0;
4669     x4a->tbl = (x4node*)malloc(
4670       (sizeof(x4node) + sizeof(x4node*))*64 );
4671     if( x4a->tbl==0 ){
4672       free(x4a);
4673       x4a = 0;
4674     }else{
4675       int i;
4676       x4a->ht = (x4node**)&(x4a->tbl[64]);
4677       for(i=0; i<64; i++) x4a->ht[i] = 0;
4678     }
4679   }
4680 }
4681 /* Insert a new record into the array.  Return TRUE if successful.
4682 ** Prior data with the same key is NOT overwritten */
4683 int Configtable_insert(data)
4684 struct config *data;
4685 {
4686   x4node *np;
4687   int h;
4688   int ph;
4689
4690   if( x4a==0 ) return 0;
4691   ph = confighash(data);
4692   h = ph & (x4a->size-1);
4693   np = x4a->ht[h];
4694   while( np ){
4695     if( Configcmp(np->data,data)==0 ){
4696       /* An existing entry with the same key is found. */
4697       /* Fail because overwrite is not allows. */
4698       return 0;
4699     }
4700     np = np->next;
4701   }
4702   if( x4a->count>=x4a->size ){
4703     /* Need to make the hash table bigger */
4704     int i,size;
4705     struct s_x4 array;
4706     array.size = size = x4a->size*2;
4707     array.count = x4a->count;
4708     array.tbl = (x4node*)malloc(
4709       (sizeof(x4node) + sizeof(x4node*))*size );
4710     if( array.tbl==0 ) return 0;  /* Fail due to malloc failure */
4711     array.ht = (x4node**)&(array.tbl[size]);
4712     for(i=0; i<size; i++) array.ht[i] = 0;
4713     for(i=0; i<x4a->count; i++){
4714       x4node *oldnp, *newnp;
4715       oldnp = &(x4a->tbl[i]);
4716       h = confighash(oldnp->data) & (size-1);
4717       newnp = &(array.tbl[i]);
4718       if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4719       newnp->next = array.ht[h];
4720       newnp->data = oldnp->data;
4721       newnp->from = &(array.ht[h]);
4722       array.ht[h] = newnp;
4723     }
4724     free(x4a->tbl);
4725     *x4a = array;
4726   }
4727   /* Insert the new data */
4728   h = ph & (x4a->size-1);
4729   np = &(x4a->tbl[x4a->count++]);
4730   np->data = data;
4731   if( x4a->ht[h] ) x4a->ht[h]->from = &(np->next);
4732   np->next = x4a->ht[h];
4733   x4a->ht[h] = np;
4734   np->from = &(x4a->ht[h]);
4735   return 1;
4736 }
4737
4738 /* Return a pointer to data assigned to the given key.  Return NULL
4739 ** if no such key. */
4740 struct config *Configtable_find(key)
4741 struct config *key;
4742 {
4743   int h;
4744   x4node *np;
4745
4746   if( x4a==0 ) return 0;
4747   h = confighash(key) & (x4a->size-1);
4748   np = x4a->ht[h];
4749   while( np ){
4750     if( Configcmp(np->data,key)==0 ) break;
4751     np = np->next;
4752   }
4753   return np ? np->data : 0;
4754 }
4755
4756 /* Remove all data from the table.  Pass each data to the function "f"
4757 ** as it is removed.  ("f" may be null to avoid this step.) */
4758 void Configtable_clear(f)
4759 int(*f)(/* struct config * */);
4760 {
4761   int i;
4762   if( x4a==0 || x4a->count==0 ) return;
4763   if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
4764   for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;
4765   x4a->count = 0;
4766   return;
4767 }