1 /*
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.
6 **
7 ** The author of this program disclaims copyright.
8 */
9 #include <stdio.h>
10 #include <stdarg.h>
11 #include <string.h>
12 #include <ctype.h>
13 #include <stdlib.h>
14 #include <assert.h>
15
16 #define ISSPACE(X) isspace((unsigned char)(X))
17 #define ISDIGIT(X) isdigit((unsigned char)(X))
18 #define ISALNUM(X) isalnum((unsigned char)(X))
19 #define ISALPHA(X) isalpha((unsigned char)(X))
20 #define ISUPPER(X) isupper((unsigned char)(X))
21 #define ISLOWER(X) islower((unsigned char)(X))
22
23
24 #ifndef __WIN32__
25 # if defined(_WIN32) || defined(WIN32)
26 # define __WIN32__
27 # endif
28 #endif
29
30 #ifdef __WIN32__
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34 extern int access(const char *path, int mode);
35 #ifdef __cplusplus
36 }
37 #endif
38 #else
39 #include <unistd.h>
40 #endif
41
42 /* #define PRIVATE static */
43 #define PRIVATE
44
45 #ifdef TEST
46 #define MAXRHS 5 /* Set low to exercise exception code */
47 #else
48 #define MAXRHS 1000
49 #endif
50
51 extern void memory_error(void);
52 static int showPrecedenceConflict = 0;
53 static char *msort(char*,char**,int(*)(const char*,const char*));
54
55 /*
56 ** Compilers are getting increasingly pedantic about type conversions
57 ** as C evolves ever closer to Ada.... To work around the latest problems
58 ** we have to define the following variant of strlen().
59 */
60 #define lemonStrlen(X) ((int)strlen(X))
61
62 /*
63 ** Compilers are starting to complain about the use of sprintf() and strcpy(),
64 ** saying they are unsafe. So we define our own versions of those routines too.
65 **
66 ** There are three routines here: lemon_sprintf(), lemon_vsprintf(), and
67 ** lemon_addtext(). The first two are replacements for sprintf() and vsprintf().
68 ** The third is a helper routine for vsnprintf() that adds texts to the end of a
69 ** buffer, making sure the buffer is always zero-terminated.
70 **
71 ** The string formatter is a minimal subset of stdlib sprintf() supporting only
72 ** a few simply conversions:
73 **
74 ** %d
75 ** %s
76 ** %.*s
77 **
78 */
lemon_addtext(char * zBuf,int * pnUsed,const char * zIn,int nIn,int iWidth)79 static void lemon_addtext(
80 char *zBuf, /* The buffer to which text is added */
81 int *pnUsed, /* Slots of the buffer used so far */
82 const char *zIn, /* Text to add */
83 int nIn, /* Bytes of text to add. -1 to use strlen() */
84 int iWidth /* Field width. Negative to left justify */
85 ){
86 if( nIn<0 ) for(nIn=0; zIn[nIn]; nIn++){}
87 while( iWidth>nIn ){ zBuf[(*pnUsed)++] = ' '; iWidth--; }
88 if( nIn==0 ) return;
89 memcpy(&zBuf[*pnUsed], zIn, nIn);
90 *pnUsed += nIn;
91 while( (-iWidth)>nIn ){ zBuf[(*pnUsed)++] = ' '; iWidth++; }
92 zBuf[*pnUsed] = 0;
93 }
lemon_vsprintf(char * str,const char * zFormat,va_list ap)94 static int lemon_vsprintf(char *str, const char *zFormat, va_list ap){
95 int i, j, k, c;
96 int nUsed = 0;
97 const char *z;
98 char zTemp[50];
99 str[0] = 0;
100 for(i=j=0; (c = zFormat[i])!=0; i++){
101 if( c=='%' ){
102 int iWidth = 0;
103 lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0);
104 c = zFormat[++i];
105 if( ISDIGIT(c) || (c=='-' && ISDIGIT(zFormat[i+1])) ){
106 if( c=='-' ) i++;
107 while( ISDIGIT(zFormat[i]) ) iWidth = iWidth*10 + zFormat[i++] - '0';
108 if( c=='-' ) iWidth = -iWidth;
109 c = zFormat[i];
110 }
111 if( c=='d' ){
112 int v = va_arg(ap, int);
113 if( v<0 ){
114 lemon_addtext(str, &nUsed, "-", 1, iWidth);
115 v = -v;
116 }else if( v==0 ){
117 lemon_addtext(str, &nUsed, "0", 1, iWidth);
118 }
119 k = 0;
120 while( v>0 ){
121 k++;
122 zTemp[sizeof(zTemp)-k] = (v%10) + '0';
123 v /= 10;
124 }
125 lemon_addtext(str, &nUsed, &zTemp[sizeof(zTemp)-k], k, iWidth);
126 }else if( c=='s' ){
127 z = va_arg(ap, const char*);
128 lemon_addtext(str, &nUsed, z, -1, iWidth);
129 }else if( c=='.' && memcmp(&zFormat[i], ".*s", 3)==0 ){
130 i += 2;
131 k = va_arg(ap, int);
132 z = va_arg(ap, const char*);
133 lemon_addtext(str, &nUsed, z, k, iWidth);
134 }else if( c=='%' ){
135 lemon_addtext(str, &nUsed, "%", 1, 0);
136 }else{
137 fprintf(stderr, "illegal format\n");
138 exit(1);
139 }
140 j = i+1;
141 }
142 }
143 lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0);
144 return nUsed;
145 }
lemon_sprintf(char * str,const char * format,...)146 static int lemon_sprintf(char *str, const char *format, ...){
147 va_list ap;
148 int rc;
149 va_start(ap, format);
150 rc = lemon_vsprintf(str, format, ap);
151 va_end(ap);
152 return rc;
153 }
lemon_strcpy(char * dest,const char * src)154 static void lemon_strcpy(char *dest, const char *src){
155 while( (*(dest++) = *(src++))!=0 ){}
156 }
lemon_strcat(char * dest,const char * src)157 static void lemon_strcat(char *dest, const char *src){
158 while( *dest ) dest++;
159 lemon_strcpy(dest, src);
160 }
161
162
163 /* a few forward declarations... */
164 struct rule;
165 struct lemon;
166 struct action;
167
168 static struct action *Action_new(void);
169 static struct action *Action_sort(struct action *);
170
171 /********** From the file "build.h" ************************************/
172 void FindRulePrecedences(struct lemon*);
173 void FindFirstSets(struct lemon*);
174 void FindStates(struct lemon*);
175 void FindLinks(struct lemon*);
176 void FindFollowSets(struct lemon*);
177 void FindActions(struct lemon*);
178
179 /********* From the file "configlist.h" *********************************/
180 void Configlist_init(void);
181 struct config *Configlist_add(struct rule *, int);
182 struct config *Configlist_addbasis(struct rule *, int);
183 void Configlist_closure(struct lemon *);
184 void Configlist_sort(void);
185 void Configlist_sortbasis(void);
186 struct config *Configlist_return(void);
187 struct config *Configlist_basis(void);
188 void Configlist_eat(struct config *);
189 void Configlist_reset(void);
190
191 /********* From the file "error.h" ***************************************/
192 void ErrorMsg(const char *, int,const char *, ...);
193
194 /****** From the file "option.h" ******************************************/
195 enum option_type { OPT_FLAG=1, OPT_INT, OPT_DBL, OPT_STR,
196 OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR};
197 struct s_options {
198 enum option_type type;
199 const char *label;
200 char *arg;
201 const char *message;
202 };
203 int OptInit(char**,struct s_options*,FILE*);
204 int OptNArgs(void);
205 char *OptArg(int);
206 void OptErr(int);
207 void OptPrint(void);
208
209 /******** From the file "parse.h" *****************************************/
210 void Parse(struct lemon *lemp);
211
212 /********* From the file "plink.h" ***************************************/
213 struct plink *Plink_new(void);
214 void Plink_add(struct plink **, struct config *);
215 void Plink_copy(struct plink **, struct plink *);
216 void Plink_delete(struct plink *);
217
218 /********** From the file "report.h" *************************************/
219 void Reprint(struct lemon *);
220 void ReportOutput(struct lemon *);
221 void ReportTable(struct lemon *, int, int);
222 void ReportHeader(struct lemon *);
223 void CompressTables(struct lemon *);
224 void ResortStates(struct lemon *);
225
226 /********** From the file "set.h" ****************************************/
227 void SetSize(int); /* All sets will be of size N */
228 char *SetNew(void); /* A new set for element 0..N */
229 void SetFree(char*); /* Deallocate a set */
230 int SetAdd(char*,int); /* Add element to a set */
231 int SetUnion(char *,char *); /* A <- A U B, thru element N */
232 #define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
233
234 /********** From the file "struct.h" *************************************/
235 /*
236 ** Principal data structures for the LEMON parser generator.
237 */
238
239 typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;
240
241 /* Symbols (terminals and nonterminals) of the grammar are stored
242 ** in the following: */
243 enum symbol_type {
244 TERMINAL,
245 NONTERMINAL,
246 MULTITERMINAL
247 };
248 enum e_assoc {
249 LEFT,
250 RIGHT,
251 NONE,
252 UNK
253 };
254 struct symbol {
255 const char *name; /* Name of the symbol */
256 int index; /* Index number for this symbol */
257 enum symbol_type type; /* Symbols are all either TERMINALS or NTs */
258 struct rule *rule; /* Linked list of rules of this (if an NT) */
259 struct symbol *fallback; /* fallback token in case this token doesn't parse */
260 int prec; /* Precedence if defined (-1 otherwise) */
261 enum e_assoc assoc; /* Associativity if precedence is defined */
262 char *firstset; /* First-set for all rules of this symbol */
263 Boolean lambda; /* True if NT and can generate an empty string */
264 int useCnt; /* Number of times used */
265 char *destructor; /* Code which executes whenever this symbol is
266 ** popped from the stack during error processing */
267 int destLineno; /* Line number for start of destructor. Set to
268 ** -1 for duplicate destructors. */
269 char *datatype; /* The data type of information held by this
270 ** object. Only used if type==NONTERMINAL */
271 int dtnum; /* The data type number. In the parser, the value
272 ** stack is a union. The .yy%d element of this
273 ** union is the correct data type for this object */
274 int bContent; /* True if this symbol ever carries content - if
275 ** it is ever more than just syntax */
276 /* The following fields are used by MULTITERMINALs only */
277 int nsubsym; /* Number of constituent symbols in the MULTI */
278 struct symbol **subsym; /* Array of constituent symbols */
279 };
280
281 /* Each production rule in the grammar is stored in the following
282 ** structure. */
283 struct rule {
284 struct symbol *lhs; /* Left-hand side of the rule */
285 const char *lhsalias; /* Alias for the LHS (NULL if none) */
286 int lhsStart; /* True if left-hand side is the start symbol */
287 int ruleline; /* Line number for the rule */
288 int nrhs; /* Number of RHS symbols */
289 struct symbol **rhs; /* The RHS symbols */
290 const char **rhsalias; /* An alias for each RHS symbol (NULL if none) */
291 int line; /* Line number at which code begins */
292 const char *code; /* The code executed when this rule is reduced */
293 const char *codePrefix; /* Setup code before code[] above */
294 const char *codeSuffix; /* Breakdown code after code[] above */
295 struct symbol *precsym; /* Precedence symbol for this rule */
296 int index; /* An index number for this rule */
297 int iRule; /* Rule number as used in the generated tables */
298 Boolean noCode; /* True if this rule has no associated C code */
299 Boolean codeEmitted; /* True if the code has been emitted already */
300 Boolean canReduce; /* True if this rule is ever reduced */
301 Boolean doesReduce; /* Reduce actions occur after optimization */
302 Boolean neverReduce; /* Reduce is theoretically possible, but prevented
303 ** by actions or other outside implementation */
304 struct rule *nextlhs; /* Next rule with the same LHS */
305 struct rule *next; /* Next rule in the global list */
306 };
307
308 /* A configuration is a production rule of the grammar together with
309 ** a mark (dot) showing how much of that rule has been processed so far.
310 ** Configurations also contain a follow-set which is a list of terminal
311 ** symbols which are allowed to immediately follow the end of the rule.
312 ** Every configuration is recorded as an instance of the following: */
313 enum cfgstatus {
314 COMPLETE,
315 INCOMPLETE
316 };
317 struct config {
318 struct rule *rp; /* The rule upon which the configuration is based */
319 int dot; /* The parse point */
320 char *fws; /* Follow-set for this configuration only */
321 struct plink *fplp; /* Follow-set forward propagation links */
322 struct plink *bplp; /* Follow-set backwards propagation links */
323 struct state *stp; /* Pointer to state which contains this */
324 enum cfgstatus status; /* used during followset and shift computations */
325 struct config *next; /* Next configuration in the state */
326 struct config *bp; /* The next basis configuration */
327 };
328
329 enum e_action {
330 SHIFT,
331 ACCEPT,
332 REDUCE,
333 ERROR,
334 SSCONFLICT, /* A shift/shift conflict */
335 SRCONFLICT, /* Was a reduce, but part of a conflict */
336 RRCONFLICT, /* Was a reduce, but part of a conflict */
337 SH_RESOLVED, /* Was a shift. Precedence resolved conflict */
338 RD_RESOLVED, /* Was reduce. Precedence resolved conflict */
339 NOT_USED, /* Deleted by compression */
340 SHIFTREDUCE /* Shift first, then reduce */
341 };
342
343 /* Every shift or reduce operation is stored as one of the following */
344 struct action {
345 struct symbol *sp; /* The look-ahead symbol */
346 enum e_action type;
347 union {
348 struct state *stp; /* The new state, if a shift */
349 struct rule *rp; /* The rule, if a reduce */
350 } x;
351 struct symbol *spOpt; /* SHIFTREDUCE optimization to this symbol */
352 struct action *next; /* Next action for this state */
353 struct action *collide; /* Next action with the same hash */
354 };
355
356 /* Each state of the generated parser's finite state machine
357 ** is encoded as an instance of the following structure. */
358 struct state {
359 struct config *bp; /* The basis configurations for this state */
360 struct config *cfp; /* All configurations in this set */
361 int statenum; /* Sequential number for this state */
362 struct action *ap; /* List of actions for this state */
363 int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */
364 int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */
365 int iDfltReduce; /* Default action is to REDUCE by this rule */
366 struct rule *pDfltReduce;/* The default REDUCE rule. */
367 int autoReduce; /* True if this is an auto-reduce state */
368 };
369 #define NO_OFFSET (-2147483647)
370
371 /* A followset propagation link indicates that the contents of one
372 ** configuration followset should be propagated to another whenever
373 ** the first changes. */
374 struct plink {
375 struct config *cfp; /* The configuration to which linked */
376 struct plink *next; /* The next propagate link */
377 };
378
379 /* The state vector for the entire parser generator is recorded as
380 ** follows. (LEMON uses no global variables and makes little use of
381 ** static variables. Fields in the following structure can be thought
382 ** of as begin global variables in the program.) */
383 struct lemon {
384 struct state **sorted; /* Table of states sorted by state number */
385 struct rule *rule; /* List of all rules */
386 struct rule *startRule; /* First rule */
387 int nstate; /* Number of states */
388 int nxstate; /* nstate with tail degenerate states removed */
389 int nrule; /* Number of rules */
390 int nruleWithAction; /* Number of rules with actions */
391 int nsymbol; /* Number of terminal and nonterminal symbols */
392 int nterminal; /* Number of terminal symbols */
393 int minShiftReduce; /* Minimum shift-reduce action value */
394 int errAction; /* Error action value */
395 int accAction; /* Accept action value */
396 int noAction; /* No-op action value */
397 int minReduce; /* Minimum reduce action */
398 int maxAction; /* Maximum action value of any kind */
399 struct symbol **symbols; /* Sorted array of pointers to symbols */
400 int errorcnt; /* Number of errors */
401 struct symbol *errsym; /* The error symbol */
402 struct symbol *wildcard; /* Token that matches anything */
403 char *name; /* Name of the generated parser */
404 char *arg; /* Declaration of the 3th argument to parser */
405 char *ctx; /* Declaration of 2nd argument to constructor */
406 char *tokentype; /* Type of terminal symbols in the parser stack */
407 char *vartype; /* The default type of non-terminal symbols */
408 char *start; /* Name of the start symbol for the grammar */
409 char *stacksize; /* Size of the parser stack */
410 char *include; /* Code to put at the start of the C file */
411 char *error; /* Code to execute when an error is seen */
412 char *overflow; /* Code to execute on a stack overflow */
413 char *failure; /* Code to execute on parser failure */
414 char *accept; /* Code to execute when the parser excepts */
415 char *extracode; /* Code appended to the generated file */
416 char *tokendest; /* Code to execute to destroy token data */
417 char *vardest; /* Code for the default non-terminal destructor */
418 char *filename; /* Name of the input file */
419 char *outname; /* Name of the current output file */
420 char *tokenprefix; /* A prefix added to token names in the .h file */
421 int nconflict; /* Number of parsing conflicts */
422 int nactiontab; /* Number of entries in the yy_action[] table */
423 int nlookaheadtab; /* Number of entries in yy_lookahead[] */
424 int tablesize; /* Total table size of all tables in bytes */
425 int basisflag; /* Print only basis configurations */
426 int printPreprocessed; /* Show preprocessor output on stdout */
427 int has_fallback; /* True if any %fallback is seen in the grammar */
428 int nolinenosflag; /* True if #line statements should not be printed */
429 char *argv0; /* Name of the program */
430 };
431
432 #define MemoryCheck(X) if((X)==0){ \
433 memory_error(); \
434 }
435
436 /**************** From the file "table.h" *********************************/
437 /*
438 ** All code in this file has been automatically generated
439 ** from a specification in the file
440 ** "table.q"
441 ** by the associative array code building program "aagen".
442 ** Do not edit this file! Instead, edit the specification
443 ** file, then rerun aagen.
444 */
445 /*
446 ** Code for processing tables in the LEMON parser generator.
447 */
448 /* Routines for handling a strings */
449
450 const char *Strsafe(const char *);
451
452 void Strsafe_init(void);
453 int Strsafe_insert(const char *);
454 const char *Strsafe_find(const char *);
455
456 /* Routines for handling symbols of the grammar */
457
458 struct symbol *Symbol_new(const char *);
459 int Symbolcmpp(const void *, const void *);
460 void Symbol_init(void);
461 int Symbol_insert(struct symbol *, const char *);
462 struct symbol *Symbol_find(const char *);
463 struct symbol *Symbol_Nth(int);
464 int Symbol_count(void);
465 struct symbol **Symbol_arrayof(void);
466
467 /* Routines to manage the state table */
468
469 int Configcmp(const char *, const char *);
470 struct state *State_new(void);
471 void State_init(void);
472 int State_insert(struct state *, struct config *);
473 struct state *State_find(struct config *);
474 struct state **State_arrayof(void);
475
476 /* Routines used for efficiency in Configlist_add */
477
478 void Configtable_init(void);
479 int Configtable_insert(struct config *);
480 struct config *Configtable_find(struct config *);
481 void Configtable_clear(int(*)(struct config *));
482
483 /****************** From the file "action.c" *******************************/
484 /*
485 ** Routines processing parser actions in the LEMON parser generator.
486 */
487
488 /* Allocate a new parser action */
Action_new(void)489 static struct action *Action_new(void){
490 static struct action *actionfreelist = 0;
491 struct action *newaction;
492
493 if( actionfreelist==0 ){
494 int i;
495 int amt = 100;
496 actionfreelist = (struct action *)calloc(amt, sizeof(struct action));
497 if( actionfreelist==0 ){
498 fprintf(stderr,"Unable to allocate memory for a new parser action.");
499 exit(1);
500 }
501 for(i=0; i<amt-1; i++) actionfreelist[i].next = &actionfreelist[i+1];
502 actionfreelist[amt-1].next = 0;
503 }
504 newaction = actionfreelist;
505 actionfreelist = actionfreelist->next;
506 return newaction;
507 }
508
509 /* Compare two actions for sorting purposes. Return negative, zero, or
510 ** positive if the first action is less than, equal to, or greater than
511 ** the first
512 */
actioncmp(struct action * ap1,struct action * ap2)513 static int actioncmp(
514 struct action *ap1,
515 struct action *ap2
516 ){
517 int rc;
518 rc = ap1->sp->index - ap2->sp->index;
519 if( rc==0 ){
520 rc = (int)ap1->type - (int)ap2->type;
521 }
522 if( rc==0 && (ap1->type==REDUCE || ap1->type==SHIFTREDUCE) ){
523 rc = ap1->x.rp->index - ap2->x.rp->index;
524 }
525 if( rc==0 ){
526 rc = (int) (ap2 - ap1);
527 }
528 return rc;
529 }
530
531 /* Sort parser actions */
Action_sort(struct action * ap)532 static struct action *Action_sort(
533 struct action *ap
534 ){
535 ap = (struct action *)msort((char *)ap,(char **)&ap->next,
536 (int(*)(const char*,const char*))actioncmp);
537 return ap;
538 }
539
Action_add(struct action ** app,enum e_action type,struct symbol * sp,char * arg)540 void Action_add(
541 struct action **app,
542 enum e_action type,
543 struct symbol *sp,
544 char *arg
545 ){
546 struct action *newaction;
547 newaction = Action_new();
548 newaction->next = *app;
549 *app = newaction;
550 newaction->type = type;
551 newaction->sp = sp;
552 newaction->spOpt = 0;
553 if( type==SHIFT ){
554 newaction->x.stp = (struct state *)arg;
555 }else{
556 newaction->x.rp = (struct rule *)arg;
557 }
558 }
559 /********************** New code to implement the "acttab" module ***********/
560 /*
561 ** This module implements routines use to construct the yy_action[] table.
562 */
563
564 /*
565 ** The state of the yy_action table under construction is an instance of
566 ** the following structure.
567 **
568 ** The yy_action table maps the pair (state_number, lookahead) into an
569 ** action_number. The table is an array of integers pairs. The state_number
570 ** determines an initial offset into the yy_action array. The lookahead
571 ** value is then added to this initial offset to get an index X into the
572 ** yy_action array. If the aAction[X].lookahead equals the value of the
573 ** of the lookahead input, then the value of the action_number output is
574 ** aAction[X].action. If the lookaheads do not match then the
575 ** default action for the state_number is returned.
576 **
577 ** All actions associated with a single state_number are first entered
578 ** into aLookahead[] using multiple calls to acttab_action(). Then the
579 ** actions for that single state_number are placed into the aAction[]
580 ** array with a single call to acttab_insert(). The acttab_insert() call
581 ** also resets the aLookahead[] array in preparation for the next
582 ** state number.
583 */
584 struct lookahead_action {
585 int lookahead; /* Value of the lookahead token */
586 int action; /* Action to take on the given lookahead */
587 };
588 typedef struct acttab acttab;
589 struct acttab {
590 int nAction; /* Number of used slots in aAction[] */
591 int nActionAlloc; /* Slots allocated for aAction[] */
592 struct lookahead_action
593 *aAction, /* The yy_action[] table under construction */
594 *aLookahead; /* A single new transaction set */
595 int mnLookahead; /* Minimum aLookahead[].lookahead */
596 int mnAction; /* Action associated with mnLookahead */
597 int mxLookahead; /* Maximum aLookahead[].lookahead */
598 int nLookahead; /* Used slots in aLookahead[] */
599 int nLookaheadAlloc; /* Slots allocated in aLookahead[] */
600 int nterminal; /* Number of terminal symbols */
601 int nsymbol; /* total number of symbols */
602 };
603
604 /* Return the number of entries in the yy_action table */
605 #define acttab_lookahead_size(X) ((X)->nAction)
606
607 /* The value for the N-th entry in yy_action */
608 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
609
610 /* The value for the N-th entry in yy_lookahead */
611 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
612
613 /* Free all memory associated with the given acttab */
acttab_free(acttab * p)614 void acttab_free(acttab *p){
615 free( p->aAction );
616 free( p->aLookahead );
617 free( p );
618 }
619
620 /* Allocate a new acttab structure */
acttab_alloc(int nsymbol,int nterminal)621 acttab *acttab_alloc(int nsymbol, int nterminal){
622 acttab *p = (acttab *) calloc( 1, sizeof(*p) );
623 if( p==0 ){
624 fprintf(stderr,"Unable to allocate memory for a new acttab.");
625 exit(1);
626 }
627 memset(p, 0, sizeof(*p));
628 p->nsymbol = nsymbol;
629 p->nterminal = nterminal;
630 return p;
631 }
632
633 /* Add a new action to the current transaction set.
634 **
635 ** This routine is called once for each lookahead for a particular
636 ** state.
637 */
acttab_action(acttab * p,int lookahead,int action)638 void acttab_action(acttab *p, int lookahead, int action){
639 if( p->nLookahead>=p->nLookaheadAlloc ){
640 p->nLookaheadAlloc += 25;
641 p->aLookahead = (struct lookahead_action *) realloc( p->aLookahead,
642 sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
643 if( p->aLookahead==0 ){
644 fprintf(stderr,"malloc failed\n");
645 exit(1);
646 }
647 }
648 if( p->nLookahead==0 ){
649 p->mxLookahead = lookahead;
650 p->mnLookahead = lookahead;
651 p->mnAction = action;
652 }else{
653 if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
654 if( p->mnLookahead>lookahead ){
655 p->mnLookahead = lookahead;
656 p->mnAction = action;
657 }
658 }
659 p->aLookahead[p->nLookahead].lookahead = lookahead;
660 p->aLookahead[p->nLookahead].action = action;
661 p->nLookahead++;
662 }
663
664 /*
665 ** Add the transaction set built up with prior calls to acttab_action()
666 ** into the current action table. Then reset the transaction set back
667 ** to an empty set in preparation for a new round of acttab_action() calls.
668 **
669 ** Return the offset into the action table of the new transaction.
670 **
671 ** If the makeItSafe parameter is true, then the offset is chosen so that
672 ** it is impossible to overread the yy_lookaside[] table regardless of
673 ** the lookaside token. This is done for the terminal symbols, as they
674 ** come from external inputs and can contain syntax errors. When makeItSafe
675 ** is false, there is more flexibility in selecting offsets, resulting in
676 ** a smaller table. For non-terminal symbols, which are never syntax errors,
677 ** makeItSafe can be false.
678 */
acttab_insert(acttab * p,int makeItSafe)679 int acttab_insert(acttab *p, int makeItSafe){
680 int i, j, k, n, end;
681 assert( p->nLookahead>0 );
682
683 /* Make sure we have enough space to hold the expanded action table
684 ** in the worst case. The worst case occurs if the transaction set
685 ** must be appended to the current action table
686 */
687 n = p->nsymbol + 1;
688 if( p->nAction + n >= p->nActionAlloc ){
689 int oldAlloc = p->nActionAlloc;
690 p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
691 p->aAction = (struct lookahead_action *) realloc( p->aAction,
692 sizeof(p->aAction[0])*p->nActionAlloc);
693 if( p->aAction==0 ){
694 fprintf(stderr,"malloc failed\n");
695 exit(1);
696 }
697 assert(oldAlloc < p->nActionAlloc); /* hint for CSA */
698 for(i=oldAlloc; i<p->nActionAlloc; i++){
699 p->aAction[i].lookahead = -1;
700 p->aAction[i].action = -1;
701 }
702 }
703 assert(p->aAction); /* Hint for CSA (for p->aAction[i] below) */
704
705 /* Scan the existing action table looking for an offset that is a
706 ** duplicate of the current transaction set. Fall out of the loop
707 ** if and when the duplicate is found.
708 **
709 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
710 */
711 end = makeItSafe ? p->mnLookahead : 0;
712 for(i=p->nAction-1; i>=end; i--){
713 if( p->aAction[i].lookahead==p->mnLookahead ){
714 /* All lookaheads and actions in the aLookahead[] transaction
715 ** must match against the candidate aAction[i] entry. */
716 if( p->aAction[i].action!=p->mnAction ) continue;
717 for(j=0; j<p->nLookahead; j++){
718 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
719 if( k<0 || k>=p->nAction ) break;
720 if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
721 if( p->aLookahead[j].action!=p->aAction[k].action ) break;
722 }
723 if( j<p->nLookahead ) continue;
724
725 /* No possible lookahead value that is not in the aLookahead[]
726 ** transaction is allowed to match aAction[i] */
727 n = 0;
728 for(j=0; j<p->nAction; j++){
729 if( p->aAction[j].lookahead<0 ) continue;
730 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
731 }
732 if( n==p->nLookahead ){
733 break; /* An exact match is found at offset i */
734 }
735 }
736 }
737
738 /* If no existing offsets exactly match the current transaction, find an
739 ** an empty offset in the aAction[] table in which we can add the
740 ** aLookahead[] transaction.
741 */
742 if( i<end ){
743 /* Look for holes in the aAction[] table that fit the current
744 ** aLookahead[] transaction. Leave i set to the offset of the hole.
745 ** If no holes are found, i is left at p->nAction, which means the
746 ** transaction will be appended. */
747 i = makeItSafe ? p->mnLookahead : 0;
748 for(; i<p->nActionAlloc - p->mxLookahead; i++){
749 if( p->aAction[i].lookahead<0 ){
750 for(j=0; j<p->nLookahead; j++){
751 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
752 if( k<0 ) break;
753 if( p->aAction[k].lookahead>=0 ) break;
754 }
755 if( j<p->nLookahead ) continue;
756 for(j=0; j<p->nAction; j++){
757 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
758 }
759 if( j==p->nAction ){
760 break; /* Fits in empty slots */
761 }
762 }
763 }
764 }
765 /* Insert transaction set at index i. */
766 #if 0
767 printf("Acttab:");
768 for(j=0; j<p->nLookahead; j++){
769 printf(" %d", p->aLookahead[j].lookahead);
770 }
771 printf(" inserted at %d\n", i);
772 #endif
773 for(j=0; j<p->nLookahead; j++){
774 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
775 p->aAction[k] = p->aLookahead[j];
776 if( k>=p->nAction ) p->nAction = k+1;
777 }
778 if( makeItSafe && i+p->nterminal>=p->nAction ) p->nAction = i+p->nterminal+1;
779 p->nLookahead = 0;
780
781 /* Return the offset that is added to the lookahead in order to get the
782 ** index into yy_action of the action */
783 return i - p->mnLookahead;
784 }
785
786 /*
787 ** Return the size of the action table without the trailing syntax error
788 ** entries.
789 */
acttab_action_size(acttab * p)790 int acttab_action_size(acttab *p){
791 int n = p->nAction;
792 while( n>0 && p->aAction[n-1].lookahead<0 ){ n--; }
793 return n;
794 }
795
796 /********************** From the file "build.c" *****************************/
797 /*
798 ** Routines to construction the finite state machine for the LEMON
799 ** parser generator.
800 */
801
802 /* Find a precedence symbol of every rule in the grammar.
803 **
804 ** Those rules which have a precedence symbol coded in the input
805 ** grammar using the "[symbol]" construct will already have the
806 ** rp->precsym field filled. Other rules take as their precedence
807 ** symbol the first RHS symbol with a defined precedence. If there
808 ** are not RHS symbols with a defined precedence, the precedence
809 ** symbol field is left blank.
810 */
FindRulePrecedences(struct lemon * xp)811 void FindRulePrecedences(struct lemon *xp)
812 {
813 struct rule *rp;
814 for(rp=xp->rule; rp; rp=rp->next){
815 if( rp->precsym==0 ){
816 int i, j;
817 for(i=0; i<rp->nrhs && rp->precsym==0; i++){
818 struct symbol *sp = rp->rhs[i];
819 if( sp->type==MULTITERMINAL ){
820 for(j=0; j<sp->nsubsym; j++){
821 if( sp->subsym[j]->prec>=0 ){
822 rp->precsym = sp->subsym[j];
823 break;
824 }
825 }
826 }else if( sp->prec>=0 ){
827 rp->precsym = rp->rhs[i];
828 }
829 }
830 }
831 }
832 return;
833 }
834
835 /* Find all nonterminals which will generate the empty string.
836 ** Then go back and compute the first sets of every nonterminal.
837 ** The first set is the set of all terminal symbols which can begin
838 ** a string generated by that nonterminal.
839 */
FindFirstSets(struct lemon * lemp)840 void FindFirstSets(struct lemon *lemp)
841 {
842 int i, j;
843 struct rule *rp;
844 int progress;
845
846 for(i=0; i<lemp->nsymbol; i++){
847 lemp->symbols[i]->lambda = LEMON_FALSE;
848 }
849 for(i=lemp->nterminal; i<lemp->nsymbol; i++){
850 lemp->symbols[i]->firstset = SetNew();
851 }
852
853 /* First compute all lambdas */
854 do{
855 progress = 0;
856 for(rp=lemp->rule; rp; rp=rp->next){
857 if( rp->lhs->lambda ) continue;
858 for(i=0; i<rp->nrhs; i++){
859 struct symbol *sp = rp->rhs[i];
860 assert( sp->type==NONTERMINAL || sp->lambda==LEMON_FALSE );
861 if( sp->lambda==LEMON_FALSE ) break;
862 }
863 if( i==rp->nrhs ){
864 rp->lhs->lambda = LEMON_TRUE;
865 progress = 1;
866 }
867 }
868 }while( progress );
869
870 /* Now compute all first sets */
871 do{
872 struct symbol *s1, *s2;
873 progress = 0;
874 for(rp=lemp->rule; rp; rp=rp->next){
875 s1 = rp->lhs;
876 for(i=0; i<rp->nrhs; i++){
877 s2 = rp->rhs[i];
878 if( s2->type==TERMINAL ){
879 progress += SetAdd(s1->firstset,s2->index);
880 break;
881 }else if( s2->type==MULTITERMINAL ){
882 for(j=0; j<s2->nsubsym; j++){
883 progress += SetAdd(s1->firstset,s2->subsym[j]->index);
884 }
885 break;
886 }else if( s1==s2 ){
887 if( s1->lambda==LEMON_FALSE ) break;
888 }else{
889 progress += SetUnion(s1->firstset,s2->firstset);
890 if( s2->lambda==LEMON_FALSE ) break;
891 }
892 }
893 }
894 }while( progress );
895 return;
896 }
897
898 /* Compute all LR(0) states for the grammar. Links
899 ** are added to between some states so that the LR(1) follow sets
900 ** can be computed later.
901 */
902 PRIVATE struct state *getstate(struct lemon *); /* forward reference */
FindStates(struct lemon * lemp)903 void FindStates(struct lemon *lemp)
904 {
905 struct symbol *sp;
906 struct rule *rp;
907
908 Configlist_init();
909
910 /* Find the start symbol */
911 if( lemp->start ){
912 sp = Symbol_find(lemp->start);
913 if( sp==0 ){
914 ErrorMsg(lemp->filename,0,
915 "The specified start symbol \"%s\" is not "
916 "in a nonterminal of the grammar. \"%s\" will be used as the start "
917 "symbol instead.",lemp->start,lemp->startRule->lhs->name);
918 lemp->errorcnt++;
919 sp = lemp->startRule->lhs;
920 }
921 }else{
922 sp = lemp->startRule->lhs;
923 }
924
925 /* Make sure the start symbol doesn't occur on the right-hand side of
926 ** any rule. Report an error if it does. (YACC would generate a new
927 ** start symbol in this case.) */
928 for(rp=lemp->rule; rp; rp=rp->next){
929 int i;
930 for(i=0; i<rp->nrhs; i++){
931 if( rp->rhs[i]==sp ){ /* FIX ME: Deal with multiterminals */
932 ErrorMsg(lemp->filename,0,
933 "The start symbol \"%s\" occurs on the "
934 "right-hand side of a rule. This will result in a parser which "
935 "does not work properly.",sp->name);
936 lemp->errorcnt++;
937 }
938 }
939 }
940
941 /* The basis configuration set for the first state
942 ** is all rules which have the start symbol as their
943 ** left-hand side */
944 for(rp=sp->rule; rp; rp=rp->nextlhs){
945 struct config *newcfp;
946 rp->lhsStart = 1;
947 newcfp = Configlist_addbasis(rp,0);
948 SetAdd(newcfp->fws,0);
949 }
950
951 /* Compute the first state. All other states will be
952 ** computed automatically during the computation of the first one.
953 ** The returned pointer to the first state is not used. */
954 (void)getstate(lemp);
955 return;
956 }
957
958 /* Return a pointer to a state which is described by the configuration
959 ** list which has been built from calls to Configlist_add.
960 */
961 PRIVATE void buildshifts(struct lemon *, struct state *); /* Forwd ref */
getstate(struct lemon * lemp)962 PRIVATE struct state *getstate(struct lemon *lemp)
963 {
964 struct config *cfp, *bp;
965 struct state *stp;
966
967 /* Extract the sorted basis of the new state. The basis was constructed
968 ** by prior calls to "Configlist_addbasis()". */
969 Configlist_sortbasis();
970 bp = Configlist_basis();
971
972 /* Get a state with the same basis */
973 stp = State_find(bp);
974 if( stp ){
975 /* A state with the same basis already exists! Copy all the follow-set
976 ** propagation links from the state under construction into the
977 ** preexisting state, then return a pointer to the preexisting state */
978 struct config *x, *y;
979 for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
980 Plink_copy(&y->bplp,x->bplp);
981 Plink_delete(x->fplp);
982 x->fplp = x->bplp = 0;
983 }
984 cfp = Configlist_return();
985 Configlist_eat(cfp);
986 }else{
987 /* This really is a new state. Construct all the details */
988 Configlist_closure(lemp); /* Compute the configuration closure */
989 Configlist_sort(); /* Sort the configuration closure */
990 cfp = Configlist_return(); /* Get a pointer to the config list */
991 stp = State_new(); /* A new state structure */
992 MemoryCheck(stp);
993 stp->bp = bp; /* Remember the configuration basis */
994 stp->cfp = cfp; /* Remember the configuration closure */
995 stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
996 stp->ap = 0; /* No actions, yet. */
997 #ifndef NDEBUG
998 int ret =
999 #endif
1000 State_insert(stp,stp->bp); /* Add to the state table */
1001 #ifndef NDEBUG
1002 assert(ret == 1); /* CSA hint: stp did not leak, it has escaped. */
1003 #endif
1004 buildshifts(lemp,stp); /* Recursively compute successor states */
1005 }
1006 return stp;
1007 }
1008
1009 /*
1010 ** Return true if two symbols are the same.
1011 */
same_symbol(struct symbol * a,struct symbol * b)1012 int same_symbol(struct symbol *a, struct symbol *b)
1013 {
1014 int i;
1015 if( a==b ) return 1;
1016 if( a->type!=MULTITERMINAL ) return 0;
1017 if( b->type!=MULTITERMINAL ) return 0;
1018 if( a->nsubsym!=b->nsubsym ) return 0;
1019 for(i=0; i<a->nsubsym; i++){
1020 if( a->subsym[i]!=b->subsym[i] ) return 0;
1021 }
1022 return 1;
1023 }
1024
1025 /* Construct all successor states to the given state. A "successor"
1026 ** state is any state which can be reached by a shift action.
1027 */
buildshifts(struct lemon * lemp,struct state * stp)1028 PRIVATE void buildshifts(struct lemon *lemp, struct state *stp)
1029 {
1030 struct config *cfp; /* For looping thru the config closure of "stp" */
1031 struct config *bcfp; /* For the inner loop on config closure of "stp" */
1032 struct config *newcfg; /* */
1033 struct symbol *sp; /* Symbol following the dot in configuration "cfp" */
1034 struct symbol *bsp; /* Symbol following the dot in configuration "bcfp" */
1035 struct state *newstp; /* A pointer to a successor state */
1036
1037 /* Each configuration becomes complete after it contibutes to a successor
1038 ** state. Initially, all configurations are incomplete */
1039 for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
1040
1041 /* Loop through all configurations of the state "stp" */
1042 for(cfp=stp->cfp; cfp; cfp=cfp->next){
1043 if( cfp->status==COMPLETE ) continue; /* Already used by inner loop */
1044 if( cfp->dot>=cfp->rp->nrhs ) continue; /* Can't shift this config */
1045 Configlist_reset(); /* Reset the new config set */
1046 sp = cfp->rp->rhs[cfp->dot]; /* Symbol after the dot */
1047
1048 /* For every configuration in the state "stp" which has the symbol "sp"
1049 ** following its dot, add the same configuration to the basis set under
1050 ** construction but with the dot shifted one symbol to the right. */
1051 for(bcfp=cfp; bcfp; bcfp=bcfp->next){
1052 if( bcfp->status==COMPLETE ) continue; /* Already used */
1053 if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
1054 bsp = bcfp->rp->rhs[bcfp->dot]; /* Get symbol after dot */
1055 if( !same_symbol(bsp,sp) ) continue; /* Must be same as for "cfp" */
1056 bcfp->status = COMPLETE; /* Mark this config as used */
1057 newcfg = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
1058 Plink_add(&newcfg->bplp,bcfp);
1059 }
1060
1061 /* Get a pointer to the state described by the basis configuration set
1062 ** constructed in the preceding loop */
1063 newstp = getstate(lemp);
1064
1065 /* The state "newstp" is reached from the state "stp" by a shift action
1066 ** on the symbol "sp" */
1067 if( sp->type==MULTITERMINAL ){
1068 int i;
1069 for(i=0; i<sp->nsubsym; i++){
1070 Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
1071 }
1072 }else{
1073 Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
1074 }
1075 }
1076 }
1077
1078 /*
1079 ** Construct the propagation links
1080 */
FindLinks(struct lemon * lemp)1081 void FindLinks(struct lemon *lemp)
1082 {
1083 int i;
1084 struct config *cfp, *other;
1085 struct state *stp;
1086 struct plink *plp;
1087
1088 /* Housekeeping detail:
1089 ** Add to every propagate link a pointer back to the state to
1090 ** which the link is attached. */
1091 for(i=0; i<lemp->nstate; i++){
1092 stp = lemp->sorted[i];
1093 assert(stp); /* Hint for CSA */
1094 for(cfp=stp->cfp; cfp; cfp=cfp->next){
1095 cfp->stp = stp;
1096 }
1097 }
1098
1099 /* Convert all backlinks into forward links. Only the forward
1100 ** links are used in the follow-set computation. */
1101 for(i=0; i<lemp->nstate; i++){
1102 stp = lemp->sorted[i];
1103 for(cfp=stp->cfp; cfp; cfp=cfp->next){
1104 for(plp=cfp->bplp; plp; plp=plp->next){
1105 other = plp->cfp;
1106 Plink_add(&other->fplp,cfp);
1107 }
1108 }
1109 }
1110 }
1111
1112 /* Compute all followsets.
1113 **
1114 ** A followset is the set of all symbols which can come immediately
1115 ** after a configuration.
1116 */
FindFollowSets(struct lemon * lemp)1117 void FindFollowSets(struct lemon *lemp)
1118 {
1119 int i;
1120 struct config *cfp;
1121 struct plink *plp;
1122 int progress;
1123 int change;
1124
1125 for(i=0; i<lemp->nstate; i++){
1126 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
1127 cfp->status = INCOMPLETE;
1128 }
1129 }
1130
1131 do{
1132 progress = 0;
1133 for(i=0; i<lemp->nstate; i++){
1134 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
1135 if( cfp->status==COMPLETE ) continue;
1136 for(plp=cfp->fplp; plp; plp=plp->next){
1137 change = SetUnion(plp->cfp->fws,cfp->fws);
1138 if( change ){
1139 plp->cfp->status = INCOMPLETE;
1140 progress = 1;
1141 }
1142 }
1143 cfp->status = COMPLETE;
1144 }
1145 }
1146 }while( progress );
1147 }
1148
1149 static int resolve_conflict(struct action *,struct action *);
1150
1151 /* Compute the reduce actions, and resolve conflicts.
1152 */
FindActions(struct lemon * lemp)1153 void FindActions(struct lemon *lemp)
1154 {
1155 int i,j;
1156 struct config *cfp;
1157 struct state *stp;
1158 struct symbol *sp;
1159 struct rule *rp;
1160
1161 /* Add all of the reduce actions
1162 ** A reduce action is added for each element of the followset of
1163 ** a configuration which has its dot at the extreme right.
1164 */
1165 for(i=0; i<lemp->nstate; i++){ /* Loop over all states */
1166 stp = lemp->sorted[i];
1167 for(cfp=stp->cfp; cfp; cfp=cfp->next){ /* Loop over all configurations */
1168 if( cfp->rp->nrhs==cfp->dot ){ /* Is dot at extreme right? */
1169 for(j=0; j<lemp->nterminal; j++){
1170 if( SetFind(cfp->fws,j) ){
1171 /* Add a reduce action to the state "stp" which will reduce by the
1172 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
1173 Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
1174 }
1175 }
1176 }
1177 }
1178 }
1179
1180 /* Add the accepting token */
1181 if( lemp->start ){
1182 sp = Symbol_find(lemp->start);
1183 if( sp==0 ) sp = lemp->startRule->lhs;
1184 }else{
1185 sp = lemp->startRule->lhs;
1186 }
1187 /* Add to the first state (which is always the starting state of the
1188 ** finite state machine) an action to ACCEPT if the lookahead is the
1189 ** start nonterminal. */
1190 Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
1191
1192 /* Resolve conflicts */
1193 for(i=0; i<lemp->nstate; i++){
1194 struct action *ap, *nap;
1195 stp = lemp->sorted[i];
1196 /* assert( stp->ap ); */
1197 stp->ap = Action_sort(stp->ap);
1198 for(ap=stp->ap; ap && ap->next; ap=ap->next){
1199 for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
1200 /* The two actions "ap" and "nap" have the same lookahead.
1201 ** Figure out which one should be used */
1202 lemp->nconflict += resolve_conflict(ap,nap);
1203 }
1204 }
1205 }
1206
1207 /* Report an error for each rule that can never be reduced. */
1208 for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;
1209 for(i=0; i<lemp->nstate; i++){
1210 struct action *ap;
1211 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
1212 if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;
1213 }
1214 }
1215 for(rp=lemp->rule; rp; rp=rp->next){
1216 if( rp->canReduce ) continue;
1217 ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
1218 lemp->errorcnt++;
1219 }
1220 }
1221
1222 /* Resolve a conflict between the two given actions. If the
1223 ** conflict can't be resolved, return non-zero.
1224 **
1225 ** NO LONGER TRUE:
1226 ** To resolve a conflict, first look to see if either action
1227 ** is on an error rule. In that case, take the action which
1228 ** is not associated with the error rule. If neither or both
1229 ** actions are associated with an error rule, then try to
1230 ** use precedence to resolve the conflict.
1231 **
1232 ** If either action is a SHIFT, then it must be apx. This
1233 ** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1234 */
resolve_conflict(struct action * apx,struct action * apy)1235 static int resolve_conflict(
1236 struct action *apx,
1237 struct action *apy
1238 ){
1239 struct symbol *spx, *spy;
1240 int errcnt = 0;
1241 assert( apx->sp==apy->sp ); /* Otherwise there would be no conflict */
1242 if( apx->type==SHIFT && apy->type==SHIFT ){
1243 apy->type = SSCONFLICT;
1244 errcnt++;
1245 }
1246 if( apx->type==SHIFT && apy->type==REDUCE ){
1247 spx = apx->sp;
1248 spy = apy->x.rp->precsym;
1249 if( spy==0 || spx->prec<0 || spy->prec<0 ){
1250 /* Not enough precedence information. */
1251 apy->type = SRCONFLICT;
1252 errcnt++;
1253 }else if( spx->prec>spy->prec ){ /* higher precedence wins */
1254 apy->type = RD_RESOLVED;
1255 }else if( spx->prec<spy->prec ){
1256 apx->type = SH_RESOLVED;
1257 }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
1258 apy->type = RD_RESOLVED; /* associativity */
1259 }else if( spx->prec==spy->prec && spx->assoc==LEFT ){ /* to break tie */
1260 apx->type = SH_RESOLVED;
1261 }else{
1262 assert( spx->prec==spy->prec && spx->assoc==NONE );
1263 apx->type = ERROR;
1264 }
1265 }else if( apx->type==REDUCE && apy->type==REDUCE ){
1266 spx = apx->x.rp->precsym;
1267 spy = apy->x.rp->precsym;
1268 if( spx==0 || spy==0 || spx->prec<0 ||
1269 spy->prec<0 || spx->prec==spy->prec ){
1270 apy->type = RRCONFLICT;
1271 errcnt++;
1272 }else if( spx->prec>spy->prec ){
1273 apy->type = RD_RESOLVED;
1274 }else if( spx->prec<spy->prec ){
1275 apx->type = RD_RESOLVED;
1276 }
1277 }else{
1278 assert(
1279 apx->type==SH_RESOLVED ||
1280 apx->type==RD_RESOLVED ||
1281 apx->type==SSCONFLICT ||
1282 apx->type==SRCONFLICT ||
1283 apx->type==RRCONFLICT ||
1284 apy->type==SH_RESOLVED ||
1285 apy->type==RD_RESOLVED ||
1286 apy->type==SSCONFLICT ||
1287 apy->type==SRCONFLICT ||
1288 apy->type==RRCONFLICT
1289 );
1290 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1291 ** REDUCEs on the list. If we reach this point it must be because
1292 ** the parser conflict had already been resolved. */
1293 }
1294 return errcnt;
1295 }
1296 /********************* From the file "configlist.c" *************************/
1297 /*
1298 ** Routines to processing a configuration list and building a state
1299 ** in the LEMON parser generator.
1300 */
1301
1302 static struct config *freelist = 0; /* List of free configurations */
1303 static struct config *current = 0; /* Top of list of configurations */
1304 static struct config **currentend = 0; /* Last on list of configs */
1305 static struct config *basis = 0; /* Top of list of basis configs */
1306 static struct config **basisend = 0; /* End of list of basis configs */
1307
1308 /* Return a pointer to a new configuration */
newconfig(void)1309 PRIVATE struct config *newconfig(void){
1310 struct config *newcfg;
1311 if( freelist==0 ){
1312 int i;
1313 int amt = 3;
1314 freelist = (struct config *)calloc( amt, sizeof(struct config) );
1315 if( freelist==0 ){
1316 fprintf(stderr,"Unable to allocate memory for a new configuration.");
1317 exit(1);
1318 }
1319 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
1320 freelist[amt-1].next = 0;
1321 }
1322 newcfg = freelist;
1323 freelist = freelist->next;
1324 return newcfg;
1325 }
1326
1327 /* The configuration "old" is no longer used */
deleteconfig(struct config * old)1328 PRIVATE void deleteconfig(struct config *old)
1329 {
1330 old->next = freelist;
1331 freelist = old;
1332 }
1333
1334 /* Initialized the configuration list builder */
Configlist_init(void)1335 void Configlist_init(void){
1336 current = 0;
1337 currentend = ¤t;
1338 basis = 0;
1339 basisend = &basis;
1340 Configtable_init();
1341 return;
1342 }
1343
1344 /* Initialized the configuration list builder */
Configlist_reset(void)1345 void Configlist_reset(void){
1346 current = 0;
1347 currentend = ¤t;
1348 basis = 0;
1349 basisend = &basis;
1350 Configtable_clear(0);
1351 return;
1352 }
1353
1354 /* Add another configuration to the configuration list */
Configlist_add(struct rule * rp,int dot)1355 struct config *Configlist_add(
1356 struct rule *rp, /* The rule */
1357 int dot /* Index into the RHS of the rule where the dot goes */
1358 ){
1359 struct config *cfp, model;
1360
1361 assert( currentend!=0 );
1362 model.rp = rp;
1363 model.dot = dot;
1364 cfp = Configtable_find(&model);
1365 if( cfp==0 ){
1366 cfp = newconfig();
1367 cfp->rp = rp;
1368 cfp->dot = dot;
1369 cfp->fws = SetNew();
1370 cfp->stp = 0;
1371 cfp->fplp = cfp->bplp = 0;
1372 cfp->next = 0;
1373 cfp->bp = 0;
1374 *currentend = cfp;
1375 currentend = &cfp->next;
1376 Configtable_insert(cfp);
1377 }
1378 return cfp;
1379 }
1380
1381 /* Add a basis configuration to the configuration list */
Configlist_addbasis(struct rule * rp,int dot)1382 struct config *Configlist_addbasis(struct rule *rp, int dot)
1383 {
1384 struct config *cfp, model;
1385
1386 assert( basisend!=0 );
1387 assert( currentend!=0 );
1388 model.rp = rp;
1389 model.dot = dot;
1390 cfp = Configtable_find(&model);
1391 if( cfp==0 ){
1392 cfp = newconfig();
1393 cfp->rp = rp;
1394 cfp->dot = dot;
1395 cfp->fws = SetNew();
1396 cfp->stp = 0;
1397 cfp->fplp = cfp->bplp = 0;
1398 cfp->next = 0;
1399 cfp->bp = 0;
1400 *currentend = cfp;
1401 currentend = &cfp->next;
1402 *basisend = cfp;
1403 basisend = &cfp->bp;
1404 Configtable_insert(cfp);
1405 }
1406 return cfp;
1407 }
1408
1409 /* Compute the closure of the configuration list */
Configlist_closure(struct lemon * lemp)1410 void Configlist_closure(struct lemon *lemp)
1411 {
1412 struct config *cfp, *newcfp;
1413 struct rule *rp, *newrp;
1414 struct symbol *sp, *xsp;
1415 int i, dot;
1416
1417 assert( currentend!=0 );
1418 for(cfp=current; cfp; cfp=cfp->next){
1419 rp = cfp->rp;
1420 dot = cfp->dot;
1421 if( dot>=rp->nrhs ) continue;
1422 sp = rp->rhs[dot];
1423 if( sp->type==NONTERMINAL ){
1424 if( sp->rule==0 && sp!=lemp->errsym ){
1425 ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",
1426 sp->name);
1427 lemp->errorcnt++;
1428 }
1429 for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
1430 newcfp = Configlist_add(newrp,0);
1431 for(i=dot+1; i<rp->nrhs; i++){
1432 xsp = rp->rhs[i];
1433 if( xsp->type==TERMINAL ){
1434 SetAdd(newcfp->fws,xsp->index);
1435 break;
1436 }else if( xsp->type==MULTITERMINAL ){
1437 int k;
1438 for(k=0; k<xsp->nsubsym; k++){
1439 SetAdd(newcfp->fws, xsp->subsym[k]->index);
1440 }
1441 break;
1442 }else{
1443 SetUnion(newcfp->fws,xsp->firstset);
1444 if( xsp->lambda==LEMON_FALSE ) break;
1445 }
1446 }
1447 if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);
1448 }
1449 }
1450 }
1451 return;
1452 }
1453
1454 /* Sort the configuration list */
Configlist_sort(void)1455 void Configlist_sort(void){
1456 current = (struct config*)msort((char*)current,(char**)&(current->next),
1457 Configcmp);
1458 currentend = 0;
1459 return;
1460 }
1461
1462 /* Sort the basis configuration list */
Configlist_sortbasis(void)1463 void Configlist_sortbasis(void){
1464 basis = (struct config*)msort((char*)current,(char**)&(current->bp),
1465 Configcmp);
1466 basisend = 0;
1467 return;
1468 }
1469
1470 /* Return a pointer to the head of the configuration list and
1471 ** reset the list */
Configlist_return(void)1472 struct config *Configlist_return(void){
1473 struct config *old;
1474 old = current;
1475 current = 0;
1476 currentend = 0;
1477 return old;
1478 }
1479
1480 /* Return a pointer to the head of the configuration list and
1481 ** reset the list */
Configlist_basis(void)1482 struct config *Configlist_basis(void){
1483 struct config *old;
1484 old = basis;
1485 basis = 0;
1486 basisend = 0;
1487 return old;
1488 }
1489
1490 /* Free all elements of the given configuration list */
Configlist_eat(struct config * cfp)1491 void Configlist_eat(struct config *cfp)
1492 {
1493 struct config *nextcfp;
1494 for(; cfp; cfp=nextcfp){
1495 nextcfp = cfp->next;
1496 assert( cfp->fplp==0 );
1497 assert( cfp->bplp==0 );
1498 if( cfp->fws ) SetFree(cfp->fws);
1499 deleteconfig(cfp);
1500 }
1501 return;
1502 }
1503 /***************** From the file "error.c" *********************************/
1504 /*
1505 ** Code for printing error message.
1506 */
1507
ErrorMsg(const char * filename,int lineno,const char * format,...)1508 void ErrorMsg(const char *filename, int lineno, const char *format, ...){
1509 va_list ap;
1510 fprintf(stderr, "%s:%d: ", filename, lineno);
1511 va_start(ap, format);
1512 vfprintf(stderr,format,ap);
1513 va_end(ap);
1514 fprintf(stderr, "\n");
1515 }
1516 /**************** From the file "main.c" ************************************/
1517 /*
1518 ** Main program file for the LEMON parser generator.
1519 */
1520
1521 /* Report an out-of-memory condition and abort. This function
1522 ** is used mostly by the "MemoryCheck" macro in struct.h
1523 */
memory_error(void)1524 void memory_error(void){
1525 fprintf(stderr,"Out of memory. Aborting...\n");
1526 exit(1);
1527 }
1528
1529 static int nDefine = 0; /* Number of -D options on the command line */
1530 static char **azDefine = 0; /* Name of the -D macros */
1531
1532 /* This routine is called with the argument to each -D command-line option.
1533 ** Add the macro defined to the azDefine array.
1534 */
handle_D_option(char * z)1535 static void handle_D_option(char *z){
1536 char **paz;
1537 nDefine++;
1538 azDefine = (char **) realloc(azDefine, sizeof(azDefine[0])*nDefine);
1539 if( azDefine==0 ){
1540 fprintf(stderr,"out of memory\n");
1541 exit(1);
1542 }
1543 paz = &azDefine[nDefine-1];
1544 *paz = (char *) malloc( lemonStrlen(z)+1 );
1545 if( *paz==0 ){
1546 fprintf(stderr,"out of memory\n");
1547 exit(1);
1548 }
1549 lemon_strcpy(*paz, z);
1550 for(z=*paz; *z && *z!='='; z++){}
1551 *z = 0;
1552 }
1553
1554 /* Rember the name of the output directory
1555 */
1556 static char *outputDir = NULL;
handle_d_option(char * z)1557 static void handle_d_option(char *z){
1558 outputDir = (char *) malloc( lemonStrlen(z)+1 );
1559 if( outputDir==0 ){
1560 fprintf(stderr,"out of memory\n");
1561 exit(1);
1562 }
1563 lemon_strcpy(outputDir, z);
1564 }
1565
1566 static char *user_templatename = NULL;
handle_T_option(char * z)1567 static void handle_T_option(char *z){
1568 user_templatename = (char *) malloc( lemonStrlen(z)+1 );
1569 if( user_templatename==0 ){
1570 memory_error();
1571 }
1572 lemon_strcpy(user_templatename, z);
1573 }
1574
1575 /* Merge together to lists of rules ordered by rule.iRule */
Rule_merge(struct rule * pA,struct rule * pB)1576 static struct rule *Rule_merge(struct rule *pA, struct rule *pB){
1577 struct rule *pFirst = 0;
1578 struct rule **ppPrev = &pFirst;
1579 while( pA && pB ){
1580 if( pA->iRule<pB->iRule ){
1581 *ppPrev = pA;
1582 ppPrev = &pA->next;
1583 pA = pA->next;
1584 }else{
1585 *ppPrev = pB;
1586 ppPrev = &pB->next;
1587 pB = pB->next;
1588 }
1589 }
1590 if( pA ){
1591 *ppPrev = pA;
1592 }else{
1593 *ppPrev = pB;
1594 }
1595 return pFirst;
1596 }
1597
1598 /*
1599 ** Sort a list of rules in order of increasing iRule value
1600 */
Rule_sort(struct rule * rp)1601 static struct rule *Rule_sort(struct rule *rp){
1602 unsigned int i;
1603 struct rule *pNext;
1604 struct rule *x[32];
1605 memset(x, 0, sizeof(x));
1606 while( rp ){
1607 pNext = rp->next;
1608 rp->next = 0;
1609 for(i=0; i<sizeof(x)/sizeof(x[0])-1 && x[i]; i++){
1610 rp = Rule_merge(x[i], rp);
1611 x[i] = 0;
1612 }
1613 x[i] = rp;
1614 rp = pNext;
1615 }
1616 rp = 0;
1617 for(i=0; i<sizeof(x)/sizeof(x[0]); i++){
1618 rp = Rule_merge(x[i], rp);
1619 }
1620 return rp;
1621 }
1622
1623 /* forward reference */
1624 static const char *minimum_size_type(int lwr, int upr, int *pnByte);
1625
1626 /* Print a single line of the "Parser Stats" output
1627 */
stats_line(const char * zLabel,int iValue)1628 static void stats_line(const char *zLabel, int iValue){
1629 int nLabel = lemonStrlen(zLabel);
1630 printf(" %s%.*s %5d\n", zLabel,
1631 35-nLabel, "................................",
1632 iValue);
1633 }
1634
1635 /* The main program. Parse the command line and do it... */
main(int argc,char ** argv)1636 int main(int argc, char **argv){
1637 static int version = 0;
1638 static int rpflag = 0;
1639 static int basisflag = 0;
1640 static int compress = 0;
1641 static int quiet = 0;
1642 static int statistics = 0;
1643 static int mhflag = 0;
1644 static int nolinenosflag = 0;
1645 static int noResort = 0;
1646 static int sqlFlag = 0;
1647 static int printPP = 0;
1648
1649 static struct s_options options[] = {
1650 {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
1651 {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
1652 {OPT_FSTR, "d", (char*)&handle_d_option, "Output directory. Default '.'"},
1653 {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
1654 {OPT_FLAG, "E", (char*)&printPP, "Print input file after preprocessing."},
1655 {OPT_FSTR, "f", 0, "Ignored. (Placeholder for -f compiler options.)"},
1656 {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
1657 {OPT_FSTR, "I", 0, "Ignored. (Placeholder for '-I' compiler options.)"},
1658 {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file."},
1659 {OPT_FLAG, "l", (char*)&nolinenosflag, "Do not print #line statements."},
1660 {OPT_FSTR, "O", 0, "Ignored. (Placeholder for '-O' compiler options.)"},
1661 {OPT_FLAG, "p", (char*)&showPrecedenceConflict,
1662 "Show conflicts resolved by precedence rules"},
1663 {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
1664 {OPT_FLAG, "r", (char*)&noResort, "Do not sort or renumber states"},
1665 {OPT_FLAG, "s", (char*)&statistics,
1666 "Print parser stats to standard output."},
1667 {OPT_FLAG, "S", (char*)&sqlFlag,
1668 "Generate the *.sql file describing the parser tables."},
1669 {OPT_FLAG, "x", (char*)&version, "Print the version number."},
1670 {OPT_FSTR, "T", (char*)handle_T_option, "Specify a template file."},
1671 {OPT_FSTR, "W", 0, "Ignored. (Placeholder for '-W' compiler options.)"},
1672 {OPT_FLAG,0,0,0}
1673 };
1674 int i;
1675 int exitcode;
1676 struct lemon lem;
1677 struct rule *rp;
1678
1679 (void)argc;
1680 OptInit(argv,options,stderr);
1681 if( version ){
1682 printf("Lemon version 1.0\n");
1683 exit(0);
1684 }
1685 if( OptNArgs()!=1 ){
1686 fprintf(stderr,"Exactly one filename argument is required.\n");
1687 exit(1);
1688 }
1689 memset(&lem, 0, sizeof(lem));
1690 lem.errorcnt = 0;
1691
1692 /* Initialize the machine */
1693 Strsafe_init();
1694 Symbol_init();
1695 State_init();
1696 lem.argv0 = argv[0];
1697 lem.filename = OptArg(0);
1698 lem.basisflag = basisflag;
1699 lem.nolinenosflag = nolinenosflag;
1700 lem.printPreprocessed = printPP;
1701 Symbol_new("$");
1702
1703 /* Parse the input file */
1704 Parse(&lem);
1705 if( lem.printPreprocessed || lem.errorcnt ) exit(lem.errorcnt);
1706 assert(lem.rule); /* Hint for CSA (no errors => rule found). */
1707 if( lem.nrule==0 ){
1708 fprintf(stderr,"Empty grammar.\n");
1709 exit(1);
1710 }
1711 lem.errsym = Symbol_find("error");
1712
1713 /* Count and index the symbols of the grammar */
1714 Symbol_new("{default}");
1715 lem.nsymbol = Symbol_count();
1716 lem.symbols = Symbol_arrayof();
1717 for(i=0; i<lem.nsymbol; i++) lem.symbols[i]->index = i;
1718 qsort(lem.symbols,lem.nsymbol,sizeof(struct symbol*), Symbolcmpp);
1719 for(i=0; i<lem.nsymbol; i++) lem.symbols[i]->index = i;
1720 while( lem.symbols[i-1]->type==MULTITERMINAL ){ i--; }
1721 assert( strcmp(lem.symbols[i-1]->name,"{default}")==0 );
1722 lem.nsymbol = i - 1;
1723 for(i=1; ISUPPER(lem.symbols[i]->name[0]); i++);
1724 lem.nterminal = i;
1725
1726 /* Assign sequential rule numbers. Start with 0. Put rules that have no
1727 ** reduce action C-code associated with them last, so that the switch()
1728 ** statement that selects reduction actions will have a smaller jump table.
1729 */
1730 for(i=0, rp=lem.rule; rp; rp=rp->next){
1731 rp->iRule = rp->code ? i++ : -1;
1732 }
1733 lem.nruleWithAction = i;
1734 for(rp=lem.rule; rp; rp=rp->next){
1735 if( rp->iRule<0 ) rp->iRule = i++;
1736 }
1737 lem.startRule = lem.rule;
1738 lem.rule = Rule_sort(lem.rule);
1739
1740 /* Generate a reprint of the grammar, if requested on the command line */
1741 if( rpflag ){
1742 Reprint(&lem);
1743 }else{
1744 /* Initialize the size for all follow and first sets */
1745 SetSize(lem.nterminal+1);
1746
1747 /* Find the precedence for every production rule (that has one) */
1748 FindRulePrecedences(&lem);
1749
1750 /* Compute the lambda-nonterminals and the first-sets for every
1751 ** nonterminal */
1752 FindFirstSets(&lem);
1753
1754 /* Compute all LR(0) states. Also record follow-set propagation
1755 ** links so that the follow-set can be computed later */
1756 lem.nstate = 0;
1757 FindStates(&lem);
1758 lem.sorted = State_arrayof();
1759
1760 /* Tie up loose ends on the propagation links */
1761 FindLinks(&lem);
1762
1763 /* Compute the follow set of every reducible configuration */
1764 FindFollowSets(&lem);
1765
1766 /* Compute the action tables */
1767 FindActions(&lem);
1768
1769 /* Compress the action tables */
1770 if( compress==0 ) CompressTables(&lem);
1771
1772 /* Reorder and renumber the states so that states with fewer choices
1773 ** occur at the end. This is an optimization that helps make the
1774 ** generated parser tables smaller. */
1775 if( noResort==0 ) ResortStates(&lem);
1776
1777 /* Generate a report of the parser generated. (the "y.output" file) */
1778 if( !quiet ) ReportOutput(&lem);
1779
1780 /* Generate the source code for the parser */
1781 ReportTable(&lem, mhflag, sqlFlag);
1782
1783 /* Produce a header file for use by the scanner. (This step is
1784 ** omitted if the "-m" option is used because makeheaders will
1785 ** generate the file for us.) */
1786 if( !mhflag ) ReportHeader(&lem);
1787 }
1788 if( statistics ){
1789 printf("Parser statistics:\n");
1790 stats_line("terminal symbols", lem.nterminal);
1791 stats_line("non-terminal symbols", lem.nsymbol - lem.nterminal);
1792 stats_line("total symbols", lem.nsymbol);
1793 stats_line("rules", lem.nrule);
1794 stats_line("states", lem.nxstate);
1795 stats_line("conflicts", lem.nconflict);
1796 stats_line("action table entries", lem.nactiontab);
1797 stats_line("lookahead table entries", lem.nlookaheadtab);
1798 stats_line("total table size (bytes)", lem.tablesize);
1799 }
1800 if( lem.nconflict > 0 ){
1801 fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
1802 }
1803
1804 /* return 0 on success, 1 on failure. */
1805 exitcode = ((lem.errorcnt > 0) || (lem.nconflict > 0)) ? 1 : 0;
1806 exit(exitcode);
1807 return (exitcode);
1808 }
1809 /******************** From the file "msort.c" *******************************/
1810 /*
1811 ** A generic merge-sort program.
1812 **
1813 ** USAGE:
1814 ** Let "ptr" be a pointer to some structure which is at the head of
1815 ** a null-terminated list. Then to sort the list call:
1816 **
1817 ** ptr = msort(ptr,&(ptr->next),cmpfnc);
1818 **
1819 ** In the above, "cmpfnc" is a pointer to a function which compares
1820 ** two instances of the structure and returns an integer, as in
1821 ** strcmp. The second argument is a pointer to the pointer to the
1822 ** second element of the linked list. This address is used to compute
1823 ** the offset to the "next" field within the structure. The offset to
1824 ** the "next" field must be constant for all structures in the list.
1825 **
1826 ** The function returns a new pointer which is the head of the list
1827 ** after sorting.
1828 **
1829 ** ALGORITHM:
1830 ** Merge-sort.
1831 */
1832
1833 /*
1834 ** Return a pointer to the next structure in the linked list.
1835 */
1836 #define NEXT(A) (*(char**)(((char*)A)+offset))
1837
1838 /*
1839 ** Inputs:
1840 ** a: A sorted, null-terminated linked list. (May be null).
1841 ** b: A sorted, null-terminated linked list. (May be null).
1842 ** cmp: A pointer to the comparison function.
1843 ** offset: Offset in the structure to the "next" field.
1844 **
1845 ** Return Value:
1846 ** A pointer to the head of a sorted list containing the elements
1847 ** of both a and b.
1848 **
1849 ** Side effects:
1850 ** The "next" pointers for elements in the lists a and b are
1851 ** changed.
1852 */
merge(char * a,char * b,int (* cmp)(const char *,const char *),int offset)1853 static char *merge(
1854 char *a,
1855 char *b,
1856 int (*cmp)(const char*,const char*),
1857 int offset
1858 ){
1859 char *ptr, *head;
1860
1861 if( a==0 ){
1862 head = b;
1863 }else if( b==0 ){
1864 head = a;
1865 }else{
1866 if( (*cmp)(a,b)<=0 ){
1867 ptr = a;
1868 a = NEXT(a);
1869 }else{
1870 ptr = b;
1871 b = NEXT(b);
1872 }
1873 head = ptr;
1874 while( a && b ){
1875 if( (*cmp)(a,b)<=0 ){
1876 NEXT(ptr) = a;
1877 ptr = a;
1878 a = NEXT(a);
1879 }else{
1880 NEXT(ptr) = b;
1881 ptr = b;
1882 b = NEXT(b);
1883 }
1884 }
1885 if( a ) NEXT(ptr) = a;
1886 else NEXT(ptr) = b;
1887 }
1888 return head;
1889 }
1890
1891 /*
1892 ** Inputs:
1893 ** list: Pointer to a singly-linked list of structures.
1894 ** next: Pointer to pointer to the second element of the list.
1895 ** cmp: A comparison function.
1896 **
1897 ** Return Value:
1898 ** A pointer to the head of a sorted list containing the elements
1899 ** orginally in list.
1900 **
1901 ** Side effects:
1902 ** The "next" pointers for elements in list are changed.
1903 */
1904 #define LISTSIZE 30
msort(char * list,char ** next,int (* cmp)(const char *,const char *))1905 static char *msort(
1906 char *list,
1907 char **next,
1908 int (*cmp)(const char*,const char*)
1909 ){
1910 unsigned long offset;
1911 char *ep;
1912 char *set[LISTSIZE];
1913 int i;
1914 offset = (unsigned long)((char*)next - (char*)list);
1915 for(i=0; i<LISTSIZE; i++) set[i] = 0;
1916 while( list ){
1917 ep = list;
1918 list = NEXT(list);
1919 NEXT(ep) = 0;
1920 for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
1921 ep = merge(ep,set[i],cmp,offset);
1922 set[i] = 0;
1923 }
1924 set[i] = ep;
1925 }
1926 ep = 0;
1927 for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(set[i],ep,cmp,offset);
1928 return ep;
1929 }
1930 /************************ From the file "option.c" **************************/
1931 static char **g_argv;
1932 static struct s_options *op;
1933 static FILE *errstream;
1934
1935 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1936
1937 /*
1938 ** Print the command line with a carrot pointing to the k-th character
1939 ** of the n-th field.
1940 */
errline(int n,int k,FILE * err)1941 static void errline(int n, int k, FILE *err)
1942 {
1943 int spcnt, i;
1944 if( g_argv[0] ) fprintf(err,"%s",g_argv[0]);
1945 spcnt = lemonStrlen(g_argv[0]) + 1;
1946 for(i=1; i<n && g_argv[i]; i++){
1947 fprintf(err," %s",g_argv[i]);
1948 spcnt += lemonStrlen(g_argv[i])+1;
1949 }
1950 spcnt += k;
1951 for(; g_argv[i]; i++) fprintf(err," %s",g_argv[i]);
1952 if( spcnt<20 ){
1953 fprintf(err,"\n%*s^-- here\n",spcnt,"");
1954 }else{
1955 fprintf(err,"\n%*shere --^\n",spcnt-7,"");
1956 }
1957 }
1958
1959 /*
1960 ** Return the index of the N-th non-switch argument. Return -1
1961 ** if N is out of range.
1962 */
argindex(int n)1963 static int argindex(int n)
1964 {
1965 int i;
1966 int dashdash = 0;
1967 if( g_argv!=0 && *g_argv!=0 ){
1968 for(i=1; g_argv[i]; i++){
1969 if( dashdash || !ISOPT(g_argv[i]) ){
1970 if( n==0 ) return i;
1971 n--;
1972 }
1973 if( strcmp(g_argv[i],"--")==0 ) dashdash = 1;
1974 }
1975 }
1976 return -1;
1977 }
1978
1979 static char emsg[] = "Command line syntax error: ";
1980
1981 /*
1982 ** Process a flag command line argument.
1983 */
handleflags(int i,FILE * err)1984 static int handleflags(int i, FILE *err)
1985 {
1986 int v;
1987 int errcnt = 0;
1988 int j;
1989 for(j=0; op[j].label; j++){
1990 if( strncmp(&g_argv[i][1],op[j].label,lemonStrlen(op[j].label))==0 ) break;
1991 }
1992 v = g_argv[i][0]=='-' ? 1 : 0;
1993 if( op[j].label==0 ){
1994 if( err ){
1995 fprintf(err,"%sundefined option.\n",emsg);
1996 errline(i,1,err);
1997 }
1998 errcnt++;
1999 }else if( op[j].arg==0 ){
2000 /* Ignore this option */
2001 }else if( op[j].type==OPT_FLAG ){
2002 *((int*)op[j].arg) = v;
2003 }else if( op[j].type==OPT_FFLAG ){
2004 (*(void(*)(int))(op[j].arg))(v);
2005 }else if( op[j].type==OPT_FSTR ){
2006 (*(void(*)(char *))(op[j].arg))(&g_argv[i][2]);
2007 }else{
2008 if( err ){
2009 fprintf(err,"%smissing argument on switch.\n",emsg);
2010 errline(i,1,err);
2011 }
2012 errcnt++;
2013 }
2014 return errcnt;
2015 }
2016
2017 /*
2018 ** Process a command line switch which has an argument.
2019 */
handleswitch(int i,FILE * err)2020 static int handleswitch(int i, FILE *err)
2021 {
2022 int lv = 0;
2023 double dv = 0.0;
2024 char *sv = 0, *end;
2025 char *cp;
2026 int j;
2027 int errcnt = 0;
2028 cp = strchr(g_argv[i],'=');
2029 assert( cp!=0 );
2030 *cp = 0;
2031 for(j=0; op[j].label; j++){
2032 if( strcmp(g_argv[i],op[j].label)==0 ) break;
2033 }
2034 *cp = '=';
2035 if( op[j].label==0 ){
2036 if( err ){
2037 fprintf(err,"%sundefined option.\n",emsg);
2038 errline(i,0,err);
2039 }
2040 errcnt++;
2041 }else{
2042 cp++;
2043 switch( op[j].type ){
2044 case OPT_FLAG:
2045 case OPT_FFLAG:
2046 if( err ){
2047 fprintf(err,"%soption requires an argument.\n",emsg);
2048 errline(i,0,err);
2049 }
2050 errcnt++;
2051 break;
2052 case OPT_DBL:
2053 case OPT_FDBL:
2054 dv = strtod(cp,&end);
2055 if( *end ){
2056 if( err ){
2057 fprintf(err,
2058 "%sillegal character in floating-point argument.\n",emsg);
2059 errline(i,(int)((char*)end-(char*)g_argv[i]),err);
2060 }
2061 errcnt++;
2062 }
2063 break;
2064 case OPT_INT:
2065 case OPT_FINT:
2066 lv = strtol(cp,&end,0);
2067 if( *end ){
2068 if( err ){
2069 fprintf(err,"%sillegal character in integer argument.\n",emsg);
2070 errline(i,(int)((char*)end-(char*)g_argv[i]),err);
2071 }
2072 errcnt++;
2073 }
2074 break;
2075 case OPT_STR:
2076 case OPT_FSTR:
2077 sv = cp;
2078 break;
2079 }
2080 switch( op[j].type ){
2081 case OPT_FLAG:
2082 case OPT_FFLAG:
2083 break;
2084 case OPT_DBL:
2085 *(double*)(op[j].arg) = dv;
2086 break;
2087 case OPT_FDBL:
2088 (*(void(*)(double))(op[j].arg))(dv);
2089 break;
2090 case OPT_INT:
2091 *(int*)(op[j].arg) = lv;
2092 break;
2093 case OPT_FINT:
2094 (*(void(*)(int))(op[j].arg))((int)lv);
2095 break;
2096 case OPT_STR:
2097 *(char**)(op[j].arg) = sv;
2098 break;
2099 case OPT_FSTR:
2100 (*(void(*)(char *))(op[j].arg))(sv);
2101 break;
2102 }
2103 }
2104 return errcnt;
2105 }
2106
OptInit(char ** a,struct s_options * o,FILE * err)2107 int OptInit(char **a, struct s_options *o, FILE *err)
2108 {
2109 int errcnt = 0;
2110 g_argv = a;
2111 op = o;
2112 errstream = err;
2113 if( g_argv && *g_argv && op ){
2114 int i;
2115 for(i=1; g_argv[i]; i++){
2116 if( g_argv[i][0]=='+' || g_argv[i][0]=='-' ){
2117 errcnt += handleflags(i,err);
2118 }else if( strchr(g_argv[i],'=') ){
2119 errcnt += handleswitch(i,err);
2120 }
2121 }
2122 }
2123 if( errcnt>0 ){
2124 fprintf(err,"Valid command line options for \"%s\" are:\n",*a);
2125 OptPrint();
2126 exit(1);
2127 }
2128 return 0;
2129 }
2130
OptNArgs(void)2131 int OptNArgs(void){
2132 int cnt = 0;
2133 int dashdash = 0;
2134 int i;
2135 if( g_argv!=0 && g_argv[0]!=0 ){
2136 for(i=1; g_argv[i]; i++){
2137 if( dashdash || !ISOPT(g_argv[i]) ) cnt++;
2138 if( strcmp(g_argv[i],"--")==0 ) dashdash = 1;
2139 }
2140 }
2141 return cnt;
2142 }
2143
OptArg(int n)2144 char *OptArg(int n)
2145 {
2146 int i;
2147 i = argindex(n);
2148 return i>=0 ? g_argv[i] : 0;
2149 }
2150
OptErr(int n)2151 void OptErr(int n)
2152 {
2153 int i;
2154 i = argindex(n);
2155 if( i>=0 ) errline(i,0,errstream);
2156 }
2157
OptPrint(void)2158 void OptPrint(void){
2159 int i;
2160 int max, len;
2161 max = 0;
2162 for(i=0; op[i].label; i++){
2163 len = lemonStrlen(op[i].label) + 1;
2164 switch( op[i].type ){
2165 case OPT_FLAG:
2166 case OPT_FFLAG:
2167 break;
2168 case OPT_INT:
2169 case OPT_FINT:
2170 len += 9; /* length of "<integer>" */
2171 break;
2172 case OPT_DBL:
2173 case OPT_FDBL:
2174 len += 6; /* length of "<real>" */
2175 break;
2176 case OPT_STR:
2177 case OPT_FSTR:
2178 len += 8; /* length of "<string>" */
2179 break;
2180 }
2181 if( len>max ) max = len;
2182 }
2183 for(i=0; op[i].label; i++){
2184 switch( op[i].type ){
2185 case OPT_FLAG:
2186 case OPT_FFLAG:
2187 fprintf(errstream," -%-*s %s\n",max,op[i].label,op[i].message);
2188 break;
2189 case OPT_INT:
2190 case OPT_FINT:
2191 fprintf(errstream," -%s<integer>%*s %s\n",op[i].label,
2192 (int)(max-lemonStrlen(op[i].label)-9),"",op[i].message);
2193 break;
2194 case OPT_DBL:
2195 case OPT_FDBL:
2196 fprintf(errstream," -%s<real>%*s %s\n",op[i].label,
2197 (int)(max-lemonStrlen(op[i].label)-6),"",op[i].message);
2198 break;
2199 case OPT_STR:
2200 case OPT_FSTR:
2201 fprintf(errstream," -%s<string>%*s %s\n",op[i].label,
2202 (int)(max-lemonStrlen(op[i].label)-8),"",op[i].message);
2203 break;
2204 }
2205 }
2206 }
2207 /*********************** From the file "parse.c" ****************************/
2208 /*
2209 ** Input file parser for the LEMON parser generator.
2210 */
2211
2212 /* The state of the parser */
2213 enum e_state {
2214 INITIALIZE,
2215 WAITING_FOR_DECL_OR_RULE,
2216 WAITING_FOR_DECL_KEYWORD,
2217 WAITING_FOR_DECL_ARG,
2218 WAITING_FOR_PRECEDENCE_SYMBOL,
2219 WAITING_FOR_ARROW,
2220 IN_RHS,
2221 LHS_ALIAS_1,
2222 LHS_ALIAS_2,
2223 LHS_ALIAS_3,
2224 RHS_ALIAS_1,
2225 RHS_ALIAS_2,
2226 PRECEDENCE_MARK_1,
2227 PRECEDENCE_MARK_2,
2228 RESYNC_AFTER_RULE_ERROR,
2229 RESYNC_AFTER_DECL_ERROR,
2230 WAITING_FOR_DESTRUCTOR_SYMBOL,
2231 WAITING_FOR_DATATYPE_SYMBOL,
2232 WAITING_FOR_FALLBACK_ID,
2233 WAITING_FOR_WILDCARD_ID,
2234 WAITING_FOR_CLASS_ID,
2235 WAITING_FOR_CLASS_TOKEN,
2236 WAITING_FOR_TOKEN_NAME
2237 };
2238 struct pstate {
2239 char *filename; /* Name of the input file */
2240 int tokenlineno; /* Linenumber at which current token starts */
2241 int errorcnt; /* Number of errors so far */
2242 char *tokenstart; /* Text of current token */
2243 struct lemon *gp; /* Global state vector */
2244 enum e_state state; /* The state of the parser */
2245 struct symbol *fallback; /* The fallback token */
2246 struct symbol *tkclass; /* Token class symbol */
2247 struct symbol *lhs; /* Left-hand side of current rule */
2248 const char *lhsalias; /* Alias for the LHS */
2249 int nrhs; /* Number of right-hand side symbols seen */
2250 struct symbol *rhs[MAXRHS]; /* RHS symbols */
2251 const char *alias[MAXRHS]; /* Aliases for each RHS symbol (or NULL) */
2252 struct rule *prevrule; /* Previous rule parsed */
2253 const char *declkeyword; /* Keyword of a declaration */
2254 char **declargslot; /* Where the declaration argument should be put */
2255 int insertLineMacro; /* Add #line before declaration insert */
2256 int *decllinenoslot; /* Where to write declaration line number */
2257 enum e_assoc declassoc; /* Assign this association to decl arguments */
2258 int preccounter; /* Assign this precedence to decl arguments */
2259 struct rule *firstrule; /* Pointer to first rule in the grammar */
2260 struct rule *lastrule; /* Pointer to the most recently parsed rule */
2261 };
2262
2263 /* Parse a single token */
parseonetoken(struct pstate * psp)2264 static void parseonetoken(struct pstate *psp)
2265 {
2266 const char *x;
2267 x = Strsafe(psp->tokenstart); /* Save the token permanently */
2268 #if 0
2269 printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
2270 x,psp->state);
2271 #endif
2272 switch( psp->state ){
2273 case INITIALIZE:
2274 psp->prevrule = 0;
2275 psp->preccounter = 0;
2276 psp->firstrule = psp->lastrule = 0;
2277 psp->gp->nrule = 0;
2278 /* fall through */
2279 case WAITING_FOR_DECL_OR_RULE:
2280 if( x[0]=='%' ){
2281 psp->state = WAITING_FOR_DECL_KEYWORD;
2282 }else if( ISLOWER(x[0]) ){
2283 psp->lhs = Symbol_new(x);
2284 psp->nrhs = 0;
2285 psp->lhsalias = 0;
2286 psp->state = WAITING_FOR_ARROW;
2287 }else if( x[0]=='{' ){
2288 if( psp->prevrule==0 ){
2289 ErrorMsg(psp->filename,psp->tokenlineno,
2290 "There is no prior rule upon which to attach the code "
2291 "fragment which begins on this line.");
2292 psp->errorcnt++;
2293 }else if( psp->prevrule->code!=0 ){
2294 ErrorMsg(psp->filename,psp->tokenlineno,
2295 "Code fragment beginning on this line is not the first "
2296 "to follow the previous rule.");
2297 psp->errorcnt++;
2298 }else if( strcmp(x, "{NEVER-REDUCE")==0 ){
2299 psp->prevrule->neverReduce = 1;
2300 }else{
2301 psp->prevrule->line = psp->tokenlineno;
2302 psp->prevrule->code = &x[1];
2303 psp->prevrule->noCode = 0;
2304 }
2305 }else if( x[0]=='[' ){
2306 psp->state = PRECEDENCE_MARK_1;
2307 }else{
2308 ErrorMsg(psp->filename,psp->tokenlineno,
2309 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2310 x);
2311 psp->errorcnt++;
2312 }
2313 break;
2314 case PRECEDENCE_MARK_1:
2315 if( !ISUPPER(x[0]) ){
2316 ErrorMsg(psp->filename,psp->tokenlineno,
2317 "The precedence symbol must be a terminal.");
2318 psp->errorcnt++;
2319 }else if( psp->prevrule==0 ){
2320 ErrorMsg(psp->filename,psp->tokenlineno,
2321 "There is no prior rule to assign precedence \"[%s]\".",x);
2322 psp->errorcnt++;
2323 }else if( psp->prevrule->precsym!=0 ){
2324 ErrorMsg(psp->filename,psp->tokenlineno,
2325 "Precedence mark on this line is not the first "
2326 "to follow the previous rule.");
2327 psp->errorcnt++;
2328 }else{
2329 psp->prevrule->precsym = Symbol_new(x);
2330 }
2331 psp->state = PRECEDENCE_MARK_2;
2332 break;
2333 case PRECEDENCE_MARK_2:
2334 if( x[0]!=']' ){
2335 ErrorMsg(psp->filename,psp->tokenlineno,
2336 "Missing \"]\" on precedence mark.");
2337 psp->errorcnt++;
2338 }
2339 psp->state = WAITING_FOR_DECL_OR_RULE;
2340 break;
2341 case WAITING_FOR_ARROW:
2342 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2343 psp->state = IN_RHS;
2344 }else if( x[0]=='(' ){
2345 psp->state = LHS_ALIAS_1;
2346 }else{
2347 ErrorMsg(psp->filename,psp->tokenlineno,
2348 "Expected to see a \":\" following the LHS symbol \"%s\".",
2349 psp->lhs->name);
2350 psp->errorcnt++;
2351 psp->state = RESYNC_AFTER_RULE_ERROR;
2352 }
2353 break;
2354 case LHS_ALIAS_1:
2355 if( ISALPHA(x[0]) ){
2356 psp->lhsalias = x;
2357 psp->state = LHS_ALIAS_2;
2358 }else{
2359 ErrorMsg(psp->filename,psp->tokenlineno,
2360 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2361 x,psp->lhs->name);
2362 psp->errorcnt++;
2363 psp->state = RESYNC_AFTER_RULE_ERROR;
2364 }
2365 break;
2366 case LHS_ALIAS_2:
2367 if( x[0]==')' ){
2368 psp->state = LHS_ALIAS_3;
2369 }else{
2370 ErrorMsg(psp->filename,psp->tokenlineno,
2371 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2372 psp->errorcnt++;
2373 psp->state = RESYNC_AFTER_RULE_ERROR;
2374 }
2375 break;
2376 case LHS_ALIAS_3:
2377 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2378 psp->state = IN_RHS;
2379 }else{
2380 ErrorMsg(psp->filename,psp->tokenlineno,
2381 "Missing \"->\" following: \"%s(%s)\".",
2382 psp->lhs->name,psp->lhsalias);
2383 psp->errorcnt++;
2384 psp->state = RESYNC_AFTER_RULE_ERROR;
2385 }
2386 break;
2387 case IN_RHS:
2388 if( x[0]=='.' ){
2389 struct rule *rp;
2390 rp = (struct rule *)calloc( sizeof(struct rule) +
2391 sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs, 1);
2392 if( rp==0 ){
2393 ErrorMsg(psp->filename,psp->tokenlineno,
2394 "Can't allocate enough memory for this rule.");
2395 psp->errorcnt++;
2396 psp->prevrule = 0;
2397 }else{
2398 int i;
2399 rp->ruleline = psp->tokenlineno;
2400 rp->rhs = (struct symbol**)&rp[1];
2401 rp->rhsalias = (const char**)&(rp->rhs[psp->nrhs]);
2402 for(i=0; i<psp->nrhs; i++){
2403 rp->rhs[i] = psp->rhs[i];
2404 rp->rhsalias[i] = psp->alias[i];
2405 if( rp->rhsalias[i]!=0 ){ rp->rhs[i]->bContent = 1; }
2406 }
2407 rp->lhs = psp->lhs;
2408 rp->lhsalias = psp->lhsalias;
2409 rp->nrhs = psp->nrhs;
2410 rp->code = 0;
2411 rp->noCode = 1;
2412 rp->precsym = 0;
2413 rp->index = psp->gp->nrule++;
2414 rp->nextlhs = rp->lhs->rule;
2415 rp->lhs->rule = rp;
2416 rp->next = 0;
2417 if( psp->firstrule==0 ){
2418 psp->firstrule = psp->lastrule = rp;
2419 }else{
2420 psp->lastrule->next = rp;
2421 psp->lastrule = rp;
2422 }
2423 psp->prevrule = rp;
2424 }
2425 psp->state = WAITING_FOR_DECL_OR_RULE;
2426 }else if( ISALPHA(x[0]) ){
2427 if( psp->nrhs>=MAXRHS ){
2428 ErrorMsg(psp->filename,psp->tokenlineno,
2429 "Too many symbols on RHS of rule beginning at \"%s\".",
2430 x);
2431 psp->errorcnt++;
2432 psp->state = RESYNC_AFTER_RULE_ERROR;
2433 }else{
2434 psp->rhs[psp->nrhs] = Symbol_new(x);
2435 psp->alias[psp->nrhs] = 0;
2436 psp->nrhs++;
2437 }
2438 }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 && ISUPPER(x[1]) ){
2439 struct symbol *msp = psp->rhs[psp->nrhs-1];
2440 if( msp->type!=MULTITERMINAL ){
2441 struct symbol *origsp = msp;
2442 msp = (struct symbol *) calloc(1,sizeof(*msp));
2443 memset(msp, 0, sizeof(*msp));
2444 msp->type = MULTITERMINAL;
2445 msp->nsubsym = 1;
2446 msp->subsym = (struct symbol **) calloc(1,sizeof(struct symbol*));
2447 msp->subsym[0] = origsp;
2448 msp->name = origsp->name;
2449 psp->rhs[psp->nrhs-1] = msp;
2450 }
2451 msp->nsubsym++;
2452 msp->subsym = (struct symbol **) realloc(msp->subsym,
2453 sizeof(struct symbol*)*msp->nsubsym);
2454 msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);
2455 if( ISLOWER(x[1]) || ISLOWER(msp->subsym[0]->name[0]) ){
2456 ErrorMsg(psp->filename,psp->tokenlineno,
2457 "Cannot form a compound containing a non-terminal");
2458 psp->errorcnt++;
2459 }
2460 }else if( x[0]=='(' && psp->nrhs>0 ){
2461 psp->state = RHS_ALIAS_1;
2462 }else{
2463 ErrorMsg(psp->filename,psp->tokenlineno,
2464 "Illegal character on RHS of rule: \"%s\".",x);
2465 psp->errorcnt++;
2466 psp->state = RESYNC_AFTER_RULE_ERROR;
2467 }
2468 break;
2469 case RHS_ALIAS_1:
2470 if( ISALPHA(x[0]) ){
2471 psp->alias[psp->nrhs-1] = x;
2472 psp->state = RHS_ALIAS_2;
2473 }else{
2474 ErrorMsg(psp->filename,psp->tokenlineno,
2475 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2476 x,psp->rhs[psp->nrhs-1]->name);
2477 psp->errorcnt++;
2478 psp->state = RESYNC_AFTER_RULE_ERROR;
2479 }
2480 break;
2481 case RHS_ALIAS_2:
2482 if( x[0]==')' ){
2483 psp->state = IN_RHS;
2484 }else{
2485 ErrorMsg(psp->filename,psp->tokenlineno,
2486 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2487 psp->errorcnt++;
2488 psp->state = RESYNC_AFTER_RULE_ERROR;
2489 }
2490 break;
2491 case WAITING_FOR_DECL_KEYWORD:
2492 if( ISALPHA(x[0]) ){
2493 psp->declkeyword = x;
2494 psp->declargslot = 0;
2495 psp->decllinenoslot = 0;
2496 psp->insertLineMacro = 1;
2497 psp->state = WAITING_FOR_DECL_ARG;
2498 if( strcmp(x,"name")==0 ){
2499 psp->declargslot = &(psp->gp->name);
2500 psp->insertLineMacro = 0;
2501 }else if( strcmp(x,"include")==0 ){
2502 psp->declargslot = &(psp->gp->include);
2503 }else if( strcmp(x,"code")==0 ){
2504 psp->declargslot = &(psp->gp->extracode);
2505 }else if( strcmp(x,"token_destructor")==0 ){
2506 psp->declargslot = &psp->gp->tokendest;
2507 }else if( strcmp(x,"default_destructor")==0 ){
2508 psp->declargslot = &psp->gp->vardest;
2509 }else if( strcmp(x,"token_prefix")==0 ){
2510 psp->declargslot = &psp->gp->tokenprefix;
2511 psp->insertLineMacro = 0;
2512 }else if( strcmp(x,"syntax_error")==0 ){
2513 psp->declargslot = &(psp->gp->error);
2514 }else if( strcmp(x,"parse_accept")==0 ){
2515 psp->declargslot = &(psp->gp->accept);
2516 }else if( strcmp(x,"parse_failure")==0 ){
2517 psp->declargslot = &(psp->gp->failure);
2518 }else if( strcmp(x,"stack_overflow")==0 ){
2519 psp->declargslot = &(psp->gp->overflow);
2520 }else if( strcmp(x,"extra_argument")==0 ){
2521 psp->declargslot = &(psp->gp->arg);
2522 psp->insertLineMacro = 0;
2523 }else if( strcmp(x,"extra_context")==0 ){
2524 psp->declargslot = &(psp->gp->ctx);
2525 psp->insertLineMacro = 0;
2526 }else if( strcmp(x,"token_type")==0 ){
2527 psp->declargslot = &(psp->gp->tokentype);
2528 psp->insertLineMacro = 0;
2529 }else if( strcmp(x,"default_type")==0 ){
2530 psp->declargslot = &(psp->gp->vartype);
2531 psp->insertLineMacro = 0;
2532 }else if( strcmp(x,"stack_size")==0 ){
2533 psp->declargslot = &(psp->gp->stacksize);
2534 psp->insertLineMacro = 0;
2535 }else if( strcmp(x,"start_symbol")==0 ){
2536 psp->declargslot = &(psp->gp->start);
2537 psp->insertLineMacro = 0;
2538 }else if( strcmp(x,"left")==0 ){
2539 psp->preccounter++;
2540 psp->declassoc = LEFT;
2541 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2542 }else if( strcmp(x,"right")==0 ){
2543 psp->preccounter++;
2544 psp->declassoc = RIGHT;
2545 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2546 }else if( strcmp(x,"nonassoc")==0 ){
2547 psp->preccounter++;
2548 psp->declassoc = NONE;
2549 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2550 }else if( strcmp(x,"destructor")==0 ){
2551 psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;
2552 }else if( strcmp(x,"type")==0 ){
2553 psp->state = WAITING_FOR_DATATYPE_SYMBOL;
2554 }else if( strcmp(x,"fallback")==0 ){
2555 psp->fallback = 0;
2556 psp->state = WAITING_FOR_FALLBACK_ID;
2557 }else if( strcmp(x,"token")==0 ){
2558 psp->state = WAITING_FOR_TOKEN_NAME;
2559 }else if( strcmp(x,"wildcard")==0 ){
2560 psp->state = WAITING_FOR_WILDCARD_ID;
2561 }else if( strcmp(x,"token_class")==0 ){
2562 psp->state = WAITING_FOR_CLASS_ID;
2563 }else{
2564 ErrorMsg(psp->filename,psp->tokenlineno,
2565 "Unknown declaration keyword: \"%%%s\".",x);
2566 psp->errorcnt++;
2567 psp->state = RESYNC_AFTER_DECL_ERROR;
2568 }
2569 }else{
2570 ErrorMsg(psp->filename,psp->tokenlineno,
2571 "Illegal declaration keyword: \"%s\".",x);
2572 psp->errorcnt++;
2573 psp->state = RESYNC_AFTER_DECL_ERROR;
2574 }
2575 break;
2576 case WAITING_FOR_DESTRUCTOR_SYMBOL:
2577 if( !ISALPHA(x[0]) ){
2578 ErrorMsg(psp->filename,psp->tokenlineno,
2579 "Symbol name missing after %%destructor keyword");
2580 psp->errorcnt++;
2581 psp->state = RESYNC_AFTER_DECL_ERROR;
2582 }else{
2583 struct symbol *sp = Symbol_new(x);
2584 psp->declargslot = &sp->destructor;
2585 psp->decllinenoslot = &sp->destLineno;
2586 psp->insertLineMacro = 1;
2587 psp->state = WAITING_FOR_DECL_ARG;
2588 }
2589 break;
2590 case WAITING_FOR_DATATYPE_SYMBOL:
2591 if( !ISALPHA(x[0]) ){
2592 ErrorMsg(psp->filename,psp->tokenlineno,
2593 "Symbol name missing after %%type keyword");
2594 psp->errorcnt++;
2595 psp->state = RESYNC_AFTER_DECL_ERROR;
2596 }else{
2597 struct symbol *sp = Symbol_find(x);
2598 if((sp) && (sp->datatype)){
2599 ErrorMsg(psp->filename,psp->tokenlineno,
2600 "Symbol %%type \"%s\" already defined", x);
2601 psp->errorcnt++;
2602 psp->state = RESYNC_AFTER_DECL_ERROR;
2603 }else{
2604 if (!sp){
2605 sp = Symbol_new(x);
2606 }
2607 psp->declargslot = &sp->datatype;
2608 psp->insertLineMacro = 0;
2609 psp->state = WAITING_FOR_DECL_ARG;
2610 }
2611 }
2612 break;
2613 case WAITING_FOR_PRECEDENCE_SYMBOL:
2614 if( x[0]=='.' ){
2615 psp->state = WAITING_FOR_DECL_OR_RULE;
2616 }else if( ISUPPER(x[0]) ){
2617 struct symbol *sp;
2618 sp = Symbol_new(x);
2619 if( sp->prec>=0 ){
2620 ErrorMsg(psp->filename,psp->tokenlineno,
2621 "Symbol \"%s\" has already be given a precedence.",x);
2622 psp->errorcnt++;
2623 }else{
2624 sp->prec = psp->preccounter;
2625 sp->assoc = psp->declassoc;
2626 }
2627 }else{
2628 ErrorMsg(psp->filename,psp->tokenlineno,
2629 "Can't assign a precedence to \"%s\".",x);
2630 psp->errorcnt++;
2631 }
2632 break;
2633 case WAITING_FOR_DECL_ARG:
2634 if( x[0]=='{' || x[0]=='\"' || ISALNUM(x[0]) ){
2635 const char *zOld, *zNew;
2636 char *zBuf, *z;
2637 int nOld, n, nLine = 0, nNew, nBack;
2638 int addLineMacro;
2639 char zLine[50];
2640 zNew = x;
2641 if( zNew[0]=='"' || zNew[0]=='{' ) zNew++;
2642 nNew = lemonStrlen(zNew);
2643 if( *psp->declargslot ){
2644 zOld = *psp->declargslot;
2645 }else{
2646 zOld = "";
2647 }
2648 nOld = lemonStrlen(zOld);
2649 n = nOld + nNew + 20;
2650 addLineMacro = !psp->gp->nolinenosflag
2651 && psp->insertLineMacro
2652 && psp->tokenlineno>1
2653 && (psp->decllinenoslot==0 || psp->decllinenoslot[0]!=0);
2654 if( addLineMacro ){
2655 for(z=psp->filename, nBack=0; *z; z++){
2656 if( *z=='\\' ) nBack++;
2657 }
2658 lemon_sprintf(zLine, "#line %d ", psp->tokenlineno);
2659 nLine = lemonStrlen(zLine);
2660 n += nLine + lemonStrlen(psp->filename) + nBack;
2661 }
2662 *psp->declargslot = (char *) realloc(*psp->declargslot, n);
2663 zBuf = *psp->declargslot + nOld;
2664 if( addLineMacro ){
2665 if( nOld && zBuf[-1]!='\n' ){
2666 *(zBuf++) = '\n';
2667 }
2668 memcpy(zBuf, zLine, nLine);
2669 zBuf += nLine;
2670 *(zBuf++) = '"';
2671 for(z=psp->filename; *z; z++){
2672 if( *z=='\\' ){
2673 *(zBuf++) = '\\';
2674 }
2675 *(zBuf++) = *z;
2676 }
2677 *(zBuf++) = '"';
2678 *(zBuf++) = '\n';
2679 }
2680 if( psp->decllinenoslot && psp->decllinenoslot[0]==0 ){
2681 psp->decllinenoslot[0] = psp->tokenlineno;
2682 }
2683 memcpy(zBuf, zNew, nNew);
2684 zBuf += nNew;
2685 *zBuf = 0;
2686 psp->state = WAITING_FOR_DECL_OR_RULE;
2687 }else{
2688 ErrorMsg(psp->filename,psp->tokenlineno,
2689 "Illegal argument to %%%s: %s",psp->declkeyword,x);
2690 psp->errorcnt++;
2691 psp->state = RESYNC_AFTER_DECL_ERROR;
2692 }
2693 break;
2694 case WAITING_FOR_FALLBACK_ID:
2695 if( x[0]=='.' ){
2696 psp->state = WAITING_FOR_DECL_OR_RULE;
2697 }else if( !ISUPPER(x[0]) ){
2698 ErrorMsg(psp->filename, psp->tokenlineno,
2699 "%%fallback argument \"%s\" should be a token", x);
2700 psp->errorcnt++;
2701 }else{
2702 struct symbol *sp = Symbol_new(x);
2703 if( psp->fallback==0 ){
2704 psp->fallback = sp;
2705 }else if( sp->fallback ){
2706 ErrorMsg(psp->filename, psp->tokenlineno,
2707 "More than one fallback assigned to token %s", x);
2708 psp->errorcnt++;
2709 }else{
2710 sp->fallback = psp->fallback;
2711 psp->gp->has_fallback = 1;
2712 }
2713 }
2714 break;
2715 case WAITING_FOR_TOKEN_NAME:
2716 /* Tokens do not have to be declared before use. But they can be
2717 ** in order to control their assigned integer number. The number for
2718 ** each token is assigned when it is first seen. So by including
2719 **
2720 ** %token ONE TWO THREE
2721 **
2722 ** early in the grammar file, that assigns small consecutive values
2723 ** to each of the tokens ONE TWO and THREE.
2724 */
2725 if( x[0]=='.' ){
2726 psp->state = WAITING_FOR_DECL_OR_RULE;
2727 }else if( !ISUPPER(x[0]) ){
2728 ErrorMsg(psp->filename, psp->tokenlineno,
2729 "%%token argument \"%s\" should be a token", x);
2730 psp->errorcnt++;
2731 }else{
2732 (void)Symbol_new(x);
2733 }
2734 break;
2735 case WAITING_FOR_WILDCARD_ID:
2736 if( x[0]=='.' ){
2737 psp->state = WAITING_FOR_DECL_OR_RULE;
2738 }else if( !ISUPPER(x[0]) ){
2739 ErrorMsg(psp->filename, psp->tokenlineno,
2740 "%%wildcard argument \"%s\" should be a token", x);
2741 psp->errorcnt++;
2742 }else{
2743 struct symbol *sp = Symbol_new(x);
2744 if( psp->gp->wildcard==0 ){
2745 psp->gp->wildcard = sp;
2746 }else{
2747 ErrorMsg(psp->filename, psp->tokenlineno,
2748 "Extra wildcard to token: %s", x);
2749 psp->errorcnt++;
2750 }
2751 }
2752 break;
2753 case WAITING_FOR_CLASS_ID:
2754 if( !ISLOWER(x[0]) ){
2755 ErrorMsg(psp->filename, psp->tokenlineno,
2756 "%%token_class must be followed by an identifier: %s", x);
2757 psp->errorcnt++;
2758 psp->state = RESYNC_AFTER_DECL_ERROR;
2759 }else if( Symbol_find(x) ){
2760 ErrorMsg(psp->filename, psp->tokenlineno,
2761 "Symbol \"%s\" already used", x);
2762 psp->errorcnt++;
2763 psp->state = RESYNC_AFTER_DECL_ERROR;
2764 }else{
2765 psp->tkclass = Symbol_new(x);
2766 psp->tkclass->type = MULTITERMINAL;
2767 psp->state = WAITING_FOR_CLASS_TOKEN;
2768 }
2769 break;
2770 case WAITING_FOR_CLASS_TOKEN:
2771 if( x[0]=='.' ){
2772 psp->state = WAITING_FOR_DECL_OR_RULE;
2773 }else if( ISUPPER(x[0]) || ((x[0]=='|' || x[0]=='/') && ISUPPER(x[1])) ){
2774 struct symbol *msp = psp->tkclass;
2775 msp->nsubsym++;
2776 msp->subsym = (struct symbol **) realloc(msp->subsym,
2777 sizeof(struct symbol*)*msp->nsubsym);
2778 if( !ISUPPER(x[0]) ) x++;
2779 msp->subsym[msp->nsubsym-1] = Symbol_new(x);
2780 }else{
2781 ErrorMsg(psp->filename, psp->tokenlineno,
2782 "%%token_class argument \"%s\" should be a token", x);
2783 psp->errorcnt++;
2784 psp->state = RESYNC_AFTER_DECL_ERROR;
2785 }
2786 break;
2787 case RESYNC_AFTER_RULE_ERROR:
2788 /* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2789 ** break; */
2790 case RESYNC_AFTER_DECL_ERROR:
2791 if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2792 if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;
2793 break;
2794 }
2795 }
2796
2797 /* The text in the input is part of the argument to an %ifdef or %ifndef.
2798 ** Evaluate the text as a boolean expression. Return true or false.
2799 */
eval_preprocessor_boolean(char * z,int lineno)2800 static int eval_preprocessor_boolean(char *z, int lineno){
2801 int neg = 0;
2802 int res = 0;
2803 int okTerm = 1;
2804 int i;
2805 for(i=0; z[i]!=0; i++){
2806 if( ISSPACE(z[i]) ) continue;
2807 if( z[i]=='!' ){
2808 if( !okTerm ) goto pp_syntax_error;
2809 neg = !neg;
2810 continue;
2811 }
2812 if( z[i]=='|' && z[i+1]=='|' ){
2813 if( okTerm ) goto pp_syntax_error;
2814 if( res ) return 1;
2815 i++;
2816 okTerm = 1;
2817 continue;
2818 }
2819 if( z[i]=='&' && z[i+1]=='&' ){
2820 if( okTerm ) goto pp_syntax_error;
2821 if( !res ) return 0;
2822 i++;
2823 okTerm = 1;
2824 continue;
2825 }
2826 if( z[i]=='(' ){
2827 int k;
2828 int n = 1;
2829 if( !okTerm ) goto pp_syntax_error;
2830 for(k=i+1; z[k]; k++){
2831 if( z[k]==')' ){
2832 n--;
2833 if( n==0 ){
2834 z[k] = 0;
2835 res = eval_preprocessor_boolean(&z[i+1], -1);
2836 z[k] = ')';
2837 if( res<0 ){
2838 i = i-res;
2839 goto pp_syntax_error;
2840 }
2841 i = k;
2842 break;
2843 }
2844 }else if( z[k]=='(' ){
2845 n++;
2846 }else if( z[k]==0 ){
2847 i = k;
2848 goto pp_syntax_error;
2849 }
2850 }
2851 if( neg ){
2852 res = !res;
2853 neg = 0;
2854 }
2855 okTerm = 0;
2856 continue;
2857 }
2858 if( ISALPHA(z[i]) ){
2859 int j, k, n;
2860 if( !okTerm ) goto pp_syntax_error;
2861 for(k=i+1; ISALNUM(z[k]) || z[k]=='_'; k++){}
2862 n = k - i;
2863 res = 0;
2864 for(j=0; j<nDefine; j++){
2865 if( strncmp(azDefine[j],&z[i],n)==0 && azDefine[j][n]==0 ){
2866 res = 1;
2867 break;
2868 }
2869 }
2870 i = k-1;
2871 if( neg ){
2872 res = !res;
2873 neg = 0;
2874 }
2875 okTerm = 0;
2876 continue;
2877 }
2878 goto pp_syntax_error;
2879 }
2880 return res;
2881
2882 pp_syntax_error:
2883 if( lineno>0 ){
2884 fprintf(stderr, "%%if syntax error on line %d.\n", lineno);
2885 fprintf(stderr, " %.*s <-- syntax error here\n", i+1, z);
2886 exit(1);
2887 }else{
2888 return -(i+1);
2889 }
2890 }
2891
2892 /* Run the preprocessor over the input file text. The global variables
2893 ** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2894 ** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2895 ** comments them out. Text in between is also commented out as appropriate.
2896 */
preprocess_input(char * z)2897 static void preprocess_input(char *z){
2898 int i, j, k;
2899 int exclude = 0;
2900 int start = 0;
2901 int lineno = 1;
2902 int start_lineno = 1;
2903 for(i=0; z[i]; i++){
2904 if( z[i]=='\n' ) lineno++;
2905 if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue;
2906 if( strncmp(&z[i],"%endif",6)==0 && ISSPACE(z[i+6]) ){
2907 if( exclude ){
2908 exclude--;
2909 if( exclude==0 ){
2910 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';
2911 }
2912 }
2913 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2914 }else if( strncmp(&z[i],"%else",5)==0 && ISSPACE(z[i+5]) ){
2915 if( exclude==1){
2916 exclude = 0;
2917 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';
2918 }else if( exclude==0 ){
2919 exclude = 1;
2920 start = i;
2921 start_lineno = lineno;
2922 }
2923 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2924 }else if( strncmp(&z[i],"%ifdef ",7)==0
2925 || strncmp(&z[i],"%if ",4)==0
2926 || strncmp(&z[i],"%ifndef ",8)==0 ){
2927 if( exclude ){
2928 exclude++;
2929 }else{
2930 int isNot;
2931 int iBool;
2932 for(j=i; z[j] && !ISSPACE(z[j]); j++){}
2933 iBool = j;
2934 isNot = (j==i+7);
2935 while( z[j] && z[j]!='\n' ){ j++; }
2936 k = z[j];
2937 z[j] = 0;
2938 exclude = eval_preprocessor_boolean(&z[iBool], lineno);
2939 z[j] = k;
2940 if( !isNot ) exclude = !exclude;
2941 if( exclude ){
2942 start = i;
2943 start_lineno = lineno;
2944 }
2945 }
2946 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2947 }
2948 }
2949 if( exclude ){
2950 fprintf(stderr,"unterminated %%ifdef starting on line %d\n", start_lineno);
2951 exit(1);
2952 }
2953 }
2954
2955 /* In spite of its name, this function is really a scanner. It read
2956 ** in the entire input file (all at once) then tokenizes it. Each
2957 ** token is passed to the function "parseonetoken" which builds all
2958 ** the appropriate data structures in the global state vector "gp".
2959 */
Parse(struct lemon * gp)2960 void Parse(struct lemon *gp)
2961 {
2962 struct pstate ps;
2963 FILE *fp;
2964 char *filebuf;
2965 unsigned int filesize;
2966 int lineno;
2967 int c;
2968 char *cp, *nextcp;
2969 int startline = 0;
2970
2971 memset(&ps, '\0', sizeof(ps));
2972 ps.gp = gp;
2973 ps.filename = gp->filename;
2974 ps.errorcnt = 0;
2975 ps.state = INITIALIZE;
2976
2977 /* Begin by reading the input file */
2978 fp = fopen(ps.filename,"rb");
2979 if( fp==0 ){
2980 ErrorMsg(ps.filename,0,"Can't open this file for reading.");
2981 gp->errorcnt++;
2982 return;
2983 }
2984 fseek(fp,0,2);
2985 filesize = ftell(fp);
2986 rewind(fp);
2987 filebuf = (char *)malloc( filesize+1 );
2988 if( filesize>100000000 || filebuf==0 ){
2989 ErrorMsg(ps.filename,0,"Input file too large.");
2990 free(filebuf);
2991 gp->errorcnt++;
2992 fclose(fp);
2993 return;
2994 }
2995 if( fread(filebuf,1,filesize,fp)!=filesize ){
2996 ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",
2997 filesize);
2998 free(filebuf);
2999 gp->errorcnt++;
3000 fclose(fp);
3001 return;
3002 }
3003 fclose(fp);
3004 filebuf[filesize] = 0;
3005
3006 /* Make an initial pass through the file to handle %ifdef and %ifndef */
3007 preprocess_input(filebuf);
3008 if( gp->printPreprocessed ){
3009 printf("%s\n", filebuf);
3010 return;
3011 }
3012
3013 /* Now scan the text of the input file */
3014 lineno = 1;
3015 for(cp=filebuf; (c= *cp)!=0; ){
3016 if( c=='\n' ) lineno++; /* Keep track of the line number */
3017 if( ISSPACE(c) ){ cp++; continue; } /* Skip all white space */
3018 if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments */
3019 cp+=2;
3020 while( (c= *cp)!=0 && c!='\n' ) cp++;
3021 continue;
3022 }
3023 if( c=='/' && cp[1]=='*' ){ /* Skip C style comments */
3024 cp+=2;
3025 while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){
3026 if( c=='\n' ) lineno++;
3027 cp++;
3028 }
3029 if( c ) cp++;
3030 continue;
3031 }
3032 ps.tokenstart = cp; /* Mark the beginning of the token */
3033 ps.tokenlineno = lineno; /* Linenumber on which token begins */
3034 if( c=='\"' ){ /* String literals */
3035 cp++;
3036 while( (c= *cp)!=0 && c!='\"' ){
3037 if( c=='\n' ) lineno++;
3038 cp++;
3039 }
3040 if( c==0 ){
3041 ErrorMsg(ps.filename,startline,
3042 "String starting on this line is not terminated before "
3043 "the end of the file.");
3044 ps.errorcnt++;
3045 nextcp = cp;
3046 }else{
3047 nextcp = cp+1;
3048 }
3049 }else if( c=='{' ){ /* A block of C code */
3050 int level;
3051 cp++;
3052 for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){
3053 if( c=='\n' ) lineno++;
3054 else if( c=='{' ) level++;
3055 else if( c=='}' ) level--;
3056 else if( c=='/' && cp[1]=='*' ){ /* Skip comments */
3057 int prevc;
3058 cp = &cp[2];
3059 prevc = 0;
3060 while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){
3061 if( c=='\n' ) lineno++;
3062 prevc = c;
3063 cp++;
3064 }
3065 }else if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments too */
3066 cp = &cp[2];
3067 while( (c= *cp)!=0 && c!='\n' ) cp++;
3068 if( c ) lineno++;
3069 }else if( c=='\'' || c=='\"' ){ /* String a character literals */
3070 int startchar, prevc;
3071 startchar = c;
3072 prevc = 0;
3073 for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){
3074 if( c=='\n' ) lineno++;
3075 if( prevc=='\\' ) prevc = 0;
3076 else prevc = c;
3077 }
3078 }
3079 }
3080 if( c==0 ){
3081 ErrorMsg(ps.filename,ps.tokenlineno,
3082 "C code starting on this line is not terminated before "
3083 "the end of the file.");
3084 ps.errorcnt++;
3085 nextcp = cp;
3086 }else{
3087 nextcp = cp+1;
3088 }
3089 }else if( ISALNUM(c) ){ /* Identifiers */
3090 while( (c= *cp)!=0 && (ISALNUM(c) || c=='_') ) cp++;
3091 nextcp = cp;
3092 }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */
3093 cp += 3;
3094 nextcp = cp;
3095 }else if( (c=='/' || c=='|') && ISALPHA(cp[1]) ){
3096 cp += 2;
3097 while( (c = *cp)!=0 && (ISALNUM(c) || c=='_') ) cp++;
3098 nextcp = cp;
3099 }else{ /* All other (one character) operators */
3100 cp++;
3101 nextcp = cp;
3102 }
3103 c = *cp;
3104 *cp = 0; /* Null terminate the token */
3105 parseonetoken(&ps); /* Parse the token */
3106 *cp = (char)c; /* Restore the buffer */
3107 cp = nextcp;
3108 }
3109 free(filebuf); /* Release the buffer after parsing */
3110 gp->rule = ps.firstrule;
3111 gp->errorcnt = ps.errorcnt;
3112 }
3113 /*************************** From the file "plink.c" *********************/
3114 /*
3115 ** Routines processing configuration follow-set propagation links
3116 ** in the LEMON parser generator.
3117 */
3118 static struct plink *plink_freelist = 0;
3119
3120 /* Allocate a new plink */
Plink_new(void)3121 struct plink *Plink_new(void){
3122 struct plink *newlink;
3123
3124 if( plink_freelist==0 ){
3125 int i;
3126 int amt = 100;
3127 plink_freelist = (struct plink *)calloc( amt, sizeof(struct plink) );
3128 if( plink_freelist==0 ){
3129 fprintf(stderr,
3130 "Unable to allocate memory for a new follow-set propagation link.\n");
3131 exit(1);
3132 }
3133 for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
3134 plink_freelist[amt-1].next = 0;
3135 }
3136 newlink = plink_freelist;
3137 plink_freelist = plink_freelist->next;
3138 return newlink;
3139 }
3140
3141 /* Add a plink to a plink list */
Plink_add(struct plink ** plpp,struct config * cfp)3142 void Plink_add(struct plink **plpp, struct config *cfp)
3143 {
3144 struct plink *newlink;
3145 newlink = Plink_new();
3146 newlink->next = *plpp;
3147 *plpp = newlink;
3148 newlink->cfp = cfp;
3149 }
3150
3151 /* Transfer every plink on the list "from" to the list "to" */
Plink_copy(struct plink ** to,struct plink * from)3152 void Plink_copy(struct plink **to, struct plink *from)
3153 {
3154 struct plink *nextpl;
3155 while( from ){
3156 nextpl = from->next;
3157 from->next = *to;
3158 *to = from;
3159 from = nextpl;
3160 }
3161 }
3162
3163 /* Delete every plink on the list */
Plink_delete(struct plink * plp)3164 void Plink_delete(struct plink *plp)
3165 {
3166 struct plink *nextpl;
3167
3168 while( plp ){
3169 nextpl = plp->next;
3170 plp->next = plink_freelist;
3171 plink_freelist = plp;
3172 plp = nextpl;
3173 }
3174 }
3175 /*********************** From the file "report.c" **************************/
3176 /*
3177 ** Procedures for generating reports and tables in the LEMON parser generator.
3178 */
3179
3180 /* Generate a filename with the given suffix. Space to hold the
3181 ** name comes from malloc() and must be freed by the calling
3182 ** function.
3183 */
file_makename(struct lemon * lemp,const char * suffix)3184 PRIVATE char *file_makename(struct lemon *lemp, const char *suffix)
3185 {
3186 char *name;
3187 char *cp;
3188 char *filename = lemp->filename;
3189 int sz;
3190
3191 if( outputDir ){
3192 cp = strrchr(filename, '/');
3193 if( cp ) filename = cp + 1;
3194 }
3195 sz = lemonStrlen(filename);
3196 sz += lemonStrlen(suffix);
3197 if( outputDir ) sz += lemonStrlen(outputDir) + 1;
3198 sz += 5;
3199 name = (char*)malloc( sz );
3200 if( name==0 ){
3201 fprintf(stderr,"Can't allocate space for a filename.\n");
3202 exit(1);
3203 }
3204 name[0] = 0;
3205 if( outputDir ){
3206 lemon_strcpy(name, outputDir);
3207 lemon_strcat(name, "/");
3208 }
3209 lemon_strcat(name,filename);
3210 cp = strrchr(name,'.');
3211 if( cp ) *cp = 0;
3212 lemon_strcat(name,suffix);
3213 return name;
3214 }
3215
3216 /* Open a file with a name based on the name of the input file,
3217 ** but with a different (specified) suffix, and return a pointer
3218 ** to the stream */
file_open(struct lemon * lemp,const char * suffix,const char * mode)3219 PRIVATE FILE *file_open(
3220 struct lemon *lemp,
3221 const char *suffix,
3222 const char *mode
3223 ){
3224 FILE *fp;
3225
3226 if( lemp->outname ) free(lemp->outname);
3227 lemp->outname = file_makename(lemp, suffix);
3228 fp = fopen(lemp->outname,mode);
3229 if( fp==0 && *mode=='w' ){
3230 fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
3231 lemp->errorcnt++;
3232 return 0;
3233 }
3234 return fp;
3235 }
3236
3237 /* Print the text of a rule
3238 */
rule_print(FILE * out,struct rule * rp)3239 void rule_print(FILE *out, struct rule *rp){
3240 int i, j;
3241 fprintf(out, "%s",rp->lhs->name);
3242 /* if( rp->lhsalias ) fprintf(out,"(%s)",rp->lhsalias); */
3243 fprintf(out," ::=");
3244 for(i=0; i<rp->nrhs; i++){
3245 struct symbol *sp = rp->rhs[i];
3246 if( sp->type==MULTITERMINAL ){
3247 fprintf(out," %s", sp->subsym[0]->name);
3248 for(j=1; j<sp->nsubsym; j++){
3249 fprintf(out,"|%s", sp->subsym[j]->name);
3250 }
3251 }else{
3252 fprintf(out," %s", sp->name);
3253 }
3254 /* if( rp->rhsalias[i] ) fprintf(out,"(%s)",rp->rhsalias[i]); */
3255 }
3256 }
3257
3258 /* Duplicate the input file without comments and without actions
3259 ** on rules */
Reprint(struct lemon * lemp)3260 void Reprint(struct lemon *lemp)
3261 {
3262 struct rule *rp;
3263 struct symbol *sp;
3264 int i, j, maxlen, len, ncolumns, skip;
3265 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
3266 maxlen = 10;
3267 for(i=0; i<lemp->nsymbol; i++){
3268 sp = lemp->symbols[i];
3269 len = lemonStrlen(sp->name);
3270 if( len>maxlen ) maxlen = len;
3271 }
3272 ncolumns = 76/(maxlen+5);
3273 if( ncolumns<1 ) ncolumns = 1;
3274 skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
3275 for(i=0; i<skip; i++){
3276 printf("//");
3277 for(j=i; j<lemp->nsymbol; j+=skip){
3278 sp = lemp->symbols[j];
3279 assert( sp->index==j );
3280 printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
3281 }
3282 printf("\n");
3283 }
3284 for(rp=lemp->rule; rp; rp=rp->next){
3285 rule_print(stdout, rp);
3286 printf(".");
3287 if( rp->precsym ) printf(" [%s]",rp->precsym->name);
3288 /* if( rp->code ) printf("\n %s",rp->code); */
3289 printf("\n");
3290 }
3291 }
3292
3293 /* Print a single rule.
3294 */
RulePrint(FILE * fp,struct rule * rp,int iCursor)3295 void RulePrint(FILE *fp, struct rule *rp, int iCursor){
3296 struct symbol *sp;
3297 int i, j;
3298 fprintf(fp,"%s ::=",rp->lhs->name);
3299 for(i=0; i<=rp->nrhs; i++){
3300 if( i==iCursor ) fprintf(fp," *");
3301 if( i==rp->nrhs ) break;
3302 sp = rp->rhs[i];
3303 if( sp->type==MULTITERMINAL ){
3304 fprintf(fp," %s", sp->subsym[0]->name);
3305 for(j=1; j<sp->nsubsym; j++){
3306 fprintf(fp,"|%s",sp->subsym[j]->name);
3307 }
3308 }else{
3309 fprintf(fp," %s", sp->name);
3310 }
3311 }
3312 }
3313
3314 /* Print the rule for a configuration.
3315 */
ConfigPrint(FILE * fp,struct config * cfp)3316 void ConfigPrint(FILE *fp, struct config *cfp){
3317 RulePrint(fp, cfp->rp, cfp->dot);
3318 }
3319
3320 /* #define TEST */
3321 #if 0
3322 /* Print a set */
3323 PRIVATE void SetPrint(out,set,lemp)
3324 FILE *out;
3325 char *set;
3326 struct lemon *lemp;
3327 {
3328 int i;
3329 char *spacer;
3330 spacer = "";
3331 fprintf(out,"%12s[","");
3332 for(i=0; i<lemp->nterminal; i++){
3333 if( SetFind(set,i) ){
3334 fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
3335 spacer = " ";
3336 }
3337 }
3338 fprintf(out,"]\n");
3339 }
3340
3341 /* Print a plink chain */
3342 PRIVATE void PlinkPrint(out,plp,tag)
3343 FILE *out;
3344 struct plink *plp;
3345 char *tag;
3346 {
3347 while( plp ){
3348 fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->statenum);
3349 ConfigPrint(out,plp->cfp);
3350 fprintf(out,"\n");
3351 plp = plp->next;
3352 }
3353 }
3354 #endif
3355
3356 /* Print an action to the given file descriptor. Return FALSE if
3357 ** nothing was actually printed.
3358 */
PrintAction(struct action * ap,FILE * fp,int indent)3359 int PrintAction(
3360 struct action *ap, /* The action to print */
3361 FILE *fp, /* Print the action here */
3362 int indent /* Indent by this amount */
3363 ){
3364 int result = 1;
3365 switch( ap->type ){
3366 case SHIFT: {
3367 struct state *stp = ap->x.stp;
3368 fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum);
3369 break;
3370 }
3371 case REDUCE: {
3372 struct rule *rp = ap->x.rp;
3373 fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->iRule);
3374 RulePrint(fp, rp, -1);
3375 break;
3376 }
3377 case SHIFTREDUCE: {
3378 struct rule *rp = ap->x.rp;
3379 fprintf(fp,"%*s shift-reduce %-7d",indent,ap->sp->name,rp->iRule);
3380 RulePrint(fp, rp, -1);
3381 break;
3382 }
3383 case ACCEPT:
3384 fprintf(fp,"%*s accept",indent,ap->sp->name);
3385 break;
3386 case ERROR:
3387 fprintf(fp,"%*s error",indent,ap->sp->name);
3388 break;
3389 case SRCONFLICT:
3390 case RRCONFLICT:
3391 fprintf(fp,"%*s reduce %-7d ** Parsing conflict **",
3392 indent,ap->sp->name,ap->x.rp->iRule);
3393 break;
3394 case SSCONFLICT:
3395 fprintf(fp,"%*s shift %-7d ** Parsing conflict **",
3396 indent,ap->sp->name,ap->x.stp->statenum);
3397 break;
3398 case SH_RESOLVED:
3399 if( showPrecedenceConflict ){
3400 fprintf(fp,"%*s shift %-7d -- dropped by precedence",
3401 indent,ap->sp->name,ap->x.stp->statenum);
3402 }else{
3403 result = 0;
3404 }
3405 break;
3406 case RD_RESOLVED:
3407 if( showPrecedenceConflict ){
3408 fprintf(fp,"%*s reduce %-7d -- dropped by precedence",
3409 indent,ap->sp->name,ap->x.rp->iRule);
3410 }else{
3411 result = 0;
3412 }
3413 break;
3414 case NOT_USED:
3415 result = 0;
3416 break;
3417 }
3418 if( result && ap->spOpt ){
3419 fprintf(fp," /* because %s==%s */", ap->sp->name, ap->spOpt->name);
3420 }
3421 return result;
3422 }
3423
3424 /* Generate the "*.out" log file */
ReportOutput(struct lemon * lemp)3425 void ReportOutput(struct lemon *lemp)
3426 {
3427 int i, n;
3428 struct state *stp;
3429 struct config *cfp;
3430 struct action *ap;
3431 struct rule *rp;
3432 FILE *fp;
3433
3434 fp = file_open(lemp,".out","wb");
3435 if( fp==0 ) return;
3436 for(i=0; i<lemp->nxstate; i++){
3437 stp = lemp->sorted[i];
3438 fprintf(fp,"State %d:\n",stp->statenum);
3439 if( lemp->basisflag ) cfp=stp->bp;
3440 else cfp=stp->cfp;
3441 while( cfp ){
3442 char buf[20];
3443 if( cfp->dot==cfp->rp->nrhs ){
3444 lemon_sprintf(buf,"(%d)",cfp->rp->iRule);
3445 fprintf(fp," %5s ",buf);
3446 }else{
3447 fprintf(fp," ");
3448 }
3449 ConfigPrint(fp,cfp);
3450 fprintf(fp,"\n");
3451 #if 0
3452 SetPrint(fp,cfp->fws,lemp);
3453 PlinkPrint(fp,cfp->fplp,"To ");
3454 PlinkPrint(fp,cfp->bplp,"From");
3455 #endif
3456 if( lemp->basisflag ) cfp=cfp->bp;
3457 else cfp=cfp->next;
3458 }
3459 fprintf(fp,"\n");
3460 for(ap=stp->ap; ap; ap=ap->next){
3461 if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
3462 }
3463 fprintf(fp,"\n");
3464 }
3465 fprintf(fp, "----------------------------------------------------\n");
3466 fprintf(fp, "Symbols:\n");
3467 fprintf(fp, "The first-set of non-terminals is shown after the name.\n\n");
3468 for(i=0; i<lemp->nsymbol; i++){
3469 int j;
3470 struct symbol *sp;
3471
3472 sp = lemp->symbols[i];
3473 fprintf(fp, " %3d: %s", i, sp->name);
3474 if( sp->type==NONTERMINAL ){
3475 fprintf(fp, ":");
3476 if( sp->lambda ){
3477 fprintf(fp, " <lambda>");
3478 }
3479 for(j=0; j<lemp->nterminal; j++){
3480 if( sp->firstset && SetFind(sp->firstset, j) ){
3481 fprintf(fp, " %s", lemp->symbols[j]->name);
3482 }
3483 }
3484 }
3485 if( sp->prec>=0 ) fprintf(fp," (precedence=%d)", sp->prec);
3486 fprintf(fp, "\n");
3487 }
3488 fprintf(fp, "----------------------------------------------------\n");
3489 fprintf(fp, "Syntax-only Symbols:\n");
3490 fprintf(fp, "The following symbols never carry semantic content.\n\n");
3491 for(i=n=0; i<lemp->nsymbol; i++){
3492 int w;
3493 struct symbol *sp = lemp->symbols[i];
3494 if( sp->bContent ) continue;
3495 w = (int)strlen(sp->name);
3496 if( n>0 && n+w>75 ){
3497 fprintf(fp,"\n");
3498 n = 0;
3499 }
3500 if( n>0 ){
3501 fprintf(fp, " ");
3502 n++;
3503 }
3504 fprintf(fp, "%s", sp->name);
3505 n += w;
3506 }
3507 if( n>0 ) fprintf(fp, "\n");
3508 fprintf(fp, "----------------------------------------------------\n");
3509 fprintf(fp, "Rules:\n");
3510 for(rp=lemp->rule; rp; rp=rp->next){
3511 fprintf(fp, "%4d: ", rp->iRule);
3512 rule_print(fp, rp);
3513 fprintf(fp,".");
3514 if( rp->precsym ){
3515 fprintf(fp," [%s precedence=%d]",
3516 rp->precsym->name, rp->precsym->prec);
3517 }
3518 fprintf(fp,"\n");
3519 }
3520 fclose(fp);
3521 return;
3522 }
3523
3524 /* Search for the file "name" which is in the same directory as
3525 ** the exacutable */
pathsearch(char * argv0,char * name,int modemask)3526 PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
3527 {
3528 const char *pathlist;
3529 char *pathbufptr = 0;
3530 char *pathbuf = 0;
3531 char *path,*cp;
3532 char c;
3533
3534 #ifdef __WIN32__
3535 cp = strrchr(argv0,'\\');
3536 #else
3537 cp = strrchr(argv0,'/');
3538 #endif
3539 if( cp ){
3540 c = *cp;
3541 *cp = 0;
3542 path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2 );
3543 if( path ) lemon_sprintf(path,"%s/%s",argv0,name);
3544 *cp = c;
3545 }else{
3546 pathlist = getenv("PATH");
3547 if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
3548 pathbuf = (char *) malloc( lemonStrlen(pathlist) + 1 );
3549 path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
3550 MemoryCheck(pathbuf); MemoryCheck(path); /* Fail on allocation failure. */
3551 if( (pathbuf != 0) && (path!=0) ){
3552 pathbufptr = pathbuf;
3553 lemon_strcpy(pathbuf, pathlist);
3554 while( *pathbuf ){
3555 cp = strchr(pathbuf,':');
3556 if( cp==0 ) cp = &pathbuf[lemonStrlen(pathbuf)];
3557 c = *cp;
3558 *cp = 0;
3559 lemon_sprintf(path,"%s/%s",pathbuf,name);
3560 *cp = c;
3561 if( c==0 ) pathbuf[0] = 0;
3562 else pathbuf = &cp[1];
3563 if( access(path,modemask)==0 ) break;
3564 }
3565 }
3566 free(pathbufptr);
3567 }
3568 return path;
3569 }
3570
3571 /* Given an action, compute the integer value for that action
3572 ** which is to be put in the action table of the generated machine.
3573 ** Return negative if no action should be generated.
3574 */
compute_action(struct lemon * lemp,struct action * ap)3575 PRIVATE int compute_action(struct lemon *lemp, struct action *ap)
3576 {
3577 int act;
3578 switch( ap->type ){
3579 case SHIFT: act = ap->x.stp->statenum; break;
3580 case SHIFTREDUCE: {
3581 /* Since a SHIFT is inherient after a prior REDUCE, convert any
3582 ** SHIFTREDUCE action with a nonterminal on the LHS into a simple
3583 ** REDUCE action: */
3584 if( ap->sp->index>=lemp->nterminal ){
3585 act = lemp->minReduce + ap->x.rp->iRule;
3586 }else{
3587 act = lemp->minShiftReduce + ap->x.rp->iRule;
3588 }
3589 break;
3590 }
3591 case REDUCE: act = lemp->minReduce + ap->x.rp->iRule; break;
3592 case ERROR: act = lemp->errAction; break;
3593 case ACCEPT: act = lemp->accAction; break;
3594 default: act = -1; break;
3595 }
3596 return act;
3597 }
3598
3599 #define LINESIZE 1000
3600 /* The next cluster of routines are for reading the template file
3601 ** and writing the results to the generated parser */
3602 /* The first function transfers data from "in" to "out" until
3603 ** a line is seen which begins with "%%". The line number is
3604 ** tracked.
3605 **
3606 ** if name!=0, then any word that begin with "Parse" is changed to
3607 ** begin with *name instead.
3608 */
tplt_xfer(char * name,FILE * in,FILE * out,int * lineno)3609 PRIVATE void tplt_xfer(char *name, FILE *in, FILE *out, int *lineno)
3610 {
3611 int i, iStart;
3612 char line[LINESIZE];
3613 while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
3614 (*lineno)++;
3615 iStart = 0;
3616 if( name ){
3617 for(i=0; line[i]; i++){
3618 if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0
3619 && (i==0 || !ISALPHA(line[i-1]))
3620 ){
3621 if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);
3622 fprintf(out,"%s",name);
3623 i += 4;
3624 iStart = i+1;
3625 }
3626 }
3627 }
3628 fprintf(out,"%s",&line[iStart]);
3629 }
3630 }
3631
3632 /* Skip forward past the header of the template file to the first "%%"
3633 */
tplt_skip_header(FILE * in,int * lineno)3634 PRIVATE void tplt_skip_header(FILE *in, int *lineno)
3635 {
3636 char line[LINESIZE];
3637 while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
3638 (*lineno)++;
3639 }
3640 }
3641
3642 /* The next function finds the template file and opens it, returning
3643 ** a pointer to the opened file. */
tplt_open(struct lemon * lemp)3644 PRIVATE FILE *tplt_open(struct lemon *lemp)
3645 {
3646 static char templatename[] = "lempar.c";
3647 char buf[1000];
3648 FILE *in;
3649 char *tpltname;
3650 char *toFree = 0;
3651 char *cp;
3652
3653 /* first, see if user specified a template filename on the command line. */
3654 if (user_templatename != 0) {
3655 if( access(user_templatename,004)==-1 ){
3656 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3657 user_templatename);
3658 lemp->errorcnt++;
3659 return 0;
3660 }
3661 in = fopen(user_templatename,"rb");
3662 if( in==0 ){
3663 fprintf(stderr,"Can't open the template file \"%s\".\n",
3664 user_templatename);
3665 lemp->errorcnt++;
3666 return 0;
3667 }
3668 return in;
3669 }
3670
3671 cp = strrchr(lemp->filename,'.');
3672 if( cp ){
3673 lemon_sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
3674 }else{
3675 lemon_sprintf(buf,"%s.lt",lemp->filename);
3676 }
3677 if( access(buf,004)==0 ){
3678 tpltname = buf;
3679 }else if( access(templatename,004)==0 ){
3680 tpltname = templatename;
3681 }else{
3682 toFree = tpltname = pathsearch(lemp->argv0,templatename,0);
3683 }
3684 if( tpltname==0 ){
3685 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3686 templatename);
3687 lemp->errorcnt++;
3688 return 0;
3689 }
3690 in = fopen(tpltname,"rb");
3691 if( in==0 ){
3692 fprintf(stderr,"Can't open the template file \"%s\".\n",tpltname);
3693 lemp->errorcnt++;
3694 }
3695 free(toFree);
3696 return in;
3697 }
3698
3699 /* Print a #line directive line to the output file. */
tplt_linedir(FILE * out,int lineno,char * filename)3700 PRIVATE void tplt_linedir(FILE *out, int lineno, char *filename)
3701 {
3702 fprintf(out,"#line %d \"",lineno);
3703 while( *filename ){
3704 if( *filename == '\\' ) putc('\\',out);
3705 putc(*filename,out);
3706 filename++;
3707 }
3708 fprintf(out,"\"\n");
3709 }
3710
3711 /* Print a string to the file and keep the linenumber up to date */
tplt_print(FILE * out,struct lemon * lemp,char * str,int * lineno)3712 PRIVATE void tplt_print(FILE *out, struct lemon *lemp, char *str, int *lineno)
3713 {
3714 if( str==0 ) return;
3715 while( *str ){
3716 putc(*str,out);
3717 if( *str=='\n' ) (*lineno)++;
3718 str++;
3719 }
3720 if( str[-1]!='\n' ){
3721 putc('\n',out);
3722 (*lineno)++;
3723 }
3724 if (!lemp->nolinenosflag) {
3725 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);
3726 }
3727 return;
3728 }
3729
3730 /*
3731 ** The following routine emits code for the destructor for the
3732 ** symbol sp
3733 */
emit_destructor_code(FILE * out,struct symbol * sp,struct lemon * lemp,int * lineno)3734 void emit_destructor_code(
3735 FILE *out,
3736 struct symbol *sp,
3737 struct lemon *lemp,
3738 int *lineno
3739 ){
3740 char *cp = 0;
3741
3742 if( sp->type==TERMINAL ){
3743 cp = lemp->tokendest;
3744 if( cp==0 ) return;
3745 fprintf(out,"{\n"); (*lineno)++;
3746 }else if( sp->destructor ){
3747 cp = sp->destructor;
3748 fprintf(out,"{\n"); (*lineno)++;
3749 if( !lemp->nolinenosflag ){
3750 (*lineno)++;
3751 tplt_linedir(out,sp->destLineno,lemp->filename);
3752 }
3753 }else if( lemp->vardest ){
3754 cp = lemp->vardest;
3755 if( cp==0 ) return;
3756 fprintf(out,"{\n"); (*lineno)++;
3757 }else{
3758 assert( 0 ); /* Cannot happen */
3759 }
3760 for(; *cp; cp++){
3761 if( *cp=='$' && cp[1]=='$' ){
3762 fprintf(out,"(yypminor->yy%d)",sp->dtnum);
3763 cp++;
3764 continue;
3765 }
3766 if( *cp=='\n' ) (*lineno)++;
3767 fputc(*cp,out);
3768 }
3769 fprintf(out,"\n"); (*lineno)++;
3770 if (!lemp->nolinenosflag) {
3771 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);
3772 }
3773 fprintf(out,"}\n"); (*lineno)++;
3774 return;
3775 }
3776
3777 /*
3778 ** Return TRUE (non-zero) if the given symbol has a destructor.
3779 */
has_destructor(struct symbol * sp,struct lemon * lemp)3780 int has_destructor(struct symbol *sp, struct lemon *lemp)
3781 {
3782 int ret;
3783 if( sp->type==TERMINAL ){
3784 ret = lemp->tokendest!=0;
3785 }else{
3786 ret = lemp->vardest!=0 || sp->destructor!=0;
3787 }
3788 return ret;
3789 }
3790
3791 /*
3792 ** Append text to a dynamically allocated string. If zText is 0 then
3793 ** reset the string to be empty again. Always return the complete text
3794 ** of the string (which is overwritten with each call).
3795 **
3796 ** n bytes of zText are stored. If n==0 then all of zText up to the first
3797 ** \000 terminator is stored. zText can contain up to two instances of
3798 ** %d. The values of p1 and p2 are written into the first and second
3799 ** %d.
3800 **
3801 ** If n==-1, then the previous character is overwritten.
3802 */
append_str(const char * zText,int n,int p1,int p2)3803 PRIVATE char *append_str(const char *zText, int n, int p1, int p2){
3804 static char empty[1] = { 0 };
3805 static char *z = 0;
3806 static int alloced = 0;
3807 static int used = 0;
3808 int c;
3809 char zInt[40];
3810 if( zText==0 ){
3811 if( used==0 && z!=0 ) z[0] = 0;
3812 used = 0;
3813 return z;
3814 }
3815 if( n<=0 ){
3816 if( n<0 ){
3817 used += n;
3818 assert( used>=0 );
3819 }
3820 n = lemonStrlen(zText);
3821 }
3822 if( (int) (n+sizeof(zInt)*2+used) >= alloced ){
3823 alloced = n + sizeof(zInt)*2 + used + 200;
3824 z = (char *) realloc(z, alloced);
3825 }
3826 if( z==0 ) return empty;
3827 while( n-- > 0 ){
3828 c = *(zText++);
3829 if( c=='%' && n>0 && zText[0]=='d' ){
3830 lemon_sprintf(zInt, "%d", p1);
3831 p1 = p2;
3832 lemon_strcpy(&z[used], zInt);
3833 used += lemonStrlen(&z[used]);
3834 zText++;
3835 n--;
3836 }else{
3837 z[used++] = (char)c;
3838 }
3839 }
3840 z[used] = 0;
3841 return z;
3842 }
3843
3844 /*
3845 ** Write and transform the rp->code string so that symbols are expanded.
3846 ** Populate the rp->codePrefix and rp->codeSuffix strings, as appropriate.
3847 **
3848 ** Return 1 if the expanded code requires that "yylhsminor" local variable
3849 ** to be defined.
3850 */
translate_code(struct lemon * lemp,struct rule * rp)3851 PRIVATE int translate_code(struct lemon *lemp, struct rule *rp){
3852 char *cp, *xp;
3853 int i;
3854 int rc = 0; /* True if yylhsminor is used */
3855 int dontUseRhs0 = 0; /* If true, use of left-most RHS label is illegal */
3856 const char *zSkip = 0; /* The zOvwrt comment within rp->code, or NULL */
3857 char lhsused = 0; /* True if the LHS element has been used */
3858 char lhsdirect; /* True if LHS writes directly into stack */
3859 char used[MAXRHS]; /* True for each RHS element which is used */
3860 char zLhs[50]; /* Convert the LHS symbol into this string */
3861 char zOvwrt[900]; /* Comment that to allow LHS to overwrite RHS */
3862
3863 for(i=0; i<rp->nrhs; i++) used[i] = 0;
3864 lhsused = 0;
3865
3866 if( rp->code==0 ){
3867 static char newlinestr[2] = { '\n', '\0' };
3868 rp->code = newlinestr;
3869 rp->line = rp->ruleline;
3870 rp->noCode = 1;
3871 }else{
3872 rp->noCode = 0;
3873 }
3874
3875
3876 if( rp->nrhs==0 ){
3877 /* If there are no RHS symbols, then writing directly to the LHS is ok */
3878 lhsdirect = 1;
3879 }else if( rp->rhsalias[0]==0 ){
3880 /* The left-most RHS symbol has no value. LHS direct is ok. But
3881 ** we have to call the distructor on the RHS symbol first. */
3882 lhsdirect = 1;
3883 if( has_destructor(rp->rhs[0],lemp) ){
3884 append_str(0,0,0,0);
3885 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
3886 rp->rhs[0]->index,1-rp->nrhs);
3887 rp->codePrefix = Strsafe(append_str(0,0,0,0));
3888 rp->noCode = 0;
3889 }
3890 }else if( rp->lhsalias==0 ){
3891 /* There is no LHS value symbol. */
3892 lhsdirect = 1;
3893 }else if( strcmp(rp->lhsalias,rp->rhsalias[0])==0 ){
3894 /* The LHS symbol and the left-most RHS symbol are the same, so
3895 ** direct writing is allowed */
3896 lhsdirect = 1;
3897 lhsused = 1;
3898 used[0] = 1;
3899 if( rp->lhs->dtnum!=rp->rhs[0]->dtnum ){
3900 ErrorMsg(lemp->filename,rp->ruleline,
3901 "%s(%s) and %s(%s) share the same label but have "
3902 "different datatypes.",
3903 rp->lhs->name, rp->lhsalias, rp->rhs[0]->name, rp->rhsalias[0]);
3904 lemp->errorcnt++;
3905 }
3906 }else{
3907 lemon_sprintf(zOvwrt, "/*%s-overwrites-%s*/",
3908 rp->lhsalias, rp->rhsalias[0]);
3909 zSkip = strstr(rp->code, zOvwrt);
3910 if( zSkip!=0 ){
3911 /* The code contains a special comment that indicates that it is safe
3912 ** for the LHS label to overwrite left-most RHS label. */
3913 lhsdirect = 1;
3914 }else{
3915 lhsdirect = 0;
3916 }
3917 }
3918 if( lhsdirect ){
3919 sprintf(zLhs, "yymsp[%d].minor.yy%d",1-rp->nrhs,rp->lhs->dtnum);
3920 }else{
3921 rc = 1;
3922 sprintf(zLhs, "yylhsminor.yy%d",rp->lhs->dtnum);
3923 }
3924
3925 append_str(0,0,0,0);
3926
3927 /* This const cast is wrong but harmless, if we're careful. */
3928 for(cp=(char *)rp->code; *cp; cp++){
3929 if( cp==zSkip ){
3930 append_str(zOvwrt,0,0,0);
3931 cp += lemonStrlen(zOvwrt)-1;
3932 dontUseRhs0 = 1;
3933 continue;
3934 }
3935 if( ISALPHA(*cp) && (cp==rp->code || (!ISALNUM(cp[-1]) && cp[-1]!='_')) ){
3936 char saved;
3937 for(xp= &cp[1]; ISALNUM(*xp) || *xp=='_'; xp++);
3938 saved = *xp;
3939 *xp = 0;
3940 if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
3941 append_str(zLhs,0,0,0);
3942 cp = xp;
3943 lhsused = 1;
3944 }else{
3945 for(i=0; i<rp->nrhs; i++){
3946 if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
3947 if( i==0 && dontUseRhs0 ){
3948 ErrorMsg(lemp->filename,rp->ruleline,
3949 "Label %s used after '%s'.",
3950 rp->rhsalias[0], zOvwrt);
3951 lemp->errorcnt++;
3952 }else if( cp!=rp->code && cp[-1]=='@' ){
3953 /* If the argument is of the form @X then substituted
3954 ** the token number of X, not the value of X */
3955 append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);
3956 }else{
3957 struct symbol *sp = rp->rhs[i];
3958 int dtnum;
3959 if( sp->type==MULTITERMINAL ){
3960 dtnum = sp->subsym[0]->dtnum;
3961 }else{
3962 dtnum = sp->dtnum;
3963 }
3964 append_str("yymsp[%d].minor.yy%d",0,i-rp->nrhs+1, dtnum);
3965 }
3966 cp = xp;
3967 used[i] = 1;
3968 break;
3969 }
3970 }
3971 }
3972 *xp = saved;
3973 }
3974 append_str(cp, 1, 0, 0);
3975 } /* End loop */
3976
3977 /* Main code generation completed */
3978 cp = append_str(0,0,0,0);
3979 if( cp && cp[0] ) rp->code = Strsafe(cp);
3980 append_str(0,0,0,0);
3981
3982 /* Check to make sure the LHS has been used */
3983 if( rp->lhsalias && !lhsused ){
3984 ErrorMsg(lemp->filename,rp->ruleline,
3985 "Label \"%s\" for \"%s(%s)\" is never used.",
3986 rp->lhsalias,rp->lhs->name,rp->lhsalias);
3987 lemp->errorcnt++;
3988 }
3989
3990 /* Generate destructor code for RHS minor values which are not referenced.
3991 ** Generate error messages for unused labels and duplicate labels.
3992 */
3993 for(i=0; i<rp->nrhs; i++){
3994 if( rp->rhsalias[i] ){
3995 if( i>0 ){
3996 int j;
3997 if( rp->lhsalias && strcmp(rp->lhsalias,rp->rhsalias[i])==0 ){
3998 ErrorMsg(lemp->filename,rp->ruleline,
3999 "%s(%s) has the same label as the LHS but is not the left-most "
4000 "symbol on the RHS.",
4001 rp->rhs[i]->name, rp->rhsalias[i]);
4002 lemp->errorcnt++;
4003 }
4004 for(j=0; j<i; j++){
4005 if( rp->rhsalias[j] && strcmp(rp->rhsalias[j],rp->rhsalias[i])==0 ){
4006 ErrorMsg(lemp->filename,rp->ruleline,
4007 "Label %s used for multiple symbols on the RHS of a rule.",
4008 rp->rhsalias[i]);
4009 lemp->errorcnt++;
4010 break;
4011 }
4012 }
4013 }
4014 if( !used[i] ){
4015 ErrorMsg(lemp->filename,rp->ruleline,
4016 "Label %s for \"%s(%s)\" is never used.",
4017 rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
4018 lemp->errorcnt++;
4019 }
4020 }else if( i>0 && has_destructor(rp->rhs[i],lemp) ){
4021 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
4022 rp->rhs[i]->index,i-rp->nrhs+1);
4023 }
4024 }
4025
4026 /* If unable to write LHS values directly into the stack, write the
4027 ** saved LHS value now. */
4028 if( lhsdirect==0 ){
4029 append_str(" yymsp[%d].minor.yy%d = ", 0, 1-rp->nrhs, rp->lhs->dtnum);
4030 append_str(zLhs, 0, 0, 0);
4031 append_str(";\n", 0, 0, 0);
4032 }
4033
4034 /* Suffix code generation complete */
4035 cp = append_str(0,0,0,0);
4036 if( cp && cp[0] ){
4037 rp->codeSuffix = Strsafe(cp);
4038 rp->noCode = 0;
4039 }
4040
4041 return rc;
4042 }
4043
4044 /*
4045 ** Generate code which executes when the rule "rp" is reduced. Write
4046 ** the code to "out". Make sure lineno stays up-to-date.
4047 */
emit_code(FILE * out,struct rule * rp,struct lemon * lemp,int * lineno)4048 PRIVATE void emit_code(
4049 FILE *out,
4050 struct rule *rp,
4051 struct lemon *lemp,
4052 int *lineno
4053 ){
4054 const char *cp;
4055
4056 /* Setup code prior to the #line directive */
4057 if( rp->codePrefix && rp->codePrefix[0] ){
4058 fprintf(out, "{%s", rp->codePrefix);
4059 for(cp=rp->codePrefix; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; }
4060 }
4061
4062 /* Generate code to do the reduce action */
4063 if( rp->code ){
4064 if( !lemp->nolinenosflag ){
4065 (*lineno)++;
4066 tplt_linedir(out,rp->line,lemp->filename);
4067 }
4068 fprintf(out,"{%s",rp->code);
4069 for(cp=rp->code; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; }
4070 fprintf(out,"}\n"); (*lineno)++;
4071 if( !lemp->nolinenosflag ){
4072 (*lineno)++;
4073 tplt_linedir(out,*lineno,lemp->outname);
4074 }
4075 }
4076
4077 /* Generate breakdown code that occurs after the #line directive */
4078 if( rp->codeSuffix && rp->codeSuffix[0] ){
4079 fprintf(out, "%s", rp->codeSuffix);
4080 for(cp=rp->codeSuffix; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; }
4081 }
4082
4083 if( rp->codePrefix ){
4084 fprintf(out, "}\n"); (*lineno)++;
4085 }
4086
4087 return;
4088 }
4089
4090 /*
4091 ** Print the definition of the union used for the parser's data stack.
4092 ** This union contains fields for every possible data type for tokens
4093 ** and nonterminals. In the process of computing and printing this
4094 ** union, also set the ".dtnum" field of every terminal and nonterminal
4095 ** symbol.
4096 */
print_stack_union(FILE * out,struct lemon * lemp,int * plineno,int mhflag)4097 void print_stack_union(
4098 FILE *out, /* The output stream */
4099 struct lemon *lemp, /* The main info structure for this parser */
4100 int *plineno, /* Pointer to the line number */
4101 int mhflag /* True if generating makeheaders output */
4102 ){
4103 int lineno; /* The line number of the output */
4104 char **types; /* A hash table of datatypes */
4105 int arraysize; /* Size of the "types" array */
4106 int maxdtlength; /* Maximum length of any ".datatype" field. */
4107 char *stddt; /* Standardized name for a datatype */
4108 int i,j; /* Loop counters */
4109 unsigned hash; /* For hashing the name of a type */
4110 const char *name; /* Name of the parser */
4111
4112 /* Allocate and initialize types[] and allocate stddt[] */
4113 arraysize = lemp->nsymbol * 2;
4114 types = (char**)calloc( arraysize, sizeof(char*) );
4115 if( types==0 ){
4116 fprintf(stderr,"Out of memory.\n");
4117 exit(1);
4118 }
4119 for(i=0; i<arraysize; i++) types[i] = 0;
4120 maxdtlength = 0;
4121 if( lemp->vartype ){
4122 maxdtlength = lemonStrlen(lemp->vartype);
4123 }
4124 for(i=0; i<lemp->nsymbol; i++){
4125 int len;
4126 struct symbol *sp = lemp->symbols[i];
4127 if( sp->datatype==0 ) continue;
4128 len = lemonStrlen(sp->datatype);
4129 if( len>maxdtlength ) maxdtlength = len;
4130 }
4131 stddt = (char*)malloc( maxdtlength*2 + 1 );
4132 if( stddt==0 ){
4133 fprintf(stderr,"Out of memory.\n");
4134 exit(1);
4135 }
4136
4137 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
4138 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
4139 ** used for terminal symbols. If there is no %default_type defined then
4140 ** 0 is also used as the .dtnum value for nonterminals which do not specify
4141 ** a datatype using the %type directive.
4142 */
4143 for(i=0; i<lemp->nsymbol; i++){
4144 struct symbol *sp = lemp->symbols[i];
4145 char *cp;
4146 if( sp==lemp->errsym ){
4147 sp->dtnum = arraysize+1;
4148 continue;
4149 }
4150 if( sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0) ){
4151 sp->dtnum = 0;
4152 continue;
4153 }
4154 cp = sp->datatype;
4155 if( cp==0 ) cp = lemp->vartype;
4156 j = 0;
4157 while( ISSPACE(*cp) ) cp++;
4158 while( *cp ) stddt[j++] = *cp++;
4159 while( j>0 && ISSPACE(stddt[j-1]) ) j--;
4160 stddt[j] = 0;
4161 if( lemp->tokentype && strcmp(stddt, lemp->tokentype)==0 ){
4162 sp->dtnum = 0;
4163 continue;
4164 }
4165 hash = 0;
4166 for(j=0; stddt[j]; j++){
4167 hash = hash*53 + stddt[j];
4168 }
4169 hash = (hash & 0x7fffffff)%arraysize;
4170 while( types[hash] ){
4171 if( strcmp(types[hash],stddt)==0 ){
4172 sp->dtnum = hash + 1;
4173 break;
4174 }
4175 hash++;
4176 if( hash>=(unsigned)arraysize ) hash = 0;
4177 }
4178 if( types[hash]==0 ){
4179 sp->dtnum = hash + 1;
4180 types[hash] = (char*)malloc( lemonStrlen(stddt)+1 );
4181 if( types[hash]==0 ){
4182 fprintf(stderr,"Out of memory.\n");
4183 exit(1);
4184 }
4185 lemon_strcpy(types[hash],stddt);
4186 }
4187 }
4188
4189 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
4190 name = lemp->name ? lemp->name : "Parse";
4191 lineno = *plineno;
4192 if( mhflag ){ fprintf(out,"#if INTERFACE\n"); lineno++; }
4193 fprintf(out,"#define %sTOKENTYPE %s\n",name,
4194 lemp->tokentype?lemp->tokentype:"void*"); lineno++;
4195 if( mhflag ){ fprintf(out,"#endif\n"); lineno++; }
4196 fprintf(out,"typedef union {\n"); lineno++;
4197 fprintf(out," int yyinit;\n"); lineno++;
4198 fprintf(out," %sTOKENTYPE yy0;\n",name); lineno++;
4199 for(i=0; i<arraysize; i++){
4200 if( types[i]==0 ) continue;
4201 fprintf(out," %s yy%d;\n",types[i],i+1); lineno++;
4202 free(types[i]);
4203 }
4204 if( lemp->errsym && lemp->errsym->useCnt ){
4205 fprintf(out," int yy%d;\n",lemp->errsym->dtnum); lineno++;
4206 }
4207 free(stddt);
4208 free(types);
4209 fprintf(out,"} YYMINORTYPE;\n"); lineno++;
4210 *plineno = lineno;
4211 }
4212
4213 /*
4214 ** Return the name of a C datatype able to represent values between
4215 ** lwr and upr, inclusive. If pnByte!=NULL then also write the sizeof
4216 ** for that type (1, 2, or 4) into *pnByte.
4217 */
minimum_size_type(int lwr,int upr,int * pnByte)4218 static const char *minimum_size_type(int lwr, int upr, int *pnByte){
4219 const char *zType = "int";
4220 int nByte = 4;
4221 if( lwr>=0 ){
4222 if( upr<=255 ){
4223 zType = "unsigned char";
4224 nByte = 1;
4225 }else if( upr<65535 ){
4226 zType = "unsigned short int";
4227 nByte = 2;
4228 }else{
4229 zType = "unsigned int";
4230 nByte = 4;
4231 }
4232 }else if( lwr>=-127 && upr<=127 ){
4233 zType = "signed char";
4234 nByte = 1;
4235 }else if( lwr>=-32767 && upr<32767 ){
4236 zType = "short";
4237 nByte = 2;
4238 }
4239 if( pnByte ) *pnByte = nByte;
4240 return zType;
4241 }
4242
4243 /*
4244 ** Each state contains a set of token transaction and a set of
4245 ** nonterminal transactions. Each of these sets makes an instance
4246 ** of the following structure. An array of these structures is used
4247 ** to order the creation of entries in the yy_action[] table.
4248 */
4249 struct axset {
4250 struct state *stp; /* A pointer to a state */
4251 int isTkn; /* True to use tokens. False for non-terminals */
4252 int nAction; /* Number of actions */
4253 int iOrder; /* Original order of action sets */
4254 };
4255
4256 /*
4257 ** Compare to axset structures for sorting purposes
4258 */
axset_compare(const void * a,const void * b)4259 static int axset_compare(const void *a, const void *b){
4260 struct axset *p1 = (struct axset*)a;
4261 struct axset *p2 = (struct axset*)b;
4262 int c;
4263 c = p2->nAction - p1->nAction;
4264 if( c==0 ){
4265 c = p1->iOrder - p2->iOrder;
4266 }
4267 assert( c!=0 || p1==p2 );
4268 return c;
4269 }
4270
4271 /*
4272 ** Write text on "out" that describes the rule "rp".
4273 */
writeRuleText(FILE * out,struct rule * rp)4274 static void writeRuleText(FILE *out, struct rule *rp){
4275 int j;
4276 fprintf(out,"%s ::=", rp->lhs->name);
4277 for(j=0; j<rp->nrhs; j++){
4278 struct symbol *sp = rp->rhs[j];
4279 if( sp->type!=MULTITERMINAL ){
4280 fprintf(out," %s", sp->name);
4281 }else{
4282 int k;
4283 fprintf(out," %s", sp->subsym[0]->name);
4284 for(k=1; k<sp->nsubsym; k++){
4285 fprintf(out,"|%s",sp->subsym[k]->name);
4286 }
4287 }
4288 }
4289 }
4290
4291
4292 /* Generate C source code for the parser */
ReportTable(struct lemon * lemp,int mhflag,int sqlFlag)4293 void ReportTable(
4294 struct lemon *lemp,
4295 int mhflag, /* Output in makeheaders format if true */
4296 int sqlFlag /* Generate the *.sql file too */
4297 ){
4298 FILE *out, *in, *sql;
4299 char line[LINESIZE];
4300 int lineno;
4301 struct state *stp;
4302 struct action *ap;
4303 struct rule *rp;
4304 struct acttab *pActtab;
4305 int i, j, n, sz;
4306 int nLookAhead;
4307 int szActionType; /* sizeof(YYACTIONTYPE) */
4308 int szCodeType; /* sizeof(YYCODETYPE) */
4309 const char *name;
4310 int mnTknOfst, mxTknOfst;
4311 int mnNtOfst, mxNtOfst;
4312 struct axset *ax;
4313 char *prefix;
4314
4315 lemp->minShiftReduce = lemp->nstate;
4316 lemp->errAction = lemp->minShiftReduce + lemp->nrule;
4317 lemp->accAction = lemp->errAction + 1;
4318 lemp->noAction = lemp->accAction + 1;
4319 lemp->minReduce = lemp->noAction + 1;
4320 lemp->maxAction = lemp->minReduce + lemp->nrule;
4321
4322 in = tplt_open(lemp);
4323 if( in==0 ) return;
4324 out = file_open(lemp,".c","wb");
4325 if( out==0 ){
4326 fclose(in);
4327 return;
4328 }
4329 if( sqlFlag==0 ){
4330 sql = 0;
4331 }else{
4332 sql = file_open(lemp, ".sql", "wb");
4333 if( sql==0 ){
4334 fclose(in);
4335 fclose(out);
4336 return;
4337 }
4338 fprintf(sql,
4339 "BEGIN;\n"
4340 "CREATE TABLE symbol(\n"
4341 " id INTEGER PRIMARY KEY,\n"
4342 " name TEXT NOT NULL,\n"
4343 " isTerminal BOOLEAN NOT NULL,\n"
4344 " fallback INTEGER REFERENCES symbol"
4345 " DEFERRABLE INITIALLY DEFERRED\n"
4346 ");\n"
4347 );
4348 for(i=0; i<lemp->nsymbol; i++){
4349 fprintf(sql,
4350 "INSERT INTO symbol(id,name,isTerminal,fallback)"
4351 "VALUES(%d,'%s',%s",
4352 i, lemp->symbols[i]->name,
4353 i<lemp->nterminal ? "TRUE" : "FALSE"
4354 );
4355 if( lemp->symbols[i]->fallback ){
4356 fprintf(sql, ",%d);\n", lemp->symbols[i]->fallback->index);
4357 }else{
4358 fprintf(sql, ",NULL);\n");
4359 }
4360 }
4361 fprintf(sql,
4362 "CREATE TABLE rule(\n"
4363 " ruleid INTEGER PRIMARY KEY,\n"
4364 " lhs INTEGER REFERENCES symbol(id),\n"
4365 " txt TEXT\n"
4366 ");\n"
4367 "CREATE TABLE rulerhs(\n"
4368 " ruleid INTEGER REFERENCES rule(ruleid),\n"
4369 " pos INTEGER,\n"
4370 " sym INTEGER REFERENCES symbol(id)\n"
4371 ");\n"
4372 );
4373 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
4374 assert( i==rp->iRule );
4375 fprintf(sql,
4376 "INSERT INTO rule(ruleid,lhs,txt)VALUES(%d,%d,'",
4377 rp->iRule, rp->lhs->index
4378 );
4379 writeRuleText(sql, rp);
4380 fprintf(sql,"');\n");
4381 for(j=0; j<rp->nrhs; j++){
4382 struct symbol *sp = rp->rhs[j];
4383 if( sp->type!=MULTITERMINAL ){
4384 fprintf(sql,
4385 "INSERT INTO rulerhs(ruleid,pos,sym)VALUES(%d,%d,%d);\n",
4386 i,j,sp->index
4387 );
4388 }else{
4389 int k;
4390 for(k=0; k<sp->nsubsym; k++){
4391 fprintf(sql,
4392 "INSERT INTO rulerhs(ruleid,pos,sym)VALUES(%d,%d,%d);\n",
4393 i,j,sp->subsym[k]->index
4394 );
4395 }
4396 }
4397 }
4398 }
4399 fprintf(sql, "COMMIT;\n");
4400 }
4401 lineno = 1;
4402
4403 fprintf(out,
4404 "/* This file is automatically generated by Lemon from input grammar\n"
4405 "** source file \"%s\". */\n", lemp->filename); lineno += 2;
4406
4407 /* The first %include directive begins with a C-language comment,
4408 ** then skip over the header comment of the template file
4409 */
4410 if( lemp->include==0 ) lemp->include = "";
4411 for(i=0; ISSPACE(lemp->include[i]); i++){
4412 if( lemp->include[i]=='\n' ){
4413 lemp->include += i+1;
4414 i = -1;
4415 }
4416 }
4417 if( lemp->include[0]=='/' ){
4418 tplt_skip_header(in,&lineno);
4419 }else{
4420 tplt_xfer(lemp->name,in,out,&lineno);
4421 }
4422
4423 /* Generate the include code, if any */
4424 tplt_print(out,lemp,lemp->include,&lineno);
4425 if( mhflag ){
4426 char *incName = file_makename(lemp, ".h");
4427 fprintf(out,"#include \"%s\"\n", incName); lineno++;
4428 free(incName);
4429 }
4430 tplt_xfer(lemp->name,in,out,&lineno);
4431
4432 /* Generate #defines for all tokens */
4433 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
4434 else prefix = "";
4435 if( mhflag ){
4436 fprintf(out,"#if INTERFACE\n"); lineno++;
4437 }else{
4438 fprintf(out,"#ifndef %s%s\n", prefix, lemp->symbols[1]->name);
4439 }
4440 for(i=1; i<lemp->nterminal; i++){
4441 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
4442 lineno++;
4443 }
4444 fprintf(out,"#endif\n"); lineno++;
4445 tplt_xfer(lemp->name,in,out,&lineno);
4446
4447 /* Generate the defines */
4448 fprintf(out,"#define YYCODETYPE %s\n",
4449 minimum_size_type(0, lemp->nsymbol, &szCodeType)); lineno++;
4450 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol); lineno++;
4451 fprintf(out,"#define YYACTIONTYPE %s\n",
4452 minimum_size_type(0,lemp->maxAction,&szActionType)); lineno++;
4453 if( lemp->wildcard ){
4454 fprintf(out,"#define YYWILDCARD %d\n",
4455 lemp->wildcard->index); lineno++;
4456 }
4457 print_stack_union(out,lemp,&lineno,mhflag);
4458 fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;
4459 if( lemp->stacksize ){
4460 fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize); lineno++;
4461 }else{
4462 fprintf(out,"#define YYSTACKDEPTH 100\n"); lineno++;
4463 }
4464 fprintf(out, "#endif\n"); lineno++;
4465 if( mhflag ){
4466 fprintf(out,"#if INTERFACE\n"); lineno++;
4467 }
4468 name = lemp->name ? lemp->name : "Parse";
4469 if( lemp->arg && lemp->arg[0] ){
4470 i = lemonStrlen(lemp->arg);
4471 while( i>=1 && ISSPACE(lemp->arg[i-1]) ) i--;
4472 while( i>=1 && (ISALNUM(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--;
4473 fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg); lineno++;
4474 fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg); lineno++;
4475 fprintf(out,"#define %sARG_PARAM ,%s\n",name,&lemp->arg[i]); lineno++;
4476 fprintf(out,"#define %sARG_FETCH %s=yypParser->%s;\n",
4477 name,lemp->arg,&lemp->arg[i]); lineno++;
4478 fprintf(out,"#define %sARG_STORE yypParser->%s=%s;\n",
4479 name,&lemp->arg[i],&lemp->arg[i]); lineno++;
4480 }else{
4481 fprintf(out,"#define %sARG_SDECL\n",name); lineno++;
4482 fprintf(out,"#define %sARG_PDECL\n",name); lineno++;
4483 fprintf(out,"#define %sARG_PARAM\n",name); lineno++;
4484 fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
4485 fprintf(out,"#define %sARG_STORE\n",name); lineno++;
4486 }
4487 if( lemp->ctx && lemp->ctx[0] ){
4488 i = lemonStrlen(lemp->ctx);
4489 while( i>=1 && ISSPACE(lemp->ctx[i-1]) ) i--;
4490 while( i>=1 && (ISALNUM(lemp->ctx[i-1]) || lemp->ctx[i-1]=='_') ) i--;
4491 fprintf(out,"#define %sCTX_SDECL %s;\n",name,lemp->ctx); lineno++;
4492 fprintf(out,"#define %sCTX_PDECL ,%s\n",name,lemp->ctx); lineno++;
4493 fprintf(out,"#define %sCTX_PARAM ,%s\n",name,&lemp->ctx[i]); lineno++;
4494 fprintf(out,"#define %sCTX_FETCH %s=yypParser->%s;\n",
4495 name,lemp->ctx,&lemp->ctx[i]); lineno++;
4496 fprintf(out,"#define %sCTX_STORE yypParser->%s=%s;\n",
4497 name,&lemp->ctx[i],&lemp->ctx[i]); lineno++;
4498 }else{
4499 fprintf(out,"#define %sCTX_SDECL\n",name); lineno++;
4500 fprintf(out,"#define %sCTX_PDECL\n",name); lineno++;
4501 fprintf(out,"#define %sCTX_PARAM\n",name); lineno++;
4502 fprintf(out,"#define %sCTX_FETCH\n",name); lineno++;
4503 fprintf(out,"#define %sCTX_STORE\n",name); lineno++;
4504 }
4505 if( mhflag ){
4506 fprintf(out,"#endif\n"); lineno++;
4507 }
4508 if( lemp->errsym && lemp->errsym->useCnt ){
4509 fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;
4510 fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;
4511 }
4512 if( lemp->has_fallback ){
4513 fprintf(out,"#define YYFALLBACK 1\n"); lineno++;
4514 }
4515
4516 /* Compute the action table, but do not output it yet. The action
4517 ** table must be computed before generating the YYNSTATE macro because
4518 ** we need to know how many states can be eliminated.
4519 */
4520 ax = (struct axset *) calloc(lemp->nxstate*2, sizeof(ax[0]));
4521 if( ax==0 ){
4522 fprintf(stderr,"malloc failed\n");
4523 exit(1);
4524 }
4525 for(i=0; i<lemp->nxstate; i++){
4526 stp = lemp->sorted[i];
4527 ax[i*2].stp = stp;
4528 ax[i*2].isTkn = 1;
4529 ax[i*2].nAction = stp->nTknAct;
4530 ax[i*2+1].stp = stp;
4531 ax[i*2+1].isTkn = 0;
4532 ax[i*2+1].nAction = stp->nNtAct;
4533 }
4534 mxTknOfst = mnTknOfst = 0;
4535 mxNtOfst = mnNtOfst = 0;
4536 /* In an effort to minimize the action table size, use the heuristic
4537 ** of placing the largest action sets first */
4538 for(i=0; i<lemp->nxstate*2; i++) ax[i].iOrder = i;
4539 qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare);
4540 pActtab = acttab_alloc(lemp->nsymbol, lemp->nterminal);
4541 for(i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++){
4542 stp = ax[i].stp;
4543 if( ax[i].isTkn ){
4544 for(ap=stp->ap; ap; ap=ap->next){
4545 int action;
4546 if( ap->sp->index>=lemp->nterminal ) continue;
4547 action = compute_action(lemp, ap);
4548 if( action<0 ) continue;
4549 acttab_action(pActtab, ap->sp->index, action);
4550 }
4551 stp->iTknOfst = acttab_insert(pActtab, 1);
4552 if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
4553 if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
4554 }else{
4555 for(ap=stp->ap; ap; ap=ap->next){
4556 int action;
4557 if( ap->sp->index<lemp->nterminal ) continue;
4558 if( ap->sp->index==lemp->nsymbol ) continue;
4559 action = compute_action(lemp, ap);
4560 if( action<0 ) continue;
4561 acttab_action(pActtab, ap->sp->index, action);
4562 }
4563 stp->iNtOfst = acttab_insert(pActtab, 0);
4564 if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
4565 if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
4566 }
4567 #if 0 /* Uncomment for a trace of how the yy_action[] table fills out */
4568 { int jj, nn;
4569 for(jj=nn=0; jj<pActtab->nAction; jj++){
4570 if( pActtab->aAction[jj].action<0 ) nn++;
4571 }
4572 printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n",
4573 i, stp->statenum, ax[i].isTkn ? "Token" : "Var ",
4574 ax[i].nAction, pActtab->nAction, nn);
4575 }
4576 #endif
4577 }
4578 free(ax);
4579
4580 /* Mark rules that are actually used for reduce actions after all
4581 ** optimizations have been applied
4582 */
4583 for(rp=lemp->rule; rp; rp=rp->next) rp->doesReduce = LEMON_FALSE;
4584 for(i=0; i<lemp->nxstate; i++){
4585 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
4586 if( ap->type==REDUCE || ap->type==SHIFTREDUCE ){
4587 ap->x.rp->doesReduce = 1;
4588 }
4589 }
4590 }
4591
4592 /* Finish rendering the constants now that the action table has
4593 ** been computed */
4594 fprintf(out,"#define YYNSTATE %d\n",lemp->nxstate); lineno++;
4595 fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++;
4596 fprintf(out,"#define YYNRULE_WITH_ACTION %d\n",lemp->nruleWithAction);
4597 lineno++;
4598 fprintf(out,"#define YYNTOKEN %d\n",lemp->nterminal); lineno++;
4599 fprintf(out,"#define YY_MAX_SHIFT %d\n",lemp->nxstate-1); lineno++;
4600 i = lemp->minShiftReduce;
4601 fprintf(out,"#define YY_MIN_SHIFTREDUCE %d\n",i); lineno++;
4602 i += lemp->nrule;
4603 fprintf(out,"#define YY_MAX_SHIFTREDUCE %d\n", i-1); lineno++;
4604 fprintf(out,"#define YY_ERROR_ACTION %d\n", lemp->errAction); lineno++;
4605 fprintf(out,"#define YY_ACCEPT_ACTION %d\n", lemp->accAction); lineno++;
4606 fprintf(out,"#define YY_NO_ACTION %d\n", lemp->noAction); lineno++;
4607 fprintf(out,"#define YY_MIN_REDUCE %d\n", lemp->minReduce); lineno++;
4608 i = lemp->minReduce + lemp->nrule;
4609 fprintf(out,"#define YY_MAX_REDUCE %d\n", i-1); lineno++;
4610 tplt_xfer(lemp->name,in,out,&lineno);
4611
4612 /* Now output the action table and its associates:
4613 **
4614 ** yy_action[] A single table containing all actions.
4615 ** yy_lookahead[] A table containing the lookahead for each entry in
4616 ** yy_action. Used to detect hash collisions.
4617 ** yy_shift_ofst[] For each state, the offset into yy_action for
4618 ** shifting terminals.
4619 ** yy_reduce_ofst[] For each state, the offset into yy_action for
4620 ** shifting non-terminals after a reduce.
4621 ** yy_default[] Default action for each state.
4622 */
4623
4624 /* Output the yy_action table */
4625 lemp->nactiontab = n = acttab_action_size(pActtab);
4626 lemp->tablesize += n*szActionType;
4627 fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
4628 fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
4629 for(i=j=0; i<n; i++){
4630 int action = acttab_yyaction(pActtab, i);
4631 if( action<0 ) action = lemp->noAction;
4632 if( j==0 ) fprintf(out," /* %5d */ ", i);
4633 fprintf(out, " %4d,", action);
4634 if( j==9 || i==n-1 ){
4635 fprintf(out, "\n"); lineno++;
4636 j = 0;
4637 }else{
4638 j++;
4639 }
4640 }
4641 fprintf(out, "};\n"); lineno++;
4642
4643 /* Output the yy_lookahead table */
4644 lemp->nlookaheadtab = n = acttab_lookahead_size(pActtab);
4645 lemp->tablesize += n*szCodeType;
4646 fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
4647 for(i=j=0; i<n; i++){
4648 int la = acttab_yylookahead(pActtab, i);
4649 if( la<0 ) la = lemp->nsymbol;
4650 if( j==0 ) fprintf(out," /* %5d */ ", i);
4651 fprintf(out, " %4d,", la);
4652 if( j==9 ){
4653 fprintf(out, "\n"); lineno++;
4654 j = 0;
4655 }else{
4656 j++;
4657 }
4658 }
4659 /* Add extra entries to the end of the yy_lookahead[] table so that
4660 ** yy_shift_ofst[]+iToken will always be a valid index into the array,
4661 ** even for the largest possible value of yy_shift_ofst[] and iToken. */
4662 nLookAhead = lemp->nterminal + lemp->nactiontab;
4663 while( i<nLookAhead ){
4664 if( j==0 ) fprintf(out," /* %5d */ ", i);
4665 fprintf(out, " %4d,", lemp->nterminal);
4666 if( j==9 ){
4667 fprintf(out, "\n"); lineno++;
4668 j = 0;
4669 }else{
4670 j++;
4671 }
4672 i++;
4673 }
4674 if( j>0 ){ fprintf(out, "\n"); lineno++; }
4675 fprintf(out, "};\n"); lineno++;
4676
4677 /* Output the yy_shift_ofst[] table */
4678 n = lemp->nxstate;
4679 while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
4680 fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;
4681 fprintf(out, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst); lineno++;
4682 fprintf(out, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst); lineno++;
4683 fprintf(out, "static const %s yy_shift_ofst[] = {\n",
4684 minimum_size_type(mnTknOfst, lemp->nterminal+lemp->nactiontab, &sz));
4685 lineno++;
4686 lemp->tablesize += n*sz;
4687 for(i=j=0; i<n; i++){
4688 int ofst;
4689 stp = lemp->sorted[i];
4690 ofst = stp->iTknOfst;
4691 if( ofst==NO_OFFSET ) ofst = lemp->nactiontab;
4692 if( j==0 ) fprintf(out," /* %5d */ ", i);
4693 fprintf(out, " %4d,", ofst);
4694 if( j==9 || i==n-1 ){
4695 fprintf(out, "\n"); lineno++;
4696 j = 0;
4697 }else{
4698 j++;
4699 }
4700 }
4701 fprintf(out, "};\n"); lineno++;
4702
4703 /* Output the yy_reduce_ofst[] table */
4704 n = lemp->nxstate;
4705 while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
4706 fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
4707 fprintf(out, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst); lineno++;
4708 fprintf(out, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst); lineno++;
4709 fprintf(out, "static const %s yy_reduce_ofst[] = {\n",
4710 minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++;
4711 lemp->tablesize += n*sz;
4712 for(i=j=0; i<n; i++){
4713 int ofst;
4714 stp = lemp->sorted[i];
4715 ofst = stp->iNtOfst;
4716 if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
4717 if( j==0 ) fprintf(out," /* %5d */ ", i);
4718 fprintf(out, " %4d,", ofst);
4719 if( j==9 || i==n-1 ){
4720 fprintf(out, "\n"); lineno++;
4721 j = 0;
4722 }else{
4723 j++;
4724 }
4725 }
4726 fprintf(out, "};\n"); lineno++;
4727
4728 /* Output the default action table */
4729 fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
4730 n = lemp->nxstate;
4731 lemp->tablesize += n*szActionType;
4732 for(i=j=0; i<n; i++){
4733 stp = lemp->sorted[i];
4734 if( j==0 ) fprintf(out," /* %5d */ ", i);
4735 if( stp->iDfltReduce<0 ){
4736 fprintf(out, " %4d,", lemp->errAction);
4737 }else{
4738 fprintf(out, " %4d,", stp->iDfltReduce + lemp->minReduce);
4739 }
4740 if( j==9 || i==n-1 ){
4741 fprintf(out, "\n"); lineno++;
4742 j = 0;
4743 }else{
4744 j++;
4745 }
4746 }
4747 fprintf(out, "};\n"); lineno++;
4748 tplt_xfer(lemp->name,in,out,&lineno);
4749
4750 /* Generate the table of fallback tokens.
4751 */
4752 if( lemp->has_fallback ){
4753 int mx = lemp->nterminal - 1;
4754 /* 2019-08-28: Generate fallback entries for every token to avoid
4755 ** having to do a range check on the index */
4756 /* while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; } */
4757 lemp->tablesize += (mx+1)*szCodeType;
4758 for(i=0; i<=mx; i++){
4759 struct symbol *p = lemp->symbols[i];
4760 if( p->fallback==0 ){
4761 fprintf(out, " 0, /* %10s => nothing */\n", p->name);
4762 }else{
4763 fprintf(out, " %3d, /* %10s => %s */\n", p->fallback->index,
4764 p->name, p->fallback->name);
4765 }
4766 lineno++;
4767 }
4768 }
4769 tplt_xfer(lemp->name, in, out, &lineno);
4770
4771 /* Generate a table containing the symbolic name of every symbol
4772 */
4773 for(i=0; i<lemp->nsymbol; i++){
4774 lemon_sprintf(line,"\"%s\",",lemp->symbols[i]->name);
4775 fprintf(out," /* %4d */ \"%s\",\n",i, lemp->symbols[i]->name); lineno++;
4776 }
4777 tplt_xfer(lemp->name,in,out,&lineno);
4778
4779 /* Generate a table containing a text string that describes every
4780 ** rule in the rule set of the grammar. This information is used
4781 ** when tracing REDUCE actions.
4782 */
4783 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
4784 assert( rp->iRule==i );
4785 fprintf(out," /* %3d */ \"", i);
4786 writeRuleText(out, rp);
4787 fprintf(out,"\",\n"); lineno++;
4788 }
4789 tplt_xfer(lemp->name,in,out,&lineno);
4790
4791 /* Generate code which executes every time a symbol is popped from
4792 ** the stack while processing errors or while destroying the parser.
4793 ** (In other words, generate the %destructor actions)
4794 */
4795 if( lemp->tokendest ){
4796 int once = 1;
4797 for(i=0; i<lemp->nsymbol; i++){
4798 struct symbol *sp = lemp->symbols[i];
4799 if( sp==0 || sp->type!=TERMINAL ) continue;
4800 if( once ){
4801 fprintf(out, " /* TERMINAL Destructor */\n"); lineno++;
4802 once = 0;
4803 }
4804 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
4805 }
4806 for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
4807 if( i<lemp->nsymbol ){
4808 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
4809 fprintf(out," break;\n"); lineno++;
4810 }
4811 }
4812 if( lemp->vardest ){
4813 struct symbol *dflt_sp = 0;
4814 int once = 1;
4815 for(i=0; i<lemp->nsymbol; i++){
4816 struct symbol *sp = lemp->symbols[i];
4817 if( sp==0 || sp->type==TERMINAL ||
4818 sp->index<=0 || sp->destructor!=0 ) continue;
4819 if( once ){
4820 fprintf(out, " /* Default NON-TERMINAL Destructor */\n");lineno++;
4821 once = 0;
4822 }
4823 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
4824 dflt_sp = sp;
4825 }
4826 if( dflt_sp!=0 ){
4827 emit_destructor_code(out,dflt_sp,lemp,&lineno);
4828 }
4829 fprintf(out," break;\n"); lineno++;
4830 }
4831 for(i=0; i<lemp->nsymbol; i++){
4832 struct symbol *sp = lemp->symbols[i];
4833 if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
4834 if( sp->destLineno<0 ) continue; /* Already emitted */
4835 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
4836
4837 /* Combine duplicate destructors into a single case */
4838 for(j=i+1; j<lemp->nsymbol; j++){
4839 struct symbol *sp2 = lemp->symbols[j];
4840 if( sp2 && sp2->type!=TERMINAL && sp2->destructor
4841 && sp2->dtnum==sp->dtnum
4842 && strcmp(sp->destructor,sp2->destructor)==0 ){
4843 fprintf(out," case %d: /* %s */\n",
4844 sp2->index, sp2->name); lineno++;
4845 sp2->destLineno = -1; /* Avoid emitting this destructor again */
4846 }
4847 }
4848
4849 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
4850 fprintf(out," break;\n"); lineno++;
4851 }
4852 tplt_xfer(lemp->name,in,out,&lineno);
4853
4854 /* Generate code which executes whenever the parser stack overflows */
4855 tplt_print(out,lemp,lemp->overflow,&lineno);
4856 tplt_xfer(lemp->name,in,out,&lineno);
4857
4858 /* Generate the tables of rule information. yyRuleInfoLhs[] and
4859 ** yyRuleInfoNRhs[].
4860 **
4861 ** Note: This code depends on the fact that rules are number
4862 ** sequentually beginning with 0.
4863 */
4864 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
4865 fprintf(out," %4d, /* (%d) ", rp->lhs->index, i);
4866 rule_print(out, rp);
4867 fprintf(out," */\n"); lineno++;
4868 }
4869 tplt_xfer(lemp->name,in,out,&lineno);
4870 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
4871 fprintf(out," %3d, /* (%d) ", -rp->nrhs, i);
4872 rule_print(out, rp);
4873 fprintf(out," */\n"); lineno++;
4874 }
4875 tplt_xfer(lemp->name,in,out,&lineno);
4876
4877 /* Generate code which execution during each REDUCE action */
4878 i = 0;
4879 for(rp=lemp->rule; rp; rp=rp->next){
4880 i += translate_code(lemp, rp);
4881 }
4882 if( i ){
4883 fprintf(out," YYMINORTYPE yylhsminor;\n"); lineno++;
4884 }
4885 /* First output rules other than the default: rule */
4886 for(rp=lemp->rule; rp; rp=rp->next){
4887 struct rule *rp2; /* Other rules with the same action */
4888 if( rp->codeEmitted ) continue;
4889 if( rp->noCode ){
4890 /* No C code actions, so this will be part of the "default:" rule */
4891 continue;
4892 }
4893 fprintf(out," case %d: /* ", rp->iRule);
4894 writeRuleText(out, rp);
4895 fprintf(out, " */\n"); lineno++;
4896 for(rp2=rp->next; rp2; rp2=rp2->next){
4897 if( rp2->code==rp->code && rp2->codePrefix==rp->codePrefix
4898 && rp2->codeSuffix==rp->codeSuffix ){
4899 fprintf(out," case %d: /* ", rp2->iRule);
4900 writeRuleText(out, rp2);
4901 fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->iRule); lineno++;
4902 rp2->codeEmitted = 1;
4903 }
4904 }
4905 emit_code(out,rp,lemp,&lineno);
4906 fprintf(out," break;\n"); lineno++;
4907 rp->codeEmitted = 1;
4908 }
4909 /* Finally, output the default: rule. We choose as the default: all
4910 ** empty actions. */
4911 fprintf(out," default:\n"); lineno++;
4912 for(rp=lemp->rule; rp; rp=rp->next){
4913 if( rp->codeEmitted ) continue;
4914 assert( rp->noCode );
4915 fprintf(out," /* (%d) ", rp->iRule);
4916 writeRuleText(out, rp);
4917 if( rp->neverReduce ){
4918 fprintf(out, " (NEVER REDUCES) */ assert(yyruleno!=%d);\n",
4919 rp->iRule); lineno++;
4920 }else if( rp->doesReduce ){
4921 fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->iRule); lineno++;
4922 }else{
4923 fprintf(out, " (OPTIMIZED OUT) */ assert(yyruleno!=%d);\n",
4924 rp->iRule); lineno++;
4925 }
4926 }
4927 fprintf(out," break;\n"); lineno++;
4928 tplt_xfer(lemp->name,in,out,&lineno);
4929
4930 /* Generate code which executes if a parse fails */
4931 tplt_print(out,lemp,lemp->failure,&lineno);
4932 tplt_xfer(lemp->name,in,out,&lineno);
4933
4934 /* Generate code which executes when a syntax error occurs */
4935 tplt_print(out,lemp,lemp->error,&lineno);
4936 tplt_xfer(lemp->name,in,out,&lineno);
4937
4938 /* Generate code which executes when the parser accepts its input */
4939 tplt_print(out,lemp,lemp->accept,&lineno);
4940 tplt_xfer(lemp->name,in,out,&lineno);
4941
4942 /* Append any addition code the user desires */
4943 tplt_print(out,lemp,lemp->extracode,&lineno);
4944
4945 acttab_free(pActtab);
4946 fclose(in);
4947 fclose(out);
4948 if( sql ) fclose(sql);
4949 return;
4950 }
4951
4952 /* Generate a header file for the parser */
ReportHeader(struct lemon * lemp)4953 void ReportHeader(struct lemon *lemp)
4954 {
4955 FILE *out, *in;
4956 const char *prefix;
4957 char line[LINESIZE];
4958 char pattern[LINESIZE];
4959 int i;
4960
4961 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
4962 else prefix = "";
4963 in = file_open(lemp,".h","rb");
4964 if( in ){
4965 int nextChar;
4966 for(i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++){
4967 lemon_sprintf(pattern,"#define %s%-30s %3d\n",
4968 prefix,lemp->symbols[i]->name,i);
4969 if( strcmp(line,pattern) ) break;
4970 }
4971 nextChar = fgetc(in);
4972 fclose(in);
4973 if( i==lemp->nterminal && nextChar==EOF ){
4974 /* No change in the file. Don't rewrite it. */
4975 return;
4976 }
4977 }
4978 out = file_open(lemp,".h","wb");
4979 if( out ){
4980 for(i=1; i<lemp->nterminal; i++){
4981 fprintf(out,"#define %s%-30s %3d\n",prefix,lemp->symbols[i]->name,i);
4982 }
4983 fclose(out);
4984 }
4985 return;
4986 }
4987
4988 /* Reduce the size of the action tables, if possible, by making use
4989 ** of defaults.
4990 **
4991 ** In this version, we take the most frequent REDUCE action and make
4992 ** it the default. Except, there is no default if the wildcard token
4993 ** is a possible look-ahead.
4994 */
CompressTables(struct lemon * lemp)4995 void CompressTables(struct lemon *lemp)
4996 {
4997 struct state *stp;
4998 struct action *ap, *ap2, *nextap;
4999 struct rule *rp, *rp2, *rbest;
5000 int nbest, n;
5001 int i;
5002 int usesWildcard;
5003
5004 for(i=0; i<lemp->nstate; i++){
5005 stp = lemp->sorted[i];
5006 nbest = 0;
5007 rbest = 0;
5008 usesWildcard = 0;
5009
5010 for(ap=stp->ap; ap; ap=ap->next){
5011 if( ap->type==SHIFT && ap->sp==lemp->wildcard ){
5012 usesWildcard = 1;
5013 }
5014 if( ap->type!=REDUCE ) continue;
5015 rp = ap->x.rp;
5016 if( rp->lhsStart ) continue;
5017 if( rp==rbest ) continue;
5018 n = 1;
5019 for(ap2=ap->next; ap2; ap2=ap2->next){
5020 if( ap2->type!=REDUCE ) continue;
5021 rp2 = ap2->x.rp;
5022 if( rp2==rbest ) continue;
5023 if( rp2==rp ) n++;
5024 }
5025 if( n>nbest ){
5026 nbest = n;
5027 rbest = rp;
5028 }
5029 }
5030
5031 /* Do not make a default if the number of rules to default
5032 ** is not at least 1 or if the wildcard token is a possible
5033 ** lookahead.
5034 */
5035 if( nbest<1 || usesWildcard ) continue;
5036
5037
5038 /* Combine matching REDUCE actions into a single default */
5039 for(ap=stp->ap; ap; ap=ap->next){
5040 if( ap->type==REDUCE && ap->x.rp==rbest ) break;
5041 }
5042 assert( ap );
5043 ap->sp = Symbol_new("{default}");
5044 for(ap=ap->next; ap; ap=ap->next){
5045 if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
5046 }
5047 stp->ap = Action_sort(stp->ap);
5048
5049 for(ap=stp->ap; ap; ap=ap->next){
5050 if( ap->type==SHIFT ) break;
5051 if( ap->type==REDUCE && ap->x.rp!=rbest ) break;
5052 }
5053 if( ap==0 ){
5054 stp->autoReduce = 1;
5055 stp->pDfltReduce = rbest;
5056 }
5057 }
5058
5059 /* Make a second pass over all states and actions. Convert
5060 ** every action that is a SHIFT to an autoReduce state into
5061 ** a SHIFTREDUCE action.
5062 */
5063 for(i=0; i<lemp->nstate; i++){
5064 stp = lemp->sorted[i];
5065 for(ap=stp->ap; ap; ap=ap->next){
5066 struct state *pNextState;
5067 if( ap->type!=SHIFT ) continue;
5068 pNextState = ap->x.stp;
5069 if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){
5070 ap->type = SHIFTREDUCE;
5071 ap->x.rp = pNextState->pDfltReduce;
5072 }
5073 }
5074 }
5075
5076 /* If a SHIFTREDUCE action specifies a rule that has a single RHS term
5077 ** (meaning that the SHIFTREDUCE will land back in the state where it
5078 ** started) and if there is no C-code associated with the reduce action,
5079 ** then we can go ahead and convert the action to be the same as the
5080 ** action for the RHS of the rule.
5081 */
5082 for(i=0; i<lemp->nstate; i++){
5083 stp = lemp->sorted[i];
5084 for(ap=stp->ap; ap; ap=nextap){
5085 nextap = ap->next;
5086 if( ap->type!=SHIFTREDUCE ) continue;
5087 rp = ap->x.rp;
5088 if( rp->noCode==0 ) continue;
5089 if( rp->nrhs!=1 ) continue;
5090 #if 1
5091 /* Only apply this optimization to non-terminals. It would be OK to
5092 ** apply it to terminal symbols too, but that makes the parser tables
5093 ** larger. */
5094 if( ap->sp->index<lemp->nterminal ) continue;
5095 #endif
5096 /* If we reach this point, it means the optimization can be applied */
5097 nextap = ap;
5098 for(ap2=stp->ap; ap2 && (ap2==ap || ap2->sp!=rp->lhs); ap2=ap2->next){}
5099 assert( ap2!=0 );
5100 ap->spOpt = ap2->sp;
5101 ap->type = ap2->type;
5102 ap->x = ap2->x;
5103 }
5104 }
5105 }
5106
5107
5108 /*
5109 ** Compare two states for sorting purposes. The smaller state is the
5110 ** one with the most non-terminal actions. If they have the same number
5111 ** of non-terminal actions, then the smaller is the one with the most
5112 ** token actions.
5113 */
stateResortCompare(const void * a,const void * b)5114 static int stateResortCompare(const void *a, const void *b){
5115 const struct state *pA = *(const struct state**)a;
5116 const struct state *pB = *(const struct state**)b;
5117 int n;
5118
5119 n = pB->nNtAct - pA->nNtAct;
5120 if( n==0 ){
5121 n = pB->nTknAct - pA->nTknAct;
5122 if( n==0 ){
5123 n = pB->statenum - pA->statenum;
5124 }
5125 }
5126 assert( n!=0 );
5127 return n;
5128 }
5129
5130
5131 /*
5132 ** Renumber and resort states so that states with fewer choices
5133 ** occur at the end. Except, keep state 0 as the first state.
5134 */
ResortStates(struct lemon * lemp)5135 void ResortStates(struct lemon *lemp)
5136 {
5137 int i;
5138 struct state *stp;
5139 struct action *ap;
5140
5141 for(i=0; i<lemp->nstate; i++){
5142 stp = lemp->sorted[i];
5143 stp->nTknAct = stp->nNtAct = 0;
5144 stp->iDfltReduce = -1; /* Init dflt action to "syntax error" */
5145 stp->iTknOfst = NO_OFFSET;
5146 stp->iNtOfst = NO_OFFSET;
5147 for(ap=stp->ap; ap; ap=ap->next){
5148 int iAction = compute_action(lemp,ap);
5149 if( iAction>=0 ){
5150 if( ap->sp->index<lemp->nterminal ){
5151 stp->nTknAct++;
5152 }else if( ap->sp->index<lemp->nsymbol ){
5153 stp->nNtAct++;
5154 }else{
5155 assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp );
5156 stp->iDfltReduce = iAction;
5157 }
5158 }
5159 }
5160 }
5161 qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
5162 stateResortCompare);
5163 for(i=0; i<lemp->nstate; i++){
5164 lemp->sorted[i]->statenum = i;
5165 }
5166 lemp->nxstate = lemp->nstate;
5167 while( lemp->nxstate>1 && lemp->sorted[lemp->nxstate-1]->autoReduce ){
5168 lemp->nxstate--;
5169 }
5170 }
5171
5172
5173 /***************** From the file "set.c" ************************************/
5174 /*
5175 ** Set manipulation routines for the LEMON parser generator.
5176 */
5177
5178 static int size = 0;
5179
5180 /* Set the set size */
SetSize(int n)5181 void SetSize(int n)
5182 {
5183 size = n+1;
5184 }
5185
5186 /* Allocate a new set */
SetNew(void)5187 char *SetNew(void){
5188 char *s;
5189 s = (char*)calloc( size, 1);
5190 if( s==0 ){
5191 memory_error();
5192 }
5193 return s;
5194 }
5195
5196 /* Deallocate a set */
SetFree(char * s)5197 void SetFree(char *s)
5198 {
5199 free(s);
5200 }
5201
5202 /* Add a new element to the set. Return TRUE if the element was added
5203 ** and FALSE if it was already there. */
SetAdd(char * s,int e)5204 int SetAdd(char *s, int e)
5205 {
5206 int rv;
5207 assert( e>=0 && e<size );
5208 rv = s[e];
5209 s[e] = 1;
5210 return !rv;
5211 }
5212
5213 /* Add every element of s2 to s1. Return TRUE if s1 changes. */
SetUnion(char * s1,char * s2)5214 int SetUnion(char *s1, char *s2)
5215 {
5216 int i, progress;
5217 progress = 0;
5218 for(i=0; i<size; i++){
5219 if( s2[i]==0 ) continue;
5220 if( s1[i]==0 ){
5221 progress = 1;
5222 s1[i] = 1;
5223 }
5224 }
5225 return progress;
5226 }
5227 /********************** From the file "table.c" ****************************/
5228 /*
5229 ** All code in this file has been automatically generated
5230 ** from a specification in the file
5231 ** "table.q"
5232 ** by the associative array code building program "aagen".
5233 ** Do not edit this file! Instead, edit the specification
5234 ** file, then rerun aagen.
5235 */
5236 /*
5237 ** Code for processing tables in the LEMON parser generator.
5238 */
5239
strhash(const char * x)5240 PRIVATE unsigned strhash(const char *x)
5241 {
5242 unsigned h = 0;
5243 while( *x ) h = h*13 + *(x++);
5244 return h;
5245 }
5246
5247 /* Works like strdup, sort of. Save a string in malloced memory, but
5248 ** keep strings in a table so that the same string is not in more
5249 ** than one place.
5250 */
Strsafe(const char * y)5251 const char *Strsafe(const char *y)
5252 {
5253 const char *z;
5254 char *cpy;
5255
5256 if( y==0 ) return 0;
5257 z = Strsafe_find(y);
5258 if( z==0 && (cpy=(char *)malloc( lemonStrlen(y)+1 ))!=0 ){
5259 lemon_strcpy(cpy,y);
5260 z = cpy;
5261 Strsafe_insert(z);
5262 }
5263 MemoryCheck(z);
5264 return z;
5265 }
5266
5267 /* There is one instance of the following structure for each
5268 ** associative array of type "x1".
5269 */
5270 struct s_x1 {
5271 int size; /* The number of available slots. */
5272 /* Must be a power of 2 greater than or */
5273 /* equal to 1 */
5274 int count; /* Number of currently slots filled */
5275 struct s_x1node *tbl; /* The data stored here */
5276 struct s_x1node **ht; /* Hash table for lookups */
5277 };
5278
5279 /* There is one instance of this structure for every data element
5280 ** in an associative array of type "x1".
5281 */
5282 typedef struct s_x1node {
5283 const char *data; /* The data */
5284 struct s_x1node *next; /* Next entry with the same hash */
5285 struct s_x1node **from; /* Previous link */
5286 } x1node;
5287
5288 /* There is only one instance of the array, which is the following */
5289 static struct s_x1 *x1a;
5290
5291 /* Allocate a new associative array */
Strsafe_init(void)5292 void Strsafe_init(void){
5293 if( x1a ) return;
5294 x1a = (struct s_x1*)malloc( sizeof(struct s_x1) );
5295 if( x1a ){
5296 x1a->size = 1024;
5297 x1a->count = 0;
5298 x1a->tbl = (x1node*)calloc(1024, sizeof(x1node) + sizeof(x1node*));
5299 if( x1a->tbl==0 ){
5300 free(x1a);
5301 x1a = 0;
5302 }else{
5303 int i;
5304 x1a->ht = (x1node**)&(x1a->tbl[1024]);
5305 for(i=0; i<1024; i++) x1a->ht[i] = 0;
5306 }
5307 }
5308 }
5309 /* Insert a new record into the array. Return TRUE if successful.
5310 ** Prior data with the same key is NOT overwritten */
Strsafe_insert(const char * data)5311 int Strsafe_insert(const char *data)
5312 {
5313 x1node *np;
5314 unsigned h;
5315 unsigned ph;
5316
5317 if( x1a==0 ) return 0;
5318 ph = strhash(data);
5319 h = ph & (x1a->size-1);
5320 np = x1a->ht[h];
5321 while( np ){
5322 if( strcmp(np->data,data)==0 ){
5323 /* An existing entry with the same key is found. */
5324 /* Fail because overwrite is not allows. */
5325 return 0;
5326 }
5327 np = np->next;
5328 }
5329 if( x1a->count>=x1a->size ){
5330 /* Need to make the hash table bigger */
5331 int i,arrSize;
5332 struct s_x1 array;
5333 array.size = arrSize = x1a->size*2;
5334 array.count = x1a->count;
5335 array.tbl = (x1node*)calloc(arrSize, sizeof(x1node) + sizeof(x1node*));
5336 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
5337 array.ht = (x1node**)&(array.tbl[arrSize]);
5338 for(i=0; i<arrSize; i++) array.ht[i] = 0;
5339 for(i=0; i<x1a->count; i++){
5340 x1node *oldnp, *newnp;
5341 oldnp = &(x1a->tbl[i]);
5342 h = strhash(oldnp->data) & (arrSize-1);
5343 newnp = &(array.tbl[i]);
5344 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
5345 newnp->next = array.ht[h];
5346 newnp->data = oldnp->data;
5347 newnp->from = &(array.ht[h]);
5348 array.ht[h] = newnp;
5349 }
5350 free(x1a->tbl);
5351 memcpy(x1a, &array, sizeof(array)); /* *x1a = array; */
5352 }
5353 /* Insert the new data */
5354 h = ph & (x1a->size-1);
5355 np = &(x1a->tbl[x1a->count++]);
5356 np->data = data;
5357 if( x1a->ht[h] ) x1a->ht[h]->from = &(np->next);
5358 np->next = x1a->ht[h];
5359 x1a->ht[h] = np;
5360 np->from = &(x1a->ht[h]);
5361 return 1;
5362 }
5363
5364 /* Return a pointer to data assigned to the given key. Return NULL
5365 ** if no such key. */
Strsafe_find(const char * key)5366 const char *Strsafe_find(const char *key)
5367 {
5368 unsigned h;
5369 x1node *np;
5370
5371 if( x1a==0 ) return 0;
5372 h = strhash(key) & (x1a->size-1);
5373 np = x1a->ht[h];
5374 while( np ){
5375 if( strcmp(np->data,key)==0 ) break;
5376 np = np->next;
5377 }
5378 return np ? np->data : 0;
5379 }
5380
5381 /* Return a pointer to the (terminal or nonterminal) symbol "x".
5382 ** Create a new symbol if this is the first time "x" has been seen.
5383 */
Symbol_new(const char * x)5384 struct symbol *Symbol_new(const char *x)
5385 {
5386 struct symbol *sp;
5387
5388 sp = Symbol_find(x);
5389 if( sp==0 ){
5390 sp = (struct symbol *)calloc(1, sizeof(struct symbol) );
5391 MemoryCheck(sp);
5392 sp->name = Strsafe(x);
5393 sp->type = ISUPPER(*x) ? TERMINAL : NONTERMINAL;
5394 sp->rule = 0;
5395 sp->fallback = 0;
5396 sp->prec = -1;
5397 sp->assoc = UNK;
5398 sp->firstset = 0;
5399 sp->lambda = LEMON_FALSE;
5400 sp->destructor = 0;
5401 sp->destLineno = 0;
5402 sp->datatype = 0;
5403 sp->useCnt = 0;
5404 Symbol_insert(sp,sp->name);
5405 }
5406 sp->useCnt++;
5407 return sp;
5408 }
5409
5410 /* Compare two symbols for sorting purposes. Return negative,
5411 ** zero, or positive if a is less then, equal to, or greater
5412 ** than b.
5413 **
5414 ** Symbols that begin with upper case letters (terminals or tokens)
5415 ** must sort before symbols that begin with lower case letters
5416 ** (non-terminals). And MULTITERMINAL symbols (created using the
5417 ** %token_class directive) must sort at the very end. Other than
5418 ** that, the order does not matter.
5419 **
5420 ** We find experimentally that leaving the symbols in their original
5421 ** order (the order they appeared in the grammar file) gives the
5422 ** smallest parser tables in SQLite.
5423 */
Symbolcmpp(const void * _a,const void * _b)5424 int Symbolcmpp(const void *_a, const void *_b)
5425 {
5426 const struct symbol *a = *(const struct symbol **) _a;
5427 const struct symbol *b = *(const struct symbol **) _b;
5428 int i1 = a->type==MULTITERMINAL ? 3 : a->name[0]>'Z' ? 2 : 1;
5429 int i2 = b->type==MULTITERMINAL ? 3 : b->name[0]>'Z' ? 2 : 1;
5430 return i1==i2 ? a->index - b->index : i1 - i2;
5431 }
5432
5433 /* There is one instance of the following structure for each
5434 ** associative array of type "x2".
5435 */
5436 struct s_x2 {
5437 int size; /* The number of available slots. */
5438 /* Must be a power of 2 greater than or */
5439 /* equal to 1 */
5440 int count; /* Number of currently slots filled */
5441 struct s_x2node *tbl; /* The data stored here */
5442 struct s_x2node **ht; /* Hash table for lookups */
5443 };
5444
5445 /* There is one instance of this structure for every data element
5446 ** in an associative array of type "x2".
5447 */
5448 typedef struct s_x2node {
5449 struct symbol *data; /* The data */
5450 const char *key; /* The key */
5451 struct s_x2node *next; /* Next entry with the same hash */
5452 struct s_x2node **from; /* Previous link */
5453 } x2node;
5454
5455 /* There is only one instance of the array, which is the following */
5456 static struct s_x2 *x2a;
5457
5458 /* Allocate a new associative array */
Symbol_init(void)5459 void Symbol_init(void){
5460 if( x2a ) return;
5461 x2a = (struct s_x2*)malloc( sizeof(struct s_x2) );
5462 if( x2a ){
5463 x2a->size = 128;
5464 x2a->count = 0;
5465 x2a->tbl = (x2node*)calloc(128, sizeof(x2node) + sizeof(x2node*));
5466 if( x2a->tbl==0 ){
5467 free(x2a);
5468 x2a = 0;
5469 }else{
5470 int i;
5471 x2a->ht = (x2node**)&(x2a->tbl[128]);
5472 for(i=0; i<128; i++) x2a->ht[i] = 0;
5473 }
5474 }
5475 }
5476 /* Insert a new record into the array. Return TRUE if successful.
5477 ** Prior data with the same key is NOT overwritten */
Symbol_insert(struct symbol * data,const char * key)5478 int Symbol_insert(struct symbol *data, const char *key)
5479 {
5480 x2node *np;
5481 unsigned h;
5482 unsigned ph;
5483
5484 if( x2a==0 ) return 0;
5485 ph = strhash(key);
5486 h = ph & (x2a->size-1);
5487 np = x2a->ht[h];
5488 while( np ){
5489 if( strcmp(np->key,key)==0 ){
5490 /* An existing entry with the same key is found. */
5491 /* Fail because overwrite is not allows. */
5492 return 0;
5493 }
5494 np = np->next;
5495 }
5496 if( x2a->count>=x2a->size ){
5497 /* Need to make the hash table bigger */
5498 int i,arrSize;
5499 struct s_x2 array;
5500 array.size = arrSize = x2a->size*2;
5501 array.count = x2a->count;
5502 array.tbl = (x2node*)calloc(arrSize, sizeof(x2node) + sizeof(x2node*));
5503 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
5504 array.ht = (x2node**)&(array.tbl[arrSize]);
5505 for(i=0; i<arrSize; i++) array.ht[i] = 0;
5506 for(i=0; i<x2a->count; i++){
5507 x2node *oldnp, *newnp;
5508 oldnp = &(x2a->tbl[i]);
5509 h = strhash(oldnp->key) & (arrSize-1);
5510 newnp = &(array.tbl[i]);
5511 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
5512 newnp->next = array.ht[h];
5513 newnp->key = oldnp->key;
5514 newnp->data = oldnp->data;
5515 newnp->from = &(array.ht[h]);
5516 array.ht[h] = newnp;
5517 }
5518 free(x2a->tbl);
5519 memcpy(x2a, &array, sizeof(array)); /* *x2a = array; */
5520 }
5521 /* Insert the new data */
5522 h = ph & (x2a->size-1);
5523 np = &(x2a->tbl[x2a->count++]);
5524 np->key = key;
5525 np->data = data;
5526 if( x2a->ht[h] ) x2a->ht[h]->from = &(np->next);
5527 np->next = x2a->ht[h];
5528 x2a->ht[h] = np;
5529 np->from = &(x2a->ht[h]);
5530 return 1;
5531 }
5532
5533 /* Return a pointer to data assigned to the given key. Return NULL
5534 ** if no such key. */
Symbol_find(const char * key)5535 struct symbol *Symbol_find(const char *key)
5536 {
5537 unsigned h;
5538 x2node *np;
5539
5540 if( x2a==0 ) return 0;
5541 h = strhash(key) & (x2a->size-1);
5542 np = x2a->ht[h];
5543 while( np ){
5544 if( strcmp(np->key,key)==0 ) break;
5545 np = np->next;
5546 }
5547 return np ? np->data : 0;
5548 }
5549
5550 /* Return the n-th data. Return NULL if n is out of range. */
Symbol_Nth(int n)5551 struct symbol *Symbol_Nth(int n)
5552 {
5553 struct symbol *data;
5554 if( x2a && n>0 && n<=x2a->count ){
5555 data = x2a->tbl[n-1].data;
5556 }else{
5557 data = 0;
5558 }
5559 return data;
5560 }
5561
5562 /* Return the size of the array */
Symbol_count()5563 int Symbol_count()
5564 {
5565 return x2a ? x2a->count : 0;
5566 }
5567
5568 /* Return an array of pointers to all data in the table.
5569 ** The array is obtained from malloc. Return NULL if memory allocation
5570 ** problems, or if the array is empty. */
Symbol_arrayof()5571 struct symbol **Symbol_arrayof()
5572 {
5573 struct symbol **array;
5574 int i,arrSize;
5575 if( x2a==0 ) return 0;
5576 arrSize = x2a->count;
5577 array = (struct symbol **)calloc(arrSize, sizeof(struct symbol *));
5578 if( array ){
5579 for(i=0; i<arrSize; i++) array[i] = x2a->tbl[i].data;
5580 }
5581 return array;
5582 }
5583
5584 /* Compare two configurations */
Configcmp(const char * _a,const char * _b)5585 int Configcmp(const char *_a,const char *_b)
5586 {
5587 const struct config *a = (struct config *) _a;
5588 const struct config *b = (struct config *) _b;
5589 int x;
5590 x = a->rp->index - b->rp->index;
5591 if( x==0 ) x = a->dot - b->dot;
5592 return x;
5593 }
5594
5595 /* Compare two states */
statecmp(struct config * a,struct config * b)5596 PRIVATE int statecmp(struct config *a, struct config *b)
5597 {
5598 int rc;
5599 for(rc=0; rc==0 && a && b; a=a->bp, b=b->bp){
5600 rc = a->rp->index - b->rp->index;
5601 if( rc==0 ) rc = a->dot - b->dot;
5602 }
5603 if( rc==0 ){
5604 if( a ) rc = 1;
5605 if( b ) rc = -1;
5606 }
5607 return rc;
5608 }
5609
5610 /* Hash a state */
statehash(struct config * a)5611 PRIVATE unsigned statehash(struct config *a)
5612 {
5613 unsigned h=0;
5614 while( a ){
5615 h = h*571 + a->rp->index*37 + a->dot;
5616 a = a->bp;
5617 }
5618 return h;
5619 }
5620
5621 /* Allocate a new state structure */
State_new()5622 struct state *State_new()
5623 {
5624 struct state *newstate;
5625 newstate = (struct state *)calloc(1, sizeof(struct state) );
5626 MemoryCheck(newstate);
5627 return newstate;
5628 }
5629
5630 /* There is one instance of the following structure for each
5631 ** associative array of type "x3".
5632 */
5633 struct s_x3 {
5634 int size; /* The number of available slots. */
5635 /* Must be a power of 2 greater than or */
5636 /* equal to 1 */
5637 int count; /* Number of currently slots filled */
5638 struct s_x3node *tbl; /* The data stored here */
5639 struct s_x3node **ht; /* Hash table for lookups */
5640 };
5641
5642 /* There is one instance of this structure for every data element
5643 ** in an associative array of type "x3".
5644 */
5645 typedef struct s_x3node {
5646 struct state *data; /* The data */
5647 struct config *key; /* The key */
5648 struct s_x3node *next; /* Next entry with the same hash */
5649 struct s_x3node **from; /* Previous link */
5650 } x3node;
5651
5652 /* There is only one instance of the array, which is the following */
5653 static struct s_x3 *x3a;
5654
5655 /* Allocate a new associative array */
State_init(void)5656 void State_init(void){
5657 if( x3a ) return;
5658 x3a = (struct s_x3*)malloc( sizeof(struct s_x3) );
5659 if( x3a ){
5660 x3a->size = 128;
5661 x3a->count = 0;
5662 x3a->tbl = (x3node*)calloc(128, sizeof(x3node) + sizeof(x3node*));
5663 if( x3a->tbl==0 ){
5664 free(x3a);
5665 x3a = 0;
5666 }else{
5667 int i;
5668 x3a->ht = (x3node**)&(x3a->tbl[128]);
5669 for(i=0; i<128; i++) x3a->ht[i] = 0;
5670 }
5671 }
5672 }
5673 /* Insert a new record into the array. Return TRUE if successful.
5674 ** Prior data with the same key is NOT overwritten */
State_insert(struct state * data,struct config * key)5675 int State_insert(struct state *data, struct config *key)
5676 {
5677 x3node *np;
5678 unsigned h;
5679 unsigned ph;
5680
5681 if( x3a==0 ) return 0;
5682 ph = statehash(key);
5683 h = ph & (x3a->size-1);
5684 np = x3a->ht[h];
5685 while( np ){
5686 if( statecmp(np->key,key)==0 ){
5687 /* An existing entry with the same key is found. */
5688 /* Fail because overwrite is not allows. */
5689 return 0;
5690 }
5691 np = np->next;
5692 }
5693 if( x3a->count>=x3a->size ){
5694 /* Need to make the hash table bigger */
5695 int i,arrSize;
5696 struct s_x3 array;
5697 array.size = arrSize = x3a->size*2;
5698 array.count = x3a->count;
5699 array.tbl = (x3node*)calloc(arrSize, sizeof(x3node) + sizeof(x3node*));
5700 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
5701 array.ht = (x3node**)&(array.tbl[arrSize]);
5702 for(i=0; i<arrSize; i++) array.ht[i] = 0;
5703 for(i=0; i<x3a->count; i++){
5704 x3node *oldnp, *newnp;
5705 oldnp = &(x3a->tbl[i]);
5706 h = statehash(oldnp->key) & (arrSize-1);
5707 newnp = &(array.tbl[i]);
5708 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
5709 newnp->next = array.ht[h];
5710 newnp->key = oldnp->key;
5711 newnp->data = oldnp->data;
5712 newnp->from = &(array.ht[h]);
5713 array.ht[h] = newnp;
5714 }
5715 free(x3a->tbl);
5716 memcpy(x3a, &array, sizeof(array)); /* *x3a = array; */
5717 }
5718 /* Insert the new data */
5719 h = ph & (x3a->size-1);
5720 np = &(x3a->tbl[x3a->count++]);
5721 np->key = key;
5722 np->data = data;
5723 if( x3a->ht[h] ) x3a->ht[h]->from = &(np->next);
5724 np->next = x3a->ht[h];
5725 x3a->ht[h] = np;
5726 np->from = &(x3a->ht[h]);
5727 return 1;
5728 }
5729
5730 /* Return a pointer to data assigned to the given key. Return NULL
5731 ** if no such key. */
State_find(struct config * key)5732 struct state *State_find(struct config *key)
5733 {
5734 unsigned h;
5735 x3node *np;
5736
5737 if( x3a==0 ) return 0;
5738 h = statehash(key) & (x3a->size-1);
5739 np = x3a->ht[h];
5740 while( np ){
5741 if( statecmp(np->key,key)==0 ) break;
5742 np = np->next;
5743 }
5744 return np ? np->data : 0;
5745 }
5746
5747 /* Return an array of pointers to all data in the table.
5748 ** The array is obtained from malloc. Return NULL if memory allocation
5749 ** problems, or if the array is empty. */
State_arrayof(void)5750 struct state **State_arrayof(void)
5751 {
5752 struct state **array;
5753 int i,arrSize;
5754 if( x3a==0 ) return 0;
5755 arrSize = x3a->count;
5756 array = (struct state **)calloc(arrSize, sizeof(struct state *));
5757 if( array ){
5758 for(i=0; i<arrSize; i++) array[i] = x3a->tbl[i].data;
5759 }
5760 return array;
5761 }
5762
5763 /* Hash a configuration */
confighash(struct config * a)5764 PRIVATE unsigned confighash(struct config *a)
5765 {
5766 unsigned h=0;
5767 h = h*571 + a->rp->index*37 + a->dot;
5768 return h;
5769 }
5770
5771 /* There is one instance of the following structure for each
5772 ** associative array of type "x4".
5773 */
5774 struct s_x4 {
5775 int size; /* The number of available slots. */
5776 /* Must be a power of 2 greater than or */
5777 /* equal to 1 */
5778 int count; /* Number of currently slots filled */
5779 struct s_x4node *tbl; /* The data stored here */
5780 struct s_x4node **ht; /* Hash table for lookups */
5781 };
5782
5783 /* There is one instance of this structure for every data element
5784 ** in an associative array of type "x4".
5785 */
5786 typedef struct s_x4node {
5787 struct config *data; /* The data */
5788 struct s_x4node *next; /* Next entry with the same hash */
5789 struct s_x4node **from; /* Previous link */
5790 } x4node;
5791
5792 /* There is only one instance of the array, which is the following */
5793 static struct s_x4 *x4a;
5794
5795 /* Allocate a new associative array */
Configtable_init(void)5796 void Configtable_init(void){
5797 if( x4a ) return;
5798 x4a = (struct s_x4*)malloc( sizeof(struct s_x4) );
5799 if( x4a ){
5800 x4a->size = 64;
5801 x4a->count = 0;
5802 x4a->tbl = (x4node*)calloc(64, sizeof(x4node) + sizeof(x4node*));
5803 if( x4a->tbl==0 ){
5804 free(x4a);
5805 x4a = 0;
5806 }else{
5807 int i;
5808 x4a->ht = (x4node**)&(x4a->tbl[64]);
5809 for(i=0; i<64; i++) x4a->ht[i] = 0;
5810 }
5811 }
5812 }
5813 /* Insert a new record into the array. Return TRUE if successful.
5814 ** Prior data with the same key is NOT overwritten */
Configtable_insert(struct config * data)5815 int Configtable_insert(struct config *data)
5816 {
5817 x4node *np;
5818 unsigned h;
5819 unsigned ph;
5820
5821 if( x4a==0 ) return 0;
5822 ph = confighash(data);
5823 h = ph & (x4a->size-1);
5824 np = x4a->ht[h];
5825 while( np ){
5826 if( Configcmp((const char *) np->data,(const char *) data)==0 ){
5827 /* An existing entry with the same key is found. */
5828 /* Fail because overwrite is not allows. */
5829 return 0;
5830 }
5831 np = np->next;
5832 }
5833 if( x4a->count>=x4a->size ){
5834 /* Need to make the hash table bigger */
5835 int i,arrSize;
5836 struct s_x4 array;
5837 array.size = arrSize = x4a->size*2;
5838 array.count = x4a->count;
5839 array.tbl = (x4node*)calloc(arrSize, sizeof(x4node) + sizeof(x4node*));
5840 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
5841 array.ht = (x4node**)&(array.tbl[arrSize]);
5842 for(i=0; i<arrSize; i++) array.ht[i] = 0;
5843 for(i=0; i<x4a->count; i++){
5844 x4node *oldnp, *newnp;
5845 oldnp = &(x4a->tbl[i]);
5846 h = confighash(oldnp->data) & (arrSize-1);
5847 newnp = &(array.tbl[i]);
5848 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
5849 newnp->next = array.ht[h];
5850 newnp->data = oldnp->data;
5851 newnp->from = &(array.ht[h]);
5852 array.ht[h] = newnp;
5853 }
5854 free(x4a->tbl);
5855 memcpy(x4a, &array, sizeof(array)); /* *x4a = array; */
5856 }
5857 /* Insert the new data */
5858 h = ph & (x4a->size-1);
5859 np = &(x4a->tbl[x4a->count++]);
5860 np->data = data;
5861 if( x4a->ht[h] ) x4a->ht[h]->from = &(np->next);
5862 np->next = x4a->ht[h];
5863 x4a->ht[h] = np;
5864 np->from = &(x4a->ht[h]);
5865 return 1;
5866 }
5867
5868 /* Return a pointer to data assigned to the given key. Return NULL
5869 ** if no such key. */
Configtable_find(struct config * key)5870 struct config *Configtable_find(struct config *key)
5871 {
5872 int h;
5873 x4node *np;
5874
5875 if( x4a==0 ) return 0;
5876 h = confighash(key) & (x4a->size-1);
5877 np = x4a->ht[h];
5878 while( np ){
5879 if( Configcmp((const char *) np->data,(const char *) key)==0 ) break;
5880 np = np->next;
5881 }
5882 return np ? np->data : 0;
5883 }
5884
5885 /* Remove all data from the table. Pass each data to the function "f"
5886 ** as it is removed. ("f" may be null to avoid this step.) */
Configtable_clear(int (* f)(struct config *))5887 void Configtable_clear(int(*f)(struct config *))
5888 {
5889 int i;
5890 if( x4a==0 || x4a->count==0 ) return;
5891 if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
5892 for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;
5893 x4a->count = 0;
5894 return;
5895 }
5896