Return to lemon.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / tool

sqlite3

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