lac : aa0f4e3e9ca39c39ebb5fa4f3877de8e4b33c648

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

Generated by git2html.