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