BadVPN – Blame information for rev 1

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