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