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