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 extern void memory_error();
52 static int showPrecedenceConflict
= 0;
53 static char *msort(char*,char**,int(*)(const char*,const char*));
56 ** Compilers are getting increasingly pedantic about type conversions
57 ** as C evolves ever closer to Ada.... To work around the latest problems
58 ** we have to define the following variant of strlen().
60 #define lemonStrlen(X) ((int)strlen(X))
63 ** Compilers are starting to complain about the use of sprintf() and strcpy(),
64 ** saying they are unsafe. So we define our own versions of those routines too.
66 ** There are three routines here: lemon_sprintf(), lemon_vsprintf(), and
67 ** lemon_addtext(). The first two are replacements for sprintf() and vsprintf().
68 ** The third is a helper routine for vsnprintf() that adds texts to the end of a
69 ** buffer, making sure the buffer is always zero-terminated.
71 ** The string formatter is a minimal subset of stdlib sprintf() supporting only
72 ** a few simply conversions:
79 static void lemon_addtext(
80 char *zBuf
, /* The buffer to which text is added */
81 int *pnUsed
, /* Slots of the buffer used so far */
82 const char *zIn
, /* Text to add */
83 int nIn
, /* Bytes of text to add. -1 to use strlen() */
84 int iWidth
/* Field width. Negative to left justify */
86 if( nIn
<0 ) for(nIn
=0; zIn
[nIn
]; nIn
++){}
87 while( iWidth
>nIn
){ zBuf
[(*pnUsed
)++] = ' '; iWidth
--; }
89 memcpy(&zBuf
[*pnUsed
], zIn
, nIn
);
91 while( (-iWidth
)>nIn
){ zBuf
[(*pnUsed
)++] = ' '; iWidth
++; }
94 static int lemon_vsprintf(char *str
, const char *zFormat
, va_list ap
){
100 for(i
=j
=0; (c
= zFormat
[i
])!=0; i
++){
103 lemon_addtext(str
, &nUsed
, &zFormat
[j
], i
-j
, 0);
105 if( ISDIGIT(c
) || (c
=='-' && ISDIGIT(zFormat
[i
+1])) ){
107 while( ISDIGIT(zFormat
[i
]) ) iWidth
= iWidth
*10 + zFormat
[i
++] - '0';
108 if( c
=='-' ) iWidth
= -iWidth
;
112 int v
= va_arg(ap
, int);
114 lemon_addtext(str
, &nUsed
, "-", 1, iWidth
);
117 lemon_addtext(str
, &nUsed
, "0", 1, iWidth
);
122 zTemp
[sizeof(zTemp
)-k
] = (v
%10) + '0';
125 lemon_addtext(str
, &nUsed
, &zTemp
[sizeof(zTemp
)-k
], k
, iWidth
);
127 z
= va_arg(ap
, const char*);
128 lemon_addtext(str
, &nUsed
, z
, -1, iWidth
);
129 }else if( c
=='.' && memcmp(&zFormat
[i
], ".*s", 3)==0 ){
132 z
= va_arg(ap
, const char*);
133 lemon_addtext(str
, &nUsed
, z
, k
, iWidth
);
135 lemon_addtext(str
, &nUsed
, "%", 1, 0);
137 fprintf(stderr
, "illegal format\n");
143 lemon_addtext(str
, &nUsed
, &zFormat
[j
], i
-j
, 0);
146 static int lemon_sprintf(char *str
, const char *format
, ...){
149 va_start(ap
, format
);
150 rc
= lemon_vsprintf(str
, format
, ap
);
154 static void lemon_strcpy(char *dest
, const char *src
){
155 while( (*(dest
++) = *(src
++))!=0 ){}
157 static void lemon_strcat(char *dest
, const char *src
){
158 while( *dest
) dest
++;
159 lemon_strcpy(dest
, src
);
163 /* a few forward declarations... */
168 static struct action
*Action_new(void);
169 static struct action
*Action_sort(struct action
*);
171 /********** From the file "build.h" ************************************/
172 void FindRulePrecedences(struct lemon
*);
173 void FindFirstSets(struct lemon
*);
174 void FindStates(struct lemon
*);
175 void FindLinks(struct lemon
*);
176 void FindFollowSets(struct lemon
*);
177 void FindActions(struct lemon
*);
179 /********* From the file "configlist.h" *********************************/
180 void Configlist_init(void);
181 struct config
*Configlist_add(struct rule
*, int);
182 struct config
*Configlist_addbasis(struct rule
*, int);
183 void Configlist_closure(struct lemon
*);
184 void Configlist_sort(void);
185 void Configlist_sortbasis(void);
186 struct config
*Configlist_return(void);
187 struct config
*Configlist_basis(void);
188 void Configlist_eat(struct config
*);
189 void Configlist_reset(void);
191 /********* From the file "error.h" ***************************************/
192 void ErrorMsg(const char *, int,const char *, ...);
194 /****** From the file "option.h" ******************************************/
195 enum option_type
{ OPT_FLAG
=1, OPT_INT
, OPT_DBL
, OPT_STR
,
196 OPT_FFLAG
, OPT_FINT
, OPT_FDBL
, OPT_FSTR
};
198 enum option_type type
;
203 int OptInit(char**,struct s_options
*,FILE*);
209 /******** From the file "parse.h" *****************************************/
210 void Parse(struct lemon
*lemp
);
212 /********* From the file "plink.h" ***************************************/
213 struct plink
*Plink_new(void);
214 void Plink_add(struct plink
**, struct config
*);
215 void Plink_copy(struct plink
**, struct plink
*);
216 void Plink_delete(struct plink
*);
218 /********** From the file "report.h" *************************************/
219 void Reprint(struct lemon
*);
220 void ReportOutput(struct lemon
*);
221 void ReportTable(struct lemon
*, int, int);
222 void ReportHeader(struct lemon
*);
223 void CompressTables(struct lemon
*);
224 void ResortStates(struct lemon
*);
226 /********** From the file "set.h" ****************************************/
227 void SetSize(int); /* All sets will be of size N */
228 char *SetNew(void); /* A new set for element 0..N */
229 void SetFree(char*); /* Deallocate a set */
230 int SetAdd(char*,int); /* Add element to a set */
231 int SetUnion(char *,char *); /* A <- A U B, thru element N */
232 #define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
234 /********** From the file "struct.h" *************************************/
236 ** Principal data structures for the LEMON parser generator.
239 typedef enum {LEMON_FALSE
=0, LEMON_TRUE
} Boolean
;
241 /* Symbols (terminals and nonterminals) of the grammar are stored
242 ** in the following: */
255 const char *name
; /* Name of the symbol */
256 int index
; /* Index number for this symbol */
257 enum symbol_type type
; /* Symbols are all either TERMINALS or NTs */
258 struct rule
*rule
; /* Linked list of rules of this (if an NT) */
259 struct symbol
*fallback
; /* fallback token in case this token doesn't parse */
260 int prec
; /* Precedence if defined (-1 otherwise) */
261 enum e_assoc assoc
; /* Associativity if precedence is defined */
262 char *firstset
; /* First-set for all rules of this symbol */
263 Boolean lambda
; /* True if NT and can generate an empty string */
264 int useCnt
; /* Number of times used */
265 char *destructor
; /* Code which executes whenever this symbol is
266 ** popped from the stack during error processing */
267 int destLineno
; /* Line number for start of destructor. Set to
268 ** -1 for duplicate destructors. */
269 char *datatype
; /* The data type of information held by this
270 ** object. Only used if type==NONTERMINAL */
271 int dtnum
; /* The data type number. In the parser, the value
272 ** stack is a union. The .yy%d element of this
273 ** union is the correct data type for this object */
274 int bContent
; /* True if this symbol ever carries content - if
275 ** it is ever more than just syntax */
276 /* The following fields are used by MULTITERMINALs only */
277 int nsubsym
; /* Number of constituent symbols in the MULTI */
278 struct symbol
**subsym
; /* Array of constituent symbols */
281 /* Each production rule in the grammar is stored in the following
284 struct symbol
*lhs
; /* Left-hand side of the rule */
285 const char *lhsalias
; /* Alias for the LHS (NULL if none) */
286 int lhsStart
; /* True if left-hand side is the start symbol */
287 int ruleline
; /* Line number for the rule */
288 int nrhs
; /* Number of RHS symbols */
289 struct symbol
**rhs
; /* The RHS symbols */
290 const char **rhsalias
; /* An alias for each RHS symbol (NULL if none) */
291 int line
; /* Line number at which code begins */
292 const char *code
; /* The code executed when this rule is reduced */
293 const char *codePrefix
; /* Setup code before code[] above */
294 const char *codeSuffix
; /* Breakdown code after code[] above */
295 struct symbol
*precsym
; /* Precedence symbol for this rule */
296 int index
; /* An index number for this rule */
297 int iRule
; /* Rule number as used in the generated tables */
298 Boolean noCode
; /* True if this rule has no associated C code */
299 Boolean codeEmitted
; /* True if the code has been emitted already */
300 Boolean canReduce
; /* True if this rule is ever reduced */
301 Boolean doesReduce
; /* Reduce actions occur after optimization */
302 Boolean neverReduce
; /* Reduce is theoretically possible, but prevented
303 ** by actions or other outside implementation */
304 struct rule
*nextlhs
; /* Next rule with the same LHS */
305 struct rule
*next
; /* Next rule in the global list */
308 /* A configuration is a production rule of the grammar together with
309 ** a mark (dot) showing how much of that rule has been processed so far.
310 ** Configurations also contain a follow-set which is a list of terminal
311 ** symbols which are allowed to immediately follow the end of the rule.
312 ** Every configuration is recorded as an instance of the following: */
318 struct rule
*rp
; /* The rule upon which the configuration is based */
319 int dot
; /* The parse point */
320 char *fws
; /* Follow-set for this configuration only */
321 struct plink
*fplp
; /* Follow-set forward propagation links */
322 struct plink
*bplp
; /* Follow-set backwards propagation links */
323 struct state
*stp
; /* Pointer to state which contains this */
324 enum cfgstatus status
; /* used during followset and shift computations */
325 struct config
*next
; /* Next configuration in the state */
326 struct config
*bp
; /* The next basis configuration */
334 SSCONFLICT
, /* A shift/shift conflict */
335 SRCONFLICT
, /* Was a reduce, but part of a conflict */
336 RRCONFLICT
, /* Was a reduce, but part of a conflict */
337 SH_RESOLVED
, /* Was a shift. Precedence resolved conflict */
338 RD_RESOLVED
, /* Was reduce. Precedence resolved conflict */
339 NOT_USED
, /* Deleted by compression */
340 SHIFTREDUCE
/* Shift first, then reduce */
343 /* Every shift or reduce operation is stored as one of the following */
345 struct symbol
*sp
; /* The look-ahead symbol */
348 struct state
*stp
; /* The new state, if a shift */
349 struct rule
*rp
; /* The rule, if a reduce */
351 struct symbol
*spOpt
; /* SHIFTREDUCE optimization to this symbol */
352 struct action
*next
; /* Next action for this state */
353 struct action
*collide
; /* Next action with the same hash */
356 /* Each state of the generated parser's finite state machine
357 ** is encoded as an instance of the following structure. */
359 struct config
*bp
; /* The basis configurations for this state */
360 struct config
*cfp
; /* All configurations in this set */
361 int statenum
; /* Sequential number for this state */
362 struct action
*ap
; /* List of actions for this state */
363 int nTknAct
, nNtAct
; /* Number of actions on terminals and nonterminals */
364 int iTknOfst
, iNtOfst
; /* yy_action[] offset for terminals and nonterms */
365 int iDfltReduce
; /* Default action is to REDUCE by this rule */
366 struct rule
*pDfltReduce
;/* The default REDUCE rule. */
367 int autoReduce
; /* True if this is an auto-reduce state */
369 #define NO_OFFSET (-2147483647)
371 /* A followset propagation link indicates that the contents of one
372 ** configuration followset should be propagated to another whenever
373 ** the first changes. */
375 struct config
*cfp
; /* The configuration to which linked */
376 struct plink
*next
; /* The next propagate link */
379 /* The state vector for the entire parser generator is recorded as
380 ** follows. (LEMON uses no global variables and makes little use of
381 ** static variables. Fields in the following structure can be thought
382 ** of as begin global variables in the program.) */
384 struct state
**sorted
; /* Table of states sorted by state number */
385 struct rule
*rule
; /* List of all rules */
386 struct rule
*startRule
; /* First rule */
387 int nstate
; /* Number of states */
388 int nxstate
; /* nstate with tail degenerate states removed */
389 int nrule
; /* Number of rules */
390 int nruleWithAction
; /* Number of rules with actions */
391 int nsymbol
; /* Number of terminal and nonterminal symbols */
392 int nterminal
; /* Number of terminal symbols */
393 int minShiftReduce
; /* Minimum shift-reduce action value */
394 int errAction
; /* Error action value */
395 int accAction
; /* Accept action value */
396 int noAction
; /* No-op action value */
397 int minReduce
; /* Minimum reduce action */
398 int maxAction
; /* Maximum action value of any kind */
399 struct symbol
**symbols
; /* Sorted array of pointers to symbols */
400 int errorcnt
; /* Number of errors */
401 struct symbol
*errsym
; /* The error symbol */
402 struct symbol
*wildcard
; /* Token that matches anything */
403 char *name
; /* Name of the generated parser */
404 char *arg
; /* Declaration of the 3rd argument to parser */
405 char *ctx
; /* Declaration of 2nd argument to constructor */
406 char *tokentype
; /* Type of terminal symbols in the parser stack */
407 char *vartype
; /* The default type of non-terminal symbols */
408 char *start
; /* Name of the start symbol for the grammar */
409 char *stacksize
; /* Size of the parser stack */
410 char *include
; /* Code to put at the start of the C file */
411 char *error
; /* Code to execute when an error is seen */
412 char *overflow
; /* Code to execute on a stack overflow */
413 char *failure
; /* Code to execute on parser failure */
414 char *accept
; /* Code to execute when the parser excepts */
415 char *extracode
; /* Code appended to the generated file */
416 char *tokendest
; /* Code to execute to destroy token data */
417 char *vardest
; /* Code for the default non-terminal destructor */
418 char *filename
; /* Name of the input file */
419 char *outname
; /* Name of the current output file */
420 char *tokenprefix
; /* A prefix added to token names in the .h file */
421 char *reallocFunc
; /* Function to use to allocate stack space */
422 char *freeFunc
; /* Function to use to free stack space */
423 int nconflict
; /* Number of parsing conflicts */
424 int nactiontab
; /* Number of entries in the yy_action[] table */
425 int nlookaheadtab
; /* Number of entries in yy_lookahead[] */
426 int tablesize
; /* Total table size of all tables in bytes */
427 int basisflag
; /* Print only basis configurations */
428 int printPreprocessed
; /* Show preprocessor output on stdout */
429 int has_fallback
; /* True if any %fallback is seen in the grammar */
430 int nolinenosflag
; /* True if #line statements should not be printed */
431 int argc
; /* Number of command-line arguments */
432 char **argv
; /* Command-line arguments */
435 #define MemoryCheck(X) if((X)==0){ \
436 extern void memory_error(); \
440 /**************** From the file "table.h" *********************************/
442 ** All code in this file has been automatically generated
443 ** from a specification in the file
445 ** by the associative array code building program "aagen".
446 ** Do not edit this file! Instead, edit the specification
447 ** file, then rerun aagen.
450 ** Code for processing tables in the LEMON parser generator.
452 /* Routines for handling a strings */
454 const char *Strsafe(const char *);
456 void Strsafe_init(void);
457 int Strsafe_insert(const char *);
458 const char *Strsafe_find(const char *);
460 /* Routines for handling symbols of the grammar */
462 struct symbol
*Symbol_new(const char *);
463 int Symbolcmpp(const void *, const void *);
464 void Symbol_init(void);
465 int Symbol_insert(struct symbol
*, const char *);
466 struct symbol
*Symbol_find(const char *);
467 struct symbol
*Symbol_Nth(int);
468 int Symbol_count(void);
469 struct symbol
**Symbol_arrayof(void);
471 /* Routines to manage the state table */
473 int Configcmp(const char *, const char *);
474 struct state
*State_new(void);
475 void State_init(void);
476 int State_insert(struct state
*, struct config
*);
477 struct state
*State_find(struct config
*);
478 struct state
**State_arrayof(void);
480 /* Routines used for efficiency in Configlist_add */
482 void Configtable_init(void);
483 int Configtable_insert(struct config
*);
484 struct config
*Configtable_find(struct config
*);
485 void Configtable_clear(int(*)(struct config
*));
487 /****************** From the file "action.c" *******************************/
489 ** Routines processing parser actions in the LEMON parser generator.
492 /* Allocate a new parser action */
493 static struct action
*Action_new(void){
494 static struct action
*actionfreelist
= 0;
495 struct action
*newaction
;
497 if( actionfreelist
==0 ){
500 actionfreelist
= (struct action
*)calloc(amt
, sizeof(struct action
));
501 if( actionfreelist
==0 ){
502 fprintf(stderr
,"Unable to allocate memory for a new parser action.");
505 for(i
=0; i
<amt
-1; i
++) actionfreelist
[i
].next
= &actionfreelist
[i
+1];
506 actionfreelist
[amt
-1].next
= 0;
508 newaction
= actionfreelist
;
509 actionfreelist
= actionfreelist
->next
;
513 /* Compare two actions for sorting purposes. Return negative, zero, or
514 ** positive if the first action is less than, equal to, or greater than
517 static int actioncmp(
522 rc
= ap1
->sp
->index
- ap2
->sp
->index
;
524 rc
= (int)ap1
->type
- (int)ap2
->type
;
526 if( rc
==0 && (ap1
->type
==REDUCE
|| ap1
->type
==SHIFTREDUCE
) ){
527 rc
= ap1
->x
.rp
->index
- ap2
->x
.rp
->index
;
530 rc
= (int) (ap2
- ap1
);
535 /* Sort parser actions */
536 static struct action
*Action_sort(
539 ap
= (struct action
*)msort((char *)ap
,(char **)&ap
->next
,
540 (int(*)(const char*,const char*))actioncmp
);
550 struct action
*newaction
;
551 newaction
= Action_new();
552 newaction
->next
= *app
;
554 newaction
->type
= type
;
556 newaction
->spOpt
= 0;
558 newaction
->x
.stp
= (struct state
*)arg
;
560 newaction
->x
.rp
= (struct rule
*)arg
;
563 /********************** New code to implement the "acttab" module ***********/
565 ** This module implements routines use to construct the yy_action[] table.
569 ** The state of the yy_action table under construction is an instance of
570 ** the following structure.
572 ** The yy_action table maps the pair (state_number, lookahead) into an
573 ** action_number. The table is an array of integers pairs. The state_number
574 ** determines an initial offset into the yy_action array. The lookahead
575 ** value is then added to this initial offset to get an index X into the
576 ** yy_action array. If the aAction[X].lookahead equals the value of the
577 ** of the lookahead input, then the value of the action_number output is
578 ** aAction[X].action. If the lookaheads do not match then the
579 ** default action for the state_number is returned.
581 ** All actions associated with a single state_number are first entered
582 ** into aLookahead[] using multiple calls to acttab_action(). Then the
583 ** actions for that single state_number are placed into the aAction[]
584 ** array with a single call to acttab_insert(). The acttab_insert() call
585 ** also resets the aLookahead[] array in preparation for the next
588 struct lookahead_action
{
589 int lookahead
; /* Value of the lookahead token */
590 int action
; /* Action to take on the given lookahead */
592 typedef struct acttab acttab
;
594 int nAction
; /* Number of used slots in aAction[] */
595 int nActionAlloc
; /* Slots allocated for aAction[] */
596 struct lookahead_action
597 *aAction
, /* The yy_action[] table under construction */
598 *aLookahead
; /* A single new transaction set */
599 int mnLookahead
; /* Minimum aLookahead[].lookahead */
600 int mnAction
; /* Action associated with mnLookahead */
601 int mxLookahead
; /* Maximum aLookahead[].lookahead */
602 int nLookahead
; /* Used slots in aLookahead[] */
603 int nLookaheadAlloc
; /* Slots allocated in aLookahead[] */
604 int nterminal
; /* Number of terminal symbols */
605 int nsymbol
; /* total number of symbols */
608 /* Return the number of entries in the yy_action table */
609 #define acttab_lookahead_size(X) ((X)->nAction)
611 /* The value for the N-th entry in yy_action */
612 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
614 /* The value for the N-th entry in yy_lookahead */
615 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
617 /* Free all memory associated with the given acttab */
618 void acttab_free(acttab
*p
){
620 free( p
->aLookahead
);
624 /* Allocate a new acttab structure */
625 acttab
*acttab_alloc(int nsymbol
, int nterminal
){
626 acttab
*p
= (acttab
*) calloc( 1, sizeof(*p
) );
628 fprintf(stderr
,"Unable to allocate memory for a new acttab.");
631 memset(p
, 0, sizeof(*p
));
632 p
->nsymbol
= nsymbol
;
633 p
->nterminal
= nterminal
;
637 /* Add a new action to the current transaction set.
639 ** This routine is called once for each lookahead for a particular
642 void acttab_action(acttab
*p
, int lookahead
, int action
){
643 if( p
->nLookahead
>=p
->nLookaheadAlloc
){
644 p
->nLookaheadAlloc
+= 25;
645 p
->aLookahead
= (struct lookahead_action
*) realloc( p
->aLookahead
,
646 sizeof(p
->aLookahead
[0])*p
->nLookaheadAlloc
);
647 if( p
->aLookahead
==0 ){
648 fprintf(stderr
,"malloc failed\n");
652 if( p
->nLookahead
==0 ){
653 p
->mxLookahead
= lookahead
;
654 p
->mnLookahead
= lookahead
;
655 p
->mnAction
= action
;
657 if( p
->mxLookahead
<lookahead
) p
->mxLookahead
= lookahead
;
658 if( p
->mnLookahead
>lookahead
){
659 p
->mnLookahead
= lookahead
;
660 p
->mnAction
= action
;
663 p
->aLookahead
[p
->nLookahead
].lookahead
= lookahead
;
664 p
->aLookahead
[p
->nLookahead
].action
= action
;
669 ** Add the transaction set built up with prior calls to acttab_action()
670 ** into the current action table. Then reset the transaction set back
671 ** to an empty set in preparation for a new round of acttab_action() calls.
673 ** Return the offset into the action table of the new transaction.
675 ** If the makeItSafe parameter is true, then the offset is chosen so that
676 ** it is impossible to overread the yy_lookaside[] table regardless of
677 ** the lookaside token. This is done for the terminal symbols, as they
678 ** come from external inputs and can contain syntax errors. When makeItSafe
679 ** is false, there is more flexibility in selecting offsets, resulting in
680 ** a smaller table. For non-terminal symbols, which are never syntax errors,
681 ** makeItSafe can be false.
683 int acttab_insert(acttab
*p
, int makeItSafe
){
685 assert( p
->nLookahead
>0 );
687 /* Make sure we have enough space to hold the expanded action table
688 ** in the worst case. The worst case occurs if the transaction set
689 ** must be appended to the current action table
692 if( p
->nAction
+ n
>= p
->nActionAlloc
){
693 int oldAlloc
= p
->nActionAlloc
;
694 p
->nActionAlloc
= p
->nAction
+ n
+ p
->nActionAlloc
+ 20;
695 p
->aAction
= (struct lookahead_action
*) realloc( p
->aAction
,
696 sizeof(p
->aAction
[0])*p
->nActionAlloc
);
698 fprintf(stderr
,"malloc failed\n");
701 for(i
=oldAlloc
; i
<p
->nActionAlloc
; i
++){
702 p
->aAction
[i
].lookahead
= -1;
703 p
->aAction
[i
].action
= -1;
707 /* Scan the existing action table looking for an offset that is a
708 ** duplicate of the current transaction set. Fall out of the loop
709 ** if and when the duplicate is found.
711 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
713 end
= makeItSafe
? p
->mnLookahead
: 0;
714 for(i
=p
->nAction
-1; i
>=end
; i
--){
715 if( p
->aAction
[i
].lookahead
==p
->mnLookahead
){
716 /* All lookaheads and actions in the aLookahead[] transaction
717 ** must match against the candidate aAction[i] entry. */
718 if( p
->aAction
[i
].action
!=p
->mnAction
) continue;
719 for(j
=0; j
<p
->nLookahead
; j
++){
720 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
721 if( k
<0 || k
>=p
->nAction
) break;
722 if( p
->aLookahead
[j
].lookahead
!=p
->aAction
[k
].lookahead
) break;
723 if( p
->aLookahead
[j
].action
!=p
->aAction
[k
].action
) break;
725 if( j
<p
->nLookahead
) continue;
727 /* No possible lookahead value that is not in the aLookahead[]
728 ** transaction is allowed to match aAction[i] */
730 for(j
=0; j
<p
->nAction
; j
++){
731 if( p
->aAction
[j
].lookahead
<0 ) continue;
732 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) n
++;
734 if( n
==p
->nLookahead
){
735 break; /* An exact match is found at offset i */
740 /* If no existing offsets exactly match the current transaction, find an
741 ** an empty offset in the aAction[] table in which we can add the
742 ** aLookahead[] transaction.
745 /* Look for holes in the aAction[] table that fit the current
746 ** aLookahead[] transaction. Leave i set to the offset of the hole.
747 ** If no holes are found, i is left at p->nAction, which means the
748 ** transaction will be appended. */
749 i
= makeItSafe
? p
->mnLookahead
: 0;
750 for(; i
<p
->nActionAlloc
- p
->mxLookahead
; i
++){
751 if( p
->aAction
[i
].lookahead
<0 ){
752 for(j
=0; j
<p
->nLookahead
; j
++){
753 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
755 if( p
->aAction
[k
].lookahead
>=0 ) break;
757 if( j
<p
->nLookahead
) continue;
758 for(j
=0; j
<p
->nAction
; j
++){
759 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) break;
762 break; /* Fits in empty slots */
767 /* Insert transaction set at index i. */
770 for(j
=0; j
<p
->nLookahead
; j
++){
771 printf(" %d", p
->aLookahead
[j
].lookahead
);
773 printf(" inserted at %d\n", i
);
775 for(j
=0; j
<p
->nLookahead
; j
++){
776 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
777 p
->aAction
[k
] = p
->aLookahead
[j
];
778 if( k
>=p
->nAction
) p
->nAction
= k
+1;
780 if( makeItSafe
&& i
+p
->nterminal
>=p
->nAction
) p
->nAction
= i
+p
->nterminal
+1;
783 /* Return the offset that is added to the lookahead in order to get the
784 ** index into yy_action of the action */
785 return i
- p
->mnLookahead
;
789 ** Return the size of the action table without the trailing syntax error
792 int acttab_action_size(acttab
*p
){
794 while( n
>0 && p
->aAction
[n
-1].lookahead
<0 ){ n
--; }
798 /********************** From the file "build.c" *****************************/
800 ** Routines to construction the finite state machine for the LEMON
804 /* Find a precedence symbol of every rule in the grammar.
806 ** Those rules which have a precedence symbol coded in the input
807 ** grammar using the "[symbol]" construct will already have the
808 ** rp->precsym field filled. Other rules take as their precedence
809 ** symbol the first RHS symbol with a defined precedence. If there
810 ** are not RHS symbols with a defined precedence, the precedence
811 ** symbol field is left blank.
813 void FindRulePrecedences(struct lemon
*xp
)
816 for(rp
=xp
->rule
; rp
; rp
=rp
->next
){
817 if( rp
->precsym
==0 ){
819 for(i
=0; i
<rp
->nrhs
&& rp
->precsym
==0; i
++){
820 struct symbol
*sp
= rp
->rhs
[i
];
821 if( sp
->type
==MULTITERMINAL
){
822 for(j
=0; j
<sp
->nsubsym
; j
++){
823 if( sp
->subsym
[j
]->prec
>=0 ){
824 rp
->precsym
= sp
->subsym
[j
];
828 }else if( sp
->prec
>=0 ){
829 rp
->precsym
= rp
->rhs
[i
];
837 /* Find all nonterminals which will generate the empty string.
838 ** Then go back and compute the first sets of every nonterminal.
839 ** The first set is the set of all terminal symbols which can begin
840 ** a string generated by that nonterminal.
842 void FindFirstSets(struct lemon
*lemp
)
848 for(i
=0; i
<lemp
->nsymbol
; i
++){
849 lemp
->symbols
[i
]->lambda
= LEMON_FALSE
;
851 for(i
=lemp
->nterminal
; i
<lemp
->nsymbol
; i
++){
852 lemp
->symbols
[i
]->firstset
= SetNew();
855 /* First compute all lambdas */
858 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
859 if( rp
->lhs
->lambda
) continue;
860 for(i
=0; i
<rp
->nrhs
; i
++){
861 struct symbol
*sp
= rp
->rhs
[i
];
862 assert( sp
->type
==NONTERMINAL
|| sp
->lambda
==LEMON_FALSE
);
863 if( sp
->lambda
==LEMON_FALSE
) break;
866 rp
->lhs
->lambda
= LEMON_TRUE
;
872 /* Now compute all first sets */
874 struct symbol
*s1
, *s2
;
876 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
878 for(i
=0; i
<rp
->nrhs
; i
++){
880 if( s2
->type
==TERMINAL
){
881 progress
+= SetAdd(s1
->firstset
,s2
->index
);
883 }else if( s2
->type
==MULTITERMINAL
){
884 for(j
=0; j
<s2
->nsubsym
; j
++){
885 progress
+= SetAdd(s1
->firstset
,s2
->subsym
[j
]->index
);
889 if( s1
->lambda
==LEMON_FALSE
) break;
891 progress
+= SetUnion(s1
->firstset
,s2
->firstset
);
892 if( s2
->lambda
==LEMON_FALSE
) break;
900 /* Compute all LR(0) states for the grammar. Links
901 ** are added to between some states so that the LR(1) follow sets
902 ** can be computed later.
904 PRIVATE
struct state
*getstate(struct lemon
*); /* forward reference */
905 void FindStates(struct lemon
*lemp
)
912 /* Find the start symbol */
914 sp
= Symbol_find(lemp
->start
);
916 ErrorMsg(lemp
->filename
,0,
917 "The specified start symbol \"%s\" is not "
918 "in a nonterminal of the grammar. \"%s\" will be used as the start "
919 "symbol instead.",lemp
->start
,lemp
->startRule
->lhs
->name
);
921 sp
= lemp
->startRule
->lhs
;
923 }else if( lemp
->startRule
){
924 sp
= lemp
->startRule
->lhs
;
926 ErrorMsg(lemp
->filename
,0,"Internal error - no start rule\n");
930 /* Make sure the start symbol doesn't occur on the right-hand side of
931 ** any rule. Report an error if it does. (YACC would generate a new
932 ** start symbol in this case.) */
933 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
935 for(i
=0; i
<rp
->nrhs
; i
++){
936 if( rp
->rhs
[i
]==sp
){ /* FIX ME: Deal with multiterminals */
937 ErrorMsg(lemp
->filename
,0,
938 "The start symbol \"%s\" occurs on the "
939 "right-hand side of a rule. This will result in a parser which "
940 "does not work properly.",sp
->name
);
946 /* The basis configuration set for the first state
947 ** is all rules which have the start symbol as their
949 for(rp
=sp
->rule
; rp
; rp
=rp
->nextlhs
){
950 struct config
*newcfp
;
952 newcfp
= Configlist_addbasis(rp
,0);
953 SetAdd(newcfp
->fws
,0);
956 /* Compute the first state. All other states will be
957 ** computed automatically during the computation of the first one.
958 ** The returned pointer to the first state is not used. */
959 (void)getstate(lemp
);
963 /* Return a pointer to a state which is described by the configuration
964 ** list which has been built from calls to Configlist_add.
966 PRIVATE
void buildshifts(struct lemon
*, struct state
*); /* Forwd ref */
967 PRIVATE
struct state
*getstate(struct lemon
*lemp
)
969 struct config
*cfp
, *bp
;
972 /* Extract the sorted basis of the new state. The basis was constructed
973 ** by prior calls to "Configlist_addbasis()". */
974 Configlist_sortbasis();
975 bp
= Configlist_basis();
977 /* Get a state with the same basis */
978 stp
= State_find(bp
);
980 /* A state with the same basis already exists! Copy all the follow-set
981 ** propagation links from the state under construction into the
982 ** preexisting state, then return a pointer to the preexisting state */
983 struct config
*x
, *y
;
984 for(x
=bp
, y
=stp
->bp
; x
&& y
; x
=x
->bp
, y
=y
->bp
){
985 Plink_copy(&y
->bplp
,x
->bplp
);
986 Plink_delete(x
->fplp
);
987 x
->fplp
= x
->bplp
= 0;
989 cfp
= Configlist_return();
992 /* This really is a new state. Construct all the details */
993 Configlist_closure(lemp
); /* Compute the configuration closure */
994 Configlist_sort(); /* Sort the configuration closure */
995 cfp
= Configlist_return(); /* Get a pointer to the config list */
996 stp
= State_new(); /* A new state structure */
998 stp
->bp
= bp
; /* Remember the configuration basis */
999 stp
->cfp
= cfp
; /* Remember the configuration closure */
1000 stp
->statenum
= lemp
->nstate
++; /* Every state gets a sequence number */
1001 stp
->ap
= 0; /* No actions, yet. */
1002 State_insert(stp
,stp
->bp
); /* Add to the state table */
1003 buildshifts(lemp
,stp
); /* Recursively compute successor states */
1009 ** Return true if two symbols are the same.
1011 int same_symbol(struct symbol
*a
, struct symbol
*b
)
1014 if( a
==b
) return 1;
1015 if( a
->type
!=MULTITERMINAL
) return 0;
1016 if( b
->type
!=MULTITERMINAL
) return 0;
1017 if( a
->nsubsym
!=b
->nsubsym
) return 0;
1018 for(i
=0; i
<a
->nsubsym
; i
++){
1019 if( a
->subsym
[i
]!=b
->subsym
[i
] ) return 0;
1024 /* Construct all successor states to the given state. A "successor"
1025 ** state is any state which can be reached by a shift action.
1027 PRIVATE
void buildshifts(struct lemon
*lemp
, struct state
*stp
)
1029 struct config
*cfp
; /* For looping thru the config closure of "stp" */
1030 struct config
*bcfp
; /* For the inner loop on config closure of "stp" */
1031 struct config
*newcfg
; /* */
1032 struct symbol
*sp
; /* Symbol following the dot in configuration "cfp" */
1033 struct symbol
*bsp
; /* Symbol following the dot in configuration "bcfp" */
1034 struct state
*newstp
; /* A pointer to a successor state */
1036 /* Each configuration becomes complete after it contributes to a successor
1037 ** state. Initially, all configurations are incomplete */
1038 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
) cfp
->status
= INCOMPLETE
;
1040 /* Loop through all configurations of the state "stp" */
1041 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1042 if( cfp
->status
==COMPLETE
) continue; /* Already used by inner loop */
1043 if( cfp
->dot
>=cfp
->rp
->nrhs
) continue; /* Can't shift this config */
1044 Configlist_reset(); /* Reset the new config set */
1045 sp
= cfp
->rp
->rhs
[cfp
->dot
]; /* Symbol after the dot */
1047 /* For every configuration in the state "stp" which has the symbol "sp"
1048 ** following its dot, add the same configuration to the basis set under
1049 ** construction but with the dot shifted one symbol to the right. */
1050 for(bcfp
=cfp
; bcfp
; bcfp
=bcfp
->next
){
1051 if( bcfp
->status
==COMPLETE
) continue; /* Already used */
1052 if( bcfp
->dot
>=bcfp
->rp
->nrhs
) continue; /* Can't shift this one */
1053 bsp
= bcfp
->rp
->rhs
[bcfp
->dot
]; /* Get symbol after dot */
1054 if( !same_symbol(bsp
,sp
) ) continue; /* Must be same as for "cfp" */
1055 bcfp
->status
= COMPLETE
; /* Mark this config as used */
1056 newcfg
= Configlist_addbasis(bcfp
->rp
,bcfp
->dot
+1);
1057 Plink_add(&newcfg
->bplp
,bcfp
);
1060 /* Get a pointer to the state described by the basis configuration set
1061 ** constructed in the preceding loop */
1062 newstp
= getstate(lemp
);
1064 /* The state "newstp" is reached from the state "stp" by a shift action
1065 ** on the symbol "sp" */
1066 if( sp
->type
==MULTITERMINAL
){
1068 for(i
=0; i
<sp
->nsubsym
; i
++){
1069 Action_add(&stp
->ap
,SHIFT
,sp
->subsym
[i
],(char*)newstp
);
1072 Action_add(&stp
->ap
,SHIFT
,sp
,(char *)newstp
);
1078 ** Construct the propagation links
1080 void FindLinks(struct lemon
*lemp
)
1083 struct config
*cfp
, *other
;
1087 /* Housekeeping detail:
1088 ** Add to every propagate link a pointer back to the state to
1089 ** which the link is attached. */
1090 for(i
=0; i
<lemp
->nstate
; i
++){
1091 stp
= lemp
->sorted
[i
];
1092 for(cfp
=stp
?stp
->cfp
:0; cfp
; cfp
=cfp
->next
){
1097 /* Convert all backlinks into forward links. Only the forward
1098 ** links are used in the follow-set computation. */
1099 for(i
=0; i
<lemp
->nstate
; i
++){
1100 stp
= lemp
->sorted
[i
];
1101 for(cfp
=stp
?stp
->cfp
:0; cfp
; cfp
=cfp
->next
){
1102 for(plp
=cfp
->bplp
; plp
; plp
=plp
->next
){
1104 Plink_add(&other
->fplp
,cfp
);
1110 /* Compute all followsets.
1112 ** A followset is the set of all symbols which can come immediately
1113 ** after a configuration.
1115 void FindFollowSets(struct lemon
*lemp
)
1123 for(i
=0; i
<lemp
->nstate
; i
++){
1124 assert( lemp
->sorted
[i
]!=0 );
1125 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1126 cfp
->status
= INCOMPLETE
;
1132 for(i
=0; i
<lemp
->nstate
; i
++){
1133 assert( lemp
->sorted
[i
]!=0 );
1134 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1135 if( cfp
->status
==COMPLETE
) continue;
1136 for(plp
=cfp
->fplp
; plp
; plp
=plp
->next
){
1137 change
= SetUnion(plp
->cfp
->fws
,cfp
->fws
);
1139 plp
->cfp
->status
= INCOMPLETE
;
1143 cfp
->status
= COMPLETE
;
1149 static int resolve_conflict(struct action
*,struct action
*);
1151 /* Compute the reduce actions, and resolve conflicts.
1153 void FindActions(struct lemon
*lemp
)
1161 /* Add all of the reduce actions
1162 ** A reduce action is added for each element of the followset of
1163 ** a configuration which has its dot at the extreme right.
1165 for(i
=0; i
<lemp
->nstate
; i
++){ /* Loop over all states */
1166 stp
= lemp
->sorted
[i
];
1167 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){ /* Loop over all configurations */
1168 if( cfp
->rp
->nrhs
==cfp
->dot
){ /* Is dot at extreme right? */
1169 for(j
=0; j
<lemp
->nterminal
; j
++){
1170 if( SetFind(cfp
->fws
,j
) ){
1171 /* Add a reduce action to the state "stp" which will reduce by the
1172 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
1173 Action_add(&stp
->ap
,REDUCE
,lemp
->symbols
[j
],(char *)cfp
->rp
);
1180 /* Add the accepting token */
1182 sp
= Symbol_find(lemp
->start
);
1184 if( lemp
->startRule
==0 ){
1185 fprintf(stderr
, "internal error on source line %d: no start rule\n",
1189 sp
= lemp
->startRule
->lhs
;
1192 sp
= lemp
->startRule
->lhs
;
1194 /* Add to the first state (which is always the starting state of the
1195 ** finite state machine) an action to ACCEPT if the lookahead is the
1196 ** start nonterminal. */
1197 Action_add(&lemp
->sorted
[0]->ap
,ACCEPT
,sp
,0);
1199 /* Resolve conflicts */
1200 for(i
=0; i
<lemp
->nstate
; i
++){
1201 struct action
*ap
, *nap
;
1202 stp
= lemp
->sorted
[i
];
1203 /* assert( stp->ap ); */
1204 stp
->ap
= Action_sort(stp
->ap
);
1205 for(ap
=stp
->ap
; ap
&& ap
->next
; ap
=ap
->next
){
1206 for(nap
=ap
->next
; nap
&& nap
->sp
==ap
->sp
; nap
=nap
->next
){
1207 /* The two actions "ap" and "nap" have the same lookahead.
1208 ** Figure out which one should be used */
1209 lemp
->nconflict
+= resolve_conflict(ap
,nap
);
1214 /* Report an error for each rule that can never be reduced. */
1215 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->canReduce
= LEMON_FALSE
;
1216 for(i
=0; i
<lemp
->nstate
; i
++){
1218 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
1219 if( ap
->type
==REDUCE
) ap
->x
.rp
->canReduce
= LEMON_TRUE
;
1222 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
1223 if( rp
->canReduce
) continue;
1224 ErrorMsg(lemp
->filename
,rp
->ruleline
,"This rule can not be reduced.\n");
1229 /* Resolve a conflict between the two given actions. If the
1230 ** conflict can't be resolved, return non-zero.
1233 ** To resolve a conflict, first look to see if either action
1234 ** is on an error rule. In that case, take the action which
1235 ** is not associated with the error rule. If neither or both
1236 ** actions are associated with an error rule, then try to
1237 ** use precedence to resolve the conflict.
1239 ** If either action is a SHIFT, then it must be apx. This
1240 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1242 static int resolve_conflict(
1246 struct symbol
*spx
, *spy
;
1248 assert( apx
->sp
==apy
->sp
); /* Otherwise there would be no conflict */
1249 if( apx
->type
==SHIFT
&& apy
->type
==SHIFT
){
1250 apy
->type
= SSCONFLICT
;
1253 if( apx
->type
==SHIFT
&& apy
->type
==REDUCE
){
1255 spy
= apy
->x
.rp
->precsym
;
1256 if( spy
==0 || spx
->prec
<0 || spy
->prec
<0 ){
1257 /* Not enough precedence information. */
1258 apy
->type
= SRCONFLICT
;
1260 }else if( spx
->prec
>spy
->prec
){ /* higher precedence wins */
1261 apy
->type
= RD_RESOLVED
;
1262 }else if( spx
->prec
<spy
->prec
){
1263 apx
->type
= SH_RESOLVED
;
1264 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==RIGHT
){ /* Use operator */
1265 apy
->type
= RD_RESOLVED
; /* associativity */
1266 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==LEFT
){ /* to break tie */
1267 apx
->type
= SH_RESOLVED
;
1269 assert( spx
->prec
==spy
->prec
&& spx
->assoc
==NONE
);
1272 }else if( apx
->type
==REDUCE
&& apy
->type
==REDUCE
){
1273 spx
= apx
->x
.rp
->precsym
;
1274 spy
= apy
->x
.rp
->precsym
;
1275 if( spx
==0 || spy
==0 || spx
->prec
<0 ||
1276 spy
->prec
<0 || spx
->prec
==spy
->prec
){
1277 apy
->type
= RRCONFLICT
;
1279 }else if( spx
->prec
>spy
->prec
){
1280 apy
->type
= RD_RESOLVED
;
1281 }else if( spx
->prec
<spy
->prec
){
1282 apx
->type
= RD_RESOLVED
;
1286 apx
->type
==SH_RESOLVED
||
1287 apx
->type
==RD_RESOLVED
||
1288 apx
->type
==SSCONFLICT
||
1289 apx
->type
==SRCONFLICT
||
1290 apx
->type
==RRCONFLICT
||
1291 apy
->type
==SH_RESOLVED
||
1292 apy
->type
==RD_RESOLVED
||
1293 apy
->type
==SSCONFLICT
||
1294 apy
->type
==SRCONFLICT
||
1295 apy
->type
==RRCONFLICT
1297 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1298 ** REDUCEs on the list. If we reach this point it must be because
1299 ** the parser conflict had already been resolved. */
1303 /********************* From the file "configlist.c" *************************/
1305 ** Routines to processing a configuration list and building a state
1306 ** in the LEMON parser generator.
1309 static struct config
*freelist
= 0; /* List of free configurations */
1310 static struct config
*current
= 0; /* Top of list of configurations */
1311 static struct config
**currentend
= 0; /* Last on list of configs */
1312 static struct config
*basis
= 0; /* Top of list of basis configs */
1313 static struct config
**basisend
= 0; /* End of list of basis configs */
1315 /* Return a pointer to a new configuration */
1316 PRIVATE
struct config
*newconfig(void){
1317 return (struct config
*)calloc(1, sizeof(struct config
));
1320 /* The configuration "old" is no longer used */
1321 PRIVATE
void deleteconfig(struct config
*old
)
1323 old
->next
= freelist
;
1327 /* Initialized the configuration list builder */
1328 void Configlist_init(void){
1330 currentend
= ¤t
;
1337 /* Initialized the configuration list builder */
1338 void Configlist_reset(void){
1340 currentend
= ¤t
;
1343 Configtable_clear(0);
1347 /* Add another configuration to the configuration list */
1348 struct config
*Configlist_add(
1349 struct rule
*rp
, /* The rule */
1350 int dot
/* Index into the RHS of the rule where the dot goes */
1352 struct config
*cfp
, model
;
1354 assert( currentend
!=0 );
1357 cfp
= Configtable_find(&model
);
1362 cfp
->fws
= SetNew();
1364 cfp
->fplp
= cfp
->bplp
= 0;
1368 currentend
= &cfp
->next
;
1369 Configtable_insert(cfp
);
1374 /* Add a basis configuration to the configuration list */
1375 struct config
*Configlist_addbasis(struct rule
*rp
, int dot
)
1377 struct config
*cfp
, model
;
1379 assert( basisend
!=0 );
1380 assert( currentend
!=0 );
1383 cfp
= Configtable_find(&model
);
1388 cfp
->fws
= SetNew();
1390 cfp
->fplp
= cfp
->bplp
= 0;
1394 currentend
= &cfp
->next
;
1396 basisend
= &cfp
->bp
;
1397 Configtable_insert(cfp
);
1402 /* Compute the closure of the configuration list */
1403 void Configlist_closure(struct lemon
*lemp
)
1405 struct config
*cfp
, *newcfp
;
1406 struct rule
*rp
, *newrp
;
1407 struct symbol
*sp
, *xsp
;
1410 assert( currentend
!=0 );
1411 for(cfp
=current
; cfp
; cfp
=cfp
->next
){
1414 if( dot
>=rp
->nrhs
) continue;
1416 if( sp
->type
==NONTERMINAL
){
1417 if( sp
->rule
==0 && sp
!=lemp
->errsym
){
1418 ErrorMsg(lemp
->filename
,rp
->line
,"Nonterminal \"%s\" has no rules.",
1422 for(newrp
=sp
->rule
; newrp
; newrp
=newrp
->nextlhs
){
1423 newcfp
= Configlist_add(newrp
,0);
1424 for(i
=dot
+1; i
<rp
->nrhs
; i
++){
1426 if( xsp
->type
==TERMINAL
){
1427 SetAdd(newcfp
->fws
,xsp
->index
);
1429 }else if( xsp
->type
==MULTITERMINAL
){
1431 for(k
=0; k
<xsp
->nsubsym
; k
++){
1432 SetAdd(newcfp
->fws
, xsp
->subsym
[k
]->index
);
1436 SetUnion(newcfp
->fws
,xsp
->firstset
);
1437 if( xsp
->lambda
==LEMON_FALSE
) break;
1440 if( i
==rp
->nrhs
) Plink_add(&cfp
->fplp
,newcfp
);
1447 /* Sort the configuration list */
1448 void Configlist_sort(void){
1449 current
= (struct config
*)msort((char*)current
,(char**)&(current
->next
),
1455 /* Sort the basis configuration list */
1456 void Configlist_sortbasis(void){
1457 basis
= (struct config
*)msort((char*)current
,(char**)&(current
->bp
),
1463 /* Return a pointer to the head of the configuration list and
1464 ** reset the list */
1465 struct config
*Configlist_return(void){
1473 /* Return a pointer to the head of the configuration list and
1474 ** reset the list */
1475 struct config
*Configlist_basis(void){
1483 /* Free all elements of the given configuration list */
1484 void Configlist_eat(struct config
*cfp
)
1486 struct config
*nextcfp
;
1487 for(; cfp
; cfp
=nextcfp
){
1488 nextcfp
= cfp
->next
;
1489 assert( cfp
->fplp
==0 );
1490 assert( cfp
->bplp
==0 );
1491 if( cfp
->fws
) SetFree(cfp
->fws
);
1496 /***************** From the file "error.c" *********************************/
1498 ** Code for printing error message.
1501 void ErrorMsg(const char *filename
, int lineno
, const char *format
, ...){
1503 fprintf(stderr
, "%s:%d: ", filename
, lineno
);
1504 va_start(ap
, format
);
1505 vfprintf(stderr
,format
,ap
);
1507 fprintf(stderr
, "\n");
1509 /**************** From the file "main.c" ************************************/
1511 ** Main program file for the LEMON parser generator.
1514 /* Report an out-of-memory condition and abort. This function
1515 ** is used mostly by the "MemoryCheck" macro in struct.h
1517 void memory_error(void){
1518 fprintf(stderr
,"Out of memory. Aborting...\n");
1522 static int nDefine
= 0; /* Number of -D options on the command line */
1523 static int nDefineUsed
= 0; /* Number of -D options actually used */
1524 static char **azDefine
= 0; /* Name of the -D macros */
1525 static char *bDefineUsed
= 0; /* True for every -D macro actually used */
1527 /* This routine is called with the argument to each -D command-line option.
1528 ** Add the macro defined to the azDefine array.
1530 static void handle_D_option(char *z
){
1533 azDefine
= (char **) realloc(azDefine
, sizeof(azDefine
[0])*nDefine
);
1535 fprintf(stderr
,"out of memory\n");
1538 bDefineUsed
= (char*)realloc(bDefineUsed
, nDefine
);
1539 if( bDefineUsed
==0 ){
1540 fprintf(stderr
,"out of memory\n");
1543 bDefineUsed
[nDefine
-1] = 0;
1544 paz
= &azDefine
[nDefine
-1];
1545 *paz
= (char *) malloc( lemonStrlen(z
)+1 );
1547 fprintf(stderr
,"out of memory\n");
1550 lemon_strcpy(*paz
, z
);
1551 for(z
=*paz
; *z
&& *z
!='='; z
++){}
1555 /* Rember the name of the output directory
1557 static char *outputDir
= NULL
;
1558 static void handle_d_option(char *z
){
1559 outputDir
= (char *) malloc( lemonStrlen(z
)+1 );
1561 fprintf(stderr
,"out of memory\n");
1564 lemon_strcpy(outputDir
, z
);
1567 static char *user_templatename
= NULL
;
1568 static void handle_T_option(char *z
){
1569 user_templatename
= (char *) malloc( lemonStrlen(z
)+1 );
1570 if( user_templatename
==0 ){
1573 lemon_strcpy(user_templatename
, z
);
1576 /* Merge together to lists of rules ordered by rule.iRule */
1577 static struct rule
*Rule_merge(struct rule
*pA
, struct rule
*pB
){
1578 struct rule
*pFirst
= 0;
1579 struct rule
**ppPrev
= &pFirst
;
1581 if( pA
->iRule
<pB
->iRule
){
1600 ** Sort a list of rules in order of increasing iRule value
1602 static struct rule
*Rule_sort(struct rule
*rp
){
1606 memset(x
, 0, sizeof(x
));
1610 for(i
=0; i
<sizeof(x
)/sizeof(x
[0])-1 && x
[i
]; i
++){
1611 rp
= Rule_merge(x
[i
], rp
);
1618 for(i
=0; i
<sizeof(x
)/sizeof(x
[0]); i
++){
1619 rp
= Rule_merge(x
[i
], rp
);
1624 /* forward reference */
1625 static const char *minimum_size_type(int lwr
, int upr
, int *pnByte
);
1627 /* Print a single line of the "Parser Stats" output
1629 static void stats_line(const char *zLabel
, int iValue
){
1630 int nLabel
= lemonStrlen(zLabel
);
1631 printf(" %s%.*s %5d\n", zLabel
,
1632 35-nLabel
, "................................",
1636 /* The main program. Parse the command line and do it... */
1637 int main(int argc
, char **argv
){
1638 static int version
= 0;
1639 static int rpflag
= 0;
1640 static int basisflag
= 0;
1641 static int compress
= 0;
1642 static int quiet
= 0;
1643 static int statistics
= 0;
1644 static int mhflag
= 0;
1645 static int nolinenosflag
= 0;
1646 static int noResort
= 0;
1647 static int sqlFlag
= 0;
1648 static int printPP
= 0;
1650 static struct s_options options
[] = {
1651 {OPT_FLAG
, "b", (char*)&basisflag
, "Print only the basis in report."},
1652 {OPT_FLAG
, "c", (char*)&compress
, "Don't compress the action table."},
1653 {OPT_FSTR
, "d", (char*)&handle_d_option
, "Output directory. Default '.'"},
1654 {OPT_FSTR
, "D", (char*)handle_D_option
, "Define an %ifdef macro."},
1655 {OPT_FLAG
, "E", (char*)&printPP
, "Print input file after preprocessing."},
1656 {OPT_FSTR
, "f", 0, "Ignored. (Placeholder for -f compiler options.)"},
1657 {OPT_FLAG
, "g", (char*)&rpflag
, "Print grammar without actions."},
1658 {OPT_FSTR
, "I", 0, "Ignored. (Placeholder for '-I' compiler options.)"},
1659 {OPT_FLAG
, "m", (char*)&mhflag
, "Output a makeheaders compatible file."},
1660 {OPT_FLAG
, "l", (char*)&nolinenosflag
, "Do not print #line statements."},
1661 {OPT_FSTR
, "O", 0, "Ignored. (Placeholder for '-O' compiler options.)"},
1662 {OPT_FLAG
, "p", (char*)&showPrecedenceConflict
,
1663 "Show conflicts resolved by precedence rules"},
1664 {OPT_FLAG
, "q", (char*)&quiet
, "(Quiet) Don't print the report file."},
1665 {OPT_FLAG
, "r", (char*)&noResort
, "Do not sort or renumber states"},
1666 {OPT_FLAG
, "s", (char*)&statistics
,
1667 "Print parser stats to standard output."},
1668 {OPT_FLAG
, "S", (char*)&sqlFlag
,
1669 "Generate the *.sql file describing the parser tables."},
1670 {OPT_FLAG
, "x", (char*)&version
, "Print the version number."},
1671 {OPT_FSTR
, "T", (char*)handle_T_option
, "Specify a template file."},
1672 {OPT_FSTR
, "W", 0, "Ignored. (Placeholder for '-W' compiler options.)"},
1680 OptInit(argv
,options
,stderr
);
1682 printf("Lemon version 1.0\n");
1685 if( OptNArgs()!=1 ){
1686 fprintf(stderr
,"Exactly one filename argument is required.\n");
1689 memset(&lem
, 0, sizeof(lem
));
1692 /* Initialize the machine */
1698 lem
.filename
= OptArg(0);
1699 lem
.basisflag
= basisflag
;
1700 lem
.nolinenosflag
= nolinenosflag
;
1701 lem
.printPreprocessed
= printPP
;
1704 /* Parse the input file */
1706 if( lem
.printPreprocessed
|| lem
.errorcnt
) exit(lem
.errorcnt
);
1708 fprintf(stderr
,"Empty grammar.\n");
1711 lem
.errsym
= Symbol_find("error");
1713 /* Count and index the symbols of the grammar */
1714 Symbol_new("{default}");
1715 lem
.nsymbol
= Symbol_count();
1716 lem
.symbols
= Symbol_arrayof();
1717 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1718 qsort(lem
.symbols
,lem
.nsymbol
,sizeof(struct symbol
*), Symbolcmpp
);
1719 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1720 while( lem
.symbols
[i
-1]->type
==MULTITERMINAL
){ i
--; }
1721 assert( strcmp(lem
.symbols
[i
-1]->name
,"{default}")==0 );
1722 lem
.nsymbol
= i
- 1;
1723 for(i
=1; ISUPPER(lem
.symbols
[i
]->name
[0]); i
++);
1726 /* Assign sequential rule numbers. Start with 0. Put rules that have no
1727 ** reduce action C-code associated with them last, so that the switch()
1728 ** statement that selects reduction actions will have a smaller jump table.
1730 for(i
=0, rp
=lem
.rule
; rp
; rp
=rp
->next
){
1731 rp
->iRule
= rp
->code
? i
++ : -1;
1733 lem
.nruleWithAction
= i
;
1734 for(rp
=lem
.rule
; rp
; rp
=rp
->next
){
1735 if( rp
->iRule
<0 ) rp
->iRule
= i
++;
1737 lem
.startRule
= lem
.rule
;
1738 lem
.rule
= Rule_sort(lem
.rule
);
1740 /* Generate a reprint of the grammar, if requested on the command line */
1744 /* Initialize the size for all follow and first sets */
1745 SetSize(lem
.nterminal
+1);
1747 /* Find the precedence for every production rule (that has one) */
1748 FindRulePrecedences(&lem
);
1750 /* Compute the lambda-nonterminals and the first-sets for every
1752 FindFirstSets(&lem
);
1754 /* Compute all LR(0) states. Also record follow-set propagation
1755 ** links so that the follow-set can be computed later */
1758 lem
.sorted
= State_arrayof();
1760 /* Tie up loose ends on the propagation links */
1763 /* Compute the follow set of every reducible configuration */
1764 FindFollowSets(&lem
);
1766 /* Compute the action tables */
1769 /* Compress the action tables */
1770 if( compress
==0 ) CompressTables(&lem
);
1772 /* Reorder and renumber the states so that states with fewer choices
1773 ** occur at the end. This is an optimization that helps make the
1774 ** generated parser tables smaller. */
1775 if( noResort
==0 ) ResortStates(&lem
);
1777 /* Generate a report of the parser generated. (the "y.output" file) */
1778 if( !quiet
) ReportOutput(&lem
);
1780 /* Generate the source code for the parser */
1781 ReportTable(&lem
, mhflag
, sqlFlag
);
1783 /* Produce a header file for use by the scanner. (This step is
1784 ** omitted if the "-m" option is used because makeheaders will
1785 ** generate the file for us.) */
1786 if( !mhflag
) ReportHeader(&lem
);
1789 printf("Parser statistics:\n");
1790 stats_line("terminal symbols", lem
.nterminal
);
1791 stats_line("non-terminal symbols", lem
.nsymbol
- lem
.nterminal
);
1792 stats_line("total symbols", lem
.nsymbol
);
1793 stats_line("rules", lem
.nrule
);
1794 stats_line("states", lem
.nxstate
);
1795 stats_line("conflicts", lem
.nconflict
);
1796 stats_line("action table entries", lem
.nactiontab
);
1797 stats_line("lookahead table entries", lem
.nlookaheadtab
);
1798 stats_line("total table size (bytes)", lem
.tablesize
);
1800 if( lem
.nconflict
> 0 ){
1801 fprintf(stderr
,"%d parsing conflicts.\n",lem
.nconflict
);
1804 /* return 0 on success, 1 on failure. */
1805 exitcode
= ((lem
.errorcnt
> 0) || (lem
.nconflict
> 0)) ? 1 : 0;
1809 /******************** From the file "msort.c" *******************************/
1811 ** A generic merge-sort program.
1814 ** Let "ptr" be a pointer to some structure which is at the head of
1815 ** a null-terminated list. Then to sort the list call:
1817 ** ptr = msort(ptr,&(ptr->next),cmpfnc);
1819 ** In the above, "cmpfnc" is a pointer to a function which compares
1820 ** two instances of the structure and returns an integer, as in
1821 ** strcmp. The second argument is a pointer to the pointer to the
1822 ** second element of the linked list. This address is used to compute
1823 ** the offset to the "next" field within the structure. The offset to
1824 ** the "next" field must be constant for all structures in the list.
1826 ** The function returns a new pointer which is the head of the list
1834 ** Return a pointer to the next structure in the linked list.
1836 #define NEXT(A) (*(char**)(((char*)A)+offset))
1840 ** a: A sorted, null-terminated linked list. (May be null).
1841 ** b: A sorted, null-terminated linked list. (May be null).
1842 ** cmp: A pointer to the comparison function.
1843 ** offset: Offset in the structure to the "next" field.
1846 ** A pointer to the head of a sorted list containing the elements
1850 ** The "next" pointers for elements in the lists a and b are
1856 int (*cmp
)(const char*,const char*),
1866 if( (*cmp
)(a
,b
)<=0 ){
1875 if( (*cmp
)(a
,b
)<=0 ){
1885 if( a
) NEXT(ptr
) = a
;
1893 ** list: Pointer to a singly-linked list of structures.
1894 ** next: Pointer to pointer to the second element of the list.
1895 ** cmp: A comparison function.
1898 ** A pointer to the head of a sorted list containing the elements
1899 ** originally in list.
1902 ** The "next" pointers for elements in list are changed.
1908 int (*cmp
)(const char*,const char*)
1910 unsigned long offset
;
1912 char *set
[LISTSIZE
];
1914 offset
= (unsigned long)((char*)next
- (char*)list
);
1915 for(i
=0; i
<LISTSIZE
; i
++) set
[i
] = 0;
1920 for(i
=0; i
<LISTSIZE
-1 && set
[i
]!=0; i
++){
1921 ep
= merge(ep
,set
[i
],cmp
,offset
);
1927 for(i
=0; i
<LISTSIZE
; i
++) if( set
[i
] ) ep
= merge(set
[i
],ep
,cmp
,offset
);
1930 /************************ From the file "option.c" **************************/
1931 static char **g_argv
;
1932 static struct s_options
*op
;
1933 static FILE *errstream
;
1935 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1938 ** Print the command line with a carrot pointing to the k-th character
1939 ** of the n-th field.
1941 static void errline(int n
, int k
, FILE *err
)
1945 fprintf(err
,"%s",g_argv
[0]);
1946 spcnt
= lemonStrlen(g_argv
[0]) + 1;
1950 for(i
=1; i
<n
&& g_argv
[i
]; i
++){
1951 fprintf(err
," %s",g_argv
[i
]);
1952 spcnt
+= lemonStrlen(g_argv
[i
])+1;
1955 for(; g_argv
[i
]; i
++) fprintf(err
," %s",g_argv
[i
]);
1957 fprintf(err
,"\n%*s^-- here\n",spcnt
,"");
1959 fprintf(err
,"\n%*shere --^\n",spcnt
-7,"");
1964 ** Return the index of the N-th non-switch argument. Return -1
1965 ** if N is out of range.
1967 static int argindex(int n
)
1971 if( g_argv
!=0 && *g_argv
!=0 ){
1972 for(i
=1; g_argv
[i
]; i
++){
1973 if( dashdash
|| !ISOPT(g_argv
[i
]) ){
1974 if( n
==0 ) return i
;
1977 if( strcmp(g_argv
[i
],"--")==0 ) dashdash
= 1;
1983 static char emsg
[] = "Command line syntax error: ";
1986 ** Process a flag command line argument.
1988 static int handleflags(int i
, FILE *err
)
1993 for(j
=0; op
[j
].label
; j
++){
1994 if( strncmp(&g_argv
[i
][1],op
[j
].label
,lemonStrlen(op
[j
].label
))==0 ) break;
1996 v
= g_argv
[i
][0]=='-' ? 1 : 0;
1997 if( op
[j
].label
==0 ){
1999 fprintf(err
,"%sundefined option.\n",emsg
);
2003 }else if( op
[j
].arg
==0 ){
2004 /* Ignore this option */
2005 }else if( op
[j
].type
==OPT_FLAG
){
2006 *((int*)op
[j
].arg
) = v
;
2007 }else if( op
[j
].type
==OPT_FFLAG
){
2008 (*(void(*)(int))(op
[j
].arg
))(v
);
2009 }else if( op
[j
].type
==OPT_FSTR
){
2010 (*(void(*)(char *))(op
[j
].arg
))(&g_argv
[i
][2]);
2013 fprintf(err
,"%smissing argument on switch.\n",emsg
);
2022 ** Process a command line switch which has an argument.
2024 static int handleswitch(int i
, FILE *err
)
2032 cp
= strchr(g_argv
[i
],'=');
2035 for(j
=0; op
[j
].label
; j
++){
2036 if( strcmp(g_argv
[i
],op
[j
].label
)==0 ) break;
2039 if( op
[j
].label
==0 ){
2041 fprintf(err
,"%sundefined option.\n",emsg
);
2047 switch( op
[j
].type
){
2051 fprintf(err
,"%soption requires an argument.\n",emsg
);
2058 dv
= strtod(cp
,&end
);
2062 "%sillegal character in floating-point argument.\n",emsg
);
2063 errline(i
,(int)((char*)end
-(char*)g_argv
[i
]),err
);
2070 lv
= strtol(cp
,&end
,0);
2073 fprintf(err
,"%sillegal character in integer argument.\n",emsg
);
2074 errline(i
,(int)((char*)end
-(char*)g_argv
[i
]),err
);
2084 switch( op
[j
].type
){
2089 *(double*)(op
[j
].arg
) = dv
;
2092 (*(void(*)(double))(op
[j
].arg
))(dv
);
2095 *(int*)(op
[j
].arg
) = lv
;
2098 (*(void(*)(int))(op
[j
].arg
))((int)lv
);
2101 *(char**)(op
[j
].arg
) = sv
;
2104 (*(void(*)(char *))(op
[j
].arg
))(sv
);
2111 int OptInit(char **a
, struct s_options
*o
, FILE *err
)
2117 if( g_argv
&& *g_argv
&& op
){
2119 for(i
=1; g_argv
[i
]; i
++){
2120 if( g_argv
[i
][0]=='+' || g_argv
[i
][0]=='-' ){
2121 errcnt
+= handleflags(i
,err
);
2122 }else if( strchr(g_argv
[i
],'=') ){
2123 errcnt
+= handleswitch(i
,err
);
2128 fprintf(err
,"Valid command line options for \"%s\" are:\n",*a
);
2139 if( g_argv
!=0 && g_argv
[0]!=0 ){
2140 for(i
=1; g_argv
[i
]; i
++){
2141 if( dashdash
|| !ISOPT(g_argv
[i
]) ) cnt
++;
2142 if( strcmp(g_argv
[i
],"--")==0 ) dashdash
= 1;
2152 return i
>=0 ? g_argv
[i
] : 0;
2159 if( i
>=0 ) errline(i
,0,errstream
);
2162 void OptPrint(void){
2166 for(i
=0; op
[i
].label
; i
++){
2167 len
= lemonStrlen(op
[i
].label
) + 1;
2168 switch( op
[i
].type
){
2174 len
+= 9; /* length of "<integer>" */
2178 len
+= 6; /* length of "<real>" */
2182 len
+= 8; /* length of "<string>" */
2185 if( len
>max
) max
= len
;
2187 for(i
=0; op
[i
].label
; i
++){
2188 switch( op
[i
].type
){
2191 fprintf(errstream
," -%-*s %s\n",max
,op
[i
].label
,op
[i
].message
);
2195 fprintf(errstream
," -%s<integer>%*s %s\n",op
[i
].label
,
2196 (int)(max
-lemonStrlen(op
[i
].label
)-9),"",op
[i
].message
);
2200 fprintf(errstream
," -%s<real>%*s %s\n",op
[i
].label
,
2201 (int)(max
-lemonStrlen(op
[i
].label
)-6),"",op
[i
].message
);
2205 fprintf(errstream
," -%s<string>%*s %s\n",op
[i
].label
,
2206 (int)(max
-lemonStrlen(op
[i
].label
)-8),"",op
[i
].message
);
2211 /*********************** From the file "parse.c" ****************************/
2213 ** Input file parser for the LEMON parser generator.
2216 /* The state of the parser */
2219 WAITING_FOR_DECL_OR_RULE
,
2220 WAITING_FOR_DECL_KEYWORD
,
2221 WAITING_FOR_DECL_ARG
,
2222 WAITING_FOR_PRECEDENCE_SYMBOL
,
2232 RESYNC_AFTER_RULE_ERROR
,
2233 RESYNC_AFTER_DECL_ERROR
,
2234 WAITING_FOR_DESTRUCTOR_SYMBOL
,
2235 WAITING_FOR_DATATYPE_SYMBOL
,
2236 WAITING_FOR_FALLBACK_ID
,
2237 WAITING_FOR_WILDCARD_ID
,
2238 WAITING_FOR_CLASS_ID
,
2239 WAITING_FOR_CLASS_TOKEN
,
2240 WAITING_FOR_TOKEN_NAME
2243 char *filename
; /* Name of the input file */
2244 int tokenlineno
; /* Linenumber at which current token starts */
2245 int errorcnt
; /* Number of errors so far */
2246 char *tokenstart
; /* Text of current token */
2247 struct lemon
*gp
; /* Global state vector */
2248 enum e_state state
; /* The state of the parser */
2249 struct symbol
*fallback
; /* The fallback token */
2250 struct symbol
*tkclass
; /* Token class symbol */
2251 struct symbol
*lhs
; /* Left-hand side of current rule */
2252 const char *lhsalias
; /* Alias for the LHS */
2253 int nrhs
; /* Number of right-hand side symbols seen */
2254 struct symbol
*rhs
[MAXRHS
]; /* RHS symbols */
2255 const char *alias
[MAXRHS
]; /* Aliases for each RHS symbol (or NULL) */
2256 struct rule
*prevrule
; /* Previous rule parsed */
2257 const char *declkeyword
; /* Keyword of a declaration */
2258 char **declargslot
; /* Where the declaration argument should be put */
2259 int insertLineMacro
; /* Add #line before declaration insert */
2260 int *decllinenoslot
; /* Where to write declaration line number */
2261 enum e_assoc declassoc
; /* Assign this association to decl arguments */
2262 int preccounter
; /* Assign this precedence to decl arguments */
2263 struct rule
*firstrule
; /* Pointer to first rule in the grammar */
2264 struct rule
*lastrule
; /* Pointer to the most recently parsed rule */
2267 /* Parse a single token */
2268 static void parseonetoken(struct pstate
*psp
)
2271 x
= Strsafe(psp
->tokenstart
); /* Save the token permanently */
2273 printf("%s:%d: Token=[%s] state=%d\n",psp
->filename
,psp
->tokenlineno
,
2276 switch( psp
->state
){
2279 psp
->preccounter
= 0;
2280 psp
->firstrule
= psp
->lastrule
= 0;
2283 case WAITING_FOR_DECL_OR_RULE
:
2285 psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2286 }else if( ISLOWER(x
[0]) ){
2287 psp
->lhs
= Symbol_new(x
);
2290 psp
->state
= WAITING_FOR_ARROW
;
2291 }else if( x
[0]=='{' ){
2292 if( psp
->prevrule
==0 ){
2293 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2294 "There is no prior rule upon which to attach the code "
2295 "fragment which begins on this line.");
2297 }else if( psp
->prevrule
->code
!=0 ){
2298 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2299 "Code fragment beginning on this line is not the first "
2300 "to follow the previous rule.");
2302 }else if( strcmp(x
, "{NEVER-REDUCE")==0 ){
2303 psp
->prevrule
->neverReduce
= 1;
2305 psp
->prevrule
->line
= psp
->tokenlineno
;
2306 psp
->prevrule
->code
= &x
[1];
2307 psp
->prevrule
->noCode
= 0;
2309 }else if( x
[0]=='[' ){
2310 psp
->state
= PRECEDENCE_MARK_1
;
2312 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2313 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2318 case PRECEDENCE_MARK_1
:
2319 if( !ISUPPER(x
[0]) ){
2320 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2321 "The precedence symbol must be a terminal.");
2323 }else if( psp
->prevrule
==0 ){
2324 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2325 "There is no prior rule to assign precedence \"[%s]\".",x
);
2327 }else if( psp
->prevrule
->precsym
!=0 ){
2328 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2329 "Precedence mark on this line is not the first "
2330 "to follow the previous rule.");
2333 psp
->prevrule
->precsym
= Symbol_new(x
);
2335 psp
->state
= PRECEDENCE_MARK_2
;
2337 case PRECEDENCE_MARK_2
:
2339 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2340 "Missing \"]\" on precedence mark.");
2343 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2345 case WAITING_FOR_ARROW
:
2346 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2347 psp
->state
= IN_RHS
;
2348 }else if( x
[0]=='(' ){
2349 psp
->state
= LHS_ALIAS_1
;
2351 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2352 "Expected to see a \":\" following the LHS symbol \"%s\".",
2355 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2359 if( ISALPHA(x
[0]) ){
2361 psp
->state
= LHS_ALIAS_2
;
2363 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2364 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2367 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2372 psp
->state
= LHS_ALIAS_3
;
2374 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2375 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2377 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2381 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2382 psp
->state
= IN_RHS
;
2384 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2385 "Missing \"->\" following: \"%s(%s)\".",
2386 psp
->lhs
->name
,psp
->lhsalias
);
2388 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2394 rp
= (struct rule
*)calloc( sizeof(struct rule
) +
2395 sizeof(struct symbol
*)*psp
->nrhs
+ sizeof(char*)*psp
->nrhs
, 1);
2397 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2398 "Can't allocate enough memory for this rule.");
2403 rp
->ruleline
= psp
->tokenlineno
;
2404 rp
->rhs
= (struct symbol
**)&rp
[1];
2405 rp
->rhsalias
= (const char**)&(rp
->rhs
[psp
->nrhs
]);
2406 for(i
=0; i
<psp
->nrhs
; i
++){
2407 rp
->rhs
[i
] = psp
->rhs
[i
];
2408 rp
->rhsalias
[i
] = psp
->alias
[i
];
2409 if( rp
->rhsalias
[i
]!=0 ){ rp
->rhs
[i
]->bContent
= 1; }
2412 rp
->lhsalias
= psp
->lhsalias
;
2413 rp
->nrhs
= psp
->nrhs
;
2417 rp
->index
= psp
->gp
->nrule
++;
2418 rp
->nextlhs
= rp
->lhs
->rule
;
2421 if( psp
->firstrule
==0 ){
2422 psp
->firstrule
= psp
->lastrule
= rp
;
2424 psp
->lastrule
->next
= rp
;
2429 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2430 }else if( ISALPHA(x
[0]) ){
2431 if( psp
->nrhs
>=MAXRHS
){
2432 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2433 "Too many symbols on RHS of rule beginning at \"%s\".",
2436 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2438 psp
->rhs
[psp
->nrhs
] = Symbol_new(x
);
2439 psp
->alias
[psp
->nrhs
] = 0;
2442 }else if( (x
[0]=='|' || x
[0]=='/') && psp
->nrhs
>0 && ISUPPER(x
[1]) ){
2443 struct symbol
*msp
= psp
->rhs
[psp
->nrhs
-1];
2444 if( msp
->type
!=MULTITERMINAL
){
2445 struct symbol
*origsp
= msp
;
2446 msp
= (struct symbol
*) calloc(1,sizeof(*msp
));
2447 memset(msp
, 0, sizeof(*msp
));
2448 msp
->type
= MULTITERMINAL
;
2450 msp
->subsym
= (struct symbol
**) calloc(1,sizeof(struct symbol
*));
2451 msp
->subsym
[0] = origsp
;
2452 msp
->name
= origsp
->name
;
2453 psp
->rhs
[psp
->nrhs
-1] = msp
;
2456 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2457 sizeof(struct symbol
*)*msp
->nsubsym
);
2458 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(&x
[1]);
2459 if( ISLOWER(x
[1]) || ISLOWER(msp
->subsym
[0]->name
[0]) ){
2460 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2461 "Cannot form a compound containing a non-terminal");
2464 }else if( x
[0]=='(' && psp
->nrhs
>0 ){
2465 psp
->state
= RHS_ALIAS_1
;
2467 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2468 "Illegal character on RHS of rule: \"%s\".",x
);
2470 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2474 if( ISALPHA(x
[0]) ){
2475 psp
->alias
[psp
->nrhs
-1] = x
;
2476 psp
->state
= RHS_ALIAS_2
;
2478 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2479 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2480 x
,psp
->rhs
[psp
->nrhs
-1]->name
);
2482 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2487 psp
->state
= IN_RHS
;
2489 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2490 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2492 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2495 case WAITING_FOR_DECL_KEYWORD
:
2496 if( ISALPHA(x
[0]) ){
2497 psp
->declkeyword
= x
;
2498 psp
->declargslot
= 0;
2499 psp
->decllinenoslot
= 0;
2500 psp
->insertLineMacro
= 1;
2501 psp
->state
= WAITING_FOR_DECL_ARG
;
2502 if( strcmp(x
,"name")==0 ){
2503 psp
->declargslot
= &(psp
->gp
->name
);
2504 psp
->insertLineMacro
= 0;
2505 }else if( strcmp(x
,"include")==0 ){
2506 psp
->declargslot
= &(psp
->gp
->include
);
2507 }else if( strcmp(x
,"code")==0 ){
2508 psp
->declargslot
= &(psp
->gp
->extracode
);
2509 }else if( strcmp(x
,"token_destructor")==0 ){
2510 psp
->declargslot
= &psp
->gp
->tokendest
;
2511 }else if( strcmp(x
,"default_destructor")==0 ){
2512 psp
->declargslot
= &psp
->gp
->vardest
;
2513 }else if( strcmp(x
,"token_prefix")==0 ){
2514 psp
->declargslot
= &psp
->gp
->tokenprefix
;
2515 psp
->insertLineMacro
= 0;
2516 }else if( strcmp(x
,"syntax_error")==0 ){
2517 psp
->declargslot
= &(psp
->gp
->error
);
2518 }else if( strcmp(x
,"parse_accept")==0 ){
2519 psp
->declargslot
= &(psp
->gp
->accept
);
2520 }else if( strcmp(x
,"parse_failure")==0 ){
2521 psp
->declargslot
= &(psp
->gp
->failure
);
2522 }else if( strcmp(x
,"stack_overflow")==0 ){
2523 psp
->declargslot
= &(psp
->gp
->overflow
);
2524 }else if( strcmp(x
,"extra_argument")==0 ){
2525 psp
->declargslot
= &(psp
->gp
->arg
);
2526 psp
->insertLineMacro
= 0;
2527 }else if( strcmp(x
,"extra_context")==0 ){
2528 psp
->declargslot
= &(psp
->gp
->ctx
);
2529 psp
->insertLineMacro
= 0;
2530 }else if( strcmp(x
,"token_type")==0 ){
2531 psp
->declargslot
= &(psp
->gp
->tokentype
);
2532 psp
->insertLineMacro
= 0;
2533 }else if( strcmp(x
,"default_type")==0 ){
2534 psp
->declargslot
= &(psp
->gp
->vartype
);
2535 psp
->insertLineMacro
= 0;
2536 }else if( strcmp(x
,"realloc")==0 ){
2537 psp
->declargslot
= &(psp
->gp
->reallocFunc
);
2538 psp
->insertLineMacro
= 0;
2539 }else if( strcmp(x
,"free")==0 ){
2540 psp
->declargslot
= &(psp
->gp
->freeFunc
);
2541 psp
->insertLineMacro
= 0;
2542 }else if( strcmp(x
,"stack_size")==0 ){
2543 psp
->declargslot
= &(psp
->gp
->stacksize
);
2544 psp
->insertLineMacro
= 0;
2545 }else if( strcmp(x
,"start_symbol")==0 ){
2546 psp
->declargslot
= &(psp
->gp
->start
);
2547 psp
->insertLineMacro
= 0;
2548 }else if( strcmp(x
,"left")==0 ){
2550 psp
->declassoc
= LEFT
;
2551 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2552 }else if( strcmp(x
,"right")==0 ){
2554 psp
->declassoc
= RIGHT
;
2555 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2556 }else if( strcmp(x
,"nonassoc")==0 ){
2558 psp
->declassoc
= NONE
;
2559 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2560 }else if( strcmp(x
,"destructor")==0 ){
2561 psp
->state
= WAITING_FOR_DESTRUCTOR_SYMBOL
;
2562 }else if( strcmp(x
,"type")==0 ){
2563 psp
->state
= WAITING_FOR_DATATYPE_SYMBOL
;
2564 }else if( strcmp(x
,"fallback")==0 ){
2566 psp
->state
= WAITING_FOR_FALLBACK_ID
;
2567 }else if( strcmp(x
,"token")==0 ){
2568 psp
->state
= WAITING_FOR_TOKEN_NAME
;
2569 }else if( strcmp(x
,"wildcard")==0 ){
2570 psp
->state
= WAITING_FOR_WILDCARD_ID
;
2571 }else if( strcmp(x
,"token_class")==0 ){
2572 psp
->state
= WAITING_FOR_CLASS_ID
;
2574 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2575 "Unknown declaration keyword: \"%%%s\".",x
);
2577 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2580 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2581 "Illegal declaration keyword: \"%s\".",x
);
2583 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2586 case WAITING_FOR_DESTRUCTOR_SYMBOL
:
2587 if( !ISALPHA(x
[0]) ){
2588 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2589 "Symbol name missing after %%destructor keyword");
2591 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2593 struct symbol
*sp
= Symbol_new(x
);
2594 psp
->declargslot
= &sp
->destructor
;
2595 psp
->decllinenoslot
= &sp
->destLineno
;
2596 psp
->insertLineMacro
= 1;
2597 psp
->state
= WAITING_FOR_DECL_ARG
;
2600 case WAITING_FOR_DATATYPE_SYMBOL
:
2601 if( !ISALPHA(x
[0]) ){
2602 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2603 "Symbol name missing after %%type keyword");
2605 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2607 struct symbol
*sp
= Symbol_find(x
);
2608 if((sp
) && (sp
->datatype
)){
2609 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2610 "Symbol %%type \"%s\" already defined", x
);
2612 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2617 psp
->declargslot
= &sp
->datatype
;
2618 psp
->insertLineMacro
= 0;
2619 psp
->state
= WAITING_FOR_DECL_ARG
;
2623 case WAITING_FOR_PRECEDENCE_SYMBOL
:
2625 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2626 }else if( ISUPPER(x
[0]) ){
2630 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2631 "Symbol \"%s\" has already be given a precedence.",x
);
2634 sp
->prec
= psp
->preccounter
;
2635 sp
->assoc
= psp
->declassoc
;
2638 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2639 "Can't assign a precedence to \"%s\".",x
);
2643 case WAITING_FOR_DECL_ARG
:
2644 if( x
[0]=='{' || x
[0]=='\"' || ISALNUM(x
[0]) ){
2645 const char *zOld
, *zNew
;
2647 int nOld
, n
, nLine
= 0, nNew
, nBack
;
2651 if( zNew
[0]=='"' || zNew
[0]=='{' ) zNew
++;
2652 nNew
= lemonStrlen(zNew
);
2653 if( *psp
->declargslot
){
2654 zOld
= *psp
->declargslot
;
2658 nOld
= lemonStrlen(zOld
);
2659 n
= nOld
+ nNew
+ 20;
2660 addLineMacro
= !psp
->gp
->nolinenosflag
2661 && psp
->insertLineMacro
2662 && psp
->tokenlineno
>1
2663 && (psp
->decllinenoslot
==0 || psp
->decllinenoslot
[0]!=0);
2665 for(z
=psp
->filename
, nBack
=0; *z
; z
++){
2666 if( *z
=='\\' ) nBack
++;
2668 lemon_sprintf(zLine
, "#line %d ", psp
->tokenlineno
);
2669 nLine
= lemonStrlen(zLine
);
2670 n
+= nLine
+ lemonStrlen(psp
->filename
) + nBack
;
2672 *psp
->declargslot
= (char *) realloc(*psp
->declargslot
, n
);
2673 zBuf
= *psp
->declargslot
+ nOld
;
2675 if( nOld
&& zBuf
[-1]!='\n' ){
2678 memcpy(zBuf
, zLine
, nLine
);
2681 for(z
=psp
->filename
; *z
; z
++){
2690 if( psp
->decllinenoslot
&& psp
->decllinenoslot
[0]==0 ){
2691 psp
->decllinenoslot
[0] = psp
->tokenlineno
;
2693 memcpy(zBuf
, zNew
, nNew
);
2696 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2698 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2699 "Illegal argument to %%%s: %s",psp
->declkeyword
,x
);
2701 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2704 case WAITING_FOR_FALLBACK_ID
:
2706 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2707 }else if( !ISUPPER(x
[0]) ){
2708 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2709 "%%fallback argument \"%s\" should be a token", x
);
2712 struct symbol
*sp
= Symbol_new(x
);
2713 if( psp
->fallback
==0 ){
2715 }else if( sp
->fallback
){
2716 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2717 "More than one fallback assigned to token %s", x
);
2720 sp
->fallback
= psp
->fallback
;
2721 psp
->gp
->has_fallback
= 1;
2725 case WAITING_FOR_TOKEN_NAME
:
2726 /* Tokens do not have to be declared before use. But they can be
2727 ** in order to control their assigned integer number. The number for
2728 ** each token is assigned when it is first seen. So by including
2730 ** %token ONE TWO THREE.
2732 ** early in the grammar file, that assigns small consecutive values
2733 ** to each of the tokens ONE TWO and THREE.
2736 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2737 }else if( !ISUPPER(x
[0]) ){
2738 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2739 "%%token argument \"%s\" should be a token", x
);
2742 (void)Symbol_new(x
);
2745 case WAITING_FOR_WILDCARD_ID
:
2747 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2748 }else if( !ISUPPER(x
[0]) ){
2749 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2750 "%%wildcard argument \"%s\" should be a token", x
);
2753 struct symbol
*sp
= Symbol_new(x
);
2754 if( psp
->gp
->wildcard
==0 ){
2755 psp
->gp
->wildcard
= sp
;
2757 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2758 "Extra wildcard to token: %s", x
);
2763 case WAITING_FOR_CLASS_ID
:
2764 if( !ISLOWER(x
[0]) ){
2765 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2766 "%%token_class must be followed by an identifier: %s", x
);
2768 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2769 }else if( Symbol_find(x
) ){
2770 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2771 "Symbol \"%s\" already used", x
);
2773 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2775 psp
->tkclass
= Symbol_new(x
);
2776 psp
->tkclass
->type
= MULTITERMINAL
;
2777 psp
->state
= WAITING_FOR_CLASS_TOKEN
;
2780 case WAITING_FOR_CLASS_TOKEN
:
2782 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2783 }else if( ISUPPER(x
[0]) || ((x
[0]=='|' || x
[0]=='/') && ISUPPER(x
[1])) ){
2784 struct symbol
*msp
= psp
->tkclass
;
2786 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2787 sizeof(struct symbol
*)*msp
->nsubsym
);
2788 if( !ISUPPER(x
[0]) ) x
++;
2789 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(x
);
2791 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2792 "%%token_class argument \"%s\" should be a token", x
);
2794 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2797 case RESYNC_AFTER_RULE_ERROR
:
2798 /* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2800 case RESYNC_AFTER_DECL_ERROR
:
2801 if( x
[0]=='.' ) psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2802 if( x
[0]=='%' ) psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2807 /* The text in the input is part of the argument to an %ifdef or %ifndef.
2808 ** Evaluate the text as a boolean expression. Return true or false.
2810 static int eval_preprocessor_boolean(char *z
, int lineno
){
2815 for(i
=0; z
[i
]!=0; i
++){
2816 if( ISSPACE(z
[i
]) ) continue;
2818 if( !okTerm
) goto pp_syntax_error
;
2822 if( z
[i
]=='|' && z
[i
+1]=='|' ){
2823 if( okTerm
) goto pp_syntax_error
;
2829 if( z
[i
]=='&' && z
[i
+1]=='&' ){
2830 if( okTerm
) goto pp_syntax_error
;
2831 if( !res
) return 0;
2839 if( !okTerm
) goto pp_syntax_error
;
2840 for(k
=i
+1; z
[k
]; k
++){
2845 res
= eval_preprocessor_boolean(&z
[i
+1], -1);
2849 goto pp_syntax_error
;
2854 }else if( z
[k
]=='(' ){
2856 }else if( z
[k
]==0 ){
2858 goto pp_syntax_error
;
2868 if( ISALPHA(z
[i
]) ){
2870 if( !okTerm
) goto pp_syntax_error
;
2871 for(k
=i
+1; ISALNUM(z
[k
]) || z
[k
]=='_'; k
++){}
2874 for(j
=0; j
<nDefine
; j
++){
2875 if( strncmp(azDefine
[j
],&z
[i
],n
)==0 && azDefine
[j
][n
]==0 ){
2876 if( !bDefineUsed
[j
] ){
2892 goto pp_syntax_error
;
2898 fprintf(stderr
, "%%if syntax error on line %d.\n", lineno
);
2899 fprintf(stderr
, " %.*s <-- syntax error here\n", i
+1, z
);
2906 /* Run the preprocessor over the input file text. The global variables
2907 ** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2908 ** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2909 ** comments them out. Text in between is also commented out as appropriate.
2911 static void preprocess_input(char *z
){
2916 int start_lineno
= 1;
2917 for(i
=0; z
[i
]; i
++){
2918 if( z
[i
]=='\n' ) lineno
++;
2919 if( z
[i
]!='%' || (i
>0 && z
[i
-1]!='\n') ) continue;
2920 if( strncmp(&z
[i
],"%endif",6)==0 && ISSPACE(z
[i
+6]) ){
2924 for(j
=start
; j
<i
; j
++) if( z
[j
]!='\n' ) z
[j
] = ' ';
2927 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2928 }else if( strncmp(&z
[i
],"%else",5)==0 && ISSPACE(z
[i
+5]) ){
2931 for(j
=start
; j
<i
; j
++) if( z
[j
]!='\n' ) z
[j
] = ' ';
2932 }else if( exclude
==0 ){
2935 start_lineno
= lineno
;
2937 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2938 }else if( strncmp(&z
[i
],"%ifdef ",7)==0
2939 || strncmp(&z
[i
],"%if ",4)==0
2940 || strncmp(&z
[i
],"%ifndef ",8)==0 ){
2946 for(j
=i
; z
[j
] && !ISSPACE(z
[j
]); j
++){}
2949 while( z
[j
] && z
[j
]!='\n' ){ j
++; }
2952 exclude
= eval_preprocessor_boolean(&z
[iBool
], lineno
);
2954 if( !isNot
) exclude
= !exclude
;
2957 start_lineno
= lineno
;
2960 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2964 fprintf(stderr
,"unterminated %%ifdef starting on line %d\n", start_lineno
);
2969 /* In spite of its name, this function is really a scanner. It read
2970 ** in the entire input file (all at once) then tokenizes it. Each
2971 ** token is passed to the function "parseonetoken" which builds all
2972 ** the appropriate data structures in the global state vector "gp".
2974 void Parse(struct lemon
*gp
)
2979 unsigned int filesize
;
2985 memset(&ps
, '\0', sizeof(ps
));
2987 ps
.filename
= gp
->filename
;
2989 ps
.state
= INITIALIZE
;
2991 /* Begin by reading the input file */
2992 fp
= fopen(ps
.filename
,"rb");
2994 ErrorMsg(ps
.filename
,0,"Can't open this file for reading.");
2999 filesize
= ftell(fp
);
3001 filebuf
= (char *)malloc( filesize
+1 );
3002 if( filesize
>100000000 || filebuf
==0 ){
3003 ErrorMsg(ps
.filename
,0,"Input file too large.");
3009 if( fread(filebuf
,1,filesize
,fp
)!=filesize
){
3010 ErrorMsg(ps
.filename
,0,"Can't read in all %d bytes of this file.",
3018 filebuf
[filesize
] = 0;
3020 /* Make an initial pass through the file to handle %ifdef and %ifndef */
3021 preprocess_input(filebuf
);
3022 if( gp
->printPreprocessed
){
3023 printf("%s\n", filebuf
);
3027 /* Now scan the text of the input file */
3029 for(cp
=filebuf
; (c
= *cp
)!=0; ){
3030 if( c
=='\n' ) lineno
++; /* Keep track of the line number */
3031 if( ISSPACE(c
) ){ cp
++; continue; } /* Skip all white space */
3032 if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments */
3034 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
3037 if( c
=='/' && cp
[1]=='*' ){ /* Skip C style comments */
3039 if( (*cp
)=='/' ) cp
++;
3040 while( (c
= *cp
)!=0 && (c
!='/' || cp
[-1]!='*') ){
3041 if( c
=='\n' ) lineno
++;
3047 ps
.tokenstart
= cp
; /* Mark the beginning of the token */
3048 ps
.tokenlineno
= lineno
; /* Linenumber on which token begins */
3049 if( c
=='\"' ){ /* String literals */
3051 while( (c
= *cp
)!=0 && c
!='\"' ){
3052 if( c
=='\n' ) lineno
++;
3056 ErrorMsg(ps
.filename
,startline
,
3057 "String starting on this line is not terminated before "
3058 "the end of the file.");
3064 }else if( c
=='{' ){ /* A block of C code */
3067 for(level
=1; (c
= *cp
)!=0 && (level
>1 || c
!='}'); cp
++){
3068 if( c
=='\n' ) lineno
++;
3069 else if( c
=='{' ) level
++;
3070 else if( c
=='}' ) level
--;
3071 else if( c
=='/' && cp
[1]=='*' ){ /* Skip comments */
3075 while( (c
= *cp
)!=0 && (c
!='/' || prevc
!='*') ){
3076 if( c
=='\n' ) lineno
++;
3080 }else if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments too */
3082 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
3084 }else if( c
=='\'' || c
=='\"' ){ /* String a character literals */
3085 int startchar
, prevc
;
3088 for(cp
++; (c
= *cp
)!=0 && (c
!=startchar
|| prevc
=='\\'); cp
++){
3089 if( c
=='\n' ) lineno
++;
3090 if( prevc
=='\\' ) prevc
= 0;
3096 ErrorMsg(ps
.filename
,ps
.tokenlineno
,
3097 "C code starting on this line is not terminated before "
3098 "the end of the file.");
3104 }else if( ISALNUM(c
) ){ /* Identifiers */
3105 while( (c
= *cp
)!=0 && (ISALNUM(c
) || c
=='_') ) cp
++;
3107 }else if( c
==':' && cp
[1]==':' && cp
[2]=='=' ){ /* The operator "::=" */
3110 }else if( (c
=='/' || c
=='|') && ISALPHA(cp
[1]) ){
3112 while( (c
= *cp
)!=0 && (ISALNUM(c
) || c
=='_') ) cp
++;
3114 }else{ /* All other (one character) operators */
3119 *cp
= 0; /* Null terminate the token */
3120 parseonetoken(&ps
); /* Parse the token */
3121 *cp
= (char)c
; /* Restore the buffer */
3124 free(filebuf
); /* Release the buffer after parsing */
3125 gp
->rule
= ps
.firstrule
;
3126 gp
->errorcnt
= ps
.errorcnt
;
3128 /*************************** From the file "plink.c" *********************/
3130 ** Routines processing configuration follow-set propagation links
3131 ** in the LEMON parser generator.
3133 static struct plink
*plink_freelist
= 0;
3135 /* Allocate a new plink */
3136 struct plink
*Plink_new(void){
3137 struct plink
*newlink
;
3139 if( plink_freelist
==0 ){
3142 plink_freelist
= (struct plink
*)calloc( amt
, sizeof(struct plink
) );
3143 if( plink_freelist
==0 ){
3145 "Unable to allocate memory for a new follow-set propagation link.\n");
3148 for(i
=0; i
<amt
-1; i
++) plink_freelist
[i
].next
= &plink_freelist
[i
+1];
3149 plink_freelist
[amt
-1].next
= 0;
3151 newlink
= plink_freelist
;
3152 plink_freelist
= plink_freelist
->next
;
3156 /* Add a plink to a plink list */
3157 void Plink_add(struct plink
**plpp
, struct config
*cfp
)
3159 struct plink
*newlink
;
3160 newlink
= Plink_new();
3161 newlink
->next
= *plpp
;
3166 /* Transfer every plink on the list "from" to the list "to" */
3167 void Plink_copy(struct plink
**to
, struct plink
*from
)
3169 struct plink
*nextpl
;
3171 nextpl
= from
->next
;
3178 /* Delete every plink on the list */
3179 void Plink_delete(struct plink
*plp
)
3181 struct plink
*nextpl
;
3185 plp
->next
= plink_freelist
;
3186 plink_freelist
= plp
;
3190 /*********************** From the file "report.c" **************************/
3192 ** Procedures for generating reports and tables in the LEMON parser generator.
3195 /* Generate a filename with the given suffix. Space to hold the
3196 ** name comes from malloc() and must be freed by the calling
3199 PRIVATE
char *file_makename(struct lemon
*lemp
, const char *suffix
)
3203 char *filename
= lemp
->filename
;
3207 cp
= strrchr(filename
, '/');
3208 if( cp
) filename
= cp
+ 1;
3210 sz
= lemonStrlen(filename
);
3211 sz
+= lemonStrlen(suffix
);
3212 if( outputDir
) sz
+= lemonStrlen(outputDir
) + 1;
3214 name
= (char*)malloc( sz
);
3216 fprintf(stderr
,"Can't allocate space for a filename.\n");
3221 lemon_strcpy(name
, outputDir
);
3222 lemon_strcat(name
, "/");
3224 lemon_strcat(name
,filename
);
3225 cp
= strrchr(name
,'.');
3227 lemon_strcat(name
,suffix
);
3231 /* Open a file with a name based on the name of the input file,
3232 ** but with a different (specified) suffix, and return a pointer
3234 PRIVATE
FILE *file_open(
3241 if( lemp
->outname
) free(lemp
->outname
);
3242 lemp
->outname
= file_makename(lemp
, suffix
);
3243 fp
= fopen(lemp
->outname
,mode
);
3244 if( fp
==0 && *mode
=='w' ){
3245 fprintf(stderr
,"Can't open file \"%s\".\n",lemp
->outname
);
3252 /* Print the text of a rule
3254 void rule_print(FILE *out
, struct rule
*rp
){
3256 fprintf(out
, "%s",rp
->lhs
->name
);
3257 /* if( rp->lhsalias ) fprintf(out,"(%s)",rp->lhsalias); */
3258 fprintf(out
," ::=");
3259 for(i
=0; i
<rp
->nrhs
; i
++){
3260 struct symbol
*sp
= rp
->rhs
[i
];
3261 if( sp
->type
==MULTITERMINAL
){
3262 fprintf(out
," %s", sp
->subsym
[0]->name
);
3263 for(j
=1; j
<sp
->nsubsym
; j
++){
3264 fprintf(out
,"|%s", sp
->subsym
[j
]->name
);
3267 fprintf(out
," %s", sp
->name
);
3269 /* if( rp->rhsalias[i] ) fprintf(out,"(%s)",rp->rhsalias[i]); */
3273 /* Duplicate the input file without comments and without actions
3275 void Reprint(struct lemon
*lemp
)
3279 int i
, j
, maxlen
, len
, ncolumns
, skip
;
3280 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp
->filename
);
3282 for(i
=0; i
<lemp
->nsymbol
; i
++){
3283 sp
= lemp
->symbols
[i
];
3284 len
= lemonStrlen(sp
->name
);
3285 if( len
>maxlen
) maxlen
= len
;
3287 ncolumns
= 76/(maxlen
+5);
3288 if( ncolumns
<1 ) ncolumns
= 1;
3289 skip
= (lemp
->nsymbol
+ ncolumns
- 1)/ncolumns
;
3290 for(i
=0; i
<skip
; i
++){
3292 for(j
=i
; j
<lemp
->nsymbol
; j
+=skip
){
3293 sp
= lemp
->symbols
[j
];
3294 assert( sp
->index
==j
);
3295 printf(" %3d %-*.*s",j
,maxlen
,maxlen
,sp
->name
);
3299 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3300 rule_print(stdout
, rp
);
3302 if( rp
->precsym
) printf(" [%s]",rp
->precsym
->name
);
3303 /* if( rp->code ) printf("\n %s",rp->code); */
3308 /* Print a single rule.
3310 void RulePrint(FILE *fp
, struct rule
*rp
, int iCursor
){
3313 fprintf(fp
,"%s ::=",rp
->lhs
->name
);
3314 for(i
=0; i
<=rp
->nrhs
; i
++){
3315 if( i
==iCursor
) fprintf(fp
," *");
3316 if( i
==rp
->nrhs
) break;
3318 if( sp
->type
==MULTITERMINAL
){
3319 fprintf(fp
," %s", sp
->subsym
[0]->name
);
3320 for(j
=1; j
<sp
->nsubsym
; j
++){
3321 fprintf(fp
,"|%s",sp
->subsym
[j
]->name
);
3324 fprintf(fp
," %s", sp
->name
);
3329 /* Print the rule for a configuration.
3331 void ConfigPrint(FILE *fp
, struct config
*cfp
){
3332 RulePrint(fp
, cfp
->rp
, cfp
->dot
);
3338 PRIVATE
void SetPrint(out
,set
,lemp
)
3346 fprintf(out
,"%12s[","");
3347 for(i
=0; i
<lemp
->nterminal
; i
++){
3348 if( SetFind(set
,i
) ){
3349 fprintf(out
,"%s%s",spacer
,lemp
->symbols
[i
]->name
);
3356 /* Print a plink chain */
3357 PRIVATE
void PlinkPrint(out
,plp
,tag
)
3363 fprintf(out
,"%12s%s (state %2d) ","",tag
,plp
->cfp
->stp
->statenum
);
3364 ConfigPrint(out
,plp
->cfp
);
3371 /* Print an action to the given file descriptor. Return FALSE if
3372 ** nothing was actually printed.
3375 struct action
*ap
, /* The action to print */
3376 FILE *fp
, /* Print the action here */
3377 int indent
/* Indent by this amount */
3382 struct state
*stp
= ap
->x
.stp
;
3383 fprintf(fp
,"%*s shift %-7d",indent
,ap
->sp
->name
,stp
->statenum
);
3387 struct rule
*rp
= ap
->x
.rp
;
3388 fprintf(fp
,"%*s reduce %-7d",indent
,ap
->sp
->name
,rp
->iRule
);
3389 RulePrint(fp
, rp
, -1);
3393 struct rule
*rp
= ap
->x
.rp
;
3394 fprintf(fp
,"%*s shift-reduce %-7d",indent
,ap
->sp
->name
,rp
->iRule
);
3395 RulePrint(fp
, rp
, -1);
3399 fprintf(fp
,"%*s accept",indent
,ap
->sp
->name
);
3402 fprintf(fp
,"%*s error",indent
,ap
->sp
->name
);
3406 fprintf(fp
,"%*s reduce %-7d ** Parsing conflict **",
3407 indent
,ap
->sp
->name
,ap
->x
.rp
->iRule
);
3410 fprintf(fp
,"%*s shift %-7d ** Parsing conflict **",
3411 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3414 if( showPrecedenceConflict
){
3415 fprintf(fp
,"%*s shift %-7d -- dropped by precedence",
3416 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3422 if( showPrecedenceConflict
){
3423 fprintf(fp
,"%*s reduce %-7d -- dropped by precedence",
3424 indent
,ap
->sp
->name
,ap
->x
.rp
->iRule
);
3433 if( result
&& ap
->spOpt
){
3434 fprintf(fp
," /* because %s==%s */", ap
->sp
->name
, ap
->spOpt
->name
);
3439 /* Generate the "*.out" log file */
3440 void ReportOutput(struct lemon
*lemp
)
3449 fp
= file_open(lemp
,".out","wb");
3451 for(i
=0; i
<lemp
->nxstate
; i
++){
3452 stp
= lemp
->sorted
[i
];
3453 fprintf(fp
,"State %d:\n",stp
->statenum
);
3454 if( lemp
->basisflag
) cfp
=stp
->bp
;
3458 if( cfp
->dot
==cfp
->rp
->nrhs
){
3459 lemon_sprintf(buf
,"(%d)",cfp
->rp
->iRule
);
3460 fprintf(fp
," %5s ",buf
);
3464 ConfigPrint(fp
,cfp
);
3467 SetPrint(fp
,cfp
->fws
,lemp
);
3468 PlinkPrint(fp
,cfp
->fplp
,"To ");
3469 PlinkPrint(fp
,cfp
->bplp
,"From");
3471 if( lemp
->basisflag
) cfp
=cfp
->bp
;
3475 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3476 if( PrintAction(ap
,fp
,30) ) fprintf(fp
,"\n");
3480 fprintf(fp
, "----------------------------------------------------\n");
3481 fprintf(fp
, "Symbols:\n");
3482 fprintf(fp
, "The first-set of non-terminals is shown after the name.\n\n");
3483 for(i
=0; i
<lemp
->nsymbol
; i
++){
3487 sp
= lemp
->symbols
[i
];
3488 fprintf(fp
, " %3d: %s", i
, sp
->name
);
3489 if( sp
->type
==NONTERMINAL
){
3492 fprintf(fp
, " <lambda>");
3494 for(j
=0; j
<lemp
->nterminal
; j
++){
3495 if( sp
->firstset
&& SetFind(sp
->firstset
, j
) ){
3496 fprintf(fp
, " %s", lemp
->symbols
[j
]->name
);
3500 if( sp
->prec
>=0 ) fprintf(fp
," (precedence=%d)", sp
->prec
);
3503 fprintf(fp
, "----------------------------------------------------\n");
3504 fprintf(fp
, "Syntax-only Symbols:\n");
3505 fprintf(fp
, "The following symbols never carry semantic content.\n\n");
3506 for(i
=n
=0; i
<lemp
->nsymbol
; i
++){
3508 struct symbol
*sp
= lemp
->symbols
[i
];
3509 if( sp
->bContent
) continue;
3510 w
= (int)strlen(sp
->name
);
3511 if( n
>0 && n
+w
>75 ){
3519 fprintf(fp
, "%s", sp
->name
);
3522 if( n
>0 ) fprintf(fp
, "\n");
3523 fprintf(fp
, "----------------------------------------------------\n");
3524 fprintf(fp
, "Rules:\n");
3525 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
3526 fprintf(fp
, "%4d: ", rp
->iRule
);
3530 fprintf(fp
," [%s precedence=%d]",
3531 rp
->precsym
->name
, rp
->precsym
->prec
);
3539 /* Search for the file "name" which is in the same directory as
3540 ** the executable */
3541 PRIVATE
char *pathsearch(char *argv0
, char *name
, int modemask
)
3543 const char *pathlist
;
3544 char *pathbufptr
= 0;
3550 cp
= strrchr(argv0
,'\\');
3552 cp
= strrchr(argv0
,'/');
3557 path
= (char *)malloc( lemonStrlen(argv0
) + lemonStrlen(name
) + 2 );
3558 if( path
) lemon_sprintf(path
,"%s/%s",argv0
,name
);
3561 pathlist
= getenv("PATH");
3562 if( pathlist
==0 ) pathlist
= ".:/bin:/usr/bin";
3563 pathbuf
= (char *) malloc( lemonStrlen(pathlist
) + 1 );
3564 path
= (char *)malloc( lemonStrlen(pathlist
)+lemonStrlen(name
)+2 );
3565 if( (pathbuf
!= 0) && (path
!=0) ){
3566 pathbufptr
= pathbuf
;
3567 lemon_strcpy(pathbuf
, pathlist
);
3569 cp
= strchr(pathbuf
,':');
3570 if( cp
==0 ) cp
= &pathbuf
[lemonStrlen(pathbuf
)];
3573 lemon_sprintf(path
,"%s/%s",pathbuf
,name
);
3575 if( c
==0 ) pathbuf
[0] = 0;
3576 else pathbuf
= &cp
[1];
3577 if( access(path
,modemask
)==0 ) break;
3585 /* Given an action, compute the integer value for that action
3586 ** which is to be put in the action table of the generated machine.
3587 ** Return negative if no action should be generated.
3589 PRIVATE
int compute_action(struct lemon
*lemp
, struct action
*ap
)
3593 case SHIFT
: act
= ap
->x
.stp
->statenum
; break;
3595 /* Since a SHIFT is inherient after a prior REDUCE, convert any
3596 ** SHIFTREDUCE action with a nonterminal on the LHS into a simple
3597 ** REDUCE action: */
3598 if( ap
->sp
->index
>=lemp
->nterminal
3599 && (lemp
->errsym
==0 || ap
->sp
->index
!=lemp
->errsym
->index
)
3601 act
= lemp
->minReduce
+ ap
->x
.rp
->iRule
;
3603 act
= lemp
->minShiftReduce
+ ap
->x
.rp
->iRule
;
3607 case REDUCE
: act
= lemp
->minReduce
+ ap
->x
.rp
->iRule
; break;
3608 case ERROR
: act
= lemp
->errAction
; break;
3609 case ACCEPT
: act
= lemp
->accAction
; break;
3610 default: act
= -1; break;
3615 #define LINESIZE 1000
3616 /* The next cluster of routines are for reading the template file
3617 ** and writing the results to the generated parser */
3618 /* The first function transfers data from "in" to "out" until
3619 ** a line is seen which begins with "%%". The line number is
3622 ** if name!=0, then any word that begin with "Parse" is changed to
3623 ** begin with *name instead.
3625 PRIVATE
void tplt_xfer(char *name
, FILE *in
, FILE *out
, int *lineno
)
3628 char line
[LINESIZE
];
3629 while( fgets(line
,LINESIZE
,in
) && (line
[0]!='%' || line
[1]!='%') ){
3633 for(i
=0; line
[i
]; i
++){
3634 if( line
[i
]=='P' && strncmp(&line
[i
],"Parse",5)==0
3635 && (i
==0 || !ISALPHA(line
[i
-1]))
3637 if( i
>iStart
) fprintf(out
,"%.*s",i
-iStart
,&line
[iStart
]);
3638 fprintf(out
,"%s",name
);
3644 fprintf(out
,"%s",&line
[iStart
]);
3648 /* Skip forward past the header of the template file to the first "%%"
3650 PRIVATE
void tplt_skip_header(FILE *in
, int *lineno
)
3652 char line
[LINESIZE
];
3653 while( fgets(line
,LINESIZE
,in
) && (line
[0]!='%' || line
[1]!='%') ){
3658 /* The next function finds the template file and opens it, returning
3659 ** a pointer to the opened file. */
3660 PRIVATE
FILE *tplt_open(struct lemon
*lemp
)
3662 static char templatename
[] = "lempar.c";
3669 /* first, see if user specified a template filename on the command line. */
3670 if (user_templatename
!= 0) {
3671 if( access(user_templatename
,004)==-1 ){
3672 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3677 in
= fopen(user_templatename
,"rb");
3679 fprintf(stderr
,"Can't open the template file \"%s\".\n",
3687 cp
= strrchr(lemp
->filename
,'.');
3689 lemon_sprintf(buf
,"%.*s.lt",(int)(cp
-lemp
->filename
),lemp
->filename
);
3691 lemon_sprintf(buf
,"%s.lt",lemp
->filename
);
3693 if( access(buf
,004)==0 ){
3695 }else if( access(templatename
,004)==0 ){
3696 tpltname
= templatename
;
3698 toFree
= tpltname
= pathsearch(lemp
->argv
[0],templatename
,0);
3701 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3706 in
= fopen(tpltname
,"rb");
3708 fprintf(stderr
,"Can't open the template file \"%s\".\n",tpltname
);
3715 /* Print a #line directive line to the output file. */
3716 PRIVATE
void tplt_linedir(FILE *out
, int lineno
, char *filename
)
3718 fprintf(out
,"#line %d \"",lineno
);
3720 if( *filename
== '\\' ) putc('\\',out
);
3721 putc(*filename
,out
);
3724 fprintf(out
,"\"\n");
3727 /* Print a string to the file and keep the linenumber up to date */
3728 PRIVATE
void tplt_print(FILE *out
, struct lemon
*lemp
, char *str
, int *lineno
)
3730 if( str
==0 ) return;
3733 if( *str
=='\n' ) (*lineno
)++;
3736 if( str
[-1]!='\n' ){
3740 if (!lemp
->nolinenosflag
) {
3741 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3747 ** The following routine emits code for the destructor for the
3750 void emit_destructor_code(
3758 if( sp
->type
==TERMINAL
){
3759 cp
= lemp
->tokendest
;
3761 fprintf(out
,"{\n"); (*lineno
)++;
3762 }else if( sp
->destructor
){
3763 cp
= sp
->destructor
;
3764 fprintf(out
,"{\n"); (*lineno
)++;
3765 if( !lemp
->nolinenosflag
){
3767 tplt_linedir(out
,sp
->destLineno
,lemp
->filename
);
3769 }else if( lemp
->vardest
){
3772 fprintf(out
,"{\n"); (*lineno
)++;
3774 assert( 0 ); /* Cannot happen */
3777 if( *cp
=='$' && cp
[1]=='$' ){
3778 fprintf(out
,"(yypminor->yy%d)",sp
->dtnum
);
3782 if( *cp
=='\n' ) (*lineno
)++;
3785 fprintf(out
,"\n"); (*lineno
)++;
3786 if (!lemp
->nolinenosflag
) {
3787 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3789 fprintf(out
,"}\n"); (*lineno
)++;
3794 ** Return TRUE (non-zero) if the given symbol has a destructor.
3796 int has_destructor(struct symbol
*sp
, struct lemon
*lemp
)
3799 if( sp
->type
==TERMINAL
){
3800 ret
= lemp
->tokendest
!=0;
3802 ret
= lemp
->vardest
!=0 || sp
->destructor
!=0;
3808 ** Append text to a dynamically allocated string. If zText is 0 then
3809 ** reset the string to be empty again. Always return the complete text
3810 ** of the string (which is overwritten with each call).
3812 ** n bytes of zText are stored. If n==0 then all of zText up to the first
3813 ** \000 terminator is stored. zText can contain up to two instances of
3814 ** %d. The values of p1 and p2 are written into the first and second
3817 ** If n==-1, then the previous character is overwritten.
3819 PRIVATE
char *append_str(const char *zText
, int n
, int p1
, int p2
){
3820 static char empty
[1] = { 0 };
3822 static int alloced
= 0;
3823 static int used
= 0;
3827 if( used
==0 && z
!=0 ) z
[0] = 0;
3836 n
= lemonStrlen(zText
);
3838 if( (int) (n
+sizeof(zInt
)*2+used
) >= alloced
){
3839 alloced
= n
+ sizeof(zInt
)*2 + used
+ 200;
3840 z
= (char *) realloc(z
, alloced
);
3842 if( z
==0 ) return empty
;
3845 if( c
=='%' && n
>0 && zText
[0]=='d' ){
3846 lemon_sprintf(zInt
, "%d", p1
);
3848 lemon_strcpy(&z
[used
], zInt
);
3849 used
+= lemonStrlen(&z
[used
]);
3853 z
[used
++] = (char)c
;
3861 ** Write and transform the rp->code string so that symbols are expanded.
3862 ** Populate the rp->codePrefix and rp->codeSuffix strings, as appropriate.
3864 ** Return 1 if the expanded code requires that "yylhsminor" local variable
3867 PRIVATE
int translate_code(struct lemon
*lemp
, struct rule
*rp
){
3870 int rc
= 0; /* True if yylhsminor is used */
3871 int dontUseRhs0
= 0; /* If true, use of left-most RHS label is illegal */
3872 const char *zSkip
= 0; /* The zOvwrt comment within rp->code, or NULL */
3873 char lhsused
= 0; /* True if the LHS element has been used */
3874 char lhsdirect
; /* True if LHS writes directly into stack */
3875 char used
[MAXRHS
]; /* True for each RHS element which is used */
3876 char zLhs
[50]; /* Convert the LHS symbol into this string */
3877 char zOvwrt
[900]; /* Comment that to allow LHS to overwrite RHS */
3879 for(i
=0; i
<rp
->nrhs
; i
++) used
[i
] = 0;
3883 static char newlinestr
[2] = { '\n', '\0' };
3884 rp
->code
= newlinestr
;
3885 rp
->line
= rp
->ruleline
;
3893 /* If there are no RHS symbols, then writing directly to the LHS is ok */
3895 }else if( rp
->rhsalias
[0]==0 ){
3896 /* The left-most RHS symbol has no value. LHS direct is ok. But
3897 ** we have to call the destructor on the RHS symbol first. */
3899 if( has_destructor(rp
->rhs
[0],lemp
) ){
3900 append_str(0,0,0,0);
3901 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3902 rp
->rhs
[0]->index
,1-rp
->nrhs
);
3903 rp
->codePrefix
= Strsafe(append_str(0,0,0,0));
3906 }else if( rp
->lhsalias
==0 ){
3907 /* There is no LHS value symbol. */
3909 }else if( strcmp(rp
->lhsalias
,rp
->rhsalias
[0])==0 ){
3910 /* The LHS symbol and the left-most RHS symbol are the same, so
3911 ** direct writing is allowed */
3915 if( rp
->lhs
->dtnum
!=rp
->rhs
[0]->dtnum
){
3916 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3917 "%s(%s) and %s(%s) share the same label but have "
3918 "different datatypes.",
3919 rp
->lhs
->name
, rp
->lhsalias
, rp
->rhs
[0]->name
, rp
->rhsalias
[0]);
3923 lemon_sprintf(zOvwrt
, "/*%s-overwrites-%s*/",
3924 rp
->lhsalias
, rp
->rhsalias
[0]);
3925 zSkip
= strstr(rp
->code
, zOvwrt
);
3927 /* The code contains a special comment that indicates that it is safe
3928 ** for the LHS label to overwrite left-most RHS label. */
3935 sprintf(zLhs
, "yymsp[%d].minor.yy%d",1-rp
->nrhs
,rp
->lhs
->dtnum
);
3938 sprintf(zLhs
, "yylhsminor.yy%d",rp
->lhs
->dtnum
);
3941 append_str(0,0,0,0);
3943 /* This const cast is wrong but harmless, if we're careful. */
3944 for(cp
=(char *)rp
->code
; *cp
; cp
++){
3946 append_str(zOvwrt
,0,0,0);
3947 cp
+= lemonStrlen(zOvwrt
)-1;
3951 if( ISALPHA(*cp
) && (cp
==rp
->code
|| (!ISALNUM(cp
[-1]) && cp
[-1]!='_')) ){
3953 for(xp
= &cp
[1]; ISALNUM(*xp
) || *xp
=='_'; xp
++);
3956 if( rp
->lhsalias
&& strcmp(cp
,rp
->lhsalias
)==0 ){
3957 append_str(zLhs
,0,0,0);
3961 for(i
=0; i
<rp
->nrhs
; i
++){
3962 if( rp
->rhsalias
[i
] && strcmp(cp
,rp
->rhsalias
[i
])==0 ){
3963 if( i
==0 && dontUseRhs0
){
3964 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3965 "Label %s used after '%s'.",
3966 rp
->rhsalias
[0], zOvwrt
);
3968 }else if( cp
!=rp
->code
&& cp
[-1]=='@' ){
3969 /* If the argument is of the form @X then substituted
3970 ** the token number of X, not the value of X */
3971 append_str("yymsp[%d].major",-1,i
-rp
->nrhs
+1,0);
3973 struct symbol
*sp
= rp
->rhs
[i
];
3975 if( sp
->type
==MULTITERMINAL
){
3976 dtnum
= sp
->subsym
[0]->dtnum
;
3980 append_str("yymsp[%d].minor.yy%d",0,i
-rp
->nrhs
+1, dtnum
);
3990 append_str(cp
, 1, 0, 0);
3993 /* Main code generation completed */
3994 cp
= append_str(0,0,0,0);
3995 if( cp
&& cp
[0] ) rp
->code
= Strsafe(cp
);
3996 append_str(0,0,0,0);
3998 /* Check to make sure the LHS has been used */
3999 if( rp
->lhsalias
&& !lhsused
){
4000 ErrorMsg(lemp
->filename
,rp
->ruleline
,
4001 "Label \"%s\" for \"%s(%s)\" is never used.",
4002 rp
->lhsalias
,rp
->lhs
->name
,rp
->lhsalias
);
4006 /* Generate destructor code for RHS minor values which are not referenced.
4007 ** Generate error messages for unused labels and duplicate labels.
4009 for(i
=0; i
<rp
->nrhs
; i
++){
4010 if( rp
->rhsalias
[i
] ){
4013 if( rp
->lhsalias
&& strcmp(rp
->lhsalias
,rp
->rhsalias
[i
])==0 ){
4014 ErrorMsg(lemp
->filename
,rp
->ruleline
,
4015 "%s(%s) has the same label as the LHS but is not the left-most "
4016 "symbol on the RHS.",
4017 rp
->rhs
[i
]->name
, rp
->rhsalias
[i
]);
4021 if( rp
->rhsalias
[j
] && strcmp(rp
->rhsalias
[j
],rp
->rhsalias
[i
])==0 ){
4022 ErrorMsg(lemp
->filename
,rp
->ruleline
,
4023 "Label %s used for multiple symbols on the RHS of a rule.",
4031 ErrorMsg(lemp
->filename
,rp
->ruleline
,
4032 "Label %s for \"%s(%s)\" is never used.",
4033 rp
->rhsalias
[i
],rp
->rhs
[i
]->name
,rp
->rhsalias
[i
]);
4036 }else if( i
>0 && has_destructor(rp
->rhs
[i
],lemp
) ){
4037 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
4038 rp
->rhs
[i
]->index
,i
-rp
->nrhs
+1);
4042 /* If unable to write LHS values directly into the stack, write the
4043 ** saved LHS value now. */
4045 append_str(" yymsp[%d].minor.yy%d = ", 0, 1-rp
->nrhs
, rp
->lhs
->dtnum
);
4046 append_str(zLhs
, 0, 0, 0);
4047 append_str(";\n", 0, 0, 0);
4050 /* Suffix code generation complete */
4051 cp
= append_str(0,0,0,0);
4053 rp
->codeSuffix
= Strsafe(cp
);
4061 ** Generate code which executes when the rule "rp" is reduced. Write
4062 ** the code to "out". Make sure lineno stays up-to-date.
4064 PRIVATE
void emit_code(
4072 /* Setup code prior to the #line directive */
4073 if( rp
->codePrefix
&& rp
->codePrefix
[0] ){
4074 fprintf(out
, "{%s", rp
->codePrefix
);
4075 for(cp
=rp
->codePrefix
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
4078 /* Generate code to do the reduce action */
4080 if( !lemp
->nolinenosflag
){
4082 tplt_linedir(out
,rp
->line
,lemp
->filename
);
4084 fprintf(out
,"{%s",rp
->code
);
4085 for(cp
=rp
->code
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
4086 fprintf(out
,"}\n"); (*lineno
)++;
4087 if( !lemp
->nolinenosflag
){
4089 tplt_linedir(out
,*lineno
,lemp
->outname
);
4093 /* Generate breakdown code that occurs after the #line directive */
4094 if( rp
->codeSuffix
&& rp
->codeSuffix
[0] ){
4095 fprintf(out
, "%s", rp
->codeSuffix
);
4096 for(cp
=rp
->codeSuffix
; *cp
; cp
++){ if( *cp
=='\n' ) (*lineno
)++; }
4099 if( rp
->codePrefix
){
4100 fprintf(out
, "}\n"); (*lineno
)++;
4107 ** Print the definition of the union used for the parser's data stack.
4108 ** This union contains fields for every possible data type for tokens
4109 ** and nonterminals. In the process of computing and printing this
4110 ** union, also set the ".dtnum" field of every terminal and nonterminal
4113 void print_stack_union(
4114 FILE *out
, /* The output stream */
4115 struct lemon
*lemp
, /* The main info structure for this parser */
4116 int *plineno
, /* Pointer to the line number */
4117 int mhflag
/* True if generating makeheaders output */
4119 int lineno
; /* The line number of the output */
4120 char **types
; /* A hash table of datatypes */
4121 int arraysize
; /* Size of the "types" array */
4122 int maxdtlength
; /* Maximum length of any ".datatype" field. */
4123 char *stddt
; /* Standardized name for a datatype */
4124 int i
,j
; /* Loop counters */
4125 unsigned hash
; /* For hashing the name of a type */
4126 const char *name
; /* Name of the parser */
4128 /* Allocate and initialize types[] and allocate stddt[] */
4129 arraysize
= lemp
->nsymbol
* 2;
4130 types
= (char**)calloc( arraysize
, sizeof(char*) );
4132 fprintf(stderr
,"Out of memory.\n");
4135 for(i
=0; i
<arraysize
; i
++) types
[i
] = 0;
4137 if( lemp
->vartype
){
4138 maxdtlength
= lemonStrlen(lemp
->vartype
);
4140 for(i
=0; i
<lemp
->nsymbol
; i
++){
4142 struct symbol
*sp
= lemp
->symbols
[i
];
4143 if( sp
->datatype
==0 ) continue;
4144 len
= lemonStrlen(sp
->datatype
);
4145 if( len
>maxdtlength
) maxdtlength
= len
;
4147 stddt
= (char*)malloc( maxdtlength
*2 + 1 );
4149 fprintf(stderr
,"Out of memory.\n");
4153 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
4154 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
4155 ** used for terminal symbols. If there is no %default_type defined then
4156 ** 0 is also used as the .dtnum value for nonterminals which do not specify
4157 ** a datatype using the %type directive.
4159 for(i
=0; i
<lemp
->nsymbol
; i
++){
4160 struct symbol
*sp
= lemp
->symbols
[i
];
4162 if( sp
==lemp
->errsym
){
4163 sp
->dtnum
= arraysize
+1;
4166 if( sp
->type
!=NONTERMINAL
|| (sp
->datatype
==0 && lemp
->vartype
==0) ){
4171 if( cp
==0 ) cp
= lemp
->vartype
;
4173 while( ISSPACE(*cp
) ) cp
++;
4174 while( *cp
) stddt
[j
++] = *cp
++;
4175 while( j
>0 && ISSPACE(stddt
[j
-1]) ) j
--;
4177 if( lemp
->tokentype
&& strcmp(stddt
, lemp
->tokentype
)==0 ){
4182 for(j
=0; stddt
[j
]; j
++){
4183 hash
= hash
*53 + stddt
[j
];
4185 hash
= (hash
& 0x7fffffff)%arraysize
;
4186 while( types
[hash
] ){
4187 if( strcmp(types
[hash
],stddt
)==0 ){
4188 sp
->dtnum
= hash
+ 1;
4192 if( hash
>=(unsigned)arraysize
) hash
= 0;
4194 if( types
[hash
]==0 ){
4195 sp
->dtnum
= hash
+ 1;
4196 types
[hash
] = (char*)malloc( lemonStrlen(stddt
)+1 );
4197 if( types
[hash
]==0 ){
4198 fprintf(stderr
,"Out of memory.\n");
4201 lemon_strcpy(types
[hash
],stddt
);
4205 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
4206 name
= lemp
->name
? lemp
->name
: "Parse";
4208 if( mhflag
){ fprintf(out
,"#if INTERFACE\n"); lineno
++; }
4209 fprintf(out
,"#define %sTOKENTYPE %s\n",name
,
4210 lemp
->tokentype
?lemp
->tokentype
:"void*"); lineno
++;
4211 if( mhflag
){ fprintf(out
,"#endif\n"); lineno
++; }
4212 fprintf(out
,"typedef union {\n"); lineno
++;
4213 fprintf(out
," int yyinit;\n"); lineno
++;
4214 fprintf(out
," %sTOKENTYPE yy0;\n",name
); lineno
++;
4215 for(i
=0; i
<arraysize
; i
++){
4216 if( types
[i
]==0 ) continue;
4217 fprintf(out
," %s yy%d;\n",types
[i
],i
+1); lineno
++;
4220 if( lemp
->errsym
&& lemp
->errsym
->useCnt
){
4221 fprintf(out
," int yy%d;\n",lemp
->errsym
->dtnum
); lineno
++;
4225 fprintf(out
,"} YYMINORTYPE;\n"); lineno
++;
4230 ** Return the name of a C datatype able to represent values between
4231 ** lwr and upr, inclusive. If pnByte!=NULL then also write the sizeof
4232 ** for that type (1, 2, or 4) into *pnByte.
4234 static const char *minimum_size_type(int lwr
, int upr
, int *pnByte
){
4235 const char *zType
= "int";
4239 zType
= "unsigned char";
4241 }else if( upr
<65535 ){
4242 zType
= "unsigned short int";
4245 zType
= "unsigned int";
4248 }else if( lwr
>=-127 && upr
<=127 ){
4249 zType
= "signed char";
4251 }else if( lwr
>=-32767 && upr
<32767 ){
4255 if( pnByte
) *pnByte
= nByte
;
4260 ** Each state contains a set of token transaction and a set of
4261 ** nonterminal transactions. Each of these sets makes an instance
4262 ** of the following structure. An array of these structures is used
4263 ** to order the creation of entries in the yy_action[] table.
4266 struct state
*stp
; /* A pointer to a state */
4267 int isTkn
; /* True to use tokens. False for non-terminals */
4268 int nAction
; /* Number of actions */
4269 int iOrder
; /* Original order of action sets */
4273 ** Compare to axset structures for sorting purposes
4275 static int axset_compare(const void *a
, const void *b
){
4276 struct axset
*p1
= (struct axset
*)a
;
4277 struct axset
*p2
= (struct axset
*)b
;
4279 c
= p2
->nAction
- p1
->nAction
;
4281 c
= p1
->iOrder
- p2
->iOrder
;
4283 assert( c
!=0 || p1
==p2
);
4288 ** Write text on "out" that describes the rule "rp".
4290 static void writeRuleText(FILE *out
, struct rule
*rp
){
4292 fprintf(out
,"%s ::=", rp
->lhs
->name
);
4293 for(j
=0; j
<rp
->nrhs
; j
++){
4294 struct symbol
*sp
= rp
->rhs
[j
];
4295 if( sp
->type
!=MULTITERMINAL
){
4296 fprintf(out
," %s", sp
->name
);
4299 fprintf(out
," %s", sp
->subsym
[0]->name
);
4300 for(k
=1; k
<sp
->nsubsym
; k
++){
4301 fprintf(out
,"|%s",sp
->subsym
[k
]->name
);
4308 /* Generate C source code for the parser */
4311 int mhflag
, /* Output in makeheaders format if true */
4312 int sqlFlag
/* Generate the *.sql file too */
4314 FILE *out
, *in
, *sql
;
4319 struct acttab
*pActtab
;
4320 int i
, j
, n
, sz
, mn
, mx
;
4322 int szActionType
; /* sizeof(YYACTIONTYPE) */
4323 int szCodeType
; /* sizeof(YYCODETYPE) */
4325 int mnTknOfst
, mxTknOfst
;
4326 int mnNtOfst
, mxNtOfst
;
4330 lemp
->minShiftReduce
= lemp
->nstate
;
4331 lemp
->errAction
= lemp
->minShiftReduce
+ lemp
->nrule
;
4332 lemp
->accAction
= lemp
->errAction
+ 1;
4333 lemp
->noAction
= lemp
->accAction
+ 1;
4334 lemp
->minReduce
= lemp
->noAction
+ 1;
4335 lemp
->maxAction
= lemp
->minReduce
+ lemp
->nrule
;
4337 in
= tplt_open(lemp
);
4339 out
= file_open(lemp
,".c","wb");
4347 sql
= file_open(lemp
, ".sql", "wb");
4355 "CREATE TABLE symbol(\n"
4356 " id INTEGER PRIMARY KEY,\n"
4357 " name TEXT NOT NULL,\n"
4358 " isTerminal BOOLEAN NOT NULL,\n"
4359 " fallback INTEGER REFERENCES symbol"
4360 " DEFERRABLE INITIALLY DEFERRED\n"
4363 for(i
=0; i
<lemp
->nsymbol
; i
++){
4365 "INSERT INTO symbol(id,name,isTerminal,fallback)"
4366 "VALUES(%d,'%s',%s",
4367 i
, lemp
->symbols
[i
]->name
,
4368 i
<lemp
->nterminal
? "TRUE" : "FALSE"
4370 if( lemp
->symbols
[i
]->fallback
){
4371 fprintf(sql
, ",%d);\n", lemp
->symbols
[i
]->fallback
->index
);
4373 fprintf(sql
, ",NULL);\n");
4377 "CREATE TABLE rule(\n"
4378 " ruleid INTEGER PRIMARY KEY,\n"
4379 " lhs INTEGER REFERENCES symbol(id),\n"
4382 "CREATE TABLE rulerhs(\n"
4383 " ruleid INTEGER REFERENCES rule(ruleid),\n"
4385 " sym INTEGER REFERENCES symbol(id)\n"
4388 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4389 assert( i
==rp
->iRule
);
4391 "INSERT INTO rule(ruleid,lhs,txt)VALUES(%d,%d,'",
4392 rp
->iRule
, rp
->lhs
->index
4394 writeRuleText(sql
, rp
);
4395 fprintf(sql
,"');\n");
4396 for(j
=0; j
<rp
->nrhs
; j
++){
4397 struct symbol
*sp
= rp
->rhs
[j
];
4398 if( sp
->type
!=MULTITERMINAL
){
4400 "INSERT INTO rulerhs(ruleid,pos,sym)VALUES(%d,%d,%d);\n",
4405 for(k
=0; k
<sp
->nsubsym
; k
++){
4407 "INSERT INTO rulerhs(ruleid,pos,sym)VALUES(%d,%d,%d);\n",
4408 i
,j
,sp
->subsym
[k
]->index
4414 fprintf(sql
, "COMMIT;\n");
4419 "/* This file is automatically generated by Lemon from input grammar\n"
4420 "** source file \"%s\"", lemp
->filename
); lineno
++;
4421 if( nDefineUsed
==0 ){
4422 fprintf(out
, ".\n*/\n"); lineno
+= 2;
4424 fprintf(out
, " with these options:\n**\n"); lineno
+= 2;
4425 for(i
=0; i
<nDefine
; i
++){
4426 if( !bDefineUsed
[i
] ) continue;
4427 fprintf(out
, "** -D%s\n", azDefine
[i
]); lineno
++;
4429 fprintf(out
, "*/\n"); lineno
++;
4432 /* The first %include directive begins with a C-language comment,
4433 ** then skip over the header comment of the template file
4435 if( lemp
->include
==0 ) lemp
->include
= "";
4436 for(i
=0; ISSPACE(lemp
->include
[i
]); i
++){
4437 if( lemp
->include
[i
]=='\n' ){
4438 lemp
->include
+= i
+1;
4442 if( lemp
->include
[0]=='/' ){
4443 tplt_skip_header(in
,&lineno
);
4445 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4448 /* Generate the include code, if any */
4449 tplt_print(out
,lemp
,lemp
->include
,&lineno
);
4451 char *incName
= file_makename(lemp
, ".h");
4452 fprintf(out
,"#include \"%s\"\n", incName
); lineno
++;
4455 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4457 /* Generate #defines for all tokens */
4458 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
4461 fprintf(out
,"#if INTERFACE\n"); lineno
++;
4463 fprintf(out
,"#ifndef %s%s\n", prefix
, lemp
->symbols
[1]->name
);
4465 for(i
=1; i
<lemp
->nterminal
; i
++){
4466 fprintf(out
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
4469 fprintf(out
,"#endif\n"); lineno
++;
4470 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4472 /* Generate the defines */
4473 fprintf(out
,"#define YYCODETYPE %s\n",
4474 minimum_size_type(0, lemp
->nsymbol
, &szCodeType
)); lineno
++;
4475 fprintf(out
,"#define YYNOCODE %d\n",lemp
->nsymbol
); lineno
++;
4476 fprintf(out
,"#define YYACTIONTYPE %s\n",
4477 minimum_size_type(0,lemp
->maxAction
,&szActionType
)); lineno
++;
4478 if( lemp
->wildcard
){
4479 fprintf(out
,"#define YYWILDCARD %d\n",
4480 lemp
->wildcard
->index
); lineno
++;
4482 print_stack_union(out
,lemp
,&lineno
,mhflag
);
4483 fprintf(out
, "#ifndef YYSTACKDEPTH\n"); lineno
++;
4484 if( lemp
->stacksize
){
4485 fprintf(out
,"#define YYSTACKDEPTH %s\n",lemp
->stacksize
); lineno
++;
4487 fprintf(out
,"#define YYSTACKDEPTH 100\n"); lineno
++;
4489 fprintf(out
, "#endif\n"); lineno
++;
4491 fprintf(out
,"#if INTERFACE\n"); lineno
++;
4493 name
= lemp
->name
? lemp
->name
: "Parse";
4494 if( lemp
->arg
&& lemp
->arg
[0] ){
4495 i
= lemonStrlen(lemp
->arg
);
4496 while( i
>=1 && ISSPACE(lemp
->arg
[i
-1]) ) i
--;
4497 while( i
>=1 && (ISALNUM(lemp
->arg
[i
-1]) || lemp
->arg
[i
-1]=='_') ) i
--;
4498 fprintf(out
,"#define %sARG_SDECL %s;\n",name
,lemp
->arg
); lineno
++;
4499 fprintf(out
,"#define %sARG_PDECL ,%s\n",name
,lemp
->arg
); lineno
++;
4500 fprintf(out
,"#define %sARG_PARAM ,%s\n",name
,&lemp
->arg
[i
]); lineno
++;
4501 fprintf(out
,"#define %sARG_FETCH %s=yypParser->%s;\n",
4502 name
,lemp
->arg
,&lemp
->arg
[i
]); lineno
++;
4503 fprintf(out
,"#define %sARG_STORE yypParser->%s=%s;\n",
4504 name
,&lemp
->arg
[i
],&lemp
->arg
[i
]); lineno
++;
4506 fprintf(out
,"#define %sARG_SDECL\n",name
); lineno
++;
4507 fprintf(out
,"#define %sARG_PDECL\n",name
); lineno
++;
4508 fprintf(out
,"#define %sARG_PARAM\n",name
); lineno
++;
4509 fprintf(out
,"#define %sARG_FETCH\n",name
); lineno
++;
4510 fprintf(out
,"#define %sARG_STORE\n",name
); lineno
++;
4512 if( lemp
->reallocFunc
){
4513 fprintf(out
,"#define YYREALLOC %s\n", lemp
->reallocFunc
); lineno
++;
4515 fprintf(out
,"#define YYREALLOC realloc\n"); lineno
++;
4517 if( lemp
->freeFunc
){
4518 fprintf(out
,"#define YYFREE %s\n", lemp
->freeFunc
); lineno
++;
4520 fprintf(out
,"#define YYFREE free\n"); lineno
++;
4522 if( lemp
->reallocFunc
&& lemp
->freeFunc
){
4523 fprintf(out
,"#define YYDYNSTACK 1\n"); lineno
++;
4525 fprintf(out
,"#define YYDYNSTACK 0\n"); lineno
++;
4527 if( lemp
->ctx
&& lemp
->ctx
[0] ){
4528 i
= lemonStrlen(lemp
->ctx
);
4529 while( i
>=1 && ISSPACE(lemp
->ctx
[i
-1]) ) i
--;
4530 while( i
>=1 && (ISALNUM(lemp
->ctx
[i
-1]) || lemp
->ctx
[i
-1]=='_') ) i
--;
4531 fprintf(out
,"#define %sCTX_SDECL %s;\n",name
,lemp
->ctx
); lineno
++;
4532 fprintf(out
,"#define %sCTX_PDECL ,%s\n",name
,lemp
->ctx
); lineno
++;
4533 fprintf(out
,"#define %sCTX_PARAM ,%s\n",name
,&lemp
->ctx
[i
]); lineno
++;
4534 fprintf(out
,"#define %sCTX_FETCH %s=yypParser->%s;\n",
4535 name
,lemp
->ctx
,&lemp
->ctx
[i
]); lineno
++;
4536 fprintf(out
,"#define %sCTX_STORE yypParser->%s=%s;\n",
4537 name
,&lemp
->ctx
[i
],&lemp
->ctx
[i
]); lineno
++;
4539 fprintf(out
,"#define %sCTX_SDECL\n",name
); lineno
++;
4540 fprintf(out
,"#define %sCTX_PDECL\n",name
); lineno
++;
4541 fprintf(out
,"#define %sCTX_PARAM\n",name
); lineno
++;
4542 fprintf(out
,"#define %sCTX_FETCH\n",name
); lineno
++;
4543 fprintf(out
,"#define %sCTX_STORE\n",name
); lineno
++;
4546 fprintf(out
,"#endif\n"); lineno
++;
4548 if( lemp
->errsym
&& lemp
->errsym
->useCnt
){
4549 fprintf(out
,"#define YYERRORSYMBOL %d\n",lemp
->errsym
->index
); lineno
++;
4550 fprintf(out
,"#define YYERRSYMDT yy%d\n",lemp
->errsym
->dtnum
); lineno
++;
4552 if( lemp
->has_fallback
){
4553 fprintf(out
,"#define YYFALLBACK 1\n"); lineno
++;
4556 /* Compute the action table, but do not output it yet. The action
4557 ** table must be computed before generating the YYNSTATE macro because
4558 ** we need to know how many states can be eliminated.
4560 ax
= (struct axset
*) calloc(lemp
->nxstate
*2, sizeof(ax
[0]));
4562 fprintf(stderr
,"malloc failed\n");
4565 for(i
=0; i
<lemp
->nxstate
; i
++){
4566 stp
= lemp
->sorted
[i
];
4569 ax
[i
*2].nAction
= stp
->nTknAct
;
4570 ax
[i
*2+1].stp
= stp
;
4571 ax
[i
*2+1].isTkn
= 0;
4572 ax
[i
*2+1].nAction
= stp
->nNtAct
;
4574 mxTknOfst
= mnTknOfst
= 0;
4575 mxNtOfst
= mnNtOfst
= 0;
4576 /* In an effort to minimize the action table size, use the heuristic
4577 ** of placing the largest action sets first */
4578 for(i
=0; i
<lemp
->nxstate
*2; i
++) ax
[i
].iOrder
= i
;
4579 qsort(ax
, lemp
->nxstate
*2, sizeof(ax
[0]), axset_compare
);
4580 pActtab
= acttab_alloc(lemp
->nsymbol
, lemp
->nterminal
);
4581 for(i
=0; i
<lemp
->nxstate
*2 && ax
[i
].nAction
>0; i
++){
4584 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4586 if( ap
->sp
->index
>=lemp
->nterminal
) continue;
4587 action
= compute_action(lemp
, ap
);
4588 if( action
<0 ) continue;
4589 acttab_action(pActtab
, ap
->sp
->index
, action
);
4591 stp
->iTknOfst
= acttab_insert(pActtab
, 1);
4592 if( stp
->iTknOfst
<mnTknOfst
) mnTknOfst
= stp
->iTknOfst
;
4593 if( stp
->iTknOfst
>mxTknOfst
) mxTknOfst
= stp
->iTknOfst
;
4595 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4597 if( ap
->sp
->index
<lemp
->nterminal
) continue;
4598 if( ap
->sp
->index
==lemp
->nsymbol
) continue;
4599 action
= compute_action(lemp
, ap
);
4600 if( action
<0 ) continue;
4601 acttab_action(pActtab
, ap
->sp
->index
, action
);
4603 stp
->iNtOfst
= acttab_insert(pActtab
, 0);
4604 if( stp
->iNtOfst
<mnNtOfst
) mnNtOfst
= stp
->iNtOfst
;
4605 if( stp
->iNtOfst
>mxNtOfst
) mxNtOfst
= stp
->iNtOfst
;
4607 #if 0 /* Uncomment for a trace of how the yy_action[] table fills out */
4609 for(jj
=nn
=0; jj
<pActtab
->nAction
; jj
++){
4610 if( pActtab
->aAction
[jj
].action
<0 ) nn
++;
4612 printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n",
4613 i
, stp
->statenum
, ax
[i
].isTkn
? "Token" : "Var ",
4614 ax
[i
].nAction
, pActtab
->nAction
, nn
);
4620 /* Mark rules that are actually used for reduce actions after all
4621 ** optimizations have been applied
4623 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->doesReduce
= LEMON_FALSE
;
4624 for(i
=0; i
<lemp
->nxstate
; i
++){
4625 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
4626 if( ap
->type
==REDUCE
|| ap
->type
==SHIFTREDUCE
){
4627 ap
->x
.rp
->doesReduce
= 1;
4632 /* Finish rendering the constants now that the action table has
4634 fprintf(out
,"#define YYNSTATE %d\n",lemp
->nxstate
); lineno
++;
4635 fprintf(out
,"#define YYNRULE %d\n",lemp
->nrule
); lineno
++;
4636 fprintf(out
,"#define YYNRULE_WITH_ACTION %d\n",lemp
->nruleWithAction
);
4638 fprintf(out
,"#define YYNTOKEN %d\n",lemp
->nterminal
); lineno
++;
4639 fprintf(out
,"#define YY_MAX_SHIFT %d\n",lemp
->nxstate
-1); lineno
++;
4640 i
= lemp
->minShiftReduce
;
4641 fprintf(out
,"#define YY_MIN_SHIFTREDUCE %d\n",i
); lineno
++;
4643 fprintf(out
,"#define YY_MAX_SHIFTREDUCE %d\n", i
-1); lineno
++;
4644 fprintf(out
,"#define YY_ERROR_ACTION %d\n", lemp
->errAction
); lineno
++;
4645 fprintf(out
,"#define YY_ACCEPT_ACTION %d\n", lemp
->accAction
); lineno
++;
4646 fprintf(out
,"#define YY_NO_ACTION %d\n", lemp
->noAction
); lineno
++;
4647 fprintf(out
,"#define YY_MIN_REDUCE %d\n", lemp
->minReduce
); lineno
++;
4648 i
= lemp
->minReduce
+ lemp
->nrule
;
4649 fprintf(out
,"#define YY_MAX_REDUCE %d\n", i
-1); lineno
++;
4651 /* Minimum and maximum token values that have a destructor */
4653 for(i
=0; i
<lemp
->nsymbol
; i
++){
4654 struct symbol
*sp
= lemp
->symbols
[i
];
4656 if( sp
&& sp
->type
!=TERMINAL
&& sp
->destructor
){
4657 if( mn
==0 || sp
->index
<mn
) mn
= sp
->index
;
4658 if( sp
->index
>mx
) mx
= sp
->index
;
4661 if( lemp
->tokendest
) mn
= 0;
4662 if( lemp
->vardest
) mx
= lemp
->nsymbol
-1;
4663 fprintf(out
,"#define YY_MIN_DSTRCTR %d\n", mn
); lineno
++;
4664 fprintf(out
,"#define YY_MAX_DSTRCTR %d\n", mx
); lineno
++;
4666 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4668 /* Now output the action table and its associates:
4670 ** yy_action[] A single table containing all actions.
4671 ** yy_lookahead[] A table containing the lookahead for each entry in
4672 ** yy_action. Used to detect hash collisions.
4673 ** yy_shift_ofst[] For each state, the offset into yy_action for
4674 ** shifting terminals.
4675 ** yy_reduce_ofst[] For each state, the offset into yy_action for
4676 ** shifting non-terminals after a reduce.
4677 ** yy_default[] Default action for each state.
4680 /* Output the yy_action table */
4681 lemp
->nactiontab
= n
= acttab_action_size(pActtab
);
4682 lemp
->tablesize
+= n
*szActionType
;
4683 fprintf(out
,"#define YY_ACTTAB_COUNT (%d)\n", n
); lineno
++;
4684 fprintf(out
,"static const YYACTIONTYPE yy_action[] = {\n"); lineno
++;
4685 for(i
=j
=0; i
<n
; i
++){
4686 int action
= acttab_yyaction(pActtab
, i
);
4687 if( action
<0 ) action
= lemp
->noAction
;
4688 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4689 fprintf(out
, " %4d,", action
);
4690 if( j
==9 || i
==n
-1 ){
4691 fprintf(out
, "\n"); lineno
++;
4697 fprintf(out
, "};\n"); lineno
++;
4699 /* Output the yy_lookahead table */
4700 lemp
->nlookaheadtab
= n
= acttab_lookahead_size(pActtab
);
4701 lemp
->tablesize
+= n
*szCodeType
;
4702 fprintf(out
,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno
++;
4703 for(i
=j
=0; i
<n
; i
++){
4704 int la
= acttab_yylookahead(pActtab
, i
);
4705 if( la
<0 ) la
= lemp
->nsymbol
;
4706 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4707 fprintf(out
, " %4d,", la
);
4709 fprintf(out
, "\n"); lineno
++;
4715 /* Add extra entries to the end of the yy_lookahead[] table so that
4716 ** yy_shift_ofst[]+iToken will always be a valid index into the array,
4717 ** even for the largest possible value of yy_shift_ofst[] and iToken. */
4718 nLookAhead
= lemp
->nterminal
+ lemp
->nactiontab
;
4719 while( i
<nLookAhead
){
4720 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4721 fprintf(out
, " %4d,", lemp
->nterminal
);
4723 fprintf(out
, "\n"); lineno
++;
4730 if( j
>0 ){ fprintf(out
, "\n"); lineno
++; }
4731 fprintf(out
, "};\n"); lineno
++;
4733 /* Output the yy_shift_ofst[] table */
4735 while( n
>0 && lemp
->sorted
[n
-1]->iTknOfst
==NO_OFFSET
) n
--;
4736 fprintf(out
, "#define YY_SHIFT_COUNT (%d)\n", n
-1); lineno
++;
4737 fprintf(out
, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst
); lineno
++;
4738 fprintf(out
, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst
); lineno
++;
4739 fprintf(out
, "static const %s yy_shift_ofst[] = {\n",
4740 minimum_size_type(mnTknOfst
, lemp
->nterminal
+lemp
->nactiontab
, &sz
));
4742 lemp
->tablesize
+= n
*sz
;
4743 for(i
=j
=0; i
<n
; i
++){
4745 stp
= lemp
->sorted
[i
];
4746 ofst
= stp
->iTknOfst
;
4747 if( ofst
==NO_OFFSET
) ofst
= lemp
->nactiontab
;
4748 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4749 fprintf(out
, " %4d,", ofst
);
4750 if( j
==9 || i
==n
-1 ){
4751 fprintf(out
, "\n"); lineno
++;
4757 fprintf(out
, "};\n"); lineno
++;
4759 /* Output the yy_reduce_ofst[] table */
4761 while( n
>0 && lemp
->sorted
[n
-1]->iNtOfst
==NO_OFFSET
) n
--;
4762 fprintf(out
, "#define YY_REDUCE_COUNT (%d)\n", n
-1); lineno
++;
4763 fprintf(out
, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst
); lineno
++;
4764 fprintf(out
, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst
); lineno
++;
4765 fprintf(out
, "static const %s yy_reduce_ofst[] = {\n",
4766 minimum_size_type(mnNtOfst
-1, mxNtOfst
, &sz
)); lineno
++;
4767 lemp
->tablesize
+= n
*sz
;
4768 for(i
=j
=0; i
<n
; i
++){
4770 stp
= lemp
->sorted
[i
];
4771 ofst
= stp
->iNtOfst
;
4772 if( ofst
==NO_OFFSET
) ofst
= mnNtOfst
- 1;
4773 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4774 fprintf(out
, " %4d,", ofst
);
4775 if( j
==9 || i
==n
-1 ){
4776 fprintf(out
, "\n"); lineno
++;
4782 fprintf(out
, "};\n"); lineno
++;
4784 /* Output the default action table */
4785 fprintf(out
, "static const YYACTIONTYPE yy_default[] = {\n"); lineno
++;
4787 lemp
->tablesize
+= n
*szActionType
;
4788 for(i
=j
=0; i
<n
; i
++){
4789 stp
= lemp
->sorted
[i
];
4790 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4791 if( stp
->iDfltReduce
<0 ){
4792 fprintf(out
, " %4d,", lemp
->errAction
);
4794 fprintf(out
, " %4d,", stp
->iDfltReduce
+ lemp
->minReduce
);
4796 if( j
==9 || i
==n
-1 ){
4797 fprintf(out
, "\n"); lineno
++;
4803 fprintf(out
, "};\n"); lineno
++;
4804 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4806 /* Generate the table of fallback tokens.
4808 if( lemp
->has_fallback
){
4809 int mx
= lemp
->nterminal
- 1;
4810 /* 2019-08-28: Generate fallback entries for every token to avoid
4811 ** having to do a range check on the index */
4812 /* while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; } */
4813 lemp
->tablesize
+= (mx
+1)*szCodeType
;
4814 for(i
=0; i
<=mx
; i
++){
4815 struct symbol
*p
= lemp
->symbols
[i
];
4816 if( p
->fallback
==0 ){
4817 fprintf(out
, " 0, /* %10s => nothing */\n", p
->name
);
4819 fprintf(out
, " %3d, /* %10s => %s */\n", p
->fallback
->index
,
4820 p
->name
, p
->fallback
->name
);
4825 tplt_xfer(lemp
->name
, in
, out
, &lineno
);
4827 /* Generate a table containing the symbolic name of every symbol
4829 for(i
=0; i
<lemp
->nsymbol
; i
++){
4830 fprintf(out
," /* %4d */ \"%s\",\n",i
, lemp
->symbols
[i
]->name
); lineno
++;
4832 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4834 /* Generate a table containing a text string that describes every
4835 ** rule in the rule set of the grammar. This information is used
4836 ** when tracing REDUCE actions.
4838 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4839 assert( rp
->iRule
==i
);
4840 fprintf(out
," /* %3d */ \"", i
);
4841 writeRuleText(out
, rp
);
4842 fprintf(out
,"\",\n"); lineno
++;
4844 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4846 /* Generate code which executes every time a symbol is popped from
4847 ** the stack while processing errors or while destroying the parser.
4848 ** (In other words, generate the %destructor actions)
4850 if( lemp
->tokendest
){
4852 for(i
=0; i
<lemp
->nsymbol
; i
++){
4853 struct symbol
*sp
= lemp
->symbols
[i
];
4854 if( sp
==0 || sp
->type
!=TERMINAL
) continue;
4856 fprintf(out
, " /* TERMINAL Destructor */\n"); lineno
++;
4859 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4861 for(i
=0; i
<lemp
->nsymbol
&& lemp
->symbols
[i
]->type
!=TERMINAL
; i
++);
4862 if( i
<lemp
->nsymbol
){
4863 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4864 fprintf(out
," break;\n"); lineno
++;
4867 if( lemp
->vardest
){
4868 struct symbol
*dflt_sp
= 0;
4870 for(i
=0; i
<lemp
->nsymbol
; i
++){
4871 struct symbol
*sp
= lemp
->symbols
[i
];
4872 if( sp
==0 || sp
->type
==TERMINAL
||
4873 sp
->index
<=0 || sp
->destructor
!=0 ) continue;
4875 fprintf(out
, " /* Default NON-TERMINAL Destructor */\n");lineno
++;
4878 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4882 emit_destructor_code(out
,dflt_sp
,lemp
,&lineno
);
4884 fprintf(out
," break;\n"); lineno
++;
4886 for(i
=0; i
<lemp
->nsymbol
; i
++){
4887 struct symbol
*sp
= lemp
->symbols
[i
];
4888 if( sp
==0 || sp
->type
==TERMINAL
|| sp
->destructor
==0 ) continue;
4889 if( sp
->destLineno
<0 ) continue; /* Already emitted */
4890 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4892 /* Combine duplicate destructors into a single case */
4893 for(j
=i
+1; j
<lemp
->nsymbol
; j
++){
4894 struct symbol
*sp2
= lemp
->symbols
[j
];
4895 if( sp2
&& sp2
->type
!=TERMINAL
&& sp2
->destructor
4896 && sp2
->dtnum
==sp
->dtnum
4897 && strcmp(sp
->destructor
,sp2
->destructor
)==0 ){
4898 fprintf(out
," case %d: /* %s */\n",
4899 sp2
->index
, sp2
->name
); lineno
++;
4900 sp2
->destLineno
= -1; /* Avoid emitting this destructor again */
4904 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4905 fprintf(out
," break;\n"); lineno
++;
4907 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4909 /* Generate code which executes whenever the parser stack overflows */
4910 tplt_print(out
,lemp
,lemp
->overflow
,&lineno
);
4911 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4913 /* Generate the tables of rule information. yyRuleInfoLhs[] and
4914 ** yyRuleInfoNRhs[].
4916 ** Note: This code depends on the fact that rules are number
4917 ** sequentially beginning with 0.
4919 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4920 fprintf(out
," %4d, /* (%d) ", rp
->lhs
->index
, i
);
4921 rule_print(out
, rp
);
4922 fprintf(out
," */\n"); lineno
++;
4924 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4925 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4926 fprintf(out
," %3d, /* (%d) ", -rp
->nrhs
, i
);
4927 rule_print(out
, rp
);
4928 fprintf(out
," */\n"); lineno
++;
4930 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4932 /* Generate code which execution during each REDUCE action */
4934 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4935 i
+= translate_code(lemp
, rp
);
4938 fprintf(out
," YYMINORTYPE yylhsminor;\n"); lineno
++;
4940 /* First output rules other than the default: rule */
4941 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4942 struct rule
*rp2
; /* Other rules with the same action */
4943 if( rp
->codeEmitted
) continue;
4945 /* No C code actions, so this will be part of the "default:" rule */
4948 fprintf(out
," case %d: /* ", rp
->iRule
);
4949 writeRuleText(out
, rp
);
4950 fprintf(out
, " */\n"); lineno
++;
4951 for(rp2
=rp
->next
; rp2
; rp2
=rp2
->next
){
4952 if( rp2
->code
==rp
->code
&& rp2
->codePrefix
==rp
->codePrefix
4953 && rp2
->codeSuffix
==rp
->codeSuffix
){
4954 fprintf(out
," case %d: /* ", rp2
->iRule
);
4955 writeRuleText(out
, rp2
);
4956 fprintf(out
," */ yytestcase(yyruleno==%d);\n", rp2
->iRule
); lineno
++;
4957 rp2
->codeEmitted
= 1;
4960 emit_code(out
,rp
,lemp
,&lineno
);
4961 fprintf(out
," break;\n"); lineno
++;
4962 rp
->codeEmitted
= 1;
4964 /* Finally, output the default: rule. We choose as the default: all
4965 ** empty actions. */
4966 fprintf(out
," default:\n"); lineno
++;
4967 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4968 if( rp
->codeEmitted
) continue;
4969 assert( rp
->noCode
);
4970 fprintf(out
," /* (%d) ", rp
->iRule
);
4971 writeRuleText(out
, rp
);
4972 if( rp
->neverReduce
){
4973 fprintf(out
, " (NEVER REDUCES) */ assert(yyruleno!=%d);\n",
4974 rp
->iRule
); lineno
++;
4975 }else if( rp
->doesReduce
){
4976 fprintf(out
, " */ yytestcase(yyruleno==%d);\n", rp
->iRule
); lineno
++;
4978 fprintf(out
, " (OPTIMIZED OUT) */ assert(yyruleno!=%d);\n",
4979 rp
->iRule
); lineno
++;
4982 fprintf(out
," break;\n"); lineno
++;
4983 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4985 /* Generate code which executes if a parse fails */
4986 tplt_print(out
,lemp
,lemp
->failure
,&lineno
);
4987 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4989 /* Generate code which executes when a syntax error occurs */
4990 tplt_print(out
,lemp
,lemp
->error
,&lineno
);
4991 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4993 /* Generate code which executes when the parser accepts its input */
4994 tplt_print(out
,lemp
,lemp
->accept
,&lineno
);
4995 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4997 /* Append any addition code the user desires */
4998 tplt_print(out
,lemp
,lemp
->extracode
,&lineno
);
5000 acttab_free(pActtab
);
5003 if( sql
) fclose(sql
);
5007 /* Generate a header file for the parser */
5008 void ReportHeader(struct lemon
*lemp
)
5012 char line
[LINESIZE
];
5013 char pattern
[LINESIZE
];
5016 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
5018 in
= file_open(lemp
,".h","rb");
5021 for(i
=1; i
<lemp
->nterminal
&& fgets(line
,LINESIZE
,in
); i
++){
5022 lemon_sprintf(pattern
,"#define %s%-30s %3d\n",
5023 prefix
,lemp
->symbols
[i
]->name
,i
);
5024 if( strcmp(line
,pattern
) ) break;
5026 nextChar
= fgetc(in
);
5028 if( i
==lemp
->nterminal
&& nextChar
==EOF
){
5029 /* No change in the file. Don't rewrite it. */
5033 out
= file_open(lemp
,".h","wb");
5035 for(i
=1; i
<lemp
->nterminal
; i
++){
5036 fprintf(out
,"#define %s%-30s %3d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
5043 /* Reduce the size of the action tables, if possible, by making use
5046 ** In this version, we take the most frequent REDUCE action and make
5047 ** it the default. Except, there is no default if the wildcard token
5048 ** is a possible look-ahead.
5050 void CompressTables(struct lemon
*lemp
)
5053 struct action
*ap
, *ap2
, *nextap
;
5054 struct rule
*rp
, *rp2
, *rbest
;
5059 for(i
=0; i
<lemp
->nstate
; i
++){
5060 stp
= lemp
->sorted
[i
];
5065 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
5066 if( ap
->type
==SHIFT
&& ap
->sp
==lemp
->wildcard
){
5069 if( ap
->type
!=REDUCE
) continue;
5071 if( rp
->lhsStart
) continue;
5072 if( rp
==rbest
) continue;
5074 for(ap2
=ap
->next
; ap2
; ap2
=ap2
->next
){
5075 if( ap2
->type
!=REDUCE
) continue;
5077 if( rp2
==rbest
) continue;
5086 /* Do not make a default if the number of rules to default
5087 ** is not at least 1 or if the wildcard token is a possible
5090 if( nbest
<1 || usesWildcard
) continue;
5093 /* Combine matching REDUCE actions into a single default */
5094 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
5095 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) break;
5098 ap
->sp
= Symbol_new("{default}");
5099 for(ap
=ap
->next
; ap
; ap
=ap
->next
){
5100 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) ap
->type
= NOT_USED
;
5102 stp
->ap
= Action_sort(stp
->ap
);
5104 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
5105 if( ap
->type
==SHIFT
) break;
5106 if( ap
->type
==REDUCE
&& ap
->x
.rp
!=rbest
) break;
5109 stp
->autoReduce
= 1;
5110 stp
->pDfltReduce
= rbest
;
5114 /* Make a second pass over all states and actions. Convert
5115 ** every action that is a SHIFT to an autoReduce state into
5116 ** a SHIFTREDUCE action.
5118 for(i
=0; i
<lemp
->nstate
; i
++){
5119 stp
= lemp
->sorted
[i
];
5120 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
5121 struct state
*pNextState
;
5122 if( ap
->type
!=SHIFT
) continue;
5123 pNextState
= ap
->x
.stp
;
5124 if( pNextState
->autoReduce
&& pNextState
->pDfltReduce
!=0 ){
5125 ap
->type
= SHIFTREDUCE
;
5126 ap
->x
.rp
= pNextState
->pDfltReduce
;
5131 /* If a SHIFTREDUCE action specifies a rule that has a single RHS term
5132 ** (meaning that the SHIFTREDUCE will land back in the state where it
5133 ** started) and if there is no C-code associated with the reduce action,
5134 ** then we can go ahead and convert the action to be the same as the
5135 ** action for the RHS of the rule.
5137 for(i
=0; i
<lemp
->nstate
; i
++){
5138 stp
= lemp
->sorted
[i
];
5139 for(ap
=stp
->ap
; ap
; ap
=nextap
){
5141 if( ap
->type
!=SHIFTREDUCE
) continue;
5143 if( rp
->noCode
==0 ) continue;
5144 if( rp
->nrhs
!=1 ) continue;
5146 /* Only apply this optimization to non-terminals. It would be OK to
5147 ** apply it to terminal symbols too, but that makes the parser tables
5149 if( ap
->sp
->index
<lemp
->nterminal
) continue;
5151 /* If we reach this point, it means the optimization can be applied */
5153 for(ap2
=stp
->ap
; ap2
&& (ap2
==ap
|| ap2
->sp
!=rp
->lhs
); ap2
=ap2
->next
){}
5155 ap
->spOpt
= ap2
->sp
;
5156 ap
->type
= ap2
->type
;
5164 ** Compare two states for sorting purposes. The smaller state is the
5165 ** one with the most non-terminal actions. If they have the same number
5166 ** of non-terminal actions, then the smaller is the one with the most
5169 static int stateResortCompare(const void *a
, const void *b
){
5170 const struct state
*pA
= *(const struct state
**)a
;
5171 const struct state
*pB
= *(const struct state
**)b
;
5174 n
= pB
->nNtAct
- pA
->nNtAct
;
5176 n
= pB
->nTknAct
- pA
->nTknAct
;
5178 n
= pB
->statenum
- pA
->statenum
;
5187 ** Renumber and resort states so that states with fewer choices
5188 ** occur at the end. Except, keep state 0 as the first state.
5190 void ResortStates(struct lemon
*lemp
)
5196 for(i
=0; i
<lemp
->nstate
; i
++){
5197 stp
= lemp
->sorted
[i
];
5198 stp
->nTknAct
= stp
->nNtAct
= 0;
5199 stp
->iDfltReduce
= -1; /* Init dflt action to "syntax error" */
5200 stp
->iTknOfst
= NO_OFFSET
;
5201 stp
->iNtOfst
= NO_OFFSET
;
5202 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
5203 int iAction
= compute_action(lemp
,ap
);
5205 if( ap
->sp
->index
<lemp
->nterminal
){
5207 }else if( ap
->sp
->index
<lemp
->nsymbol
){
5210 assert( stp
->autoReduce
==0 || stp
->pDfltReduce
==ap
->x
.rp
);
5211 stp
->iDfltReduce
= iAction
;
5216 qsort(&lemp
->sorted
[1], lemp
->nstate
-1, sizeof(lemp
->sorted
[0]),
5217 stateResortCompare
);
5218 for(i
=0; i
<lemp
->nstate
; i
++){
5219 lemp
->sorted
[i
]->statenum
= i
;
5221 lemp
->nxstate
= lemp
->nstate
;
5222 while( lemp
->nxstate
>1 && lemp
->sorted
[lemp
->nxstate
-1]->autoReduce
){
5228 /***************** From the file "set.c" ************************************/
5230 ** Set manipulation routines for the LEMON parser generator.
5233 static int size
= 0;
5235 /* Set the set size */
5241 /* Allocate a new set */
5244 s
= (char*)calloc( size
, 1);
5251 /* Deallocate a set */
5252 void SetFree(char *s
)
5257 /* Add a new element to the set. Return TRUE if the element was added
5258 ** and FALSE if it was already there. */
5259 int SetAdd(char *s
, int e
)
5262 assert( e
>=0 && e
<size
);
5268 /* Add every element of s2 to s1. Return TRUE if s1 changes. */
5269 int SetUnion(char *s1
, char *s2
)
5273 for(i
=0; i
<size
; i
++){
5274 if( s2
[i
]==0 ) continue;
5282 /********************** From the file "table.c" ****************************/
5284 ** All code in this file has been automatically generated
5285 ** from a specification in the file
5287 ** by the associative array code building program "aagen".
5288 ** Do not edit this file! Instead, edit the specification
5289 ** file, then rerun aagen.
5292 ** Code for processing tables in the LEMON parser generator.
5295 PRIVATE
unsigned strhash(const char *x
)
5298 while( *x
) h
= h
*13 + *(x
++);
5302 /* Works like strdup, sort of. Save a string in malloced memory, but
5303 ** keep strings in a table so that the same string is not in more
5306 const char *Strsafe(const char *y
)
5311 if( y
==0 ) return 0;
5312 z
= Strsafe_find(y
);
5313 if( z
==0 && (cpy
=(char *)malloc( lemonStrlen(y
)+1 ))!=0 ){
5314 lemon_strcpy(cpy
,y
);
5322 /* There is one instance of the following structure for each
5323 ** associative array of type "x1".
5326 int size
; /* The number of available slots. */
5327 /* Must be a power of 2 greater than or */
5329 int count
; /* Number of currently slots filled */
5330 struct s_x1node
*tbl
; /* The data stored here */
5331 struct s_x1node
**ht
; /* Hash table for lookups */
5334 /* There is one instance of this structure for every data element
5335 ** in an associative array of type "x1".
5337 typedef struct s_x1node
{
5338 const char *data
; /* The data */
5339 struct s_x1node
*next
; /* Next entry with the same hash */
5340 struct s_x1node
**from
; /* Previous link */
5343 /* There is only one instance of the array, which is the following */
5344 static struct s_x1
*x1a
;
5346 /* Allocate a new associative array */
5347 void Strsafe_init(void){
5349 x1a
= (struct s_x1
*)malloc( sizeof(struct s_x1
) );
5353 x1a
->tbl
= (x1node
*)calloc(1024, sizeof(x1node
) + sizeof(x1node
*));
5359 x1a
->ht
= (x1node
**)&(x1a
->tbl
[1024]);
5360 for(i
=0; i
<1024; i
++) x1a
->ht
[i
] = 0;
5364 /* Insert a new record into the array. Return TRUE if successful.
5365 ** Prior data with the same key is NOT overwritten */
5366 int Strsafe_insert(const char *data
)
5372 if( x1a
==0 ) return 0;
5374 h
= ph
& (x1a
->size
-1);
5377 if( strcmp(np
->data
,data
)==0 ){
5378 /* An existing entry with the same key is found. */
5379 /* Fail because overwrite is not allows. */
5384 if( x1a
->count
>=x1a
->size
){
5385 /* Need to make the hash table bigger */
5388 array
.size
= arrSize
= x1a
->size
*2;
5389 array
.count
= x1a
->count
;
5390 array
.tbl
= (x1node
*)calloc(arrSize
, sizeof(x1node
) + sizeof(x1node
*));
5391 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5392 array
.ht
= (x1node
**)&(array
.tbl
[arrSize
]);
5393 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5394 for(i
=0; i
<x1a
->count
; i
++){
5395 x1node
*oldnp
, *newnp
;
5396 oldnp
= &(x1a
->tbl
[i
]);
5397 h
= strhash(oldnp
->data
) & (arrSize
-1);
5398 newnp
= &(array
.tbl
[i
]);
5399 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5400 newnp
->next
= array
.ht
[h
];
5401 newnp
->data
= oldnp
->data
;
5402 newnp
->from
= &(array
.ht
[h
]);
5403 array
.ht
[h
] = newnp
;
5405 /* free(x1a->tbl); // This program was originally for 16-bit machines.
5406 ** Don't worry about freeing memory on modern platforms. */
5409 /* Insert the new data */
5410 h
= ph
& (x1a
->size
-1);
5411 np
= &(x1a
->tbl
[x1a
->count
++]);
5413 if( x1a
->ht
[h
] ) x1a
->ht
[h
]->from
= &(np
->next
);
5414 np
->next
= x1a
->ht
[h
];
5416 np
->from
= &(x1a
->ht
[h
]);
5420 /* Return a pointer to data assigned to the given key. Return NULL
5421 ** if no such key. */
5422 const char *Strsafe_find(const char *key
)
5427 if( x1a
==0 ) return 0;
5428 h
= strhash(key
) & (x1a
->size
-1);
5431 if( strcmp(np
->data
,key
)==0 ) break;
5434 return np
? np
->data
: 0;
5437 /* Return a pointer to the (terminal or nonterminal) symbol "x".
5438 ** Create a new symbol if this is the first time "x" has been seen.
5440 struct symbol
*Symbol_new(const char *x
)
5444 sp
= Symbol_find(x
);
5446 sp
= (struct symbol
*)calloc(1, sizeof(struct symbol
) );
5448 sp
->name
= Strsafe(x
);
5449 sp
->type
= ISUPPER(*x
) ? TERMINAL
: NONTERMINAL
;
5455 sp
->lambda
= LEMON_FALSE
;
5460 Symbol_insert(sp
,sp
->name
);
5466 /* Compare two symbols for sorting purposes. Return negative,
5467 ** zero, or positive if a is less then, equal to, or greater
5470 ** Symbols that begin with upper case letters (terminals or tokens)
5471 ** must sort before symbols that begin with lower case letters
5472 ** (non-terminals). And MULTITERMINAL symbols (created using the
5473 ** %token_class directive) must sort at the very end. Other than
5474 ** that, the order does not matter.
5476 ** We find experimentally that leaving the symbols in their original
5477 ** order (the order they appeared in the grammar file) gives the
5478 ** smallest parser tables in SQLite.
5480 int Symbolcmpp(const void *_a
, const void *_b
)
5482 const struct symbol
*a
= *(const struct symbol
**) _a
;
5483 const struct symbol
*b
= *(const struct symbol
**) _b
;
5484 int i1
= a
->type
==MULTITERMINAL
? 3 : a
->name
[0]>'Z' ? 2 : 1;
5485 int i2
= b
->type
==MULTITERMINAL
? 3 : b
->name
[0]>'Z' ? 2 : 1;
5486 return i1
==i2
? a
->index
- b
->index
: i1
- i2
;
5489 /* There is one instance of the following structure for each
5490 ** associative array of type "x2".
5493 int size
; /* The number of available slots. */
5494 /* Must be a power of 2 greater than or */
5496 int count
; /* Number of currently slots filled */
5497 struct s_x2node
*tbl
; /* The data stored here */
5498 struct s_x2node
**ht
; /* Hash table for lookups */
5501 /* There is one instance of this structure for every data element
5502 ** in an associative array of type "x2".
5504 typedef struct s_x2node
{
5505 struct symbol
*data
; /* The data */
5506 const char *key
; /* The key */
5507 struct s_x2node
*next
; /* Next entry with the same hash */
5508 struct s_x2node
**from
; /* Previous link */
5511 /* There is only one instance of the array, which is the following */
5512 static struct s_x2
*x2a
;
5514 /* Allocate a new associative array */
5515 void Symbol_init(void){
5517 x2a
= (struct s_x2
*)malloc( sizeof(struct s_x2
) );
5521 x2a
->tbl
= (x2node
*)calloc(128, sizeof(x2node
) + sizeof(x2node
*));
5527 x2a
->ht
= (x2node
**)&(x2a
->tbl
[128]);
5528 for(i
=0; i
<128; i
++) x2a
->ht
[i
] = 0;
5532 /* Insert a new record into the array. Return TRUE if successful.
5533 ** Prior data with the same key is NOT overwritten */
5534 int Symbol_insert(struct symbol
*data
, const char *key
)
5540 if( x2a
==0 ) return 0;
5542 h
= ph
& (x2a
->size
-1);
5545 if( strcmp(np
->key
,key
)==0 ){
5546 /* An existing entry with the same key is found. */
5547 /* Fail because overwrite is not allows. */
5552 if( x2a
->count
>=x2a
->size
){
5553 /* Need to make the hash table bigger */
5556 array
.size
= arrSize
= x2a
->size
*2;
5557 array
.count
= x2a
->count
;
5558 array
.tbl
= (x2node
*)calloc(arrSize
, sizeof(x2node
) + sizeof(x2node
*));
5559 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5560 array
.ht
= (x2node
**)&(array
.tbl
[arrSize
]);
5561 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5562 for(i
=0; i
<x2a
->count
; i
++){
5563 x2node
*oldnp
, *newnp
;
5564 oldnp
= &(x2a
->tbl
[i
]);
5565 h
= strhash(oldnp
->key
) & (arrSize
-1);
5566 newnp
= &(array
.tbl
[i
]);
5567 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5568 newnp
->next
= array
.ht
[h
];
5569 newnp
->key
= oldnp
->key
;
5570 newnp
->data
= oldnp
->data
;
5571 newnp
->from
= &(array
.ht
[h
]);
5572 array
.ht
[h
] = newnp
;
5574 /* free(x2a->tbl); // This program was originally written for 16-bit
5575 ** machines. Don't worry about freeing this trivial amount of memory
5576 ** on modern platforms. Just leak it. */
5579 /* Insert the new data */
5580 h
= ph
& (x2a
->size
-1);
5581 np
= &(x2a
->tbl
[x2a
->count
++]);
5584 if( x2a
->ht
[h
] ) x2a
->ht
[h
]->from
= &(np
->next
);
5585 np
->next
= x2a
->ht
[h
];
5587 np
->from
= &(x2a
->ht
[h
]);
5591 /* Return a pointer to data assigned to the given key. Return NULL
5592 ** if no such key. */
5593 struct symbol
*Symbol_find(const char *key
)
5598 if( x2a
==0 ) return 0;
5599 h
= strhash(key
) & (x2a
->size
-1);
5602 if( strcmp(np
->key
,key
)==0 ) break;
5605 return np
? np
->data
: 0;
5608 /* Return the n-th data. Return NULL if n is out of range. */
5609 struct symbol
*Symbol_Nth(int n
)
5611 struct symbol
*data
;
5612 if( x2a
&& n
>0 && n
<=x2a
->count
){
5613 data
= x2a
->tbl
[n
-1].data
;
5620 /* Return the size of the array */
5623 return x2a
? x2a
->count
: 0;
5626 /* Return an array of pointers to all data in the table.
5627 ** The array is obtained from malloc. Return NULL if memory allocation
5628 ** problems, or if the array is empty. */
5629 struct symbol
**Symbol_arrayof()
5631 struct symbol
**array
;
5633 if( x2a
==0 ) return 0;
5634 arrSize
= x2a
->count
;
5635 array
= (struct symbol
**)calloc(arrSize
, sizeof(struct symbol
*));
5637 for(i
=0; i
<arrSize
; i
++) array
[i
] = x2a
->tbl
[i
].data
;
5642 /* Compare two configurations */
5643 int Configcmp(const char *_a
,const char *_b
)
5645 const struct config
*a
= (struct config
*) _a
;
5646 const struct config
*b
= (struct config
*) _b
;
5648 x
= a
->rp
->index
- b
->rp
->index
;
5649 if( x
==0 ) x
= a
->dot
- b
->dot
;
5653 /* Compare two states */
5654 PRIVATE
int statecmp(struct config
*a
, struct config
*b
)
5657 for(rc
=0; rc
==0 && a
&& b
; a
=a
->bp
, b
=b
->bp
){
5658 rc
= a
->rp
->index
- b
->rp
->index
;
5659 if( rc
==0 ) rc
= a
->dot
- b
->dot
;
5669 PRIVATE
unsigned statehash(struct config
*a
)
5673 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
5679 /* Allocate a new state structure */
5680 struct state
*State_new()
5682 struct state
*newstate
;
5683 newstate
= (struct state
*)calloc(1, sizeof(struct state
) );
5684 MemoryCheck(newstate
);
5688 /* There is one instance of the following structure for each
5689 ** associative array of type "x3".
5692 int size
; /* The number of available slots. */
5693 /* Must be a power of 2 greater than or */
5695 int count
; /* Number of currently slots filled */
5696 struct s_x3node
*tbl
; /* The data stored here */
5697 struct s_x3node
**ht
; /* Hash table for lookups */
5700 /* There is one instance of this structure for every data element
5701 ** in an associative array of type "x3".
5703 typedef struct s_x3node
{
5704 struct state
*data
; /* The data */
5705 struct config
*key
; /* The key */
5706 struct s_x3node
*next
; /* Next entry with the same hash */
5707 struct s_x3node
**from
; /* Previous link */
5710 /* There is only one instance of the array, which is the following */
5711 static struct s_x3
*x3a
;
5713 /* Allocate a new associative array */
5714 void State_init(void){
5716 x3a
= (struct s_x3
*)malloc( sizeof(struct s_x3
) );
5720 x3a
->tbl
= (x3node
*)calloc(128, sizeof(x3node
) + sizeof(x3node
*));
5726 x3a
->ht
= (x3node
**)&(x3a
->tbl
[128]);
5727 for(i
=0; i
<128; i
++) x3a
->ht
[i
] = 0;
5731 /* Insert a new record into the array. Return TRUE if successful.
5732 ** Prior data with the same key is NOT overwritten */
5733 int State_insert(struct state
*data
, struct config
*key
)
5739 if( x3a
==0 ) return 0;
5740 ph
= statehash(key
);
5741 h
= ph
& (x3a
->size
-1);
5744 if( statecmp(np
->key
,key
)==0 ){
5745 /* An existing entry with the same key is found. */
5746 /* Fail because overwrite is not allows. */
5751 if( x3a
->count
>=x3a
->size
){
5752 /* Need to make the hash table bigger */
5755 array
.size
= arrSize
= x3a
->size
*2;
5756 array
.count
= x3a
->count
;
5757 array
.tbl
= (x3node
*)calloc(arrSize
, sizeof(x3node
) + sizeof(x3node
*));
5758 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5759 array
.ht
= (x3node
**)&(array
.tbl
[arrSize
]);
5760 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5761 for(i
=0; i
<x3a
->count
; i
++){
5762 x3node
*oldnp
, *newnp
;
5763 oldnp
= &(x3a
->tbl
[i
]);
5764 h
= statehash(oldnp
->key
) & (arrSize
-1);
5765 newnp
= &(array
.tbl
[i
]);
5766 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5767 newnp
->next
= array
.ht
[h
];
5768 newnp
->key
= oldnp
->key
;
5769 newnp
->data
= oldnp
->data
;
5770 newnp
->from
= &(array
.ht
[h
]);
5771 array
.ht
[h
] = newnp
;
5776 /* Insert the new data */
5777 h
= ph
& (x3a
->size
-1);
5778 np
= &(x3a
->tbl
[x3a
->count
++]);
5781 if( x3a
->ht
[h
] ) x3a
->ht
[h
]->from
= &(np
->next
);
5782 np
->next
= x3a
->ht
[h
];
5784 np
->from
= &(x3a
->ht
[h
]);
5788 /* Return a pointer to data assigned to the given key. Return NULL
5789 ** if no such key. */
5790 struct state
*State_find(struct config
*key
)
5795 if( x3a
==0 ) return 0;
5796 h
= statehash(key
) & (x3a
->size
-1);
5799 if( statecmp(np
->key
,key
)==0 ) break;
5802 return np
? np
->data
: 0;
5805 /* Return an array of pointers to all data in the table.
5806 ** The array is obtained from malloc. Return NULL if memory allocation
5807 ** problems, or if the array is empty. */
5808 struct state
**State_arrayof(void)
5810 struct state
**array
;
5812 if( x3a
==0 ) return 0;
5813 arrSize
= x3a
->count
;
5814 array
= (struct state
**)calloc(arrSize
, sizeof(struct state
*));
5816 for(i
=0; i
<arrSize
; i
++) array
[i
] = x3a
->tbl
[i
].data
;
5821 /* Hash a configuration */
5822 PRIVATE
unsigned confighash(struct config
*a
)
5825 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
5829 /* There is one instance of the following structure for each
5830 ** associative array of type "x4".
5833 int size
; /* The number of available slots. */
5834 /* Must be a power of 2 greater than or */
5836 int count
; /* Number of currently slots filled */
5837 struct s_x4node
*tbl
; /* The data stored here */
5838 struct s_x4node
**ht
; /* Hash table for lookups */
5841 /* There is one instance of this structure for every data element
5842 ** in an associative array of type "x4".
5844 typedef struct s_x4node
{
5845 struct config
*data
; /* The data */
5846 struct s_x4node
*next
; /* Next entry with the same hash */
5847 struct s_x4node
**from
; /* Previous link */
5850 /* There is only one instance of the array, which is the following */
5851 static struct s_x4
*x4a
;
5853 /* Allocate a new associative array */
5854 void Configtable_init(void){
5856 x4a
= (struct s_x4
*)malloc( sizeof(struct s_x4
) );
5860 x4a
->tbl
= (x4node
*)calloc(64, sizeof(x4node
) + sizeof(x4node
*));
5866 x4a
->ht
= (x4node
**)&(x4a
->tbl
[64]);
5867 for(i
=0; i
<64; i
++) x4a
->ht
[i
] = 0;
5871 /* Insert a new record into the array. Return TRUE if successful.
5872 ** Prior data with the same key is NOT overwritten */
5873 int Configtable_insert(struct config
*data
)
5879 if( x4a
==0 ) return 0;
5880 ph
= confighash(data
);
5881 h
= ph
& (x4a
->size
-1);
5884 if( Configcmp((const char *) np
->data
,(const char *) data
)==0 ){
5885 /* An existing entry with the same key is found. */
5886 /* Fail because overwrite is not allows. */
5891 if( x4a
->count
>=x4a
->size
){
5892 /* Need to make the hash table bigger */
5895 array
.size
= arrSize
= x4a
->size
*2;
5896 array
.count
= x4a
->count
;
5897 array
.tbl
= (x4node
*)calloc(arrSize
, sizeof(x4node
) + sizeof(x4node
*));
5898 if( array
.tbl
==0 ) return 0; /* Fail due to malloc failure */
5899 array
.ht
= (x4node
**)&(array
.tbl
[arrSize
]);
5900 for(i
=0; i
<arrSize
; i
++) array
.ht
[i
] = 0;
5901 for(i
=0; i
<x4a
->count
; i
++){
5902 x4node
*oldnp
, *newnp
;
5903 oldnp
= &(x4a
->tbl
[i
]);
5904 h
= confighash(oldnp
->data
) & (arrSize
-1);
5905 newnp
= &(array
.tbl
[i
]);
5906 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5907 newnp
->next
= array
.ht
[h
];
5908 newnp
->data
= oldnp
->data
;
5909 newnp
->from
= &(array
.ht
[h
]);
5910 array
.ht
[h
] = newnp
;
5912 /* free(x4a->tbl); // This code was originall written for 16-bit machines.
5913 ** on modern machines, don't worry about freeing this trival amount of
5917 /* Insert the new data */
5918 h
= ph
& (x4a
->size
-1);
5919 np
= &(x4a
->tbl
[x4a
->count
++]);
5921 if( x4a
->ht
[h
] ) x4a
->ht
[h
]->from
= &(np
->next
);
5922 np
->next
= x4a
->ht
[h
];
5924 np
->from
= &(x4a
->ht
[h
]);
5928 /* Return a pointer to data assigned to the given key. Return NULL
5929 ** if no such key. */
5930 struct config
*Configtable_find(struct config
*key
)
5935 if( x4a
==0 ) return 0;
5936 h
= confighash(key
) & (x4a
->size
-1);
5939 if( Configcmp((const char *) np
->data
,(const char *) key
)==0 ) break;
5942 return np
? np
->data
: 0;
5945 /* Remove all data from the table. Pass each data to the function "f"
5946 ** as it is removed. ("f" may be null to avoid this step.) */
5947 void Configtable_clear(int(*f
)(struct config
*))
5950 if( x4a
==0 || x4a
->count
==0 ) return;
5951 if( f
) for(i
=0; i
<x4a
->count
; i
++) (*f
)(x4a
->tbl
[i
].data
);
5952 for(i
=0; i
<x4a
->size
; i
++) x4a
->ht
[i
] = 0;