blob: 122ab970c53a4eadd91b362f061af140b1c0cd33 [file] [log] [blame]
drh75897232000-05-29 14:26:00 +00001/*
drh75897232000-05-29 14:26:00 +00002** This file contains all sources (including headers) to the LEMON
3** LALR(1) parser generator. The sources have been combined into a
drh960e8c62001-04-03 16:53:21 +00004** single file to make it easy to include LEMON in the source tree
5** and Makefile of another program.
drh75897232000-05-29 14:26:00 +00006**
drhb19a2bc2001-09-16 00:13:26 +00007** The author of this program disclaims copyright.
drh75897232000-05-29 14:26:00 +00008*/
9#include <stdio.h>
drhf9a2e7b2003-04-15 01:49:48 +000010#include <stdarg.h>
drh75897232000-05-29 14:26:00 +000011#include <string.h>
12#include <ctype.h>
drh8b582012003-10-21 13:16:03 +000013#include <stdlib.h>
drhe9278182007-07-18 18:16:29 +000014#include <assert.h>
drh75897232000-05-29 14:26:00 +000015
drh75897232000-05-29 14:26:00 +000016#ifndef __WIN32__
17# if defined(_WIN32) || defined(WIN32)
18# define __WIN32__
19# endif
20#endif
21
rse8f304482007-07-30 18:31:53 +000022#ifdef __WIN32__
23extern int access();
24#else
25#include <unistd.h>
26#endif
27
drh75897232000-05-29 14:26:00 +000028/* #define PRIVATE static */
29#define PRIVATE
30
31#ifdef TEST
32#define MAXRHS 5 /* Set low to exercise exception code */
33#else
34#define MAXRHS 1000
35#endif
36
drhe9278182007-07-18 18:16:29 +000037static char *msort(char*,char**,int(*)(const char*,const char*));
drh75897232000-05-29 14:26:00 +000038
drh87cf1372008-08-13 20:09:06 +000039/*
40** Compilers are getting increasingly pedantic about type conversions
41** as C evolves ever closer to Ada.... To work around the latest problems
42** we have to define the following variant of strlen().
43*/
44#define lemonStrlen(X) ((int)strlen(X))
45
drhe9278182007-07-18 18:16:29 +000046static struct action *Action_new(void);
47static struct action *Action_sort(struct action *);
drh75897232000-05-29 14:26:00 +000048
49/********** From the file "build.h" ************************************/
50void FindRulePrecedences();
51void FindFirstSets();
52void FindStates();
53void FindLinks();
54void FindFollowSets();
55void FindActions();
56
57/********* From the file "configlist.h" *********************************/
58void Configlist_init(/* void */);
59struct config *Configlist_add(/* struct rule *, int */);
60struct config *Configlist_addbasis(/* struct rule *, int */);
61void Configlist_closure(/* void */);
62void Configlist_sort(/* void */);
63void Configlist_sortbasis(/* void */);
64struct config *Configlist_return(/* void */);
65struct config *Configlist_basis(/* void */);
66void Configlist_eat(/* struct config * */);
67void Configlist_reset(/* void */);
68
69/********* From the file "error.h" ***************************************/
drhf9a2e7b2003-04-15 01:49:48 +000070void ErrorMsg(const char *, int,const char *, ...);
drh75897232000-05-29 14:26:00 +000071
72/****** From the file "option.h" ******************************************/
73struct s_options {
74 enum { OPT_FLAG=1, OPT_INT, OPT_DBL, OPT_STR,
75 OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;
76 char *label;
77 char *arg;
78 char *message;
79};
drhb0c86772000-06-02 23:21:26 +000080int OptInit(/* char**,struct s_options*,FILE* */);
81int OptNArgs(/* void */);
82char *OptArg(/* int */);
83void OptErr(/* int */);
84void OptPrint(/* void */);
drh75897232000-05-29 14:26:00 +000085
86/******** From the file "parse.h" *****************************************/
87void Parse(/* struct lemon *lemp */);
88
89/********* From the file "plink.h" ***************************************/
90struct plink *Plink_new(/* void */);
91void Plink_add(/* struct plink **, struct config * */);
92void Plink_copy(/* struct plink **, struct plink * */);
93void Plink_delete(/* struct plink * */);
94
95/********** From the file "report.h" *************************************/
96void Reprint(/* struct lemon * */);
97void ReportOutput(/* struct lemon * */);
98void ReportTable(/* struct lemon * */);
99void ReportHeader(/* struct lemon * */);
100void CompressTables(/* struct lemon * */);
drhada354d2005-11-05 15:03:59 +0000101void ResortStates(/* struct lemon * */);
drh75897232000-05-29 14:26:00 +0000102
103/********** From the file "set.h" ****************************************/
104void SetSize(/* int N */); /* All sets will be of size N */
105char *SetNew(/* void */); /* A new set for element 0..N */
106void SetFree(/* char* */); /* Deallocate a set */
107
108int SetAdd(/* char*,int */); /* Add element to a set */
109int SetUnion(/* char *A,char *B */); /* A <- A U B, thru element N */
110
111#define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
112
113/********** From the file "struct.h" *************************************/
114/*
115** Principal data structures for the LEMON parser generator.
116*/
117
drhaa9f1122007-08-23 02:50:56 +0000118typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;
drh75897232000-05-29 14:26:00 +0000119
120/* Symbols (terminals and nonterminals) of the grammar are stored
121** in the following: */
122struct symbol {
123 char *name; /* Name of the symbol */
124 int index; /* Index number for this symbol */
125 enum {
126 TERMINAL,
drhfd405312005-11-06 04:06:59 +0000127 NONTERMINAL,
128 MULTITERMINAL
drh75897232000-05-29 14:26:00 +0000129 } type; /* Symbols are all either TERMINALS or NTs */
130 struct rule *rule; /* Linked list of rules of this (if an NT) */
drh0bd1f4e2002-06-06 18:54:39 +0000131 struct symbol *fallback; /* fallback token in case this token doesn't parse */
drh75897232000-05-29 14:26:00 +0000132 int prec; /* Precedence if defined (-1 otherwise) */
133 enum e_assoc {
134 LEFT,
135 RIGHT,
136 NONE,
137 UNK
drh34ff57b2008-07-14 12:27:51 +0000138 } assoc; /* Associativity if precedence is defined */
drh75897232000-05-29 14:26:00 +0000139 char *firstset; /* First-set for all rules of this symbol */
140 Boolean lambda; /* True if NT and can generate an empty string */
drhc4dd3fd2008-01-22 01:48:05 +0000141 int useCnt; /* Number of times used */
drh75897232000-05-29 14:26:00 +0000142 char *destructor; /* Code which executes whenever this symbol is
143 ** popped from the stack during error processing */
drh4dc8ef52008-07-01 17:13:57 +0000144 int destLineno; /* Line number for start of destructor */
drh75897232000-05-29 14:26:00 +0000145 char *datatype; /* The data type of information held by this
146 ** object. Only used if type==NONTERMINAL */
147 int dtnum; /* The data type number. In the parser, the value
148 ** stack is a union. The .yy%d element of this
149 ** union is the correct data type for this object */
drhfd405312005-11-06 04:06:59 +0000150 /* The following fields are used by MULTITERMINALs only */
151 int nsubsym; /* Number of constituent symbols in the MULTI */
152 struct symbol **subsym; /* Array of constituent symbols */
drh75897232000-05-29 14:26:00 +0000153};
154
155/* Each production rule in the grammar is stored in the following
156** structure. */
157struct rule {
158 struct symbol *lhs; /* Left-hand side of the rule */
159 char *lhsalias; /* Alias for the LHS (NULL if none) */
drhb4960992007-10-05 16:16:36 +0000160 int lhsStart; /* True if left-hand side is the start symbol */
drh75897232000-05-29 14:26:00 +0000161 int ruleline; /* Line number for the rule */
162 int nrhs; /* Number of RHS symbols */
163 struct symbol **rhs; /* The RHS symbols */
164 char **rhsalias; /* An alias for each RHS symbol (NULL if none) */
165 int line; /* Line number at which code begins */
166 char *code; /* The code executed when this rule is reduced */
167 struct symbol *precsym; /* Precedence symbol for this rule */
168 int index; /* An index number for this rule */
169 Boolean canReduce; /* True if this rule is ever reduced */
170 struct rule *nextlhs; /* Next rule with the same LHS */
171 struct rule *next; /* Next rule in the global list */
172};
173
174/* A configuration is a production rule of the grammar together with
175** a mark (dot) showing how much of that rule has been processed so far.
176** Configurations also contain a follow-set which is a list of terminal
177** symbols which are allowed to immediately follow the end of the rule.
178** Every configuration is recorded as an instance of the following: */
179struct config {
180 struct rule *rp; /* The rule upon which the configuration is based */
181 int dot; /* The parse point */
182 char *fws; /* Follow-set for this configuration only */
183 struct plink *fplp; /* Follow-set forward propagation links */
184 struct plink *bplp; /* Follow-set backwards propagation links */
185 struct state *stp; /* Pointer to state which contains this */
186 enum {
187 COMPLETE, /* The status is used during followset and */
188 INCOMPLETE /* shift computations */
189 } status;
190 struct config *next; /* Next configuration in the state */
191 struct config *bp; /* The next basis configuration */
192};
193
194/* Every shift or reduce operation is stored as one of the following */
195struct action {
196 struct symbol *sp; /* The look-ahead symbol */
197 enum e_action {
198 SHIFT,
199 ACCEPT,
200 REDUCE,
201 ERROR,
drh9892c5d2007-12-21 00:02:11 +0000202 SSCONFLICT, /* A shift/shift conflict */
203 SRCONFLICT, /* Was a reduce, but part of a conflict */
204 RRCONFLICT, /* Was a reduce, but part of a conflict */
drh75897232000-05-29 14:26:00 +0000205 SH_RESOLVED, /* Was a shift. Precedence resolved conflict */
206 RD_RESOLVED, /* Was reduce. Precedence resolved conflict */
207 NOT_USED /* Deleted by compression */
208 } type;
209 union {
210 struct state *stp; /* The new state, if a shift */
211 struct rule *rp; /* The rule, if a reduce */
212 } x;
213 struct action *next; /* Next action for this state */
214 struct action *collide; /* Next action with the same hash */
215};
216
217/* Each state of the generated parser's finite state machine
218** is encoded as an instance of the following structure. */
219struct state {
220 struct config *bp; /* The basis configurations for this state */
221 struct config *cfp; /* All configurations in this set */
drh34ff57b2008-07-14 12:27:51 +0000222 int statenum; /* Sequential number for this state */
drh75897232000-05-29 14:26:00 +0000223 struct action *ap; /* Array of actions for this state */
drh8b582012003-10-21 13:16:03 +0000224 int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */
225 int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */
226 int iDflt; /* Default action */
drh75897232000-05-29 14:26:00 +0000227};
drh8b582012003-10-21 13:16:03 +0000228#define NO_OFFSET (-2147483647)
drh75897232000-05-29 14:26:00 +0000229
230/* A followset propagation link indicates that the contents of one
231** configuration followset should be propagated to another whenever
232** the first changes. */
233struct plink {
234 struct config *cfp; /* The configuration to which linked */
235 struct plink *next; /* The next propagate link */
236};
237
238/* The state vector for the entire parser generator is recorded as
239** follows. (LEMON uses no global variables and makes little use of
240** static variables. Fields in the following structure can be thought
241** of as begin global variables in the program.) */
242struct lemon {
243 struct state **sorted; /* Table of states sorted by state number */
244 struct rule *rule; /* List of all rules */
245 int nstate; /* Number of states */
246 int nrule; /* Number of rules */
247 int nsymbol; /* Number of terminal and nonterminal symbols */
248 int nterminal; /* Number of terminal symbols */
249 struct symbol **symbols; /* Sorted array of pointers to symbols */
250 int errorcnt; /* Number of errors */
251 struct symbol *errsym; /* The error symbol */
drhe09daa92006-06-10 13:29:31 +0000252 struct symbol *wildcard; /* Token that matches anything */
drh75897232000-05-29 14:26:00 +0000253 char *name; /* Name of the generated parser */
254 char *arg; /* Declaration of the 3th argument to parser */
255 char *tokentype; /* Type of terminal symbols in the parser stack */
drh960e8c62001-04-03 16:53:21 +0000256 char *vartype; /* The default type of non-terminal symbols */
drh75897232000-05-29 14:26:00 +0000257 char *start; /* Name of the start symbol for the grammar */
258 char *stacksize; /* Size of the parser stack */
259 char *include; /* Code to put at the start of the C file */
drh75897232000-05-29 14:26:00 +0000260 char *error; /* Code to execute when an error is seen */
drh75897232000-05-29 14:26:00 +0000261 char *overflow; /* Code to execute on a stack overflow */
drh75897232000-05-29 14:26:00 +0000262 char *failure; /* Code to execute on parser failure */
drh75897232000-05-29 14:26:00 +0000263 char *accept; /* Code to execute when the parser excepts */
drh75897232000-05-29 14:26:00 +0000264 char *extracode; /* Code appended to the generated file */
drh75897232000-05-29 14:26:00 +0000265 char *tokendest; /* Code to execute to destroy token data */
drh960e8c62001-04-03 16:53:21 +0000266 char *vardest; /* Code for the default non-terminal destructor */
drh75897232000-05-29 14:26:00 +0000267 char *filename; /* Name of the input file */
268 char *outname; /* Name of the current output file */
269 char *tokenprefix; /* A prefix added to token names in the .h file */
270 int nconflict; /* Number of parsing conflicts */
icculus42585cf2010-02-14 05:19:56 +0000271 int nexpected; /* Number of expected parsing conflicts */
drh75897232000-05-29 14:26:00 +0000272 int tablesize; /* Size of the parse tables */
273 int basisflag; /* Print only basis configurations */
drh34ff57b2008-07-14 12:27:51 +0000274 int has_fallback; /* True if any %fallback is seen in the grammar */
shane58543932008-12-10 20:10:04 +0000275 int nolinenosflag; /* True if #line statements should not be printed */
drh75897232000-05-29 14:26:00 +0000276 char *argv0; /* Name of the program */
277};
278
279#define MemoryCheck(X) if((X)==0){ \
280 extern void memory_error(); \
281 memory_error(); \
282}
283
284/**************** From the file "table.h" *********************************/
285/*
286** All code in this file has been automatically generated
287** from a specification in the file
288** "table.q"
289** by the associative array code building program "aagen".
290** Do not edit this file! Instead, edit the specification
291** file, then rerun aagen.
292*/
293/*
294** Code for processing tables in the LEMON parser generator.
295*/
296
297/* Routines for handling a strings */
298
299char *Strsafe();
300
301void Strsafe_init(/* void */);
302int Strsafe_insert(/* char * */);
303char *Strsafe_find(/* char * */);
304
305/* Routines for handling symbols of the grammar */
306
307struct symbol *Symbol_new();
308int Symbolcmpp(/* struct symbol **, struct symbol ** */);
309void Symbol_init(/* void */);
310int Symbol_insert(/* struct symbol *, char * */);
311struct symbol *Symbol_find(/* char * */);
312struct symbol *Symbol_Nth(/* int */);
313int Symbol_count(/* */);
314struct symbol **Symbol_arrayof(/* */);
315
316/* Routines to manage the state table */
317
318int Configcmp(/* struct config *, struct config * */);
319struct state *State_new();
320void State_init(/* void */);
321int State_insert(/* struct state *, struct config * */);
322struct state *State_find(/* struct config * */);
323struct state **State_arrayof(/* */);
324
325/* Routines used for efficiency in Configlist_add */
326
327void Configtable_init(/* void */);
328int Configtable_insert(/* struct config * */);
329struct config *Configtable_find(/* struct config * */);
330void Configtable_clear(/* int(*)(struct config *) */);
331/****************** From the file "action.c" *******************************/
332/*
333** Routines processing parser actions in the LEMON parser generator.
334*/
335
336/* Allocate a new parser action */
drhe9278182007-07-18 18:16:29 +0000337static struct action *Action_new(void){
drh75897232000-05-29 14:26:00 +0000338 static struct action *freelist = 0;
339 struct action *new;
340
341 if( freelist==0 ){
342 int i;
343 int amt = 100;
drh9892c5d2007-12-21 00:02:11 +0000344 freelist = (struct action *)calloc(amt, sizeof(struct action));
drh75897232000-05-29 14:26:00 +0000345 if( freelist==0 ){
346 fprintf(stderr,"Unable to allocate memory for a new parser action.");
347 exit(1);
348 }
349 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
350 freelist[amt-1].next = 0;
351 }
352 new = freelist;
353 freelist = freelist->next;
354 return new;
355}
356
drhe9278182007-07-18 18:16:29 +0000357/* Compare two actions for sorting purposes. Return negative, zero, or
358** positive if the first action is less than, equal to, or greater than
359** the first
360*/
361static int actioncmp(
362 struct action *ap1,
363 struct action *ap2
364){
drh75897232000-05-29 14:26:00 +0000365 int rc;
366 rc = ap1->sp->index - ap2->sp->index;
drh75897232000-05-29 14:26:00 +0000367 if( rc==0 ){
drh9892c5d2007-12-21 00:02:11 +0000368 rc = (int)ap1->type - (int)ap2->type;
369 }
370 if( rc==0 && ap1->type==REDUCE ){
drh75897232000-05-29 14:26:00 +0000371 rc = ap1->x.rp->index - ap2->x.rp->index;
372 }
drhe594bc32009-11-03 13:02:25 +0000373 if( rc==0 ){
374 rc = ap2 - ap1;
375 }
drh75897232000-05-29 14:26:00 +0000376 return rc;
377}
378
379/* Sort parser actions */
drhe9278182007-07-18 18:16:29 +0000380static struct action *Action_sort(
381 struct action *ap
382){
383 ap = (struct action *)msort((char *)ap,(char **)&ap->next,
384 (int(*)(const char*,const char*))actioncmp);
drh75897232000-05-29 14:26:00 +0000385 return ap;
386}
387
388void Action_add(app,type,sp,arg)
389struct action **app;
390enum e_action type;
391struct symbol *sp;
392char *arg;
393{
394 struct action *new;
395 new = Action_new();
396 new->next = *app;
397 *app = new;
398 new->type = type;
399 new->sp = sp;
400 if( type==SHIFT ){
401 new->x.stp = (struct state *)arg;
402 }else{
403 new->x.rp = (struct rule *)arg;
404 }
405}
drh8b582012003-10-21 13:16:03 +0000406/********************** New code to implement the "acttab" module ***********/
407/*
408** This module implements routines use to construct the yy_action[] table.
409*/
410
411/*
412** The state of the yy_action table under construction is an instance of
drh8dc3e8f2010-01-07 03:53:03 +0000413** the following structure.
414**
415** The yy_action table maps the pair (state_number, lookahead) into an
416** action_number. The table is an array of integers pairs. The state_number
417** determines an initial offset into the yy_action array. The lookahead
418** value is then added to this initial offset to get an index X into the
419** yy_action array. If the aAction[X].lookahead equals the value of the
420** of the lookahead input, then the value of the action_number output is
421** aAction[X].action. If the lookaheads do not match then the
422** default action for the state_number is returned.
423**
424** All actions associated with a single state_number are first entered
425** into aLookahead[] using multiple calls to acttab_action(). Then the
426** actions for that single state_number are placed into the aAction[]
427** array with a single call to acttab_insert(). The acttab_insert() call
428** also resets the aLookahead[] array in preparation for the next
429** state number.
drh8b582012003-10-21 13:16:03 +0000430*/
431typedef struct acttab acttab;
432struct acttab {
433 int nAction; /* Number of used slots in aAction[] */
434 int nActionAlloc; /* Slots allocated for aAction[] */
435 struct {
436 int lookahead; /* Value of the lookahead token */
437 int action; /* Action to take on the given lookahead */
438 } *aAction, /* The yy_action[] table under construction */
439 *aLookahead; /* A single new transaction set */
440 int mnLookahead; /* Minimum aLookahead[].lookahead */
441 int mnAction; /* Action associated with mnLookahead */
442 int mxLookahead; /* Maximum aLookahead[].lookahead */
443 int nLookahead; /* Used slots in aLookahead[] */
444 int nLookaheadAlloc; /* Slots allocated in aLookahead[] */
445};
446
447/* Return the number of entries in the yy_action table */
448#define acttab_size(X) ((X)->nAction)
449
450/* The value for the N-th entry in yy_action */
451#define acttab_yyaction(X,N) ((X)->aAction[N].action)
452
453/* The value for the N-th entry in yy_lookahead */
454#define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
455
456/* Free all memory associated with the given acttab */
457void acttab_free(acttab *p){
458 free( p->aAction );
459 free( p->aLookahead );
460 free( p );
461}
462
463/* Allocate a new acttab structure */
464acttab *acttab_alloc(void){
drh9892c5d2007-12-21 00:02:11 +0000465 acttab *p = calloc( 1, sizeof(*p) );
drh8b582012003-10-21 13:16:03 +0000466 if( p==0 ){
467 fprintf(stderr,"Unable to allocate memory for a new acttab.");
468 exit(1);
469 }
470 memset(p, 0, sizeof(*p));
471 return p;
472}
473
drh8dc3e8f2010-01-07 03:53:03 +0000474/* Add a new action to the current transaction set.
475**
476** This routine is called once for each lookahead for a particular
477** state.
drh8b582012003-10-21 13:16:03 +0000478*/
479void acttab_action(acttab *p, int lookahead, int action){
480 if( p->nLookahead>=p->nLookaheadAlloc ){
481 p->nLookaheadAlloc += 25;
482 p->aLookahead = realloc( p->aLookahead,
483 sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
484 if( p->aLookahead==0 ){
485 fprintf(stderr,"malloc failed\n");
486 exit(1);
487 }
488 }
489 if( p->nLookahead==0 ){
490 p->mxLookahead = lookahead;
491 p->mnLookahead = lookahead;
492 p->mnAction = action;
493 }else{
494 if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
495 if( p->mnLookahead>lookahead ){
496 p->mnLookahead = lookahead;
497 p->mnAction = action;
498 }
499 }
500 p->aLookahead[p->nLookahead].lookahead = lookahead;
501 p->aLookahead[p->nLookahead].action = action;
502 p->nLookahead++;
503}
504
505/*
506** Add the transaction set built up with prior calls to acttab_action()
507** into the current action table. Then reset the transaction set back
508** to an empty set in preparation for a new round of acttab_action() calls.
509**
510** Return the offset into the action table of the new transaction.
511*/
512int acttab_insert(acttab *p){
513 int i, j, k, n;
514 assert( p->nLookahead>0 );
515
516 /* Make sure we have enough space to hold the expanded action table
517 ** in the worst case. The worst case occurs if the transaction set
518 ** must be appended to the current action table
519 */
drh784d86f2004-02-19 18:41:53 +0000520 n = p->mxLookahead + 1;
drh8dc3e8f2010-01-07 03:53:03 +0000521 if( p->nAction + n >= p->nActionAlloc ){
drhfdbf9282003-10-21 16:34:41 +0000522 int oldAlloc = p->nActionAlloc;
drh8b582012003-10-21 13:16:03 +0000523 p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
524 p->aAction = realloc( p->aAction,
525 sizeof(p->aAction[0])*p->nActionAlloc);
526 if( p->aAction==0 ){
527 fprintf(stderr,"malloc failed\n");
528 exit(1);
529 }
drhfdbf9282003-10-21 16:34:41 +0000530 for(i=oldAlloc; i<p->nActionAlloc; i++){
drh8b582012003-10-21 13:16:03 +0000531 p->aAction[i].lookahead = -1;
532 p->aAction[i].action = -1;
533 }
534 }
535
drh8dc3e8f2010-01-07 03:53:03 +0000536 /* Scan the existing action table looking for an offset that is a
537 ** duplicate of the current transaction set. Fall out of the loop
538 ** if and when the duplicate is found.
drh8b582012003-10-21 13:16:03 +0000539 **
540 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
541 */
drh8dc3e8f2010-01-07 03:53:03 +0000542 for(i=p->nAction-1; i>=0; i--){
drhf16371d2009-11-03 19:18:31 +0000543 if( p->aAction[i].lookahead==p->mnLookahead ){
drh8dc3e8f2010-01-07 03:53:03 +0000544 /* All lookaheads and actions in the aLookahead[] transaction
545 ** must match against the candidate aAction[i] entry. */
drh8b582012003-10-21 13:16:03 +0000546 if( p->aAction[i].action!=p->mnAction ) continue;
547 for(j=0; j<p->nLookahead; j++){
548 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
549 if( k<0 || k>=p->nAction ) break;
550 if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
551 if( p->aLookahead[j].action!=p->aAction[k].action ) break;
552 }
553 if( j<p->nLookahead ) continue;
drh8dc3e8f2010-01-07 03:53:03 +0000554
555 /* No possible lookahead value that is not in the aLookahead[]
556 ** transaction is allowed to match aAction[i] */
drh8b582012003-10-21 13:16:03 +0000557 n = 0;
558 for(j=0; j<p->nAction; j++){
drhfdbf9282003-10-21 16:34:41 +0000559 if( p->aAction[j].lookahead<0 ) continue;
560 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
drh8b582012003-10-21 13:16:03 +0000561 }
drhfdbf9282003-10-21 16:34:41 +0000562 if( n==p->nLookahead ){
drh8dc3e8f2010-01-07 03:53:03 +0000563 break; /* An exact match is found at offset i */
drhfdbf9282003-10-21 16:34:41 +0000564 }
drh8b582012003-10-21 13:16:03 +0000565 }
566 }
drh8dc3e8f2010-01-07 03:53:03 +0000567
568 /* If no existing offsets exactly match the current transaction, find an
569 ** an empty offset in the aAction[] table in which we can add the
570 ** aLookahead[] transaction.
571 */
drhf16371d2009-11-03 19:18:31 +0000572 if( i<0 ){
drh8dc3e8f2010-01-07 03:53:03 +0000573 /* Look for holes in the aAction[] table that fit the current
574 ** aLookahead[] transaction. Leave i set to the offset of the hole.
575 ** If no holes are found, i is left at p->nAction, which means the
576 ** transaction will be appended. */
577 for(i=0; i<p->nActionAlloc - p->mxLookahead; i++){
drhf16371d2009-11-03 19:18:31 +0000578 if( p->aAction[i].lookahead<0 ){
579 for(j=0; j<p->nLookahead; j++){
580 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
581 if( k<0 ) break;
582 if( p->aAction[k].lookahead>=0 ) break;
583 }
584 if( j<p->nLookahead ) continue;
585 for(j=0; j<p->nAction; j++){
586 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
587 }
588 if( j==p->nAction ){
589 break; /* Fits in empty slots */
590 }
591 }
592 }
593 }
drh8b582012003-10-21 13:16:03 +0000594 /* Insert transaction set at index i. */
595 for(j=0; j<p->nLookahead; j++){
596 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
597 p->aAction[k] = p->aLookahead[j];
598 if( k>=p->nAction ) p->nAction = k+1;
599 }
600 p->nLookahead = 0;
601
602 /* Return the offset that is added to the lookahead in order to get the
603 ** index into yy_action of the action */
604 return i - p->mnLookahead;
605}
606
drh75897232000-05-29 14:26:00 +0000607/********************** From the file "build.c" *****************************/
608/*
609** Routines to construction the finite state machine for the LEMON
610** parser generator.
611*/
612
613/* Find a precedence symbol of every rule in the grammar.
614**
615** Those rules which have a precedence symbol coded in the input
616** grammar using the "[symbol]" construct will already have the
617** rp->precsym field filled. Other rules take as their precedence
618** symbol the first RHS symbol with a defined precedence. If there
619** are not RHS symbols with a defined precedence, the precedence
620** symbol field is left blank.
621*/
622void FindRulePrecedences(xp)
623struct lemon *xp;
624{
625 struct rule *rp;
626 for(rp=xp->rule; rp; rp=rp->next){
627 if( rp->precsym==0 ){
drhfd405312005-11-06 04:06:59 +0000628 int i, j;
629 for(i=0; i<rp->nrhs && rp->precsym==0; i++){
630 struct symbol *sp = rp->rhs[i];
631 if( sp->type==MULTITERMINAL ){
632 for(j=0; j<sp->nsubsym; j++){
633 if( sp->subsym[j]->prec>=0 ){
634 rp->precsym = sp->subsym[j];
635 break;
636 }
637 }
638 }else if( sp->prec>=0 ){
drh75897232000-05-29 14:26:00 +0000639 rp->precsym = rp->rhs[i];
drh75897232000-05-29 14:26:00 +0000640 }
641 }
642 }
643 }
644 return;
645}
646
647/* Find all nonterminals which will generate the empty string.
648** Then go back and compute the first sets of every nonterminal.
649** The first set is the set of all terminal symbols which can begin
650** a string generated by that nonterminal.
651*/
652void FindFirstSets(lemp)
653struct lemon *lemp;
654{
drhfd405312005-11-06 04:06:59 +0000655 int i, j;
drh75897232000-05-29 14:26:00 +0000656 struct rule *rp;
657 int progress;
658
659 for(i=0; i<lemp->nsymbol; i++){
drhaa9f1122007-08-23 02:50:56 +0000660 lemp->symbols[i]->lambda = LEMON_FALSE;
drh75897232000-05-29 14:26:00 +0000661 }
662 for(i=lemp->nterminal; i<lemp->nsymbol; i++){
663 lemp->symbols[i]->firstset = SetNew();
664 }
665
666 /* First compute all lambdas */
667 do{
668 progress = 0;
669 for(rp=lemp->rule; rp; rp=rp->next){
670 if( rp->lhs->lambda ) continue;
671 for(i=0; i<rp->nrhs; i++){
drhfd405312005-11-06 04:06:59 +0000672 struct symbol *sp = rp->rhs[i];
drhaa9f1122007-08-23 02:50:56 +0000673 if( sp->type!=TERMINAL || sp->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +0000674 }
675 if( i==rp->nrhs ){
drhaa9f1122007-08-23 02:50:56 +0000676 rp->lhs->lambda = LEMON_TRUE;
drh75897232000-05-29 14:26:00 +0000677 progress = 1;
678 }
679 }
680 }while( progress );
681
682 /* Now compute all first sets */
683 do{
684 struct symbol *s1, *s2;
685 progress = 0;
686 for(rp=lemp->rule; rp; rp=rp->next){
687 s1 = rp->lhs;
688 for(i=0; i<rp->nrhs; i++){
689 s2 = rp->rhs[i];
690 if( s2->type==TERMINAL ){
691 progress += SetAdd(s1->firstset,s2->index);
692 break;
drhfd405312005-11-06 04:06:59 +0000693 }else if( s2->type==MULTITERMINAL ){
694 for(j=0; j<s2->nsubsym; j++){
695 progress += SetAdd(s1->firstset,s2->subsym[j]->index);
696 }
697 break;
drh75897232000-05-29 14:26:00 +0000698 }else if( s1==s2 ){
drhaa9f1122007-08-23 02:50:56 +0000699 if( s1->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +0000700 }else{
701 progress += SetUnion(s1->firstset,s2->firstset);
drhaa9f1122007-08-23 02:50:56 +0000702 if( s2->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +0000703 }
704 }
705 }
706 }while( progress );
707 return;
708}
709
710/* Compute all LR(0) states for the grammar. Links
711** are added to between some states so that the LR(1) follow sets
712** can be computed later.
713*/
714PRIVATE struct state *getstate(/* struct lemon * */); /* forward reference */
715void FindStates(lemp)
716struct lemon *lemp;
717{
718 struct symbol *sp;
719 struct rule *rp;
720
721 Configlist_init();
722
723 /* Find the start symbol */
724 if( lemp->start ){
725 sp = Symbol_find(lemp->start);
726 if( sp==0 ){
727 ErrorMsg(lemp->filename,0,
728"The specified start symbol \"%s\" is not \
729in a nonterminal of the grammar. \"%s\" will be used as the start \
730symbol instead.",lemp->start,lemp->rule->lhs->name);
731 lemp->errorcnt++;
732 sp = lemp->rule->lhs;
733 }
734 }else{
735 sp = lemp->rule->lhs;
736 }
737
738 /* Make sure the start symbol doesn't occur on the right-hand side of
739 ** any rule. Report an error if it does. (YACC would generate a new
740 ** start symbol in this case.) */
741 for(rp=lemp->rule; rp; rp=rp->next){
742 int i;
743 for(i=0; i<rp->nrhs; i++){
drhfd405312005-11-06 04:06:59 +0000744 if( rp->rhs[i]==sp ){ /* FIX ME: Deal with multiterminals */
drh75897232000-05-29 14:26:00 +0000745 ErrorMsg(lemp->filename,0,
746"The start symbol \"%s\" occurs on the \
747right-hand side of a rule. This will result in a parser which \
748does not work properly.",sp->name);
749 lemp->errorcnt++;
750 }
751 }
752 }
753
754 /* The basis configuration set for the first state
755 ** is all rules which have the start symbol as their
756 ** left-hand side */
757 for(rp=sp->rule; rp; rp=rp->nextlhs){
758 struct config *newcfp;
drhb4960992007-10-05 16:16:36 +0000759 rp->lhsStart = 1;
drh75897232000-05-29 14:26:00 +0000760 newcfp = Configlist_addbasis(rp,0);
761 SetAdd(newcfp->fws,0);
762 }
763
764 /* Compute the first state. All other states will be
765 ** computed automatically during the computation of the first one.
766 ** The returned pointer to the first state is not used. */
767 (void)getstate(lemp);
768 return;
769}
770
771/* Return a pointer to a state which is described by the configuration
772** list which has been built from calls to Configlist_add.
773*/
774PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */
775PRIVATE struct state *getstate(lemp)
776struct lemon *lemp;
777{
778 struct config *cfp, *bp;
779 struct state *stp;
780
781 /* Extract the sorted basis of the new state. The basis was constructed
782 ** by prior calls to "Configlist_addbasis()". */
783 Configlist_sortbasis();
784 bp = Configlist_basis();
785
786 /* Get a state with the same basis */
787 stp = State_find(bp);
788 if( stp ){
789 /* A state with the same basis already exists! Copy all the follow-set
790 ** propagation links from the state under construction into the
791 ** preexisting state, then return a pointer to the preexisting state */
792 struct config *x, *y;
793 for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
794 Plink_copy(&y->bplp,x->bplp);
795 Plink_delete(x->fplp);
796 x->fplp = x->bplp = 0;
797 }
798 cfp = Configlist_return();
799 Configlist_eat(cfp);
800 }else{
801 /* This really is a new state. Construct all the details */
802 Configlist_closure(lemp); /* Compute the configuration closure */
803 Configlist_sort(); /* Sort the configuration closure */
804 cfp = Configlist_return(); /* Get a pointer to the config list */
805 stp = State_new(); /* A new state structure */
806 MemoryCheck(stp);
807 stp->bp = bp; /* Remember the configuration basis */
808 stp->cfp = cfp; /* Remember the configuration closure */
drhada354d2005-11-05 15:03:59 +0000809 stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
drh75897232000-05-29 14:26:00 +0000810 stp->ap = 0; /* No actions, yet. */
811 State_insert(stp,stp->bp); /* Add to the state table */
812 buildshifts(lemp,stp); /* Recursively compute successor states */
813 }
814 return stp;
815}
816
drhfd405312005-11-06 04:06:59 +0000817/*
818** Return true if two symbols are the same.
819*/
820int same_symbol(a,b)
821struct symbol *a;
822struct symbol *b;
823{
824 int i;
825 if( a==b ) return 1;
826 if( a->type!=MULTITERMINAL ) return 0;
827 if( b->type!=MULTITERMINAL ) return 0;
828 if( a->nsubsym!=b->nsubsym ) return 0;
829 for(i=0; i<a->nsubsym; i++){
830 if( a->subsym[i]!=b->subsym[i] ) return 0;
831 }
832 return 1;
833}
834
drh75897232000-05-29 14:26:00 +0000835/* Construct all successor states to the given state. A "successor"
836** state is any state which can be reached by a shift action.
837*/
838PRIVATE void buildshifts(lemp,stp)
839struct lemon *lemp;
840struct state *stp; /* The state from which successors are computed */
841{
842 struct config *cfp; /* For looping thru the config closure of "stp" */
843 struct config *bcfp; /* For the inner loop on config closure of "stp" */
844 struct config *new; /* */
845 struct symbol *sp; /* Symbol following the dot in configuration "cfp" */
846 struct symbol *bsp; /* Symbol following the dot in configuration "bcfp" */
847 struct state *newstp; /* A pointer to a successor state */
848
849 /* Each configuration becomes complete after it contibutes to a successor
850 ** state. Initially, all configurations are incomplete */
851 for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
852
853 /* Loop through all configurations of the state "stp" */
854 for(cfp=stp->cfp; cfp; cfp=cfp->next){
855 if( cfp->status==COMPLETE ) continue; /* Already used by inner loop */
856 if( cfp->dot>=cfp->rp->nrhs ) continue; /* Can't shift this config */
857 Configlist_reset(); /* Reset the new config set */
858 sp = cfp->rp->rhs[cfp->dot]; /* Symbol after the dot */
859
860 /* For every configuration in the state "stp" which has the symbol "sp"
861 ** following its dot, add the same configuration to the basis set under
862 ** construction but with the dot shifted one symbol to the right. */
863 for(bcfp=cfp; bcfp; bcfp=bcfp->next){
864 if( bcfp->status==COMPLETE ) continue; /* Already used */
865 if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
866 bsp = bcfp->rp->rhs[bcfp->dot]; /* Get symbol after dot */
drhfd405312005-11-06 04:06:59 +0000867 if( !same_symbol(bsp,sp) ) continue; /* Must be same as for "cfp" */
drh75897232000-05-29 14:26:00 +0000868 bcfp->status = COMPLETE; /* Mark this config as used */
869 new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
870 Plink_add(&new->bplp,bcfp);
871 }
872
873 /* Get a pointer to the state described by the basis configuration set
874 ** constructed in the preceding loop */
875 newstp = getstate(lemp);
876
877 /* The state "newstp" is reached from the state "stp" by a shift action
878 ** on the symbol "sp" */
drhfd405312005-11-06 04:06:59 +0000879 if( sp->type==MULTITERMINAL ){
880 int i;
881 for(i=0; i<sp->nsubsym; i++){
882 Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
883 }
884 }else{
885 Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
886 }
drh75897232000-05-29 14:26:00 +0000887 }
888}
889
890/*
891** Construct the propagation links
892*/
893void FindLinks(lemp)
894struct lemon *lemp;
895{
896 int i;
897 struct config *cfp, *other;
898 struct state *stp;
899 struct plink *plp;
900
901 /* Housekeeping detail:
902 ** Add to every propagate link a pointer back to the state to
903 ** which the link is attached. */
904 for(i=0; i<lemp->nstate; i++){
905 stp = lemp->sorted[i];
906 for(cfp=stp->cfp; cfp; cfp=cfp->next){
907 cfp->stp = stp;
908 }
909 }
910
911 /* Convert all backlinks into forward links. Only the forward
912 ** links are used in the follow-set computation. */
913 for(i=0; i<lemp->nstate; i++){
914 stp = lemp->sorted[i];
915 for(cfp=stp->cfp; cfp; cfp=cfp->next){
916 for(plp=cfp->bplp; plp; plp=plp->next){
917 other = plp->cfp;
918 Plink_add(&other->fplp,cfp);
919 }
920 }
921 }
922}
923
924/* Compute all followsets.
925**
926** A followset is the set of all symbols which can come immediately
927** after a configuration.
928*/
929void FindFollowSets(lemp)
930struct lemon *lemp;
931{
932 int i;
933 struct config *cfp;
934 struct plink *plp;
935 int progress;
936 int change;
937
938 for(i=0; i<lemp->nstate; i++){
939 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
940 cfp->status = INCOMPLETE;
941 }
942 }
943
944 do{
945 progress = 0;
946 for(i=0; i<lemp->nstate; i++){
947 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
948 if( cfp->status==COMPLETE ) continue;
949 for(plp=cfp->fplp; plp; plp=plp->next){
950 change = SetUnion(plp->cfp->fws,cfp->fws);
951 if( change ){
952 plp->cfp->status = INCOMPLETE;
953 progress = 1;
954 }
955 }
956 cfp->status = COMPLETE;
957 }
958 }
959 }while( progress );
960}
961
962static int resolve_conflict();
963
964/* Compute the reduce actions, and resolve conflicts.
965*/
966void FindActions(lemp)
967struct lemon *lemp;
968{
969 int i,j;
970 struct config *cfp;
971 struct state *stp;
972 struct symbol *sp;
973 struct rule *rp;
974
975 /* Add all of the reduce actions
976 ** A reduce action is added for each element of the followset of
977 ** a configuration which has its dot at the extreme right.
978 */
979 for(i=0; i<lemp->nstate; i++){ /* Loop over all states */
980 stp = lemp->sorted[i];
981 for(cfp=stp->cfp; cfp; cfp=cfp->next){ /* Loop over all configurations */
982 if( cfp->rp->nrhs==cfp->dot ){ /* Is dot at extreme right? */
983 for(j=0; j<lemp->nterminal; j++){
984 if( SetFind(cfp->fws,j) ){
985 /* Add a reduce action to the state "stp" which will reduce by the
986 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
drh218dc692004-05-31 23:13:45 +0000987 Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
drh75897232000-05-29 14:26:00 +0000988 }
989 }
990 }
991 }
992 }
993
994 /* Add the accepting token */
995 if( lemp->start ){
996 sp = Symbol_find(lemp->start);
997 if( sp==0 ) sp = lemp->rule->lhs;
998 }else{
999 sp = lemp->rule->lhs;
1000 }
1001 /* Add to the first state (which is always the starting state of the
1002 ** finite state machine) an action to ACCEPT if the lookahead is the
1003 ** start nonterminal. */
1004 Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
1005
1006 /* Resolve conflicts */
1007 for(i=0; i<lemp->nstate; i++){
1008 struct action *ap, *nap;
1009 struct state *stp;
1010 stp = lemp->sorted[i];
drhe9278182007-07-18 18:16:29 +00001011 /* assert( stp->ap ); */
drh75897232000-05-29 14:26:00 +00001012 stp->ap = Action_sort(stp->ap);
drhb59499c2002-02-23 18:45:13 +00001013 for(ap=stp->ap; ap && ap->next; ap=ap->next){
drh75897232000-05-29 14:26:00 +00001014 for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
1015 /* The two actions "ap" and "nap" have the same lookahead.
1016 ** Figure out which one should be used */
1017 lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
1018 }
1019 }
1020 }
1021
1022 /* Report an error for each rule that can never be reduced. */
drhaa9f1122007-08-23 02:50:56 +00001023 for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;
drh75897232000-05-29 14:26:00 +00001024 for(i=0; i<lemp->nstate; i++){
1025 struct action *ap;
1026 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
drhaa9f1122007-08-23 02:50:56 +00001027 if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;
drh75897232000-05-29 14:26:00 +00001028 }
1029 }
1030 for(rp=lemp->rule; rp; rp=rp->next){
1031 if( rp->canReduce ) continue;
1032 ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
1033 lemp->errorcnt++;
1034 }
1035}
1036
1037/* Resolve a conflict between the two given actions. If the
drh34ff57b2008-07-14 12:27:51 +00001038** conflict can't be resolved, return non-zero.
drh75897232000-05-29 14:26:00 +00001039**
1040** NO LONGER TRUE:
1041** To resolve a conflict, first look to see if either action
1042** is on an error rule. In that case, take the action which
1043** is not associated with the error rule. If neither or both
1044** actions are associated with an error rule, then try to
1045** use precedence to resolve the conflict.
1046**
1047** If either action is a SHIFT, then it must be apx. This
1048** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1049*/
1050static int resolve_conflict(apx,apy,errsym)
1051struct action *apx;
1052struct action *apy;
1053struct symbol *errsym; /* The error symbol (if defined. NULL otherwise) */
1054{
1055 struct symbol *spx, *spy;
1056 int errcnt = 0;
1057 assert( apx->sp==apy->sp ); /* Otherwise there would be no conflict */
drhf0fa1c12006-12-14 01:06:22 +00001058 if( apx->type==SHIFT && apy->type==SHIFT ){
drh9892c5d2007-12-21 00:02:11 +00001059 apy->type = SSCONFLICT;
drhf0fa1c12006-12-14 01:06:22 +00001060 errcnt++;
1061 }
drh75897232000-05-29 14:26:00 +00001062 if( apx->type==SHIFT && apy->type==REDUCE ){
1063 spx = apx->sp;
1064 spy = apy->x.rp->precsym;
1065 if( spy==0 || spx->prec<0 || spy->prec<0 ){
1066 /* Not enough precedence information. */
drh9892c5d2007-12-21 00:02:11 +00001067 apy->type = SRCONFLICT;
drh75897232000-05-29 14:26:00 +00001068 errcnt++;
1069 }else if( spx->prec>spy->prec ){ /* Lower precedence wins */
1070 apy->type = RD_RESOLVED;
1071 }else if( spx->prec<spy->prec ){
1072 apx->type = SH_RESOLVED;
1073 }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
1074 apy->type = RD_RESOLVED; /* associativity */
1075 }else if( spx->prec==spy->prec && spx->assoc==LEFT ){ /* to break tie */
1076 apx->type = SH_RESOLVED;
1077 }else{
1078 assert( spx->prec==spy->prec && spx->assoc==NONE );
drh9892c5d2007-12-21 00:02:11 +00001079 apy->type = SRCONFLICT;
drh75897232000-05-29 14:26:00 +00001080 errcnt++;
1081 }
1082 }else if( apx->type==REDUCE && apy->type==REDUCE ){
1083 spx = apx->x.rp->precsym;
1084 spy = apy->x.rp->precsym;
1085 if( spx==0 || spy==0 || spx->prec<0 ||
1086 spy->prec<0 || spx->prec==spy->prec ){
drh9892c5d2007-12-21 00:02:11 +00001087 apy->type = RRCONFLICT;
drh75897232000-05-29 14:26:00 +00001088 errcnt++;
1089 }else if( spx->prec>spy->prec ){
1090 apy->type = RD_RESOLVED;
1091 }else if( spx->prec<spy->prec ){
1092 apx->type = RD_RESOLVED;
1093 }
1094 }else{
drhb59499c2002-02-23 18:45:13 +00001095 assert(
1096 apx->type==SH_RESOLVED ||
1097 apx->type==RD_RESOLVED ||
drh9892c5d2007-12-21 00:02:11 +00001098 apx->type==SSCONFLICT ||
1099 apx->type==SRCONFLICT ||
1100 apx->type==RRCONFLICT ||
drhb59499c2002-02-23 18:45:13 +00001101 apy->type==SH_RESOLVED ||
1102 apy->type==RD_RESOLVED ||
drh9892c5d2007-12-21 00:02:11 +00001103 apy->type==SSCONFLICT ||
1104 apy->type==SRCONFLICT ||
1105 apy->type==RRCONFLICT
drhb59499c2002-02-23 18:45:13 +00001106 );
1107 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1108 ** REDUCEs on the list. If we reach this point it must be because
1109 ** the parser conflict had already been resolved. */
drh75897232000-05-29 14:26:00 +00001110 }
1111 return errcnt;
1112}
1113/********************* From the file "configlist.c" *************************/
1114/*
1115** Routines to processing a configuration list and building a state
1116** in the LEMON parser generator.
1117*/
1118
1119static struct config *freelist = 0; /* List of free configurations */
1120static struct config *current = 0; /* Top of list of configurations */
1121static struct config **currentend = 0; /* Last on list of configs */
1122static struct config *basis = 0; /* Top of list of basis configs */
1123static struct config **basisend = 0; /* End of list of basis configs */
1124
1125/* Return a pointer to a new configuration */
1126PRIVATE struct config *newconfig(){
1127 struct config *new;
1128 if( freelist==0 ){
1129 int i;
1130 int amt = 3;
drh9892c5d2007-12-21 00:02:11 +00001131 freelist = (struct config *)calloc( amt, sizeof(struct config) );
drh75897232000-05-29 14:26:00 +00001132 if( freelist==0 ){
1133 fprintf(stderr,"Unable to allocate memory for a new configuration.");
1134 exit(1);
1135 }
1136 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
1137 freelist[amt-1].next = 0;
1138 }
1139 new = freelist;
1140 freelist = freelist->next;
1141 return new;
1142}
1143
1144/* The configuration "old" is no longer used */
1145PRIVATE void deleteconfig(old)
1146struct config *old;
1147{
1148 old->next = freelist;
1149 freelist = old;
1150}
1151
1152/* Initialized the configuration list builder */
1153void Configlist_init(){
1154 current = 0;
1155 currentend = &current;
1156 basis = 0;
1157 basisend = &basis;
1158 Configtable_init();
1159 return;
1160}
1161
1162/* Initialized the configuration list builder */
1163void Configlist_reset(){
1164 current = 0;
1165 currentend = &current;
1166 basis = 0;
1167 basisend = &basis;
1168 Configtable_clear(0);
1169 return;
1170}
1171
1172/* Add another configuration to the configuration list */
1173struct config *Configlist_add(rp,dot)
1174struct rule *rp; /* The rule */
1175int dot; /* Index into the RHS of the rule where the dot goes */
1176{
1177 struct config *cfp, model;
1178
1179 assert( currentend!=0 );
1180 model.rp = rp;
1181 model.dot = dot;
1182 cfp = Configtable_find(&model);
1183 if( cfp==0 ){
1184 cfp = newconfig();
1185 cfp->rp = rp;
1186 cfp->dot = dot;
1187 cfp->fws = SetNew();
1188 cfp->stp = 0;
1189 cfp->fplp = cfp->bplp = 0;
1190 cfp->next = 0;
1191 cfp->bp = 0;
1192 *currentend = cfp;
1193 currentend = &cfp->next;
1194 Configtable_insert(cfp);
1195 }
1196 return cfp;
1197}
1198
1199/* Add a basis configuration to the configuration list */
1200struct config *Configlist_addbasis(rp,dot)
1201struct rule *rp;
1202int dot;
1203{
1204 struct config *cfp, model;
1205
1206 assert( basisend!=0 );
1207 assert( currentend!=0 );
1208 model.rp = rp;
1209 model.dot = dot;
1210 cfp = Configtable_find(&model);
1211 if( cfp==0 ){
1212 cfp = newconfig();
1213 cfp->rp = rp;
1214 cfp->dot = dot;
1215 cfp->fws = SetNew();
1216 cfp->stp = 0;
1217 cfp->fplp = cfp->bplp = 0;
1218 cfp->next = 0;
1219 cfp->bp = 0;
1220 *currentend = cfp;
1221 currentend = &cfp->next;
1222 *basisend = cfp;
1223 basisend = &cfp->bp;
1224 Configtable_insert(cfp);
1225 }
1226 return cfp;
1227}
1228
1229/* Compute the closure of the configuration list */
1230void Configlist_closure(lemp)
1231struct lemon *lemp;
1232{
1233 struct config *cfp, *newcfp;
1234 struct rule *rp, *newrp;
1235 struct symbol *sp, *xsp;
1236 int i, dot;
1237
1238 assert( currentend!=0 );
1239 for(cfp=current; cfp; cfp=cfp->next){
1240 rp = cfp->rp;
1241 dot = cfp->dot;
1242 if( dot>=rp->nrhs ) continue;
1243 sp = rp->rhs[dot];
1244 if( sp->type==NONTERMINAL ){
1245 if( sp->rule==0 && sp!=lemp->errsym ){
1246 ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",
1247 sp->name);
1248 lemp->errorcnt++;
1249 }
1250 for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
1251 newcfp = Configlist_add(newrp,0);
1252 for(i=dot+1; i<rp->nrhs; i++){
1253 xsp = rp->rhs[i];
1254 if( xsp->type==TERMINAL ){
1255 SetAdd(newcfp->fws,xsp->index);
1256 break;
drhfd405312005-11-06 04:06:59 +00001257 }else if( xsp->type==MULTITERMINAL ){
1258 int k;
1259 for(k=0; k<xsp->nsubsym; k++){
1260 SetAdd(newcfp->fws, xsp->subsym[k]->index);
1261 }
1262 break;
drh75897232000-05-29 14:26:00 +00001263 }else{
1264 SetUnion(newcfp->fws,xsp->firstset);
drhaa9f1122007-08-23 02:50:56 +00001265 if( xsp->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +00001266 }
1267 }
1268 if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);
1269 }
1270 }
1271 }
1272 return;
1273}
1274
1275/* Sort the configuration list */
1276void Configlist_sort(){
drh218dc692004-05-31 23:13:45 +00001277 current = (struct config *)msort((char *)current,(char **)&(current->next),Configcmp);
drh75897232000-05-29 14:26:00 +00001278 currentend = 0;
1279 return;
1280}
1281
1282/* Sort the basis configuration list */
1283void Configlist_sortbasis(){
drh218dc692004-05-31 23:13:45 +00001284 basis = (struct config *)msort((char *)current,(char **)&(current->bp),Configcmp);
drh75897232000-05-29 14:26:00 +00001285 basisend = 0;
1286 return;
1287}
1288
1289/* Return a pointer to the head of the configuration list and
1290** reset the list */
1291struct config *Configlist_return(){
1292 struct config *old;
1293 old = current;
1294 current = 0;
1295 currentend = 0;
1296 return old;
1297}
1298
1299/* Return a pointer to the head of the configuration list and
1300** reset the list */
1301struct config *Configlist_basis(){
1302 struct config *old;
1303 old = basis;
1304 basis = 0;
1305 basisend = 0;
1306 return old;
1307}
1308
1309/* Free all elements of the given configuration list */
1310void Configlist_eat(cfp)
1311struct config *cfp;
1312{
1313 struct config *nextcfp;
1314 for(; cfp; cfp=nextcfp){
1315 nextcfp = cfp->next;
1316 assert( cfp->fplp==0 );
1317 assert( cfp->bplp==0 );
1318 if( cfp->fws ) SetFree(cfp->fws);
1319 deleteconfig(cfp);
1320 }
1321 return;
1322}
1323/***************** From the file "error.c" *********************************/
1324/*
1325** Code for printing error message.
1326*/
1327
1328/* Find a good place to break "msg" so that its length is at least "min"
1329** but no more than "max". Make the point as close to max as possible.
1330*/
1331static int findbreak(msg,min,max)
1332char *msg;
1333int min;
1334int max;
1335{
1336 int i,spot;
1337 char c;
1338 for(i=spot=min; i<=max; i++){
1339 c = msg[i];
1340 if( c=='\t' ) msg[i] = ' ';
1341 if( c=='\n' ){ msg[i] = ' '; spot = i; break; }
1342 if( c==0 ){ spot = i; break; }
1343 if( c=='-' && i<max-1 ) spot = i+1;
1344 if( c==' ' ) spot = i;
1345 }
1346 return spot;
1347}
1348
1349/*
1350** The error message is split across multiple lines if necessary. The
1351** splits occur at a space, if there is a space available near the end
1352** of the line.
1353*/
1354#define ERRMSGSIZE 10000 /* Hope this is big enough. No way to error check */
1355#define LINEWIDTH 79 /* Max width of any output line */
1356#define PREFIXLIMIT 30 /* Max width of the prefix on each line */
drhf9a2e7b2003-04-15 01:49:48 +00001357void ErrorMsg(const char *filename, int lineno, const char *format, ...){
drh75897232000-05-29 14:26:00 +00001358 char errmsg[ERRMSGSIZE];
1359 char prefix[PREFIXLIMIT+10];
1360 int errmsgsize;
1361 int prefixsize;
1362 int availablewidth;
1363 va_list ap;
1364 int end, restart, base;
1365
drhf9a2e7b2003-04-15 01:49:48 +00001366 va_start(ap, format);
drh75897232000-05-29 14:26:00 +00001367 /* Prepare a prefix to be prepended to every output line */
1368 if( lineno>0 ){
1369 sprintf(prefix,"%.*s:%d: ",PREFIXLIMIT-10,filename,lineno);
1370 }else{
1371 sprintf(prefix,"%.*s: ",PREFIXLIMIT-10,filename);
1372 }
drh87cf1372008-08-13 20:09:06 +00001373 prefixsize = lemonStrlen(prefix);
drh75897232000-05-29 14:26:00 +00001374 availablewidth = LINEWIDTH - prefixsize;
1375
1376 /* Generate the error message */
1377 vsprintf(errmsg,format,ap);
1378 va_end(ap);
drh87cf1372008-08-13 20:09:06 +00001379 errmsgsize = lemonStrlen(errmsg);
drh75897232000-05-29 14:26:00 +00001380 /* Remove trailing '\n's from the error message. */
1381 while( errmsgsize>0 && errmsg[errmsgsize-1]=='\n' ){
1382 errmsg[--errmsgsize] = 0;
1383 }
1384
1385 /* Print the error message */
1386 base = 0;
1387 while( errmsg[base]!=0 ){
1388 end = restart = findbreak(&errmsg[base],0,availablewidth);
1389 restart += base;
1390 while( errmsg[restart]==' ' ) restart++;
1391 fprintf(stdout,"%s%.*s\n",prefix,end,&errmsg[base]);
1392 base = restart;
1393 }
1394}
1395/**************** From the file "main.c" ************************************/
1396/*
1397** Main program file for the LEMON parser generator.
1398*/
1399
1400/* Report an out-of-memory condition and abort. This function
1401** is used mostly by the "MemoryCheck" macro in struct.h
1402*/
1403void memory_error(){
1404 fprintf(stderr,"Out of memory. Aborting...\n");
1405 exit(1);
1406}
1407
drh6d08b4d2004-07-20 12:45:22 +00001408static int nDefine = 0; /* Number of -D options on the command line */
1409static char **azDefine = 0; /* Name of the -D macros */
1410
1411/* This routine is called with the argument to each -D command-line option.
1412** Add the macro defined to the azDefine array.
1413*/
1414static void handle_D_option(char *z){
1415 char **paz;
1416 nDefine++;
1417 azDefine = realloc(azDefine, sizeof(azDefine[0])*nDefine);
1418 if( azDefine==0 ){
1419 fprintf(stderr,"out of memory\n");
1420 exit(1);
1421 }
1422 paz = &azDefine[nDefine-1];
drh87cf1372008-08-13 20:09:06 +00001423 *paz = malloc( lemonStrlen(z)+1 );
drh6d08b4d2004-07-20 12:45:22 +00001424 if( *paz==0 ){
1425 fprintf(stderr,"out of memory\n");
1426 exit(1);
1427 }
1428 strcpy(*paz, z);
1429 for(z=*paz; *z && *z!='='; z++){}
1430 *z = 0;
1431}
1432
icculus3e143bd2010-02-14 00:48:49 +00001433static char *user_templatename = NULL;
1434static void handle_T_option(char *z){
1435 user_templatename = malloc( lemonStrlen(z)+1 );
1436 if( user_templatename==0 ){
1437 memory_error();
1438 }
1439 strcpy(user_templatename, z);
1440}
drh75897232000-05-29 14:26:00 +00001441
1442/* The main program. Parse the command line and do it... */
1443int main(argc,argv)
1444int argc;
1445char **argv;
1446{
1447 static int version = 0;
1448 static int rpflag = 0;
1449 static int basisflag = 0;
1450 static int compress = 0;
1451 static int quiet = 0;
1452 static int statistics = 0;
1453 static int mhflag = 0;
shane58543932008-12-10 20:10:04 +00001454 static int nolinenosflag = 0;
drh75897232000-05-29 14:26:00 +00001455 static struct s_options options[] = {
1456 {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
1457 {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
drh6d08b4d2004-07-20 12:45:22 +00001458 {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
icculus3e143bd2010-02-14 00:48:49 +00001459 {OPT_FSTR, "T", (char*)handle_T_option, "Specify a template file."},
drh75897232000-05-29 14:26:00 +00001460 {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
shane58543932008-12-10 20:10:04 +00001461 {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file."},
1462 {OPT_FLAG, "l", (char*)&nolinenosflag, "Do not print #line statements."},
drh75897232000-05-29 14:26:00 +00001463 {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
drh6d08b4d2004-07-20 12:45:22 +00001464 {OPT_FLAG, "s", (char*)&statistics,
1465 "Print parser stats to standard output."},
drh75897232000-05-29 14:26:00 +00001466 {OPT_FLAG, "x", (char*)&version, "Print the version number."},
1467 {OPT_FLAG,0,0,0}
1468 };
1469 int i;
icculus42585cf2010-02-14 05:19:56 +00001470 int exitcode;
drh75897232000-05-29 14:26:00 +00001471 struct lemon lem;
1472
drhb0c86772000-06-02 23:21:26 +00001473 OptInit(argv,options,stderr);
drh75897232000-05-29 14:26:00 +00001474 if( version ){
drhb19a2bc2001-09-16 00:13:26 +00001475 printf("Lemon version 1.0\n");
drh75897232000-05-29 14:26:00 +00001476 exit(0);
1477 }
drhb0c86772000-06-02 23:21:26 +00001478 if( OptNArgs()!=1 ){
drh75897232000-05-29 14:26:00 +00001479 fprintf(stderr,"Exactly one filename argument is required.\n");
1480 exit(1);
1481 }
drh954f6b42006-06-13 13:27:46 +00001482 memset(&lem, 0, sizeof(lem));
drh75897232000-05-29 14:26:00 +00001483 lem.errorcnt = 0;
icculus42585cf2010-02-14 05:19:56 +00001484 lem.nexpected = -1;
drh75897232000-05-29 14:26:00 +00001485
1486 /* Initialize the machine */
1487 Strsafe_init();
1488 Symbol_init();
1489 State_init();
1490 lem.argv0 = argv[0];
drhb0c86772000-06-02 23:21:26 +00001491 lem.filename = OptArg(0);
drh75897232000-05-29 14:26:00 +00001492 lem.basisflag = basisflag;
shane58543932008-12-10 20:10:04 +00001493 lem.nolinenosflag = nolinenosflag;
drh75897232000-05-29 14:26:00 +00001494 Symbol_new("$");
1495 lem.errsym = Symbol_new("error");
drhc4dd3fd2008-01-22 01:48:05 +00001496 lem.errsym->useCnt = 0;
drh75897232000-05-29 14:26:00 +00001497
1498 /* Parse the input file */
1499 Parse(&lem);
1500 if( lem.errorcnt ) exit(lem.errorcnt);
drh954f6b42006-06-13 13:27:46 +00001501 if( lem.nrule==0 ){
drh75897232000-05-29 14:26:00 +00001502 fprintf(stderr,"Empty grammar.\n");
1503 exit(1);
1504 }
1505
1506 /* Count and index the symbols of the grammar */
1507 lem.nsymbol = Symbol_count();
1508 Symbol_new("{default}");
1509 lem.symbols = Symbol_arrayof();
drh60d31652004-02-22 00:08:04 +00001510 for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
drh75897232000-05-29 14:26:00 +00001511 qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*),
1512 (int(*)())Symbolcmpp);
1513 for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
1514 for(i=1; isupper(lem.symbols[i]->name[0]); i++);
1515 lem.nterminal = i;
1516
1517 /* Generate a reprint of the grammar, if requested on the command line */
1518 if( rpflag ){
1519 Reprint(&lem);
1520 }else{
1521 /* Initialize the size for all follow and first sets */
drh9892c5d2007-12-21 00:02:11 +00001522 SetSize(lem.nterminal+1);
drh75897232000-05-29 14:26:00 +00001523
1524 /* Find the precedence for every production rule (that has one) */
1525 FindRulePrecedences(&lem);
1526
1527 /* Compute the lambda-nonterminals and the first-sets for every
1528 ** nonterminal */
1529 FindFirstSets(&lem);
1530
1531 /* Compute all LR(0) states. Also record follow-set propagation
1532 ** links so that the follow-set can be computed later */
1533 lem.nstate = 0;
1534 FindStates(&lem);
1535 lem.sorted = State_arrayof();
1536
1537 /* Tie up loose ends on the propagation links */
1538 FindLinks(&lem);
1539
1540 /* Compute the follow set of every reducible configuration */
1541 FindFollowSets(&lem);
1542
1543 /* Compute the action tables */
1544 FindActions(&lem);
1545
1546 /* Compress the action tables */
1547 if( compress==0 ) CompressTables(&lem);
1548
drhada354d2005-11-05 15:03:59 +00001549 /* Reorder and renumber the states so that states with fewer choices
1550 ** occur at the end. */
1551 ResortStates(&lem);
1552
drh75897232000-05-29 14:26:00 +00001553 /* Generate a report of the parser generated. (the "y.output" file) */
1554 if( !quiet ) ReportOutput(&lem);
1555
1556 /* Generate the source code for the parser */
1557 ReportTable(&lem, mhflag);
1558
1559 /* Produce a header file for use by the scanner. (This step is
1560 ** omitted if the "-m" option is used because makeheaders will
1561 ** generate the file for us.) */
1562 if( !mhflag ) ReportHeader(&lem);
1563 }
1564 if( statistics ){
1565 printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
1566 lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
1567 printf(" %d states, %d parser table entries, %d conflicts\n",
1568 lem.nstate, lem.tablesize, lem.nconflict);
1569 }
icculus42585cf2010-02-14 05:19:56 +00001570 if( lem.nexpected < 0 ) {
1571 lem.nexpected = 0; /* grammar didn't have an %expect declaration. */
drh75897232000-05-29 14:26:00 +00001572 }
icculus42585cf2010-02-14 05:19:56 +00001573 if( lem.nconflict != lem.nexpected ){
1574 fprintf(stderr,"%d parsing conflicts (%d expected).\n",lem.nconflict,lem.nexpected);
1575 }
1576
1577 /* return 0 on success, 1 on failure. */
1578 exitcode = ((lem.errorcnt > 0) || (lem.nconflict != lem.nexpected)) ? 1 : 0;
1579 exit(exitcode);
1580 return (exitcode);
drh75897232000-05-29 14:26:00 +00001581}
1582/******************** From the file "msort.c" *******************************/
1583/*
1584** A generic merge-sort program.
1585**
1586** USAGE:
1587** Let "ptr" be a pointer to some structure which is at the head of
1588** a null-terminated list. Then to sort the list call:
1589**
1590** ptr = msort(ptr,&(ptr->next),cmpfnc);
1591**
1592** In the above, "cmpfnc" is a pointer to a function which compares
1593** two instances of the structure and returns an integer, as in
1594** strcmp. The second argument is a pointer to the pointer to the
1595** second element of the linked list. This address is used to compute
1596** the offset to the "next" field within the structure. The offset to
1597** the "next" field must be constant for all structures in the list.
1598**
1599** The function returns a new pointer which is the head of the list
1600** after sorting.
1601**
1602** ALGORITHM:
1603** Merge-sort.
1604*/
1605
1606/*
1607** Return a pointer to the next structure in the linked list.
1608*/
drhba99af52001-10-25 20:37:16 +00001609#define NEXT(A) (*(char**)(((unsigned long)A)+offset))
drh75897232000-05-29 14:26:00 +00001610
1611/*
1612** Inputs:
1613** a: A sorted, null-terminated linked list. (May be null).
1614** b: A sorted, null-terminated linked list. (May be null).
1615** cmp: A pointer to the comparison function.
1616** offset: Offset in the structure to the "next" field.
1617**
1618** Return Value:
1619** A pointer to the head of a sorted list containing the elements
1620** of both a and b.
1621**
1622** Side effects:
1623** The "next" pointers for elements in the lists a and b are
1624** changed.
1625*/
drhe9278182007-07-18 18:16:29 +00001626static char *merge(
1627 char *a,
1628 char *b,
1629 int (*cmp)(const char*,const char*),
1630 int offset
1631){
drh75897232000-05-29 14:26:00 +00001632 char *ptr, *head;
1633
1634 if( a==0 ){
1635 head = b;
1636 }else if( b==0 ){
1637 head = a;
1638 }else{
drhe594bc32009-11-03 13:02:25 +00001639 if( (*cmp)(a,b)<=0 ){
drh75897232000-05-29 14:26:00 +00001640 ptr = a;
1641 a = NEXT(a);
1642 }else{
1643 ptr = b;
1644 b = NEXT(b);
1645 }
1646 head = ptr;
1647 while( a && b ){
drhe594bc32009-11-03 13:02:25 +00001648 if( (*cmp)(a,b)<=0 ){
drh75897232000-05-29 14:26:00 +00001649 NEXT(ptr) = a;
1650 ptr = a;
1651 a = NEXT(a);
1652 }else{
1653 NEXT(ptr) = b;
1654 ptr = b;
1655 b = NEXT(b);
1656 }
1657 }
1658 if( a ) NEXT(ptr) = a;
1659 else NEXT(ptr) = b;
1660 }
1661 return head;
1662}
1663
1664/*
1665** Inputs:
1666** list: Pointer to a singly-linked list of structures.
1667** next: Pointer to pointer to the second element of the list.
1668** cmp: A comparison function.
1669**
1670** Return Value:
1671** A pointer to the head of a sorted list containing the elements
1672** orginally in list.
1673**
1674** Side effects:
1675** The "next" pointers for elements in list are changed.
1676*/
1677#define LISTSIZE 30
drhe9278182007-07-18 18:16:29 +00001678static char *msort(
1679 char *list,
1680 char **next,
1681 int (*cmp)(const char*,const char*)
1682){
drhba99af52001-10-25 20:37:16 +00001683 unsigned long offset;
drh75897232000-05-29 14:26:00 +00001684 char *ep;
1685 char *set[LISTSIZE];
1686 int i;
drhba99af52001-10-25 20:37:16 +00001687 offset = (unsigned long)next - (unsigned long)list;
drh75897232000-05-29 14:26:00 +00001688 for(i=0; i<LISTSIZE; i++) set[i] = 0;
1689 while( list ){
1690 ep = list;
1691 list = NEXT(list);
1692 NEXT(ep) = 0;
1693 for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
1694 ep = merge(ep,set[i],cmp,offset);
1695 set[i] = 0;
1696 }
1697 set[i] = ep;
1698 }
1699 ep = 0;
drhe594bc32009-11-03 13:02:25 +00001700 for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(set[i],ep,cmp,offset);
drh75897232000-05-29 14:26:00 +00001701 return ep;
1702}
1703/************************ From the file "option.c" **************************/
1704static char **argv;
1705static struct s_options *op;
1706static FILE *errstream;
1707
1708#define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1709
1710/*
1711** Print the command line with a carrot pointing to the k-th character
1712** of the n-th field.
1713*/
1714static void errline(n,k,err)
1715int n;
1716int k;
1717FILE *err;
1718{
1719 int spcnt, i;
drh75897232000-05-29 14:26:00 +00001720 if( argv[0] ) fprintf(err,"%s",argv[0]);
drh87cf1372008-08-13 20:09:06 +00001721 spcnt = lemonStrlen(argv[0]) + 1;
drh75897232000-05-29 14:26:00 +00001722 for(i=1; i<n && argv[i]; i++){
1723 fprintf(err," %s",argv[i]);
drh87cf1372008-08-13 20:09:06 +00001724 spcnt += lemonStrlen(argv[i])+1;
drh75897232000-05-29 14:26:00 +00001725 }
1726 spcnt += k;
1727 for(; argv[i]; i++) fprintf(err," %s",argv[i]);
1728 if( spcnt<20 ){
1729 fprintf(err,"\n%*s^-- here\n",spcnt,"");
1730 }else{
1731 fprintf(err,"\n%*shere --^\n",spcnt-7,"");
1732 }
1733}
1734
1735/*
1736** Return the index of the N-th non-switch argument. Return -1
1737** if N is out of range.
1738*/
1739static int argindex(n)
1740int n;
1741{
1742 int i;
1743 int dashdash = 0;
1744 if( argv!=0 && *argv!=0 ){
1745 for(i=1; argv[i]; i++){
1746 if( dashdash || !ISOPT(argv[i]) ){
1747 if( n==0 ) return i;
1748 n--;
1749 }
1750 if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1751 }
1752 }
1753 return -1;
1754}
1755
1756static char emsg[] = "Command line syntax error: ";
1757
1758/*
1759** Process a flag command line argument.
1760*/
1761static int handleflags(i,err)
1762int i;
1763FILE *err;
1764{
1765 int v;
1766 int errcnt = 0;
1767 int j;
1768 for(j=0; op[j].label; j++){
drh87cf1372008-08-13 20:09:06 +00001769 if( strncmp(&argv[i][1],op[j].label,lemonStrlen(op[j].label))==0 ) break;
drh75897232000-05-29 14:26:00 +00001770 }
1771 v = argv[i][0]=='-' ? 1 : 0;
1772 if( op[j].label==0 ){
1773 if( err ){
1774 fprintf(err,"%sundefined option.\n",emsg);
1775 errline(i,1,err);
1776 }
1777 errcnt++;
1778 }else if( op[j].type==OPT_FLAG ){
1779 *((int*)op[j].arg) = v;
1780 }else if( op[j].type==OPT_FFLAG ){
1781 (*(void(*)())(op[j].arg))(v);
drh6d08b4d2004-07-20 12:45:22 +00001782 }else if( op[j].type==OPT_FSTR ){
1783 (*(void(*)())(op[j].arg))(&argv[i][2]);
drh75897232000-05-29 14:26:00 +00001784 }else{
1785 if( err ){
1786 fprintf(err,"%smissing argument on switch.\n",emsg);
1787 errline(i,1,err);
1788 }
1789 errcnt++;
1790 }
1791 return errcnt;
1792}
1793
1794/*
1795** Process a command line switch which has an argument.
1796*/
1797static int handleswitch(i,err)
1798int i;
1799FILE *err;
1800{
1801 int lv = 0;
1802 double dv = 0.0;
1803 char *sv = 0, *end;
1804 char *cp;
1805 int j;
1806 int errcnt = 0;
1807 cp = strchr(argv[i],'=');
drh43617e92006-03-06 20:55:46 +00001808 assert( cp!=0 );
drh75897232000-05-29 14:26:00 +00001809 *cp = 0;
1810 for(j=0; op[j].label; j++){
1811 if( strcmp(argv[i],op[j].label)==0 ) break;
1812 }
1813 *cp = '=';
1814 if( op[j].label==0 ){
1815 if( err ){
1816 fprintf(err,"%sundefined option.\n",emsg);
1817 errline(i,0,err);
1818 }
1819 errcnt++;
1820 }else{
1821 cp++;
1822 switch( op[j].type ){
1823 case OPT_FLAG:
1824 case OPT_FFLAG:
1825 if( err ){
1826 fprintf(err,"%soption requires an argument.\n",emsg);
1827 errline(i,0,err);
1828 }
1829 errcnt++;
1830 break;
1831 case OPT_DBL:
1832 case OPT_FDBL:
1833 dv = strtod(cp,&end);
1834 if( *end ){
1835 if( err ){
1836 fprintf(err,"%sillegal character in floating-point argument.\n",emsg);
drhba99af52001-10-25 20:37:16 +00001837 errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
drh75897232000-05-29 14:26:00 +00001838 }
1839 errcnt++;
1840 }
1841 break;
1842 case OPT_INT:
1843 case OPT_FINT:
1844 lv = strtol(cp,&end,0);
1845 if( *end ){
1846 if( err ){
1847 fprintf(err,"%sillegal character in integer argument.\n",emsg);
drhba99af52001-10-25 20:37:16 +00001848 errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
drh75897232000-05-29 14:26:00 +00001849 }
1850 errcnt++;
1851 }
1852 break;
1853 case OPT_STR:
1854 case OPT_FSTR:
1855 sv = cp;
1856 break;
1857 }
1858 switch( op[j].type ){
1859 case OPT_FLAG:
1860 case OPT_FFLAG:
1861 break;
1862 case OPT_DBL:
1863 *(double*)(op[j].arg) = dv;
1864 break;
1865 case OPT_FDBL:
1866 (*(void(*)())(op[j].arg))(dv);
1867 break;
1868 case OPT_INT:
1869 *(int*)(op[j].arg) = lv;
1870 break;
1871 case OPT_FINT:
1872 (*(void(*)())(op[j].arg))((int)lv);
1873 break;
1874 case OPT_STR:
1875 *(char**)(op[j].arg) = sv;
1876 break;
1877 case OPT_FSTR:
1878 (*(void(*)())(op[j].arg))(sv);
1879 break;
1880 }
1881 }
1882 return errcnt;
1883}
1884
drhb0c86772000-06-02 23:21:26 +00001885int OptInit(a,o,err)
drh75897232000-05-29 14:26:00 +00001886char **a;
1887struct s_options *o;
1888FILE *err;
1889{
1890 int errcnt = 0;
1891 argv = a;
1892 op = o;
1893 errstream = err;
1894 if( argv && *argv && op ){
1895 int i;
1896 for(i=1; argv[i]; i++){
1897 if( argv[i][0]=='+' || argv[i][0]=='-' ){
1898 errcnt += handleflags(i,err);
1899 }else if( strchr(argv[i],'=') ){
1900 errcnt += handleswitch(i,err);
1901 }
1902 }
1903 }
1904 if( errcnt>0 ){
1905 fprintf(err,"Valid command line options for \"%s\" are:\n",*a);
drhb0c86772000-06-02 23:21:26 +00001906 OptPrint();
drh75897232000-05-29 14:26:00 +00001907 exit(1);
1908 }
1909 return 0;
1910}
1911
drhb0c86772000-06-02 23:21:26 +00001912int OptNArgs(){
drh75897232000-05-29 14:26:00 +00001913 int cnt = 0;
1914 int dashdash = 0;
1915 int i;
1916 if( argv!=0 && argv[0]!=0 ){
1917 for(i=1; argv[i]; i++){
1918 if( dashdash || !ISOPT(argv[i]) ) cnt++;
1919 if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1920 }
1921 }
1922 return cnt;
1923}
1924
drhb0c86772000-06-02 23:21:26 +00001925char *OptArg(n)
drh75897232000-05-29 14:26:00 +00001926int n;
1927{
1928 int i;
1929 i = argindex(n);
1930 return i>=0 ? argv[i] : 0;
1931}
1932
drhb0c86772000-06-02 23:21:26 +00001933void OptErr(n)
drh75897232000-05-29 14:26:00 +00001934int n;
1935{
1936 int i;
1937 i = argindex(n);
1938 if( i>=0 ) errline(i,0,errstream);
1939}
1940
drhb0c86772000-06-02 23:21:26 +00001941void OptPrint(){
drh75897232000-05-29 14:26:00 +00001942 int i;
1943 int max, len;
1944 max = 0;
1945 for(i=0; op[i].label; i++){
drh87cf1372008-08-13 20:09:06 +00001946 len = lemonStrlen(op[i].label) + 1;
drh75897232000-05-29 14:26:00 +00001947 switch( op[i].type ){
1948 case OPT_FLAG:
1949 case OPT_FFLAG:
1950 break;
1951 case OPT_INT:
1952 case OPT_FINT:
1953 len += 9; /* length of "<integer>" */
1954 break;
1955 case OPT_DBL:
1956 case OPT_FDBL:
1957 len += 6; /* length of "<real>" */
1958 break;
1959 case OPT_STR:
1960 case OPT_FSTR:
1961 len += 8; /* length of "<string>" */
1962 break;
1963 }
1964 if( len>max ) max = len;
1965 }
1966 for(i=0; op[i].label; i++){
1967 switch( op[i].type ){
1968 case OPT_FLAG:
1969 case OPT_FFLAG:
1970 fprintf(errstream," -%-*s %s\n",max,op[i].label,op[i].message);
1971 break;
1972 case OPT_INT:
1973 case OPT_FINT:
1974 fprintf(errstream," %s=<integer>%*s %s\n",op[i].label,
drh87cf1372008-08-13 20:09:06 +00001975 (int)(max-lemonStrlen(op[i].label)-9),"",op[i].message);
drh75897232000-05-29 14:26:00 +00001976 break;
1977 case OPT_DBL:
1978 case OPT_FDBL:
1979 fprintf(errstream," %s=<real>%*s %s\n",op[i].label,
drh87cf1372008-08-13 20:09:06 +00001980 (int)(max-lemonStrlen(op[i].label)-6),"",op[i].message);
drh75897232000-05-29 14:26:00 +00001981 break;
1982 case OPT_STR:
1983 case OPT_FSTR:
1984 fprintf(errstream," %s=<string>%*s %s\n",op[i].label,
drh87cf1372008-08-13 20:09:06 +00001985 (int)(max-lemonStrlen(op[i].label)-8),"",op[i].message);
drh75897232000-05-29 14:26:00 +00001986 break;
1987 }
1988 }
1989}
1990/*********************** From the file "parse.c" ****************************/
1991/*
1992** Input file parser for the LEMON parser generator.
1993*/
1994
1995/* The state of the parser */
1996struct pstate {
1997 char *filename; /* Name of the input file */
1998 int tokenlineno; /* Linenumber at which current token starts */
1999 int errorcnt; /* Number of errors so far */
2000 char *tokenstart; /* Text of current token */
2001 struct lemon *gp; /* Global state vector */
2002 enum e_state {
2003 INITIALIZE,
2004 WAITING_FOR_DECL_OR_RULE,
2005 WAITING_FOR_DECL_KEYWORD,
2006 WAITING_FOR_DECL_ARG,
2007 WAITING_FOR_PRECEDENCE_SYMBOL,
2008 WAITING_FOR_ARROW,
2009 IN_RHS,
2010 LHS_ALIAS_1,
2011 LHS_ALIAS_2,
2012 LHS_ALIAS_3,
2013 RHS_ALIAS_1,
2014 RHS_ALIAS_2,
2015 PRECEDENCE_MARK_1,
2016 PRECEDENCE_MARK_2,
2017 RESYNC_AFTER_RULE_ERROR,
2018 RESYNC_AFTER_DECL_ERROR,
2019 WAITING_FOR_DESTRUCTOR_SYMBOL,
drh0bd1f4e2002-06-06 18:54:39 +00002020 WAITING_FOR_DATATYPE_SYMBOL,
drhe09daa92006-06-10 13:29:31 +00002021 WAITING_FOR_FALLBACK_ID,
icculus42585cf2010-02-14 05:19:56 +00002022 WAITING_FOR_EXPECT_VALUE,
drhe09daa92006-06-10 13:29:31 +00002023 WAITING_FOR_WILDCARD_ID
drh75897232000-05-29 14:26:00 +00002024 } state; /* The state of the parser */
drh0bd1f4e2002-06-06 18:54:39 +00002025 struct symbol *fallback; /* The fallback token */
drh75897232000-05-29 14:26:00 +00002026 struct symbol *lhs; /* Left-hand side of current rule */
2027 char *lhsalias; /* Alias for the LHS */
2028 int nrhs; /* Number of right-hand side symbols seen */
2029 struct symbol *rhs[MAXRHS]; /* RHS symbols */
2030 char *alias[MAXRHS]; /* Aliases for each RHS symbol (or NULL) */
2031 struct rule *prevrule; /* Previous rule parsed */
2032 char *declkeyword; /* Keyword of a declaration */
2033 char **declargslot; /* Where the declaration argument should be put */
drha5808f32008-04-27 22:19:44 +00002034 int insertLineMacro; /* Add #line before declaration insert */
drh4dc8ef52008-07-01 17:13:57 +00002035 int *decllinenoslot; /* Where to write declaration line number */
drh75897232000-05-29 14:26:00 +00002036 enum e_assoc declassoc; /* Assign this association to decl arguments */
2037 int preccounter; /* Assign this precedence to decl arguments */
2038 struct rule *firstrule; /* Pointer to first rule in the grammar */
2039 struct rule *lastrule; /* Pointer to the most recently parsed rule */
2040};
2041
2042/* Parse a single token */
2043static void parseonetoken(psp)
2044struct pstate *psp;
2045{
icculus42585cf2010-02-14 05:19:56 +00002046 char *endptr;
drh75897232000-05-29 14:26:00 +00002047 char *x;
2048 x = Strsafe(psp->tokenstart); /* Save the token permanently */
2049#if 0
2050 printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
2051 x,psp->state);
2052#endif
2053 switch( psp->state ){
2054 case INITIALIZE:
2055 psp->prevrule = 0;
2056 psp->preccounter = 0;
2057 psp->firstrule = psp->lastrule = 0;
2058 psp->gp->nrule = 0;
2059 /* Fall thru to next case */
2060 case WAITING_FOR_DECL_OR_RULE:
2061 if( x[0]=='%' ){
2062 psp->state = WAITING_FOR_DECL_KEYWORD;
2063 }else if( islower(x[0]) ){
2064 psp->lhs = Symbol_new(x);
2065 psp->nrhs = 0;
2066 psp->lhsalias = 0;
2067 psp->state = WAITING_FOR_ARROW;
2068 }else if( x[0]=='{' ){
2069 if( psp->prevrule==0 ){
2070 ErrorMsg(psp->filename,psp->tokenlineno,
drh34ff57b2008-07-14 12:27:51 +00002071"There is no prior rule opon which to attach the code \
drh75897232000-05-29 14:26:00 +00002072fragment which begins on this line.");
2073 psp->errorcnt++;
2074 }else if( psp->prevrule->code!=0 ){
2075 ErrorMsg(psp->filename,psp->tokenlineno,
2076"Code fragment beginning on this line is not the first \
2077to follow the previous rule.");
2078 psp->errorcnt++;
2079 }else{
2080 psp->prevrule->line = psp->tokenlineno;
2081 psp->prevrule->code = &x[1];
2082 }
2083 }else if( x[0]=='[' ){
2084 psp->state = PRECEDENCE_MARK_1;
2085 }else{
2086 ErrorMsg(psp->filename,psp->tokenlineno,
2087 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2088 x);
2089 psp->errorcnt++;
2090 }
2091 break;
2092 case PRECEDENCE_MARK_1:
2093 if( !isupper(x[0]) ){
2094 ErrorMsg(psp->filename,psp->tokenlineno,
2095 "The precedence symbol must be a terminal.");
2096 psp->errorcnt++;
2097 }else if( psp->prevrule==0 ){
2098 ErrorMsg(psp->filename,psp->tokenlineno,
2099 "There is no prior rule to assign precedence \"[%s]\".",x);
2100 psp->errorcnt++;
2101 }else if( psp->prevrule->precsym!=0 ){
2102 ErrorMsg(psp->filename,psp->tokenlineno,
2103"Precedence mark on this line is not the first \
2104to follow the previous rule.");
2105 psp->errorcnt++;
2106 }else{
2107 psp->prevrule->precsym = Symbol_new(x);
2108 }
2109 psp->state = PRECEDENCE_MARK_2;
2110 break;
2111 case PRECEDENCE_MARK_2:
2112 if( x[0]!=']' ){
2113 ErrorMsg(psp->filename,psp->tokenlineno,
2114 "Missing \"]\" on precedence mark.");
2115 psp->errorcnt++;
2116 }
2117 psp->state = WAITING_FOR_DECL_OR_RULE;
2118 break;
2119 case WAITING_FOR_ARROW:
2120 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2121 psp->state = IN_RHS;
2122 }else if( x[0]=='(' ){
2123 psp->state = LHS_ALIAS_1;
2124 }else{
2125 ErrorMsg(psp->filename,psp->tokenlineno,
2126 "Expected to see a \":\" following the LHS symbol \"%s\".",
2127 psp->lhs->name);
2128 psp->errorcnt++;
2129 psp->state = RESYNC_AFTER_RULE_ERROR;
2130 }
2131 break;
2132 case LHS_ALIAS_1:
2133 if( isalpha(x[0]) ){
2134 psp->lhsalias = x;
2135 psp->state = LHS_ALIAS_2;
2136 }else{
2137 ErrorMsg(psp->filename,psp->tokenlineno,
2138 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2139 x,psp->lhs->name);
2140 psp->errorcnt++;
2141 psp->state = RESYNC_AFTER_RULE_ERROR;
2142 }
2143 break;
2144 case LHS_ALIAS_2:
2145 if( x[0]==')' ){
2146 psp->state = LHS_ALIAS_3;
2147 }else{
2148 ErrorMsg(psp->filename,psp->tokenlineno,
2149 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2150 psp->errorcnt++;
2151 psp->state = RESYNC_AFTER_RULE_ERROR;
2152 }
2153 break;
2154 case LHS_ALIAS_3:
2155 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2156 psp->state = IN_RHS;
2157 }else{
2158 ErrorMsg(psp->filename,psp->tokenlineno,
2159 "Missing \"->\" following: \"%s(%s)\".",
2160 psp->lhs->name,psp->lhsalias);
2161 psp->errorcnt++;
2162 psp->state = RESYNC_AFTER_RULE_ERROR;
2163 }
2164 break;
2165 case IN_RHS:
2166 if( x[0]=='.' ){
2167 struct rule *rp;
drh9892c5d2007-12-21 00:02:11 +00002168 rp = (struct rule *)calloc( sizeof(struct rule) +
2169 sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs, 1);
drh75897232000-05-29 14:26:00 +00002170 if( rp==0 ){
2171 ErrorMsg(psp->filename,psp->tokenlineno,
2172 "Can't allocate enough memory for this rule.");
2173 psp->errorcnt++;
2174 psp->prevrule = 0;
2175 }else{
2176 int i;
2177 rp->ruleline = psp->tokenlineno;
2178 rp->rhs = (struct symbol**)&rp[1];
2179 rp->rhsalias = (char**)&(rp->rhs[psp->nrhs]);
2180 for(i=0; i<psp->nrhs; i++){
2181 rp->rhs[i] = psp->rhs[i];
2182 rp->rhsalias[i] = psp->alias[i];
2183 }
2184 rp->lhs = psp->lhs;
2185 rp->lhsalias = psp->lhsalias;
2186 rp->nrhs = psp->nrhs;
2187 rp->code = 0;
2188 rp->precsym = 0;
2189 rp->index = psp->gp->nrule++;
2190 rp->nextlhs = rp->lhs->rule;
2191 rp->lhs->rule = rp;
2192 rp->next = 0;
2193 if( psp->firstrule==0 ){
2194 psp->firstrule = psp->lastrule = rp;
2195 }else{
2196 psp->lastrule->next = rp;
2197 psp->lastrule = rp;
2198 }
2199 psp->prevrule = rp;
2200 }
2201 psp->state = WAITING_FOR_DECL_OR_RULE;
2202 }else if( isalpha(x[0]) ){
2203 if( psp->nrhs>=MAXRHS ){
2204 ErrorMsg(psp->filename,psp->tokenlineno,
drhc4dd3fd2008-01-22 01:48:05 +00002205 "Too many symbols on RHS of rule beginning at \"%s\".",
drh75897232000-05-29 14:26:00 +00002206 x);
2207 psp->errorcnt++;
2208 psp->state = RESYNC_AFTER_RULE_ERROR;
2209 }else{
2210 psp->rhs[psp->nrhs] = Symbol_new(x);
2211 psp->alias[psp->nrhs] = 0;
2212 psp->nrhs++;
2213 }
drhfd405312005-11-06 04:06:59 +00002214 }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 ){
2215 struct symbol *msp = psp->rhs[psp->nrhs-1];
2216 if( msp->type!=MULTITERMINAL ){
2217 struct symbol *origsp = msp;
drh9892c5d2007-12-21 00:02:11 +00002218 msp = calloc(1,sizeof(*msp));
drhfd405312005-11-06 04:06:59 +00002219 memset(msp, 0, sizeof(*msp));
2220 msp->type = MULTITERMINAL;
2221 msp->nsubsym = 1;
drh9892c5d2007-12-21 00:02:11 +00002222 msp->subsym = calloc(1,sizeof(struct symbol*));
drhfd405312005-11-06 04:06:59 +00002223 msp->subsym[0] = origsp;
2224 msp->name = origsp->name;
2225 psp->rhs[psp->nrhs-1] = msp;
2226 }
2227 msp->nsubsym++;
2228 msp->subsym = realloc(msp->subsym, sizeof(struct symbol*)*msp->nsubsym);
2229 msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);
2230 if( islower(x[1]) || islower(msp->subsym[0]->name[0]) ){
2231 ErrorMsg(psp->filename,psp->tokenlineno,
2232 "Cannot form a compound containing a non-terminal");
2233 psp->errorcnt++;
2234 }
drh75897232000-05-29 14:26:00 +00002235 }else if( x[0]=='(' && psp->nrhs>0 ){
2236 psp->state = RHS_ALIAS_1;
2237 }else{
2238 ErrorMsg(psp->filename,psp->tokenlineno,
2239 "Illegal character on RHS of rule: \"%s\".",x);
2240 psp->errorcnt++;
2241 psp->state = RESYNC_AFTER_RULE_ERROR;
2242 }
2243 break;
2244 case RHS_ALIAS_1:
2245 if( isalpha(x[0]) ){
2246 psp->alias[psp->nrhs-1] = x;
2247 psp->state = RHS_ALIAS_2;
2248 }else{
2249 ErrorMsg(psp->filename,psp->tokenlineno,
2250 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2251 x,psp->rhs[psp->nrhs-1]->name);
2252 psp->errorcnt++;
2253 psp->state = RESYNC_AFTER_RULE_ERROR;
2254 }
2255 break;
2256 case RHS_ALIAS_2:
2257 if( x[0]==')' ){
2258 psp->state = IN_RHS;
2259 }else{
2260 ErrorMsg(psp->filename,psp->tokenlineno,
2261 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2262 psp->errorcnt++;
2263 psp->state = RESYNC_AFTER_RULE_ERROR;
2264 }
2265 break;
2266 case WAITING_FOR_DECL_KEYWORD:
2267 if( isalpha(x[0]) ){
2268 psp->declkeyword = x;
2269 psp->declargslot = 0;
drh4dc8ef52008-07-01 17:13:57 +00002270 psp->decllinenoslot = 0;
drha5808f32008-04-27 22:19:44 +00002271 psp->insertLineMacro = 1;
drh75897232000-05-29 14:26:00 +00002272 psp->state = WAITING_FOR_DECL_ARG;
2273 if( strcmp(x,"name")==0 ){
2274 psp->declargslot = &(psp->gp->name);
drha5808f32008-04-27 22:19:44 +00002275 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002276 }else if( strcmp(x,"include")==0 ){
2277 psp->declargslot = &(psp->gp->include);
drh75897232000-05-29 14:26:00 +00002278 }else if( strcmp(x,"code")==0 ){
2279 psp->declargslot = &(psp->gp->extracode);
drh75897232000-05-29 14:26:00 +00002280 }else if( strcmp(x,"token_destructor")==0 ){
2281 psp->declargslot = &psp->gp->tokendest;
drh960e8c62001-04-03 16:53:21 +00002282 }else if( strcmp(x,"default_destructor")==0 ){
2283 psp->declargslot = &psp->gp->vardest;
drh75897232000-05-29 14:26:00 +00002284 }else if( strcmp(x,"token_prefix")==0 ){
2285 psp->declargslot = &psp->gp->tokenprefix;
drha5808f32008-04-27 22:19:44 +00002286 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002287 }else if( strcmp(x,"syntax_error")==0 ){
2288 psp->declargslot = &(psp->gp->error);
drh75897232000-05-29 14:26:00 +00002289 }else if( strcmp(x,"parse_accept")==0 ){
2290 psp->declargslot = &(psp->gp->accept);
drh75897232000-05-29 14:26:00 +00002291 }else if( strcmp(x,"parse_failure")==0 ){
2292 psp->declargslot = &(psp->gp->failure);
drh75897232000-05-29 14:26:00 +00002293 }else if( strcmp(x,"stack_overflow")==0 ){
2294 psp->declargslot = &(psp->gp->overflow);
drh75897232000-05-29 14:26:00 +00002295 }else if( strcmp(x,"extra_argument")==0 ){
2296 psp->declargslot = &(psp->gp->arg);
drha5808f32008-04-27 22:19:44 +00002297 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002298 }else if( strcmp(x,"token_type")==0 ){
2299 psp->declargslot = &(psp->gp->tokentype);
drha5808f32008-04-27 22:19:44 +00002300 psp->insertLineMacro = 0;
drh960e8c62001-04-03 16:53:21 +00002301 }else if( strcmp(x,"default_type")==0 ){
2302 psp->declargslot = &(psp->gp->vartype);
drha5808f32008-04-27 22:19:44 +00002303 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002304 }else if( strcmp(x,"stack_size")==0 ){
2305 psp->declargslot = &(psp->gp->stacksize);
drha5808f32008-04-27 22:19:44 +00002306 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002307 }else if( strcmp(x,"start_symbol")==0 ){
2308 psp->declargslot = &(psp->gp->start);
drha5808f32008-04-27 22:19:44 +00002309 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002310 }else if( strcmp(x,"left")==0 ){
2311 psp->preccounter++;
2312 psp->declassoc = LEFT;
2313 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2314 }else if( strcmp(x,"right")==0 ){
2315 psp->preccounter++;
2316 psp->declassoc = RIGHT;
2317 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2318 }else if( strcmp(x,"nonassoc")==0 ){
2319 psp->preccounter++;
2320 psp->declassoc = NONE;
2321 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2322 }else if( strcmp(x,"destructor")==0 ){
2323 psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;
2324 }else if( strcmp(x,"type")==0 ){
2325 psp->state = WAITING_FOR_DATATYPE_SYMBOL;
drh0bd1f4e2002-06-06 18:54:39 +00002326 }else if( strcmp(x,"fallback")==0 ){
2327 psp->fallback = 0;
2328 psp->state = WAITING_FOR_FALLBACK_ID;
drhe09daa92006-06-10 13:29:31 +00002329 }else if( strcmp(x,"wildcard")==0 ){
2330 psp->state = WAITING_FOR_WILDCARD_ID;
icculus42585cf2010-02-14 05:19:56 +00002331 }else if( strcmp(x,"expect")==0 ){
2332 if (psp->gp->nexpected >= 0) {
2333 ErrorMsg(psp->filename,psp->tokenlineno, "Multiple %expect declarations.");
2334 psp->errorcnt++;
2335 psp->state = RESYNC_AFTER_DECL_ERROR;
2336 } else {
2337 psp->state = WAITING_FOR_EXPECT_VALUE;
2338 }
drh75897232000-05-29 14:26:00 +00002339 }else{
2340 ErrorMsg(psp->filename,psp->tokenlineno,
2341 "Unknown declaration keyword: \"%%%s\".",x);
2342 psp->errorcnt++;
2343 psp->state = RESYNC_AFTER_DECL_ERROR;
2344 }
2345 }else{
2346 ErrorMsg(psp->filename,psp->tokenlineno,
2347 "Illegal declaration keyword: \"%s\".",x);
2348 psp->errorcnt++;
2349 psp->state = RESYNC_AFTER_DECL_ERROR;
2350 }
2351 break;
2352 case WAITING_FOR_DESTRUCTOR_SYMBOL:
2353 if( !isalpha(x[0]) ){
2354 ErrorMsg(psp->filename,psp->tokenlineno,
2355 "Symbol name missing after %destructor keyword");
2356 psp->errorcnt++;
2357 psp->state = RESYNC_AFTER_DECL_ERROR;
2358 }else{
2359 struct symbol *sp = Symbol_new(x);
2360 psp->declargslot = &sp->destructor;
drh4dc8ef52008-07-01 17:13:57 +00002361 psp->decllinenoslot = &sp->destLineno;
drha5808f32008-04-27 22:19:44 +00002362 psp->insertLineMacro = 1;
drh75897232000-05-29 14:26:00 +00002363 psp->state = WAITING_FOR_DECL_ARG;
2364 }
2365 break;
icculus42585cf2010-02-14 05:19:56 +00002366 case WAITING_FOR_EXPECT_VALUE:
2367 psp->gp->nexpected = (int) strtol(x, &endptr, 10);
2368 if( (*endptr != '\0') || (endptr == x) ) {
2369 ErrorMsg(psp->filename,psp->tokenlineno,
2370 "Integer expected after %%expect keyword");
2371 psp->errorcnt++;
2372 } else if (psp->gp->nexpected < 0) {
2373 ErrorMsg(psp->filename,psp->tokenlineno,
2374 "Integer can't be negative after %%expect keyword");
2375 psp->errorcnt++;
2376 }
2377 psp->state = WAITING_FOR_DECL_OR_RULE;
2378 break;
drh75897232000-05-29 14:26:00 +00002379 case WAITING_FOR_DATATYPE_SYMBOL:
2380 if( !isalpha(x[0]) ){
2381 ErrorMsg(psp->filename,psp->tokenlineno,
2382 "Symbol name missing after %destructor keyword");
2383 psp->errorcnt++;
2384 psp->state = RESYNC_AFTER_DECL_ERROR;
2385 }else{
2386 struct symbol *sp = Symbol_new(x);
2387 psp->declargslot = &sp->datatype;
drha5808f32008-04-27 22:19:44 +00002388 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002389 psp->state = WAITING_FOR_DECL_ARG;
2390 }
2391 break;
2392 case WAITING_FOR_PRECEDENCE_SYMBOL:
2393 if( x[0]=='.' ){
2394 psp->state = WAITING_FOR_DECL_OR_RULE;
2395 }else if( isupper(x[0]) ){
2396 struct symbol *sp;
2397 sp = Symbol_new(x);
2398 if( sp->prec>=0 ){
2399 ErrorMsg(psp->filename,psp->tokenlineno,
2400 "Symbol \"%s\" has already be given a precedence.",x);
2401 psp->errorcnt++;
2402 }else{
2403 sp->prec = psp->preccounter;
2404 sp->assoc = psp->declassoc;
2405 }
2406 }else{
2407 ErrorMsg(psp->filename,psp->tokenlineno,
2408 "Can't assign a precedence to \"%s\".",x);
2409 psp->errorcnt++;
2410 }
2411 break;
2412 case WAITING_FOR_DECL_ARG:
drha5808f32008-04-27 22:19:44 +00002413 if( x[0]=='{' || x[0]=='\"' || isalnum(x[0]) ){
2414 char *zOld, *zNew, *zBuf, *z;
2415 int nOld, n, nLine, nNew, nBack;
drhb5bd49e2008-07-14 12:21:08 +00002416 int addLineMacro;
drha5808f32008-04-27 22:19:44 +00002417 char zLine[50];
2418 zNew = x;
2419 if( zNew[0]=='"' || zNew[0]=='{' ) zNew++;
drh87cf1372008-08-13 20:09:06 +00002420 nNew = lemonStrlen(zNew);
drha5808f32008-04-27 22:19:44 +00002421 if( *psp->declargslot ){
2422 zOld = *psp->declargslot;
2423 }else{
2424 zOld = "";
2425 }
drh87cf1372008-08-13 20:09:06 +00002426 nOld = lemonStrlen(zOld);
drha5808f32008-04-27 22:19:44 +00002427 n = nOld + nNew + 20;
shane58543932008-12-10 20:10:04 +00002428 addLineMacro = !psp->gp->nolinenosflag && psp->insertLineMacro &&
drhb5bd49e2008-07-14 12:21:08 +00002429 (psp->decllinenoslot==0 || psp->decllinenoslot[0]!=0);
2430 if( addLineMacro ){
drha5808f32008-04-27 22:19:44 +00002431 for(z=psp->filename, nBack=0; *z; z++){
2432 if( *z=='\\' ) nBack++;
2433 }
2434 sprintf(zLine, "#line %d ", psp->tokenlineno);
drh87cf1372008-08-13 20:09:06 +00002435 nLine = lemonStrlen(zLine);
2436 n += nLine + lemonStrlen(psp->filename) + nBack;
drha5808f32008-04-27 22:19:44 +00002437 }
2438 *psp->declargslot = zBuf = realloc(*psp->declargslot, n);
2439 zBuf += nOld;
drhb5bd49e2008-07-14 12:21:08 +00002440 if( addLineMacro ){
drha5808f32008-04-27 22:19:44 +00002441 if( nOld && zBuf[-1]!='\n' ){
2442 *(zBuf++) = '\n';
2443 }
2444 memcpy(zBuf, zLine, nLine);
2445 zBuf += nLine;
2446 *(zBuf++) = '"';
2447 for(z=psp->filename; *z; z++){
2448 if( *z=='\\' ){
2449 *(zBuf++) = '\\';
2450 }
2451 *(zBuf++) = *z;
2452 }
2453 *(zBuf++) = '"';
2454 *(zBuf++) = '\n';
2455 }
drh4dc8ef52008-07-01 17:13:57 +00002456 if( psp->decllinenoslot && psp->decllinenoslot[0]==0 ){
2457 psp->decllinenoslot[0] = psp->tokenlineno;
2458 }
drha5808f32008-04-27 22:19:44 +00002459 memcpy(zBuf, zNew, nNew);
2460 zBuf += nNew;
2461 *zBuf = 0;
2462 psp->state = WAITING_FOR_DECL_OR_RULE;
drh75897232000-05-29 14:26:00 +00002463 }else{
2464 ErrorMsg(psp->filename,psp->tokenlineno,
2465 "Illegal argument to %%%s: %s",psp->declkeyword,x);
2466 psp->errorcnt++;
2467 psp->state = RESYNC_AFTER_DECL_ERROR;
2468 }
2469 break;
drh0bd1f4e2002-06-06 18:54:39 +00002470 case WAITING_FOR_FALLBACK_ID:
2471 if( x[0]=='.' ){
2472 psp->state = WAITING_FOR_DECL_OR_RULE;
2473 }else if( !isupper(x[0]) ){
2474 ErrorMsg(psp->filename, psp->tokenlineno,
2475 "%%fallback argument \"%s\" should be a token", x);
2476 psp->errorcnt++;
2477 }else{
2478 struct symbol *sp = Symbol_new(x);
2479 if( psp->fallback==0 ){
2480 psp->fallback = sp;
2481 }else if( sp->fallback ){
2482 ErrorMsg(psp->filename, psp->tokenlineno,
2483 "More than one fallback assigned to token %s", x);
2484 psp->errorcnt++;
2485 }else{
2486 sp->fallback = psp->fallback;
2487 psp->gp->has_fallback = 1;
2488 }
2489 }
2490 break;
drhe09daa92006-06-10 13:29:31 +00002491 case WAITING_FOR_WILDCARD_ID:
2492 if( x[0]=='.' ){
2493 psp->state = WAITING_FOR_DECL_OR_RULE;
2494 }else if( !isupper(x[0]) ){
2495 ErrorMsg(psp->filename, psp->tokenlineno,
2496 "%%wildcard argument \"%s\" should be a token", x);
2497 psp->errorcnt++;
2498 }else{
2499 struct symbol *sp = Symbol_new(x);
2500 if( psp->gp->wildcard==0 ){
2501 psp->gp->wildcard = sp;
2502 }else{
2503 ErrorMsg(psp->filename, psp->tokenlineno,
2504 "Extra wildcard to token: %s", x);
2505 psp->errorcnt++;
2506 }
2507 }
2508 break;
drh75897232000-05-29 14:26:00 +00002509 case RESYNC_AFTER_RULE_ERROR:
2510/* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2511** break; */
2512 case RESYNC_AFTER_DECL_ERROR:
2513 if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2514 if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;
2515 break;
2516 }
2517}
2518
drh34ff57b2008-07-14 12:27:51 +00002519/* Run the preprocessor over the input file text. The global variables
drh6d08b4d2004-07-20 12:45:22 +00002520** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2521** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2522** comments them out. Text in between is also commented out as appropriate.
2523*/
danielk1977940fac92005-01-23 22:41:37 +00002524static void preprocess_input(char *z){
drh6d08b4d2004-07-20 12:45:22 +00002525 int i, j, k, n;
2526 int exclude = 0;
rse38514a92007-09-20 11:34:17 +00002527 int start = 0;
drh6d08b4d2004-07-20 12:45:22 +00002528 int lineno = 1;
rse38514a92007-09-20 11:34:17 +00002529 int start_lineno = 1;
drh6d08b4d2004-07-20 12:45:22 +00002530 for(i=0; z[i]; i++){
2531 if( z[i]=='\n' ) lineno++;
2532 if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue;
2533 if( strncmp(&z[i],"%endif",6)==0 && isspace(z[i+6]) ){
2534 if( exclude ){
2535 exclude--;
2536 if( exclude==0 ){
2537 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';
2538 }
2539 }
2540 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2541 }else if( (strncmp(&z[i],"%ifdef",6)==0 && isspace(z[i+6]))
2542 || (strncmp(&z[i],"%ifndef",7)==0 && isspace(z[i+7])) ){
2543 if( exclude ){
2544 exclude++;
2545 }else{
2546 for(j=i+7; isspace(z[j]); j++){}
2547 for(n=0; z[j+n] && !isspace(z[j+n]); n++){}
2548 exclude = 1;
2549 for(k=0; k<nDefine; k++){
drh87cf1372008-08-13 20:09:06 +00002550 if( strncmp(azDefine[k],&z[j],n)==0 && lemonStrlen(azDefine[k])==n ){
drh6d08b4d2004-07-20 12:45:22 +00002551 exclude = 0;
2552 break;
2553 }
2554 }
2555 if( z[i+3]=='n' ) exclude = !exclude;
2556 if( exclude ){
2557 start = i;
2558 start_lineno = lineno;
2559 }
2560 }
2561 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2562 }
2563 }
2564 if( exclude ){
2565 fprintf(stderr,"unterminated %%ifdef starting on line %d\n", start_lineno);
2566 exit(1);
2567 }
2568}
2569
drh75897232000-05-29 14:26:00 +00002570/* In spite of its name, this function is really a scanner. It read
2571** in the entire input file (all at once) then tokenizes it. Each
2572** token is passed to the function "parseonetoken" which builds all
2573** the appropriate data structures in the global state vector "gp".
2574*/
2575void Parse(gp)
2576struct lemon *gp;
2577{
2578 struct pstate ps;
2579 FILE *fp;
2580 char *filebuf;
2581 int filesize;
2582 int lineno;
2583 int c;
2584 char *cp, *nextcp;
2585 int startline = 0;
2586
rse38514a92007-09-20 11:34:17 +00002587 memset(&ps, '\0', sizeof(ps));
drh75897232000-05-29 14:26:00 +00002588 ps.gp = gp;
2589 ps.filename = gp->filename;
2590 ps.errorcnt = 0;
2591 ps.state = INITIALIZE;
2592
2593 /* Begin by reading the input file */
2594 fp = fopen(ps.filename,"rb");
2595 if( fp==0 ){
2596 ErrorMsg(ps.filename,0,"Can't open this file for reading.");
2597 gp->errorcnt++;
2598 return;
2599 }
2600 fseek(fp,0,2);
2601 filesize = ftell(fp);
2602 rewind(fp);
2603 filebuf = (char *)malloc( filesize+1 );
2604 if( filebuf==0 ){
2605 ErrorMsg(ps.filename,0,"Can't allocate %d of memory to hold this file.",
2606 filesize+1);
2607 gp->errorcnt++;
2608 return;
2609 }
2610 if( fread(filebuf,1,filesize,fp)!=filesize ){
2611 ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",
2612 filesize);
2613 free(filebuf);
2614 gp->errorcnt++;
2615 return;
2616 }
2617 fclose(fp);
2618 filebuf[filesize] = 0;
2619
drh6d08b4d2004-07-20 12:45:22 +00002620 /* Make an initial pass through the file to handle %ifdef and %ifndef */
2621 preprocess_input(filebuf);
2622
drh75897232000-05-29 14:26:00 +00002623 /* Now scan the text of the input file */
2624 lineno = 1;
2625 for(cp=filebuf; (c= *cp)!=0; ){
2626 if( c=='\n' ) lineno++; /* Keep track of the line number */
2627 if( isspace(c) ){ cp++; continue; } /* Skip all white space */
2628 if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments */
2629 cp+=2;
2630 while( (c= *cp)!=0 && c!='\n' ) cp++;
2631 continue;
2632 }
2633 if( c=='/' && cp[1]=='*' ){ /* Skip C style comments */
2634 cp+=2;
2635 while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){
2636 if( c=='\n' ) lineno++;
2637 cp++;
2638 }
2639 if( c ) cp++;
2640 continue;
2641 }
2642 ps.tokenstart = cp; /* Mark the beginning of the token */
2643 ps.tokenlineno = lineno; /* Linenumber on which token begins */
2644 if( c=='\"' ){ /* String literals */
2645 cp++;
2646 while( (c= *cp)!=0 && c!='\"' ){
2647 if( c=='\n' ) lineno++;
2648 cp++;
2649 }
2650 if( c==0 ){
2651 ErrorMsg(ps.filename,startline,
2652"String starting on this line is not terminated before the end of the file.");
2653 ps.errorcnt++;
2654 nextcp = cp;
2655 }else{
2656 nextcp = cp+1;
2657 }
2658 }else if( c=='{' ){ /* A block of C code */
2659 int level;
2660 cp++;
2661 for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){
2662 if( c=='\n' ) lineno++;
2663 else if( c=='{' ) level++;
2664 else if( c=='}' ) level--;
2665 else if( c=='/' && cp[1]=='*' ){ /* Skip comments */
2666 int prevc;
2667 cp = &cp[2];
2668 prevc = 0;
2669 while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){
2670 if( c=='\n' ) lineno++;
2671 prevc = c;
2672 cp++;
2673 }
2674 }else if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments too */
2675 cp = &cp[2];
2676 while( (c= *cp)!=0 && c!='\n' ) cp++;
2677 if( c ) lineno++;
2678 }else if( c=='\'' || c=='\"' ){ /* String a character literals */
2679 int startchar, prevc;
2680 startchar = c;
2681 prevc = 0;
2682 for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){
2683 if( c=='\n' ) lineno++;
2684 if( prevc=='\\' ) prevc = 0;
2685 else prevc = c;
2686 }
2687 }
2688 }
2689 if( c==0 ){
drh960e8c62001-04-03 16:53:21 +00002690 ErrorMsg(ps.filename,ps.tokenlineno,
drh75897232000-05-29 14:26:00 +00002691"C code starting on this line is not terminated before the end of the file.");
2692 ps.errorcnt++;
2693 nextcp = cp;
2694 }else{
2695 nextcp = cp+1;
2696 }
2697 }else if( isalnum(c) ){ /* Identifiers */
2698 while( (c= *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2699 nextcp = cp;
2700 }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */
2701 cp += 3;
2702 nextcp = cp;
drhfd405312005-11-06 04:06:59 +00002703 }else if( (c=='/' || c=='|') && isalpha(cp[1]) ){
2704 cp += 2;
2705 while( (c = *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2706 nextcp = cp;
drh75897232000-05-29 14:26:00 +00002707 }else{ /* All other (one character) operators */
2708 cp++;
2709 nextcp = cp;
2710 }
2711 c = *cp;
2712 *cp = 0; /* Null terminate the token */
2713 parseonetoken(&ps); /* Parse the token */
2714 *cp = c; /* Restore the buffer */
2715 cp = nextcp;
2716 }
2717 free(filebuf); /* Release the buffer after parsing */
2718 gp->rule = ps.firstrule;
2719 gp->errorcnt = ps.errorcnt;
2720}
2721/*************************** From the file "plink.c" *********************/
2722/*
2723** Routines processing configuration follow-set propagation links
2724** in the LEMON parser generator.
2725*/
2726static struct plink *plink_freelist = 0;
2727
2728/* Allocate a new plink */
2729struct plink *Plink_new(){
2730 struct plink *new;
2731
2732 if( plink_freelist==0 ){
2733 int i;
2734 int amt = 100;
drh9892c5d2007-12-21 00:02:11 +00002735 plink_freelist = (struct plink *)calloc( amt, sizeof(struct plink) );
drh75897232000-05-29 14:26:00 +00002736 if( plink_freelist==0 ){
2737 fprintf(stderr,
2738 "Unable to allocate memory for a new follow-set propagation link.\n");
2739 exit(1);
2740 }
2741 for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
2742 plink_freelist[amt-1].next = 0;
2743 }
2744 new = plink_freelist;
2745 plink_freelist = plink_freelist->next;
2746 return new;
2747}
2748
2749/* Add a plink to a plink list */
2750void Plink_add(plpp,cfp)
2751struct plink **plpp;
2752struct config *cfp;
2753{
2754 struct plink *new;
2755 new = Plink_new();
2756 new->next = *plpp;
2757 *plpp = new;
2758 new->cfp = cfp;
2759}
2760
2761/* Transfer every plink on the list "from" to the list "to" */
2762void Plink_copy(to,from)
2763struct plink **to;
2764struct plink *from;
2765{
2766 struct plink *nextpl;
2767 while( from ){
2768 nextpl = from->next;
2769 from->next = *to;
2770 *to = from;
2771 from = nextpl;
2772 }
2773}
2774
2775/* Delete every plink on the list */
2776void Plink_delete(plp)
2777struct plink *plp;
2778{
2779 struct plink *nextpl;
2780
2781 while( plp ){
2782 nextpl = plp->next;
2783 plp->next = plink_freelist;
2784 plink_freelist = plp;
2785 plp = nextpl;
2786 }
2787}
2788/*********************** From the file "report.c" **************************/
2789/*
2790** Procedures for generating reports and tables in the LEMON parser generator.
2791*/
2792
2793/* Generate a filename with the given suffix. Space to hold the
2794** name comes from malloc() and must be freed by the calling
2795** function.
2796*/
2797PRIVATE char *file_makename(lemp,suffix)
2798struct lemon *lemp;
2799char *suffix;
2800{
2801 char *name;
2802 char *cp;
2803
drh87cf1372008-08-13 20:09:06 +00002804 name = malloc( lemonStrlen(lemp->filename) + lemonStrlen(suffix) + 5 );
drh75897232000-05-29 14:26:00 +00002805 if( name==0 ){
2806 fprintf(stderr,"Can't allocate space for a filename.\n");
2807 exit(1);
2808 }
2809 strcpy(name,lemp->filename);
2810 cp = strrchr(name,'.');
2811 if( cp ) *cp = 0;
2812 strcat(name,suffix);
2813 return name;
2814}
2815
2816/* Open a file with a name based on the name of the input file,
2817** but with a different (specified) suffix, and return a pointer
2818** to the stream */
2819PRIVATE FILE *file_open(lemp,suffix,mode)
2820struct lemon *lemp;
2821char *suffix;
2822char *mode;
2823{
2824 FILE *fp;
2825
2826 if( lemp->outname ) free(lemp->outname);
2827 lemp->outname = file_makename(lemp, suffix);
2828 fp = fopen(lemp->outname,mode);
2829 if( fp==0 && *mode=='w' ){
2830 fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
2831 lemp->errorcnt++;
2832 return 0;
2833 }
2834 return fp;
2835}
2836
2837/* Duplicate the input file without comments and without actions
2838** on rules */
2839void Reprint(lemp)
2840struct lemon *lemp;
2841{
2842 struct rule *rp;
2843 struct symbol *sp;
2844 int i, j, maxlen, len, ncolumns, skip;
2845 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
2846 maxlen = 10;
2847 for(i=0; i<lemp->nsymbol; i++){
2848 sp = lemp->symbols[i];
drh87cf1372008-08-13 20:09:06 +00002849 len = lemonStrlen(sp->name);
drh75897232000-05-29 14:26:00 +00002850 if( len>maxlen ) maxlen = len;
2851 }
2852 ncolumns = 76/(maxlen+5);
2853 if( ncolumns<1 ) ncolumns = 1;
2854 skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
2855 for(i=0; i<skip; i++){
2856 printf("//");
2857 for(j=i; j<lemp->nsymbol; j+=skip){
2858 sp = lemp->symbols[j];
2859 assert( sp->index==j );
2860 printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
2861 }
2862 printf("\n");
2863 }
2864 for(rp=lemp->rule; rp; rp=rp->next){
2865 printf("%s",rp->lhs->name);
drhfd405312005-11-06 04:06:59 +00002866 /* if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
drh75897232000-05-29 14:26:00 +00002867 printf(" ::=");
2868 for(i=0; i<rp->nrhs; i++){
drhfd405312005-11-06 04:06:59 +00002869 sp = rp->rhs[i];
2870 printf(" %s", sp->name);
2871 if( sp->type==MULTITERMINAL ){
2872 for(j=1; j<sp->nsubsym; j++){
2873 printf("|%s", sp->subsym[j]->name);
2874 }
2875 }
2876 /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
drh75897232000-05-29 14:26:00 +00002877 }
2878 printf(".");
2879 if( rp->precsym ) printf(" [%s]",rp->precsym->name);
drhfd405312005-11-06 04:06:59 +00002880 /* if( rp->code ) printf("\n %s",rp->code); */
drh75897232000-05-29 14:26:00 +00002881 printf("\n");
2882 }
2883}
2884
2885void ConfigPrint(fp,cfp)
2886FILE *fp;
2887struct config *cfp;
2888{
2889 struct rule *rp;
drhfd405312005-11-06 04:06:59 +00002890 struct symbol *sp;
2891 int i, j;
drh75897232000-05-29 14:26:00 +00002892 rp = cfp->rp;
2893 fprintf(fp,"%s ::=",rp->lhs->name);
2894 for(i=0; i<=rp->nrhs; i++){
2895 if( i==cfp->dot ) fprintf(fp," *");
2896 if( i==rp->nrhs ) break;
drhfd405312005-11-06 04:06:59 +00002897 sp = rp->rhs[i];
2898 fprintf(fp," %s", sp->name);
2899 if( sp->type==MULTITERMINAL ){
2900 for(j=1; j<sp->nsubsym; j++){
2901 fprintf(fp,"|%s",sp->subsym[j]->name);
2902 }
2903 }
drh75897232000-05-29 14:26:00 +00002904 }
2905}
2906
2907/* #define TEST */
drhfd405312005-11-06 04:06:59 +00002908#if 0
drh75897232000-05-29 14:26:00 +00002909/* Print a set */
2910PRIVATE void SetPrint(out,set,lemp)
2911FILE *out;
2912char *set;
2913struct lemon *lemp;
2914{
2915 int i;
2916 char *spacer;
2917 spacer = "";
2918 fprintf(out,"%12s[","");
2919 for(i=0; i<lemp->nterminal; i++){
2920 if( SetFind(set,i) ){
2921 fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
2922 spacer = " ";
2923 }
2924 }
2925 fprintf(out,"]\n");
2926}
2927
2928/* Print a plink chain */
2929PRIVATE void PlinkPrint(out,plp,tag)
2930FILE *out;
2931struct plink *plp;
2932char *tag;
2933{
2934 while( plp ){
drhada354d2005-11-05 15:03:59 +00002935 fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->statenum);
drh75897232000-05-29 14:26:00 +00002936 ConfigPrint(out,plp->cfp);
2937 fprintf(out,"\n");
2938 plp = plp->next;
2939 }
2940}
2941#endif
2942
2943/* Print an action to the given file descriptor. Return FALSE if
2944** nothing was actually printed.
2945*/
2946int PrintAction(struct action *ap, FILE *fp, int indent){
2947 int result = 1;
2948 switch( ap->type ){
2949 case SHIFT:
drhada354d2005-11-05 15:03:59 +00002950 fprintf(fp,"%*s shift %d",indent,ap->sp->name,ap->x.stp->statenum);
drh75897232000-05-29 14:26:00 +00002951 break;
2952 case REDUCE:
2953 fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
2954 break;
2955 case ACCEPT:
2956 fprintf(fp,"%*s accept",indent,ap->sp->name);
2957 break;
2958 case ERROR:
2959 fprintf(fp,"%*s error",indent,ap->sp->name);
2960 break;
drh9892c5d2007-12-21 00:02:11 +00002961 case SRCONFLICT:
2962 case RRCONFLICT:
drh75897232000-05-29 14:26:00 +00002963 fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
2964 indent,ap->sp->name,ap->x.rp->index);
2965 break;
drh9892c5d2007-12-21 00:02:11 +00002966 case SSCONFLICT:
2967 fprintf(fp,"%*s shift %d ** Parsing conflict **",
2968 indent,ap->sp->name,ap->x.stp->statenum);
2969 break;
drh75897232000-05-29 14:26:00 +00002970 case SH_RESOLVED:
2971 case RD_RESOLVED:
2972 case NOT_USED:
2973 result = 0;
2974 break;
2975 }
2976 return result;
2977}
2978
2979/* Generate the "y.output" log file */
2980void ReportOutput(lemp)
2981struct lemon *lemp;
2982{
2983 int i;
2984 struct state *stp;
2985 struct config *cfp;
2986 struct action *ap;
2987 FILE *fp;
2988
drh2aa6ca42004-09-10 00:14:04 +00002989 fp = file_open(lemp,".out","wb");
drh75897232000-05-29 14:26:00 +00002990 if( fp==0 ) return;
drh75897232000-05-29 14:26:00 +00002991 for(i=0; i<lemp->nstate; i++){
2992 stp = lemp->sorted[i];
drhada354d2005-11-05 15:03:59 +00002993 fprintf(fp,"State %d:\n",stp->statenum);
drh75897232000-05-29 14:26:00 +00002994 if( lemp->basisflag ) cfp=stp->bp;
2995 else cfp=stp->cfp;
2996 while( cfp ){
2997 char buf[20];
2998 if( cfp->dot==cfp->rp->nrhs ){
2999 sprintf(buf,"(%d)",cfp->rp->index);
3000 fprintf(fp," %5s ",buf);
3001 }else{
3002 fprintf(fp," ");
3003 }
3004 ConfigPrint(fp,cfp);
3005 fprintf(fp,"\n");
drhfd405312005-11-06 04:06:59 +00003006#if 0
drh75897232000-05-29 14:26:00 +00003007 SetPrint(fp,cfp->fws,lemp);
3008 PlinkPrint(fp,cfp->fplp,"To ");
3009 PlinkPrint(fp,cfp->bplp,"From");
3010#endif
3011 if( lemp->basisflag ) cfp=cfp->bp;
3012 else cfp=cfp->next;
3013 }
3014 fprintf(fp,"\n");
3015 for(ap=stp->ap; ap; ap=ap->next){
3016 if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
3017 }
3018 fprintf(fp,"\n");
3019 }
drhe9278182007-07-18 18:16:29 +00003020 fprintf(fp, "----------------------------------------------------\n");
3021 fprintf(fp, "Symbols:\n");
3022 for(i=0; i<lemp->nsymbol; i++){
3023 int j;
3024 struct symbol *sp;
3025
3026 sp = lemp->symbols[i];
3027 fprintf(fp, " %3d: %s", i, sp->name);
3028 if( sp->type==NONTERMINAL ){
3029 fprintf(fp, ":");
3030 if( sp->lambda ){
3031 fprintf(fp, " <lambda>");
3032 }
3033 for(j=0; j<lemp->nterminal; j++){
3034 if( sp->firstset && SetFind(sp->firstset, j) ){
3035 fprintf(fp, " %s", lemp->symbols[j]->name);
3036 }
3037 }
3038 }
3039 fprintf(fp, "\n");
3040 }
drh75897232000-05-29 14:26:00 +00003041 fclose(fp);
3042 return;
3043}
3044
3045/* Search for the file "name" which is in the same directory as
3046** the exacutable */
3047PRIVATE char *pathsearch(argv0,name,modemask)
3048char *argv0;
3049char *name;
3050int modemask;
3051{
3052 char *pathlist;
3053 char *path,*cp;
3054 char c;
drh75897232000-05-29 14:26:00 +00003055
3056#ifdef __WIN32__
3057 cp = strrchr(argv0,'\\');
3058#else
3059 cp = strrchr(argv0,'/');
3060#endif
3061 if( cp ){
3062 c = *cp;
3063 *cp = 0;
drh87cf1372008-08-13 20:09:06 +00003064 path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2 );
drh75897232000-05-29 14:26:00 +00003065 if( path ) sprintf(path,"%s/%s",argv0,name);
3066 *cp = c;
3067 }else{
3068 extern char *getenv();
3069 pathlist = getenv("PATH");
3070 if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
drh87cf1372008-08-13 20:09:06 +00003071 path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
drh75897232000-05-29 14:26:00 +00003072 if( path!=0 ){
3073 while( *pathlist ){
3074 cp = strchr(pathlist,':');
drh87cf1372008-08-13 20:09:06 +00003075 if( cp==0 ) cp = &pathlist[lemonStrlen(pathlist)];
drh75897232000-05-29 14:26:00 +00003076 c = *cp;
3077 *cp = 0;
3078 sprintf(path,"%s/%s",pathlist,name);
3079 *cp = c;
3080 if( c==0 ) pathlist = "";
3081 else pathlist = &cp[1];
3082 if( access(path,modemask)==0 ) break;
3083 }
3084 }
3085 }
3086 return path;
3087}
3088
3089/* Given an action, compute the integer value for that action
3090** which is to be put in the action table of the generated machine.
3091** Return negative if no action should be generated.
3092*/
3093PRIVATE int compute_action(lemp,ap)
3094struct lemon *lemp;
3095struct action *ap;
3096{
3097 int act;
3098 switch( ap->type ){
drhada354d2005-11-05 15:03:59 +00003099 case SHIFT: act = ap->x.stp->statenum; break;
drh75897232000-05-29 14:26:00 +00003100 case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
3101 case ERROR: act = lemp->nstate + lemp->nrule; break;
3102 case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break;
3103 default: act = -1; break;
3104 }
3105 return act;
3106}
3107
3108#define LINESIZE 1000
3109/* The next cluster of routines are for reading the template file
3110** and writing the results to the generated parser */
3111/* The first function transfers data from "in" to "out" until
3112** a line is seen which begins with "%%". The line number is
3113** tracked.
3114**
3115** if name!=0, then any word that begin with "Parse" is changed to
3116** begin with *name instead.
3117*/
3118PRIVATE void tplt_xfer(name,in,out,lineno)
3119char *name;
3120FILE *in;
3121FILE *out;
3122int *lineno;
3123{
3124 int i, iStart;
3125 char line[LINESIZE];
3126 while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
3127 (*lineno)++;
3128 iStart = 0;
3129 if( name ){
3130 for(i=0; line[i]; i++){
3131 if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0
3132 && (i==0 || !isalpha(line[i-1]))
3133 ){
3134 if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);
3135 fprintf(out,"%s",name);
3136 i += 4;
3137 iStart = i+1;
3138 }
3139 }
3140 }
3141 fprintf(out,"%s",&line[iStart]);
3142 }
3143}
3144
3145/* The next function finds the template file and opens it, returning
3146** a pointer to the opened file. */
3147PRIVATE FILE *tplt_open(lemp)
3148struct lemon *lemp;
3149{
3150 static char templatename[] = "lempar.c";
3151 char buf[1000];
3152 FILE *in;
3153 char *tpltname;
3154 char *cp;
3155
icculus3e143bd2010-02-14 00:48:49 +00003156 /* first, see if user specified a template filename on the command line. */
3157 if (user_templatename != 0) {
3158 if( access(user_templatename,004)==-1 ){
3159 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3160 user_templatename);
3161 lemp->errorcnt++;
3162 return 0;
3163 }
3164 in = fopen(user_templatename,"rb");
3165 if( in==0 ){
3166 fprintf(stderr,"Can't open the template file \"%s\".\n",user_templatename);
3167 lemp->errorcnt++;
3168 return 0;
3169 }
3170 return in;
3171 }
3172
drh75897232000-05-29 14:26:00 +00003173 cp = strrchr(lemp->filename,'.');
3174 if( cp ){
drh8b582012003-10-21 13:16:03 +00003175 sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
drh75897232000-05-29 14:26:00 +00003176 }else{
3177 sprintf(buf,"%s.lt",lemp->filename);
3178 }
3179 if( access(buf,004)==0 ){
3180 tpltname = buf;
drh960e8c62001-04-03 16:53:21 +00003181 }else if( access(templatename,004)==0 ){
3182 tpltname = templatename;
drh75897232000-05-29 14:26:00 +00003183 }else{
3184 tpltname = pathsearch(lemp->argv0,templatename,0);
3185 }
3186 if( tpltname==0 ){
3187 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3188 templatename);
3189 lemp->errorcnt++;
3190 return 0;
3191 }
drh2aa6ca42004-09-10 00:14:04 +00003192 in = fopen(tpltname,"rb");
drh75897232000-05-29 14:26:00 +00003193 if( in==0 ){
3194 fprintf(stderr,"Can't open the template file \"%s\".\n",templatename);
3195 lemp->errorcnt++;
3196 return 0;
3197 }
3198 return in;
3199}
3200
drhaf805ca2004-09-07 11:28:25 +00003201/* Print a #line directive line to the output file. */
3202PRIVATE void tplt_linedir(out,lineno,filename)
3203FILE *out;
3204int lineno;
3205char *filename;
3206{
3207 fprintf(out,"#line %d \"",lineno);
3208 while( *filename ){
3209 if( *filename == '\\' ) putc('\\',out);
3210 putc(*filename,out);
3211 filename++;
3212 }
3213 fprintf(out,"\"\n");
3214}
3215
drh75897232000-05-29 14:26:00 +00003216/* Print a string to the file and keep the linenumber up to date */
drha5808f32008-04-27 22:19:44 +00003217PRIVATE void tplt_print(out,lemp,str,lineno)
drh75897232000-05-29 14:26:00 +00003218FILE *out;
3219struct lemon *lemp;
3220char *str;
drh75897232000-05-29 14:26:00 +00003221int *lineno;
3222{
3223 if( str==0 ) return;
drh75897232000-05-29 14:26:00 +00003224 while( *str ){
drh75897232000-05-29 14:26:00 +00003225 putc(*str,out);
shane58543932008-12-10 20:10:04 +00003226 if( *str=='\n' ) (*lineno)++;
drh75897232000-05-29 14:26:00 +00003227 str++;
3228 }
drh9db55df2004-09-09 14:01:21 +00003229 if( str[-1]!='\n' ){
3230 putc('\n',out);
3231 (*lineno)++;
3232 }
shane58543932008-12-10 20:10:04 +00003233 if (!lemp->nolinenosflag) {
3234 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);
3235 }
drh75897232000-05-29 14:26:00 +00003236 return;
3237}
3238
3239/*
3240** The following routine emits code for the destructor for the
3241** symbol sp
3242*/
3243void emit_destructor_code(out,sp,lemp,lineno)
3244FILE *out;
3245struct symbol *sp;
3246struct lemon *lemp;
3247int *lineno;
3248{
drhcc83b6e2004-04-23 23:38:42 +00003249 char *cp = 0;
drh75897232000-05-29 14:26:00 +00003250
drh75897232000-05-29 14:26:00 +00003251 if( sp->type==TERMINAL ){
3252 cp = lemp->tokendest;
3253 if( cp==0 ) return;
drha5808f32008-04-27 22:19:44 +00003254 fprintf(out,"{\n"); (*lineno)++;
drh960e8c62001-04-03 16:53:21 +00003255 }else if( sp->destructor ){
drh75897232000-05-29 14:26:00 +00003256 cp = sp->destructor;
drha5808f32008-04-27 22:19:44 +00003257 fprintf(out,"{\n"); (*lineno)++;
shane58543932008-12-10 20:10:04 +00003258 if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,sp->destLineno,lemp->filename); }
drh960e8c62001-04-03 16:53:21 +00003259 }else if( lemp->vardest ){
3260 cp = lemp->vardest;
3261 if( cp==0 ) return;
drha5808f32008-04-27 22:19:44 +00003262 fprintf(out,"{\n"); (*lineno)++;
drhcc83b6e2004-04-23 23:38:42 +00003263 }else{
3264 assert( 0 ); /* Cannot happen */
drh75897232000-05-29 14:26:00 +00003265 }
3266 for(; *cp; cp++){
3267 if( *cp=='$' && cp[1]=='$' ){
3268 fprintf(out,"(yypminor->yy%d)",sp->dtnum);
3269 cp++;
3270 continue;
3271 }
shane58543932008-12-10 20:10:04 +00003272 if( *cp=='\n' ) (*lineno)++;
drh75897232000-05-29 14:26:00 +00003273 fputc(*cp,out);
3274 }
shane58543932008-12-10 20:10:04 +00003275 fprintf(out,"\n"); (*lineno)++;
3276 if (!lemp->nolinenosflag) {
3277 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);
3278 }
3279 fprintf(out,"}\n"); (*lineno)++;
drh75897232000-05-29 14:26:00 +00003280 return;
3281}
3282
3283/*
drh960e8c62001-04-03 16:53:21 +00003284** Return TRUE (non-zero) if the given symbol has a destructor.
drh75897232000-05-29 14:26:00 +00003285*/
3286int has_destructor(sp, lemp)
3287struct symbol *sp;
3288struct lemon *lemp;
3289{
3290 int ret;
3291 if( sp->type==TERMINAL ){
3292 ret = lemp->tokendest!=0;
3293 }else{
drh960e8c62001-04-03 16:53:21 +00003294 ret = lemp->vardest!=0 || sp->destructor!=0;
drh75897232000-05-29 14:26:00 +00003295 }
3296 return ret;
3297}
3298
drh0bb132b2004-07-20 14:06:51 +00003299/*
3300** Append text to a dynamically allocated string. If zText is 0 then
3301** reset the string to be empty again. Always return the complete text
3302** of the string (which is overwritten with each call).
drh7ac25c72004-08-19 15:12:26 +00003303**
3304** n bytes of zText are stored. If n==0 then all of zText up to the first
3305** \000 terminator is stored. zText can contain up to two instances of
3306** %d. The values of p1 and p2 are written into the first and second
3307** %d.
3308**
3309** If n==-1, then the previous character is overwritten.
drh0bb132b2004-07-20 14:06:51 +00003310*/
3311PRIVATE char *append_str(char *zText, int n, int p1, int p2){
3312 static char *z = 0;
3313 static int alloced = 0;
3314 static int used = 0;
drhaf805ca2004-09-07 11:28:25 +00003315 int c;
drh0bb132b2004-07-20 14:06:51 +00003316 char zInt[40];
3317
3318 if( zText==0 ){
3319 used = 0;
3320 return z;
3321 }
drh7ac25c72004-08-19 15:12:26 +00003322 if( n<=0 ){
3323 if( n<0 ){
3324 used += n;
3325 assert( used>=0 );
3326 }
drh87cf1372008-08-13 20:09:06 +00003327 n = lemonStrlen(zText);
drh7ac25c72004-08-19 15:12:26 +00003328 }
drh0bb132b2004-07-20 14:06:51 +00003329 if( n+sizeof(zInt)*2+used >= alloced ){
3330 alloced = n + sizeof(zInt)*2 + used + 200;
3331 z = realloc(z, alloced);
3332 }
3333 if( z==0 ) return "";
3334 while( n-- > 0 ){
3335 c = *(zText++);
drh50489622006-10-13 12:25:29 +00003336 if( c=='%' && n>0 && zText[0]=='d' ){
drh0bb132b2004-07-20 14:06:51 +00003337 sprintf(zInt, "%d", p1);
3338 p1 = p2;
3339 strcpy(&z[used], zInt);
drh87cf1372008-08-13 20:09:06 +00003340 used += lemonStrlen(&z[used]);
drh0bb132b2004-07-20 14:06:51 +00003341 zText++;
3342 n--;
3343 }else{
3344 z[used++] = c;
3345 }
3346 }
3347 z[used] = 0;
3348 return z;
3349}
3350
3351/*
3352** zCode is a string that is the action associated with a rule. Expand
3353** the symbols in this string so that the refer to elements of the parser
drhaf805ca2004-09-07 11:28:25 +00003354** stack.
drh0bb132b2004-07-20 14:06:51 +00003355*/
drhaf805ca2004-09-07 11:28:25 +00003356PRIVATE void translate_code(struct lemon *lemp, struct rule *rp){
drh0bb132b2004-07-20 14:06:51 +00003357 char *cp, *xp;
3358 int i;
3359 char lhsused = 0; /* True if the LHS element has been used */
3360 char used[MAXRHS]; /* True for each RHS element which is used */
3361
3362 for(i=0; i<rp->nrhs; i++) used[i] = 0;
3363 lhsused = 0;
3364
drh19c9e562007-03-29 20:13:53 +00003365 if( rp->code==0 ){
3366 rp->code = "\n";
3367 rp->line = rp->ruleline;
3368 }
3369
drh0bb132b2004-07-20 14:06:51 +00003370 append_str(0,0,0,0);
drh19c9e562007-03-29 20:13:53 +00003371 for(cp=rp->code; *cp; cp++){
drh0bb132b2004-07-20 14:06:51 +00003372 if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
3373 char saved;
3374 for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
3375 saved = *xp;
3376 *xp = 0;
3377 if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
drh7ac25c72004-08-19 15:12:26 +00003378 append_str("yygotominor.yy%d",0,rp->lhs->dtnum,0);
drh0bb132b2004-07-20 14:06:51 +00003379 cp = xp;
3380 lhsused = 1;
3381 }else{
3382 for(i=0; i<rp->nrhs; i++){
3383 if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
drh7ac25c72004-08-19 15:12:26 +00003384 if( cp!=rp->code && cp[-1]=='@' ){
3385 /* If the argument is of the form @X then substituted
3386 ** the token number of X, not the value of X */
3387 append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);
3388 }else{
drhfd405312005-11-06 04:06:59 +00003389 struct symbol *sp = rp->rhs[i];
3390 int dtnum;
3391 if( sp->type==MULTITERMINAL ){
3392 dtnum = sp->subsym[0]->dtnum;
3393 }else{
3394 dtnum = sp->dtnum;
3395 }
3396 append_str("yymsp[%d].minor.yy%d",0,i-rp->nrhs+1, dtnum);
drh7ac25c72004-08-19 15:12:26 +00003397 }
drh0bb132b2004-07-20 14:06:51 +00003398 cp = xp;
3399 used[i] = 1;
3400 break;
3401 }
3402 }
3403 }
3404 *xp = saved;
3405 }
3406 append_str(cp, 1, 0, 0);
3407 } /* End loop */
3408
3409 /* Check to make sure the LHS has been used */
3410 if( rp->lhsalias && !lhsused ){
3411 ErrorMsg(lemp->filename,rp->ruleline,
3412 "Label \"%s\" for \"%s(%s)\" is never used.",
3413 rp->lhsalias,rp->lhs->name,rp->lhsalias);
3414 lemp->errorcnt++;
3415 }
3416
3417 /* Generate destructor code for RHS symbols which are not used in the
3418 ** reduce code */
3419 for(i=0; i<rp->nrhs; i++){
3420 if( rp->rhsalias[i] && !used[i] ){
3421 ErrorMsg(lemp->filename,rp->ruleline,
3422 "Label %s for \"%s(%s)\" is never used.",
3423 rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
3424 lemp->errorcnt++;
3425 }else if( rp->rhsalias[i]==0 ){
3426 if( has_destructor(rp->rhs[i],lemp) ){
drh639efd02008-08-13 20:04:29 +00003427 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
drh0bb132b2004-07-20 14:06:51 +00003428 rp->rhs[i]->index,i-rp->nrhs+1);
3429 }else{
3430 /* No destructor defined for this term */
3431 }
3432 }
3433 }
drh61e339a2007-01-16 03:09:02 +00003434 if( rp->code ){
3435 cp = append_str(0,0,0,0);
3436 rp->code = Strsafe(cp?cp:"");
3437 }
drh0bb132b2004-07-20 14:06:51 +00003438}
3439
drh75897232000-05-29 14:26:00 +00003440/*
3441** Generate code which executes when the rule "rp" is reduced. Write
3442** the code to "out". Make sure lineno stays up-to-date.
3443*/
3444PRIVATE void emit_code(out,rp,lemp,lineno)
3445FILE *out;
3446struct rule *rp;
3447struct lemon *lemp;
3448int *lineno;
3449{
drh0bb132b2004-07-20 14:06:51 +00003450 char *cp;
drh75897232000-05-29 14:26:00 +00003451
3452 /* Generate code to do the reduce action */
3453 if( rp->code ){
shane58543932008-12-10 20:10:04 +00003454 if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,rp->line,lemp->filename); }
drhaf805ca2004-09-07 11:28:25 +00003455 fprintf(out,"{%s",rp->code);
drh75897232000-05-29 14:26:00 +00003456 for(cp=rp->code; *cp; cp++){
shane58543932008-12-10 20:10:04 +00003457 if( *cp=='\n' ) (*lineno)++;
drh75897232000-05-29 14:26:00 +00003458 } /* End loop */
shane58543932008-12-10 20:10:04 +00003459 fprintf(out,"}\n"); (*lineno)++;
3460 if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,*lineno,lemp->outname); }
drh75897232000-05-29 14:26:00 +00003461 } /* End if( rp->code ) */
3462
drh75897232000-05-29 14:26:00 +00003463 return;
3464}
3465
3466/*
3467** Print the definition of the union used for the parser's data stack.
3468** This union contains fields for every possible data type for tokens
3469** and nonterminals. In the process of computing and printing this
3470** union, also set the ".dtnum" field of every terminal and nonterminal
3471** symbol.
3472*/
3473void print_stack_union(out,lemp,plineno,mhflag)
3474FILE *out; /* The output stream */
3475struct lemon *lemp; /* The main info structure for this parser */
3476int *plineno; /* Pointer to the line number */
3477int mhflag; /* True if generating makeheaders output */
3478{
3479 int lineno = *plineno; /* The line number of the output */
3480 char **types; /* A hash table of datatypes */
3481 int arraysize; /* Size of the "types" array */
3482 int maxdtlength; /* Maximum length of any ".datatype" field. */
3483 char *stddt; /* Standardized name for a datatype */
3484 int i,j; /* Loop counters */
3485 int hash; /* For hashing the name of a type */
3486 char *name; /* Name of the parser */
3487
3488 /* Allocate and initialize types[] and allocate stddt[] */
3489 arraysize = lemp->nsymbol * 2;
drh9892c5d2007-12-21 00:02:11 +00003490 types = (char**)calloc( arraysize, sizeof(char*) );
drh75897232000-05-29 14:26:00 +00003491 for(i=0; i<arraysize; i++) types[i] = 0;
3492 maxdtlength = 0;
drh960e8c62001-04-03 16:53:21 +00003493 if( lemp->vartype ){
drh87cf1372008-08-13 20:09:06 +00003494 maxdtlength = lemonStrlen(lemp->vartype);
drh960e8c62001-04-03 16:53:21 +00003495 }
drh75897232000-05-29 14:26:00 +00003496 for(i=0; i<lemp->nsymbol; i++){
3497 int len;
3498 struct symbol *sp = lemp->symbols[i];
3499 if( sp->datatype==0 ) continue;
drh87cf1372008-08-13 20:09:06 +00003500 len = lemonStrlen(sp->datatype);
drh75897232000-05-29 14:26:00 +00003501 if( len>maxdtlength ) maxdtlength = len;
3502 }
3503 stddt = (char*)malloc( maxdtlength*2 + 1 );
3504 if( types==0 || stddt==0 ){
3505 fprintf(stderr,"Out of memory.\n");
3506 exit(1);
3507 }
3508
3509 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3510 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
drh960e8c62001-04-03 16:53:21 +00003511 ** used for terminal symbols. If there is no %default_type defined then
3512 ** 0 is also used as the .dtnum value for nonterminals which do not specify
3513 ** a datatype using the %type directive.
3514 */
drh75897232000-05-29 14:26:00 +00003515 for(i=0; i<lemp->nsymbol; i++){
3516 struct symbol *sp = lemp->symbols[i];
3517 char *cp;
3518 if( sp==lemp->errsym ){
3519 sp->dtnum = arraysize+1;
3520 continue;
3521 }
drh960e8c62001-04-03 16:53:21 +00003522 if( sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0) ){
drh75897232000-05-29 14:26:00 +00003523 sp->dtnum = 0;
3524 continue;
3525 }
3526 cp = sp->datatype;
drh960e8c62001-04-03 16:53:21 +00003527 if( cp==0 ) cp = lemp->vartype;
drh75897232000-05-29 14:26:00 +00003528 j = 0;
3529 while( isspace(*cp) ) cp++;
3530 while( *cp ) stddt[j++] = *cp++;
3531 while( j>0 && isspace(stddt[j-1]) ) j--;
3532 stddt[j] = 0;
drh02368c92009-04-05 15:18:02 +00003533 if( lemp->tokentype && strcmp(stddt, lemp->tokentype)==0 ){
drh32c4d742008-07-01 16:34:49 +00003534 sp->dtnum = 0;
3535 continue;
3536 }
drh75897232000-05-29 14:26:00 +00003537 hash = 0;
3538 for(j=0; stddt[j]; j++){
3539 hash = hash*53 + stddt[j];
3540 }
drh3b2129c2003-05-13 00:34:21 +00003541 hash = (hash & 0x7fffffff)%arraysize;
drh75897232000-05-29 14:26:00 +00003542 while( types[hash] ){
3543 if( strcmp(types[hash],stddt)==0 ){
3544 sp->dtnum = hash + 1;
3545 break;
3546 }
3547 hash++;
3548 if( hash>=arraysize ) hash = 0;
3549 }
3550 if( types[hash]==0 ){
3551 sp->dtnum = hash + 1;
drh87cf1372008-08-13 20:09:06 +00003552 types[hash] = (char*)malloc( lemonStrlen(stddt)+1 );
drh75897232000-05-29 14:26:00 +00003553 if( types[hash]==0 ){
3554 fprintf(stderr,"Out of memory.\n");
3555 exit(1);
3556 }
3557 strcpy(types[hash],stddt);
3558 }
3559 }
3560
3561 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3562 name = lemp->name ? lemp->name : "Parse";
3563 lineno = *plineno;
3564 if( mhflag ){ fprintf(out,"#if INTERFACE\n"); lineno++; }
3565 fprintf(out,"#define %sTOKENTYPE %s\n",name,
3566 lemp->tokentype?lemp->tokentype:"void*"); lineno++;
3567 if( mhflag ){ fprintf(out,"#endif\n"); lineno++; }
3568 fprintf(out,"typedef union {\n"); lineno++;
drh15b024c2008-12-11 02:20:43 +00003569 fprintf(out," int yyinit;\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003570 fprintf(out," %sTOKENTYPE yy0;\n",name); lineno++;
3571 for(i=0; i<arraysize; i++){
3572 if( types[i]==0 ) continue;
3573 fprintf(out," %s yy%d;\n",types[i],i+1); lineno++;
3574 free(types[i]);
3575 }
drhc4dd3fd2008-01-22 01:48:05 +00003576 if( lemp->errsym->useCnt ){
3577 fprintf(out," int yy%d;\n",lemp->errsym->dtnum); lineno++;
3578 }
drh75897232000-05-29 14:26:00 +00003579 free(stddt);
3580 free(types);
3581 fprintf(out,"} YYMINORTYPE;\n"); lineno++;
3582 *plineno = lineno;
3583}
3584
drhb29b0a52002-02-23 19:39:46 +00003585/*
3586** Return the name of a C datatype able to represent values between
drh8b582012003-10-21 13:16:03 +00003587** lwr and upr, inclusive.
drhb29b0a52002-02-23 19:39:46 +00003588*/
drh8b582012003-10-21 13:16:03 +00003589static const char *minimum_size_type(int lwr, int upr){
3590 if( lwr>=0 ){
3591 if( upr<=255 ){
3592 return "unsigned char";
3593 }else if( upr<65535 ){
3594 return "unsigned short int";
3595 }else{
3596 return "unsigned int";
3597 }
3598 }else if( lwr>=-127 && upr<=127 ){
3599 return "signed char";
3600 }else if( lwr>=-32767 && upr<32767 ){
3601 return "short";
drhb29b0a52002-02-23 19:39:46 +00003602 }else{
drh8b582012003-10-21 13:16:03 +00003603 return "int";
drhb29b0a52002-02-23 19:39:46 +00003604 }
3605}
3606
drhfdbf9282003-10-21 16:34:41 +00003607/*
3608** Each state contains a set of token transaction and a set of
3609** nonterminal transactions. Each of these sets makes an instance
3610** of the following structure. An array of these structures is used
3611** to order the creation of entries in the yy_action[] table.
3612*/
3613struct axset {
3614 struct state *stp; /* A pointer to a state */
3615 int isTkn; /* True to use tokens. False for non-terminals */
3616 int nAction; /* Number of actions */
drhe594bc32009-11-03 13:02:25 +00003617 int iOrder; /* Original order of action sets */
drhfdbf9282003-10-21 16:34:41 +00003618};
3619
3620/*
3621** Compare to axset structures for sorting purposes
3622*/
3623static int axset_compare(const void *a, const void *b){
3624 struct axset *p1 = (struct axset*)a;
3625 struct axset *p2 = (struct axset*)b;
drhe594bc32009-11-03 13:02:25 +00003626 int c;
3627 c = p2->nAction - p1->nAction;
3628 if( c==0 ){
3629 c = p2->iOrder - p1->iOrder;
3630 }
3631 assert( c!=0 || p1==p2 );
3632 return c;
drhfdbf9282003-10-21 16:34:41 +00003633}
3634
drhc4dd3fd2008-01-22 01:48:05 +00003635/*
3636** Write text on "out" that describes the rule "rp".
3637*/
3638static void writeRuleText(FILE *out, struct rule *rp){
3639 int j;
3640 fprintf(out,"%s ::=", rp->lhs->name);
3641 for(j=0; j<rp->nrhs; j++){
3642 struct symbol *sp = rp->rhs[j];
3643 fprintf(out," %s", sp->name);
3644 if( sp->type==MULTITERMINAL ){
3645 int k;
3646 for(k=1; k<sp->nsubsym; k++){
3647 fprintf(out,"|%s",sp->subsym[k]->name);
3648 }
3649 }
3650 }
3651}
3652
3653
drh75897232000-05-29 14:26:00 +00003654/* Generate C source code for the parser */
3655void ReportTable(lemp, mhflag)
3656struct lemon *lemp;
3657int mhflag; /* Output in makeheaders format if true */
3658{
3659 FILE *out, *in;
3660 char line[LINESIZE];
3661 int lineno;
3662 struct state *stp;
3663 struct action *ap;
3664 struct rule *rp;
drh8b582012003-10-21 13:16:03 +00003665 struct acttab *pActtab;
drhf16371d2009-11-03 19:18:31 +00003666 int i, j, k, n;
drh75897232000-05-29 14:26:00 +00003667 char *name;
drh8b582012003-10-21 13:16:03 +00003668 int mnTknOfst, mxTknOfst;
3669 int mnNtOfst, mxNtOfst;
drhfdbf9282003-10-21 16:34:41 +00003670 struct axset *ax;
drh75897232000-05-29 14:26:00 +00003671
3672 in = tplt_open(lemp);
3673 if( in==0 ) return;
drh2aa6ca42004-09-10 00:14:04 +00003674 out = file_open(lemp,".c","wb");
drh75897232000-05-29 14:26:00 +00003675 if( out==0 ){
3676 fclose(in);
3677 return;
3678 }
3679 lineno = 1;
3680 tplt_xfer(lemp->name,in,out,&lineno);
3681
3682 /* Generate the include code, if any */
drha5808f32008-04-27 22:19:44 +00003683 tplt_print(out,lemp,lemp->include,&lineno);
drh75897232000-05-29 14:26:00 +00003684 if( mhflag ){
3685 char *name = file_makename(lemp, ".h");
3686 fprintf(out,"#include \"%s\"\n", name); lineno++;
3687 free(name);
3688 }
3689 tplt_xfer(lemp->name,in,out,&lineno);
3690
3691 /* Generate #defines for all tokens */
3692 if( mhflag ){
3693 char *prefix;
3694 fprintf(out,"#if INTERFACE\n"); lineno++;
3695 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
3696 else prefix = "";
3697 for(i=1; i<lemp->nterminal; i++){
3698 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
3699 lineno++;
3700 }
3701 fprintf(out,"#endif\n"); lineno++;
3702 }
3703 tplt_xfer(lemp->name,in,out,&lineno);
3704
3705 /* Generate the defines */
drh75897232000-05-29 14:26:00 +00003706 fprintf(out,"#define YYCODETYPE %s\n",
drh8a415d32009-06-12 13:53:51 +00003707 minimum_size_type(0, lemp->nsymbol+1)); lineno++;
drh75897232000-05-29 14:26:00 +00003708 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++;
3709 fprintf(out,"#define YYACTIONTYPE %s\n",
drh8b582012003-10-21 13:16:03 +00003710 minimum_size_type(0, lemp->nstate+lemp->nrule+5)); lineno++;
drhe09daa92006-06-10 13:29:31 +00003711 if( lemp->wildcard ){
3712 fprintf(out,"#define YYWILDCARD %d\n",
3713 lemp->wildcard->index); lineno++;
3714 }
drh75897232000-05-29 14:26:00 +00003715 print_stack_union(out,lemp,&lineno,mhflag);
drhca44b5a2007-02-22 23:06:58 +00003716 fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003717 if( lemp->stacksize ){
drh75897232000-05-29 14:26:00 +00003718 fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize); lineno++;
3719 }else{
3720 fprintf(out,"#define YYSTACKDEPTH 100\n"); lineno++;
3721 }
drhca44b5a2007-02-22 23:06:58 +00003722 fprintf(out, "#endif\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003723 if( mhflag ){
3724 fprintf(out,"#if INTERFACE\n"); lineno++;
3725 }
3726 name = lemp->name ? lemp->name : "Parse";
3727 if( lemp->arg && lemp->arg[0] ){
3728 int i;
drh87cf1372008-08-13 20:09:06 +00003729 i = lemonStrlen(lemp->arg);
drhb1edd012000-06-02 18:52:12 +00003730 while( i>=1 && isspace(lemp->arg[i-1]) ) i--;
3731 while( i>=1 && (isalnum(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--;
drh1f245e42002-03-11 13:55:50 +00003732 fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg); lineno++;
3733 fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg); lineno++;
3734 fprintf(out,"#define %sARG_FETCH %s = yypParser->%s\n",
3735 name,lemp->arg,&lemp->arg[i]); lineno++;
3736 fprintf(out,"#define %sARG_STORE yypParser->%s = %s\n",
3737 name,&lemp->arg[i],&lemp->arg[i]); lineno++;
drh75897232000-05-29 14:26:00 +00003738 }else{
drh1f245e42002-03-11 13:55:50 +00003739 fprintf(out,"#define %sARG_SDECL\n",name); lineno++;
3740 fprintf(out,"#define %sARG_PDECL\n",name); lineno++;
3741 fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
3742 fprintf(out,"#define %sARG_STORE\n",name); lineno++;
drh75897232000-05-29 14:26:00 +00003743 }
3744 if( mhflag ){
3745 fprintf(out,"#endif\n"); lineno++;
3746 }
3747 fprintf(out,"#define YYNSTATE %d\n",lemp->nstate); lineno++;
3748 fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++;
drhc4dd3fd2008-01-22 01:48:05 +00003749 if( lemp->errsym->useCnt ){
3750 fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;
3751 fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;
3752 }
drh0bd1f4e2002-06-06 18:54:39 +00003753 if( lemp->has_fallback ){
3754 fprintf(out,"#define YYFALLBACK 1\n"); lineno++;
3755 }
drh75897232000-05-29 14:26:00 +00003756 tplt_xfer(lemp->name,in,out,&lineno);
3757
drh8b582012003-10-21 13:16:03 +00003758 /* Generate the action table and its associates:
drh75897232000-05-29 14:26:00 +00003759 **
drh8b582012003-10-21 13:16:03 +00003760 ** yy_action[] A single table containing all actions.
3761 ** yy_lookahead[] A table containing the lookahead for each entry in
3762 ** yy_action. Used to detect hash collisions.
3763 ** yy_shift_ofst[] For each state, the offset into yy_action for
3764 ** shifting terminals.
3765 ** yy_reduce_ofst[] For each state, the offset into yy_action for
3766 ** shifting non-terminals after a reduce.
3767 ** yy_default[] Default action for each state.
drh75897232000-05-29 14:26:00 +00003768 */
drh75897232000-05-29 14:26:00 +00003769
drh8b582012003-10-21 13:16:03 +00003770 /* Compute the actions on all states and count them up */
drh9892c5d2007-12-21 00:02:11 +00003771 ax = calloc(lemp->nstate*2, sizeof(ax[0]));
drhfdbf9282003-10-21 16:34:41 +00003772 if( ax==0 ){
3773 fprintf(stderr,"malloc failed\n");
3774 exit(1);
3775 }
drh75897232000-05-29 14:26:00 +00003776 for(i=0; i<lemp->nstate; i++){
drh75897232000-05-29 14:26:00 +00003777 stp = lemp->sorted[i];
drhfdbf9282003-10-21 16:34:41 +00003778 ax[i*2].stp = stp;
3779 ax[i*2].isTkn = 1;
3780 ax[i*2].nAction = stp->nTknAct;
3781 ax[i*2+1].stp = stp;
3782 ax[i*2+1].isTkn = 0;
3783 ax[i*2+1].nAction = stp->nNtAct;
drh75897232000-05-29 14:26:00 +00003784 }
drh8b582012003-10-21 13:16:03 +00003785 mxTknOfst = mnTknOfst = 0;
3786 mxNtOfst = mnNtOfst = 0;
3787
drhfdbf9282003-10-21 16:34:41 +00003788 /* Compute the action table. In order to try to keep the size of the
3789 ** action table to a minimum, the heuristic of placing the largest action
3790 ** sets first is used.
drh8b582012003-10-21 13:16:03 +00003791 */
drhe594bc32009-11-03 13:02:25 +00003792 for(i=0; i<lemp->nstate*2; i++) ax[i].iOrder = i;
drhfdbf9282003-10-21 16:34:41 +00003793 qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
drh8b582012003-10-21 13:16:03 +00003794 pActtab = acttab_alloc();
drhfdbf9282003-10-21 16:34:41 +00003795 for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
3796 stp = ax[i].stp;
3797 if( ax[i].isTkn ){
3798 for(ap=stp->ap; ap; ap=ap->next){
3799 int action;
3800 if( ap->sp->index>=lemp->nterminal ) continue;
3801 action = compute_action(lemp, ap);
3802 if( action<0 ) continue;
3803 acttab_action(pActtab, ap->sp->index, action);
drh8b582012003-10-21 13:16:03 +00003804 }
drhfdbf9282003-10-21 16:34:41 +00003805 stp->iTknOfst = acttab_insert(pActtab);
3806 if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
3807 if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
3808 }else{
3809 for(ap=stp->ap; ap; ap=ap->next){
3810 int action;
3811 if( ap->sp->index<lemp->nterminal ) continue;
3812 if( ap->sp->index==lemp->nsymbol ) continue;
3813 action = compute_action(lemp, ap);
3814 if( action<0 ) continue;
3815 acttab_action(pActtab, ap->sp->index, action);
drh8b582012003-10-21 13:16:03 +00003816 }
drhfdbf9282003-10-21 16:34:41 +00003817 stp->iNtOfst = acttab_insert(pActtab);
3818 if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
3819 if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
drh8b582012003-10-21 13:16:03 +00003820 }
3821 }
drhfdbf9282003-10-21 16:34:41 +00003822 free(ax);
drh8b582012003-10-21 13:16:03 +00003823
3824 /* Output the yy_action table */
drh8b582012003-10-21 13:16:03 +00003825 n = acttab_size(pActtab);
drhf16371d2009-11-03 19:18:31 +00003826 fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
3827 fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
drh8b582012003-10-21 13:16:03 +00003828 for(i=j=0; i<n; i++){
3829 int action = acttab_yyaction(pActtab, i);
drhe0479212007-01-12 23:09:23 +00003830 if( action<0 ) action = lemp->nstate + lemp->nrule + 2;
drhfdbf9282003-10-21 16:34:41 +00003831 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003832 fprintf(out, " %4d,", action);
3833 if( j==9 || i==n-1 ){
3834 fprintf(out, "\n"); lineno++;
3835 j = 0;
3836 }else{
3837 j++;
3838 }
3839 }
3840 fprintf(out, "};\n"); lineno++;
3841
3842 /* Output the yy_lookahead table */
drh57196282004-10-06 15:41:16 +00003843 fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
drh8b582012003-10-21 13:16:03 +00003844 for(i=j=0; i<n; i++){
3845 int la = acttab_yylookahead(pActtab, i);
3846 if( la<0 ) la = lemp->nsymbol;
drhfdbf9282003-10-21 16:34:41 +00003847 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003848 fprintf(out, " %4d,", la);
3849 if( j==9 || i==n-1 ){
3850 fprintf(out, "\n"); lineno++;
3851 j = 0;
3852 }else{
3853 j++;
3854 }
3855 }
3856 fprintf(out, "};\n"); lineno++;
3857
3858 /* Output the yy_shift_ofst[] table */
3859 fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
drhada354d2005-11-05 15:03:59 +00003860 n = lemp->nstate;
3861 while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
drhf16371d2009-11-03 19:18:31 +00003862 fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;
3863 fprintf(out, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst); lineno++;
3864 fprintf(out, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst); lineno++;
drh57196282004-10-06 15:41:16 +00003865 fprintf(out, "static const %s yy_shift_ofst[] = {\n",
drh8b582012003-10-21 13:16:03 +00003866 minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
drh8b582012003-10-21 13:16:03 +00003867 for(i=j=0; i<n; i++){
3868 int ofst;
3869 stp = lemp->sorted[i];
3870 ofst = stp->iTknOfst;
3871 if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;
drhfdbf9282003-10-21 16:34:41 +00003872 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003873 fprintf(out, " %4d,", ofst);
3874 if( j==9 || i==n-1 ){
3875 fprintf(out, "\n"); lineno++;
3876 j = 0;
3877 }else{
3878 j++;
3879 }
3880 }
3881 fprintf(out, "};\n"); lineno++;
3882
3883 /* Output the yy_reduce_ofst[] table */
3884 fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
drhada354d2005-11-05 15:03:59 +00003885 n = lemp->nstate;
3886 while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
drhf16371d2009-11-03 19:18:31 +00003887 fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
3888 fprintf(out, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst); lineno++;
3889 fprintf(out, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst); lineno++;
drh57196282004-10-06 15:41:16 +00003890 fprintf(out, "static const %s yy_reduce_ofst[] = {\n",
drh8b582012003-10-21 13:16:03 +00003891 minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
drh8b582012003-10-21 13:16:03 +00003892 for(i=j=0; i<n; i++){
3893 int ofst;
3894 stp = lemp->sorted[i];
3895 ofst = stp->iNtOfst;
3896 if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
drhfdbf9282003-10-21 16:34:41 +00003897 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003898 fprintf(out, " %4d,", ofst);
3899 if( j==9 || i==n-1 ){
3900 fprintf(out, "\n"); lineno++;
3901 j = 0;
3902 }else{
3903 j++;
3904 }
3905 }
3906 fprintf(out, "};\n"); lineno++;
3907
3908 /* Output the default action table */
drh57196282004-10-06 15:41:16 +00003909 fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
drh8b582012003-10-21 13:16:03 +00003910 n = lemp->nstate;
3911 for(i=j=0; i<n; i++){
3912 stp = lemp->sorted[i];
drhfdbf9282003-10-21 16:34:41 +00003913 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003914 fprintf(out, " %4d,", stp->iDflt);
3915 if( j==9 || i==n-1 ){
3916 fprintf(out, "\n"); lineno++;
3917 j = 0;
3918 }else{
3919 j++;
3920 }
3921 }
3922 fprintf(out, "};\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003923 tplt_xfer(lemp->name,in,out,&lineno);
3924
drh0bd1f4e2002-06-06 18:54:39 +00003925 /* Generate the table of fallback tokens.
3926 */
3927 if( lemp->has_fallback ){
drh1441f3e2009-06-12 12:50:50 +00003928 int mx = lemp->nterminal - 1;
3929 while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; }
3930 for(i=0; i<=mx; i++){
drh0bd1f4e2002-06-06 18:54:39 +00003931 struct symbol *p = lemp->symbols[i];
3932 if( p->fallback==0 ){
3933 fprintf(out, " 0, /* %10s => nothing */\n", p->name);
3934 }else{
3935 fprintf(out, " %3d, /* %10s => %s */\n", p->fallback->index,
3936 p->name, p->fallback->name);
3937 }
3938 lineno++;
3939 }
3940 }
3941 tplt_xfer(lemp->name, in, out, &lineno);
3942
3943 /* Generate a table containing the symbolic name of every symbol
3944 */
drh75897232000-05-29 14:26:00 +00003945 for(i=0; i<lemp->nsymbol; i++){
3946 sprintf(line,"\"%s\",",lemp->symbols[i]->name);
3947 fprintf(out," %-15s",line);
3948 if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; }
3949 }
3950 if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; }
3951 tplt_xfer(lemp->name,in,out,&lineno);
3952
drh0bd1f4e2002-06-06 18:54:39 +00003953 /* Generate a table containing a text string that describes every
drh34ff57b2008-07-14 12:27:51 +00003954 ** rule in the rule set of the grammar. This information is used
drh0bd1f4e2002-06-06 18:54:39 +00003955 ** when tracing REDUCE actions.
3956 */
3957 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
3958 assert( rp->index==i );
drhc4dd3fd2008-01-22 01:48:05 +00003959 fprintf(out," /* %3d */ \"", i);
3960 writeRuleText(out, rp);
drh0bd1f4e2002-06-06 18:54:39 +00003961 fprintf(out,"\",\n"); lineno++;
3962 }
3963 tplt_xfer(lemp->name,in,out,&lineno);
3964
drh75897232000-05-29 14:26:00 +00003965 /* Generate code which executes every time a symbol is popped from
3966 ** the stack while processing errors or while destroying the parser.
drh0bd1f4e2002-06-06 18:54:39 +00003967 ** (In other words, generate the %destructor actions)
3968 */
drh75897232000-05-29 14:26:00 +00003969 if( lemp->tokendest ){
drh4dc8ef52008-07-01 17:13:57 +00003970 int once = 1;
drh75897232000-05-29 14:26:00 +00003971 for(i=0; i<lemp->nsymbol; i++){
3972 struct symbol *sp = lemp->symbols[i];
3973 if( sp==0 || sp->type!=TERMINAL ) continue;
drh4dc8ef52008-07-01 17:13:57 +00003974 if( once ){
3975 fprintf(out, " /* TERMINAL Destructor */\n"); lineno++;
3976 once = 0;
3977 }
drhc53eed12009-06-12 17:46:19 +00003978 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
drh75897232000-05-29 14:26:00 +00003979 }
3980 for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
3981 if( i<lemp->nsymbol ){
3982 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
3983 fprintf(out," break;\n"); lineno++;
3984 }
3985 }
drh8d659732005-01-13 23:54:06 +00003986 if( lemp->vardest ){
3987 struct symbol *dflt_sp = 0;
drh4dc8ef52008-07-01 17:13:57 +00003988 int once = 1;
drh8d659732005-01-13 23:54:06 +00003989 for(i=0; i<lemp->nsymbol; i++){
3990 struct symbol *sp = lemp->symbols[i];
3991 if( sp==0 || sp->type==TERMINAL ||
3992 sp->index<=0 || sp->destructor!=0 ) continue;
drh4dc8ef52008-07-01 17:13:57 +00003993 if( once ){
3994 fprintf(out, " /* Default NON-TERMINAL Destructor */\n"); lineno++;
3995 once = 0;
3996 }
drhc53eed12009-06-12 17:46:19 +00003997 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
drh8d659732005-01-13 23:54:06 +00003998 dflt_sp = sp;
3999 }
4000 if( dflt_sp!=0 ){
4001 emit_destructor_code(out,dflt_sp,lemp,&lineno);
drh8d659732005-01-13 23:54:06 +00004002 }
drh4dc8ef52008-07-01 17:13:57 +00004003 fprintf(out," break;\n"); lineno++;
drh8d659732005-01-13 23:54:06 +00004004 }
drh75897232000-05-29 14:26:00 +00004005 for(i=0; i<lemp->nsymbol; i++){
4006 struct symbol *sp = lemp->symbols[i];
4007 if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
drh75013012009-06-12 15:47:34 +00004008 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
drh0bb132b2004-07-20 14:06:51 +00004009
4010 /* Combine duplicate destructors into a single case */
4011 for(j=i+1; j<lemp->nsymbol; j++){
4012 struct symbol *sp2 = lemp->symbols[j];
4013 if( sp2 && sp2->type!=TERMINAL && sp2->destructor
4014 && sp2->dtnum==sp->dtnum
4015 && strcmp(sp->destructor,sp2->destructor)==0 ){
drhc53eed12009-06-12 17:46:19 +00004016 fprintf(out," case %d: /* %s */\n",
4017 sp2->index, sp2->name); lineno++;
drh0bb132b2004-07-20 14:06:51 +00004018 sp2->destructor = 0;
4019 }
4020 }
4021
drh75897232000-05-29 14:26:00 +00004022 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
4023 fprintf(out," break;\n"); lineno++;
4024 }
drh75897232000-05-29 14:26:00 +00004025 tplt_xfer(lemp->name,in,out,&lineno);
4026
4027 /* Generate code which executes whenever the parser stack overflows */
drha5808f32008-04-27 22:19:44 +00004028 tplt_print(out,lemp,lemp->overflow,&lineno);
drh75897232000-05-29 14:26:00 +00004029 tplt_xfer(lemp->name,in,out,&lineno);
4030
4031 /* Generate the table of rule information
4032 **
4033 ** Note: This code depends on the fact that rules are number
4034 ** sequentually beginning with 0.
4035 */
4036 for(rp=lemp->rule; rp; rp=rp->next){
4037 fprintf(out," { %d, %d },\n",rp->lhs->index,rp->nrhs); lineno++;
4038 }
4039 tplt_xfer(lemp->name,in,out,&lineno);
4040
4041 /* Generate code which execution during each REDUCE action */
4042 for(rp=lemp->rule; rp; rp=rp->next){
drh61e339a2007-01-16 03:09:02 +00004043 translate_code(lemp, rp);
drh0bb132b2004-07-20 14:06:51 +00004044 }
drhc53eed12009-06-12 17:46:19 +00004045 /* First output rules other than the default: rule */
drh0bb132b2004-07-20 14:06:51 +00004046 for(rp=lemp->rule; rp; rp=rp->next){
drhc53eed12009-06-12 17:46:19 +00004047 struct rule *rp2; /* Other rules with the same action */
drh0bb132b2004-07-20 14:06:51 +00004048 if( rp->code==0 ) continue;
drhc53eed12009-06-12 17:46:19 +00004049 if( rp->code[0]=='\n' && rp->code[1]==0 ) continue; /* Will be default: */
drhc4dd3fd2008-01-22 01:48:05 +00004050 fprintf(out," case %d: /* ", rp->index);
4051 writeRuleText(out, rp);
4052 fprintf(out, " */\n"); lineno++;
drh0bb132b2004-07-20 14:06:51 +00004053 for(rp2=rp->next; rp2; rp2=rp2->next){
4054 if( rp2->code==rp->code ){
drhc4dd3fd2008-01-22 01:48:05 +00004055 fprintf(out," case %d: /* ", rp2->index);
4056 writeRuleText(out, rp2);
drh8a415d32009-06-12 13:53:51 +00004057 fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->index); lineno++;
drh0bb132b2004-07-20 14:06:51 +00004058 rp2->code = 0;
4059 }
4060 }
drh75897232000-05-29 14:26:00 +00004061 emit_code(out,rp,lemp,&lineno);
4062 fprintf(out," break;\n"); lineno++;
drhc53eed12009-06-12 17:46:19 +00004063 rp->code = 0;
drh75897232000-05-29 14:26:00 +00004064 }
drhc53eed12009-06-12 17:46:19 +00004065 /* Finally, output the default: rule. We choose as the default: all
4066 ** empty actions. */
4067 fprintf(out," default:\n"); lineno++;
4068 for(rp=lemp->rule; rp; rp=rp->next){
4069 if( rp->code==0 ) continue;
4070 assert( rp->code[0]=='\n' && rp->code[1]==0 );
4071 fprintf(out," /* (%d) ", rp->index);
4072 writeRuleText(out, rp);
4073 fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->index); lineno++;
4074 }
4075 fprintf(out," break;\n"); lineno++;
drh75897232000-05-29 14:26:00 +00004076 tplt_xfer(lemp->name,in,out,&lineno);
4077
4078 /* Generate code which executes if a parse fails */
drha5808f32008-04-27 22:19:44 +00004079 tplt_print(out,lemp,lemp->failure,&lineno);
drh75897232000-05-29 14:26:00 +00004080 tplt_xfer(lemp->name,in,out,&lineno);
4081
4082 /* Generate code which executes when a syntax error occurs */
drha5808f32008-04-27 22:19:44 +00004083 tplt_print(out,lemp,lemp->error,&lineno);
drh75897232000-05-29 14:26:00 +00004084 tplt_xfer(lemp->name,in,out,&lineno);
4085
4086 /* Generate code which executes when the parser accepts its input */
drha5808f32008-04-27 22:19:44 +00004087 tplt_print(out,lemp,lemp->accept,&lineno);
drh75897232000-05-29 14:26:00 +00004088 tplt_xfer(lemp->name,in,out,&lineno);
4089
4090 /* Append any addition code the user desires */
drha5808f32008-04-27 22:19:44 +00004091 tplt_print(out,lemp,lemp->extracode,&lineno);
drh75897232000-05-29 14:26:00 +00004092
4093 fclose(in);
4094 fclose(out);
4095 return;
4096}
4097
4098/* Generate a header file for the parser */
4099void ReportHeader(lemp)
4100struct lemon *lemp;
4101{
4102 FILE *out, *in;
4103 char *prefix;
4104 char line[LINESIZE];
4105 char pattern[LINESIZE];
4106 int i;
4107
4108 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
4109 else prefix = "";
drh2aa6ca42004-09-10 00:14:04 +00004110 in = file_open(lemp,".h","rb");
drh75897232000-05-29 14:26:00 +00004111 if( in ){
4112 for(i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++){
4113 sprintf(pattern,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
4114 if( strcmp(line,pattern) ) break;
4115 }
4116 fclose(in);
4117 if( i==lemp->nterminal ){
4118 /* No change in the file. Don't rewrite it. */
4119 return;
4120 }
4121 }
drh2aa6ca42004-09-10 00:14:04 +00004122 out = file_open(lemp,".h","wb");
drh75897232000-05-29 14:26:00 +00004123 if( out ){
4124 for(i=1; i<lemp->nterminal; i++){
4125 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
4126 }
4127 fclose(out);
4128 }
4129 return;
4130}
4131
4132/* Reduce the size of the action tables, if possible, by making use
4133** of defaults.
4134**
drhb59499c2002-02-23 18:45:13 +00004135** In this version, we take the most frequent REDUCE action and make
drhe09daa92006-06-10 13:29:31 +00004136** it the default. Except, there is no default if the wildcard token
4137** is a possible look-ahead.
drh75897232000-05-29 14:26:00 +00004138*/
4139void CompressTables(lemp)
4140struct lemon *lemp;
4141{
4142 struct state *stp;
drhb59499c2002-02-23 18:45:13 +00004143 struct action *ap, *ap2;
4144 struct rule *rp, *rp2, *rbest;
4145 int nbest, n;
drh75897232000-05-29 14:26:00 +00004146 int i;
drhe09daa92006-06-10 13:29:31 +00004147 int usesWildcard;
drh75897232000-05-29 14:26:00 +00004148
4149 for(i=0; i<lemp->nstate; i++){
4150 stp = lemp->sorted[i];
drhb59499c2002-02-23 18:45:13 +00004151 nbest = 0;
4152 rbest = 0;
drhe09daa92006-06-10 13:29:31 +00004153 usesWildcard = 0;
drh75897232000-05-29 14:26:00 +00004154
drhb59499c2002-02-23 18:45:13 +00004155 for(ap=stp->ap; ap; ap=ap->next){
drhe09daa92006-06-10 13:29:31 +00004156 if( ap->type==SHIFT && ap->sp==lemp->wildcard ){
4157 usesWildcard = 1;
4158 }
drhb59499c2002-02-23 18:45:13 +00004159 if( ap->type!=REDUCE ) continue;
4160 rp = ap->x.rp;
drhb4960992007-10-05 16:16:36 +00004161 if( rp->lhsStart ) continue;
drhb59499c2002-02-23 18:45:13 +00004162 if( rp==rbest ) continue;
4163 n = 1;
4164 for(ap2=ap->next; ap2; ap2=ap2->next){
4165 if( ap2->type!=REDUCE ) continue;
4166 rp2 = ap2->x.rp;
4167 if( rp2==rbest ) continue;
4168 if( rp2==rp ) n++;
4169 }
4170 if( n>nbest ){
4171 nbest = n;
4172 rbest = rp;
drh75897232000-05-29 14:26:00 +00004173 }
4174 }
drhb59499c2002-02-23 18:45:13 +00004175
4176 /* Do not make a default if the number of rules to default
drhe09daa92006-06-10 13:29:31 +00004177 ** is not at least 1 or if the wildcard token is a possible
4178 ** lookahead.
4179 */
4180 if( nbest<1 || usesWildcard ) continue;
drh75897232000-05-29 14:26:00 +00004181
drhb59499c2002-02-23 18:45:13 +00004182
4183 /* Combine matching REDUCE actions into a single default */
4184 for(ap=stp->ap; ap; ap=ap->next){
4185 if( ap->type==REDUCE && ap->x.rp==rbest ) break;
4186 }
drh75897232000-05-29 14:26:00 +00004187 assert( ap );
4188 ap->sp = Symbol_new("{default}");
4189 for(ap=ap->next; ap; ap=ap->next){
drhb59499c2002-02-23 18:45:13 +00004190 if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
drh75897232000-05-29 14:26:00 +00004191 }
4192 stp->ap = Action_sort(stp->ap);
4193 }
4194}
drhb59499c2002-02-23 18:45:13 +00004195
drhada354d2005-11-05 15:03:59 +00004196
4197/*
4198** Compare two states for sorting purposes. The smaller state is the
4199** one with the most non-terminal actions. If they have the same number
4200** of non-terminal actions, then the smaller is the one with the most
4201** token actions.
4202*/
4203static int stateResortCompare(const void *a, const void *b){
4204 const struct state *pA = *(const struct state**)a;
4205 const struct state *pB = *(const struct state**)b;
4206 int n;
4207
4208 n = pB->nNtAct - pA->nNtAct;
4209 if( n==0 ){
4210 n = pB->nTknAct - pA->nTknAct;
drhe594bc32009-11-03 13:02:25 +00004211 if( n==0 ){
4212 n = pB->statenum - pA->statenum;
4213 }
drhada354d2005-11-05 15:03:59 +00004214 }
drhe594bc32009-11-03 13:02:25 +00004215 assert( n!=0 );
drhada354d2005-11-05 15:03:59 +00004216 return n;
4217}
4218
4219
4220/*
4221** Renumber and resort states so that states with fewer choices
4222** occur at the end. Except, keep state 0 as the first state.
4223*/
4224void ResortStates(lemp)
4225struct lemon *lemp;
4226{
4227 int i;
4228 struct state *stp;
4229 struct action *ap;
4230
4231 for(i=0; i<lemp->nstate; i++){
4232 stp = lemp->sorted[i];
4233 stp->nTknAct = stp->nNtAct = 0;
4234 stp->iDflt = lemp->nstate + lemp->nrule;
4235 stp->iTknOfst = NO_OFFSET;
4236 stp->iNtOfst = NO_OFFSET;
4237 for(ap=stp->ap; ap; ap=ap->next){
4238 if( compute_action(lemp,ap)>=0 ){
4239 if( ap->sp->index<lemp->nterminal ){
4240 stp->nTknAct++;
4241 }else if( ap->sp->index<lemp->nsymbol ){
4242 stp->nNtAct++;
4243 }else{
4244 stp->iDflt = compute_action(lemp, ap);
4245 }
4246 }
4247 }
4248 }
4249 qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
4250 stateResortCompare);
4251 for(i=0; i<lemp->nstate; i++){
4252 lemp->sorted[i]->statenum = i;
4253 }
4254}
4255
4256
drh75897232000-05-29 14:26:00 +00004257/***************** From the file "set.c" ************************************/
4258/*
4259** Set manipulation routines for the LEMON parser generator.
4260*/
4261
4262static int size = 0;
4263
4264/* Set the set size */
4265void SetSize(n)
4266int n;
4267{
4268 size = n+1;
4269}
4270
4271/* Allocate a new set */
4272char *SetNew(){
4273 char *s;
drh9892c5d2007-12-21 00:02:11 +00004274 s = (char*)calloc( size, 1);
drh75897232000-05-29 14:26:00 +00004275 if( s==0 ){
4276 extern void memory_error();
4277 memory_error();
4278 }
drh75897232000-05-29 14:26:00 +00004279 return s;
4280}
4281
4282/* Deallocate a set */
4283void SetFree(s)
4284char *s;
4285{
4286 free(s);
4287}
4288
4289/* Add a new element to the set. Return TRUE if the element was added
4290** and FALSE if it was already there. */
4291int SetAdd(s,e)
4292char *s;
4293int e;
4294{
4295 int rv;
drh9892c5d2007-12-21 00:02:11 +00004296 assert( e>=0 && e<size );
drh75897232000-05-29 14:26:00 +00004297 rv = s[e];
4298 s[e] = 1;
4299 return !rv;
4300}
4301
4302/* Add every element of s2 to s1. Return TRUE if s1 changes. */
4303int SetUnion(s1,s2)
4304char *s1;
4305char *s2;
4306{
4307 int i, progress;
4308 progress = 0;
4309 for(i=0; i<size; i++){
4310 if( s2[i]==0 ) continue;
4311 if( s1[i]==0 ){
4312 progress = 1;
4313 s1[i] = 1;
4314 }
4315 }
4316 return progress;
4317}
4318/********************** From the file "table.c" ****************************/
4319/*
4320** All code in this file has been automatically generated
4321** from a specification in the file
4322** "table.q"
4323** by the associative array code building program "aagen".
4324** Do not edit this file! Instead, edit the specification
4325** file, then rerun aagen.
4326*/
4327/*
4328** Code for processing tables in the LEMON parser generator.
4329*/
4330
4331PRIVATE int strhash(x)
4332char *x;
4333{
4334 int h = 0;
4335 while( *x) h = h*13 + *(x++);
4336 return h;
4337}
4338
4339/* Works like strdup, sort of. Save a string in malloced memory, but
4340** keep strings in a table so that the same string is not in more
4341** than one place.
4342*/
4343char *Strsafe(y)
4344char *y;
4345{
4346 char *z;
4347
drh916f75f2006-07-17 00:19:39 +00004348 if( y==0 ) return 0;
drh75897232000-05-29 14:26:00 +00004349 z = Strsafe_find(y);
drh87cf1372008-08-13 20:09:06 +00004350 if( z==0 && (z=malloc( lemonStrlen(y)+1 ))!=0 ){
drh75897232000-05-29 14:26:00 +00004351 strcpy(z,y);
4352 Strsafe_insert(z);
4353 }
4354 MemoryCheck(z);
4355 return z;
4356}
4357
4358/* There is one instance of the following structure for each
4359** associative array of type "x1".
4360*/
4361struct s_x1 {
4362 int size; /* The number of available slots. */
4363 /* Must be a power of 2 greater than or */
4364 /* equal to 1 */
4365 int count; /* Number of currently slots filled */
4366 struct s_x1node *tbl; /* The data stored here */
4367 struct s_x1node **ht; /* Hash table for lookups */
4368};
4369
4370/* There is one instance of this structure for every data element
4371** in an associative array of type "x1".
4372*/
4373typedef struct s_x1node {
4374 char *data; /* The data */
4375 struct s_x1node *next; /* Next entry with the same hash */
4376 struct s_x1node **from; /* Previous link */
4377} x1node;
4378
4379/* There is only one instance of the array, which is the following */
4380static struct s_x1 *x1a;
4381
4382/* Allocate a new associative array */
4383void Strsafe_init(){
4384 if( x1a ) return;
4385 x1a = (struct s_x1*)malloc( sizeof(struct s_x1) );
4386 if( x1a ){
4387 x1a->size = 1024;
4388 x1a->count = 0;
4389 x1a->tbl = (x1node*)malloc(
4390 (sizeof(x1node) + sizeof(x1node*))*1024 );
4391 if( x1a->tbl==0 ){
4392 free(x1a);
4393 x1a = 0;
4394 }else{
4395 int i;
4396 x1a->ht = (x1node**)&(x1a->tbl[1024]);
4397 for(i=0; i<1024; i++) x1a->ht[i] = 0;
4398 }
4399 }
4400}
4401/* Insert a new record into the array. Return TRUE if successful.
4402** Prior data with the same key is NOT overwritten */
4403int Strsafe_insert(data)
4404char *data;
4405{
4406 x1node *np;
4407 int h;
4408 int ph;
4409
4410 if( x1a==0 ) return 0;
4411 ph = strhash(data);
4412 h = ph & (x1a->size-1);
4413 np = x1a->ht[h];
4414 while( np ){
4415 if( strcmp(np->data,data)==0 ){
4416 /* An existing entry with the same key is found. */
4417 /* Fail because overwrite is not allows. */
4418 return 0;
4419 }
4420 np = np->next;
4421 }
4422 if( x1a->count>=x1a->size ){
4423 /* Need to make the hash table bigger */
4424 int i,size;
4425 struct s_x1 array;
4426 array.size = size = x1a->size*2;
4427 array.count = x1a->count;
4428 array.tbl = (x1node*)malloc(
4429 (sizeof(x1node) + sizeof(x1node*))*size );
4430 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4431 array.ht = (x1node**)&(array.tbl[size]);
4432 for(i=0; i<size; i++) array.ht[i] = 0;
4433 for(i=0; i<x1a->count; i++){
4434 x1node *oldnp, *newnp;
4435 oldnp = &(x1a->tbl[i]);
4436 h = strhash(oldnp->data) & (size-1);
4437 newnp = &(array.tbl[i]);
4438 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4439 newnp->next = array.ht[h];
4440 newnp->data = oldnp->data;
4441 newnp->from = &(array.ht[h]);
4442 array.ht[h] = newnp;
4443 }
4444 free(x1a->tbl);
4445 *x1a = array;
4446 }
4447 /* Insert the new data */
4448 h = ph & (x1a->size-1);
4449 np = &(x1a->tbl[x1a->count++]);
4450 np->data = data;
4451 if( x1a->ht[h] ) x1a->ht[h]->from = &(np->next);
4452 np->next = x1a->ht[h];
4453 x1a->ht[h] = np;
4454 np->from = &(x1a->ht[h]);
4455 return 1;
4456}
4457
4458/* Return a pointer to data assigned to the given key. Return NULL
4459** if no such key. */
4460char *Strsafe_find(key)
4461char *key;
4462{
4463 int h;
4464 x1node *np;
4465
4466 if( x1a==0 ) return 0;
4467 h = strhash(key) & (x1a->size-1);
4468 np = x1a->ht[h];
4469 while( np ){
4470 if( strcmp(np->data,key)==0 ) break;
4471 np = np->next;
4472 }
4473 return np ? np->data : 0;
4474}
4475
4476/* Return a pointer to the (terminal or nonterminal) symbol "x".
4477** Create a new symbol if this is the first time "x" has been seen.
4478*/
4479struct symbol *Symbol_new(x)
4480char *x;
4481{
4482 struct symbol *sp;
4483
4484 sp = Symbol_find(x);
4485 if( sp==0 ){
drh9892c5d2007-12-21 00:02:11 +00004486 sp = (struct symbol *)calloc(1, sizeof(struct symbol) );
drh75897232000-05-29 14:26:00 +00004487 MemoryCheck(sp);
4488 sp->name = Strsafe(x);
4489 sp->type = isupper(*x) ? TERMINAL : NONTERMINAL;
4490 sp->rule = 0;
drh0bd1f4e2002-06-06 18:54:39 +00004491 sp->fallback = 0;
drh75897232000-05-29 14:26:00 +00004492 sp->prec = -1;
4493 sp->assoc = UNK;
4494 sp->firstset = 0;
drhaa9f1122007-08-23 02:50:56 +00004495 sp->lambda = LEMON_FALSE;
drh75897232000-05-29 14:26:00 +00004496 sp->destructor = 0;
drh4dc8ef52008-07-01 17:13:57 +00004497 sp->destLineno = 0;
drh75897232000-05-29 14:26:00 +00004498 sp->datatype = 0;
drhc4dd3fd2008-01-22 01:48:05 +00004499 sp->useCnt = 0;
drh75897232000-05-29 14:26:00 +00004500 Symbol_insert(sp,sp->name);
4501 }
drhc4dd3fd2008-01-22 01:48:05 +00004502 sp->useCnt++;
drh75897232000-05-29 14:26:00 +00004503 return sp;
4504}
4505
drh60d31652004-02-22 00:08:04 +00004506/* Compare two symbols for working purposes
4507**
4508** Symbols that begin with upper case letters (terminals or tokens)
4509** must sort before symbols that begin with lower case letters
4510** (non-terminals). Other than that, the order does not matter.
4511**
4512** We find experimentally that leaving the symbols in their original
4513** order (the order they appeared in the grammar file) gives the
4514** smallest parser tables in SQLite.
4515*/
4516int Symbolcmpp(struct symbol **a, struct symbol **b){
4517 int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
4518 int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
drhe594bc32009-11-03 13:02:25 +00004519 assert( i1!=i2 || strcmp((**a).name,(**b).name)==0 );
drh60d31652004-02-22 00:08:04 +00004520 return i1-i2;
drh75897232000-05-29 14:26:00 +00004521}
4522
4523/* There is one instance of the following structure for each
4524** associative array of type "x2".
4525*/
4526struct s_x2 {
4527 int size; /* The number of available slots. */
4528 /* Must be a power of 2 greater than or */
4529 /* equal to 1 */
4530 int count; /* Number of currently slots filled */
4531 struct s_x2node *tbl; /* The data stored here */
4532 struct s_x2node **ht; /* Hash table for lookups */
4533};
4534
4535/* There is one instance of this structure for every data element
4536** in an associative array of type "x2".
4537*/
4538typedef struct s_x2node {
4539 struct symbol *data; /* The data */
4540 char *key; /* The key */
4541 struct s_x2node *next; /* Next entry with the same hash */
4542 struct s_x2node **from; /* Previous link */
4543} x2node;
4544
4545/* There is only one instance of the array, which is the following */
4546static struct s_x2 *x2a;
4547
4548/* Allocate a new associative array */
4549void Symbol_init(){
4550 if( x2a ) return;
4551 x2a = (struct s_x2*)malloc( sizeof(struct s_x2) );
4552 if( x2a ){
4553 x2a->size = 128;
4554 x2a->count = 0;
4555 x2a->tbl = (x2node*)malloc(
4556 (sizeof(x2node) + sizeof(x2node*))*128 );
4557 if( x2a->tbl==0 ){
4558 free(x2a);
4559 x2a = 0;
4560 }else{
4561 int i;
4562 x2a->ht = (x2node**)&(x2a->tbl[128]);
4563 for(i=0; i<128; i++) x2a->ht[i] = 0;
4564 }
4565 }
4566}
4567/* Insert a new record into the array. Return TRUE if successful.
4568** Prior data with the same key is NOT overwritten */
4569int Symbol_insert(data,key)
4570struct symbol *data;
4571char *key;
4572{
4573 x2node *np;
4574 int h;
4575 int ph;
4576
4577 if( x2a==0 ) return 0;
4578 ph = strhash(key);
4579 h = ph & (x2a->size-1);
4580 np = x2a->ht[h];
4581 while( np ){
4582 if( strcmp(np->key,key)==0 ){
4583 /* An existing entry with the same key is found. */
4584 /* Fail because overwrite is not allows. */
4585 return 0;
4586 }
4587 np = np->next;
4588 }
4589 if( x2a->count>=x2a->size ){
4590 /* Need to make the hash table bigger */
4591 int i,size;
4592 struct s_x2 array;
4593 array.size = size = x2a->size*2;
4594 array.count = x2a->count;
4595 array.tbl = (x2node*)malloc(
4596 (sizeof(x2node) + sizeof(x2node*))*size );
4597 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4598 array.ht = (x2node**)&(array.tbl[size]);
4599 for(i=0; i<size; i++) array.ht[i] = 0;
4600 for(i=0; i<x2a->count; i++){
4601 x2node *oldnp, *newnp;
4602 oldnp = &(x2a->tbl[i]);
4603 h = strhash(oldnp->key) & (size-1);
4604 newnp = &(array.tbl[i]);
4605 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4606 newnp->next = array.ht[h];
4607 newnp->key = oldnp->key;
4608 newnp->data = oldnp->data;
4609 newnp->from = &(array.ht[h]);
4610 array.ht[h] = newnp;
4611 }
4612 free(x2a->tbl);
4613 *x2a = array;
4614 }
4615 /* Insert the new data */
4616 h = ph & (x2a->size-1);
4617 np = &(x2a->tbl[x2a->count++]);
4618 np->key = key;
4619 np->data = data;
4620 if( x2a->ht[h] ) x2a->ht[h]->from = &(np->next);
4621 np->next = x2a->ht[h];
4622 x2a->ht[h] = np;
4623 np->from = &(x2a->ht[h]);
4624 return 1;
4625}
4626
4627/* Return a pointer to data assigned to the given key. Return NULL
4628** if no such key. */
4629struct symbol *Symbol_find(key)
4630char *key;
4631{
4632 int h;
4633 x2node *np;
4634
4635 if( x2a==0 ) return 0;
4636 h = strhash(key) & (x2a->size-1);
4637 np = x2a->ht[h];
4638 while( np ){
4639 if( strcmp(np->key,key)==0 ) break;
4640 np = np->next;
4641 }
4642 return np ? np->data : 0;
4643}
4644
4645/* Return the n-th data. Return NULL if n is out of range. */
4646struct symbol *Symbol_Nth(n)
4647int n;
4648{
4649 struct symbol *data;
4650 if( x2a && n>0 && n<=x2a->count ){
4651 data = x2a->tbl[n-1].data;
4652 }else{
4653 data = 0;
4654 }
4655 return data;
4656}
4657
4658/* Return the size of the array */
4659int Symbol_count()
4660{
4661 return x2a ? x2a->count : 0;
4662}
4663
4664/* Return an array of pointers to all data in the table.
4665** The array is obtained from malloc. Return NULL if memory allocation
4666** problems, or if the array is empty. */
4667struct symbol **Symbol_arrayof()
4668{
4669 struct symbol **array;
4670 int i,size;
4671 if( x2a==0 ) return 0;
4672 size = x2a->count;
drh9892c5d2007-12-21 00:02:11 +00004673 array = (struct symbol **)calloc(size, sizeof(struct symbol *));
drh75897232000-05-29 14:26:00 +00004674 if( array ){
4675 for(i=0; i<size; i++) array[i] = x2a->tbl[i].data;
4676 }
4677 return array;
4678}
4679
4680/* Compare two configurations */
4681int Configcmp(a,b)
4682struct config *a;
4683struct config *b;
4684{
4685 int x;
4686 x = a->rp->index - b->rp->index;
4687 if( x==0 ) x = a->dot - b->dot;
4688 return x;
4689}
4690
4691/* Compare two states */
4692PRIVATE int statecmp(a,b)
4693struct config *a;
4694struct config *b;
4695{
4696 int rc;
4697 for(rc=0; rc==0 && a && b; a=a->bp, b=b->bp){
4698 rc = a->rp->index - b->rp->index;
4699 if( rc==0 ) rc = a->dot - b->dot;
4700 }
4701 if( rc==0 ){
4702 if( a ) rc = 1;
4703 if( b ) rc = -1;
4704 }
4705 return rc;
4706}
4707
4708/* Hash a state */
4709PRIVATE int statehash(a)
4710struct config *a;
4711{
4712 int h=0;
4713 while( a ){
4714 h = h*571 + a->rp->index*37 + a->dot;
4715 a = a->bp;
4716 }
4717 return h;
4718}
4719
4720/* Allocate a new state structure */
4721struct state *State_new()
4722{
4723 struct state *new;
drh9892c5d2007-12-21 00:02:11 +00004724 new = (struct state *)calloc(1, sizeof(struct state) );
drh75897232000-05-29 14:26:00 +00004725 MemoryCheck(new);
4726 return new;
4727}
4728
4729/* There is one instance of the following structure for each
4730** associative array of type "x3".
4731*/
4732struct s_x3 {
4733 int size; /* The number of available slots. */
4734 /* Must be a power of 2 greater than or */
4735 /* equal to 1 */
4736 int count; /* Number of currently slots filled */
4737 struct s_x3node *tbl; /* The data stored here */
4738 struct s_x3node **ht; /* Hash table for lookups */
4739};
4740
4741/* There is one instance of this structure for every data element
4742** in an associative array of type "x3".
4743*/
4744typedef struct s_x3node {
4745 struct state *data; /* The data */
4746 struct config *key; /* The key */
4747 struct s_x3node *next; /* Next entry with the same hash */
4748 struct s_x3node **from; /* Previous link */
4749} x3node;
4750
4751/* There is only one instance of the array, which is the following */
4752static struct s_x3 *x3a;
4753
4754/* Allocate a new associative array */
4755void State_init(){
4756 if( x3a ) return;
4757 x3a = (struct s_x3*)malloc( sizeof(struct s_x3) );
4758 if( x3a ){
4759 x3a->size = 128;
4760 x3a->count = 0;
4761 x3a->tbl = (x3node*)malloc(
4762 (sizeof(x3node) + sizeof(x3node*))*128 );
4763 if( x3a->tbl==0 ){
4764 free(x3a);
4765 x3a = 0;
4766 }else{
4767 int i;
4768 x3a->ht = (x3node**)&(x3a->tbl[128]);
4769 for(i=0; i<128; i++) x3a->ht[i] = 0;
4770 }
4771 }
4772}
4773/* Insert a new record into the array. Return TRUE if successful.
4774** Prior data with the same key is NOT overwritten */
4775int State_insert(data,key)
4776struct state *data;
4777struct config *key;
4778{
4779 x3node *np;
4780 int h;
4781 int ph;
4782
4783 if( x3a==0 ) return 0;
4784 ph = statehash(key);
4785 h = ph & (x3a->size-1);
4786 np = x3a->ht[h];
4787 while( np ){
4788 if( statecmp(np->key,key)==0 ){
4789 /* An existing entry with the same key is found. */
4790 /* Fail because overwrite is not allows. */
4791 return 0;
4792 }
4793 np = np->next;
4794 }
4795 if( x3a->count>=x3a->size ){
4796 /* Need to make the hash table bigger */
4797 int i,size;
4798 struct s_x3 array;
4799 array.size = size = x3a->size*2;
4800 array.count = x3a->count;
4801 array.tbl = (x3node*)malloc(
4802 (sizeof(x3node) + sizeof(x3node*))*size );
4803 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4804 array.ht = (x3node**)&(array.tbl[size]);
4805 for(i=0; i<size; i++) array.ht[i] = 0;
4806 for(i=0; i<x3a->count; i++){
4807 x3node *oldnp, *newnp;
4808 oldnp = &(x3a->tbl[i]);
4809 h = statehash(oldnp->key) & (size-1);
4810 newnp = &(array.tbl[i]);
4811 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4812 newnp->next = array.ht[h];
4813 newnp->key = oldnp->key;
4814 newnp->data = oldnp->data;
4815 newnp->from = &(array.ht[h]);
4816 array.ht[h] = newnp;
4817 }
4818 free(x3a->tbl);
4819 *x3a = array;
4820 }
4821 /* Insert the new data */
4822 h = ph & (x3a->size-1);
4823 np = &(x3a->tbl[x3a->count++]);
4824 np->key = key;
4825 np->data = data;
4826 if( x3a->ht[h] ) x3a->ht[h]->from = &(np->next);
4827 np->next = x3a->ht[h];
4828 x3a->ht[h] = np;
4829 np->from = &(x3a->ht[h]);
4830 return 1;
4831}
4832
4833/* Return a pointer to data assigned to the given key. Return NULL
4834** if no such key. */
4835struct state *State_find(key)
4836struct config *key;
4837{
4838 int h;
4839 x3node *np;
4840
4841 if( x3a==0 ) return 0;
4842 h = statehash(key) & (x3a->size-1);
4843 np = x3a->ht[h];
4844 while( np ){
4845 if( statecmp(np->key,key)==0 ) break;
4846 np = np->next;
4847 }
4848 return np ? np->data : 0;
4849}
4850
4851/* Return an array of pointers to all data in the table.
4852** The array is obtained from malloc. Return NULL if memory allocation
4853** problems, or if the array is empty. */
4854struct state **State_arrayof()
4855{
4856 struct state **array;
4857 int i,size;
4858 if( x3a==0 ) return 0;
4859 size = x3a->count;
4860 array = (struct state **)malloc( sizeof(struct state *)*size );
4861 if( array ){
4862 for(i=0; i<size; i++) array[i] = x3a->tbl[i].data;
4863 }
4864 return array;
4865}
4866
4867/* Hash a configuration */
4868PRIVATE int confighash(a)
4869struct config *a;
4870{
4871 int h=0;
4872 h = h*571 + a->rp->index*37 + a->dot;
4873 return h;
4874}
4875
4876/* There is one instance of the following structure for each
4877** associative array of type "x4".
4878*/
4879struct s_x4 {
4880 int size; /* The number of available slots. */
4881 /* Must be a power of 2 greater than or */
4882 /* equal to 1 */
4883 int count; /* Number of currently slots filled */
4884 struct s_x4node *tbl; /* The data stored here */
4885 struct s_x4node **ht; /* Hash table for lookups */
4886};
4887
4888/* There is one instance of this structure for every data element
4889** in an associative array of type "x4".
4890*/
4891typedef struct s_x4node {
4892 struct config *data; /* The data */
4893 struct s_x4node *next; /* Next entry with the same hash */
4894 struct s_x4node **from; /* Previous link */
4895} x4node;
4896
4897/* There is only one instance of the array, which is the following */
4898static struct s_x4 *x4a;
4899
4900/* Allocate a new associative array */
4901void Configtable_init(){
4902 if( x4a ) return;
4903 x4a = (struct s_x4*)malloc( sizeof(struct s_x4) );
4904 if( x4a ){
4905 x4a->size = 64;
4906 x4a->count = 0;
4907 x4a->tbl = (x4node*)malloc(
4908 (sizeof(x4node) + sizeof(x4node*))*64 );
4909 if( x4a->tbl==0 ){
4910 free(x4a);
4911 x4a = 0;
4912 }else{
4913 int i;
4914 x4a->ht = (x4node**)&(x4a->tbl[64]);
4915 for(i=0; i<64; i++) x4a->ht[i] = 0;
4916 }
4917 }
4918}
4919/* Insert a new record into the array. Return TRUE if successful.
4920** Prior data with the same key is NOT overwritten */
4921int Configtable_insert(data)
4922struct config *data;
4923{
4924 x4node *np;
4925 int h;
4926 int ph;
4927
4928 if( x4a==0 ) return 0;
4929 ph = confighash(data);
4930 h = ph & (x4a->size-1);
4931 np = x4a->ht[h];
4932 while( np ){
4933 if( Configcmp(np->data,data)==0 ){
4934 /* An existing entry with the same key is found. */
4935 /* Fail because overwrite is not allows. */
4936 return 0;
4937 }
4938 np = np->next;
4939 }
4940 if( x4a->count>=x4a->size ){
4941 /* Need to make the hash table bigger */
4942 int i,size;
4943 struct s_x4 array;
4944 array.size = size = x4a->size*2;
4945 array.count = x4a->count;
4946 array.tbl = (x4node*)malloc(
4947 (sizeof(x4node) + sizeof(x4node*))*size );
4948 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4949 array.ht = (x4node**)&(array.tbl[size]);
4950 for(i=0; i<size; i++) array.ht[i] = 0;
4951 for(i=0; i<x4a->count; i++){
4952 x4node *oldnp, *newnp;
4953 oldnp = &(x4a->tbl[i]);
4954 h = confighash(oldnp->data) & (size-1);
4955 newnp = &(array.tbl[i]);
4956 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4957 newnp->next = array.ht[h];
4958 newnp->data = oldnp->data;
4959 newnp->from = &(array.ht[h]);
4960 array.ht[h] = newnp;
4961 }
4962 free(x4a->tbl);
4963 *x4a = array;
4964 }
4965 /* Insert the new data */
4966 h = ph & (x4a->size-1);
4967 np = &(x4a->tbl[x4a->count++]);
4968 np->data = data;
4969 if( x4a->ht[h] ) x4a->ht[h]->from = &(np->next);
4970 np->next = x4a->ht[h];
4971 x4a->ht[h] = np;
4972 np->from = &(x4a->ht[h]);
4973 return 1;
4974}
4975
4976/* Return a pointer to data assigned to the given key. Return NULL
4977** if no such key. */
4978struct config *Configtable_find(key)
4979struct config *key;
4980{
4981 int h;
4982 x4node *np;
4983
4984 if( x4a==0 ) return 0;
4985 h = confighash(key) & (x4a->size-1);
4986 np = x4a->ht[h];
4987 while( np ){
4988 if( Configcmp(np->data,key)==0 ) break;
4989 np = np->next;
4990 }
4991 return np ? np->data : 0;
4992}
4993
4994/* Remove all data from the table. Pass each data to the function "f"
4995** as it is removed. ("f" may be null to avoid this step.) */
4996void Configtable_clear(f)
4997int(*f)(/* struct config * */);
4998{
4999 int i;
5000 if( x4a==0 || x4a->count==0 ) return;
5001 if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
5002 for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;
5003 x4a->count = 0;
5004 return;
5005}