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