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