2 ** This file contains all sources (including headers) to the LEMON
3 ** LALR(1) parser generator. The sources have been combined into a
4 ** single file to make it easy to include LEMON in the source tree
5 ** and Makefile of another program.
7 ** The author of this program disclaims copyright.
16 #define ISSPACE(X) isspace((unsigned char)(X))
17 #define ISDIGIT(X) isdigit((unsigned char)(X))
18 #define ISALNUM(X) isalnum((unsigned char)(X))
19 #define ISALPHA(X) isalpha((unsigned char)(X))
20 #define ISUPPER(X) isupper((unsigned char)(X))
21 #define ISLOWER(X) islower((unsigned char)(X))
25 # if defined(_WIN32) || defined(WIN32)
34 extern int access(const char *path
, int mode
);
42 /* #define PRIVATE static */
46 #define MAXRHS 5 /* Set low to exercise exception code */
51 static int showPrecedenceConflict
= 0;
52 static char *msort(char*,char**,int(*)(const char*,const char*));
55 ** Compilers are getting increasingly pedantic about type conversions
56 ** as C evolves ever closer to Ada.... To work around the latest problems
57 ** we have to define the following variant of strlen().
59 #define lemonStrlen(X) ((int)strlen(X))
62 ** Compilers are starting to complain about the use of sprintf() and strcpy(),
63 ** saying they are unsafe. So we define our own versions of those routines too.
65 ** There are three routines here: lemon_sprintf(), lemon_vsprintf(), and
66 ** lemon_addtext(). The first two are replacements for sprintf() and vsprintf().
67 ** The third is a helper routine for vsnprintf() that adds texts to the end of a
68 ** buffer, making sure the buffer is always zero-terminated.
70 ** The string formatter is a minimal subset of stdlib sprintf() supporting only
71 ** a few simply conversions:
78 static void lemon_addtext(
79 char *zBuf
, /* The buffer to which text is added */
80 int *pnUsed
, /* Slots of the buffer used so far */
81 const char *zIn
, /* Text to add */
82 int nIn
, /* Bytes of text to add. -1 to use strlen() */
83 int iWidth
/* Field width. Negative to left justify */
85 if( nIn
<0 ) for(nIn
=0; zIn
[nIn
]; nIn
++){}
86 while( iWidth
>nIn
){ zBuf
[(*pnUsed
)++] = ' '; iWidth
--; }
88 memcpy(&zBuf
[*pnUsed
], zIn
, nIn
);
90 while( (-iWidth
)>nIn
){ zBuf
[(*pnUsed
)++] = ' '; iWidth
++; }
93 static int lemon_vsprintf(char *str
, const char *zFormat
, va_list ap
){
99 for(i
=j
=0; (c
= zFormat
[i
])!=0; i
++){
102 lemon_addtext(str
, &nUsed
, &zFormat
[j
], i
-j
, 0);
104 if( ISDIGIT(c
) || (c
=='-' && ISDIGIT(zFormat
[i
+1])) ){
106 while( ISDIGIT(zFormat
[i
]) ) iWidth
= iWidth
*10 + zFormat
[i
++] - '0';
107 if( c
=='-' ) iWidth
= -iWidth
;
111 int v
= va_arg(ap
, int);
113 lemon_addtext(str
, &nUsed
, "-", 1, iWidth
);
116 lemon_addtext(str
, &nUsed
, "0", 1, iWidth
);
121 zTemp
[sizeof(zTemp
)-k
] = (v
%10) + '0';
124 lemon_addtext(str
, &nUsed
, &zTemp
[sizeof(zTemp
)-k
], k
, iWidth
);
126 z
= va_arg(ap
, const char*);
127 lemon_addtext(str
, &nUsed
, z
, -1, iWidth
);
128 }else if( c
=='.' && memcmp(&zFormat
[i
], ".*s", 3)==0 ){
131 z
= va_arg(ap
, const char*);
132 lemon_addtext(str
, &nUsed
, z
, k
, iWidth
);
134 lemon_addtext(str
, &nUsed
, "%", 1, 0);
136 fprintf(stderr
, "illegal format\n");
142 lemon_addtext(str
, &nUsed
, &zFormat
[j
], i
-j
, 0);
145 static int lemon_sprintf(char *str
, const char *format
, ...){
148 va_start(ap
, format
);
149 rc
= lemon_vsprintf(str
, format
, ap
);
153 static void lemon_strcpy(char *dest
, const char *src
){
154 while( (*(dest
++) = *(src
++))!=0 ){}
156 static void lemon_strcat(char *dest
, const char *src
){
157 while( *dest
) dest
++;
158 lemon_strcpy(dest
, src
);
162 /* a few forward declarations... */
167 static struct action
*Action_new(void);
168 static struct action
*Action_sort(struct action
*);
170 /********** From the file "build.h" ************************************/
171 void FindRulePrecedences(struct lemon
*);
172 void FindFirstSets(struct lemon
*);
173 void FindStates(struct lemon
*);
174 void FindLinks(struct lemon
*);
175 void FindFollowSets(struct lemon
*);
176 void FindActions(struct lemon
*);
178 /********* From the file "configlist.h" *********************************/
179 void Configlist_init(void);
180 struct config
*Configlist_add(struct rule
*, int);
181 struct config
*Configlist_addbasis(struct rule
*, int);
182 void Configlist_closure(struct lemon
*);
183 void Configlist_sort(void);
184 void Configlist_sortbasis(void);
185 struct config
*Configlist_return(void);
186 struct config
*Configlist_basis(void);
187 void Configlist_eat(struct config
*);
188 void Configlist_reset(void);
190 /********* From the file "error.h" ***************************************/
191 void ErrorMsg(const char *, int,const char *, ...);
193 /****** From the file "option.h" ******************************************/
194 enum option_type
{ OPT_FLAG
=1, OPT_INT
, OPT_DBL
, OPT_STR
,
195 OPT_FFLAG
, OPT_FINT
, OPT_FDBL
, OPT_FSTR
};
197 enum option_type type
;
202 int OptInit(char**,struct s_options
*,FILE*);
208 /******** From the file "parse.h" *****************************************/
209 void Parse(struct lemon
*lemp
);
211 /********* From the file "plink.h" ***************************************/
212 struct plink
*Plink_new(void);
213 void Plink_add(struct plink
**, struct config
*);
214 void Plink_copy(struct plink
**, struct plink
*);
215 void Plink_delete(struct plink
*);
217 /********** From the file "report.h" *************************************/
218 void Reprint(struct lemon
*);
219 void ReportOutput(struct lemon
*);
220 void ReportTable(struct lemon
*, int);
221 void ReportHeader(struct lemon
*);
222 void CompressTables(struct lemon
*);
223 void ResortStates(struct lemon
*);
225 /********** From the file "set.h" ****************************************/
226 void SetSize(int); /* All sets will be of size N */
227 char *SetNew(void); /* A new set for element 0..N */
228 void SetFree(char*); /* Deallocate a set */
229 int SetAdd(char*,int); /* Add element to a set */
230 int SetUnion(char *,char *); /* A <- A U B, thru element N */
231 #define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
233 /********** From the file "struct.h" *************************************/
235 ** Principal data structures for the LEMON parser generator.
238 typedef enum {LEMON_FALSE
=0, LEMON_TRUE
} Boolean
;
240 /* Symbols (terminals and nonterminals) of the grammar are stored
241 ** in the following: */
254 const char *name
; /* Name of the symbol */
255 int index
; /* Index number for this symbol */
256 enum symbol_type type
; /* Symbols are all either TERMINALS or NTs */
257 struct rule
*rule
; /* Linked list of rules of this (if an NT) */
258 struct symbol
*fallback
; /* fallback token in case this token doesn't parse */
259 int prec
; /* Precedence if defined (-1 otherwise) */
260 enum e_assoc assoc
; /* Associativity if precedence is defined */
261 char *firstset
; /* First-set for all rules of this symbol */
262 Boolean lambda
; /* True if NT and can generate an empty string */
263 int useCnt
; /* Number of times used */
264 char *destructor
; /* Code which executes whenever this symbol is
265 ** popped from the stack during error processing */
266 int destLineno
; /* Line number for start of destructor. Set to
267 ** -1 for duplicate destructors. */
268 char *datatype
; /* The data type of information held by this
269 ** object. Only used if type==NONTERMINAL */
270 int dtnum
; /* The data type number. In the parser, the value
271 ** stack is a union. The .yy%d element of this
272 ** union is the correct data type for this object */
273 /* The following fields are used by MULTITERMINALs only */
274 int nsubsym
; /* Number of constituent symbols in the MULTI */
275 struct symbol
**subsym
; /* Array of constituent symbols */
278 /* Each production rule in the grammar is stored in the following
281 struct symbol
*lhs
; /* Left-hand side of the rule */
282 const char *lhsalias
; /* Alias for the LHS (NULL if none) */
283 int lhsStart
; /* True if left-hand side is the start symbol */
284 int ruleline
; /* Line number for the rule */
285 int nrhs
; /* Number of RHS symbols */
286 struct symbol
**rhs
; /* The RHS symbols */
287 const char **rhsalias
; /* An alias for each RHS symbol (NULL if none) */
288 int line
; /* Line number at which code begins */
289 const char *code
; /* The code executed when this rule is reduced */
290 const char *codePrefix
; /* Setup code before code[] above */
291 const char *codeSuffix
; /* Breakdown code after code[] above */
292 int noCode
; /* True if this rule has no associated C code */
293 int codeEmitted
; /* True if the code has been emitted already */
294 struct symbol
*precsym
; /* Precedence symbol for this rule */
295 int index
; /* An index number for this rule */
296 int iRule
; /* Rule number as used in the generated tables */
297 Boolean canReduce
; /* True if this rule is ever reduced */
298 Boolean doesReduce
; /* Reduce actions occur after optimization */
299 struct rule
*nextlhs
; /* Next rule with the same LHS */
300 struct rule
*next
; /* Next rule in the global list */
303 /* A configuration is a production rule of the grammar together with
304 ** a mark (dot) showing how much of that rule has been processed so far.
305 ** Configurations also contain a follow-set which is a list of terminal
306 ** symbols which are allowed to immediately follow the end of the rule.
307 ** Every configuration is recorded as an instance of the following: */
313 struct rule
*rp
; /* The rule upon which the configuration is based */
314 int dot
; /* The parse point */
315 char *fws
; /* Follow-set for this configuration only */
316 struct plink
*fplp
; /* Follow-set forward propagation links */
317 struct plink
*bplp
; /* Follow-set backwards propagation links */
318 struct state
*stp
; /* Pointer to state which contains this */
319 enum cfgstatus status
; /* used during followset and shift computations */
320 struct config
*next
; /* Next configuration in the state */
321 struct config
*bp
; /* The next basis configuration */
329 SSCONFLICT
, /* A shift/shift conflict */
330 SRCONFLICT
, /* Was a reduce, but part of a conflict */
331 RRCONFLICT
, /* Was a reduce, but part of a conflict */
332 SH_RESOLVED
, /* Was a shift. Precedence resolved conflict */
333 RD_RESOLVED
, /* Was reduce. Precedence resolved conflict */
334 NOT_USED
, /* Deleted by compression */
335 SHIFTREDUCE
/* Shift first, then reduce */
338 /* Every shift or reduce operation is stored as one of the following */
340 struct symbol
*sp
; /* The look-ahead symbol */
343 struct state
*stp
; /* The new state, if a shift */
344 struct rule
*rp
; /* The rule, if a reduce */
346 struct symbol
*spOpt
; /* SHIFTREDUCE optimization to this symbol */
347 struct action
*next
; /* Next action for this state */
348 struct action
*collide
; /* Next action with the same hash */
351 /* Each state of the generated parser's finite state machine
352 ** is encoded as an instance of the following structure. */
354 struct config
*bp
; /* The basis configurations for this state */
355 struct config
*cfp
; /* All configurations in this set */
356 int statenum
; /* Sequential number for this state */
357 struct action
*ap
; /* List of actions for this state */
358 int nTknAct
, nNtAct
; /* Number of actions on terminals and nonterminals */
359 int iTknOfst
, iNtOfst
; /* yy_action[] offset for terminals and nonterms */
360 int iDfltReduce
; /* Default action is to REDUCE by this rule */
361 struct rule
*pDfltReduce
;/* The default REDUCE rule. */
362 int autoReduce
; /* True if this is an auto-reduce state */
364 #define NO_OFFSET (-2147483647)
366 /* A followset propagation link indicates that the contents of one
367 ** configuration followset should be propagated to another whenever
368 ** the first changes. */
370 struct config
*cfp
; /* The configuration to which linked */
371 struct plink
*next
; /* The next propagate link */
374 /* The state vector for the entire parser generator is recorded as
375 ** follows. (LEMON uses no global variables and makes little use of
376 ** static variables. Fields in the following structure can be thought
377 ** of as begin global variables in the program.) */
379 struct state
**sorted
; /* Table of states sorted by state number */
380 struct rule
*rule
; /* List of all rules */
381 struct rule
*startRule
; /* First rule */
382 int nstate
; /* Number of states */
383 int nxstate
; /* nstate with tail degenerate states removed */
384 int nrule
; /* Number of rules */
385 int nsymbol
; /* Number of terminal and nonterminal symbols */
386 int nterminal
; /* Number of terminal symbols */
387 struct symbol
**symbols
; /* Sorted array of pointers to symbols */
388 int errorcnt
; /* Number of errors */
389 struct symbol
*errsym
; /* The error symbol */
390 struct symbol
*wildcard
; /* Token that matches anything */
391 char *name
; /* Name of the generated parser */
392 char *arg
; /* Declaration of the 3th argument to parser */
393 char *tokentype
; /* Type of terminal symbols in the parser stack */
394 char *vartype
; /* The default type of non-terminal symbols */
395 char *start
; /* Name of the start symbol for the grammar */
396 char *stacksize
; /* Size of the parser stack */
397 char *include
; /* Code to put at the start of the C file */
398 char *error
; /* Code to execute when an error is seen */
399 char *overflow
; /* Code to execute on a stack overflow */
400 char *failure
; /* Code to execute on parser failure */
401 char *accept
; /* Code to execute when the parser excepts */
402 char *extracode
; /* Code appended to the generated file */
403 char *tokendest
; /* Code to execute to destroy token data */
404 char *vardest
; /* Code for the default non-terminal destructor */
405 char *filename
; /* Name of the input file */
406 char *outname
; /* Name of the current output file */
407 char *tokenprefix
; /* A prefix added to token names in the .h file */
408 int nconflict
; /* Number of parsing conflicts */
409 int nactiontab
; /* Number of entries in the yy_action[] table */
410 int tablesize
; /* Total table size of all tables in bytes */
411 int basisflag
; /* Print only basis configurations */
412 int has_fallback
; /* True if any %fallback is seen in the grammar */
413 int nolinenosflag
; /* True if #line statements should not be printed */
414 char *argv0
; /* Name of the program */
417 #define MemoryCheck(X) if((X)==0){ \
418 extern void memory_error(); \
422 /**************** From the file "table.h" *********************************/
424 ** All code in this file has been automatically generated
425 ** from a specification in the file
427 ** by the associative array code building program "aagen".
428 ** Do not edit this file! Instead, edit the specification
429 ** file, then rerun aagen.
432 ** Code for processing tables in the LEMON parser generator.
434 /* Routines for handling a strings */
436 const char *Strsafe(const char *);
438 void Strsafe_init(void);
439 int Strsafe_insert(const char *);
440 const char *Strsafe_find(const char *);
442 /* Routines for handling symbols of the grammar */
444 struct symbol
*Symbol_new(const char *);
445 int Symbolcmpp(const void *, const void *);
446 void Symbol_init(void);
447 int Symbol_insert(struct symbol
*, const char *);
448 struct symbol
*Symbol_find(const char *);
449 struct symbol
*Symbol_Nth(int);
450 int Symbol_count(void);
451 struct symbol
**Symbol_arrayof(void);
453 /* Routines to manage the state table */
455 int Configcmp(const char *, const char *);
456 struct state
*State_new(void);
457 void State_init(void);
458 int State_insert(struct state
*, struct config
*);
459 struct state
*State_find(struct config
*);
460 struct state
**State_arrayof(void);
462 /* Routines used for efficiency in Configlist_add */
464 void Configtable_init(void);
465 int Configtable_insert(struct config
*);
466 struct config
*Configtable_find(struct config
*);
467 void Configtable_clear(int(*)(struct config
*));
469 /****************** From the file "action.c" *******************************/
471 ** Routines processing parser actions in the LEMON parser generator.
474 /* Allocate a new parser action */
475 static struct action
*Action_new(void){
476 static struct action
*freelist
= 0;
477 struct action
*newaction
;
482 freelist
= (struct action
*)calloc(amt
, sizeof(struct action
));
484 fprintf(stderr
,"Unable to allocate memory for a new parser action.");
487 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
488 freelist
[amt
-1].next
= 0;
490 newaction
= freelist
;
491 freelist
= freelist
->next
;
495 /* Compare two actions for sorting purposes. Return negative, zero, or
496 ** positive if the first action is less than, equal to, or greater than
499 static int actioncmp(
504 rc
= ap1
->sp
->index
- ap2
->sp
->index
;
506 rc
= (int)ap1
->type
- (int)ap2
->type
;
508 if( rc
==0 && (ap1
->type
==REDUCE
|| ap1
->type
==SHIFTREDUCE
) ){
509 rc
= ap1
->x
.rp
->index
- ap2
->x
.rp
->index
;
512 rc
= (int) (ap2
- ap1
);
517 /* Sort parser actions */
518 static struct action
*Action_sort(
521 ap
= (struct action
*)msort((char *)ap
,(char **)&ap
->next
,
522 (int(*)(const char*,const char*))actioncmp
);
532 struct action
*newaction
;
533 newaction
= Action_new();
534 newaction
->next
= *app
;
536 newaction
->type
= type
;
538 newaction
->spOpt
= 0;
540 newaction
->x
.stp
= (struct state
*)arg
;
542 newaction
->x
.rp
= (struct rule
*)arg
;
545 /********************** New code to implement the "acttab" module ***********/
547 ** This module implements routines use to construct the yy_action[] table.
551 ** The state of the yy_action table under construction is an instance of
552 ** the following structure.
554 ** The yy_action table maps the pair (state_number, lookahead) into an
555 ** action_number. The table is an array of integers pairs. The state_number
556 ** determines an initial offset into the yy_action array. The lookahead
557 ** value is then added to this initial offset to get an index X into the
558 ** yy_action array. If the aAction[X].lookahead equals the value of the
559 ** of the lookahead input, then the value of the action_number output is
560 ** aAction[X].action. If the lookaheads do not match then the
561 ** default action for the state_number is returned.
563 ** All actions associated with a single state_number are first entered
564 ** into aLookahead[] using multiple calls to acttab_action(). Then the
565 ** actions for that single state_number are placed into the aAction[]
566 ** array with a single call to acttab_insert(). The acttab_insert() call
567 ** also resets the aLookahead[] array in preparation for the next
570 struct lookahead_action
{
571 int lookahead
; /* Value of the lookahead token */
572 int action
; /* Action to take on the given lookahead */
574 typedef struct acttab acttab
;
576 int nAction
; /* Number of used slots in aAction[] */
577 int nActionAlloc
; /* Slots allocated for aAction[] */
578 struct lookahead_action
579 *aAction
, /* The yy_action[] table under construction */
580 *aLookahead
; /* A single new transaction set */
581 int mnLookahead
; /* Minimum aLookahead[].lookahead */
582 int mnAction
; /* Action associated with mnLookahead */
583 int mxLookahead
; /* Maximum aLookahead[].lookahead */
584 int nLookahead
; /* Used slots in aLookahead[] */
585 int nLookaheadAlloc
; /* Slots allocated in aLookahead[] */
588 /* Return the number of entries in the yy_action table */
589 #define acttab_size(X) ((X)->nAction)
591 /* The value for the N-th entry in yy_action */
592 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
594 /* The value for the N-th entry in yy_lookahead */
595 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
597 /* Free all memory associated with the given acttab */
598 void acttab_free(acttab
*p
){
600 free( p
->aLookahead
);
604 /* Allocate a new acttab structure */
605 acttab
*acttab_alloc(void){
606 acttab
*p
= (acttab
*) calloc( 1, sizeof(*p
) );
608 fprintf(stderr
,"Unable to allocate memory for a new acttab.");
611 memset(p
, 0, sizeof(*p
));
615 /* Add a new action to the current transaction set.
617 ** This routine is called once for each lookahead for a particular
620 void acttab_action(acttab
*p
, int lookahead
, int action
){
621 if( p
->nLookahead
>=p
->nLookaheadAlloc
){
622 p
->nLookaheadAlloc
+= 25;
623 p
->aLookahead
= (struct lookahead_action
*) realloc( p
->aLookahead
,
624 sizeof(p
->aLookahead
[0])*p
->nLookaheadAlloc
);
625 if( p
->aLookahead
==0 ){
626 fprintf(stderr
,"malloc failed\n");
630 if( p
->nLookahead
==0 ){
631 p
->mxLookahead
= lookahead
;
632 p
->mnLookahead
= lookahead
;
633 p
->mnAction
= action
;
635 if( p
->mxLookahead
<lookahead
) p
->mxLookahead
= lookahead
;
636 if( p
->mnLookahead
>lookahead
){
637 p
->mnLookahead
= lookahead
;
638 p
->mnAction
= action
;
641 p
->aLookahead
[p
->nLookahead
].lookahead
= lookahead
;
642 p
->aLookahead
[p
->nLookahead
].action
= action
;
647 ** Add the transaction set built up with prior calls to acttab_action()
648 ** into the current action table. Then reset the transaction set back
649 ** to an empty set in preparation for a new round of acttab_action() calls.
651 ** Return the offset into the action table of the new transaction.
653 int acttab_insert(acttab
*p
){
655 assert( p
->nLookahead
>0 );
657 /* Make sure we have enough space to hold the expanded action table
658 ** in the worst case. The worst case occurs if the transaction set
659 ** must be appended to the current action table
661 n
= p
->mxLookahead
+ 1;
662 if( p
->nAction
+ n
>= p
->nActionAlloc
){
663 int oldAlloc
= p
->nActionAlloc
;
664 p
->nActionAlloc
= p
->nAction
+ n
+ p
->nActionAlloc
+ 20;
665 p
->aAction
= (struct lookahead_action
*) realloc( p
->aAction
,
666 sizeof(p
->aAction
[0])*p
->nActionAlloc
);
668 fprintf(stderr
,"malloc failed\n");
671 for(i
=oldAlloc
; i
<p
->nActionAlloc
; i
++){
672 p
->aAction
[i
].lookahead
= -1;
673 p
->aAction
[i
].action
= -1;
677 /* Scan the existing action table looking for an offset that is a
678 ** duplicate of the current transaction set. Fall out of the loop
679 ** if and when the duplicate is found.
681 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
683 for(i
=p
->nAction
-1; i
>=0; i
--){
684 if( p
->aAction
[i
].lookahead
==p
->mnLookahead
){
685 /* All lookaheads and actions in the aLookahead[] transaction
686 ** must match against the candidate aAction[i] entry. */
687 if( p
->aAction
[i
].action
!=p
->mnAction
) continue;
688 for(j
=0; j
<p
->nLookahead
; j
++){
689 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
690 if( k
<0 || k
>=p
->nAction
) break;
691 if( p
->aLookahead
[j
].lookahead
!=p
->aAction
[k
].lookahead
) break;
692 if( p
->aLookahead
[j
].action
!=p
->aAction
[k
].action
) break;
694 if( j
<p
->nLookahead
) continue;
696 /* No possible lookahead value that is not in the aLookahead[]
697 ** transaction is allowed to match aAction[i] */
699 for(j
=0; j
<p
->nAction
; j
++){
700 if( p
->aAction
[j
].lookahead
<0 ) continue;
701 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) n
++;
703 if( n
==p
->nLookahead
){
704 break; /* An exact match is found at offset i */
709 /* If no existing offsets exactly match the current transaction, find an
710 ** an empty offset in the aAction[] table in which we can add the
711 ** aLookahead[] transaction.
714 /* Look for holes in the aAction[] table that fit the current
715 ** aLookahead[] transaction. Leave i set to the offset of the hole.
716 ** If no holes are found, i is left at p->nAction, which means the
717 ** transaction will be appended. */
718 for(i
=0; i
<p
->nActionAlloc
- p
->mxLookahead
; i
++){
719 if( p
->aAction
[i
].lookahead
<0 ){
720 for(j
=0; j
<p
->nLookahead
; j
++){
721 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
723 if( p
->aAction
[k
].lookahead
>=0 ) break;
725 if( j
<p
->nLookahead
) continue;
726 for(j
=0; j
<p
->nAction
; j
++){
727 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) break;
730 break; /* Fits in empty slots */
735 /* Insert transaction set at index i. */
736 for(j
=0; j
<p
->nLookahead
; j
++){
737 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
738 p
->aAction
[k
] = p
->aLookahead
[j
];
739 if( k
>=p
->nAction
) p
->nAction
= k
+1;
743 /* Return the offset that is added to the lookahead in order to get the
744 ** index into yy_action of the action */
745 return i
- p
->mnLookahead
;
748 /********************** From the file "build.c" *****************************/
750 ** Routines to construction the finite state machine for the LEMON
754 /* Find a precedence symbol of every rule in the grammar.
756 ** Those rules which have a precedence symbol coded in the input
757 ** grammar using the "[symbol]" construct will already have the
758 ** rp->precsym field filled. Other rules take as their precedence
759 ** symbol the first RHS symbol with a defined precedence. If there
760 ** are not RHS symbols with a defined precedence, the precedence
761 ** symbol field is left blank.
763 void FindRulePrecedences(struct lemon
*xp
)
766 for(rp
=xp
->rule
; rp
; rp
=rp
->next
){
767 if( rp
->precsym
==0 ){
769 for(i
=0; i
<rp
->nrhs
&& rp
->precsym
==0; i
++){
770 struct symbol
*sp
= rp
->rhs
[i
];
771 if( sp
->type
==MULTITERMINAL
){
772 for(j
=0; j
<sp
->nsubsym
; j
++){
773 if( sp
->subsym
[j
]->prec
>=0 ){
774 rp
->precsym
= sp
->subsym
[j
];
778 }else if( sp
->prec
>=0 ){
779 rp
->precsym
= rp
->rhs
[i
];
787 /* Find all nonterminals which will generate the empty string.
788 ** Then go back and compute the first sets of every nonterminal.
789 ** The first set is the set of all terminal symbols which can begin
790 ** a string generated by that nonterminal.
792 void FindFirstSets(struct lemon
*lemp
)
798 for(i
=0; i
<lemp
->nsymbol
; i
++){
799 lemp
->symbols
[i
]->lambda
= LEMON_FALSE
;
801 for(i
=lemp
->nterminal
; i
<lemp
->nsymbol
; i
++){
802 lemp
->symbols
[i
]->firstset
= SetNew();
805 /* First compute all lambdas */
808 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
809 if( rp
->lhs
->lambda
) continue;
810 for(i
=0; i
<rp
->nrhs
; i
++){
811 struct symbol
*sp
= rp
->rhs
[i
];
812 assert( sp
->type
==NONTERMINAL
|| sp
->lambda
==LEMON_FALSE
);
813 if( sp
->lambda
==LEMON_FALSE
) break;
816 rp
->lhs
->lambda
= LEMON_TRUE
;
822 /* Now compute all first sets */
824 struct symbol
*s1
, *s2
;
826 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
828 for(i
=0; i
<rp
->nrhs
; i
++){
830 if( s2
->type
==TERMINAL
){
831 progress
+= SetAdd(s1
->firstset
,s2
->index
);
833 }else if( s2
->type
==MULTITERMINAL
){
834 for(j
=0; j
<s2
->nsubsym
; j
++){
835 progress
+= SetAdd(s1
->firstset
,s2
->subsym
[j
]->index
);
839 if( s1
->lambda
==LEMON_FALSE
) break;
841 progress
+= SetUnion(s1
->firstset
,s2
->firstset
);
842 if( s2
->lambda
==LEMON_FALSE
) break;
850 /* Compute all LR(0) states for the grammar. Links
851 ** are added to between some states so that the LR(1) follow sets
852 ** can be computed later.
854 PRIVATE
struct state
*getstate(struct lemon
*); /* forward reference */
855 void FindStates(struct lemon
*lemp
)
862 /* Find the start symbol */
864 sp
= Symbol_find(lemp
->start
);
866 ErrorMsg(lemp
->filename
,0,
867 "The specified start symbol \"%s\" is not \
868 in a nonterminal of the grammar. \"%s\" will be used as the start \
869 symbol instead.",lemp
->start
,lemp
->startRule
->lhs
->name
);
871 sp
= lemp
->startRule
->lhs
;
874 sp
= lemp
->startRule
->lhs
;
877 /* Make sure the start symbol doesn't occur on the right-hand side of
878 ** any rule. Report an error if it does. (YACC would generate a new
879 ** start symbol in this case.) */
880 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
882 for(i
=0; i
<rp
->nrhs
; i
++){
883 if( rp
->rhs
[i
]==sp
){ /* FIX ME: Deal with multiterminals */
884 ErrorMsg(lemp
->filename
,0,
885 "The start symbol \"%s\" occurs on the \
886 right-hand side of a rule. This will result in a parser which \
887 does not work properly.",sp
->name
);
893 /* The basis configuration set for the first state
894 ** is all rules which have the start symbol as their
896 for(rp
=sp
->rule
; rp
; rp
=rp
->nextlhs
){
897 struct config
*newcfp
;
899 newcfp
= Configlist_addbasis(rp
,0);
900 SetAdd(newcfp
->fws
,0);
903 /* Compute the first state. All other states will be
904 ** computed automatically during the computation of the first one.
905 ** The returned pointer to the first state is not used. */
906 (void)getstate(lemp
);
910 /* Return a pointer to a state which is described by the configuration
911 ** list which has been built from calls to Configlist_add.
913 PRIVATE
void buildshifts(struct lemon
*, struct state
*); /* Forwd ref */
914 PRIVATE
struct state
*getstate(struct lemon
*lemp
)
916 struct config
*cfp
, *bp
;
919 /* Extract the sorted basis of the new state. The basis was constructed
920 ** by prior calls to "Configlist_addbasis()". */
921 Configlist_sortbasis();
922 bp
= Configlist_basis();
924 /* Get a state with the same basis */
925 stp
= State_find(bp
);
927 /* A state with the same basis already exists! Copy all the follow-set
928 ** propagation links from the state under construction into the
929 ** preexisting state, then return a pointer to the preexisting state */
930 struct config
*x
, *y
;
931 for(x
=bp
, y
=stp
->bp
; x
&& y
; x
=x
->bp
, y
=y
->bp
){
932 Plink_copy(&y
->bplp
,x
->bplp
);
933 Plink_delete(x
->fplp
);
934 x
->fplp
= x
->bplp
= 0;
936 cfp
= Configlist_return();
939 /* This really is a new state. Construct all the details */
940 Configlist_closure(lemp
); /* Compute the configuration closure */
941 Configlist_sort(); /* Sort the configuration closure */
942 cfp
= Configlist_return(); /* Get a pointer to the config list */
943 stp
= State_new(); /* A new state structure */
945 stp
->bp
= bp
; /* Remember the configuration basis */
946 stp
->cfp
= cfp
; /* Remember the configuration closure */
947 stp
->statenum
= lemp
->nstate
++; /* Every state gets a sequence number */
948 stp
->ap
= 0; /* No actions, yet. */
949 State_insert(stp
,stp
->bp
); /* Add to the state table */
950 buildshifts(lemp
,stp
); /* Recursively compute successor states */
956 ** Return true if two symbols are the same.
958 int same_symbol(struct symbol
*a
, struct symbol
*b
)
962 if( a
->type
!=MULTITERMINAL
) return 0;
963 if( b
->type
!=MULTITERMINAL
) return 0;
964 if( a
->nsubsym
!=b
->nsubsym
) return 0;
965 for(i
=0; i
<a
->nsubsym
; i
++){
966 if( a
->subsym
[i
]!=b
->subsym
[i
] ) return 0;
971 /* Construct all successor states to the given state. A "successor"
972 ** state is any state which can be reached by a shift action.
974 PRIVATE
void buildshifts(struct lemon
*lemp
, struct state
*stp
)
976 struct config
*cfp
; /* For looping thru the config closure of "stp" */
977 struct config
*bcfp
; /* For the inner loop on config closure of "stp" */
978 struct config
*newcfg
; /* */
979 struct symbol
*sp
; /* Symbol following the dot in configuration "cfp" */
980 struct symbol
*bsp
; /* Symbol following the dot in configuration "bcfp" */
981 struct state
*newstp
; /* A pointer to a successor state */
983 /* Each configuration becomes complete after it contibutes to a successor
984 ** state. Initially, all configurations are incomplete */
985 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
) cfp
->status
= INCOMPLETE
;
987 /* Loop through all configurations of the state "stp" */
988 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
989 if( cfp
->status
==COMPLETE
) continue; /* Already used by inner loop */
990 if( cfp
->dot
>=cfp
->rp
->nrhs
) continue; /* Can't shift this config */
991 Configlist_reset(); /* Reset the new config set */
992 sp
= cfp
->rp
->rhs
[cfp
->dot
]; /* Symbol after the dot */
994 /* For every configuration in the state "stp" which has the symbol "sp"
995 ** following its dot, add the same configuration to the basis set under
996 ** construction but with the dot shifted one symbol to the right. */
997 for(bcfp
=cfp
; bcfp
; bcfp
=bcfp
->next
){
998 if( bcfp
->status
==COMPLETE
) continue; /* Already used */
999 if( bcfp
->dot
>=bcfp
->rp
->nrhs
) continue; /* Can't shift this one */
1000 bsp
= bcfp
->rp
->rhs
[bcfp
->dot
]; /* Get symbol after dot */
1001 if( !same_symbol(bsp
,sp
) ) continue; /* Must be same as for "cfp" */
1002 bcfp
->status
= COMPLETE
; /* Mark this config as used */
1003 newcfg
= Configlist_addbasis(bcfp
->rp
,bcfp
->dot
+1);
1004 Plink_add(&newcfg
->bplp
,bcfp
);
1007 /* Get a pointer to the state described by the basis configuration set
1008 ** constructed in the preceding loop */
1009 newstp
= getstate(lemp
);
1011 /* The state "newstp" is reached from the state "stp" by a shift action
1012 ** on the symbol "sp" */
1013 if( sp
->type
==MULTITERMINAL
){
1015 for(i
=0; i
<sp
->nsubsym
; i
++){
1016 Action_add(&stp
->ap
,SHIFT
,sp
->subsym
[i
],(char*)newstp
);
1019 Action_add(&stp
->ap
,SHIFT
,sp
,(char *)newstp
);
1025 ** Construct the propagation links
1027 void FindLinks(struct lemon
*lemp
)
1030 struct config
*cfp
, *other
;
1034 /* Housekeeping detail:
1035 ** Add to every propagate link a pointer back to the state to
1036 ** which the link is attached. */
1037 for(i
=0; i
<lemp
->nstate
; i
++){
1038 stp
= lemp
->sorted
[i
];
1039 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1044 /* Convert all backlinks into forward links. Only the forward
1045 ** links are used in the follow-set computation. */
1046 for(i
=0; i
<lemp
->nstate
; i
++){
1047 stp
= lemp
->sorted
[i
];
1048 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1049 for(plp
=cfp
->bplp
; plp
; plp
=plp
->next
){
1051 Plink_add(&other
->fplp
,cfp
);
1057 /* Compute all followsets.
1059 ** A followset is the set of all symbols which can come immediately
1060 ** after a configuration.
1062 void FindFollowSets(struct lemon
*lemp
)
1070 for(i
=0; i
<lemp
->nstate
; i
++){
1071 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1072 cfp
->status
= INCOMPLETE
;
1078 for(i
=0; i
<lemp
->nstate
; i
++){
1079 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1080 if( cfp
->status
==COMPLETE
) continue;
1081 for(plp
=cfp
->fplp
; plp
; plp
=plp
->next
){
1082 change
= SetUnion(plp
->cfp
->fws
,cfp
->fws
);
1084 plp
->cfp
->status
= INCOMPLETE
;
1088 cfp
->status
= COMPLETE
;
1094 static int resolve_conflict(struct action
*,struct action
*);
1096 /* Compute the reduce actions, and resolve conflicts.
1098 void FindActions(struct lemon
*lemp
)
1106 /* Add all of the reduce actions
1107 ** A reduce action is added for each element of the followset of
1108 ** a configuration which has its dot at the extreme right.
1110 for(i
=0; i
<lemp
->nstate
; i
++){ /* Loop over all states */
1111 stp
= lemp
->sorted
[i
];
1112 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){ /* Loop over all configurations */
1113 if( cfp
->rp
->nrhs
==cfp
->dot
){ /* Is dot at extreme right? */
1114 for(j
=0; j
<lemp
->nterminal
; j
++){
1115 if( SetFind(cfp
->fws
,j
) ){
1116 /* Add a reduce action to the state "stp" which will reduce by the
1117 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
1118 Action_add(&stp
->ap
,REDUCE
,lemp
->symbols
[j
],(char *)cfp
->rp
);
1125 /* Add the accepting token */
1127 sp
= Symbol_find(lemp
->start
);
1128 if( sp
==0 ) sp
= lemp
->startRule
->lhs
;
1130 sp
= lemp
->startRule
->lhs
;
1132 /* Add to the first state (which is always the starting state of the
1133 ** finite state machine) an action to ACCEPT if the lookahead is the
1134 ** start nonterminal. */
1135 Action_add(&lemp
->sorted
[0]->ap
,ACCEPT
,sp
,0);
1137 /* Resolve conflicts */
1138 for(i
=0; i
<lemp
->nstate
; i
++){
1139 struct action
*ap
, *nap
;
1140 stp
= lemp
->sorted
[i
];
1141 /* assert( stp->ap ); */
1142 stp
->ap
= Action_sort(stp
->ap
);
1143 for(ap
=stp
->ap
; ap
&& ap
->next
; ap
=ap
->next
){
1144 for(nap
=ap
->next
; nap
&& nap
->sp
==ap
->sp
; nap
=nap
->next
){
1145 /* The two actions "ap" and "nap" have the same lookahead.
1146 ** Figure out which one should be used */
1147 lemp
->nconflict
+= resolve_conflict(ap
,nap
);
1152 /* Report an error for each rule that can never be reduced. */
1153 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->canReduce
= LEMON_FALSE
;
1154 for(i
=0; i
<lemp
->nstate
; i
++){
1156 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
1157 if( ap
->type
==REDUCE
) ap
->x
.rp
->canReduce
= LEMON_TRUE
;
1160 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
1161 if( rp
->canReduce
) continue;
1162 ErrorMsg(lemp
->filename
,rp
->ruleline
,"This rule can not be reduced.\n");
1167 /* Resolve a conflict between the two given actions. If the
1168 ** conflict can't be resolved, return non-zero.
1171 ** To resolve a conflict, first look to see if either action
1172 ** is on an error rule. In that case, take the action which
1173 ** is not associated with the error rule. If neither or both
1174 ** actions are associated with an error rule, then try to
1175 ** use precedence to resolve the conflict.
1177 ** If either action is a SHIFT, then it must be apx. This
1178 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1180 static int resolve_conflict(
1184 struct symbol
*spx
, *spy
;
1186 assert( apx
->sp
==apy
->sp
); /* Otherwise there would be no conflict */
1187 if( apx
->type
==SHIFT
&& apy
->type
==SHIFT
){
1188 apy
->type
= SSCONFLICT
;
1191 if( apx
->type
==SHIFT
&& apy
->type
==REDUCE
){
1193 spy
= apy
->x
.rp
->precsym
;
1194 if( spy
==0 || spx
->prec
<0 || spy
->prec
<0 ){
1195 /* Not enough precedence information. */
1196 apy
->type
= SRCONFLICT
;
1198 }else if( spx
->prec
>spy
->prec
){ /* higher precedence wins */
1199 apy
->type
= RD_RESOLVED
;
1200 }else if( spx
->prec
<spy
->prec
){
1201 apx
->type
= SH_RESOLVED
;
1202 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==RIGHT
){ /* Use operator */
1203 apy
->type
= RD_RESOLVED
; /* associativity */
1204 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==LEFT
){ /* to break tie */
1205 apx
->type
= SH_RESOLVED
;
1207 assert( spx
->prec
==spy
->prec
&& spx
->assoc
==NONE
);
1210 }else if( apx
->type
==REDUCE
&& apy
->type
==REDUCE
){
1211 spx
= apx
->x
.rp
->precsym
;
1212 spy
= apy
->x
.rp
->precsym
;
1213 if( spx
==0 || spy
==0 || spx
->prec
<0 ||
1214 spy
->prec
<0 || spx
->prec
==spy
->prec
){
1215 apy
->type
= RRCONFLICT
;
1217 }else if( spx
->prec
>spy
->prec
){
1218 apy
->type
= RD_RESOLVED
;
1219 }else if( spx
->prec
<spy
->prec
){
1220 apx
->type
= RD_RESOLVED
;
1224 apx
->type
==SH_RESOLVED
||
1225 apx
->type
==RD_RESOLVED
||
1226 apx
->type
==SSCONFLICT
||
1227 apx
->type
==SRCONFLICT
||
1228 apx
->type
==RRCONFLICT
||
1229 apy
->type
==SH_RESOLVED
||
1230 apy
->type
==RD_RESOLVED
||
1231 apy
->type
==SSCONFLICT
||
1232 apy
->type
==SRCONFLICT
||
1233 apy
->type
==RRCONFLICT
1235 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1236 ** REDUCEs on the list. If we reach this point it must be because
1237 ** the parser conflict had already been resolved. */
1241 /********************* From the file "configlist.c" *************************/
1243 ** Routines to processing a configuration list and building a state
1244 ** in the LEMON parser generator.
1247 static struct config
*freelist
= 0; /* List of free configurations */
1248 static struct config
*current
= 0; /* Top of list of configurations */
1249 static struct config
**currentend
= 0; /* Last on list of configs */
1250 static struct config
*basis
= 0; /* Top of list of basis configs */
1251 static struct config
**basisend
= 0; /* End of list of basis configs */
1253 /* Return a pointer to a new configuration */
1254 PRIVATE
struct config
*newconfig(void){
1255 struct config
*newcfg
;
1259 freelist
= (struct config
*)calloc( amt
, sizeof(struct config
) );
1261 fprintf(stderr
,"Unable to allocate memory for a new configuration.");
1264 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
1265 freelist
[amt
-1].next
= 0;
1268 freelist
= freelist
->next
;
1272 /* The configuration "old" is no longer used */
1273 PRIVATE
void deleteconfig(struct config
*old
)
1275 old
->next
= freelist
;
1279 /* Initialized the configuration list builder */
1280 void Configlist_init(void){
1282 currentend
= ¤t
;
1289 /* Initialized the configuration list builder */
1290 void Configlist_reset(void){
1292 currentend
= ¤t
;
1295 Configtable_clear(0);
1299 /* Add another configuration to the configuration list */
1300 struct config
*Configlist_add(
1301 struct rule
*rp
, /* The rule */
1302 int dot
/* Index into the RHS of the rule where the dot goes */
1304 struct config
*cfp
, model
;
1306 assert( currentend
!=0 );
1309 cfp
= Configtable_find(&model
);
1314 cfp
->fws
= SetNew();
1316 cfp
->fplp
= cfp
->bplp
= 0;
1320 currentend
= &cfp
->next
;
1321 Configtable_insert(cfp
);
1326 /* Add a basis configuration to the configuration list */
1327 struct config
*Configlist_addbasis(struct rule
*rp
, int dot
)
1329 struct config
*cfp
, model
;
1331 assert( basisend
!=0 );
1332 assert( currentend
!=0 );
1335 cfp
= Configtable_find(&model
);
1340 cfp
->fws
= SetNew();
1342 cfp
->fplp
= cfp
->bplp
= 0;
1346 currentend
= &cfp
->next
;
1348 basisend
= &cfp
->bp
;
1349 Configtable_insert(cfp
);
1354 /* Compute the closure of the configuration list */
1355 void Configlist_closure(struct lemon
*lemp
)
1357 struct config
*cfp
, *newcfp
;
1358 struct rule
*rp
, *newrp
;
1359 struct symbol
*sp
, *xsp
;
1362 assert( currentend
!=0 );
1363 for(cfp
=current
; cfp
; cfp
=cfp
->next
){
1366 if( dot
>=rp
->nrhs
) continue;
1368 if( sp
->type
==NONTERMINAL
){
1369 if( sp
->rule
==0 && sp
!=lemp
->errsym
){
1370 ErrorMsg(lemp
->filename
,rp
->line
,"Nonterminal \"%s\" has no rules.",
1374 for(newrp
=sp
->rule
; newrp
; newrp
=newrp
->nextlhs
){
1375 newcfp
= Configlist_add(newrp
,0);
1376 for(i
=dot
+1; i
<rp
->nrhs
; i
++){
1378 if( xsp
->type
==TERMINAL
){
1379 SetAdd(newcfp
->fws
,xsp
->index
);
1381 }else if( xsp
->type
==MULTITERMINAL
){
1383 for(k
=0; k
<xsp
->nsubsym
; k
++){
1384 SetAdd(newcfp
->fws
, xsp
->subsym
[k
]->index
);
1388 SetUnion(newcfp
->fws
,xsp
->firstset
);
1389 if( xsp
->lambda
==LEMON_FALSE
) break;
1392 if( i
==rp
->nrhs
) Plink_add(&cfp
->fplp
,newcfp
);
1399 /* Sort the configuration list */
1400 void Configlist_sort(void){
1401 current
= (struct config
*)msort((char*)current
,(char**)&(current
->next
),
1407 /* Sort the basis configuration list */
1408 void Configlist_sortbasis(void){
1409 basis
= (struct config
*)msort((char*)current
,(char**)&(current
->bp
),
1415 /* Return a pointer to the head of the configuration list and
1416 ** reset the list */
1417 struct config
*Configlist_return(void){
1425 /* Return a pointer to the head of the configuration list and
1426 ** reset the list */
1427 struct config
*Configlist_basis(void){
1435 /* Free all elements of the given configuration list */
1436 void Configlist_eat(struct config
*cfp
)
1438 struct config
*nextcfp
;
1439 for(; cfp
; cfp
=nextcfp
){
1440 nextcfp
= cfp
->next
;
1441 assert( cfp
->fplp
==0 );
1442 assert( cfp
->bplp
==0 );
1443 if( cfp
->fws
) SetFree(cfp
->fws
);
1448 /***************** From the file "error.c" *********************************/
1450 ** Code for printing error message.
1453 void ErrorMsg(const char *filename
, int lineno
, const char *format
, ...){
1455 fprintf(stderr
, "%s:%d: ", filename
, lineno
);
1456 va_start(ap
, format
);
1457 vfprintf(stderr
,format
,ap
);
1459 fprintf(stderr
, "\n");
1461 /**************** From the file "main.c" ************************************/
1463 ** Main program file for the LEMON parser generator.
1466 /* Report an out-of-memory condition and abort. This function
1467 ** is used mostly by the "MemoryCheck" macro in struct.h
1469 void memory_error(void){
1470 fprintf(stderr
,"Out of memory. Aborting...\n");
1474 static int nDefine
= 0; /* Number of -D options on the command line */
1475 static char **azDefine
= 0; /* Name of the -D macros */
1477 /* This routine is called with the argument to each -D command-line option.
1478 ** Add the macro defined to the azDefine array.
1480 static void handle_D_option(char *z
){
1483 azDefine
= (char **) realloc(azDefine
, sizeof(azDefine
[0])*nDefine
);
1485 fprintf(stderr
,"out of memory\n");
1488 paz
= &azDefine
[nDefine
-1];
1489 *paz
= (char *) malloc( lemonStrlen(z
)+1 );
1491 fprintf(stderr
,"out of memory\n");
1494 lemon_strcpy(*paz
, z
);
1495 for(z
=*paz
; *z
&& *z
!='='; z
++){}
1499 static char *user_templatename
= NULL
;
1500 static void handle_T_option(char *z
){
1501 user_templatename
= (char *) malloc( lemonStrlen(z
)+1 );
1502 if( user_templatename
==0 ){
1505 lemon_strcpy(user_templatename
, z
);
1508 /* Merge together to lists of rules ordered by rule.iRule */
1509 static struct rule
*Rule_merge(struct rule
*pA
, struct rule
*pB
){
1510 struct rule
*pFirst
= 0;
1511 struct rule
**ppPrev
= &pFirst
;
1513 if( pA
->iRule
<pB
->iRule
){
1532 ** Sort a list of rules in order of increasing iRule value
1534 static struct rule
*Rule_sort(struct rule
*rp
){
1538 memset(x
, 0, sizeof(x
));
1542 for(i
=0; i
<sizeof(x
)/sizeof(x
[0]) && x
[i
]; i
++){
1543 rp
= Rule_merge(x
[i
], rp
);
1550 for(i
=0; i
<sizeof(x
)/sizeof(x
[0]); i
++){
1551 rp
= Rule_merge(x
[i
], rp
);
1556 /* forward reference */
1557 static const char *minimum_size_type(int lwr
, int upr
, int *pnByte
);
1559 /* Print a single line of the "Parser Stats" output
1561 static void stats_line(const char *zLabel
, int iValue
){
1562 int nLabel
= lemonStrlen(zLabel
);
1563 printf(" %s%.*s %5d\n", zLabel
,
1564 35-nLabel
, "................................",
1568 /* The main program. Parse the command line and do it... */
1569 int main(int argc
, char **argv
)
1571 static int version
= 0;
1572 static int rpflag
= 0;
1573 static int basisflag
= 0;
1574 static int compress
= 0;
1575 static int quiet
= 0;
1576 static int statistics
= 0;
1577 static int mhflag
= 0;
1578 static int nolinenosflag
= 0;
1579 static int noResort
= 0;
1580 static struct s_options options
[] = {
1581 {OPT_FLAG
, "b", (char*)&basisflag
, "Print only the basis in report."},
1582 {OPT_FLAG
, "c", (char*)&compress
, "Don't compress the action table."},
1583 {OPT_FSTR
, "D", (char*)handle_D_option
, "Define an %ifdef macro."},
1584 {OPT_FSTR
, "f", 0, "Ignored. (Placeholder for -f compiler options.)"},
1585 {OPT_FLAG
, "g", (char*)&rpflag
, "Print grammar without actions."},
1586 {OPT_FSTR
, "I", 0, "Ignored. (Placeholder for '-I' compiler options.)"},
1587 {OPT_FLAG
, "m", (char*)&mhflag
, "Output a makeheaders compatible file."},
1588 {OPT_FLAG
, "l", (char*)&nolinenosflag
, "Do not print #line statements."},
1589 {OPT_FSTR
, "O", 0, "Ignored. (Placeholder for '-O' compiler options.)"},
1590 {OPT_FLAG
, "p", (char*)&showPrecedenceConflict
,
1591 "Show conflicts resolved by precedence rules"},
1592 {OPT_FLAG
, "q", (char*)&quiet
, "(Quiet) Don't print the report file."},
1593 {OPT_FLAG
, "r", (char*)&noResort
, "Do not sort or renumber states"},
1594 {OPT_FLAG
, "s", (char*)&statistics
,
1595 "Print parser stats to standard output."},
1596 {OPT_FLAG
, "x", (char*)&version
, "Print the version number."},
1597 {OPT_FSTR
, "T", (char*)handle_T_option
, "Specify a template file."},
1598 {OPT_FSTR
, "W", 0, "Ignored. (Placeholder for '-W' compiler options.)"},
1606 OptInit(argv
,options
,stderr
);
1608 printf("Lemon version 1.0\n");
1611 if( OptNArgs()!=1 ){
1612 fprintf(stderr
,"Exactly one filename argument is required.\n");
1615 memset(&lem
, 0, sizeof(lem
));
1618 /* Initialize the machine */
1622 lem
.argv0
= argv
[0];
1623 lem
.filename
= OptArg(0);
1624 lem
.basisflag
= basisflag
;
1625 lem
.nolinenosflag
= nolinenosflag
;
1627 lem
.errsym
= Symbol_new("error");
1628 lem
.errsym
->useCnt
= 0;
1630 /* Parse the input file */
1632 if( lem
.errorcnt
) exit(lem
.errorcnt
);
1634 fprintf(stderr
,"Empty grammar.\n");
1638 /* Count and index the symbols of the grammar */
1639 Symbol_new("{default}");
1640 lem
.nsymbol
= Symbol_count();
1641 lem
.symbols
= Symbol_arrayof();
1642 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1643 qsort(lem
.symbols
,lem
.nsymbol
,sizeof(struct symbol
*), Symbolcmpp
);
1644 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1645 while( lem
.symbols
[i
-1]->type
==MULTITERMINAL
){ i
--; }
1646 assert( strcmp(lem
.symbols
[i
-1]->name
,"{default}")==0 );
1647 lem
.nsymbol
= i
- 1;
1648 for(i
=1; ISUPPER(lem
.symbols
[i
]->name
[0]); i
++);
1651 /* Assign sequential rule numbers. Start with 0. Put rules that have no
1652 ** reduce action C-code associated with them last, so that the switch()
1653 ** statement that selects reduction actions will have a smaller jump table.
1655 for(i
=0, rp
=lem
.rule
; rp
; rp
=rp
->next
){
1656 rp
->iRule
= rp
->code
? i
++ : -1;
1658 for(rp
=lem
.rule
; rp
; rp
=rp
->next
){
1659 if( rp
->iRule
<0 ) rp
->iRule
= i
++;
1661 lem
.startRule
= lem
.rule
;
1662 lem
.rule
= Rule_sort(lem
.rule
);
1664 /* Generate a reprint of the grammar, if requested on the command line */
1668 /* Initialize the size for all follow and first sets */
1669 SetSize(lem
.nterminal
+1);
1671 /* Find the precedence for every production rule (that has one) */
1672 FindRulePrecedences(&lem
);
1674 /* Compute the lambda-nonterminals and the first-sets for every
1676 FindFirstSets(&lem
);
1678 /* Compute all LR(0) states. Also record follow-set propagation
1679 ** links so that the follow-set can be computed later */
1682 lem
.sorted
= State_arrayof();
1684 /* Tie up loose ends on the propagation links */
1687 /* Compute the follow set of every reducible configuration */
1688 FindFollowSets(&lem
);
1690 /* Compute the action tables */
1693 /* Compress the action tables */
1694 if( compress
==0 ) CompressTables(&lem
);
1696 /* Reorder and renumber the states so that states with fewer choices
1697 ** occur at the end. This is an optimization that helps make the
1698 ** generated parser tables smaller. */
1699 if( noResort
==0 ) ResortStates(&lem
);
1701 /* Generate a report of the parser generated. (the "y.output" file) */
1702 if( !quiet
) ReportOutput(&lem
);
1704 /* Generate the source code for the parser */
1705 ReportTable(&lem
, mhflag
);
1707 /* Produce a header file for use by the scanner. (This step is
1708 ** omitted if the "-m" option is used because makeheaders will
1709 ** generate the file for us.) */
1710 if( !mhflag
) ReportHeader(&lem
);
1713 printf("Parser statistics:\n");
1714 stats_line("terminal symbols", lem
.nterminal
);
1715 stats_line("non-terminal symbols", lem
.nsymbol
- lem
.nterminal
);
1716 stats_line("total symbols", lem
.nsymbol
);
1717 stats_line("rules", lem
.nrule
);
1718 stats_line("states", lem
.nxstate
);
1719 stats_line("conflicts", lem
.nconflict
);
1720 stats_line("action table entries", lem
.nactiontab
);
1721 stats_line("total table size (bytes)", lem
.tablesize
);
1723 if( lem
.nconflict
> 0 ){
1724 fprintf(stderr
,"%d parsing conflicts.\n",lem
.nconflict
);
1727 /* return 0 on success, 1 on failure. */
1728 exitcode
= ((lem
.errorcnt
> 0) || (lem
.nconflict
> 0)) ? 1 : 0;
1732 /******************** From the file "msort.c" *******************************/
1734 ** A generic merge-sort program.
1737 ** Let "ptr" be a pointer to some structure which is at the head of
1738 ** a null-terminated list. Then to sort the list call:
1740 ** ptr = msort(ptr,&(ptr->next),cmpfnc);
1742 ** In the above, "cmpfnc" is a pointer to a function which compares
1743 ** two instances of the structure and returns an integer, as in
1744 ** strcmp. The second argument is a pointer to the pointer to the
1745 ** second element of the linked list. This address is used to compute
1746 ** the offset to the "next" field within the structure. The offset to
1747 ** the "next" field must be constant for all structures in the list.
1749 ** The function returns a new pointer which is the head of the list
1757 ** Return a pointer to the next structure in the linked list.
1759 #define NEXT(A) (*(char**)(((char*)A)+offset))
1763 ** a: A sorted, null-terminated linked list. (May be null).
1764 ** b: A sorted, null-terminated linked list. (May be null).
1765 ** cmp: A pointer to the comparison function.
1766 ** offset: Offset in the structure to the "next" field.
1769 ** A pointer to the head of a sorted list containing the elements
1773 ** The "next" pointers for elements in the lists a and b are
1779 int (*cmp
)(const char*,const char*),
1789 if( (*cmp
)(a
,b
)<=0 ){
1798 if( (*cmp
)(a
,b
)<=0 ){
1808 if( a
) NEXT(ptr
) = a
;
1816 ** list: Pointer to a singly-linked list of structures.
1817 ** next: Pointer to pointer to the second element of the list.
1818 ** cmp: A comparison function.
1821 ** A pointer to the head of a sorted list containing the elements
1822 ** orginally in list.
1825 ** The "next" pointers for elements in list are changed.
1831 int (*cmp
)(const char*,const char*)
1833 unsigned long offset
;
1835 char *set
[LISTSIZE
];
1837 offset
= (unsigned long)((char*)next
- (char*)list
);
1838 for(i
=0; i
<LISTSIZE
; i
++) set
[i
] = 0;
1843 for(i
=0; i
<LISTSIZE
-1 && set
[i
]!=0; i
++){
1844 ep
= merge(ep
,set
[i
],cmp
,offset
);
1850 for(i
=0; i
<LISTSIZE
; i
++) if( set
[i
] ) ep
= merge(set
[i
],ep
,cmp
,offset
);
1853 /************************ From the file "option.c" **************************/
1855 static struct s_options
*op
;
1856 static FILE *errstream
;
1858 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1861 ** Print the command line with a carrot pointing to the k-th character
1862 ** of the n-th field.
1864 static void errline(int n
, int k
, FILE *err
)
1867 if( argv
[0] ) fprintf(err
,"%s",argv
[0]);
1868 spcnt
= lemonStrlen(argv
[0]) + 1;
1869 for(i
=1; i
<n
&& argv
[i
]; i
++){
1870 fprintf(err
," %s",argv
[i
]);
1871 spcnt
+= lemonStrlen(argv
[i
])+1;
1874 for(; argv
[i
]; i
++) fprintf(err
," %s",argv
[i
]);
1876 fprintf(err
,"\n%*s^-- here\n",spcnt
,"");
1878 fprintf(err
,"\n%*shere --^\n",spcnt
-7,"");
1883 ** Return the index of the N-th non-switch argument. Return -1
1884 ** if N is out of range.
1886 static int argindex(int n
)
1890 if( argv
!=0 && *argv
!=0 ){
1891 for(i
=1; argv
[i
]; i
++){
1892 if( dashdash
|| !ISOPT(argv
[i
]) ){
1893 if( n
==0 ) return i
;
1896 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
1902 static char emsg
[] = "Command line syntax error: ";
1905 ** Process a flag command line argument.
1907 static int handleflags(int i
, FILE *err
)
1912 for(j
=0; op
[j
].label
; j
++){
1913 if( strncmp(&argv
[i
][1],op
[j
].label
,lemonStrlen(op
[j
].label
))==0 ) break;
1915 v
= argv
[i
][0]=='-' ? 1 : 0;
1916 if( op
[j
].label
==0 ){
1918 fprintf(err
,"%sundefined option.\n",emsg
);
1922 }else if( op
[j
].arg
==0 ){
1923 /* Ignore this option */
1924 }else if( op
[j
].type
==OPT_FLAG
){
1925 *((int*)op
[j
].arg
) = v
;
1926 }else if( op
[j
].type
==OPT_FFLAG
){
1927 (*(void(*)(int))(op
[j
].arg
))(v
);
1928 }else if( op
[j
].type
==OPT_FSTR
){
1929 (*(void(*)(char *))(op
[j
].arg
))(&argv
[i
][2]);
1932 fprintf(err
,"%smissing argument on switch.\n",emsg
);
1941 ** Process a command line switch which has an argument.
1943 static int handleswitch(int i
, FILE *err
)
1951 cp
= strchr(argv
[i
],'=');
1954 for(j
=0; op
[j
].label
; j
++){
1955 if( strcmp(argv
[i
],op
[j
].label
)==0 ) break;
1958 if( op
[j
].label
==0 ){
1960 fprintf(err
,"%sundefined option.\n",emsg
);
1966 switch( op
[j
].type
){
1970 fprintf(err
,"%soption requires an argument.\n",emsg
);
1977 dv
= strtod(cp
,&end
);
1981 "%sillegal character in floating-point argument.\n",emsg
);
1982 errline(i
,(int)((char*)end
-(char*)argv
[i
]),err
);
1989 lv
= strtol(cp
,&end
,0);
1992 fprintf(err
,"%sillegal character in integer argument.\n",emsg
);
1993 errline(i
,(int)((char*)end
-(char*)argv
[i
]),err
);
2003 switch( op
[j
].type
){
2008 *(double*)(op
[j
].arg
) = dv
;
2011 (*(void(*)(double))(op
[j
].arg
))(dv
);
2014 *(int*)(op
[j
].arg
) = lv
;
2017 (*(void(*)(int))(op
[j
].arg
))((int)lv
);
2020 *(char**)(op
[j
].arg
) = sv
;
2023 (*(void(*)(char *))(op
[j
].arg
))(sv
);
2030 int OptInit(char **a
, struct s_options
*o
, FILE *err
)
2036 if( argv
&& *argv
&& op
){
2038 for(i
=1; argv
[i
]; i
++){
2039 if( argv
[i
][0]=='+' || argv
[i
][0]=='-' ){
2040 errcnt
+= handleflags(i
,err
);
2041 }else if( strchr(argv
[i
],'=') ){
2042 errcnt
+= handleswitch(i
,err
);
2047 fprintf(err
,"Valid command line options for \"%s\" are:\n",*a
);
2058 if( argv
!=0 && argv
[0]!=0 ){
2059 for(i
=1; argv
[i
]; i
++){
2060 if( dashdash
|| !ISOPT(argv
[i
]) ) cnt
++;
2061 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
2071 return i
>=0 ? argv
[i
] : 0;
2078 if( i
>=0 ) errline(i
,0,errstream
);
2081 void OptPrint(void){
2085 for(i
=0; op
[i
].label
; i
++){
2086 len
= lemonStrlen(op
[i
].label
) + 1;
2087 switch( op
[i
].type
){
2093 len
+= 9; /* length of "<integer>" */
2097 len
+= 6; /* length of "<real>" */
2101 len
+= 8; /* length of "<string>" */
2104 if( len
>max
) max
= len
;
2106 for(i
=0; op
[i
].label
; i
++){
2107 switch( op
[i
].type
){
2110 fprintf(errstream
," -%-*s %s\n",max
,op
[i
].label
,op
[i
].message
);
2114 fprintf(errstream
," -%s<integer>%*s %s\n",op
[i
].label
,
2115 (int)(max
-lemonStrlen(op
[i
].label
)-9),"",op
[i
].message
);
2119 fprintf(errstream
," -%s<real>%*s %s\n",op
[i
].label
,
2120 (int)(max
-lemonStrlen(op
[i
].label
)-6),"",op
[i
].message
);
2124 fprintf(errstream
," -%s<string>%*s %s\n",op
[i
].label
,
2125 (int)(max
-lemonStrlen(op
[i
].label
)-8),"",op
[i
].message
);
2130 /*********************** From the file "parse.c" ****************************/
2132 ** Input file parser for the LEMON parser generator.
2135 /* The state of the parser */
2138 WAITING_FOR_DECL_OR_RULE
,
2139 WAITING_FOR_DECL_KEYWORD
,
2140 WAITING_FOR_DECL_ARG
,
2141 WAITING_FOR_PRECEDENCE_SYMBOL
,
2151 RESYNC_AFTER_RULE_ERROR
,
2152 RESYNC_AFTER_DECL_ERROR
,
2153 WAITING_FOR_DESTRUCTOR_SYMBOL
,
2154 WAITING_FOR_DATATYPE_SYMBOL
,
2155 WAITING_FOR_FALLBACK_ID
,
2156 WAITING_FOR_WILDCARD_ID
,
2157 WAITING_FOR_CLASS_ID
,
2158 WAITING_FOR_CLASS_TOKEN
2161 char *filename
; /* Name of the input file */
2162 int tokenlineno
; /* Linenumber at which current token starts */
2163 int errorcnt
; /* Number of errors so far */
2164 char *tokenstart
; /* Text of current token */
2165 struct lemon
*gp
; /* Global state vector */
2166 enum e_state state
; /* The state of the parser */
2167 struct symbol
*fallback
; /* The fallback token */
2168 struct symbol
*tkclass
; /* Token class symbol */
2169 struct symbol
*lhs
; /* Left-hand side of current rule */
2170 const char *lhsalias
; /* Alias for the LHS */
2171 int nrhs
; /* Number of right-hand side symbols seen */
2172 struct symbol
*rhs
[MAXRHS
]; /* RHS symbols */
2173 const char *alias
[MAXRHS
]; /* Aliases for each RHS symbol (or NULL) */
2174 struct rule
*prevrule
; /* Previous rule parsed */
2175 const char *declkeyword
; /* Keyword of a declaration */
2176 char **declargslot
; /* Where the declaration argument should be put */
2177 int insertLineMacro
; /* Add #line before declaration insert */
2178 int *decllinenoslot
; /* Where to write declaration line number */
2179 enum e_assoc declassoc
; /* Assign this association to decl arguments */
2180 int preccounter
; /* Assign this precedence to decl arguments */
2181 struct rule
*firstrule
; /* Pointer to first rule in the grammar */
2182 struct rule
*lastrule
; /* Pointer to the most recently parsed rule */
2185 /* Parse a single token */
2186 static void parseonetoken(struct pstate
*psp
)
2189 x
= Strsafe(psp
->tokenstart
); /* Save the token permanently */
2191 printf("%s:%d: Token=[%s] state=%d\n",psp
->filename
,psp
->tokenlineno
,
2194 switch( psp
->state
){
2197 psp
->preccounter
= 0;
2198 psp
->firstrule
= psp
->lastrule
= 0;
2200 /* Fall thru to next case */
2201 case WAITING_FOR_DECL_OR_RULE
:
2203 psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2204 }else if( ISLOWER(x
[0]) ){
2205 psp
->lhs
= Symbol_new(x
);
2208 psp
->state
= WAITING_FOR_ARROW
;
2209 }else if( x
[0]=='{' ){
2210 if( psp
->prevrule
==0 ){
2211 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2212 "There is no prior rule upon which to attach the code \
2213 fragment which begins on this line.");
2215 }else if( psp
->prevrule
->code
!=0 ){
2216 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2217 "Code fragment beginning on this line is not the first \
2218 to follow the previous rule.");
2221 psp
->prevrule
->line
= psp
->tokenlineno
;
2222 psp
->prevrule
->code
= &x
[1];
2223 psp
->prevrule
->noCode
= 0;
2225 }else if( x
[0]=='[' ){
2226 psp
->state
= PRECEDENCE_MARK_1
;
2228 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2229 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2234 case PRECEDENCE_MARK_1
:
2235 if( !ISUPPER(x
[0]) ){
2236 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2237 "The precedence symbol must be a terminal.");
2239 }else if( psp
->prevrule
==0 ){
2240 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2241 "There is no prior rule to assign precedence \"[%s]\".",x
);
2243 }else if( psp
->prevrule
->precsym
!=0 ){
2244 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2245 "Precedence mark on this line is not the first \
2246 to follow the previous rule.");
2249 psp
->prevrule
->precsym
= Symbol_new(x
);
2251 psp
->state
= PRECEDENCE_MARK_2
;
2253 case PRECEDENCE_MARK_2
:
2255 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2256 "Missing \"]\" on precedence mark.");
2259 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2261 case WAITING_FOR_ARROW
:
2262 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2263 psp
->state
= IN_RHS
;
2264 }else if( x
[0]=='(' ){
2265 psp
->state
= LHS_ALIAS_1
;
2267 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2268 "Expected to see a \":\" following the LHS symbol \"%s\".",
2271 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2275 if( ISALPHA(x
[0]) ){
2277 psp
->state
= LHS_ALIAS_2
;
2279 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2280 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2283 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2288 psp
->state
= LHS_ALIAS_3
;
2290 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2291 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2293 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2297 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2298 psp
->state
= IN_RHS
;
2300 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2301 "Missing \"->\" following: \"%s(%s)\".",
2302 psp
->lhs
->name
,psp
->lhsalias
);
2304 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2310 rp
= (struct rule
*)calloc( sizeof(struct rule
) +
2311 sizeof(struct symbol
*)*psp
->nrhs
+ sizeof(char*)*psp
->nrhs
, 1);
2313 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2314 "Can't allocate enough memory for this rule.");
2319 rp
->ruleline
= psp
->tokenlineno
;
2320 rp
->rhs
= (struct symbol
**)&rp
[1];
2321 rp
->rhsalias
= (const char**)&(rp
->rhs
[psp
->nrhs
]);
2322 for(i
=0; i
<psp
->nrhs
; i
++){
2323 rp
->rhs
[i
] = psp
->rhs
[i
];
2324 rp
->rhsalias
[i
] = psp
->alias
[i
];
2327 rp
->lhsalias
= psp
->lhsalias
;
2328 rp
->nrhs
= psp
->nrhs
;
2332 rp
->index
= psp
->gp
->nrule
++;
2333 rp
->nextlhs
= rp
->lhs
->rule
;
2336 if( psp
->firstrule
==0 ){
2337 psp
->firstrule
= psp
->lastrule
= rp
;
2339 psp
->lastrule
->next
= rp
;
2344 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2345 }else if( ISALPHA(x
[0]) ){
2346 if( psp
->nrhs
>=MAXRHS
){
2347 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2348 "Too many symbols on RHS of rule beginning at \"%s\".",
2351 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2353 psp
->rhs
[psp
->nrhs
] = Symbol_new(x
);
2354 psp
->alias
[psp
->nrhs
] = 0;
2357 }else if( (x
[0]=='|' || x
[0]=='/') && psp
->nrhs
>0 ){
2358 struct symbol
*msp
= psp
->rhs
[psp
->nrhs
-1];
2359 if( msp
->type
!=MULTITERMINAL
){
2360 struct symbol
*origsp
= msp
;
2361 msp
= (struct symbol
*) calloc(1,sizeof(*msp
));
2362 memset(msp
, 0, sizeof(*msp
));
2363 msp
->type
= MULTITERMINAL
;
2365 msp
->subsym
= (struct symbol
**) calloc(1,sizeof(struct symbol
*));
2366 msp
->subsym
[0] = origsp
;
2367 msp
->name
= origsp
->name
;
2368 psp
->rhs
[psp
->nrhs
-1] = msp
;
2371 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2372 sizeof(struct symbol
*)*msp
->nsubsym
);
2373 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(&x
[1]);
2374 if( ISLOWER(x
[1]) || ISLOWER(msp
->subsym
[0]->name
[0]) ){
2375 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2376 "Cannot form a compound containing a non-terminal");
2379 }else if( x
[0]=='(' && psp
->nrhs
>0 ){
2380 psp
->state
= RHS_ALIAS_1
;
2382 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2383 "Illegal character on RHS of rule: \"%s\".",x
);
2385 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2389 if( ISALPHA(x
[0]) ){
2390 psp
->alias
[psp
->nrhs
-1] = x
;
2391 psp
->state
= RHS_ALIAS_2
;
2393 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2394 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2395 x
,psp
->rhs
[psp
->nrhs
-1]->name
);
2397 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2402 psp
->state
= IN_RHS
;
2404 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2405 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2407 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2410 case WAITING_FOR_DECL_KEYWORD
:
2411 if( ISALPHA(x
[0]) ){
2412 psp
->declkeyword
= x
;
2413 psp
->declargslot
= 0;
2414 psp
->decllinenoslot
= 0;
2415 psp
->insertLineMacro
= 1;
2416 psp
->state
= WAITING_FOR_DECL_ARG
;
2417 if( strcmp(x
,"name")==0 ){
2418 psp
->declargslot
= &(psp
->gp
->name
);
2419 psp
->insertLineMacro
= 0;
2420 }else if( strcmp(x
,"include")==0 ){
2421 psp
->declargslot
= &(psp
->gp
->include
);
2422 }else if( strcmp(x
,"code")==0 ){
2423 psp
->declargslot
= &(psp
->gp
->extracode
);
2424 }else if( strcmp(x
,"token_destructor")==0 ){
2425 psp
->declargslot
= &psp
->gp
->tokendest
;
2426 }else if( strcmp(x
,"default_destructor")==0 ){
2427 psp
->declargslot
= &psp
->gp
->vardest
;
2428 }else if( strcmp(x
,"token_prefix")==0 ){
2429 psp
->declargslot
= &psp
->gp
->tokenprefix
;
2430 psp
->insertLineMacro
= 0;
2431 }else if( strcmp(x
,"syntax_error")==0 ){
2432 psp
->declargslot
= &(psp
->gp
->error
);
2433 }else if( strcmp(x
,"parse_accept")==0 ){
2434 psp
->declargslot
= &(psp
->gp
->accept
);
2435 }else if( strcmp(x
,"parse_failure")==0 ){
2436 psp
->declargslot
= &(psp
->gp
->failure
);
2437 }else if( strcmp(x
,"stack_overflow")==0 ){
2438 psp
->declargslot
= &(psp
->gp
->overflow
);
2439 }else if( strcmp(x
,"extra_argument")==0 ){
2440 psp
->declargslot
= &(psp
->gp
->arg
);
2441 psp
->insertLineMacro
= 0;
2442 }else if( strcmp(x
,"token_type")==0 ){
2443 psp
->declargslot
= &(psp
->gp
->tokentype
);
2444 psp
->insertLineMacro
= 0;
2445 }else if( strcmp(x
,"default_type")==0 ){
2446 psp
->declargslot
= &(psp
->gp
->vartype
);
2447 psp
->insertLineMacro
= 0;
2448 }else if( strcmp(x
,"stack_size")==0 ){
2449 psp
->declargslot
= &(psp
->gp
->stacksize
);
2450 psp
->insertLineMacro
= 0;
2451 }else if( strcmp(x
,"start_symbol")==0 ){
2452 psp
->declargslot
= &(psp
->gp
->start
);
2453 psp
->insertLineMacro
= 0;
2454 }else if( strcmp(x
,"left")==0 ){
2456 psp
->declassoc
= LEFT
;
2457 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2458 }else if( strcmp(x
,"right")==0 ){
2460 psp
->declassoc
= RIGHT
;
2461 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2462 }else if( strcmp(x
,"nonassoc")==0 ){
2464 psp
->declassoc
= NONE
;
2465 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2466 }else if( strcmp(x
,"destructor")==0 ){
2467 psp
->state
= WAITING_FOR_DESTRUCTOR_SYMBOL
;
2468 }else if( strcmp(x
,"type")==0 ){
2469 psp
->state
= WAITING_FOR_DATATYPE_SYMBOL
;
2470 }else if( strcmp(x
,"fallback")==0 ){
2472 psp
->state
= WAITING_FOR_FALLBACK_ID
;
2473 }else if( strcmp(x
,"wildcard")==0 ){
2474 psp
->state
= WAITING_FOR_WILDCARD_ID
;
2475 }else if( strcmp(x
,"token_class")==0 ){
2476 psp
->state
= WAITING_FOR_CLASS_ID
;
2478 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2479 "Unknown declaration keyword: \"%%%s\".",x
);
2481 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2484 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2485 "Illegal declaration keyword: \"%s\".",x
);
2487 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2490 case WAITING_FOR_DESTRUCTOR_SYMBOL
:
2491 if( !ISALPHA(x
[0]) ){
2492 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2493 "Symbol name missing after %%destructor keyword");
2495 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2497 struct symbol
*sp
= Symbol_new(x
);
2498 psp
->declargslot
= &sp
->destructor
;
2499 psp
->decllinenoslot
= &sp
->destLineno
;
2500 psp
->insertLineMacro
= 1;
2501 psp
->state
= WAITING_FOR_DECL_ARG
;
2504 case WAITING_FOR_DATATYPE_SYMBOL
:
2505 if( !ISALPHA(x
[0]) ){
2506 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2507 "Symbol name missing after %%type keyword");
2509 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2511 struct symbol
*sp
= Symbol_find(x
);
2512 if((sp
) && (sp
->datatype
)){
2513 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2514 "Symbol %%type \"%s\" already defined", x
);
2516 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2521 psp
->declargslot
= &sp
->datatype
;
2522 psp
->insertLineMacro
= 0;
2523 psp
->state
= WAITING_FOR_DECL_ARG
;
2527 case WAITING_FOR_PRECEDENCE_SYMBOL
:
2529 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2530 }else if( ISUPPER(x
[0]) ){
2534 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2535 "Symbol \"%s\" has already be given a precedence.",x
);
2538 sp
->prec
= psp
->preccounter
;
2539 sp
->assoc
= psp
->declassoc
;
2542 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2543 "Can't assign a precedence to \"%s\".",x
);
2547 case WAITING_FOR_DECL_ARG
:
2548 if( x
[0]=='{' || x
[0]=='\"' || ISALNUM(x
[0]) ){
2549 const char *zOld
, *zNew
;
2551 int nOld
, n
, nLine
= 0, nNew
, nBack
;
2555 if( zNew
[0]=='"' || zNew
[0]=='{' ) zNew
++;
2556 nNew
= lemonStrlen(zNew
);
2557 if( *psp
->declargslot
){
2558 zOld
= *psp
->declargslot
;
2562 nOld
= lemonStrlen(zOld
);
2563 n
= nOld
+ nNew
+ 20;
2564 addLineMacro
= !psp
->gp
->nolinenosflag
&& psp
->insertLineMacro
&&
2565 (psp
->decllinenoslot
==0 || psp
->decllinenoslot
[0]!=0);
2567 for(z
=psp
->filename
, nBack
=0; *z
; z
++){
2568 if( *z
=='\\' ) nBack
++;
2570 lemon_sprintf(zLine
, "#line %d ", psp
->tokenlineno
);
2571 nLine
= lemonStrlen(zLine
);
2572 n
+= nLine
+ lemonStrlen(psp
->filename
) + nBack
;
2574 *psp
->declargslot
= (char *) realloc(*psp
->declargslot
, n
);
2575 zBuf
= *psp
->declargslot
+ nOld
;
2577 if( nOld
&& zBuf
[-1]!='\n' ){
2580 memcpy(zBuf
, zLine
, nLine
);
2583 for(z
=psp
->filename
; *z
; z
++){
2592 if( psp
->decllinenoslot
&& psp
->decllinenoslot
[0]==0 ){
2593 psp
->decllinenoslot
[0] = psp
->tokenlineno
;
2595 memcpy(zBuf
, zNew
, nNew
);
2598 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2600 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2601 "Illegal argument to %%%s: %s",psp
->declkeyword
,x
);
2603 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2606 case WAITING_FOR_FALLBACK_ID
:
2608 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2609 }else if( !ISUPPER(x
[0]) ){
2610 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2611 "%%fallback argument \"%s\" should be a token", x
);
2614 struct symbol
*sp
= Symbol_new(x
);
2615 if( psp
->fallback
==0 ){
2617 }else if( sp
->fallback
){
2618 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2619 "More than one fallback assigned to token %s", x
);
2622 sp
->fallback
= psp
->fallback
;
2623 psp
->gp
->has_fallback
= 1;
2627 case WAITING_FOR_WILDCARD_ID
:
2629 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2630 }else if( !ISUPPER(x
[0]) ){
2631 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2632 "%%wildcard argument \"%s\" should be a token", x
);
2635 struct symbol
*sp
= Symbol_new(x
);
2636 if( psp
->gp
->wildcard
==0 ){
2637 psp
->gp
->wildcard
= sp
;
2639 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2640 "Extra wildcard to token: %s", x
);
2645 case WAITING_FOR_CLASS_ID
:
2646 if( !ISLOWER(x
[0]) ){
2647 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2648 "%%token_class must be followed by an identifier: ", x
);
2650 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2651 }else if( Symbol_find(x
) ){
2652 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2653 "Symbol \"%s\" already used", x
);
2655 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2657 psp
->tkclass
= Symbol_new(x
);
2658 psp
->tkclass
->type
= MULTITERMINAL
;
2659 psp
->state
= WAITING_FOR_CLASS_TOKEN
;
2662 case WAITING_FOR_CLASS_TOKEN
:
2664 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2665 }else if( ISUPPER(x
[0]) || ((x
[0]=='|' || x
[0]=='/') && ISUPPER(x
[1])) ){
2666 struct symbol
*msp
= psp
->tkclass
;
2668 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2669 sizeof(struct symbol
*)*msp
->nsubsym
);
2670 if( !ISUPPER(x
[0]) ) x
++;
2671 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(x
);
2673 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2674 "%%token_class argument \"%s\" should be a token", x
);
2676 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2679 case RESYNC_AFTER_RULE_ERROR
:
2680 /* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2682 case RESYNC_AFTER_DECL_ERROR
:
2683 if( x
[0]=='.' ) psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2684 if( x
[0]=='%' ) psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2689 /* Run the preprocessor over the input file text. The global variables
2690 ** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2691 ** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2692 ** comments them out. Text in between is also commented out as appropriate.
2694 static void preprocess_input(char *z
){
2699 int start_lineno
= 1;
2700 for(i
=0; z
[i
]; i
++){
2701 if( z
[i
]=='\n' ) lineno
++;
2702 if( z
[i
]!='%' || (i
>0 && z
[i
-1]!='\n') ) continue;
2703 if( strncmp(&z
[i
],"%endif",6)==0 && ISSPACE(z
[i
+6]) ){
2707 for(j
=start
; j
<i
; j
++) if( z
[j
]!='\n' ) z
[j
] = ' ';
2710 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2711 }else if( (strncmp(&z
[i
],"%ifdef",6)==0 && ISSPACE(z
[i
+6]))
2712 || (strncmp(&z
[i
],"%ifndef",7)==0 && ISSPACE(z
[i
+7])) ){
2716 for(j
=i
+7; ISSPACE(z
[j
]); j
++){}
2717 for(n
=0; z
[j
+n
] && !ISSPACE(z
[j
+n
]); n
++){}
2719 for(k
=0; k
<nDefine
; k
++){
2720 if( strncmp(azDefine
[k
],&z
[j
],n
)==0 && lemonStrlen(azDefine
[k
])==n
){
2725 if( z
[i
+3]=='n' ) exclude
= !exclude
;
2728 start_lineno
= lineno
;
2731 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2735 fprintf(stderr
,"unterminated %%ifdef starting on line %d\n", start_lineno
);
2740 /* In spite of its name, this function is really a scanner. It read
2741 ** in the entire input file (all at once) then tokenizes it. Each
2742 ** token is passed to the function "parseonetoken" which builds all
2743 ** the appropriate data structures in the global state vector "gp".
2745 void Parse(struct lemon
*gp
)
2750 unsigned int filesize
;
2756 memset(&ps
, '\0', sizeof(ps
));
2758 ps
.filename
= gp
->filename
;
2760 ps
.state
= INITIALIZE
;
2762 /* Begin by reading the input file */
2763 fp
= fopen(ps
.filename
,"rb");
2765 ErrorMsg(ps
.filename
,0,"Can't open this file for reading.");
2770 filesize
= ftell(fp
);
2772 filebuf
= (char *)malloc( filesize
+1 );
2773 if( filesize
>100000000 || filebuf
==0 ){
2774 ErrorMsg(ps
.filename
,0,"Input file too large.");
2779 if( fread(filebuf
,1,filesize
,fp
)!=filesize
){
2780 ErrorMsg(ps
.filename
,0,"Can't read in all %d bytes of this file.",
2788 filebuf
[filesize
] = 0;
2790 /* Make an initial pass through the file to handle %ifdef and %ifndef */
2791 preprocess_input(filebuf
);
2793 /* Now scan the text of the input file */
2795 for(cp
=filebuf
; (c
= *cp
)!=0; ){
2796 if( c
=='\n' ) lineno
++; /* Keep track of the line number */
2797 if( ISSPACE(c
) ){ cp
++; continue; } /* Skip all white space */
2798 if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments */
2800 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2803 if( c
=='/' && cp
[1]=='*' ){ /* Skip C style comments */
2805 while( (c
= *cp
)!=0 && (c
!='/' || cp
[-1]!='*') ){
2806 if( c
=='\n' ) lineno
++;
2812 ps
.tokenstart
= cp
; /* Mark the beginning of the token */
2813 ps
.tokenlineno
= lineno
; /* Linenumber on which token begins */
2814 if( c
=='\"' ){ /* String literals */
2816 while( (c
= *cp
)!=0 && c
!='\"' ){
2817 if( c
=='\n' ) lineno
++;
2821 ErrorMsg(ps
.filename
,startline
,
2822 "String starting on this line is not terminated before the end of the file.");
2828 }else if( c
=='{' ){ /* A block of C code */
2831 for(level
=1; (c
= *cp
)!=0 && (level
>1 || c
!='}'); cp
++){
2832 if( c
=='\n' ) lineno
++;
2833 else if( c
=='{' ) level
++;
2834 else if( c
=='}' ) level
--;
2835 else if( c
=='/' && cp
[1]=='*' ){ /* Skip comments */
2839 while( (c
= *cp
)!=0 && (c
!='/' || prevc
!='*') ){
2840 if( c
=='\n' ) lineno
++;
2844 }else if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments too */
2846 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2848 }else if( c
=='\'' || c
=='\"' ){ /* String a character literals */
2849 int startchar
, prevc
;
2852 for(cp
++; (c
= *cp
)!=0 && (c
!=startchar
|| prevc
=='\\'); cp
++){
2853 if( c
=='\n' ) lineno
++;
2854 if( prevc
=='\\' ) prevc
= 0;
2860 ErrorMsg(ps
.filename
,ps
.tokenlineno
,
2861 "C code starting on this line is not terminated before the end of the file.");
2867 }else if( ISALNUM(c
) ){ /* Identifiers */
2868 while( (c
= *cp
)!=0 && (ISALNUM(c
) || c
=='_') ) cp
++;
2870 }else if( c
==':' && cp
[1]==':' && cp
[2]=='=' ){ /* The operator "::=" */
2873 }else if( (c
=='/' || c
=='|') && ISALPHA(cp
[1]) ){
2875 while( (c
= *cp
)!=0 && (ISALNUM(c
) || c
=='_') ) cp
++;
2877 }else{ /* All other (one character) operators */
2882 *cp
= 0; /* Null terminate the token */
2883 parseonetoken(&ps
); /* Parse the token */
2884 *cp
= (char)c
; /* Restore the buffer */
2887 free(filebuf
); /* Release the buffer after parsing */
2888 gp
->rule
= ps
.firstrule
;
2889 gp
->errorcnt
= ps
.errorcnt
;
2891 /*************************** From the file "plink.c" *********************/
2893 ** Routines processing configuration follow-set propagation links
2894 ** in the LEMON parser generator.
2896 static struct plink
*plink_freelist
= 0;
2898 /* Allocate a new plink */
2899 struct plink
*Plink_new(void){
2900 struct plink
*newlink
;
2902 if( plink_freelist
==0 ){
2905 plink_freelist
= (struct plink
*)calloc( amt
, sizeof(struct plink
) );
2906 if( plink_freelist
==0 ){
2908 "Unable to allocate memory for a new follow-set propagation link.\n");
2911 for(i
=0; i
<amt
-1; i
++) plink_freelist
[i
].next
= &plink_freelist
[i
+1];
2912 plink_freelist
[amt
-1].next
= 0;
2914 newlink
= plink_freelist
;
2915 plink_freelist
= plink_freelist
->next
;
2919 /* Add a plink to a plink list */
2920 void Plink_add(struct plink
**plpp
, struct config
*cfp
)
2922 struct plink
*newlink
;
2923 newlink
= Plink_new();
2924 newlink
->next
= *plpp
;
2929 /* Transfer every plink on the list "from" to the list "to" */
2930 void Plink_copy(struct plink
**to
, struct plink
*from
)
2932 struct plink
*nextpl
;
2934 nextpl
= from
->next
;
2941 /* Delete every plink on the list */
2942 void Plink_delete(struct plink
*plp
)
2944 struct plink
*nextpl
;
2948 plp
->next
= plink_freelist
;
2949 plink_freelist
= plp
;
2953 /*********************** From the file "report.c" **************************/
2955 ** Procedures for generating reports and tables in the LEMON parser generator.
2958 /* Generate a filename with the given suffix. Space to hold the
2959 ** name comes from malloc() and must be freed by the calling
2962 PRIVATE
char *file_makename(struct lemon
*lemp
, const char *suffix
)
2967 name
= (char*)malloc( lemonStrlen(lemp
->filename
) + lemonStrlen(suffix
) + 5 );
2969 fprintf(stderr
,"Can't allocate space for a filename.\n");
2972 lemon_strcpy(name
,lemp
->filename
);
2973 cp
= strrchr(name
,'.');
2975 lemon_strcat(name
,suffix
);
2979 /* Open a file with a name based on the name of the input file,
2980 ** but with a different (specified) suffix, and return a pointer
2982 PRIVATE
FILE *file_open(
2989 if( lemp
->outname
) free(lemp
->outname
);
2990 lemp
->outname
= file_makename(lemp
, suffix
);
2991 fp
= fopen(lemp
->outname
,mode
);
2992 if( fp
==0 && *mode
=='w' ){
2993 fprintf(stderr
,"Can't open file \"%s\".\n",lemp
->outname
);
3000 /* Duplicate the input file without comments and without actions
3002 void Reprint(struct lemon
*lemp
)
3006 int i
, j
, maxlen
, len
, ncolumns
, skip
;
3007 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp
->filename
);
3009 for(i
=0; i
<lemp
->nsymbol
; i
++){
3010 sp
= lemp
->symbols
[i
];
3011 len
= lemonStrlen(sp
->name
);
3012 if( len
>maxlen
) maxlen
= len
;
3014 ncolumns
= 76/(maxlen
+5);
3015 if( ncolumns
<1 ) ncolumns
= 1;
3016 skip
= (lemp
->nsymbol
+ ncolumns
- 1)/ncolumns
;
3017 for(i
=0; i
<skip
; i
++){
3019 for(j
=i
; j
<lemp
->nsymbol
; j
+=skip
){
3020 sp
= lemp
->symbols
[j
];
3021 assert( sp
->index
==j
);
3022 printf(" %3d %-*.*s",j
,maxlen
,maxlen
,sp
->name
);
3026 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3027 printf("%s",rp
->lhs
->name
);
3028 /* if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
3030 for(i
=0; i
<rp
->nrhs
; i
++){
3032 if( sp
->type
==MULTITERMINAL
){
3033 printf(" %s", sp
->subsym
[0]->name
);
3034 for(j
=1; j
<sp
->nsubsym
; j
++){
3035 printf("|%s", sp
->subsym
[j
]->name
);
3038 printf(" %s", sp
->name
);
3040 /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
3043 if( rp
->precsym
) printf(" [%s]",rp
->precsym
->name
);
3044 /* if( rp->code ) printf("\n %s",rp->code); */
3049 /* Print a single rule.
3051 void RulePrint(FILE *fp
, struct rule
*rp
, int iCursor
){
3054 fprintf(fp
,"%s ::=",rp
->lhs
->name
);
3055 for(i
=0; i
<=rp
->nrhs
; i
++){
3056 if( i
==iCursor
) fprintf(fp
," *");
3057 if( i
==rp
->nrhs
) break;
3059 if( sp
->type
==MULTITERMINAL
){
3060 fprintf(fp
," %s", sp
->subsym
[0]->name
);
3061 for(j
=1; j
<sp
->nsubsym
; j
++){
3062 fprintf(fp
,"|%s",sp
->subsym
[j
]->name
);
3065 fprintf(fp
," %s", sp
->name
);
3070 /* Print the rule for a configuration.
3072 void ConfigPrint(FILE *fp
, struct config
*cfp
){
3073 RulePrint(fp
, cfp
->rp
, cfp
->dot
);
3079 PRIVATE
void SetPrint(out
,set
,lemp
)
3087 fprintf(out
,"%12s[","");
3088 for(i
=0; i
<lemp
->nterminal
; i
++){
3089 if( SetFind(set
,i
) ){
3090 fprintf(out
,"%s%s",spacer
,lemp
->symbols
[i
]->name
);
3097 /* Print a plink chain */
3098 PRIVATE
void PlinkPrint(out
,plp
,tag
)
3104 fprintf(out
,"%12s%s (state %2d) ","",tag
,plp
->cfp
->stp
->statenum
);
3105 ConfigPrint(out
,plp
->cfp
);
3112 /* Print an action to the given file descriptor. Return FALSE if
3113 ** nothing was actually printed.
3116 struct action
*ap
, /* The action to print */
3117 FILE *fp
, /* Print the action here */
3118 int indent
/* Indent by this amount */
3123 struct state
*stp
= ap
->x
.stp
;
3124 fprintf(fp
,"%*s shift %-7d",indent
,ap
->sp
->name
,stp
->statenum
);
3128 struct rule
*rp
= ap
->x
.rp
;
3129 fprintf(fp
,"%*s reduce %-7d",indent
,ap
->sp
->name
,rp
->iRule
);
3130 RulePrint(fp
, rp
, -1);
3134 struct rule
*rp
= ap
->x
.rp
;
3135 fprintf(fp
,"%*s shift-reduce %-7d",indent
,ap
->sp
->name
,rp
->iRule
);
3136 RulePrint(fp
, rp
, -1);
3140 fprintf(fp
,"%*s accept",indent
,ap
->sp
->name
);
3143 fprintf(fp
,"%*s error",indent
,ap
->sp
->name
);
3147 fprintf(fp
,"%*s reduce %-7d ** Parsing conflict **",
3148 indent
,ap
->sp
->name
,ap
->x
.rp
->iRule
);
3151 fprintf(fp
,"%*s shift %-7d ** Parsing conflict **",
3152 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3155 if( showPrecedenceConflict
){
3156 fprintf(fp
,"%*s shift %-7d -- dropped by precedence",
3157 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3163 if( showPrecedenceConflict
){
3164 fprintf(fp
,"%*s reduce %-7d -- dropped by precedence",
3165 indent
,ap
->sp
->name
,ap
->x
.rp
->iRule
);
3174 if( result
&& ap
->spOpt
){
3175 fprintf(fp
," /* because %s==%s */", ap
->sp
->name
, ap
->spOpt
->name
);
3180 /* Generate the "*.out" log file */
3181 void ReportOutput(struct lemon
*lemp
)
3189 fp
= file_open(lemp
,".out","wb");
3191 for(i
=0; i
<lemp
->nxstate
; i
++){
3192 stp
= lemp
->sorted
[i
];
3193 fprintf(fp
,"State %d:\n",stp
->statenum
);
3194 if( lemp
->basisflag
) cfp
=stp
->bp
;
3198 if( cfp
->dot
==cfp
->rp
->nrhs
){
3199 lemon_sprintf(buf
,"(%d)",cfp
->rp
->iRule
);
3200 fprintf(fp
," %5s ",buf
);
3204 ConfigPrint(fp
,cfp
);
3207 SetPrint(fp
,cfp
->fws
,lemp
);
3208 PlinkPrint(fp
,cfp
->fplp
,"To ");
3209 PlinkPrint(fp
,cfp
->bplp
,"From");
3211 if( lemp
->basisflag
) cfp
=cfp
->bp
;
3215 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3216 if( PrintAction(ap
,fp
,30) ) fprintf(fp
,"\n");
3220 fprintf(fp
, "----------------------------------------------------\n");
3221 fprintf(fp
, "Symbols:\n");
3222 for(i
=0; i
<lemp
->nsymbol
; i
++){
3226 sp
= lemp
->symbols
[i
];
3227 fprintf(fp
, " %3d: %s", i
, sp
->name
);
3228 if( sp
->type
==NONTERMINAL
){
3231 fprintf(fp
, " <lambda>");
3233 for(j
=0; j
<lemp
->nterminal
; j
++){
3234 if( sp
->firstset
&& SetFind(sp
->firstset
, j
) ){
3235 fprintf(fp
, " %s", lemp
->symbols
[j
]->name
);
3245 /* Search for the file "name" which is in the same directory as
3246 ** the exacutable */
3247 PRIVATE
char *pathsearch(char *argv0
, char *name
, int modemask
)
3249 const char *pathlist
;
3256 cp
= strrchr(argv0
,'\\');
3258 cp
= strrchr(argv0
,'/');
3263 path
= (char *)malloc( lemonStrlen(argv0
) + lemonStrlen(name
) + 2 );
3264 if( path
) lemon_sprintf(path
,"%s/%s",argv0
,name
);
3267 pathlist
= getenv("PATH");
3268 if( pathlist
==0 ) pathlist
= ".:/bin:/usr/bin";
3269 pathbuf
= (char *) malloc( lemonStrlen(pathlist
) + 1 );
3270 path
= (char *)malloc( lemonStrlen(pathlist
)+lemonStrlen(name
)+2 );
3271 if( (pathbuf
!= 0) && (path
!=0) ){
3272 pathbufptr
= pathbuf
;
3273 lemon_strcpy(pathbuf
, pathlist
);
3275 cp
= strchr(pathbuf
,':');
3276 if( cp
==0 ) cp
= &pathbuf
[lemonStrlen(pathbuf
)];
3279 lemon_sprintf(path
,"%s/%s",pathbuf
,name
);
3281 if( c
==0 ) pathbuf
[0] = 0;
3282 else pathbuf
= &cp
[1];
3283 if( access(path
,modemask
)==0 ) break;
3291 /* Given an action, compute the integer value for that action
3292 ** which is to be put in the action table of the generated machine.
3293 ** Return negative if no action should be generated.
3295 PRIVATE
int compute_action(struct lemon
*lemp
, struct action
*ap
)
3299 case SHIFT
: act
= ap
->x
.stp
->statenum
; break;
3301 act
= ap
->x
.rp
->iRule
+ lemp
->nstate
;
3302 /* Since a SHIFT is inherient after a prior REDUCE, convert any
3303 ** SHIFTREDUCE action with a nonterminal on the LHS into a simple
3304 ** REDUCE action: */
3305 if( ap
->sp
->index
>=lemp
->nterminal
) act
+= lemp
->nrule
;
3308 case REDUCE
: act
= ap
->x
.rp
->iRule
+ lemp
->nstate
+lemp
->nrule
; break;
3309 case ERROR
: act
= lemp
->nstate
+ lemp
->nrule
*2; break;
3310 case ACCEPT
: act
= lemp
->nstate
+ lemp
->nrule
*2 + 1; break;
3311 default: act
= -1; break;
3316 #define LINESIZE 1000
3317 /* The next cluster of routines are for reading the template file
3318 ** and writing the results to the generated parser */
3319 /* The first function transfers data from "in" to "out" until
3320 ** a line is seen which begins with "%%". The line number is
3323 ** if name!=0, then any word that begin with "Parse" is changed to
3324 ** begin with *name instead.
3326 PRIVATE
void tplt_xfer(char *name
, FILE *in
, FILE *out
, int *lineno
)
3329 char line
[LINESIZE
];
3330 while( fgets(line
,LINESIZE
,in
) && (line
[0]!='%' || line
[1]!='%') ){
3334 for(i
=0; line
[i
]; i
++){
3335 if( line
[i
]=='P' && strncmp(&line
[i
],"Parse",5)==0
3336 && (i
==0 || !ISALPHA(line
[i
-1]))
3338 if( i
>iStart
) fprintf(out
,"%.*s",i
-iStart
,&line
[iStart
]);
3339 fprintf(out
,"%s",name
);
3345 fprintf(out
,"%s",&line
[iStart
]);
3349 /* The next function finds the template file and opens it, returning
3350 ** a pointer to the opened file. */
3351 PRIVATE
FILE *tplt_open(struct lemon
*lemp
)
3353 static char templatename
[] = "lempar.c";
3359 /* first, see if user specified a template filename on the command line. */
3360 if (user_templatename
!= 0) {
3361 if( access(user_templatename
,004)==-1 ){
3362 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3367 in
= fopen(user_templatename
,"rb");
3369 fprintf(stderr
,"Can't open the template file \"%s\".\n",
3377 cp
= strrchr(lemp
->filename
,'.');
3379 lemon_sprintf(buf
,"%.*s.lt",(int)(cp
-lemp
->filename
),lemp
->filename
);
3381 lemon_sprintf(buf
,"%s.lt",lemp
->filename
);
3383 if( access(buf
,004)==0 ){
3385 }else if( access(templatename
,004)==0 ){
3386 tpltname
= templatename
;
3388 tpltname
= pathsearch(lemp
->argv0
,templatename
,0);
3391 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3396 in
= fopen(tpltname
,"rb");
3398 fprintf(stderr
,"Can't open the template file \"%s\".\n",templatename
);
3405 /* Print a #line directive line to the output file. */
3406 PRIVATE
void tplt_linedir(FILE *out
, int lineno
, char *filename
)
3408 fprintf(out
,"#line %d \"",lineno
);
3410 if( *filename
== '\\' ) putc('\\',out
);
3411 putc(*filename
,out
);
3414 fprintf(out
,"\"\n");
3417 /* Print a string to the file and keep the linenumber up to date */
3418 PRIVATE
void tplt_print(FILE *out
, struct lemon
*lemp
, char *str
, int *lineno
)
3420 if( str
==0 ) return;
3423 if( *str
=='\n' ) (*lineno
)++;
3426 if( str
[-1]!='\n' ){
3430 if (!lemp
->nolinenosflag
) {
3431 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3437 ** The following routine emits code for the destructor for the
3440 void emit_destructor_code(
3448 if( sp
->type
==TERMINAL
){
3449 cp
= lemp
->tokendest
;
3451 fprintf(out
,"{\n"); (*lineno
)++;
3452 }else if( sp
->destructor
){
3453 cp
= sp
->destructor
;
3454 fprintf(out
,"{\n"); (*lineno
)++;
3455 if( !lemp
->nolinenosflag
){
3457 tplt_linedir(out
,sp
->destLineno
,lemp
->filename
);
3459 }else if( lemp
->vardest
){
3462 fprintf(out
,"{\n"); (*lineno
)++;
3464 assert( 0 ); /* Cannot happen */
3467 if( *cp
=='$' && cp
[1]=='$' ){
3468 fprintf(out
,"(yypminor->yy%d)",sp
->dtnum
);
3472 if( *cp
=='\n' ) (*lineno
)++;
3475 fprintf(out
,"\n"); (*lineno
)++;
3476 if (!lemp
->nolinenosflag
) {
3477 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3479 fprintf(out
,"}\n"); (*lineno
)++;
3484 ** Return TRUE (non-zero) if the given symbol has a destructor.
3486 int has_destructor(struct symbol
*sp
, struct lemon
*lemp
)
3489 if( sp
->type
==TERMINAL
){
3490 ret
= lemp
->tokendest
!=0;
3492 ret
= lemp
->vardest
!=0 || sp
->destructor
!=0;
3498 ** Append text to a dynamically allocated string. If zText is 0 then
3499 ** reset the string to be empty again. Always return the complete text
3500 ** of the string (which is overwritten with each call).
3502 ** n bytes of zText are stored. If n==0 then all of zText up to the first
3503 ** \000 terminator is stored. zText can contain up to two instances of
3504 ** %d. The values of p1 and p2 are written into the first and second
3507 ** If n==-1, then the previous character is overwritten.
3509 PRIVATE
char *append_str(const char *zText
, int n
, int p1
, int p2
){
3510 static char empty
[1] = { 0 };
3512 static int alloced
= 0;
3513 static int used
= 0;
3517 if( used
==0 && z
!=0 ) z
[0] = 0;
3526 n
= lemonStrlen(zText
);
3528 if( (int) (n
+sizeof(zInt
)*2+used
) >= alloced
){
3529 alloced
= n
+ sizeof(zInt
)*2 + used
+ 200;
3530 z
= (char *) realloc(z
, alloced
);
3532 if( z
==0 ) return empty
;
3535 if( c
=='%' && n
>0 && zText
[0]=='d' ){
3536 lemon_sprintf(zInt
, "%d", p1
);
3538 lemon_strcpy(&z
[used
], zInt
);
3539 used
+= lemonStrlen(&z
[used
]);
3543 z
[used
++] = (char)c
;
3551 ** Write and transform the rp->code string so that symbols are expanded.
3552 ** Populate the rp->codePrefix and rp->codeSuffix strings, as appropriate.
3554 ** Return 1 if the expanded code requires that "yylhsminor" local variable
3557 PRIVATE
int translate_code(struct lemon
*lemp
, struct rule
*rp
){
3560 int rc
= 0; /* True if yylhsminor is used */
3561 int dontUseRhs0
= 0; /* If true, use of left-most RHS label is illegal */
3562 const char *zSkip
= 0; /* The zOvwrt comment within rp->code, or NULL */
3563 char lhsused
= 0; /* True if the LHS element has been used */
3564 char lhsdirect
; /* True if LHS writes directly into stack */
3565 char used
[MAXRHS
]; /* True for each RHS element which is used */
3566 char zLhs
[50]; /* Convert the LHS symbol into this string */
3567 char zOvwrt
[900]; /* Comment that to allow LHS to overwrite RHS */
3569 for(i
=0; i
<rp
->nrhs
; i
++) used
[i
] = 0;
3573 static char newlinestr
[2] = { '\n', '\0' };
3574 rp
->code
= newlinestr
;
3575 rp
->line
= rp
->ruleline
;
3583 /* If there are no RHS symbols, then writing directly to the LHS is ok */
3585 }else if( rp
->rhsalias
[0]==0 ){
3586 /* The left-most RHS symbol has no value. LHS direct is ok. But
3587 ** we have to call the distructor on the RHS symbol first. */
3589 if( has_destructor(rp
->rhs
[0],lemp
) ){
3590 append_str(0,0,0,0);
3591 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3592 rp
->rhs
[0]->index
,1-rp
->nrhs
);
3593 rp
->codePrefix
= Strsafe(append_str(0,0,0,0));
3596 }else if( rp
->lhsalias
==0 ){
3597 /* There is no LHS value symbol. */
3599 }else if( strcmp(rp
->lhsalias
,rp
->rhsalias
[0])==0 ){
3600 /* The LHS symbol and the left-most RHS symbol are the same, so
3601 ** direct writing is allowed */
3605 if( rp
->lhs
->dtnum
!=rp
->rhs
[0]->dtnum
){
3606 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3607 "%s(%s) and %s(%s) share the same label but have "
3608 "different datatypes.",
3609 rp
->lhs
->name
, rp
->lhsalias
, rp
->rhs
[0]->name
, rp
->rhsalias
[0]);
3613 lemon_sprintf(zOvwrt
, "/*%s-overwrites-%s*/",
3614 rp
->lhsalias
, rp
->rhsalias
[0]);
3615 zSkip
= strstr(rp
->code
, zOvwrt
);
3617 /* The code contains a special comment that indicates that it is safe
3618 ** for the LHS label to overwrite left-most RHS label. */
3625 sprintf(zLhs
, "yymsp[%d].minor.yy%d",1-rp
->nrhs
,rp
->lhs
->dtnum
);
3628 sprintf(zLhs
, "yylhsminor.yy%d",rp
->lhs
->dtnum
);
3631 append_str(0,0,0,0);
3633 /* This const cast is wrong but harmless, if we're careful. */
3634 for(cp
=(char *)rp
->code
; *cp
; cp
++){
3636 append_str(zOvwrt
,0,0,0);
3637 cp
+= lemonStrlen(zOvwrt
)-1;
3641 if( ISALPHA(*cp
) && (cp
==rp
->code
|| (!ISALNUM(cp
[-1]) && cp
[-1]!='_')) ){
3643 for(xp
= &cp
[1]; ISALNUM(*xp
) || *xp
=='_'; xp
++);
3646 if( rp
->lhsalias
&& strcmp(cp
,rp
->lhsalias
)==0 ){
3647 append_str(zLhs
,0,0,0);
3651 for(i
=0; i
<rp
->nrhs
; i
++){
3652 if( rp
->rhsalias
[i
] && strcmp(cp
,rp
->rhsalias
[i
])==0 ){
3653 if( i
==0 && dontUseRhs0
){
3654 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3655 "Label %s used after '%s'.",
3656 rp
->rhsalias
[0], zOvwrt
);
3658 }else if( cp
!=rp
->code
&& cp
[-1]=='@' ){
3659 /* If the argument is of the form @X then substituted
3660 ** the token number of X, not the value of X */
3661 append_str("yymsp[%d].major",-1,i
-rp
->nrhs
+1,0);
3663 struct symbol
*sp
= rp
->rhs
[i
];
3665 if( sp
->type
==MULTITERMINAL
){
3666 dtnum
= sp
->subsym
[0]->dtnum
;
3670 append_str("yymsp[%d].minor.yy%d",0,i
-rp
->nrhs
+1, dtnum
);
3680 append_str(cp
, 1, 0, 0);
3683 /* Main code generation completed */
3684 cp
= append_str(0,0,0,0);
3685 if( cp
&& cp
[0] ) rp
->code
= Strsafe(cp
);
3686 append_str(0,0,0,0);
3688 /* Check to make sure the LHS has been used */
3689 if( rp
->lhsalias
&& !lhsused
){
3690 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3691 "Label \"%s\" for \"%s(%s)\" is never used.",
3692 rp
->lhsalias
,rp
->lhs
->name
,rp
->lhsalias
);
3696 /* Generate destructor code for RHS minor values which are not referenced.
3697 ** Generate error messages for unused labels and duplicate labels.
3699 for(i
=0; i
<rp
->nrhs
; i
++){
3700 if( rp
->rhsalias
[i
] ){
3703 if( rp
->lhsalias
&& strcmp(rp
->lhsalias
,rp
->rhsalias
[i
])==0 ){
3704 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3705 "%s(%s) has the same label as the LHS but is not the left-most "
3706 "symbol on the RHS.",
3707 rp
->rhs
[i
]->name
, rp
->rhsalias
);
3711 if( rp
->rhsalias
[j
] && strcmp(rp
->rhsalias
[j
],rp
->rhsalias
[i
])==0 ){
3712 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3713 "Label %s used for multiple symbols on the RHS of a rule.",
3721 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3722 "Label %s for \"%s(%s)\" is never used.",
3723 rp
->rhsalias
[i
],rp
->rhs
[i
]->name
,rp
->rhsalias
[i
]);
3726 }else if( i
>0 && has_destructor(rp
->rhs
[i
],lemp
) ){
3727 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3728 rp
->rhs
[i
]->index
,i
-rp
->nrhs
+1);
3732 /* If unable to write LHS values directly into the stack, write the
3733 ** saved LHS value now. */
3735 append_str(" yymsp[%d].minor.yy%d = ", 0, 1-rp
->nrhs
, rp
->lhs
->dtnum
);
3736 append_str(zLhs
, 0, 0, 0);
3737 append_str(";\n", 0, 0, 0);
3740 /* Suffix code generation complete */
3741 cp
= append_str(0,0,0,0);
3743 rp
->codeSuffix
= Strsafe(cp
);
3751 ** Generate code which executes when the rule "rp" is reduced. Write
3752 ** the code to "out". Make sure lineno stays up-to-date.
3754 PRIVATE
void emit_code(
3762 /* Setup code prior to the #line directive */
3763 if( rp
->codePrefix
&& rp
->codePrefix
[0] ){
3764 fprintf(out
, "{%s", rp
->codePrefix
);
3765 for(cp
=rp
->codePrefix
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
3768 /* Generate code to do the reduce action */
3770 if( !lemp
->nolinenosflag
){
3772 tplt_linedir(out
,rp
->line
,lemp
->filename
);
3774 fprintf(out
,"{%s",rp
->code
);
3775 for(cp
=rp
->code
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
3776 fprintf(out
,"}\n"); (*lineno
)++;
3777 if( !lemp
->nolinenosflag
){
3779 tplt_linedir(out
,*lineno
,lemp
->outname
);
3783 /* Generate breakdown code that occurs after the #line directive */
3784 if( rp
->codeSuffix
&& rp
->codeSuffix
[0] ){
3785 fprintf(out
, "%s", rp
->codeSuffix
);
3786 for(cp
=rp
->codeSuffix
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
3789 if( rp
->codePrefix
){
3790 fprintf(out
, "}\n"); (*lineno
)++;
3797 ** Print the definition of the union used for the parser's data stack.
3798 ** This union contains fields for every possible data type for tokens
3799 ** and nonterminals. In the process of computing and printing this
3800 ** union, also set the ".dtnum" field of every terminal and nonterminal
3803 void print_stack_union(
3804 FILE *out
, /* The output stream */
3805 struct lemon
*lemp
, /* The main info structure for this parser */
3806 int *plineno
, /* Pointer to the line number */
3807 int mhflag
/* True if generating makeheaders output */
3809 int lineno
= *plineno
; /* The line number of the output */
3810 char **types
; /* A hash table of datatypes */
3811 int arraysize
; /* Size of the "types" array */
3812 int maxdtlength
; /* Maximum length of any ".datatype" field. */
3813 char *stddt
; /* Standardized name for a datatype */
3814 int i
,j
; /* Loop counters */
3815 unsigned hash
; /* For hashing the name of a type */
3816 const char *name
; /* Name of the parser */
3818 /* Allocate and initialize types[] and allocate stddt[] */
3819 arraysize
= lemp
->nsymbol
* 2;
3820 types
= (char**)calloc( arraysize
, sizeof(char*) );
3822 fprintf(stderr
,"Out of memory.\n");
3825 for(i
=0; i
<arraysize
; i
++) types
[i
] = 0;
3827 if( lemp
->vartype
){
3828 maxdtlength
= lemonStrlen(lemp
->vartype
);
3830 for(i
=0; i
<lemp
->nsymbol
; i
++){
3832 struct symbol
*sp
= lemp
->symbols
[i
];
3833 if( sp
->datatype
==0 ) continue;
3834 len
= lemonStrlen(sp
->datatype
);
3835 if( len
>maxdtlength
) maxdtlength
= len
;
3837 stddt
= (char*)malloc( maxdtlength
*2 + 1 );
3839 fprintf(stderr
,"Out of memory.\n");
3843 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3844 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
3845 ** used for terminal symbols. If there is no %default_type defined then
3846 ** 0 is also used as the .dtnum value for nonterminals which do not specify
3847 ** a datatype using the %type directive.
3849 for(i
=0; i
<lemp
->nsymbol
; i
++){
3850 struct symbol
*sp
= lemp
->symbols
[i
];
3852 if( sp
==lemp
->errsym
){
3853 sp
->dtnum
= arraysize
+1;
3856 if( sp
->type
!=NONTERMINAL
|| (sp
->datatype
==0 && lemp
->vartype
==0) ){
3861 if( cp
==0 ) cp
= lemp
->vartype
;
3863 while( ISSPACE(*cp
) ) cp
++;
3864 while( *cp
) stddt
[j
++] = *cp
++;
3865 while( j
>0 && ISSPACE(stddt
[j
-1]) ) j
--;
3867 if( lemp
->tokentype
&& strcmp(stddt
, lemp
->tokentype
)==0 ){
3872 for(j
=0; stddt
[j
]; j
++){
3873 hash
= hash
*53 + stddt
[j
];
3875 hash
= (hash
& 0x7fffffff)%arraysize
;
3876 while( types
[hash
] ){
3877 if( strcmp(types
[hash
],stddt
)==0 ){
3878 sp
->dtnum
= hash
+ 1;
3882 if( hash
>=(unsigned)arraysize
) hash
= 0;
3884 if( types
[hash
]==0 ){
3885 sp
->dtnum
= hash
+ 1;
3886 types
[hash
] = (char*)malloc( lemonStrlen(stddt
)+1 );
3887 if( types
[hash
]==0 ){
3888 fprintf(stderr
,"Out of memory.\n");
3891 lemon_strcpy(types
[hash
],stddt
);
3895 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3896 name
= lemp
->name
? lemp
->name
: "Parse";
3898 if( mhflag
){ fprintf(out
,"#if INTERFACE\n"); lineno
++; }
3899 fprintf(out
,"#define %sTOKENTYPE %s\n",name
,
3900 lemp
->tokentype
?lemp
->tokentype
:"void*"); lineno
++;
3901 if( mhflag
){ fprintf(out
,"#endif\n"); lineno
++; }
3902 fprintf(out
,"typedef union {\n"); lineno
++;
3903 fprintf(out
," int yyinit;\n"); lineno
++;
3904 fprintf(out
," %sTOKENTYPE yy0;\n",name
); lineno
++;
3905 for(i
=0; i
<arraysize
; i
++){
3906 if( types
[i
]==0 ) continue;
3907 fprintf(out
," %s yy%d;\n",types
[i
],i
+1); lineno
++;
3910 if( lemp
->errsym
->useCnt
){
3911 fprintf(out
," int yy%d;\n",lemp
->errsym
->dtnum
); lineno
++;
3915 fprintf(out
,"} YYMINORTYPE;\n"); lineno
++;
3920 ** Return the name of a C datatype able to represent values between
3921 ** lwr and upr, inclusive. If pnByte!=NULL then also write the sizeof
3922 ** for that type (1, 2, or 4) into *pnByte.
3924 static const char *minimum_size_type(int lwr
, int upr
, int *pnByte
){
3925 const char *zType
= "int";
3929 zType
= "unsigned char";
3931 }else if( upr
<65535 ){
3932 zType
= "unsigned short int";
3935 zType
= "unsigned int";
3938 }else if( lwr
>=-127 && upr
<=127 ){
3939 zType
= "signed char";
3941 }else if( lwr
>=-32767 && upr
<32767 ){
3945 if( pnByte
) *pnByte
= nByte
;
3950 ** Each state contains a set of token transaction and a set of
3951 ** nonterminal transactions. Each of these sets makes an instance
3952 ** of the following structure. An array of these structures is used
3953 ** to order the creation of entries in the yy_action[] table.
3956 struct state
*stp
; /* A pointer to a state */
3957 int isTkn
; /* True to use tokens. False for non-terminals */
3958 int nAction
; /* Number of actions */
3959 int iOrder
; /* Original order of action sets */
3963 ** Compare to axset structures for sorting purposes
3965 static int axset_compare(const void *a
, const void *b
){
3966 struct axset
*p1
= (struct axset
*)a
;
3967 struct axset
*p2
= (struct axset
*)b
;
3969 c
= p2
->nAction
- p1
->nAction
;
3971 c
= p1
->iOrder
- p2
->iOrder
;
3973 assert( c
!=0 || p1
==p2
);
3978 ** Write text on "out" that describes the rule "rp".
3980 static void writeRuleText(FILE *out
, struct rule
*rp
){
3982 fprintf(out
,"%s ::=", rp
->lhs
->name
);
3983 for(j
=0; j
<rp
->nrhs
; j
++){
3984 struct symbol
*sp
= rp
->rhs
[j
];
3985 if( sp
->type
!=MULTITERMINAL
){
3986 fprintf(out
," %s", sp
->name
);
3989 fprintf(out
," %s", sp
->subsym
[0]->name
);
3990 for(k
=1; k
<sp
->nsubsym
; k
++){
3991 fprintf(out
,"|%s",sp
->subsym
[k
]->name
);
3998 /* Generate C source code for the parser */
4001 int mhflag
/* Output in makeheaders format if true */
4004 char line
[LINESIZE
];
4009 struct acttab
*pActtab
;
4011 int szActionType
; /* sizeof(YYACTIONTYPE) */
4012 int szCodeType
; /* sizeof(YYCODETYPE) */
4014 int mnTknOfst
, mxTknOfst
;
4015 int mnNtOfst
, mxNtOfst
;
4018 in
= tplt_open(lemp
);
4020 out
= file_open(lemp
,".c","wb");
4026 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4028 /* Generate the include code, if any */
4029 tplt_print(out
,lemp
,lemp
->include
,&lineno
);
4031 char *incName
= file_makename(lemp
, ".h");
4032 fprintf(out
,"#include \"%s\"\n", incName
); lineno
++;
4035 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4037 /* Generate #defines for all tokens */
4040 fprintf(out
,"#if INTERFACE\n"); lineno
++;
4041 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
4043 for(i
=1; i
<lemp
->nterminal
; i
++){
4044 fprintf(out
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
4047 fprintf(out
,"#endif\n"); lineno
++;
4049 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4051 /* Generate the defines */
4052 fprintf(out
,"#define YYCODETYPE %s\n",
4053 minimum_size_type(0, lemp
->nsymbol
+1, &szCodeType
)); lineno
++;
4054 fprintf(out
,"#define YYNOCODE %d\n",lemp
->nsymbol
+1); lineno
++;
4055 fprintf(out
,"#define YYACTIONTYPE %s\n",
4056 minimum_size_type(0,lemp
->nstate
+lemp
->nrule
*2+5,&szActionType
)); lineno
++;
4057 if( lemp
->wildcard
){
4058 fprintf(out
,"#define YYWILDCARD %d\n",
4059 lemp
->wildcard
->index
); lineno
++;
4061 print_stack_union(out
,lemp
,&lineno
,mhflag
);
4062 fprintf(out
, "#ifndef YYSTACKDEPTH\n"); lineno
++;
4063 if( lemp
->stacksize
){
4064 fprintf(out
,"#define YYSTACKDEPTH %s\n",lemp
->stacksize
); lineno
++;
4066 fprintf(out
,"#define YYSTACKDEPTH 100\n"); lineno
++;
4068 fprintf(out
, "#endif\n"); lineno
++;
4070 fprintf(out
,"#if INTERFACE\n"); lineno
++;
4072 name
= lemp
->name
? lemp
->name
: "Parse";
4073 if( lemp
->arg
&& lemp
->arg
[0] ){
4074 i
= lemonStrlen(lemp
->arg
);
4075 while( i
>=1 && ISSPACE(lemp
->arg
[i
-1]) ) i
--;
4076 while( i
>=1 && (ISALNUM(lemp
->arg
[i
-1]) || lemp
->arg
[i
-1]=='_') ) i
--;
4077 fprintf(out
,"#define %sARG_SDECL %s;\n",name
,lemp
->arg
); lineno
++;
4078 fprintf(out
,"#define %sARG_PDECL ,%s\n",name
,lemp
->arg
); lineno
++;
4079 fprintf(out
,"#define %sARG_FETCH %s = yypParser->%s\n",
4080 name
,lemp
->arg
,&lemp
->arg
[i
]); lineno
++;
4081 fprintf(out
,"#define %sARG_STORE yypParser->%s = %s\n",
4082 name
,&lemp
->arg
[i
],&lemp
->arg
[i
]); lineno
++;
4084 fprintf(out
,"#define %sARG_SDECL\n",name
); lineno
++;
4085 fprintf(out
,"#define %sARG_PDECL\n",name
); lineno
++;
4086 fprintf(out
,"#define %sARG_FETCH\n",name
); lineno
++;
4087 fprintf(out
,"#define %sARG_STORE\n",name
); lineno
++;
4090 fprintf(out
,"#endif\n"); lineno
++;
4092 if( lemp
->errsym
->useCnt
){
4093 fprintf(out
,"#define YYERRORSYMBOL %d\n",lemp
->errsym
->index
); lineno
++;
4094 fprintf(out
,"#define YYERRSYMDT yy%d\n",lemp
->errsym
->dtnum
); lineno
++;
4096 if( lemp
->has_fallback
){
4097 fprintf(out
,"#define YYFALLBACK 1\n"); lineno
++;
4100 /* Compute the action table, but do not output it yet. The action
4101 ** table must be computed before generating the YYNSTATE macro because
4102 ** we need to know how many states can be eliminated.
4104 ax
= (struct axset
*) calloc(lemp
->nxstate
*2, sizeof(ax
[0]));
4106 fprintf(stderr
,"malloc failed\n");
4109 for(i
=0; i
<lemp
->nxstate
; i
++){
4110 stp
= lemp
->sorted
[i
];
4113 ax
[i
*2].nAction
= stp
->nTknAct
;
4114 ax
[i
*2+1].stp
= stp
;
4115 ax
[i
*2+1].isTkn
= 0;
4116 ax
[i
*2+1].nAction
= stp
->nNtAct
;
4118 mxTknOfst
= mnTknOfst
= 0;
4119 mxNtOfst
= mnNtOfst
= 0;
4120 /* In an effort to minimize the action table size, use the heuristic
4121 ** of placing the largest action sets first */
4122 for(i
=0; i
<lemp
->nxstate
*2; i
++) ax
[i
].iOrder
= i
;
4123 qsort(ax
, lemp
->nxstate
*2, sizeof(ax
[0]), axset_compare
);
4124 pActtab
= acttab_alloc();
4125 for(i
=0; i
<lemp
->nxstate
*2 && ax
[i
].nAction
>0; i
++){
4128 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4130 if( ap
->sp
->index
>=lemp
->nterminal
) continue;
4131 action
= compute_action(lemp
, ap
);
4132 if( action
<0 ) continue;
4133 acttab_action(pActtab
, ap
->sp
->index
, action
);
4135 stp
->iTknOfst
= acttab_insert(pActtab
);
4136 if( stp
->iTknOfst
<mnTknOfst
) mnTknOfst
= stp
->iTknOfst
;
4137 if( stp
->iTknOfst
>mxTknOfst
) mxTknOfst
= stp
->iTknOfst
;
4139 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4141 if( ap
->sp
->index
<lemp
->nterminal
) continue;
4142 if( ap
->sp
->index
==lemp
->nsymbol
) continue;
4143 action
= compute_action(lemp
, ap
);
4144 if( action
<0 ) continue;
4145 acttab_action(pActtab
, ap
->sp
->index
, action
);
4147 stp
->iNtOfst
= acttab_insert(pActtab
);
4148 if( stp
->iNtOfst
<mnNtOfst
) mnNtOfst
= stp
->iNtOfst
;
4149 if( stp
->iNtOfst
>mxNtOfst
) mxNtOfst
= stp
->iNtOfst
;
4151 #if 0 /* Uncomment for a trace of how the yy_action[] table fills out */
4153 for(jj
=nn
=0; jj
<pActtab
->nAction
; jj
++){
4154 if( pActtab
->aAction
[jj
].action
<0 ) nn
++;
4156 printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n",
4157 i
, stp
->statenum
, ax
[i
].isTkn
? "Token" : "Var ",
4158 ax
[i
].nAction
, pActtab
->nAction
, nn
);
4164 /* Mark rules that are actually used for reduce actions after all
4165 ** optimizations have been applied
4167 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->doesReduce
= LEMON_FALSE
;
4168 for(i
=0; i
<lemp
->nxstate
; i
++){
4169 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
4170 if( ap
->type
==REDUCE
|| ap
->type
==SHIFTREDUCE
){
4171 ap
->x
.rp
->doesReduce
= 1;
4176 /* Finish rendering the constants now that the action table has
4178 fprintf(out
,"#define YYNSTATE %d\n",lemp
->nxstate
); lineno
++;
4179 fprintf(out
,"#define YYNRULE %d\n",lemp
->nrule
); lineno
++;
4180 fprintf(out
,"#define YY_MAX_SHIFT %d\n",lemp
->nxstate
-1); lineno
++;
4181 fprintf(out
,"#define YY_MIN_SHIFTREDUCE %d\n",lemp
->nstate
); lineno
++;
4182 i
= lemp
->nstate
+ lemp
->nrule
;
4183 fprintf(out
,"#define YY_MAX_SHIFTREDUCE %d\n", i
-1); lineno
++;
4184 fprintf(out
,"#define YY_MIN_REDUCE %d\n", i
); lineno
++;
4185 i
= lemp
->nstate
+ lemp
->nrule
*2;
4186 fprintf(out
,"#define YY_MAX_REDUCE %d\n", i
-1); lineno
++;
4187 fprintf(out
,"#define YY_ERROR_ACTION %d\n", i
); lineno
++;
4188 fprintf(out
,"#define YY_ACCEPT_ACTION %d\n", i
+1); lineno
++;
4189 fprintf(out
,"#define YY_NO_ACTION %d\n", i
+2); lineno
++;
4190 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4192 /* Now output the action table and its associates:
4194 ** yy_action[] A single table containing all actions.
4195 ** yy_lookahead[] A table containing the lookahead for each entry in
4196 ** yy_action. Used to detect hash collisions.
4197 ** yy_shift_ofst[] For each state, the offset into yy_action for
4198 ** shifting terminals.
4199 ** yy_reduce_ofst[] For each state, the offset into yy_action for
4200 ** shifting non-terminals after a reduce.
4201 ** yy_default[] Default action for each state.
4204 /* Output the yy_action table */
4205 lemp
->nactiontab
= n
= acttab_size(pActtab
);
4206 lemp
->tablesize
+= n
*szActionType
;
4207 fprintf(out
,"#define YY_ACTTAB_COUNT (%d)\n", n
); lineno
++;
4208 fprintf(out
,"static const YYACTIONTYPE yy_action[] = {\n"); lineno
++;
4209 for(i
=j
=0; i
<n
; i
++){
4210 int action
= acttab_yyaction(pActtab
, i
);
4211 if( action
<0 ) action
= lemp
->nstate
+ lemp
->nrule
+ 2;
4212 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4213 fprintf(out
, " %4d,", action
);
4214 if( j
==9 || i
==n
-1 ){
4215 fprintf(out
, "\n"); lineno
++;
4221 fprintf(out
, "};\n"); lineno
++;
4223 /* Output the yy_lookahead table */
4224 lemp
->tablesize
+= n
*szCodeType
;
4225 fprintf(out
,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno
++;
4226 for(i
=j
=0; i
<n
; i
++){
4227 int la
= acttab_yylookahead(pActtab
, i
);
4228 if( la
<0 ) la
= lemp
->nsymbol
;
4229 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4230 fprintf(out
, " %4d,", la
);
4231 if( j
==9 || i
==n
-1 ){
4232 fprintf(out
, "\n"); lineno
++;
4238 fprintf(out
, "};\n"); lineno
++;
4240 /* Output the yy_shift_ofst[] table */
4242 while( n
>0 && lemp
->sorted
[n
-1]->iTknOfst
==NO_OFFSET
) n
--;
4243 fprintf(out
, "#define YY_SHIFT_USE_DFLT (%d)\n", lemp
->nactiontab
); lineno
++;
4244 fprintf(out
, "#define YY_SHIFT_COUNT (%d)\n", n
-1); lineno
++;
4245 fprintf(out
, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst
); lineno
++;
4246 fprintf(out
, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst
); lineno
++;
4247 fprintf(out
, "static const %s yy_shift_ofst[] = {\n",
4248 minimum_size_type(mnTknOfst
, lemp
->nterminal
+lemp
->nactiontab
, &sz
));
4250 lemp
->tablesize
+= n
*sz
;
4251 for(i
=j
=0; i
<n
; i
++){
4253 stp
= lemp
->sorted
[i
];
4254 ofst
= stp
->iTknOfst
;
4255 if( ofst
==NO_OFFSET
) ofst
= lemp
->nactiontab
;
4256 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4257 fprintf(out
, " %4d,", ofst
);
4258 if( j
==9 || i
==n
-1 ){
4259 fprintf(out
, "\n"); lineno
++;
4265 fprintf(out
, "};\n"); lineno
++;
4267 /* Output the yy_reduce_ofst[] table */
4268 fprintf(out
, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst
-1); lineno
++;
4270 while( n
>0 && lemp
->sorted
[n
-1]->iNtOfst
==NO_OFFSET
) n
--;
4271 fprintf(out
, "#define YY_REDUCE_COUNT (%d)\n", n
-1); lineno
++;
4272 fprintf(out
, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst
); lineno
++;
4273 fprintf(out
, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst
); lineno
++;
4274 fprintf(out
, "static const %s yy_reduce_ofst[] = {\n",
4275 minimum_size_type(mnNtOfst
-1, mxNtOfst
, &sz
)); lineno
++;
4276 lemp
->tablesize
+= n
*sz
;
4277 for(i
=j
=0; i
<n
; i
++){
4279 stp
= lemp
->sorted
[i
];
4280 ofst
= stp
->iNtOfst
;
4281 if( ofst
==NO_OFFSET
) ofst
= mnNtOfst
- 1;
4282 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4283 fprintf(out
, " %4d,", ofst
);
4284 if( j
==9 || i
==n
-1 ){
4285 fprintf(out
, "\n"); lineno
++;
4291 fprintf(out
, "};\n"); lineno
++;
4293 /* Output the default action table */
4294 fprintf(out
, "static const YYACTIONTYPE yy_default[] = {\n"); lineno
++;
4296 lemp
->tablesize
+= n
*szActionType
;
4297 for(i
=j
=0; i
<n
; i
++){
4298 stp
= lemp
->sorted
[i
];
4299 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4300 fprintf(out
, " %4d,", stp
->iDfltReduce
+lemp
->nstate
+lemp
->nrule
);
4301 if( j
==9 || i
==n
-1 ){
4302 fprintf(out
, "\n"); lineno
++;
4308 fprintf(out
, "};\n"); lineno
++;
4309 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4311 /* Generate the table of fallback tokens.
4313 if( lemp
->has_fallback
){
4314 int mx
= lemp
->nterminal
- 1;
4315 while( mx
>0 && lemp
->symbols
[mx
]->fallback
==0 ){ mx
--; }
4316 lemp
->tablesize
+= (mx
+1)*szCodeType
;
4317 for(i
=0; i
<=mx
; i
++){
4318 struct symbol
*p
= lemp
->symbols
[i
];
4319 if( p
->fallback
==0 ){
4320 fprintf(out
, " 0, /* %10s => nothing */\n", p
->name
);
4322 fprintf(out
, " %3d, /* %10s => %s */\n", p
->fallback
->index
,
4323 p
->name
, p
->fallback
->name
);
4328 tplt_xfer(lemp
->name
, in
, out
, &lineno
);
4330 /* Generate a table containing the symbolic name of every symbol
4332 for(i
=0; i
<lemp
->nsymbol
; i
++){
4333 lemon_sprintf(line
,"\"%s\",",lemp
->symbols
[i
]->name
);
4334 fprintf(out
," %-15s",line
);
4335 if( (i
&3)==3 ){ fprintf(out
,"\n"); lineno
++; }
4337 if( (i
&3)!=0 ){ fprintf(out
,"\n"); lineno
++; }
4338 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4340 /* Generate a table containing a text string that describes every
4341 ** rule in the rule set of the grammar. This information is used
4342 ** when tracing REDUCE actions.
4344 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4345 assert( rp
->iRule
==i
);
4346 fprintf(out
," /* %3d */ \"", i
);
4347 writeRuleText(out
, rp
);
4348 fprintf(out
,"\",\n"); lineno
++;
4350 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4352 /* Generate code which executes every time a symbol is popped from
4353 ** the stack while processing errors or while destroying the parser.
4354 ** (In other words, generate the %destructor actions)
4356 if( lemp
->tokendest
){
4358 for(i
=0; i
<lemp
->nsymbol
; i
++){
4359 struct symbol
*sp
= lemp
->symbols
[i
];
4360 if( sp
==0 || sp
->type
!=TERMINAL
) continue;
4362 fprintf(out
, " /* TERMINAL Destructor */\n"); lineno
++;
4365 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4367 for(i
=0; i
<lemp
->nsymbol
&& lemp
->symbols
[i
]->type
!=TERMINAL
; i
++);
4368 if( i
<lemp
->nsymbol
){
4369 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4370 fprintf(out
," break;\n"); lineno
++;
4373 if( lemp
->vardest
){
4374 struct symbol
*dflt_sp
= 0;
4376 for(i
=0; i
<lemp
->nsymbol
; i
++){
4377 struct symbol
*sp
= lemp
->symbols
[i
];
4378 if( sp
==0 || sp
->type
==TERMINAL
||
4379 sp
->index
<=0 || sp
->destructor
!=0 ) continue;
4381 fprintf(out
, " /* Default NON-TERMINAL Destructor */\n"); lineno
++;
4384 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4388 emit_destructor_code(out
,dflt_sp
,lemp
,&lineno
);
4390 fprintf(out
," break;\n"); lineno
++;
4392 for(i
=0; i
<lemp
->nsymbol
; i
++){
4393 struct symbol
*sp
= lemp
->symbols
[i
];
4394 if( sp
==0 || sp
->type
==TERMINAL
|| sp
->destructor
==0 ) continue;
4395 if( sp
->destLineno
<0 ) continue; /* Already emitted */
4396 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4398 /* Combine duplicate destructors into a single case */
4399 for(j
=i
+1; j
<lemp
->nsymbol
; j
++){
4400 struct symbol
*sp2
= lemp
->symbols
[j
];
4401 if( sp2
&& sp2
->type
!=TERMINAL
&& sp2
->destructor
4402 && sp2
->dtnum
==sp
->dtnum
4403 && strcmp(sp
->destructor
,sp2
->destructor
)==0 ){
4404 fprintf(out
," case %d: /* %s */\n",
4405 sp2
->index
, sp2
->name
); lineno
++;
4406 sp2
->destLineno
= -1; /* Avoid emitting this destructor again */
4410 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4411 fprintf(out
," break;\n"); lineno
++;
4413 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4415 /* Generate code which executes whenever the parser stack overflows */
4416 tplt_print(out
,lemp
,lemp
->overflow
,&lineno
);
4417 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4419 /* Generate the table of rule information
4421 ** Note: This code depends on the fact that rules are number
4422 ** sequentually beginning with 0.
4424 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4425 fprintf(out
," { %d, %d },\n",rp
->lhs
->index
,-rp
->nrhs
); lineno
++;
4427 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4429 /* Generate code which execution during each REDUCE action */
4431 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4432 i
+= translate_code(lemp
, rp
);
4435 fprintf(out
," YYMINORTYPE yylhsminor;\n"); lineno
++;
4437 /* First output rules other than the default: rule */
4438 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4439 struct rule
*rp2
; /* Other rules with the same action */
4440 if( rp
->codeEmitted
) continue;
4442 /* No C code actions, so this will be part of the "default:" rule */
4445 fprintf(out
," case %d: /* ", rp
->iRule
);
4446 writeRuleText(out
, rp
);
4447 fprintf(out
, " */\n"); lineno
++;
4448 for(rp2
=rp
->next
; rp2
; rp2
=rp2
->next
){
4449 if( rp2
->code
==rp
->code
&& rp2
->codePrefix
==rp
->codePrefix
4450 && rp2
->codeSuffix
==rp
->codeSuffix
){
4451 fprintf(out
," case %d: /* ", rp2
->iRule
);
4452 writeRuleText(out
, rp2
);
4453 fprintf(out
," */ yytestcase(yyruleno==%d);\n", rp2
->iRule
); lineno
++;
4454 rp2
->codeEmitted
= 1;
4457 emit_code(out
,rp
,lemp
,&lineno
);
4458 fprintf(out
," break;\n"); lineno
++;
4459 rp
->codeEmitted
= 1;
4461 /* Finally, output the default: rule. We choose as the default: all
4462 ** empty actions. */
4463 fprintf(out
," default:\n"); lineno
++;
4464 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4465 if( rp
->codeEmitted
) continue;
4466 assert( rp
->noCode
);
4467 fprintf(out
," /* (%d) ", rp
->iRule
);
4468 writeRuleText(out
, rp
);
4469 if( rp
->doesReduce
){
4470 fprintf(out
, " */ yytestcase(yyruleno==%d);\n", rp
->iRule
); lineno
++;
4472 fprintf(out
, " (OPTIMIZED OUT) */ assert(yyruleno!=%d);\n",
4473 rp
->iRule
); lineno
++;
4476 fprintf(out
," break;\n"); lineno
++;
4477 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4479 /* Generate code which executes if a parse fails */
4480 tplt_print(out
,lemp
,lemp
->failure
,&lineno
);
4481 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4483 /* Generate code which executes when a syntax error occurs */
4484 tplt_print(out
,lemp
,lemp
->error
,&lineno
);
4485 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4487 /* Generate code which executes when the parser accepts its input */
4488 tplt_print(out
,lemp
,lemp
->accept
,&lineno
);
4489 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4491 /* Append any addition code the user desires */
4492 tplt_print(out
,lemp
,lemp
->extracode
,&lineno
);
4499 /* Generate a header file for the parser */
4500 void ReportHeader(struct lemon
*lemp
)
4504 char line
[LINESIZE
];
4505 char pattern
[LINESIZE
];
4508 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
4510 in
= file_open(lemp
,".h","rb");
4513 for(i
=1; i
<lemp
->nterminal
&& fgets(line
,LINESIZE
,in
); i
++){
4514 lemon_sprintf(pattern
,"#define %s%-30s %3d\n",
4515 prefix
,lemp
->symbols
[i
]->name
,i
);
4516 if( strcmp(line
,pattern
) ) break;
4518 nextChar
= fgetc(in
);
4520 if( i
==lemp
->nterminal
&& nextChar
==EOF
){
4521 /* No change in the file. Don't rewrite it. */
4525 out
= file_open(lemp
,".h","wb");
4527 for(i
=1; i
<lemp
->nterminal
; i
++){
4528 fprintf(out
,"#define %s%-30s %3d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
4535 /* Reduce the size of the action tables, if possible, by making use
4538 ** In this version, we take the most frequent REDUCE action and make
4539 ** it the default. Except, there is no default if the wildcard token
4540 ** is a possible look-ahead.
4542 void CompressTables(struct lemon
*lemp
)
4545 struct action
*ap
, *ap2
, *nextap
;
4546 struct rule
*rp
, *rp2
, *rbest
;
4551 for(i
=0; i
<lemp
->nstate
; i
++){
4552 stp
= lemp
->sorted
[i
];
4557 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4558 if( ap
->type
==SHIFT
&& ap
->sp
==lemp
->wildcard
){
4561 if( ap
->type
!=REDUCE
) continue;
4563 if( rp
->lhsStart
) continue;
4564 if( rp
==rbest
) continue;
4566 for(ap2
=ap
->next
; ap2
; ap2
=ap2
->next
){
4567 if( ap2
->type
!=REDUCE
) continue;
4569 if( rp2
==rbest
) continue;
4578 /* Do not make a default if the number of rules to default
4579 ** is not at least 1 or if the wildcard token is a possible
4582 if( nbest
<1 || usesWildcard
) continue;
4585 /* Combine matching REDUCE actions into a single default */
4586 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4587 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) break;
4590 ap
->sp
= Symbol_new("{default}");
4591 for(ap
=ap
->next
; ap
; ap
=ap
->next
){
4592 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) ap
->type
= NOT_USED
;
4594 stp
->ap
= Action_sort(stp
->ap
);
4596 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4597 if( ap
->type
==SHIFT
) break;
4598 if( ap
->type
==REDUCE
&& ap
->x
.rp
!=rbest
) break;
4601 stp
->autoReduce
= 1;
4602 stp
->pDfltReduce
= rbest
;
4606 /* Make a second pass over all states and actions. Convert
4607 ** every action that is a SHIFT to an autoReduce state into
4608 ** a SHIFTREDUCE action.
4610 for(i
=0; i
<lemp
->nstate
; i
++){
4611 stp
= lemp
->sorted
[i
];
4612 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4613 struct state
*pNextState
;
4614 if( ap
->type
!=SHIFT
) continue;
4615 pNextState
= ap
->x
.stp
;
4616 if( pNextState
->autoReduce
&& pNextState
->pDfltReduce
!=0 ){
4617 ap
->type
= SHIFTREDUCE
;
4618 ap
->x
.rp
= pNextState
->pDfltReduce
;
4623 /* If a SHIFTREDUCE action specifies a rule that has a single RHS term
4624 ** (meaning that the SHIFTREDUCE will land back in the state where it
4625 ** started) and if there is no C-code associated with the reduce action,
4626 ** then we can go ahead and convert the action to be the same as the
4627 ** action for the RHS of the rule.
4629 for(i
=0; i
<lemp
->nstate
; i
++){
4630 stp
= lemp
->sorted
[i
];
4631 for(ap
=stp
->ap
; ap
; ap
=nextap
){
4633 if( ap
->type
!=SHIFTREDUCE
) continue;
4635 if( rp
->noCode
==0 ) continue;
4636 if( rp
->nrhs
!=1 ) continue;
4638 /* Only apply this optimization to non-terminals. It would be OK to
4639 ** apply it to terminal symbols too, but that makes the parser tables
4641 if( ap
->sp
->index
<lemp
->nterminal
) continue;
4643 /* If we reach this point, it means the optimization can be applied */
4645 for(ap2
=stp
->ap
; ap2
&& (ap2
==ap
|| ap2
->sp
!=rp
->lhs
); ap2
=ap2
->next
){}
4647 ap
->spOpt
= ap2
->sp
;
4648 ap
->type
= ap2
->type
;
4656 ** Compare two states for sorting purposes. The smaller state is the
4657 ** one with the most non-terminal actions. If they have the same number
4658 ** of non-terminal actions, then the smaller is the one with the most
4661 static int stateResortCompare(const void *a
, const void *b
){
4662 const struct state
*pA
= *(const struct state
**)a
;
4663 const struct state
*pB
= *(const struct state
**)b
;
4666 n
= pB
->nNtAct
- pA
->nNtAct
;
4668 n
= pB
->nTknAct
- pA
->nTknAct
;
4670 n
= pB
->statenum
- pA
->statenum
;
4679 ** Renumber and resort states so that states with fewer choices
4680 ** occur at the end. Except, keep state 0 as the first state.
4682 void ResortStates(struct lemon
*lemp
)
4688 for(i
=0; i
<lemp
->nstate
; i
++){
4689 stp
= lemp
->sorted
[i
];
4690 stp
->nTknAct
= stp
->nNtAct
= 0;
4691 stp
->iDfltReduce
= lemp
->nrule
; /* Init dflt action to "syntax error" */
4692 stp
->iTknOfst
= NO_OFFSET
;
4693 stp
->iNtOfst
= NO_OFFSET
;
4694 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4695 int iAction
= compute_action(lemp
,ap
);
4697 if( ap
->sp
->index
<lemp
->nterminal
){
4699 }else if( ap
->sp
->index
<lemp
->nsymbol
){
4702 assert( stp
->autoReduce
==0 || stp
->pDfltReduce
==ap
->x
.rp
);
4703 stp
->iDfltReduce
= iAction
- lemp
->nstate
- lemp
->nrule
;
4708 qsort(&lemp
->sorted
[1], lemp
->nstate
-1, sizeof(lemp
->sorted
[0]),
4709 stateResortCompare
);
4710 for(i
=0; i
<lemp
->nstate
; i
++){
4711 lemp
->sorted
[i
]->statenum
= i
;
4713 lemp
->nxstate
= lemp
->nstate
;
4714 while( lemp
->nxstate
>1 && lemp
->sorted
[lemp
->nxstate
-1]->autoReduce
){
4720 /***************** From the file "set.c" ************************************/
4722 ** Set manipulation routines for the LEMON parser generator.
4725 static int size
= 0;
4727 /* Set the set size */
4733 /* Allocate a new set */
4736 s
= (char*)calloc( size
, 1);
4738 extern void memory_error();
4744 /* Deallocate a set */
4745 void SetFree(char *s
)
4750 /* Add a new element to the set. Return TRUE if the element was added
4751 ** and FALSE if it was already there. */
4752 int SetAdd(char *s
, int e
)
4755 assert( e
>=0 && e
<size
);
4761 /* Add every element of s2 to s1. Return TRUE if s1 changes. */
4762 int SetUnion(char *s1
, char *s2
)
4766 for(i
=0; i
<size
; i
++){
4767 if( s2
[i
]==0 ) continue;
4775 /********************** From the file "table.c" ****************************/
4777 ** All code in this file has been automatically generated
4778 ** from a specification in the file
4780 ** by the associative array code building program "aagen".
4781 ** Do not edit this file! Instead, edit the specification
4782 ** file, then rerun aagen.
4785 ** Code for processing tables in the LEMON parser generator.
4788 PRIVATE
unsigned strhash(const char *x
)
4791 while( *x
) h
= h
*13 + *(x
++);
4795 /* Works like strdup, sort of. Save a string in malloced memory, but
4796 ** keep strings in a table so that the same string is not in more
4799 const char *Strsafe(const char *y
)
4804 if( y
==0 ) return 0;
4805 z
= Strsafe_find(y
);
4806 if( z
==0 && (cpy
=(char *)malloc( lemonStrlen(y
)+1 ))!=0 ){
4807 lemon_strcpy(cpy
,y
);
4815 /* There is one instance of the following structure for each
4816 ** associative array of type "x1".
4819 int size
; /* The number of available slots. */
4820 /* Must be a power of 2 greater than or */
4822 int count
; /* Number of currently slots filled */
4823 struct s_x1node
*tbl
; /* The data stored here */
4824 struct s_x1node
**ht
; /* Hash table for lookups */
4827 /* There is one instance of this structure for every data element
4828 ** in an associative array of type "x1".
4830 typedef struct s_x1node
{
4831 const char *data
; /* The data */
4832 struct s_x1node
*next
; /* Next entry with the same hash */
4833 struct s_x1node
**from
; /* Previous link */
4836 /* There is only one instance of the array, which is the following */
4837 static struct s_x1
*x1a
;
4839 /* Allocate a new associative array */
4840 void Strsafe_init(void){
4842 x1a
= (struct s_x1
*)malloc( sizeof(struct s_x1
) );
4846 x1a
->tbl
= (x1node
*)calloc(1024, sizeof(x1node
) + sizeof(x1node
*));
4852 x1a
->ht
= (x1node
**)&(x1a
->tbl
[1024]);
4853 for(i
=0; i
<1024; i
++) x1a
->ht
[i
] = 0;
4857 /* Insert a new record into the array. Return TRUE if successful.
4858 ** Prior data with the same key is NOT overwritten */
4859 int Strsafe_insert(const char *data
)
4865 if( x1a
==0 ) return 0;
4867 h
= ph
& (x1a
->size
-1);
4870 if( strcmp(np
->data
,data
)==0 ){
4871 /* An existing entry with the same key is found. */
4872 /* Fail because overwrite is not allows. */
4877 if( x1a
->count
>=x1a
->size
){
4878 /* Need to make the hash table bigger */
4881 array
.size
= arrSize
= x1a
->size
*2;
4882 array
.count
= x1a
->count
;
4883 array
.tbl
= (x1node
*)calloc(arrSize
, sizeof(x1node
) + sizeof(x1node
*));
4884 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
4885 array
.ht
= (x1node
**)&(array
.tbl
[arrSize
]);
4886 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
4887 for(i
=0; i
<x1a
->count
; i
++){
4888 x1node
*oldnp
, *newnp
;
4889 oldnp
= &(x1a
->tbl
[i
]);
4890 h
= strhash(oldnp
->data
) & (arrSize
-1);
4891 newnp
= &(array
.tbl
[i
]);
4892 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4893 newnp
->next
= array
.ht
[h
];
4894 newnp
->data
= oldnp
->data
;
4895 newnp
->from
= &(array
.ht
[h
]);
4896 array
.ht
[h
] = newnp
;
4901 /* Insert the new data */
4902 h
= ph
& (x1a
->size
-1);
4903 np
= &(x1a
->tbl
[x1a
->count
++]);
4905 if( x1a
->ht
[h
] ) x1a
->ht
[h
]->from
= &(np
->next
);
4906 np
->next
= x1a
->ht
[h
];
4908 np
->from
= &(x1a
->ht
[h
]);
4912 /* Return a pointer to data assigned to the given key. Return NULL
4913 ** if no such key. */
4914 const char *Strsafe_find(const char *key
)
4919 if( x1a
==0 ) return 0;
4920 h
= strhash(key
) & (x1a
->size
-1);
4923 if( strcmp(np
->data
,key
)==0 ) break;
4926 return np
? np
->data
: 0;
4929 /* Return a pointer to the (terminal or nonterminal) symbol "x".
4930 ** Create a new symbol if this is the first time "x" has been seen.
4932 struct symbol
*Symbol_new(const char *x
)
4936 sp
= Symbol_find(x
);
4938 sp
= (struct symbol
*)calloc(1, sizeof(struct symbol
) );
4940 sp
->name
= Strsafe(x
);
4941 sp
->type
= ISUPPER(*x
) ? TERMINAL
: NONTERMINAL
;
4947 sp
->lambda
= LEMON_FALSE
;
4952 Symbol_insert(sp
,sp
->name
);
4958 /* Compare two symbols for sorting purposes. Return negative,
4959 ** zero, or positive if a is less then, equal to, or greater
4962 ** Symbols that begin with upper case letters (terminals or tokens)
4963 ** must sort before symbols that begin with lower case letters
4964 ** (non-terminals). And MULTITERMINAL symbols (created using the
4965 ** %token_class directive) must sort at the very end. Other than
4966 ** that, the order does not matter.
4968 ** We find experimentally that leaving the symbols in their original
4969 ** order (the order they appeared in the grammar file) gives the
4970 ** smallest parser tables in SQLite.
4972 int Symbolcmpp(const void *_a
, const void *_b
)
4974 const struct symbol
*a
= *(const struct symbol
**) _a
;
4975 const struct symbol
*b
= *(const struct symbol
**) _b
;
4976 int i1
= a
->type
==MULTITERMINAL
? 3 : a
->name
[0]>'Z' ? 2 : 1;
4977 int i2
= b
->type
==MULTITERMINAL
? 3 : b
->name
[0]>'Z' ? 2 : 1;
4978 return i1
==i2
? a
->index
- b
->index
: i1
- i2
;
4981 /* There is one instance of the following structure for each
4982 ** associative array of type "x2".
4985 int size
; /* The number of available slots. */
4986 /* Must be a power of 2 greater than or */
4988 int count
; /* Number of currently slots filled */
4989 struct s_x2node
*tbl
; /* The data stored here */
4990 struct s_x2node
**ht
; /* Hash table for lookups */
4993 /* There is one instance of this structure for every data element
4994 ** in an associative array of type "x2".
4996 typedef struct s_x2node
{
4997 struct symbol
*data
; /* The data */
4998 const char *key
; /* The key */
4999 struct s_x2node
*next
; /* Next entry with the same hash */
5000 struct s_x2node
**from
; /* Previous link */
5003 /* There is only one instance of the array, which is the following */
5004 static struct s_x2
*x2a
;
5006 /* Allocate a new associative array */
5007 void Symbol_init(void){
5009 x2a
= (struct s_x2
*)malloc( sizeof(struct s_x2
) );
5013 x2a
->tbl
= (x2node
*)calloc(128, sizeof(x2node
) + sizeof(x2node
*));
5019 x2a
->ht
= (x2node
**)&(x2a
->tbl
[128]);
5020 for(i
=0; i
<128; i
++) x2a
->ht
[i
] = 0;
5024 /* Insert a new record into the array. Return TRUE if successful.
5025 ** Prior data with the same key is NOT overwritten */
5026 int Symbol_insert(struct symbol
*data
, const char *key
)
5032 if( x2a
==0 ) return 0;
5034 h
= ph
& (x2a
->size
-1);
5037 if( strcmp(np
->key
,key
)==0 ){
5038 /* An existing entry with the same key is found. */
5039 /* Fail because overwrite is not allows. */
5044 if( x2a
->count
>=x2a
->size
){
5045 /* Need to make the hash table bigger */
5048 array
.size
= arrSize
= x2a
->size
*2;
5049 array
.count
= x2a
->count
;
5050 array
.tbl
= (x2node
*)calloc(arrSize
, sizeof(x2node
) + sizeof(x2node
*));
5051 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5052 array
.ht
= (x2node
**)&(array
.tbl
[arrSize
]);
5053 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5054 for(i
=0; i
<x2a
->count
; i
++){
5055 x2node
*oldnp
, *newnp
;
5056 oldnp
= &(x2a
->tbl
[i
]);
5057 h
= strhash(oldnp
->key
) & (arrSize
-1);
5058 newnp
= &(array
.tbl
[i
]);
5059 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5060 newnp
->next
= array
.ht
[h
];
5061 newnp
->key
= oldnp
->key
;
5062 newnp
->data
= oldnp
->data
;
5063 newnp
->from
= &(array
.ht
[h
]);
5064 array
.ht
[h
] = newnp
;
5069 /* Insert the new data */
5070 h
= ph
& (x2a
->size
-1);
5071 np
= &(x2a
->tbl
[x2a
->count
++]);
5074 if( x2a
->ht
[h
] ) x2a
->ht
[h
]->from
= &(np
->next
);
5075 np
->next
= x2a
->ht
[h
];
5077 np
->from
= &(x2a
->ht
[h
]);
5081 /* Return a pointer to data assigned to the given key. Return NULL
5082 ** if no such key. */
5083 struct symbol
*Symbol_find(const char *key
)
5088 if( x2a
==0 ) return 0;
5089 h
= strhash(key
) & (x2a
->size
-1);
5092 if( strcmp(np
->key
,key
)==0 ) break;
5095 return np
? np
->data
: 0;
5098 /* Return the n-th data. Return NULL if n is out of range. */
5099 struct symbol
*Symbol_Nth(int n
)
5101 struct symbol
*data
;
5102 if( x2a
&& n
>0 && n
<=x2a
->count
){
5103 data
= x2a
->tbl
[n
-1].data
;
5110 /* Return the size of the array */
5113 return x2a
? x2a
->count
: 0;
5116 /* Return an array of pointers to all data in the table.
5117 ** The array is obtained from malloc. Return NULL if memory allocation
5118 ** problems, or if the array is empty. */
5119 struct symbol
**Symbol_arrayof()
5121 struct symbol
**array
;
5123 if( x2a
==0 ) return 0;
5124 arrSize
= x2a
->count
;
5125 array
= (struct symbol
**)calloc(arrSize
, sizeof(struct symbol
*));
5127 for(i
=0; i
<arrSize
; i
++) array
[i
] = x2a
->tbl
[i
].data
;
5132 /* Compare two configurations */
5133 int Configcmp(const char *_a
,const char *_b
)
5135 const struct config
*a
= (struct config
*) _a
;
5136 const struct config
*b
= (struct config
*) _b
;
5138 x
= a
->rp
->index
- b
->rp
->index
;
5139 if( x
==0 ) x
= a
->dot
- b
->dot
;
5143 /* Compare two states */
5144 PRIVATE
int statecmp(struct config
*a
, struct config
*b
)
5147 for(rc
=0; rc
==0 && a
&& b
; a
=a
->bp
, b
=b
->bp
){
5148 rc
= a
->rp
->index
- b
->rp
->index
;
5149 if( rc
==0 ) rc
= a
->dot
- b
->dot
;
5159 PRIVATE
unsigned statehash(struct config
*a
)
5163 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
5169 /* Allocate a new state structure */
5170 struct state
*State_new()
5172 struct state
*newstate
;
5173 newstate
= (struct state
*)calloc(1, sizeof(struct state
) );
5174 MemoryCheck(newstate
);
5178 /* There is one instance of the following structure for each
5179 ** associative array of type "x3".
5182 int size
; /* The number of available slots. */
5183 /* Must be a power of 2 greater than or */
5185 int count
; /* Number of currently slots filled */
5186 struct s_x3node
*tbl
; /* The data stored here */
5187 struct s_x3node
**ht
; /* Hash table for lookups */
5190 /* There is one instance of this structure for every data element
5191 ** in an associative array of type "x3".
5193 typedef struct s_x3node
{
5194 struct state
*data
; /* The data */
5195 struct config
*key
; /* The key */
5196 struct s_x3node
*next
; /* Next entry with the same hash */
5197 struct s_x3node
**from
; /* Previous link */
5200 /* There is only one instance of the array, which is the following */
5201 static struct s_x3
*x3a
;
5203 /* Allocate a new associative array */
5204 void State_init(void){
5206 x3a
= (struct s_x3
*)malloc( sizeof(struct s_x3
) );
5210 x3a
->tbl
= (x3node
*)calloc(128, sizeof(x3node
) + sizeof(x3node
*));
5216 x3a
->ht
= (x3node
**)&(x3a
->tbl
[128]);
5217 for(i
=0; i
<128; i
++) x3a
->ht
[i
] = 0;
5221 /* Insert a new record into the array. Return TRUE if successful.
5222 ** Prior data with the same key is NOT overwritten */
5223 int State_insert(struct state
*data
, struct config
*key
)
5229 if( x3a
==0 ) return 0;
5230 ph
= statehash(key
);
5231 h
= ph
& (x3a
->size
-1);
5234 if( statecmp(np
->key
,key
)==0 ){
5235 /* An existing entry with the same key is found. */
5236 /* Fail because overwrite is not allows. */
5241 if( x3a
->count
>=x3a
->size
){
5242 /* Need to make the hash table bigger */
5245 array
.size
= arrSize
= x3a
->size
*2;
5246 array
.count
= x3a
->count
;
5247 array
.tbl
= (x3node
*)calloc(arrSize
, sizeof(x3node
) + sizeof(x3node
*));
5248 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5249 array
.ht
= (x3node
**)&(array
.tbl
[arrSize
]);
5250 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5251 for(i
=0; i
<x3a
->count
; i
++){
5252 x3node
*oldnp
, *newnp
;
5253 oldnp
= &(x3a
->tbl
[i
]);
5254 h
= statehash(oldnp
->key
) & (arrSize
-1);
5255 newnp
= &(array
.tbl
[i
]);
5256 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5257 newnp
->next
= array
.ht
[h
];
5258 newnp
->key
= oldnp
->key
;
5259 newnp
->data
= oldnp
->data
;
5260 newnp
->from
= &(array
.ht
[h
]);
5261 array
.ht
[h
] = newnp
;
5266 /* Insert the new data */
5267 h
= ph
& (x3a
->size
-1);
5268 np
= &(x3a
->tbl
[x3a
->count
++]);
5271 if( x3a
->ht
[h
] ) x3a
->ht
[h
]->from
= &(np
->next
);
5272 np
->next
= x3a
->ht
[h
];
5274 np
->from
= &(x3a
->ht
[h
]);
5278 /* Return a pointer to data assigned to the given key. Return NULL
5279 ** if no such key. */
5280 struct state
*State_find(struct config
*key
)
5285 if( x3a
==0 ) return 0;
5286 h
= statehash(key
) & (x3a
->size
-1);
5289 if( statecmp(np
->key
,key
)==0 ) break;
5292 return np
? np
->data
: 0;
5295 /* Return an array of pointers to all data in the table.
5296 ** The array is obtained from malloc. Return NULL if memory allocation
5297 ** problems, or if the array is empty. */
5298 struct state
**State_arrayof(void)
5300 struct state
**array
;
5302 if( x3a
==0 ) return 0;
5303 arrSize
= x3a
->count
;
5304 array
= (struct state
**)calloc(arrSize
, sizeof(struct state
*));
5306 for(i
=0; i
<arrSize
; i
++) array
[i
] = x3a
->tbl
[i
].data
;
5311 /* Hash a configuration */
5312 PRIVATE
unsigned confighash(struct config
*a
)
5315 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
5319 /* There is one instance of the following structure for each
5320 ** associative array of type "x4".
5323 int size
; /* The number of available slots. */
5324 /* Must be a power of 2 greater than or */
5326 int count
; /* Number of currently slots filled */
5327 struct s_x4node
*tbl
; /* The data stored here */
5328 struct s_x4node
**ht
; /* Hash table for lookups */
5331 /* There is one instance of this structure for every data element
5332 ** in an associative array of type "x4".
5334 typedef struct s_x4node
{
5335 struct config
*data
; /* The data */
5336 struct s_x4node
*next
; /* Next entry with the same hash */
5337 struct s_x4node
**from
; /* Previous link */
5340 /* There is only one instance of the array, which is the following */
5341 static struct s_x4
*x4a
;
5343 /* Allocate a new associative array */
5344 void Configtable_init(void){
5346 x4a
= (struct s_x4
*)malloc( sizeof(struct s_x4
) );
5350 x4a
->tbl
= (x4node
*)calloc(64, sizeof(x4node
) + sizeof(x4node
*));
5356 x4a
->ht
= (x4node
**)&(x4a
->tbl
[64]);
5357 for(i
=0; i
<64; i
++) x4a
->ht
[i
] = 0;
5361 /* Insert a new record into the array. Return TRUE if successful.
5362 ** Prior data with the same key is NOT overwritten */
5363 int Configtable_insert(struct config
*data
)
5369 if( x4a
==0 ) return 0;
5370 ph
= confighash(data
);
5371 h
= ph
& (x4a
->size
-1);
5374 if( Configcmp((const char *) np
->data
,(const char *) data
)==0 ){
5375 /* An existing entry with the same key is found. */
5376 /* Fail because overwrite is not allows. */
5381 if( x4a
->count
>=x4a
->size
){
5382 /* Need to make the hash table bigger */
5385 array
.size
= arrSize
= x4a
->size
*2;
5386 array
.count
= x4a
->count
;
5387 array
.tbl
= (x4node
*)calloc(arrSize
, sizeof(x4node
) + sizeof(x4node
*));
5388 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5389 array
.ht
= (x4node
**)&(array
.tbl
[arrSize
]);
5390 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5391 for(i
=0; i
<x4a
->count
; i
++){
5392 x4node
*oldnp
, *newnp
;
5393 oldnp
= &(x4a
->tbl
[i
]);
5394 h
= confighash(oldnp
->data
) & (arrSize
-1);
5395 newnp
= &(array
.tbl
[i
]);
5396 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5397 newnp
->next
= array
.ht
[h
];
5398 newnp
->data
= oldnp
->data
;
5399 newnp
->from
= &(array
.ht
[h
]);
5400 array
.ht
[h
] = newnp
;
5405 /* Insert the new data */
5406 h
= ph
& (x4a
->size
-1);
5407 np
= &(x4a
->tbl
[x4a
->count
++]);
5409 if( x4a
->ht
[h
] ) x4a
->ht
[h
]->from
= &(np
->next
);
5410 np
->next
= x4a
->ht
[h
];
5412 np
->from
= &(x4a
->ht
[h
]);
5416 /* Return a pointer to data assigned to the given key. Return NULL
5417 ** if no such key. */
5418 struct config
*Configtable_find(struct config
*key
)
5423 if( x4a
==0 ) return 0;
5424 h
= confighash(key
) & (x4a
->size
-1);
5427 if( Configcmp((const char *) np
->data
,(const char *) key
)==0 ) break;
5430 return np
? np
->data
: 0;
5433 /* Remove all data from the table. Pass each data to the function "f"
5434 ** as it is removed. ("f" may be null to avoid this step.) */
5435 void Configtable_clear(int(*f
)(struct config
*))
5438 if( x4a
==0 || x4a
->count
==0 ) return;
5439 if( f
) for(i
=0; i
<x4a
->count
; i
++) (*f
)(x4a
->tbl
[i
].data
);
5440 for(i
=0; i
<x4a
->size
; i
++) x4a
->ht
[i
] = 0;