misc/lemon.c
changeset 831 80e47b096ecd
parent 830 b15b3c3b5c4a
child 832 375ac4fcdc51
equal deleted inserted replaced
830:b15b3c3b5c4a 831:80e47b096ecd
    38 #define MAXRHS 5       /* Set low to exercise exception code */
    38 #define MAXRHS 5       /* Set low to exercise exception code */
    39 #else
    39 #else
    40 #define MAXRHS 1000
    40 #define MAXRHS 1000
    41 #endif
    41 #endif
    42 
    42 
    43 #if __MOJOSHADER__
       
    44 static const char **made_files = NULL;
    43 static const char **made_files = NULL;
    45 static int made_files_count = 0;
    44 static int made_files_count = 0;
    46 static void lemon_exit(const int status)
    45 static int successful_exit = 0;
       
    46 static void LemonAtExit(void)
    47 {
    47 {
    48     /* if we failed, delete (most) files we made, to unconfuse build tools. */
    48     /* if we failed, delete (most) files we made, to unconfuse build tools. */
    49     int i;
    49     int i;
    50     for (i = 0; i < made_files_count; i++) {
    50     for (i = 0; i < made_files_count; i++) {
    51         if (status != 0) {
    51         if (!successful_exit) {
    52             remove(made_files[i]);
    52             remove(made_files[i]);
    53         }
    53         }
    54         free((void *) made_files[i]);
    54         free((void *) made_files[i]);
    55     }
    55     }
    56     free(made_files);
    56     free(made_files);
    57     made_files_count = 0;
    57     made_files_count = 0;
    58     made_files = NULL;
    58     made_files = NULL;
    59     exit(status);
    59 }
    60 }
       
    61 #define exit(x) lemon_exit(x)
       
    62 #endif
       
    63 
    60 
    64 static char *msort(char*,char**,int(*)(const char*,const char*));
    61 static char *msort(char*,char**,int(*)(const char*,const char*));
    65 
    62 
    66 /*
    63 /*
    67 ** Compilers are getting increasingly pedantic about type conversions
    64 ** Compilers are getting increasingly pedantic about type conversions
    68 ** as C evolves ever closer to Ada....  To work around the latest problems
    65 ** as C evolves ever closer to Ada....  To work around the latest problems
    69 ** we have to define the following variant of strlen().
    66 ** we have to define the following variant of strlen().
    70 */
    67 */
    71 #define lemonStrlen(X)   ((int)strlen(X))
    68 #define lemonStrlen(X)   ((int)strlen(X))
       
    69 
       
    70 /* a few forward declarations... */
       
    71 struct rule;
       
    72 struct lemon;
       
    73 struct action;
    72 
    74 
    73 static struct action *Action_new(void);
    75 static struct action *Action_new(void);
    74 static struct action *Action_sort(struct action *);
    76 static struct action *Action_sort(struct action *);
    75 
    77 
    76 /********** From the file "build.h" ************************************/
    78 /********** From the file "build.h" ************************************/
    80 void FindLinks();
    82 void FindLinks();
    81 void FindFollowSets();
    83 void FindFollowSets();
    82 void FindActions();
    84 void FindActions();
    83 
    85 
    84 /********* From the file "configlist.h" *********************************/
    86 /********* From the file "configlist.h" *********************************/
    85 void Configlist_init(/* void */);
    87 void Configlist_init(void);
    86 struct config *Configlist_add(/* struct rule *, int */);
    88 struct config *Configlist_add(struct rule *, int);
    87 struct config *Configlist_addbasis(/* struct rule *, int */);
    89 struct config *Configlist_addbasis(struct rule *, int);
    88 void Configlist_closure(/* void */);
    90 void Configlist_closure(struct lemon *);
    89 void Configlist_sort(/* void */);
    91 void Configlist_sort(void);
    90 void Configlist_sortbasis(/* void */);
    92 void Configlist_sortbasis(void);
    91 struct config *Configlist_return(/* void */);
    93 struct config *Configlist_return(void);
    92 struct config *Configlist_basis(/* void */);
    94 struct config *Configlist_basis(void);
    93 void Configlist_eat(/* struct config * */);
    95 void Configlist_eat(struct config *);
    94 void Configlist_reset(/* void */);
    96 void Configlist_reset(void);
    95 
    97 
    96 /********* From the file "error.h" ***************************************/
    98 /********* From the file "error.h" ***************************************/
    97 void ErrorMsg(const char *, int,const char *, ...);
    99 void ErrorMsg(const char *, int,const char *, ...);
    98 
   100 
    99 /****** From the file "option.h" ******************************************/
   101 /****** From the file "option.h" ******************************************/
       
   102 enum option_type { OPT_FLAG=1,  OPT_INT,  OPT_DBL,  OPT_STR,
       
   103          OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR};
   100 struct s_options {
   104 struct s_options {
   101   enum { OPT_FLAG=1,  OPT_INT,  OPT_DBL,  OPT_STR,
   105   enum option_type type;
   102          OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;
   106   const char *label;
   103   char *label;
       
   104   char *arg;
   107   char *arg;
   105   char *message;
   108   const char *message;
   106 };
   109 };
   107 int    OptInit(/* char**,struct s_options*,FILE* */);
   110 int    OptInit(char**,struct s_options*,FILE*);
   108 int    OptNArgs(/* void */);
   111 int    OptNArgs(void);
   109 char  *OptArg(/* int */);
   112 char  *OptArg(int);
   110 void   OptErr(/* int */);
   113 void   OptErr(int);
   111 void   OptPrint(/* void */);
   114 void   OptPrint(void);
   112 
   115 
   113 /******** From the file "parse.h" *****************************************/
   116 /******** From the file "parse.h" *****************************************/
   114 void Parse(/* struct lemon *lemp */);
   117 void Parse(struct lemon *lemp);
   115 
   118 
   116 /********* From the file "plink.h" ***************************************/
   119 /********* From the file "plink.h" ***************************************/
   117 struct plink *Plink_new(/* void */);
   120 struct plink *Plink_new(void);
   118 void Plink_add(/* struct plink **, struct config * */);
   121 void Plink_add(struct plink **, struct config *);
   119 void Plink_copy(/* struct plink **, struct plink * */);
   122 void Plink_copy(struct plink **, struct plink *);
   120 void Plink_delete(/* struct plink * */);
   123 void Plink_delete(struct plink *);
   121 
   124 
   122 /********** From the file "report.h" *************************************/
   125 /********** From the file "report.h" *************************************/
   123 void Reprint(/* struct lemon * */);
   126 void Reprint(struct lemon *);
   124 void ReportOutput(/* struct lemon * */);
   127 void ReportOutput(struct lemon *);
   125 void ReportTable(/* struct lemon * */);
   128 void ReportTable(struct lemon *, int);
   126 void ReportHeader(/* struct lemon * */);
   129 void ReportHeader(struct lemon *);
   127 void CompressTables(/* struct lemon * */);
   130 void CompressTables(struct lemon *);
   128 void ResortStates(/* struct lemon * */);
   131 void ResortStates(struct lemon *);
   129 
   132 
   130 /********** From the file "set.h" ****************************************/
   133 /********** From the file "set.h" ****************************************/
   131 void  SetSize(/* int N */);             /* All sets will be of size N */
   134 void  SetSize(int);             /* All sets will be of size N */
   132 char *SetNew(/* void */);               /* A new set for element 0..N */
   135 char *SetNew(void);               /* A new set for element 0..N */
   133 void  SetFree(/* char* */);             /* Deallocate a set */
   136 void  SetFree(char*);             /* Deallocate a set */
   134 
   137 
   135 int SetAdd(/* char*,int */);            /* Add element to a set */
   138 char *SetNew(void);               /* A new set for element 0..N */
   136 int SetUnion(/* char *A,char *B */);    /* A <- A U B, thru element N */
   139 int SetAdd(char*,int);            /* Add element to a set */
   137 
   140 int SetUnion(char *,char *);    /* A <- A U B, thru element N */
   138 #define SetFind(X,Y) (X[Y])       /* True if Y is in set X */
   141 #define SetFind(X,Y) (X[Y])       /* True if Y is in set X */
   139 
   142 
   140 /********** From the file "struct.h" *************************************/
   143 /********** From the file "struct.h" *************************************/
   141 /*
   144 /*
   142 ** Principal data structures for the LEMON parser generator.
   145 ** Principal data structures for the LEMON parser generator.
   144 
   147 
   145 typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;
   148 typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;
   146 
   149 
   147 /* Symbols (terminals and nonterminals) of the grammar are stored
   150 /* Symbols (terminals and nonterminals) of the grammar are stored
   148 ** in the following: */
   151 ** in the following: */
   149 struct symbol {
   152 enum symbol_type {
   150   char *name;              /* Name of the symbol */
   153   TERMINAL,
   151   int index;               /* Index number for this symbol */
   154   NONTERMINAL,
   152   enum {
   155   MULTITERMINAL
   153     TERMINAL,
   156 };
   154     NONTERMINAL,
   157 enum e_assoc {
   155     MULTITERMINAL
       
   156   } type;                  /* Symbols are all either TERMINALS or NTs */
       
   157   struct rule *rule;       /* Linked list of rules of this (if an NT) */
       
   158   struct symbol *fallback; /* fallback token in case this token doesn't parse */
       
   159   int prec;                /* Precedence if defined (-1 otherwise) */
       
   160   enum e_assoc {
       
   161     LEFT,
   158     LEFT,
   162     RIGHT,
   159     RIGHT,
   163     NONE,
   160     NONE,
   164     UNK
   161     UNK
   165   } assoc;                 /* Associativity if precedence is defined */
   162 };
       
   163 struct symbol {
       
   164   const char *name;        /* Name of the symbol */
       
   165   int index;               /* Index number for this symbol */
       
   166   enum symbol_type type;   /* Symbols are all either TERMINALS or NTs */
       
   167   struct rule *rule;       /* Linked list of rules of this (if an NT) */
       
   168   struct symbol *fallback; /* fallback token in case this token doesn't parse */
       
   169   int prec;                /* Precedence if defined (-1 otherwise) */
       
   170   enum e_assoc assoc;      /* Associativity if precedence is defined */
   166   char *firstset;          /* First-set for all rules of this symbol */
   171   char *firstset;          /* First-set for all rules of this symbol */
   167   Boolean lambda;          /* True if NT and can generate an empty string */
   172   Boolean lambda;          /* True if NT and can generate an empty string */
   168   int useCnt;              /* Number of times used */
   173   int useCnt;              /* Number of times used */
   169   char *destructor;        /* Code which executes whenever this symbol is
   174   char *destructor;        /* Code which executes whenever this symbol is
   170                            ** popped from the stack during error processing */
   175                            ** popped from the stack during error processing */
   181 
   186 
   182 /* Each production rule in the grammar is stored in the following
   187 /* Each production rule in the grammar is stored in the following
   183 ** structure.  */
   188 ** structure.  */
   184 struct rule {
   189 struct rule {
   185   struct symbol *lhs;      /* Left-hand side of the rule */
   190   struct symbol *lhs;      /* Left-hand side of the rule */
   186   char *lhsalias;          /* Alias for the LHS (NULL if none) */
   191   const char *lhsalias;    /* Alias for the LHS (NULL if none) */
   187   int lhsStart;            /* True if left-hand side is the start symbol */
   192   int lhsStart;            /* True if left-hand side is the start symbol */
   188   int ruleline;            /* Line number for the rule */
   193   int ruleline;            /* Line number for the rule */
   189   int nrhs;                /* Number of RHS symbols */
   194   int nrhs;                /* Number of RHS symbols */
   190   struct symbol **rhs;     /* The RHS symbols */
   195   struct symbol **rhs;     /* The RHS symbols */
   191   char **rhsalias;         /* An alias for each RHS symbol (NULL if none) */
   196   const char **rhsalias;   /* An alias for each RHS symbol (NULL if none) */
   192   int line;                /* Line number at which code begins */
   197   int line;                /* Line number at which code begins */
   193   char *code;              /* The code executed when this rule is reduced */
   198   const char *code;        /* The code executed when this rule is reduced */
   194   struct symbol *precsym;  /* Precedence symbol for this rule */
   199   struct symbol *precsym;  /* Precedence symbol for this rule */
   195   int index;               /* An index number for this rule */
   200   int index;               /* An index number for this rule */
   196   Boolean canReduce;       /* True if this rule is ever reduced */
   201   Boolean canReduce;       /* True if this rule is ever reduced */
   197   struct rule *nextlhs;    /* Next rule with the same LHS */
   202   struct rule *nextlhs;    /* Next rule with the same LHS */
   198   struct rule *next;       /* Next rule in the global list */
   203   struct rule *next;       /* Next rule in the global list */
   201 /* A configuration is a production rule of the grammar together with
   206 /* A configuration is a production rule of the grammar together with
   202 ** a mark (dot) showing how much of that rule has been processed so far.
   207 ** a mark (dot) showing how much of that rule has been processed so far.
   203 ** Configurations also contain a follow-set which is a list of terminal
   208 ** Configurations also contain a follow-set which is a list of terminal
   204 ** symbols which are allowed to immediately follow the end of the rule.
   209 ** symbols which are allowed to immediately follow the end of the rule.
   205 ** Every configuration is recorded as an instance of the following: */
   210 ** Every configuration is recorded as an instance of the following: */
       
   211 enum cfgstatus {
       
   212   COMPLETE,
       
   213   INCOMPLETE
       
   214 };
   206 struct config {
   215 struct config {
   207   struct rule *rp;         /* The rule upon which the configuration is based */
   216   struct rule *rp;         /* The rule upon which the configuration is based */
   208   int dot;                 /* The parse point */
   217   int dot;                 /* The parse point */
   209   char *fws;               /* Follow-set for this configuration only */
   218   char *fws;               /* Follow-set for this configuration only */
   210   struct plink *fplp;      /* Follow-set forward propagation links */
   219   struct plink *fplp;      /* Follow-set forward propagation links */
   211   struct plink *bplp;      /* Follow-set backwards propagation links */
   220   struct plink *bplp;      /* Follow-set backwards propagation links */
   212   struct state *stp;       /* Pointer to state which contains this */
   221   struct state *stp;       /* Pointer to state which contains this */
   213   enum {
   222   enum cfgstatus status;   /* used during followset and shift computations */
   214     COMPLETE,              /* The status is used during followset and */
       
   215     INCOMPLETE             /*    shift computations */
       
   216   } status;
       
   217   struct config *next;     /* Next configuration in the state */
   223   struct config *next;     /* Next configuration in the state */
   218   struct config *bp;       /* The next basis configuration */
   224   struct config *bp;       /* The next basis configuration */
   219 };
   225 };
   220 
   226 
       
   227 enum e_action {
       
   228   SHIFT,
       
   229   ACCEPT,
       
   230   REDUCE,
       
   231   ERROR,
       
   232   SSCONFLICT,              /* A shift/shift conflict */
       
   233   SRCONFLICT,              /* Was a reduce, but part of a conflict */
       
   234   RRCONFLICT,              /* Was a reduce, but part of a conflict */
       
   235   SH_RESOLVED,             /* Was a shift.  Precedence resolved conflict */
       
   236   RD_RESOLVED,             /* Was reduce.  Precedence resolved conflict */
       
   237   NOT_USED                 /* Deleted by compression */
       
   238 };
       
   239 
   221 /* Every shift or reduce operation is stored as one of the following */
   240 /* Every shift or reduce operation is stored as one of the following */
   222 struct action {
   241 struct action {
   223   struct symbol *sp;       /* The look-ahead symbol */
   242   struct symbol *sp;       /* The look-ahead symbol */
   224   enum e_action {
   243   enum e_action type;
   225     SHIFT,
       
   226     ACCEPT,
       
   227     REDUCE,
       
   228     ERROR,
       
   229     SSCONFLICT,              /* A shift/shift conflict */
       
   230     SRCONFLICT,              /* Was a reduce, but part of a conflict */
       
   231     RRCONFLICT,              /* Was a reduce, but part of a conflict */
       
   232     SH_RESOLVED,             /* Was a shift.  Precedence resolved conflict */
       
   233     RD_RESOLVED,             /* Was reduce.  Precedence resolved conflict */
       
   234     NOT_USED                 /* Deleted by compression */
       
   235   } type;
       
   236   union {
   244   union {
   237     struct state *stp;     /* The new state, if a shift */
   245     struct state *stp;     /* The new state, if a shift */
   238     struct rule *rp;       /* The rule, if a reduce */
   246     struct rule *rp;       /* The rule, if a reduce */
   239   } x;
   247   } x;
   240   struct action *next;     /* Next action for this state */
   248   struct action *next;     /* Next action for this state */
   320 ** file, then rerun aagen.
   328 ** file, then rerun aagen.
   321 */
   329 */
   322 /*
   330 /*
   323 ** Code for processing tables in the LEMON parser generator.
   331 ** Code for processing tables in the LEMON parser generator.
   324 */
   332 */
   325 
       
   326 /* Routines for handling a strings */
   333 /* Routines for handling a strings */
   327 
   334 
   328 char *Strsafe();
   335 const char *Strsafe(const char *);
   329 
   336 
   330 void Strsafe_init(/* void */);
   337 void Strsafe_init(void);
   331 int Strsafe_insert(/* char * */);
   338 int Strsafe_insert(const char *);
   332 char *Strsafe_find(/* char * */);
   339 const char *Strsafe_find(const char *);
   333 
   340 
   334 /* Routines for handling symbols of the grammar */
   341 /* Routines for handling symbols of the grammar */
   335 
   342 
   336 struct symbol *Symbol_new();
   343 struct symbol *Symbol_new(const char *);
   337 int Symbolcmpp(/* struct symbol **, struct symbol ** */);
   344 int Symbolcmpp(const void *, const void *);
   338 void Symbol_init(/* void */);
   345 void Symbol_init(void);
   339 int Symbol_insert(/* struct symbol *, char * */);
   346 int Symbol_insert(struct symbol *, const char *);
   340 struct symbol *Symbol_find(/* char * */);
   347 struct symbol *Symbol_find(const char *);
   341 struct symbol *Symbol_Nth(/* int */);
   348 struct symbol *Symbol_Nth(int);
   342 int Symbol_count(/*  */);
   349 int Symbol_count(void);
   343 struct symbol **Symbol_arrayof(/*  */);
   350 struct symbol **Symbol_arrayof(void);
   344 
   351 
   345 /* Routines to manage the state table */
   352 /* Routines to manage the state table */
   346 
   353 
   347 int Configcmp(/* struct config *, struct config * */);
   354 int Configcmp(const char *, const char *);
   348 struct state *State_new();
   355 struct state *State_new(void);
   349 void State_init(/* void */);
   356 void State_init(void);
   350 int State_insert(/* struct state *, struct config * */);
   357 int State_insert(struct state *, struct config *);
   351 struct state *State_find(/* struct config * */);
   358 struct state *State_find(struct config *);
   352 struct state **State_arrayof(/*  */);
   359 struct state **State_arrayof(/*  */);
   353 
   360 
   354 /* Routines used for efficiency in Configlist_add */
   361 /* Routines used for efficiency in Configlist_add */
   355 
   362 
   356 void Configtable_init(/* void */);
   363 void Configtable_init(void);
   357 int Configtable_insert(/* struct config * */);
   364 int Configtable_insert(struct config *);
   358 struct config *Configtable_find(/* struct config * */);
   365 struct config *Configtable_find(struct config *);
   359 void Configtable_clear(/* int(*)(struct config *) */);
   366 void Configtable_clear(int(*)(struct config *));
       
   367 
   360 /****************** From the file "action.c" *******************************/
   368 /****************** From the file "action.c" *******************************/
   361 /*
   369 /*
   362 ** Routines processing parser actions in the LEMON parser generator.
   370 ** Routines processing parser actions in the LEMON parser generator.
   363 */
   371 */
   364 
   372 
   365 /* Allocate a new parser action */
   373 /* Allocate a new parser action */
   366 static struct action *Action_new(void){
   374 static struct action *Action_new(void){
   367   static struct action *freelist = 0;
   375   static struct action *freelist = 0;
   368   struct action *new;
   376   struct action *newaction;
   369 
   377 
   370   if( freelist==0 ){
   378   if( freelist==0 ){
   371     int i;
   379     int i;
   372     int amt = 100;
   380     int amt = 100;
   373     freelist = (struct action *)calloc(amt, sizeof(struct action));
   381     freelist = (struct action *)calloc(amt, sizeof(struct action));
   376       exit(1);
   384       exit(1);
   377     }
   385     }
   378     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
   386     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
   379     freelist[amt-1].next = 0;
   387     freelist[amt-1].next = 0;
   380   }
   388   }
   381   new = freelist;
   389   newaction = freelist;
   382   freelist = freelist->next;
   390   freelist = freelist->next;
   383   return new;
   391   return newaction;
   384 }
   392 }
   385 
   393 
   386 /* Compare two actions for sorting purposes.  Return negative, zero, or
   394 /* Compare two actions for sorting purposes.  Return negative, zero, or
   387 ** positive if the first action is less than, equal to, or greater than
   395 ** positive if the first action is less than, equal to, or greater than
   388 ** the first
   396 ** the first
   397     rc = (int)ap1->type - (int)ap2->type;
   405     rc = (int)ap1->type - (int)ap2->type;
   398   }
   406   }
   399   if( rc==0 && ap1->type==REDUCE ){
   407   if( rc==0 && ap1->type==REDUCE ){
   400     rc = ap1->x.rp->index - ap2->x.rp->index;
   408     rc = ap1->x.rp->index - ap2->x.rp->index;
   401   }
   409   }
       
   410   if( rc==0 ){
       
   411     rc = ap2 - ap1;
       
   412   }
   402   return rc;
   413   return rc;
   403 }
   414 }
   404 
   415 
   405 /* Sort parser actions */
   416 /* Sort parser actions */
   406 static struct action *Action_sort(
   417 static struct action *Action_sort(
   409   ap = (struct action *)msort((char *)ap,(char **)&ap->next,
   420   ap = (struct action *)msort((char *)ap,(char **)&ap->next,
   410                               (int(*)(const char*,const char*))actioncmp);
   421                               (int(*)(const char*,const char*))actioncmp);
   411   return ap;
   422   return ap;
   412 }
   423 }
   413 
   424 
   414 void Action_add(app,type,sp,arg)
   425 void Action_add(
   415 struct action **app;
   426   struct action **app,
   416 enum e_action type;
   427   enum e_action type,
   417 struct symbol *sp;
   428   struct symbol *sp,
   418 char *arg;
   429   char *arg
   419 {
   430 ){
   420   struct action *new;
   431   struct action *newaction;
   421   new = Action_new();
   432   newaction = Action_new();
   422   new->next = *app;
   433   newaction->next = *app;
   423   *app = new;
   434   *app = newaction;
   424   new->type = type;
   435   newaction->type = type;
   425   new->sp = sp;
   436   newaction->sp = sp;
   426   if( type==SHIFT ){
   437   if( type==SHIFT ){
   427     new->x.stp = (struct state *)arg;
   438     newaction->x.stp = (struct state *)arg;
   428   }else{
   439   }else{
   429     new->x.rp = (struct rule *)arg;
   440     newaction->x.rp = (struct rule *)arg;
   430   }
   441   }
   431 }
   442 }
   432 /********************** New code to implement the "acttab" module ***********/
   443 /********************** New code to implement the "acttab" module ***********/
   433 /*
   444 /*
   434 ** This module implements routines use to construct the yy_action[] table.
   445 ** This module implements routines use to construct the yy_action[] table.
   435 */
   446 */
   436 
   447 
   437 /*
   448 /*
   438 ** The state of the yy_action table under construction is an instance of
   449 ** The state of the yy_action table under construction is an instance of
   439 ** the following structure
   450 ** the following structure.
   440 */
   451 **
       
   452 ** The yy_action table maps the pair (state_number, lookahead) into an
       
   453 ** action_number.  The table is an array of integers pairs.  The state_number
       
   454 ** determines an initial offset into the yy_action array.  The lookahead
       
   455 ** value is then added to this initial offset to get an index X into the
       
   456 ** yy_action array. If the aAction[X].lookahead equals the value of the
       
   457 ** of the lookahead input, then the value of the action_number output is
       
   458 ** aAction[X].action.  If the lookaheads do not match then the
       
   459 ** default action for the state_number is returned.
       
   460 **
       
   461 ** All actions associated with a single state_number are first entered
       
   462 ** into aLookahead[] using multiple calls to acttab_action().  Then the 
       
   463 ** actions for that single state_number are placed into the aAction[] 
       
   464 ** array with a single call to acttab_insert().  The acttab_insert() call
       
   465 ** also resets the aLookahead[] array in preparation for the next
       
   466 ** state number.
       
   467 */
       
   468 struct lookahead_action {
       
   469   int lookahead;             /* Value of the lookahead token */
       
   470   int action;                /* Action to take on the given lookahead */
       
   471 };
   441 typedef struct acttab acttab;
   472 typedef struct acttab acttab;
   442 struct acttab {
   473 struct acttab {
   443   int nAction;                 /* Number of used slots in aAction[] */
   474   int nAction;                 /* Number of used slots in aAction[] */
   444   int nActionAlloc;            /* Slots allocated for aAction[] */
   475   int nActionAlloc;            /* Slots allocated for aAction[] */
   445   struct {
   476   struct lookahead_action
   446     int lookahead;             /* Value of the lookahead token */
   477     *aAction,                  /* The yy_action[] table under construction */
   447     int action;                /* Action to take on the given lookahead */
       
   448   } *aAction,                  /* The yy_action[] table under construction */
       
   449     *aLookahead;               /* A single new transaction set */
   478     *aLookahead;               /* A single new transaction set */
   450   int mnLookahead;             /* Minimum aLookahead[].lookahead */
   479   int mnLookahead;             /* Minimum aLookahead[].lookahead */
   451   int mnAction;                /* Action associated with mnLookahead */
   480   int mnAction;                /* Action associated with mnLookahead */
   452   int mxLookahead;             /* Maximum aLookahead[].lookahead */
   481   int mxLookahead;             /* Maximum aLookahead[].lookahead */
   453   int nLookahead;              /* Used slots in aLookahead[] */
   482   int nLookahead;              /* Used slots in aLookahead[] */
   470   free( p );
   499   free( p );
   471 }
   500 }
   472 
   501 
   473 /* Allocate a new acttab structure */
   502 /* Allocate a new acttab structure */
   474 acttab *acttab_alloc(void){
   503 acttab *acttab_alloc(void){
   475   acttab *p = calloc( 1, sizeof(*p) );
   504   acttab *p = (acttab *) calloc( 1, sizeof(*p) );
   476   if( p==0 ){
   505   if( p==0 ){
   477     fprintf(stderr,"Unable to allocate memory for a new acttab.");
   506     fprintf(stderr,"Unable to allocate memory for a new acttab.");
   478     exit(1);
   507     exit(1);
   479   }
   508   }
   480   memset(p, 0, sizeof(*p));
   509   memset(p, 0, sizeof(*p));
   481   return p;
   510   return p;
   482 }
   511 }
   483 
   512 
   484 /* Add a new action to the current transaction set
   513 /* Add a new action to the current transaction set.  
       
   514 **
       
   515 ** This routine is called once for each lookahead for a particular
       
   516 ** state.
   485 */
   517 */
   486 void acttab_action(acttab *p, int lookahead, int action){
   518 void acttab_action(acttab *p, int lookahead, int action){
   487   if( p->nLookahead>=p->nLookaheadAlloc ){
   519   if( p->nLookahead>=p->nLookaheadAlloc ){
   488     p->nLookaheadAlloc += 25;
   520     p->nLookaheadAlloc += 25;
   489     p->aLookahead = realloc( p->aLookahead,
   521     p->aLookahead = (struct lookahead_action *) realloc( p->aLookahead,
   490                              sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
   522                              sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
   491     if( p->aLookahead==0 ){
   523     if( p->aLookahead==0 ){
   492       fprintf(stderr,"malloc failed\n");
   524       fprintf(stderr,"malloc failed\n");
   493       exit(1);
   525       exit(1);
   494     }
   526     }
   526   */
   558   */
   527   n = p->mxLookahead + 1;
   559   n = p->mxLookahead + 1;
   528   if( p->nAction + n >= p->nActionAlloc ){
   560   if( p->nAction + n >= p->nActionAlloc ){
   529     int oldAlloc = p->nActionAlloc;
   561     int oldAlloc = p->nActionAlloc;
   530     p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
   562     p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
   531     p->aAction = realloc( p->aAction,
   563     p->aAction = (struct lookahead_action *) realloc( p->aAction,
   532                           sizeof(p->aAction[0])*p->nActionAlloc);
   564                           sizeof(p->aAction[0])*p->nActionAlloc);
   533     if( p->aAction==0 ){
   565     if( p->aAction==0 ){
   534       fprintf(stderr,"malloc failed\n");
   566       fprintf(stderr,"malloc failed\n");
   535       exit(1);
   567       exit(1);
   536     }
   568     }
   538       p->aAction[i].lookahead = -1;
   570       p->aAction[i].lookahead = -1;
   539       p->aAction[i].action = -1;
   571       p->aAction[i].action = -1;
   540     }
   572     }
   541   }
   573   }
   542 
   574 
   543   /* Scan the existing action table looking for an offset where we can
   575   /* Scan the existing action table looking for an offset that is a 
   544   ** insert the current transaction set.  Fall out of the loop when that
   576   ** duplicate of the current transaction set.  Fall out of the loop
   545   ** offset is found.  In the worst case, we fall out of the loop when
   577   ** if and when the duplicate is found.
   546   ** i reaches p->nAction, which means we append the new transaction set.
       
   547   **
   578   **
   548   ** i is the index in p->aAction[] where p->mnLookahead is inserted.
   579   ** i is the index in p->aAction[] where p->mnLookahead is inserted.
   549   */
   580   */
   550   for(i=0; i<p->nAction+p->mnLookahead; i++){
   581   for(i=p->nAction-1; i>=0; i--){
   551     if( p->aAction[i].lookahead<0 ){
   582     if( p->aAction[i].lookahead==p->mnLookahead ){
   552       for(j=0; j<p->nLookahead; j++){
   583       /* All lookaheads and actions in the aLookahead[] transaction
   553         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   584       ** must match against the candidate aAction[i] entry. */
   554         if( k<0 ) break;
       
   555         if( p->aAction[k].lookahead>=0 ) break;
       
   556       }
       
   557       if( j<p->nLookahead ) continue;
       
   558       for(j=0; j<p->nAction; j++){
       
   559         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
       
   560       }
       
   561       if( j==p->nAction ){
       
   562         break;  /* Fits in empty slots */
       
   563       }
       
   564     }else if( p->aAction[i].lookahead==p->mnLookahead ){
       
   565       if( p->aAction[i].action!=p->mnAction ) continue;
   585       if( p->aAction[i].action!=p->mnAction ) continue;
   566       for(j=0; j<p->nLookahead; j++){
   586       for(j=0; j<p->nLookahead; j++){
   567         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   587         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   568         if( k<0 || k>=p->nAction ) break;
   588         if( k<0 || k>=p->nAction ) break;
   569         if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
   589         if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
   570         if( p->aLookahead[j].action!=p->aAction[k].action ) break;
   590         if( p->aLookahead[j].action!=p->aAction[k].action ) break;
   571       }
   591       }
   572       if( j<p->nLookahead ) continue;
   592       if( j<p->nLookahead ) continue;
       
   593 
       
   594       /* No possible lookahead value that is not in the aLookahead[]
       
   595       ** transaction is allowed to match aAction[i] */
   573       n = 0;
   596       n = 0;
   574       for(j=0; j<p->nAction; j++){
   597       for(j=0; j<p->nAction; j++){
   575         if( p->aAction[j].lookahead<0 ) continue;
   598         if( p->aAction[j].lookahead<0 ) continue;
   576         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
   599         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
   577       }
   600       }
   578       if( n==p->nLookahead ){
   601       if( n==p->nLookahead ){
   579         break;  /* Same as a prior transaction set */
   602         break;  /* An exact match is found at offset i */
       
   603       }
       
   604     }
       
   605   }
       
   606 
       
   607   /* If no existing offsets exactly match the current transaction, find an
       
   608   ** an empty offset in the aAction[] table in which we can add the
       
   609   ** aLookahead[] transaction.
       
   610   */
       
   611   if( i<0 ){
       
   612     /* Look for holes in the aAction[] table that fit the current
       
   613     ** aLookahead[] transaction.  Leave i set to the offset of the hole.
       
   614     ** If no holes are found, i is left at p->nAction, which means the
       
   615     ** transaction will be appended. */
       
   616     for(i=0; i<p->nActionAlloc - p->mxLookahead; i++){
       
   617       if( p->aAction[i].lookahead<0 ){
       
   618         for(j=0; j<p->nLookahead; j++){
       
   619           k = p->aLookahead[j].lookahead - p->mnLookahead + i;
       
   620           if( k<0 ) break;
       
   621           if( p->aAction[k].lookahead>=0 ) break;
       
   622         }
       
   623         if( j<p->nLookahead ) continue;
       
   624         for(j=0; j<p->nAction; j++){
       
   625           if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
       
   626         }
       
   627         if( j==p->nAction ){
       
   628           break;  /* Fits in empty slots */
       
   629         }
   580       }
   630       }
   581     }
   631     }
   582   }
   632   }
   583   /* Insert transaction set at index i. */
   633   /* Insert transaction set at index i. */
   584   for(j=0; j<p->nLookahead; j++){
   634   for(j=0; j<p->nLookahead; j++){
   606 ** rp->precsym field filled.  Other rules take as their precedence
   656 ** rp->precsym field filled.  Other rules take as their precedence
   607 ** symbol the first RHS symbol with a defined precedence.  If there
   657 ** symbol the first RHS symbol with a defined precedence.  If there
   608 ** are not RHS symbols with a defined precedence, the precedence
   658 ** are not RHS symbols with a defined precedence, the precedence
   609 ** symbol field is left blank.
   659 ** symbol field is left blank.
   610 */
   660 */
   611 void FindRulePrecedences(xp)
   661 void FindRulePrecedences(struct lemon *xp)
   612 struct lemon *xp;
       
   613 {
   662 {
   614   struct rule *rp;
   663   struct rule *rp;
   615   for(rp=xp->rule; rp; rp=rp->next){
   664   for(rp=xp->rule; rp; rp=rp->next){
   616     if( rp->precsym==0 ){
   665     if( rp->precsym==0 ){
   617       int i, j;
   666       int i, j;
   636 /* Find all nonterminals which will generate the empty string.
   685 /* Find all nonterminals which will generate the empty string.
   637 ** Then go back and compute the first sets of every nonterminal.
   686 ** Then go back and compute the first sets of every nonterminal.
   638 ** The first set is the set of all terminal symbols which can begin
   687 ** The first set is the set of all terminal symbols which can begin
   639 ** a string generated by that nonterminal.
   688 ** a string generated by that nonterminal.
   640 */
   689 */
   641 void FindFirstSets(lemp)
   690 void FindFirstSets(struct lemon *lemp)
   642 struct lemon *lemp;
       
   643 {
   691 {
   644   int i, j;
   692   int i, j;
   645   struct rule *rp;
   693   struct rule *rp;
   646   int progress;
   694   int progress;
   647 
   695 
   698 
   746 
   699 /* Compute all LR(0) states for the grammar.  Links
   747 /* Compute all LR(0) states for the grammar.  Links
   700 ** are added to between some states so that the LR(1) follow sets
   748 ** are added to between some states so that the LR(1) follow sets
   701 ** can be computed later.
   749 ** can be computed later.
   702 */
   750 */
   703 PRIVATE struct state *getstate(/* struct lemon * */);  /* forward reference */
   751 PRIVATE struct state *getstate(struct lemon *);  /* forward reference */
   704 void FindStates(lemp)
   752 void FindStates(struct lemon *lemp)
   705 struct lemon *lemp;
       
   706 {
   753 {
   707   struct symbol *sp;
   754   struct symbol *sp;
   708   struct rule *rp;
   755   struct rule *rp;
   709 
   756 
   710   Configlist_init();
   757   Configlist_init();
   758 }
   805 }
   759 
   806 
   760 /* Return a pointer to a state which is described by the configuration
   807 /* Return a pointer to a state which is described by the configuration
   761 ** list which has been built from calls to Configlist_add.
   808 ** list which has been built from calls to Configlist_add.
   762 */
   809 */
   763 PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */
   810 PRIVATE void buildshifts(struct lemon *, struct state *); /* Forwd ref */
   764 PRIVATE struct state *getstate(lemp)
   811 PRIVATE struct state *getstate(struct lemon *lemp)
   765 struct lemon *lemp;
       
   766 {
   812 {
   767   struct config *cfp, *bp;
   813   struct config *cfp, *bp;
   768   struct state *stp;
   814   struct state *stp;
   769 
   815 
   770   /* Extract the sorted basis of the new state.  The basis was constructed
   816   /* Extract the sorted basis of the new state.  The basis was constructed
   804 }
   850 }
   805 
   851 
   806 /*
   852 /*
   807 ** Return true if two symbols are the same.
   853 ** Return true if two symbols are the same.
   808 */
   854 */
   809 int same_symbol(a,b)
   855 int same_symbol(struct symbol *a, struct symbol *b)
   810 struct symbol *a;
       
   811 struct symbol *b;
       
   812 {
   856 {
   813   int i;
   857   int i;
   814   if( a==b ) return 1;
   858   if( a==b ) return 1;
   815   if( a->type!=MULTITERMINAL ) return 0;
   859   if( a->type!=MULTITERMINAL ) return 0;
   816   if( b->type!=MULTITERMINAL ) return 0;
   860   if( b->type!=MULTITERMINAL ) return 0;
   822 }
   866 }
   823 
   867 
   824 /* Construct all successor states to the given state.  A "successor"
   868 /* Construct all successor states to the given state.  A "successor"
   825 ** state is any state which can be reached by a shift action.
   869 ** state is any state which can be reached by a shift action.
   826 */
   870 */
   827 PRIVATE void buildshifts(lemp,stp)
   871 PRIVATE void buildshifts(struct lemon *lemp, struct state *stp)
   828 struct lemon *lemp;
       
   829 struct state *stp;     /* The state from which successors are computed */
       
   830 {
   872 {
   831   struct config *cfp;  /* For looping thru the config closure of "stp" */
   873   struct config *cfp;  /* For looping thru the config closure of "stp" */
   832   struct config *bcfp; /* For the inner loop on config closure of "stp" */
   874   struct config *bcfp; /* For the inner loop on config closure of "stp" */
   833   struct config *new;  /* */
   875   struct config *newcfg;  /* */
   834   struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */
   876   struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */
   835   struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */
   877   struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */
   836   struct state *newstp; /* A pointer to a successor state */
   878   struct state *newstp; /* A pointer to a successor state */
   837 
   879 
   838   /* Each configuration becomes complete after it contibutes to a successor
   880   /* Each configuration becomes complete after it contibutes to a successor
   853       if( bcfp->status==COMPLETE ) continue;    /* Already used */
   895       if( bcfp->status==COMPLETE ) continue;    /* Already used */
   854       if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
   896       if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
   855       bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
   897       bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
   856       if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */
   898       if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */
   857       bcfp->status = COMPLETE;                  /* Mark this config as used */
   899       bcfp->status = COMPLETE;                  /* Mark this config as used */
   858       new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
   900       newcfg = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
   859       Plink_add(&new->bplp,bcfp);
   901       Plink_add(&newcfg->bplp,bcfp);
   860     }
   902     }
   861 
   903 
   862     /* Get a pointer to the state described by the basis configuration set
   904     /* Get a pointer to the state described by the basis configuration set
   863     ** constructed in the preceding loop */
   905     ** constructed in the preceding loop */
   864     newstp = getstate(lemp);
   906     newstp = getstate(lemp);
   877 }
   919 }
   878 
   920 
   879 /*
   921 /*
   880 ** Construct the propagation links
   922 ** Construct the propagation links
   881 */
   923 */
   882 void FindLinks(lemp)
   924 void FindLinks(struct lemon *lemp)
   883 struct lemon *lemp;
       
   884 {
   925 {
   885   int i;
   926   int i;
   886   struct config *cfp, *other;
   927   struct config *cfp, *other;
   887   struct state *stp;
   928   struct state *stp;
   888   struct plink *plp;
   929   struct plink *plp;
   913 /* Compute all followsets.
   954 /* Compute all followsets.
   914 **
   955 **
   915 ** A followset is the set of all symbols which can come immediately
   956 ** A followset is the set of all symbols which can come immediately
   916 ** after a configuration.
   957 ** after a configuration.
   917 */
   958 */
   918 void FindFollowSets(lemp)
   959 void FindFollowSets(struct lemon *lemp)
   919 struct lemon *lemp;
       
   920 {
   960 {
   921   int i;
   961   int i;
   922   struct config *cfp;
   962   struct config *cfp;
   923   struct plink *plp;
   963   struct plink *plp;
   924   int progress;
   964   int progress;
   946       }
   986       }
   947     }
   987     }
   948   }while( progress );
   988   }while( progress );
   949 }
   989 }
   950 
   990 
   951 static int resolve_conflict();
   991 static int resolve_conflict(struct action *,struct action *, struct symbol *);
   952 
   992 
   953 /* Compute the reduce actions, and resolve conflicts.
   993 /* Compute the reduce actions, and resolve conflicts.
   954 */
   994 */
   955 void FindActions(lemp)
   995 void FindActions(struct lemon *lemp)
   956 struct lemon *lemp;
       
   957 {
   996 {
   958   int i,j;
   997   int i,j;
   959   struct config *cfp;
   998   struct config *cfp;
   960   struct state *stp;
   999   struct state *stp;
   961   struct symbol *sp;
  1000   struct symbol *sp;
  1034 **   use precedence to resolve the conflict.
  1073 **   use precedence to resolve the conflict.
  1035 **
  1074 **
  1036 ** If either action is a SHIFT, then it must be apx.  This
  1075 ** If either action is a SHIFT, then it must be apx.  This
  1037 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
  1076 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
  1038 */
  1077 */
  1039 static int resolve_conflict(apx,apy,errsym)
  1078 static int resolve_conflict(
  1040 struct action *apx;
  1079   struct action *apx,
  1041 struct action *apy;
  1080   struct action *apy,
  1042 struct symbol *errsym;   /* The error symbol (if defined.  NULL otherwise) */
  1081   struct symbol *errsym   /* The error symbol (if defined.  NULL otherwise) */
  1043 {
  1082 ){
  1044   struct symbol *spx, *spy;
  1083   struct symbol *spx, *spy;
  1045   int errcnt = 0;
  1084   int errcnt = 0;
  1046   assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
  1085   assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
  1047   if( apx->type==SHIFT && apy->type==SHIFT ){
  1086   if( apx->type==SHIFT && apy->type==SHIFT ){
  1048     apy->type = SSCONFLICT;
  1087     apy->type = SSCONFLICT;
  1111 static struct config *basis = 0;         /* Top of list of basis configs */
  1150 static struct config *basis = 0;         /* Top of list of basis configs */
  1112 static struct config **basisend = 0;     /* End of list of basis configs */
  1151 static struct config **basisend = 0;     /* End of list of basis configs */
  1113 
  1152 
  1114 /* Return a pointer to a new configuration */
  1153 /* Return a pointer to a new configuration */
  1115 PRIVATE struct config *newconfig(){
  1154 PRIVATE struct config *newconfig(){
  1116   struct config *new;
  1155   struct config *newcfg;
  1117   if( freelist==0 ){
  1156   if( freelist==0 ){
  1118     int i;
  1157     int i;
  1119     int amt = 3;
  1158     int amt = 3;
  1120     freelist = (struct config *)calloc( amt, sizeof(struct config) );
  1159     freelist = (struct config *)calloc( amt, sizeof(struct config) );
  1121     if( freelist==0 ){
  1160     if( freelist==0 ){
  1123       exit(1);
  1162       exit(1);
  1124     }
  1163     }
  1125     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
  1164     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
  1126     freelist[amt-1].next = 0;
  1165     freelist[amt-1].next = 0;
  1127   }
  1166   }
  1128   new = freelist;
  1167   newcfg = freelist;
  1129   freelist = freelist->next;
  1168   freelist = freelist->next;
  1130   return new;
  1169   return newcfg;
  1131 }
  1170 }
  1132 
  1171 
  1133 /* The configuration "old" is no longer used */
  1172 /* The configuration "old" is no longer used */
  1134 PRIVATE void deleteconfig(old)
  1173 PRIVATE void deleteconfig(struct config *old)
  1135 struct config *old;
       
  1136 {
  1174 {
  1137   old->next = freelist;
  1175   old->next = freelist;
  1138   freelist = old;
  1176   freelist = old;
  1139 }
  1177 }
  1140 
  1178 
  1157   Configtable_clear(0);
  1195   Configtable_clear(0);
  1158   return;
  1196   return;
  1159 }
  1197 }
  1160 
  1198 
  1161 /* Add another configuration to the configuration list */
  1199 /* Add another configuration to the configuration list */
  1162 struct config *Configlist_add(rp,dot)
  1200 struct config *Configlist_add(
  1163 struct rule *rp;    /* The rule */
  1201   struct rule *rp,    /* The rule */
  1164 int dot;            /* Index into the RHS of the rule where the dot goes */
  1202   int dot             /* Index into the RHS of the rule where the dot goes */
  1165 {
  1203 ){
  1166   struct config *cfp, model;
  1204   struct config *cfp, model;
  1167 
  1205 
  1168   assert( currentend!=0 );
  1206   assert( currentend!=0 );
  1169   model.rp = rp;
  1207   model.rp = rp;
  1170   model.dot = dot;
  1208   model.dot = dot;
  1184   }
  1222   }
  1185   return cfp;
  1223   return cfp;
  1186 }
  1224 }
  1187 
  1225 
  1188 /* Add a basis configuration to the configuration list */
  1226 /* Add a basis configuration to the configuration list */
  1189 struct config *Configlist_addbasis(rp,dot)
  1227 struct config *Configlist_addbasis(struct rule *rp, int dot)
  1190 struct rule *rp;
       
  1191 int dot;
       
  1192 {
  1228 {
  1193   struct config *cfp, model;
  1229   struct config *cfp, model;
  1194 
  1230 
  1195   assert( basisend!=0 );
  1231   assert( basisend!=0 );
  1196   assert( currentend!=0 );
  1232   assert( currentend!=0 );
  1214   }
  1250   }
  1215   return cfp;
  1251   return cfp;
  1216 }
  1252 }
  1217 
  1253 
  1218 /* Compute the closure of the configuration list */
  1254 /* Compute the closure of the configuration list */
  1219 void Configlist_closure(lemp)
  1255 void Configlist_closure(struct lemon *lemp)
  1220 struct lemon *lemp;
       
  1221 {
  1256 {
  1222   struct config *cfp, *newcfp;
  1257   struct config *cfp, *newcfp;
  1223   struct rule *rp, *newrp;
  1258   struct rule *rp, *newrp;
  1224   struct symbol *sp, *xsp;
  1259   struct symbol *sp, *xsp;
  1225   int i, dot;
  1260   int i, dot;
  1294   basisend = 0;
  1329   basisend = 0;
  1295   return old;
  1330   return old;
  1296 }
  1331 }
  1297 
  1332 
  1298 /* Free all elements of the given configuration list */
  1333 /* Free all elements of the given configuration list */
  1299 void Configlist_eat(cfp)
  1334 void Configlist_eat(struct config *cfp)
  1300 struct config *cfp;
       
  1301 {
  1335 {
  1302   struct config *nextcfp;
  1336   struct config *nextcfp;
  1303   for(; cfp; cfp=nextcfp){
  1337   for(; cfp; cfp=nextcfp){
  1304     nextcfp = cfp->next;
  1338     nextcfp = cfp->next;
  1305     assert( cfp->fplp==0 );
  1339     assert( cfp->fplp==0 );
  1312 /***************** From the file "error.c" *********************************/
  1346 /***************** From the file "error.c" *********************************/
  1313 /*
  1347 /*
  1314 ** Code for printing error message.
  1348 ** Code for printing error message.
  1315 */
  1349 */
  1316 
  1350 
  1317 /* Find a good place to break "msg" so that its length is at least "min"
       
  1318 ** but no more than "max".  Make the point as close to max as possible.
       
  1319 */
       
  1320 static int findbreak(msg,min,max)
       
  1321 char *msg;
       
  1322 int min;
       
  1323 int max;
       
  1324 {
       
  1325   int i,spot;
       
  1326   char c;
       
  1327   for(i=spot=min; i<=max; i++){
       
  1328     c = msg[i];
       
  1329     if( c=='\t' ) msg[i] = ' ';
       
  1330     if( c=='\n' ){ msg[i] = ' '; spot = i; break; }
       
  1331     if( c==0 ){ spot = i; break; }
       
  1332     if( c=='-' && i<max-1 ) spot = i+1;
       
  1333     if( c==' ' ) spot = i;
       
  1334   }
       
  1335   return spot;
       
  1336 }
       
  1337 
       
  1338 /*
       
  1339 ** The error message is split across multiple lines if necessary.  The
       
  1340 ** splits occur at a space, if there is a space available near the end
       
  1341 ** of the line.
       
  1342 */
       
  1343 #define ERRMSGSIZE  10000 /* Hope this is big enough.  No way to error check */
       
  1344 #define LINEWIDTH      79 /* Max width of any output line */
       
  1345 #define PREFIXLIMIT    30 /* Max width of the prefix on each line */
       
  1346 void ErrorMsg(const char *filename, int lineno, const char *format, ...){
  1351 void ErrorMsg(const char *filename, int lineno, const char *format, ...){
  1347 #if __MOJOSHADER__
       
  1348   va_list ap;
  1352   va_list ap;
  1349   fprintf(stderr, "%s:%d: ", filename, lineno);
  1353   fprintf(stderr, "%s:%d: ", filename, lineno);
  1350   va_start(ap, format);
  1354   va_start(ap, format);
  1351   vfprintf(stderr,format,ap);
  1355   vfprintf(stderr,format,ap);
  1352   va_end(ap);
  1356   va_end(ap);
  1353   fprintf(stderr, "\n");
  1357   fprintf(stderr, "\n");
  1354   fflush(stderr);
       
  1355 #else
       
  1356   char errmsg[ERRMSGSIZE];
       
  1357   char prefix[PREFIXLIMIT+10];
       
  1358   int errmsgsize;
       
  1359   int prefixsize;
       
  1360   int availablewidth;
       
  1361   va_list ap;
       
  1362   int end, restart, base;
       
  1363 
       
  1364   va_start(ap, format);
       
  1365   /* Prepare a prefix to be prepended to every output line */
       
  1366   if( lineno>0 ){
       
  1367     sprintf(prefix,"%.*s:%d: ",PREFIXLIMIT-10,filename,lineno);
       
  1368   }else{
       
  1369     sprintf(prefix,"%.*s: ",PREFIXLIMIT-10,filename);
       
  1370   }
       
  1371   prefixsize = lemonStrlen(prefix);
       
  1372   availablewidth = LINEWIDTH - prefixsize;
       
  1373 
       
  1374   /* Generate the error message */
       
  1375   vsprintf(errmsg,format,ap);
       
  1376   va_end(ap);
       
  1377   errmsgsize = lemonStrlen(errmsg);
       
  1378   /* Remove trailing '\n's from the error message. */
       
  1379   while( errmsgsize>0 && errmsg[errmsgsize-1]=='\n' ){
       
  1380      errmsg[--errmsgsize] = 0;
       
  1381   }
       
  1382 
       
  1383   /* Print the error message */
       
  1384   base = 0;
       
  1385   while( errmsg[base]!=0 ){
       
  1386     end = restart = findbreak(&errmsg[base],0,availablewidth);
       
  1387     restart += base;
       
  1388     while( errmsg[restart]==' ' ) restart++;
       
  1389     fprintf(stdout,"%s%.*s\n",prefix,end,&errmsg[base]);
       
  1390     base = restart;
       
  1391   }
       
  1392 #endif
       
  1393 }
  1358 }
  1394 /**************** From the file "main.c" ************************************/
  1359 /**************** From the file "main.c" ************************************/
  1395 /*
  1360 /*
  1396 ** Main program file for the LEMON parser generator.
  1361 ** Main program file for the LEMON parser generator.
  1397 */
  1362 */
  1411 ** Add the macro defined to the azDefine array.
  1376 ** Add the macro defined to the azDefine array.
  1412 */
  1377 */
  1413 static void handle_D_option(char *z){
  1378 static void handle_D_option(char *z){
  1414   char **paz;
  1379   char **paz;
  1415   nDefine++;
  1380   nDefine++;
  1416   azDefine = realloc(azDefine, sizeof(azDefine[0])*nDefine);
  1381   azDefine = (char **) realloc(azDefine, sizeof(azDefine[0])*nDefine);
  1417   if( azDefine==0 ){
  1382   if( azDefine==0 ){
  1418     fprintf(stderr,"out of memory\n");
  1383     fprintf(stderr,"out of memory\n");
  1419     exit(1);
  1384     exit(1);
  1420   }
  1385   }
  1421   paz = &azDefine[nDefine-1];
  1386   paz = &azDefine[nDefine-1];
  1422   *paz = malloc( lemonStrlen(z)+1 );
  1387   *paz = (char *) malloc( lemonStrlen(z)+1 );
  1423   if( *paz==0 ){
  1388   if( *paz==0 ){
  1424     fprintf(stderr,"out of memory\n");
  1389     fprintf(stderr,"out of memory\n");
  1425     exit(1);
  1390     exit(1);
  1426   }
  1391   }
  1427   strcpy(*paz, z);
  1392   strcpy(*paz, z);
  1428   for(z=*paz; *z && *z!='='; z++){}
  1393   for(z=*paz; *z && *z!='='; z++){}
  1429   *z = 0;
  1394   *z = 0;
  1430 }
  1395 }
  1431 
  1396 
  1432 #if __MOJOSHADER__
       
  1433 static char *user_templatename = NULL;
  1397 static char *user_templatename = NULL;
  1434 static void handle_T_option(char *z){
  1398 static void handle_T_option(char *z){
  1435   user_templatename = malloc( lemonStrlen(z)+1 );
  1399   user_templatename = (char *) malloc( lemonStrlen(z)+1 );
  1436   if( user_templatename==0 ){
  1400   if( user_templatename==0 ){
  1437     fprintf(stderr,"out of memory\n");
  1401     memory_error();
  1438     exit(1);
       
  1439   }
  1402   }
  1440   strcpy(user_templatename, z);
  1403   strcpy(user_templatename, z);
  1441 }
  1404 }
  1442 #endif
       
  1443 
  1405 
  1444 /* The main program.  Parse the command line and do it... */
  1406 /* The main program.  Parse the command line and do it... */
  1445 int main(argc,argv)
  1407 int main(int argc, char **argv)
  1446 int argc;
       
  1447 char **argv;
       
  1448 {
  1408 {
  1449   static int version = 0;
  1409   static int version = 0;
  1450   static int rpflag = 0;
  1410   static int rpflag = 0;
  1451   static int basisflag = 0;
  1411   static int basisflag = 0;
  1452   static int compress = 0;
  1412   static int compress = 0;
  1456   static int nolinenosflag = 0;
  1416   static int nolinenosflag = 0;
  1457   static struct s_options options[] = {
  1417   static struct s_options options[] = {
  1458     {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
  1418     {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
  1459     {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
  1419     {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
  1460     {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
  1420     {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
  1461 #if __MOJOSHADER__
       
  1462     {OPT_FSTR, "T", (char*)handle_T_option, "Specify a template file."},
  1421     {OPT_FSTR, "T", (char*)handle_T_option, "Specify a template file."},
  1463 #endif
       
  1464     {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
  1422     {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
  1465     {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file."},
  1423     {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file."},
  1466     {OPT_FLAG, "l", (char*)&nolinenosflag, "Do not print #line statements."},
  1424     {OPT_FLAG, "l", (char*)&nolinenosflag, "Do not print #line statements."},
  1467     {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
  1425     {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
  1468     {OPT_FLAG, "s", (char*)&statistics,
  1426     {OPT_FLAG, "s", (char*)&statistics,
  1469                                    "Print parser stats to standard output."},
  1427                                    "Print parser stats to standard output."},
  1470     {OPT_FLAG, "x", (char*)&version, "Print the version number."},
  1428     {OPT_FLAG, "x", (char*)&version, "Print the version number."},
  1471     {OPT_FLAG,0,0,0}
  1429     {OPT_FLAG,0,0,0}
  1472   };
  1430   };
  1473   int i;
  1431   int i;
       
  1432   int exitcode;
  1474   struct lemon lem;
  1433   struct lemon lem;
       
  1434 
       
  1435   atexit(LemonAtExit);
  1475 
  1436 
  1476   OptInit(argv,options,stderr);
  1437   OptInit(argv,options,stderr);
  1477   if( version ){
  1438   if( version ){
  1478      printf("Lemon version 1.0\n");
  1439      printf("Lemon version 1.0\n");
  1479 #if __MOJOSHADER__
  1440 #if __MOJOSHADER__
  1485     fprintf(stderr,"Exactly one filename argument is required.\n");
  1446     fprintf(stderr,"Exactly one filename argument is required.\n");
  1486     exit(1);
  1447     exit(1);
  1487   }
  1448   }
  1488   memset(&lem, 0, sizeof(lem));
  1449   memset(&lem, 0, sizeof(lem));
  1489   lem.errorcnt = 0;
  1450   lem.errorcnt = 0;
  1490 
       
  1491 #if __MOJOSHADER__
  1451 #if __MOJOSHADER__
  1492   lem.nexpected = -1;
  1452   lem.nexpected = -1;
  1493 #endif
  1453 #endif
  1494 
  1454 
  1495   /* Initialize the machine */
  1455   /* Initialize the machine */
  1515   /* Count and index the symbols of the grammar */
  1475   /* Count and index the symbols of the grammar */
  1516   lem.nsymbol = Symbol_count();
  1476   lem.nsymbol = Symbol_count();
  1517   Symbol_new("{default}");
  1477   Symbol_new("{default}");
  1518   lem.symbols = Symbol_arrayof();
  1478   lem.symbols = Symbol_arrayof();
  1519   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
  1479   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
  1520   qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*),
  1480   qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*), Symbolcmpp);
  1521         (int(*)())Symbolcmpp);
       
  1522   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
  1481   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
  1523   for(i=1; isupper(lem.symbols[i]->name[0]); i++);
  1482   for(i=1; isupper(lem.symbols[i]->name[0]); i++);
  1524   lem.nterminal = i;
  1483   lem.nterminal = i;
  1525 
  1484 
  1526   /* Generate a reprint of the grammar, if requested on the command line */
  1485   /* Generate a reprint of the grammar, if requested on the command line */
  1576     printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
  1535     printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
  1577       lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
  1536       lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
  1578     printf("                   %d states, %d parser table entries, %d conflicts\n",
  1537     printf("                   %d states, %d parser table entries, %d conflicts\n",
  1579       lem.nstate, lem.tablesize, lem.nconflict);
  1538       lem.nstate, lem.tablesize, lem.nconflict);
  1580   }
  1539   }
       
  1540 
  1581 #if __MOJOSHADER__
  1541 #if __MOJOSHADER__
  1582   if (lem.nexpected < 0) {
  1542   if( lem.nexpected < 0 ) {
  1583     lem.nexpected = 0;  /* grammar didn't have a %expect declaration. */
  1543     lem.nexpected = 0;  /* grammar didn't have an %expect declaration. */
  1584   }
  1544   }
  1585 
  1545   if( lem.nconflict != lem.nexpected ){
  1586   if( lem.nconflict != lem.nexpected){
       
  1587     fprintf(stderr,"%d parsing conflicts (%d expected).\n",lem.nconflict,lem.nexpected);
  1546     fprintf(stderr,"%d parsing conflicts (%d expected).\n",lem.nconflict,lem.nexpected);
  1588   }
  1547   }
       
  1548   /* return 0 on success, 1 on failure. */
       
  1549   exitcode = ((lem.errorcnt > 0) || (lem.nconflict != lem.nexpected)) ? 1 : 0;
  1589 #else
  1550 #else
  1590   if( lem.nconflict ){
  1551   if( lem.nconflict > 0 ){
  1591     fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
  1552     fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
  1592   }
  1553   }
       
  1554 
       
  1555   /* return 0 on success, 1 on failure. */
       
  1556   exitcode = ((lem.errorcnt > 0) || (lem.nconflict > 0)) ? 1 : 0;
  1593 #endif
  1557 #endif
  1594 
  1558   successful_exit = (exitcode == 0);
  1595 #if __MOJOSHADER__
  1559   exit(exitcode);
  1596 {
  1560   return (exitcode);
  1597   // return 0 on success, 1 on failure.
       
  1598   const int rc = ((lem.errorcnt > 0) || (lem.nconflict != lem.nexpected)) ? 1 : 0;
       
  1599   exit(rc);
       
  1600   return (rc);
       
  1601 }
       
  1602 #else
       
  1603   exit(lem.errorcnt + lem.nconflict);
       
  1604   return (lem.errorcnt + lem.nconflict);
       
  1605 #endif
       
  1606 }
  1561 }
  1607 /******************** From the file "msort.c" *******************************/
  1562 /******************** From the file "msort.c" *******************************/
  1608 /*
  1563 /*
  1609 ** A generic merge-sort program.
  1564 ** A generic merge-sort program.
  1610 **
  1565 **
  1659   if( a==0 ){
  1614   if( a==0 ){
  1660     head = b;
  1615     head = b;
  1661   }else if( b==0 ){
  1616   }else if( b==0 ){
  1662     head = a;
  1617     head = a;
  1663   }else{
  1618   }else{
  1664     if( (*cmp)(a,b)<0 ){
  1619     if( (*cmp)(a,b)<=0 ){
  1665       ptr = a;
  1620       ptr = a;
  1666       a = NEXT(a);
  1621       a = NEXT(a);
  1667     }else{
  1622     }else{
  1668       ptr = b;
  1623       ptr = b;
  1669       b = NEXT(b);
  1624       b = NEXT(b);
  1670     }
  1625     }
  1671     head = ptr;
  1626     head = ptr;
  1672     while( a && b ){
  1627     while( a && b ){
  1673       if( (*cmp)(a,b)<0 ){
  1628       if( (*cmp)(a,b)<=0 ){
  1674         NEXT(ptr) = a;
  1629         NEXT(ptr) = a;
  1675         ptr = a;
  1630         ptr = a;
  1676         a = NEXT(a);
  1631         a = NEXT(a);
  1677       }else{
  1632       }else{
  1678         NEXT(ptr) = b;
  1633         NEXT(ptr) = b;
  1720       set[i] = 0;
  1675       set[i] = 0;
  1721     }
  1676     }
  1722     set[i] = ep;
  1677     set[i] = ep;
  1723   }
  1678   }
  1724   ep = 0;
  1679   ep = 0;
  1725   for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(ep,set[i],cmp,offset);
  1680   for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(set[i],ep,cmp,offset);
  1726   return ep;
  1681   return ep;
  1727 }
  1682 }
  1728 /************************ From the file "option.c" **************************/
  1683 /************************ From the file "option.c" **************************/
  1729 static char **argv;
  1684 static char **argv;
  1730 static struct s_options *op;
  1685 static struct s_options *op;
  1734 
  1689 
  1735 /*
  1690 /*
  1736 ** Print the command line with a carrot pointing to the k-th character
  1691 ** Print the command line with a carrot pointing to the k-th character
  1737 ** of the n-th field.
  1692 ** of the n-th field.
  1738 */
  1693 */
  1739 static void errline(n,k,err)
  1694 static void errline(int n, int k, FILE *err)
  1740 int n;
       
  1741 int k;
       
  1742 FILE *err;
       
  1743 {
  1695 {
  1744   int spcnt, i;
  1696   int spcnt, i;
  1745   if( argv[0] ) fprintf(err,"%s",argv[0]);
  1697   if( argv[0] ) fprintf(err,"%s",argv[0]);
  1746   spcnt = lemonStrlen(argv[0]) + 1;
  1698   spcnt = lemonStrlen(argv[0]) + 1;
  1747   for(i=1; i<n && argv[i]; i++){
  1699   for(i=1; i<n && argv[i]; i++){
  1759 
  1711 
  1760 /*
  1712 /*
  1761 ** Return the index of the N-th non-switch argument.  Return -1
  1713 ** Return the index of the N-th non-switch argument.  Return -1
  1762 ** if N is out of range.
  1714 ** if N is out of range.
  1763 */
  1715 */
  1764 static int argindex(n)
  1716 static int argindex(int n)
  1765 int n;
       
  1766 {
  1717 {
  1767   int i;
  1718   int i;
  1768   int dashdash = 0;
  1719   int dashdash = 0;
  1769   if( argv!=0 && *argv!=0 ){
  1720   if( argv!=0 && *argv!=0 ){
  1770     for(i=1; argv[i]; i++){
  1721     for(i=1; argv[i]; i++){
  1781 static char emsg[] = "Command line syntax error: ";
  1732 static char emsg[] = "Command line syntax error: ";
  1782 
  1733 
  1783 /*
  1734 /*
  1784 ** Process a flag command line argument.
  1735 ** Process a flag command line argument.
  1785 */
  1736 */
  1786 static int handleflags(i,err)
  1737 static int handleflags(int i, FILE *err)
  1787 int i;
       
  1788 FILE *err;
       
  1789 {
  1738 {
  1790   int v;
  1739   int v;
  1791   int errcnt = 0;
  1740   int errcnt = 0;
  1792   int j;
  1741   int j;
  1793   for(j=0; op[j].label; j++){
  1742   for(j=0; op[j].label; j++){
  1801     }
  1750     }
  1802     errcnt++;
  1751     errcnt++;
  1803   }else if( op[j].type==OPT_FLAG ){
  1752   }else if( op[j].type==OPT_FLAG ){
  1804     *((int*)op[j].arg) = v;
  1753     *((int*)op[j].arg) = v;
  1805   }else if( op[j].type==OPT_FFLAG ){
  1754   }else if( op[j].type==OPT_FFLAG ){
  1806     (*(void(*)())(op[j].arg))(v);
  1755     (*(void(*)(int))(op[j].arg))(v);
  1807   }else if( op[j].type==OPT_FSTR ){
  1756   }else if( op[j].type==OPT_FSTR ){
  1808     (*(void(*)())(op[j].arg))(&argv[i][2]);
  1757     (*(void(*)(char *))(op[j].arg))(&argv[i][2]);
  1809   }else{
  1758   }else{
  1810     if( err ){
  1759     if( err ){
  1811       fprintf(err,"%smissing argument on switch.\n",emsg);
  1760       fprintf(err,"%smissing argument on switch.\n",emsg);
  1812       errline(i,1,err);
  1761       errline(i,1,err);
  1813     }
  1762     }
  1817 }
  1766 }
  1818 
  1767 
  1819 /*
  1768 /*
  1820 ** Process a command line switch which has an argument.
  1769 ** Process a command line switch which has an argument.
  1821 */
  1770 */
  1822 static int handleswitch(i,err)
  1771 static int handleswitch(int i, FILE *err)
  1823 int i;
       
  1824 FILE *err;
       
  1825 {
  1772 {
  1826   int lv = 0;
  1773   int lv = 0;
  1827   double dv = 0.0;
  1774   double dv = 0.0;
  1828   char *sv = 0, *end;
  1775   char *sv = 0, *end;
  1829   char *cp;
  1776   char *cp;
  1886         break;
  1833         break;
  1887       case OPT_DBL:
  1834       case OPT_DBL:
  1888         *(double*)(op[j].arg) = dv;
  1835         *(double*)(op[j].arg) = dv;
  1889         break;
  1836         break;
  1890       case OPT_FDBL:
  1837       case OPT_FDBL:
  1891         (*(void(*)())(op[j].arg))(dv);
  1838         (*(void(*)(double))(op[j].arg))(dv);
  1892         break;
  1839         break;
  1893       case OPT_INT:
  1840       case OPT_INT:
  1894         *(int*)(op[j].arg) = lv;
  1841         *(int*)(op[j].arg) = lv;
  1895         break;
  1842         break;
  1896       case OPT_FINT:
  1843       case OPT_FINT:
  1897         (*(void(*)())(op[j].arg))((int)lv);
  1844         (*(void(*)(int))(op[j].arg))((int)lv);
  1898         break;
  1845         break;
  1899       case OPT_STR:
  1846       case OPT_STR:
  1900         *(char**)(op[j].arg) = sv;
  1847         *(char**)(op[j].arg) = sv;
  1901         break;
  1848         break;
  1902       case OPT_FSTR:
  1849       case OPT_FSTR:
  1903         (*(void(*)())(op[j].arg))(sv);
  1850         (*(void(*)(char *))(op[j].arg))(sv);
  1904         break;
  1851         break;
  1905     }
  1852     }
  1906   }
  1853   }
  1907   return errcnt;
  1854   return errcnt;
  1908 }
  1855 }
  1909 
  1856 
  1910 int OptInit(a,o,err)
  1857 int OptInit(char **a, struct s_options *o, FILE *err)
  1911 char **a;
       
  1912 struct s_options *o;
       
  1913 FILE *err;
       
  1914 {
  1858 {
  1915   int errcnt = 0;
  1859   int errcnt = 0;
  1916   argv = a;
  1860   argv = a;
  1917   op = o;
  1861   op = o;
  1918   errstream = err;
  1862   errstream = err;
  1945     }
  1889     }
  1946   }
  1890   }
  1947   return cnt;
  1891   return cnt;
  1948 }
  1892 }
  1949 
  1893 
  1950 char *OptArg(n)
  1894 char *OptArg(int n)
  1951 int n;
       
  1952 {
  1895 {
  1953   int i;
  1896   int i;
  1954   i = argindex(n);
  1897   i = argindex(n);
  1955   return i>=0 ? argv[i] : 0;
  1898   return i>=0 ? argv[i] : 0;
  1956 }
  1899 }
  1957 
  1900 
  1958 void OptErr(n)
  1901 void OptErr(int n)
  1959 int n;
       
  1960 {
  1902 {
  1961   int i;
  1903   int i;
  1962   i = argindex(n);
  1904   i = argindex(n);
  1963   if( i>=0 ) errline(i,0,errstream);
  1905   if( i>=0 ) errline(i,0,errstream);
  1964 }
  1906 }
  2016 /*
  1958 /*
  2017 ** Input file parser for the LEMON parser generator.
  1959 ** Input file parser for the LEMON parser generator.
  2018 */
  1960 */
  2019 
  1961 
  2020 /* The state of the parser */
  1962 /* The state of the parser */
       
  1963 enum e_state {
       
  1964   INITIALIZE,
       
  1965   WAITING_FOR_DECL_OR_RULE,
       
  1966   WAITING_FOR_DECL_KEYWORD,
       
  1967   WAITING_FOR_DECL_ARG,
       
  1968   WAITING_FOR_PRECEDENCE_SYMBOL,
       
  1969   WAITING_FOR_ARROW,
       
  1970   IN_RHS,
       
  1971   LHS_ALIAS_1,
       
  1972   LHS_ALIAS_2,
       
  1973   LHS_ALIAS_3,
       
  1974   RHS_ALIAS_1,
       
  1975   RHS_ALIAS_2,
       
  1976   PRECEDENCE_MARK_1,
       
  1977   PRECEDENCE_MARK_2,
       
  1978   RESYNC_AFTER_RULE_ERROR,
       
  1979   RESYNC_AFTER_DECL_ERROR,
       
  1980   WAITING_FOR_DESTRUCTOR_SYMBOL,
       
  1981   WAITING_FOR_DATATYPE_SYMBOL,
       
  1982   WAITING_FOR_FALLBACK_ID,
       
  1983   WAITING_FOR_EXPECT_VALUE,
       
  1984   WAITING_FOR_WILDCARD_ID
       
  1985 };
  2021 struct pstate {
  1986 struct pstate {
  2022   char *filename;       /* Name of the input file */
  1987   char *filename;       /* Name of the input file */
  2023   int tokenlineno;      /* Linenumber at which current token starts */
  1988   int tokenlineno;      /* Linenumber at which current token starts */
  2024   int errorcnt;         /* Number of errors so far */
  1989   int errorcnt;         /* Number of errors so far */
  2025   char *tokenstart;     /* Text of current token */
  1990   char *tokenstart;     /* Text of current token */
  2026   struct lemon *gp;     /* Global state vector */
  1991   struct lemon *gp;     /* Global state vector */
  2027   enum e_state {
  1992   enum e_state state;        /* The state of the parser */
  2028     INITIALIZE,
       
  2029     WAITING_FOR_DECL_OR_RULE,
       
  2030     WAITING_FOR_DECL_KEYWORD,
       
  2031     WAITING_FOR_DECL_ARG,
       
  2032     WAITING_FOR_PRECEDENCE_SYMBOL,
       
  2033     WAITING_FOR_ARROW,
       
  2034     IN_RHS,
       
  2035     LHS_ALIAS_1,
       
  2036     LHS_ALIAS_2,
       
  2037     LHS_ALIAS_3,
       
  2038     RHS_ALIAS_1,
       
  2039     RHS_ALIAS_2,
       
  2040     PRECEDENCE_MARK_1,
       
  2041     PRECEDENCE_MARK_2,
       
  2042     RESYNC_AFTER_RULE_ERROR,
       
  2043     RESYNC_AFTER_DECL_ERROR,
       
  2044     WAITING_FOR_DESTRUCTOR_SYMBOL,
       
  2045     WAITING_FOR_DATATYPE_SYMBOL,
       
  2046     WAITING_FOR_FALLBACK_ID,
       
  2047 #if __MOJOSHADER__
       
  2048     WAITING_FOR_EXPECT_VALUE,
       
  2049 #endif
       
  2050     WAITING_FOR_WILDCARD_ID
       
  2051   } state;                   /* The state of the parser */
       
  2052   struct symbol *fallback;   /* The fallback token */
  1993   struct symbol *fallback;   /* The fallback token */
  2053   struct symbol *lhs;        /* Left-hand side of current rule */
  1994   struct symbol *lhs;        /* Left-hand side of current rule */
  2054   char *lhsalias;            /* Alias for the LHS */
  1995   const char *lhsalias;      /* Alias for the LHS */
  2055   int nrhs;                  /* Number of right-hand side symbols seen */
  1996   int nrhs;                  /* Number of right-hand side symbols seen */
  2056   struct symbol *rhs[MAXRHS];  /* RHS symbols */
  1997   struct symbol *rhs[MAXRHS];  /* RHS symbols */
  2057   char *alias[MAXRHS];       /* Aliases for each RHS symbol (or NULL) */
  1998   const char *alias[MAXRHS]; /* Aliases for each RHS symbol (or NULL) */
  2058   struct rule *prevrule;     /* Previous rule parsed */
  1999   struct rule *prevrule;     /* Previous rule parsed */
  2059   char *declkeyword;         /* Keyword of a declaration */
  2000   const char *declkeyword;   /* Keyword of a declaration */
  2060   char **declargslot;        /* Where the declaration argument should be put */
  2001   char **declargslot;        /* Where the declaration argument should be put */
  2061   int insertLineMacro;       /* Add #line before declaration insert */
  2002   int insertLineMacro;       /* Add #line before declaration insert */
  2062   int *decllinenoslot;       /* Where to write declaration line number */
  2003   int *decllinenoslot;       /* Where to write declaration line number */
  2063   enum e_assoc declassoc;    /* Assign this association to decl arguments */
  2004   enum e_assoc declassoc;    /* Assign this association to decl arguments */
  2064   int preccounter;           /* Assign this precedence to decl arguments */
  2005   int preccounter;           /* Assign this precedence to decl arguments */
  2065   struct rule *firstrule;    /* Pointer to first rule in the grammar */
  2006   struct rule *firstrule;    /* Pointer to first rule in the grammar */
  2066   struct rule *lastrule;     /* Pointer to the most recently parsed rule */
  2007   struct rule *lastrule;     /* Pointer to the most recently parsed rule */
  2067 };
  2008 };
  2068 
  2009 
  2069 /* Parse a single token */
  2010 /* Parse a single token */
  2070 static void parseonetoken(psp)
  2011 static void parseonetoken(struct pstate *psp)
  2071 struct pstate *psp;
  2012 {
  2072 {
  2013 #if __MOJOSHADER__
  2073   char *x;
  2014   char *endptr;
       
  2015 #endif
       
  2016   const char *x;
  2074   x = Strsafe(psp->tokenstart);     /* Save the token permanently */
  2017   x = Strsafe(psp->tokenstart);     /* Save the token permanently */
  2075 #if 0
  2018 #if 0
  2076   printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
  2019   printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
  2077     x,psp->state);
  2020     x,psp->state);
  2078 #endif
  2021 #endif
  2200           psp->prevrule = 0;
  2143           psp->prevrule = 0;
  2201 	}else{
  2144 	}else{
  2202           int i;
  2145           int i;
  2203           rp->ruleline = psp->tokenlineno;
  2146           rp->ruleline = psp->tokenlineno;
  2204           rp->rhs = (struct symbol**)&rp[1];
  2147           rp->rhs = (struct symbol**)&rp[1];
  2205           rp->rhsalias = (char**)&(rp->rhs[psp->nrhs]);
  2148           rp->rhsalias = (const char**)&(rp->rhs[psp->nrhs]);
  2206           for(i=0; i<psp->nrhs; i++){
  2149           for(i=0; i<psp->nrhs; i++){
  2207             rp->rhs[i] = psp->rhs[i];
  2150             rp->rhs[i] = psp->rhs[i];
  2208             rp->rhsalias[i] = psp->alias[i];
  2151             rp->rhsalias[i] = psp->alias[i];
  2209 	  }
  2152 	  }
  2210           rp->lhs = psp->lhs;
  2153           rp->lhs = psp->lhs;
  2239 	}
  2182 	}
  2240       }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 ){
  2183       }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 ){
  2241         struct symbol *msp = psp->rhs[psp->nrhs-1];
  2184         struct symbol *msp = psp->rhs[psp->nrhs-1];
  2242         if( msp->type!=MULTITERMINAL ){
  2185         if( msp->type!=MULTITERMINAL ){
  2243           struct symbol *origsp = msp;
  2186           struct symbol *origsp = msp;
  2244           msp = calloc(1,sizeof(*msp));
  2187           msp = (struct symbol *) calloc(1,sizeof(*msp));
  2245           memset(msp, 0, sizeof(*msp));
  2188           memset(msp, 0, sizeof(*msp));
  2246           msp->type = MULTITERMINAL;
  2189           msp->type = MULTITERMINAL;
  2247           msp->nsubsym = 1;
  2190           msp->nsubsym = 1;
  2248           msp->subsym = calloc(1,sizeof(struct symbol*));
  2191           msp->subsym = (struct symbol **) calloc(1,sizeof(struct symbol*));
  2249           msp->subsym[0] = origsp;
  2192           msp->subsym[0] = origsp;
  2250           msp->name = origsp->name;
  2193           msp->name = origsp->name;
  2251           psp->rhs[psp->nrhs-1] = msp;
  2194           psp->rhs[psp->nrhs-1] = msp;
  2252         }
  2195         }
  2253         msp->nsubsym++;
  2196         msp->nsubsym++;
  2254         msp->subsym = realloc(msp->subsym, sizeof(struct symbol*)*msp->nsubsym);
  2197         msp->subsym = (struct symbol **) realloc(msp->subsym,
       
  2198           sizeof(struct symbol*)*msp->nsubsym);
  2255         msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);
  2199         msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);
  2256         if( islower(x[1]) || islower(msp->subsym[0]->name[0]) ){
  2200         if( islower(x[1]) || islower(msp->subsym[0]->name[0]) ){
  2257           ErrorMsg(psp->filename,psp->tokenlineno,
  2201           ErrorMsg(psp->filename,psp->tokenlineno,
  2258             "Cannot form a compound containing a non-terminal");
  2202             "Cannot form a compound containing a non-terminal");
  2259           psp->errorcnt++;
  2203           psp->errorcnt++;
  2391         psp->state = WAITING_FOR_DECL_ARG;
  2335         psp->state = WAITING_FOR_DECL_ARG;
  2392       }
  2336       }
  2393       break;
  2337       break;
  2394 #if __MOJOSHADER__
  2338 #if __MOJOSHADER__
  2395     case WAITING_FOR_EXPECT_VALUE:
  2339     case WAITING_FOR_EXPECT_VALUE:
  2396     {
       
  2397         char *endptr = NULL;
       
  2398         psp->gp->nexpected = (int) strtol(x, &endptr, 10);
  2340         psp->gp->nexpected = (int) strtol(x, &endptr, 10);
  2399         if ((*endptr != '\0') || (endptr == x)) {
  2341         if( (*endptr != '\0') || (endptr == x) ) {
  2400           ErrorMsg(psp->filename,psp->tokenlineno,
  2342           ErrorMsg(psp->filename,psp->tokenlineno,
  2401             "Integer expected after %%expect keyword");
  2343             "Integer expected after %%expect keyword");
  2402           psp->errorcnt++;
  2344           psp->errorcnt++;
  2403         } else if (psp->gp->nexpected < 0) {
  2345         } else if (psp->gp->nexpected < 0) {
  2404           ErrorMsg(psp->filename,psp->tokenlineno,
  2346           ErrorMsg(psp->filename,psp->tokenlineno,
  2405             "Integer can't be negative after %%expect keyword");
  2347             "Integer can't be negative after %%expect keyword");
  2406           psp->errorcnt++;
  2348           psp->errorcnt++;
  2407         }
  2349         }
  2408         psp->state = WAITING_FOR_DECL_OR_RULE;
  2350         psp->state = WAITING_FOR_DECL_OR_RULE;
  2409         break;
  2351         break;
  2410     }
       
  2411 #endif
  2352 #endif
  2412     case WAITING_FOR_DATATYPE_SYMBOL:
  2353     case WAITING_FOR_DATATYPE_SYMBOL:
  2413       if( !isalpha(x[0]) ){
  2354       if( !isalpha(x[0]) ){
  2414         ErrorMsg(psp->filename,psp->tokenlineno,
  2355         ErrorMsg(psp->filename,psp->tokenlineno,
  2415           "Symbol name missing after %destructor keyword");
  2356           "Symbol name missing after %destructor keyword");
  2442         psp->errorcnt++;
  2383         psp->errorcnt++;
  2443       }
  2384       }
  2444       break;
  2385       break;
  2445     case WAITING_FOR_DECL_ARG:
  2386     case WAITING_FOR_DECL_ARG:
  2446       if( x[0]=='{' || x[0]=='\"' || isalnum(x[0]) ){
  2387       if( x[0]=='{' || x[0]=='\"' || isalnum(x[0]) ){
  2447         char *zOld, *zNew, *zBuf, *z;
  2388         const char *zOld, *zNew;
  2448         int nOld, n, nLine=0, nNew, nBack;
  2389         char *zBuf, *z;
       
  2390         int nOld, n, nLine, nNew, nBack;
  2449         int addLineMacro;
  2391         int addLineMacro;
  2450         char zLine[50];
  2392         char zLine[50];
  2451         zNew = x;
  2393         zNew = x;
  2452         if( zNew[0]=='"' || zNew[0]=='{' ) zNew++;
  2394         if( zNew[0]=='"' || zNew[0]=='{' ) zNew++;
  2453         nNew = lemonStrlen(zNew);
  2395         nNew = lemonStrlen(zNew);
  2466           }
  2408           }
  2467           sprintf(zLine, "#line %d ", psp->tokenlineno);
  2409           sprintf(zLine, "#line %d ", psp->tokenlineno);
  2468           nLine = lemonStrlen(zLine);
  2410           nLine = lemonStrlen(zLine);
  2469           n += nLine + lemonStrlen(psp->filename) + nBack;
  2411           n += nLine + lemonStrlen(psp->filename) + nBack;
  2470         }
  2412         }
  2471         *psp->declargslot = zBuf = realloc(*psp->declargslot, n);
  2413         *psp->declargslot = (char *) realloc(*psp->declargslot, n);
  2472         zBuf += nOld;
  2414         zBuf = *psp->declargslot + nOld;
  2473         if( addLineMacro ){
  2415         if( addLineMacro ){
  2474           if( nOld && zBuf[-1]!='\n' ){
  2416           if( nOld && zBuf[-1]!='\n' ){
  2475             *(zBuf++) = '\n';
  2417             *(zBuf++) = '\n';
  2476           }
  2418           }
  2477           memcpy(zBuf, zLine, nLine);
  2419           memcpy(zBuf, zLine, nLine);
  2603 /* In spite of its name, this function is really a scanner.  It read
  2545 /* In spite of its name, this function is really a scanner.  It read
  2604 ** in the entire input file (all at once) then tokenizes it.  Each
  2546 ** in the entire input file (all at once) then tokenizes it.  Each
  2605 ** token is passed to the function "parseonetoken" which builds all
  2547 ** token is passed to the function "parseonetoken" which builds all
  2606 ** the appropriate data structures in the global state vector "gp".
  2548 ** the appropriate data structures in the global state vector "gp".
  2607 */
  2549 */
  2608 void Parse(gp)
  2550 void Parse(struct lemon *gp)
  2609 struct lemon *gp;
       
  2610 {
  2551 {
  2611   struct pstate ps;
  2552   struct pstate ps;
  2612   FILE *fp;
  2553   FILE *fp;
  2613   char *filebuf;
  2554   char *filebuf;
  2614   int filesize;
  2555   int filesize;
  2758 */
  2699 */
  2759 static struct plink *plink_freelist = 0;
  2700 static struct plink *plink_freelist = 0;
  2760 
  2701 
  2761 /* Allocate a new plink */
  2702 /* Allocate a new plink */
  2762 struct plink *Plink_new(){
  2703 struct plink *Plink_new(){
  2763   struct plink *new;
  2704   struct plink *newlink;
  2764 
  2705 
  2765   if( plink_freelist==0 ){
  2706   if( plink_freelist==0 ){
  2766     int i;
  2707     int i;
  2767     int amt = 100;
  2708     int amt = 100;
  2768     plink_freelist = (struct plink *)calloc( amt, sizeof(struct plink) );
  2709     plink_freelist = (struct plink *)calloc( amt, sizeof(struct plink) );
  2772       exit(1);
  2713       exit(1);
  2773     }
  2714     }
  2774     for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
  2715     for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
  2775     plink_freelist[amt-1].next = 0;
  2716     plink_freelist[amt-1].next = 0;
  2776   }
  2717   }
  2777   new = plink_freelist;
  2718   newlink = plink_freelist;
  2778   plink_freelist = plink_freelist->next;
  2719   plink_freelist = plink_freelist->next;
  2779   return new;
  2720   return newlink;
  2780 }
  2721 }
  2781 
  2722 
  2782 /* Add a plink to a plink list */
  2723 /* Add a plink to a plink list */
  2783 void Plink_add(plpp,cfp)
  2724 void Plink_add(struct plink **plpp, struct config *cfp)
  2784 struct plink **plpp;
  2725 {
  2785 struct config *cfp;
  2726   struct plink *newlink;
  2786 {
  2727   newlink = Plink_new();
  2787   struct plink *new;
  2728   newlink->next = *plpp;
  2788   new = Plink_new();
  2729   *plpp = newlink;
  2789   new->next = *plpp;
  2730   newlink->cfp = cfp;
  2790   *plpp = new;
       
  2791   new->cfp = cfp;
       
  2792 }
  2731 }
  2793 
  2732 
  2794 /* Transfer every plink on the list "from" to the list "to" */
  2733 /* Transfer every plink on the list "from" to the list "to" */
  2795 void Plink_copy(to,from)
  2734 void Plink_copy(struct plink **to, struct plink *from)
  2796 struct plink **to;
       
  2797 struct plink *from;
       
  2798 {
  2735 {
  2799   struct plink *nextpl;
  2736   struct plink *nextpl;
  2800   while( from ){
  2737   while( from ){
  2801     nextpl = from->next;
  2738     nextpl = from->next;
  2802     from->next = *to;
  2739     from->next = *to;
  2804     from = nextpl;
  2741     from = nextpl;
  2805   }
  2742   }
  2806 }
  2743 }
  2807 
  2744 
  2808 /* Delete every plink on the list */
  2745 /* Delete every plink on the list */
  2809 void Plink_delete(plp)
  2746 void Plink_delete(struct plink *plp)
  2810 struct plink *plp;
       
  2811 {
  2747 {
  2812   struct plink *nextpl;
  2748   struct plink *nextpl;
  2813 
  2749 
  2814   while( plp ){
  2750   while( plp ){
  2815     nextpl = plp->next;
  2751     nextpl = plp->next;
  2825 
  2761 
  2826 /* Generate a filename with the given suffix.  Space to hold the
  2762 /* Generate a filename with the given suffix.  Space to hold the
  2827 ** name comes from malloc() and must be freed by the calling
  2763 ** name comes from malloc() and must be freed by the calling
  2828 ** function.
  2764 ** function.
  2829 */
  2765 */
  2830 PRIVATE char *file_makename(lemp,suffix)
  2766 PRIVATE char *file_makename(struct lemon *lemp, const char *suffix)
  2831 struct lemon *lemp;
       
  2832 char *suffix;
       
  2833 {
  2767 {
  2834   char *name;
  2768   char *name;
  2835   char *cp;
  2769   char *cp;
  2836 
  2770 
  2837   name = malloc( lemonStrlen(lemp->filename) + lemonStrlen(suffix) + 5 );
  2771   name = (char*)malloc( lemonStrlen(lemp->filename) + lemonStrlen(suffix) + 5 );
  2838   if( name==0 ){
  2772   if( name==0 ){
  2839     fprintf(stderr,"Can't allocate space for a filename.\n");
  2773     fprintf(stderr,"Can't allocate space for a filename.\n");
  2840     exit(1);
  2774     exit(1);
  2841   }
  2775   }
  2842   strcpy(name,lemp->filename);
  2776   strcpy(name,lemp->filename);
  2847 }
  2781 }
  2848 
  2782 
  2849 /* Open a file with a name based on the name of the input file,
  2783 /* Open a file with a name based on the name of the input file,
  2850 ** but with a different (specified) suffix, and return a pointer
  2784 ** but with a different (specified) suffix, and return a pointer
  2851 ** to the stream */
  2785 ** to the stream */
  2852 PRIVATE FILE *file_open(lemp,suffix,mode)
  2786 PRIVATE FILE *file_open(
  2853 struct lemon *lemp;
  2787   struct lemon *lemp,
  2854 char *suffix;
  2788   const char *suffix,
  2855 char *mode;
  2789   const char *mode
  2856 {
  2790 ){
  2857   FILE *fp;
  2791   FILE *fp;
  2858 
  2792 
  2859   if( lemp->outname ) free(lemp->outname);
  2793   if( lemp->outname ) free(lemp->outname);
  2860   lemp->outname = file_makename(lemp, suffix);
  2794   lemp->outname = file_makename(lemp, suffix);
  2861   fp = fopen(lemp->outname,mode);
  2795   fp = fopen(lemp->outname,mode);
  2862   if( fp==0 && *mode=='w' ){
  2796   if( fp==0 && *mode=='w' ){
  2863     fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
  2797     fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
  2864     lemp->errorcnt++;
  2798     lemp->errorcnt++;
  2865     return 0;
  2799     return 0;
  2866   }
  2800   }
  2867 #if __MOJOSHADER__
  2801 
  2868   /* don't include .out files: this is debug information, and you don't want
  2802   /* Add files we create to a list, so we can delete them if we fail. This
  2869      it deleted if there was an error you need to track down. */
  2803   ** is to keep makefiles from getting confused. We don't include .out files,
       
  2804   ** though: this is debug information, and you don't want it deleted if there
       
  2805   ** was an error you need to track down.
       
  2806   */
  2870   if(( *mode=='w' ) && (strcmp(suffix, ".out") != 0)){
  2807   if(( *mode=='w' ) && (strcmp(suffix, ".out") != 0)){
  2871     const char **ptr = (const char **)
  2808     const char **ptr = (const char **)
  2872         realloc(made_files, sizeof (const char **) * (made_files_count + 1));
  2809         realloc(made_files, sizeof (const char **) * (made_files_count + 1));
  2873     char *fname = strdup(lemp->outname);
  2810     char *fname = strdup(lemp->outname);
  2874     if ((ptr == NULL) || (fname == NULL)) {
  2811     if ((ptr == NULL) || (fname == NULL)) {
  2877         memory_error();
  2814         memory_error();
  2878     }
  2815     }
  2879     made_files = ptr;
  2816     made_files = ptr;
  2880     made_files[made_files_count++] = fname;
  2817     made_files[made_files_count++] = fname;
  2881   }
  2818   }
  2882 #endif
       
  2883   return fp;
  2819   return fp;
  2884 }
  2820 }
  2885 
  2821 
  2886 /* Duplicate the input file without comments and without actions 
  2822 /* Duplicate the input file without comments and without actions 
  2887 ** on rules */
  2823 ** on rules */
  2888 void Reprint(lemp)
  2824 void Reprint(struct lemon *lemp)
  2889 struct lemon *lemp;
       
  2890 {
  2825 {
  2891   struct rule *rp;
  2826   struct rule *rp;
  2892   struct symbol *sp;
  2827   struct symbol *sp;
  2893   int i, j, maxlen, len, ncolumns, skip;
  2828   int i, j, maxlen, len, ncolumns, skip;
  2894   printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
  2829   printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
  2929     /* if( rp->code ) printf("\n    %s",rp->code); */
  2864     /* if( rp->code ) printf("\n    %s",rp->code); */
  2930     printf("\n");
  2865     printf("\n");
  2931   }
  2866   }
  2932 }
  2867 }
  2933 
  2868 
  2934 void ConfigPrint(fp,cfp)
  2869 void ConfigPrint(FILE *fp, struct config *cfp)
  2935 FILE *fp;
       
  2936 struct config *cfp;
       
  2937 {
  2870 {
  2938   struct rule *rp;
  2871   struct rule *rp;
  2939   struct symbol *sp;
  2872   struct symbol *sp;
  2940   int i, j;
  2873   int i, j;
  2941   rp = cfp->rp;
  2874   rp = cfp->rp;
  3024   }
  2957   }
  3025   return result;
  2958   return result;
  3026 }
  2959 }
  3027 
  2960 
  3028 /* Generate the "y.output" log file */
  2961 /* Generate the "y.output" log file */
  3029 void ReportOutput(lemp)
  2962 void ReportOutput(struct lemon *lemp)
  3030 struct lemon *lemp;
       
  3031 {
  2963 {
  3032   int i;
  2964   int i;
  3033   struct state *stp;
  2965   struct state *stp;
  3034   struct config *cfp;
  2966   struct config *cfp;
  3035   struct action *ap;
  2967   struct action *ap;
  3091   return;
  3023   return;
  3092 }
  3024 }
  3093 
  3025 
  3094 /* Search for the file "name" which is in the same directory as
  3026 /* Search for the file "name" which is in the same directory as
  3095 ** the exacutable */
  3027 ** the exacutable */
  3096 PRIVATE char *pathsearch(argv0,name,modemask)
  3028 PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
  3097 char *argv0;
  3029 {
  3098 char *name;
  3030   const char *pathlist;
  3099 int modemask;
  3031   char *pathbufptr;
  3100 {
  3032   char *pathbuf;
  3101   char *pathlist;
       
  3102   char *path,*cp;
  3033   char *path,*cp;
  3103   char c;
  3034   char c;
  3104 
  3035 
  3105 #ifdef __WIN32__
  3036 #ifdef __WIN32__
  3106   cp = strrchr(argv0,'\\');
  3037   cp = strrchr(argv0,'\\');
  3112     *cp = 0;
  3043     *cp = 0;
  3113     path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2 );
  3044     path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2 );
  3114     if( path ) sprintf(path,"%s/%s",argv0,name);
  3045     if( path ) sprintf(path,"%s/%s",argv0,name);
  3115     *cp = c;
  3046     *cp = c;
  3116   }else{
  3047   }else{
  3117     extern char *getenv();
       
  3118     pathlist = getenv("PATH");
  3048     pathlist = getenv("PATH");
  3119     if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
  3049     if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
       
  3050     pathbuf = (char *) malloc( lemonStrlen(pathlist) + 1 );
  3120     path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
  3051     path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
  3121     if( path!=0 ){
  3052     if( (pathbuf != 0) && (path!=0) ){
  3122       while( *pathlist ){
  3053       pathbufptr = pathbuf;
  3123         cp = strchr(pathlist,':');
  3054       strcpy(pathbuf, pathlist);
  3124         if( cp==0 ) cp = &pathlist[lemonStrlen(pathlist)];
  3055       while( *pathbuf ){
       
  3056         cp = strchr(pathbuf,':');
       
  3057         if( cp==0 ) cp = &pathbuf[lemonStrlen(pathbuf)];
  3125         c = *cp;
  3058         c = *cp;
  3126         *cp = 0;
  3059         *cp = 0;
  3127         sprintf(path,"%s/%s",pathlist,name);
  3060         sprintf(path,"%s/%s",pathbuf,name);
  3128         *cp = c;
  3061         *cp = c;
  3129         if( c==0 ) pathlist = "";
  3062         if( c==0 ) pathbuf[0] = 0;
  3130         else pathlist = &cp[1];
  3063         else pathbuf = &cp[1];
  3131         if( access(path,modemask)==0 ) break;
  3064         if( access(path,modemask)==0 ) break;
  3132       }
  3065       }
       
  3066       free(pathbufptr);
  3133     }
  3067     }
  3134   }
  3068   }
  3135   return path;
  3069   return path;
  3136 }
  3070 }
  3137 
  3071 
  3138 /* Given an action, compute the integer value for that action
  3072 /* Given an action, compute the integer value for that action
  3139 ** which is to be put in the action table of the generated machine.
  3073 ** which is to be put in the action table of the generated machine.
  3140 ** Return negative if no action should be generated.
  3074 ** Return negative if no action should be generated.
  3141 */
  3075 */
  3142 PRIVATE int compute_action(lemp,ap)
  3076 PRIVATE int compute_action(struct lemon *lemp, struct action *ap)
  3143 struct lemon *lemp;
       
  3144 struct action *ap;
       
  3145 {
  3077 {
  3146   int act;
  3078   int act;
  3147   switch( ap->type ){
  3079   switch( ap->type ){
  3148     case SHIFT:  act = ap->x.stp->statenum;            break;
  3080     case SHIFT:  act = ap->x.stp->statenum;            break;
  3149     case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
  3081     case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
  3162 ** tracked.
  3094 ** tracked.
  3163 **
  3095 **
  3164 ** if name!=0, then any word that begin with "Parse" is changed to
  3096 ** if name!=0, then any word that begin with "Parse" is changed to
  3165 ** begin with *name instead.
  3097 ** begin with *name instead.
  3166 */
  3098 */
  3167 PRIVATE void tplt_xfer(name,in,out,lineno)
  3099 PRIVATE void tplt_xfer(char *name, FILE *in, FILE *out, int *lineno)
  3168 char *name;
       
  3169 FILE *in;
       
  3170 FILE *out;
       
  3171 int *lineno;
       
  3172 {
  3100 {
  3173   int i, iStart;
  3101   int i, iStart;
  3174   char line[LINESIZE];
  3102   char line[LINESIZE];
  3175   while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
  3103   while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
  3176     (*lineno)++;
  3104     (*lineno)++;
  3191   }
  3119   }
  3192 }
  3120 }
  3193 
  3121 
  3194 /* The next function finds the template file and opens it, returning
  3122 /* The next function finds the template file and opens it, returning
  3195 ** a pointer to the opened file. */
  3123 ** a pointer to the opened file. */
  3196 PRIVATE FILE *tplt_open(lemp)
  3124 PRIVATE FILE *tplt_open(struct lemon *lemp)
  3197 struct lemon *lemp;
       
  3198 {
  3125 {
  3199   static char templatename[] = "lempar.c";
  3126   static char templatename[] = "lempar.c";
  3200   char buf[1000];
  3127   char buf[1000];
  3201   FILE *in;
  3128   FILE *in;
  3202   char *tpltname = 0;
  3129   char *tpltname;
  3203   char *cp;
  3130   char *cp;
  3204 
  3131 
  3205   #if __MOJOSHADER__
  3132   /* first, see if user specified a template filename on the command line. */
  3206   if (user_templatename != 0) {
  3133   if (user_templatename != 0) {
  3207     if( access(user_templatename,004)==-1 ){
  3134     if( access(user_templatename,004)==-1 ){
  3208       fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
  3135       fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
  3209         user_templatename);
  3136         user_templatename);
  3210       lemp->errorcnt++;
  3137       lemp->errorcnt++;
  3216       lemp->errorcnt++;
  3143       lemp->errorcnt++;
  3217       return 0;
  3144       return 0;
  3218     }
  3145     }
  3219     return in;
  3146     return in;
  3220   }
  3147   }
  3221   #endif
       
  3222 
  3148 
  3223   cp = strrchr(lemp->filename,'.');
  3149   cp = strrchr(lemp->filename,'.');
  3224   if( cp ){
  3150   if( cp ){
  3225     sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
  3151     sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
  3226   }else{
  3152   }else{
  3247   }
  3173   }
  3248   return in;
  3174   return in;
  3249 }
  3175 }
  3250 
  3176 
  3251 /* Print a #line directive line to the output file. */
  3177 /* Print a #line directive line to the output file. */
  3252 PRIVATE void tplt_linedir(out,lineno,filename)
  3178 PRIVATE void tplt_linedir(FILE *out, int lineno, char *filename)
  3253 FILE *out;
       
  3254 int lineno;
       
  3255 char *filename;
       
  3256 {
  3179 {
  3257   fprintf(out,"#line %d \"",lineno);
  3180   fprintf(out,"#line %d \"",lineno);
  3258   while( *filename ){
  3181   while( *filename ){
  3259     if( *filename == '\\' ) putc('\\',out);
  3182     if( *filename == '\\' ) putc('\\',out);
  3260     putc(*filename,out);
  3183     putc(*filename,out);
  3262   }
  3185   }
  3263   fprintf(out,"\"\n");
  3186   fprintf(out,"\"\n");
  3264 }
  3187 }
  3265 
  3188 
  3266 /* Print a string to the file and keep the linenumber up to date */
  3189 /* Print a string to the file and keep the linenumber up to date */
  3267 PRIVATE void tplt_print(out,lemp,str,lineno)
  3190 PRIVATE void tplt_print(FILE *out, struct lemon *lemp, char *str, int *lineno)
  3268 FILE *out;
       
  3269 struct lemon *lemp;
       
  3270 char *str;
       
  3271 int *lineno;
       
  3272 {
  3191 {
  3273   if( str==0 ) return;
  3192   if( str==0 ) return;
  3274   while( *str ){
  3193   while( *str ){
  3275     putc(*str,out);
  3194     putc(*str,out);
  3276     if( *str=='\n' ) (*lineno)++;
  3195     if( *str=='\n' ) (*lineno)++;
  3288 
  3207 
  3289 /*
  3208 /*
  3290 ** The following routine emits code for the destructor for the
  3209 ** The following routine emits code for the destructor for the
  3291 ** symbol sp
  3210 ** symbol sp
  3292 */
  3211 */
  3293 void emit_destructor_code(out,sp,lemp,lineno)
  3212 void emit_destructor_code(
  3294 FILE *out;
  3213   FILE *out,
  3295 struct symbol *sp;
  3214   struct symbol *sp,
  3296 struct lemon *lemp;
  3215   struct lemon *lemp,
  3297 int *lineno;
  3216   int *lineno
  3298 {
  3217 ){
  3299  char *cp = 0;
  3218  char *cp = 0;
  3300 
  3219 
  3301  if( sp->type==TERMINAL ){
  3220  if( sp->type==TERMINAL ){
  3302    cp = lemp->tokendest;
  3221    cp = lemp->tokendest;
  3303    if( cp==0 ) return;
  3222    if( cp==0 ) return;
  3331 }
  3250 }
  3332 
  3251 
  3333 /*
  3252 /*
  3334 ** Return TRUE (non-zero) if the given symbol has a destructor.
  3253 ** Return TRUE (non-zero) if the given symbol has a destructor.
  3335 */
  3254 */
  3336 int has_destructor(sp, lemp)
  3255 int has_destructor(struct symbol *sp, struct lemon *lemp)
  3337 struct symbol *sp;
       
  3338 struct lemon *lemp;
       
  3339 {
  3256 {
  3340   int ret;
  3257   int ret;
  3341   if( sp->type==TERMINAL ){
  3258   if( sp->type==TERMINAL ){
  3342     ret = lemp->tokendest!=0;
  3259     ret = lemp->tokendest!=0;
  3343   }else{
  3260   }else{
  3356 ** %d.  The values of p1 and p2 are written into the first and second
  3273 ** %d.  The values of p1 and p2 are written into the first and second
  3357 ** %d.
  3274 ** %d.
  3358 **
  3275 **
  3359 ** If n==-1, then the previous character is overwritten.
  3276 ** If n==-1, then the previous character is overwritten.
  3360 */
  3277 */
  3361 PRIVATE char *append_str(char *zText, int n, int p1, int p2){
  3278 PRIVATE char *append_str(const char *zText, int n, int p1, int p2){
       
  3279   static char empty[1] = { 0 };
  3362   static char *z = 0;
  3280   static char *z = 0;
  3363   static int alloced = 0;
  3281   static int alloced = 0;
  3364   static int used = 0;
  3282   static int used = 0;
  3365   int c;
  3283   int c;
  3366   char zInt[40];
  3284   char zInt[40];
  3367 
       
  3368   if( zText==0 ){
  3285   if( zText==0 ){
  3369     used = 0;
  3286     used = 0;
  3370     return z;
  3287     return z;
  3371   }
  3288   }
  3372   if( n<=0 ){
  3289   if( n<=0 ){
  3376     }
  3293     }
  3377     n = lemonStrlen(zText);
  3294     n = lemonStrlen(zText);
  3378   }
  3295   }
  3379   if( n+sizeof(zInt)*2+used >= alloced ){
  3296   if( n+sizeof(zInt)*2+used >= alloced ){
  3380     alloced = n + sizeof(zInt)*2 + used + 200;
  3297     alloced = n + sizeof(zInt)*2 + used + 200;
  3381     z = realloc(z,  alloced);
  3298     z = (char *) realloc(z,  alloced);
  3382   }
  3299   }
  3383   if( z==0 ) return "";
  3300   if( z==0 ) return empty;
  3384   while( n-- > 0 ){
  3301   while( n-- > 0 ){
  3385     c = *(zText++);
  3302     c = *(zText++);
  3386     if( c=='%' && n>0 && zText[0]=='d' ){
  3303     if( c=='%' && n>0 && zText[0]=='d' ){
  3387       sprintf(zInt, "%d", p1);
  3304       sprintf(zInt, "%d", p1);
  3388       p1 = p2;
  3305       p1 = p2;
  3411 
  3328 
  3412   for(i=0; i<rp->nrhs; i++) used[i] = 0;
  3329   for(i=0; i<rp->nrhs; i++) used[i] = 0;
  3413   lhsused = 0;
  3330   lhsused = 0;
  3414 
  3331 
  3415   if( rp->code==0 ){
  3332   if( rp->code==0 ){
  3416     rp->code = "\n";
  3333     static char newlinestr[2] = { '\n', '\0' };
       
  3334     rp->code = newlinestr;
  3417     rp->line = rp->ruleline;
  3335     rp->line = rp->ruleline;
  3418   }
  3336   }
  3419 
  3337 
  3420   append_str(0,0,0,0);
  3338   append_str(0,0,0,0);
  3421   for(cp=rp->code; *cp; cp++){
  3339 
       
  3340   /* This const cast is wrong but harmless, if we're careful. */
       
  3341   for(cp=(char *)rp->code; *cp; cp++){
  3422     if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
  3342     if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
  3423       char saved;
  3343       char saved;
  3424       for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
  3344       for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
  3425       saved = *xp;
  3345       saved = *xp;
  3426       *xp = 0;
  3346       *xp = 0;
  3489 
  3409 
  3490 /* 
  3410 /* 
  3491 ** Generate code which executes when the rule "rp" is reduced.  Write
  3411 ** Generate code which executes when the rule "rp" is reduced.  Write
  3492 ** the code to "out".  Make sure lineno stays up-to-date.
  3412 ** the code to "out".  Make sure lineno stays up-to-date.
  3493 */
  3413 */
  3494 PRIVATE void emit_code(out,rp,lemp,lineno)
  3414 PRIVATE void emit_code(
  3495 FILE *out;
  3415   FILE *out,
  3496 struct rule *rp;
  3416   struct rule *rp,
  3497 struct lemon *lemp;
  3417   struct lemon *lemp,
  3498 int *lineno;
  3418   int *lineno
  3499 {
  3419 ){
  3500  char *cp;
  3420  const char *cp;
  3501 
  3421 
  3502  /* Generate code to do the reduce action */
  3422  /* Generate code to do the reduce action */
  3503  if( rp->code ){
  3423  if( rp->code ){
  3504    if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,rp->line,lemp->filename); }
  3424    if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,rp->line,lemp->filename); }
  3505    fprintf(out,"{%s",rp->code);
  3425    fprintf(out,"{%s",rp->code);
  3518 ** This union contains fields for every possible data type for tokens
  3438 ** This union contains fields for every possible data type for tokens
  3519 ** and nonterminals.  In the process of computing and printing this
  3439 ** and nonterminals.  In the process of computing and printing this
  3520 ** union, also set the ".dtnum" field of every terminal and nonterminal
  3440 ** union, also set the ".dtnum" field of every terminal and nonterminal
  3521 ** symbol.
  3441 ** symbol.
  3522 */
  3442 */
  3523 void print_stack_union(out,lemp,plineno,mhflag)
  3443 void print_stack_union(
  3524 FILE *out;                  /* The output stream */
  3444   FILE *out,                  /* The output stream */
  3525 struct lemon *lemp;         /* The main info structure for this parser */
  3445   struct lemon *lemp,         /* The main info structure for this parser */
  3526 int *plineno;               /* Pointer to the line number */
  3446   int *plineno,               /* Pointer to the line number */
  3527 int mhflag;                 /* True if generating makeheaders output */
  3447   int mhflag                  /* True if generating makeheaders output */
  3528 {
  3448 ){
  3529   int lineno = *plineno;    /* The line number of the output */
  3449   int lineno = *plineno;    /* The line number of the output */
  3530   char **types;             /* A hash table of datatypes */
  3450   char **types;             /* A hash table of datatypes */
  3531   int arraysize;            /* Size of the "types" array */
  3451   int arraysize;            /* Size of the "types" array */
  3532   int maxdtlength;          /* Maximum length of any ".datatype" field. */
  3452   int maxdtlength;          /* Maximum length of any ".datatype" field. */
  3533   char *stddt;              /* Standardized name for a datatype */
  3453   char *stddt;              /* Standardized name for a datatype */
  3534   int i,j;                  /* Loop counters */
  3454   int i,j;                  /* Loop counters */
  3535   int hash;                 /* For hashing the name of a type */
  3455   int hash;                 /* For hashing the name of a type */
  3536   char *name;               /* Name of the parser */
  3456   const char *name;         /* Name of the parser */
  3537 
  3457 
  3538   /* Allocate and initialize types[] and allocate stddt[] */
  3458   /* Allocate and initialize types[] and allocate stddt[] */
  3539   arraysize = lemp->nsymbol * 2;
  3459   arraysize = lemp->nsymbol * 2;
  3540   types = (char**)calloc( arraysize, sizeof(char*) );
  3460   types = (char**)calloc( arraysize, sizeof(char*) );
  3541   for(i=0; i<arraysize; i++) types[i] = 0;
  3461   for(i=0; i<arraysize; i++) types[i] = 0;
  3578     j = 0;
  3498     j = 0;
  3579     while( isspace(*cp) ) cp++;
  3499     while( isspace(*cp) ) cp++;
  3580     while( *cp ) stddt[j++] = *cp++;
  3500     while( *cp ) stddt[j++] = *cp++;
  3581     while( j>0 && isspace(stddt[j-1]) ) j--;
  3501     while( j>0 && isspace(stddt[j-1]) ) j--;
  3582     stddt[j] = 0;
  3502     stddt[j] = 0;
  3583     if( strcmp(stddt, lemp->tokentype)==0 ){
  3503     if( lemp->tokentype && strcmp(stddt, lemp->tokentype)==0 ){
  3584       sp->dtnum = 0;
  3504       sp->dtnum = 0;
  3585       continue;
  3505       continue;
  3586     }
  3506     }
  3587     hash = 0;
  3507     hash = 0;
  3588     for(j=0; stddt[j]; j++){
  3508     for(j=0; stddt[j]; j++){
  3662 */
  3582 */
  3663 struct axset {
  3583 struct axset {
  3664   struct state *stp;   /* A pointer to a state */
  3584   struct state *stp;   /* A pointer to a state */
  3665   int isTkn;           /* True to use tokens.  False for non-terminals */
  3585   int isTkn;           /* True to use tokens.  False for non-terminals */
  3666   int nAction;         /* Number of actions */
  3586   int nAction;         /* Number of actions */
       
  3587   int iOrder;          /* Original order of action sets */
  3667 };
  3588 };
  3668 
  3589 
  3669 /*
  3590 /*
  3670 ** Compare to axset structures for sorting purposes
  3591 ** Compare to axset structures for sorting purposes
  3671 */
  3592 */
  3672 static int axset_compare(const void *a, const void *b){
  3593 static int axset_compare(const void *a, const void *b){
  3673   struct axset *p1 = (struct axset*)a;
  3594   struct axset *p1 = (struct axset*)a;
  3674   struct axset *p2 = (struct axset*)b;
  3595   struct axset *p2 = (struct axset*)b;
  3675   return p2->nAction - p1->nAction;
  3596   int c;
       
  3597   c = p2->nAction - p1->nAction;
       
  3598   if( c==0 ){
       
  3599     c = p2->iOrder - p1->iOrder;
       
  3600   }
       
  3601   assert( c!=0 || p1==p2 );
       
  3602   return c;
  3676 }
  3603 }
  3677 
  3604 
  3678 /*
  3605 /*
  3679 ** Write text on "out" that describes the rule "rp".
  3606 ** Write text on "out" that describes the rule "rp".
  3680 */
  3607 */
  3693   }
  3620   }
  3694 }
  3621 }
  3695 
  3622 
  3696 
  3623 
  3697 /* Generate C source code for the parser */
  3624 /* Generate C source code for the parser */
  3698 void ReportTable(lemp, mhflag)
  3625 void ReportTable(
  3699 struct lemon *lemp;
  3626   struct lemon *lemp,
  3700 int mhflag;     /* Output in makeheaders format if true */
  3627   int mhflag     /* Output in makeheaders format if true */
  3701 {
  3628 ){
  3702   FILE *out, *in;
  3629   FILE *out, *in;
  3703   char line[LINESIZE];
  3630   char line[LINESIZE];
  3704   int  lineno;
  3631   int  lineno;
  3705   struct state *stp;
  3632   struct state *stp;
  3706   struct action *ap;
  3633   struct action *ap;
  3707   struct rule *rp;
  3634   struct rule *rp;
  3708   struct acttab *pActtab;
  3635   struct acttab *pActtab;
  3709   int i, j, n;
  3636   int i, j, n;
  3710   char *name;
  3637   const char *name;
  3711   int mnTknOfst, mxTknOfst;
  3638   int mnTknOfst, mxTknOfst;
  3712   int mnNtOfst, mxNtOfst;
  3639   int mnNtOfst, mxNtOfst;
  3713   struct axset *ax;
  3640   struct axset *ax;
  3714 
  3641 
  3715   in = tplt_open(lemp);
  3642   in = tplt_open(lemp);
  3759   }
  3686   }
  3760   tplt_xfer(lemp->name,in,out,&lineno);
  3687   tplt_xfer(lemp->name,in,out,&lineno);
  3761 
  3688 
  3762   /* Generate the defines */
  3689   /* Generate the defines */
  3763   fprintf(out,"#define YYCODETYPE %s\n",
  3690   fprintf(out,"#define YYCODETYPE %s\n",
  3764     minimum_size_type(0, lemp->nsymbol+5)); lineno++;
  3691     minimum_size_type(0, lemp->nsymbol+1)); lineno++;
  3765   fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  3692   fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1);  lineno++;
  3766   fprintf(out,"#define YYACTIONTYPE %s\n",
  3693   fprintf(out,"#define YYACTIONTYPE %s\n",
  3767     minimum_size_type(0, lemp->nstate+lemp->nrule+5));  lineno++;
  3694     minimum_size_type(0, lemp->nstate+lemp->nrule+5));  lineno++;
  3768   if( lemp->wildcard ){
  3695   if( lemp->wildcard ){
  3769     fprintf(out,"#define YYWILDCARD %d\n",
  3696     fprintf(out,"#define YYWILDCARD %d\n",
  3823   **                     shifting non-terminals after a reduce.
  3750   **                     shifting non-terminals after a reduce.
  3824   **  yy_default[]       Default action for each state.
  3751   **  yy_default[]       Default action for each state.
  3825   */
  3752   */
  3826 
  3753 
  3827   /* Compute the actions on all states and count them up */
  3754   /* Compute the actions on all states and count them up */
  3828   ax = calloc(lemp->nstate*2, sizeof(ax[0]));
  3755   ax = (struct axset *) calloc(lemp->nstate*2, sizeof(ax[0]));
  3829   if( ax==0 ){
  3756   if( ax==0 ){
  3830     fprintf(stderr,"malloc failed\n");
  3757     fprintf(stderr,"malloc failed\n");
  3831     exit(1);
  3758     exit(1);
  3832   }
  3759   }
  3833   for(i=0; i<lemp->nstate; i++){
  3760   for(i=0; i<lemp->nstate; i++){
  3844 
  3771 
  3845   /* Compute the action table.  In order to try to keep the size of the
  3772   /* Compute the action table.  In order to try to keep the size of the
  3846   ** action table to a minimum, the heuristic of placing the largest action
  3773   ** action table to a minimum, the heuristic of placing the largest action
  3847   ** sets first is used.
  3774   ** sets first is used.
  3848   */
  3775   */
       
  3776   for(i=0; i<lemp->nstate*2; i++) ax[i].iOrder = i;
  3849   qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
  3777   qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
  3850   pActtab = acttab_alloc();
  3778   pActtab = acttab_alloc();
  3851   for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
  3779   for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
  3852     stp = ax[i].stp;
  3780     stp = ax[i].stp;
  3853     if( ax[i].isTkn ){
  3781     if( ax[i].isTkn ){
  3876     }
  3804     }
  3877   }
  3805   }
  3878   free(ax);
  3806   free(ax);
  3879 
  3807 
  3880   /* Output the yy_action table */
  3808   /* Output the yy_action table */
       
  3809   n = acttab_size(pActtab);
       
  3810   fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
  3881   fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
  3811   fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
  3882   n = acttab_size(pActtab);
       
  3883   for(i=j=0; i<n; i++){
  3812   for(i=j=0; i<n; i++){
  3884     int action = acttab_yyaction(pActtab, i);
  3813     int action = acttab_yyaction(pActtab, i);
  3885     if( action<0 ) action = lemp->nstate + lemp->nrule + 2;
  3814     if( action<0 ) action = lemp->nstate + lemp->nrule + 2;
  3886     if( j==0 ) fprintf(out," /* %5d */ ", i);
  3815     if( j==0 ) fprintf(out," /* %5d */ ", i);
  3887     fprintf(out, " %4d,", action);
  3816     fprintf(out, " %4d,", action);
  3912 
  3841 
  3913   /* Output the yy_shift_ofst[] table */
  3842   /* Output the yy_shift_ofst[] table */
  3914   fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
  3843   fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
  3915   n = lemp->nstate;
  3844   n = lemp->nstate;
  3916   while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
  3845   while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
  3917   fprintf(out, "#define YY_SHIFT_MAX %d\n", n-1); lineno++;
  3846   fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;
       
  3847   fprintf(out, "#define YY_SHIFT_MIN   (%d)\n", mnTknOfst); lineno++;
       
  3848   fprintf(out, "#define YY_SHIFT_MAX   (%d)\n", mxTknOfst); lineno++;
  3918   fprintf(out, "static const %s yy_shift_ofst[] = {\n", 
  3849   fprintf(out, "static const %s yy_shift_ofst[] = {\n", 
  3919           minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
  3850           minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
  3920   for(i=j=0; i<n; i++){
  3851   for(i=j=0; i<n; i++){
  3921     int ofst;
  3852     int ofst;
  3922     stp = lemp->sorted[i];
  3853     stp = lemp->sorted[i];
  3935 
  3866 
  3936   /* Output the yy_reduce_ofst[] table */
  3867   /* Output the yy_reduce_ofst[] table */
  3937   fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
  3868   fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
  3938   n = lemp->nstate;
  3869   n = lemp->nstate;
  3939   while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
  3870   while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
  3940   fprintf(out, "#define YY_REDUCE_MAX %d\n", n-1); lineno++;
  3871   fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
       
  3872   fprintf(out, "#define YY_REDUCE_MIN   (%d)\n", mnNtOfst); lineno++;
       
  3873   fprintf(out, "#define YY_REDUCE_MAX   (%d)\n", mxNtOfst); lineno++;
  3941   fprintf(out, "static const %s yy_reduce_ofst[] = {\n", 
  3874   fprintf(out, "static const %s yy_reduce_ofst[] = {\n", 
  3942           minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
  3875           minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
  3943   for(i=j=0; i<n; i++){
  3876   for(i=j=0; i<n; i++){
  3944     int ofst;
  3877     int ofst;
  3945     stp = lemp->sorted[i];
  3878     stp = lemp->sorted[i];
  3974   tplt_xfer(lemp->name,in,out,&lineno);
  3907   tplt_xfer(lemp->name,in,out,&lineno);
  3975 
  3908 
  3976   /* Generate the table of fallback tokens.
  3909   /* Generate the table of fallback tokens.
  3977   */
  3910   */
  3978   if( lemp->has_fallback ){
  3911   if( lemp->has_fallback ){
  3979     for(i=0; i<lemp->nterminal; i++){
  3912     int mx = lemp->nterminal - 1;
       
  3913     while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; }
       
  3914     for(i=0; i<=mx; i++){
  3980       struct symbol *p = lemp->symbols[i];
  3915       struct symbol *p = lemp->symbols[i];
  3981       if( p->fallback==0 ){
  3916       if( p->fallback==0 ){
  3982         fprintf(out, "    0,  /* %10s => nothing */\n", p->name);
  3917         fprintf(out, "    0,  /* %10s => nothing */\n", p->name);
  3983       }else{
  3918       }else{
  3984         fprintf(out, "  %3d,  /* %10s => %s */\n", p->fallback->index,
  3919         fprintf(out, "  %3d,  /* %10s => %s */\n", p->fallback->index,
  4022       if( sp==0 || sp->type!=TERMINAL ) continue;
  3957       if( sp==0 || sp->type!=TERMINAL ) continue;
  4023       if( once ){
  3958       if( once ){
  4024         fprintf(out, "      /* TERMINAL Destructor */\n"); lineno++;
  3959         fprintf(out, "      /* TERMINAL Destructor */\n"); lineno++;
  4025         once = 0;
  3960         once = 0;
  4026       }
  3961       }
  4027       fprintf(out,"    case %d: /* %s */\n",
  3962       fprintf(out,"    case %d: /* %s */\n", sp->index, sp->name); lineno++;
  4028               sp->index, sp->name); lineno++;
       
  4029     }
  3963     }
  4030     for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
  3964     for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
  4031     if( i<lemp->nsymbol ){
  3965     if( i<lemp->nsymbol ){
  4032       emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
  3966       emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
  4033       fprintf(out,"      break;\n"); lineno++;
  3967       fprintf(out,"      break;\n"); lineno++;
  4042           sp->index<=0 || sp->destructor!=0 ) continue;
  3976           sp->index<=0 || sp->destructor!=0 ) continue;
  4043       if( once ){
  3977       if( once ){
  4044         fprintf(out, "      /* Default NON-TERMINAL Destructor */\n"); lineno++;
  3978         fprintf(out, "      /* Default NON-TERMINAL Destructor */\n"); lineno++;
  4045         once = 0;
  3979         once = 0;
  4046       }
  3980       }
  4047       fprintf(out,"    case %d: /* %s */\n",
  3981       fprintf(out,"    case %d: /* %s */\n", sp->index, sp->name); lineno++;
  4048               sp->index, sp->name); lineno++;
       
  4049       dflt_sp = sp;
  3982       dflt_sp = sp;
  4050     }
  3983     }
  4051     if( dflt_sp!=0 ){
  3984     if( dflt_sp!=0 ){
  4052       emit_destructor_code(out,dflt_sp,lemp,&lineno);
  3985       emit_destructor_code(out,dflt_sp,lemp,&lineno);
  4053     }
  3986     }
  4054     fprintf(out,"      break;\n"); lineno++;
  3987     fprintf(out,"      break;\n"); lineno++;
  4055   }
  3988   }
  4056   for(i=0; i<lemp->nsymbol; i++){
  3989   for(i=0; i<lemp->nsymbol; i++){
  4057     struct symbol *sp = lemp->symbols[i];
  3990     struct symbol *sp = lemp->symbols[i];
  4058     if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
  3991     if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
  4059     fprintf(out,"    case %d: /* %s */\n",
  3992     fprintf(out,"    case %d: /* %s */\n", sp->index, sp->name); lineno++;
  4060             sp->index, sp->name); lineno++;
       
  4061 
  3993 
  4062     /* Combine duplicate destructors into a single case */
  3994     /* Combine duplicate destructors into a single case */
  4063     for(j=i+1; j<lemp->nsymbol; j++){
  3995     for(j=i+1; j<lemp->nsymbol; j++){
  4064       struct symbol *sp2 = lemp->symbols[j];
  3996       struct symbol *sp2 = lemp->symbols[j];
  4065       if( sp2 && sp2->type!=TERMINAL && sp2->destructor
  3997       if( sp2 && sp2->type!=TERMINAL && sp2->destructor
  4092 
  4024 
  4093   /* Generate code which execution during each REDUCE action */
  4025   /* Generate code which execution during each REDUCE action */
  4094   for(rp=lemp->rule; rp; rp=rp->next){
  4026   for(rp=lemp->rule; rp; rp=rp->next){
  4095     translate_code(lemp, rp);
  4027     translate_code(lemp, rp);
  4096   }
  4028   }
       
  4029   /* First output rules other than the default: rule */
  4097   for(rp=lemp->rule; rp; rp=rp->next){
  4030   for(rp=lemp->rule; rp; rp=rp->next){
  4098     struct rule *rp2;
  4031     struct rule *rp2;               /* Other rules with the same action */
  4099     if( rp->code==0 ) continue;
  4032     if( rp->code==0 ) continue;
       
  4033     if( rp->code[0]=='\n' && rp->code[1]==0 ) continue; /* Will be default: */
  4100     fprintf(out,"      case %d: /* ", rp->index);
  4034     fprintf(out,"      case %d: /* ", rp->index);
  4101     writeRuleText(out, rp);
  4035     writeRuleText(out, rp);
  4102     fprintf(out, " */\n"); lineno++;
  4036     fprintf(out, " */\n"); lineno++;
  4103     for(rp2=rp->next; rp2; rp2=rp2->next){
  4037     for(rp2=rp->next; rp2; rp2=rp2->next){
  4104       if( rp2->code==rp->code ){
  4038       if( rp2->code==rp->code ){
  4105         fprintf(out,"      case %d: /* ", rp2->index);
  4039         fprintf(out,"      case %d: /* ", rp2->index);
  4106         writeRuleText(out, rp2);
  4040         writeRuleText(out, rp2);
  4107         fprintf(out," */\n"); lineno++;
  4041         fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->index); lineno++;
  4108         rp2->code = 0;
  4042         rp2->code = 0;
  4109       }
  4043       }
  4110     }
  4044     }
  4111     emit_code(out,rp,lemp,&lineno);
  4045     emit_code(out,rp,lemp,&lineno);
  4112     fprintf(out,"        break;\n"); lineno++;
  4046     fprintf(out,"        break;\n"); lineno++;
  4113   }
  4047     rp->code = 0;
       
  4048   }
       
  4049   /* Finally, output the default: rule.  We choose as the default: all
       
  4050   ** empty actions. */
       
  4051   fprintf(out,"      default:\n"); lineno++;
       
  4052   for(rp=lemp->rule; rp; rp=rp->next){
       
  4053     if( rp->code==0 ) continue;
       
  4054     assert( rp->code[0]=='\n' && rp->code[1]==0 );
       
  4055     fprintf(out,"      /* (%d) ", rp->index);
       
  4056     writeRuleText(out, rp);
       
  4057     fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->index); lineno++;
       
  4058   }
       
  4059   fprintf(out,"        break;\n"); lineno++;
  4114   tplt_xfer(lemp->name,in,out,&lineno);
  4060   tplt_xfer(lemp->name,in,out,&lineno);
  4115 
  4061 
  4116   /* Generate code which executes if a parse fails */
  4062   /* Generate code which executes if a parse fails */
  4117   tplt_print(out,lemp,lemp->failure,&lineno);
  4063   tplt_print(out,lemp,lemp->failure,&lineno);
  4118   tplt_xfer(lemp->name,in,out,&lineno);
  4064   tplt_xfer(lemp->name,in,out,&lineno);
  4132   fclose(out);
  4078   fclose(out);
  4133   return;
  4079   return;
  4134 }
  4080 }
  4135 
  4081 
  4136 /* Generate a header file for the parser */
  4082 /* Generate a header file for the parser */
  4137 void ReportHeader(lemp)
  4083 void ReportHeader(struct lemon *lemp)
  4138 struct lemon *lemp;
       
  4139 {
  4084 {
  4140   FILE *out, *in;
  4085   FILE *out, *in;
  4141   char *prefix;
  4086   const char *prefix;
  4142   char line[LINESIZE];
  4087   char line[LINESIZE];
  4143   char pattern[LINESIZE];
  4088   char pattern[LINESIZE];
  4144   int i;
  4089   int i;
  4145 
  4090 
  4146   if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
  4091   if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
  4172 **
  4117 **
  4173 ** In this version, we take the most frequent REDUCE action and make
  4118 ** In this version, we take the most frequent REDUCE action and make
  4174 ** it the default.  Except, there is no default if the wildcard token
  4119 ** it the default.  Except, there is no default if the wildcard token
  4175 ** is a possible look-ahead.
  4120 ** is a possible look-ahead.
  4176 */
  4121 */
  4177 void CompressTables(lemp)
  4122 void CompressTables(struct lemon *lemp)
  4178 struct lemon *lemp;
       
  4179 {
  4123 {
  4180   struct state *stp;
  4124   struct state *stp;
  4181   struct action *ap, *ap2;
  4125   struct action *ap, *ap2;
  4182   struct rule *rp, *rp2, *rbest;
  4126   struct rule *rp, *rp2, *rbest;
  4183   int nbest, n;
  4127   int nbest, n;
  4244   int n;
  4188   int n;
  4245 
  4189 
  4246   n = pB->nNtAct - pA->nNtAct;
  4190   n = pB->nNtAct - pA->nNtAct;
  4247   if( n==0 ){
  4191   if( n==0 ){
  4248     n = pB->nTknAct - pA->nTknAct;
  4192     n = pB->nTknAct - pA->nTknAct;
  4249   }
  4193     if( n==0 ){
       
  4194       n = pB->statenum - pA->statenum;
       
  4195     }
       
  4196   }
       
  4197   assert( n!=0 );
  4250   return n;
  4198   return n;
  4251 }
  4199 }
  4252 
  4200 
  4253 
  4201 
  4254 /*
  4202 /*
  4255 ** Renumber and resort states so that states with fewer choices
  4203 ** Renumber and resort states so that states with fewer choices
  4256 ** occur at the end.  Except, keep state 0 as the first state.
  4204 ** occur at the end.  Except, keep state 0 as the first state.
  4257 */
  4205 */
  4258 void ResortStates(lemp)
  4206 void ResortStates(struct lemon *lemp)
  4259 struct lemon *lemp;
       
  4260 {
  4207 {
  4261   int i;
  4208   int i;
  4262   struct state *stp;
  4209   struct state *stp;
  4263   struct action *ap;
  4210   struct action *ap;
  4264 
  4211 
  4294 */
  4241 */
  4295 
  4242 
  4296 static int size = 0;
  4243 static int size = 0;
  4297 
  4244 
  4298 /* Set the set size */
  4245 /* Set the set size */
  4299 void SetSize(n)
  4246 void SetSize(int n)
  4300 int n;
       
  4301 {
  4247 {
  4302   size = n+1;
  4248   size = n+1;
  4303 }
  4249 }
  4304 
  4250 
  4305 /* Allocate a new set */
  4251 /* Allocate a new set */
  4312   }
  4258   }
  4313   return s;
  4259   return s;
  4314 }
  4260 }
  4315 
  4261 
  4316 /* Deallocate a set */
  4262 /* Deallocate a set */
  4317 void SetFree(s)
  4263 void SetFree(char *s)
  4318 char *s;
       
  4319 {
  4264 {
  4320   free(s);
  4265   free(s);
  4321 }
  4266 }
  4322 
  4267 
  4323 /* Add a new element to the set.  Return TRUE if the element was added
  4268 /* Add a new element to the set.  Return TRUE if the element was added
  4324 ** and FALSE if it was already there. */
  4269 ** and FALSE if it was already there. */
  4325 int SetAdd(s,e)
  4270 int SetAdd(char *s, int e)
  4326 char *s;
       
  4327 int e;
       
  4328 {
  4271 {
  4329   int rv;
  4272   int rv;
  4330   assert( e>=0 && e<size );
  4273   assert( e>=0 && e<size );
  4331   rv = s[e];
  4274   rv = s[e];
  4332   s[e] = 1;
  4275   s[e] = 1;
  4333   return !rv;
  4276   return !rv;
  4334 }
  4277 }
  4335 
  4278 
  4336 /* Add every element of s2 to s1.  Return TRUE if s1 changes. */
  4279 /* Add every element of s2 to s1.  Return TRUE if s1 changes. */
  4337 int SetUnion(s1,s2)
  4280 int SetUnion(char *s1, char *s2)
  4338 char *s1;
       
  4339 char *s2;
       
  4340 {
  4281 {
  4341   int i, progress;
  4282   int i, progress;
  4342   progress = 0;
  4283   progress = 0;
  4343   for(i=0; i<size; i++){
  4284   for(i=0; i<size; i++){
  4344     if( s2[i]==0 ) continue;
  4285     if( s2[i]==0 ) continue;
  4360 */
  4301 */
  4361 /*
  4302 /*
  4362 ** Code for processing tables in the LEMON parser generator.
  4303 ** Code for processing tables in the LEMON parser generator.
  4363 */
  4304 */
  4364 
  4305 
  4365 PRIVATE int strhash(x)
  4306 PRIVATE int strhash(const char *x)
  4366 char *x;
       
  4367 {
  4307 {
  4368   int h = 0;
  4308   int h = 0;
  4369   while( *x) h = h*13 + *(x++);
  4309   while( *x) h = h*13 + *(x++);
  4370   return h;
  4310   return h;
  4371 }
  4311 }
  4372 
  4312 
  4373 /* Works like strdup, sort of.  Save a string in malloced memory, but
  4313 /* Works like strdup, sort of.  Save a string in malloced memory, but
  4374 ** keep strings in a table so that the same string is not in more
  4314 ** keep strings in a table so that the same string is not in more
  4375 ** than one place.
  4315 ** than one place.
  4376 */
  4316 */
  4377 char *Strsafe(y)
  4317 const char *Strsafe(const char *y)
  4378 char *y;
  4318 {
  4379 {
  4319   const char *z;
  4380   char *z;
  4320   char *cpy;
  4381 
  4321 
  4382   if( y==0 ) return 0;
  4322   if( y==0 ) return 0;
  4383   z = Strsafe_find(y);
  4323   z = Strsafe_find(y);
  4384   if( z==0 && (z=malloc( lemonStrlen(y)+1 ))!=0 ){
  4324   if( z==0 && (cpy=(char *)malloc( lemonStrlen(y)+1 ))!=0 ){
  4385     strcpy(z,y);
  4325     strcpy(cpy,y);
       
  4326     z = cpy;
  4386     Strsafe_insert(z);
  4327     Strsafe_insert(z);
  4387   }
  4328   }
  4388   MemoryCheck(z);
  4329   MemoryCheck(z);
  4389   return z;
  4330   return z;
  4390 }
  4331 }
  4403 
  4344 
  4404 /* There is one instance of this structure for every data element
  4345 /* There is one instance of this structure for every data element
  4405 ** in an associative array of type "x1".
  4346 ** in an associative array of type "x1".
  4406 */
  4347 */
  4407 typedef struct s_x1node {
  4348 typedef struct s_x1node {
  4408   char *data;                  /* The data */
  4349   const char *data;        /* The data */
  4409   struct s_x1node *next;   /* Next entry with the same hash */
  4350   struct s_x1node *next;   /* Next entry with the same hash */
  4410   struct s_x1node **from;  /* Previous link */
  4351   struct s_x1node **from;  /* Previous link */
  4411 } x1node;
  4352 } x1node;
  4412 
  4353 
  4413 /* There is only one instance of the array, which is the following */
  4354 /* There is only one instance of the array, which is the following */
  4432     }
  4373     }
  4433   }
  4374   }
  4434 }
  4375 }
  4435 /* Insert a new record into the array.  Return TRUE if successful.
  4376 /* Insert a new record into the array.  Return TRUE if successful.
  4436 ** Prior data with the same key is NOT overwritten */
  4377 ** Prior data with the same key is NOT overwritten */
  4437 int Strsafe_insert(data)
  4378 int Strsafe_insert(const char *data)
  4438 char *data;
       
  4439 {
  4379 {
  4440   x1node *np;
  4380   x1node *np;
  4441   int h;
  4381   int h;
  4442   int ph;
  4382   int ph;
  4443 
  4383 
  4489   return 1;
  4429   return 1;
  4490 }
  4430 }
  4491 
  4431 
  4492 /* Return a pointer to data assigned to the given key.  Return NULL
  4432 /* Return a pointer to data assigned to the given key.  Return NULL
  4493 ** if no such key. */
  4433 ** if no such key. */
  4494 char *Strsafe_find(key)
  4434 const char *Strsafe_find(const char *key)
  4495 char *key;
       
  4496 {
  4435 {
  4497   int h;
  4436   int h;
  4498   x1node *np;
  4437   x1node *np;
  4499 
  4438 
  4500   if( x1a==0 ) return 0;
  4439   if( x1a==0 ) return 0;
  4508 }
  4447 }
  4509 
  4448 
  4510 /* Return a pointer to the (terminal or nonterminal) symbol "x".
  4449 /* Return a pointer to the (terminal or nonterminal) symbol "x".
  4511 ** Create a new symbol if this is the first time "x" has been seen.
  4450 ** Create a new symbol if this is the first time "x" has been seen.
  4512 */
  4451 */
  4513 struct symbol *Symbol_new(x)
  4452 struct symbol *Symbol_new(const char *x)
  4514 char *x;
       
  4515 {
  4453 {
  4516   struct symbol *sp;
  4454   struct symbol *sp;
  4517 
  4455 
  4518   sp = Symbol_find(x);
  4456   sp = Symbol_find(x);
  4519   if( sp==0 ){
  4457   if( sp==0 ){
  4545 **
  4483 **
  4546 ** We find experimentally that leaving the symbols in their original
  4484 ** We find experimentally that leaving the symbols in their original
  4547 ** order (the order they appeared in the grammar file) gives the
  4485 ** order (the order they appeared in the grammar file) gives the
  4548 ** smallest parser tables in SQLite.
  4486 ** smallest parser tables in SQLite.
  4549 */
  4487 */
  4550 int Symbolcmpp(struct symbol **a, struct symbol **b){
  4488 int Symbolcmpp(const void *_a, const void *_b)
       
  4489 {
       
  4490   const struct symbol **a = (const struct symbol **) _a;
       
  4491   const struct symbol **b = (const struct symbol **) _b;
  4551   int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
  4492   int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
  4552   int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
  4493   int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
       
  4494   assert( i1!=i2 || strcmp((**a).name,(**b).name)==0 );
  4553   return i1-i2;
  4495   return i1-i2;
  4554 }
  4496 }
  4555 
  4497 
  4556 /* There is one instance of the following structure for each
  4498 /* There is one instance of the following structure for each
  4557 ** associative array of type "x2".
  4499 ** associative array of type "x2".
  4567 
  4509 
  4568 /* There is one instance of this structure for every data element
  4510 /* There is one instance of this structure for every data element
  4569 ** in an associative array of type "x2".
  4511 ** in an associative array of type "x2".
  4570 */
  4512 */
  4571 typedef struct s_x2node {
  4513 typedef struct s_x2node {
  4572   struct symbol *data;                  /* The data */
  4514   struct symbol *data;     /* The data */
  4573   char *key;                   /* The key */
  4515   const char *key;         /* The key */
  4574   struct s_x2node *next;   /* Next entry with the same hash */
  4516   struct s_x2node *next;   /* Next entry with the same hash */
  4575   struct s_x2node **from;  /* Previous link */
  4517   struct s_x2node **from;  /* Previous link */
  4576 } x2node;
  4518 } x2node;
  4577 
  4519 
  4578 /* There is only one instance of the array, which is the following */
  4520 /* There is only one instance of the array, which is the following */
  4597     }
  4539     }
  4598   }
  4540   }
  4599 }
  4541 }
  4600 /* Insert a new record into the array.  Return TRUE if successful.
  4542 /* Insert a new record into the array.  Return TRUE if successful.
  4601 ** Prior data with the same key is NOT overwritten */
  4543 ** Prior data with the same key is NOT overwritten */
  4602 int Symbol_insert(data,key)
  4544 int Symbol_insert(struct symbol *data, const char *key)
  4603 struct symbol *data;
       
  4604 char *key;
       
  4605 {
  4545 {
  4606   x2node *np;
  4546   x2node *np;
  4607   int h;
  4547   int h;
  4608   int ph;
  4548   int ph;
  4609 
  4549 
  4657   return 1;
  4597   return 1;
  4658 }
  4598 }
  4659 
  4599 
  4660 /* Return a pointer to data assigned to the given key.  Return NULL
  4600 /* Return a pointer to data assigned to the given key.  Return NULL
  4661 ** if no such key. */
  4601 ** if no such key. */
  4662 struct symbol *Symbol_find(key)
  4602 struct symbol *Symbol_find(const char *key)
  4663 char *key;
       
  4664 {
  4603 {
  4665   int h;
  4604   int h;
  4666   x2node *np;
  4605   x2node *np;
  4667 
  4606 
  4668   if( x2a==0 ) return 0;
  4607   if( x2a==0 ) return 0;
  4674   }
  4613   }
  4675   return np ? np->data : 0;
  4614   return np ? np->data : 0;
  4676 }
  4615 }
  4677 
  4616 
  4678 /* Return the n-th data.  Return NULL if n is out of range. */
  4617 /* Return the n-th data.  Return NULL if n is out of range. */
  4679 struct symbol *Symbol_Nth(n)
  4618 struct symbol *Symbol_Nth(int n)
  4680 int n;
       
  4681 {
  4619 {
  4682   struct symbol *data;
  4620   struct symbol *data;
  4683   if( x2a && n>0 && n<=x2a->count ){
  4621   if( x2a && n>0 && n<=x2a->count ){
  4684     data = x2a->tbl[n-1].data;
  4622     data = x2a->tbl[n-1].data;
  4685   }else{
  4623   }else{
  4709   }
  4647   }
  4710   return array;
  4648   return array;
  4711 }
  4649 }
  4712 
  4650 
  4713 /* Compare two configurations */
  4651 /* Compare two configurations */
  4714 int Configcmp(a,b)
  4652 int Configcmp(const char *_a,const char *_b)
  4715 struct config *a;
  4653 {
  4716 struct config *b;
  4654   const struct config *a = (struct config *) _a;
  4717 {
  4655   const struct config *b = (struct config *) _b;
  4718   int x;
  4656   int x;
  4719   x = a->rp->index - b->rp->index;
  4657   x = a->rp->index - b->rp->index;
  4720   if( x==0 ) x = a->dot - b->dot;
  4658   if( x==0 ) x = a->dot - b->dot;
  4721   return x;
  4659   return x;
  4722 }
  4660 }
  4723 
  4661 
  4724 /* Compare two states */
  4662 /* Compare two states */
  4725 PRIVATE int statecmp(a,b)
  4663 PRIVATE int statecmp(struct config *a, struct config *b)
  4726 struct config *a;
       
  4727 struct config *b;
       
  4728 {
  4664 {
  4729   int rc;
  4665   int rc;
  4730   for(rc=0; rc==0 && a && b;  a=a->bp, b=b->bp){
  4666   for(rc=0; rc==0 && a && b;  a=a->bp, b=b->bp){
  4731     rc = a->rp->index - b->rp->index;
  4667     rc = a->rp->index - b->rp->index;
  4732     if( rc==0 ) rc = a->dot - b->dot;
  4668     if( rc==0 ) rc = a->dot - b->dot;
  4737   }
  4673   }
  4738   return rc;
  4674   return rc;
  4739 }
  4675 }
  4740 
  4676 
  4741 /* Hash a state */
  4677 /* Hash a state */
  4742 PRIVATE int statehash(a)
  4678 PRIVATE int statehash(struct config *a)
  4743 struct config *a;
       
  4744 {
  4679 {
  4745   int h=0;
  4680   int h=0;
  4746   while( a ){
  4681   while( a ){
  4747     h = h*571 + a->rp->index*37 + a->dot;
  4682     h = h*571 + a->rp->index*37 + a->dot;
  4748     a = a->bp;
  4683     a = a->bp;
  4751 }
  4686 }
  4752 
  4687 
  4753 /* Allocate a new state structure */
  4688 /* Allocate a new state structure */
  4754 struct state *State_new()
  4689 struct state *State_new()
  4755 {
  4690 {
  4756   struct state *new;
  4691   struct state *newstate;
  4757   new = (struct state *)calloc(1, sizeof(struct state) );
  4692   newstate = (struct state *)calloc(1, sizeof(struct state) );
  4758   MemoryCheck(new);
  4693   MemoryCheck(newstate);
  4759   return new;
  4694   return newstate;
  4760 }
  4695 }
  4761 
  4696 
  4762 /* There is one instance of the following structure for each
  4697 /* There is one instance of the following structure for each
  4763 ** associative array of type "x3".
  4698 ** associative array of type "x3".
  4764 */
  4699 */
  4803     }
  4738     }
  4804   }
  4739   }
  4805 }
  4740 }
  4806 /* Insert a new record into the array.  Return TRUE if successful.
  4741 /* Insert a new record into the array.  Return TRUE if successful.
  4807 ** Prior data with the same key is NOT overwritten */
  4742 ** Prior data with the same key is NOT overwritten */
  4808 int State_insert(data,key)
  4743 int State_insert(struct state *data, struct config *key)
  4809 struct state *data;
       
  4810 struct config *key;
       
  4811 {
  4744 {
  4812   x3node *np;
  4745   x3node *np;
  4813   int h;
  4746   int h;
  4814   int ph;
  4747   int ph;
  4815 
  4748 
  4863   return 1;
  4796   return 1;
  4864 }
  4797 }
  4865 
  4798 
  4866 /* Return a pointer to data assigned to the given key.  Return NULL
  4799 /* Return a pointer to data assigned to the given key.  Return NULL
  4867 ** if no such key. */
  4800 ** if no such key. */
  4868 struct state *State_find(key)
  4801 struct state *State_find(struct config *key)
  4869 struct config *key;
       
  4870 {
  4802 {
  4871   int h;
  4803   int h;
  4872   x3node *np;
  4804   x3node *np;
  4873 
  4805 
  4874   if( x3a==0 ) return 0;
  4806   if( x3a==0 ) return 0;
  4896   }
  4828   }
  4897   return array;
  4829   return array;
  4898 }
  4830 }
  4899 
  4831 
  4900 /* Hash a configuration */
  4832 /* Hash a configuration */
  4901 PRIVATE int confighash(a)
  4833 PRIVATE int confighash(struct config *a)
  4902 struct config *a;
       
  4903 {
  4834 {
  4904   int h=0;
  4835   int h=0;
  4905   h = h*571 + a->rp->index*37 + a->dot;
  4836   h = h*571 + a->rp->index*37 + a->dot;
  4906   return h;
  4837   return h;
  4907 }
  4838 }
  4949     }
  4880     }
  4950   }
  4881   }
  4951 }
  4882 }
  4952 /* Insert a new record into the array.  Return TRUE if successful.
  4883 /* Insert a new record into the array.  Return TRUE if successful.
  4953 ** Prior data with the same key is NOT overwritten */
  4884 ** Prior data with the same key is NOT overwritten */
  4954 int Configtable_insert(data)
  4885 int Configtable_insert(struct config *data)
  4955 struct config *data;
       
  4956 {
  4886 {
  4957   x4node *np;
  4887   x4node *np;
  4958   int h;
  4888   int h;
  4959   int ph;
  4889   int ph;
  4960 
  4890 
  4961   if( x4a==0 ) return 0;
  4891   if( x4a==0 ) return 0;
  4962   ph = confighash(data);
  4892   ph = confighash(data);
  4963   h = ph & (x4a->size-1);
  4893   h = ph & (x4a->size-1);
  4964   np = x4a->ht[h];
  4894   np = x4a->ht[h];
  4965   while( np ){
  4895   while( np ){
  4966     if( Configcmp(np->data,data)==0 ){
  4896     if( Configcmp((const char *) np->data,(const char *) data)==0 ){
  4967       /* An existing entry with the same key is found. */
  4897       /* An existing entry with the same key is found. */
  4968       /* Fail because overwrite is not allows. */
  4898       /* Fail because overwrite is not allows. */
  4969       return 0;
  4899       return 0;
  4970     }
  4900     }
  4971     np = np->next;
  4901     np = np->next;
  5006   return 1;
  4936   return 1;
  5007 }
  4937 }
  5008 
  4938 
  5009 /* Return a pointer to data assigned to the given key.  Return NULL
  4939 /* Return a pointer to data assigned to the given key.  Return NULL
  5010 ** if no such key. */
  4940 ** if no such key. */
  5011 struct config *Configtable_find(key)
  4941 struct config *Configtable_find(struct config *key)
  5012 struct config *key;
       
  5013 {
  4942 {
  5014   int h;
  4943   int h;
  5015   x4node *np;
  4944   x4node *np;
  5016 
  4945 
  5017   if( x4a==0 ) return 0;
  4946   if( x4a==0 ) return 0;
  5018   h = confighash(key) & (x4a->size-1);
  4947   h = confighash(key) & (x4a->size-1);
  5019   np = x4a->ht[h];
  4948   np = x4a->ht[h];
  5020   while( np ){
  4949   while( np ){
  5021     if( Configcmp(np->data,key)==0 ) break;
  4950     if( Configcmp((const char *) np->data,(const char *) key)==0 ) break;
  5022     np = np->next;
  4951     np = np->next;
  5023   }
  4952   }
  5024   return np ? np->data : 0;
  4953   return np ? np->data : 0;
  5025 }
  4954 }
  5026 
  4955 
  5027 /* Remove all data from the table.  Pass each data to the function "f"
  4956 /* Remove all data from the table.  Pass each data to the function "f"
  5028 ** as it is removed.  ("f" may be null to avoid this step.) */
  4957 ** as it is removed.  ("f" may be null to avoid this step.) */
  5029 void Configtable_clear(f)
  4958 void Configtable_clear(int(*f)(struct config *))
  5030 int(*f)(/* struct config * */);
       
  5031 {
  4959 {
  5032   int i;
  4960   int i;
  5033   if( x4a==0 || x4a->count==0 ) return;
  4961   if( x4a==0 || x4a->count==0 ) return;
  5034   if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
  4962   if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
  5035   for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;
  4963   for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;