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 authors of this program disclaim copyright.
9 ** Modified to add "-o" and "-h" command line options. Olly Betts 2005-02-14
10 ** Modified to fix a number of compiler warnings. Olly Betts 2007-02-20
12 ** Synced with upstream:
13 ** http://www.sqlite.org/src/artifact/3ff0fec22f92dfb54e62eeb48772eddffdbeb0d6
23 # if defined(_WIN32) || defined(WIN32)
32 extern int access(const char *path
, int mode
);
40 #define PRIVATE static
43 #define MAXRHS 5 /* Set low to exercise exception code */
48 static int showPrecedenceConflict
= 0;
49 static char *msort(char*,char**,int(*)(const char*,const char*));
52 ** Compilers are getting increasingly pedantic about type conversions
53 ** as C evolves ever closer to Ada.... To work around the latest problems
54 ** we have to define the following variant of strlen().
56 #define lemonStrlen(X) ((int)strlen(X))
59 ** Compilers are starting to complain about the use of sprintf() and strcpy(),
60 ** saying they are unsafe. So we define our own versions of those routines too.
62 ** There are three routines here: lemon_sprintf(), lemon_vsprintf(), and
63 ** lemon_addtext(). The first two are replacements for sprintf() and vsprintf().
64 ** The third is a helper routine for vsnprintf() that adds texts to the end of a
65 ** buffer, making sure the buffer is always zero-terminated.
67 ** The string formatter is a minimal subset of stdlib sprintf() supporting only
68 ** a few simply conversions:
75 static void lemon_addtext(
76 char *zBuf
, /* The buffer to which text is added */
77 int *pnUsed
, /* Slots of the buffer used so far */
78 const char *zIn
, /* Text to add */
79 int nIn
, /* Bytes of text to add. -1 to use strlen() */
80 int iWidth
/* Field width. Negative to left justify */
82 if( nIn
<0 ) for(nIn
=0; zIn
[nIn
]; nIn
++){}
83 while( iWidth
>nIn
){ zBuf
[(*pnUsed
)++] = ' '; iWidth
--; }
85 memcpy(&zBuf
[*pnUsed
], zIn
, nIn
);
87 while( (-iWidth
)>nIn
){ zBuf
[(*pnUsed
)++] = ' '; iWidth
++; }
90 static int lemon_vsprintf(char *str
, const char *zFormat
, va_list ap
){
96 for(i
=j
=0; (c
= zFormat
[i
])!=0; i
++){
99 lemon_addtext(str
, &nUsed
, &zFormat
[j
], i
-j
, 0);
101 if( isdigit(c
) || (c
=='-' && isdigit(zFormat
[i
+1])) ){
103 while( isdigit(zFormat
[i
]) ) iWidth
= iWidth
*10 + zFormat
[i
++] - '0';
104 if( c
=='-' ) iWidth
= -iWidth
;
108 int v
= va_arg(ap
, int);
110 lemon_addtext(str
, &nUsed
, "-", 1, iWidth
);
113 lemon_addtext(str
, &nUsed
, "0", 1, iWidth
);
118 zTemp
[sizeof(zTemp
)-k
] = (v
%10) + '0';
121 lemon_addtext(str
, &nUsed
, &zTemp
[sizeof(zTemp
)-k
], k
, iWidth
);
123 z
= va_arg(ap
, const char*);
124 lemon_addtext(str
, &nUsed
, z
, -1, iWidth
);
125 }else if( c
=='.' && memcmp(&zFormat
[i
], ".*s", 3)==0 ){
128 z
= va_arg(ap
, const char*);
129 lemon_addtext(str
, &nUsed
, z
, k
, iWidth
);
131 lemon_addtext(str
, &nUsed
, "%", 1, 0);
133 fprintf(stderr
, "illegal format\n");
139 lemon_addtext(str
, &nUsed
, &zFormat
[j
], i
-j
, 0);
142 static int lemon_sprintf(char *str
, const char *format
, ...){
145 va_start(ap
, format
);
146 rc
= lemon_vsprintf(str
, format
, ap
);
150 static void lemon_strcpy(char *dest
, const char *src
){
151 while( (*(dest
++) = *(src
++))!=0 ){}
153 static void lemon_strcat(char *dest
, const char *src
){
154 while( *dest
) dest
++;
155 lemon_strcpy(dest
, src
);
159 /* a few forward declarations... */
164 static struct action
*Action_new(void);
165 static struct action
*Action_sort(struct action
*);
167 /********** From the file "build.h" ************************************/
168 void FindRulePrecedences();
169 void FindFirstSets();
172 void FindFollowSets();
175 /********* From the file "configlist.h" *********************************/
176 void Configlist_init(void);
177 struct config
*Configlist_add(struct rule
*, int);
178 struct config
*Configlist_addbasis(struct rule
*, int);
179 void Configlist_closure(struct lemon
*);
180 void Configlist_sort(void);
181 void Configlist_sortbasis(void);
182 struct config
*Configlist_return(void);
183 struct config
*Configlist_basis(void);
184 void Configlist_eat(struct config
*);
185 void Configlist_reset(void);
187 /********* From the file "error.h" ***************************************/
188 void ErrorMsg(const char *, int,const char *, ...);
190 /****** From the file "option.h" ******************************************/
191 enum option_type
{ OPT_FLAG
=1, OPT_INT
, OPT_DBL
, OPT_STR
,
192 OPT_FFLAG
, OPT_FINT
, OPT_FDBL
, OPT_FSTR
};
194 enum option_type type
;
200 int OptInit(char**,struct s_options
*,FILE*);
206 /******** From the file "parse.h" *****************************************/
207 void Parse(struct lemon
*lemp
);
209 /********* From the file "plink.h" ***************************************/
210 struct plink
*Plink_new(void);
211 void Plink_add(struct plink
**, struct config
*);
212 void Plink_copy(struct plink
**, struct plink
*);
213 void Plink_delete(struct plink
*);
215 /********** From the file "report.h" *************************************/
216 void Reprint(struct lemon
*);
217 void ReportOutput(struct lemon
*);
218 void ReportTable(struct lemon
*, int);
219 void ReportHeader(struct lemon
*);
220 void CompressTables(struct lemon
*);
221 void ResortStates(struct lemon
*);
223 /********** From the file "set.h" ****************************************/
224 void SetSize(int); /* All sets will be of size N */
225 char *SetNew(void); /* A new set for element 0..N */
226 void SetFree(char*); /* Deallocate a set */
227 int SetAdd(char*,int); /* Add element to a set */
228 int SetUnion(char *,char *); /* A <- A U B, thru element N */
229 #define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
231 /********** From the file "struct.h" *************************************/
233 ** Principal data structures for the LEMON parser generator.
236 typedef enum {LEMON_FALSE
=0, LEMON_TRUE
} Boolean
;
238 /* Symbols (terminals and nonterminals) of the grammar are stored
239 ** in the following: */
252 const char *name
; /* Name of the symbol */
253 int index
; /* Index number for this symbol */
254 enum symbol_type type
; /* Symbols are all either TERMINALS or NTs */
255 struct rule
*rule
; /* Linked list of rules of this (if an NT) */
256 struct symbol
*fallback
; /* fallback token in case this token doesn't parse */
257 int prec
; /* Precedence if defined (-1 otherwise) */
258 enum e_assoc assoc
; /* Associativity if precedence is defined */
259 char *firstset
; /* First-set for all rules of this symbol */
260 Boolean lambda
; /* True if NT and can generate an empty string */
261 int useCnt
; /* Number of times used */
262 char *destructor
; /* Code which executes whenever this symbol is
263 ** popped from the stack during error processing */
264 int destLineno
; /* Line number for start of destructor */
265 char *datatype
; /* The data type of information held by this
266 ** object. Only used if type==NONTERMINAL */
267 int dtnum
; /* The data type number. In the parser, the value
268 ** stack is a union. The .yy%d element of this
269 ** union is the correct data type for this object */
270 /* The following fields are used by MULTITERMINALs only */
271 int nsubsym
; /* Number of constituent symbols in the MULTI */
272 struct symbol
**subsym
; /* Array of constituent symbols */
275 /* Each production rule in the grammar is stored in the following
278 struct symbol
*lhs
; /* Left-hand side of the rule */
279 const char *lhsalias
; /* Alias for the LHS (NULL if none) */
280 int lhsStart
; /* True if left-hand side is the start symbol */
281 int ruleline
; /* Line number for the rule */
282 int nrhs
; /* Number of RHS symbols */
283 struct symbol
**rhs
; /* The RHS symbols */
284 const char **rhsalias
; /* An alias for each RHS symbol (NULL if none) */
285 int line
; /* Line number at which code begins */
286 const char *code
; /* The code executed when this rule is reduced */
287 struct symbol
*precsym
; /* Precedence symbol for this rule */
288 int index
; /* An index number for this rule */
289 Boolean canReduce
; /* True if this rule is ever reduced */
290 struct rule
*nextlhs
; /* Next rule with the same LHS */
291 struct rule
*next
; /* Next rule in the global list */
294 /* A configuration is a production rule of the grammar together with
295 ** a mark (dot) showing how much of that rule has been processed so far.
296 ** Configurations also contain a follow-set which is a list of terminal
297 ** symbols which are allowed to immediately follow the end of the rule.
298 ** Every configuration is recorded as an instance of the following: */
304 struct rule
*rp
; /* The rule upon which the configuration is based */
305 int dot
; /* The parse point */
306 char *fws
; /* Follow-set for this configuration only */
307 struct plink
*fplp
; /* Follow-set forward propagation links */
308 struct plink
*bplp
; /* Follow-set backwards propagation links */
309 struct state
*stp
; /* Pointer to state which contains this */
310 enum cfgstatus status
; /* used during followset and shift computations */
311 struct config
*next
; /* Next configuration in the state */
312 struct config
*bp
; /* The next basis configuration */
320 SSCONFLICT
, /* A shift/shift conflict */
321 SRCONFLICT
, /* Was a reduce, but part of a conflict */
322 RRCONFLICT
, /* Was a reduce, but part of a conflict */
323 SH_RESOLVED
, /* Was a shift. Precedence resolved conflict */
324 RD_RESOLVED
, /* Was reduce. Precedence resolved conflict */
325 NOT_USED
/* Deleted by compression */
328 /* Every shift or reduce operation is stored as one of the following */
330 struct symbol
*sp
; /* The look-ahead symbol */
333 struct state
*stp
; /* The new state, if a shift */
334 struct rule
*rp
; /* The rule, if a reduce */
336 struct action
*next
; /* Next action for this state */
337 struct action
*collide
; /* Next action with the same hash */
340 /* Each state of the generated parser's finite state machine
341 ** is encoded as an instance of the following structure. */
343 struct config
*bp
; /* The basis configurations for this state */
344 struct config
*cfp
; /* All configurations in this set */
345 int statenum
; /* Sequential number for this state */
346 struct action
*ap
; /* Array of actions for this state */
347 int nTknAct
, nNtAct
; /* Number of actions on terminals and nonterminals */
348 int iTknOfst
, iNtOfst
; /* yy_action[] offset for terminals and nonterms */
349 int iDflt
; /* Default action */
351 #define NO_OFFSET (-2147483647)
353 /* A followset propagation link indicates that the contents of one
354 ** configuration followset should be propagated to another whenever
355 ** the first changes. */
357 struct config
*cfp
; /* The configuration to which linked */
358 struct plink
*next
; /* The next propagate link */
361 /* The state vector for the entire parser generator is recorded as
362 ** follows. (LEMON uses no global variables and makes little use of
363 ** static variables. Fields in the following structure can be thought
364 ** of as begin global variables in the program.) */
366 struct state
**sorted
; /* Table of states sorted by state number */
367 struct rule
*rule
; /* List of all rules */
368 int nstate
; /* Number of states */
369 int nrule
; /* Number of rules */
370 int nsymbol
; /* Number of terminal and nonterminal symbols */
371 int nterminal
; /* Number of terminal symbols */
372 struct symbol
**symbols
; /* Sorted array of pointers to symbols */
373 int errorcnt
; /* Number of errors */
374 struct symbol
*errsym
; /* The error symbol */
375 struct symbol
*wildcard
; /* Token that matches anything */
376 char *name
; /* Name of the generated parser */
377 char *arg
; /* Declaration of the 3th argument to parser */
378 char *tokentype
; /* Type of terminal symbols in the parser stack */
379 char *vartype
; /* The default type of non-terminal symbols */
380 char *start
; /* Name of the start symbol for the grammar */
381 char *stacksize
; /* Size of the parser stack */
382 char *include
; /* Code to put at the start of the C file */
383 char *error
; /* Code to execute when an error is seen */
384 char *overflow
; /* Code to execute on a stack overflow */
385 char *failure
; /* Code to execute on parser failure */
386 char *accept
; /* Code to execute when the parser excepts */
387 char *extracode
; /* Code appended to the generated file */
388 char *tokendest
; /* Code to execute to destroy token data */
389 char *vardest
; /* Code for the default non-terminal destructor */
390 char *filename
; /* Name of the input file */
391 char *outname
; /* Name of the current output file */
392 char *tokenprefix
; /* A prefix added to token names in the .h file */
393 int nconflict
; /* Number of parsing conflicts */
394 int tablesize
; /* Size of the parse tables */
395 int basisflag
; /* Print only basis configurations */
396 int has_fallback
; /* True if any %fallback is seen in the grammar */
397 int nolinenosflag
; /* True if #line statements should not be printed */
398 char *argv0
; /* Name of the program */
401 #define MemoryCheck(X) if((X)==0){ \
402 extern void memory_error(); \
406 /**************** From the file "table.h" *********************************/
408 ** All code in this file has been automatically generated
409 ** from a specification in the file
411 ** by the associative array code building program "aagen".
412 ** Do not edit this file! Instead, edit the specification
413 ** file, then rerun aagen.
416 ** Code for processing tables in the LEMON parser generator.
418 /* Routines for handling strings */
420 const char *Strsafe(const char *);
422 void Strsafe_init(void);
423 int Strsafe_insert(const char *);
424 const char *Strsafe_find(const char *);
426 /* Routines for handling symbols of the grammar */
428 struct symbol
*Symbol_new(const char *);
429 int Symbolcmpp(const void *, const void *);
430 void Symbol_init(void);
431 int Symbol_insert(struct symbol
*, const char *);
432 struct symbol
*Symbol_find(const char *);
433 struct symbol
*Symbol_Nth(int);
434 int Symbol_count(void);
435 struct symbol
**Symbol_arrayof(void);
437 /* Routines to manage the state table */
439 int Configcmp(const char *, const char *);
440 struct state
*State_new(void);
441 void State_init(void);
442 int State_insert(struct state
*, struct config
*);
443 struct state
*State_find(struct config
*);
444 struct state
**State_arrayof(/* */);
446 /* Routines used for efficiency in Configlist_add */
448 void Configtable_init(void);
449 int Configtable_insert(struct config
*);
450 struct config
*Configtable_find(struct config
*);
451 void Configtable_clear(int(*)(struct config
*));
453 /****************** From the file "action.c" *******************************/
455 ** Routines processing parser actions in the LEMON parser generator.
458 /* Allocate a new parser action */
459 static struct action
*Action_new(void){
460 static struct action
*freelist
= 0;
461 struct action
*newaction
;
466 freelist
= (struct action
*)calloc(amt
, sizeof(struct action
));
468 fprintf(stderr
,"Unable to allocate memory for a new parser action.");
471 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
472 freelist
[amt
-1].next
= 0;
474 newaction
= freelist
;
475 freelist
= freelist
->next
;
479 /* Compare two actions for sorting purposes. Return negative, zero, or
480 ** positive if the first action is less than, equal to, or greater than
483 static int actioncmp(
484 const char *char_ap1
,
487 const struct action
*ap1
= (const struct action
*)char_ap1
;
488 const struct action
*ap2
= (const struct action
*)char_ap2
;
490 rc
= ap1
->sp
->index
- ap2
->sp
->index
;
492 rc
= (int)ap1
->type
- (int)ap2
->type
;
494 if( rc
==0 && ap1
->type
==REDUCE
){
495 rc
= ap1
->x
.rp
->index
- ap2
->x
.rp
->index
;
498 rc
= (int) (ap2
- ap1
);
503 /* Sort parser actions */
504 static struct action
*Action_sort(
507 /* Cast to "char **" via "void *" to avoid aliasing problems. */
508 ap
= (struct action
*)msort((char *)ap
,(char **)(void *)&ap
->next
,actioncmp
);
518 struct action
*newaction
;
519 newaction
= Action_new();
520 newaction
->next
= *app
;
522 newaction
->type
= type
;
525 newaction
->x
.stp
= (struct state
*)arg
;
527 newaction
->x
.rp
= (struct rule
*)arg
;
530 /********************** New code to implement the "acttab" module ***********/
532 ** This module implements routines use to construct the yy_action[] table.
536 ** The state of the yy_action table under construction is an instance of
537 ** the following structure.
539 ** The yy_action table maps the pair (state_number, lookahead) into an
540 ** action_number. The table is an array of integers pairs. The state_number
541 ** determines an initial offset into the yy_action array. The lookahead
542 ** value is then added to this initial offset to get an index X into the
543 ** yy_action array. If the aAction[X].lookahead equals the value of the
544 ** of the lookahead input, then the value of the action_number output is
545 ** aAction[X].action. If the lookaheads do not match then the
546 ** default action for the state_number is returned.
548 ** All actions associated with a single state_number are first entered
549 ** into aLookahead[] using multiple calls to acttab_action(). Then the
550 ** actions for that single state_number are placed into the aAction[]
551 ** array with a single call to acttab_insert(). The acttab_insert() call
552 ** also resets the aLookahead[] array in preparation for the next
555 struct lookahead_action
{
556 int lookahead
; /* Value of the lookahead token */
557 int action
; /* Action to take on the given lookahead */
559 typedef struct acttab acttab
;
561 int nAction
; /* Number of used slots in aAction[] */
562 int nActionAlloc
; /* Slots allocated for aAction[] */
563 struct lookahead_action
564 *aAction
, /* The yy_action[] table under construction */
565 *aLookahead
; /* A single new transaction set */
566 int mnLookahead
; /* Minimum aLookahead[].lookahead */
567 int mnAction
; /* Action associated with mnLookahead */
568 int mxLookahead
; /* Maximum aLookahead[].lookahead */
569 int nLookahead
; /* Used slots in aLookahead[] */
570 int nLookaheadAlloc
; /* Slots allocated in aLookahead[] */
573 /* Return the number of entries in the yy_action table */
574 #define acttab_size(X) ((X)->nAction)
576 /* The value for the N-th entry in yy_action */
577 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
579 /* The value for the N-th entry in yy_lookahead */
580 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
582 /* Free all memory associated with the given acttab */
583 void acttab_free(acttab
*p
){
585 free( p
->aLookahead
);
589 /* Allocate a new acttab structure */
590 acttab
*acttab_alloc(void){
591 acttab
*p
= (acttab
*) calloc( 1, sizeof(*p
) );
593 fprintf(stderr
,"Unable to allocate memory for a new acttab.");
596 memset(p
, 0, sizeof(*p
));
600 /* Add a new action to the current transaction set.
602 ** This routine is called once for each lookahead for a particular
605 void acttab_action(acttab
*p
, int lookahead
, int action
){
606 if( p
->nLookahead
>=p
->nLookaheadAlloc
){
607 p
->nLookaheadAlloc
+= 25;
608 p
->aLookahead
= (struct lookahead_action
*) realloc( p
->aLookahead
,
609 sizeof(p
->aLookahead
[0])*p
->nLookaheadAlloc
);
610 if( p
->aLookahead
==0 ){
611 fprintf(stderr
,"malloc failed\n");
615 if( p
->nLookahead
==0 ){
616 p
->mxLookahead
= lookahead
;
617 p
->mnLookahead
= lookahead
;
618 p
->mnAction
= action
;
620 if( p
->mxLookahead
<lookahead
) p
->mxLookahead
= lookahead
;
621 if( p
->mnLookahead
>lookahead
){
622 p
->mnLookahead
= lookahead
;
623 p
->mnAction
= action
;
626 p
->aLookahead
[p
->nLookahead
].lookahead
= lookahead
;
627 p
->aLookahead
[p
->nLookahead
].action
= action
;
632 ** Add the transaction set built up with prior calls to acttab_action()
633 ** into the current action table. Then reset the transaction set back
634 ** to an empty set in preparation for a new round of acttab_action() calls.
636 ** Return the offset into the action table of the new transaction.
638 int acttab_insert(acttab
*p
){
640 assert( p
->nLookahead
>0 );
642 /* Make sure we have enough space to hold the expanded action table
643 ** in the worst case. The worst case occurs if the transaction set
644 ** must be appended to the current action table
646 n
= p
->mxLookahead
+ 1;
647 if( p
->nAction
+ n
>= p
->nActionAlloc
){
648 int oldAlloc
= p
->nActionAlloc
;
649 p
->nActionAlloc
= p
->nAction
+ n
+ p
->nActionAlloc
+ 20;
650 p
->aAction
= (struct lookahead_action
*) realloc( p
->aAction
,
651 sizeof(p
->aAction
[0])*p
->nActionAlloc
);
653 fprintf(stderr
,"malloc failed\n");
656 for(i
=oldAlloc
; i
<p
->nActionAlloc
; i
++){
657 p
->aAction
[i
].lookahead
= -1;
658 p
->aAction
[i
].action
= -1;
662 /* Scan the existing action table looking for an offset that is a
663 ** duplicate of the current transaction set. Fall out of the loop
664 ** if and when the duplicate is found.
666 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
668 for(i
=p
->nAction
-1; i
>=0; i
--){
669 if( p
->aAction
[i
].lookahead
==p
->mnLookahead
){
670 /* All lookaheads and actions in the aLookahead[] transaction
671 ** must match against the candidate aAction[i] entry. */
672 if( p
->aAction
[i
].action
!=p
->mnAction
) continue;
673 for(j
=0; j
<p
->nLookahead
; j
++){
674 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
675 if( k
<0 || k
>=p
->nAction
) break;
676 if( p
->aLookahead
[j
].lookahead
!=p
->aAction
[k
].lookahead
) break;
677 if( p
->aLookahead
[j
].action
!=p
->aAction
[k
].action
) break;
679 if( j
<p
->nLookahead
) continue;
681 /* No possible lookahead value that is not in the aLookahead[]
682 ** transaction is allowed to match aAction[i] */
684 for(j
=0; j
<p
->nAction
; j
++){
685 if( p
->aAction
[j
].lookahead
<0 ) continue;
686 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) n
++;
688 if( n
==p
->nLookahead
){
689 break; /* An exact match is found at offset i */
694 /* If no existing offsets exactly match the current transaction, find an
695 ** an empty offset in the aAction[] table in which we can add the
696 ** aLookahead[] transaction.
699 /* Look for holes in the aAction[] table that fit the current
700 ** aLookahead[] transaction. Leave i set to the offset of the hole.
701 ** If no holes are found, i is left at p->nAction, which means the
702 ** transaction will be appended. */
703 for(i
=0; i
<p
->nActionAlloc
- p
->mxLookahead
; i
++){
704 if( p
->aAction
[i
].lookahead
<0 ){
705 for(j
=0; j
<p
->nLookahead
; j
++){
706 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
708 if( p
->aAction
[k
].lookahead
>=0 ) break;
710 if( j
<p
->nLookahead
) continue;
711 for(j
=0; j
<p
->nAction
; j
++){
712 if( p
->aAction
[j
].lookahead
==j
+p
->mnLookahead
-i
) break;
715 break; /* Fits in empty slots */
720 /* Insert transaction set at index i. */
721 for(j
=0; j
<p
->nLookahead
; j
++){
722 k
= p
->aLookahead
[j
].lookahead
- p
->mnLookahead
+ i
;
723 p
->aAction
[k
] = p
->aLookahead
[j
];
724 if( k
>=p
->nAction
) p
->nAction
= k
+1;
728 /* Return the offset that is added to the lookahead in order to get the
729 ** index into yy_action of the action */
730 return i
- p
->mnLookahead
;
733 /********************** From the file "build.c" *****************************/
735 ** Routines to construction the finite state machine for the LEMON
739 /* Find a precedence symbol of every rule in the grammar.
741 ** Those rules which have a precedence symbol coded in the input
742 ** grammar using the "[symbol]" construct will already have the
743 ** rp->precsym field filled. Other rules take as their precedence
744 ** symbol the first RHS symbol with a defined precedence. If there
745 ** are not RHS symbols with a defined precedence, the precedence
746 ** symbol field is left blank.
748 void FindRulePrecedences(struct lemon
*xp
)
751 for(rp
=xp
->rule
; rp
; rp
=rp
->next
){
752 if( rp
->precsym
==0 ){
754 for(i
=0; i
<rp
->nrhs
&& rp
->precsym
==0; i
++){
755 struct symbol
*sp
= rp
->rhs
[i
];
756 if( sp
->type
==MULTITERMINAL
){
757 for(j
=0; j
<sp
->nsubsym
; j
++){
758 if( sp
->subsym
[j
]->prec
>=0 ){
759 rp
->precsym
= sp
->subsym
[j
];
763 }else if( sp
->prec
>=0 ){
764 rp
->precsym
= rp
->rhs
[i
];
772 /* Find all nonterminals which will generate the empty string.
773 ** Then go back and compute the first sets of every nonterminal.
774 ** The first set is the set of all terminal symbols which can begin
775 ** a string generated by that nonterminal.
777 void FindFirstSets(struct lemon
*lemp
)
783 for(i
=0; i
<lemp
->nsymbol
; i
++){
784 lemp
->symbols
[i
]->lambda
= LEMON_FALSE
;
786 for(i
=lemp
->nterminal
; i
<lemp
->nsymbol
; i
++){
787 lemp
->symbols
[i
]->firstset
= SetNew();
790 /* First compute all lambdas */
793 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
794 if( rp
->lhs
->lambda
) continue;
795 for(i
=0; i
<rp
->nrhs
; i
++){
796 struct symbol
*sp
= rp
->rhs
[i
];
797 assert( sp
->type
==NONTERMINAL
|| sp
->lambda
==LEMON_FALSE
);
798 if( sp
->lambda
==LEMON_FALSE
) break;
801 rp
->lhs
->lambda
= LEMON_TRUE
;
807 /* Now compute all first sets */
809 struct symbol
*s1
, *s2
;
811 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
813 for(i
=0; i
<rp
->nrhs
; i
++){
815 if( s2
->type
==TERMINAL
){
816 progress
+= SetAdd(s1
->firstset
,s2
->index
);
818 }else if( s2
->type
==MULTITERMINAL
){
819 for(j
=0; j
<s2
->nsubsym
; j
++){
820 progress
+= SetAdd(s1
->firstset
,s2
->subsym
[j
]->index
);
824 if( s1
->lambda
==LEMON_FALSE
) break;
826 progress
+= SetUnion(s1
->firstset
,s2
->firstset
);
827 if( s2
->lambda
==LEMON_FALSE
) break;
835 /* Compute all LR(0) states for the grammar. Links
836 ** are added to between some states so that the LR(1) follow sets
837 ** can be computed later.
839 PRIVATE
struct state
*getstate(struct lemon
*); /* forward reference */
840 void FindStates(struct lemon
*lemp
)
847 /* Find the start symbol */
849 sp
= Symbol_find(lemp
->start
);
851 ErrorMsg(lemp
->filename
,0,
852 "The specified start symbol \"%s\" is not "
853 "in a nonterminal of the grammar. \"%s\" will be used as the start "
854 "symbol instead.",lemp
->start
,lemp
->rule
->lhs
->name
);
856 sp
= lemp
->rule
->lhs
;
859 sp
= lemp
->rule
->lhs
;
862 /* Make sure the start symbol doesn't occur on the right-hand side of
863 ** any rule. Report an error if it does. (YACC would generate a new
864 ** start symbol in this case.) */
865 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
867 for(i
=0; i
<rp
->nrhs
; i
++){
868 if( rp
->rhs
[i
]==sp
){ /* FIX ME: Deal with multiterminals */
869 ErrorMsg(lemp
->filename
,0,
870 "The start symbol \"%s\" occurs on the "
871 "right-hand side of a rule. This will result in a parser which "
872 "does not work properly.",sp
->name
);
878 /* The basis configuration set for the first state
879 ** is all rules which have the start symbol as their
881 for(rp
=sp
->rule
; rp
; rp
=rp
->nextlhs
){
882 struct config
*newcfp
;
884 newcfp
= Configlist_addbasis(rp
,0);
885 SetAdd(newcfp
->fws
,0);
888 /* Compute the first state. All other states will be
889 ** computed automatically during the computation of the first one.
890 ** The returned pointer to the first state is not used. */
891 (void)getstate(lemp
);
895 /* Return a pointer to a state which is described by the configuration
896 ** list which has been built from calls to Configlist_add.
898 PRIVATE
void buildshifts(struct lemon
*, struct state
*); /* Forwd ref */
899 PRIVATE
struct state
*getstate(struct lemon
*lemp
)
901 struct config
*cfp
, *bp
;
904 /* Extract the sorted basis of the new state. The basis was constructed
905 ** by prior calls to "Configlist_addbasis()". */
906 Configlist_sortbasis();
907 bp
= Configlist_basis();
909 /* Get a state with the same basis */
910 stp
= State_find(bp
);
912 /* A state with the same basis already exists! Copy all the follow-set
913 ** propagation links from the state under construction into the
914 ** preexisting state, then return a pointer to the preexisting state */
915 struct config
*x
, *y
;
916 for(x
=bp
, y
=stp
->bp
; x
&& y
; x
=x
->bp
, y
=y
->bp
){
917 Plink_copy(&y
->bplp
,x
->bplp
);
918 Plink_delete(x
->fplp
);
919 x
->fplp
= x
->bplp
= 0;
921 cfp
= Configlist_return();
924 /* This really is a new state. Construct all the details */
925 Configlist_closure(lemp
); /* Compute the configuration closure */
926 Configlist_sort(); /* Sort the configuration closure */
927 cfp
= Configlist_return(); /* Get a pointer to the config list */
928 stp
= State_new(); /* A new state structure */
930 stp
->bp
= bp
; /* Remember the configuration basis */
931 stp
->cfp
= cfp
; /* Remember the configuration closure */
932 stp
->statenum
= lemp
->nstate
++; /* Every state gets a sequence number */
933 stp
->ap
= 0; /* No actions, yet. */
934 State_insert(stp
,stp
->bp
); /* Add to the state table */
935 buildshifts(lemp
,stp
); /* Recursively compute successor states */
941 ** Return true if two symbols are the same.
943 int same_symbol(struct symbol
*a
, struct symbol
*b
)
947 if( a
->type
!=MULTITERMINAL
) return 0;
948 if( b
->type
!=MULTITERMINAL
) return 0;
949 if( a
->nsubsym
!=b
->nsubsym
) return 0;
950 for(i
=0; i
<a
->nsubsym
; i
++){
951 if( a
->subsym
[i
]!=b
->subsym
[i
] ) return 0;
956 /* Construct all successor states to the given state. A "successor"
957 ** state is any state which can be reached by a shift action.
959 PRIVATE
void buildshifts(struct lemon
*lemp
, struct state
*stp
)
961 struct config
*cfp
; /* For looping thru the config closure of "stp" */
962 struct config
*bcfp
; /* For the inner loop on config closure of "stp" */
963 struct config
*newcfg
; /* */
964 struct symbol
*sp
; /* Symbol following the dot in configuration "cfp" */
965 struct symbol
*bsp
; /* Symbol following the dot in configuration "bcfp" */
966 struct state
*newstp
; /* A pointer to a successor state */
968 /* Each configuration becomes complete after it contributes to a successor
969 ** state. Initially, all configurations are incomplete */
970 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
) cfp
->status
= INCOMPLETE
;
972 /* Loop through all configurations of the state "stp" */
973 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
974 if( cfp
->status
==COMPLETE
) continue; /* Already used by inner loop */
975 if( cfp
->dot
>=cfp
->rp
->nrhs
) continue; /* Can't shift this config */
976 Configlist_reset(); /* Reset the new config set */
977 sp
= cfp
->rp
->rhs
[cfp
->dot
]; /* Symbol after the dot */
979 /* For every configuration in the state "stp" which has the symbol "sp"
980 ** following its dot, add the same configuration to the basis set under
981 ** construction but with the dot shifted one symbol to the right. */
982 for(bcfp
=cfp
; bcfp
; bcfp
=bcfp
->next
){
983 if( bcfp
->status
==COMPLETE
) continue; /* Already used */
984 if( bcfp
->dot
>=bcfp
->rp
->nrhs
) continue; /* Can't shift this one */
985 bsp
= bcfp
->rp
->rhs
[bcfp
->dot
]; /* Get symbol after dot */
986 if( !same_symbol(bsp
,sp
) ) continue; /* Must be same as for "cfp" */
987 bcfp
->status
= COMPLETE
; /* Mark this config as used */
988 newcfg
= Configlist_addbasis(bcfp
->rp
,bcfp
->dot
+1);
989 Plink_add(&newcfg
->bplp
,bcfp
);
992 /* Get a pointer to the state described by the basis configuration set
993 ** constructed in the preceding loop */
994 newstp
= getstate(lemp
);
996 /* The state "newstp" is reached from the state "stp" by a shift action
997 ** on the symbol "sp" */
998 if( sp
->type
==MULTITERMINAL
){
1000 for(i
=0; i
<sp
->nsubsym
; i
++){
1001 Action_add(&stp
->ap
,SHIFT
,sp
->subsym
[i
],(char*)newstp
);
1004 Action_add(&stp
->ap
,SHIFT
,sp
,(char *)newstp
);
1010 ** Construct the propagation links
1012 void FindLinks(struct lemon
*lemp
)
1015 struct config
*cfp
, *other
;
1019 /* Housekeeping detail:
1020 ** Add to every propagate link a pointer back to the state to
1021 ** which the link is attached. */
1022 for(i
=0; i
<lemp
->nstate
; i
++){
1023 stp
= lemp
->sorted
[i
];
1024 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1029 /* Convert all backlinks into forward links. Only the forward
1030 ** links are used in the follow-set computation. */
1031 for(i
=0; i
<lemp
->nstate
; i
++){
1032 stp
= lemp
->sorted
[i
];
1033 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){
1034 for(plp
=cfp
->bplp
; plp
; plp
=plp
->next
){
1036 Plink_add(&other
->fplp
,cfp
);
1042 /* Compute all followsets.
1044 ** A followset is the set of all symbols which can come immediately
1045 ** after a configuration.
1047 void FindFollowSets(struct lemon
*lemp
)
1055 for(i
=0; i
<lemp
->nstate
; i
++){
1056 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1057 cfp
->status
= INCOMPLETE
;
1063 for(i
=0; i
<lemp
->nstate
; i
++){
1064 for(cfp
=lemp
->sorted
[i
]->cfp
; cfp
; cfp
=cfp
->next
){
1065 if( cfp
->status
==COMPLETE
) continue;
1066 for(plp
=cfp
->fplp
; plp
; plp
=plp
->next
){
1067 change
= SetUnion(plp
->cfp
->fws
,cfp
->fws
);
1069 plp
->cfp
->status
= INCOMPLETE
;
1073 cfp
->status
= COMPLETE
;
1079 static int resolve_conflict(struct action
*,struct action
*);
1081 /* Compute the reduce actions, and resolve conflicts.
1083 void FindActions(struct lemon
*lemp
)
1091 /* Add all of the reduce actions
1092 ** A reduce action is added for each element of the followset of
1093 ** a configuration which has its dot at the extreme right.
1095 for(i
=0; i
<lemp
->nstate
; i
++){ /* Loop over all states */
1096 stp
= lemp
->sorted
[i
];
1097 for(cfp
=stp
->cfp
; cfp
; cfp
=cfp
->next
){ /* Loop over all configurations */
1098 if( cfp
->rp
->nrhs
==cfp
->dot
){ /* Is dot at extreme right? */
1099 for(j
=0; j
<lemp
->nterminal
; j
++){
1100 if( SetFind(cfp
->fws
,j
) ){
1101 /* Add a reduce action to the state "stp" which will reduce by the
1102 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
1103 Action_add(&stp
->ap
,REDUCE
,lemp
->symbols
[j
],(char *)cfp
->rp
);
1110 /* Add the accepting token */
1112 sp
= Symbol_find(lemp
->start
);
1113 if( sp
==0 ) sp
= lemp
->rule
->lhs
;
1115 sp
= lemp
->rule
->lhs
;
1117 /* Add to the first state (which is always the starting state of the
1118 ** finite state machine) an action to ACCEPT if the lookahead is the
1119 ** start nonterminal. */
1120 Action_add(&lemp
->sorted
[0]->ap
,ACCEPT
,sp
,0);
1122 /* Resolve conflicts */
1123 for(i
=0; i
<lemp
->nstate
; i
++){
1124 struct action
*ap
, *nap
;
1126 stp
= lemp
->sorted
[i
];
1127 /* assert( stp->ap ); */
1128 stp
->ap
= Action_sort(stp
->ap
);
1129 for(ap
=stp
->ap
; ap
&& ap
->next
; ap
=ap
->next
){
1130 for(nap
=ap
->next
; nap
&& nap
->sp
==ap
->sp
; nap
=nap
->next
){
1131 /* The two actions "ap" and "nap" have the same lookahead.
1132 ** Figure out which one should be used */
1133 lemp
->nconflict
+= resolve_conflict(ap
,nap
);
1138 /* Report an error for each rule that can never be reduced. */
1139 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
) rp
->canReduce
= LEMON_FALSE
;
1140 for(i
=0; i
<lemp
->nstate
; i
++){
1142 for(ap
=lemp
->sorted
[i
]->ap
; ap
; ap
=ap
->next
){
1143 if( ap
->type
==REDUCE
) ap
->x
.rp
->canReduce
= LEMON_TRUE
;
1146 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
1147 if( rp
->canReduce
) continue;
1148 ErrorMsg(lemp
->filename
,rp
->ruleline
,"This rule can not be reduced.\n");
1153 /* Resolve a conflict between the two given actions. If the
1154 ** conflict can't be resolved, return non-zero.
1157 ** To resolve a conflict, first look to see if either action
1158 ** is on an error rule. In that case, take the action which
1159 ** is not associated with the error rule. If neither or both
1160 ** actions are associated with an error rule, then try to
1161 ** use precedence to resolve the conflict.
1163 ** If either action is a SHIFT, then it must be apx. This
1164 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1166 static int resolve_conflict(
1170 struct symbol
*spx
, *spy
;
1172 assert( apx
->sp
==apy
->sp
); /* Otherwise there would be no conflict */
1173 if( apx
->type
==SHIFT
&& apy
->type
==SHIFT
){
1174 apy
->type
= SSCONFLICT
;
1177 if( apx
->type
==SHIFT
&& apy
->type
==REDUCE
){
1179 spy
= apy
->x
.rp
->precsym
;
1180 if( spy
==0 || spx
->prec
<0 || spy
->prec
<0 ){
1181 /* Not enough precedence information. */
1182 apy
->type
= SRCONFLICT
;
1184 }else if( spx
->prec
>spy
->prec
){ /* higher precedence wins */
1185 apy
->type
= RD_RESOLVED
;
1186 }else if( spx
->prec
<spy
->prec
){
1187 apx
->type
= SH_RESOLVED
;
1188 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==RIGHT
){ /* Use operator */
1189 apy
->type
= RD_RESOLVED
; /* associativity */
1190 }else if( spx
->prec
==spy
->prec
&& spx
->assoc
==LEFT
){ /* to break tie */
1191 apx
->type
= SH_RESOLVED
;
1193 assert( spx
->prec
==spy
->prec
&& spx
->assoc
==NONE
);
1196 }else if( apx
->type
==REDUCE
&& apy
->type
==REDUCE
){
1197 spx
= apx
->x
.rp
->precsym
;
1198 spy
= apy
->x
.rp
->precsym
;
1199 if( spx
==0 || spy
==0 || spx
->prec
<0 ||
1200 spy
->prec
<0 || spx
->prec
==spy
->prec
){
1201 apy
->type
= RRCONFLICT
;
1203 }else if( spx
->prec
>spy
->prec
){
1204 apy
->type
= RD_RESOLVED
;
1205 }else if( spx
->prec
<spy
->prec
){
1206 apx
->type
= RD_RESOLVED
;
1210 apx
->type
==SH_RESOLVED
||
1211 apx
->type
==RD_RESOLVED
||
1212 apx
->type
==SSCONFLICT
||
1213 apx
->type
==SRCONFLICT
||
1214 apx
->type
==RRCONFLICT
||
1215 apy
->type
==SH_RESOLVED
||
1216 apy
->type
==RD_RESOLVED
||
1217 apy
->type
==SSCONFLICT
||
1218 apy
->type
==SRCONFLICT
||
1219 apy
->type
==RRCONFLICT
1221 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1222 ** REDUCEs on the list. If we reach this point it must be because
1223 ** the parser conflict had already been resolved. */
1227 /********************* From the file "configlist.c" *************************/
1229 ** Routines to processing a configuration list and building a state
1230 ** in the LEMON parser generator.
1233 static struct config
*freelist
= 0; /* List of free configurations */
1234 static struct config
*current
= 0; /* Top of list of configurations */
1235 static struct config
**currentend
= 0; /* Last on list of configs */
1236 static struct config
*basis
= 0; /* Top of list of basis configs */
1237 static struct config
**basisend
= 0; /* End of list of basis configs */
1239 /* Return a pointer to a new configuration */
1240 PRIVATE
struct config
*newconfig(){
1241 struct config
*newcfg
;
1245 freelist
= (struct config
*)calloc( amt
, sizeof(struct config
) );
1247 fprintf(stderr
,"Unable to allocate memory for a new configuration.");
1250 for(i
=0; i
<amt
-1; i
++) freelist
[i
].next
= &freelist
[i
+1];
1251 freelist
[amt
-1].next
= 0;
1254 freelist
= freelist
->next
;
1258 /* The configuration "old" is no longer used */
1259 PRIVATE
void deleteconfig(struct config
*old
)
1261 old
->next
= freelist
;
1265 /* Initialized the configuration list builder */
1266 void Configlist_init(){
1268 currentend
= ¤t
;
1275 /* Initialized the configuration list builder */
1276 void Configlist_reset(){
1278 currentend
= ¤t
;
1281 Configtable_clear(0);
1285 /* Add another configuration to the configuration list */
1286 struct config
*Configlist_add(
1287 struct rule
*rp
, /* The rule */
1288 int dot
/* Index into the RHS of the rule where the dot goes */
1290 struct config
*cfp
, model
;
1292 assert( currentend
!=0 );
1295 cfp
= Configtable_find(&model
);
1300 cfp
->fws
= SetNew();
1302 cfp
->fplp
= cfp
->bplp
= 0;
1306 currentend
= &cfp
->next
;
1307 Configtable_insert(cfp
);
1312 /* Add a basis configuration to the configuration list */
1313 struct config
*Configlist_addbasis(struct rule
*rp
, int dot
)
1315 struct config
*cfp
, model
;
1317 assert( basisend
!=0 );
1318 assert( currentend
!=0 );
1321 cfp
= Configtable_find(&model
);
1326 cfp
->fws
= SetNew();
1328 cfp
->fplp
= cfp
->bplp
= 0;
1332 currentend
= &cfp
->next
;
1334 basisend
= &cfp
->bp
;
1335 Configtable_insert(cfp
);
1340 /* Compute the closure of the configuration list */
1341 void Configlist_closure(struct lemon
*lemp
)
1343 struct config
*cfp
, *newcfp
;
1344 struct rule
*rp
, *newrp
;
1345 struct symbol
*sp
, *xsp
;
1348 assert( currentend
!=0 );
1349 for(cfp
=current
; cfp
; cfp
=cfp
->next
){
1352 if( dot
>=rp
->nrhs
) continue;
1354 if( sp
->type
==NONTERMINAL
){
1355 if( sp
->rule
==0 && sp
!=lemp
->errsym
){
1356 ErrorMsg(lemp
->filename
,rp
->line
,"Nonterminal \"%s\" has no rules.",
1360 for(newrp
=sp
->rule
; newrp
; newrp
=newrp
->nextlhs
){
1361 newcfp
= Configlist_add(newrp
,0);
1362 for(i
=dot
+1; i
<rp
->nrhs
; i
++){
1364 if( xsp
->type
==TERMINAL
){
1365 SetAdd(newcfp
->fws
,xsp
->index
);
1367 }else if( xsp
->type
==MULTITERMINAL
){
1369 for(k
=0; k
<xsp
->nsubsym
; k
++){
1370 SetAdd(newcfp
->fws
, xsp
->subsym
[k
]->index
);
1374 SetUnion(newcfp
->fws
,xsp
->firstset
);
1375 if( xsp
->lambda
==LEMON_FALSE
) break;
1378 if( i
==rp
->nrhs
) Plink_add(&cfp
->fplp
,newcfp
);
1385 /* Sort the configuration list */
1386 void Configlist_sort(){
1387 /* Cast to "char **" via "void *" to avoid aliasing problems. */
1388 current
= (struct config
*)msort((char *)current
,(char **)(void *)&(current
->next
),Configcmp
);
1393 /* Sort the basis configuration list */
1394 void Configlist_sortbasis(){
1395 /* Cast to "char **" via "void *" to avoid aliasing problems. */
1396 basis
= (struct config
*)msort((char *)current
,(char **)(void *)&(current
->bp
),Configcmp
);
1401 /* Return a pointer to the head of the configuration list and
1402 ** reset the list */
1403 struct config
*Configlist_return(){
1411 /* Return a pointer to the head of the configuration list and
1412 ** reset the list */
1413 struct config
*Configlist_basis(){
1421 /* Free all elements of the given configuration list */
1422 void Configlist_eat(struct config
*cfp
)
1424 struct config
*nextcfp
;
1425 for(; cfp
; cfp
=nextcfp
){
1426 nextcfp
= cfp
->next
;
1427 assert( cfp
->fplp
==0 );
1428 assert( cfp
->bplp
==0 );
1429 if( cfp
->fws
) SetFree(cfp
->fws
);
1434 /***************** From the file "error.c" *********************************/
1436 ** Code for printing error message.
1439 void ErrorMsg(const char *filename
, int lineno
, const char *format
, ...){
1441 fprintf(stderr
, "%s:%d: ", filename
, lineno
);
1442 va_start(ap
, format
);
1443 vfprintf(stderr
,format
,ap
);
1445 fprintf(stderr
, "\n");
1447 /**************** From the file "main.c" ************************************/
1449 ** Main program file for the LEMON parser generator.
1452 /* Report an out-of-memory condition and abort. This function
1453 ** is used mostly by the "MemoryCheck" macro in struct.h
1455 void memory_error(){
1456 fprintf(stderr
,"Out of memory. Aborting...\n");
1460 static int nDefine
= 0; /* Number of -D options on the command line */
1461 static char **azDefine
= 0; /* Name of the -D macros */
1463 /* This routine is called with the argument to each -D command-line option.
1464 ** Add the macro defined to the azDefine array.
1466 static void handle_D_option(char *z
){
1469 azDefine
= (char **) realloc(azDefine
, sizeof(azDefine
[0])*nDefine
);
1471 fprintf(stderr
,"out of memory\n");
1474 paz
= &azDefine
[nDefine
-1];
1475 *paz
= (char *) malloc( lemonStrlen(z
)+1 );
1477 fprintf(stderr
,"out of memory\n");
1480 lemon_strcpy(*paz
, z
);
1481 for(z
=*paz
; *z
&& *z
!='='; z
++){}
1485 static char *output_filename
= 0; /* Output filename from -o */
1487 /* This routine is called with the argument to any -o command-line option.
1489 static void handle_o_option(char *z
){
1490 output_filename
= (char *) malloc( strlen(z
)+1 );
1491 if( output_filename
==0 ){
1492 fprintf(stderr
,"out of memory\n");
1495 strcpy(output_filename
, z
);
1498 static char *output_header_filename
= 0; /* Output filename from -h */
1500 /* This routine is called with the argument to any -h command-line option.
1502 static void handle_h_option(char *z
){
1503 output_header_filename
= (char *) malloc( strlen(z
)+1 );
1504 if( output_header_filename
==0 ){
1505 fprintf(stderr
,"out of memory\n");
1508 strcpy(output_header_filename
, z
);
1511 static char *user_templatename
= NULL
;
1512 static void handle_T_option(char *z
){
1513 user_templatename
= (char *) malloc( lemonStrlen(z
)+1 );
1514 if( user_templatename
==0 ){
1517 lemon_strcpy(user_templatename
, z
);
1520 /* The main program. Parse the command line and do it... */
1521 int main(int argc
, char **argv
)
1523 static int version
= 0;
1524 static int rpflag
= 0;
1525 static int basisflag
= 0;
1526 static int compress
= 0;
1527 static int quiet
= 0;
1528 static int statistics
= 0;
1529 static int mhflag
= 0;
1530 static int nolinenosflag
= 0;
1531 static int noResort
= 0;
1532 static struct s_options options
[] = {
1533 {OPT_FLAG
, "b", (void*)&basisflag
, 0, "Print only the basis in report."},
1534 {OPT_FLAG
, "c", (void*)&compress
, 0, "Don't compress the action table."},
1535 {OPT_FSTR
, "D", 0, handle_D_option
, "Define an %ifdef macro."},
1536 {OPT_FSTR
, "T", 0, handle_T_option
, "Specify a template file."},
1537 {OPT_FLAG
, "g", (void*)&rpflag
, 0, "Print grammar without actions."},
1538 {OPT_FLAG
, "m", (void*)&mhflag
, 0, "Output a makeheaders compatible file."},
1539 {OPT_FLAG
, "l", (void*)&nolinenosflag
, 0, "Do not print #line statements."},
1540 {OPT_FLAG
, "p", (void*)&showPrecedenceConflict
, 0,
1541 "Show conflicts resolved by precedence rules"},
1542 {OPT_FLAG
, "q", (void*)&quiet
, 0, "(Quiet) Don't print the report file."},
1543 {OPT_FLAG
, "r", (void*)&noResort
, 0, "Do not sort or renumber states"},
1544 {OPT_FLAG
, "s", (void*)&statistics
, 0,
1545 "Print parser stats to standard output."},
1546 {OPT_FLAG
, "x", (void*)&version
, 0, "Print the version number."},
1547 {OPT_FSTR
, "o", 0, handle_o_option
, "Specify output filename."},
1548 {OPT_FSTR
, "h", 0, handle_h_option
, "Specify output header filename."},
1555 (void)argc
; /* Suppress "unused argument" warning. */
1556 OptInit(argv
,options
,stderr
);
1558 printf("Lemon version 1.0 (patched for Xapian)\n");
1561 if( OptNArgs()!=1 ){
1562 fprintf(stderr
,"Exactly one filename argument is required.\n");
1565 memset(&lem
, 0, sizeof(lem
));
1568 /* Initialize the machine */
1572 lem
.argv0
= argv
[0];
1573 lem
.filename
= OptArg(0);
1574 lem
.basisflag
= basisflag
;
1575 lem
.nolinenosflag
= nolinenosflag
;
1577 lem
.errsym
= Symbol_new("error");
1578 lem
.errsym
->useCnt
= 0;
1580 /* Parse the input file */
1582 if( lem
.errorcnt
) exit(lem
.errorcnt
);
1584 fprintf(stderr
,"Empty grammar.\n");
1588 /* Count and index the symbols of the grammar */
1589 Symbol_new("{default}");
1590 lem
.nsymbol
= Symbol_count();
1591 lem
.symbols
= Symbol_arrayof();
1592 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1593 qsort(lem
.symbols
,lem
.nsymbol
,sizeof(struct symbol
*), Symbolcmpp
);
1594 for(i
=0; i
<lem
.nsymbol
; i
++) lem
.symbols
[i
]->index
= i
;
1595 while( lem
.symbols
[i
-1]->type
==MULTITERMINAL
){ i
--; }
1596 assert( strcmp(lem
.symbols
[i
-1]->name
,"{default}")==0 );
1597 lem
.nsymbol
= i
- 1;
1598 for(i
=1; isupper(lem
.symbols
[i
]->name
[0]); i
++);
1601 /* Generate a reprint of the grammar, if requested on the command line */
1605 /* Initialize the size for all follow and first sets */
1606 SetSize(lem
.nterminal
+1);
1608 /* Find the precedence for every production rule (that has one) */
1609 FindRulePrecedences(&lem
);
1611 /* Compute the lambda-nonterminals and the first-sets for every
1613 FindFirstSets(&lem
);
1615 /* Compute all LR(0) states. Also record follow-set propagation
1616 ** links so that the follow-set can be computed later */
1619 lem
.sorted
= State_arrayof();
1621 /* Tie up loose ends on the propagation links */
1624 /* Compute the follow set of every reducible configuration */
1625 FindFollowSets(&lem
);
1627 /* Compute the action tables */
1630 /* Compress the action tables */
1631 if( compress
==0 ) CompressTables(&lem
);
1633 /* Reorder and renumber the states so that states with fewer choices
1634 ** occur at the end. This is an optimization that helps make the
1635 ** generated parser tables smaller. */
1636 if( noResort
==0 ) ResortStates(&lem
);
1638 /* Generate a report of the parser generated. (the "y.output" file) */
1639 if( !quiet
) ReportOutput(&lem
);
1641 /* Generate the source code for the parser */
1642 ReportTable(&lem
, mhflag
);
1644 /* Produce a header file for use by the scanner. (This step is
1645 ** omitted if the "-m" option is used because makeheaders will
1646 ** generate the file for us.) */
1647 if( !mhflag
) ReportHeader(&lem
);
1650 printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
1651 lem
.nterminal
, lem
.nsymbol
- lem
.nterminal
, lem
.nrule
);
1652 printf(" %d states, %d parser table entries, %d conflicts\n",
1653 lem
.nstate
, lem
.tablesize
, lem
.nconflict
);
1655 if( lem
.nconflict
> 0 ){
1656 fprintf(stderr
,"%d parsing conflicts.\n",lem
.nconflict
);
1659 /* return 0 on success, 1 on failure. */
1660 exitcode
= ((lem
.errorcnt
> 0) || (lem
.nconflict
> 0)) ? 1 : 0;
1664 /******************** From the file "msort.c" *******************************/
1666 ** A generic merge-sort program.
1669 ** Let "ptr" be a pointer to some structure which is at the head of
1670 ** a null-terminated list. Then to sort the list call:
1672 ** ptr = msort(ptr,&(ptr->next),cmpfnc);
1674 ** In the above, "cmpfnc" is a pointer to a function which compares
1675 ** two instances of the structure and returns an integer, as in
1676 ** strcmp. The second argument is a pointer to the pointer to the
1677 ** second element of the linked list. This address is used to compute
1678 ** the offset to the "next" field within the structure. The offset to
1679 ** the "next" field must be constant for all structures in the list.
1681 ** The function returns a new pointer which is the head of the list
1689 ** Return a pointer to the next structure in the linked list.
1691 #define NEXT(A) (*(char**)(((char*)A)+offset))
1695 ** a: A sorted, null-terminated linked list. (May be null).
1696 ** b: A sorted, null-terminated linked list. (May be null).
1697 ** cmp: A pointer to the comparison function.
1698 ** offset: Offset in the structure to the "next" field.
1701 ** A pointer to the head of a sorted list containing the elements
1705 ** The "next" pointers for elements in the lists a and b are
1711 int (*cmp
)(const char*,const char*),
1721 if( (*cmp
)(a
,b
)<=0 ){
1730 if( (*cmp
)(a
,b
)<=0 ){
1740 if( a
) NEXT(ptr
) = a
;
1748 ** list: Pointer to a singly-linked list of structures.
1749 ** next: Pointer to pointer to the second element of the list.
1750 ** cmp: A comparison function.
1753 ** A pointer to the head of a sorted list containing the elements
1754 ** originally in list.
1757 ** The "next" pointers for elements in list are changed.
1763 int (*cmp
)(const char*,const char*)
1765 unsigned long offset
;
1767 char *set
[LISTSIZE
];
1769 offset
= (unsigned long)next
- (unsigned long)list
;
1770 for(i
=0; i
<LISTSIZE
; i
++) set
[i
] = 0;
1775 for(i
=0; i
<LISTSIZE
-1 && set
[i
]!=0; i
++){
1776 ep
= merge(ep
,set
[i
],cmp
,offset
);
1782 for(i
=0; i
<LISTSIZE
; i
++) if( set
[i
] ) ep
= merge(set
[i
],ep
,cmp
,offset
);
1785 /************************ From the file "option.c" **************************/
1787 static struct s_options
*op
;
1788 static FILE *errstream
;
1790 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1793 ** Print the command line with a carrot pointing to the k-th character
1794 ** of the n-th field.
1796 static void errline(int n
, int k
, FILE *err
)
1799 if( argv
[0] ) fprintf(err
,"%s",argv
[0]);
1800 spcnt
= lemonStrlen(argv
[0]) + 1;
1801 for(i
=1; i
<n
&& argv
[i
]; i
++){
1802 fprintf(err
," %s",argv
[i
]);
1803 spcnt
+= lemonStrlen(argv
[i
])+1;
1806 for(; argv
[i
]; i
++) fprintf(err
," %s",argv
[i
]);
1808 fprintf(err
,"\n%*s^-- here\n",spcnt
,"");
1810 fprintf(err
,"\n%*shere --^\n",spcnt
-7,"");
1815 ** Return the index of the N-th non-switch argument. Return -1
1816 ** if N is out of range.
1818 static int argindex(int n
)
1822 if( argv
!=0 && *argv
!=0 ){
1823 for(i
=1; argv
[i
]; i
++){
1824 if( dashdash
|| !ISOPT(argv
[i
]) ){
1825 if( n
==0 ) return i
;
1828 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
1834 static char emsg
[] = "Command line syntax error: ";
1837 ** Process a flag command line argument.
1839 static int handleflags(int i
, FILE *err
)
1844 for(j
=0; op
[j
].label
; j
++){
1845 if( strncmp(&argv
[i
][1],op
[j
].label
,lemonStrlen(op
[j
].label
))==0 ) break;
1847 v
= argv
[i
][0]=='-' ? 1 : 0;
1848 if( op
[j
].label
==0 ){
1850 fprintf(err
,"%sundefined option.\n",emsg
);
1854 }else if( op
[j
].type
==OPT_FLAG
){
1855 *((int*)op
[j
].arg
) = v
;
1856 }else if( op
[j
].type
==OPT_FFLAG
){
1858 }else if( op
[j
].type
==OPT_FSTR
){
1859 (op
[j
].func
)(&argv
[i
][2]);
1862 fprintf(err
,"%smissing argument on switch.\n",emsg
);
1871 ** Process a command line switch which has an argument.
1873 static int handleswitch(int i
, FILE *err
)
1881 cp
= strchr(argv
[i
],'=');
1884 for(j
=0; op
[j
].label
; j
++){
1885 if( strcmp(argv
[i
],op
[j
].label
)==0 ) break;
1888 if( op
[j
].label
==0 ){
1890 fprintf(err
,"%sundefined option.\n",emsg
);
1896 switch( op
[j
].type
){
1900 fprintf(err
,"%soption requires an argument.\n",emsg
);
1907 dv
= strtod(cp
,&end
);
1910 fprintf(err
,"%sillegal character in floating-point argument.\n",emsg
);
1911 errline(i
,((unsigned long)end
)-(unsigned long)argv
[i
],err
);
1918 lv
= strtol(cp
,&end
,0);
1921 fprintf(err
,"%sillegal character in integer argument.\n",emsg
);
1922 errline(i
,((unsigned long)end
)-(unsigned long)argv
[i
],err
);
1932 switch( op
[j
].type
){
1937 *(double*)(op
[j
].arg
) = dv
;
1943 *(int*)(op
[j
].arg
) = lv
;
1946 (op
[j
].func
)((int)lv
);
1949 *(char**)(op
[j
].arg
) = sv
;
1959 int OptInit(char **a
, struct s_options
*o
, FILE *err
)
1965 if( argv
&& *argv
&& op
){
1967 for(i
=1; argv
[i
]; i
++){
1968 if( argv
[i
][0]=='+' || argv
[i
][0]=='-' ){
1969 errcnt
+= handleflags(i
,err
);
1970 }else if( strchr(argv
[i
],'=') ){
1971 errcnt
+= handleswitch(i
,err
);
1976 fprintf(err
,"Valid command line options for \"%s\" are:\n",*a
);
1987 if( argv
!=0 && argv
[0]!=0 ){
1988 for(i
=1; argv
[i
]; i
++){
1989 if( dashdash
|| !ISOPT(argv
[i
]) ) cnt
++;
1990 if( strcmp(argv
[i
],"--")==0 ) dashdash
= 1;
2000 return i
>=0 ? argv
[i
] : 0;
2007 if( i
>=0 ) errline(i
,0,errstream
);
2014 for(i
=0; op
[i
].label
; i
++){
2015 len
= lemonStrlen(op
[i
].label
) + 1;
2016 switch( op
[i
].type
){
2022 len
+= 9; /* length of "<integer>" */
2026 len
+= 6; /* length of "<real>" */
2030 len
+= 8; /* length of "<string>" */
2033 if( len
>max
) max
= len
;
2035 for(i
=0; op
[i
].label
; i
++){
2036 switch( op
[i
].type
){
2039 fprintf(errstream
," -%-*s %s\n",max
,op
[i
].label
,op
[i
].message
);
2043 fprintf(errstream
," %s=<integer>%*s %s\n",op
[i
].label
,
2044 (int)(max
-lemonStrlen(op
[i
].label
)-9),"",op
[i
].message
);
2048 fprintf(errstream
," %s=<real>%*s %s\n",op
[i
].label
,
2049 (int)(max
-lemonStrlen(op
[i
].label
)-6),"",op
[i
].message
);
2053 fprintf(errstream
," %s=<string>%*s %s\n",op
[i
].label
,
2054 (int)(max
-lemonStrlen(op
[i
].label
)-8),"",op
[i
].message
);
2059 /*********************** From the file "parse.c" ****************************/
2061 ** Input file parser for the LEMON parser generator.
2064 /* The state of the parser */
2067 WAITING_FOR_DECL_OR_RULE
,
2068 WAITING_FOR_DECL_KEYWORD
,
2069 WAITING_FOR_DECL_ARG
,
2070 WAITING_FOR_PRECEDENCE_SYMBOL
,
2080 RESYNC_AFTER_RULE_ERROR
,
2081 RESYNC_AFTER_DECL_ERROR
,
2082 WAITING_FOR_DESTRUCTOR_SYMBOL
,
2083 WAITING_FOR_DATATYPE_SYMBOL
,
2084 WAITING_FOR_FALLBACK_ID
,
2085 WAITING_FOR_WILDCARD_ID
,
2086 WAITING_FOR_CLASS_ID
,
2087 WAITING_FOR_CLASS_TOKEN
2090 char *filename
; /* Name of the input file */
2091 int tokenlineno
; /* Linenumber at which current token starts */
2092 int errorcnt
; /* Number of errors so far */
2093 char *tokenstart
; /* Text of current token */
2094 struct lemon
*gp
; /* Global state vector */
2095 enum e_state state
; /* The state of the parser */
2096 struct symbol
*fallback
; /* The fallback token */
2097 struct symbol
*tkclass
; /* Token class symbol */
2098 struct symbol
*lhs
; /* Left-hand side of current rule */
2099 const char *lhsalias
; /* Alias for the LHS */
2100 int nrhs
; /* Number of right-hand side symbols seen */
2101 struct symbol
*rhs
[MAXRHS
]; /* RHS symbols */
2102 const char *alias
[MAXRHS
]; /* Aliases for each RHS symbol (or NULL) */
2103 struct rule
*prevrule
; /* Previous rule parsed */
2104 const char *declkeyword
; /* Keyword of a declaration */
2105 char **declargslot
; /* Where the declaration argument should be put */
2106 int insertLineMacro
; /* Add #line before declaration insert */
2107 int *decllinenoslot
; /* Where to write declaration line number */
2108 enum e_assoc declassoc
; /* Assign this association to decl arguments */
2109 int preccounter
; /* Assign this precedence to decl arguments */
2110 struct rule
*firstrule
; /* Pointer to first rule in the grammar */
2111 struct rule
*lastrule
; /* Pointer to the most recently parsed rule */
2114 /* Parse a single token */
2115 static void parseonetoken(struct pstate
*psp
)
2118 x
= Strsafe(psp
->tokenstart
); /* Save the token permanently */
2120 printf("%s:%d: Token=[%s] state=%d\n",psp
->filename
,psp
->tokenlineno
,
2123 switch( psp
->state
){
2126 psp
->preccounter
= 0;
2127 psp
->firstrule
= psp
->lastrule
= 0;
2129 /* Fall thru to next case */
2130 case WAITING_FOR_DECL_OR_RULE
:
2132 psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2133 }else if( islower(x
[0]) ){
2134 psp
->lhs
= Symbol_new(x
);
2137 psp
->state
= WAITING_FOR_ARROW
;
2138 }else if( x
[0]=='{' ){
2139 if( psp
->prevrule
==0 ){
2140 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2141 "There is no prior rule upon which to attach the code "
2142 "fragment which begins on this line.");
2144 }else if( psp
->prevrule
->code
!=0 ){
2145 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2146 "Code fragment beginning on this line is not the first "
2147 "to follow the previous rule.");
2150 psp
->prevrule
->line
= psp
->tokenlineno
;
2151 psp
->prevrule
->code
= &x
[1];
2153 }else if( x
[0]=='[' ){
2154 psp
->state
= PRECEDENCE_MARK_1
;
2156 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2157 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2162 case PRECEDENCE_MARK_1
:
2163 if( !isupper(x
[0]) ){
2164 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2165 "The precedence symbol must be a terminal.");
2167 }else if( psp
->prevrule
==0 ){
2168 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2169 "There is no prior rule to assign precedence \"[%s]\".",x
);
2171 }else if( psp
->prevrule
->precsym
!=0 ){
2172 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2173 "Precedence mark on this line is not the first "
2174 "to follow the previous rule.");
2177 psp
->prevrule
->precsym
= Symbol_new(x
);
2179 psp
->state
= PRECEDENCE_MARK_2
;
2181 case PRECEDENCE_MARK_2
:
2183 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2184 "Missing \"]\" on precedence mark.");
2187 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2189 case WAITING_FOR_ARROW
:
2190 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2191 psp
->state
= IN_RHS
;
2192 }else if( x
[0]=='(' ){
2193 psp
->state
= LHS_ALIAS_1
;
2195 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2196 "Expected to see a \":\" following the LHS symbol \"%s\".",
2199 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2203 if( isalpha(x
[0]) ){
2205 psp
->state
= LHS_ALIAS_2
;
2207 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2208 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2211 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2216 psp
->state
= LHS_ALIAS_3
;
2218 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2219 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2221 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2225 if( x
[0]==':' && x
[1]==':' && x
[2]=='=' ){
2226 psp
->state
= IN_RHS
;
2228 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2229 "Missing \"->\" following: \"%s(%s)\".",
2230 psp
->lhs
->name
,psp
->lhsalias
);
2232 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2238 rp
= (struct rule
*)calloc( sizeof(struct rule
) +
2239 sizeof(struct symbol
*)*psp
->nrhs
+ sizeof(char*)*psp
->nrhs
, 1);
2241 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2242 "Can't allocate enough memory for this rule.");
2247 rp
->ruleline
= psp
->tokenlineno
;
2248 rp
->rhs
= (struct symbol
**)&rp
[1];
2249 rp
->rhsalias
= (const char**)&(rp
->rhs
[psp
->nrhs
]);
2250 for(i
=0; i
<psp
->nrhs
; i
++){
2251 rp
->rhs
[i
] = psp
->rhs
[i
];
2252 rp
->rhsalias
[i
] = psp
->alias
[i
];
2255 rp
->lhsalias
= psp
->lhsalias
;
2256 rp
->nrhs
= psp
->nrhs
;
2259 rp
->index
= psp
->gp
->nrule
++;
2260 rp
->nextlhs
= rp
->lhs
->rule
;
2263 if( psp
->firstrule
==0 ){
2264 psp
->firstrule
= psp
->lastrule
= rp
;
2266 psp
->lastrule
->next
= rp
;
2271 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2272 }else if( isalpha(x
[0]) ){
2273 if( psp
->nrhs
>=MAXRHS
){
2274 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2275 "Too many symbols on RHS of rule beginning at \"%s\".",
2278 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2280 psp
->rhs
[psp
->nrhs
] = Symbol_new(x
);
2281 psp
->alias
[psp
->nrhs
] = 0;
2284 }else if( (x
[0]=='|' || x
[0]=='/') && psp
->nrhs
>0 ){
2285 struct symbol
*msp
= psp
->rhs
[psp
->nrhs
-1];
2286 if( msp
->type
!=MULTITERMINAL
){
2287 struct symbol
*origsp
= msp
;
2288 msp
= (struct symbol
*) calloc(1,sizeof(*msp
));
2290 memset(msp
, 0, sizeof(*msp
));
2291 msp
->type
= MULTITERMINAL
;
2293 msp
->subsym
= (struct symbol
**) calloc(1,sizeof(struct symbol
*));
2294 MemoryCheck(msp
->subsym
);
2295 msp
->subsym
[0] = origsp
;
2296 msp
->name
= origsp
->name
;
2297 psp
->rhs
[psp
->nrhs
-1] = msp
;
2300 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2301 sizeof(struct symbol
*)*msp
->nsubsym
);
2302 MemoryCheck(msp
->subsym
);
2303 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(&x
[1]);
2304 if( islower(x
[1]) || islower(msp
->subsym
[0]->name
[0]) ){
2305 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2306 "Cannot form a compound containing a non-terminal");
2309 }else if( x
[0]=='(' && psp
->nrhs
>0 ){
2310 psp
->state
= RHS_ALIAS_1
;
2312 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2313 "Illegal character on RHS of rule: \"%s\".",x
);
2315 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2319 if( isalpha(x
[0]) ){
2320 psp
->alias
[psp
->nrhs
-1] = x
;
2321 psp
->state
= RHS_ALIAS_2
;
2323 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2324 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2325 x
,psp
->rhs
[psp
->nrhs
-1]->name
);
2327 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2332 psp
->state
= IN_RHS
;
2334 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2335 "Missing \")\" following LHS alias name \"%s\".",psp
->lhsalias
);
2337 psp
->state
= RESYNC_AFTER_RULE_ERROR
;
2340 case WAITING_FOR_DECL_KEYWORD
:
2341 if( isalpha(x
[0]) ){
2342 psp
->declkeyword
= x
;
2343 psp
->declargslot
= 0;
2344 psp
->decllinenoslot
= 0;
2345 psp
->insertLineMacro
= 1;
2346 psp
->state
= WAITING_FOR_DECL_ARG
;
2347 if( strcmp(x
,"name")==0 ){
2348 psp
->declargslot
= &(psp
->gp
->name
);
2349 psp
->insertLineMacro
= 0;
2350 }else if( strcmp(x
,"include")==0 ){
2351 psp
->declargslot
= &(psp
->gp
->include
);
2352 }else if( strcmp(x
,"code")==0 ){
2353 psp
->declargslot
= &(psp
->gp
->extracode
);
2354 }else if( strcmp(x
,"token_destructor")==0 ){
2355 psp
->declargslot
= &psp
->gp
->tokendest
;
2356 }else if( strcmp(x
,"default_destructor")==0 ){
2357 psp
->declargslot
= &psp
->gp
->vardest
;
2358 }else if( strcmp(x
,"token_prefix")==0 ){
2359 psp
->declargslot
= &psp
->gp
->tokenprefix
;
2360 psp
->insertLineMacro
= 0;
2361 }else if( strcmp(x
,"syntax_error")==0 ){
2362 psp
->declargslot
= &(psp
->gp
->error
);
2363 }else if( strcmp(x
,"parse_accept")==0 ){
2364 psp
->declargslot
= &(psp
->gp
->accept
);
2365 }else if( strcmp(x
,"parse_failure")==0 ){
2366 psp
->declargslot
= &(psp
->gp
->failure
);
2367 }else if( strcmp(x
,"stack_overflow")==0 ){
2368 psp
->declargslot
= &(psp
->gp
->overflow
);
2369 }else if( strcmp(x
,"extra_argument")==0 ){
2370 psp
->declargslot
= &(psp
->gp
->arg
);
2371 psp
->insertLineMacro
= 0;
2372 }else if( strcmp(x
,"token_type")==0 ){
2373 psp
->declargslot
= &(psp
->gp
->tokentype
);
2374 psp
->insertLineMacro
= 0;
2375 }else if( strcmp(x
,"default_type")==0 ){
2376 psp
->declargslot
= &(psp
->gp
->vartype
);
2377 psp
->insertLineMacro
= 0;
2378 }else if( strcmp(x
,"stack_size")==0 ){
2379 psp
->declargslot
= &(psp
->gp
->stacksize
);
2380 psp
->insertLineMacro
= 0;
2381 }else if( strcmp(x
,"start_symbol")==0 ){
2382 psp
->declargslot
= &(psp
->gp
->start
);
2383 psp
->insertLineMacro
= 0;
2384 }else if( strcmp(x
,"left")==0 ){
2386 psp
->declassoc
= LEFT
;
2387 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2388 }else if( strcmp(x
,"right")==0 ){
2390 psp
->declassoc
= RIGHT
;
2391 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2392 }else if( strcmp(x
,"nonassoc")==0 ){
2394 psp
->declassoc
= NONE
;
2395 psp
->state
= WAITING_FOR_PRECEDENCE_SYMBOL
;
2396 }else if( strcmp(x
,"destructor")==0 ){
2397 psp
->state
= WAITING_FOR_DESTRUCTOR_SYMBOL
;
2398 }else if( strcmp(x
,"type")==0 ){
2399 psp
->state
= WAITING_FOR_DATATYPE_SYMBOL
;
2400 }else if( strcmp(x
,"fallback")==0 ){
2402 psp
->state
= WAITING_FOR_FALLBACK_ID
;
2403 }else if( strcmp(x
,"wildcard")==0 ){
2404 psp
->state
= WAITING_FOR_WILDCARD_ID
;
2405 }else if( strcmp(x
,"token_class")==0 ){
2406 psp
->state
= WAITING_FOR_CLASS_ID
;
2408 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2409 "Unknown declaration keyword: \"%%%s\".",x
);
2411 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2414 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2415 "Illegal declaration keyword: \"%s\".",x
);
2417 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2420 case WAITING_FOR_DESTRUCTOR_SYMBOL
:
2421 if( !isalpha(x
[0]) ){
2422 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2423 "Symbol name missing after %%destructor keyword");
2425 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2427 struct symbol
*sp
= Symbol_new(x
);
2428 psp
->declargslot
= &sp
->destructor
;
2429 psp
->decllinenoslot
= &sp
->destLineno
;
2430 psp
->insertLineMacro
= 1;
2431 psp
->state
= WAITING_FOR_DECL_ARG
;
2434 case WAITING_FOR_DATATYPE_SYMBOL
:
2435 if( !isalpha(x
[0]) ){
2436 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2437 "Symbol name missing after %%type keyword");
2439 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2441 struct symbol
*sp
= Symbol_find(x
);
2442 if((sp
) && (sp
->datatype
)){
2443 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2444 "Symbol %%type \"%s\" already defined", x
);
2446 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2451 psp
->declargslot
= &sp
->datatype
;
2452 psp
->insertLineMacro
= 0;
2453 psp
->state
= WAITING_FOR_DECL_ARG
;
2457 case WAITING_FOR_PRECEDENCE_SYMBOL
:
2459 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2460 }else if( isupper(x
[0]) ){
2464 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2465 "Symbol \"%s\" has already be given a precedence.",x
);
2468 sp
->prec
= psp
->preccounter
;
2469 sp
->assoc
= psp
->declassoc
;
2472 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2473 "Can't assign a precedence to \"%s\".",x
);
2477 case WAITING_FOR_DECL_ARG
:
2478 if( x
[0]=='{' || x
[0]=='\"' || isalnum(x
[0]) ){
2479 const char *zOld
, *zNew
;
2481 int nOld
, n
, nLine
, nNew
, nBack
;
2485 if( zNew
[0]=='"' || zNew
[0]=='{' ) zNew
++;
2486 nNew
= lemonStrlen(zNew
);
2487 if( *psp
->declargslot
){
2488 zOld
= *psp
->declargslot
;
2492 nOld
= lemonStrlen(zOld
);
2493 n
= nOld
+ nNew
+ 20;
2494 addLineMacro
= !psp
->gp
->nolinenosflag
&& psp
->insertLineMacro
&&
2495 (psp
->decllinenoslot
==0 || psp
->decllinenoslot
[0]!=0);
2497 for(z
=psp
->filename
, nBack
=0; *z
; z
++){
2498 if( *z
=='\\' ) nBack
++;
2500 lemon_sprintf(zLine
, "#line %d ", psp
->tokenlineno
);
2501 nLine
= lemonStrlen(zLine
);
2502 n
+= nLine
+ lemonStrlen(psp
->filename
) + nBack
;
2504 *psp
->declargslot
= (char *) realloc(*psp
->declargslot
, n
);
2505 MemoryCheck(*psp
->declargslot
);
2506 zBuf
= *psp
->declargslot
+ nOld
;
2508 if( nOld
&& zBuf
[-1]!='\n' ){
2511 memcpy(zBuf
, zLine
, nLine
);
2514 for(z
=psp
->filename
; *z
; z
++){
2523 if( psp
->decllinenoslot
&& psp
->decllinenoslot
[0]==0 ){
2524 psp
->decllinenoslot
[0] = psp
->tokenlineno
;
2526 memcpy(zBuf
, zNew
, nNew
);
2529 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2531 ErrorMsg(psp
->filename
,psp
->tokenlineno
,
2532 "Illegal argument to %%%s: %s",psp
->declkeyword
,x
);
2534 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2537 case WAITING_FOR_FALLBACK_ID
:
2539 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2540 }else if( !isupper(x
[0]) ){
2541 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2542 "%%fallback argument \"%s\" should be a token", x
);
2545 struct symbol
*sp
= Symbol_new(x
);
2546 if( psp
->fallback
==0 ){
2548 }else if( sp
->fallback
){
2549 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2550 "More than one fallback assigned to token %s", x
);
2553 sp
->fallback
= psp
->fallback
;
2554 psp
->gp
->has_fallback
= 1;
2558 case WAITING_FOR_WILDCARD_ID
:
2560 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2561 }else if( !isupper(x
[0]) ){
2562 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2563 "%%wildcard argument \"%s\" should be a token", x
);
2566 struct symbol
*sp
= Symbol_new(x
);
2567 if( psp
->gp
->wildcard
==0 ){
2568 psp
->gp
->wildcard
= sp
;
2570 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2571 "Extra wildcard to token: %s", x
);
2576 case WAITING_FOR_CLASS_ID
:
2577 if( !islower(x
[0]) ){
2578 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2579 "%%token_class must be followed by an identifier: ", x
);
2581 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2582 }else if( Symbol_find(x
) ){
2583 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2584 "Symbol \"%s\" already used", x
);
2586 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2588 psp
->tkclass
= Symbol_new(x
);
2589 psp
->tkclass
->type
= MULTITERMINAL
;
2590 psp
->state
= WAITING_FOR_CLASS_TOKEN
;
2593 case WAITING_FOR_CLASS_TOKEN
:
2595 psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2596 }else if( isupper(x
[0]) || ((x
[0]=='|' || x
[0]=='/') && isupper(x
[1])) ){
2597 struct symbol
*msp
= psp
->tkclass
;
2599 msp
->subsym
= (struct symbol
**) realloc(msp
->subsym
,
2600 sizeof(struct symbol
*)*msp
->nsubsym
);
2601 MemoryCheck(msp
->subsym
);
2602 if( !isupper(x
[0]) ) x
++;
2603 msp
->subsym
[msp
->nsubsym
-1] = Symbol_new(x
);
2605 ErrorMsg(psp
->filename
, psp
->tokenlineno
,
2606 "%%token_class argument \"%s\" should be a token", x
);
2608 psp
->state
= RESYNC_AFTER_DECL_ERROR
;
2611 case RESYNC_AFTER_RULE_ERROR
:
2612 /* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2614 case RESYNC_AFTER_DECL_ERROR
:
2615 if( x
[0]=='.' ) psp
->state
= WAITING_FOR_DECL_OR_RULE
;
2616 if( x
[0]=='%' ) psp
->state
= WAITING_FOR_DECL_KEYWORD
;
2621 /* Run the preprocessor over the input file text. The global variables
2622 ** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2623 ** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2624 ** comments them out. Text in between is also commented out as appropriate.
2626 static void preprocess_input(char *z
){
2631 int start_lineno
= 1;
2632 for(i
=0; z
[i
]; i
++){
2633 if( z
[i
]=='\n' ) lineno
++;
2634 if( z
[i
]!='%' || (i
>0 && z
[i
-1]!='\n') ) continue;
2635 if( strncmp(&z
[i
],"%endif",6)==0 && isspace(z
[i
+6]) ){
2639 for(j
=start
; j
<i
; j
++) if( z
[j
]!='\n' ) z
[j
] = ' ';
2642 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2643 }else if( (strncmp(&z
[i
],"%ifdef",6)==0 && isspace(z
[i
+6]))
2644 || (strncmp(&z
[i
],"%ifndef",7)==0 && isspace(z
[i
+7])) ){
2648 for(j
=i
+7; isspace(z
[j
]); j
++){}
2649 for(n
=0; z
[j
+n
] && !isspace(z
[j
+n
]); n
++){}
2651 for(k
=0; k
<nDefine
; k
++){
2652 if( strncmp(azDefine
[k
],&z
[j
],n
)==0 && lemonStrlen(azDefine
[k
])==n
){
2657 if( z
[i
+3]=='n' ) exclude
= !exclude
;
2660 start_lineno
= lineno
;
2663 for(j
=i
; z
[j
] && z
[j
]!='\n'; j
++) z
[j
] = ' ';
2667 fprintf(stderr
,"unterminated %%ifdef starting on line %d\n", start_lineno
);
2672 /* In spite of its name, this function is really a scanner. It read
2673 ** in the entire input file (all at once) then tokenizes it. Each
2674 ** token is passed to the function "parseonetoken" which builds all
2675 ** the appropriate data structures in the global state vector "gp".
2677 void Parse(struct lemon
*gp
)
2688 memset(&ps
, '\0', sizeof(ps
));
2690 ps
.filename
= gp
->filename
;
2692 ps
.state
= INITIALIZE
;
2694 /* Begin by reading the input file */
2695 fp
= fopen(ps
.filename
,"rb");
2697 ErrorMsg(ps
.filename
,0,"Can't open this file for reading.");
2702 filesize
= ftell(fp
);
2704 filebuf
= (char *)malloc( filesize
+1 );
2705 if( filesize
>100000000 || filebuf
==0 ){
2706 ErrorMsg(ps
.filename
,0,"Input file too large.");
2711 if( fread(filebuf
,1,filesize
,fp
)!=filesize
){
2712 ErrorMsg(ps
.filename
,0,"Can't read in all %d bytes of this file.",
2720 filebuf
[filesize
] = 0;
2722 /* Make an initial pass through the file to handle %ifdef and %ifndef */
2723 preprocess_input(filebuf
);
2725 /* Now scan the text of the input file */
2727 for(cp
=filebuf
; (c
= *cp
)!=0; ){
2728 if( c
=='\n' ) lineno
++; /* Keep track of the line number */
2729 if( isspace(c
) ){ cp
++; continue; } /* Skip all white space */
2730 if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments */
2732 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2735 if( c
=='/' && cp
[1]=='*' ){ /* Skip C style comments */
2737 while( (c
= *cp
)!=0 && (c
!='/' || cp
[-1]!='*') ){
2738 if( c
=='\n' ) lineno
++;
2744 ps
.tokenstart
= cp
; /* Mark the beginning of the token */
2745 ps
.tokenlineno
= lineno
; /* Linenumber on which token begins */
2746 if( c
=='\"' ){ /* String literals */
2748 while( (c
= *cp
)!=0 && c
!='\"' ){
2749 if( c
=='\n' ) lineno
++;
2753 ErrorMsg(ps
.filename
,startline
,
2754 "String starting on this line is not terminated before the end of the file.");
2760 }else if( c
=='{' ){ /* A block of C code */
2763 for(level
=1; (c
= *cp
)!=0 && (level
>1 || c
!='}'); cp
++){
2764 if( c
=='\n' ) lineno
++;
2765 else if( c
=='{' ) level
++;
2766 else if( c
=='}' ) level
--;
2767 else if( c
=='/' && cp
[1]=='*' ){ /* Skip comments */
2771 while( (c
= *cp
)!=0 && (c
!='/' || prevc
!='*') ){
2772 if( c
=='\n' ) lineno
++;
2776 }else if( c
=='/' && cp
[1]=='/' ){ /* Skip C++ style comments too */
2778 while( (c
= *cp
)!=0 && c
!='\n' ) cp
++;
2780 }else if( c
=='\'' || c
=='\"' ){ /* String a character literals */
2781 int startchar
, prevc
;
2784 for(cp
++; (c
= *cp
)!=0 && (c
!=startchar
|| prevc
=='\\'); cp
++){
2785 if( c
=='\n' ) lineno
++;
2786 if( prevc
=='\\' ) prevc
= 0;
2792 ErrorMsg(ps
.filename
,ps
.tokenlineno
,
2793 "C code starting on this line is not terminated before the end of the file.");
2799 }else if( isalnum(c
) ){ /* Identifiers */
2800 while( (c
= *cp
)!=0 && (isalnum(c
) || c
=='_') ) cp
++;
2802 }else if( c
==':' && cp
[1]==':' && cp
[2]=='=' ){ /* The operator "::=" */
2805 }else if( (c
=='/' || c
=='|') && isalpha(cp
[1]) ){
2807 while( (c
= *cp
)!=0 && (isalnum(c
) || c
=='_') ) cp
++;
2809 }else{ /* All other (one character) operators */
2814 *cp
= 0; /* Null terminate the token */
2815 parseonetoken(&ps
); /* Parse the token */
2816 *cp
= c
; /* Restore the buffer */
2819 free(filebuf
); /* Release the buffer after parsing */
2820 gp
->rule
= ps
.firstrule
;
2821 gp
->errorcnt
= ps
.errorcnt
;
2823 /*************************** From the file "plink.c" *********************/
2825 ** Routines processing configuration follow-set propagation links
2826 ** in the LEMON parser generator.
2828 static struct plink
*plink_freelist
= 0;
2830 /* Allocate a new plink */
2831 struct plink
*Plink_new(){
2832 struct plink
*newlink
;
2834 if( plink_freelist
==0 ){
2837 plink_freelist
= (struct plink
*)calloc( amt
, sizeof(struct plink
) );
2838 if( plink_freelist
==0 ){
2840 "Unable to allocate memory for a new follow-set propagation link.\n");
2843 for(i
=0; i
<amt
-1; i
++) plink_freelist
[i
].next
= &plink_freelist
[i
+1];
2844 plink_freelist
[amt
-1].next
= 0;
2846 newlink
= plink_freelist
;
2847 plink_freelist
= plink_freelist
->next
;
2851 /* Add a plink to a plink list */
2852 void Plink_add(struct plink
**plpp
, struct config
*cfp
)
2854 struct plink
*newlink
;
2855 newlink
= Plink_new();
2856 newlink
->next
= *plpp
;
2861 /* Transfer every plink on the list "from" to the list "to" */
2862 void Plink_copy(struct plink
**to
, struct plink
*from
)
2864 struct plink
*nextpl
;
2866 nextpl
= from
->next
;
2873 /* Delete every plink on the list */
2874 void Plink_delete(struct plink
*plp
)
2876 struct plink
*nextpl
;
2880 plp
->next
= plink_freelist
;
2881 plink_freelist
= plp
;
2885 /*********************** From the file "report.c" **************************/
2887 ** Procedures for generating reports and tables in the LEMON parser generator.
2890 /* Generate a filename with the given suffix. Space to hold the
2891 ** name comes from malloc() and must be freed by the calling
2894 PRIVATE
char *file_makename(struct lemon
*lemp
, const char *suffix
)
2899 name
= (char*)malloc( lemonStrlen(lemp
->filename
) + lemonStrlen(suffix
) + 5 );
2901 fprintf(stderr
,"Can't allocate space for a filename.\n");
2904 lemon_strcpy(name
,lemp
->filename
);
2905 cp
= strrchr(name
,'.');
2907 lemon_strcat(name
,suffix
);
2911 /* Open a file with a name based on the name of the input file,
2912 ** but with a different (specified) suffix, and return a pointer
2914 PRIVATE
FILE *file_open(
2921 if( lemp
->outname
) free(lemp
->outname
);
2922 lemp
->outname
= file_makename(lemp
, suffix
);
2923 fp
= fopen(lemp
->outname
,mode
);
2924 if( fp
==0 && *mode
=='w' ){
2925 fprintf(stderr
,"Can't open file \"%s\".\n",lemp
->outname
);
2932 /* Duplicate the input file without comments and without actions
2934 void Reprint(struct lemon
*lemp
)
2938 int i
, j
, maxlen
, len
, ncolumns
, skip
;
2939 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp
->filename
);
2941 for(i
=0; i
<lemp
->nsymbol
; i
++){
2942 sp
= lemp
->symbols
[i
];
2943 len
= lemonStrlen(sp
->name
);
2944 if( len
>maxlen
) maxlen
= len
;
2946 ncolumns
= 76/(maxlen
+5);
2947 if( ncolumns
<1 ) ncolumns
= 1;
2948 skip
= (lemp
->nsymbol
+ ncolumns
- 1)/ncolumns
;
2949 for(i
=0; i
<skip
; i
++){
2951 for(j
=i
; j
<lemp
->nsymbol
; j
+=skip
){
2952 sp
= lemp
->symbols
[j
];
2953 assert( sp
->index
==j
);
2954 printf(" %3d %-*.*s",j
,maxlen
,maxlen
,sp
->name
);
2958 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
2959 printf("%s",rp
->lhs
->name
);
2960 /* if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
2962 for(i
=0; i
<rp
->nrhs
; i
++){
2964 if( sp
->type
==MULTITERMINAL
){
2965 printf(" %s", sp
->subsym
[0]->name
);
2966 for(j
=1; j
<sp
->nsubsym
; j
++){
2967 printf("|%s", sp
->subsym
[j
]->name
);
2970 printf(" %s", sp
->name
);
2972 /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
2975 if( rp
->precsym
) printf(" [%s]",rp
->precsym
->name
);
2976 /* if( rp->code ) printf("\n %s",rp->code); */
2981 void ConfigPrint(FILE *fp
, struct config
*cfp
)
2987 fprintf(fp
,"%s ::=",rp
->lhs
->name
);
2988 for(i
=0; i
<=rp
->nrhs
; i
++){
2989 if( i
==cfp
->dot
) fprintf(fp
," *");
2990 if( i
==rp
->nrhs
) break;
2992 if( sp
->type
==MULTITERMINAL
){
2993 fprintf(fp
," %s", sp
->subsym
[0]->name
);
2994 for(j
=1; j
<sp
->nsubsym
; j
++){
2995 fprintf(fp
,"|%s",sp
->subsym
[j
]->name
);
2998 fprintf(fp
," %s", sp
->name
);
3006 PRIVATE
void SetPrint(out
,set
,lemp
)
3014 fprintf(out
,"%12s[","");
3015 for(i
=0; i
<lemp
->nterminal
; i
++){
3016 if( SetFind(set
,i
) ){
3017 fprintf(out
,"%s%s",spacer
,lemp
->symbols
[i
]->name
);
3024 /* Print a plink chain */
3025 PRIVATE
void PlinkPrint(out
,plp
,tag
)
3031 fprintf(out
,"%12s%s (state %2d) ","",tag
,plp
->cfp
->stp
->statenum
);
3032 ConfigPrint(out
,plp
->cfp
);
3039 /* Print an action to the given file descriptor. Return FALSE if
3040 ** nothing was actually printed.
3042 int PrintAction(struct action
*ap
, FILE *fp
, int indent
){
3046 fprintf(fp
,"%*s shift %d",indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3049 fprintf(fp
,"%*s reduce %d",indent
,ap
->sp
->name
,ap
->x
.rp
->index
);
3052 fprintf(fp
,"%*s accept",indent
,ap
->sp
->name
);
3055 fprintf(fp
,"%*s error",indent
,ap
->sp
->name
);
3059 fprintf(fp
,"%*s reduce %-3d ** Parsing conflict **",
3060 indent
,ap
->sp
->name
,ap
->x
.rp
->index
);
3063 fprintf(fp
,"%*s shift %-3d ** Parsing conflict **",
3064 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3067 if( showPrecedenceConflict
){
3068 fprintf(fp
,"%*s shift %-3d -- dropped by precedence",
3069 indent
,ap
->sp
->name
,ap
->x
.stp
->statenum
);
3075 if( showPrecedenceConflict
){
3076 fprintf(fp
,"%*s reduce %-3d -- dropped by precedence",
3077 indent
,ap
->sp
->name
,ap
->x
.rp
->index
);
3089 /* Generate the "y.output" log file */
3090 void ReportOutput(struct lemon
*lemp
)
3098 fp
= file_open(lemp
,".out","wb");
3100 for(i
=0; i
<lemp
->nstate
; i
++){
3101 stp
= lemp
->sorted
[i
];
3102 fprintf(fp
,"State %d:\n",stp
->statenum
);
3103 if( lemp
->basisflag
) cfp
=stp
->bp
;
3107 if( cfp
->dot
==cfp
->rp
->nrhs
){
3108 lemon_sprintf(buf
,"(%d)",cfp
->rp
->index
);
3109 fprintf(fp
," %5s ",buf
);
3113 ConfigPrint(fp
,cfp
);
3116 SetPrint(fp
,cfp
->fws
,lemp
);
3117 PlinkPrint(fp
,cfp
->fplp
,"To ");
3118 PlinkPrint(fp
,cfp
->bplp
,"From");
3120 if( lemp
->basisflag
) cfp
=cfp
->bp
;
3124 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3125 if( PrintAction(ap
,fp
,30) ) fprintf(fp
,"\n");
3129 fprintf(fp
, "----------------------------------------------------\n");
3130 fprintf(fp
, "Symbols:\n");
3131 for(i
=0; i
<lemp
->nsymbol
; i
++){
3135 sp
= lemp
->symbols
[i
];
3136 fprintf(fp
, " %3d: %s", i
, sp
->name
);
3137 if( sp
->type
==NONTERMINAL
){
3140 fprintf(fp
, " <lambda>");
3142 for(j
=0; j
<lemp
->nterminal
; j
++){
3143 if( sp
->firstset
&& SetFind(sp
->firstset
, j
) ){
3144 fprintf(fp
, " %s", lemp
->symbols
[j
]->name
);
3154 /* Search for the file "name" which is in the same directory as
3155 ** the executable */
3156 PRIVATE
char *pathsearch(char *argv0
, char *name
, int modemask
)
3158 const char *pathlist
;
3165 cp
= strrchr(argv0
,'\\');
3167 cp
= strrchr(argv0
,'/');
3172 path
= (char *)malloc( lemonStrlen(argv0
) + lemonStrlen(name
) + 2 );
3173 if( path
) lemon_sprintf(path
,"%s/%s",argv0
,name
);
3176 pathlist
= getenv("PATH");
3177 if( pathlist
==0 ) pathlist
= ".:/bin:/usr/bin";
3178 pathbuf
= (char *) malloc( lemonStrlen(pathlist
) + 1 );
3179 path
= (char *)malloc( lemonStrlen(pathlist
)+lemonStrlen(name
)+2 );
3180 if( (pathbuf
!= 0) && (path
!=0) ){
3181 pathbufptr
= pathbuf
;
3182 lemon_strcpy(pathbuf
, pathlist
);
3184 cp
= strchr(pathbuf
,':');
3185 if( cp
==0 ) cp
= &pathbuf
[lemonStrlen(pathbuf
)];
3188 lemon_sprintf(path
,"%s/%s",pathbuf
,name
);
3190 if( c
==0 ) pathbuf
[0] = 0;
3191 else pathbuf
= &cp
[1];
3192 if( access(path
,modemask
)==0 ) break;
3200 /* Given an action, compute the integer value for that action
3201 ** which is to be put in the action table of the generated machine.
3202 ** Return negative if no action should be generated.
3204 PRIVATE
int compute_action(struct lemon
*lemp
, struct action
*ap
)
3208 case SHIFT
: act
= ap
->x
.stp
->statenum
; break;
3209 case REDUCE
: act
= ap
->x
.rp
->index
+ lemp
->nstate
; break;
3210 case ERROR
: act
= lemp
->nstate
+ lemp
->nrule
; break;
3211 case ACCEPT
: act
= lemp
->nstate
+ lemp
->nrule
+ 1; break;
3212 default: act
= -1; break;
3217 #define LINESIZE 1000
3218 /* The next cluster of routines are for reading the template file
3219 ** and writing the results to the generated parser */
3220 /* The first function transfers data from "in" to "out" until
3221 ** a line is seen which begins with "%%". The line number is
3224 ** if name!=0, then any word that begin with "Parse" is changed to
3225 ** begin with *name instead.
3227 PRIVATE
void tplt_xfer(char *name
, FILE *in
, FILE *out
, int *lineno
)
3230 char line
[LINESIZE
];
3231 while( fgets(line
,LINESIZE
,in
) && (line
[0]!='%' || line
[1]!='%') ){
3235 for(i
=0; line
[i
]; i
++){
3236 if( line
[i
]=='P' && strncmp(&line
[i
],"Parse",5)==0
3237 && (i
==0 || !isalpha(line
[i
-1]))
3239 if( i
>iStart
) fprintf(out
,"%.*s",i
-iStart
,&line
[iStart
]);
3240 fprintf(out
,"%s",name
);
3246 fprintf(out
,"%s",&line
[iStart
]);
3250 /* The next function finds the template file and opens it, returning
3251 ** a pointer to the opened file. */
3252 PRIVATE
FILE *tplt_open(struct lemon
*lemp
)
3254 static char templatename
[] = "lempar.c";
3259 char *to_free
= NULL
;
3261 /* first, see if user specified a template filename on the command line. */
3262 if (user_templatename
!= 0) {
3263 if( access(user_templatename
,004)==-1 ){
3264 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3269 in
= fopen(user_templatename
,"rb");
3271 fprintf(stderr
,"Can't open the template file \"%s\".\n",user_templatename
);
3278 cp
= strrchr(lemp
->filename
,'.');
3280 lemon_sprintf(buf
,"%.*s.lt",(int)(cp
-lemp
->filename
),lemp
->filename
);
3282 lemon_sprintf(buf
,"%s.lt",lemp
->filename
);
3284 if( access(buf
,004)==0 ){
3286 }else if( access(templatename
,004)==0 ){
3287 tpltname
= templatename
;
3289 tpltname
= pathsearch(lemp
->argv0
,templatename
,0);
3293 fprintf(stderr
,"Can't find the parser driver template file \"%s\".\n",
3298 in
= fopen(tpltname
,"rb");
3299 if (to_free
) free(to_free
);
3301 fprintf(stderr
,"Can't open the template file \"%s\".\n",templatename
);
3308 /* Print a #line directive line to the output file. */
3309 PRIVATE
void tplt_linedir(FILE *out
, int lineno
, char *filename
)
3311 fprintf(out
,"#line %d \"",lineno
);
3313 if( *filename
== '\\' ) putc('\\',out
);
3314 putc(*filename
,out
);
3317 fprintf(out
,"\"\n");
3320 /* Print a string to the file and keep the linenumber up to date */
3321 PRIVATE
void tplt_print(FILE *out
, struct lemon
*lemp
, char *str
, int *lineno
)
3323 if( str
==0 ) return;
3326 if( *str
=='\n' ) (*lineno
)++;
3329 if( str
[-1]!='\n' ){
3333 if (!lemp
->nolinenosflag
) {
3334 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3340 ** The following routine emits code for the destructor for the
3343 void emit_destructor_code(
3351 if( sp
->type
==TERMINAL
){
3352 cp
= lemp
->tokendest
;
3354 fprintf(out
,"{\n"); (*lineno
)++;
3355 }else if( sp
->destructor
){
3356 cp
= sp
->destructor
;
3357 fprintf(out
,"{\n"); (*lineno
)++;
3358 if (!lemp
->nolinenosflag
) { (*lineno
)++; tplt_linedir(out
,sp
->destLineno
,lemp
->filename
); }
3359 }else if( lemp
->vardest
){
3362 fprintf(out
,"{\n"); (*lineno
)++;
3364 assert( 0 ); /* Cannot happen */
3367 if( *cp
=='$' && cp
[1]=='$' ){
3368 fprintf(out
,"(yypminor->yy%d)",sp
->dtnum
);
3372 if( *cp
=='\n' ) (*lineno
)++;
3375 fprintf(out
,"\n"); (*lineno
)++;
3376 if (!lemp
->nolinenosflag
) {
3377 (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
);
3379 fprintf(out
,"}\n"); (*lineno
)++;
3384 ** Return TRUE (non-zero) if the given symbol has a destructor.
3386 int has_destructor(struct symbol
*sp
, struct lemon
*lemp
)
3389 if( sp
->type
==TERMINAL
){
3390 ret
= lemp
->tokendest
!=0;
3392 ret
= lemp
->vardest
!=0 || sp
->destructor
!=0;
3398 ** Append text to a dynamically allocated string. If zText is 0 then
3399 ** reset the string to be empty again. Always return the complete text
3400 ** of the string (which is overwritten with each call).
3402 ** n bytes of zText are stored. If n==0 then all of zText up to the first
3403 ** \000 terminator is stored. zText can contain up to two instances of
3404 ** %d. The values of p1 and p2 are written into the first and second
3407 ** If n==-1, then the previous character is overwritten.
3409 PRIVATE
char *append_str(const char *zText
, int n
, int p1
, int p2
){
3411 static int alloced
= 0;
3412 static int used
= 0;
3424 n
= lemonStrlen(zText
);
3426 if( (int) (n
+sizeof(zInt
)*2+used
) >= alloced
){
3427 alloced
= n
+ sizeof(zInt
)*2 + used
+ 200;
3428 z
= (char *) realloc(z
, alloced
);
3431 fprintf(stderr
,"Out of memory.\n");
3436 if( c
=='%' && n
>0 && zText
[0]=='d' ){
3437 lemon_sprintf(zInt
, "%d", p1
);
3439 lemon_strcpy(&z
[used
], zInt
);
3440 used
+= lemonStrlen(&z
[used
]);
3452 ** zCode is a string that is the action associated with a rule. Expand
3453 ** the symbols in this string so that the refer to elements of the parser
3456 PRIVATE
void translate_code(struct lemon
*lemp
, struct rule
*rp
){
3459 char lhsused
= 0; /* True if the LHS element has been used */
3460 char used
[MAXRHS
]; /* True for each RHS element which is used */
3462 for(i
=0; i
<rp
->nrhs
; i
++) used
[i
] = 0;
3467 rp
->line
= rp
->ruleline
;
3470 append_str(0,0,0,0);
3472 /* This const cast is wrong but harmless, if we're careful. */
3473 for(cp
=(char *)rp
->code
; *cp
; cp
++){
3474 if( isalpha(*cp
) && (cp
==rp
->code
|| (!isalnum(cp
[-1]) && cp
[-1]!='_')) ){
3476 for(xp
= &cp
[1]; isalnum(*xp
) || *xp
=='_'; xp
++);
3479 if( rp
->lhsalias
&& strcmp(cp
,rp
->lhsalias
)==0 ){
3480 append_str("yygotominor.yy%d",0,rp
->lhs
->dtnum
,0);
3484 for(i
=0; i
<rp
->nrhs
; i
++){
3485 if( rp
->rhsalias
[i
] && strcmp(cp
,rp
->rhsalias
[i
])==0 ){
3486 if( cp
!=rp
->code
&& cp
[-1]=='@' ){
3487 /* If the argument is of the form @X then substituted
3488 ** the token number of X, not the value of X */
3489 append_str("yymsp[%d].major",-1,i
-rp
->nrhs
+1,0);
3491 struct symbol
*sp
= rp
->rhs
[i
];
3493 if( sp
->type
==MULTITERMINAL
){
3494 dtnum
= sp
->subsym
[0]->dtnum
;
3498 append_str("yymsp[%d].minor.yy%d",0,i
-rp
->nrhs
+1, dtnum
);
3508 append_str(cp
, 1, 0, 0);
3511 /* Check to make sure the LHS has been used */
3512 if( rp
->lhsalias
&& !lhsused
){
3513 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3514 "Label \"%s\" for \"%s(%s)\" is never used.",
3515 rp
->lhsalias
,rp
->lhs
->name
,rp
->lhsalias
);
3519 /* Generate destructor code for RHS symbols which are not used in the
3521 for(i
=0; i
<rp
->nrhs
; i
++){
3522 if( rp
->rhsalias
[i
] && !used
[i
] ){
3523 ErrorMsg(lemp
->filename
,rp
->ruleline
,
3524 "Label %s for \"%s(%s)\" is never used.",
3525 rp
->rhsalias
[i
],rp
->rhs
[i
]->name
,rp
->rhsalias
[i
]);
3527 }else if( rp
->rhsalias
[i
]==0 ){
3528 if( has_destructor(rp
->rhs
[i
],lemp
) ){
3529 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3530 rp
->rhs
[i
]->index
,i
-rp
->nrhs
+1);
3532 /* No destructor defined for this term */
3537 cp
= append_str(0,0,0,0);
3538 rp
->code
= Strsafe(cp
?cp
:"");
3543 ** Generate code which executes when the rule "rp" is reduced. Write
3544 ** the code to "out". Make sure lineno stays up-to-date.
3546 PRIVATE
void emit_code(
3554 /* Generate code to do the reduce action */
3556 if (!lemp
->nolinenosflag
) { (*lineno
)++; tplt_linedir(out
,rp
->line
,lemp
->filename
); }
3557 fprintf(out
,"{%s",rp
->code
);
3558 for(cp
=rp
->code
; *cp
; cp
++){
3559 if( *cp
=='\n' ) (*lineno
)++;
3561 fprintf(out
,"}\n"); (*lineno
)++;
3562 if (!lemp
->nolinenosflag
) { (*lineno
)++; tplt_linedir(out
,*lineno
,lemp
->outname
); }
3563 } /* End if( rp->code ) */
3569 ** Print the definition of the union used for the parser's data stack.
3570 ** This union contains fields for every possible data type for tokens
3571 ** and nonterminals. In the process of computing and printing this
3572 ** union, also set the ".dtnum" field of every terminal and nonterminal
3575 void print_stack_union(
3576 FILE *out
, /* The output stream */
3577 struct lemon
*lemp
, /* The main info structure for this parser */
3578 int *plineno
, /* Pointer to the line number */
3579 int mhflag
/* True if generating makeheaders output */
3581 int lineno
= *plineno
; /* The line number of the output */
3582 char **types
; /* A hash table of datatypes */
3583 int arraysize
; /* Size of the "types" array */
3584 int maxdtlength
; /* Maximum length of any ".datatype" field. */
3585 char *stddt
; /* Standardized name for a datatype */
3586 int i
,j
; /* Loop counters */
3587 unsigned hash
; /* For hashing the name of a type */
3588 const char *name
; /* Name of the parser */
3590 /* Allocate and initialize types[] and allocate stddt[] */
3591 arraysize
= lemp
->nsymbol
* 2;
3592 types
= (char**)calloc( arraysize
, sizeof(char*) );
3594 fprintf(stderr
,"Out of memory.\n");
3597 for(i
=0; i
<arraysize
; i
++) types
[i
] = 0;
3599 if( lemp
->vartype
){
3600 maxdtlength
= lemonStrlen(lemp
->vartype
);
3602 for(i
=0; i
<lemp
->nsymbol
; i
++){
3604 struct symbol
*sp
= lemp
->symbols
[i
];
3605 if( sp
->datatype
==0 ) continue;
3606 len
= lemonStrlen(sp
->datatype
);
3607 if( len
>maxdtlength
) maxdtlength
= len
;
3609 stddt
= (char*)malloc( maxdtlength
*2 + 1 );
3611 fprintf(stderr
,"Out of memory.\n");
3615 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3616 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
3617 ** used for terminal symbols. If there is no %default_type defined then
3618 ** 0 is also used as the .dtnum value for nonterminals which do not specify
3619 ** a datatype using the %type directive.
3621 for(i
=0; i
<lemp
->nsymbol
; i
++){
3622 struct symbol
*sp
= lemp
->symbols
[i
];
3624 if( sp
==lemp
->errsym
){
3625 sp
->dtnum
= arraysize
+1;
3628 if( sp
->type
!=NONTERMINAL
|| (sp
->datatype
==0 && lemp
->vartype
==0) ){
3633 if( cp
==0 ) cp
= lemp
->vartype
;
3635 while( isspace(*cp
) ) cp
++;
3636 while( *cp
) stddt
[j
++] = *cp
++;
3637 while( j
>0 && isspace(stddt
[j
-1]) ) j
--;
3639 if( lemp
->tokentype
&& strcmp(stddt
, lemp
->tokentype
)==0 ){
3644 for(j
=0; stddt
[j
]; j
++){
3645 hash
= hash
*53 + stddt
[j
];
3647 hash
= (hash
& 0x7fffffff)%arraysize
;
3648 while( types
[hash
] ){
3649 if( strcmp(types
[hash
],stddt
)==0 ){
3650 sp
->dtnum
= hash
+ 1;
3654 if( hash
>=(unsigned)arraysize
) hash
= 0;
3656 if( types
[hash
]==0 ){
3657 sp
->dtnum
= hash
+ 1;
3658 types
[hash
] = (char*)malloc( lemonStrlen(stddt
)+1 );
3659 if( types
[hash
]==0 ){
3660 fprintf(stderr
,"Out of memory.\n");
3663 lemon_strcpy(types
[hash
],stddt
);
3667 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3668 name
= lemp
->name
? lemp
->name
: "Parse";
3670 if( mhflag
){ fprintf(out
,"#if INTERFACE\n"); lineno
++; }
3671 fprintf(out
,"#define %sTOKENTYPE %s\n",name
,
3672 lemp
->tokentype
?lemp
->tokentype
:"void*"); lineno
++;
3673 if( mhflag
){ fprintf(out
,"#endif\n"); lineno
++; }
3674 fprintf(out
,"typedef union {\n"); lineno
++;
3675 fprintf(out
," int yyinit;\n"); lineno
++;
3676 fprintf(out
," %sTOKENTYPE yy0;\n",name
); lineno
++;
3677 for(i
=0; i
<arraysize
; i
++){
3678 if( types
[i
]==0 ) continue;
3679 fprintf(out
," %s yy%d;\n",types
[i
],i
+1); lineno
++;
3682 if( lemp
->errsym
->useCnt
){
3683 fprintf(out
," int yy%d;\n",lemp
->errsym
->dtnum
); lineno
++;
3687 fprintf(out
,"} YYMINORTYPE;\n"); lineno
++;
3692 ** Return the name of a C datatype able to represent values between
3693 ** lwr and upr, inclusive.
3695 static const char *minimum_size_type(int lwr
, int upr
){
3698 return "unsigned char";
3699 }else if( upr
<65535 ){
3700 return "unsigned short int";
3702 return "unsigned int";
3704 }else if( lwr
>=-127 && upr
<=127 ){
3705 return "signed char";
3706 }else if( lwr
>=-32767 && upr
<32767 ){
3714 ** Each state contains a set of token transaction and a set of
3715 ** nonterminal transactions. Each of these sets makes an instance
3716 ** of the following structure. An array of these structures is used
3717 ** to order the creation of entries in the yy_action[] table.
3720 struct state
*stp
; /* A pointer to a state */
3721 int isTkn
; /* True to use tokens. False for non-terminals */
3722 int nAction
; /* Number of actions */
3723 int iOrder
; /* Original order of action sets */
3727 ** Compare to axset structures for sorting purposes
3729 static int axset_compare(const void *a
, const void *b
){
3730 struct axset
*p1
= (struct axset
*)a
;
3731 struct axset
*p2
= (struct axset
*)b
;
3733 c
= p2
->nAction
- p1
->nAction
;
3735 c
= p2
->iOrder
- p1
->iOrder
;
3737 assert( c
!=0 || p1
==p2
);
3742 ** Write text on "out" that describes the rule "rp".
3744 static void writeRuleText(FILE *out
, struct rule
*rp
){
3746 fprintf(out
,"%s ::=", rp
->lhs
->name
);
3747 for(j
=0; j
<rp
->nrhs
; j
++){
3748 struct symbol
*sp
= rp
->rhs
[j
];
3749 if( sp
->type
!=MULTITERMINAL
){
3750 fprintf(out
," %s", sp
->name
);
3753 fprintf(out
," %s", sp
->subsym
[0]->name
);
3754 for(k
=1; k
<sp
->nsubsym
; k
++){
3755 fprintf(out
,"|%s",sp
->subsym
[k
]->name
);
3762 /* Generate C source code for the parser */
3765 int mhflag
/* Output in makeheaders format if true */
3768 char line
[LINESIZE
];
3773 struct acttab
*pActtab
;
3776 int mnTknOfst
, mxTknOfst
;
3777 int mnNtOfst
, mxNtOfst
;
3780 in
= tplt_open(lemp
);
3782 if( output_filename
!=0 ){
3783 char *tmp
= lemp
->filename
;
3784 char *ext
= strrchr(output_filename
, '.');
3785 if( ext
==0 ) ext
= ".c";
3786 lemp
->filename
= output_filename
;
3787 out
= file_open(lemp
,ext
,"wb");
3788 lemp
->filename
= tmp
;
3790 out
= file_open(lemp
,".c","wb");
3797 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3799 /* Generate the include code, if any */
3800 tplt_print(out
,lemp
,lemp
->include
,&lineno
);
3802 char *name
= file_makename(lemp
, ".h");
3803 fprintf(out
,"#include \"%s\"\n", name
); lineno
++;
3806 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3808 /* Generate #defines for all tokens */
3811 fprintf(out
,"#if INTERFACE\n"); lineno
++;
3812 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
3814 for(i
=1; i
<lemp
->nterminal
; i
++){
3815 fprintf(out
,"#define %s%-30s %2d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
3818 fprintf(out
,"#endif\n"); lineno
++;
3820 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3822 /* Generate the defines */
3823 fprintf(out
,"#define YYCODETYPE %s\n",
3824 minimum_size_type(0, lemp
->nsymbol
+1)); lineno
++;
3825 fprintf(out
,"#define YYNOCODE %d\n",lemp
->nsymbol
+1); lineno
++;
3826 fprintf(out
,"#define YYACTIONTYPE %s\n",
3827 minimum_size_type(0, lemp
->nstate
+lemp
->nrule
+5)); lineno
++;
3828 if( lemp
->wildcard
){
3829 fprintf(out
,"#define YYWILDCARD %d\n",
3830 lemp
->wildcard
->index
); lineno
++;
3832 print_stack_union(out
,lemp
,&lineno
,mhflag
);
3833 fprintf(out
, "#ifndef YYSTACKDEPTH\n"); lineno
++;
3834 if( lemp
->stacksize
){
3835 fprintf(out
,"#define YYSTACKDEPTH %s\n",lemp
->stacksize
); lineno
++;
3837 fprintf(out
,"#define YYSTACKDEPTH 100\n"); lineno
++;
3839 fprintf(out
, "#endif\n"); lineno
++;
3841 fprintf(out
,"#if INTERFACE\n"); lineno
++;
3843 name
= lemp
->name
? lemp
->name
: "Parse";
3844 if( lemp
->arg
&& lemp
->arg
[0] ){
3846 i
= lemonStrlen(lemp
->arg
);
3847 while( i
>=1 && isspace(lemp
->arg
[i
-1]) ) i
--;
3848 while( i
>=1 && (isalnum(lemp
->arg
[i
-1]) || lemp
->arg
[i
-1]=='_') ) i
--;
3849 fprintf(out
,"#define %sARG_SDECL %s;\n",name
,lemp
->arg
); lineno
++;
3850 fprintf(out
,"#define %sARG_PDECL ,%s\n",name
,lemp
->arg
); lineno
++;
3851 fprintf(out
,"#define %sARG_FETCH %s = yypParser->%s\n",
3852 name
,lemp
->arg
,&lemp
->arg
[i
]); lineno
++;
3853 fprintf(out
,"#define %sARG_STORE yypParser->%s = %s\n",
3854 name
,&lemp
->arg
[i
],&lemp
->arg
[i
]); lineno
++;
3856 fprintf(out
,"#define %sARG_SDECL\n",name
); lineno
++;
3857 fprintf(out
,"#define %sARG_PDECL\n",name
); lineno
++;
3858 fprintf(out
,"#define %sARG_FETCH\n",name
); lineno
++;
3859 fprintf(out
,"#define %sARG_STORE\n",name
); lineno
++;
3862 fprintf(out
,"#endif\n"); lineno
++;
3864 fprintf(out
,"#define YYNSTATE %d\n",lemp
->nstate
); lineno
++;
3865 fprintf(out
,"#define YYNRULE %d\n",lemp
->nrule
); lineno
++;
3866 if( lemp
->errsym
->useCnt
){
3867 fprintf(out
,"#define YYERRORSYMBOL %d\n",lemp
->errsym
->index
); lineno
++;
3868 fprintf(out
,"#define YYERRSYMDT yy%d\n",lemp
->errsym
->dtnum
); lineno
++;
3870 if( lemp
->has_fallback
){
3871 fprintf(out
,"#define YYFALLBACK 1\n"); lineno
++;
3873 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
3875 /* Generate the action table and its associates:
3877 ** yy_action[] A single table containing all actions.
3878 ** yy_lookahead[] A table containing the lookahead for each entry in
3879 ** yy_action. Used to detect hash collisions.
3880 ** yy_shift_ofst[] For each state, the offset into yy_action for
3881 ** shifting terminals.
3882 ** yy_reduce_ofst[] For each state, the offset into yy_action for
3883 ** shifting non-terminals after a reduce.
3884 ** yy_default[] Default action for each state.
3887 /* Compute the actions on all states and count them up */
3888 ax
= (struct axset
*) calloc(lemp
->nstate
*2, sizeof(ax
[0]));
3890 fprintf(stderr
,"malloc failed\n");
3893 for(i
=0; i
<lemp
->nstate
; i
++){
3894 stp
= lemp
->sorted
[i
];
3897 ax
[i
*2].nAction
= stp
->nTknAct
;
3898 ax
[i
*2+1].stp
= stp
;
3899 ax
[i
*2+1].isTkn
= 0;
3900 ax
[i
*2+1].nAction
= stp
->nNtAct
;
3902 mxTknOfst
= mnTknOfst
= 0;
3903 mxNtOfst
= mnNtOfst
= 0;
3905 /* Compute the action table. In order to try to keep the size of the
3906 ** action table to a minimum, the heuristic of placing the largest action
3907 ** sets first is used.
3909 for(i
=0; i
<lemp
->nstate
*2; i
++) ax
[i
].iOrder
= i
;
3910 qsort(ax
, lemp
->nstate
*2, sizeof(ax
[0]), axset_compare
);
3911 pActtab
= acttab_alloc();
3912 for(i
=0; i
<lemp
->nstate
*2 && ax
[i
].nAction
>0; i
++){
3915 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3917 if( ap
->sp
->index
>=lemp
->nterminal
) continue;
3918 action
= compute_action(lemp
, ap
);
3919 if( action
<0 ) continue;
3920 acttab_action(pActtab
, ap
->sp
->index
, action
);
3922 stp
->iTknOfst
= acttab_insert(pActtab
);
3923 if( stp
->iTknOfst
<mnTknOfst
) mnTknOfst
= stp
->iTknOfst
;
3924 if( stp
->iTknOfst
>mxTknOfst
) mxTknOfst
= stp
->iTknOfst
;
3926 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
3928 if( ap
->sp
->index
<lemp
->nterminal
) continue;
3929 if( ap
->sp
->index
==lemp
->nsymbol
) continue;
3930 action
= compute_action(lemp
, ap
);
3931 if( action
<0 ) continue;
3932 acttab_action(pActtab
, ap
->sp
->index
, action
);
3934 stp
->iNtOfst
= acttab_insert(pActtab
);
3935 if( stp
->iNtOfst
<mnNtOfst
) mnNtOfst
= stp
->iNtOfst
;
3936 if( stp
->iNtOfst
>mxNtOfst
) mxNtOfst
= stp
->iNtOfst
;
3941 /* Output the yy_action table */
3942 n
= acttab_size(pActtab
);
3943 fprintf(out
,"#define YY_ACTTAB_COUNT (%d)\n", n
); lineno
++;
3944 fprintf(out
,"static const YYACTIONTYPE yy_action[] = {\n"); lineno
++;
3945 for(i
=j
=0; i
<n
; i
++){
3946 int action
= acttab_yyaction(pActtab
, i
);
3947 if( action
<0 ) action
= lemp
->nstate
+ lemp
->nrule
+ 2;
3948 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3949 fprintf(out
, " %4d,", action
);
3950 if( j
==9 || i
==n
-1 ){
3951 fprintf(out
, "\n"); lineno
++;
3957 fprintf(out
, "};\n"); lineno
++;
3959 /* Output the yy_lookahead table */
3960 fprintf(out
,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno
++;
3961 for(i
=j
=0; i
<n
; i
++){
3962 int la
= acttab_yylookahead(pActtab
, i
);
3963 if( la
<0 ) la
= lemp
->nsymbol
;
3964 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3965 fprintf(out
, " %4d,", la
);
3966 if( j
==9 || i
==n
-1 ){
3967 fprintf(out
, "\n"); lineno
++;
3973 fprintf(out
, "};\n"); lineno
++;
3975 /* Output the yy_shift_ofst[] table */
3976 fprintf(out
, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst
-1); lineno
++;
3978 while( n
>0 && lemp
->sorted
[n
-1]->iTknOfst
==NO_OFFSET
) n
--;
3979 fprintf(out
, "#define YY_SHIFT_COUNT (%d)\n", n
-1); lineno
++;
3980 fprintf(out
, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst
); lineno
++;
3981 fprintf(out
, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst
); lineno
++;
3982 fprintf(out
, "static const %s yy_shift_ofst[] = {\n",
3983 minimum_size_type(mnTknOfst
-1, mxTknOfst
)); lineno
++;
3984 for(i
=j
=0; i
<n
; i
++){
3986 stp
= lemp
->sorted
[i
];
3987 ofst
= stp
->iTknOfst
;
3988 if( ofst
==NO_OFFSET
) ofst
= mnTknOfst
- 1;
3989 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
3990 fprintf(out
, " %4d,", ofst
);
3991 if( j
==9 || i
==n
-1 ){
3992 fprintf(out
, "\n"); lineno
++;
3998 fprintf(out
, "};\n"); lineno
++;
4000 /* Output the yy_reduce_ofst[] table */
4001 fprintf(out
, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst
-1); lineno
++;
4003 while( n
>0 && lemp
->sorted
[n
-1]->iNtOfst
==NO_OFFSET
) n
--;
4004 fprintf(out
, "#define YY_REDUCE_COUNT (%d)\n", n
-1); lineno
++;
4005 fprintf(out
, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst
); lineno
++;
4006 fprintf(out
, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst
); lineno
++;
4007 fprintf(out
, "static const %s yy_reduce_ofst[] = {\n",
4008 minimum_size_type(mnNtOfst
-1, mxNtOfst
)); lineno
++;
4009 for(i
=j
=0; i
<n
; i
++){
4011 stp
= lemp
->sorted
[i
];
4012 ofst
= stp
->iNtOfst
;
4013 if( ofst
==NO_OFFSET
) ofst
= mnNtOfst
- 1;
4014 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4015 fprintf(out
, " %4d,", ofst
);
4016 if( j
==9 || i
==n
-1 ){
4017 fprintf(out
, "\n"); lineno
++;
4023 fprintf(out
, "};\n"); lineno
++;
4025 /* Output the default action table */
4026 fprintf(out
, "static const YYACTIONTYPE yy_default[] = {\n"); lineno
++;
4028 for(i
=j
=0; i
<n
; i
++){
4029 stp
= lemp
->sorted
[i
];
4030 if( j
==0 ) fprintf(out
," /* %5d */ ", i
);
4031 fprintf(out
, " %4d,", stp
->iDflt
);
4032 if( j
==9 || i
==n
-1 ){
4033 fprintf(out
, "\n"); lineno
++;
4039 fprintf(out
, "};\n"); lineno
++;
4040 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4042 /* Generate the table of fallback tokens.
4044 if( lemp
->has_fallback
){
4045 int mx
= lemp
->nterminal
- 1;
4046 while( mx
>0 && lemp
->symbols
[mx
]->fallback
==0 ){ mx
--; }
4047 for(i
=0; i
<=mx
; i
++){
4048 struct symbol
*p
= lemp
->symbols
[i
];
4049 if( p
->fallback
==0 ){
4050 fprintf(out
, " 0, /* %10s => nothing */\n", p
->name
);
4052 fprintf(out
, " %3d, /* %10s => %s */\n", p
->fallback
->index
,
4053 p
->name
, p
->fallback
->name
);
4058 tplt_xfer(lemp
->name
, in
, out
, &lineno
);
4060 /* Generate a table containing the symbolic name of every symbol
4062 for(i
=0; i
<lemp
->nsymbol
; i
++){
4063 lemon_sprintf(line
,"\"%s\",",lemp
->symbols
[i
]->name
);
4064 fprintf(out
," %-15s",line
);
4065 if( (i
&3)==3 ){ fprintf(out
,"\n"); lineno
++; }
4067 if( (i
&3)!=0 ){ fprintf(out
,"\n"); lineno
++; }
4068 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4070 /* Generate a table containing a text string that describes every
4071 ** rule in the rule set of the grammar. This information is used
4072 ** when tracing REDUCE actions.
4074 for(i
=0, rp
=lemp
->rule
; rp
; rp
=rp
->next
, i
++){
4075 assert( rp
->index
==i
);
4076 fprintf(out
," /* %3d */ \"", i
);
4077 writeRuleText(out
, rp
);
4078 fprintf(out
,"\",\n"); lineno
++;
4080 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4082 /* Generate code which executes every time a symbol is popped from
4083 ** the stack while processing errors or while destroying the parser.
4084 ** (In other words, generate the %destructor actions)
4086 if( lemp
->tokendest
){
4088 for(i
=0; i
<lemp
->nsymbol
; i
++){
4089 struct symbol
*sp
= lemp
->symbols
[i
];
4090 if( sp
==0 || sp
->type
!=TERMINAL
) continue;
4092 fprintf(out
, " /* TERMINAL Destructor */\n"); lineno
++;
4095 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4097 for(i
=0; i
<lemp
->nsymbol
&& lemp
->symbols
[i
]->type
!=TERMINAL
; i
++);
4098 if( i
<lemp
->nsymbol
){
4099 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4100 fprintf(out
," break;\n"); lineno
++;
4103 if( lemp
->vardest
){
4104 struct symbol
*dflt_sp
= 0;
4106 for(i
=0; i
<lemp
->nsymbol
; i
++){
4107 struct symbol
*sp
= lemp
->symbols
[i
];
4108 if( sp
==0 || sp
->type
==TERMINAL
||
4109 sp
->index
<=0 || sp
->destructor
!=0 ) continue;
4111 fprintf(out
, " /* Default NON-TERMINAL Destructor */\n"); lineno
++;
4114 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4118 emit_destructor_code(out
,dflt_sp
,lemp
,&lineno
);
4120 fprintf(out
," break;\n"); lineno
++;
4122 for(i
=0; i
<lemp
->nsymbol
; i
++){
4123 struct symbol
*sp
= lemp
->symbols
[i
];
4124 if( sp
==0 || sp
->type
==TERMINAL
|| sp
->destructor
==0 ) continue;
4125 fprintf(out
," case %d: /* %s */\n", sp
->index
, sp
->name
); lineno
++;
4127 /* Combine duplicate destructors into a single case */
4128 for(j
=i
+1; j
<lemp
->nsymbol
; j
++){
4129 struct symbol
*sp2
= lemp
->symbols
[j
];
4130 if( sp2
&& sp2
->type
!=TERMINAL
&& sp2
->destructor
4131 && sp2
->dtnum
==sp
->dtnum
4132 && strcmp(sp
->destructor
,sp2
->destructor
)==0 ){
4133 fprintf(out
," case %d: /* %s */\n",
4134 sp2
->index
, sp2
->name
); lineno
++;
4135 sp2
->destructor
= 0;
4139 emit_destructor_code(out
,lemp
->symbols
[i
],lemp
,&lineno
);
4140 fprintf(out
," break;\n"); lineno
++;
4142 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4144 /* Generate code which executes whenever the parser stack overflows */
4145 tplt_print(out
,lemp
,lemp
->overflow
,&lineno
);
4146 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4148 /* Generate the table of rule information
4150 ** Note: This code depends on the fact that rules are number
4151 ** sequentially beginning with 0.
4153 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4154 fprintf(out
," { %d, %d },\n",rp
->lhs
->index
,rp
->nrhs
); lineno
++;
4156 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4158 /* Generate code which execution during each REDUCE action */
4159 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4160 translate_code(lemp
, rp
);
4162 /* First output rules other than the default: rule */
4163 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4164 struct rule
*rp2
; /* Other rules with the same action */
4165 if( rp
->code
==0 ) continue;
4166 if( rp
->code
[0]=='\n' && rp
->code
[1]==0 ) continue; /* Will be default: */
4167 fprintf(out
," case %d: /* ", rp
->index
);
4168 writeRuleText(out
, rp
);
4169 fprintf(out
, " */\n"); lineno
++;
4170 for(rp2
=rp
->next
; rp2
; rp2
=rp2
->next
){
4171 if( rp2
->code
==rp
->code
){
4172 fprintf(out
," case %d: /* ", rp2
->index
);
4173 writeRuleText(out
, rp2
);
4174 fprintf(out
," */ yytestcase(yyruleno==%d);\n", rp2
->index
); lineno
++;
4178 emit_code(out
,rp
,lemp
,&lineno
);
4179 fprintf(out
," break;\n"); lineno
++;
4182 /* Finally, output the default: rule. We choose as the default: all
4183 ** empty actions. */
4184 fprintf(out
," default:\n"); lineno
++;
4185 for(rp
=lemp
->rule
; rp
; rp
=rp
->next
){
4186 if( rp
->code
==0 ) continue;
4187 assert( rp
->code
[0]=='\n' && rp
->code
[1]==0 );
4188 fprintf(out
," /* (%d) ", rp
->index
);
4189 writeRuleText(out
, rp
);
4190 fprintf(out
, " */ yytestcase(yyruleno==%d);\n", rp
->index
); lineno
++;
4192 fprintf(out
," break;\n"); lineno
++;
4193 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4195 /* Generate code which executes if a parse fails */
4196 tplt_print(out
,lemp
,lemp
->failure
,&lineno
);
4197 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4199 /* Generate code which executes when a syntax error occurs */
4200 tplt_print(out
,lemp
,lemp
->error
,&lineno
);
4201 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4203 /* Generate code which executes when the parser accepts its input */
4204 tplt_print(out
,lemp
,lemp
->accept
,&lineno
);
4205 tplt_xfer(lemp
->name
,in
,out
,&lineno
);
4207 /* Append any additional code the user desires */
4208 tplt_print(out
,lemp
,lemp
->extracode
,&lineno
);
4215 /* Generate a header file for the parser */
4216 void ReportHeader(struct lemon
*lemp
)
4220 char line
[LINESIZE
];
4221 char pattern
[LINESIZE
];
4224 if( lemp
->tokenprefix
) prefix
= lemp
->tokenprefix
;
4226 if( output_header_filename
!=0 ){
4227 char *tmp
= lemp
->filename
;
4228 char *ext
= strrchr(output_header_filename
, '.');
4229 if( ext
==0 ) ext
= ".h";
4230 lemp
->filename
= output_header_filename
;
4231 in
= file_open(lemp
,ext
,"rb");
4232 lemp
->filename
= tmp
;
4234 in
= file_open(lemp
,".h","rb");
4238 for(i
=1; i
<lemp
->nterminal
&& fgets(line
,LINESIZE
,in
); i
++){
4239 lemon_sprintf(pattern
,"#define %s%-30s %3d\n",
4240 prefix
,lemp
->symbols
[i
]->name
,i
);
4241 if( strcmp(line
,pattern
) ) break;
4243 nextChar
= fgetc(in
);
4245 if( i
==lemp
->nterminal
&& nextChar
==EOF
){
4246 /* No change in the file. Don't rewrite it. */
4250 if( output_header_filename
!=0 ){
4251 char *tmp
= lemp
->filename
;
4252 char *ext
= strrchr(output_header_filename
, '.');
4253 if( ext
==0 ) ext
= ".h";
4254 lemp
->filename
= output_header_filename
;
4255 out
= file_open(lemp
,ext
,"wb");
4256 lemp
->filename
= tmp
;
4258 out
= file_open(lemp
,".h","wb");
4261 for(i
=1; i
<lemp
->nterminal
; i
++){
4262 fprintf(out
,"#define %s%-30s %3d\n",prefix
,lemp
->symbols
[i
]->name
,i
);
4269 /* Reduce the size of the action tables, if possible, by making use
4272 ** In this version, we take the most frequent REDUCE action and make
4273 ** it the default. Except, there is no default if the wildcard token
4274 ** is a possible look-ahead.
4276 void CompressTables(struct lemon
*lemp
)
4279 struct action
*ap
, *ap2
;
4280 struct rule
*rp
, *rp2
, *rbest
;
4285 for(i
=0; i
<lemp
->nstate
; i
++){
4286 stp
= lemp
->sorted
[i
];
4291 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4292 if( ap
->type
==SHIFT
&& ap
->sp
==lemp
->wildcard
){
4295 if( ap
->type
!=REDUCE
) continue;
4297 if( rp
->lhsStart
) continue;
4298 if( rp
==rbest
) continue;
4300 for(ap2
=ap
->next
; ap2
; ap2
=ap2
->next
){
4301 if( ap2
->type
!=REDUCE
) continue;
4303 if( rp2
==rbest
) continue;
4312 /* Do not make a default if the number of rules to default
4313 ** is not at least 1 or if the wildcard token is a possible
4316 if( nbest
<1 || usesWildcard
) continue;
4319 /* Combine matching REDUCE actions into a single default */
4320 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4321 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) break;
4324 ap
->sp
= Symbol_new("{default}");
4325 for(ap
=ap
->next
; ap
; ap
=ap
->next
){
4326 if( ap
->type
==REDUCE
&& ap
->x
.rp
==rbest
) ap
->type
= NOT_USED
;
4328 stp
->ap
= Action_sort(stp
->ap
);
4334 ** Compare two states for sorting purposes. The smaller state is the
4335 ** one with the most non-terminal actions. If they have the same number
4336 ** of non-terminal actions, then the smaller is the one with the most
4339 static int stateResortCompare(const void *a
, const void *b
){
4340 const struct state
*pA
= *(const struct state
**)a
;
4341 const struct state
*pB
= *(const struct state
**)b
;
4344 n
= pB
->nNtAct
- pA
->nNtAct
;
4346 n
= pB
->nTknAct
- pA
->nTknAct
;
4348 n
= pB
->statenum
- pA
->statenum
;
4357 ** Renumber and resort states so that states with fewer choices
4358 ** occur at the end. Except, keep state 0 as the first state.
4360 void ResortStates(struct lemon
*lemp
)
4366 for(i
=0; i
<lemp
->nstate
; i
++){
4367 stp
= lemp
->sorted
[i
];
4368 stp
->nTknAct
= stp
->nNtAct
= 0;
4369 stp
->iDflt
= lemp
->nstate
+ lemp
->nrule
;
4370 stp
->iTknOfst
= NO_OFFSET
;
4371 stp
->iNtOfst
= NO_OFFSET
;
4372 for(ap
=stp
->ap
; ap
; ap
=ap
->next
){
4373 if( compute_action(lemp
,ap
)>=0 ){
4374 if( ap
->sp
->index
<lemp
->nterminal
){
4376 }else if( ap
->sp
->index
<lemp
->nsymbol
){
4379 stp
->iDflt
= compute_action(lemp
, ap
);
4384 qsort(&lemp
->sorted
[1], lemp
->nstate
-1, sizeof(lemp
->sorted
[0]),
4385 stateResortCompare
);
4386 for(i
=0; i
<lemp
->nstate
; i
++){
4387 lemp
->sorted
[i
]->statenum
= i
;
4392 /***************** From the file "set.c" ************************************/
4394 ** Set manipulation routines for the LEMON parser generator.
4397 static int size
= 0;
4399 /* Set the set size */
4405 /* Allocate a new set */
4408 s
= (char*)calloc( size
, 1);
4410 extern void memory_error();
4416 /* Deallocate a set */
4417 void SetFree(char *s
)
4422 /* Add a new element to the set. Return TRUE if the element was added
4423 ** and FALSE if it was already there. */
4424 int SetAdd(char *s
, int e
)
4427 assert( e
>=0 && e
<size
);
4433 /* Add every element of s2 to s1. Return TRUE if s1 changes. */
4434 int SetUnion(char *s1
, char *s2
)
4438 for(i
=0; i
<size
; i
++){
4439 if( s2
[i
]==0 ) continue;
4447 /********************** From the file "table.c" ****************************/
4449 ** All code in this file has been automatically generated
4450 ** from a specification in the file
4452 ** by the associative array code building program "aagen".
4453 ** Do not edit this file! Instead, edit the specification
4454 ** file, then rerun aagen.
4457 ** Code for processing tables in the LEMON parser generator.
4460 PRIVATE
unsigned strhash(const char *x
)
4463 while( *x
) h
= h
*13 + *(x
++);
4467 /* Works like strdup, sort of. Save a string in malloced memory, but
4468 ** keep strings in a table so that the same string is not in more
4471 const char *Strsafe(const char *y
)
4476 if( y
==0 ) return 0;
4477 z
= Strsafe_find(y
);
4478 if( z
==0 && (cpy
=(char *)malloc( lemonStrlen(y
)+1 ))!=0 ){
4479 lemon_strcpy(cpy
,y
);
4487 /* There is one instance of the following structure for each
4488 ** associative array of type "x1".
4491 int size
; /* The number of available slots. */
4492 /* Must be a power of 2 greater than or */
4494 int count
; /* Number of currently slots filled */
4495 struct s_x1node
*tbl
; /* The data stored here */
4496 struct s_x1node
**ht
; /* Hash table for lookups */
4499 /* There is one instance of this structure for every data element
4500 ** in an associative array of type "x1".
4502 typedef struct s_x1node
{
4503 const char *data
; /* The data */
4504 struct s_x1node
*next
; /* Next entry with the same hash */
4505 struct s_x1node
**from
; /* Previous link */
4508 /* There is only one instance of the array, which is the following */
4509 static struct s_x1
*x1a
;
4511 /* Allocate a new associative array */
4512 void Strsafe_init(){
4514 x1a
= (struct s_x1
*)malloc( sizeof(struct s_x1
) );
4518 x1a
->tbl
= (x1node
*)calloc(1024, sizeof(x1node
) + sizeof(x1node
*));
4523 x1a
->ht
= (x1node
**)&(x1a
->tbl
[1024]);
4524 for(i
=0; i
<1024; i
++) x1a
->ht
[i
] = 0;
4530 /* Insert a new record into the array. Return TRUE if successful.
4531 ** Prior data with the same key is NOT overwritten */
4532 int Strsafe_insert(const char *data
)
4538 if( x1a
==0 ) return 0;
4540 h
= ph
& (x1a
->size
-1);
4543 if( strcmp(np
->data
,data
)==0 ){
4544 /* An existing entry with the same key is found. */
4545 /* Fail because overwrite is not allows. */
4550 if( x1a
->count
>=x1a
->size
){
4551 /* Need to make the hash table bigger */
4554 array
.size
= size
= x1a
->size
*2;
4555 array
.count
= x1a
->count
;
4556 array
.tbl
= (x1node
*)calloc(size
, sizeof(x1node
) + sizeof(x1node
*));
4557 MemoryCheck(array
.tbl
);
4558 array
.ht
= (x1node
**)&(array
.tbl
[size
]);
4559 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
4560 for(i
=0; i
<x1a
->count
; i
++){
4561 x1node
*oldnp
, *newnp
;
4562 oldnp
= &(x1a
->tbl
[i
]);
4563 h
= strhash(oldnp
->data
) & (size
-1);
4564 newnp
= &(array
.tbl
[i
]);
4565 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4566 newnp
->next
= array
.ht
[h
];
4567 newnp
->data
= oldnp
->data
;
4568 newnp
->from
= &(array
.ht
[h
]);
4569 array
.ht
[h
] = newnp
;
4574 /* Insert the new data */
4575 h
= ph
& (x1a
->size
-1);
4576 np
= &(x1a
->tbl
[x1a
->count
++]);
4578 if( x1a
->ht
[h
] ) x1a
->ht
[h
]->from
= &(np
->next
);
4579 np
->next
= x1a
->ht
[h
];
4581 np
->from
= &(x1a
->ht
[h
]);
4585 /* Return a pointer to data assigned to the given key. Return NULL
4586 ** if no such key. */
4587 const char *Strsafe_find(const char *key
)
4592 if( x1a
==0 ) return 0;
4593 h
= strhash(key
) & (x1a
->size
-1);
4596 if( strcmp(np
->data
,key
)==0 ) break;
4599 return np
? np
->data
: 0;
4602 /* Return a pointer to the (terminal or nonterminal) symbol "x".
4603 ** Create a new symbol if this is the first time "x" has been seen.
4605 struct symbol
*Symbol_new(const char *x
)
4609 sp
= Symbol_find(x
);
4611 sp
= (struct symbol
*)calloc(1, sizeof(struct symbol
) );
4613 sp
->name
= Strsafe(x
);
4614 sp
->type
= isupper(*x
) ? TERMINAL
: NONTERMINAL
;
4620 sp
->lambda
= LEMON_FALSE
;
4625 Symbol_insert(sp
,sp
->name
);
4631 /* Compare two symbols for sorting purposes. Return negative,
4632 ** zero, or positive if a is less then, equal to, or greater
4635 ** Symbols that begin with upper case letters (terminals or tokens)
4636 ** must sort before symbols that begin with lower case letters
4637 ** (non-terminals). And MULTITERMINAL symbols (created using the
4638 ** %token_class directive) must sort at the very end. Other than
4639 ** that, the order does not matter.
4641 ** We find experimentally that leaving the symbols in their original
4642 ** order (the order they appeared in the grammar file) gives the
4643 ** smallest parser tables in SQLite.
4645 int Symbolcmpp(const void *_a
, const void *_b
)
4647 const struct symbol
*a
= *(const struct symbol
**)_a
;
4648 const struct symbol
*b
= *(const struct symbol
**)_b
;
4649 int i1
= a
->type
==MULTITERMINAL
? 3 : a
->name
[0]>'Z' ? 2 : 1;
4650 int i2
= b
->type
==MULTITERMINAL
? 3 : b
->name
[0]>'Z' ? 2 : 1;
4651 return i1
==i2
? a
->index
- b
->index
: i1
- i2
;
4654 /* There is one instance of the following structure for each
4655 ** associative array of type "x2".
4658 int size
; /* The number of available slots. */
4659 /* Must be a power of 2 greater than or */
4661 int count
; /* Number of currently slots filled */
4662 struct s_x2node
*tbl
; /* The data stored here */
4663 struct s_x2node
**ht
; /* Hash table for lookups */
4666 /* There is one instance of this structure for every data element
4667 ** in an associative array of type "x2".
4669 typedef struct s_x2node
{
4670 struct symbol
*data
; /* The data */
4671 const char *key
; /* The key */
4672 struct s_x2node
*next
; /* Next entry with the same hash */
4673 struct s_x2node
**from
; /* Previous link */
4676 /* There is only one instance of the array, which is the following */
4677 static struct s_x2
*x2a
;
4679 /* Allocate a new associative array */
4682 x2a
= (struct s_x2
*)malloc( sizeof(struct s_x2
) );
4686 x2a
->tbl
= (x2node
*)calloc(128, sizeof(x2node
) + sizeof(x2node
*));
4691 x2a
->ht
= (x2node
**)&(x2a
->tbl
[128]);
4692 for(i
=0; i
<128; i
++) x2a
->ht
[i
] = 0;
4698 /* Insert a new record into the array. Return TRUE if successful.
4699 ** Prior data with the same key is NOT overwritten */
4700 int Symbol_insert(struct symbol
*data
, const char *key
)
4706 if( x2a
==0 ) return 0;
4708 h
= ph
& (x2a
->size
-1);
4711 if( strcmp(np
->key
,key
)==0 ){
4712 /* An existing entry with the same key is found. */
4713 /* Fail because overwrite is not allows. */
4718 if( x2a
->count
>=x2a
->size
){
4719 /* Need to make the hash table bigger */
4722 array
.size
= size
= x2a
->size
*2;
4723 array
.count
= x2a
->count
;
4724 array
.tbl
= (x2node
*)calloc(size
, sizeof(x2node
) + sizeof(x2node
*));
4725 MemoryCheck(array
.tbl
);
4726 array
.ht
= (x2node
**)&(array
.tbl
[size
]);
4727 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
4728 for(i
=0; i
<x2a
->count
; i
++){
4729 x2node
*oldnp
, *newnp
;
4730 oldnp
= &(x2a
->tbl
[i
]);
4731 h
= strhash(oldnp
->key
) & (size
-1);
4732 newnp
= &(array
.tbl
[i
]);
4733 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4734 newnp
->next
= array
.ht
[h
];
4735 newnp
->key
= oldnp
->key
;
4736 newnp
->data
= oldnp
->data
;
4737 newnp
->from
= &(array
.ht
[h
]);
4738 array
.ht
[h
] = newnp
;
4743 /* Insert the new data */
4744 h
= ph
& (x2a
->size
-1);
4745 np
= &(x2a
->tbl
[x2a
->count
++]);
4748 if( x2a
->ht
[h
] ) x2a
->ht
[h
]->from
= &(np
->next
);
4749 np
->next
= x2a
->ht
[h
];
4751 np
->from
= &(x2a
->ht
[h
]);
4755 /* Return a pointer to data assigned to the given key. Return NULL
4756 ** if no such key. */
4757 struct symbol
*Symbol_find(const char *key
)
4762 if( x2a
==0 ) return 0;
4763 h
= strhash(key
) & (x2a
->size
-1);
4766 if( strcmp(np
->key
,key
)==0 ) break;
4769 return np
? np
->data
: 0;
4772 /* Return the n-th data. Return NULL if n is out of range. */
4773 struct symbol
*Symbol_Nth(int n
)
4775 struct symbol
*data
;
4776 if( x2a
&& n
>0 && n
<=x2a
->count
){
4777 data
= x2a
->tbl
[n
-1].data
;
4784 /* Return the size of the array */
4787 return x2a
? x2a
->count
: 0;
4790 /* Return an array of pointers to all data in the table.
4791 ** The array is obtained from malloc. Return NULL if memory allocation
4792 ** problems, or if the array is empty. */
4793 struct symbol
**Symbol_arrayof()
4795 struct symbol
**array
;
4797 if( x2a
==0 ) return 0;
4799 array
= (struct symbol
**)calloc(size
, sizeof(struct symbol
*));
4801 for(i
=0; i
<size
; i
++) array
[i
] = x2a
->tbl
[i
].data
;
4808 /* Compare two configurations */
4809 int Configcmp(const char *_a
,const char *_b
)
4811 const struct config
*a
= (struct config
*) _a
;
4812 const struct config
*b
= (struct config
*) _b
;
4814 x
= a
->rp
->index
- b
->rp
->index
;
4815 if( x
==0 ) x
= a
->dot
- b
->dot
;
4819 /* Compare two states */
4820 PRIVATE
int statecmp(struct config
*a
, struct config
*b
)
4823 for(rc
=0; rc
==0 && a
&& b
; a
=a
->bp
, b
=b
->bp
){
4824 rc
= a
->rp
->index
- b
->rp
->index
;
4825 if( rc
==0 ) rc
= a
->dot
- b
->dot
;
4835 PRIVATE
unsigned statehash(struct config
*a
)
4839 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
4845 /* Allocate a new state structure */
4846 struct state
*State_new()
4848 struct state
*newstate
;
4849 newstate
= (struct state
*)calloc(1, sizeof(struct state
) );
4850 MemoryCheck(newstate
);
4854 /* There is one instance of the following structure for each
4855 ** associative array of type "x3".
4858 int size
; /* The number of available slots. */
4859 /* Must be a power of 2 greater than or */
4861 int count
; /* Number of currently slots filled */
4862 struct s_x3node
*tbl
; /* The data stored here */
4863 struct s_x3node
**ht
; /* Hash table for lookups */
4866 /* There is one instance of this structure for every data element
4867 ** in an associative array of type "x3".
4869 typedef struct s_x3node
{
4870 struct state
*data
; /* The data */
4871 struct config
*key
; /* The key */
4872 struct s_x3node
*next
; /* Next entry with the same hash */
4873 struct s_x3node
**from
; /* Previous link */
4876 /* There is only one instance of the array, which is the following */
4877 static struct s_x3
*x3a
;
4879 /* Allocate a new associative array */
4882 x3a
= (struct s_x3
*)malloc( sizeof(struct s_x3
) );
4886 x3a
->tbl
= (x3node
*)calloc(128, sizeof(x3node
) + sizeof(x3node
*));
4891 x3a
->ht
= (x3node
**)&(x3a
->tbl
[128]);
4892 for(i
=0; i
<128; i
++) x3a
->ht
[i
] = 0;
4898 /* Insert a new record into the array. Return TRUE if successful.
4899 ** Prior data with the same key is NOT overwritten */
4900 int State_insert(struct state
*data
, struct config
*key
)
4906 if( x3a
==0 ) return 0;
4907 ph
= statehash(key
);
4908 h
= ph
& (x3a
->size
-1);
4911 if( statecmp(np
->key
,key
)==0 ){
4912 /* An existing entry with the same key is found. */
4913 /* Fail because overwrite is not allows. */
4918 if( x3a
->count
>=x3a
->size
){
4919 /* Need to make the hash table bigger */
4922 array
.size
= size
= x3a
->size
*2;
4923 array
.count
= x3a
->count
;
4924 array
.tbl
= (x3node
*)calloc(size
, sizeof(x3node
) + sizeof(x3node
*));
4925 MemoryCheck(array
.tbl
);
4926 array
.ht
= (x3node
**)&(array
.tbl
[size
]);
4927 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
4928 for(i
=0; i
<x3a
->count
; i
++){
4929 x3node
*oldnp
, *newnp
;
4930 oldnp
= &(x3a
->tbl
[i
]);
4931 h
= statehash(oldnp
->key
) & (size
-1);
4932 newnp
= &(array
.tbl
[i
]);
4933 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
4934 newnp
->next
= array
.ht
[h
];
4935 newnp
->key
= oldnp
->key
;
4936 newnp
->data
= oldnp
->data
;
4937 newnp
->from
= &(array
.ht
[h
]);
4938 array
.ht
[h
] = newnp
;
4943 /* Insert the new data */
4944 h
= ph
& (x3a
->size
-1);
4945 np
= &(x3a
->tbl
[x3a
->count
++]);
4948 if( x3a
->ht
[h
] ) x3a
->ht
[h
]->from
= &(np
->next
);
4949 np
->next
= x3a
->ht
[h
];
4951 np
->from
= &(x3a
->ht
[h
]);
4955 /* Return a pointer to data assigned to the given key. Return NULL
4956 ** if no such key. */
4957 struct state
*State_find(struct config
*key
)
4962 if( x3a
==0 ) return 0;
4963 h
= statehash(key
) & (x3a
->size
-1);
4966 if( statecmp(np
->key
,key
)==0 ) break;
4969 return np
? np
->data
: 0;
4972 /* Return an array of pointers to all data in the table.
4973 ** The array is obtained from malloc. Return NULL if the array is empty. */
4974 struct state
**State_arrayof()
4976 struct state
**array
;
4978 if( x3a
==0 ) return 0;
4980 array
= (struct state
**)calloc(size
, sizeof(struct state
*));
4982 for(i
=0; i
<size
; i
++) array
[i
] = x3a
->tbl
[i
].data
;
4989 /* Hash a configuration */
4990 PRIVATE
unsigned confighash(struct config
*a
)
4993 h
= h
*571 + a
->rp
->index
*37 + a
->dot
;
4997 /* There is one instance of the following structure for each
4998 ** associative array of type "x4".
5001 int size
; /* The number of available slots. */
5002 /* Must be a power of 2 greater than or */
5004 int count
; /* Number of currently slots filled */
5005 struct s_x4node
*tbl
; /* The data stored here */
5006 struct s_x4node
**ht
; /* Hash table for lookups */
5009 /* There is one instance of this structure for every data element
5010 ** in an associative array of type "x4".
5012 typedef struct s_x4node
{
5013 struct config
*data
; /* The data */
5014 struct s_x4node
*next
; /* Next entry with the same hash */
5015 struct s_x4node
**from
; /* Previous link */
5018 /* There is only one instance of the array, which is the following */
5019 static struct s_x4
*x4a
;
5021 /* Allocate a new associative array */
5022 void Configtable_init(){
5024 x4a
= (struct s_x4
*)malloc( sizeof(struct s_x4
) );
5028 x4a
->tbl
= (x4node
*)calloc(64, sizeof(x4node
) + sizeof(x4node
*));
5033 x4a
->ht
= (x4node
**)&(x4a
->tbl
[64]);
5034 for(i
=0; i
<64; i
++) x4a
->ht
[i
] = 0;
5040 /* Insert a new record into the array. Return TRUE if successful.
5041 ** Prior data with the same key is NOT overwritten */
5042 int Configtable_insert(struct config
*data
)
5048 if( x4a
==0 ) return 0;
5049 ph
= confighash(data
);
5050 h
= ph
& (x4a
->size
-1);
5053 if( Configcmp((const char *) np
->data
,(const char *) data
)==0 ){
5054 /* An existing entry with the same key is found. */
5055 /* Fail because overwrite is not allows. */
5060 if( x4a
->count
>=x4a
->size
){
5061 /* Need to make the hash table bigger */
5064 array
.size
= size
= x4a
->size
*2;
5065 array
.count
= x4a
->count
;
5066 array
.tbl
= (x4node
*)calloc(size
, sizeof(x4node
) + sizeof(x4node
*));
5067 MemoryCheck(array
.tbl
);
5068 array
.ht
= (x4node
**)&(array
.tbl
[size
]);
5069 for(i
=0; i
<size
; i
++) array
.ht
[i
] = 0;
5070 for(i
=0; i
<x4a
->count
; i
++){
5071 x4node
*oldnp
, *newnp
;
5072 oldnp
= &(x4a
->tbl
[i
]);
5073 h
= confighash(oldnp
->data
) & (size
-1);
5074 newnp
= &(array
.tbl
[i
]);
5075 if( array
.ht
[h
] ) array
.ht
[h
]->from
= &(newnp
->next
);
5076 newnp
->next
= array
.ht
[h
];
5077 newnp
->data
= oldnp
->data
;
5078 newnp
->from
= &(array
.ht
[h
]);
5079 array
.ht
[h
] = newnp
;
5084 /* Insert the new data */
5085 h
= ph
& (x4a
->size
-1);
5086 np
= &(x4a
->tbl
[x4a
->count
++]);
5088 if( x4a
->ht
[h
] ) x4a
->ht
[h
]->from
= &(np
->next
);
5089 np
->next
= x4a
->ht
[h
];
5091 np
->from
= &(x4a
->ht
[h
]);
5095 /* Return a pointer to data assigned to the given key. Return NULL
5096 ** if no such key. */
5097 struct config
*Configtable_find(struct config
*key
)
5102 if( x4a
==0 ) return 0;
5103 h
= confighash(key
) & (x4a
->size
-1);
5106 if( Configcmp((const char *) np
->data
,(const char *) key
)==0 ) break;
5109 return np
? np
->data
: 0;
5112 /* Remove all data from the table. Pass each data to the function "f"
5113 ** as it is removed. ("f" may be null to avoid this step.) */
5114 void Configtable_clear(int(*f
)(struct config
*))
5117 if( x4a
==0 || x4a
->count
==0 ) return;
5118 if( f
) for(i
=0; i
<x4a
->count
; i
++) (*f
)(x4a
->tbl
[i
].data
);
5119 for(i
=0; i
<x4a
->size
; i
++) x4a
->ht
[i
] = 0;