6 ** This file contains all sources (including headers) to the LEMON
7 ** LALR(1) parser generator. The sources have been combined into a
8 ** single file to make it easy to include LEMON in the source tree
9 ** and Makefile of another program.
11 ** The author of this program disclaims copyright.
19 #include <unistd.h> /* access() */
21 #define UNUSED(x) ( (void)(x) )
24 # if defined(_WIN32) || defined(WIN32)
30 #define NORETURN __attribute__ ((__noreturn__))
35 /* #define PRIVATE static */
36 #define PRIVATE static
39 #define MAXRHS 5 /* Set low to exercise exception code */
44 void *msort(void *list
, void **next
, int(*cmp
)(void *, void *));
46 static void memory_error() NORETURN
;
48 /******** From the file "action.h" *************************************/
49 struct action
*Action_new();
50 struct action
*Action_sort();
53 /********* From the file "assert.h" ************************************/
54 void myassert() NORETURN
;
56 # define assert(X) if(!(X))myassert(__FILE__,__LINE__)
61 /********** From the file "build.h" ************************************/
62 void FindRulePrecedences();
66 void FindFollowSets();
69 /********* From the file "configlist.h" *********************************/
70 void Configlist_init(/* void */);
71 struct config
*Configlist_add(/* struct rule *, int */);
72 struct config
*Configlist_addbasis(/* struct rule *, int */);
73 void Configlist_closure(/* void */);
74 void Configlist_sort(/* void */);
75 void Configlist_sortbasis(/* void */);
76 struct config
*Configlist_return(/* void */);
77 struct config
*Configlist_basis(/* void */);
78 void Configlist_eat(/* struct config * */);
79 void Configlist_reset(/* void */);
81 /********* From the file "error.h" ***************************************/
82 void ErrorMsg(const char *, int,const char *, ...);
84 /****** From the file "option.h" ******************************************/
86 enum { OPT_FLAG
=1, OPT_INT
, OPT_DBL
, OPT_STR
,
87 OPT_FFLAG
, OPT_FINT
, OPT_FDBL
, OPT_FSTR
} type
;
92 int OptInit(/* char**,struct s_options*,FILE* */);
93 int OptNArgs(/* void */);
94 char *OptArg(/* int */);
95 void OptErr(/* int */);
96 void OptPrint(/* void */);
98 /******** From the file "parse.h" *****************************************/
99 void Parse(/* struct lemon *lemp */);
101 /********* From the file "plink.h" ***************************************/
102 struct plink
*Plink_new(/* void */);
103 void Plink_add(/* struct plink **, struct config * */);
104 void Plink_copy(/* struct plink **, struct plink * */);
105 void Plink_delete(/* struct plink * */);
107 /********** From the file "report.h" *************************************/
108 void Reprint(/* struct lemon * */);
109 void ReportOutput(/* struct lemon * */);
110 void ReportTable(/* struct lemon * */);
111 void ReportHeader(/* struct lemon * */);
112 void CompressTables(/* struct lemon * */);
114 /********** From the file "set.h" ****************************************/
115 void SetSize(/* int N */); /* All sets will be of size N */
116 char *SetNew(/* void */); /* A new set for element 0..N */
117 void SetFree(/* char* */); /* Deallocate a set */
119 int SetAdd(/* char*,int */); /* Add element to a set */
120 int SetUnion(/* char *A,char *B */); /* A <- A U B, thru element N */
122 #define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
124 /********** From the file "struct.h" *************************************/
126 ** Principal data structures for the LEMON parser generator.
129 typedef enum {Bo_FALSE
=0, Bo_TRUE
} Boolean
;
131 /* Symbols (terminals and nonterminals) of the grammar are stored
132 ** in the following: */
134 char *name
; /* Name of the symbol */
135 int index
; /* Index number for this symbol */
139 } type
; /* Symbols are all either TERMINALS or NTs */
140 struct rule
*rule
; /* Linked list of rules of this (if an NT) */
141 struct symbol
*fallback
; /* fallback token in case this token doesn't parse */
142 int prec
; /* Precedence if defined (-1 otherwise) */
148 } assoc
; /* Associativity if predecence is defined */
149 char *firstset
; /* First-set for all rules of this symbol */
150 Boolean lambda
; /* True if NT and can generate an empty string */
151 char *destructor
; /* Code which executes whenever this symbol is
152 ** popped from the stack during error processing */
153 int destructorln
; /* Line number of destructor code */
154 char *datatype
; /* The data type of information held by this
155 ** object. Only used if type==NONTERMINAL */
156 int dtnum
; /* The data type number. In the parser, the value
157 ** stack is a union. The .yy%d element of this
158 ** union is the correct data type for this object */
161 /* Each production rule in the grammar is stored in the following
164 struct symbol
*lhs
; /* Left-hand side of the rule */
165 char *lhsalias
; /* Alias for the LHS (NULL if none) */
166 int ruleline
; /* Line number for the rule */
167 int nrhs
; /* Number of RHS symbols */
168 struct symbol
**rhs
; /* The RHS symbols */
169 char **rhsalias
; /* An alias for each RHS symbol (NULL if none) */
170 int line
; /* Line number at which code begins */
171 char *code
; /* The code executed when this rule is reduced */
172 struct symbol
*precsym
; /* Precedence symbol for this rule */
173 int index
; /* An index number for this rule */
174 Boolean canReduce
; /* True if this rule is ever reduced */
175 struct rule
*nextlhs
; /* Next rule with the same LHS */
176 struct rule
*next
; /* Next rule in the global list */
179 /* A configuration is a production rule of the grammar together with
180 ** a mark (dot) showing how much of that rule has been processed so far.
181 ** Configurations also contain a follow-set which is a list of terminal
182 ** symbols which are allowed to immediately follow the end of the rule.
183 ** Every configuration is recorded as an instance of the following: */
185 struct rule
*rp
; /* The rule upon which the configuration is based */
186 int dot
; /* The parse point */
187 char *fws
; /* Follow-set for this configuration only */
188 struct plink
*fplp
; /* Follow-set forward propagation links */
189 struct plink
*bplp
; /* Follow-set backwards propagation links */
190 struct state
*stp
; /* Pointer to state which contains this */
192 COMPLETE
, /* The status is used during followset and */
193 INCOMPLETE
/* shift computations */
195 struct config
*next
; /* Next configuration in the state */
196 struct config
*bp
; /* The next basis configuration */
199 /* Every shift or reduce operation is stored as one of the following */
201 struct symbol
*sp
; /* The look-ahead symbol */
207 CONFLICT
, /* Was a reduce, but part of a conflict */
208 SH_RESOLVED
, /* Was a shift. Precedence resolved conflict */
209 RD_RESOLVED
, /* Was reduce. Precedence resolved conflict */
210 NOT_USED
/* Deleted by compression */
213 struct state
*stp
; /* The new state, if a shift */
214 struct rule
*rp
; /* The rule, if a reduce */
216 struct action
*next
; /* Next action for this state */
217 struct action
*collide
; /* Next action with the same hash */
220 /* Each state of the generated parser's finite state machine
221 ** is encoded as an instance of the following structure. */
223 struct config
*bp
; /* The basis configurations for this state */
224 struct config
*cfp
; /* All configurations in this set */
225 int index
; /* Sequencial number for this state */
226 struct action
*ap
; /* Array of actions for this state */
227 int nTknAct
, nNtAct
; /* Number of actions on terminals and nonterminals */
228 int iTknOfst
, iNtOfst
; /* yy_action[] offset for terminals and nonterms */
229 int iDflt
; /* Default action */
231 #define NO_OFFSET (-2147483647)
233 /* A followset propagation link indicates that the contents of one
234 ** configuration followset should be propagated to another whenever
235 ** the first changes. */
237 struct config
*cfp
; /* The configuration to which linked */
238 struct plink
*next
; /* The next propagate link */
241 /* The state vector for the entire parser generator is recorded as
242 ** follows. (LEMON uses no global variables and makes little use of
243 ** static variables. Fields in the following structure can be thought
244 ** of as begin global variables in the program.) */
246 struct state
**sorted
; /* Table of states sorted by state number */
247 struct rule
*rule
; /* List of all rules */
248 int nstate
; /* Number of states */
249 int nrule
; /* Number of rules */
250 int nsymbol
; /* Number of terminal and nonterminal symbols */
251 int nterminal
; /* Number of terminal symbols */
252 struct symbol
**symbols
; /* Sorted array of pointers to symbols */
253 int errorcnt
; /* Number of errors */
254 struct symbol
*errsym
; /* The error symbol */
255 char *name
; /* Name of the generated parser */
256 char *arg
; /* Declaration of the 3th argument to parser */
257 char *tokentype
; /* Type of terminal symbols in the parser stack */
258 char *vartype
; /* The default type of non-terminal symbols */
259 char *start
; /* Name of the start symbol for the grammar */
260 char *stacksize
; /* Size of the parser stack */
261 char *include
; /* Code to put at the start of the C file */
262 int includeln
; /* Line number for start of include code */
263 char *error
; /* Code to execute when an error is seen */
264 int errorln
; /* Line number for start of error code */
265 char *overflow
; /* Code to execute on a stack overflow */
266 int overflowln
; /* Line number for start of overflow code */
267 char *failure
; /* Code to execute on parser failure */
268 int failureln
; /* Line number for start of failure code */
269 char *accept
; /* Code to execute when the parser excepts */
270 int acceptln
; /* Line number for the start of accept code */
271 char *extracode
; /* Code appended to the generated file */
272 int extracodeln
; /* Line number for the start of the extra code */
273 char *tokendest
; /* Code to execute to destroy token data */
274 int tokendestln
; /* Line number for token destroyer code */
275 char *vardest
; /* Code for the default non-terminal destructor */
276 int vardestln
; /* Line number for default non-term destructor code*/
277 char *filename
; /* Name of the input file */
278 char *tmplname
; /* Name of the template file */
279 char *outname
; /* Name of the current output file */
280 char *tokenprefix
; /* A prefix added to token names in the .h file */
281 int nconflict
; /* Number of parsing conflicts */
282 int tablesize
; /* Size of the parse tables */
283 int basisflag
; /* Print only basis configurations */
284 int has_fallback
; /* True if any %fallback is seen in the grammer */
285 char *argv0
; /* Name of the program */
288 #define MemoryCheck(X) if((X)==0){ \
292 /**************** From the file "table.h" *********************************/
294 ** All code in this file has been automatically generated
295 ** from a specification in the file
297 ** by the associative array code building program "aagen".
298 ** Do not edit this file! Instead, edit the specification
299 ** file, then rerun aagen.
302 ** Code for processing tables in the LEMON parser generator.
305 /* Routines for handling a strings */
309 void Strsafe_init(/* void */);
310 int Strsafe_insert(/* char * */);
311 char *Strsafe_find(/* char * */);
313 /* Routines for handling symbols of the grammar */
315 struct symbol
*Symbol_new();
316 int Symbolcmpp(/* struct symbol **, struct symbol ** */);
317 void Symbol_init(/* void */);
318 int Symbol_insert(/* struct symbol *, char * */);
319 struct symbol
*Symbol_find(/* char * */);
320 struct symbol
*Symbol_Nth(/* int */);
321 int Symbol_count(/* */);
322 int State_count(void);
323 struct symbol
**Symbol_arrayof(/* */);
325 /* Routines to manage the state table */
327 int Configcmp(/* struct config *, struct config * */);
328 struct state
*State_new();
329 void State_init(/* void */);
330 int State_insert(/* struct state *, struct config * */);
331 struct state
*State_find(/* struct config * */);
332 struct state
**State_arrayof(/* */);
334 /* Routines used for efficiency in Configlist_add */
336 void Configtable_init(/* void */);
337 int Configtable_insert(/* struct config * */);
338 struct config
*Configtable_find(/* struct config * */);
339 void Configtable_clear(/* int(*)(struct config *) */);
340 /****************** From the file "action.c" *******************************/
342 ** Routines processing parser actions in the LEMON parser generator.
345 /* Allocate a new parser action */
346 struct action
*Action_new(){
347 static struct action
*freelist
= NULL
;
350 if( freelist
==NULL
){
353 freelist
= (struct action
*)malloc( sizeof(struct action
)*amt
);
355 fprintf(stderr
,"Unable to allocate memory for a new parser action.");
358 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
359 freelist
[amt
-1].next
= 0;
362 freelist
= freelist
->next
;
366 /* Compare two actions */
367 static int actioncmp(ap1
,ap2
)
372 rc
= ap1
->sp
->index
- ap2
->sp
->index
;
373 if( rc
==0 ) rc
= (int)ap1
->type
- (int)ap2
->type
;
375 assert( ap1
->type
==REDUCE
|| ap1
->type
==RD_RESOLVED
|| ap1
->type
==CONFLICT
);
376 assert( ap2
->type
==REDUCE
|| ap2
->type
==RD_RESOLVED
|| ap2
->type
==CONFLICT
);
377 rc
= ap1
->x
.rp
->index
- ap2
->x
.rp
->index
;
382 /* Sort parser actions */
383 struct action
*Action_sort(ap
)
386 ap
= (struct action
*)msort(ap
,(void **)&ap
->next
,actioncmp
);
390 void Action_add(app
,type
,sp
,arg
)
403 new->x
.stp
= (struct state
*)arg
;
405 new->x
.rp
= (struct rule
*)arg
;
408 /********************** New code to implement the "acttab" module ***********/
410 ** This module implements routines use to construct the yy_action[] table.
414 ** The state of the yy_action table under construction is an instance of
415 ** the following structure
417 typedef struct acttab acttab
;
419 int nAction
; /* Number of used slots in aAction[] */
420 int nActionAlloc
; /* Slots allocated for aAction[] */
422 int lookahead
; /* Value of the lookahead token */
423 int action
; /* Action to take on the given lookahead */
424 } *aAction
, /* The yy_action[] table under construction */
425 *aLookahead
; /* A single new transaction set */
426 int mnLookahead
; /* Minimum aLookahead[].lookahead */
427 int mnAction
; /* Action associated with mnLookahead */
428 int mxLookahead
; /* Maximum aLookahead[].lookahead */
429 int nLookahead
; /* Used slots in aLookahead[] */
430 int nLookaheadAlloc
; /* Slots allocated in aLookahead[] */
433 /* Return the number of entries in the yy_action table */
434 #define acttab_size(X) ((X)->nAction)
436 /* The value for the N-th entry in yy_action */
437 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
439 /* The value for the N-th entry in yy_lookahead */
440 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
442 /* Free all memory associated with the given acttab */
444 PRIVATE void acttab_free(acttab *p){
446 free( p->aLookahead );
451 /* Allocate a new acttab structure */
452 PRIVATE acttab
*acttab_alloc(void){
453 acttab
*p
= malloc( sizeof(*p
) );
455 fprintf(stderr
,"Unable to allocate memory for a new acttab.");
458 memset(p
, 0, sizeof(*p
));
462 /* Add a new action to the current transaction set
464 PRIVATE
void acttab_action(acttab
*p
, int lookahead
, int action
){
465 if( p
->nLookahead
>=p
->nLookaheadAlloc
){
466 p
->nLookaheadAlloc
+= 25;
467 p
->aLookahead
= realloc( p
->aLookahead
,
468 sizeof(p
->aLookahead
[0])*p
->nLookaheadAlloc
);
469 if( p
->aLookahead
==0 ){
470 fprintf(stderr
,"malloc failed\n");
474 if( p
->nLookahead
==0 ){
475 p
->mxLookahead
= lookahead
;
476 p
->mnLookahead
= lookahead
;
477 p
->mnAction
= action
;
479 if( p
->mxLookahead
<lookahead
) p
->mxLookahead
= lookahead
;
480 if( p
->mnLookahead
>lookahead
){
481 p
->mnLookahead
= lookahead
;
482 p
->mnAction
= action
;
485 p
->aLookahead
[p
->nLookahead
].lookahead
= lookahead
;
486 p
->aLookahead
[p
->nLookahead
].action
= action
;
491 ** Add the transaction set built up with prior calls to acttab_action()
492 ** into the current action table. Then reset the transaction set back
493 ** to an empty set in preparation for a new round of acttab_action() calls.
495 ** Return the offset into the action table of the new transaction.
497 PRIVATE
int acttab_insert(acttab
*p
){
499 assert( p
->nLookahead
>0 );
501 /* Make sure we have enough space to hold the expanded action table
502 ** in the worst case. The worst case occurs if the transaction set
503 ** must be appended to the current action table
505 n
= p
->mxLookahead
+ 1;
506 if( p
->nAction
+ n
>= p
->nActionAlloc
){
507 int oldAlloc
= p
->nActionAlloc
;
508 p
->nActionAlloc
= p
->nAction
+ n
+ p
->nActionAlloc
+ 20;
509 p
->aAction
= realloc( p
->aAction
,
510 sizeof(p
->aAction
[0])*p
->nActionAlloc
);
512 fprintf(stderr
,"malloc failed\n");
515 for(i
=oldAlloc
; i
<p
->nActionAlloc
; i
++){
516 p
->aAction
[i
].lookahead
= -1;
517 p
->aAction
[i
].action
= -1;
521 /* Scan the existing action table looking for an offset where we can
522 ** insert the current transaction set. Fall out of the loop when that
523 ** offset is found. In the worst case, we fall out of the loop when
524 ** i reaches p->nAction, which means we append the new transaction set.
526 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
528 for(i
=0; i
<p
->nAction
+p
->mnLookahead
; i
++){
529 if( p
->aAction
[i
].lookahead
<0 ){
530 for(j
=0; j
<p
->nLookahead
; j
++){
531 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
533 if( p
->aAction
[k
].lookahead
>=0 ) break;
535 if( j
<p
->nLookahead
) continue;
536 for(j
=0; j
<p
->nAction
; j
++){
537 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) break;
540 break; /* Fits in empty slots */
542 }else if( p
->aAction
[i
].lookahead
==p
->mnLookahead
){
543 if( p
->aAction
[i
].action
!=p
->mnAction
) continue;
544 for(j
=0; j
<p
->nLookahead
; j
++){
545 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
546 if( k
<0 || k
>=p
->nAction
) break;
547 if( p
->aLookahead
[j
].lookahead
!=p
->aAction
[k
].lookahead
) break;
548 if( p
->aLookahead
[j
].action
!=p
->aAction
[k
].action
) break;
550 if( j
<p
->nLookahead
) continue;
552 for(j
=0; j
<p
->nAction
; j
++){
553 if( p
->aAction
[j
].lookahead
<0 ) continue;
554 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) n
++;
556 if( n
==p
->nLookahead
){
557 break; /* Same as a prior transaction set */
561 /* Insert transaction set at index i. */
562 for(j
=0; j
<p
->nLookahead
; j
++){
563 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
564 p
->aAction
[k
] = p
->aLookahead
[j
];
565 if( k
>=p
->nAction
) p
->nAction
= k
+1;
569 /* Return the offset that is added to the lookahead in order to get the
570 ** index into yy_action of the action */
571 return i
- p
->mnLookahead
;
574 /********************** From the file "assert.c" ****************************/
576 ** A more efficient way of handling assertions.
578 void myassert(file
,line
)
582 fprintf(stderr
,"Assertion failed on line %d of file \"%s\"\n",line
,file
);
585 /********************** From the file "build.c" *****************************/
587 ** Routines to construction the finite state machine for the LEMON
591 /* Find a precedence symbol of every rule in the grammar.
593 ** Those rules which have a precedence symbol coded in the input
594 ** grammar using the "[symbol]" construct will already have the
595 ** rp->precsym field filled. Other rules take as their precedence
596 ** symbol the first RHS symbol with a defined precedence. If there
597 ** are not RHS symbols with a defined precedence, the precedence
598 ** symbol field is left blank.
600 void FindRulePrecedences(xp
)
604 for(rp
=xp
->rule
; rp
; rp
=rp
->next
){
605 if( rp
->precsym
==0 ){
607 for(i
=0; i
<rp
->nrhs
; i
++){
608 if( rp
->rhs
[i
]->prec
>=0 ){
609 rp
->precsym
= rp
->rhs
[i
];
618 /* Find all nonterminals which will generate the empty string.
619 ** Then go back and compute the first sets of every nonterminal.
620 ** The first set is the set of all terminal symbols which can begin
621 ** a string generated by that nonterminal.
623 void FindFirstSets(lemp
)
630 for(i
=0; i
<lemp
->nsymbol
; i
++){
631 lemp
->symbols
[i
]->lambda
= Bo_FALSE
;
633 for(i
=lemp
->nterminal
; i
<lemp
->nsymbol
; i
++){
634 lemp
->symbols
[i
]->firstset
= SetNew();
637 /* First compute all lambdas */
640 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
641 if( rp
->lhs
->lambda
) continue;
642 for(i
=0; i
<rp
->nrhs
; i
++){
643 if( rp
->rhs
[i
]->lambda
==Bo_FALSE
) break;
646 rp
->lhs
->lambda
= Bo_TRUE
;
652 /* Now compute all first sets */
654 struct symbol
*s1
, *s2
;
656 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
658 for(i
=0; i
<rp
->nrhs
; i
++){
660 if( s2
->type
==TERMINAL
){
661 progress
+= SetAdd(s1
->firstset
,s2
->index
);
664 if( s1
->lambda
==Bo_FALSE
) break;
666 progress
+= SetUnion(s1
->firstset
,s2
->firstset
);
667 if( s2
->lambda
==Bo_FALSE
) break;
675 /* Compute all LR(0) states for the grammar. Links
676 ** are added to between some states so that the LR(1) follow sets
677 ** can be computed later.
679 PRIVATE
struct state
*getstate(/* struct lemon * */); /* forward reference */
680 void FindStates(lemp
)
688 /* Find the start symbol */
690 sp
= Symbol_find(lemp
->start
);
692 ErrorMsg(lemp
->filename
,0,
693 "The specified start symbol \"%s\" is not \
694 in a nonterminal of the grammar. \"%s\" will be used as the start \
695 symbol instead.",lemp
->start
,lemp
->rule
->lhs
->name
);
697 sp
= lemp
->rule
->lhs
;
700 sp
= lemp
->rule
->lhs
;
703 /* Make sure the start symbol doesn't occur on the right-hand side of
704 ** any rule. Report an error if it does. (YACC would generate a new
705 ** start symbol in this case.) */
706 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
708 for(i
=0; i
<rp
->nrhs
; i
++){
709 if( rp
->rhs
[i
]==sp
){
710 ErrorMsg(lemp
->filename
,0,
711 "The start symbol \"%s\" occurs on the \
712 right-hand side of a rule. This will result in a parser which \
713 does not work properly.",sp
->name
);
719 /* The basis configuration set for the first state
720 ** is all rules which have the start symbol as their
722 for(rp
=sp
->rule
; rp
; rp
=rp
->nextlhs
){
723 struct config
*newcfp
;
724 newcfp
= Configlist_addbasis(rp
,0);
725 SetAdd(newcfp
->fws
,0);
728 /* Compute the first state. All other states will be
729 ** computed automatically during the computation of the first one.
730 ** The returned pointer to the first state is not used. */
731 (void)getstate(lemp
);
735 /* Return a pointer to a state which is described by the configuration
736 ** list which has been built from calls to Configlist_add.
738 PRIVATE
void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */
739 PRIVATE
struct state
*getstate(lemp
)
742 struct config
*cfp
, *bp
;
745 /* Extract the sorted basis of the new state. The basis was constructed
746 ** by prior calls to "Configlist_addbasis()". */
747 Configlist_sortbasis();
748 bp
= Configlist_basis();
750 /* Get a state with the same basis */
751 stp
= State_find(bp
);
753 /* A state with the same basis already exists! Copy all the follow-set
754 ** propagation links from the state under construction into the
755 ** preexisting state, then return a pointer to the preexisting state */
756 struct config
*x
, *y
;
757 for(x
=bp
, y
=stp
->bp
; x
&& y
; x
=x
->bp
, y
=y
->bp
){
758 Plink_copy(&y
->bplp
,x
->bplp
);
759 Plink_delete(x
->fplp
);
760 x
->fplp
= x
->bplp
= 0;
762 cfp
= Configlist_return();
765 /* This really is a new state. Construct all the details */
766 Configlist_closure(lemp
); /* Compute the configuration closure */
767 Configlist_sort(); /* Sort the configuration closure */
768 cfp
= Configlist_return(); /* Get a pointer to the config list */
769 stp
= State_new(); /* A new state structure */
771 stp
->bp
= bp
; /* Remember the configuration basis */
772 stp
->cfp
= cfp
; /* Remember the configuration closure */
773 stp
->index
= lemp
->nstate
++; /* Every state gets a sequence number */
774 stp
->ap
= 0; /* No actions, yet. */
775 State_insert(stp
,stp
->bp
); /* Add to the state table */
776 buildshifts(lemp
,stp
); /* Recursively compute successor states */
781 /* Construct all successor states to the given state. A "successor"
782 ** state is any state which can be reached by a shift action.
784 PRIVATE
void buildshifts(lemp
,stp
)
786 struct state
*stp
; /* The state from which successors are computed */
788 struct config
*cfp
; /* For looping thru the config closure of "stp" */
789 struct config
*bcfp
; /* For the inner loop on config closure of "stp" */
790 struct config
*new; /* */
791 struct symbol
*sp
; /* Symbol following the dot in configuration "cfp" */
792 struct symbol
*bsp
; /* Symbol following the dot in configuration "bcfp" */
793 struct state
*newstp
; /* A pointer to a successor state */
795 /* Each configuration becomes complete after it contibutes to a successor
796 ** state. Initially, all configurations are incomplete */
797 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
) cfp
->status
= INCOMPLETE
;
799 /* Loop through all configurations of the state "stp" */
800 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
801 if( cfp
->status
==COMPLETE
) continue; /* Already used by inner loop */
802 if( cfp
->dot
>=cfp
->rp
->nrhs
) continue; /* Can't shift this config */
803 Configlist_reset(); /* Reset the new config set */
804 sp
= cfp
->rp
->rhs
[cfp
->dot
]; /* Symbol after the dot */
806 /* For every configuration in the state "stp" which has the symbol "sp"
807 ** following its dot, add the same configuration to the basis set under
808 ** construction but with the dot shifted one symbol to the right. */
809 for(bcfp
=cfp
; bcfp
; bcfp
=bcfp
->next
){
810 if( bcfp
->status
==COMPLETE
) continue; /* Already used */
811 if( bcfp
->dot
>=bcfp
->rp
->nrhs
) continue; /* Can't shift this one */
812 bsp
= bcfp
->rp
->rhs
[bcfp
->dot
]; /* Get symbol after dot */
813 if( bsp
!=sp
) continue; /* Must be same as for "cfp" */
814 bcfp
->status
= COMPLETE
; /* Mark this config as used */
815 new = Configlist_addbasis(bcfp
->rp
,bcfp
->dot
+1);
816 Plink_add(&new->bplp
,bcfp
);
819 /* Get a pointer to the state described by the basis configuration set
820 ** constructed in the preceding loop */
821 newstp
= getstate(lemp
);
823 /* The state "newstp" is reached from the state "stp" by a shift action
824 ** on the symbol "sp" */
825 Action_add(&stp
->ap
,SHIFT
,sp
,newstp
);
830 ** Construct the propagation links
836 struct config
*cfp
, *other
;
840 /* Housekeeping detail:
841 ** Add to every propagate link a pointer back to the state to
842 ** which the link is attached. */
843 for(i
=0; i
<lemp
->nstate
; i
++){
844 stp
= lemp
->sorted
[i
];
845 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
850 /* Convert all backlinks into forward links. Only the forward
851 ** links are used in the follow-set computation. */
852 for(i
=0; i
<lemp
->nstate
; i
++){
853 stp
= lemp
->sorted
[i
];
854 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
855 for(plp
=cfp
->bplp
; plp
; plp
=plp
->next
){
857 Plink_add(&other
->fplp
,cfp
);
863 /* Compute all followsets.
865 ** A followset is the set of all symbols which can come immediately
866 ** after a configuration.
868 void FindFollowSets(lemp
)
878 for(i
=0; i
<lemp
->nstate
; i
++){
879 stp
= lemp
->sorted
[i
];
880 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
881 cfp
->status
= INCOMPLETE
;
887 for(i
=0; i
<lemp
->nstate
; i
++){
888 stp
= lemp
->sorted
[i
];
889 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
890 if( cfp
->status
==COMPLETE
) continue;
891 for(plp
=cfp
->fplp
; plp
; plp
=plp
->next
){
892 change
= SetUnion(plp
->cfp
->fws
,cfp
->fws
);
894 plp
->cfp
->status
= INCOMPLETE
;
898 cfp
->status
= COMPLETE
;
904 static int resolve_conflict();
906 /* Compute the reduce actions, and resolve conflicts.
908 void FindActions(lemp
)
916 /* Add all of the reduce actions
917 ** A reduce action is added for each element of the followset of
918 ** a configuration which has its dot at the extreme right.
920 for(i
=0; i
<lemp
->nstate
; i
++){ /* Loop over all states */
922 stp
= lemp
->sorted
[i
];
923 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){ /* Loop over all configurations */
924 if( cfp
->rp
->nrhs
==cfp
->dot
){ /* Is dot at extreme right? */
925 for(j
=0; j
<lemp
->nterminal
; j
++){
926 if( SetFind(cfp
->fws
,j
) ){
927 /* Add a reduce action to the state "stp" which will reduce by the
928 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
929 Action_add(&stp
->ap
,REDUCE
,lemp
->symbols
[j
],cfp
->rp
);
936 /* Add the accepting token */
938 sp
= Symbol_find(lemp
->start
);
939 if( sp
==0 ) sp
= lemp
->rule
->lhs
;
941 sp
= lemp
->rule
->lhs
;
943 /* Add to the first state (which is always the starting state of the
944 ** finite state machine) an action to ACCEPT if the lookahead is the
945 ** start nonterminal. */
946 if (lemp
->nstate
) { /*(should always be true)*/
948 stp
= lemp
->sorted
[0];
949 Action_add(&stp
->ap
,ACCEPT
,sp
,0);
952 /* Resolve conflicts */
953 for(i
=0; i
<lemp
->nstate
; i
++){
954 struct action
*ap
, *nap
;
956 stp
= lemp
->sorted
[i
];
958 stp
->ap
= Action_sort(stp
->ap
);
959 for(ap
=stp
->ap
; ap
&& ap
->next
; ap
=ap
->next
){
960 for(nap
=ap
->next
; nap
&& nap
->sp
==ap
->sp
; nap
=nap
->next
){
961 /* The two actions "ap" and "nap" have the same lookahead.
962 ** Figure out which one should be used */
963 lemp
->nconflict
+= resolve_conflict(ap
,nap
,lemp
->errsym
);
968 /* Report an error for each rule that can never be reduced. */
969 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->canReduce
= Bo_FALSE
;
970 for(i
=0; i
<lemp
->nstate
; i
++){
972 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
973 if( ap
->type
==REDUCE
) ap
->x
.rp
->canReduce
= Bo_TRUE
;
976 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
977 if( rp
->canReduce
) continue;
978 ErrorMsg(lemp
->filename
,rp
->ruleline
,"This rule can not be reduced.\n");
983 /* Resolve a conflict between the two given actions. If the
984 ** conflict can't be resolve, return non-zero.
987 ** To resolve a conflict, first look to see if either action
988 ** is on an error rule. In that case, take the action which
989 ** is not associated with the error rule. If neither or both
990 ** actions are associated with an error rule, then try to
991 ** use precedence to resolve the conflict.
993 ** If either action is a SHIFT, then it must be apx. This
994 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
996 static int resolve_conflict(apx
,apy
,errsym
)
999 struct symbol
*errsym
; /* The error symbol (if defined. NULL otherwise) */
1001 struct symbol
*spx
, *spy
;
1004 assert( apx
->sp
==apy
->sp
); /* Otherwise there would be no conflict */
1005 if( apx
->type
==SHIFT
&& apy
->type
==REDUCE
){
1007 spy
= apy
->x
.rp
->precsym
;
1008 if( spy
==0 || spx
->prec
<0 || spy
->prec
<0 ){
1009 /* Not enough precedence information. */
1010 apy
->type
= CONFLICT
;
1012 }else if( spx
->prec
>spy
->prec
){ /* Lower precedence wins */
1013 apy
->type
= RD_RESOLVED
;
1014 }else if( spx
->prec
<spy
->prec
){
1015 apx
->type
= SH_RESOLVED
;
1016 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==RIGHT
){ /* Use operator */
1017 apy
->type
= RD_RESOLVED
; /* associativity */
1018 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==LEFT
){ /* to break tie */
1019 apx
->type
= SH_RESOLVED
;
1021 assert( spx
->prec
==spy
->prec
&& spx
->assoc
==NONE
);
1022 apy
->type
= CONFLICT
;
1025 }else if( apx
->type
==REDUCE
&& apy
->type
==REDUCE
){
1026 spx
= apx
->x
.rp
->precsym
;
1027 spy
= apy
->x
.rp
->precsym
;
1028 if( spx
==0 || spy
==0 || spx
->prec
<0 ||
1029 spy
->prec
<0 || spx
->prec
==spy
->prec
){
1030 apy
->type
= CONFLICT
;
1032 }else if( spx
->prec
>spy
->prec
){
1033 apy
->type
= RD_RESOLVED
;
1034 }else if( spx
->prec
<spy
->prec
){
1035 apx
->type
= RD_RESOLVED
;
1039 apx
->type
==SH_RESOLVED
||
1040 apx
->type
==RD_RESOLVED
||
1041 apx
->type
==CONFLICT
||
1042 apy
->type
==SH_RESOLVED
||
1043 apy
->type
==RD_RESOLVED
||
1046 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1047 ** REDUCEs on the list. If we reach this point it must be because
1048 ** the parser conflict had already been resolved. */
1052 /********************* From the file "configlist.c" *************************/
1054 ** Routines to processing a configuration list and building a state
1055 ** in the LEMON parser generator.
1058 static struct config
*freelist
= 0; /* List of free configurations */
1059 static struct config
*current
= 0; /* Top of list of configurations */
1060 static struct config
**currentend
= 0; /* Last on list of configs */
1061 static struct config
*basis
= 0; /* Top of list of basis configs */
1062 static struct config
**basisend
= 0; /* End of list of basis configs */
1064 /* Return a pointer to a new configuration */
1065 PRIVATE
struct config
*newconfig(){
1070 freelist
= (struct config
*)malloc( sizeof(struct config
)*amt
);
1072 fprintf(stderr
,"Unable to allocate memory for a new configuration.");
1075 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
1076 freelist
[amt
-1].next
= 0;
1079 freelist
= freelist
->next
;
1083 /* The configuration "old" is no longer used */
1084 PRIVATE
void deleteconfig(old
)
1087 old
->next
= freelist
;
1091 /* Initialized the configuration list builder */
1092 void Configlist_init(){
1094 currentend
= ¤t
;
1101 /* Initialized the configuration list builder */
1102 void Configlist_reset(){
1104 currentend
= ¤t
;
1107 Configtable_clear(0);
1111 /* Add another configuration to the configuration list */
1112 struct config
*Configlist_add(rp
,dot
)
1113 struct rule
*rp
; /* The rule */
1114 int dot
; /* Index into the RHS of the rule where the dot goes */
1116 struct config
*cfp
, model
;
1118 assert( currentend
!=0 );
1121 cfp
= Configtable_find(&model
);
1126 cfp
->fws
= SetNew();
1128 cfp
->fplp
= cfp
->bplp
= 0;
1132 currentend
= &cfp
->next
;
1133 Configtable_insert(cfp
);
1138 /* Add a basis configuration to the configuration list */
1139 struct config
*Configlist_addbasis(rp
,dot
)
1143 struct config
*cfp
, model
;
1145 assert( basisend
!=0 );
1146 assert( currentend
!=0 );
1149 cfp
= Configtable_find(&model
);
1154 cfp
->fws
= SetNew();
1156 cfp
->fplp
= cfp
->bplp
= 0;
1160 currentend
= &cfp
->next
;
1162 basisend
= &cfp
->bp
;
1163 Configtable_insert(cfp
);
1168 /* Compute the closure of the configuration list */
1169 void Configlist_closure(lemp
)
1172 struct config
*cfp
, *newcfp
;
1173 struct rule
*rp
, *newrp
;
1174 struct symbol
*sp
, *xsp
;
1177 assert( currentend
!=0 );
1178 for(cfp
=current
; cfp
; cfp
=cfp
->next
){
1181 if( dot
>=rp
->nrhs
) continue;
1183 if( sp
->type
==NONTERMINAL
){
1184 if( sp
->rule
==0 && sp
!=lemp
->errsym
){
1185 ErrorMsg(lemp
->filename
,rp
->line
,"Nonterminal \"%s\" has no rules.",
1189 for(newrp
=sp
->rule
; newrp
; newrp
=newrp
->nextlhs
){
1190 newcfp
= Configlist_add(newrp
,0);
1191 for(i
=dot
+1; i
<rp
->nrhs
; i
++){
1193 if( xsp
->type
==TERMINAL
){
1194 SetAdd(newcfp
->fws
,xsp
->index
);
1197 SetUnion(newcfp
->fws
,xsp
->firstset
);
1198 if( xsp
->lambda
==Bo_FALSE
) break;
1201 if( i
==rp
->nrhs
) Plink_add(&cfp
->fplp
,newcfp
);
1208 /* Sort the configuration list */
1209 void Configlist_sort(){
1210 current
= (struct config
*)msort(current
,(void **)&(current
->next
),Configcmp
);
1215 /* Sort the basis configuration list */
1216 void Configlist_sortbasis(){
1217 basis
= (struct config
*)msort(current
,(void **)&(current
->bp
),Configcmp
);
1222 /* Return a pointer to the head of the configuration list and
1223 ** reset the list */
1224 struct config
*Configlist_return(){
1232 /* Return a pointer to the head of the configuration list and
1233 ** reset the list */
1234 struct config
*Configlist_basis(){
1242 /* Free all elements of the given configuration list */
1243 void Configlist_eat(cfp
)
1246 struct config
*nextcfp
;
1247 for(; cfp
; cfp
=nextcfp
){
1248 nextcfp
= cfp
->next
;
1249 assert( cfp
->fplp
==0 );
1250 assert( cfp
->bplp
==0 );
1251 if( cfp
->fws
) SetFree(cfp
->fws
);
1256 /***************** From the file "error.c" *********************************/
1258 ** Code for printing error message.
1261 /* Find a good place to break "msg" so that its length is at least "min"
1262 ** but no more than "max". Make the point as close to max as possible.
1264 static int findbreak(msg
,min
,max
)
1271 for(i
=spot
=min
; i
<=max
; i
++){
1273 if( c
=='\t' ) msg
[i
] = ' ';
1274 if( c
=='\n' ){ msg
[i
] = ' '; spot
= i
; break; }
1275 if( c
==0 ){ spot
= i
; break; }
1276 if( c
=='-' && i
<max
-1 ) spot
= i
+1;
1277 if( c
==' ' ) spot
= i
;
1283 ** The error message is split across multiple lines if necessary. The
1284 ** splits occur at a space, if there is a space available near the end
1287 #define ERRMSGSIZE 10000 /* Hope this is big enough. No way to error check */
1288 #define LINEWIDTH 79 /* Max width of any output line */
1289 #define PREFIXLIMIT 30 /* Max width of the prefix on each line */
1290 void ErrorMsg(const char *filename
, int lineno
, const char *format
, ...){
1291 char errmsg
[ERRMSGSIZE
];
1292 char prefix
[PREFIXLIMIT
+10];
1297 int end
, restart
, base
;
1299 va_start(ap
, format
);
1300 /* Prepare a prefix to be prepended to every output line */
1302 sprintf(prefix
,"%.*s:%d: ",PREFIXLIMIT
-10,filename
,lineno
);
1304 sprintf(prefix
,"%.*s: ",PREFIXLIMIT
-10,filename
);
1306 prefixsize
= strlen(prefix
);
1307 availablewidth
= LINEWIDTH
- prefixsize
;
1309 /* Generate the error message */
1310 vsprintf(errmsg
,format
,ap
);
1312 errmsgsize
= strlen(errmsg
);
1313 /* Remove trailing '\n's from the error message. */
1314 while( errmsgsize
>0 && errmsg
[errmsgsize
-1]=='\n' ){
1315 errmsg
[--errmsgsize
] = 0;
1318 /* Print the error message */
1320 while( errmsg
[base
]!=0 ){
1321 end
= restart
= findbreak(&errmsg
[base
],0,availablewidth
);
1323 while( errmsg
[restart
]==' ' ) restart
++;
1324 fprintf(stdout
,"%s%.*s\n",prefix
,end
,&errmsg
[base
]);
1328 /**************** From the file "main.c" ************************************/
1330 ** Main program file for the LEMON parser generator.
1333 /* Report an out-of-memory condition and abort. This function
1334 ** is used mostly by the "MemoryCheck" macro in struct.h
1336 void memory_error() {
1337 fprintf(stderr
,"Out of memory. Aborting...\n");
1341 static const char* out_dir
= ".";
1342 /* The main program. Parse the command line and do it... */
1347 static int version
= 0;
1348 static int rpflag
= 0;
1349 static int basisflag
= 0;
1350 static int compress
= 0;
1351 static int quiet
= 0;
1352 static int statistics
= 0;
1353 static int mhflag
= 0;
1354 static struct s_options options
[] = {
1355 {OPT_FLAG
, "b", (char*)&basisflag
, "Print only the basis in report."},
1356 {OPT_FLAG
, "c", (char*)&compress
, "Don't compress the action table."},
1357 {OPT_FLAG
, "g", (char*)&rpflag
, "Print grammar without actions."},
1358 {OPT_FLAG
, "m", (char*)&mhflag
, "Output a makeheaders compatible file"},
1359 {OPT_FLAG
, "q", (char*)&quiet
, "(Quiet) Don't print the report file."},
1360 {OPT_FLAG
, "s", (char*)&statistics
, "Print parser stats to standard output."},
1361 {OPT_FLAG
, "x", (char*)&version
, "Print the version number."},
1362 {OPT_STR
, "o", (char*)&out_dir
, "Customize output directory."},
1367 char *def_tmpl_name
= "lempar.c";
1370 OptInit(argv
,options
,stderr
);
1372 printf("Lemon version 1.0\n");
1375 if( OptNArgs() < 1 ){
1376 fprintf(stderr
,"Exactly one filename argument is required.\n");
1381 /* Initialize the machine */
1385 lem
.argv0
= argv
[0];
1386 lem
.filename
= OptArg(0);
1387 lem
.tmplname
= (OptNArgs() == 2) ? OptArg(1) : def_tmpl_name
;
1388 lem
.basisflag
= basisflag
;
1389 lem
.has_fallback
= 0;
1391 lem
.name
= lem
.include
= lem
.arg
= lem
.tokentype
= lem
.start
= 0;
1394 lem
.error
= lem
.overflow
= lem
.failure
= lem
.accept
= lem
.tokendest
=
1395 lem
.tokenprefix
= lem
.outname
= lem
.extracode
= 0;
1399 lem
.errsym
= Symbol_new("error");
1401 /* Parse the input file */
1403 if( lem
.errorcnt
) exit(lem
.errorcnt
);
1405 fprintf(stderr
,"Empty grammar.\n");
1409 /* Count and index the symbols of the grammar */
1410 Symbol_new("{default}");
1411 lem
.nsymbol
= Symbol_count();
1412 lem
.symbols
= Symbol_arrayof();
1413 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1414 qsort(lem
.symbols
,lem
.nsymbol
,sizeof(struct symbol
*),
1415 (int(*)())Symbolcmpp
);
1416 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1417 for(i
=1; i
<lem
.nsymbol
&& isupper(lem
.symbols
[i
]->name
[0]); i
++);
1418 lem
.nsymbol
--; /*(do not count "{default}")*/
1421 /* Generate a reprint of the grammar, if requested on the command line */
1425 /* Initialize the size for all follow and first sets */
1426 SetSize(lem
.nterminal
);
1428 /* Find the precedence for every production rule (that has one) */
1429 FindRulePrecedences(&lem
);
1431 /* Compute the lambda-nonterminals and the first-sets for every
1433 FindFirstSets(&lem
);
1435 /* Compute all LR(0) states. Also record follow-set propagation
1436 ** links so that the follow-set can be computed later */
1439 lem
.nstate
= State_count();
1440 lem
.sorted
= State_arrayof();
1442 /* Tie up loose ends on the propagation links */
1445 /* Compute the follow set of every reducible configuration */
1446 FindFollowSets(&lem
);
1448 /* Compute the action tables */
1451 /* Compress the action tables */
1452 if( compress
==0 ) CompressTables(&lem
);
1454 /* Generate a report of the parser generated. (the "y.output" file) */
1455 if( !quiet
) ReportOutput(&lem
);
1457 /* Generate the source code for the parser */
1458 ReportTable(&lem
, mhflag
);
1460 /* Produce a header file for use by the scanner. (This step is
1461 ** omitted if the "-m" option is used because makeheaders will
1462 ** generate the file for us.) */
1463 if( !mhflag
) ReportHeader(&lem
);
1466 printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
1467 lem
.nterminal
, lem
.nsymbol
- lem
.nterminal
, lem
.nrule
);
1468 printf(" %d states, %d parser table entries, %d conflicts\n",
1469 lem
.nstate
, lem
.tablesize
, lem
.nconflict
);
1471 if( lem
.nconflict
){
1472 fprintf(stderr
,"%d parsing conflicts.\n",lem
.nconflict
);
1474 exit(lem
.errorcnt
+ lem
.nconflict
);
1476 /******************** From the file "msort.c" *******************************/
1478 ** A generic merge-sort program.
1481 ** Let "ptr" be a pointer to some structure which is at the head of
1482 ** a null-terminated list. Then to sort the list call:
1484 ** ptr = msort(ptr,&(ptr->next),cmpfnc);
1486 ** In the above, "cmpfnc" is a pointer to a function which compares
1487 ** two instances of the structure and returns an integer, as in
1488 ** strcmp. The second argument is a pointer to the pointer to the
1489 ** second element of the linked list. This address is used to compute
1490 ** the offset to the "next" field within the structure. The offset to
1491 ** the "next" field must be constant for all structures in the list.
1493 ** The function returns a new pointer which is the head of the list
1501 ** Return a pointer to the next structure in the linked list.
1503 #define NEXT(A) (*(char**)(((unsigned long)A)+offset))
1507 ** a: A sorted, null-terminated linked list. (May be null).
1508 ** b: A sorted, null-terminated linked list. (May be null).
1509 ** cmp: A pointer to the comparison function.
1510 ** offset: Offset in the structure to the "next" field.
1513 ** A pointer to the head of a sorted list containing the elements
1517 ** The "next" pointers for elements in the lists a and b are
1520 static char *merge(a
,b
,cmp
,offset
)
1533 if( (*cmp
)(a
,b
)<0 ){
1542 if( (*cmp
)(a
,b
)<0 ){
1552 if( a
) NEXT(ptr
) = a
;
1560 ** list: Pointer to a singly-linked list of structures.
1561 ** next: Pointer to pointer to the second element of the list.
1562 ** cmp: A comparison function.
1565 ** A pointer to the head of a sorted list containing the elements
1566 ** orginally in list.
1569 ** The "next" pointers for elements in list are changed.
1572 void *msort(void *list
, void **next
, int(*cmp
)(void *, void *))
1574 unsigned long offset
;
1576 char *set
[LISTSIZE
];
1578 offset
= (unsigned long)next
- (unsigned long)list
;
1579 for(i
=0; i
<LISTSIZE
; i
++) set
[i
] = 0;
1584 for(i
=0; i
<LISTSIZE
-1 && set
[i
]!=0; i
++){
1585 ep
= merge(ep
,set
[i
],cmp
,offset
);
1591 for(i
=0; i
<LISTSIZE
; i
++) if( set
[i
] ) ep
= merge(ep
,set
[i
],cmp
,offset
);
1594 /************************ From the file "option.c" **************************/
1596 static struct s_options
*op
;
1597 static FILE *errstream
;
1599 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1602 ** Print the command line with a carrot pointing to the k-th character
1603 ** of the n-th field.
1605 static void errline(n
,k
,err
)
1612 fprintf(err
,"%s",argv
[0]);
1613 spcnt
+= strlen(argv
[0]) + 1;
1615 for(i
=1; i
<n
&& argv
[i
]; i
++){
1616 fprintf(err
," %s",argv
[i
]);
1617 spcnt
+= strlen(argv
[i
]) + 1;
1620 for(; argv
[i
]; i
++) fprintf(err
," %s",argv
[i
]);
1622 fprintf(err
,"\n%*s^-- here\n",spcnt
,"");
1624 fprintf(err
,"\n%*shere --^\n",spcnt
-7,"");
1629 ** Return the index of the N-th non-switch argument. Return -1
1630 ** if N is out of range.
1632 static int argindex(n
)
1637 if( argv
!=0 && *argv
!=0 ){
1638 for(i
=1; argv
[i
]; i
++){
1639 if( dashdash
|| !ISOPT(argv
[i
]) ){
1640 if( n
==0 ) return i
;
1643 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
1649 static char emsg
[] = "Command line syntax error: ";
1652 ** Process a flag command line argument.
1654 static int handleflags(i
,err
)
1661 for(j
=0; op
[j
].label
; j
++){
1662 if( strcmp(&argv
[i
][1],op
[j
].label
)==0 ) break;
1664 v
= argv
[i
][0]=='-' ? 1 : 0;
1665 if( op
[j
].label
==0 ){
1667 fprintf(err
,"%sundefined option.\n",emsg
);
1671 }else if( op
[j
].type
==OPT_FLAG
){
1672 *((int*)op
[j
].arg
) = v
;
1673 }else if( op
[j
].type
==OPT_FFLAG
){
1674 (*(void(*)())(intptr_t)(op
[j
].arg
))(v
);
1677 fprintf(err
,"%smissing argument on switch.\n",emsg
);
1686 ** Process a command line switch which has an argument.
1688 static int handleswitch(i
,err
)
1698 cp
= strchr(argv
[i
],'=');
1700 for(j
=0; op
[j
].label
; j
++){
1701 if( strcmp(argv
[i
],op
[j
].label
)==0 ) break;
1704 if( op
[j
].label
==0 ){
1706 fprintf(err
,"%sundefined option.\n",emsg
);
1712 switch( op
[j
].type
){
1716 fprintf(err
,"%soption requires an argument.\n",emsg
);
1723 dv
= strtod(cp
,&end
);
1726 fprintf(err
,"%sillegal character in floating-point argument.\n",emsg
);
1727 errline(i
,((unsigned long)end
)-(unsigned long)argv
[i
],err
);
1734 lv
= strtol(cp
,&end
,0);
1737 fprintf(err
,"%sillegal character in integer argument.\n",emsg
);
1738 errline(i
,((unsigned long)end
)-(unsigned long)argv
[i
],err
);
1748 switch( op
[j
].type
){
1753 *(double*)(op
[j
].arg
) = dv
;
1756 (*(void(*)())(intptr_t)(op
[j
].arg
))(dv
);
1759 *(int*)(op
[j
].arg
) = lv
;
1762 (*(void(*)())(intptr_t)(op
[j
].arg
))((int)lv
);
1765 *(char**)(op
[j
].arg
) = sv
;
1768 (*(void(*)())(intptr_t)(op
[j
].arg
))(sv
);
1775 int OptInit(a
,o
,err
)
1777 struct s_options
*o
;
1784 if( argv
&& *argv
&& op
){
1786 for(i
=1; argv
[i
]; i
++){
1787 if( argv
[i
][0]=='+' || argv
[i
][0]=='-' ){
1788 errcnt
+= handleflags(i
,err
);
1789 }else if( strchr(argv
[i
],'=') ){
1790 errcnt
+= handleswitch(i
,err
);
1795 fprintf(err
,"Valid command line options for \"%s\" are:\n",*a
);
1806 if( argv
!=0 && argv
[0]!=0 ){
1807 for(i
=1; argv
[i
]; i
++){
1808 if( dashdash
|| !ISOPT(argv
[i
]) ) cnt
++;
1809 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
1820 return i
>=0 ? argv
[i
] : 0;
1828 if( i
>=0 ) errline(i
,0,errstream
);
1835 for(i
=0; op
[i
].label
; i
++){
1836 len
= strlen(op
[i
].label
) + 1;
1837 switch( op
[i
].type
){
1843 len
+= 9; /* length of "<integer>" */
1847 len
+= 6; /* length of "<real>" */
1851 len
+= 8; /* length of "<string>" */
1854 if( len
>max
) max
= len
;
1856 for(i
=0; op
[i
].label
; i
++){
1857 switch( op
[i
].type
){
1860 fprintf(errstream
," -%-*s %s\n",max
,op
[i
].label
,op
[i
].message
);
1864 fprintf(errstream
," %s=<integer>%*s %s\n",op
[i
].label
,
1865 (int)(max
-strlen(op
[i
].label
)-9),"",op
[i
].message
);
1869 fprintf(errstream
," %s=<real>%*s %s\n",op
[i
].label
,
1870 (int)(max
-strlen(op
[i
].label
)-6),"",op
[i
].message
);
1874 fprintf(errstream
," %s=<string>%*s %s\n",op
[i
].label
,
1875 (int)(max
-strlen(op
[i
].label
)-8),"",op
[i
].message
);
1880 /*********************** From the file "parse.c" ****************************/
1882 ** Input file parser for the LEMON parser generator.
1885 /* The state of the parser */
1887 char *filename
; /* Name of the input file */
1888 int tokenlineno
; /* Linenumber at which current token starts */
1889 int errorcnt
; /* Number of errors so far */
1890 char *tokenstart
; /* Text of current token */
1891 struct lemon
*gp
; /* Global state vector */
1894 WAITING_FOR_DECL_OR_RULE
,
1895 WAITING_FOR_DECL_KEYWORD
,
1896 WAITING_FOR_DECL_ARG
,
1897 WAITING_FOR_PRECEDENCE_SYMBOL
,
1907 RESYNC_AFTER_RULE_ERROR
,
1908 RESYNC_AFTER_DECL_ERROR
,
1909 WAITING_FOR_DESTRUCTOR_SYMBOL
,
1910 WAITING_FOR_DATATYPE_SYMBOL
,
1911 WAITING_FOR_FALLBACK_ID
1912 } state
; /* The state of the parser */
1913 struct symbol
*fallback
; /* The fallback token */
1914 struct symbol
*lhs
; /* Left-hand side of current rule */
1915 char *lhsalias
; /* Alias for the LHS */
1916 int nrhs
; /* Number of right-hand side symbols seen */
1917 struct symbol
*rhs
[MAXRHS
]; /* RHS symbols */
1918 char *alias
[MAXRHS
]; /* Aliases for each RHS symbol (or NULL) */
1919 struct rule
*prevrule
; /* Previous rule parsed */
1920 char *declkeyword
; /* Keyword of a declaration */
1921 char **declargslot
; /* Where the declaration argument should be put */
1922 int *decllnslot
; /* Where the declaration linenumber is put */
1923 enum e_assoc declassoc
; /* Assign this association to decl arguments */
1924 int preccounter
; /* Assign this precedence to decl arguments */
1925 struct rule
*firstrule
; /* Pointer to first rule in the grammar */
1926 struct rule
*lastrule
; /* Pointer to the most recently parsed rule */
1929 /* Parse a single token */
1930 static void parseonetoken(psp
)
1934 x
= Strsafe(psp
->tokenstart
); /* Save the token permanently */
1936 printf("%s:%d: Token=[%s] state=%d\n",psp
->filename
,psp
->tokenlineno
,
1939 switch( psp
->state
){
1942 psp
->preccounter
= 0;
1943 psp
->firstrule
= psp
->lastrule
= 0;
1946 case WAITING_FOR_DECL_OR_RULE
:
1948 psp
->state
= WAITING_FOR_DECL_KEYWORD
;
1949 }else if( islower(x
[0]) ){
1950 psp
->lhs
= Symbol_new(x
);
1953 psp
->state
= WAITING_FOR_ARROW
;
1954 }else if( x
[0]=='{' ){
1955 if( psp
->prevrule
==0 ){
1956 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
1957 "There is not prior rule opon which to attach the code \
1958 fragment which begins on this line.");
1960 }else if( psp
->prevrule
->code
!=0 ){
1961 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
1962 "Code fragment beginning on this line is not the first \
1963 to follow the previous rule.");
1966 psp
->prevrule
->line
= psp
->tokenlineno
;
1967 psp
->prevrule
->code
= &x
[1];
1969 }else if( x
[0]=='[' ){
1970 psp
->state
= PRECEDENCE_MARK_1
;
1972 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
1973 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
1978 case PRECEDENCE_MARK_1
:
1979 if( !isupper(x
[0]) ){
1980 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
1981 "The precedence symbol must be a terminal.");
1983 }else if( psp
->prevrule
==0 ){
1984 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
1985 "There is no prior rule to assign precedence \"[%s]\".",x
);
1987 }else if( psp
->prevrule
->precsym
!=0 ){
1988 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
1989 "Precedence mark on this line is not the first \
1990 to follow the previous rule.");
1993 psp
->prevrule
->precsym
= Symbol_new(x
);
1995 psp
->state
= PRECEDENCE_MARK_2
;
1997 case PRECEDENCE_MARK_2
:
1999 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2000 "Missing \"]\" on precedence mark.");
2003 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2005 case WAITING_FOR_ARROW
:
2006 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2007 psp
->state
= IN_RHS
;
2008 }else if( x
[0]=='(' ){
2009 psp
->state
= LHS_ALIAS_1
;
2011 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2012 "Expected to see a \":\" following the LHS symbol \"%s\".",
2015 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2019 if( isalpha(x
[0]) ){
2021 psp
->state
= LHS_ALIAS_2
;
2023 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2024 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2027 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2032 psp
->state
= LHS_ALIAS_3
;
2034 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2035 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2037 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2041 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2042 psp
->state
= IN_RHS
;
2044 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2045 "Missing \"->\" following: \"%s(%s)\".",
2046 psp
->lhs
->name
,psp
->lhsalias
);
2048 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2054 rp
= (struct rule
*)malloc( sizeof(struct rule
) +
2055 sizeof(struct symbol
*)*psp
->nrhs
+ sizeof(char*)*psp
->nrhs
);
2057 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2058 "Can't allocate enough memory for this rule.");
2063 rp
->ruleline
= psp
->tokenlineno
;
2064 rp
->rhs
= (struct symbol
**)&rp
[1];
2065 rp
->rhsalias
= (char**)&(rp
->rhs
[psp
->nrhs
]);
2066 for(i
=0; i
<psp
->nrhs
; i
++){
2067 rp
->rhs
[i
] = psp
->rhs
[i
];
2068 rp
->rhsalias
[i
] = psp
->alias
[i
];
2071 rp
->lhsalias
= psp
->lhsalias
;
2072 rp
->nrhs
= psp
->nrhs
;
2075 rp
->index
= psp
->gp
->nrule
++;
2076 rp
->nextlhs
= rp
->lhs
->rule
;
2079 if( psp
->firstrule
==0 ){
2080 psp
->firstrule
= psp
->lastrule
= rp
;
2082 psp
->lastrule
->next
= rp
;
2087 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2088 }else if( isalpha(x
[0]) ){
2089 if( psp
->nrhs
>=MAXRHS
){
2090 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2091 "Too many symbol on RHS or rule beginning at \"%s\".",
2094 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2096 psp
->rhs
[psp
->nrhs
] = Symbol_new(x
);
2097 psp
->alias
[psp
->nrhs
] = 0;
2100 }else if( x
[0]=='(' && psp
->nrhs
>0 ){
2101 psp
->state
= RHS_ALIAS_1
;
2103 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2104 "Illegal character on RHS of rule: \"%s\".",x
);
2106 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2110 if( isalpha(x
[0]) ){
2111 psp
->alias
[psp
->nrhs
-1] = x
;
2112 psp
->state
= RHS_ALIAS_2
;
2114 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2115 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2116 x
,psp
->rhs
[psp
->nrhs
-1]->name
);
2118 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2123 psp
->state
= IN_RHS
;
2125 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2126 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2128 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2131 case WAITING_FOR_DECL_KEYWORD
:
2132 if( isalpha(x
[0]) ){
2133 psp
->declkeyword
= x
;
2134 psp
->declargslot
= 0;
2135 psp
->decllnslot
= 0;
2136 psp
->state
= WAITING_FOR_DECL_ARG
;
2137 if( strcmp(x
,"name")==0 ){
2138 psp
->declargslot
= &(psp
->gp
->name
);
2139 }else if( strcmp(x
,"include")==0 ){
2140 psp
->declargslot
= &(psp
->gp
->include
);
2141 psp
->decllnslot
= &psp
->gp
->includeln
;
2142 }else if( strcmp(x
,"code")==0 ){
2143 psp
->declargslot
= &(psp
->gp
->extracode
);
2144 psp
->decllnslot
= &psp
->gp
->extracodeln
;
2145 }else if( strcmp(x
,"token_destructor")==0 ){
2146 psp
->declargslot
= &psp
->gp
->tokendest
;
2147 psp
->decllnslot
= &psp
->gp
->tokendestln
;
2148 }else if( strcmp(x
,"default_destructor")==0 ){
2149 psp
->declargslot
= &psp
->gp
->vardest
;
2150 psp
->decllnslot
= &psp
->gp
->vardestln
;
2151 }else if( strcmp(x
,"token_prefix")==0 ){
2152 psp
->declargslot
= &psp
->gp
->tokenprefix
;
2153 }else if( strcmp(x
,"syntax_error")==0 ){
2154 psp
->declargslot
= &(psp
->gp
->error
);
2155 psp
->decllnslot
= &psp
->gp
->errorln
;
2156 }else if( strcmp(x
,"parse_accept")==0 ){
2157 psp
->declargslot
= &(psp
->gp
->accept
);
2158 psp
->decllnslot
= &psp
->gp
->acceptln
;
2159 }else if( strcmp(x
,"parse_failure")==0 ){
2160 psp
->declargslot
= &(psp
->gp
->failure
);
2161 psp
->decllnslot
= &psp
->gp
->failureln
;
2162 }else if( strcmp(x
,"stack_overflow")==0 ){
2163 psp
->declargslot
= &(psp
->gp
->overflow
);
2164 psp
->decllnslot
= &psp
->gp
->overflowln
;
2165 }else if( strcmp(x
,"extra_argument")==0 ){
2166 psp
->declargslot
= &(psp
->gp
->arg
);
2167 }else if( strcmp(x
,"token_type")==0 ){
2168 psp
->declargslot
= &(psp
->gp
->tokentype
);
2169 }else if( strcmp(x
,"default_type")==0 ){
2170 psp
->declargslot
= &(psp
->gp
->vartype
);
2171 }else if( strcmp(x
,"stack_size")==0 ){
2172 psp
->declargslot
= &(psp
->gp
->stacksize
);
2173 }else if( strcmp(x
,"start_symbol")==0 ){
2174 psp
->declargslot
= &(psp
->gp
->start
);
2175 }else if( strcmp(x
,"left")==0 ){
2177 psp
->declassoc
= LEFT
;
2178 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2179 }else if( strcmp(x
,"right")==0 ){
2181 psp
->declassoc
= RIGHT
;
2182 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2183 }else if( strcmp(x
,"nonassoc")==0 ){
2185 psp
->declassoc
= NONE
;
2186 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2187 }else if( strcmp(x
,"destructor")==0 ){
2188 psp
->state
= WAITING_FOR_DESTRUCTOR_SYMBOL
;
2189 }else if( strcmp(x
,"type")==0 ){
2190 psp
->state
= WAITING_FOR_DATATYPE_SYMBOL
;
2191 }else if( strcmp(x
,"fallback")==0 ){
2193 psp
->state
= WAITING_FOR_FALLBACK_ID
;
2195 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2196 "Unknown declaration keyword: \"%%%s\".",x
);
2198 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2201 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2202 "Illegal declaration keyword: \"%s\".",x
);
2204 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2207 case WAITING_FOR_DESTRUCTOR_SYMBOL
:
2208 if( !isalpha(x
[0]) ){
2209 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2210 "Symbol name missing after %destructor keyword");
2212 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2214 struct symbol
*sp
= Symbol_new(x
);
2215 psp
->declargslot
= &sp
->destructor
;
2216 psp
->decllnslot
= &sp
->destructorln
;
2217 psp
->state
= WAITING_FOR_DECL_ARG
;
2220 case WAITING_FOR_DATATYPE_SYMBOL
:
2221 if( !isalpha(x
[0]) ){
2222 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2223 "Symbol name missing after %destructor keyword");
2225 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2227 struct symbol
*sp
= Symbol_new(x
);
2228 psp
->declargslot
= &sp
->datatype
;
2229 psp
->decllnslot
= 0;
2230 psp
->state
= WAITING_FOR_DECL_ARG
;
2233 case WAITING_FOR_PRECEDENCE_SYMBOL
:
2235 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2236 }else if( isupper(x
[0]) ){
2240 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2241 "Symbol \"%s\" has already be given a precedence.",x
);
2244 sp
->prec
= psp
->preccounter
;
2245 sp
->assoc
= psp
->declassoc
;
2248 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2249 "Can't assign a precedence to \"%s\".",x
);
2253 case WAITING_FOR_DECL_ARG
:
2254 if( (x
[0]=='{' || x
[0]=='\"' || isalnum(x
[0])) ){
2255 if( *(psp
->declargslot
)!=0 ){
2256 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2257 "The argument \"%s\" to declaration \"%%%s\" is not the first.",
2258 x
[0]=='\"' ? &x
[1] : x
,psp
->declkeyword
);
2260 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2262 *(psp
->declargslot
) = (x
[0]=='\"' || x
[0]=='{') ? &x
[1] : x
;
2263 if( psp
->decllnslot
) *psp
->decllnslot
= psp
->tokenlineno
;
2264 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2267 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2268 "Illegal argument to %%%s: %s",psp
->declkeyword
,x
);
2270 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2273 case WAITING_FOR_FALLBACK_ID
:
2275 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2276 }else if( !isupper(x
[0]) ){
2277 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2278 "%%fallback argument \"%s\" should be a token", x
);
2281 struct symbol
*sp
= Symbol_new(x
);
2282 if( psp
->fallback
==0 ){
2284 }else if( sp
->fallback
){
2285 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2286 "More than one fallback assigned to token %s", x
);
2289 sp
->fallback
= psp
->fallback
;
2290 psp
->gp
->has_fallback
= 1;
2294 case RESYNC_AFTER_RULE_ERROR
:
2295 /* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2297 case RESYNC_AFTER_DECL_ERROR
:
2298 if( x
[0]=='.' ) psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2299 if( x
[0]=='%' ) psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2304 /* In spite of its name, this function is really a scanner. It read
2305 ** in the entire input file (all at once) then tokenizes it. Each
2306 ** token is passed to the function "parseonetoken" which builds all
2307 ** the appropriate data structures in the global state vector "gp".
2322 ps
.filename
= gp
->filename
;
2324 ps
.state
= INITIALIZE
;
2326 /* Begin by reading the input file */
2327 fp
= fopen(ps
.filename
,"rb");
2329 ErrorMsg(ps
.filename
,0,"Can't open this file for reading.");
2334 filesize
= ftell(fp
);
2336 filebuf
= (char *)malloc( filesize
+1 );
2338 ErrorMsg(ps
.filename
,0,"Can't allocate %d of memory to hold this file.",
2344 if( fread(filebuf
,1,filesize
,fp
)!=filesize
){
2345 ErrorMsg(ps
.filename
,0,"Can't read in all %d bytes of this file.",
2353 filebuf
[filesize
] = 0;
2355 /* Now scan the text of the input file */
2357 for(cp
=filebuf
; (c
= *cp
)!=0; ){
2358 if( c
=='\n' ) lineno
++; /* Keep track of the line number */
2359 if( isspace(c
) ){ cp
++; continue; } /* Skip all white space */
2360 if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments */
2362 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2365 if( c
=='/' && cp
[1]=='*' ){ /* Skip C style comments */
2367 while( (c
= *cp
)!=0 && (c
!='/' || cp
[-1]!='*') ){
2368 if( c
=='\n' ) lineno
++;
2374 ps
.tokenstart
= cp
; /* Mark the beginning of the token */
2375 ps
.tokenlineno
= lineno
; /* Linenumber on which token begins */
2376 if( c
=='\"' ){ /* String literals */
2378 while( (c
= *cp
)!=0 && c
!='\"' ){
2379 if( c
=='\n' ) lineno
++;
2383 ErrorMsg(ps
.filename
,startline
,
2384 "String starting on this line is not terminated before the end of the file.");
2390 }else if( c
=='{' ){ /* A block of C code */
2393 for(level
=1; (c
= *cp
)!=0 && (level
>1 || c
!='}'); cp
++){
2394 if( c
=='\n' ) lineno
++;
2395 else if( c
=='{' ) level
++;
2396 else if( c
=='}' ) level
--;
2397 else if( c
=='/' && cp
[1]=='*' ){ /* Skip comments */
2401 while( (c
= *cp
)!=0 && (c
!='/' || prevc
!='*') ){
2402 if( c
=='\n' ) lineno
++;
2406 }else if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments too */
2408 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2410 }else if( c
=='\'' || c
=='\"' ){ /* String a character literals */
2411 int startchar
, prevc
;
2414 for(cp
++; (c
= *cp
)!=0 && (c
!=startchar
|| prevc
=='\\'); cp
++){
2415 if( c
=='\n' ) lineno
++;
2416 if( prevc
=='\\' ) prevc
= 0;
2422 ErrorMsg(ps
.filename
,ps
.tokenlineno
,
2423 "C code starting on this line is not terminated before the end of the file.");
2429 }else if( isalnum(c
) ){ /* Identifiers */
2430 while( (c
= *cp
)!=0 && (isalnum(c
) || c
=='_') ) cp
++;
2432 }else if( c
==':' && cp
[1]==':' && cp
[2]=='=' ){ /* The operator "::=" */
2435 }else{ /* All other (one character) operators */
2440 *cp
= 0; /* Null terminate the token */
2441 parseonetoken(&ps
); /* Parse the token */
2442 *cp
= c
; /* Restore the buffer */
2445 free(filebuf
); /* Release the buffer after parsing */
2446 gp
->rule
= ps
.firstrule
;
2447 gp
->errorcnt
= ps
.errorcnt
;
2449 /*************************** From the file "plink.c" *********************/
2451 ** Routines processing configuration follow-set propagation links
2452 ** in the LEMON parser generator.
2454 static struct plink
*plink_freelist
= 0;
2456 /* Allocate a new plink */
2457 struct plink
*Plink_new(){
2460 if( plink_freelist
==0 ){
2463 plink_freelist
= (struct plink
*)malloc( sizeof(struct plink
)*amt
);
2464 if( plink_freelist
==0 ){
2466 "Unable to allocate memory for a new follow-set propagation link.\n");
2469 for(i
=0; i
<amt
-1; i
++) plink_freelist
[i
].next
= &plink_freelist
[i
+1];
2470 plink_freelist
[amt
-1].next
= 0;
2472 new = plink_freelist
;
2473 plink_freelist
= plink_freelist
->next
;
2477 /* Add a plink to a plink list */
2478 void Plink_add(plpp
,cfp
)
2479 struct plink
**plpp
;
2489 /* Transfer every plink on the list "from" to the list "to" */
2490 void Plink_copy(to
,from
)
2494 struct plink
*nextpl
;
2496 nextpl
= from
->next
;
2503 /* Delete every plink on the list */
2504 void Plink_delete(plp
)
2507 struct plink
*nextpl
;
2511 plp
->next
= plink_freelist
;
2512 plink_freelist
= plp
;
2516 /*********************** From the file "report.c" **************************/
2518 ** Procedures for generating reports and tables in the LEMON parser generator.
2521 /* Generate a filename with the given suffix. Space to hold the
2522 ** name comes from malloc() and must be freed by the calling
2525 PRIVATE
char *file_makename(lemp
,suffix
)
2532 name
= malloc( strlen(out_dir
) + strlen(lemp
->filename
) + strlen(suffix
) + 6 );
2534 fprintf(stderr
,"Can't allocate space for a filename.\n");
2537 /* skip directory, JK */
2538 if (NULL
== (cp
= strrchr(lemp
->filename
, '/'))) {
2539 cp
= lemp
->filename
;
2543 strcpy(name
,out_dir
);
2546 cp
= strrchr(name
,'.');
2548 strcat(name
,suffix
);
2552 /* Open a file with a name based on the name of the input file,
2553 ** but with a different (specified) suffix, and return a pointer
2555 PRIVATE
FILE *file_open(lemp
,suffix
,mode
)
2562 if( lemp
->outname
) free(lemp
->outname
);
2563 lemp
->outname
= file_makename(lemp
, suffix
);
2564 fp
= fopen(lemp
->outname
,mode
);
2565 if( fp
==0 && *mode
=='w' ){
2566 fprintf(stderr
,"Can't open file \"%s\".\n",lemp
->outname
);
2573 /* Duplicate the input file without comments and without actions
2580 int i
, j
, maxlen
, len
, ncolumns
, skip
;
2581 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp
->filename
);
2583 for(i
=0; i
<lemp
->nsymbol
; i
++){
2584 sp
= lemp
->symbols
[i
];
2585 len
= strlen(sp
->name
);
2586 if( len
>maxlen
) maxlen
= len
;
2588 ncolumns
= 76/(maxlen
+5);
2589 if( ncolumns
<1 ) ncolumns
= 1;
2590 skip
= (lemp
->nsymbol
+ ncolumns
- 1)/ncolumns
;
2591 for(i
=0; i
<skip
; i
++){
2593 for(j
=i
; j
<lemp
->nsymbol
; j
+=skip
){
2594 sp
= lemp
->symbols
[j
];
2595 assert( sp
->index
==j
);
2596 printf(" %3d %-*.*s",j
,maxlen
,maxlen
,sp
->name
);
2600 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
2601 printf("%s",rp
->lhs
->name
);
2602 /* if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
2604 for(i
=0; i
<rp
->nrhs
; i
++){
2605 printf(" %s",rp
->rhs
[i
]->name
);
2606 /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
2609 if( rp
->precsym
) printf(" [%s]",rp
->precsym
->name
);
2610 /* if( rp->code ) printf("\n %s",rp->code); */
2615 PRIVATE
void ConfigPrint(fp
,cfp
)
2622 fprintf(fp
,"%s ::=",rp
->lhs
->name
);
2623 for(i
=0; i
<=rp
->nrhs
; i
++){
2624 if( i
==cfp
->dot
) fprintf(fp
," *");
2625 if( i
==rp
->nrhs
) break;
2626 fprintf(fp
," %s",rp
->rhs
[i
]->name
);
2633 PRIVATE
void SetPrint(out
,set
,lemp
)
2641 fprintf(out
,"%12s[","");
2642 for(i
=0; i
<lemp
->nterminal
; i
++){
2643 if( SetFind(set
,i
) ){
2644 fprintf(out
,"%s%s",spacer
,lemp
->symbols
[i
]->name
);
2651 /* Print a plink chain */
2652 void PlinkPrint(out
,plp
,tag
)
2658 fprintf(out
,"%12s%s (state %2d) ","",tag
,plp
->cfp
->stp
->index
);
2659 ConfigPrint(out
,plp
->cfp
);
2666 /* Print an action to the given file descriptor. Return FALSE if
2667 ** nothing was actually printed.
2669 PRIVATE
int PrintAction(struct action
*ap
, FILE *fp
, int indent
){
2673 fprintf(fp
,"%*s shift %d",indent
,ap
->sp
->name
,ap
->x
.stp
->index
);
2676 fprintf(fp
,"%*s reduce %d",indent
,ap
->sp
->name
,ap
->x
.rp
->index
);
2679 fprintf(fp
,"%*s accept",indent
,ap
->sp
->name
);
2682 fprintf(fp
,"%*s error",indent
,ap
->sp
->name
);
2685 fprintf(fp
,"%*s reduce %-3d ** Parsing conflict **",
2686 indent
,ap
->sp
->name
,ap
->x
.rp
->index
);
2697 /* Generate the "y.output" log file */
2698 void ReportOutput(lemp
)
2707 fp
= file_open(lemp
,".out","w");
2710 for(i
=0; i
<lemp
->nstate
; i
++){
2711 stp
= lemp
->sorted
[i
];
2712 fprintf(fp
,"State %d:\n",stp
->index
);
2713 if( lemp
->basisflag
) cfp
=stp
->bp
;
2717 if( cfp
->dot
==cfp
->rp
->nrhs
){
2718 sprintf(buf
,"(%d)",cfp
->rp
->index
);
2719 fprintf(fp
," %5s ",buf
);
2723 ConfigPrint(fp
,cfp
);
2726 SetPrint(fp
,cfp
->fws
,lemp
);
2727 PlinkPrint(fp
,cfp
->fplp
,"To ");
2728 PlinkPrint(fp
,cfp
->bplp
,"From");
2730 if( lemp
->basisflag
) cfp
=cfp
->bp
;
2734 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
2735 if( PrintAction(ap
,fp
,30) ) fprintf(fp
,"\n");
2743 /* Search for the file "name" which is in the same directory as
2744 ** the exacutable */
2745 PRIVATE
char *pathsearch(argv0
,name
,modemask
)
2755 cp
= strrchr(argv0
,'\\');
2757 cp
= strrchr(argv0
,'/');
2762 path
= (char *)malloc( strlen(argv0
) + strlen(name
) + 2 );
2763 if( path
) sprintf(path
,"%s/%s",argv0
,name
);
2766 pathlist
= getenv("PATH");
2767 if( pathlist
==0 ) pathlist
= ".:/bin:/usr/bin";
2768 path
= (char *)malloc( strlen(pathlist
)+strlen(name
)+2 );
2771 cp
= strchr(pathlist
,':');
2772 if( cp
==0 ) cp
= &pathlist
[strlen(pathlist
)];
2775 sprintf(path
,"%s/%s",pathlist
,name
);
2777 if( c
==0 ) pathlist
= "";
2778 else pathlist
= &cp
[1];
2779 if( access(path
,modemask
)==0 ) break;
2786 /* Given an action, compute the integer value for that action
2787 ** which is to be put in the action table of the generated machine.
2788 ** Return negative if no action should be generated.
2790 PRIVATE
int compute_action(lemp
,ap
)
2796 case SHIFT
: act
= ap
->x
.stp
->index
; break;
2797 case REDUCE
: act
= ap
->x
.rp
->index
+ lemp
->nstate
; break;
2798 case ERROR
: act
= lemp
->nstate
+ lemp
->nrule
; break;
2799 case ACCEPT
: act
= lemp
->nstate
+ lemp
->nrule
+ 1; break;
2800 default: act
= -1; break;
2805 #define LINESIZE 1000
2806 /* The next cluster of routines are for reading the template file
2807 ** and writing the results to the generated parser */
2808 /* The first function transfers data from "in" to "out" until
2809 ** a line is seen which begins with "%%". The line number is
2812 ** if name!=0, then any word that begin with "Parse" is changed to
2813 ** begin with *name instead.
2815 PRIVATE
void tplt_xfer(name
,in
,out
,lineno
)
2822 char line
[LINESIZE
];
2823 while( fgets(line
,LINESIZE
,in
) && (line
[0]!='%' || line
[1]!='%') ){
2827 for(i
=0; line
[i
]; i
++){
2828 if( line
[i
]=='P' && strncmp(&line
[i
],"Parse",5)==0
2829 && (i
==0 || !isalpha(line
[i
-1]))
2831 if( i
>iStart
) fprintf(out
,"%.*s",i
-iStart
,&line
[iStart
]);
2832 fprintf(out
,"%s",name
);
2838 fprintf(out
,"%s",&line
[iStart
]);
2842 /* The next function finds the template file and opens it, returning
2843 ** a pointer to the opened file. */
2844 PRIVATE
FILE *tplt_open(lemp
)
2851 char *tpltname_alloc
= NULL
;
2854 cp
= strrchr(lemp
->filename
,'.');
2856 sprintf(buf
,"%.*s.lt",(int)(cp
-lemp
->filename
),lemp
->filename
);
2858 sprintf(buf
,"%s.lt",lemp
->filename
);
2860 if( access(buf
,004)==0 ){
2862 }else if( access(lemp
->tmplname
,004)==0 ){
2863 tpltname
= lemp
->tmplname
;
2865 tpltname
= tpltname_alloc
= pathsearch(lemp
->argv0
,lemp
->tmplname
,0);
2868 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
2873 in
= fopen(tpltname
,"r");
2875 fprintf(stderr
,"Can't open the template file \"%s\".\n",tpltname
);
2878 if (tpltname_alloc
) free(tpltname_alloc
);
2882 /* Print a string to the file and keep the linenumber up to date */
2883 PRIVATE
void tplt_print(out
,lemp
,str
,strln
,lineno
)
2890 if( str
==0 ) return;
2891 fprintf(out
,"#line %d \"%s\"\n",strln
,lemp
->filename
); (*lineno
)++;
2893 if( *str
=='\n' ) (*lineno
)++;
2897 fprintf(out
,"\n#line %d \"%s\"\n",*lineno
+2,lemp
->outname
); (*lineno
)+=2;
2902 ** The following routine emits code for the destructor for the
2905 PRIVATE
void emit_destructor_code(out
,sp
,lemp
,lineno
)
2914 if( sp
->type
==TERMINAL
){
2915 cp
= lemp
->tokendest
;
2917 fprintf(out
,"#line %d \"%s\"\n{",lemp
->tokendestln
,lemp
->filename
);
2918 }else if( sp
->destructor
){
2919 cp
= sp
->destructor
;
2920 fprintf(out
,"#line %d \"%s\"\n{",sp
->destructorln
,lemp
->filename
);
2924 fprintf(out
,"#line %d \"%s\"\n{",lemp
->vardestln
,lemp
->filename
);
2927 if( *cp
=='$' && cp
[1]=='$' ){
2928 fprintf(out
,"(yypminor->yy%d)",sp
->dtnum
);
2932 if( *cp
=='\n' ) linecnt
++;
2935 (*lineno
) += 3 + linecnt
;
2936 fprintf(out
,"}\n#line %d \"%s\"\n",*lineno
,lemp
->outname
);
2941 ** Return TRUE (non-zero) if the given symbol has a destructor.
2943 PRIVATE
int has_destructor(sp
, lemp
)
2948 if( sp
->type
==TERMINAL
){
2949 ret
= lemp
->tokendest
!=0;
2951 ret
= lemp
->vardest
!=0 || sp
->destructor
!=0;
2957 ** Generate code which executes when the rule "rp" is reduced. Write
2958 ** the code to "out". Make sure lineno stays up-to-date.
2960 PRIVATE
void emit_code(out
,rp
,lemp
,lineno
)
2969 char lhsused
= 0; /* True if the LHS element has been used */
2970 char used
[MAXRHS
]; /* True for each RHS element which is used */
2972 for(i
=0; i
<rp
->nrhs
; i
++) used
[i
] = 0;
2975 /* Generate code to do the reduce action */
2977 fprintf(out
,"#line %d \"%s\"\n{",rp
->line
,lemp
->filename
);
2978 for(cp
=rp
->code
; *cp
; cp
++){
2979 if( isalpha(*cp
) && (cp
==rp
->code
|| (!isalnum(cp
[-1]) && cp
[-1]!='_')) ){
2981 for(xp
= &cp
[1]; isalnum(*xp
) || *xp
=='_'; xp
++);
2984 if( rp
->lhsalias
&& strcmp(cp
,rp
->lhsalias
)==0 ){
2985 fprintf(out
,"yygotominor.yy%d",rp
->lhs
->dtnum
);
2989 for(i
=0; i
<rp
->nrhs
; i
++){
2990 if( rp
->rhsalias
[i
] && strcmp(cp
,rp
->rhsalias
[i
])==0 ){
2991 fprintf(out
,"yymsp[%d].minor.yy%d",i
-rp
->nrhs
+1,rp
->rhs
[i
]->dtnum
);
3000 if( *cp
=='\n' ) linecnt
++;
3003 (*lineno
) += 3 + linecnt
;
3004 fprintf(out
,"}\n#line %d \"%s\"\n",*lineno
,lemp
->outname
);
3005 } /* End if( rp->code ) */
3007 /* Check to make sure the LHS has been used */
3008 if( rp
->lhsalias
&& !lhsused
){
3009 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3010 "Label \"%s\" for \"%s(%s)\" is never used.",
3011 rp
->lhsalias
,rp
->lhs
->name
,rp
->lhsalias
);
3015 /* Generate destructor code for RHS symbols which are not used in the
3017 for(i
=0; i
<rp
->nrhs
; i
++){
3018 if( rp
->rhsalias
[i
] && !used
[i
] ){
3019 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3020 "Label %s for \"%s(%s)\" is never used.",
3021 rp
->rhsalias
[i
],rp
->rhs
[i
]->name
,rp
->rhsalias
[i
]);
3023 }else if( rp
->rhsalias
[i
]==0 ){
3024 if( has_destructor(rp
->rhs
[i
],lemp
) ){
3025 fprintf(out
," yy_destructor(%d,&yymsp[%d].minor);\n",
3026 rp
->rhs
[i
]->index
,i
-rp
->nrhs
+1); (*lineno
)++;
3028 fprintf(out
," /* No destructor defined for %s */\n",
3038 ** Print the definition of the union used for the parser's data stack.
3039 ** This union contains fields for every possible data type for tokens
3040 ** and nonterminals. In the process of computing and printing this
3041 ** union, also set the ".dtnum" field of every terminal and nonterminal
3044 PRIVATE
void print_stack_union(out
,lemp
,plineno
,mhflag
)
3045 FILE *out
; /* The output stream */
3046 struct lemon
*lemp
; /* The main info structure for this parser */
3047 int *plineno
; /* Pointer to the line number */
3048 int mhflag
; /* True if generating makeheaders output */
3050 int lineno
; /* The line number of the output */
3051 char **types
; /* A hash table of datatypes */
3052 int arraysize
; /* Size of the "types" array */
3053 int maxdtlength
; /* Maximum length of any ".datatype" field. */
3054 char *stddt
; /* Standardized name for a datatype */
3055 int i
,j
; /* Loop counters */
3056 int hash
; /* For hashing the name of a type */
3057 char *name
; /* Name of the parser */
3059 /* Allocate and initialize types[] and allocate stddt[] */
3060 arraysize
= lemp
->nsymbol
* 2;
3061 types
= (char**)malloc( arraysize
* sizeof(char*) );
3062 for(i
=0; i
<arraysize
; i
++) types
[i
] = 0;
3064 if( lemp
->vartype
){
3065 maxdtlength
= strlen(lemp
->vartype
);
3067 for(i
=0; i
<lemp
->nsymbol
; i
++){
3069 struct symbol
*sp
= lemp
->symbols
[i
];
3070 if( sp
->datatype
==0 ) continue;
3071 len
= strlen(sp
->datatype
);
3072 if( len
>maxdtlength
) maxdtlength
= len
;
3074 stddt
= (char*)malloc( maxdtlength
*2 + 1 );
3075 if( types
==0 || stddt
==0 ){
3076 fprintf(stderr
,"Out of memory.\n");
3080 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3081 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
3082 ** used for terminal symbols. If there is no %default_type defined then
3083 ** 0 is also used as the .dtnum value for nonterminals which do not specify
3084 ** a datatype using the %type directive.
3086 for(i
=0; i
<lemp
->nsymbol
; i
++){
3087 struct symbol
*sp
= lemp
->symbols
[i
];
3089 if( sp
==lemp
->errsym
){
3090 sp
->dtnum
= arraysize
+1;
3093 if( sp
->type
!=NONTERMINAL
|| (sp
->datatype
==0 && lemp
->vartype
==0) ){
3098 if( cp
==0 ) cp
= lemp
->vartype
;
3100 while( isspace(*cp
) ) cp
++;
3101 while( *cp
) stddt
[j
++] = *cp
++;
3102 while( j
>0 && isspace(stddt
[j
-1]) ) j
--;
3105 for(j
=0; stddt
[j
]; j
++){
3106 hash
= (unsigned int)hash
*53u + (unsigned int) stddt
[j
];
3108 hash
= (hash
& 0x7fffffff)%arraysize
;
3109 while( types
[hash
] ){
3110 if( strcmp(types
[hash
],stddt
)==0 ){
3111 sp
->dtnum
= hash
+ 1;
3115 if( hash
>=arraysize
) hash
= 0;
3117 if( types
[hash
]==0 ){
3118 sp
->dtnum
= hash
+ 1;
3119 types
[hash
] = (char*)malloc( strlen(stddt
)+1 );
3120 if( types
[hash
]==0 ){
3121 fprintf(stderr
,"Out of memory.\n");
3124 strcpy(types
[hash
],stddt
);
3128 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3129 name
= lemp
->name
? lemp
->name
: "Parse";
3131 if( mhflag
){ fprintf(out
,"#if INTERFACE\n"); lineno
++; }
3132 fprintf(out
,"#define %sTOKENTYPE %s\n",name
,
3133 lemp
->tokentype
?lemp
->tokentype
:"void*"); lineno
++;
3134 if( mhflag
){ fprintf(out
,"#endif\n"); lineno
++; }
3135 fprintf(out
,"typedef union {\n"); lineno
++;
3136 fprintf(out
," %sTOKENTYPE yy0;\n",name
); lineno
++;
3137 for(i
=0; i
<arraysize
; i
++){
3138 if( types
[i
]==0 ) continue;
3139 fprintf(out
," %s yy%d;\n",types
[i
],i
+1); lineno
++;
3142 fprintf(out
," int yy%d;\n",lemp
->errsym
->dtnum
); lineno
++;
3145 fprintf(out
,"} YYMINORTYPE;\n"); lineno
++;
3150 ** Return the name of a C datatype able to represent values between
3151 ** lwr and upr, inclusive.
3153 static const char *minimum_size_type(int lwr
, int upr
){
3156 return "unsigned char";
3157 }else if( upr
<65535 ){
3158 return "unsigned short int";
3160 return "unsigned int";
3162 }else if( lwr
>=-127 && upr
<=127 ){
3163 return "signed char";
3164 }else if( lwr
>=-32767 && upr
<32767 ){
3172 ** Each state contains a set of token transaction and a set of
3173 ** nonterminal transactions. Each of these sets makes an instance
3174 ** of the following structure. An array of these structures is used
3175 ** to order the creation of entries in the yy_action[] table.
3178 struct state
*stp
; /* A pointer to a state */
3179 int isTkn
; /* True to use tokens. False for non-terminals */
3180 int nAction
; /* Number of actions */
3184 ** Compare to axset structures for sorting purposes
3186 static int axset_compare(const void *a
, const void *b
){
3187 struct axset
*p1
= (struct axset
*)a
;
3188 struct axset
*p2
= (struct axset
*)b
;
3189 return p2
->nAction
- p1
->nAction
;
3192 /* Generate C source code for the parser */
3193 void ReportTable(lemp
, mhflag
)
3195 int mhflag
; /* Output in makeheaders format if true */
3198 char line
[LINESIZE
];
3203 struct acttab
*pActtab
;
3205 int mnTknOfst
, mxTknOfst
;
3206 int mnNtOfst
, mxNtOfst
;
3210 in
= tplt_open(lemp
);
3212 out
= file_open(lemp
,".c","w");
3218 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3220 /* Generate the include code, if any */
3221 tplt_print(out
,lemp
,lemp
->include
,lemp
->includeln
,&lineno
);
3223 name
= file_makename(lemp
, ".h");
3224 fprintf(out
,"#include \"%s\"\n", name
); lineno
++;
3227 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3229 /* Generate #defines for all tokens */
3232 fprintf(out
,"#if INTERFACE\n"); lineno
++;
3233 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
3235 for(i
=1; i
<lemp
->nterminal
; i
++){
3236 fprintf(out
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
3239 fprintf(out
,"#endif\n"); lineno
++;
3241 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3243 /* Generate the defines */
3244 fprintf(out
,"/* \001 */\n");
3245 fprintf(out
,"#define YYCODETYPE %s\n",
3246 minimum_size_type(0, lemp
->nsymbol
+5)); lineno
++;
3247 fprintf(out
,"#define YYNOCODE %d\n",lemp
->nsymbol
+1); lineno
++;
3248 fprintf(out
,"#define YYACTIONTYPE %s\n",
3249 minimum_size_type(0, lemp
->nstate
+lemp
->nrule
+5)); lineno
++;
3250 print_stack_union(out
,lemp
,&lineno
,mhflag
);
3251 if( lemp
->stacksize
){
3252 if( atoi(lemp
->stacksize
)<=0 ){
3253 ErrorMsg(lemp
->filename
,0,
3254 "Illegal stack size: [%s]. The stack size should be an integer constant.",
3257 lemp
->stacksize
= "100";
3259 fprintf(out
,"#define YYSTACKDEPTH %s\n",lemp
->stacksize
); lineno
++;
3261 fprintf(out
,"#define YYSTACKDEPTH 100\n"); lineno
++;
3264 fprintf(out
,"#if INTERFACE\n"); lineno
++;
3266 name
= lemp
->name
? lemp
->name
: "Parse";
3267 if( lemp
->arg
&& lemp
->arg
[0] ){
3268 i
= strlen(lemp
->arg
);
3269 while( i
>=1 && isspace(lemp
->arg
[i
-1]) ) i
--;
3270 while( i
>=1 && (isalnum(lemp
->arg
[i
-1]) || lemp
->arg
[i
-1]=='_') ) i
--;
3271 fprintf(out
,"#define %sARG_SDECL %s;\n",name
,lemp
->arg
); lineno
++;
3272 fprintf(out
,"#define %sARG_PDECL ,%s\n",name
,lemp
->arg
); lineno
++;
3273 fprintf(out
,"#define %sARG_FETCH %s = yypParser->%s\n",
3274 name
,lemp
->arg
,&lemp
->arg
[i
]); lineno
++;
3275 fprintf(out
,"#define %sARG_STORE yypParser->%s = %s\n",
3276 name
,&lemp
->arg
[i
],&lemp
->arg
[i
]); lineno
++;
3278 fprintf(out
,"#define %sARG_SDECL\n",name
); lineno
++;
3279 fprintf(out
,"#define %sARG_PDECL\n",name
); lineno
++;
3280 fprintf(out
,"#define %sARG_FETCH\n",name
); lineno
++;
3281 fprintf(out
,"#define %sARG_STORE\n",name
); lineno
++;
3284 fprintf(out
,"#endif\n"); lineno
++;
3286 fprintf(out
,"#define YYNSTATE %d\n",lemp
->nstate
); lineno
++;
3287 fprintf(out
,"#define YYNRULE %d\n",lemp
->nrule
); lineno
++;
3288 fprintf(out
,"#define YYERRORSYMBOL %d\n",lemp
->errsym
->index
); lineno
++;
3289 fprintf(out
,"#define YYERRSYMDT yy%d\n",lemp
->errsym
->dtnum
); lineno
++;
3290 if( lemp
->has_fallback
){
3291 fprintf(out
,"#define YYFALLBACK 1\n"); lineno
++;
3293 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3295 /* Generate the action table and its associates:
3297 ** yy_action[] A single table containing all actions.
3298 ** yy_lookahead[] A table containing the lookahead for each entry in
3299 ** yy_action. Used to detect hash collisions.
3300 ** yy_shift_ofst[] For each state, the offset into yy_action for
3301 ** shifting terminals.
3302 ** yy_reduce_ofst[] For each state, the offset into yy_action for
3303 ** shifting non-terminals after a reduce.
3304 ** yy_default[] Default action for each state.
3307 /* Compute the actions on all states and count them up */
3308 ax
= malloc( sizeof(ax
[0])*lemp
->nstate
*2 );
3310 fprintf(stderr
,"malloc failed\n");
3313 for(i
=0; i
<lemp
->nstate
; i
++){
3314 stp
= lemp
->sorted
[i
];
3315 stp
->nTknAct
= stp
->nNtAct
= 0;
3316 stp
->iDflt
= lemp
->nstate
+ lemp
->nrule
;
3317 stp
->iTknOfst
= NO_OFFSET
;
3318 stp
->iNtOfst
= NO_OFFSET
;
3319 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3320 if( compute_action(lemp
,ap
)>=0 ){
3321 if( ap
->sp
->index
<lemp
->nterminal
){
3323 }else if( ap
->sp
->index
<lemp
->nsymbol
){
3326 stp
->iDflt
= compute_action(lemp
, ap
);
3332 ax
[i
*2].nAction
= stp
->nTknAct
;
3333 ax
[i
*2+1].stp
= stp
;
3334 ax
[i
*2+1].isTkn
= 0;
3335 ax
[i
*2+1].nAction
= stp
->nNtAct
;
3337 mxTknOfst
= mnTknOfst
= 0;
3338 mxNtOfst
= mnNtOfst
= 0;
3340 /* Compute the action table. In order to try to keep the size of the
3341 ** action table to a minimum, the heuristic of placing the largest action
3342 ** sets first is used.
3344 qsort(ax
, lemp
->nstate
*2, sizeof(ax
[0]), axset_compare
);
3345 pActtab
= acttab_alloc();
3346 for(i
=0; i
<lemp
->nstate
*2 && ax
[i
].nAction
>0; i
++){
3349 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3351 if( ap
->sp
->index
>=lemp
->nterminal
) continue;
3352 action
= compute_action(lemp
, ap
);
3353 if( action
<0 ) continue;
3354 acttab_action(pActtab
, ap
->sp
->index
, action
);
3356 stp
->iTknOfst
= acttab_insert(pActtab
);
3357 if( stp
->iTknOfst
<mnTknOfst
) mnTknOfst
= stp
->iTknOfst
;
3358 if( stp
->iTknOfst
>mxTknOfst
) mxTknOfst
= stp
->iTknOfst
;
3360 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3362 if( ap
->sp
->index
<lemp
->nterminal
) continue;
3363 if( ap
->sp
->index
==lemp
->nsymbol
) continue;
3364 action
= compute_action(lemp
, ap
);
3365 if( action
<0 ) continue;
3366 acttab_action(pActtab
, ap
->sp
->index
, action
);
3368 stp
->iNtOfst
= acttab_insert(pActtab
);
3369 if( stp
->iNtOfst
<mnNtOfst
) mnNtOfst
= stp
->iNtOfst
;
3370 if( stp
->iNtOfst
>mxNtOfst
) mxNtOfst
= stp
->iNtOfst
;
3375 /* Output the yy_action table */
3376 fprintf(out
,"static YYACTIONTYPE yy_action[] = {\n"); lineno
++;
3377 n
= acttab_size(pActtab
);
3378 for(i
=j
=0; i
<n
; i
++){
3379 int action
= acttab_yyaction(pActtab
, i
);
3380 if( action
<0 ) action
= lemp
->nsymbol
+ lemp
->nrule
+ 2;
3381 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3382 fprintf(out
, " %4d,", action
);
3383 if( j
==9 || i
==n
-1 ){
3384 fprintf(out
, "\n"); lineno
++;
3390 fprintf(out
, "};\n"); lineno
++;
3392 /* Output the yy_lookahead table */
3393 fprintf(out
,"static YYCODETYPE yy_lookahead[] = {\n"); lineno
++;
3394 for(i
=j
=0; i
<n
; i
++){
3395 int la
= acttab_yylookahead(pActtab
, i
);
3396 if( la
<0 ) la
= lemp
->nsymbol
;
3397 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3398 fprintf(out
, " %4d,", la
);
3399 if( j
==9 || i
==n
-1 ){
3400 fprintf(out
, "\n"); lineno
++;
3406 fprintf(out
, "};\n"); lineno
++;
3408 /* Output the yy_shift_ofst[] table */
3409 fprintf(out
, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst
-1); lineno
++;
3410 fprintf(out
, "static %s yy_shift_ofst[] = {\n",
3411 minimum_size_type(mnTknOfst
-1, mxTknOfst
)); lineno
++;
3413 for(i
=j
=0; i
<n
; i
++){
3415 stp
= lemp
->sorted
[i
];
3416 ofst
= stp
->iTknOfst
;
3417 if( ofst
==NO_OFFSET
) ofst
= mnTknOfst
- 1;
3418 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3419 fprintf(out
, " %4d,", ofst
);
3420 if( j
==9 || i
==n
-1 ){
3421 fprintf(out
, "\n"); lineno
++;
3427 fprintf(out
, "};\n"); lineno
++;
3429 /* Output the yy_reduce_ofst[] table */
3430 fprintf(out
, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst
-1); lineno
++;
3431 fprintf(out
, "static %s yy_reduce_ofst[] = {\n",
3432 minimum_size_type(mnNtOfst
-1, mxNtOfst
)); lineno
++;
3434 for(i
=j
=0; i
<n
; i
++){
3436 stp
= lemp
->sorted
[i
];
3437 ofst
= stp
->iNtOfst
;
3438 if( ofst
==NO_OFFSET
) ofst
= mnNtOfst
- 1;
3439 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3440 fprintf(out
, " %4d,", ofst
);
3441 if( j
==9 || i
==n
-1 ){
3442 fprintf(out
, "\n"); lineno
++;
3448 fprintf(out
, "};\n"); lineno
++;
3450 /* Output the default action table */
3451 fprintf(out
, "static YYACTIONTYPE yy_default[] = {\n"); lineno
++;
3453 for(i
=j
=0; i
<n
; i
++){
3454 stp
= lemp
->sorted
[i
];
3455 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3456 fprintf(out
, " %4d,", stp
->iDflt
);
3457 if( j
==9 || i
==n
-1 ){
3458 fprintf(out
, "\n"); lineno
++;
3464 fprintf(out
, "};\n"); lineno
++;
3465 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3467 /* Generate the table of fallback tokens.
3469 if( lemp
->has_fallback
){
3470 for(i
=0; i
<lemp
->nterminal
; i
++){
3471 struct symbol
*p
= lemp
->symbols
[i
];
3472 if( p
->fallback
==0 ){
3473 fprintf(out
, " 0, /* %10s => nothing */\n", p
->name
);
3475 fprintf(out
, " %3d, /* %10s => %s */\n", p
->fallback
->index
,
3476 p
->name
, p
->fallback
->name
);
3481 tplt_xfer(lemp
->name
, in
, out
, &lineno
);
3483 /* Generate a table containing the symbolic name of every symbol
3485 for(i
=0; i
<lemp
->nsymbol
; i
++){
3486 sprintf(line
,"\"%s\",",lemp
->symbols
[i
]->name
);
3487 fprintf(out
," %-15s",line
);
3488 if( (i
&3)==3 ){ fprintf(out
,"\n"); lineno
++; }
3490 if( (i
&3)!=0 ){ fprintf(out
,"\n"); lineno
++; }
3491 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3493 /* Generate a table containing a text string that describes every
3494 ** rule in the rule set of the grammer. This information is used
3495 ** when tracing REDUCE actions.
3497 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
3498 assert( rp
->index
==i
);
3499 fprintf(out
," /* %3d */ \"%s ::=", i
, rp
->lhs
->name
);
3500 for(j
=0; j
<rp
->nrhs
; j
++) fprintf(out
," %s",rp
->rhs
[j
]->name
);
3501 fprintf(out
,"\",\n"); lineno
++;
3503 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3505 /* Generate code which executes every time a symbol is popped from
3506 ** the stack while processing errors or while destroying the parser.
3507 ** (In other words, generate the %destructor actions)
3509 if( lemp
->tokendest
){
3510 for(i
=0; i
<lemp
->nsymbol
; i
++){
3511 struct symbol
*sp
= lemp
->symbols
[i
];
3512 if( sp
==0 || sp
->type
!=TERMINAL
) continue;
3513 fprintf(out
," case %d:\n",sp
->index
); lineno
++;
3515 for(i
=0; i
<lemp
->nsymbol
&& lemp
->symbols
[i
]->type
!=TERMINAL
; i
++);
3516 if( i
<lemp
->nsymbol
){
3517 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
3518 fprintf(out
," break;\n"); lineno
++;
3521 for(i
=0; i
<lemp
->nsymbol
; i
++){
3522 struct symbol
*sp
= lemp
->symbols
[i
];
3523 if( sp
==0 || sp
->type
==TERMINAL
|| sp
->destructor
==0 ) continue;
3524 fprintf(out
," case %d:\n",sp
->index
); lineno
++;
3525 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
3526 fprintf(out
," break;\n"); lineno
++;
3528 if( lemp
->vardest
){
3529 struct symbol
*dflt_sp
= 0;
3530 for(i
=0; i
<lemp
->nsymbol
; i
++){
3531 struct symbol
*sp
= lemp
->symbols
[i
];
3532 if( sp
==0 || sp
->type
==TERMINAL
||
3533 sp
->index
<=0 || sp
->destructor
!=0 ) continue;
3534 fprintf(out
," case %d:\n",sp
->index
); lineno
++;
3538 emit_destructor_code(out
,dflt_sp
,lemp
,&lineno
);
3539 fprintf(out
," break;\n"); lineno
++;
3542 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3544 /* Generate code which executes whenever the parser stack overflows */
3545 tplt_print(out
,lemp
,lemp
->overflow
,lemp
->overflowln
,&lineno
);
3546 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3548 /* Generate the table of rule information
3550 ** Note: This code depends on the fact that rules are number
3551 ** sequentually beginning with 0.
3553 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3554 fprintf(out
," { %d, %d },\n",rp
->lhs
->index
,rp
->nrhs
); lineno
++;
3556 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3558 /* Generate code which execution during each REDUCE action */
3559 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3560 fprintf(out
," case %d:\n",rp
->index
); lineno
++;
3561 emit_code(out
,rp
,lemp
,&lineno
);
3562 fprintf(out
," break;\n"); lineno
++;
3564 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3566 /* Generate code which executes if a parse fails */
3567 tplt_print(out
,lemp
,lemp
->failure
,lemp
->failureln
,&lineno
);
3568 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3570 /* Generate code which executes when a syntax error occurs */
3571 tplt_print(out
,lemp
,lemp
->error
,lemp
->errorln
,&lineno
);
3572 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3574 /* Generate code which executes when the parser accepts its input */
3575 tplt_print(out
,lemp
,lemp
->accept
,lemp
->acceptln
,&lineno
);
3576 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3578 /* Append any addition code the user desires */
3579 tplt_print(out
,lemp
,lemp
->extracode
,lemp
->extracodeln
,&lineno
);
3586 /* Generate a header file for the parser */
3587 void ReportHeader(lemp
)
3592 char line
[LINESIZE
];
3593 char pattern
[LINESIZE
];
3596 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
3598 in
= file_open(lemp
,".h","r");
3600 for(i
=1; i
<lemp
->nterminal
&& fgets(line
,LINESIZE
,in
); i
++){
3601 sprintf(pattern
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
3602 if( strcmp(line
,pattern
) ) break;
3605 if( i
==lemp
->nterminal
){
3606 /* No change in the file. Don't rewrite it. */
3610 out
= file_open(lemp
,".h","w");
3612 for(i
=1; i
<lemp
->nterminal
; i
++){
3613 fprintf(out
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
3620 /* Reduce the size of the action tables, if possible, by making use
3623 ** In this version, we take the most frequent REDUCE action and make
3624 ** it the default. Only default a reduce if there are more than one.
3626 void CompressTables(lemp
)
3630 struct action
*ap
, *ap2
;
3631 struct rule
*rp
, *rp2
, *rbest
;
3635 for(i
=0; i
<lemp
->nstate
; i
++){
3636 stp
= lemp
->sorted
[i
];
3640 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3641 if( ap
->type
!=REDUCE
) continue;
3643 if( rp
==rbest
) continue;
3645 for(ap2
=ap
->next
; ap2
; ap2
=ap2
->next
){
3646 if( ap2
->type
!=REDUCE
) continue;
3648 if( rp2
==rbest
) continue;
3657 /* Do not make a default if the number of rules to default
3658 ** is not at least 2 */
3659 if( nbest
<2 ) continue;
3662 /* Combine matching REDUCE actions into a single default */
3663 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3664 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) break;
3667 ap
->sp
= Symbol_new("{default}");
3668 for(ap
=ap
->next
; ap
; ap
=ap
->next
){
3669 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) ap
->type
= NOT_USED
;
3671 stp
->ap
= Action_sort(stp
->ap
);
3675 /***************** From the file "set.c" ************************************/
3677 ** Set manipulation routines for the LEMON parser generator.
3680 static int global_size
= 0;
3682 /* Set the set size */
3689 /* Allocate a new set */
3693 s
= (char*)malloc( global_size
);
3697 for(i
=0; i
<global_size
; i
++) s
[i
] = 0;
3701 /* Deallocate a set */
3708 /* Add a new element to the set. Return TRUE if the element was added
3709 ** and FALSE if it was already there. */
3720 /* Add every element of s2 to s1. Return TRUE if s1 changes. */
3727 for(i
=0; i
<global_size
; i
++){
3728 if( s2
[i
]==0 ) continue;
3736 /********************** From the file "table.c" ****************************/
3738 ** All code in this file has been automatically generated
3739 ** from a specification in the file
3741 ** by the associative array code building program "aagen".
3742 ** Do not edit this file! Instead, edit the specification
3743 ** file, then rerun aagen.
3746 ** Code for processing tables in the LEMON parser generator.
3749 PRIVATE
int strhash(x
)
3753 while( *x
) h
= h
*13u + (unsigned int) *(x
++);
3757 /* Works like strdup, sort of. Save a string in malloced memory, but
3758 ** keep strings in a table so that the same string is not in more
3766 z
= Strsafe_find(y
);
3767 if( z
==0 && (z
=malloc( strlen(y
)+1 ))!=0 ){
3775 /* There is one instance of the following structure for each
3776 ** associative array of type "x1".
3779 int size
; /* The number of available slots. */
3780 /* Must be a power of 2 greater than or */
3782 int count
; /* Number of currently slots filled */
3783 struct s_x1node
*tbl
; /* The data stored here */
3784 struct s_x1node
**ht
; /* Hash table for lookups */
3787 /* There is one instance of this structure for every data element
3788 ** in an associative array of type "x1".
3790 typedef struct s_x1node
{
3791 char *data
; /* The data */
3792 struct s_x1node
*next
; /* Next entry with the same hash */
3793 struct s_x1node
**from
; /* Previous link */
3796 /* There is only one instance of the array, which is the following */
3797 static struct s_x1
*x1a
;
3799 /* Allocate a new associative array */
3800 void Strsafe_init(){
3802 x1a
= (struct s_x1
*)malloc( sizeof(struct s_x1
) );
3806 x1a
->tbl
= (x1node
*)malloc(
3807 (sizeof(x1node
) + sizeof(x1node
*))*1024 );
3813 x1a
->ht
= (x1node
**)&(x1a
->tbl
[1024]);
3814 for(i
=0; i
<1024; i
++) x1a
->ht
[i
] = 0;
3818 /* Insert a new record into the array. Return TRUE if successful.
3819 ** Prior data with the same key is NOT overwritten */
3820 int Strsafe_insert(data
)
3827 if( x1a
==0 ) return 0;
3829 h
= ph
& (x1a
->size
-1);
3832 if( strcmp(np
->data
,data
)==0 ){
3833 /* An existing entry with the same key is found. */
3834 /* Fail because overwrite is not allows. */
3839 if( x1a
->count
>=x1a
->size
){
3840 /* Need to make the hash table bigger */
3843 array
.size
= size
= x1a
->size
*2;
3844 array
.count
= x1a
->count
;
3845 array
.tbl
= (x1node
*)malloc(
3846 (sizeof(x1node
) + sizeof(x1node
*))*size
);
3847 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
3848 array
.ht
= (x1node
**)&(array
.tbl
[size
]);
3849 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
3850 for(i
=0; i
<x1a
->count
; i
++){
3851 x1node
*oldnp
, *newnp
;
3852 oldnp
= &(x1a
->tbl
[i
]);
3853 h
= strhash(oldnp
->data
) & (size
-1);
3854 newnp
= &(array
.tbl
[i
]);
3855 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
3856 newnp
->next
= array
.ht
[h
];
3857 newnp
->data
= oldnp
->data
;
3858 newnp
->from
= &(array
.ht
[h
]);
3859 array
.ht
[h
] = newnp
;
3862 /* *x1a = array; *//* copy 'array' */
3863 memcpy(x1a
, &array
, sizeof(array
));
3865 /* Insert the new data */
3866 h
= ph
& (x1a
->size
-1);
3867 np
= &(x1a
->tbl
[x1a
->count
++]);
3869 if( x1a
->ht
[h
] ) x1a
->ht
[h
]->from
= &(np
->next
);
3870 np
->next
= x1a
->ht
[h
];
3872 np
->from
= &(x1a
->ht
[h
]);
3876 /* Return a pointer to data assigned to the given key. Return NULL
3877 ** if no such key. */
3878 char *Strsafe_find(key
)
3884 if( x1a
==0 ) return 0;
3885 h
= strhash(key
) & (x1a
->size
-1);
3888 if( strcmp(np
->data
,key
)==0 ) break;
3891 return np
? np
->data
: 0;
3894 /* Return a pointer to the (terminal or nonterminal) symbol "x".
3895 ** Create a new symbol if this is the first time "x" has been seen.
3897 struct symbol
*Symbol_new(x
)
3902 sp
= Symbol_find(x
);
3904 sp
= (struct symbol
*)malloc( sizeof(struct symbol
) );
3906 sp
->name
= Strsafe(x
);
3907 sp
->type
= isupper(*x
) ? TERMINAL
: NONTERMINAL
;
3913 sp
->lambda
= Bo_FALSE
;
3916 Symbol_insert(sp
,sp
->name
);
3921 /* Compare two symbols for working purposes
3923 ** Symbols that begin with upper case letters (terminals or tokens)
3924 ** must sort before symbols that begin with lower case letters
3925 ** (non-terminals). Other than that, the order does not matter.
3927 ** We find experimentally that leaving the symbols in their original
3928 ** order (the order they appeared in the grammar file) gives the
3929 ** smallest parser tables in SQLite.
3931 int Symbolcmpp(struct symbol
**a
, struct symbol
**b
){
3932 int i1
= (**a
).index
+ 10000000*((**a
).name
[0]>'Z');
3933 int i2
= (**b
).index
+ 10000000*((**b
).name
[0]>'Z');
3937 /* There is one instance of the following structure for each
3938 ** associative array of type "x2".
3941 int size
; /* The number of available slots. */
3942 /* Must be a power of 2 greater than or */
3944 int count
; /* Number of currently slots filled */
3945 struct s_x2node
*tbl
; /* The data stored here */
3946 struct s_x2node
**ht
; /* Hash table for lookups */
3949 /* There is one instance of this structure for every data element
3950 ** in an associative array of type "x2".
3952 typedef struct s_x2node
{
3953 struct symbol
*data
; /* The data */
3954 char *key
; /* The key */
3955 struct s_x2node
*next
; /* Next entry with the same hash */
3956 struct s_x2node
**from
; /* Previous link */
3959 /* There is only one instance of the array, which is the following */
3960 static struct s_x2
*x2a
;
3962 /* Allocate a new associative array */
3965 x2a
= (struct s_x2
*)malloc( sizeof(struct s_x2
) );
3969 x2a
->tbl
= (x2node
*)malloc(
3970 (sizeof(x2node
) + sizeof(x2node
*))*128 );
3976 x2a
->ht
= (x2node
**)&(x2a
->tbl
[128]);
3977 for(i
=0; i
<128; i
++) x2a
->ht
[i
] = 0;
3981 /* Insert a new record into the array. Return TRUE if successful.
3982 ** Prior data with the same key is NOT overwritten */
3983 int Symbol_insert(data
,key
)
3984 struct symbol
*data
;
3991 if( x2a
==0 ) return 0;
3993 h
= ph
& (x2a
->size
-1);
3996 if( strcmp(np
->key
,key
)==0 ){
3997 /* An existing entry with the same key is found. */
3998 /* Fail because overwrite is not allows. */
4003 if( x2a
->count
>=x2a
->size
){
4004 /* Need to make the hash table bigger */
4007 array
.size
= size
= x2a
->size
*2;
4008 array
.count
= x2a
->count
;
4009 array
.tbl
= (x2node
*)malloc(
4010 (sizeof(x2node
) + sizeof(x2node
*))*size
);
4011 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
4012 array
.ht
= (x2node
**)&(array
.tbl
[size
]);
4013 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
4014 for(i
=0; i
<x2a
->count
; i
++){
4015 x2node
*oldnp
, *newnp
;
4016 oldnp
= &(x2a
->tbl
[i
]);
4017 h
= strhash(oldnp
->key
) & (size
-1);
4018 newnp
= &(array
.tbl
[i
]);
4019 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4020 newnp
->next
= array
.ht
[h
];
4021 newnp
->key
= oldnp
->key
;
4022 newnp
->data
= oldnp
->data
;
4023 newnp
->from
= &(array
.ht
[h
]);
4024 array
.ht
[h
] = newnp
;
4027 /* *x2a = array; *//* copy 'array' */
4028 memcpy(x2a
, &array
, sizeof(array
));
4030 /* Insert the new data */
4031 h
= ph
& (x2a
->size
-1);
4032 np
= &(x2a
->tbl
[x2a
->count
++]);
4035 if( x2a
->ht
[h
] ) x2a
->ht
[h
]->from
= &(np
->next
);
4036 np
->next
= x2a
->ht
[h
];
4038 np
->from
= &(x2a
->ht
[h
]);
4042 /* Return a pointer to data assigned to the given key. Return NULL
4043 ** if no such key. */
4044 struct symbol
*Symbol_find(key
)
4050 if( x2a
==0 ) return 0;
4051 h
= strhash(key
) & (x2a
->size
-1);
4054 if( strcmp(np
->key
,key
)==0 ) break;
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
)
4064 struct symbol
*data
;
4065 if( x2a
&& n
>0 && n
<=x2a
->count
){
4066 data
= x2a
->tbl
[n
-1].data
;
4073 /* Return the size of the array */
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
;
4086 if( x2a
==0 ) return 0;
4088 array
= (struct symbol
**)malloc( sizeof(struct symbol
*)*size
);
4090 for(i
=0; i
<size
; i
++) array
[i
] = x2a
->tbl
[i
].data
;
4095 /* Compare two configurations */
4101 x
= a
->rp
->index
- b
->rp
->index
;
4102 if( x
==0 ) x
= a
->dot
- b
->dot
;
4106 /* Compare two states */
4107 PRIVATE
int statecmp(a
,b
)
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
;
4124 PRIVATE
int statehash(a
)
4129 h
= h
*571u + (unsigned int)a
->rp
->index
*37u + (unsigned int)a
->dot
;
4135 /* Allocate a new state structure */
4136 struct state
*State_new()
4139 new = (struct state
*)malloc( sizeof(struct state
) );
4144 /* There is one instance of the following structure for each
4145 ** associative array of type "x3".
4148 int size
; /* The number of available slots. */
4149 /* Must be a power of 2 greater than or */
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 */
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 */
4172 x3a
= (struct s_x3
*)malloc( sizeof(struct s_x3
) );
4176 x3a
->tbl
= (x3node
*)malloc(
4177 (sizeof(x3node
) + sizeof(x3node
*))*128 );
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
)
4198 if( x3a
==0 ) return 0;
4199 ph
= statehash(key
);
4200 h
= ph
& (x3a
->size
-1);
4203 if( statecmp(np
->key
,key
)==0 ){
4204 /* An existing entry with the same key is found. */
4205 /* Fail because overwrite is not allows. */
4210 if( x3a
->count
>=x3a
->size
){
4211 /* Need to make the hash table bigger */
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
;
4234 /* *x3a = array; *//* copy 'array' */
4235 memcpy(x3a
, &array
, sizeof(array
));
4237 /* Insert the new data */
4238 h
= ph
& (x3a
->size
-1);
4239 np
= &(x3a
->tbl
[x3a
->count
++]);
4242 if( x3a
->ht
[h
] ) x3a
->ht
[h
]->from
= &(np
->next
);
4243 np
->next
= x3a
->ht
[h
];
4245 np
->from
= &(x3a
->ht
[h
]);
4249 /* Return a pointer to data assigned to the given key. Return NULL
4250 ** if no such key. */
4251 struct state
*State_find(key
)
4257 if( x3a
==0 ) return 0;
4258 h
= statehash(key
) & (x3a
->size
-1);
4261 if( statecmp(np
->key
,key
)==0 ) break;
4264 return np
? np
->data
: 0;
4267 /* Return the size of the array */
4268 int State_count(void)
4270 return x3a
? x3a
->count
: 0;
4273 /* Return an array of pointers to all data in the table.
4274 ** The array is obtained from malloc. Return NULL if memory allocation
4275 ** problems, or if the array is empty. */
4276 struct state
**State_arrayof()
4278 struct state
**array
;
4280 if( x3a
==0 ) return 0;
4282 array
= (struct state
**)malloc( sizeof(struct state
*)*size
);
4284 for(i
=0; i
<size
; i
++) array
[i
] = x3a
->tbl
[i
].data
;
4289 /* Hash a configuration */
4290 PRIVATE
int confighash(a
)
4294 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
4298 /* There is one instance of the following structure for each
4299 ** associative array of type "x4".
4302 int size
; /* The number of available slots. */
4303 /* Must be a power of 2 greater than or */
4305 int count
; /* Number of currently slots filled */
4306 struct s_x4node
*tbl
; /* The data stored here */
4307 struct s_x4node
**ht
; /* Hash table for lookups */
4310 /* There is one instance of this structure for every data element
4311 ** in an associative array of type "x4".
4313 typedef struct s_x4node
{
4314 struct config
*data
; /* The data */
4315 struct s_x4node
*next
; /* Next entry with the same hash */
4316 struct s_x4node
**from
; /* Previous link */
4319 /* There is only one instance of the array, which is the following */
4320 static struct s_x4
*x4a
;
4322 /* Allocate a new associative array */
4323 void Configtable_init(){
4325 x4a
= (struct s_x4
*)malloc( sizeof(struct s_x4
) );
4329 x4a
->tbl
= (x4node
*)malloc(
4330 (sizeof(x4node
) + sizeof(x4node
*))*64 );
4336 x4a
->ht
= (x4node
**)&(x4a
->tbl
[64]);
4337 for(i
=0; i
<64; i
++) x4a
->ht
[i
] = 0;
4341 /* Insert a new record into the array. Return TRUE if successful.
4342 ** Prior data with the same key is NOT overwritten */
4343 int Configtable_insert(data
)
4344 struct config
*data
;
4350 if( x4a
==0 ) return 0;
4351 ph
= confighash(data
);
4352 h
= ph
& (x4a
->size
-1);
4355 if( Configcmp(np
->data
,data
)==0 ){
4356 /* An existing entry with the same key is found. */
4357 /* Fail because overwrite is not allows. */
4362 if( x4a
->count
>=x4a
->size
){
4363 /* Need to make the hash table bigger */
4366 array
.size
= size
= x4a
->size
*2;
4367 array
.count
= x4a
->count
;
4368 array
.tbl
= (x4node
*)malloc(
4369 (sizeof(x4node
) + sizeof(x4node
*))*size
);
4370 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
4371 array
.ht
= (x4node
**)&(array
.tbl
[size
]);
4372 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
4373 for(i
=0; i
<x4a
->count
; i
++){
4374 x4node
*oldnp
, *newnp
;
4375 oldnp
= &(x4a
->tbl
[i
]);
4376 h
= confighash(oldnp
->data
) & (size
-1);
4377 newnp
= &(array
.tbl
[i
]);
4378 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4379 newnp
->next
= array
.ht
[h
];
4380 newnp
->data
= oldnp
->data
;
4381 newnp
->from
= &(array
.ht
[h
]);
4382 array
.ht
[h
] = newnp
;
4385 /* *x4a = array; *//* copy 'array' */
4386 memcpy(x4a
, &array
, sizeof(array
));
4388 /* Insert the new data */
4389 h
= ph
& (x4a
->size
-1);
4390 np
= &(x4a
->tbl
[x4a
->count
++]);
4392 if( x4a
->ht
[h
] ) x4a
->ht
[h
]->from
= &(np
->next
);
4393 np
->next
= x4a
->ht
[h
];
4395 np
->from
= &(x4a
->ht
[h
]);
4399 /* Return a pointer to data assigned to the given key. Return NULL
4400 ** if no such key. */
4401 struct config
*Configtable_find(key
)
4407 if( x4a
==0 ) return 0;
4408 h
= confighash(key
) & (x4a
->size
-1);
4411 if( Configcmp(np
->data
,key
)==0 ) break;
4414 return np
? np
->data
: 0;
4417 /* Remove all data from the table. Pass each data to the function "f"
4418 ** as it is removed. ("f" may be null to avoid this step.) */
4419 void Configtable_clear(f
)
4420 int(*f
)(/* struct config * */);
4423 if( x4a
==0 || x4a
->count
==0 ) return;
4424 if( f
) for(i
=0; i
<x4a
->count
; i
++) (*f
)(x4a
->tbl
[i
].data
);
4425 for(i
=0; i
<x4a
->size
; i
++) x4a
->ht
[i
] = 0;