source: cpp/_old/f8-to-f1/lemon.c @ 196

Last change on this file since 196 was 193, checked in by Maciej Komosinski, 10 years ago

Set svn:eol-style native for all textual files

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