xref: /illumos-gate/usr/src/lib/libsqlite/tool/lemon.c (revision c5c4113d)
1 
2 #pragma ident	"%Z%%M%	%I%	%E% SMI"
3 
4 /*
5 ** This file contains all sources (including headers) to the LEMON
6 ** LALR(1) parser generator.  The sources have been combined into a
7 ** single file to make it easy to include LEMON in the source tree
8 ** and Makefile of another program.
9 **
10 ** The author of this program disclaims copyright.
11 */
12 #include <stdio.h>
13 #include <stdarg.h>
14 #include <string.h>
15 #include <ctype.h>
16 #include <stdlib.h>
17 
18 #ifndef __WIN32__
19 #   if defined(_WIN32) || defined(WIN32)
20 #	define __WIN32__
21 #   endif
22 #endif
23 
24 /* #define PRIVATE static */
25 #define PRIVATE
26 
27 #ifdef TEST
28 #define MAXRHS 5       /* Set low to exercise exception code */
29 #else
30 #define MAXRHS 1000
31 #endif
32 
33 char *msort();
34 extern void *malloc();
35 
36 /******** From the file "action.h" *************************************/
37 struct action *Action_new();
38 struct action *Action_sort();
39 
40 /********* From the file "assert.h" ************************************/
41 void myassert();
42 #ifndef NDEBUG
43 #  define assert(X) if(!(X))myassert(__FILE__,__LINE__)
44 #else
45 #  define assert(X)
46 #endif
47 
48 /********** From the file "build.h" ************************************/
49 void FindRulePrecedences();
50 void FindFirstSets();
51 void FindStates();
52 void FindLinks();
53 void FindFollowSets();
54 void FindActions();
55 
56 /********* From the file "configlist.h" *********************************/
57 void Configlist_init(/* void */);
58 struct config *Configlist_add(/* struct rule *, int */);
59 struct config *Configlist_addbasis(/* struct rule *, int */);
60 void Configlist_closure(/* void */);
61 void Configlist_sort(/* void */);
62 void Configlist_sortbasis(/* void */);
63 struct config *Configlist_return(/* void */);
64 struct config *Configlist_basis(/* void */);
65 void Configlist_eat(/* struct config * */);
66 void Configlist_reset(/* void */);
67 
68 /********* From the file "error.h" ***************************************/
69 void ErrorMsg(const char *, int,const char *, ...);
70 
71 /****** From the file "option.h" ******************************************/
72 struct s_options {
73   enum { OPT_FLAG=1,  OPT_INT,  OPT_DBL,  OPT_STR,
74          OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;
75   char *label;
76   char *arg;
77   char *message;
78 };
79 int    OptInit(/* char**,struct s_options*,FILE* */);
80 int    OptNArgs(/* void */);
81 char  *OptArg(/* int */);
82 void   OptErr(/* int */);
83 void   OptPrint(/* void */);
84 
85 /******** From the file "parse.h" *****************************************/
86 void Parse(/* struct lemon *lemp */);
87 
88 /********* From the file "plink.h" ***************************************/
89 struct plink *Plink_new(/* void */);
90 void Plink_add(/* struct plink **, struct config * */);
91 void Plink_copy(/* struct plink **, struct plink * */);
92 void Plink_delete(/* struct plink * */);
93 
94 /********** From the file "report.h" *************************************/
95 void Reprint(/* struct lemon * */);
96 void ReportOutput(/* struct lemon * */);
97 void ReportTable(/* struct lemon * */);
98 void ReportHeader(/* struct lemon * */);
99 void CompressTables(/* struct lemon * */);
100 
101 /********** From the file "set.h" ****************************************/
102 void  SetSize(/* int N */);             /* All sets will be of size N */
103 char *SetNew(/* void */);               /* A new set for element 0..N */
104 void  SetFree(/* char* */);             /* Deallocate a set */
105 
106 int SetAdd(/* char*,int */);            /* Add element to a set */
107 int SetUnion(/* char *A,char *B */);    /* A <- A U B, thru element N */
108 
109 #define SetFind(X,Y) (X[Y])       /* True if Y is in set X */
110 
111 /********** From the file "struct.h" *************************************/
112 /*
113 ** Principal data structures for the LEMON parser generator.
114 */
115 
116 typedef enum {B_FALSE=0, B_TRUE} Boolean;
117 
118 /* Symbols (terminals and nonterminals) of the grammar are stored
119 ** in the following: */
120 struct symbol {
121   char *name;              /* Name of the symbol */
122   int index;               /* Index number for this symbol */
123   enum {
124     TERMINAL,
125     NONTERMINAL
126   } type;                  /* Symbols are all either TERMINALS or NTs */
127   struct rule *rule;       /* Linked list of rules of this (if an NT) */
128   struct symbol *fallback; /* fallback token in case this token doesn't parse */
129   int prec;                /* Precedence if defined (-1 otherwise) */
130   enum e_assoc {
131     LEFT,
132     RIGHT,
133     NONE,
134     UNK
135   } assoc;                 /* Associativity if predecence is defined */
136   char *firstset;          /* First-set for all rules of this symbol */
137   Boolean lambda;          /* True if NT and can generate an empty string */
138   char *destructor;        /* Code which executes whenever this symbol is
139                            ** popped from the stack during error processing */
140   int destructorln;        /* Line number of destructor code */
141   char *datatype;          /* The data type of information held by this
142                            ** object. Only used if type==NONTERMINAL */
143   int dtnum;               /* The data type number.  In the parser, the value
144                            ** stack is a union.  The .yy%d element of this
145                            ** union is the correct data type for this object */
146 };
147 
148 /* Each production rule in the grammar is stored in the following
149 ** structure.  */
150 struct rule {
151   struct symbol *lhs;      /* Left-hand side of the rule */
152   char *lhsalias;          /* Alias for the LHS (NULL if none) */
153   int ruleline;            /* Line number for the rule */
154   int nrhs;                /* Number of RHS symbols */
155   struct symbol **rhs;     /* The RHS symbols */
156   char **rhsalias;         /* An alias for each RHS symbol (NULL if none) */
157   int line;                /* Line number at which code begins */
158   char *code;              /* The code executed when this rule is reduced */
159   struct symbol *precsym;  /* Precedence symbol for this rule */
160   int index;               /* An index number for this rule */
161   Boolean canReduce;       /* True if this rule is ever reduced */
162   struct rule *nextlhs;    /* Next rule with the same LHS */
163   struct rule *next;       /* Next rule in the global list */
164 };
165 
166 /* A configuration is a production rule of the grammar together with
167 ** a mark (dot) showing how much of that rule has been processed so far.
168 ** Configurations also contain a follow-set which is a list of terminal
169 ** symbols which are allowed to immediately follow the end of the rule.
170 ** Every configuration is recorded as an instance of the following: */
171 struct config {
172   struct rule *rp;         /* The rule upon which the configuration is based */
173   int dot;                 /* The parse point */
174   char *fws;               /* Follow-set for this configuration only */
175   struct plink *fplp;      /* Follow-set forward propagation links */
176   struct plink *bplp;      /* Follow-set backwards propagation links */
177   struct state *stp;       /* Pointer to state which contains this */
178   enum {
179     COMPLETE,              /* The status is used during followset and */
180     INCOMPLETE             /*    shift computations */
181   } status;
182   struct config *next;     /* Next configuration in the state */
183   struct config *bp;       /* The next basis configuration */
184 };
185 
186 /* Every shift or reduce operation is stored as one of the following */
187 struct action {
188   struct symbol *sp;       /* The look-ahead symbol */
189   enum e_action {
190     SHIFT,
191     ACCEPT,
192     REDUCE,
193     ERROR,
194     CONFLICT,                /* Was a reduce, but part of a conflict */
195     SH_RESOLVED,             /* Was a shift.  Precedence resolved conflict */
196     RD_RESOLVED,             /* Was reduce.  Precedence resolved conflict */
197     NOT_USED                 /* Deleted by compression */
198   } type;
199   union {
200     struct state *stp;     /* The new state, if a shift */
201     struct rule *rp;       /* The rule, if a reduce */
202   } x;
203   struct action *next;     /* Next action for this state */
204   struct action *collide;  /* Next action with the same hash */
205 };
206 
207 /* Each state of the generated parser's finite state machine
208 ** is encoded as an instance of the following structure. */
209 struct state {
210   struct config *bp;       /* The basis configurations for this state */
211   struct config *cfp;      /* All configurations in this set */
212   int index;               /* Sequencial number for this state */
213   struct action *ap;       /* Array of actions for this state */
214   int nTknAct, nNtAct;     /* Number of actions on terminals and nonterminals */
215   int iTknOfst, iNtOfst;   /* yy_action[] offset for terminals and nonterms */
216   int iDflt;               /* Default action */
217 };
218 #define NO_OFFSET (-2147483647)
219 
220 /* A followset propagation link indicates that the contents of one
221 ** configuration followset should be propagated to another whenever
222 ** the first changes. */
223 struct plink {
224   struct config *cfp;      /* The configuration to which linked */
225   struct plink *next;      /* The next propagate link */
226 };
227 
228 /* The state vector for the entire parser generator is recorded as
229 ** follows.  (LEMON uses no global variables and makes little use of
230 ** static variables.  Fields in the following structure can be thought
231 ** of as begin global variables in the program.) */
232 struct lemon {
233   struct state **sorted;   /* Table of states sorted by state number */
234   struct rule *rule;       /* List of all rules */
235   int nstate;              /* Number of states */
236   int nrule;               /* Number of rules */
237   int nsymbol;             /* Number of terminal and nonterminal symbols */
238   int nterminal;           /* Number of terminal symbols */
239   struct symbol **symbols; /* Sorted array of pointers to symbols */
240   int errorcnt;            /* Number of errors */
241   struct symbol *errsym;   /* The error symbol */
242   char *name;              /* Name of the generated parser */
243   char *arg;               /* Declaration of the 3th argument to parser */
244   char *tokentype;         /* Type of terminal symbols in the parser stack */
245   char *vartype;           /* The default type of non-terminal symbols */
246   char *start;             /* Name of the start symbol for the grammar */
247   char *stacksize;         /* Size of the parser stack */
248   char *include;           /* Code to put at the start of the C file */
249   int  includeln;          /* Line number for start of include code */
250   char *error;             /* Code to execute when an error is seen */
251   int  errorln;            /* Line number for start of error code */
252   char *overflow;          /* Code to execute on a stack overflow */
253   int  overflowln;         /* Line number for start of overflow code */
254   char *failure;           /* Code to execute on parser failure */
255   int  failureln;          /* Line number for start of failure code */
256   char *accept;            /* Code to execute when the parser excepts */
257   int  acceptln;           /* Line number for the start of accept code */
258   char *extracode;         /* Code appended to the generated file */
259   int  extracodeln;        /* Line number for the start of the extra code */
260   char *tokendest;         /* Code to execute to destroy token data */
261   int  tokendestln;        /* Line number for token destroyer code */
262   char *vardest;           /* Code for the default non-terminal destructor */
263   int  vardestln;          /* Line number for default non-term destructor code*/
264   char *filename;          /* Name of the input file */
265   char *outname;           /* Name of the current output file */
266   char *tokenprefix;       /* A prefix added to token names in the .h file */
267   int nconflict;           /* Number of parsing conflicts */
268   int tablesize;           /* Size of the parse tables */
269   int basisflag;           /* Print only basis configurations */
270   int has_fallback;        /* True if any %fallback is seen in the grammer */
271   char *argv0;             /* Name of the program */
272 };
273 
274 #define MemoryCheck(X) if((X)==0){ \
275   extern void memory_error(); \
276   memory_error(); \
277 }
278 
279 /**************** From the file "table.h" *********************************/
280 /*
281 ** All code in this file has been automatically generated
282 ** from a specification in the file
283 **              "table.q"
284 ** by the associative array code building program "aagen".
285 ** Do not edit this file!  Instead, edit the specification
286 ** file, then rerun aagen.
287 */
288 /*
289 ** Code for processing tables in the LEMON parser generator.
290 */
291 
292 /* Routines for handling a strings */
293 
294 char *Strsafe();
295 
296 void Strsafe_init(/* void */);
297 int Strsafe_insert(/* char * */);
298 char *Strsafe_find(/* char * */);
299 
300 /* Routines for handling symbols of the grammar */
301 
302 struct symbol *Symbol_new();
303 int Symbolcmpp(/* struct symbol **, struct symbol ** */);
304 void Symbol_init(/* void */);
305 int Symbol_insert(/* struct symbol *, char * */);
306 struct symbol *Symbol_find(/* char * */);
307 struct symbol *Symbol_Nth(/* int */);
308 int Symbol_count(/*  */);
309 struct symbol **Symbol_arrayof(/*  */);
310 
311 /* Routines to manage the state table */
312 
313 int Configcmp(/* struct config *, struct config * */);
314 struct state *State_new();
315 void State_init(/* void */);
316 int State_insert(/* struct state *, struct config * */);
317 struct state *State_find(/* struct config * */);
318 struct state **State_arrayof(/*  */);
319 
320 /* Routines used for efficiency in Configlist_add */
321 
322 void Configtable_init(/* void */);
323 int Configtable_insert(/* struct config * */);
324 struct config *Configtable_find(/* struct config * */);
325 void Configtable_clear(/* int(*)(struct config *) */);
326 /****************** From the file "action.c" *******************************/
327 /*
328 ** Routines processing parser actions in the LEMON parser generator.
329 */
330 
331 /* Allocate a new parser action */
332 struct action *Action_new(){
333   static struct action *freelist = 0;
334   struct action *new;
335 
336   if( freelist==0 ){
337     int i;
338     int amt = 100;
339     freelist = (struct action *)malloc( sizeof(struct action)*amt );
340     if( freelist==0 ){
341       fprintf(stderr,"Unable to allocate memory for a new parser action.");
342       exit(1);
343     }
344     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
345     freelist[amt-1].next = 0;
346   }
347   new = freelist;
348   freelist = freelist->next;
349   return new;
350 }
351 
352 /* Compare two actions */
353 static int actioncmp(ap1,ap2)
354 struct action *ap1;
355 struct action *ap2;
356 {
357   int rc;
358   rc = ap1->sp->index - ap2->sp->index;
359   if( rc==0 ) rc = (int)ap1->type - (int)ap2->type;
360   if( rc==0 ){
361     assert( ap1->type==REDUCE || ap1->type==RD_RESOLVED || ap1->type==CONFLICT);
362     assert( ap2->type==REDUCE || ap2->type==RD_RESOLVED || ap2->type==CONFLICT);
363     rc = ap1->x.rp->index - ap2->x.rp->index;
364   }
365   return rc;
366 }
367 
368 /* Sort parser actions */
369 struct action *Action_sort(ap)
370 struct action *ap;
371 {
372   ap = (struct action *)msort((char *)ap,(char **)&ap->next,actioncmp);
373   return ap;
374 }
375 
376 void Action_add(app,type,sp,arg)
377 struct action **app;
378 enum e_action type;
379 struct symbol *sp;
380 char *arg;
381 {
382   struct action *new;
383   new = Action_new();
384   new->next = *app;
385   *app = new;
386   new->type = type;
387   new->sp = sp;
388   if( type==SHIFT ){
389     new->x.stp = (struct state *)arg;
390   }else{
391     new->x.rp = (struct rule *)arg;
392   }
393 }
394 /********************** New code to implement the "acttab" module ***********/
395 /*
396 ** This module implements routines use to construct the yy_action[] table.
397 */
398 
399 /*
400 ** The state of the yy_action table under construction is an instance of
401 ** the following structure
402 */
403 typedef struct acttab acttab;
404 struct acttab {
405   int nAction;                 /* Number of used slots in aAction[] */
406   int nActionAlloc;            /* Slots allocated for aAction[] */
407   struct {
408     int lookahead;             /* Value of the lookahead token */
409     int action;                /* Action to take on the given lookahead */
410   } *aAction,                  /* The yy_action[] table under construction */
411     *aLookahead;               /* A single new transaction set */
412   int mnLookahead;             /* Minimum aLookahead[].lookahead */
413   int mnAction;                /* Action associated with mnLookahead */
414   int mxLookahead;             /* Maximum aLookahead[].lookahead */
415   int nLookahead;              /* Used slots in aLookahead[] */
416   int nLookaheadAlloc;         /* Slots allocated in aLookahead[] */
417 };
418 
419 /* Return the number of entries in the yy_action table */
420 #define acttab_size(X) ((X)->nAction)
421 
422 /* The value for the N-th entry in yy_action */
423 #define acttab_yyaction(X,N)  ((X)->aAction[N].action)
424 
425 /* The value for the N-th entry in yy_lookahead */
426 #define acttab_yylookahead(X,N)  ((X)->aAction[N].lookahead)
427 
428 /* Free all memory associated with the given acttab */
429 void acttab_free(acttab *p){
430   free( p->aAction );
431   free( p->aLookahead );
432   free( p );
433 }
434 
435 /* Allocate a new acttab structure */
436 acttab *acttab_alloc(void){
437   acttab *p = malloc( sizeof(*p) );
438   if( p==0 ){
439     fprintf(stderr,"Unable to allocate memory for a new acttab.");
440     exit(1);
441   }
442   memset(p, 0, sizeof(*p));
443   return p;
444 }
445 
446 /* Add a new action to the current transaction set
447 */
448 void acttab_action(acttab *p, int lookahead, int action){
449   if( p->nLookahead>=p->nLookaheadAlloc ){
450     p->nLookaheadAlloc += 25;
451     p->aLookahead = realloc( p->aLookahead,
452                              sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
453     if( p->aLookahead==0 ){
454       fprintf(stderr,"malloc failed\n");
455       exit(1);
456     }
457   }
458   if( p->nLookahead==0 ){
459     p->mxLookahead = lookahead;
460     p->mnLookahead = lookahead;
461     p->mnAction = action;
462   }else{
463     if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
464     if( p->mnLookahead>lookahead ){
465       p->mnLookahead = lookahead;
466       p->mnAction = action;
467     }
468   }
469   p->aLookahead[p->nLookahead].lookahead = lookahead;
470   p->aLookahead[p->nLookahead].action = action;
471   p->nLookahead++;
472 }
473 
474 /*
475 ** Add the transaction set built up with prior calls to acttab_action()
476 ** into the current action table.  Then reset the transaction set back
477 ** to an empty set in preparation for a new round of acttab_action() calls.
478 **
479 ** Return the offset into the action table of the new transaction.
480 */
481 int acttab_insert(acttab *p){
482   int i, j, k, n;
483   assert( p->nLookahead>0 );
484 
485   /* Make sure we have enough space to hold the expanded action table
486   ** in the worst case.  The worst case occurs if the transaction set
487   ** must be appended to the current action table
488   */
489   n = p->mxLookahead + 1;
490   if( p->nAction + n >= p->nActionAlloc ){
491     int oldAlloc = p->nActionAlloc;
492     p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
493     p->aAction = realloc( p->aAction,
494                           sizeof(p->aAction[0])*p->nActionAlloc);
495     if( p->aAction==0 ){
496       fprintf(stderr,"malloc failed\n");
497       exit(1);
498     }
499     for(i=oldAlloc; i<p->nActionAlloc; i++){
500       p->aAction[i].lookahead = -1;
501       p->aAction[i].action = -1;
502     }
503   }
504 
505   /* Scan the existing action table looking for an offset where we can
506   ** insert the current transaction set.  Fall out of the loop when that
507   ** offset is found.  In the worst case, we fall out of the loop when
508   ** i reaches p->nAction, which means we append the new transaction set.
509   **
510   ** i is the index in p->aAction[] where p->mnLookahead is inserted.
511   */
512   for(i=0; i<p->nAction+p->mnLookahead; i++){
513     if( p->aAction[i].lookahead<0 ){
514       for(j=0; j<p->nLookahead; j++){
515         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
516         if( k<0 ) break;
517         if( p->aAction[k].lookahead>=0 ) break;
518       }
519       if( j<p->nLookahead ) continue;
520       for(j=0; j<p->nAction; j++){
521         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
522       }
523       if( j==p->nAction ){
524         break;  /* Fits in empty slots */
525       }
526     }else if( p->aAction[i].lookahead==p->mnLookahead ){
527       if( p->aAction[i].action!=p->mnAction ) continue;
528       for(j=0; j<p->nLookahead; j++){
529         k = p->aLookahead[j].lookahead - p->mnLookahead + i;
530         if( k<0 || k>=p->nAction ) break;
531         if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
532         if( p->aLookahead[j].action!=p->aAction[k].action ) break;
533       }
534       if( j<p->nLookahead ) continue;
535       n = 0;
536       for(j=0; j<p->nAction; j++){
537         if( p->aAction[j].lookahead<0 ) continue;
538         if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
539       }
540       if( n==p->nLookahead ){
541         break;  /* Same as a prior transaction set */
542       }
543     }
544   }
545   /* Insert transaction set at index i. */
546   for(j=0; j<p->nLookahead; j++){
547     k = p->aLookahead[j].lookahead - p->mnLookahead + i;
548     p->aAction[k] = p->aLookahead[j];
549     if( k>=p->nAction ) p->nAction = k+1;
550   }
551   p->nLookahead = 0;
552 
553   /* Return the offset that is added to the lookahead in order to get the
554   ** index into yy_action of the action */
555   return i - p->mnLookahead;
556 }
557 
558 /********************** From the file "assert.c" ****************************/
559 /*
560 ** A more efficient way of handling assertions.
561 */
562 void myassert(file,line)
563 char *file;
564 int line;
565 {
566   fprintf(stderr,"Assertion failed on line %d of file \"%s\"\n",line,file);
567   exit(1);
568 }
569 /********************** From the file "build.c" *****************************/
570 /*
571 ** Routines to construction the finite state machine for the LEMON
572 ** parser generator.
573 */
574 
575 /* Find a precedence symbol of every rule in the grammar.
576 **
577 ** Those rules which have a precedence symbol coded in the input
578 ** grammar using the "[symbol]" construct will already have the
579 ** rp->precsym field filled.  Other rules take as their precedence
580 ** symbol the first RHS symbol with a defined precedence.  If there
581 ** are not RHS symbols with a defined precedence, the precedence
582 ** symbol field is left blank.
583 */
584 void FindRulePrecedences(xp)
585 struct lemon *xp;
586 {
587   struct rule *rp;
588   for(rp=xp->rule; rp; rp=rp->next){
589     if( rp->precsym==0 ){
590       int i;
591       for(i=0; i<rp->nrhs; i++){
592         if( rp->rhs[i]->prec>=0 ){
593           rp->precsym = rp->rhs[i];
594           break;
595 	}
596       }
597     }
598   }
599   return;
600 }
601 
602 /* Find all nonterminals which will generate the empty string.
603 ** Then go back and compute the first sets of every nonterminal.
604 ** The first set is the set of all terminal symbols which can begin
605 ** a string generated by that nonterminal.
606 */
607 void FindFirstSets(lemp)
608 struct lemon *lemp;
609 {
610   int i;
611   struct rule *rp;
612   int progress;
613 
614   for(i=0; i<lemp->nsymbol; i++){
615     lemp->symbols[i]->lambda = B_FALSE;
616   }
617   for(i=lemp->nterminal; i<lemp->nsymbol; i++){
618     lemp->symbols[i]->firstset = SetNew();
619   }
620 
621   /* First compute all lambdas */
622   do{
623     progress = 0;
624     for(rp=lemp->rule; rp; rp=rp->next){
625       if( rp->lhs->lambda ) continue;
626       for(i=0; i<rp->nrhs; i++){
627          if( rp->rhs[i]->lambda==B_FALSE ) break;
628       }
629       if( i==rp->nrhs ){
630         rp->lhs->lambda = B_TRUE;
631         progress = 1;
632       }
633     }
634   }while( progress );
635 
636   /* Now compute all first sets */
637   do{
638     struct symbol *s1, *s2;
639     progress = 0;
640     for(rp=lemp->rule; rp; rp=rp->next){
641       s1 = rp->lhs;
642       for(i=0; i<rp->nrhs; i++){
643         s2 = rp->rhs[i];
644         if( s2->type==TERMINAL ){
645           progress += SetAdd(s1->firstset,s2->index);
646           break;
647 	}else if( s1==s2 ){
648           if( s1->lambda==B_FALSE ) break;
649 	}else{
650           progress += SetUnion(s1->firstset,s2->firstset);
651           if( s2->lambda==B_FALSE ) break;
652 	}
653       }
654     }
655   }while( progress );
656   return;
657 }
658 
659 /* Compute all LR(0) states for the grammar.  Links
660 ** are added to between some states so that the LR(1) follow sets
661 ** can be computed later.
662 */
663 PRIVATE struct state *getstate(/* struct lemon * */);  /* forward reference */
664 void FindStates(lemp)
665 struct lemon *lemp;
666 {
667   struct symbol *sp;
668   struct rule *rp;
669 
670   Configlist_init();
671 
672   /* Find the start symbol */
673   if( lemp->start ){
674     sp = Symbol_find(lemp->start);
675     if( sp==0 ){
676       ErrorMsg(lemp->filename,0,
677 "The specified start symbol \"%s\" is not \
678 in a nonterminal of the grammar.  \"%s\" will be used as the start \
679 symbol instead.",lemp->start,lemp->rule->lhs->name);
680       lemp->errorcnt++;
681       sp = lemp->rule->lhs;
682     }
683   }else{
684     sp = lemp->rule->lhs;
685   }
686 
687   /* Make sure the start symbol doesn't occur on the right-hand side of
688   ** any rule.  Report an error if it does.  (YACC would generate a new
689   ** start symbol in this case.) */
690   for(rp=lemp->rule; rp; rp=rp->next){
691     int i;
692     for(i=0; i<rp->nrhs; i++){
693       if( rp->rhs[i]==sp ){
694         ErrorMsg(lemp->filename,0,
695 "The start symbol \"%s\" occurs on the \
696 right-hand side of a rule. This will result in a parser which \
697 does not work properly.",sp->name);
698         lemp->errorcnt++;
699       }
700     }
701   }
702 
703   /* The basis configuration set for the first state
704   ** is all rules which have the start symbol as their
705   ** left-hand side */
706   for(rp=sp->rule; rp; rp=rp->nextlhs){
707     struct config *newcfp;
708     newcfp = Configlist_addbasis(rp,0);
709     SetAdd(newcfp->fws,0);
710   }
711 
712   /* Compute the first state.  All other states will be
713   ** computed automatically during the computation of the first one.
714   ** The returned pointer to the first state is not used. */
715   (void)getstate(lemp);
716   return;
717 }
718 
719 /* Return a pointer to a state which is described by the configuration
720 ** list which has been built from calls to Configlist_add.
721 */
722 PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */
723 PRIVATE struct state *getstate(lemp)
724 struct lemon *lemp;
725 {
726   struct config *cfp, *bp;
727   struct state *stp;
728 
729   /* Extract the sorted basis of the new state.  The basis was constructed
730   ** by prior calls to "Configlist_addbasis()". */
731   Configlist_sortbasis();
732   bp = Configlist_basis();
733 
734   /* Get a state with the same basis */
735   stp = State_find(bp);
736   if( stp ){
737     /* A state with the same basis already exists!  Copy all the follow-set
738     ** propagation links from the state under construction into the
739     ** preexisting state, then return a pointer to the preexisting state */
740     struct config *x, *y;
741     for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
742       Plink_copy(&y->bplp,x->bplp);
743       Plink_delete(x->fplp);
744       x->fplp = x->bplp = 0;
745     }
746     cfp = Configlist_return();
747     Configlist_eat(cfp);
748   }else{
749     /* This really is a new state.  Construct all the details */
750     Configlist_closure(lemp);    /* Compute the configuration closure */
751     Configlist_sort();           /* Sort the configuration closure */
752     cfp = Configlist_return();   /* Get a pointer to the config list */
753     stp = State_new();           /* A new state structure */
754     MemoryCheck(stp);
755     stp->bp = bp;                /* Remember the configuration basis */
756     stp->cfp = cfp;              /* Remember the configuration closure */
757     stp->index = lemp->nstate++; /* Every state gets a sequence number */
758     stp->ap = 0;                 /* No actions, yet. */
759     State_insert(stp,stp->bp);   /* Add to the state table */
760     buildshifts(lemp,stp);       /* Recursively compute successor states */
761   }
762   return stp;
763 }
764 
765 /* Construct all successor states to the given state.  A "successor"
766 ** state is any state which can be reached by a shift action.
767 */
768 PRIVATE void buildshifts(lemp,stp)
769 struct lemon *lemp;
770 struct state *stp;     /* The state from which successors are computed */
771 {
772   struct config *cfp;  /* For looping thru the config closure of "stp" */
773   struct config *bcfp; /* For the inner loop on config closure of "stp" */
774   struct config *new;  /* */
775   struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */
776   struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */
777   struct state *newstp; /* A pointer to a successor state */
778 
779   /* Each configuration becomes complete after it contibutes to a successor
780   ** state.  Initially, all configurations are incomplete */
781   for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
782 
783   /* Loop through all configurations of the state "stp" */
784   for(cfp=stp->cfp; cfp; cfp=cfp->next){
785     if( cfp->status==COMPLETE ) continue;    /* Already used by inner loop */
786     if( cfp->dot>=cfp->rp->nrhs ) continue;  /* Can't shift this config */
787     Configlist_reset();                      /* Reset the new config set */
788     sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */
789 
790     /* For every configuration in the state "stp" which has the symbol "sp"
791     ** following its dot, add the same configuration to the basis set under
792     ** construction but with the dot shifted one symbol to the right. */
793     for(bcfp=cfp; bcfp; bcfp=bcfp->next){
794       if( bcfp->status==COMPLETE ) continue;    /* Already used */
795       if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
796       bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */
797       if( bsp!=sp ) continue;                   /* Must be same as for "cfp" */
798       bcfp->status = COMPLETE;                  /* Mark this config as used */
799       new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
800       Plink_add(&new->bplp,bcfp);
801     }
802 
803     /* Get a pointer to the state described by the basis configuration set
804     ** constructed in the preceding loop */
805     newstp = getstate(lemp);
806 
807     /* The state "newstp" is reached from the state "stp" by a shift action
808     ** on the symbol "sp" */
809     Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
810   }
811 }
812 
813 /*
814 ** Construct the propagation links
815 */
816 void FindLinks(lemp)
817 struct lemon *lemp;
818 {
819   int i;
820   struct config *cfp, *other;
821   struct state *stp;
822   struct plink *plp;
823 
824   /* Housekeeping detail:
825   ** Add to every propagate link a pointer back to the state to
826   ** which the link is attached. */
827   for(i=0; i<lemp->nstate; i++){
828     stp = lemp->sorted[i];
829     for(cfp=stp->cfp; cfp; cfp=cfp->next){
830       cfp->stp = stp;
831     }
832   }
833 
834   /* Convert all backlinks into forward links.  Only the forward
835   ** links are used in the follow-set computation. */
836   for(i=0; i<lemp->nstate; i++){
837     stp = lemp->sorted[i];
838     for(cfp=stp->cfp; cfp; cfp=cfp->next){
839       for(plp=cfp->bplp; plp; plp=plp->next){
840         other = plp->cfp;
841         Plink_add(&other->fplp,cfp);
842       }
843     }
844   }
845 }
846 
847 /* Compute all followsets.
848 **
849 ** A followset is the set of all symbols which can come immediately
850 ** after a configuration.
851 */
852 void FindFollowSets(lemp)
853 struct lemon *lemp;
854 {
855   int i;
856   struct config *cfp;
857   struct plink *plp;
858   int progress;
859   int change;
860 
861   for(i=0; i<lemp->nstate; i++){
862     for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
863       cfp->status = INCOMPLETE;
864     }
865   }
866 
867   do{
868     progress = 0;
869     for(i=0; i<lemp->nstate; i++){
870       for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
871         if( cfp->status==COMPLETE ) continue;
872         for(plp=cfp->fplp; plp; plp=plp->next){
873           change = SetUnion(plp->cfp->fws,cfp->fws);
874           if( change ){
875             plp->cfp->status = INCOMPLETE;
876             progress = 1;
877 	  }
878 	}
879         cfp->status = COMPLETE;
880       }
881     }
882   }while( progress );
883 }
884 
885 static int resolve_conflict();
886 
887 /* Compute the reduce actions, and resolve conflicts.
888 */
889 void FindActions(lemp)
890 struct lemon *lemp;
891 {
892   int i,j;
893   struct config *cfp;
894   struct state *stp;
895   struct symbol *sp;
896   struct rule *rp;
897 
898   /* Add all of the reduce actions
899   ** A reduce action is added for each element of the followset of
900   ** a configuration which has its dot at the extreme right.
901   */
902   for(i=0; i<lemp->nstate; i++){   /* Loop over all states */
903     stp = lemp->sorted[i];
904     for(cfp=stp->cfp; cfp; cfp=cfp->next){  /* Loop over all configurations */
905       if( cfp->rp->nrhs==cfp->dot ){        /* Is dot at extreme right? */
906         for(j=0; j<lemp->nterminal; j++){
907           if( SetFind(cfp->fws,j) ){
908             /* Add a reduce action to the state "stp" which will reduce by the
909             ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
910             Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
911           }
912 	}
913       }
914     }
915   }
916 
917   /* Add the accepting token */
918   if( lemp->start ){
919     sp = Symbol_find(lemp->start);
920     if( sp==0 ) sp = lemp->rule->lhs;
921   }else{
922     sp = lemp->rule->lhs;
923   }
924   /* Add to the first state (which is always the starting state of the
925   ** finite state machine) an action to ACCEPT if the lookahead is the
926   ** start nonterminal.  */
927   Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
928 
929   /* Resolve conflicts */
930   for(i=0; i<lemp->nstate; i++){
931     struct action *ap, *nap;
932     struct state *stp;
933     stp = lemp->sorted[i];
934     assert( stp->ap );
935     stp->ap = Action_sort(stp->ap);
936     for(ap=stp->ap; ap && ap->next; ap=ap->next){
937       for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
938          /* The two actions "ap" and "nap" have the same lookahead.
939          ** Figure out which one should be used */
940          lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
941       }
942     }
943   }
944 
945   /* Report an error for each rule that can never be reduced. */
946   for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = B_FALSE;
947   for(i=0; i<lemp->nstate; i++){
948     struct action *ap;
949     for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
950       if( ap->type==REDUCE ) ap->x.rp->canReduce = B_TRUE;
951     }
952   }
953   for(rp=lemp->rule; rp; rp=rp->next){
954     if( rp->canReduce ) continue;
955     ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
956     lemp->errorcnt++;
957   }
958 }
959 
960 /* Resolve a conflict between the two given actions.  If the
961 ** conflict can't be resolve, return non-zero.
962 **
963 ** NO LONGER TRUE:
964 **   To resolve a conflict, first look to see if either action
965 **   is on an error rule.  In that case, take the action which
966 **   is not associated with the error rule.  If neither or both
967 **   actions are associated with an error rule, then try to
968 **   use precedence to resolve the conflict.
969 **
970 ** If either action is a SHIFT, then it must be apx.  This
971 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
972 */
973 static int resolve_conflict(apx,apy,errsym)
974 struct action *apx;
975 struct action *apy;
976 struct symbol *errsym;   /* The error symbol (if defined.  NULL otherwise) */
977 {
978   struct symbol *spx, *spy;
979   int errcnt = 0;
980   assert( apx->sp==apy->sp );  /* Otherwise there would be no conflict */
981   if( apx->type==SHIFT && apy->type==REDUCE ){
982     spx = apx->sp;
983     spy = apy->x.rp->precsym;
984     if( spy==0 || spx->prec<0 || spy->prec<0 ){
985       /* Not enough precedence information. */
986       apy->type = CONFLICT;
987       errcnt++;
988     }else if( spx->prec>spy->prec ){    /* Lower precedence wins */
989       apy->type = RD_RESOLVED;
990     }else if( spx->prec<spy->prec ){
991       apx->type = SH_RESOLVED;
992     }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
993       apy->type = RD_RESOLVED;                             /* associativity */
994     }else if( spx->prec==spy->prec && spx->assoc==LEFT ){  /* to break tie */
995       apx->type = SH_RESOLVED;
996     }else{
997       assert( spx->prec==spy->prec && spx->assoc==NONE );
998       apy->type = CONFLICT;
999       errcnt++;
1000     }
1001   }else if( apx->type==REDUCE && apy->type==REDUCE ){
1002     spx = apx->x.rp->precsym;
1003     spy = apy->x.rp->precsym;
1004     if( spx==0 || spy==0 || spx->prec<0 ||
1005     spy->prec<0 || spx->prec==spy->prec ){
1006       apy->type = CONFLICT;
1007       errcnt++;
1008     }else if( spx->prec>spy->prec ){
1009       apy->type = RD_RESOLVED;
1010     }else if( spx->prec<spy->prec ){
1011       apx->type = RD_RESOLVED;
1012     }
1013   }else{
1014     assert(
1015       apx->type==SH_RESOLVED ||
1016       apx->type==RD_RESOLVED ||
1017       apx->type==CONFLICT ||
1018       apy->type==SH_RESOLVED ||
1019       apy->type==RD_RESOLVED ||
1020       apy->type==CONFLICT
1021     );
1022     /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1023     ** REDUCEs on the list.  If we reach this point it must be because
1024     ** the parser conflict had already been resolved. */
1025   }
1026   return errcnt;
1027 }
1028 /********************* From the file "configlist.c" *************************/
1029 /*
1030 ** Routines to processing a configuration list and building a state
1031 ** in the LEMON parser generator.
1032 */
1033 
1034 static struct config *freelist = 0;      /* List of free configurations */
1035 static struct config *current = 0;       /* Top of list of configurations */
1036 static struct config **currentend = 0;   /* Last on list of configs */
1037 static struct config *basis = 0;         /* Top of list of basis configs */
1038 static struct config **basisend = 0;     /* End of list of basis configs */
1039 
1040 /* Return a pointer to a new configuration */
1041 PRIVATE struct config *newconfig(){
1042   struct config *new;
1043   if( freelist==0 ){
1044     int i;
1045     int amt = 3;
1046     freelist = (struct config *)malloc( sizeof(struct config)*amt );
1047     if( freelist==0 ){
1048       fprintf(stderr,"Unable to allocate memory for a new configuration.");
1049       exit(1);
1050     }
1051     for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
1052     freelist[amt-1].next = 0;
1053   }
1054   new = freelist;
1055   freelist = freelist->next;
1056   return new;
1057 }
1058 
1059 /* The configuration "old" is no longer used */
1060 PRIVATE void deleteconfig(old)
1061 struct config *old;
1062 {
1063   old->next = freelist;
1064   freelist = old;
1065 }
1066 
1067 /* Initialized the configuration list builder */
1068 void Configlist_init(){
1069   current = 0;
1070   currentend = &current;
1071   basis = 0;
1072   basisend = &basis;
1073   Configtable_init();
1074   return;
1075 }
1076 
1077 /* Initialized the configuration list builder */
1078 void Configlist_reset(){
1079   current = 0;
1080   currentend = &current;
1081   basis = 0;
1082   basisend = &basis;
1083   Configtable_clear(0);
1084   return;
1085 }
1086 
1087 /* Add another configuration to the configuration list */
1088 struct config *Configlist_add(rp,dot)
1089 struct rule *rp;    /* The rule */
1090 int dot;            /* Index into the RHS of the rule where the dot goes */
1091 {
1092   struct config *cfp, model;
1093 
1094   assert( currentend!=0 );
1095   model.rp = rp;
1096   model.dot = dot;
1097   cfp = Configtable_find(&model);
1098   if( cfp==0 ){
1099     cfp = newconfig();
1100     cfp->rp = rp;
1101     cfp->dot = dot;
1102     cfp->fws = SetNew();
1103     cfp->stp = 0;
1104     cfp->fplp = cfp->bplp = 0;
1105     cfp->next = 0;
1106     cfp->bp = 0;
1107     *currentend = cfp;
1108     currentend = &cfp->next;
1109     Configtable_insert(cfp);
1110   }
1111   return cfp;
1112 }
1113 
1114 /* Add a basis configuration to the configuration list */
1115 struct config *Configlist_addbasis(rp,dot)
1116 struct rule *rp;
1117 int dot;
1118 {
1119   struct config *cfp, model;
1120 
1121   assert( basisend!=0 );
1122   assert( currentend!=0 );
1123   model.rp = rp;
1124   model.dot = dot;
1125   cfp = Configtable_find(&model);
1126   if( cfp==0 ){
1127     cfp = newconfig();
1128     cfp->rp = rp;
1129     cfp->dot = dot;
1130     cfp->fws = SetNew();
1131     cfp->stp = 0;
1132     cfp->fplp = cfp->bplp = 0;
1133     cfp->next = 0;
1134     cfp->bp = 0;
1135     *currentend = cfp;
1136     currentend = &cfp->next;
1137     *basisend = cfp;
1138     basisend = &cfp->bp;
1139     Configtable_insert(cfp);
1140   }
1141   return cfp;
1142 }
1143 
1144 /* Compute the closure of the configuration list */
1145 void Configlist_closure(lemp)
1146 struct lemon *lemp;
1147 {
1148   struct config *cfp, *newcfp;
1149   struct rule *rp, *newrp;
1150   struct symbol *sp, *xsp;
1151   int i, dot;
1152 
1153   assert( currentend!=0 );
1154   for(cfp=current; cfp; cfp=cfp->next){
1155     rp = cfp->rp;
1156     dot = cfp->dot;
1157     if( dot>=rp->nrhs ) continue;
1158     sp = rp->rhs[dot];
1159     if( sp->type==NONTERMINAL ){
1160       if( sp->rule==0 && sp!=lemp->errsym ){
1161         ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",
1162           sp->name);
1163         lemp->errorcnt++;
1164       }
1165       for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
1166         newcfp = Configlist_add(newrp,0);
1167         for(i=dot+1; i<rp->nrhs; i++){
1168           xsp = rp->rhs[i];
1169           if( xsp->type==TERMINAL ){
1170             SetAdd(newcfp->fws,xsp->index);
1171             break;
1172 	  }else{
1173             SetUnion(newcfp->fws,xsp->firstset);
1174             if( xsp->lambda==B_FALSE ) break;
1175 	  }
1176 	}
1177         if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);
1178       }
1179     }
1180   }
1181   return;
1182 }
1183 
1184 /* Sort the configuration list */
1185 void Configlist_sort(){
1186   current = (struct config *)msort((char *)current,(char **)&(current->next),Configcmp);
1187   currentend = 0;
1188   return;
1189 }
1190 
1191 /* Sort the basis configuration list */
1192 void Configlist_sortbasis(){
1193   basis = (struct config *)msort((char *)current,(char **)&(current->bp),Configcmp);
1194   basisend = 0;
1195   return;
1196 }
1197 
1198 /* Return a pointer to the head of the configuration list and
1199 ** reset the list */
1200 struct config *Configlist_return(){
1201   struct config *old;
1202   old = current;
1203   current = 0;
1204   currentend = 0;
1205   return old;
1206 }
1207 
1208 /* Return a pointer to the head of the configuration list and
1209 ** reset the list */
1210 struct config *Configlist_basis(){
1211   struct config *old;
1212   old = basis;
1213   basis = 0;
1214   basisend = 0;
1215   return old;
1216 }
1217 
1218 /* Free all elements of the given configuration list */
1219 void Configlist_eat(cfp)
1220 struct config *cfp;
1221 {
1222   struct config *nextcfp;
1223   for(; cfp; cfp=nextcfp){
1224     nextcfp = cfp->next;
1225     assert( cfp->fplp==0 );
1226     assert( cfp->bplp==0 );
1227     if( cfp->fws ) SetFree(cfp->fws);
1228     deleteconfig(cfp);
1229   }
1230   return;
1231 }
1232 /***************** From the file "error.c" *********************************/
1233 /*
1234 ** Code for printing error message.
1235 */
1236 
1237 /* Find a good place to break "msg" so that its length is at least "min"
1238 ** but no more than "max".  Make the point as close to max as possible.
1239 */
1240 static int findbreak(msg,min,max)
1241 char *msg;
1242 int min;
1243 int max;
1244 {
1245   int i,spot;
1246   char c;
1247   for(i=spot=min; i<=max; i++){
1248     c = msg[i];
1249     if( c=='\t' ) msg[i] = ' ';
1250     if( c=='\n' ){ msg[i] = ' '; spot = i; break; }
1251     if( c==0 ){ spot = i; break; }
1252     if( c=='-' && i<max-1 ) spot = i+1;
1253     if( c==' ' ) spot = i;
1254   }
1255   return spot;
1256 }
1257 
1258 /*
1259 ** The error message is split across multiple lines if necessary.  The
1260 ** splits occur at a space, if there is a space available near the end
1261 ** of the line.
1262 */
1263 #define ERRMSGSIZE  10000 /* Hope this is big enough.  No way to error check */
1264 #define LINEWIDTH      79 /* Max width of any output line */
1265 #define PREFIXLIMIT    30 /* Max width of the prefix on each line */
1266 void ErrorMsg(const char *filename, int lineno, const char *format, ...){
1267   char errmsg[ERRMSGSIZE];
1268   char prefix[PREFIXLIMIT+10];
1269   int errmsgsize;
1270   int prefixsize;
1271   int availablewidth;
1272   va_list ap;
1273   int end, restart, base;
1274 
1275   va_start(ap, format);
1276   /* Prepare a prefix to be prepended to every output line */
1277   if( lineno>0 ){
1278     sprintf(prefix,"%.*s:%d: ",PREFIXLIMIT-10,filename,lineno);
1279   }else{
1280     sprintf(prefix,"%.*s: ",PREFIXLIMIT-10,filename);
1281   }
1282   prefixsize = strlen(prefix);
1283   availablewidth = LINEWIDTH - prefixsize;
1284 
1285   /* Generate the error message */
1286   vsprintf(errmsg,format,ap);
1287   va_end(ap);
1288   errmsgsize = strlen(errmsg);
1289   /* Remove trailing '\n's from the error message. */
1290   while( errmsgsize>0 && errmsg[errmsgsize-1]=='\n' ){
1291      errmsg[--errmsgsize] = 0;
1292   }
1293 
1294   /* Print the error message */
1295   base = 0;
1296   while( errmsg[base]!=0 ){
1297     end = restart = findbreak(&errmsg[base],0,availablewidth);
1298     restart += base;
1299     while( errmsg[restart]==' ' ) restart++;
1300     fprintf(stdout,"%s%.*s\n",prefix,end,&errmsg[base]);
1301     base = restart;
1302   }
1303 }
1304 /**************** From the file "main.c" ************************************/
1305 /*
1306 ** Main program file for the LEMON parser generator.
1307 */
1308 
1309 /* Report an out-of-memory condition and abort.  This function
1310 ** is used mostly by the "MemoryCheck" macro in struct.h
1311 */
1312 void memory_error(){
1313   fprintf(stderr,"Out of memory.  Aborting...\n");
1314   exit(1);
1315 }
1316 
1317 
1318 /* The main program.  Parse the command line and do it... */
1319 int main(argc,argv)
1320 int argc;
1321 char **argv;
1322 {
1323   static int version = 0;
1324   static int rpflag = 0;
1325   static int basisflag = 0;
1326   static int compress = 0;
1327   static int quiet = 0;
1328   static int statistics = 0;
1329   static int mhflag = 0;
1330   static struct s_options options[] = {
1331     {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
1332     {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
1333     {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
1334     {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file"},
1335     {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
1336     {OPT_FLAG, "s", (char*)&statistics, "Print parser stats to standard output."},
1337     {OPT_FLAG, "x", (char*)&version, "Print the version number."},
1338     {OPT_FLAG,0,0,0}
1339   };
1340   int i;
1341   struct lemon lem;
1342 
1343   OptInit(argv,options,stderr);
1344   if( version ){
1345      printf("Lemon version 1.0\n");
1346      exit(0);
1347   }
1348   if( OptNArgs()!=1 ){
1349     fprintf(stderr,"Exactly one filename argument is required.\n");
1350     exit(1);
1351   }
1352   lem.errorcnt = 0;
1353 
1354   /* Initialize the machine */
1355   Strsafe_init();
1356   Symbol_init();
1357   State_init();
1358   lem.argv0 = argv[0];
1359   lem.filename = OptArg(0);
1360   lem.basisflag = basisflag;
1361   lem.has_fallback = 0;
1362   lem.nconflict = 0;
1363   lem.name = lem.include = lem.arg = lem.tokentype = lem.start = 0;
1364   lem.vartype = 0;
1365   lem.stacksize = 0;
1366   lem.error = lem.overflow = lem.failure = lem.accept = lem.tokendest =
1367      lem.tokenprefix = lem.outname = lem.extracode = 0;
1368   lem.vardest = 0;
1369   lem.tablesize = 0;
1370   Symbol_new("$");
1371   lem.errsym = Symbol_new("error");
1372 
1373   /* Parse the input file */
1374   Parse(&lem);
1375   if( lem.errorcnt ) exit(lem.errorcnt);
1376   if( lem.rule==0 ){
1377     fprintf(stderr,"Empty grammar.\n");
1378     exit(1);
1379   }
1380 
1381   /* Count and index the symbols of the grammar */
1382   lem.nsymbol = Symbol_count();
1383   Symbol_new("{default}");
1384   lem.symbols = Symbol_arrayof();
1385   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
1386   qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*),
1387         (int(*)())Symbolcmpp);
1388   for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
1389   for(i=1; isupper(lem.symbols[i]->name[0]); i++);
1390   lem.nterminal = i;
1391 
1392   /* Generate a reprint of the grammar, if requested on the command line */
1393   if( rpflag ){
1394     Reprint(&lem);
1395   }else{
1396     /* Initialize the size for all follow and first sets */
1397     SetSize(lem.nterminal);
1398 
1399     /* Find the precedence for every production rule (that has one) */
1400     FindRulePrecedences(&lem);
1401 
1402     /* Compute the lambda-nonterminals and the first-sets for every
1403     ** nonterminal */
1404     FindFirstSets(&lem);
1405 
1406     /* Compute all LR(0) states.  Also record follow-set propagation
1407     ** links so that the follow-set can be computed later */
1408     lem.nstate = 0;
1409     FindStates(&lem);
1410     lem.sorted = State_arrayof();
1411 
1412     /* Tie up loose ends on the propagation links */
1413     FindLinks(&lem);
1414 
1415     /* Compute the follow set of every reducible configuration */
1416     FindFollowSets(&lem);
1417 
1418     /* Compute the action tables */
1419     FindActions(&lem);
1420 
1421     /* Compress the action tables */
1422     if( compress==0 ) CompressTables(&lem);
1423 
1424     /* Generate a report of the parser generated.  (the "y.output" file) */
1425     if( !quiet ) ReportOutput(&lem);
1426 
1427     /* Generate the source code for the parser */
1428     ReportTable(&lem, mhflag);
1429 
1430     /* Produce a header file for use by the scanner.  (This step is
1431     ** omitted if the "-m" option is used because makeheaders will
1432     ** generate the file for us.) */
1433     if( !mhflag ) ReportHeader(&lem);
1434   }
1435   if( statistics ){
1436     printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
1437       lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
1438     printf("                   %d states, %d parser table entries, %d conflicts\n",
1439       lem.nstate, lem.tablesize, lem.nconflict);
1440   }
1441   if( lem.nconflict ){
1442     fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
1443   }
1444   exit(lem.errorcnt + lem.nconflict);
1445   return (lem.errorcnt + lem.nconflict);
1446 }
1447 /******************** From the file "msort.c" *******************************/
1448 /*
1449 ** A generic merge-sort program.
1450 **
1451 ** USAGE:
1452 ** Let "ptr" be a pointer to some structure which is at the head of
1453 ** a null-terminated list.  Then to sort the list call:
1454 **
1455 **     ptr = msort(ptr,&(ptr->next),cmpfnc);
1456 **
1457 ** In the above, "cmpfnc" is a pointer to a function which compares
1458 ** two instances of the structure and returns an integer, as in
1459 ** strcmp.  The second argument is a pointer to the pointer to the
1460 ** second element of the linked list.  This address is used to compute
1461 ** the offset to the "next" field within the structure.  The offset to
1462 ** the "next" field must be constant for all structures in the list.
1463 **
1464 ** The function returns a new pointer which is the head of the list
1465 ** after sorting.
1466 **
1467 ** ALGORITHM:
1468 ** Merge-sort.
1469 */
1470 
1471 /*
1472 ** Return a pointer to the next structure in the linked list.
1473 */
1474 #define NEXT(A) (*(char**)(((unsigned long)A)+offset))
1475 
1476 /*
1477 ** Inputs:
1478 **   a:       A sorted, null-terminated linked list.  (May be null).
1479 **   b:       A sorted, null-terminated linked list.  (May be null).
1480 **   cmp:     A pointer to the comparison function.
1481 **   offset:  Offset in the structure to the "next" field.
1482 **
1483 ** Return Value:
1484 **   A pointer to the head of a sorted list containing the elements
1485 **   of both a and b.
1486 **
1487 ** Side effects:
1488 **   The "next" pointers for elements in the lists a and b are
1489 **   changed.
1490 */
1491 static char *merge(a,b,cmp,offset)
1492 char *a;
1493 char *b;
1494 int (*cmp)();
1495 int offset;
1496 {
1497   char *ptr, *head;
1498 
1499   if( a==0 ){
1500     head = b;
1501   }else if( b==0 ){
1502     head = a;
1503   }else{
1504     if( (*cmp)(a,b)<0 ){
1505       ptr = a;
1506       a = NEXT(a);
1507     }else{
1508       ptr = b;
1509       b = NEXT(b);
1510     }
1511     head = ptr;
1512     while( a && b ){
1513       if( (*cmp)(a,b)<0 ){
1514         NEXT(ptr) = a;
1515         ptr = a;
1516         a = NEXT(a);
1517       }else{
1518         NEXT(ptr) = b;
1519         ptr = b;
1520         b = NEXT(b);
1521       }
1522     }
1523     if( a ) NEXT(ptr) = a;
1524     else    NEXT(ptr) = b;
1525   }
1526   return head;
1527 }
1528 
1529 /*
1530 ** Inputs:
1531 **   list:      Pointer to a singly-linked list of structures.
1532 **   next:      Pointer to pointer to the second element of the list.
1533 **   cmp:       A comparison function.
1534 **
1535 ** Return Value:
1536 **   A pointer to the head of a sorted list containing the elements
1537 **   orginally in list.
1538 **
1539 ** Side effects:
1540 **   The "next" pointers for elements in list are changed.
1541 */
1542 #define LISTSIZE 30
1543 char *msort(list,next,cmp)
1544 char *list;
1545 char **next;
1546 int (*cmp)();
1547 {
1548   unsigned long offset;
1549   char *ep;
1550   char *set[LISTSIZE];
1551   int i;
1552   offset = (unsigned long)next - (unsigned long)list;
1553   for(i=0; i<LISTSIZE; i++) set[i] = 0;
1554   while( list ){
1555     ep = list;
1556     list = NEXT(list);
1557     NEXT(ep) = 0;
1558     for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
1559       ep = merge(ep,set[i],cmp,offset);
1560       set[i] = 0;
1561     }
1562     set[i] = ep;
1563   }
1564   ep = 0;
1565   for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(ep,set[i],cmp,offset);
1566   return ep;
1567 }
1568 /************************ From the file "option.c" **************************/
1569 static char **argv;
1570 static struct s_options *op;
1571 static FILE *errstream;
1572 
1573 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1574 
1575 /*
1576 ** Print the command line with a carrot pointing to the k-th character
1577 ** of the n-th field.
1578 */
1579 static void errline(n,k,err)
1580 int n;
1581 int k;
1582 FILE *err;
1583 {
1584   int spcnt, i;
1585   spcnt = 0;
1586   if( argv[0] ) fprintf(err,"%s",argv[0]);
1587   spcnt = strlen(argv[0]) + 1;
1588   for(i=1; i<n && argv[i]; i++){
1589     fprintf(err," %s",argv[i]);
1590     spcnt += strlen(argv[i]+1);
1591   }
1592   spcnt += k;
1593   for(; argv[i]; i++) fprintf(err," %s",argv[i]);
1594   if( spcnt<20 ){
1595     fprintf(err,"\n%*s^-- here\n",spcnt,"");
1596   }else{
1597     fprintf(err,"\n%*shere --^\n",spcnt-7,"");
1598   }
1599 }
1600 
1601 /*
1602 ** Return the index of the N-th non-switch argument.  Return -1
1603 ** if N is out of range.
1604 */
1605 static int argindex(n)
1606 int n;
1607 {
1608   int i;
1609   int dashdash = 0;
1610   if( argv!=0 && *argv!=0 ){
1611     for(i=1; argv[i]; i++){
1612       if( dashdash || !ISOPT(argv[i]) ){
1613         if( n==0 ) return i;
1614         n--;
1615       }
1616       if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1617     }
1618   }
1619   return -1;
1620 }
1621 
1622 static char emsg[] = "Command line syntax error: ";
1623 
1624 /*
1625 ** Process a flag command line argument.
1626 */
1627 static int handleflags(i,err)
1628 int i;
1629 FILE *err;
1630 {
1631   int v;
1632   int errcnt = 0;
1633   int j;
1634   for(j=0; op[j].label; j++){
1635     if( strcmp(&argv[i][1],op[j].label)==0 ) break;
1636   }
1637   v = argv[i][0]=='-' ? 1 : 0;
1638   if( op[j].label==0 ){
1639     if( err ){
1640       fprintf(err,"%sundefined option.\n",emsg);
1641       errline(i,1,err);
1642     }
1643     errcnt++;
1644   }else if( op[j].type==OPT_FLAG ){
1645     *((int*)op[j].arg) = v;
1646   }else if( op[j].type==OPT_FFLAG ){
1647     (*(void(*)())(op[j].arg))(v);
1648   }else{
1649     if( err ){
1650       fprintf(err,"%smissing argument on switch.\n",emsg);
1651       errline(i,1,err);
1652     }
1653     errcnt++;
1654   }
1655   return errcnt;
1656 }
1657 
1658 /*
1659 ** Process a command line switch which has an argument.
1660 */
1661 static int handleswitch(i,err)
1662 int i;
1663 FILE *err;
1664 {
1665   int lv = 0;
1666   double dv = 0.0;
1667   char *sv = 0, *end;
1668   char *cp;
1669   int j;
1670   int errcnt = 0;
1671   cp = strchr(argv[i],'=');
1672   *cp = 0;
1673   for(j=0; op[j].label; j++){
1674     if( strcmp(argv[i],op[j].label)==0 ) break;
1675   }
1676   *cp = '=';
1677   if( op[j].label==0 ){
1678     if( err ){
1679       fprintf(err,"%sundefined option.\n",emsg);
1680       errline(i,0,err);
1681     }
1682     errcnt++;
1683   }else{
1684     cp++;
1685     switch( op[j].type ){
1686       case OPT_FLAG:
1687       case OPT_FFLAG:
1688         if( err ){
1689           fprintf(err,"%soption requires an argument.\n",emsg);
1690           errline(i,0,err);
1691         }
1692         errcnt++;
1693         break;
1694       case OPT_DBL:
1695       case OPT_FDBL:
1696         dv = strtod(cp,&end);
1697         if( *end ){
1698           if( err ){
1699             fprintf(err,"%sillegal character in floating-point argument.\n",emsg);
1700             errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
1701           }
1702           errcnt++;
1703         }
1704         break;
1705       case OPT_INT:
1706       case OPT_FINT:
1707         lv = strtol(cp,&end,0);
1708         if( *end ){
1709           if( err ){
1710             fprintf(err,"%sillegal character in integer argument.\n",emsg);
1711             errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
1712           }
1713           errcnt++;
1714         }
1715         break;
1716       case OPT_STR:
1717       case OPT_FSTR:
1718         sv = cp;
1719         break;
1720     }
1721     switch( op[j].type ){
1722       case OPT_FLAG:
1723       case OPT_FFLAG:
1724         break;
1725       case OPT_DBL:
1726         *(double*)(op[j].arg) = dv;
1727         break;
1728       case OPT_FDBL:
1729         (*(void(*)())(op[j].arg))(dv);
1730         break;
1731       case OPT_INT:
1732         *(int*)(op[j].arg) = lv;
1733         break;
1734       case OPT_FINT:
1735         (*(void(*)())(op[j].arg))((int)lv);
1736         break;
1737       case OPT_STR:
1738         *(char**)(op[j].arg) = sv;
1739         break;
1740       case OPT_FSTR:
1741         (*(void(*)())(op[j].arg))(sv);
1742         break;
1743     }
1744   }
1745   return errcnt;
1746 }
1747 
1748 int OptInit(a,o,err)
1749 char **a;
1750 struct s_options *o;
1751 FILE *err;
1752 {
1753   int errcnt = 0;
1754   argv = a;
1755   op = o;
1756   errstream = err;
1757   if( argv && *argv && op ){
1758     int i;
1759     for(i=1; argv[i]; i++){
1760       if( argv[i][0]=='+' || argv[i][0]=='-' ){
1761         errcnt += handleflags(i,err);
1762       }else if( strchr(argv[i],'=') ){
1763         errcnt += handleswitch(i,err);
1764       }
1765     }
1766   }
1767   if( errcnt>0 ){
1768     fprintf(err,"Valid command line options for \"%s\" are:\n",*a);
1769     OptPrint();
1770     exit(1);
1771   }
1772   return 0;
1773 }
1774 
1775 int OptNArgs(){
1776   int cnt = 0;
1777   int dashdash = 0;
1778   int i;
1779   if( argv!=0 && argv[0]!=0 ){
1780     for(i=1; argv[i]; i++){
1781       if( dashdash || !ISOPT(argv[i]) ) cnt++;
1782       if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1783     }
1784   }
1785   return cnt;
1786 }
1787 
1788 char *OptArg(n)
1789 int n;
1790 {
1791   int i;
1792   i = argindex(n);
1793   return i>=0 ? argv[i] : 0;
1794 }
1795 
1796 void OptErr(n)
1797 int n;
1798 {
1799   int i;
1800   i = argindex(n);
1801   if( i>=0 ) errline(i,0,errstream);
1802 }
1803 
1804 void OptPrint(){
1805   int i;
1806   int max, len;
1807   max = 0;
1808   for(i=0; op[i].label; i++){
1809     len = strlen(op[i].label) + 1;
1810     switch( op[i].type ){
1811       case OPT_FLAG:
1812       case OPT_FFLAG:
1813         break;
1814       case OPT_INT:
1815       case OPT_FINT:
1816         len += 9;       /* length of "<integer>" */
1817         break;
1818       case OPT_DBL:
1819       case OPT_FDBL:
1820         len += 6;       /* length of "<real>" */
1821         break;
1822       case OPT_STR:
1823       case OPT_FSTR:
1824         len += 8;       /* length of "<string>" */
1825         break;
1826     }
1827     if( len>max ) max = len;
1828   }
1829   for(i=0; op[i].label; i++){
1830     switch( op[i].type ){
1831       case OPT_FLAG:
1832       case OPT_FFLAG:
1833         fprintf(errstream,"  -%-*s  %s\n",max,op[i].label,op[i].message);
1834         break;
1835       case OPT_INT:
1836       case OPT_FINT:
1837         fprintf(errstream,"  %s=<integer>%*s  %s\n",op[i].label,
1838           (int)(max-strlen(op[i].label)-9),"",op[i].message);
1839         break;
1840       case OPT_DBL:
1841       case OPT_FDBL:
1842         fprintf(errstream,"  %s=<real>%*s  %s\n",op[i].label,
1843           (int)(max-strlen(op[i].label)-6),"",op[i].message);
1844         break;
1845       case OPT_STR:
1846       case OPT_FSTR:
1847         fprintf(errstream,"  %s=<string>%*s  %s\n",op[i].label,
1848           (int)(max-strlen(op[i].label)-8),"",op[i].message);
1849         break;
1850     }
1851   }
1852 }
1853 /*********************** From the file "parse.c" ****************************/
1854 /*
1855 ** Input file parser for the LEMON parser generator.
1856 */
1857 
1858 /* The state of the parser */
1859 struct pstate {
1860   char *filename;       /* Name of the input file */
1861   int tokenlineno;      /* Linenumber at which current token starts */
1862   int errorcnt;         /* Number of errors so far */
1863   char *tokenstart;     /* Text of current token */
1864   struct lemon *gp;     /* Global state vector */
1865   enum e_state {
1866     INITIALIZE,
1867     WAITING_FOR_DECL_OR_RULE,
1868     WAITING_FOR_DECL_KEYWORD,
1869     WAITING_FOR_DECL_ARG,
1870     WAITING_FOR_PRECEDENCE_SYMBOL,
1871     WAITING_FOR_ARROW,
1872     IN_RHS,
1873     LHS_ALIAS_1,
1874     LHS_ALIAS_2,
1875     LHS_ALIAS_3,
1876     RHS_ALIAS_1,
1877     RHS_ALIAS_2,
1878     PRECEDENCE_MARK_1,
1879     PRECEDENCE_MARK_2,
1880     RESYNC_AFTER_RULE_ERROR,
1881     RESYNC_AFTER_DECL_ERROR,
1882     WAITING_FOR_DESTRUCTOR_SYMBOL,
1883     WAITING_FOR_DATATYPE_SYMBOL,
1884     WAITING_FOR_FALLBACK_ID
1885   } state;                   /* The state of the parser */
1886   struct symbol *fallback;   /* The fallback token */
1887   struct symbol *lhs;        /* Left-hand side of current rule */
1888   char *lhsalias;            /* Alias for the LHS */
1889   int nrhs;                  /* Number of right-hand side symbols seen */
1890   struct symbol *rhs[MAXRHS];  /* RHS symbols */
1891   char *alias[MAXRHS];       /* Aliases for each RHS symbol (or NULL) */
1892   struct rule *prevrule;     /* Previous rule parsed */
1893   char *declkeyword;         /* Keyword of a declaration */
1894   char **declargslot;        /* Where the declaration argument should be put */
1895   int *decllnslot;           /* Where the declaration linenumber is put */
1896   enum e_assoc declassoc;    /* Assign this association to decl arguments */
1897   int preccounter;           /* Assign this precedence to decl arguments */
1898   struct rule *firstrule;    /* Pointer to first rule in the grammar */
1899   struct rule *lastrule;     /* Pointer to the most recently parsed rule */
1900 };
1901 
1902 /* Parse a single token */
1903 static void parseonetoken(psp)
1904 struct pstate *psp;
1905 {
1906   char *x;
1907   x = Strsafe(psp->tokenstart);     /* Save the token permanently */
1908 #if 0
1909   printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
1910     x,psp->state);
1911 #endif
1912   switch( psp->state ){
1913     case INITIALIZE:
1914       psp->prevrule = 0;
1915       psp->preccounter = 0;
1916       psp->firstrule = psp->lastrule = 0;
1917       psp->gp->nrule = 0;
1918       /* Fall thru to next case */
1919     case WAITING_FOR_DECL_OR_RULE:
1920       if( x[0]=='%' ){
1921         psp->state = WAITING_FOR_DECL_KEYWORD;
1922       }else if( islower(x[0]) ){
1923         psp->lhs = Symbol_new(x);
1924         psp->nrhs = 0;
1925         psp->lhsalias = 0;
1926         psp->state = WAITING_FOR_ARROW;
1927       }else if( x[0]=='{' ){
1928         if( psp->prevrule==0 ){
1929           ErrorMsg(psp->filename,psp->tokenlineno,
1930 "There is not prior rule opon which to attach the code \
1931 fragment which begins on this line.");
1932           psp->errorcnt++;
1933 	}else if( psp->prevrule->code!=0 ){
1934           ErrorMsg(psp->filename,psp->tokenlineno,
1935 "Code fragment beginning on this line is not the first \
1936 to follow the previous rule.");
1937           psp->errorcnt++;
1938         }else{
1939           psp->prevrule->line = psp->tokenlineno;
1940           psp->prevrule->code = &x[1];
1941 	}
1942       }else if( x[0]=='[' ){
1943         psp->state = PRECEDENCE_MARK_1;
1944       }else{
1945         ErrorMsg(psp->filename,psp->tokenlineno,
1946           "Token \"%s\" should be either \"%%\" or a nonterminal name.",
1947           x);
1948         psp->errorcnt++;
1949       }
1950       break;
1951     case PRECEDENCE_MARK_1:
1952       if( !isupper(x[0]) ){
1953         ErrorMsg(psp->filename,psp->tokenlineno,
1954           "The precedence symbol must be a terminal.");
1955         psp->errorcnt++;
1956       }else if( psp->prevrule==0 ){
1957         ErrorMsg(psp->filename,psp->tokenlineno,
1958           "There is no prior rule to assign precedence \"[%s]\".",x);
1959         psp->errorcnt++;
1960       }else if( psp->prevrule->precsym!=0 ){
1961         ErrorMsg(psp->filename,psp->tokenlineno,
1962 "Precedence mark on this line is not the first \
1963 to follow the previous rule.");
1964         psp->errorcnt++;
1965       }else{
1966         psp->prevrule->precsym = Symbol_new(x);
1967       }
1968       psp->state = PRECEDENCE_MARK_2;
1969       break;
1970     case PRECEDENCE_MARK_2:
1971       if( x[0]!=']' ){
1972         ErrorMsg(psp->filename,psp->tokenlineno,
1973           "Missing \"]\" on precedence mark.");
1974         psp->errorcnt++;
1975       }
1976       psp->state = WAITING_FOR_DECL_OR_RULE;
1977       break;
1978     case WAITING_FOR_ARROW:
1979       if( x[0]==':' && x[1]==':' && x[2]=='=' ){
1980         psp->state = IN_RHS;
1981       }else if( x[0]=='(' ){
1982         psp->state = LHS_ALIAS_1;
1983       }else{
1984         ErrorMsg(psp->filename,psp->tokenlineno,
1985           "Expected to see a \":\" following the LHS symbol \"%s\".",
1986           psp->lhs->name);
1987         psp->errorcnt++;
1988         psp->state = RESYNC_AFTER_RULE_ERROR;
1989       }
1990       break;
1991     case LHS_ALIAS_1:
1992       if( isalpha(x[0]) ){
1993         psp->lhsalias = x;
1994         psp->state = LHS_ALIAS_2;
1995       }else{
1996         ErrorMsg(psp->filename,psp->tokenlineno,
1997           "\"%s\" is not a valid alias for the LHS \"%s\"\n",
1998           x,psp->lhs->name);
1999         psp->errorcnt++;
2000         psp->state = RESYNC_AFTER_RULE_ERROR;
2001       }
2002       break;
2003     case LHS_ALIAS_2:
2004       if( x[0]==')' ){
2005         psp->state = LHS_ALIAS_3;
2006       }else{
2007         ErrorMsg(psp->filename,psp->tokenlineno,
2008           "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2009         psp->errorcnt++;
2010         psp->state = RESYNC_AFTER_RULE_ERROR;
2011       }
2012       break;
2013     case LHS_ALIAS_3:
2014       if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2015         psp->state = IN_RHS;
2016       }else{
2017         ErrorMsg(psp->filename,psp->tokenlineno,
2018           "Missing \"->\" following: \"%s(%s)\".",
2019            psp->lhs->name,psp->lhsalias);
2020         psp->errorcnt++;
2021         psp->state = RESYNC_AFTER_RULE_ERROR;
2022       }
2023       break;
2024     case IN_RHS:
2025       if( x[0]=='.' ){
2026         struct rule *rp;
2027         rp = (struct rule *)malloc( sizeof(struct rule) +
2028              sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs );
2029         if( rp==0 ){
2030           ErrorMsg(psp->filename,psp->tokenlineno,
2031             "Can't allocate enough memory for this rule.");
2032           psp->errorcnt++;
2033           psp->prevrule = 0;
2034 	}else{
2035           int i;
2036           rp->ruleline = psp->tokenlineno;
2037           rp->rhs = (struct symbol**)&rp[1];
2038           rp->rhsalias = (char**)&(rp->rhs[psp->nrhs]);
2039           for(i=0; i<psp->nrhs; i++){
2040             rp->rhs[i] = psp->rhs[i];
2041             rp->rhsalias[i] = psp->alias[i];
2042 	  }
2043           rp->lhs = psp->lhs;
2044           rp->lhsalias = psp->lhsalias;
2045           rp->nrhs = psp->nrhs;
2046           rp->code = 0;
2047           rp->precsym = 0;
2048           rp->index = psp->gp->nrule++;
2049           rp->nextlhs = rp->lhs->rule;
2050           rp->lhs->rule = rp;
2051           rp->next = 0;
2052           if( psp->firstrule==0 ){
2053             psp->firstrule = psp->lastrule = rp;
2054 	  }else{
2055             psp->lastrule->next = rp;
2056             psp->lastrule = rp;
2057 	  }
2058           psp->prevrule = rp;
2059 	}
2060         psp->state = WAITING_FOR_DECL_OR_RULE;
2061       }else if( isalpha(x[0]) ){
2062         if( psp->nrhs>=MAXRHS ){
2063           ErrorMsg(psp->filename,psp->tokenlineno,
2064             "Too many symbol on RHS or rule beginning at \"%s\".",
2065             x);
2066           psp->errorcnt++;
2067           psp->state = RESYNC_AFTER_RULE_ERROR;
2068 	}else{
2069           psp->rhs[psp->nrhs] = Symbol_new(x);
2070           psp->alias[psp->nrhs] = 0;
2071           psp->nrhs++;
2072 	}
2073       }else if( x[0]=='(' && psp->nrhs>0 ){
2074         psp->state = RHS_ALIAS_1;
2075       }else{
2076         ErrorMsg(psp->filename,psp->tokenlineno,
2077           "Illegal character on RHS of rule: \"%s\".",x);
2078         psp->errorcnt++;
2079         psp->state = RESYNC_AFTER_RULE_ERROR;
2080       }
2081       break;
2082     case RHS_ALIAS_1:
2083       if( isalpha(x[0]) ){
2084         psp->alias[psp->nrhs-1] = x;
2085         psp->state = RHS_ALIAS_2;
2086       }else{
2087         ErrorMsg(psp->filename,psp->tokenlineno,
2088           "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2089           x,psp->rhs[psp->nrhs-1]->name);
2090         psp->errorcnt++;
2091         psp->state = RESYNC_AFTER_RULE_ERROR;
2092       }
2093       break;
2094     case RHS_ALIAS_2:
2095       if( x[0]==')' ){
2096         psp->state = IN_RHS;
2097       }else{
2098         ErrorMsg(psp->filename,psp->tokenlineno,
2099           "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2100         psp->errorcnt++;
2101         psp->state = RESYNC_AFTER_RULE_ERROR;
2102       }
2103       break;
2104     case WAITING_FOR_DECL_KEYWORD:
2105       if( isalpha(x[0]) ){
2106         psp->declkeyword = x;
2107         psp->declargslot = 0;
2108         psp->decllnslot = 0;
2109         psp->state = WAITING_FOR_DECL_ARG;
2110         if( strcmp(x,"name")==0 ){
2111           psp->declargslot = &(psp->gp->name);
2112 	}else if( strcmp(x,"include")==0 ){
2113           psp->declargslot = &(psp->gp->include);
2114           psp->decllnslot = &psp->gp->includeln;
2115 	}else if( strcmp(x,"code")==0 ){
2116           psp->declargslot = &(psp->gp->extracode);
2117           psp->decllnslot = &psp->gp->extracodeln;
2118 	}else if( strcmp(x,"token_destructor")==0 ){
2119           psp->declargslot = &psp->gp->tokendest;
2120           psp->decllnslot = &psp->gp->tokendestln;
2121 	}else if( strcmp(x,"default_destructor")==0 ){
2122           psp->declargslot = &psp->gp->vardest;
2123           psp->decllnslot = &psp->gp->vardestln;
2124 	}else if( strcmp(x,"token_prefix")==0 ){
2125           psp->declargslot = &psp->gp->tokenprefix;
2126 	}else if( strcmp(x,"syntax_error")==0 ){
2127           psp->declargslot = &(psp->gp->error);
2128           psp->decllnslot = &psp->gp->errorln;
2129 	}else if( strcmp(x,"parse_accept")==0 ){
2130           psp->declargslot = &(psp->gp->accept);
2131           psp->decllnslot = &psp->gp->acceptln;
2132 	}else if( strcmp(x,"parse_failure")==0 ){
2133           psp->declargslot = &(psp->gp->failure);
2134           psp->decllnslot = &psp->gp->failureln;
2135 	}else if( strcmp(x,"stack_overflow")==0 ){
2136           psp->declargslot = &(psp->gp->overflow);
2137           psp->decllnslot = &psp->gp->overflowln;
2138         }else if( strcmp(x,"extra_argument")==0 ){
2139           psp->declargslot = &(psp->gp->arg);
2140         }else if( strcmp(x,"token_type")==0 ){
2141           psp->declargslot = &(psp->gp->tokentype);
2142         }else if( strcmp(x,"default_type")==0 ){
2143           psp->declargslot = &(psp->gp->vartype);
2144         }else if( strcmp(x,"stack_size")==0 ){
2145           psp->declargslot = &(psp->gp->stacksize);
2146         }else if( strcmp(x,"start_symbol")==0 ){
2147           psp->declargslot = &(psp->gp->start);
2148         }else if( strcmp(x,"left")==0 ){
2149           psp->preccounter++;
2150           psp->declassoc = LEFT;
2151           psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2152         }else if( strcmp(x,"right")==0 ){
2153           psp->preccounter++;
2154           psp->declassoc = RIGHT;
2155           psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2156         }else if( strcmp(x,"nonassoc")==0 ){
2157           psp->preccounter++;
2158           psp->declassoc = NONE;
2159           psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2160 	}else if( strcmp(x,"destructor")==0 ){
2161           psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;
2162 	}else if( strcmp(x,"type")==0 ){
2163           psp->state = WAITING_FOR_DATATYPE_SYMBOL;
2164         }else if( strcmp(x,"fallback")==0 ){
2165           psp->fallback = 0;
2166           psp->state = WAITING_FOR_FALLBACK_ID;
2167         }else{
2168           ErrorMsg(psp->filename,psp->tokenlineno,
2169             "Unknown declaration keyword: \"%%%s\".",x);
2170           psp->errorcnt++;
2171           psp->state = RESYNC_AFTER_DECL_ERROR;
2172 	}
2173       }else{
2174         ErrorMsg(psp->filename,psp->tokenlineno,
2175           "Illegal declaration keyword: \"%s\".",x);
2176         psp->errorcnt++;
2177         psp->state = RESYNC_AFTER_DECL_ERROR;
2178       }
2179       break;
2180     case WAITING_FOR_DESTRUCTOR_SYMBOL:
2181       if( !isalpha(x[0]) ){
2182         ErrorMsg(psp->filename,psp->tokenlineno,
2183           "Symbol name missing after %destructor keyword");
2184         psp->errorcnt++;
2185         psp->state = RESYNC_AFTER_DECL_ERROR;
2186       }else{
2187         struct symbol *sp = Symbol_new(x);
2188         psp->declargslot = &sp->destructor;
2189         psp->decllnslot = &sp->destructorln;
2190         psp->state = WAITING_FOR_DECL_ARG;
2191       }
2192       break;
2193     case WAITING_FOR_DATATYPE_SYMBOL:
2194       if( !isalpha(x[0]) ){
2195         ErrorMsg(psp->filename,psp->tokenlineno,
2196           "Symbol name missing after %destructor keyword");
2197         psp->errorcnt++;
2198         psp->state = RESYNC_AFTER_DECL_ERROR;
2199       }else{
2200         struct symbol *sp = Symbol_new(x);
2201         psp->declargslot = &sp->datatype;
2202         psp->decllnslot = 0;
2203         psp->state = WAITING_FOR_DECL_ARG;
2204       }
2205       break;
2206     case WAITING_FOR_PRECEDENCE_SYMBOL:
2207       if( x[0]=='.' ){
2208         psp->state = WAITING_FOR_DECL_OR_RULE;
2209       }else if( isupper(x[0]) ){
2210         struct symbol *sp;
2211         sp = Symbol_new(x);
2212         if( sp->prec>=0 ){
2213           ErrorMsg(psp->filename,psp->tokenlineno,
2214             "Symbol \"%s\" has already be given a precedence.",x);
2215           psp->errorcnt++;
2216 	}else{
2217           sp->prec = psp->preccounter;
2218           sp->assoc = psp->declassoc;
2219 	}
2220       }else{
2221         ErrorMsg(psp->filename,psp->tokenlineno,
2222           "Can't assign a precedence to \"%s\".",x);
2223         psp->errorcnt++;
2224       }
2225       break;
2226     case WAITING_FOR_DECL_ARG:
2227       if( (x[0]=='{' || x[0]=='\"' || isalnum(x[0])) ){
2228         if( *(psp->declargslot)!=0 ){
2229           ErrorMsg(psp->filename,psp->tokenlineno,
2230             "The argument \"%s\" to declaration \"%%%s\" is not the first.",
2231             x[0]=='\"' ? &x[1] : x,psp->declkeyword);
2232           psp->errorcnt++;
2233           psp->state = RESYNC_AFTER_DECL_ERROR;
2234 	}else{
2235           *(psp->declargslot) = (x[0]=='\"' || x[0]=='{') ? &x[1] : x;
2236           if( psp->decllnslot ) *psp->decllnslot = psp->tokenlineno;
2237           psp->state = WAITING_FOR_DECL_OR_RULE;
2238 	}
2239       }else{
2240         ErrorMsg(psp->filename,psp->tokenlineno,
2241           "Illegal argument to %%%s: %s",psp->declkeyword,x);
2242         psp->errorcnt++;
2243         psp->state = RESYNC_AFTER_DECL_ERROR;
2244       }
2245       break;
2246     case WAITING_FOR_FALLBACK_ID:
2247       if( x[0]=='.' ){
2248         psp->state = WAITING_FOR_DECL_OR_RULE;
2249       }else if( !isupper(x[0]) ){
2250         ErrorMsg(psp->filename, psp->tokenlineno,
2251           "%%fallback argument \"%s\" should be a token", x);
2252         psp->errorcnt++;
2253       }else{
2254         struct symbol *sp = Symbol_new(x);
2255         if( psp->fallback==0 ){
2256           psp->fallback = sp;
2257         }else if( sp->fallback ){
2258           ErrorMsg(psp->filename, psp->tokenlineno,
2259             "More than one fallback assigned to token %s", x);
2260           psp->errorcnt++;
2261         }else{
2262           sp->fallback = psp->fallback;
2263           psp->gp->has_fallback = 1;
2264         }
2265       }
2266       break;
2267     case RESYNC_AFTER_RULE_ERROR:
2268 /*      if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2269 **      break; */
2270     case RESYNC_AFTER_DECL_ERROR:
2271       if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2272       if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;
2273       break;
2274   }
2275 }
2276 
2277 /* In spite of its name, this function is really a scanner.  It read
2278 ** in the entire input file (all at once) then tokenizes it.  Each
2279 ** token is passed to the function "parseonetoken" which builds all
2280 ** the appropriate data structures in the global state vector "gp".
2281 */
2282 void Parse(gp)
2283 struct lemon *gp;
2284 {
2285   struct pstate ps;
2286   FILE *fp;
2287   char *filebuf;
2288   int filesize;
2289   int lineno;
2290   int c;
2291   char *cp, *nextcp;
2292   int startline = 0;
2293 
2294   ps.gp = gp;
2295   ps.filename = gp->filename;
2296   ps.errorcnt = 0;
2297   ps.state = INITIALIZE;
2298 
2299   /* Begin by reading the input file */
2300   fp = fopen(ps.filename,"rb");
2301   if( fp==0 ){
2302     ErrorMsg(ps.filename,0,"Can't open this file for reading.");
2303     gp->errorcnt++;
2304     return;
2305   }
2306   fseek(fp,0,2);
2307   filesize = ftell(fp);
2308   rewind(fp);
2309   filebuf = (char *)malloc( filesize+1 );
2310   if( filebuf==0 ){
2311     ErrorMsg(ps.filename,0,"Can't allocate %d of memory to hold this file.",
2312       filesize+1);
2313     gp->errorcnt++;
2314     return;
2315   }
2316   if( fread(filebuf,1,filesize,fp)!=filesize ){
2317     ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",
2318       filesize);
2319     free(filebuf);
2320     gp->errorcnt++;
2321     return;
2322   }
2323   fclose(fp);
2324   filebuf[filesize] = 0;
2325 
2326   /* Now scan the text of the input file */
2327   lineno = 1;
2328   for(cp=filebuf; (c= *cp)!=0; ){
2329     if( c=='\n' ) lineno++;              /* Keep track of the line number */
2330     if( isspace(c) ){ cp++; continue; }  /* Skip all white space */
2331     if( c=='/' && cp[1]=='/' ){          /* Skip C++ style comments */
2332       cp+=2;
2333       while( (c= *cp)!=0 && c!='\n' ) cp++;
2334       continue;
2335     }
2336     if( c=='/' && cp[1]=='*' ){          /* Skip C style comments */
2337       cp+=2;
2338       while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){
2339         if( c=='\n' ) lineno++;
2340         cp++;
2341       }
2342       if( c ) cp++;
2343       continue;
2344     }
2345     ps.tokenstart = cp;                /* Mark the beginning of the token */
2346     ps.tokenlineno = lineno;           /* Linenumber on which token begins */
2347     if( c=='\"' ){                     /* String literals */
2348       cp++;
2349       while( (c= *cp)!=0 && c!='\"' ){
2350         if( c=='\n' ) lineno++;
2351         cp++;
2352       }
2353       if( c==0 ){
2354         ErrorMsg(ps.filename,startline,
2355 "String starting on this line is not terminated before the end of the file.");
2356         ps.errorcnt++;
2357         nextcp = cp;
2358       }else{
2359         nextcp = cp+1;
2360       }
2361     }else if( c=='{' ){               /* A block of C code */
2362       int level;
2363       cp++;
2364       for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){
2365         if( c=='\n' ) lineno++;
2366         else if( c=='{' ) level++;
2367         else if( c=='}' ) level--;
2368         else if( c=='/' && cp[1]=='*' ){  /* Skip comments */
2369           int prevc;
2370           cp = &cp[2];
2371           prevc = 0;
2372           while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){
2373             if( c=='\n' ) lineno++;
2374             prevc = c;
2375             cp++;
2376 	  }
2377 	}else if( c=='/' && cp[1]=='/' ){  /* Skip C++ style comments too */
2378           cp = &cp[2];
2379           while( (c= *cp)!=0 && c!='\n' ) cp++;
2380           if( c ) lineno++;
2381 	}else if( c=='\'' || c=='\"' ){    /* String a character literals */
2382           int startchar, prevc;
2383           startchar = c;
2384           prevc = 0;
2385           for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){
2386             if( c=='\n' ) lineno++;
2387             if( prevc=='\\' ) prevc = 0;
2388             else              prevc = c;
2389 	  }
2390 	}
2391       }
2392       if( c==0 ){
2393         ErrorMsg(ps.filename,ps.tokenlineno,
2394 "C code starting on this line is not terminated before the end of the file.");
2395         ps.errorcnt++;
2396         nextcp = cp;
2397       }else{
2398         nextcp = cp+1;
2399       }
2400     }else if( isalnum(c) ){          /* Identifiers */
2401       while( (c= *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2402       nextcp = cp;
2403     }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */
2404       cp += 3;
2405       nextcp = cp;
2406     }else{                          /* All other (one character) operators */
2407       cp++;
2408       nextcp = cp;
2409     }
2410     c = *cp;
2411     *cp = 0;                        /* Null terminate the token */
2412     parseonetoken(&ps);             /* Parse the token */
2413     *cp = c;                        /* Restore the buffer */
2414     cp = nextcp;
2415   }
2416   free(filebuf);                    /* Release the buffer after parsing */
2417   gp->rule = ps.firstrule;
2418   gp->errorcnt = ps.errorcnt;
2419 }
2420 /*************************** From the file "plink.c" *********************/
2421 /*
2422 ** Routines processing configuration follow-set propagation links
2423 ** in the LEMON parser generator.
2424 */
2425 static struct plink *plink_freelist = 0;
2426 
2427 /* Allocate a new plink */
2428 struct plink *Plink_new(){
2429   struct plink *new;
2430 
2431   if( plink_freelist==0 ){
2432     int i;
2433     int amt = 100;
2434     plink_freelist = (struct plink *)malloc( sizeof(struct plink)*amt );
2435     if( plink_freelist==0 ){
2436       fprintf(stderr,
2437       "Unable to allocate memory for a new follow-set propagation link.\n");
2438       exit(1);
2439     }
2440     for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
2441     plink_freelist[amt-1].next = 0;
2442   }
2443   new = plink_freelist;
2444   plink_freelist = plink_freelist->next;
2445   return new;
2446 }
2447 
2448 /* Add a plink to a plink list */
2449 void Plink_add(plpp,cfp)
2450 struct plink **plpp;
2451 struct config *cfp;
2452 {
2453   struct plink *new;
2454   new = Plink_new();
2455   new->next = *plpp;
2456   *plpp = new;
2457   new->cfp = cfp;
2458 }
2459 
2460 /* Transfer every plink on the list "from" to the list "to" */
2461 void Plink_copy(to,from)
2462 struct plink **to;
2463 struct plink *from;
2464 {
2465   struct plink *nextpl;
2466   while( from ){
2467     nextpl = from->next;
2468     from->next = *to;
2469     *to = from;
2470     from = nextpl;
2471   }
2472 }
2473 
2474 /* Delete every plink on the list */
2475 void Plink_delete(plp)
2476 struct plink *plp;
2477 {
2478   struct plink *nextpl;
2479 
2480   while( plp ){
2481     nextpl = plp->next;
2482     plp->next = plink_freelist;
2483     plink_freelist = plp;
2484     plp = nextpl;
2485   }
2486 }
2487 /*********************** From the file "report.c" **************************/
2488 /*
2489 ** Procedures for generating reports and tables in the LEMON parser generator.
2490 */
2491 
2492 /* Generate a filename with the given suffix.  Space to hold the
2493 ** name comes from malloc() and must be freed by the calling
2494 ** function.
2495 */
2496 PRIVATE char *file_makename(lemp,suffix)
2497 struct lemon *lemp;
2498 char *suffix;
2499 {
2500   char *name;
2501   char *cp;
2502 
2503   name = malloc( strlen(lemp->filename) + strlen(suffix) + 5 );
2504   if( name==0 ){
2505     fprintf(stderr,"Can't allocate space for a filename.\n");
2506     exit(1);
2507   }
2508   strcpy(name,lemp->filename);
2509   cp = strrchr(name,'.');
2510   if( cp ) *cp = 0;
2511   strcat(name,suffix);
2512   return name;
2513 }
2514 
2515 /* Open a file with a name based on the name of the input file,
2516 ** but with a different (specified) suffix, and return a pointer
2517 ** to the stream */
2518 PRIVATE FILE *file_open(lemp,suffix,mode)
2519 struct lemon *lemp;
2520 char *suffix;
2521 char *mode;
2522 {
2523   FILE *fp;
2524 
2525   if( lemp->outname ) free(lemp->outname);
2526   lemp->outname = file_makename(lemp, suffix);
2527   fp = fopen(lemp->outname,mode);
2528   if( fp==0 && *mode=='w' ){
2529     fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
2530     lemp->errorcnt++;
2531     return 0;
2532   }
2533   return fp;
2534 }
2535 
2536 /* Duplicate the input file without comments and without actions
2537 ** on rules */
2538 void Reprint(lemp)
2539 struct lemon *lemp;
2540 {
2541   struct rule *rp;
2542   struct symbol *sp;
2543   int i, j, maxlen, len, ncolumns, skip;
2544   printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
2545   maxlen = 10;
2546   for(i=0; i<lemp->nsymbol; i++){
2547     sp = lemp->symbols[i];
2548     len = strlen(sp->name);
2549     if( len>maxlen ) maxlen = len;
2550   }
2551   ncolumns = 76/(maxlen+5);
2552   if( ncolumns<1 ) ncolumns = 1;
2553   skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
2554   for(i=0; i<skip; i++){
2555     printf("//");
2556     for(j=i; j<lemp->nsymbol; j+=skip){
2557       sp = lemp->symbols[j];
2558       assert( sp->index==j );
2559       printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
2560     }
2561     printf("\n");
2562   }
2563   for(rp=lemp->rule; rp; rp=rp->next){
2564     printf("%s",rp->lhs->name);
2565 /*    if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
2566     printf(" ::=");
2567     for(i=0; i<rp->nrhs; i++){
2568       printf(" %s",rp->rhs[i]->name);
2569 /*      if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
2570     }
2571     printf(".");
2572     if( rp->precsym ) printf(" [%s]",rp->precsym->name);
2573 /*    if( rp->code ) printf("\n    %s",rp->code); */
2574     printf("\n");
2575   }
2576 }
2577 
2578 void ConfigPrint(fp,cfp)
2579 FILE *fp;
2580 struct config *cfp;
2581 {
2582   struct rule *rp;
2583   int i;
2584   rp = cfp->rp;
2585   fprintf(fp,"%s ::=",rp->lhs->name);
2586   for(i=0; i<=rp->nrhs; i++){
2587     if( i==cfp->dot ) fprintf(fp," *");
2588     if( i==rp->nrhs ) break;
2589     fprintf(fp," %s",rp->rhs[i]->name);
2590   }
2591 }
2592 
2593 /* #define TEST */
2594 #ifdef TEST
2595 /* Print a set */
2596 PRIVATE void SetPrint(out,set,lemp)
2597 FILE *out;
2598 char *set;
2599 struct lemon *lemp;
2600 {
2601   int i;
2602   char *spacer;
2603   spacer = "";
2604   fprintf(out,"%12s[","");
2605   for(i=0; i<lemp->nterminal; i++){
2606     if( SetFind(set,i) ){
2607       fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
2608       spacer = " ";
2609     }
2610   }
2611   fprintf(out,"]\n");
2612 }
2613 
2614 /* Print a plink chain */
2615 PRIVATE void PlinkPrint(out,plp,tag)
2616 FILE *out;
2617 struct plink *plp;
2618 char *tag;
2619 {
2620   while( plp ){
2621     fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->index);
2622     ConfigPrint(out,plp->cfp);
2623     fprintf(out,"\n");
2624     plp = plp->next;
2625   }
2626 }
2627 #endif
2628 
2629 /* Print an action to the given file descriptor.  Return FALSE if
2630 ** nothing was actually printed.
2631 */
2632 int PrintAction(struct action *ap, FILE *fp, int indent){
2633   int result = 1;
2634   switch( ap->type ){
2635     case SHIFT:
2636       fprintf(fp,"%*s shift  %d",indent,ap->sp->name,ap->x.stp->index);
2637       break;
2638     case REDUCE:
2639       fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
2640       break;
2641     case ACCEPT:
2642       fprintf(fp,"%*s accept",indent,ap->sp->name);
2643       break;
2644     case ERROR:
2645       fprintf(fp,"%*s error",indent,ap->sp->name);
2646       break;
2647     case CONFLICT:
2648       fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
2649         indent,ap->sp->name,ap->x.rp->index);
2650       break;
2651     case SH_RESOLVED:
2652     case RD_RESOLVED:
2653     case NOT_USED:
2654       result = 0;
2655       break;
2656   }
2657   return result;
2658 }
2659 
2660 /* Generate the "y.output" log file */
2661 void ReportOutput(lemp)
2662 struct lemon *lemp;
2663 {
2664   int i;
2665   struct state *stp;
2666   struct config *cfp;
2667   struct action *ap;
2668   FILE *fp;
2669 
2670   fp = file_open(lemp,".out","w");
2671   if( fp==0 ) return;
2672   fprintf(fp," \b");
2673   for(i=0; i<lemp->nstate; i++){
2674     stp = lemp->sorted[i];
2675     fprintf(fp,"State %d:\n",stp->index);
2676     if( lemp->basisflag ) cfp=stp->bp;
2677     else                  cfp=stp->cfp;
2678     while( cfp ){
2679       char buf[20];
2680       if( cfp->dot==cfp->rp->nrhs ){
2681         sprintf(buf,"(%d)",cfp->rp->index);
2682         fprintf(fp,"    %5s ",buf);
2683       }else{
2684         fprintf(fp,"          ");
2685       }
2686       ConfigPrint(fp,cfp);
2687       fprintf(fp,"\n");
2688 #ifdef TEST
2689       SetPrint(fp,cfp->fws,lemp);
2690       PlinkPrint(fp,cfp->fplp,"To  ");
2691       PlinkPrint(fp,cfp->bplp,"From");
2692 #endif
2693       if( lemp->basisflag ) cfp=cfp->bp;
2694       else                  cfp=cfp->next;
2695     }
2696     fprintf(fp,"\n");
2697     for(ap=stp->ap; ap; ap=ap->next){
2698       if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
2699     }
2700     fprintf(fp,"\n");
2701   }
2702   fclose(fp);
2703   return;
2704 }
2705 
2706 /* Search for the file "name" which is in the same directory as
2707 ** the exacutable */
2708 PRIVATE char *pathsearch(argv0,name,modemask)
2709 char *argv0;
2710 char *name;
2711 int modemask;
2712 {
2713   char *pathlist;
2714   char *path,*cp;
2715   char c;
2716   extern int access();
2717 
2718 #ifdef __WIN32__
2719   cp = strrchr(argv0,'\\');
2720 #else
2721   cp = strrchr(argv0,'/');
2722 #endif
2723   if( cp ){
2724     c = *cp;
2725     *cp = 0;
2726     path = (char *)malloc( strlen(argv0) + strlen(name) + 2 );
2727     if( path ) sprintf(path,"%s/%s",argv0,name);
2728     *cp = c;
2729   }else{
2730     extern char *getenv();
2731     pathlist = getenv("PATH");
2732     if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
2733     path = (char *)malloc( strlen(pathlist)+strlen(name)+2 );
2734     if( path!=0 ){
2735       while( *pathlist ){
2736         cp = strchr(pathlist,':');
2737         if( cp==0 ) cp = &pathlist[strlen(pathlist)];
2738         c = *cp;
2739         *cp = 0;
2740         sprintf(path,"%s/%s",pathlist,name);
2741         *cp = c;
2742         if( c==0 ) pathlist = "";
2743         else pathlist = &cp[1];
2744         if( access(path,modemask)==0 ) break;
2745       }
2746     }
2747   }
2748   return path;
2749 }
2750 
2751 /* Given an action, compute the integer value for that action
2752 ** which is to be put in the action table of the generated machine.
2753 ** Return negative if no action should be generated.
2754 */
2755 PRIVATE int compute_action(lemp,ap)
2756 struct lemon *lemp;
2757 struct action *ap;
2758 {
2759   int act;
2760   switch( ap->type ){
2761     case SHIFT:  act = ap->x.stp->index;               break;
2762     case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
2763     case ERROR:  act = lemp->nstate + lemp->nrule;     break;
2764     case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break;
2765     default:     act = -1; break;
2766   }
2767   return act;
2768 }
2769 
2770 #define LINESIZE 1000
2771 /* The next cluster of routines are for reading the template file
2772 ** and writing the results to the generated parser */
2773 /* The first function transfers data from "in" to "out" until
2774 ** a line is seen which begins with "%%".  The line number is
2775 ** tracked.
2776 **
2777 ** if name!=0, then any word that begin with "Parse" is changed to
2778 ** begin with *name instead.
2779 */
2780 PRIVATE void tplt_xfer(name,in,out,lineno)
2781 char *name;
2782 FILE *in;
2783 FILE *out;
2784 int *lineno;
2785 {
2786   int i, iStart;
2787   char line[LINESIZE];
2788   while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
2789     (*lineno)++;
2790     iStart = 0;
2791     if( name ){
2792       for(i=0; line[i]; i++){
2793         if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0
2794           && (i==0 || !isalpha(line[i-1]))
2795         ){
2796           if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);
2797           fprintf(out,"%s",name);
2798           i += 4;
2799           iStart = i+1;
2800         }
2801       }
2802     }
2803     fprintf(out,"%s",&line[iStart]);
2804   }
2805 }
2806 
2807 /* The next function finds the template file and opens it, returning
2808 ** a pointer to the opened file. */
2809 PRIVATE FILE *tplt_open(lemp)
2810 struct lemon *lemp;
2811 {
2812   static char templatename[] = "lempar.c";
2813   char buf[1000];
2814   FILE *in;
2815   char *tpltname;
2816   char *cp;
2817 
2818   cp = strrchr(lemp->filename,'.');
2819   if( cp ){
2820     sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
2821   }else{
2822     sprintf(buf,"%s.lt",lemp->filename);
2823   }
2824   if( access(buf,004)==0 ){
2825     tpltname = buf;
2826   }else if( access(templatename,004)==0 ){
2827     tpltname = templatename;
2828   }else{
2829     tpltname = pathsearch(lemp->argv0,templatename,0);
2830   }
2831   if( tpltname==0 ){
2832     fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
2833     templatename);
2834     lemp->errorcnt++;
2835     return 0;
2836   }
2837   in = fopen(tpltname,"r");
2838   if( in==0 ){
2839     fprintf(stderr,"Can't open the template file \"%s\".\n",templatename);
2840     lemp->errorcnt++;
2841     return 0;
2842   }
2843   return in;
2844 }
2845 
2846 /* Print a string to the file and keep the linenumber up to date */
2847 PRIVATE void tplt_print(out,lemp,str,strln,lineno)
2848 FILE *out;
2849 struct lemon *lemp;
2850 char *str;
2851 int strln;
2852 int *lineno;
2853 {
2854   if( str==0 ) return;
2855   fprintf(out,"#line %d \"%s\"\n",strln,lemp->filename); (*lineno)++;
2856   while( *str ){
2857     if( *str=='\n' ) (*lineno)++;
2858     putc(*str,out);
2859     str++;
2860   }
2861   fprintf(out,"\n#line %d \"%s\"\n",*lineno+2,lemp->outname); (*lineno)+=2;
2862   return;
2863 }
2864 
2865 /*
2866 ** The following routine emits code for the destructor for the
2867 ** symbol sp
2868 */
2869 void emit_destructor_code(out,sp,lemp,lineno)
2870 FILE *out;
2871 struct symbol *sp;
2872 struct lemon *lemp;
2873 int *lineno;
2874 {
2875  char *cp = 0;
2876 
2877  int linecnt = 0;
2878  if( sp->type==TERMINAL ){
2879    cp = lemp->tokendest;
2880    if( cp==0 ) return;
2881    fprintf(out,"#line %d \"%s\"\n{",lemp->tokendestln,lemp->filename);
2882  }else if( sp->destructor ){
2883    cp = sp->destructor;
2884    fprintf(out,"#line %d \"%s\"\n{",sp->destructorln,lemp->filename);
2885  }else if( lemp->vardest ){
2886    cp = lemp->vardest;
2887    if( cp==0 ) return;
2888    fprintf(out,"#line %d \"%s\"\n{",lemp->vardestln,lemp->filename);
2889  }else{
2890    assert( 0 );  /* Cannot happen */
2891  }
2892  for(; *cp; cp++){
2893    if( *cp=='$' && cp[1]=='$' ){
2894      fprintf(out,"(yypminor->yy%d)",sp->dtnum);
2895      cp++;
2896      continue;
2897    }
2898    if( *cp=='\n' ) linecnt++;
2899    fputc(*cp,out);
2900  }
2901  (*lineno) += 3 + linecnt;
2902  fprintf(out,"}\n#line %d \"%s\"\n",*lineno,lemp->outname);
2903  return;
2904 }
2905 
2906 /*
2907 ** Return TRUE (non-zero) if the given symbol has a destructor.
2908 */
2909 int has_destructor(sp, lemp)
2910 struct symbol *sp;
2911 struct lemon *lemp;
2912 {
2913   int ret;
2914   if( sp->type==TERMINAL ){
2915     ret = lemp->tokendest!=0;
2916   }else{
2917     ret = lemp->vardest!=0 || sp->destructor!=0;
2918   }
2919   return ret;
2920 }
2921 
2922 /*
2923 ** Generate code which executes when the rule "rp" is reduced.  Write
2924 ** the code to "out".  Make sure lineno stays up-to-date.
2925 */
2926 PRIVATE void emit_code(out,rp,lemp,lineno)
2927 FILE *out;
2928 struct rule *rp;
2929 struct lemon *lemp;
2930 int *lineno;
2931 {
2932  char *cp, *xp;
2933  int linecnt = 0;
2934  int i;
2935  char lhsused = 0;    /* True if the LHS element has been used */
2936  char used[MAXRHS];   /* True for each RHS element which is used */
2937 
2938  for(i=0; i<rp->nrhs; i++) used[i] = 0;
2939  lhsused = 0;
2940 
2941  /* Generate code to do the reduce action */
2942  if( rp->code ){
2943    fprintf(out,"#line %d \"%s\"\n{",rp->line,lemp->filename);
2944    for(cp=rp->code; *cp; cp++){
2945      if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
2946        char saved;
2947        for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
2948        saved = *xp;
2949        *xp = 0;
2950        if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
2951          fprintf(out,"yygotominor.yy%d",rp->lhs->dtnum);
2952          cp = xp;
2953          lhsused = 1;
2954        }else{
2955          for(i=0; i<rp->nrhs; i++){
2956            if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
2957              fprintf(out,"yymsp[%d].minor.yy%d",i-rp->nrhs+1,rp->rhs[i]->dtnum);
2958              cp = xp;
2959              used[i] = 1;
2960              break;
2961            }
2962          }
2963        }
2964        *xp = saved;
2965      }
2966      if( *cp=='\n' ) linecnt++;
2967      fputc(*cp,out);
2968    } /* End loop */
2969    (*lineno) += 3 + linecnt;
2970    fprintf(out,"}\n#line %d \"%s\"\n",*lineno,lemp->outname);
2971  } /* End if( rp->code ) */
2972 
2973  /* Check to make sure the LHS has been used */
2974  if( rp->lhsalias && !lhsused ){
2975    ErrorMsg(lemp->filename,rp->ruleline,
2976      "Label \"%s\" for \"%s(%s)\" is never used.",
2977        rp->lhsalias,rp->lhs->name,rp->lhsalias);
2978    lemp->errorcnt++;
2979  }
2980 
2981  /* Generate destructor code for RHS symbols which are not used in the
2982  ** reduce code */
2983  for(i=0; i<rp->nrhs; i++){
2984    if( rp->rhsalias[i] && !used[i] ){
2985      ErrorMsg(lemp->filename,rp->ruleline,
2986        "Label %s for \"%s(%s)\" is never used.",
2987        rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
2988      lemp->errorcnt++;
2989    }else if( rp->rhsalias[i]