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 int minShiftReduce
; /* Minimum shift-reduce action value */
388 int errAction
; /* Error action value */
389 int accAction
; /* Accept action value */
390 int noAction
; /* No-op action value */
391 int minReduce
; /* Minimum reduce action */
392 int maxAction
; /* Maximum action value of any kind */
393 struct symbol
**symbols
; /* Sorted array of pointers to symbols */
394 int errorcnt
; /* Number of errors */
395 struct symbol
*errsym
; /* The error symbol */
396 struct symbol
*wildcard
; /* Token that matches anything */
397 char *name
; /* Name of the generated parser */
398 char *arg
; /* Declaration of the 3th argument to parser */
399 char *tokentype
; /* Type of terminal symbols in the parser stack */
400 char *vartype
; /* The default type of non-terminal symbols */
401 char *start
; /* Name of the start symbol for the grammar */
402 char *stacksize
; /* Size of the parser stack */
403 char *include
; /* Code to put at the start of the C file */
404 char *error
; /* Code to execute when an error is seen */
405 char *overflow
; /* Code to execute on a stack overflow */
406 char *failure
; /* Code to execute on parser failure */
407 char *accept
; /* Code to execute when the parser excepts */
408 char *extracode
; /* Code appended to the generated file */
409 char *tokendest
; /* Code to execute to destroy token data */
410 char *vardest
; /* Code for the default non-terminal destructor */
411 char *filename
; /* Name of the input file */
412 char *outname
; /* Name of the current output file */
413 char *tokenprefix
; /* A prefix added to token names in the .h file */
414 int nconflict
; /* Number of parsing conflicts */
415 int nactiontab
; /* Number of entries in the yy_action[] table */
416 int nlookaheadtab
; /* Number of entries in yy_lookahead[] */
417 int tablesize
; /* Total table size of all tables in bytes */
418 int basisflag
; /* Print only basis configurations */
419 int has_fallback
; /* True if any %fallback is seen in the grammar */
420 int nolinenosflag
; /* True if #line statements should not be printed */
421 char *argv0
; /* Name of the program */
424 #define MemoryCheck(X) if((X)==0){ \
425 extern void memory_error(); \
429 /**************** From the file "table.h" *********************************/
431 ** All code in this file has been automatically generated
432 ** from a specification in the file
434 ** by the associative array code building program "aagen".
435 ** Do not edit this file! Instead, edit the specification
436 ** file, then rerun aagen.
439 ** Code for processing tables in the LEMON parser generator.
441 /* Routines for handling a strings */
443 const char *Strsafe(const char *);
445 void Strsafe_init(void);
446 int Strsafe_insert(const char *);
447 const char *Strsafe_find(const char *);
449 /* Routines for handling symbols of the grammar */
451 struct symbol
*Symbol_new(const char *);
452 int Symbolcmpp(const void *, const void *);
453 void Symbol_init(void);
454 int Symbol_insert(struct symbol
*, const char *);
455 struct symbol
*Symbol_find(const char *);
456 struct symbol
*Symbol_Nth(int);
457 int Symbol_count(void);
458 struct symbol
**Symbol_arrayof(void);
460 /* Routines to manage the state table */
462 int Configcmp(const char *, const char *);
463 struct state
*State_new(void);
464 void State_init(void);
465 int State_insert(struct state
*, struct config
*);
466 struct state
*State_find(struct config
*);
467 struct state
**State_arrayof(void);
469 /* Routines used for efficiency in Configlist_add */
471 void Configtable_init(void);
472 int Configtable_insert(struct config
*);
473 struct config
*Configtable_find(struct config
*);
474 void Configtable_clear(int(*)(struct config
*));
476 /****************** From the file "action.c" *******************************/
478 ** Routines processing parser actions in the LEMON parser generator.
481 /* Allocate a new parser action */
482 static struct action
*Action_new(void){
483 static struct action
*freelist
= 0;
484 struct action
*newaction
;
489 freelist
= (struct action
*)calloc(amt
, sizeof(struct action
));
491 fprintf(stderr
,"Unable to allocate memory for a new parser action.");
494 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
495 freelist
[amt
-1].next
= 0;
497 newaction
= freelist
;
498 freelist
= freelist
->next
;
502 /* Compare two actions for sorting purposes. Return negative, zero, or
503 ** positive if the first action is less than, equal to, or greater than
506 static int actioncmp(
511 rc
= ap1
->sp
->index
- ap2
->sp
->index
;
513 rc
= (int)ap1
->type
- (int)ap2
->type
;
515 if( rc
==0 && (ap1
->type
==REDUCE
|| ap1
->type
==SHIFTREDUCE
) ){
516 rc
= ap1
->x
.rp
->index
- ap2
->x
.rp
->index
;
519 rc
= (int) (ap2
- ap1
);
524 /* Sort parser actions */
525 static struct action
*Action_sort(
528 ap
= (struct action
*)msort((char *)ap
,(char **)&ap
->next
,
529 (int(*)(const char*,const char*))actioncmp
);
539 struct action
*newaction
;
540 newaction
= Action_new();
541 newaction
->next
= *app
;
543 newaction
->type
= type
;
545 newaction
->spOpt
= 0;
547 newaction
->x
.stp
= (struct state
*)arg
;
549 newaction
->x
.rp
= (struct rule
*)arg
;
552 /********************** New code to implement the "acttab" module ***********/
554 ** This module implements routines use to construct the yy_action[] table.
558 ** The state of the yy_action table under construction is an instance of
559 ** the following structure.
561 ** The yy_action table maps the pair (state_number, lookahead) into an
562 ** action_number. The table is an array of integers pairs. The state_number
563 ** determines an initial offset into the yy_action array. The lookahead
564 ** value is then added to this initial offset to get an index X into the
565 ** yy_action array. If the aAction[X].lookahead equals the value of the
566 ** of the lookahead input, then the value of the action_number output is
567 ** aAction[X].action. If the lookaheads do not match then the
568 ** default action for the state_number is returned.
570 ** All actions associated with a single state_number are first entered
571 ** into aLookahead[] using multiple calls to acttab_action(). Then the
572 ** actions for that single state_number are placed into the aAction[]
573 ** array with a single call to acttab_insert(). The acttab_insert() call
574 ** also resets the aLookahead[] array in preparation for the next
577 struct lookahead_action
{
578 int lookahead
; /* Value of the lookahead token */
579 int action
; /* Action to take on the given lookahead */
581 typedef struct acttab acttab
;
583 int nAction
; /* Number of used slots in aAction[] */
584 int nActionAlloc
; /* Slots allocated for aAction[] */
585 struct lookahead_action
586 *aAction
, /* The yy_action[] table under construction */
587 *aLookahead
; /* A single new transaction set */
588 int mnLookahead
; /* Minimum aLookahead[].lookahead */
589 int mnAction
; /* Action associated with mnLookahead */
590 int mxLookahead
; /* Maximum aLookahead[].lookahead */
591 int nLookahead
; /* Used slots in aLookahead[] */
592 int nLookaheadAlloc
; /* Slots allocated in aLookahead[] */
593 int nterminal
; /* Number of terminal symbols */
594 int nsymbol
; /* total number of symbols */
597 /* Return the number of entries in the yy_action table */
598 #define acttab_lookahead_size(X) ((X)->nAction)
600 /* The value for the N-th entry in yy_action */
601 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
603 /* The value for the N-th entry in yy_lookahead */
604 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
606 /* Free all memory associated with the given acttab */
607 void acttab_free(acttab
*p
){
609 free( p
->aLookahead
);
613 /* Allocate a new acttab structure */
614 acttab
*acttab_alloc(int nsymbol
, int nterminal
){
615 acttab
*p
= (acttab
*) calloc( 1, sizeof(*p
) );
617 fprintf(stderr
,"Unable to allocate memory for a new acttab.");
620 memset(p
, 0, sizeof(*p
));
621 p
->nsymbol
= nsymbol
;
622 p
->nterminal
= nterminal
;
626 /* Add a new action to the current transaction set.
628 ** This routine is called once for each lookahead for a particular
631 void acttab_action(acttab
*p
, int lookahead
, int action
){
632 if( p
->nLookahead
>=p
->nLookaheadAlloc
){
633 p
->nLookaheadAlloc
+= 25;
634 p
->aLookahead
= (struct lookahead_action
*) realloc( p
->aLookahead
,
635 sizeof(p
->aLookahead
[0])*p
->nLookaheadAlloc
);
636 if( p
->aLookahead
==0 ){
637 fprintf(stderr
,"malloc failed\n");
641 if( p
->nLookahead
==0 ){
642 p
->mxLookahead
= lookahead
;
643 p
->mnLookahead
= lookahead
;
644 p
->mnAction
= action
;
646 if( p
->mxLookahead
<lookahead
) p
->mxLookahead
= lookahead
;
647 if( p
->mnLookahead
>lookahead
){
648 p
->mnLookahead
= lookahead
;
649 p
->mnAction
= action
;
652 p
->aLookahead
[p
->nLookahead
].lookahead
= lookahead
;
653 p
->aLookahead
[p
->nLookahead
].action
= action
;
658 ** Add the transaction set built up with prior calls to acttab_action()
659 ** into the current action table. Then reset the transaction set back
660 ** to an empty set in preparation for a new round of acttab_action() calls.
662 ** Return the offset into the action table of the new transaction.
664 ** If the makeItSafe parameter is true, then the offset is chosen so that
665 ** it is impossible to overread the yy_lookaside[] table regardless of
666 ** the lookaside token. This is done for the terminal symbols, as they
667 ** come from external inputs and can contain syntax errors. When makeItSafe
668 ** is false, there is more flexibility in selecting offsets, resulting in
669 ** a smaller table. For non-terminal symbols, which are never syntax errors,
670 ** makeItSafe can be false.
672 int acttab_insert(acttab
*p
, int makeItSafe
){
674 assert( p
->nLookahead
>0 );
676 /* Make sure we have enough space to hold the expanded action table
677 ** in the worst case. The worst case occurs if the transaction set
678 ** must be appended to the current action table
681 if( p
->nAction
+ n
>= p
->nActionAlloc
){
682 int oldAlloc
= p
->nActionAlloc
;
683 p
->nActionAlloc
= p
->nAction
+ n
+ p
->nActionAlloc
+ 20;
684 p
->aAction
= (struct lookahead_action
*) realloc( p
->aAction
,
685 sizeof(p
->aAction
[0])*p
->nActionAlloc
);
687 fprintf(stderr
,"malloc failed\n");
690 for(i
=oldAlloc
; i
<p
->nActionAlloc
; i
++){
691 p
->aAction
[i
].lookahead
= -1;
692 p
->aAction
[i
].action
= -1;
696 /* Scan the existing action table looking for an offset that is a
697 ** duplicate of the current transaction set. Fall out of the loop
698 ** if and when the duplicate is found.
700 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
702 end
= makeItSafe
? p
->mnLookahead
: 0;
703 for(i
=p
->nAction
-1; i
>=end
; i
--){
704 if( p
->aAction
[i
].lookahead
==p
->mnLookahead
){
705 /* All lookaheads and actions in the aLookahead[] transaction
706 ** must match against the candidate aAction[i] entry. */
707 if( p
->aAction
[i
].action
!=p
->mnAction
) continue;
708 for(j
=0; j
<p
->nLookahead
; j
++){
709 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
710 if( k
<0 || k
>=p
->nAction
) break;
711 if( p
->aLookahead
[j
].lookahead
!=p
->aAction
[k
].lookahead
) break;
712 if( p
->aLookahead
[j
].action
!=p
->aAction
[k
].action
) break;
714 if( j
<p
->nLookahead
) continue;
716 /* No possible lookahead value that is not in the aLookahead[]
717 ** transaction is allowed to match aAction[i] */
719 for(j
=0; j
<p
->nAction
; j
++){
720 if( p
->aAction
[j
].lookahead
<0 ) continue;
721 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) n
++;
723 if( n
==p
->nLookahead
){
724 break; /* An exact match is found at offset i */
729 /* If no existing offsets exactly match the current transaction, find an
730 ** an empty offset in the aAction[] table in which we can add the
731 ** aLookahead[] transaction.
734 /* Look for holes in the aAction[] table that fit the current
735 ** aLookahead[] transaction. Leave i set to the offset of the hole.
736 ** If no holes are found, i is left at p->nAction, which means the
737 ** transaction will be appended. */
738 i
= makeItSafe
? p
->mnLookahead
: 0;
739 for(; i
<p
->nActionAlloc
- p
->mxLookahead
; i
++){
740 if( p
->aAction
[i
].lookahead
<0 ){
741 for(j
=0; j
<p
->nLookahead
; j
++){
742 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
744 if( p
->aAction
[k
].lookahead
>=0 ) break;
746 if( j
<p
->nLookahead
) continue;
747 for(j
=0; j
<p
->nAction
; j
++){
748 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) break;
751 break; /* Fits in empty slots */
756 /* Insert transaction set at index i. */
759 for(j
=0; j
<p
->nLookahead
; j
++){
760 printf(" %d", p
->aLookahead
[j
].lookahead
);
762 printf(" inserted at %d\n", i
);
764 for(j
=0; j
<p
->nLookahead
; j
++){
765 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
766 p
->aAction
[k
] = p
->aLookahead
[j
];
767 if( k
>=p
->nAction
) p
->nAction
= k
+1;
769 if( makeItSafe
&& i
+p
->nterminal
>=p
->nAction
) p
->nAction
= i
+p
->nterminal
+1;
772 /* Return the offset that is added to the lookahead in order to get the
773 ** index into yy_action of the action */
774 return i
- p
->mnLookahead
;
778 ** Return the size of the action table without the trailing syntax error
781 int acttab_action_size(acttab
*p
){
783 while( n
>0 && p
->aAction
[n
-1].lookahead
<0 ){ n
--; }
787 /********************** From the file "build.c" *****************************/
789 ** Routines to construction the finite state machine for the LEMON
793 /* Find a precedence symbol of every rule in the grammar.
795 ** Those rules which have a precedence symbol coded in the input
796 ** grammar using the "[symbol]" construct will already have the
797 ** rp->precsym field filled. Other rules take as their precedence
798 ** symbol the first RHS symbol with a defined precedence. If there
799 ** are not RHS symbols with a defined precedence, the precedence
800 ** symbol field is left blank.
802 void FindRulePrecedences(struct lemon
*xp
)
805 for(rp
=xp
->rule
; rp
; rp
=rp
->next
){
806 if( rp
->precsym
==0 ){
808 for(i
=0; i
<rp
->nrhs
&& rp
->precsym
==0; i
++){
809 struct symbol
*sp
= rp
->rhs
[i
];
810 if( sp
->type
==MULTITERMINAL
){
811 for(j
=0; j
<sp
->nsubsym
; j
++){
812 if( sp
->subsym
[j
]->prec
>=0 ){
813 rp
->precsym
= sp
->subsym
[j
];
817 }else if( sp
->prec
>=0 ){
818 rp
->precsym
= rp
->rhs
[i
];
826 /* Find all nonterminals which will generate the empty string.
827 ** Then go back and compute the first sets of every nonterminal.
828 ** The first set is the set of all terminal symbols which can begin
829 ** a string generated by that nonterminal.
831 void FindFirstSets(struct lemon
*lemp
)
837 for(i
=0; i
<lemp
->nsymbol
; i
++){
838 lemp
->symbols
[i
]->lambda
= LEMON_FALSE
;
840 for(i
=lemp
->nterminal
; i
<lemp
->nsymbol
; i
++){
841 lemp
->symbols
[i
]->firstset
= SetNew();
844 /* First compute all lambdas */
847 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
848 if( rp
->lhs
->lambda
) continue;
849 for(i
=0; i
<rp
->nrhs
; i
++){
850 struct symbol
*sp
= rp
->rhs
[i
];
851 assert( sp
->type
==NONTERMINAL
|| sp
->lambda
==LEMON_FALSE
);
852 if( sp
->lambda
==LEMON_FALSE
) break;
855 rp
->lhs
->lambda
= LEMON_TRUE
;
861 /* Now compute all first sets */
863 struct symbol
*s1
, *s2
;
865 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
867 for(i
=0; i
<rp
->nrhs
; i
++){
869 if( s2
->type
==TERMINAL
){
870 progress
+= SetAdd(s1
->firstset
,s2
->index
);
872 }else if( s2
->type
==MULTITERMINAL
){
873 for(j
=0; j
<s2
->nsubsym
; j
++){
874 progress
+= SetAdd(s1
->firstset
,s2
->subsym
[j
]->index
);
878 if( s1
->lambda
==LEMON_FALSE
) break;
880 progress
+= SetUnion(s1
->firstset
,s2
->firstset
);
881 if( s2
->lambda
==LEMON_FALSE
) break;
889 /* Compute all LR(0) states for the grammar. Links
890 ** are added to between some states so that the LR(1) follow sets
891 ** can be computed later.
893 PRIVATE
struct state
*getstate(struct lemon
*); /* forward reference */
894 void FindStates(struct lemon
*lemp
)
901 /* Find the start symbol */
903 sp
= Symbol_find(lemp
->start
);
905 ErrorMsg(lemp
->filename
,0,
906 "The specified start symbol \"%s\" is not \
907 in a nonterminal of the grammar. \"%s\" will be used as the start \
908 symbol instead.",lemp
->start
,lemp
->startRule
->lhs
->name
);
910 sp
= lemp
->startRule
->lhs
;
913 sp
= lemp
->startRule
->lhs
;
916 /* Make sure the start symbol doesn't occur on the right-hand side of
917 ** any rule. Report an error if it does. (YACC would generate a new
918 ** start symbol in this case.) */
919 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
921 for(i
=0; i
<rp
->nrhs
; i
++){
922 if( rp
->rhs
[i
]==sp
){ /* FIX ME: Deal with multiterminals */
923 ErrorMsg(lemp
->filename
,0,
924 "The start symbol \"%s\" occurs on the \
925 right-hand side of a rule. This will result in a parser which \
926 does not work properly.",sp
->name
);
932 /* The basis configuration set for the first state
933 ** is all rules which have the start symbol as their
935 for(rp
=sp
->rule
; rp
; rp
=rp
->nextlhs
){
936 struct config
*newcfp
;
938 newcfp
= Configlist_addbasis(rp
,0);
939 SetAdd(newcfp
->fws
,0);
942 /* Compute the first state. All other states will be
943 ** computed automatically during the computation of the first one.
944 ** The returned pointer to the first state is not used. */
945 (void)getstate(lemp
);
949 /* Return a pointer to a state which is described by the configuration
950 ** list which has been built from calls to Configlist_add.
952 PRIVATE
void buildshifts(struct lemon
*, struct state
*); /* Forwd ref */
953 PRIVATE
struct state
*getstate(struct lemon
*lemp
)
955 struct config
*cfp
, *bp
;
958 /* Extract the sorted basis of the new state. The basis was constructed
959 ** by prior calls to "Configlist_addbasis()". */
960 Configlist_sortbasis();
961 bp
= Configlist_basis();
963 /* Get a state with the same basis */
964 stp
= State_find(bp
);
966 /* A state with the same basis already exists! Copy all the follow-set
967 ** propagation links from the state under construction into the
968 ** preexisting state, then return a pointer to the preexisting state */
969 struct config
*x
, *y
;
970 for(x
=bp
, y
=stp
->bp
; x
&& y
; x
=x
->bp
, y
=y
->bp
){
971 Plink_copy(&y
->bplp
,x
->bplp
);
972 Plink_delete(x
->fplp
);
973 x
->fplp
= x
->bplp
= 0;
975 cfp
= Configlist_return();
978 /* This really is a new state. Construct all the details */
979 Configlist_closure(lemp
); /* Compute the configuration closure */
980 Configlist_sort(); /* Sort the configuration closure */
981 cfp
= Configlist_return(); /* Get a pointer to the config list */
982 stp
= State_new(); /* A new state structure */
984 stp
->bp
= bp
; /* Remember the configuration basis */
985 stp
->cfp
= cfp
; /* Remember the configuration closure */
986 stp
->statenum
= lemp
->nstate
++; /* Every state gets a sequence number */
987 stp
->ap
= 0; /* No actions, yet. */
988 State_insert(stp
,stp
->bp
); /* Add to the state table */
989 buildshifts(lemp
,stp
); /* Recursively compute successor states */
995 ** Return true if two symbols are the same.
997 int same_symbol(struct symbol
*a
, struct symbol
*b
)
1000 if( a
==b
) return 1;
1001 if( a
->type
!=MULTITERMINAL
) return 0;
1002 if( b
->type
!=MULTITERMINAL
) return 0;
1003 if( a
->nsubsym
!=b
->nsubsym
) return 0;
1004 for(i
=0; i
<a
->nsubsym
; i
++){
1005 if( a
->subsym
[i
]!=b
->subsym
[i
] ) return 0;
1010 /* Construct all successor states to the given state. A "successor"
1011 ** state is any state which can be reached by a shift action.
1013 PRIVATE
void buildshifts(struct lemon
*lemp
, struct state
*stp
)
1015 struct config
*cfp
; /* For looping thru the config closure of "stp" */
1016 struct config
*bcfp
; /* For the inner loop on config closure of "stp" */
1017 struct config
*newcfg
; /* */
1018 struct symbol
*sp
; /* Symbol following the dot in configuration "cfp" */
1019 struct symbol
*bsp
; /* Symbol following the dot in configuration "bcfp" */
1020 struct state
*newstp
; /* A pointer to a successor state */
1022 /* Each configuration becomes complete after it contibutes to a successor
1023 ** state. Initially, all configurations are incomplete */
1024 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
) cfp
->status
= INCOMPLETE
;
1026 /* Loop through all configurations of the state "stp" */
1027 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1028 if( cfp
->status
==COMPLETE
) continue; /* Already used by inner loop */
1029 if( cfp
->dot
>=cfp
->rp
->nrhs
) continue; /* Can't shift this config */
1030 Configlist_reset(); /* Reset the new config set */
1031 sp
= cfp
->rp
->rhs
[cfp
->dot
]; /* Symbol after the dot */
1033 /* For every configuration in the state "stp" which has the symbol "sp"
1034 ** following its dot, add the same configuration to the basis set under
1035 ** construction but with the dot shifted one symbol to the right. */
1036 for(bcfp
=cfp
; bcfp
; bcfp
=bcfp
->next
){
1037 if( bcfp
->status
==COMPLETE
) continue; /* Already used */
1038 if( bcfp
->dot
>=bcfp
->rp
->nrhs
) continue; /* Can't shift this one */
1039 bsp
= bcfp
->rp
->rhs
[bcfp
->dot
]; /* Get symbol after dot */
1040 if( !same_symbol(bsp
,sp
) ) continue; /* Must be same as for "cfp" */
1041 bcfp
->status
= COMPLETE
; /* Mark this config as used */
1042 newcfg
= Configlist_addbasis(bcfp
->rp
,bcfp
->dot
+1);
1043 Plink_add(&newcfg
->bplp
,bcfp
);
1046 /* Get a pointer to the state described by the basis configuration set
1047 ** constructed in the preceding loop */
1048 newstp
= getstate(lemp
);
1050 /* The state "newstp" is reached from the state "stp" by a shift action
1051 ** on the symbol "sp" */
1052 if( sp
->type
==MULTITERMINAL
){
1054 for(i
=0; i
<sp
->nsubsym
; i
++){
1055 Action_add(&stp
->ap
,SHIFT
,sp
->subsym
[i
],(char*)newstp
);
1058 Action_add(&stp
->ap
,SHIFT
,sp
,(char *)newstp
);
1064 ** Construct the propagation links
1066 void FindLinks(struct lemon
*lemp
)
1069 struct config
*cfp
, *other
;
1073 /* Housekeeping detail:
1074 ** Add to every propagate link a pointer back to the state to
1075 ** which the link is attached. */
1076 for(i
=0; i
<lemp
->nstate
; i
++){
1077 stp
= lemp
->sorted
[i
];
1078 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1083 /* Convert all backlinks into forward links. Only the forward
1084 ** links are used in the follow-set computation. */
1085 for(i
=0; i
<lemp
->nstate
; i
++){
1086 stp
= lemp
->sorted
[i
];
1087 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1088 for(plp
=cfp
->bplp
; plp
; plp
=plp
->next
){
1090 Plink_add(&other
->fplp
,cfp
);
1096 /* Compute all followsets.
1098 ** A followset is the set of all symbols which can come immediately
1099 ** after a configuration.
1101 void FindFollowSets(struct lemon
*lemp
)
1109 for(i
=0; i
<lemp
->nstate
; i
++){
1110 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1111 cfp
->status
= INCOMPLETE
;
1117 for(i
=0; i
<lemp
->nstate
; i
++){
1118 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1119 if( cfp
->status
==COMPLETE
) continue;
1120 for(plp
=cfp
->fplp
; plp
; plp
=plp
->next
){
1121 change
= SetUnion(plp
->cfp
->fws
,cfp
->fws
);
1123 plp
->cfp
->status
= INCOMPLETE
;
1127 cfp
->status
= COMPLETE
;
1133 static int resolve_conflict(struct action
*,struct action
*);
1135 /* Compute the reduce actions, and resolve conflicts.
1137 void FindActions(struct lemon
*lemp
)
1145 /* Add all of the reduce actions
1146 ** A reduce action is added for each element of the followset of
1147 ** a configuration which has its dot at the extreme right.
1149 for(i
=0; i
<lemp
->nstate
; i
++){ /* Loop over all states */
1150 stp
= lemp
->sorted
[i
];
1151 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){ /* Loop over all configurations */
1152 if( cfp
->rp
->nrhs
==cfp
->dot
){ /* Is dot at extreme right? */
1153 for(j
=0; j
<lemp
->nterminal
; j
++){
1154 if( SetFind(cfp
->fws
,j
) ){
1155 /* Add a reduce action to the state "stp" which will reduce by the
1156 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
1157 Action_add(&stp
->ap
,REDUCE
,lemp
->symbols
[j
],(char *)cfp
->rp
);
1164 /* Add the accepting token */
1166 sp
= Symbol_find(lemp
->start
);
1167 if( sp
==0 ) sp
= lemp
->startRule
->lhs
;
1169 sp
= lemp
->startRule
->lhs
;
1171 /* Add to the first state (which is always the starting state of the
1172 ** finite state machine) an action to ACCEPT if the lookahead is the
1173 ** start nonterminal. */
1174 Action_add(&lemp
->sorted
[0]->ap
,ACCEPT
,sp
,0);
1176 /* Resolve conflicts */
1177 for(i
=0; i
<lemp
->nstate
; i
++){
1178 struct action
*ap
, *nap
;
1179 stp
= lemp
->sorted
[i
];
1180 /* assert( stp->ap ); */
1181 stp
->ap
= Action_sort(stp
->ap
);
1182 for(ap
=stp
->ap
; ap
&& ap
->next
; ap
=ap
->next
){
1183 for(nap
=ap
->next
; nap
&& nap
->sp
==ap
->sp
; nap
=nap
->next
){
1184 /* The two actions "ap" and "nap" have the same lookahead.
1185 ** Figure out which one should be used */
1186 lemp
->nconflict
+= resolve_conflict(ap
,nap
);
1191 /* Report an error for each rule that can never be reduced. */
1192 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->canReduce
= LEMON_FALSE
;
1193 for(i
=0; i
<lemp
->nstate
; i
++){
1195 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
1196 if( ap
->type
==REDUCE
) ap
->x
.rp
->canReduce
= LEMON_TRUE
;
1199 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
1200 if( rp
->canReduce
) continue;
1201 ErrorMsg(lemp
->filename
,rp
->ruleline
,"This rule can not be reduced.\n");
1206 /* Resolve a conflict between the two given actions. If the
1207 ** conflict can't be resolved, return non-zero.
1210 ** To resolve a conflict, first look to see if either action
1211 ** is on an error rule. In that case, take the action which
1212 ** is not associated with the error rule. If neither or both
1213 ** actions are associated with an error rule, then try to
1214 ** use precedence to resolve the conflict.
1216 ** If either action is a SHIFT, then it must be apx. This
1217 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1219 static int resolve_conflict(
1223 struct symbol
*spx
, *spy
;
1225 assert( apx
->sp
==apy
->sp
); /* Otherwise there would be no conflict */
1226 if( apx
->type
==SHIFT
&& apy
->type
==SHIFT
){
1227 apy
->type
= SSCONFLICT
;
1230 if( apx
->type
==SHIFT
&& apy
->type
==REDUCE
){
1232 spy
= apy
->x
.rp
->precsym
;
1233 if( spy
==0 || spx
->prec
<0 || spy
->prec
<0 ){
1234 /* Not enough precedence information. */
1235 apy
->type
= SRCONFLICT
;
1237 }else if( spx
->prec
>spy
->prec
){ /* higher precedence wins */
1238 apy
->type
= RD_RESOLVED
;
1239 }else if( spx
->prec
<spy
->prec
){
1240 apx
->type
= SH_RESOLVED
;
1241 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==RIGHT
){ /* Use operator */
1242 apy
->type
= RD_RESOLVED
; /* associativity */
1243 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==LEFT
){ /* to break tie */
1244 apx
->type
= SH_RESOLVED
;
1246 assert( spx
->prec
==spy
->prec
&& spx
->assoc
==NONE
);
1249 }else if( apx
->type
==REDUCE
&& apy
->type
==REDUCE
){
1250 spx
= apx
->x
.rp
->precsym
;
1251 spy
= apy
->x
.rp
->precsym
;
1252 if( spx
==0 || spy
==0 || spx
->prec
<0 ||
1253 spy
->prec
<0 || spx
->prec
==spy
->prec
){
1254 apy
->type
= RRCONFLICT
;
1256 }else if( spx
->prec
>spy
->prec
){
1257 apy
->type
= RD_RESOLVED
;
1258 }else if( spx
->prec
<spy
->prec
){
1259 apx
->type
= RD_RESOLVED
;
1263 apx
->type
==SH_RESOLVED
||
1264 apx
->type
==RD_RESOLVED
||
1265 apx
->type
==SSCONFLICT
||
1266 apx
->type
==SRCONFLICT
||
1267 apx
->type
==RRCONFLICT
||
1268 apy
->type
==SH_RESOLVED
||
1269 apy
->type
==RD_RESOLVED
||
1270 apy
->type
==SSCONFLICT
||
1271 apy
->type
==SRCONFLICT
||
1272 apy
->type
==RRCONFLICT
1274 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1275 ** REDUCEs on the list. If we reach this point it must be because
1276 ** the parser conflict had already been resolved. */
1280 /********************* From the file "configlist.c" *************************/
1282 ** Routines to processing a configuration list and building a state
1283 ** in the LEMON parser generator.
1286 static struct config
*freelist
= 0; /* List of free configurations */
1287 static struct config
*current
= 0; /* Top of list of configurations */
1288 static struct config
**currentend
= 0; /* Last on list of configs */
1289 static struct config
*basis
= 0; /* Top of list of basis configs */
1290 static struct config
**basisend
= 0; /* End of list of basis configs */
1292 /* Return a pointer to a new configuration */
1293 PRIVATE
struct config
*newconfig(void){
1294 struct config
*newcfg
;
1298 freelist
= (struct config
*)calloc( amt
, sizeof(struct config
) );
1300 fprintf(stderr
,"Unable to allocate memory for a new configuration.");
1303 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
1304 freelist
[amt
-1].next
= 0;
1307 freelist
= freelist
->next
;
1311 /* The configuration "old" is no longer used */
1312 PRIVATE
void deleteconfig(struct config
*old
)
1314 old
->next
= freelist
;
1318 /* Initialized the configuration list builder */
1319 void Configlist_init(void){
1321 currentend
= ¤t
;
1328 /* Initialized the configuration list builder */
1329 void Configlist_reset(void){
1331 currentend
= ¤t
;
1334 Configtable_clear(0);
1338 /* Add another configuration to the configuration list */
1339 struct config
*Configlist_add(
1340 struct rule
*rp
, /* The rule */
1341 int dot
/* Index into the RHS of the rule where the dot goes */
1343 struct config
*cfp
, model
;
1345 assert( currentend
!=0 );
1348 cfp
= Configtable_find(&model
);
1353 cfp
->fws
= SetNew();
1355 cfp
->fplp
= cfp
->bplp
= 0;
1359 currentend
= &cfp
->next
;
1360 Configtable_insert(cfp
);
1365 /* Add a basis configuration to the configuration list */
1366 struct config
*Configlist_addbasis(struct rule
*rp
, int dot
)
1368 struct config
*cfp
, model
;
1370 assert( basisend
!=0 );
1371 assert( currentend
!=0 );
1374 cfp
= Configtable_find(&model
);
1379 cfp
->fws
= SetNew();
1381 cfp
->fplp
= cfp
->bplp
= 0;
1385 currentend
= &cfp
->next
;
1387 basisend
= &cfp
->bp
;
1388 Configtable_insert(cfp
);
1393 /* Compute the closure of the configuration list */
1394 void Configlist_closure(struct lemon
*lemp
)
1396 struct config
*cfp
, *newcfp
;
1397 struct rule
*rp
, *newrp
;
1398 struct symbol
*sp
, *xsp
;
1401 assert( currentend
!=0 );
1402 for(cfp
=current
; cfp
; cfp
=cfp
->next
){
1405 if( dot
>=rp
->nrhs
) continue;
1407 if( sp
->type
==NONTERMINAL
){
1408 if( sp
->rule
==0 && sp
!=lemp
->errsym
){
1409 ErrorMsg(lemp
->filename
,rp
->line
,"Nonterminal \"%s\" has no rules.",
1413 for(newrp
=sp
->rule
; newrp
; newrp
=newrp
->nextlhs
){
1414 newcfp
= Configlist_add(newrp
,0);
1415 for(i
=dot
+1; i
<rp
->nrhs
; i
++){
1417 if( xsp
->type
==TERMINAL
){
1418 SetAdd(newcfp
->fws
,xsp
->index
);
1420 }else if( xsp
->type
==MULTITERMINAL
){
1422 for(k
=0; k
<xsp
->nsubsym
; k
++){
1423 SetAdd(newcfp
->fws
, xsp
->subsym
[k
]->index
);
1427 SetUnion(newcfp
->fws
,xsp
->firstset
);
1428 if( xsp
->lambda
==LEMON_FALSE
) break;
1431 if( i
==rp
->nrhs
) Plink_add(&cfp
->fplp
,newcfp
);
1438 /* Sort the configuration list */
1439 void Configlist_sort(void){
1440 current
= (struct config
*)msort((char*)current
,(char**)&(current
->next
),
1446 /* Sort the basis configuration list */
1447 void Configlist_sortbasis(void){
1448 basis
= (struct config
*)msort((char*)current
,(char**)&(current
->bp
),
1454 /* Return a pointer to the head of the configuration list and
1455 ** reset the list */
1456 struct config
*Configlist_return(void){
1464 /* Return a pointer to the head of the configuration list and
1465 ** reset the list */
1466 struct config
*Configlist_basis(void){
1474 /* Free all elements of the given configuration list */
1475 void Configlist_eat(struct config
*cfp
)
1477 struct config
*nextcfp
;
1478 for(; cfp
; cfp
=nextcfp
){
1479 nextcfp
= cfp
->next
;
1480 assert( cfp
->fplp
==0 );
1481 assert( cfp
->bplp
==0 );
1482 if( cfp
->fws
) SetFree(cfp
->fws
);
1487 /***************** From the file "error.c" *********************************/
1489 ** Code for printing error message.
1492 void ErrorMsg(const char *filename
, int lineno
, const char *format
, ...){
1494 fprintf(stderr
, "%s:%d: ", filename
, lineno
);
1495 va_start(ap
, format
);
1496 vfprintf(stderr
,format
,ap
);
1498 fprintf(stderr
, "\n");
1500 /**************** From the file "main.c" ************************************/
1502 ** Main program file for the LEMON parser generator.
1505 /* Report an out-of-memory condition and abort. This function
1506 ** is used mostly by the "MemoryCheck" macro in struct.h
1508 void memory_error(void){
1509 fprintf(stderr
,"Out of memory. Aborting...\n");
1513 static int nDefine
= 0; /* Number of -D options on the command line */
1514 static char **azDefine
= 0; /* Name of the -D macros */
1516 /* This routine is called with the argument to each -D command-line option.
1517 ** Add the macro defined to the azDefine array.
1519 static void handle_D_option(char *z
){
1522 azDefine
= (char **) realloc(azDefine
, sizeof(azDefine
[0])*nDefine
);
1524 fprintf(stderr
,"out of memory\n");
1527 paz
= &azDefine
[nDefine
-1];
1528 *paz
= (char *) malloc( lemonStrlen(z
)+1 );
1530 fprintf(stderr
,"out of memory\n");
1533 lemon_strcpy(*paz
, z
);
1534 for(z
=*paz
; *z
&& *z
!='='; z
++){}
1538 static char *user_templatename
= NULL
;
1539 static void handle_T_option(char *z
){
1540 user_templatename
= (char *) malloc( lemonStrlen(z
)+1 );
1541 if( user_templatename
==0 ){
1544 lemon_strcpy(user_templatename
, z
);
1547 /* Merge together to lists of rules ordered by rule.iRule */
1548 static struct rule
*Rule_merge(struct rule
*pA
, struct rule
*pB
){
1549 struct rule
*pFirst
= 0;
1550 struct rule
**ppPrev
= &pFirst
;
1552 if( pA
->iRule
<pB
->iRule
){
1571 ** Sort a list of rules in order of increasing iRule value
1573 static struct rule
*Rule_sort(struct rule
*rp
){
1577 memset(x
, 0, sizeof(x
));
1581 for(i
=0; i
<sizeof(x
)/sizeof(x
[0]) && x
[i
]; i
++){
1582 rp
= Rule_merge(x
[i
], rp
);
1589 for(i
=0; i
<sizeof(x
)/sizeof(x
[0]); i
++){
1590 rp
= Rule_merge(x
[i
], rp
);
1595 /* forward reference */
1596 static const char *minimum_size_type(int lwr
, int upr
, int *pnByte
);
1598 /* Print a single line of the "Parser Stats" output
1600 static void stats_line(const char *zLabel
, int iValue
){
1601 int nLabel
= lemonStrlen(zLabel
);
1602 printf(" %s%.*s %5d\n", zLabel
,
1603 35-nLabel
, "................................",
1607 /* The main program. Parse the command line and do it... */
1608 int main(int argc
, char **argv
)
1610 static int version
= 0;
1611 static int rpflag
= 0;
1612 static int basisflag
= 0;
1613 static int compress
= 0;
1614 static int quiet
= 0;
1615 static int statistics
= 0;
1616 static int mhflag
= 0;
1617 static int nolinenosflag
= 0;
1618 static int noResort
= 0;
1619 static struct s_options options
[] = {
1620 {OPT_FLAG
, "b", (char*)&basisflag
, "Print only the basis in report."},
1621 {OPT_FLAG
, "c", (char*)&compress
, "Don't compress the action table."},
1622 {OPT_FSTR
, "D", (char*)handle_D_option
, "Define an %ifdef macro."},
1623 {OPT_FSTR
, "f", 0, "Ignored. (Placeholder for -f compiler options.)"},
1624 {OPT_FLAG
, "g", (char*)&rpflag
, "Print grammar without actions."},
1625 {OPT_FSTR
, "I", 0, "Ignored. (Placeholder for '-I' compiler options.)"},
1626 {OPT_FLAG
, "m", (char*)&mhflag
, "Output a makeheaders compatible file."},
1627 {OPT_FLAG
, "l", (char*)&nolinenosflag
, "Do not print #line statements."},
1628 {OPT_FSTR
, "O", 0, "Ignored. (Placeholder for '-O' compiler options.)"},
1629 {OPT_FLAG
, "p", (char*)&showPrecedenceConflict
,
1630 "Show conflicts resolved by precedence rules"},
1631 {OPT_FLAG
, "q", (char*)&quiet
, "(Quiet) Don't print the report file."},
1632 {OPT_FLAG
, "r", (char*)&noResort
, "Do not sort or renumber states"},
1633 {OPT_FLAG
, "s", (char*)&statistics
,
1634 "Print parser stats to standard output."},
1635 {OPT_FLAG
, "x", (char*)&version
, "Print the version number."},
1636 {OPT_FSTR
, "T", (char*)handle_T_option
, "Specify a template file."},
1637 {OPT_FSTR
, "W", 0, "Ignored. (Placeholder for '-W' compiler options.)"},
1645 OptInit(argv
,options
,stderr
);
1647 printf("Lemon version 1.0\n");
1650 if( OptNArgs()!=1 ){
1651 fprintf(stderr
,"Exactly one filename argument is required.\n");
1654 memset(&lem
, 0, sizeof(lem
));
1657 /* Initialize the machine */
1661 lem
.argv0
= argv
[0];
1662 lem
.filename
= OptArg(0);
1663 lem
.basisflag
= basisflag
;
1664 lem
.nolinenosflag
= nolinenosflag
;
1666 lem
.errsym
= Symbol_new("error");
1667 lem
.errsym
->useCnt
= 0;
1669 /* Parse the input file */
1671 if( lem
.errorcnt
) exit(lem
.errorcnt
);
1673 fprintf(stderr
,"Empty grammar.\n");
1677 /* Count and index the symbols of the grammar */
1678 Symbol_new("{default}");
1679 lem
.nsymbol
= Symbol_count();
1680 lem
.symbols
= Symbol_arrayof();
1681 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1682 qsort(lem
.symbols
,lem
.nsymbol
,sizeof(struct symbol
*), Symbolcmpp
);
1683 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1684 while( lem
.symbols
[i
-1]->type
==MULTITERMINAL
){ i
--; }
1685 assert( strcmp(lem
.symbols
[i
-1]->name
,"{default}")==0 );
1686 lem
.nsymbol
= i
- 1;
1687 for(i
=1; ISUPPER(lem
.symbols
[i
]->name
[0]); i
++);
1690 /* Assign sequential rule numbers. Start with 0. Put rules that have no
1691 ** reduce action C-code associated with them last, so that the switch()
1692 ** statement that selects reduction actions will have a smaller jump table.
1694 for(i
=0, rp
=lem
.rule
; rp
; rp
=rp
->next
){
1695 rp
->iRule
= rp
->code
? i
++ : -1;
1697 for(rp
=lem
.rule
; rp
; rp
=rp
->next
){
1698 if( rp
->iRule
<0 ) rp
->iRule
= i
++;
1700 lem
.startRule
= lem
.rule
;
1701 lem
.rule
= Rule_sort(lem
.rule
);
1703 /* Generate a reprint of the grammar, if requested on the command line */
1707 /* Initialize the size for all follow and first sets */
1708 SetSize(lem
.nterminal
+1);
1710 /* Find the precedence for every production rule (that has one) */
1711 FindRulePrecedences(&lem
);
1713 /* Compute the lambda-nonterminals and the first-sets for every
1715 FindFirstSets(&lem
);
1717 /* Compute all LR(0) states. Also record follow-set propagation
1718 ** links so that the follow-set can be computed later */
1721 lem
.sorted
= State_arrayof();
1723 /* Tie up loose ends on the propagation links */
1726 /* Compute the follow set of every reducible configuration */
1727 FindFollowSets(&lem
);
1729 /* Compute the action tables */
1732 /* Compress the action tables */
1733 if( compress
==0 ) CompressTables(&lem
);
1735 /* Reorder and renumber the states so that states with fewer choices
1736 ** occur at the end. This is an optimization that helps make the
1737 ** generated parser tables smaller. */
1738 if( noResort
==0 ) ResortStates(&lem
);
1740 /* Generate a report of the parser generated. (the "y.output" file) */
1741 if( !quiet
) ReportOutput(&lem
);
1743 /* Generate the source code for the parser */
1744 ReportTable(&lem
, mhflag
);
1746 /* Produce a header file for use by the scanner. (This step is
1747 ** omitted if the "-m" option is used because makeheaders will
1748 ** generate the file for us.) */
1749 if( !mhflag
) ReportHeader(&lem
);
1752 printf("Parser statistics:\n");
1753 stats_line("terminal symbols", lem
.nterminal
);
1754 stats_line("non-terminal symbols", lem
.nsymbol
- lem
.nterminal
);
1755 stats_line("total symbols", lem
.nsymbol
);
1756 stats_line("rules", lem
.nrule
);
1757 stats_line("states", lem
.nxstate
);
1758 stats_line("conflicts", lem
.nconflict
);
1759 stats_line("action table entries", lem
.nactiontab
);
1760 stats_line("lookahead table entries", lem
.nlookaheadtab
);
1761 stats_line("total table size (bytes)", lem
.tablesize
);
1763 if( lem
.nconflict
> 0 ){
1764 fprintf(stderr
,"%d parsing conflicts.\n",lem
.nconflict
);
1767 /* return 0 on success, 1 on failure. */
1768 exitcode
= ((lem
.errorcnt
> 0) || (lem
.nconflict
> 0)) ? 1 : 0;
1772 /******************** From the file "msort.c" *******************************/
1774 ** A generic merge-sort program.
1777 ** Let "ptr" be a pointer to some structure which is at the head of
1778 ** a null-terminated list. Then to sort the list call:
1780 ** ptr = msort(ptr,&(ptr->next),cmpfnc);
1782 ** In the above, "cmpfnc" is a pointer to a function which compares
1783 ** two instances of the structure and returns an integer, as in
1784 ** strcmp. The second argument is a pointer to the pointer to the
1785 ** second element of the linked list. This address is used to compute
1786 ** the offset to the "next" field within the structure. The offset to
1787 ** the "next" field must be constant for all structures in the list.
1789 ** The function returns a new pointer which is the head of the list
1797 ** Return a pointer to the next structure in the linked list.
1799 #define NEXT(A) (*(char**)(((char*)A)+offset))
1803 ** a: A sorted, null-terminated linked list. (May be null).
1804 ** b: A sorted, null-terminated linked list. (May be null).
1805 ** cmp: A pointer to the comparison function.
1806 ** offset: Offset in the structure to the "next" field.
1809 ** A pointer to the head of a sorted list containing the elements
1813 ** The "next" pointers for elements in the lists a and b are
1819 int (*cmp
)(const char*,const char*),
1829 if( (*cmp
)(a
,b
)<=0 ){
1838 if( (*cmp
)(a
,b
)<=0 ){
1848 if( a
) NEXT(ptr
) = a
;
1856 ** list: Pointer to a singly-linked list of structures.
1857 ** next: Pointer to pointer to the second element of the list.
1858 ** cmp: A comparison function.
1861 ** A pointer to the head of a sorted list containing the elements
1862 ** orginally in list.
1865 ** The "next" pointers for elements in list are changed.
1871 int (*cmp
)(const char*,const char*)
1873 unsigned long offset
;
1875 char *set
[LISTSIZE
];
1877 offset
= (unsigned long)((char*)next
- (char*)list
);
1878 for(i
=0; i
<LISTSIZE
; i
++) set
[i
] = 0;
1883 for(i
=0; i
<LISTSIZE
-1 && set
[i
]!=0; i
++){
1884 ep
= merge(ep
,set
[i
],cmp
,offset
);
1890 for(i
=0; i
<LISTSIZE
; i
++) if( set
[i
] ) ep
= merge(set
[i
],ep
,cmp
,offset
);
1893 /************************ From the file "option.c" **************************/
1895 static struct s_options
*op
;
1896 static FILE *errstream
;
1898 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1901 ** Print the command line with a carrot pointing to the k-th character
1902 ** of the n-th field.
1904 static void errline(int n
, int k
, FILE *err
)
1907 if( argv
[0] ) fprintf(err
,"%s",argv
[0]);
1908 spcnt
= lemonStrlen(argv
[0]) + 1;
1909 for(i
=1; i
<n
&& argv
[i
]; i
++){
1910 fprintf(err
," %s",argv
[i
]);
1911 spcnt
+= lemonStrlen(argv
[i
])+1;
1914 for(; argv
[i
]; i
++) fprintf(err
," %s",argv
[i
]);
1916 fprintf(err
,"\n%*s^-- here\n",spcnt
,"");
1918 fprintf(err
,"\n%*shere --^\n",spcnt
-7,"");
1923 ** Return the index of the N-th non-switch argument. Return -1
1924 ** if N is out of range.
1926 static int argindex(int n
)
1930 if( argv
!=0 && *argv
!=0 ){
1931 for(i
=1; argv
[i
]; i
++){
1932 if( dashdash
|| !ISOPT(argv
[i
]) ){
1933 if( n
==0 ) return i
;
1936 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
1942 static char emsg
[] = "Command line syntax error: ";
1945 ** Process a flag command line argument.
1947 static int handleflags(int i
, FILE *err
)
1952 for(j
=0; op
[j
].label
; j
++){
1953 if( strncmp(&argv
[i
][1],op
[j
].label
,lemonStrlen(op
[j
].label
))==0 ) break;
1955 v
= argv
[i
][0]=='-' ? 1 : 0;
1956 if( op
[j
].label
==0 ){
1958 fprintf(err
,"%sundefined option.\n",emsg
);
1962 }else if( op
[j
].arg
==0 ){
1963 /* Ignore this option */
1964 }else if( op
[j
].type
==OPT_FLAG
){
1965 *((int*)op
[j
].arg
) = v
;
1966 }else if( op
[j
].type
==OPT_FFLAG
){
1967 (*(void(*)(int))(op
[j
].arg
))(v
);
1968 }else if( op
[j
].type
==OPT_FSTR
){
1969 (*(void(*)(char *))(op
[j
].arg
))(&argv
[i
][2]);
1972 fprintf(err
,"%smissing argument on switch.\n",emsg
);
1981 ** Process a command line switch which has an argument.
1983 static int handleswitch(int i
, FILE *err
)
1991 cp
= strchr(argv
[i
],'=');
1994 for(j
=0; op
[j
].label
; j
++){
1995 if( strcmp(argv
[i
],op
[j
].label
)==0 ) break;
1998 if( op
[j
].label
==0 ){
2000 fprintf(err
,"%sundefined option.\n",emsg
);
2006 switch( op
[j
].type
){
2010 fprintf(err
,"%soption requires an argument.\n",emsg
);
2017 dv
= strtod(cp
,&end
);
2021 "%sillegal character in floating-point argument.\n",emsg
);
2022 errline(i
,(int)((char*)end
-(char*)argv
[i
]),err
);
2029 lv
= strtol(cp
,&end
,0);
2032 fprintf(err
,"%sillegal character in integer argument.\n",emsg
);
2033 errline(i
,(int)((char*)end
-(char*)argv
[i
]),err
);
2043 switch( op
[j
].type
){
2048 *(double*)(op
[j
].arg
) = dv
;
2051 (*(void(*)(double))(op
[j
].arg
))(dv
);
2054 *(int*)(op
[j
].arg
) = lv
;
2057 (*(void(*)(int))(op
[j
].arg
))((int)lv
);
2060 *(char**)(op
[j
].arg
) = sv
;
2063 (*(void(*)(char *))(op
[j
].arg
))(sv
);
2070 int OptInit(char **a
, struct s_options
*o
, FILE *err
)
2076 if( argv
&& *argv
&& op
){
2078 for(i
=1; argv
[i
]; i
++){
2079 if( argv
[i
][0]=='+' || argv
[i
][0]=='-' ){
2080 errcnt
+= handleflags(i
,err
);
2081 }else if( strchr(argv
[i
],'=') ){
2082 errcnt
+= handleswitch(i
,err
);
2087 fprintf(err
,"Valid command line options for \"%s\" are:\n",*a
);
2098 if( argv
!=0 && argv
[0]!=0 ){
2099 for(i
=1; argv
[i
]; i
++){
2100 if( dashdash
|| !ISOPT(argv
[i
]) ) cnt
++;
2101 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
2111 return i
>=0 ? argv
[i
] : 0;
2118 if( i
>=0 ) errline(i
,0,errstream
);
2121 void OptPrint(void){
2125 for(i
=0; op
[i
].label
; i
++){
2126 len
= lemonStrlen(op
[i
].label
) + 1;
2127 switch( op
[i
].type
){
2133 len
+= 9; /* length of "<integer>" */
2137 len
+= 6; /* length of "<real>" */
2141 len
+= 8; /* length of "<string>" */
2144 if( len
>max
) max
= len
;
2146 for(i
=0; op
[i
].label
; i
++){
2147 switch( op
[i
].type
){
2150 fprintf(errstream
," -%-*s %s\n",max
,op
[i
].label
,op
[i
].message
);
2154 fprintf(errstream
," -%s<integer>%*s %s\n",op
[i
].label
,
2155 (int)(max
-lemonStrlen(op
[i
].label
)-9),"",op
[i
].message
);
2159 fprintf(errstream
," -%s<real>%*s %s\n",op
[i
].label
,
2160 (int)(max
-lemonStrlen(op
[i
].label
)-6),"",op
[i
].message
);
2164 fprintf(errstream
," -%s<string>%*s %s\n",op
[i
].label
,
2165 (int)(max
-lemonStrlen(op
[i
].label
)-8),"",op
[i
].message
);
2170 /*********************** From the file "parse.c" ****************************/
2172 ** Input file parser for the LEMON parser generator.
2175 /* The state of the parser */
2178 WAITING_FOR_DECL_OR_RULE
,
2179 WAITING_FOR_DECL_KEYWORD
,
2180 WAITING_FOR_DECL_ARG
,
2181 WAITING_FOR_PRECEDENCE_SYMBOL
,
2191 RESYNC_AFTER_RULE_ERROR
,
2192 RESYNC_AFTER_DECL_ERROR
,
2193 WAITING_FOR_DESTRUCTOR_SYMBOL
,
2194 WAITING_FOR_DATATYPE_SYMBOL
,
2195 WAITING_FOR_FALLBACK_ID
,
2196 WAITING_FOR_WILDCARD_ID
,
2197 WAITING_FOR_CLASS_ID
,
2198 WAITING_FOR_CLASS_TOKEN
,
2199 WAITING_FOR_TOKEN_NAME
2202 char *filename
; /* Name of the input file */
2203 int tokenlineno
; /* Linenumber at which current token starts */
2204 int errorcnt
; /* Number of errors so far */
2205 char *tokenstart
; /* Text of current token */
2206 struct lemon
*gp
; /* Global state vector */
2207 enum e_state state
; /* The state of the parser */
2208 struct symbol
*fallback
; /* The fallback token */
2209 struct symbol
*tkclass
; /* Token class symbol */
2210 struct symbol
*lhs
; /* Left-hand side of current rule */
2211 const char *lhsalias
; /* Alias for the LHS */
2212 int nrhs
; /* Number of right-hand side symbols seen */
2213 struct symbol
*rhs
[MAXRHS
]; /* RHS symbols */
2214 const char *alias
[MAXRHS
]; /* Aliases for each RHS symbol (or NULL) */
2215 struct rule
*prevrule
; /* Previous rule parsed */
2216 const char *declkeyword
; /* Keyword of a declaration */
2217 char **declargslot
; /* Where the declaration argument should be put */
2218 int insertLineMacro
; /* Add #line before declaration insert */
2219 int *decllinenoslot
; /* Where to write declaration line number */
2220 enum e_assoc declassoc
; /* Assign this association to decl arguments */
2221 int preccounter
; /* Assign this precedence to decl arguments */
2222 struct rule
*firstrule
; /* Pointer to first rule in the grammar */
2223 struct rule
*lastrule
; /* Pointer to the most recently parsed rule */
2226 /* Parse a single token */
2227 static void parseonetoken(struct pstate
*psp
)
2230 x
= Strsafe(psp
->tokenstart
); /* Save the token permanently */
2232 printf("%s:%d: Token=[%s] state=%d\n",psp
->filename
,psp
->tokenlineno
,
2235 switch( psp
->state
){
2238 psp
->preccounter
= 0;
2239 psp
->firstrule
= psp
->lastrule
= 0;
2241 /* Fall thru to next case */
2242 case WAITING_FOR_DECL_OR_RULE
:
2244 psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2245 }else if( ISLOWER(x
[0]) ){
2246 psp
->lhs
= Symbol_new(x
);
2249 psp
->state
= WAITING_FOR_ARROW
;
2250 }else if( x
[0]=='{' ){
2251 if( psp
->prevrule
==0 ){
2252 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2253 "There is no prior rule upon which to attach the code \
2254 fragment which begins on this line.");
2256 }else if( psp
->prevrule
->code
!=0 ){
2257 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2258 "Code fragment beginning on this line is not the first \
2259 to follow the previous rule.");
2262 psp
->prevrule
->line
= psp
->tokenlineno
;
2263 psp
->prevrule
->code
= &x
[1];
2264 psp
->prevrule
->noCode
= 0;
2266 }else if( x
[0]=='[' ){
2267 psp
->state
= PRECEDENCE_MARK_1
;
2269 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2270 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2275 case PRECEDENCE_MARK_1
:
2276 if( !ISUPPER(x
[0]) ){
2277 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2278 "The precedence symbol must be a terminal.");
2280 }else if( psp
->prevrule
==0 ){
2281 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2282 "There is no prior rule to assign precedence \"[%s]\".",x
);
2284 }else if( psp
->prevrule
->precsym
!=0 ){
2285 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2286 "Precedence mark on this line is not the first \
2287 to follow the previous rule.");
2290 psp
->prevrule
->precsym
= Symbol_new(x
);
2292 psp
->state
= PRECEDENCE_MARK_2
;
2294 case PRECEDENCE_MARK_2
:
2296 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2297 "Missing \"]\" on precedence mark.");
2300 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2302 case WAITING_FOR_ARROW
:
2303 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2304 psp
->state
= IN_RHS
;
2305 }else if( x
[0]=='(' ){
2306 psp
->state
= LHS_ALIAS_1
;
2308 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2309 "Expected to see a \":\" following the LHS symbol \"%s\".",
2312 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2316 if( ISALPHA(x
[0]) ){
2318 psp
->state
= LHS_ALIAS_2
;
2320 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2321 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2324 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2329 psp
->state
= LHS_ALIAS_3
;
2331 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2332 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2334 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2338 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2339 psp
->state
= IN_RHS
;
2341 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2342 "Missing \"->\" following: \"%s(%s)\".",
2343 psp
->lhs
->name
,psp
->lhsalias
);
2345 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2351 rp
= (struct rule
*)calloc( sizeof(struct rule
) +
2352 sizeof(struct symbol
*)*psp
->nrhs
+ sizeof(char*)*psp
->nrhs
, 1);
2354 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2355 "Can't allocate enough memory for this rule.");
2360 rp
->ruleline
= psp
->tokenlineno
;
2361 rp
->rhs
= (struct symbol
**)&rp
[1];
2362 rp
->rhsalias
= (const char**)&(rp
->rhs
[psp
->nrhs
]);
2363 for(i
=0; i
<psp
->nrhs
; i
++){
2364 rp
->rhs
[i
] = psp
->rhs
[i
];
2365 rp
->rhsalias
[i
] = psp
->alias
[i
];
2368 rp
->lhsalias
= psp
->lhsalias
;
2369 rp
->nrhs
= psp
->nrhs
;
2373 rp
->index
= psp
->gp
->nrule
++;
2374 rp
->nextlhs
= rp
->lhs
->rule
;
2377 if( psp
->firstrule
==0 ){
2378 psp
->firstrule
= psp
->lastrule
= rp
;
2380 psp
->lastrule
->next
= rp
;
2385 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2386 }else if( ISALPHA(x
[0]) ){
2387 if( psp
->nrhs
>=MAXRHS
){
2388 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2389 "Too many symbols on RHS of rule beginning at \"%s\".",
2392 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2394 psp
->rhs
[psp
->nrhs
] = Symbol_new(x
);
2395 psp
->alias
[psp
->nrhs
] = 0;
2398 }else if( (x
[0]=='|' || x
[0]=='/') && psp
->nrhs
>0 ){
2399 struct symbol
*msp
= psp
->rhs
[psp
->nrhs
-1];
2400 if( msp
->type
!=MULTITERMINAL
){
2401 struct symbol
*origsp
= msp
;
2402 msp
= (struct symbol
*) calloc(1,sizeof(*msp
));
2403 memset(msp
, 0, sizeof(*msp
));
2404 msp
->type
= MULTITERMINAL
;
2406 msp
->subsym
= (struct symbol
**) calloc(1,sizeof(struct symbol
*));
2407 msp
->subsym
[0] = origsp
;
2408 msp
->name
= origsp
->name
;
2409 psp
->rhs
[psp
->nrhs
-1] = msp
;
2412 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2413 sizeof(struct symbol
*)*msp
->nsubsym
);
2414 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(&x
[1]);
2415 if( ISLOWER(x
[1]) || ISLOWER(msp
->subsym
[0]->name
[0]) ){
2416 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2417 "Cannot form a compound containing a non-terminal");
2420 }else if( x
[0]=='(' && psp
->nrhs
>0 ){
2421 psp
->state
= RHS_ALIAS_1
;
2423 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2424 "Illegal character on RHS of rule: \"%s\".",x
);
2426 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2430 if( ISALPHA(x
[0]) ){
2431 psp
->alias
[psp
->nrhs
-1] = x
;
2432 psp
->state
= RHS_ALIAS_2
;
2434 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2435 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2436 x
,psp
->rhs
[psp
->nrhs
-1]->name
);
2438 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2443 psp
->state
= IN_RHS
;
2445 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2446 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2448 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2451 case WAITING_FOR_DECL_KEYWORD
:
2452 if( ISALPHA(x
[0]) ){
2453 psp
->declkeyword
= x
;
2454 psp
->declargslot
= 0;
2455 psp
->decllinenoslot
= 0;
2456 psp
->insertLineMacro
= 1;
2457 psp
->state
= WAITING_FOR_DECL_ARG
;
2458 if( strcmp(x
,"name")==0 ){
2459 psp
->declargslot
= &(psp
->gp
->name
);
2460 psp
->insertLineMacro
= 0;
2461 }else if( strcmp(x
,"include")==0 ){
2462 psp
->declargslot
= &(psp
->gp
->include
);
2463 }else if( strcmp(x
,"code")==0 ){
2464 psp
->declargslot
= &(psp
->gp
->extracode
);
2465 }else if( strcmp(x
,"token_destructor")==0 ){
2466 psp
->declargslot
= &psp
->gp
->tokendest
;
2467 }else if( strcmp(x
,"default_destructor")==0 ){
2468 psp
->declargslot
= &psp
->gp
->vardest
;
2469 }else if( strcmp(x
,"token_prefix")==0 ){
2470 psp
->declargslot
= &psp
->gp
->tokenprefix
;
2471 psp
->insertLineMacro
= 0;
2472 }else if( strcmp(x
,"syntax_error")==0 ){
2473 psp
->declargslot
= &(psp
->gp
->error
);
2474 }else if( strcmp(x
,"parse_accept")==0 ){
2475 psp
->declargslot
= &(psp
->gp
->accept
);
2476 }else if( strcmp(x
,"parse_failure")==0 ){
2477 psp
->declargslot
= &(psp
->gp
->failure
);
2478 }else if( strcmp(x
,"stack_overflow")==0 ){
2479 psp
->declargslot
= &(psp
->gp
->overflow
);
2480 }else if( strcmp(x
,"extra_argument")==0 ){
2481 psp
->declargslot
= &(psp
->gp
->arg
);
2482 psp
->insertLineMacro
= 0;
2483 }else if( strcmp(x
,"token_type")==0 ){
2484 psp
->declargslot
= &(psp
->gp
->tokentype
);
2485 psp
->insertLineMacro
= 0;
2486 }else if( strcmp(x
,"default_type")==0 ){
2487 psp
->declargslot
= &(psp
->gp
->vartype
);
2488 psp
->insertLineMacro
= 0;
2489 }else if( strcmp(x
,"stack_size")==0 ){
2490 psp
->declargslot
= &(psp
->gp
->stacksize
);
2491 psp
->insertLineMacro
= 0;
2492 }else if( strcmp(x
,"start_symbol")==0 ){
2493 psp
->declargslot
= &(psp
->gp
->start
);
2494 psp
->insertLineMacro
= 0;
2495 }else if( strcmp(x
,"left")==0 ){
2497 psp
->declassoc
= LEFT
;
2498 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2499 }else if( strcmp(x
,"right")==0 ){
2501 psp
->declassoc
= RIGHT
;
2502 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2503 }else if( strcmp(x
,"nonassoc")==0 ){
2505 psp
->declassoc
= NONE
;
2506 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2507 }else if( strcmp(x
,"destructor")==0 ){
2508 psp
->state
= WAITING_FOR_DESTRUCTOR_SYMBOL
;
2509 }else if( strcmp(x
,"type")==0 ){
2510 psp
->state
= WAITING_FOR_DATATYPE_SYMBOL
;
2511 }else if( strcmp(x
,"fallback")==0 ){
2513 psp
->state
= WAITING_FOR_FALLBACK_ID
;
2514 }else if( strcmp(x
,"token")==0 ){
2515 psp
->state
= WAITING_FOR_TOKEN_NAME
;
2516 }else if( strcmp(x
,"wildcard")==0 ){
2517 psp
->state
= WAITING_FOR_WILDCARD_ID
;
2518 }else if( strcmp(x
,"token_class")==0 ){
2519 psp
->state
= WAITING_FOR_CLASS_ID
;
2521 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2522 "Unknown declaration keyword: \"%%%s\".",x
);
2524 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2527 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2528 "Illegal declaration keyword: \"%s\".",x
);
2530 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2533 case WAITING_FOR_DESTRUCTOR_SYMBOL
:
2534 if( !ISALPHA(x
[0]) ){
2535 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2536 "Symbol name missing after %%destructor keyword");
2538 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2540 struct symbol
*sp
= Symbol_new(x
);
2541 psp
->declargslot
= &sp
->destructor
;
2542 psp
->decllinenoslot
= &sp
->destLineno
;
2543 psp
->insertLineMacro
= 1;
2544 psp
->state
= WAITING_FOR_DECL_ARG
;
2547 case WAITING_FOR_DATATYPE_SYMBOL
:
2548 if( !ISALPHA(x
[0]) ){
2549 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2550 "Symbol name missing after %%type keyword");
2552 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2554 struct symbol
*sp
= Symbol_find(x
);
2555 if((sp
) && (sp
->datatype
)){
2556 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2557 "Symbol %%type \"%s\" already defined", x
);
2559 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2564 psp
->declargslot
= &sp
->datatype
;
2565 psp
->insertLineMacro
= 0;
2566 psp
->state
= WAITING_FOR_DECL_ARG
;
2570 case WAITING_FOR_PRECEDENCE_SYMBOL
:
2572 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2573 }else if( ISUPPER(x
[0]) ){
2577 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2578 "Symbol \"%s\" has already be given a precedence.",x
);
2581 sp
->prec
= psp
->preccounter
;
2582 sp
->assoc
= psp
->declassoc
;
2585 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2586 "Can't assign a precedence to \"%s\".",x
);
2590 case WAITING_FOR_DECL_ARG
:
2591 if( x
[0]=='{' || x
[0]=='\"' || ISALNUM(x
[0]) ){
2592 const char *zOld
, *zNew
;
2594 int nOld
, n
, nLine
= 0, nNew
, nBack
;
2598 if( zNew
[0]=='"' || zNew
[0]=='{' ) zNew
++;
2599 nNew
= lemonStrlen(zNew
);
2600 if( *psp
->declargslot
){
2601 zOld
= *psp
->declargslot
;
2605 nOld
= lemonStrlen(zOld
);
2606 n
= nOld
+ nNew
+ 20;
2607 addLineMacro
= !psp
->gp
->nolinenosflag
&& psp
->insertLineMacro
&&
2608 (psp
->decllinenoslot
==0 || psp
->decllinenoslot
[0]!=0);
2610 for(z
=psp
->filename
, nBack
=0; *z
; z
++){
2611 if( *z
=='\\' ) nBack
++;
2613 lemon_sprintf(zLine
, "#line %d ", psp
->tokenlineno
);
2614 nLine
= lemonStrlen(zLine
);
2615 n
+= nLine
+ lemonStrlen(psp
->filename
) + nBack
;
2617 *psp
->declargslot
= (char *) realloc(*psp
->declargslot
, n
);
2618 zBuf
= *psp
->declargslot
+ nOld
;
2620 if( nOld
&& zBuf
[-1]!='\n' ){
2623 memcpy(zBuf
, zLine
, nLine
);
2626 for(z
=psp
->filename
; *z
; z
++){
2635 if( psp
->decllinenoslot
&& psp
->decllinenoslot
[0]==0 ){
2636 psp
->decllinenoslot
[0] = psp
->tokenlineno
;
2638 memcpy(zBuf
, zNew
, nNew
);
2641 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2643 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2644 "Illegal argument to %%%s: %s",psp
->declkeyword
,x
);
2646 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2649 case WAITING_FOR_FALLBACK_ID
:
2651 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2652 }else if( !ISUPPER(x
[0]) ){
2653 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2654 "%%fallback argument \"%s\" should be a token", x
);
2657 struct symbol
*sp
= Symbol_new(x
);
2658 if( psp
->fallback
==0 ){
2660 }else if( sp
->fallback
){
2661 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2662 "More than one fallback assigned to token %s", x
);
2665 sp
->fallback
= psp
->fallback
;
2666 psp
->gp
->has_fallback
= 1;
2670 case WAITING_FOR_TOKEN_NAME
:
2671 /* Tokens do not have to be declared before use. But they can be
2672 ** in order to control their assigned integer number. The number for
2673 ** each token is assigned when it is first seen. So by including
2675 ** %token ONE TWO THREE
2677 ** early in the grammar file, that assigns small consecutive values
2678 ** to each of the tokens ONE TWO and THREE.
2681 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2682 }else if( !ISUPPER(x
[0]) ){
2683 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2684 "%%token argument \"%s\" should be a token", x
);
2687 (void)Symbol_new(x
);
2690 case WAITING_FOR_WILDCARD_ID
:
2692 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2693 }else if( !ISUPPER(x
[0]) ){
2694 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2695 "%%wildcard argument \"%s\" should be a token", x
);
2698 struct symbol
*sp
= Symbol_new(x
);
2699 if( psp
->gp
->wildcard
==0 ){
2700 psp
->gp
->wildcard
= sp
;
2702 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2703 "Extra wildcard to token: %s", x
);
2708 case WAITING_FOR_CLASS_ID
:
2709 if( !ISLOWER(x
[0]) ){
2710 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2711 "%%token_class must be followed by an identifier: ", x
);
2713 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2714 }else if( Symbol_find(x
) ){
2715 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2716 "Symbol \"%s\" already used", x
);
2718 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2720 psp
->tkclass
= Symbol_new(x
);
2721 psp
->tkclass
->type
= MULTITERMINAL
;
2722 psp
->state
= WAITING_FOR_CLASS_TOKEN
;
2725 case WAITING_FOR_CLASS_TOKEN
:
2727 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2728 }else if( ISUPPER(x
[0]) || ((x
[0]=='|' || x
[0]=='/') && ISUPPER(x
[1])) ){
2729 struct symbol
*msp
= psp
->tkclass
;
2731 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2732 sizeof(struct symbol
*)*msp
->nsubsym
);
2733 if( !ISUPPER(x
[0]) ) x
++;
2734 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(x
);
2736 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2737 "%%token_class argument \"%s\" should be a token", x
);
2739 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2742 case RESYNC_AFTER_RULE_ERROR
:
2743 /* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2745 case RESYNC_AFTER_DECL_ERROR
:
2746 if( x
[0]=='.' ) psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2747 if( x
[0]=='%' ) psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2752 /* Run the preprocessor over the input file text. The global variables
2753 ** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2754 ** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2755 ** comments them out. Text in between is also commented out as appropriate.
2757 static void preprocess_input(char *z
){
2762 int start_lineno
= 1;
2763 for(i
=0; z
[i
]; i
++){
2764 if( z
[i
]=='\n' ) lineno
++;
2765 if( z
[i
]!='%' || (i
>0 && z
[i
-1]!='\n') ) continue;
2766 if( strncmp(&z
[i
],"%endif",6)==0 && ISSPACE(z
[i
+6]) ){
2770 for(j
=start
; j
<i
; j
++) if( z
[j
]!='\n' ) z
[j
] = ' ';
2773 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2774 }else if( (strncmp(&z
[i
],"%ifdef",6)==0 && ISSPACE(z
[i
+6]))
2775 || (strncmp(&z
[i
],"%ifndef",7)==0 && ISSPACE(z
[i
+7])) ){
2779 for(j
=i
+7; ISSPACE(z
[j
]); j
++){}
2780 for(n
=0; z
[j
+n
] && !ISSPACE(z
[j
+n
]); n
++){}
2782 for(k
=0; k
<nDefine
; k
++){
2783 if( strncmp(azDefine
[k
],&z
[j
],n
)==0 && lemonStrlen(azDefine
[k
])==n
){
2788 if( z
[i
+3]=='n' ) exclude
= !exclude
;
2791 start_lineno
= lineno
;
2794 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2798 fprintf(stderr
,"unterminated %%ifdef starting on line %d\n", start_lineno
);
2803 /* In spite of its name, this function is really a scanner. It read
2804 ** in the entire input file (all at once) then tokenizes it. Each
2805 ** token is passed to the function "parseonetoken" which builds all
2806 ** the appropriate data structures in the global state vector "gp".
2808 void Parse(struct lemon
*gp
)
2813 unsigned int filesize
;
2819 memset(&ps
, '\0', sizeof(ps
));
2821 ps
.filename
= gp
->filename
;
2823 ps
.state
= INITIALIZE
;
2825 /* Begin by reading the input file */
2826 fp
= fopen(ps
.filename
,"rb");
2828 ErrorMsg(ps
.filename
,0,"Can't open this file for reading.");
2833 filesize
= ftell(fp
);
2835 filebuf
= (char *)malloc( filesize
+1 );
2836 if( filesize
>100000000 || filebuf
==0 ){
2837 ErrorMsg(ps
.filename
,0,"Input file too large.");
2842 if( fread(filebuf
,1,filesize
,fp
)!=filesize
){
2843 ErrorMsg(ps
.filename
,0,"Can't read in all %d bytes of this file.",
2851 filebuf
[filesize
] = 0;
2853 /* Make an initial pass through the file to handle %ifdef and %ifndef */
2854 preprocess_input(filebuf
);
2856 /* Now scan the text of the input file */
2858 for(cp
=filebuf
; (c
= *cp
)!=0; ){
2859 if( c
=='\n' ) lineno
++; /* Keep track of the line number */
2860 if( ISSPACE(c
) ){ cp
++; continue; } /* Skip all white space */
2861 if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments */
2863 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2866 if( c
=='/' && cp
[1]=='*' ){ /* Skip C style comments */
2868 while( (c
= *cp
)!=0 && (c
!='/' || cp
[-1]!='*') ){
2869 if( c
=='\n' ) lineno
++;
2875 ps
.tokenstart
= cp
; /* Mark the beginning of the token */
2876 ps
.tokenlineno
= lineno
; /* Linenumber on which token begins */
2877 if( c
=='\"' ){ /* String literals */
2879 while( (c
= *cp
)!=0 && c
!='\"' ){
2880 if( c
=='\n' ) lineno
++;
2884 ErrorMsg(ps
.filename
,startline
,
2885 "String starting on this line is not terminated before the end of the file.");
2891 }else if( c
=='{' ){ /* A block of C code */
2894 for(level
=1; (c
= *cp
)!=0 && (level
>1 || c
!='}'); cp
++){
2895 if( c
=='\n' ) lineno
++;
2896 else if( c
=='{' ) level
++;
2897 else if( c
=='}' ) level
--;
2898 else if( c
=='/' && cp
[1]=='*' ){ /* Skip comments */
2902 while( (c
= *cp
)!=0 && (c
!='/' || prevc
!='*') ){
2903 if( c
=='\n' ) lineno
++;
2907 }else if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments too */
2909 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2911 }else if( c
=='\'' || c
=='\"' ){ /* String a character literals */
2912 int startchar
, prevc
;
2915 for(cp
++; (c
= *cp
)!=0 && (c
!=startchar
|| prevc
=='\\'); cp
++){
2916 if( c
=='\n' ) lineno
++;
2917 if( prevc
=='\\' ) prevc
= 0;
2923 ErrorMsg(ps
.filename
,ps
.tokenlineno
,
2924 "C code starting on this line is not terminated before the end of the file.");
2930 }else if( ISALNUM(c
) ){ /* Identifiers */
2931 while( (c
= *cp
)!=0 && (ISALNUM(c
) || c
=='_') ) cp
++;
2933 }else if( c
==':' && cp
[1]==':' && cp
[2]=='=' ){ /* The operator "::=" */
2936 }else if( (c
=='/' || c
=='|') && ISALPHA(cp
[1]) ){
2938 while( (c
= *cp
)!=0 && (ISALNUM(c
) || c
=='_') ) cp
++;
2940 }else{ /* All other (one character) operators */
2945 *cp
= 0; /* Null terminate the token */
2946 parseonetoken(&ps
); /* Parse the token */
2947 *cp
= (char)c
; /* Restore the buffer */
2950 free(filebuf
); /* Release the buffer after parsing */
2951 gp
->rule
= ps
.firstrule
;
2952 gp
->errorcnt
= ps
.errorcnt
;
2954 /*************************** From the file "plink.c" *********************/
2956 ** Routines processing configuration follow-set propagation links
2957 ** in the LEMON parser generator.
2959 static struct plink
*plink_freelist
= 0;
2961 /* Allocate a new plink */
2962 struct plink
*Plink_new(void){
2963 struct plink
*newlink
;
2965 if( plink_freelist
==0 ){
2968 plink_freelist
= (struct plink
*)calloc( amt
, sizeof(struct plink
) );
2969 if( plink_freelist
==0 ){
2971 "Unable to allocate memory for a new follow-set propagation link.\n");
2974 for(i
=0; i
<amt
-1; i
++) plink_freelist
[i
].next
= &plink_freelist
[i
+1];
2975 plink_freelist
[amt
-1].next
= 0;
2977 newlink
= plink_freelist
;
2978 plink_freelist
= plink_freelist
->next
;
2982 /* Add a plink to a plink list */
2983 void Plink_add(struct plink
**plpp
, struct config
*cfp
)
2985 struct plink
*newlink
;
2986 newlink
= Plink_new();
2987 newlink
->next
= *plpp
;
2992 /* Transfer every plink on the list "from" to the list "to" */
2993 void Plink_copy(struct plink
**to
, struct plink
*from
)
2995 struct plink
*nextpl
;
2997 nextpl
= from
->next
;
3004 /* Delete every plink on the list */
3005 void Plink_delete(struct plink
*plp
)
3007 struct plink
*nextpl
;
3011 plp
->next
= plink_freelist
;
3012 plink_freelist
= plp
;
3016 /*********************** From the file "report.c" **************************/
3018 ** Procedures for generating reports and tables in the LEMON parser generator.
3021 /* Generate a filename with the given suffix. Space to hold the
3022 ** name comes from malloc() and must be freed by the calling
3025 PRIVATE
char *file_makename(struct lemon
*lemp
, const char *suffix
)
3030 name
= (char*)malloc( lemonStrlen(lemp
->filename
) + lemonStrlen(suffix
) + 5 );
3032 fprintf(stderr
,"Can't allocate space for a filename.\n");
3035 lemon_strcpy(name
,lemp
->filename
);
3036 cp
= strrchr(name
,'.');
3038 lemon_strcat(name
,suffix
);
3042 /* Open a file with a name based on the name of the input file,
3043 ** but with a different (specified) suffix, and return a pointer
3045 PRIVATE
FILE *file_open(
3052 if( lemp
->outname
) free(lemp
->outname
);
3053 lemp
->outname
= file_makename(lemp
, suffix
);
3054 fp
= fopen(lemp
->outname
,mode
);
3055 if( fp
==0 && *mode
=='w' ){
3056 fprintf(stderr
,"Can't open file \"%s\".\n",lemp
->outname
);
3063 /* Print the text of a rule
3065 void rule_print(FILE *out
, struct rule
*rp
){
3067 fprintf(out
, "%s",rp
->lhs
->name
);
3068 /* if( rp->lhsalias ) fprintf(out,"(%s)",rp->lhsalias); */
3069 fprintf(out
," ::=");
3070 for(i
=0; i
<rp
->nrhs
; i
++){
3071 struct symbol
*sp
= rp
->rhs
[i
];
3072 if( sp
->type
==MULTITERMINAL
){
3073 fprintf(out
," %s", sp
->subsym
[0]->name
);
3074 for(j
=1; j
<sp
->nsubsym
; j
++){
3075 fprintf(out
,"|%s", sp
->subsym
[j
]->name
);
3078 fprintf(out
," %s", sp
->name
);
3080 /* if( rp->rhsalias[i] ) fprintf(out,"(%s)",rp->rhsalias[i]); */
3084 /* Duplicate the input file without comments and without actions
3086 void Reprint(struct lemon
*lemp
)
3090 int i
, j
, maxlen
, len
, ncolumns
, skip
;
3091 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp
->filename
);
3093 for(i
=0; i
<lemp
->nsymbol
; i
++){
3094 sp
= lemp
->symbols
[i
];
3095 len
= lemonStrlen(sp
->name
);
3096 if( len
>maxlen
) maxlen
= len
;
3098 ncolumns
= 76/(maxlen
+5);
3099 if( ncolumns
<1 ) ncolumns
= 1;
3100 skip
= (lemp
->nsymbol
+ ncolumns
- 1)/ncolumns
;
3101 for(i
=0; i
<skip
; i
++){
3103 for(j
=i
; j
<lemp
->nsymbol
; j
+=skip
){
3104 sp
= lemp
->symbols
[j
];
3105 assert( sp
->index
==j
);
3106 printf(" %3d %-*.*s",j
,maxlen
,maxlen
,sp
->name
);
3110 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3111 rule_print(stdout
, rp
);
3113 if( rp
->precsym
) printf(" [%s]",rp
->precsym
->name
);
3114 /* if( rp->code ) printf("\n %s",rp->code); */
3119 /* Print a single rule.
3121 void RulePrint(FILE *fp
, struct rule
*rp
, int iCursor
){
3124 fprintf(fp
,"%s ::=",rp
->lhs
->name
);
3125 for(i
=0; i
<=rp
->nrhs
; i
++){
3126 if( i
==iCursor
) fprintf(fp
," *");
3127 if( i
==rp
->nrhs
) break;
3129 if( sp
->type
==MULTITERMINAL
){
3130 fprintf(fp
," %s", sp
->subsym
[0]->name
);
3131 for(j
=1; j
<sp
->nsubsym
; j
++){
3132 fprintf(fp
,"|%s",sp
->subsym
[j
]->name
);
3135 fprintf(fp
," %s", sp
->name
);
3140 /* Print the rule for a configuration.
3142 void ConfigPrint(FILE *fp
, struct config
*cfp
){
3143 RulePrint(fp
, cfp
->rp
, cfp
->dot
);
3149 PRIVATE
void SetPrint(out
,set
,lemp
)
3157 fprintf(out
,"%12s[","");
3158 for(i
=0; i
<lemp
->nterminal
; i
++){
3159 if( SetFind(set
,i
) ){
3160 fprintf(out
,"%s%s",spacer
,lemp
->symbols
[i
]->name
);
3167 /* Print a plink chain */
3168 PRIVATE
void PlinkPrint(out
,plp
,tag
)
3174 fprintf(out
,"%12s%s (state %2d) ","",tag
,plp
->cfp
->stp
->statenum
);
3175 ConfigPrint(out
,plp
->cfp
);
3182 /* Print an action to the given file descriptor. Return FALSE if
3183 ** nothing was actually printed.
3186 struct action
*ap
, /* The action to print */
3187 FILE *fp
, /* Print the action here */
3188 int indent
/* Indent by this amount */
3193 struct state
*stp
= ap
->x
.stp
;
3194 fprintf(fp
,"%*s shift %-7d",indent
,ap
->sp
->name
,stp
->statenum
);
3198 struct rule
*rp
= ap
->x
.rp
;
3199 fprintf(fp
,"%*s reduce %-7d",indent
,ap
->sp
->name
,rp
->iRule
);
3200 RulePrint(fp
, rp
, -1);
3204 struct rule
*rp
= ap
->x
.rp
;
3205 fprintf(fp
,"%*s shift-reduce %-7d",indent
,ap
->sp
->name
,rp
->iRule
);
3206 RulePrint(fp
, rp
, -1);
3210 fprintf(fp
,"%*s accept",indent
,ap
->sp
->name
);
3213 fprintf(fp
,"%*s error",indent
,ap
->sp
->name
);
3217 fprintf(fp
,"%*s reduce %-7d ** Parsing conflict **",
3218 indent
,ap
->sp
->name
,ap
->x
.rp
->iRule
);
3221 fprintf(fp
,"%*s shift %-7d ** Parsing conflict **",
3222 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3225 if( showPrecedenceConflict
){
3226 fprintf(fp
,"%*s shift %-7d -- dropped by precedence",
3227 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3233 if( showPrecedenceConflict
){
3234 fprintf(fp
,"%*s reduce %-7d -- dropped by precedence",
3235 indent
,ap
->sp
->name
,ap
->x
.rp
->iRule
);
3244 if( result
&& ap
->spOpt
){
3245 fprintf(fp
," /* because %s==%s */", ap
->sp
->name
, ap
->spOpt
->name
);
3250 /* Generate the "*.out" log file */
3251 void ReportOutput(struct lemon
*lemp
)
3260 fp
= file_open(lemp
,".out","wb");
3262 for(i
=0; i
<lemp
->nxstate
; i
++){
3263 stp
= lemp
->sorted
[i
];
3264 fprintf(fp
,"State %d:\n",stp
->statenum
);
3265 if( lemp
->basisflag
) cfp
=stp
->bp
;
3269 if( cfp
->dot
==cfp
->rp
->nrhs
){
3270 lemon_sprintf(buf
,"(%d)",cfp
->rp
->iRule
);
3271 fprintf(fp
," %5s ",buf
);
3275 ConfigPrint(fp
,cfp
);
3278 SetPrint(fp
,cfp
->fws
,lemp
);
3279 PlinkPrint(fp
,cfp
->fplp
,"To ");
3280 PlinkPrint(fp
,cfp
->bplp
,"From");
3282 if( lemp
->basisflag
) cfp
=cfp
->bp
;
3286 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3287 if( PrintAction(ap
,fp
,30) ) fprintf(fp
,"\n");
3291 fprintf(fp
, "----------------------------------------------------\n");
3292 fprintf(fp
, "Symbols:\n");
3293 for(i
=0; i
<lemp
->nsymbol
; i
++){
3297 sp
= lemp
->symbols
[i
];
3298 fprintf(fp
, " %3d: %s", i
, sp
->name
);
3299 if( sp
->type
==NONTERMINAL
){
3302 fprintf(fp
, " <lambda>");
3304 for(j
=0; j
<lemp
->nterminal
; j
++){
3305 if( sp
->firstset
&& SetFind(sp
->firstset
, j
) ){
3306 fprintf(fp
, " %s", lemp
->symbols
[j
]->name
);
3310 if( sp
->prec
>=0 ) fprintf(fp
," (precedence=%d)", sp
->prec
);
3313 fprintf(fp
, "----------------------------------------------------\n");
3314 fprintf(fp
, "Rules:\n");
3315 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3316 fprintf(fp
, "%4d: ", rp
->iRule
);
3320 fprintf(fp
," [%s precedence=%d]",
3321 rp
->precsym
->name
, rp
->precsym
->prec
);
3329 /* Search for the file "name" which is in the same directory as
3330 ** the exacutable */
3331 PRIVATE
char *pathsearch(char *argv0
, char *name
, int modemask
)
3333 const char *pathlist
;
3340 cp
= strrchr(argv0
,'\\');
3342 cp
= strrchr(argv0
,'/');
3347 path
= (char *)malloc( lemonStrlen(argv0
) + lemonStrlen(name
) + 2 );
3348 if( path
) lemon_sprintf(path
,"%s/%s",argv0
,name
);
3351 pathlist
= getenv("PATH");
3352 if( pathlist
==0 ) pathlist
= ".:/bin:/usr/bin";
3353 pathbuf
= (char *) malloc( lemonStrlen(pathlist
) + 1 );
3354 path
= (char *)malloc( lemonStrlen(pathlist
)+lemonStrlen(name
)+2 );
3355 if( (pathbuf
!= 0) && (path
!=0) ){
3356 pathbufptr
= pathbuf
;
3357 lemon_strcpy(pathbuf
, pathlist
);
3359 cp
= strchr(pathbuf
,':');
3360 if( cp
==0 ) cp
= &pathbuf
[lemonStrlen(pathbuf
)];
3363 lemon_sprintf(path
,"%s/%s",pathbuf
,name
);
3365 if( c
==0 ) pathbuf
[0] = 0;
3366 else pathbuf
= &cp
[1];
3367 if( access(path
,modemask
)==0 ) break;
3375 /* Given an action, compute the integer value for that action
3376 ** which is to be put in the action table of the generated machine.
3377 ** Return negative if no action should be generated.
3379 PRIVATE
int compute_action(struct lemon
*lemp
, struct action
*ap
)
3383 case SHIFT
: act
= ap
->x
.stp
->statenum
; break;
3385 /* Since a SHIFT is inherient after a prior REDUCE, convert any
3386 ** SHIFTREDUCE action with a nonterminal on the LHS into a simple
3387 ** REDUCE action: */
3388 if( ap
->sp
->index
>=lemp
->nterminal
){
3389 act
= lemp
->minReduce
+ ap
->x
.rp
->iRule
;
3391 act
= lemp
->minShiftReduce
+ ap
->x
.rp
->iRule
;
3395 case REDUCE
: act
= lemp
->minReduce
+ ap
->x
.rp
->iRule
; break;
3396 case ERROR
: act
= lemp
->errAction
; break;
3397 case ACCEPT
: act
= lemp
->accAction
; break;
3398 default: act
= -1; break;
3403 #define LINESIZE 1000
3404 /* The next cluster of routines are for reading the template file
3405 ** and writing the results to the generated parser */
3406 /* The first function transfers data from "in" to "out" until
3407 ** a line is seen which begins with "%%". The line number is
3410 ** if name!=0, then any word that begin with "Parse" is changed to
3411 ** begin with *name instead.
3413 PRIVATE
void tplt_xfer(char *name
, FILE *in
, FILE *out
, int *lineno
)
3416 char line
[LINESIZE
];
3417 while( fgets(line
,LINESIZE
,in
) && (line
[0]!='%' || line
[1]!='%') ){
3421 for(i
=0; line
[i
]; i
++){
3422 if( line
[i
]=='P' && strncmp(&line
[i
],"Parse",5)==0
3423 && (i
==0 || !ISALPHA(line
[i
-1]))
3425 if( i
>iStart
) fprintf(out
,"%.*s",i
-iStart
,&line
[iStart
]);
3426 fprintf(out
,"%s",name
);
3432 fprintf(out
,"%s",&line
[iStart
]);
3436 /* The next function finds the template file and opens it, returning
3437 ** a pointer to the opened file. */
3438 PRIVATE
FILE *tplt_open(struct lemon
*lemp
)
3440 static char templatename
[] = "lempar.c";
3446 /* first, see if user specified a template filename on the command line. */
3447 if (user_templatename
!= 0) {
3448 if( access(user_templatename
,004)==-1 ){
3449 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3454 in
= fopen(user_templatename
,"rb");
3456 fprintf(stderr
,"Can't open the template file \"%s\".\n",
3464 cp
= strrchr(lemp
->filename
,'.');
3466 lemon_sprintf(buf
,"%.*s.lt",(int)(cp
-lemp
->filename
),lemp
->filename
);
3468 lemon_sprintf(buf
,"%s.lt",lemp
->filename
);
3470 if( access(buf
,004)==0 ){
3472 }else if( access(templatename
,004)==0 ){
3473 tpltname
= templatename
;
3475 tpltname
= pathsearch(lemp
->argv0
,templatename
,0);
3478 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3483 in
= fopen(tpltname
,"rb");
3485 fprintf(stderr
,"Can't open the template file \"%s\".\n",templatename
);
3492 /* Print a #line directive line to the output file. */
3493 PRIVATE
void tplt_linedir(FILE *out
, int lineno
, char *filename
)
3495 fprintf(out
,"#line %d \"",lineno
);
3497 if( *filename
== '\\' ) putc('\\',out
);
3498 putc(*filename
,out
);
3501 fprintf(out
,"\"\n");
3504 /* Print a string to the file and keep the linenumber up to date */
3505 PRIVATE
void tplt_print(FILE *out
, struct lemon
*lemp
, char *str
, int *lineno
)
3507 if( str
==0 ) return;
3510 if( *str
=='\n' ) (*lineno
)++;
3513 if( str
[-1]!='\n' ){
3517 if (!lemp
->nolinenosflag
) {
3518 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3524 ** The following routine emits code for the destructor for the
3527 void emit_destructor_code(
3535 if( sp
->type
==TERMINAL
){
3536 cp
= lemp
->tokendest
;
3538 fprintf(out
,"{\n"); (*lineno
)++;
3539 }else if( sp
->destructor
){
3540 cp
= sp
->destructor
;
3541 fprintf(out
,"{\n"); (*lineno
)++;
3542 if( !lemp
->nolinenosflag
){
3544 tplt_linedir(out
,sp
->destLineno
,lemp
->filename
);
3546 }else if( lemp
->vardest
){
3549 fprintf(out
,"{\n"); (*lineno
)++;
3551 assert( 0 ); /* Cannot happen */
3554 if( *cp
=='$' && cp
[1]=='$' ){
3555 fprintf(out
,"(yypminor->yy%d)",sp
->dtnum
);
3559 if( *cp
=='\n' ) (*lineno
)++;
3562 fprintf(out
,"\n"); (*lineno
)++;
3563 if (!lemp
->nolinenosflag
) {
3564 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3566 fprintf(out
,"}\n"); (*lineno
)++;
3571 ** Return TRUE (non-zero) if the given symbol has a destructor.
3573 int has_destructor(struct symbol
*sp
, struct lemon
*lemp
)
3576 if( sp
->type
==TERMINAL
){
3577 ret
= lemp
->tokendest
!=0;
3579 ret
= lemp
->vardest
!=0 || sp
->destructor
!=0;
3585 ** Append text to a dynamically allocated string. If zText is 0 then
3586 ** reset the string to be empty again. Always return the complete text
3587 ** of the string (which is overwritten with each call).
3589 ** n bytes of zText are stored. If n==0 then all of zText up to the first
3590 ** \000 terminator is stored. zText can contain up to two instances of
3591 ** %d. The values of p1 and p2 are written into the first and second
3594 ** If n==-1, then the previous character is overwritten.
3596 PRIVATE
char *append_str(const char *zText
, int n
, int p1
, int p2
){
3597 static char empty
[1] = { 0 };
3599 static int alloced
= 0;
3600 static int used
= 0;
3604 if( used
==0 && z
!=0 ) z
[0] = 0;
3613 n
= lemonStrlen(zText
);
3615 if( (int) (n
+sizeof(zInt
)*2+used
) >= alloced
){
3616 alloced
= n
+ sizeof(zInt
)*2 + used
+ 200;
3617 z
= (char *) realloc(z
, alloced
);
3619 if( z
==0 ) return empty
;
3622 if( c
=='%' && n
>0 && zText
[0]=='d' ){
3623 lemon_sprintf(zInt
, "%d", p1
);
3625 lemon_strcpy(&z
[used
], zInt
);
3626 used
+= lemonStrlen(&z
[used
]);
3630 z
[used
++] = (char)c
;
3638 ** Write and transform the rp->code string so that symbols are expanded.
3639 ** Populate the rp->codePrefix and rp->codeSuffix strings, as appropriate.
3641 ** Return 1 if the expanded code requires that "yylhsminor" local variable
3644 PRIVATE
int translate_code(struct lemon
*lemp
, struct rule
*rp
){
3647 int rc
= 0; /* True if yylhsminor is used */
3648 int dontUseRhs0
= 0; /* If true, use of left-most RHS label is illegal */
3649 const char *zSkip
= 0; /* The zOvwrt comment within rp->code, or NULL */
3650 char lhsused
= 0; /* True if the LHS element has been used */
3651 char lhsdirect
; /* True if LHS writes directly into stack */
3652 char used
[MAXRHS
]; /* True for each RHS element which is used */
3653 char zLhs
[50]; /* Convert the LHS symbol into this string */
3654 char zOvwrt
[900]; /* Comment that to allow LHS to overwrite RHS */
3656 for(i
=0; i
<rp
->nrhs
; i
++) used
[i
] = 0;
3660 static char newlinestr
[2] = { '\n', '\0' };
3661 rp
->code
= newlinestr
;
3662 rp
->line
= rp
->ruleline
;
3670 /* If there are no RHS symbols, then writing directly to the LHS is ok */
3672 }else if( rp
->rhsalias
[0]==0 ){
3673 /* The left-most RHS symbol has no value. LHS direct is ok. But
3674 ** we have to call the distructor on the RHS symbol first. */
3676 if( has_destructor(rp
->rhs
[0],lemp
) ){
3677 append_str(0,0,0,0);
3678 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3679 rp
->rhs
[0]->index
,1-rp
->nrhs
);
3680 rp
->codePrefix
= Strsafe(append_str(0,0,0,0));
3683 }else if( rp
->lhsalias
==0 ){
3684 /* There is no LHS value symbol. */
3686 }else if( strcmp(rp
->lhsalias
,rp
->rhsalias
[0])==0 ){
3687 /* The LHS symbol and the left-most RHS symbol are the same, so
3688 ** direct writing is allowed */
3692 if( rp
->lhs
->dtnum
!=rp
->rhs
[0]->dtnum
){
3693 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3694 "%s(%s) and %s(%s) share the same label but have "
3695 "different datatypes.",
3696 rp
->lhs
->name
, rp
->lhsalias
, rp
->rhs
[0]->name
, rp
->rhsalias
[0]);
3700 lemon_sprintf(zOvwrt
, "/*%s-overwrites-%s*/",
3701 rp
->lhsalias
, rp
->rhsalias
[0]);
3702 zSkip
= strstr(rp
->code
, zOvwrt
);
3704 /* The code contains a special comment that indicates that it is safe
3705 ** for the LHS label to overwrite left-most RHS label. */
3712 sprintf(zLhs
, "yymsp[%d].minor.yy%d",1-rp
->nrhs
,rp
->lhs
->dtnum
);
3715 sprintf(zLhs
, "yylhsminor.yy%d",rp
->lhs
->dtnum
);
3718 append_str(0,0,0,0);
3720 /* This const cast is wrong but harmless, if we're careful. */
3721 for(cp
=(char *)rp
->code
; *cp
; cp
++){
3723 append_str(zOvwrt
,0,0,0);
3724 cp
+= lemonStrlen(zOvwrt
)-1;
3728 if( ISALPHA(*cp
) && (cp
==rp
->code
|| (!ISALNUM(cp
[-1]) && cp
[-1]!='_')) ){
3730 for(xp
= &cp
[1]; ISALNUM(*xp
) || *xp
=='_'; xp
++);
3733 if( rp
->lhsalias
&& strcmp(cp
,rp
->lhsalias
)==0 ){
3734 append_str(zLhs
,0,0,0);
3738 for(i
=0; i
<rp
->nrhs
; i
++){
3739 if( rp
->rhsalias
[i
] && strcmp(cp
,rp
->rhsalias
[i
])==0 ){
3740 if( i
==0 && dontUseRhs0
){
3741 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3742 "Label %s used after '%s'.",
3743 rp
->rhsalias
[0], zOvwrt
);
3745 }else if( cp
!=rp
->code
&& cp
[-1]=='@' ){
3746 /* If the argument is of the form @X then substituted
3747 ** the token number of X, not the value of X */
3748 append_str("yymsp[%d].major",-1,i
-rp
->nrhs
+1,0);
3750 struct symbol
*sp
= rp
->rhs
[i
];
3752 if( sp
->type
==MULTITERMINAL
){
3753 dtnum
= sp
->subsym
[0]->dtnum
;
3757 append_str("yymsp[%d].minor.yy%d",0,i
-rp
->nrhs
+1, dtnum
);
3767 append_str(cp
, 1, 0, 0);
3770 /* Main code generation completed */
3771 cp
= append_str(0,0,0,0);
3772 if( cp
&& cp
[0] ) rp
->code
= Strsafe(cp
);
3773 append_str(0,0,0,0);
3775 /* Check to make sure the LHS has been used */
3776 if( rp
->lhsalias
&& !lhsused
){
3777 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3778 "Label \"%s\" for \"%s(%s)\" is never used.",
3779 rp
->lhsalias
,rp
->lhs
->name
,rp
->lhsalias
);
3783 /* Generate destructor code for RHS minor values which are not referenced.
3784 ** Generate error messages for unused labels and duplicate labels.
3786 for(i
=0; i
<rp
->nrhs
; i
++){
3787 if( rp
->rhsalias
[i
] ){
3790 if( rp
->lhsalias
&& strcmp(rp
->lhsalias
,rp
->rhsalias
[i
])==0 ){
3791 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3792 "%s(%s) has the same label as the LHS but is not the left-most "
3793 "symbol on the RHS.",
3794 rp
->rhs
[i
]->name
, rp
->rhsalias
);
3798 if( rp
->rhsalias
[j
] && strcmp(rp
->rhsalias
[j
],rp
->rhsalias
[i
])==0 ){
3799 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3800 "Label %s used for multiple symbols on the RHS of a rule.",
3808 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3809 "Label %s for \"%s(%s)\" is never used.",
3810 rp
->rhsalias
[i
],rp
->rhs
[i
]->name
,rp
->rhsalias
[i
]);
3813 }else if( i
>0 && has_destructor(rp
->rhs
[i
],lemp
) ){
3814 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3815 rp
->rhs
[i
]->index
,i
-rp
->nrhs
+1);
3819 /* If unable to write LHS values directly into the stack, write the
3820 ** saved LHS value now. */
3822 append_str(" yymsp[%d].minor.yy%d = ", 0, 1-rp
->nrhs
, rp
->lhs
->dtnum
);
3823 append_str(zLhs
, 0, 0, 0);
3824 append_str(";\n", 0, 0, 0);
3827 /* Suffix code generation complete */
3828 cp
= append_str(0,0,0,0);
3830 rp
->codeSuffix
= Strsafe(cp
);
3838 ** Generate code which executes when the rule "rp" is reduced. Write
3839 ** the code to "out". Make sure lineno stays up-to-date.
3841 PRIVATE
void emit_code(
3849 /* Setup code prior to the #line directive */
3850 if( rp
->codePrefix
&& rp
->codePrefix
[0] ){
3851 fprintf(out
, "{%s", rp
->codePrefix
);
3852 for(cp
=rp
->codePrefix
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
3855 /* Generate code to do the reduce action */
3857 if( !lemp
->nolinenosflag
){
3859 tplt_linedir(out
,rp
->line
,lemp
->filename
);
3861 fprintf(out
,"{%s",rp
->code
);
3862 for(cp
=rp
->code
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
3863 fprintf(out
,"}\n"); (*lineno
)++;
3864 if( !lemp
->nolinenosflag
){
3866 tplt_linedir(out
,*lineno
,lemp
->outname
);
3870 /* Generate breakdown code that occurs after the #line directive */
3871 if( rp
->codeSuffix
&& rp
->codeSuffix
[0] ){
3872 fprintf(out
, "%s", rp
->codeSuffix
);
3873 for(cp
=rp
->codeSuffix
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
3876 if( rp
->codePrefix
){
3877 fprintf(out
, "}\n"); (*lineno
)++;
3884 ** Print the definition of the union used for the parser's data stack.
3885 ** This union contains fields for every possible data type for tokens
3886 ** and nonterminals. In the process of computing and printing this
3887 ** union, also set the ".dtnum" field of every terminal and nonterminal
3890 void print_stack_union(
3891 FILE *out
, /* The output stream */
3892 struct lemon
*lemp
, /* The main info structure for this parser */
3893 int *plineno
, /* Pointer to the line number */
3894 int mhflag
/* True if generating makeheaders output */
3896 int lineno
= *plineno
; /* The line number of the output */
3897 char **types
; /* A hash table of datatypes */
3898 int arraysize
; /* Size of the "types" array */
3899 int maxdtlength
; /* Maximum length of any ".datatype" field. */
3900 char *stddt
; /* Standardized name for a datatype */
3901 int i
,j
; /* Loop counters */
3902 unsigned hash
; /* For hashing the name of a type */
3903 const char *name
; /* Name of the parser */
3905 /* Allocate and initialize types[] and allocate stddt[] */
3906 arraysize
= lemp
->nsymbol
* 2;
3907 types
= (char**)calloc( arraysize
, sizeof(char*) );
3909 fprintf(stderr
,"Out of memory.\n");
3912 for(i
=0; i
<arraysize
; i
++) types
[i
] = 0;
3914 if( lemp
->vartype
){
3915 maxdtlength
= lemonStrlen(lemp
->vartype
);
3917 for(i
=0; i
<lemp
->nsymbol
; i
++){
3919 struct symbol
*sp
= lemp
->symbols
[i
];
3920 if( sp
->datatype
==0 ) continue;
3921 len
= lemonStrlen(sp
->datatype
);
3922 if( len
>maxdtlength
) maxdtlength
= len
;
3924 stddt
= (char*)malloc( maxdtlength
*2 + 1 );
3926 fprintf(stderr
,"Out of memory.\n");
3930 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3931 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
3932 ** used for terminal symbols. If there is no %default_type defined then
3933 ** 0 is also used as the .dtnum value for nonterminals which do not specify
3934 ** a datatype using the %type directive.
3936 for(i
=0; i
<lemp
->nsymbol
; i
++){
3937 struct symbol
*sp
= lemp
->symbols
[i
];
3939 if( sp
==lemp
->errsym
){
3940 sp
->dtnum
= arraysize
+1;
3943 if( sp
->type
!=NONTERMINAL
|| (sp
->datatype
==0 && lemp
->vartype
==0) ){
3948 if( cp
==0 ) cp
= lemp
->vartype
;
3950 while( ISSPACE(*cp
) ) cp
++;
3951 while( *cp
) stddt
[j
++] = *cp
++;
3952 while( j
>0 && ISSPACE(stddt
[j
-1]) ) j
--;
3954 if( lemp
->tokentype
&& strcmp(stddt
, lemp
->tokentype
)==0 ){
3959 for(j
=0; stddt
[j
]; j
++){
3960 hash
= hash
*53 + stddt
[j
];
3962 hash
= (hash
& 0x7fffffff)%arraysize
;
3963 while( types
[hash
] ){
3964 if( strcmp(types
[hash
],stddt
)==0 ){
3965 sp
->dtnum
= hash
+ 1;
3969 if( hash
>=(unsigned)arraysize
) hash
= 0;
3971 if( types
[hash
]==0 ){
3972 sp
->dtnum
= hash
+ 1;
3973 types
[hash
] = (char*)malloc( lemonStrlen(stddt
)+1 );
3974 if( types
[hash
]==0 ){
3975 fprintf(stderr
,"Out of memory.\n");
3978 lemon_strcpy(types
[hash
],stddt
);
3982 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3983 name
= lemp
->name
? lemp
->name
: "Parse";
3985 if( mhflag
){ fprintf(out
,"#if INTERFACE\n"); lineno
++; }
3986 fprintf(out
,"#define %sTOKENTYPE %s\n",name
,
3987 lemp
->tokentype
?lemp
->tokentype
:"void*"); lineno
++;
3988 if( mhflag
){ fprintf(out
,"#endif\n"); lineno
++; }
3989 fprintf(out
,"typedef union {\n"); lineno
++;
3990 fprintf(out
," int yyinit;\n"); lineno
++;
3991 fprintf(out
," %sTOKENTYPE yy0;\n",name
); lineno
++;
3992 for(i
=0; i
<arraysize
; i
++){
3993 if( types
[i
]==0 ) continue;
3994 fprintf(out
," %s yy%d;\n",types
[i
],i
+1); lineno
++;
3997 if( lemp
->errsym
->useCnt
){
3998 fprintf(out
," int yy%d;\n",lemp
->errsym
->dtnum
); lineno
++;
4002 fprintf(out
,"} YYMINORTYPE;\n"); lineno
++;
4007 ** Return the name of a C datatype able to represent values between
4008 ** lwr and upr, inclusive. If pnByte!=NULL then also write the sizeof
4009 ** for that type (1, 2, or 4) into *pnByte.
4011 static const char *minimum_size_type(int lwr
, int upr
, int *pnByte
){
4012 const char *zType
= "int";
4016 zType
= "unsigned char";
4018 }else if( upr
<65535 ){
4019 zType
= "unsigned short int";
4022 zType
= "unsigned int";
4025 }else if( lwr
>=-127 && upr
<=127 ){
4026 zType
= "signed char";
4028 }else if( lwr
>=-32767 && upr
<32767 ){
4032 if( pnByte
) *pnByte
= nByte
;
4037 ** Each state contains a set of token transaction and a set of
4038 ** nonterminal transactions. Each of these sets makes an instance
4039 ** of the following structure. An array of these structures is used
4040 ** to order the creation of entries in the yy_action[] table.
4043 struct state
*stp
; /* A pointer to a state */
4044 int isTkn
; /* True to use tokens. False for non-terminals */
4045 int nAction
; /* Number of actions */
4046 int iOrder
; /* Original order of action sets */
4050 ** Compare to axset structures for sorting purposes
4052 static int axset_compare(const void *a
, const void *b
){
4053 struct axset
*p1
= (struct axset
*)a
;
4054 struct axset
*p2
= (struct axset
*)b
;
4056 c
= p2
->nAction
- p1
->nAction
;
4058 c
= p1
->iOrder
- p2
->iOrder
;
4060 assert( c
!=0 || p1
==p2
);
4065 ** Write text on "out" that describes the rule "rp".
4067 static void writeRuleText(FILE *out
, struct rule
*rp
){
4069 fprintf(out
,"%s ::=", rp
->lhs
->name
);
4070 for(j
=0; j
<rp
->nrhs
; j
++){
4071 struct symbol
*sp
= rp
->rhs
[j
];
4072 if( sp
->type
!=MULTITERMINAL
){
4073 fprintf(out
," %s", sp
->name
);
4076 fprintf(out
," %s", sp
->subsym
[0]->name
);
4077 for(k
=1; k
<sp
->nsubsym
; k
++){
4078 fprintf(out
,"|%s",sp
->subsym
[k
]->name
);
4085 /* Generate C source code for the parser */
4088 int mhflag
/* Output in makeheaders format if true */
4091 char line
[LINESIZE
];
4096 struct acttab
*pActtab
;
4098 int szActionType
; /* sizeof(YYACTIONTYPE) */
4099 int szCodeType
; /* sizeof(YYCODETYPE) */
4101 int mnTknOfst
, mxTknOfst
;
4102 int mnNtOfst
, mxNtOfst
;
4105 lemp
->minShiftReduce
= lemp
->nstate
;
4106 lemp
->errAction
= lemp
->minShiftReduce
+ lemp
->nrule
;
4107 lemp
->accAction
= lemp
->errAction
+ 1;
4108 lemp
->noAction
= lemp
->accAction
+ 1;
4109 lemp
->minReduce
= lemp
->noAction
+ 1;
4110 lemp
->maxAction
= lemp
->minReduce
+ lemp
->nrule
;
4112 in
= tplt_open(lemp
);
4114 out
= file_open(lemp
,".c","wb");
4120 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4122 /* Generate the include code, if any */
4123 tplt_print(out
,lemp
,lemp
->include
,&lineno
);
4125 char *incName
= file_makename(lemp
, ".h");
4126 fprintf(out
,"#include \"%s\"\n", incName
); lineno
++;
4129 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4131 /* Generate #defines for all tokens */
4134 fprintf(out
,"#if INTERFACE\n"); lineno
++;
4135 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
4137 for(i
=1; i
<lemp
->nterminal
; i
++){
4138 fprintf(out
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
4141 fprintf(out
,"#endif\n"); lineno
++;
4143 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4145 /* Generate the defines */
4146 fprintf(out
,"#define YYCODETYPE %s\n",
4147 minimum_size_type(0, lemp
->nsymbol
+1, &szCodeType
)); lineno
++;
4148 fprintf(out
,"#define YYNOCODE %d\n",lemp
->nsymbol
+1); lineno
++;
4149 fprintf(out
,"#define YYACTIONTYPE %s\n",
4150 minimum_size_type(0,lemp
->maxAction
,&szActionType
)); lineno
++;
4151 if( lemp
->wildcard
){
4152 fprintf(out
,"#define YYWILDCARD %d\n",
4153 lemp
->wildcard
->index
); lineno
++;
4155 print_stack_union(out
,lemp
,&lineno
,mhflag
);
4156 fprintf(out
, "#ifndef YYSTACKDEPTH\n"); lineno
++;
4157 if( lemp
->stacksize
){
4158 fprintf(out
,"#define YYSTACKDEPTH %s\n",lemp
->stacksize
); lineno
++;
4160 fprintf(out
,"#define YYSTACKDEPTH 100\n"); lineno
++;
4162 fprintf(out
, "#endif\n"); lineno
++;
4164 fprintf(out
,"#if INTERFACE\n"); lineno
++;
4166 name
= lemp
->name
? lemp
->name
: "Parse";
4167 if( lemp
->arg
&& lemp
->arg
[0] ){
4168 i
= lemonStrlen(lemp
->arg
);
4169 while( i
>=1 && ISSPACE(lemp
->arg
[i
-1]) ) i
--;
4170 while( i
>=1 && (ISALNUM(lemp
->arg
[i
-1]) || lemp
->arg
[i
-1]=='_') ) i
--;
4171 fprintf(out
,"#define %sARG_SDECL %s;\n",name
,lemp
->arg
); lineno
++;
4172 fprintf(out
,"#define %sARG_PDECL ,%s\n",name
,lemp
->arg
); lineno
++;
4173 fprintf(out
,"#define %sARG_FETCH %s = yypParser->%s\n",
4174 name
,lemp
->arg
,&lemp
->arg
[i
]); lineno
++;
4175 fprintf(out
,"#define %sARG_STORE yypParser->%s = %s\n",
4176 name
,&lemp
->arg
[i
],&lemp
->arg
[i
]); lineno
++;
4178 fprintf(out
,"#define %sARG_SDECL\n",name
); lineno
++;
4179 fprintf(out
,"#define %sARG_PDECL\n",name
); lineno
++;
4180 fprintf(out
,"#define %sARG_FETCH\n",name
); lineno
++;
4181 fprintf(out
,"#define %sARG_STORE\n",name
); lineno
++;
4184 fprintf(out
,"#endif\n"); lineno
++;
4186 if( lemp
->errsym
->useCnt
){
4187 fprintf(out
,"#define YYERRORSYMBOL %d\n",lemp
->errsym
->index
); lineno
++;
4188 fprintf(out
,"#define YYERRSYMDT yy%d\n",lemp
->errsym
->dtnum
); lineno
++;
4190 if( lemp
->has_fallback
){
4191 fprintf(out
,"#define YYFALLBACK 1\n"); lineno
++;
4194 /* Compute the action table, but do not output it yet. The action
4195 ** table must be computed before generating the YYNSTATE macro because
4196 ** we need to know how many states can be eliminated.
4198 ax
= (struct axset
*) calloc(lemp
->nxstate
*2, sizeof(ax
[0]));
4200 fprintf(stderr
,"malloc failed\n");
4203 for(i
=0; i
<lemp
->nxstate
; i
++){
4204 stp
= lemp
->sorted
[i
];
4207 ax
[i
*2].nAction
= stp
->nTknAct
;
4208 ax
[i
*2+1].stp
= stp
;
4209 ax
[i
*2+1].isTkn
= 0;
4210 ax
[i
*2+1].nAction
= stp
->nNtAct
;
4212 mxTknOfst
= mnTknOfst
= 0;
4213 mxNtOfst
= mnNtOfst
= 0;
4214 /* In an effort to minimize the action table size, use the heuristic
4215 ** of placing the largest action sets first */
4216 for(i
=0; i
<lemp
->nxstate
*2; i
++) ax
[i
].iOrder
= i
;
4217 qsort(ax
, lemp
->nxstate
*2, sizeof(ax
[0]), axset_compare
);
4218 pActtab
= acttab_alloc(lemp
->nsymbol
, lemp
->nterminal
);
4219 for(i
=0; i
<lemp
->nxstate
*2 && ax
[i
].nAction
>0; i
++){
4222 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4224 if( ap
->sp
->index
>=lemp
->nterminal
) continue;
4225 action
= compute_action(lemp
, ap
);
4226 if( action
<0 ) continue;
4227 acttab_action(pActtab
, ap
->sp
->index
, action
);
4229 stp
->iTknOfst
= acttab_insert(pActtab
, 1);
4230 if( stp
->iTknOfst
<mnTknOfst
) mnTknOfst
= stp
->iTknOfst
;
4231 if( stp
->iTknOfst
>mxTknOfst
) mxTknOfst
= stp
->iTknOfst
;
4233 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4235 if( ap
->sp
->index
<lemp
->nterminal
) continue;
4236 if( ap
->sp
->index
==lemp
->nsymbol
) continue;
4237 action
= compute_action(lemp
, ap
);
4238 if( action
<0 ) continue;
4239 acttab_action(pActtab
, ap
->sp
->index
, action
);
4241 stp
->iNtOfst
= acttab_insert(pActtab
, 0);
4242 if( stp
->iNtOfst
<mnNtOfst
) mnNtOfst
= stp
->iNtOfst
;
4243 if( stp
->iNtOfst
>mxNtOfst
) mxNtOfst
= stp
->iNtOfst
;
4245 #if 0 /* Uncomment for a trace of how the yy_action[] table fills out */
4247 for(jj
=nn
=0; jj
<pActtab
->nAction
; jj
++){
4248 if( pActtab
->aAction
[jj
].action
<0 ) nn
++;
4250 printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n",
4251 i
, stp
->statenum
, ax
[i
].isTkn
? "Token" : "Var ",
4252 ax
[i
].nAction
, pActtab
->nAction
, nn
);
4258 /* Mark rules that are actually used for reduce actions after all
4259 ** optimizations have been applied
4261 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->doesReduce
= LEMON_FALSE
;
4262 for(i
=0; i
<lemp
->nxstate
; i
++){
4263 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
4264 if( ap
->type
==REDUCE
|| ap
->type
==SHIFTREDUCE
){
4265 ap
->x
.rp
->doesReduce
= 1;
4270 /* Finish rendering the constants now that the action table has
4272 fprintf(out
,"#define YYNSTATE %d\n",lemp
->nxstate
); lineno
++;
4273 fprintf(out
,"#define YYNRULE %d\n",lemp
->nrule
); lineno
++;
4274 fprintf(out
,"#define YYNTOKEN %d\n",lemp
->nterminal
); lineno
++;
4275 fprintf(out
,"#define YY_MAX_SHIFT %d\n",lemp
->nxstate
-1); lineno
++;
4276 i
= lemp
->minShiftReduce
;
4277 fprintf(out
,"#define YY_MIN_SHIFTREDUCE %d\n",i
); lineno
++;
4279 fprintf(out
,"#define YY_MAX_SHIFTREDUCE %d\n", i
-1); lineno
++;
4280 fprintf(out
,"#define YY_ERROR_ACTION %d\n", lemp
->errAction
); lineno
++;
4281 fprintf(out
,"#define YY_ACCEPT_ACTION %d\n", lemp
->accAction
); lineno
++;
4282 fprintf(out
,"#define YY_NO_ACTION %d\n", lemp
->noAction
); lineno
++;
4283 fprintf(out
,"#define YY_MIN_REDUCE %d\n", lemp
->minReduce
); lineno
++;
4284 i
= lemp
->minReduce
+ lemp
->nrule
;
4285 fprintf(out
,"#define YY_MAX_REDUCE %d\n", i
-1); lineno
++;
4286 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4288 /* Now output the action table and its associates:
4290 ** yy_action[] A single table containing all actions.
4291 ** yy_lookahead[] A table containing the lookahead for each entry in
4292 ** yy_action. Used to detect hash collisions.
4293 ** yy_shift_ofst[] For each state, the offset into yy_action for
4294 ** shifting terminals.
4295 ** yy_reduce_ofst[] For each state, the offset into yy_action for
4296 ** shifting non-terminals after a reduce.
4297 ** yy_default[] Default action for each state.
4300 /* Output the yy_action table */
4301 lemp
->nactiontab
= n
= acttab_action_size(pActtab
);
4302 lemp
->tablesize
+= n
*szActionType
;
4303 fprintf(out
,"#define YY_ACTTAB_COUNT (%d)\n", n
); lineno
++;
4304 fprintf(out
,"static const YYACTIONTYPE yy_action[] = {\n"); lineno
++;
4305 for(i
=j
=0; i
<n
; i
++){
4306 int action
= acttab_yyaction(pActtab
, i
);
4307 if( action
<0 ) action
= lemp
->noAction
;
4308 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4309 fprintf(out
, " %4d,", action
);
4310 if( j
==9 || i
==n
-1 ){
4311 fprintf(out
, "\n"); lineno
++;
4317 fprintf(out
, "};\n"); lineno
++;
4319 /* Output the yy_lookahead table */
4320 lemp
->nlookaheadtab
= n
= acttab_lookahead_size(pActtab
);
4321 lemp
->tablesize
+= n
*szCodeType
;
4322 fprintf(out
,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno
++;
4323 for(i
=j
=0; i
<n
; i
++){
4324 int la
= acttab_yylookahead(pActtab
, i
);
4325 if( la
<0 ) la
= lemp
->nsymbol
;
4326 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4327 fprintf(out
, " %4d,", la
);
4328 if( j
==9 || i
==n
-1 ){
4329 fprintf(out
, "\n"); lineno
++;
4335 fprintf(out
, "};\n"); lineno
++;
4337 /* Output the yy_shift_ofst[] table */
4339 while( n
>0 && lemp
->sorted
[n
-1]->iTknOfst
==NO_OFFSET
) n
--;
4340 fprintf(out
, "#define YY_SHIFT_COUNT (%d)\n", n
-1); lineno
++;
4341 fprintf(out
, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst
); lineno
++;
4342 fprintf(out
, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst
); lineno
++;
4343 fprintf(out
, "static const %s yy_shift_ofst[] = {\n",
4344 minimum_size_type(mnTknOfst
, lemp
->nterminal
+lemp
->nactiontab
, &sz
));
4346 lemp
->tablesize
+= n
*sz
;
4347 for(i
=j
=0; i
<n
; i
++){
4349 stp
= lemp
->sorted
[i
];
4350 ofst
= stp
->iTknOfst
;
4351 if( ofst
==NO_OFFSET
) ofst
= lemp
->nactiontab
;
4352 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4353 fprintf(out
, " %4d,", ofst
);
4354 if( j
==9 || i
==n
-1 ){
4355 fprintf(out
, "\n"); lineno
++;
4361 fprintf(out
, "};\n"); lineno
++;
4363 /* Output the yy_reduce_ofst[] table */
4365 while( n
>0 && lemp
->sorted
[n
-1]->iNtOfst
==NO_OFFSET
) n
--;
4366 fprintf(out
, "#define YY_REDUCE_COUNT (%d)\n", n
-1); lineno
++;
4367 fprintf(out
, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst
); lineno
++;
4368 fprintf(out
, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst
); lineno
++;
4369 fprintf(out
, "static const %s yy_reduce_ofst[] = {\n",
4370 minimum_size_type(mnNtOfst
-1, mxNtOfst
, &sz
)); lineno
++;
4371 lemp
->tablesize
+= n
*sz
;
4372 for(i
=j
=0; i
<n
; i
++){
4374 stp
= lemp
->sorted
[i
];
4375 ofst
= stp
->iNtOfst
;
4376 if( ofst
==NO_OFFSET
) ofst
= mnNtOfst
- 1;
4377 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4378 fprintf(out
, " %4d,", ofst
);
4379 if( j
==9 || i
==n
-1 ){
4380 fprintf(out
, "\n"); lineno
++;
4386 fprintf(out
, "};\n"); lineno
++;
4388 /* Output the default action table */
4389 fprintf(out
, "static const YYACTIONTYPE yy_default[] = {\n"); lineno
++;
4391 lemp
->tablesize
+= n
*szActionType
;
4392 for(i
=j
=0; i
<n
; i
++){
4393 stp
= lemp
->sorted
[i
];
4394 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4395 if( stp
->iDfltReduce
<0 ){
4396 fprintf(out
, " %4d,", lemp
->errAction
);
4398 fprintf(out
, " %4d,", stp
->iDfltReduce
+ lemp
->minReduce
);
4400 if( j
==9 || i
==n
-1 ){
4401 fprintf(out
, "\n"); lineno
++;
4407 fprintf(out
, "};\n"); lineno
++;
4408 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4410 /* Generate the table of fallback tokens.
4412 if( lemp
->has_fallback
){
4413 int mx
= lemp
->nterminal
- 1;
4414 while( mx
>0 && lemp
->symbols
[mx
]->fallback
==0 ){ mx
--; }
4415 lemp
->tablesize
+= (mx
+1)*szCodeType
;
4416 for(i
=0; i
<=mx
; i
++){
4417 struct symbol
*p
= lemp
->symbols
[i
];
4418 if( p
->fallback
==0 ){
4419 fprintf(out
, " 0, /* %10s => nothing */\n", p
->name
);
4421 fprintf(out
, " %3d, /* %10s => %s */\n", p
->fallback
->index
,
4422 p
->name
, p
->fallback
->name
);
4427 tplt_xfer(lemp
->name
, in
, out
, &lineno
);
4429 /* Generate a table containing the symbolic name of every symbol
4431 for(i
=0; i
<lemp
->nsymbol
; i
++){
4432 lemon_sprintf(line
,"\"%s\",",lemp
->symbols
[i
]->name
);
4433 fprintf(out
," /* %4d */ \"%s\",\n",i
, lemp
->symbols
[i
]->name
); lineno
++;
4435 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4437 /* Generate a table containing a text string that describes every
4438 ** rule in the rule set of the grammar. This information is used
4439 ** when tracing REDUCE actions.
4441 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4442 assert( rp
->iRule
==i
);
4443 fprintf(out
," /* %3d */ \"", i
);
4444 writeRuleText(out
, rp
);
4445 fprintf(out
,"\",\n"); lineno
++;
4447 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4449 /* Generate code which executes every time a symbol is popped from
4450 ** the stack while processing errors or while destroying the parser.
4451 ** (In other words, generate the %destructor actions)
4453 if( lemp
->tokendest
){
4455 for(i
=0; i
<lemp
->nsymbol
; i
++){
4456 struct symbol
*sp
= lemp
->symbols
[i
];
4457 if( sp
==0 || sp
->type
!=TERMINAL
) continue;
4459 fprintf(out
, " /* TERMINAL Destructor */\n"); lineno
++;
4462 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4464 for(i
=0; i
<lemp
->nsymbol
&& lemp
->symbols
[i
]->type
!=TERMINAL
; i
++);
4465 if( i
<lemp
->nsymbol
){
4466 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4467 fprintf(out
," break;\n"); lineno
++;
4470 if( lemp
->vardest
){
4471 struct symbol
*dflt_sp
= 0;
4473 for(i
=0; i
<lemp
->nsymbol
; i
++){
4474 struct symbol
*sp
= lemp
->symbols
[i
];
4475 if( sp
==0 || sp
->type
==TERMINAL
||
4476 sp
->index
<=0 || sp
->destructor
!=0 ) continue;
4478 fprintf(out
, " /* Default NON-TERMINAL Destructor */\n");lineno
++;
4481 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4485 emit_destructor_code(out
,dflt_sp
,lemp
,&lineno
);
4487 fprintf(out
," break;\n"); lineno
++;
4489 for(i
=0; i
<lemp
->nsymbol
; i
++){
4490 struct symbol
*sp
= lemp
->symbols
[i
];
4491 if( sp
==0 || sp
->type
==TERMINAL
|| sp
->destructor
==0 ) continue;
4492 if( sp
->destLineno
<0 ) continue; /* Already emitted */
4493 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4495 /* Combine duplicate destructors into a single case */
4496 for(j
=i
+1; j
<lemp
->nsymbol
; j
++){
4497 struct symbol
*sp2
= lemp
->symbols
[j
];
4498 if( sp2
&& sp2
->type
!=TERMINAL
&& sp2
->destructor
4499 && sp2
->dtnum
==sp
->dtnum
4500 && strcmp(sp
->destructor
,sp2
->destructor
)==0 ){
4501 fprintf(out
," case %d: /* %s */\n",
4502 sp2
->index
, sp2
->name
); lineno
++;
4503 sp2
->destLineno
= -1; /* Avoid emitting this destructor again */
4507 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4508 fprintf(out
," break;\n"); lineno
++;
4510 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4512 /* Generate code which executes whenever the parser stack overflows */
4513 tplt_print(out
,lemp
,lemp
->overflow
,&lineno
);
4514 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4516 /* Generate the table of rule information
4518 ** Note: This code depends on the fact that rules are number
4519 ** sequentually beginning with 0.
4521 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4522 fprintf(out
," { %4d, %4d }, /* (%d) ",rp
->lhs
->index
,-rp
->nrhs
,i
);
4523 rule_print(out
, rp
);
4524 fprintf(out
," */\n"); lineno
++;
4526 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4528 /* Generate code which execution during each REDUCE action */
4530 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4531 i
+= translate_code(lemp
, rp
);
4534 fprintf(out
," YYMINORTYPE yylhsminor;\n"); lineno
++;
4536 /* First output rules other than the default: rule */
4537 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4538 struct rule
*rp2
; /* Other rules with the same action */
4539 if( rp
->codeEmitted
) continue;
4541 /* No C code actions, so this will be part of the "default:" rule */
4544 fprintf(out
," case %d: /* ", rp
->iRule
);
4545 writeRuleText(out
, rp
);
4546 fprintf(out
, " */\n"); lineno
++;
4547 for(rp2
=rp
->next
; rp2
; rp2
=rp2
->next
){
4548 if( rp2
->code
==rp
->code
&& rp2
->codePrefix
==rp
->codePrefix
4549 && rp2
->codeSuffix
==rp
->codeSuffix
){
4550 fprintf(out
," case %d: /* ", rp2
->iRule
);
4551 writeRuleText(out
, rp2
);
4552 fprintf(out
," */ yytestcase(yyruleno==%d);\n", rp2
->iRule
); lineno
++;
4553 rp2
->codeEmitted
= 1;
4556 emit_code(out
,rp
,lemp
,&lineno
);
4557 fprintf(out
," break;\n"); lineno
++;
4558 rp
->codeEmitted
= 1;
4560 /* Finally, output the default: rule. We choose as the default: all
4561 ** empty actions. */
4562 fprintf(out
," default:\n"); lineno
++;
4563 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4564 if( rp
->codeEmitted
) continue;
4565 assert( rp
->noCode
);
4566 fprintf(out
," /* (%d) ", rp
->iRule
);
4567 writeRuleText(out
, rp
);
4568 if( rp
->doesReduce
){
4569 fprintf(out
, " */ yytestcase(yyruleno==%d);\n", rp
->iRule
); lineno
++;
4571 fprintf(out
, " (OPTIMIZED OUT) */ assert(yyruleno!=%d);\n",
4572 rp
->iRule
); lineno
++;
4575 fprintf(out
," break;\n"); lineno
++;
4576 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4578 /* Generate code which executes if a parse fails */
4579 tplt_print(out
,lemp
,lemp
->failure
,&lineno
);
4580 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4582 /* Generate code which executes when a syntax error occurs */
4583 tplt_print(out
,lemp
,lemp
->error
,&lineno
);
4584 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4586 /* Generate code which executes when the parser accepts its input */
4587 tplt_print(out
,lemp
,lemp
->accept
,&lineno
);
4588 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4590 /* Append any addition code the user desires */
4591 tplt_print(out
,lemp
,lemp
->extracode
,&lineno
);
4598 /* Generate a header file for the parser */
4599 void ReportHeader(struct lemon
*lemp
)
4603 char line
[LINESIZE
];
4604 char pattern
[LINESIZE
];
4607 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
4609 in
= file_open(lemp
,".h","rb");
4612 for(i
=1; i
<lemp
->nterminal
&& fgets(line
,LINESIZE
,in
); i
++){
4613 lemon_sprintf(pattern
,"#define %s%-30s %3d\n",
4614 prefix
,lemp
->symbols
[i
]->name
,i
);
4615 if( strcmp(line
,pattern
) ) break;
4617 nextChar
= fgetc(in
);
4619 if( i
==lemp
->nterminal
&& nextChar
==EOF
){
4620 /* No change in the file. Don't rewrite it. */
4624 out
= file_open(lemp
,".h","wb");
4626 for(i
=1; i
<lemp
->nterminal
; i
++){
4627 fprintf(out
,"#define %s%-30s %3d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
4634 /* Reduce the size of the action tables, if possible, by making use
4637 ** In this version, we take the most frequent REDUCE action and make
4638 ** it the default. Except, there is no default if the wildcard token
4639 ** is a possible look-ahead.
4641 void CompressTables(struct lemon
*lemp
)
4644 struct action
*ap
, *ap2
, *nextap
;
4645 struct rule
*rp
, *rp2
, *rbest
;
4650 for(i
=0; i
<lemp
->nstate
; i
++){
4651 stp
= lemp
->sorted
[i
];
4656 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4657 if( ap
->type
==SHIFT
&& ap
->sp
==lemp
->wildcard
){
4660 if( ap
->type
!=REDUCE
) continue;
4662 if( rp
->lhsStart
) continue;
4663 if( rp
==rbest
) continue;
4665 for(ap2
=ap
->next
; ap2
; ap2
=ap2
->next
){
4666 if( ap2
->type
!=REDUCE
) continue;
4668 if( rp2
==rbest
) continue;
4677 /* Do not make a default if the number of rules to default
4678 ** is not at least 1 or if the wildcard token is a possible
4681 if( nbest
<1 || usesWildcard
) continue;
4684 /* Combine matching REDUCE actions into a single default */
4685 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4686 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) break;
4689 ap
->sp
= Symbol_new("{default}");
4690 for(ap
=ap
->next
; ap
; ap
=ap
->next
){
4691 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) ap
->type
= NOT_USED
;
4693 stp
->ap
= Action_sort(stp
->ap
);
4695 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4696 if( ap
->type
==SHIFT
) break;
4697 if( ap
->type
==REDUCE
&& ap
->x
.rp
!=rbest
) break;
4700 stp
->autoReduce
= 1;
4701 stp
->pDfltReduce
= rbest
;
4705 /* Make a second pass over all states and actions. Convert
4706 ** every action that is a SHIFT to an autoReduce state into
4707 ** a SHIFTREDUCE action.
4709 for(i
=0; i
<lemp
->nstate
; i
++){
4710 stp
= lemp
->sorted
[i
];
4711 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4712 struct state
*pNextState
;
4713 if( ap
->type
!=SHIFT
) continue;
4714 pNextState
= ap
->x
.stp
;
4715 if( pNextState
->autoReduce
&& pNextState
->pDfltReduce
!=0 ){
4716 ap
->type
= SHIFTREDUCE
;
4717 ap
->x
.rp
= pNextState
->pDfltReduce
;
4722 /* If a SHIFTREDUCE action specifies a rule that has a single RHS term
4723 ** (meaning that the SHIFTREDUCE will land back in the state where it
4724 ** started) and if there is no C-code associated with the reduce action,
4725 ** then we can go ahead and convert the action to be the same as the
4726 ** action for the RHS of the rule.
4728 for(i
=0; i
<lemp
->nstate
; i
++){
4729 stp
= lemp
->sorted
[i
];
4730 for(ap
=stp
->ap
; ap
; ap
=nextap
){
4732 if( ap
->type
!=SHIFTREDUCE
) continue;
4734 if( rp
->noCode
==0 ) continue;
4735 if( rp
->nrhs
!=1 ) continue;
4737 /* Only apply this optimization to non-terminals. It would be OK to
4738 ** apply it to terminal symbols too, but that makes the parser tables
4740 if( ap
->sp
->index
<lemp
->nterminal
) continue;
4742 /* If we reach this point, it means the optimization can be applied */
4744 for(ap2
=stp
->ap
; ap2
&& (ap2
==ap
|| ap2
->sp
!=rp
->lhs
); ap2
=ap2
->next
){}
4746 ap
->spOpt
= ap2
->sp
;
4747 ap
->type
= ap2
->type
;
4755 ** Compare two states for sorting purposes. The smaller state is the
4756 ** one with the most non-terminal actions. If they have the same number
4757 ** of non-terminal actions, then the smaller is the one with the most
4760 static int stateResortCompare(const void *a
, const void *b
){
4761 const struct state
*pA
= *(const struct state
**)a
;
4762 const struct state
*pB
= *(const struct state
**)b
;
4765 n
= pB
->nNtAct
- pA
->nNtAct
;
4767 n
= pB
->nTknAct
- pA
->nTknAct
;
4769 n
= pB
->statenum
- pA
->statenum
;
4778 ** Renumber and resort states so that states with fewer choices
4779 ** occur at the end. Except, keep state 0 as the first state.
4781 void ResortStates(struct lemon
*lemp
)
4787 for(i
=0; i
<lemp
->nstate
; i
++){
4788 stp
= lemp
->sorted
[i
];
4789 stp
->nTknAct
= stp
->nNtAct
= 0;
4790 stp
->iDfltReduce
= -1; /* Init dflt action to "syntax error" */
4791 stp
->iTknOfst
= NO_OFFSET
;
4792 stp
->iNtOfst
= NO_OFFSET
;
4793 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4794 int iAction
= compute_action(lemp
,ap
);
4796 if( ap
->sp
->index
<lemp
->nterminal
){
4798 }else if( ap
->sp
->index
<lemp
->nsymbol
){
4801 assert( stp
->autoReduce
==0 || stp
->pDfltReduce
==ap
->x
.rp
);
4802 stp
->iDfltReduce
= iAction
;
4807 qsort(&lemp
->sorted
[1], lemp
->nstate
-1, sizeof(lemp
->sorted
[0]),
4808 stateResortCompare
);
4809 for(i
=0; i
<lemp
->nstate
; i
++){
4810 lemp
->sorted
[i
]->statenum
= i
;
4812 lemp
->nxstate
= lemp
->nstate
;
4813 while( lemp
->nxstate
>1 && lemp
->sorted
[lemp
->nxstate
-1]->autoReduce
){
4819 /***************** From the file "set.c" ************************************/
4821 ** Set manipulation routines for the LEMON parser generator.
4824 static int size
= 0;
4826 /* Set the set size */
4832 /* Allocate a new set */
4835 s
= (char*)calloc( size
, 1);
4837 extern void memory_error();
4843 /* Deallocate a set */
4844 void SetFree(char *s
)
4849 /* Add a new element to the set. Return TRUE if the element was added
4850 ** and FALSE if it was already there. */
4851 int SetAdd(char *s
, int e
)
4854 assert( e
>=0 && e
<size
);
4860 /* Add every element of s2 to s1. Return TRUE if s1 changes. */
4861 int SetUnion(char *s1
, char *s2
)
4865 for(i
=0; i
<size
; i
++){
4866 if( s2
[i
]==0 ) continue;
4874 /********************** From the file "table.c" ****************************/
4876 ** All code in this file has been automatically generated
4877 ** from a specification in the file
4879 ** by the associative array code building program "aagen".
4880 ** Do not edit this file! Instead, edit the specification
4881 ** file, then rerun aagen.
4884 ** Code for processing tables in the LEMON parser generator.
4887 PRIVATE
unsigned strhash(const char *x
)
4890 while( *x
) h
= h
*13 + *(x
++);
4894 /* Works like strdup, sort of. Save a string in malloced memory, but
4895 ** keep strings in a table so that the same string is not in more
4898 const char *Strsafe(const char *y
)
4903 if( y
==0 ) return 0;
4904 z
= Strsafe_find(y
);
4905 if( z
==0 && (cpy
=(char *)malloc( lemonStrlen(y
)+1 ))!=0 ){
4906 lemon_strcpy(cpy
,y
);
4914 /* There is one instance of the following structure for each
4915 ** associative array of type "x1".
4918 int size
; /* The number of available slots. */
4919 /* Must be a power of 2 greater than or */
4921 int count
; /* Number of currently slots filled */
4922 struct s_x1node
*tbl
; /* The data stored here */
4923 struct s_x1node
**ht
; /* Hash table for lookups */
4926 /* There is one instance of this structure for every data element
4927 ** in an associative array of type "x1".
4929 typedef struct s_x1node
{
4930 const char *data
; /* The data */
4931 struct s_x1node
*next
; /* Next entry with the same hash */
4932 struct s_x1node
**from
; /* Previous link */
4935 /* There is only one instance of the array, which is the following */
4936 static struct s_x1
*x1a
;
4938 /* Allocate a new associative array */
4939 void Strsafe_init(void){
4941 x1a
= (struct s_x1
*)malloc( sizeof(struct s_x1
) );
4945 x1a
->tbl
= (x1node
*)calloc(1024, sizeof(x1node
) + sizeof(x1node
*));
4951 x1a
->ht
= (x1node
**)&(x1a
->tbl
[1024]);
4952 for(i
=0; i
<1024; i
++) x1a
->ht
[i
] = 0;
4956 /* Insert a new record into the array. Return TRUE if successful.
4957 ** Prior data with the same key is NOT overwritten */
4958 int Strsafe_insert(const char *data
)
4964 if( x1a
==0 ) return 0;
4966 h
= ph
& (x1a
->size
-1);
4969 if( strcmp(np
->data
,data
)==0 ){
4970 /* An existing entry with the same key is found. */
4971 /* Fail because overwrite is not allows. */
4976 if( x1a
->count
>=x1a
->size
){
4977 /* Need to make the hash table bigger */
4980 array
.size
= arrSize
= x1a
->size
*2;
4981 array
.count
= x1a
->count
;
4982 array
.tbl
= (x1node
*)calloc(arrSize
, sizeof(x1node
) + sizeof(x1node
*));
4983 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
4984 array
.ht
= (x1node
**)&(array
.tbl
[arrSize
]);
4985 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
4986 for(i
=0; i
<x1a
->count
; i
++){
4987 x1node
*oldnp
, *newnp
;
4988 oldnp
= &(x1a
->tbl
[i
]);
4989 h
= strhash(oldnp
->data
) & (arrSize
-1);
4990 newnp
= &(array
.tbl
[i
]);
4991 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4992 newnp
->next
= array
.ht
[h
];
4993 newnp
->data
= oldnp
->data
;
4994 newnp
->from
= &(array
.ht
[h
]);
4995 array
.ht
[h
] = newnp
;
5000 /* Insert the new data */
5001 h
= ph
& (x1a
->size
-1);
5002 np
= &(x1a
->tbl
[x1a
->count
++]);
5004 if( x1a
->ht
[h
] ) x1a
->ht
[h
]->from
= &(np
->next
);
5005 np
->next
= x1a
->ht
[h
];
5007 np
->from
= &(x1a
->ht
[h
]);
5011 /* Return a pointer to data assigned to the given key. Return NULL
5012 ** if no such key. */
5013 const char *Strsafe_find(const char *key
)
5018 if( x1a
==0 ) return 0;
5019 h
= strhash(key
) & (x1a
->size
-1);
5022 if( strcmp(np
->data
,key
)==0 ) break;
5025 return np
? np
->data
: 0;
5028 /* Return a pointer to the (terminal or nonterminal) symbol "x".
5029 ** Create a new symbol if this is the first time "x" has been seen.
5031 struct symbol
*Symbol_new(const char *x
)
5035 sp
= Symbol_find(x
);
5037 sp
= (struct symbol
*)calloc(1, sizeof(struct symbol
) );
5039 sp
->name
= Strsafe(x
);
5040 sp
->type
= ISUPPER(*x
) ? TERMINAL
: NONTERMINAL
;
5046 sp
->lambda
= LEMON_FALSE
;
5051 Symbol_insert(sp
,sp
->name
);
5057 /* Compare two symbols for sorting purposes. Return negative,
5058 ** zero, or positive if a is less then, equal to, or greater
5061 ** Symbols that begin with upper case letters (terminals or tokens)
5062 ** must sort before symbols that begin with lower case letters
5063 ** (non-terminals). And MULTITERMINAL symbols (created using the
5064 ** %token_class directive) must sort at the very end. Other than
5065 ** that, the order does not matter.
5067 ** We find experimentally that leaving the symbols in their original
5068 ** order (the order they appeared in the grammar file) gives the
5069 ** smallest parser tables in SQLite.
5071 int Symbolcmpp(const void *_a
, const void *_b
)
5073 const struct symbol
*a
= *(const struct symbol
**) _a
;
5074 const struct symbol
*b
= *(const struct symbol
**) _b
;
5075 int i1
= a
->type
==MULTITERMINAL
? 3 : a
->name
[0]>'Z' ? 2 : 1;
5076 int i2
= b
->type
==MULTITERMINAL
? 3 : b
->name
[0]>'Z' ? 2 : 1;
5077 return i1
==i2
? a
->index
- b
->index
: i1
- i2
;
5080 /* There is one instance of the following structure for each
5081 ** associative array of type "x2".
5084 int size
; /* The number of available slots. */
5085 /* Must be a power of 2 greater than or */
5087 int count
; /* Number of currently slots filled */
5088 struct s_x2node
*tbl
; /* The data stored here */
5089 struct s_x2node
**ht
; /* Hash table for lookups */
5092 /* There is one instance of this structure for every data element
5093 ** in an associative array of type "x2".
5095 typedef struct s_x2node
{
5096 struct symbol
*data
; /* The data */
5097 const char *key
; /* The key */
5098 struct s_x2node
*next
; /* Next entry with the same hash */
5099 struct s_x2node
**from
; /* Previous link */
5102 /* There is only one instance of the array, which is the following */
5103 static struct s_x2
*x2a
;
5105 /* Allocate a new associative array */
5106 void Symbol_init(void){
5108 x2a
= (struct s_x2
*)malloc( sizeof(struct s_x2
) );
5112 x2a
->tbl
= (x2node
*)calloc(128, sizeof(x2node
) + sizeof(x2node
*));
5118 x2a
->ht
= (x2node
**)&(x2a
->tbl
[128]);
5119 for(i
=0; i
<128; i
++) x2a
->ht
[i
] = 0;
5123 /* Insert a new record into the array. Return TRUE if successful.
5124 ** Prior data with the same key is NOT overwritten */
5125 int Symbol_insert(struct symbol
*data
, const char *key
)
5131 if( x2a
==0 ) return 0;
5133 h
= ph
& (x2a
->size
-1);
5136 if( strcmp(np
->key
,key
)==0 ){
5137 /* An existing entry with the same key is found. */
5138 /* Fail because overwrite is not allows. */
5143 if( x2a
->count
>=x2a
->size
){
5144 /* Need to make the hash table bigger */
5147 array
.size
= arrSize
= x2a
->size
*2;
5148 array
.count
= x2a
->count
;
5149 array
.tbl
= (x2node
*)calloc(arrSize
, sizeof(x2node
) + sizeof(x2node
*));
5150 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5151 array
.ht
= (x2node
**)&(array
.tbl
[arrSize
]);
5152 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5153 for(i
=0; i
<x2a
->count
; i
++){
5154 x2node
*oldnp
, *newnp
;
5155 oldnp
= &(x2a
->tbl
[i
]);
5156 h
= strhash(oldnp
->key
) & (arrSize
-1);
5157 newnp
= &(array
.tbl
[i
]);
5158 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5159 newnp
->next
= array
.ht
[h
];
5160 newnp
->key
= oldnp
->key
;
5161 newnp
->data
= oldnp
->data
;
5162 newnp
->from
= &(array
.ht
[h
]);
5163 array
.ht
[h
] = newnp
;
5168 /* Insert the new data */
5169 h
= ph
& (x2a
->size
-1);
5170 np
= &(x2a
->tbl
[x2a
->count
++]);
5173 if( x2a
->ht
[h
] ) x2a
->ht
[h
]->from
= &(np
->next
);
5174 np
->next
= x2a
->ht
[h
];
5176 np
->from
= &(x2a
->ht
[h
]);
5180 /* Return a pointer to data assigned to the given key. Return NULL
5181 ** if no such key. */
5182 struct symbol
*Symbol_find(const char *key
)
5187 if( x2a
==0 ) return 0;
5188 h
= strhash(key
) & (x2a
->size
-1);
5191 if( strcmp(np
->key
,key
)==0 ) break;
5194 return np
? np
->data
: 0;
5197 /* Return the n-th data. Return NULL if n is out of range. */
5198 struct symbol
*Symbol_Nth(int n
)
5200 struct symbol
*data
;
5201 if( x2a
&& n
>0 && n
<=x2a
->count
){
5202 data
= x2a
->tbl
[n
-1].data
;
5209 /* Return the size of the array */
5212 return x2a
? x2a
->count
: 0;
5215 /* Return an array of pointers to all data in the table.
5216 ** The array is obtained from malloc. Return NULL if memory allocation
5217 ** problems, or if the array is empty. */
5218 struct symbol
**Symbol_arrayof()
5220 struct symbol
**array
;
5222 if( x2a
==0 ) return 0;
5223 arrSize
= x2a
->count
;
5224 array
= (struct symbol
**)calloc(arrSize
, sizeof(struct symbol
*));
5226 for(i
=0; i
<arrSize
; i
++) array
[i
] = x2a
->tbl
[i
].data
;
5231 /* Compare two configurations */
5232 int Configcmp(const char *_a
,const char *_b
)
5234 const struct config
*a
= (struct config
*) _a
;
5235 const struct config
*b
= (struct config
*) _b
;
5237 x
= a
->rp
->index
- b
->rp
->index
;
5238 if( x
==0 ) x
= a
->dot
- b
->dot
;
5242 /* Compare two states */
5243 PRIVATE
int statecmp(struct config
*a
, struct config
*b
)
5246 for(rc
=0; rc
==0 && a
&& b
; a
=a
->bp
, b
=b
->bp
){
5247 rc
= a
->rp
->index
- b
->rp
->index
;
5248 if( rc
==0 ) rc
= a
->dot
- b
->dot
;
5258 PRIVATE
unsigned statehash(struct config
*a
)
5262 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
5268 /* Allocate a new state structure */
5269 struct state
*State_new()
5271 struct state
*newstate
;
5272 newstate
= (struct state
*)calloc(1, sizeof(struct state
) );
5273 MemoryCheck(newstate
);
5277 /* There is one instance of the following structure for each
5278 ** associative array of type "x3".
5281 int size
; /* The number of available slots. */
5282 /* Must be a power of 2 greater than or */
5284 int count
; /* Number of currently slots filled */
5285 struct s_x3node
*tbl
; /* The data stored here */
5286 struct s_x3node
**ht
; /* Hash table for lookups */
5289 /* There is one instance of this structure for every data element
5290 ** in an associative array of type "x3".
5292 typedef struct s_x3node
{
5293 struct state
*data
; /* The data */
5294 struct config
*key
; /* The key */
5295 struct s_x3node
*next
; /* Next entry with the same hash */
5296 struct s_x3node
**from
; /* Previous link */
5299 /* There is only one instance of the array, which is the following */
5300 static struct s_x3
*x3a
;
5302 /* Allocate a new associative array */
5303 void State_init(void){
5305 x3a
= (struct s_x3
*)malloc( sizeof(struct s_x3
) );
5309 x3a
->tbl
= (x3node
*)calloc(128, sizeof(x3node
) + sizeof(x3node
*));
5315 x3a
->ht
= (x3node
**)&(x3a
->tbl
[128]);
5316 for(i
=0; i
<128; i
++) x3a
->ht
[i
] = 0;
5320 /* Insert a new record into the array. Return TRUE if successful.
5321 ** Prior data with the same key is NOT overwritten */
5322 int State_insert(struct state
*data
, struct config
*key
)
5328 if( x3a
==0 ) return 0;
5329 ph
= statehash(key
);
5330 h
= ph
& (x3a
->size
-1);
5333 if( statecmp(np
->key
,key
)==0 ){
5334 /* An existing entry with the same key is found. */
5335 /* Fail because overwrite is not allows. */
5340 if( x3a
->count
>=x3a
->size
){
5341 /* Need to make the hash table bigger */
5344 array
.size
= arrSize
= x3a
->size
*2;
5345 array
.count
= x3a
->count
;
5346 array
.tbl
= (x3node
*)calloc(arrSize
, sizeof(x3node
) + sizeof(x3node
*));
5347 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5348 array
.ht
= (x3node
**)&(array
.tbl
[arrSize
]);
5349 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5350 for(i
=0; i
<x3a
->count
; i
++){
5351 x3node
*oldnp
, *newnp
;
5352 oldnp
= &(x3a
->tbl
[i
]);
5353 h
= statehash(oldnp
->key
) & (arrSize
-1);
5354 newnp
= &(array
.tbl
[i
]);
5355 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5356 newnp
->next
= array
.ht
[h
];
5357 newnp
->key
= oldnp
->key
;
5358 newnp
->data
= oldnp
->data
;
5359 newnp
->from
= &(array
.ht
[h
]);
5360 array
.ht
[h
] = newnp
;
5365 /* Insert the new data */
5366 h
= ph
& (x3a
->size
-1);
5367 np
= &(x3a
->tbl
[x3a
->count
++]);
5370 if( x3a
->ht
[h
] ) x3a
->ht
[h
]->from
= &(np
->next
);
5371 np
->next
= x3a
->ht
[h
];
5373 np
->from
= &(x3a
->ht
[h
]);
5377 /* Return a pointer to data assigned to the given key. Return NULL
5378 ** if no such key. */
5379 struct state
*State_find(struct config
*key
)
5384 if( x3a
==0 ) return 0;
5385 h
= statehash(key
) & (x3a
->size
-1);
5388 if( statecmp(np
->key
,key
)==0 ) break;
5391 return np
? np
->data
: 0;
5394 /* Return an array of pointers to all data in the table.
5395 ** The array is obtained from malloc. Return NULL if memory allocation
5396 ** problems, or if the array is empty. */
5397 struct state
**State_arrayof(void)
5399 struct state
**array
;
5401 if( x3a
==0 ) return 0;
5402 arrSize
= x3a
->count
;
5403 array
= (struct state
**)calloc(arrSize
, sizeof(struct state
*));
5405 for(i
=0; i
<arrSize
; i
++) array
[i
] = x3a
->tbl
[i
].data
;
5410 /* Hash a configuration */
5411 PRIVATE
unsigned confighash(struct config
*a
)
5414 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
5418 /* There is one instance of the following structure for each
5419 ** associative array of type "x4".
5422 int size
; /* The number of available slots. */
5423 /* Must be a power of 2 greater than or */
5425 int count
; /* Number of currently slots filled */
5426 struct s_x4node
*tbl
; /* The data stored here */
5427 struct s_x4node
**ht
; /* Hash table for lookups */
5430 /* There is one instance of this structure for every data element
5431 ** in an associative array of type "x4".
5433 typedef struct s_x4node
{
5434 struct config
*data
; /* The data */
5435 struct s_x4node
*next
; /* Next entry with the same hash */
5436 struct s_x4node
**from
; /* Previous link */
5439 /* There is only one instance of the array, which is the following */
5440 static struct s_x4
*x4a
;
5442 /* Allocate a new associative array */
5443 void Configtable_init(void){
5445 x4a
= (struct s_x4
*)malloc( sizeof(struct s_x4
) );
5449 x4a
->tbl
= (x4node
*)calloc(64, sizeof(x4node
) + sizeof(x4node
*));
5455 x4a
->ht
= (x4node
**)&(x4a
->tbl
[64]);
5456 for(i
=0; i
<64; i
++) x4a
->ht
[i
] = 0;
5460 /* Insert a new record into the array. Return TRUE if successful.
5461 ** Prior data with the same key is NOT overwritten */
5462 int Configtable_insert(struct config
*data
)
5468 if( x4a
==0 ) return 0;
5469 ph
= confighash(data
);
5470 h
= ph
& (x4a
->size
-1);
5473 if( Configcmp((const char *) np
->data
,(const char *) data
)==0 ){
5474 /* An existing entry with the same key is found. */
5475 /* Fail because overwrite is not allows. */
5480 if( x4a
->count
>=x4a
->size
){
5481 /* Need to make the hash table bigger */
5484 array
.size
= arrSize
= x4a
->size
*2;
5485 array
.count
= x4a
->count
;
5486 array
.tbl
= (x4node
*)calloc(arrSize
, sizeof(x4node
) + sizeof(x4node
*));
5487 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5488 array
.ht
= (x4node
**)&(array
.tbl
[arrSize
]);
5489 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5490 for(i
=0; i
<x4a
->count
; i
++){
5491 x4node
*oldnp
, *newnp
;
5492 oldnp
= &(x4a
->tbl
[i
]);
5493 h
= confighash(oldnp
->data
) & (arrSize
-1);
5494 newnp
= &(array
.tbl
[i
]);
5495 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5496 newnp
->next
= array
.ht
[h
];
5497 newnp
->data
= oldnp
->data
;
5498 newnp
->from
= &(array
.ht
[h
]);
5499 array
.ht
[h
] = newnp
;
5504 /* Insert the new data */
5505 h
= ph
& (x4a
->size
-1);
5506 np
= &(x4a
->tbl
[x4a
->count
++]);
5508 if( x4a
->ht
[h
] ) x4a
->ht
[h
]->from
= &(np
->next
);
5509 np
->next
= x4a
->ht
[h
];
5511 np
->from
= &(x4a
->ht
[h
]);
5515 /* Return a pointer to data assigned to the given key. Return NULL
5516 ** if no such key. */
5517 struct config
*Configtable_find(struct config
*key
)
5522 if( x4a
==0 ) return 0;
5523 h
= confighash(key
) & (x4a
->size
-1);
5526 if( Configcmp((const char *) np
->data
,(const char *) key
)==0 ) break;
5529 return np
? np
->data
: 0;
5532 /* Remove all data from the table. Pass each data to the function "f"
5533 ** as it is removed. ("f" may be null to avoid this step.) */
5534 void Configtable_clear(int(*f
)(struct config
*))
5537 if( x4a
==0 || x4a
->count
==0 ) return;
5538 if( f
) for(i
=0; i
<x4a
->count
; i
++) (*f
)(x4a
->tbl
[i
].data
);
5539 for(i
=0; i
<x4a
->size
; i
++) x4a
->ht
[i
] = 0;