blob: ab9b8d53b280e46145b197d70e54ac46a221fc80 [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
icculusf5ad8242010-02-14 05:34:42 +000037static const char **made_files = NULL;
38static int made_files_count = 0;
39static int successful_exit = 0;
40static void LemonAtExit(void)
41{
42 /* if we failed, delete (most) files we made, to unconfuse build tools. */
43 int i;
44 for (i = 0; i < made_files_count; i++) {
45 if (!successful_exit) {
46 remove(made_files[i]);
47 }
48 free((void *) made_files[i]);
49 }
50 free(made_files);
51 made_files_count = 0;
52 made_files = NULL;
53}
54
drhe9278182007-07-18 18:16:29 +000055static char *msort(char*,char**,int(*)(const char*,const char*));
drh75897232000-05-29 14:26:00 +000056
drh87cf1372008-08-13 20:09:06 +000057/*
58** Compilers are getting increasingly pedantic about type conversions
59** as C evolves ever closer to Ada.... To work around the latest problems
60** we have to define the following variant of strlen().
61*/
62#define lemonStrlen(X) ((int)strlen(X))
63
icculus9e44cf12010-02-14 17:14:22 +000064/* a few forward declarations... */
65struct rule;
66struct lemon;
67struct action;
68
drhe9278182007-07-18 18:16:29 +000069static struct action *Action_new(void);
70static struct action *Action_sort(struct action *);
drh75897232000-05-29 14:26:00 +000071
72/********** From the file "build.h" ************************************/
73void FindRulePrecedences();
74void FindFirstSets();
75void FindStates();
76void FindLinks();
77void FindFollowSets();
78void FindActions();
79
80/********* From the file "configlist.h" *********************************/
icculus9e44cf12010-02-14 17:14:22 +000081void Configlist_init(void);
82struct config *Configlist_add(struct rule *, int);
83struct config *Configlist_addbasis(struct rule *, int);
84void Configlist_closure(struct lemon *);
85void Configlist_sort(void);
86void Configlist_sortbasis(void);
87struct config *Configlist_return(void);
88struct config *Configlist_basis(void);
89void Configlist_eat(struct config *);
90void Configlist_reset(void);
drh75897232000-05-29 14:26:00 +000091
92/********* From the file "error.h" ***************************************/
drhf9a2e7b2003-04-15 01:49:48 +000093void ErrorMsg(const char *, int,const char *, ...);
drh75897232000-05-29 14:26:00 +000094
95/****** From the file "option.h" ******************************************/
icculus9e44cf12010-02-14 17:14:22 +000096enum option_type { OPT_FLAG=1, OPT_INT, OPT_DBL, OPT_STR,
97 OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR};
drh75897232000-05-29 14:26:00 +000098struct s_options {
icculus9e44cf12010-02-14 17:14:22 +000099 enum option_type type;
100 const char *label;
drh75897232000-05-29 14:26:00 +0000101 char *arg;
icculus9e44cf12010-02-14 17:14:22 +0000102 const char *message;
drh75897232000-05-29 14:26:00 +0000103};
icculus9e44cf12010-02-14 17:14:22 +0000104int OptInit(char**,struct s_options*,FILE*);
105int OptNArgs(void);
106char *OptArg(int);
107void OptErr(int);
108void OptPrint(void);
drh75897232000-05-29 14:26:00 +0000109
110/******** From the file "parse.h" *****************************************/
icculus9e44cf12010-02-14 17:14:22 +0000111void Parse(struct lemon *lemp);
drh75897232000-05-29 14:26:00 +0000112
113/********* From the file "plink.h" ***************************************/
icculus9e44cf12010-02-14 17:14:22 +0000114struct plink *Plink_new(void);
115void Plink_add(struct plink **, struct config *);
116void Plink_copy(struct plink **, struct plink *);
117void Plink_delete(struct plink *);
drh75897232000-05-29 14:26:00 +0000118
119/********** From the file "report.h" *************************************/
icculus9e44cf12010-02-14 17:14:22 +0000120void Reprint(struct lemon *);
121void ReportOutput(struct lemon *);
122void ReportTable(struct lemon *, int);
123void ReportHeader(struct lemon *);
124void CompressTables(struct lemon *);
125void ResortStates(struct lemon *);
drh75897232000-05-29 14:26:00 +0000126
127/********** From the file "set.h" ****************************************/
icculus9e44cf12010-02-14 17:14:22 +0000128void SetSize(int); /* All sets will be of size N */
129char *SetNew(void); /* A new set for element 0..N */
130void SetFree(char*); /* Deallocate a set */
drh75897232000-05-29 14:26:00 +0000131
icculus9e44cf12010-02-14 17:14:22 +0000132char *SetNew(void); /* A new set for element 0..N */
133int SetAdd(char*,int); /* Add element to a set */
134int SetUnion(char *,char *); /* A <- A U B, thru element N */
drh75897232000-05-29 14:26:00 +0000135#define SetFind(X,Y) (X[Y]) /* True if Y is in set X */
136
137/********** From the file "struct.h" *************************************/
138/*
139** Principal data structures for the LEMON parser generator.
140*/
141
drhaa9f1122007-08-23 02:50:56 +0000142typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;
drh75897232000-05-29 14:26:00 +0000143
144/* Symbols (terminals and nonterminals) of the grammar are stored
145** in the following: */
icculus9e44cf12010-02-14 17:14:22 +0000146enum symbol_type {
147 TERMINAL,
148 NONTERMINAL,
149 MULTITERMINAL
150};
151enum e_assoc {
drh75897232000-05-29 14:26:00 +0000152 LEFT,
153 RIGHT,
154 NONE,
155 UNK
icculus9e44cf12010-02-14 17:14:22 +0000156};
157struct symbol {
158 const char *name; /* Name of the symbol */
159 int index; /* Index number for this symbol */
160 enum symbol_type type; /* Symbols are all either TERMINALS or NTs */
161 struct rule *rule; /* Linked list of rules of this (if an NT) */
162 struct symbol *fallback; /* fallback token in case this token doesn't parse */
163 int prec; /* Precedence if defined (-1 otherwise) */
164 enum e_assoc assoc; /* Associativity if precedence is defined */
drh75897232000-05-29 14:26:00 +0000165 char *firstset; /* First-set for all rules of this symbol */
166 Boolean lambda; /* True if NT and can generate an empty string */
drhc4dd3fd2008-01-22 01:48:05 +0000167 int useCnt; /* Number of times used */
drh75897232000-05-29 14:26:00 +0000168 char *destructor; /* Code which executes whenever this symbol is
169 ** popped from the stack during error processing */
drh4dc8ef52008-07-01 17:13:57 +0000170 int destLineno; /* Line number for start of destructor */
drh75897232000-05-29 14:26:00 +0000171 char *datatype; /* The data type of information held by this
172 ** object. Only used if type==NONTERMINAL */
173 int dtnum; /* The data type number. In the parser, the value
174 ** stack is a union. The .yy%d element of this
175 ** union is the correct data type for this object */
drhfd405312005-11-06 04:06:59 +0000176 /* The following fields are used by MULTITERMINALs only */
177 int nsubsym; /* Number of constituent symbols in the MULTI */
178 struct symbol **subsym; /* Array of constituent symbols */
drh75897232000-05-29 14:26:00 +0000179};
180
181/* Each production rule in the grammar is stored in the following
182** structure. */
183struct rule {
184 struct symbol *lhs; /* Left-hand side of the rule */
icculus9e44cf12010-02-14 17:14:22 +0000185 const char *lhsalias; /* Alias for the LHS (NULL if none) */
drhb4960992007-10-05 16:16:36 +0000186 int lhsStart; /* True if left-hand side is the start symbol */
drh75897232000-05-29 14:26:00 +0000187 int ruleline; /* Line number for the rule */
188 int nrhs; /* Number of RHS symbols */
189 struct symbol **rhs; /* The RHS symbols */
icculus9e44cf12010-02-14 17:14:22 +0000190 const char **rhsalias; /* An alias for each RHS symbol (NULL if none) */
drh75897232000-05-29 14:26:00 +0000191 int line; /* Line number at which code begins */
icculus9e44cf12010-02-14 17:14:22 +0000192 const char *code; /* The code executed when this rule is reduced */
drh75897232000-05-29 14:26:00 +0000193 struct symbol *precsym; /* Precedence symbol for this rule */
194 int index; /* An index number for this rule */
195 Boolean canReduce; /* True if this rule is ever reduced */
196 struct rule *nextlhs; /* Next rule with the same LHS */
197 struct rule *next; /* Next rule in the global list */
198};
199
200/* A configuration is a production rule of the grammar together with
201** a mark (dot) showing how much of that rule has been processed so far.
202** Configurations also contain a follow-set which is a list of terminal
203** symbols which are allowed to immediately follow the end of the rule.
204** Every configuration is recorded as an instance of the following: */
icculus9e44cf12010-02-14 17:14:22 +0000205enum cfgstatus {
206 COMPLETE,
207 INCOMPLETE
208};
drh75897232000-05-29 14:26:00 +0000209struct config {
210 struct rule *rp; /* The rule upon which the configuration is based */
211 int dot; /* The parse point */
212 char *fws; /* Follow-set for this configuration only */
213 struct plink *fplp; /* Follow-set forward propagation links */
214 struct plink *bplp; /* Follow-set backwards propagation links */
215 struct state *stp; /* Pointer to state which contains this */
icculus9e44cf12010-02-14 17:14:22 +0000216 enum cfgstatus status; /* used during followset and shift computations */
drh75897232000-05-29 14:26:00 +0000217 struct config *next; /* Next configuration in the state */
218 struct config *bp; /* The next basis configuration */
219};
220
icculus9e44cf12010-02-14 17:14:22 +0000221enum e_action {
222 SHIFT,
223 ACCEPT,
224 REDUCE,
225 ERROR,
226 SSCONFLICT, /* A shift/shift conflict */
227 SRCONFLICT, /* Was a reduce, but part of a conflict */
228 RRCONFLICT, /* Was a reduce, but part of a conflict */
229 SH_RESOLVED, /* Was a shift. Precedence resolved conflict */
230 RD_RESOLVED, /* Was reduce. Precedence resolved conflict */
231 NOT_USED /* Deleted by compression */
232};
233
drh75897232000-05-29 14:26:00 +0000234/* Every shift or reduce operation is stored as one of the following */
235struct action {
236 struct symbol *sp; /* The look-ahead symbol */
icculus9e44cf12010-02-14 17:14:22 +0000237 enum e_action type;
drh75897232000-05-29 14:26:00 +0000238 union {
239 struct state *stp; /* The new state, if a shift */
240 struct rule *rp; /* The rule, if a reduce */
241 } x;
242 struct action *next; /* Next action for this state */
243 struct action *collide; /* Next action with the same hash */
244};
245
246/* Each state of the generated parser's finite state machine
247** is encoded as an instance of the following structure. */
248struct state {
249 struct config *bp; /* The basis configurations for this state */
250 struct config *cfp; /* All configurations in this set */
drh34ff57b2008-07-14 12:27:51 +0000251 int statenum; /* Sequential number for this state */
drh75897232000-05-29 14:26:00 +0000252 struct action *ap; /* Array of actions for this state */
drh8b582012003-10-21 13:16:03 +0000253 int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */
254 int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */
255 int iDflt; /* Default action */
drh75897232000-05-29 14:26:00 +0000256};
drh8b582012003-10-21 13:16:03 +0000257#define NO_OFFSET (-2147483647)
drh75897232000-05-29 14:26:00 +0000258
259/* A followset propagation link indicates that the contents of one
260** configuration followset should be propagated to another whenever
261** the first changes. */
262struct plink {
263 struct config *cfp; /* The configuration to which linked */
264 struct plink *next; /* The next propagate link */
265};
266
267/* The state vector for the entire parser generator is recorded as
268** follows. (LEMON uses no global variables and makes little use of
269** static variables. Fields in the following structure can be thought
270** of as begin global variables in the program.) */
271struct lemon {
272 struct state **sorted; /* Table of states sorted by state number */
273 struct rule *rule; /* List of all rules */
274 int nstate; /* Number of states */
275 int nrule; /* Number of rules */
276 int nsymbol; /* Number of terminal and nonterminal symbols */
277 int nterminal; /* Number of terminal symbols */
278 struct symbol **symbols; /* Sorted array of pointers to symbols */
279 int errorcnt; /* Number of errors */
280 struct symbol *errsym; /* The error symbol */
drhe09daa92006-06-10 13:29:31 +0000281 struct symbol *wildcard; /* Token that matches anything */
drh75897232000-05-29 14:26:00 +0000282 char *name; /* Name of the generated parser */
283 char *arg; /* Declaration of the 3th argument to parser */
284 char *tokentype; /* Type of terminal symbols in the parser stack */
drh960e8c62001-04-03 16:53:21 +0000285 char *vartype; /* The default type of non-terminal symbols */
drh75897232000-05-29 14:26:00 +0000286 char *start; /* Name of the start symbol for the grammar */
287 char *stacksize; /* Size of the parser stack */
288 char *include; /* Code to put at the start of the C file */
drh75897232000-05-29 14:26:00 +0000289 char *error; /* Code to execute when an error is seen */
drh75897232000-05-29 14:26:00 +0000290 char *overflow; /* Code to execute on a stack overflow */
drh75897232000-05-29 14:26:00 +0000291 char *failure; /* Code to execute on parser failure */
drh75897232000-05-29 14:26:00 +0000292 char *accept; /* Code to execute when the parser excepts */
drh75897232000-05-29 14:26:00 +0000293 char *extracode; /* Code appended to the generated file */
drh75897232000-05-29 14:26:00 +0000294 char *tokendest; /* Code to execute to destroy token data */
drh960e8c62001-04-03 16:53:21 +0000295 char *vardest; /* Code for the default non-terminal destructor */
drh75897232000-05-29 14:26:00 +0000296 char *filename; /* Name of the input file */
297 char *outname; /* Name of the current output file */
298 char *tokenprefix; /* A prefix added to token names in the .h file */
299 int nconflict; /* Number of parsing conflicts */
300 int tablesize; /* Size of the parse tables */
301 int basisflag; /* Print only basis configurations */
drh34ff57b2008-07-14 12:27:51 +0000302 int has_fallback; /* True if any %fallback is seen in the grammar */
shane58543932008-12-10 20:10:04 +0000303 int nolinenosflag; /* True if #line statements should not be printed */
drh75897232000-05-29 14:26:00 +0000304 char *argv0; /* Name of the program */
305};
306
307#define MemoryCheck(X) if((X)==0){ \
308 extern void memory_error(); \
309 memory_error(); \
310}
311
312/**************** From the file "table.h" *********************************/
313/*
314** All code in this file has been automatically generated
315** from a specification in the file
316** "table.q"
317** by the associative array code building program "aagen".
318** Do not edit this file! Instead, edit the specification
319** file, then rerun aagen.
320*/
321/*
322** Code for processing tables in the LEMON parser generator.
323*/
drh75897232000-05-29 14:26:00 +0000324/* Routines for handling a strings */
325
icculus9e44cf12010-02-14 17:14:22 +0000326const char *Strsafe(const char *);
drh75897232000-05-29 14:26:00 +0000327
icculus9e44cf12010-02-14 17:14:22 +0000328void Strsafe_init(void);
329int Strsafe_insert(const char *);
330const char *Strsafe_find(const char *);
drh75897232000-05-29 14:26:00 +0000331
332/* Routines for handling symbols of the grammar */
333
icculus9e44cf12010-02-14 17:14:22 +0000334struct symbol *Symbol_new(const char *);
335int Symbolcmpp(const void *, const void *);
336void Symbol_init(void);
337int Symbol_insert(struct symbol *, const char *);
338struct symbol *Symbol_find(const char *);
339struct symbol *Symbol_Nth(int);
340int Symbol_count(void);
341struct symbol **Symbol_arrayof(void);
drh75897232000-05-29 14:26:00 +0000342
343/* Routines to manage the state table */
344
icculus9e44cf12010-02-14 17:14:22 +0000345int Configcmp(const char *, const char *);
346struct state *State_new(void);
347void State_init(void);
348int State_insert(struct state *, struct config *);
349struct state *State_find(struct config *);
drh75897232000-05-29 14:26:00 +0000350struct state **State_arrayof(/* */);
351
352/* Routines used for efficiency in Configlist_add */
353
icculus9e44cf12010-02-14 17:14:22 +0000354void Configtable_init(void);
355int Configtable_insert(struct config *);
356struct config *Configtable_find(struct config *);
357void Configtable_clear(int(*)(struct config *));
358
drh75897232000-05-29 14:26:00 +0000359/****************** From the file "action.c" *******************************/
360/*
361** Routines processing parser actions in the LEMON parser generator.
362*/
363
364/* Allocate a new parser action */
drhe9278182007-07-18 18:16:29 +0000365static struct action *Action_new(void){
drh75897232000-05-29 14:26:00 +0000366 static struct action *freelist = 0;
icculus9e44cf12010-02-14 17:14:22 +0000367 struct action *newaction;
drh75897232000-05-29 14:26:00 +0000368
369 if( freelist==0 ){
370 int i;
371 int amt = 100;
drh9892c5d2007-12-21 00:02:11 +0000372 freelist = (struct action *)calloc(amt, sizeof(struct action));
drh75897232000-05-29 14:26:00 +0000373 if( freelist==0 ){
374 fprintf(stderr,"Unable to allocate memory for a new parser action.");
375 exit(1);
376 }
377 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
378 freelist[amt-1].next = 0;
379 }
icculus9e44cf12010-02-14 17:14:22 +0000380 newaction = freelist;
drh75897232000-05-29 14:26:00 +0000381 freelist = freelist->next;
icculus9e44cf12010-02-14 17:14:22 +0000382 return newaction;
drh75897232000-05-29 14:26:00 +0000383}
384
drhe9278182007-07-18 18:16:29 +0000385/* Compare two actions for sorting purposes. Return negative, zero, or
386** positive if the first action is less than, equal to, or greater than
387** the first
388*/
389static int actioncmp(
390 struct action *ap1,
391 struct action *ap2
392){
drh75897232000-05-29 14:26:00 +0000393 int rc;
394 rc = ap1->sp->index - ap2->sp->index;
drh75897232000-05-29 14:26:00 +0000395 if( rc==0 ){
drh9892c5d2007-12-21 00:02:11 +0000396 rc = (int)ap1->type - (int)ap2->type;
397 }
398 if( rc==0 && ap1->type==REDUCE ){
drh75897232000-05-29 14:26:00 +0000399 rc = ap1->x.rp->index - ap2->x.rp->index;
400 }
drhe594bc32009-11-03 13:02:25 +0000401 if( rc==0 ){
402 rc = ap2 - ap1;
403 }
drh75897232000-05-29 14:26:00 +0000404 return rc;
405}
406
407/* Sort parser actions */
drhe9278182007-07-18 18:16:29 +0000408static struct action *Action_sort(
409 struct action *ap
410){
411 ap = (struct action *)msort((char *)ap,(char **)&ap->next,
412 (int(*)(const char*,const char*))actioncmp);
drh75897232000-05-29 14:26:00 +0000413 return ap;
414}
415
icculus9e44cf12010-02-14 17:14:22 +0000416void Action_add(
417 struct action **app,
418 enum e_action type,
419 struct symbol *sp,
420 char *arg
421){
422 struct action *newaction;
423 newaction = Action_new();
424 newaction->next = *app;
425 *app = newaction;
426 newaction->type = type;
427 newaction->sp = sp;
drh75897232000-05-29 14:26:00 +0000428 if( type==SHIFT ){
icculus9e44cf12010-02-14 17:14:22 +0000429 newaction->x.stp = (struct state *)arg;
drh75897232000-05-29 14:26:00 +0000430 }else{
icculus9e44cf12010-02-14 17:14:22 +0000431 newaction->x.rp = (struct rule *)arg;
drh75897232000-05-29 14:26:00 +0000432 }
433}
drh8b582012003-10-21 13:16:03 +0000434/********************** New code to implement the "acttab" module ***********/
435/*
436** This module implements routines use to construct the yy_action[] table.
437*/
438
439/*
440** The state of the yy_action table under construction is an instance of
drh8dc3e8f2010-01-07 03:53:03 +0000441** the following structure.
442**
443** The yy_action table maps the pair (state_number, lookahead) into an
444** action_number. The table is an array of integers pairs. The state_number
445** determines an initial offset into the yy_action array. The lookahead
446** value is then added to this initial offset to get an index X into the
447** yy_action array. If the aAction[X].lookahead equals the value of the
448** of the lookahead input, then the value of the action_number output is
449** aAction[X].action. If the lookaheads do not match then the
450** default action for the state_number is returned.
451**
452** All actions associated with a single state_number are first entered
453** into aLookahead[] using multiple calls to acttab_action(). Then the
454** actions for that single state_number are placed into the aAction[]
455** array with a single call to acttab_insert(). The acttab_insert() call
456** also resets the aLookahead[] array in preparation for the next
457** state number.
drh8b582012003-10-21 13:16:03 +0000458*/
icculus9e44cf12010-02-14 17:14:22 +0000459struct lookahead_action {
460 int lookahead; /* Value of the lookahead token */
461 int action; /* Action to take on the given lookahead */
462};
drh8b582012003-10-21 13:16:03 +0000463typedef struct acttab acttab;
464struct acttab {
465 int nAction; /* Number of used slots in aAction[] */
466 int nActionAlloc; /* Slots allocated for aAction[] */
icculus9e44cf12010-02-14 17:14:22 +0000467 struct lookahead_action
468 *aAction, /* The yy_action[] table under construction */
drh8b582012003-10-21 13:16:03 +0000469 *aLookahead; /* A single new transaction set */
470 int mnLookahead; /* Minimum aLookahead[].lookahead */
471 int mnAction; /* Action associated with mnLookahead */
472 int mxLookahead; /* Maximum aLookahead[].lookahead */
473 int nLookahead; /* Used slots in aLookahead[] */
474 int nLookaheadAlloc; /* Slots allocated in aLookahead[] */
475};
476
477/* Return the number of entries in the yy_action table */
478#define acttab_size(X) ((X)->nAction)
479
480/* The value for the N-th entry in yy_action */
481#define acttab_yyaction(X,N) ((X)->aAction[N].action)
482
483/* The value for the N-th entry in yy_lookahead */
484#define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
485
486/* Free all memory associated with the given acttab */
487void acttab_free(acttab *p){
488 free( p->aAction );
489 free( p->aLookahead );
490 free( p );
491}
492
493/* Allocate a new acttab structure */
494acttab *acttab_alloc(void){
icculus9e44cf12010-02-14 17:14:22 +0000495 acttab *p = (acttab *) calloc( 1, sizeof(*p) );
drh8b582012003-10-21 13:16:03 +0000496 if( p==0 ){
497 fprintf(stderr,"Unable to allocate memory for a new acttab.");
498 exit(1);
499 }
500 memset(p, 0, sizeof(*p));
501 return p;
502}
503
drh8dc3e8f2010-01-07 03:53:03 +0000504/* Add a new action to the current transaction set.
505**
506** This routine is called once for each lookahead for a particular
507** state.
drh8b582012003-10-21 13:16:03 +0000508*/
509void acttab_action(acttab *p, int lookahead, int action){
510 if( p->nLookahead>=p->nLookaheadAlloc ){
511 p->nLookaheadAlloc += 25;
icculus9e44cf12010-02-14 17:14:22 +0000512 p->aLookahead = (struct lookahead_action *) realloc( p->aLookahead,
drh8b582012003-10-21 13:16:03 +0000513 sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
514 if( p->aLookahead==0 ){
515 fprintf(stderr,"malloc failed\n");
516 exit(1);
517 }
518 }
519 if( p->nLookahead==0 ){
520 p->mxLookahead = lookahead;
521 p->mnLookahead = lookahead;
522 p->mnAction = action;
523 }else{
524 if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
525 if( p->mnLookahead>lookahead ){
526 p->mnLookahead = lookahead;
527 p->mnAction = action;
528 }
529 }
530 p->aLookahead[p->nLookahead].lookahead = lookahead;
531 p->aLookahead[p->nLookahead].action = action;
532 p->nLookahead++;
533}
534
535/*
536** Add the transaction set built up with prior calls to acttab_action()
537** into the current action table. Then reset the transaction set back
538** to an empty set in preparation for a new round of acttab_action() calls.
539**
540** Return the offset into the action table of the new transaction.
541*/
542int acttab_insert(acttab *p){
543 int i, j, k, n;
544 assert( p->nLookahead>0 );
545
546 /* Make sure we have enough space to hold the expanded action table
547 ** in the worst case. The worst case occurs if the transaction set
548 ** must be appended to the current action table
549 */
drh784d86f2004-02-19 18:41:53 +0000550 n = p->mxLookahead + 1;
drh8dc3e8f2010-01-07 03:53:03 +0000551 if( p->nAction + n >= p->nActionAlloc ){
drhfdbf9282003-10-21 16:34:41 +0000552 int oldAlloc = p->nActionAlloc;
drh8b582012003-10-21 13:16:03 +0000553 p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
icculus9e44cf12010-02-14 17:14:22 +0000554 p->aAction = (struct lookahead_action *) realloc( p->aAction,
drh8b582012003-10-21 13:16:03 +0000555 sizeof(p->aAction[0])*p->nActionAlloc);
556 if( p->aAction==0 ){
557 fprintf(stderr,"malloc failed\n");
558 exit(1);
559 }
drhfdbf9282003-10-21 16:34:41 +0000560 for(i=oldAlloc; i<p->nActionAlloc; i++){
drh8b582012003-10-21 13:16:03 +0000561 p->aAction[i].lookahead = -1;
562 p->aAction[i].action = -1;
563 }
564 }
565
drh8dc3e8f2010-01-07 03:53:03 +0000566 /* Scan the existing action table looking for an offset that is a
567 ** duplicate of the current transaction set. Fall out of the loop
568 ** if and when the duplicate is found.
drh8b582012003-10-21 13:16:03 +0000569 **
570 ** i is the index in p->aAction[] where p->mnLookahead is inserted.
571 */
drh8dc3e8f2010-01-07 03:53:03 +0000572 for(i=p->nAction-1; i>=0; i--){
drhf16371d2009-11-03 19:18:31 +0000573 if( p->aAction[i].lookahead==p->mnLookahead ){
drh8dc3e8f2010-01-07 03:53:03 +0000574 /* All lookaheads and actions in the aLookahead[] transaction
575 ** must match against the candidate aAction[i] entry. */
drh8b582012003-10-21 13:16:03 +0000576 if( p->aAction[i].action!=p->mnAction ) continue;
577 for(j=0; j<p->nLookahead; j++){
578 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
579 if( k<0 || k>=p->nAction ) break;
580 if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
581 if( p->aLookahead[j].action!=p->aAction[k].action ) break;
582 }
583 if( j<p->nLookahead ) continue;
drh8dc3e8f2010-01-07 03:53:03 +0000584
585 /* No possible lookahead value that is not in the aLookahead[]
586 ** transaction is allowed to match aAction[i] */
drh8b582012003-10-21 13:16:03 +0000587 n = 0;
588 for(j=0; j<p->nAction; j++){
drhfdbf9282003-10-21 16:34:41 +0000589 if( p->aAction[j].lookahead<0 ) continue;
590 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
drh8b582012003-10-21 13:16:03 +0000591 }
drhfdbf9282003-10-21 16:34:41 +0000592 if( n==p->nLookahead ){
drh8dc3e8f2010-01-07 03:53:03 +0000593 break; /* An exact match is found at offset i */
drhfdbf9282003-10-21 16:34:41 +0000594 }
drh8b582012003-10-21 13:16:03 +0000595 }
596 }
drh8dc3e8f2010-01-07 03:53:03 +0000597
598 /* If no existing offsets exactly match the current transaction, find an
599 ** an empty offset in the aAction[] table in which we can add the
600 ** aLookahead[] transaction.
601 */
drhf16371d2009-11-03 19:18:31 +0000602 if( i<0 ){
drh8dc3e8f2010-01-07 03:53:03 +0000603 /* Look for holes in the aAction[] table that fit the current
604 ** aLookahead[] transaction. Leave i set to the offset of the hole.
605 ** If no holes are found, i is left at p->nAction, which means the
606 ** transaction will be appended. */
607 for(i=0; i<p->nActionAlloc - p->mxLookahead; i++){
drhf16371d2009-11-03 19:18:31 +0000608 if( p->aAction[i].lookahead<0 ){
609 for(j=0; j<p->nLookahead; j++){
610 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
611 if( k<0 ) break;
612 if( p->aAction[k].lookahead>=0 ) break;
613 }
614 if( j<p->nLookahead ) continue;
615 for(j=0; j<p->nAction; j++){
616 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
617 }
618 if( j==p->nAction ){
619 break; /* Fits in empty slots */
620 }
621 }
622 }
623 }
drh8b582012003-10-21 13:16:03 +0000624 /* Insert transaction set at index i. */
625 for(j=0; j<p->nLookahead; j++){
626 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
627 p->aAction[k] = p->aLookahead[j];
628 if( k>=p->nAction ) p->nAction = k+1;
629 }
630 p->nLookahead = 0;
631
632 /* Return the offset that is added to the lookahead in order to get the
633 ** index into yy_action of the action */
634 return i - p->mnLookahead;
635}
636
drh75897232000-05-29 14:26:00 +0000637/********************** From the file "build.c" *****************************/
638/*
639** Routines to construction the finite state machine for the LEMON
640** parser generator.
641*/
642
643/* Find a precedence symbol of every rule in the grammar.
644**
645** Those rules which have a precedence symbol coded in the input
646** grammar using the "[symbol]" construct will already have the
647** rp->precsym field filled. Other rules take as their precedence
648** symbol the first RHS symbol with a defined precedence. If there
649** are not RHS symbols with a defined precedence, the precedence
650** symbol field is left blank.
651*/
icculus9e44cf12010-02-14 17:14:22 +0000652void FindRulePrecedences(struct lemon *xp)
drh75897232000-05-29 14:26:00 +0000653{
654 struct rule *rp;
655 for(rp=xp->rule; rp; rp=rp->next){
656 if( rp->precsym==0 ){
drhfd405312005-11-06 04:06:59 +0000657 int i, j;
658 for(i=0; i<rp->nrhs && rp->precsym==0; i++){
659 struct symbol *sp = rp->rhs[i];
660 if( sp->type==MULTITERMINAL ){
661 for(j=0; j<sp->nsubsym; j++){
662 if( sp->subsym[j]->prec>=0 ){
663 rp->precsym = sp->subsym[j];
664 break;
665 }
666 }
667 }else if( sp->prec>=0 ){
drh75897232000-05-29 14:26:00 +0000668 rp->precsym = rp->rhs[i];
drh75897232000-05-29 14:26:00 +0000669 }
670 }
671 }
672 }
673 return;
674}
675
676/* Find all nonterminals which will generate the empty string.
677** Then go back and compute the first sets of every nonterminal.
678** The first set is the set of all terminal symbols which can begin
679** a string generated by that nonterminal.
680*/
icculus9e44cf12010-02-14 17:14:22 +0000681void FindFirstSets(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +0000682{
drhfd405312005-11-06 04:06:59 +0000683 int i, j;
drh75897232000-05-29 14:26:00 +0000684 struct rule *rp;
685 int progress;
686
687 for(i=0; i<lemp->nsymbol; i++){
drhaa9f1122007-08-23 02:50:56 +0000688 lemp->symbols[i]->lambda = LEMON_FALSE;
drh75897232000-05-29 14:26:00 +0000689 }
690 for(i=lemp->nterminal; i<lemp->nsymbol; i++){
691 lemp->symbols[i]->firstset = SetNew();
692 }
693
694 /* First compute all lambdas */
695 do{
696 progress = 0;
697 for(rp=lemp->rule; rp; rp=rp->next){
698 if( rp->lhs->lambda ) continue;
699 for(i=0; i<rp->nrhs; i++){
drhfd405312005-11-06 04:06:59 +0000700 struct symbol *sp = rp->rhs[i];
drhaa9f1122007-08-23 02:50:56 +0000701 if( sp->type!=TERMINAL || sp->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +0000702 }
703 if( i==rp->nrhs ){
drhaa9f1122007-08-23 02:50:56 +0000704 rp->lhs->lambda = LEMON_TRUE;
drh75897232000-05-29 14:26:00 +0000705 progress = 1;
706 }
707 }
708 }while( progress );
709
710 /* Now compute all first sets */
711 do{
712 struct symbol *s1, *s2;
713 progress = 0;
714 for(rp=lemp->rule; rp; rp=rp->next){
715 s1 = rp->lhs;
716 for(i=0; i<rp->nrhs; i++){
717 s2 = rp->rhs[i];
718 if( s2->type==TERMINAL ){
719 progress += SetAdd(s1->firstset,s2->index);
720 break;
drhfd405312005-11-06 04:06:59 +0000721 }else if( s2->type==MULTITERMINAL ){
722 for(j=0; j<s2->nsubsym; j++){
723 progress += SetAdd(s1->firstset,s2->subsym[j]->index);
724 }
725 break;
drh75897232000-05-29 14:26:00 +0000726 }else if( s1==s2 ){
drhaa9f1122007-08-23 02:50:56 +0000727 if( s1->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +0000728 }else{
729 progress += SetUnion(s1->firstset,s2->firstset);
drhaa9f1122007-08-23 02:50:56 +0000730 if( s2->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +0000731 }
732 }
733 }
734 }while( progress );
735 return;
736}
737
738/* Compute all LR(0) states for the grammar. Links
739** are added to between some states so that the LR(1) follow sets
740** can be computed later.
741*/
icculus9e44cf12010-02-14 17:14:22 +0000742PRIVATE struct state *getstate(struct lemon *); /* forward reference */
743void FindStates(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +0000744{
745 struct symbol *sp;
746 struct rule *rp;
747
748 Configlist_init();
749
750 /* Find the start symbol */
751 if( lemp->start ){
752 sp = Symbol_find(lemp->start);
753 if( sp==0 ){
754 ErrorMsg(lemp->filename,0,
755"The specified start symbol \"%s\" is not \
756in a nonterminal of the grammar. \"%s\" will be used as the start \
757symbol instead.",lemp->start,lemp->rule->lhs->name);
758 lemp->errorcnt++;
759 sp = lemp->rule->lhs;
760 }
761 }else{
762 sp = lemp->rule->lhs;
763 }
764
765 /* Make sure the start symbol doesn't occur on the right-hand side of
766 ** any rule. Report an error if it does. (YACC would generate a new
767 ** start symbol in this case.) */
768 for(rp=lemp->rule; rp; rp=rp->next){
769 int i;
770 for(i=0; i<rp->nrhs; i++){
drhfd405312005-11-06 04:06:59 +0000771 if( rp->rhs[i]==sp ){ /* FIX ME: Deal with multiterminals */
drh75897232000-05-29 14:26:00 +0000772 ErrorMsg(lemp->filename,0,
773"The start symbol \"%s\" occurs on the \
774right-hand side of a rule. This will result in a parser which \
775does not work properly.",sp->name);
776 lemp->errorcnt++;
777 }
778 }
779 }
780
781 /* The basis configuration set for the first state
782 ** is all rules which have the start symbol as their
783 ** left-hand side */
784 for(rp=sp->rule; rp; rp=rp->nextlhs){
785 struct config *newcfp;
drhb4960992007-10-05 16:16:36 +0000786 rp->lhsStart = 1;
drh75897232000-05-29 14:26:00 +0000787 newcfp = Configlist_addbasis(rp,0);
788 SetAdd(newcfp->fws,0);
789 }
790
791 /* Compute the first state. All other states will be
792 ** computed automatically during the computation of the first one.
793 ** The returned pointer to the first state is not used. */
794 (void)getstate(lemp);
795 return;
796}
797
798/* Return a pointer to a state which is described by the configuration
799** list which has been built from calls to Configlist_add.
800*/
icculus9e44cf12010-02-14 17:14:22 +0000801PRIVATE void buildshifts(struct lemon *, struct state *); /* Forwd ref */
802PRIVATE struct state *getstate(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +0000803{
804 struct config *cfp, *bp;
805 struct state *stp;
806
807 /* Extract the sorted basis of the new state. The basis was constructed
808 ** by prior calls to "Configlist_addbasis()". */
809 Configlist_sortbasis();
810 bp = Configlist_basis();
811
812 /* Get a state with the same basis */
813 stp = State_find(bp);
814 if( stp ){
815 /* A state with the same basis already exists! Copy all the follow-set
816 ** propagation links from the state under construction into the
817 ** preexisting state, then return a pointer to the preexisting state */
818 struct config *x, *y;
819 for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
820 Plink_copy(&y->bplp,x->bplp);
821 Plink_delete(x->fplp);
822 x->fplp = x->bplp = 0;
823 }
824 cfp = Configlist_return();
825 Configlist_eat(cfp);
826 }else{
827 /* This really is a new state. Construct all the details */
828 Configlist_closure(lemp); /* Compute the configuration closure */
829 Configlist_sort(); /* Sort the configuration closure */
830 cfp = Configlist_return(); /* Get a pointer to the config list */
831 stp = State_new(); /* A new state structure */
832 MemoryCheck(stp);
833 stp->bp = bp; /* Remember the configuration basis */
834 stp->cfp = cfp; /* Remember the configuration closure */
drhada354d2005-11-05 15:03:59 +0000835 stp->statenum = lemp->nstate++; /* Every state gets a sequence number */
drh75897232000-05-29 14:26:00 +0000836 stp->ap = 0; /* No actions, yet. */
837 State_insert(stp,stp->bp); /* Add to the state table */
838 buildshifts(lemp,stp); /* Recursively compute successor states */
839 }
840 return stp;
841}
842
drhfd405312005-11-06 04:06:59 +0000843/*
844** Return true if two symbols are the same.
845*/
icculus9e44cf12010-02-14 17:14:22 +0000846int same_symbol(struct symbol *a, struct symbol *b)
drhfd405312005-11-06 04:06:59 +0000847{
848 int i;
849 if( a==b ) return 1;
850 if( a->type!=MULTITERMINAL ) return 0;
851 if( b->type!=MULTITERMINAL ) return 0;
852 if( a->nsubsym!=b->nsubsym ) return 0;
853 for(i=0; i<a->nsubsym; i++){
854 if( a->subsym[i]!=b->subsym[i] ) return 0;
855 }
856 return 1;
857}
858
drh75897232000-05-29 14:26:00 +0000859/* Construct all successor states to the given state. A "successor"
860** state is any state which can be reached by a shift action.
861*/
icculus9e44cf12010-02-14 17:14:22 +0000862PRIVATE void buildshifts(struct lemon *lemp, struct state *stp)
drh75897232000-05-29 14:26:00 +0000863{
864 struct config *cfp; /* For looping thru the config closure of "stp" */
865 struct config *bcfp; /* For the inner loop on config closure of "stp" */
icculus9e44cf12010-02-14 17:14:22 +0000866 struct config *newcfg; /* */
drh75897232000-05-29 14:26:00 +0000867 struct symbol *sp; /* Symbol following the dot in configuration "cfp" */
868 struct symbol *bsp; /* Symbol following the dot in configuration "bcfp" */
869 struct state *newstp; /* A pointer to a successor state */
870
871 /* Each configuration becomes complete after it contibutes to a successor
872 ** state. Initially, all configurations are incomplete */
873 for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
874
875 /* Loop through all configurations of the state "stp" */
876 for(cfp=stp->cfp; cfp; cfp=cfp->next){
877 if( cfp->status==COMPLETE ) continue; /* Already used by inner loop */
878 if( cfp->dot>=cfp->rp->nrhs ) continue; /* Can't shift this config */
879 Configlist_reset(); /* Reset the new config set */
880 sp = cfp->rp->rhs[cfp->dot]; /* Symbol after the dot */
881
882 /* For every configuration in the state "stp" which has the symbol "sp"
883 ** following its dot, add the same configuration to the basis set under
884 ** construction but with the dot shifted one symbol to the right. */
885 for(bcfp=cfp; bcfp; bcfp=bcfp->next){
886 if( bcfp->status==COMPLETE ) continue; /* Already used */
887 if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */
888 bsp = bcfp->rp->rhs[bcfp->dot]; /* Get symbol after dot */
drhfd405312005-11-06 04:06:59 +0000889 if( !same_symbol(bsp,sp) ) continue; /* Must be same as for "cfp" */
drh75897232000-05-29 14:26:00 +0000890 bcfp->status = COMPLETE; /* Mark this config as used */
icculus9e44cf12010-02-14 17:14:22 +0000891 newcfg = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
892 Plink_add(&newcfg->bplp,bcfp);
drh75897232000-05-29 14:26:00 +0000893 }
894
895 /* Get a pointer to the state described by the basis configuration set
896 ** constructed in the preceding loop */
897 newstp = getstate(lemp);
898
899 /* The state "newstp" is reached from the state "stp" by a shift action
900 ** on the symbol "sp" */
drhfd405312005-11-06 04:06:59 +0000901 if( sp->type==MULTITERMINAL ){
902 int i;
903 for(i=0; i<sp->nsubsym; i++){
904 Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);
905 }
906 }else{
907 Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
908 }
drh75897232000-05-29 14:26:00 +0000909 }
910}
911
912/*
913** Construct the propagation links
914*/
icculus9e44cf12010-02-14 17:14:22 +0000915void FindLinks(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +0000916{
917 int i;
918 struct config *cfp, *other;
919 struct state *stp;
920 struct plink *plp;
921
922 /* Housekeeping detail:
923 ** Add to every propagate link a pointer back to the state to
924 ** which the link is attached. */
925 for(i=0; i<lemp->nstate; i++){
926 stp = lemp->sorted[i];
927 for(cfp=stp->cfp; cfp; cfp=cfp->next){
928 cfp->stp = stp;
929 }
930 }
931
932 /* Convert all backlinks into forward links. Only the forward
933 ** links are used in the follow-set computation. */
934 for(i=0; i<lemp->nstate; i++){
935 stp = lemp->sorted[i];
936 for(cfp=stp->cfp; cfp; cfp=cfp->next){
937 for(plp=cfp->bplp; plp; plp=plp->next){
938 other = plp->cfp;
939 Plink_add(&other->fplp,cfp);
940 }
941 }
942 }
943}
944
945/* Compute all followsets.
946**
947** A followset is the set of all symbols which can come immediately
948** after a configuration.
949*/
icculus9e44cf12010-02-14 17:14:22 +0000950void FindFollowSets(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +0000951{
952 int i;
953 struct config *cfp;
954 struct plink *plp;
955 int progress;
956 int change;
957
958 for(i=0; i<lemp->nstate; i++){
959 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
960 cfp->status = INCOMPLETE;
961 }
962 }
963
964 do{
965 progress = 0;
966 for(i=0; i<lemp->nstate; i++){
967 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
968 if( cfp->status==COMPLETE ) continue;
969 for(plp=cfp->fplp; plp; plp=plp->next){
970 change = SetUnion(plp->cfp->fws,cfp->fws);
971 if( change ){
972 plp->cfp->status = INCOMPLETE;
973 progress = 1;
974 }
975 }
976 cfp->status = COMPLETE;
977 }
978 }
979 }while( progress );
980}
981
icculus9e44cf12010-02-14 17:14:22 +0000982static int resolve_conflict(struct action *,struct action *, struct symbol *);
drh75897232000-05-29 14:26:00 +0000983
984/* Compute the reduce actions, and resolve conflicts.
985*/
icculus9e44cf12010-02-14 17:14:22 +0000986void FindActions(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +0000987{
988 int i,j;
989 struct config *cfp;
990 struct state *stp;
991 struct symbol *sp;
992 struct rule *rp;
993
994 /* Add all of the reduce actions
995 ** A reduce action is added for each element of the followset of
996 ** a configuration which has its dot at the extreme right.
997 */
998 for(i=0; i<lemp->nstate; i++){ /* Loop over all states */
999 stp = lemp->sorted[i];
1000 for(cfp=stp->cfp; cfp; cfp=cfp->next){ /* Loop over all configurations */
1001 if( cfp->rp->nrhs==cfp->dot ){ /* Is dot at extreme right? */
1002 for(j=0; j<lemp->nterminal; j++){
1003 if( SetFind(cfp->fws,j) ){
1004 /* Add a reduce action to the state "stp" which will reduce by the
1005 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */
drh218dc692004-05-31 23:13:45 +00001006 Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
drh75897232000-05-29 14:26:00 +00001007 }
1008 }
1009 }
1010 }
1011 }
1012
1013 /* Add the accepting token */
1014 if( lemp->start ){
1015 sp = Symbol_find(lemp->start);
1016 if( sp==0 ) sp = lemp->rule->lhs;
1017 }else{
1018 sp = lemp->rule->lhs;
1019 }
1020 /* Add to the first state (which is always the starting state of the
1021 ** finite state machine) an action to ACCEPT if the lookahead is the
1022 ** start nonterminal. */
1023 Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
1024
1025 /* Resolve conflicts */
1026 for(i=0; i<lemp->nstate; i++){
1027 struct action *ap, *nap;
1028 struct state *stp;
1029 stp = lemp->sorted[i];
drhe9278182007-07-18 18:16:29 +00001030 /* assert( stp->ap ); */
drh75897232000-05-29 14:26:00 +00001031 stp->ap = Action_sort(stp->ap);
drhb59499c2002-02-23 18:45:13 +00001032 for(ap=stp->ap; ap && ap->next; ap=ap->next){
drh75897232000-05-29 14:26:00 +00001033 for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
1034 /* The two actions "ap" and "nap" have the same lookahead.
1035 ** Figure out which one should be used */
1036 lemp->nconflict += resolve_conflict(ap,nap,lemp->errsym);
1037 }
1038 }
1039 }
1040
1041 /* Report an error for each rule that can never be reduced. */
drhaa9f1122007-08-23 02:50:56 +00001042 for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;
drh75897232000-05-29 14:26:00 +00001043 for(i=0; i<lemp->nstate; i++){
1044 struct action *ap;
1045 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
drhaa9f1122007-08-23 02:50:56 +00001046 if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;
drh75897232000-05-29 14:26:00 +00001047 }
1048 }
1049 for(rp=lemp->rule; rp; rp=rp->next){
1050 if( rp->canReduce ) continue;
1051 ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
1052 lemp->errorcnt++;
1053 }
1054}
1055
1056/* Resolve a conflict between the two given actions. If the
drh34ff57b2008-07-14 12:27:51 +00001057** conflict can't be resolved, return non-zero.
drh75897232000-05-29 14:26:00 +00001058**
1059** NO LONGER TRUE:
1060** To resolve a conflict, first look to see if either action
1061** is on an error rule. In that case, take the action which
1062** is not associated with the error rule. If neither or both
1063** actions are associated with an error rule, then try to
1064** use precedence to resolve the conflict.
1065**
1066** If either action is a SHIFT, then it must be apx. This
1067** function won't work if apx->type==REDUCE and apy->type==SHIFT.
1068*/
icculus9e44cf12010-02-14 17:14:22 +00001069static int resolve_conflict(
1070 struct action *apx,
1071 struct action *apy,
1072 struct symbol *errsym /* The error symbol (if defined. NULL otherwise) */
1073){
drh75897232000-05-29 14:26:00 +00001074 struct symbol *spx, *spy;
1075 int errcnt = 0;
1076 assert( apx->sp==apy->sp ); /* Otherwise there would be no conflict */
drhf0fa1c12006-12-14 01:06:22 +00001077 if( apx->type==SHIFT && apy->type==SHIFT ){
drh9892c5d2007-12-21 00:02:11 +00001078 apy->type = SSCONFLICT;
drhf0fa1c12006-12-14 01:06:22 +00001079 errcnt++;
1080 }
drh75897232000-05-29 14:26:00 +00001081 if( apx->type==SHIFT && apy->type==REDUCE ){
1082 spx = apx->sp;
1083 spy = apy->x.rp->precsym;
1084 if( spy==0 || spx->prec<0 || spy->prec<0 ){
1085 /* Not enough precedence information. */
drh9892c5d2007-12-21 00:02:11 +00001086 apy->type = SRCONFLICT;
drh75897232000-05-29 14:26:00 +00001087 errcnt++;
1088 }else if( spx->prec>spy->prec ){ /* Lower precedence wins */
1089 apy->type = RD_RESOLVED;
1090 }else if( spx->prec<spy->prec ){
1091 apx->type = SH_RESOLVED;
1092 }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */
1093 apy->type = RD_RESOLVED; /* associativity */
1094 }else if( spx->prec==spy->prec && spx->assoc==LEFT ){ /* to break tie */
1095 apx->type = SH_RESOLVED;
1096 }else{
1097 assert( spx->prec==spy->prec && spx->assoc==NONE );
drh9892c5d2007-12-21 00:02:11 +00001098 apy->type = SRCONFLICT;
drh75897232000-05-29 14:26:00 +00001099 errcnt++;
1100 }
1101 }else if( apx->type==REDUCE && apy->type==REDUCE ){
1102 spx = apx->x.rp->precsym;
1103 spy = apy->x.rp->precsym;
1104 if( spx==0 || spy==0 || spx->prec<0 ||
1105 spy->prec<0 || spx->prec==spy->prec ){
drh9892c5d2007-12-21 00:02:11 +00001106 apy->type = RRCONFLICT;
drh75897232000-05-29 14:26:00 +00001107 errcnt++;
1108 }else if( spx->prec>spy->prec ){
1109 apy->type = RD_RESOLVED;
1110 }else if( spx->prec<spy->prec ){
1111 apx->type = RD_RESOLVED;
1112 }
1113 }else{
drhb59499c2002-02-23 18:45:13 +00001114 assert(
1115 apx->type==SH_RESOLVED ||
1116 apx->type==RD_RESOLVED ||
drh9892c5d2007-12-21 00:02:11 +00001117 apx->type==SSCONFLICT ||
1118 apx->type==SRCONFLICT ||
1119 apx->type==RRCONFLICT ||
drhb59499c2002-02-23 18:45:13 +00001120 apy->type==SH_RESOLVED ||
1121 apy->type==RD_RESOLVED ||
drh9892c5d2007-12-21 00:02:11 +00001122 apy->type==SSCONFLICT ||
1123 apy->type==SRCONFLICT ||
1124 apy->type==RRCONFLICT
drhb59499c2002-02-23 18:45:13 +00001125 );
1126 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before
1127 ** REDUCEs on the list. If we reach this point it must be because
1128 ** the parser conflict had already been resolved. */
drh75897232000-05-29 14:26:00 +00001129 }
1130 return errcnt;
1131}
1132/********************* From the file "configlist.c" *************************/
1133/*
1134** Routines to processing a configuration list and building a state
1135** in the LEMON parser generator.
1136*/
1137
1138static struct config *freelist = 0; /* List of free configurations */
1139static struct config *current = 0; /* Top of list of configurations */
1140static struct config **currentend = 0; /* Last on list of configs */
1141static struct config *basis = 0; /* Top of list of basis configs */
1142static struct config **basisend = 0; /* End of list of basis configs */
1143
1144/* Return a pointer to a new configuration */
1145PRIVATE struct config *newconfig(){
icculus9e44cf12010-02-14 17:14:22 +00001146 struct config *newcfg;
drh75897232000-05-29 14:26:00 +00001147 if( freelist==0 ){
1148 int i;
1149 int amt = 3;
drh9892c5d2007-12-21 00:02:11 +00001150 freelist = (struct config *)calloc( amt, sizeof(struct config) );
drh75897232000-05-29 14:26:00 +00001151 if( freelist==0 ){
1152 fprintf(stderr,"Unable to allocate memory for a new configuration.");
1153 exit(1);
1154 }
1155 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
1156 freelist[amt-1].next = 0;
1157 }
icculus9e44cf12010-02-14 17:14:22 +00001158 newcfg = freelist;
drh75897232000-05-29 14:26:00 +00001159 freelist = freelist->next;
icculus9e44cf12010-02-14 17:14:22 +00001160 return newcfg;
drh75897232000-05-29 14:26:00 +00001161}
1162
1163/* The configuration "old" is no longer used */
icculus9e44cf12010-02-14 17:14:22 +00001164PRIVATE void deleteconfig(struct config *old)
drh75897232000-05-29 14:26:00 +00001165{
1166 old->next = freelist;
1167 freelist = old;
1168}
1169
1170/* Initialized the configuration list builder */
1171void Configlist_init(){
1172 current = 0;
1173 currentend = &current;
1174 basis = 0;
1175 basisend = &basis;
1176 Configtable_init();
1177 return;
1178}
1179
1180/* Initialized the configuration list builder */
1181void Configlist_reset(){
1182 current = 0;
1183 currentend = &current;
1184 basis = 0;
1185 basisend = &basis;
1186 Configtable_clear(0);
1187 return;
1188}
1189
1190/* Add another configuration to the configuration list */
icculus9e44cf12010-02-14 17:14:22 +00001191struct config *Configlist_add(
1192 struct rule *rp, /* The rule */
1193 int dot /* Index into the RHS of the rule where the dot goes */
1194){
drh75897232000-05-29 14:26:00 +00001195 struct config *cfp, model;
1196
1197 assert( currentend!=0 );
1198 model.rp = rp;
1199 model.dot = dot;
1200 cfp = Configtable_find(&model);
1201 if( cfp==0 ){
1202 cfp = newconfig();
1203 cfp->rp = rp;
1204 cfp->dot = dot;
1205 cfp->fws = SetNew();
1206 cfp->stp = 0;
1207 cfp->fplp = cfp->bplp = 0;
1208 cfp->next = 0;
1209 cfp->bp = 0;
1210 *currentend = cfp;
1211 currentend = &cfp->next;
1212 Configtable_insert(cfp);
1213 }
1214 return cfp;
1215}
1216
1217/* Add a basis configuration to the configuration list */
icculus9e44cf12010-02-14 17:14:22 +00001218struct config *Configlist_addbasis(struct rule *rp, int dot)
drh75897232000-05-29 14:26:00 +00001219{
1220 struct config *cfp, model;
1221
1222 assert( basisend!=0 );
1223 assert( currentend!=0 );
1224 model.rp = rp;
1225 model.dot = dot;
1226 cfp = Configtable_find(&model);
1227 if( cfp==0 ){
1228 cfp = newconfig();
1229 cfp->rp = rp;
1230 cfp->dot = dot;
1231 cfp->fws = SetNew();
1232 cfp->stp = 0;
1233 cfp->fplp = cfp->bplp = 0;
1234 cfp->next = 0;
1235 cfp->bp = 0;
1236 *currentend = cfp;
1237 currentend = &cfp->next;
1238 *basisend = cfp;
1239 basisend = &cfp->bp;
1240 Configtable_insert(cfp);
1241 }
1242 return cfp;
1243}
1244
1245/* Compute the closure of the configuration list */
icculus9e44cf12010-02-14 17:14:22 +00001246void Configlist_closure(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00001247{
1248 struct config *cfp, *newcfp;
1249 struct rule *rp, *newrp;
1250 struct symbol *sp, *xsp;
1251 int i, dot;
1252
1253 assert( currentend!=0 );
1254 for(cfp=current; cfp; cfp=cfp->next){
1255 rp = cfp->rp;
1256 dot = cfp->dot;
1257 if( dot>=rp->nrhs ) continue;
1258 sp = rp->rhs[dot];
1259 if( sp->type==NONTERMINAL ){
1260 if( sp->rule==0 && sp!=lemp->errsym ){
1261 ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",
1262 sp->name);
1263 lemp->errorcnt++;
1264 }
1265 for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
1266 newcfp = Configlist_add(newrp,0);
1267 for(i=dot+1; i<rp->nrhs; i++){
1268 xsp = rp->rhs[i];
1269 if( xsp->type==TERMINAL ){
1270 SetAdd(newcfp->fws,xsp->index);
1271 break;
drhfd405312005-11-06 04:06:59 +00001272 }else if( xsp->type==MULTITERMINAL ){
1273 int k;
1274 for(k=0; k<xsp->nsubsym; k++){
1275 SetAdd(newcfp->fws, xsp->subsym[k]->index);
1276 }
1277 break;
drh75897232000-05-29 14:26:00 +00001278 }else{
1279 SetUnion(newcfp->fws,xsp->firstset);
drhaa9f1122007-08-23 02:50:56 +00001280 if( xsp->lambda==LEMON_FALSE ) break;
drh75897232000-05-29 14:26:00 +00001281 }
1282 }
1283 if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);
1284 }
1285 }
1286 }
1287 return;
1288}
1289
1290/* Sort the configuration list */
1291void Configlist_sort(){
drh218dc692004-05-31 23:13:45 +00001292 current = (struct config *)msort((char *)current,(char **)&(current->next),Configcmp);
drh75897232000-05-29 14:26:00 +00001293 currentend = 0;
1294 return;
1295}
1296
1297/* Sort the basis configuration list */
1298void Configlist_sortbasis(){
drh218dc692004-05-31 23:13:45 +00001299 basis = (struct config *)msort((char *)current,(char **)&(current->bp),Configcmp);
drh75897232000-05-29 14:26:00 +00001300 basisend = 0;
1301 return;
1302}
1303
1304/* Return a pointer to the head of the configuration list and
1305** reset the list */
1306struct config *Configlist_return(){
1307 struct config *old;
1308 old = current;
1309 current = 0;
1310 currentend = 0;
1311 return old;
1312}
1313
1314/* Return a pointer to the head of the configuration list and
1315** reset the list */
1316struct config *Configlist_basis(){
1317 struct config *old;
1318 old = basis;
1319 basis = 0;
1320 basisend = 0;
1321 return old;
1322}
1323
1324/* Free all elements of the given configuration list */
icculus9e44cf12010-02-14 17:14:22 +00001325void Configlist_eat(struct config *cfp)
drh75897232000-05-29 14:26:00 +00001326{
1327 struct config *nextcfp;
1328 for(; cfp; cfp=nextcfp){
1329 nextcfp = cfp->next;
1330 assert( cfp->fplp==0 );
1331 assert( cfp->bplp==0 );
1332 if( cfp->fws ) SetFree(cfp->fws);
1333 deleteconfig(cfp);
1334 }
1335 return;
1336}
1337/***************** From the file "error.c" *********************************/
1338/*
1339** Code for printing error message.
1340*/
1341
drhf9a2e7b2003-04-15 01:49:48 +00001342void ErrorMsg(const char *filename, int lineno, const char *format, ...){
icculus15a2cec2010-02-16 16:07:28 +00001343 va_list ap;
icculus1c11f742010-02-15 00:01:04 +00001344 fprintf(stderr, "%s:%d: ", filename, lineno);
1345 va_start(ap, format);
1346 vfprintf(stderr,format,ap);
1347 va_end(ap);
1348 fprintf(stderr, "\n");
drh75897232000-05-29 14:26:00 +00001349}
1350/**************** From the file "main.c" ************************************/
1351/*
1352** Main program file for the LEMON parser generator.
1353*/
1354
1355/* Report an out-of-memory condition and abort. This function
1356** is used mostly by the "MemoryCheck" macro in struct.h
1357*/
1358void memory_error(){
1359 fprintf(stderr,"Out of memory. Aborting...\n");
1360 exit(1);
1361}
1362
drh6d08b4d2004-07-20 12:45:22 +00001363static int nDefine = 0; /* Number of -D options on the command line */
1364static char **azDefine = 0; /* Name of the -D macros */
1365
1366/* This routine is called with the argument to each -D command-line option.
1367** Add the macro defined to the azDefine array.
1368*/
1369static void handle_D_option(char *z){
1370 char **paz;
1371 nDefine++;
icculus9e44cf12010-02-14 17:14:22 +00001372 azDefine = (char **) realloc(azDefine, sizeof(azDefine[0])*nDefine);
drh6d08b4d2004-07-20 12:45:22 +00001373 if( azDefine==0 ){
1374 fprintf(stderr,"out of memory\n");
1375 exit(1);
1376 }
1377 paz = &azDefine[nDefine-1];
icculus9e44cf12010-02-14 17:14:22 +00001378 *paz = (char *) malloc( lemonStrlen(z)+1 );
drh6d08b4d2004-07-20 12:45:22 +00001379 if( *paz==0 ){
1380 fprintf(stderr,"out of memory\n");
1381 exit(1);
1382 }
1383 strcpy(*paz, z);
1384 for(z=*paz; *z && *z!='='; z++){}
1385 *z = 0;
1386}
1387
icculus3e143bd2010-02-14 00:48:49 +00001388static char *user_templatename = NULL;
1389static void handle_T_option(char *z){
icculus9e44cf12010-02-14 17:14:22 +00001390 user_templatename = (char *) malloc( lemonStrlen(z)+1 );
icculus3e143bd2010-02-14 00:48:49 +00001391 if( user_templatename==0 ){
1392 memory_error();
1393 }
1394 strcpy(user_templatename, z);
1395}
drh75897232000-05-29 14:26:00 +00001396
1397/* The main program. Parse the command line and do it... */
icculus9e44cf12010-02-14 17:14:22 +00001398int main(int argc, char **argv)
drh75897232000-05-29 14:26:00 +00001399{
1400 static int version = 0;
1401 static int rpflag = 0;
1402 static int basisflag = 0;
1403 static int compress = 0;
1404 static int quiet = 0;
1405 static int statistics = 0;
1406 static int mhflag = 0;
shane58543932008-12-10 20:10:04 +00001407 static int nolinenosflag = 0;
drh75897232000-05-29 14:26:00 +00001408 static struct s_options options[] = {
1409 {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},
1410 {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},
drh6d08b4d2004-07-20 12:45:22 +00001411 {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},
icculus3e143bd2010-02-14 00:48:49 +00001412 {OPT_FSTR, "T", (char*)handle_T_option, "Specify a template file."},
drh75897232000-05-29 14:26:00 +00001413 {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},
shane58543932008-12-10 20:10:04 +00001414 {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file."},
1415 {OPT_FLAG, "l", (char*)&nolinenosflag, "Do not print #line statements."},
drh75897232000-05-29 14:26:00 +00001416 {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},
drh6d08b4d2004-07-20 12:45:22 +00001417 {OPT_FLAG, "s", (char*)&statistics,
1418 "Print parser stats to standard output."},
drh75897232000-05-29 14:26:00 +00001419 {OPT_FLAG, "x", (char*)&version, "Print the version number."},
1420 {OPT_FLAG,0,0,0}
1421 };
1422 int i;
icculus42585cf2010-02-14 05:19:56 +00001423 int exitcode;
drh75897232000-05-29 14:26:00 +00001424 struct lemon lem;
1425
icculusf5ad8242010-02-14 05:34:42 +00001426 atexit(LemonAtExit);
1427
drhb0c86772000-06-02 23:21:26 +00001428 OptInit(argv,options,stderr);
drh75897232000-05-29 14:26:00 +00001429 if( version ){
drhb19a2bc2001-09-16 00:13:26 +00001430 printf("Lemon version 1.0\n");
drh75897232000-05-29 14:26:00 +00001431 exit(0);
1432 }
drhb0c86772000-06-02 23:21:26 +00001433 if( OptNArgs()!=1 ){
drh75897232000-05-29 14:26:00 +00001434 fprintf(stderr,"Exactly one filename argument is required.\n");
1435 exit(1);
1436 }
drh954f6b42006-06-13 13:27:46 +00001437 memset(&lem, 0, sizeof(lem));
drh75897232000-05-29 14:26:00 +00001438 lem.errorcnt = 0;
1439
1440 /* Initialize the machine */
1441 Strsafe_init();
1442 Symbol_init();
1443 State_init();
1444 lem.argv0 = argv[0];
drhb0c86772000-06-02 23:21:26 +00001445 lem.filename = OptArg(0);
drh75897232000-05-29 14:26:00 +00001446 lem.basisflag = basisflag;
shane58543932008-12-10 20:10:04 +00001447 lem.nolinenosflag = nolinenosflag;
drh75897232000-05-29 14:26:00 +00001448 Symbol_new("$");
1449 lem.errsym = Symbol_new("error");
drhc4dd3fd2008-01-22 01:48:05 +00001450 lem.errsym->useCnt = 0;
drh75897232000-05-29 14:26:00 +00001451
1452 /* Parse the input file */
1453 Parse(&lem);
1454 if( lem.errorcnt ) exit(lem.errorcnt);
drh954f6b42006-06-13 13:27:46 +00001455 if( lem.nrule==0 ){
drh75897232000-05-29 14:26:00 +00001456 fprintf(stderr,"Empty grammar.\n");
1457 exit(1);
1458 }
1459
1460 /* Count and index the symbols of the grammar */
1461 lem.nsymbol = Symbol_count();
1462 Symbol_new("{default}");
1463 lem.symbols = Symbol_arrayof();
drh60d31652004-02-22 00:08:04 +00001464 for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
icculus9e44cf12010-02-14 17:14:22 +00001465 qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*), Symbolcmpp);
drh75897232000-05-29 14:26:00 +00001466 for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
1467 for(i=1; isupper(lem.symbols[i]->name[0]); i++);
1468 lem.nterminal = i;
1469
1470 /* Generate a reprint of the grammar, if requested on the command line */
1471 if( rpflag ){
1472 Reprint(&lem);
1473 }else{
1474 /* Initialize the size for all follow and first sets */
drh9892c5d2007-12-21 00:02:11 +00001475 SetSize(lem.nterminal+1);
drh75897232000-05-29 14:26:00 +00001476
1477 /* Find the precedence for every production rule (that has one) */
1478 FindRulePrecedences(&lem);
1479
1480 /* Compute the lambda-nonterminals and the first-sets for every
1481 ** nonterminal */
1482 FindFirstSets(&lem);
1483
1484 /* Compute all LR(0) states. Also record follow-set propagation
1485 ** links so that the follow-set can be computed later */
1486 lem.nstate = 0;
1487 FindStates(&lem);
1488 lem.sorted = State_arrayof();
1489
1490 /* Tie up loose ends on the propagation links */
1491 FindLinks(&lem);
1492
1493 /* Compute the follow set of every reducible configuration */
1494 FindFollowSets(&lem);
1495
1496 /* Compute the action tables */
1497 FindActions(&lem);
1498
1499 /* Compress the action tables */
1500 if( compress==0 ) CompressTables(&lem);
1501
drhada354d2005-11-05 15:03:59 +00001502 /* Reorder and renumber the states so that states with fewer choices
1503 ** occur at the end. */
1504 ResortStates(&lem);
1505
drh75897232000-05-29 14:26:00 +00001506 /* Generate a report of the parser generated. (the "y.output" file) */
1507 if( !quiet ) ReportOutput(&lem);
1508
1509 /* Generate the source code for the parser */
1510 ReportTable(&lem, mhflag);
1511
1512 /* Produce a header file for use by the scanner. (This step is
1513 ** omitted if the "-m" option is used because makeheaders will
1514 ** generate the file for us.) */
1515 if( !mhflag ) ReportHeader(&lem);
1516 }
1517 if( statistics ){
1518 printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
1519 lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
1520 printf(" %d states, %d parser table entries, %d conflicts\n",
1521 lem.nstate, lem.tablesize, lem.nconflict);
1522 }
icculus8e158022010-02-16 16:09:03 +00001523 if( lem.nconflict > 0 ){
1524 fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
icculus42585cf2010-02-14 05:19:56 +00001525 }
1526
1527 /* return 0 on success, 1 on failure. */
icculus8e158022010-02-16 16:09:03 +00001528 exitcode = ((lem.errorcnt > 0) || (lem.nconflict > 0)) ? 1 : 0;
icculusf5ad8242010-02-14 05:34:42 +00001529 successful_exit = (exitcode == 0);
icculus42585cf2010-02-14 05:19:56 +00001530 exit(exitcode);
1531 return (exitcode);
drh75897232000-05-29 14:26:00 +00001532}
1533/******************** From the file "msort.c" *******************************/
1534/*
1535** A generic merge-sort program.
1536**
1537** USAGE:
1538** Let "ptr" be a pointer to some structure which is at the head of
1539** a null-terminated list. Then to sort the list call:
1540**
1541** ptr = msort(ptr,&(ptr->next),cmpfnc);
1542**
1543** In the above, "cmpfnc" is a pointer to a function which compares
1544** two instances of the structure and returns an integer, as in
1545** strcmp. The second argument is a pointer to the pointer to the
1546** second element of the linked list. This address is used to compute
1547** the offset to the "next" field within the structure. The offset to
1548** the "next" field must be constant for all structures in the list.
1549**
1550** The function returns a new pointer which is the head of the list
1551** after sorting.
1552**
1553** ALGORITHM:
1554** Merge-sort.
1555*/
1556
1557/*
1558** Return a pointer to the next structure in the linked list.
1559*/
drhba99af52001-10-25 20:37:16 +00001560#define NEXT(A) (*(char**)(((unsigned long)A)+offset))
drh75897232000-05-29 14:26:00 +00001561
1562/*
1563** Inputs:
1564** a: A sorted, null-terminated linked list. (May be null).
1565** b: A sorted, null-terminated linked list. (May be null).
1566** cmp: A pointer to the comparison function.
1567** offset: Offset in the structure to the "next" field.
1568**
1569** Return Value:
1570** A pointer to the head of a sorted list containing the elements
1571** of both a and b.
1572**
1573** Side effects:
1574** The "next" pointers for elements in the lists a and b are
1575** changed.
1576*/
drhe9278182007-07-18 18:16:29 +00001577static char *merge(
1578 char *a,
1579 char *b,
1580 int (*cmp)(const char*,const char*),
1581 int offset
1582){
drh75897232000-05-29 14:26:00 +00001583 char *ptr, *head;
1584
1585 if( a==0 ){
1586 head = b;
1587 }else if( b==0 ){
1588 head = a;
1589 }else{
drhe594bc32009-11-03 13:02:25 +00001590 if( (*cmp)(a,b)<=0 ){
drh75897232000-05-29 14:26:00 +00001591 ptr = a;
1592 a = NEXT(a);
1593 }else{
1594 ptr = b;
1595 b = NEXT(b);
1596 }
1597 head = ptr;
1598 while( a && b ){
drhe594bc32009-11-03 13:02:25 +00001599 if( (*cmp)(a,b)<=0 ){
drh75897232000-05-29 14:26:00 +00001600 NEXT(ptr) = a;
1601 ptr = a;
1602 a = NEXT(a);
1603 }else{
1604 NEXT(ptr) = b;
1605 ptr = b;
1606 b = NEXT(b);
1607 }
1608 }
1609 if( a ) NEXT(ptr) = a;
1610 else NEXT(ptr) = b;
1611 }
1612 return head;
1613}
1614
1615/*
1616** Inputs:
1617** list: Pointer to a singly-linked list of structures.
1618** next: Pointer to pointer to the second element of the list.
1619** cmp: A comparison function.
1620**
1621** Return Value:
1622** A pointer to the head of a sorted list containing the elements
1623** orginally in list.
1624**
1625** Side effects:
1626** The "next" pointers for elements in list are changed.
1627*/
1628#define LISTSIZE 30
drhe9278182007-07-18 18:16:29 +00001629static char *msort(
1630 char *list,
1631 char **next,
1632 int (*cmp)(const char*,const char*)
1633){
drhba99af52001-10-25 20:37:16 +00001634 unsigned long offset;
drh75897232000-05-29 14:26:00 +00001635 char *ep;
1636 char *set[LISTSIZE];
1637 int i;
drhba99af52001-10-25 20:37:16 +00001638 offset = (unsigned long)next - (unsigned long)list;
drh75897232000-05-29 14:26:00 +00001639 for(i=0; i<LISTSIZE; i++) set[i] = 0;
1640 while( list ){
1641 ep = list;
1642 list = NEXT(list);
1643 NEXT(ep) = 0;
1644 for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
1645 ep = merge(ep,set[i],cmp,offset);
1646 set[i] = 0;
1647 }
1648 set[i] = ep;
1649 }
1650 ep = 0;
drhe594bc32009-11-03 13:02:25 +00001651 for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(set[i],ep,cmp,offset);
drh75897232000-05-29 14:26:00 +00001652 return ep;
1653}
1654/************************ From the file "option.c" **************************/
1655static char **argv;
1656static struct s_options *op;
1657static FILE *errstream;
1658
1659#define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
1660
1661/*
1662** Print the command line with a carrot pointing to the k-th character
1663** of the n-th field.
1664*/
icculus9e44cf12010-02-14 17:14:22 +00001665static void errline(int n, int k, FILE *err)
drh75897232000-05-29 14:26:00 +00001666{
1667 int spcnt, i;
drh75897232000-05-29 14:26:00 +00001668 if( argv[0] ) fprintf(err,"%s",argv[0]);
drh87cf1372008-08-13 20:09:06 +00001669 spcnt = lemonStrlen(argv[0]) + 1;
drh75897232000-05-29 14:26:00 +00001670 for(i=1; i<n && argv[i]; i++){
1671 fprintf(err," %s",argv[i]);
drh87cf1372008-08-13 20:09:06 +00001672 spcnt += lemonStrlen(argv[i])+1;
drh75897232000-05-29 14:26:00 +00001673 }
1674 spcnt += k;
1675 for(; argv[i]; i++) fprintf(err," %s",argv[i]);
1676 if( spcnt<20 ){
1677 fprintf(err,"\n%*s^-- here\n",spcnt,"");
1678 }else{
1679 fprintf(err,"\n%*shere --^\n",spcnt-7,"");
1680 }
1681}
1682
1683/*
1684** Return the index of the N-th non-switch argument. Return -1
1685** if N is out of range.
1686*/
icculus9e44cf12010-02-14 17:14:22 +00001687static int argindex(int n)
drh75897232000-05-29 14:26:00 +00001688{
1689 int i;
1690 int dashdash = 0;
1691 if( argv!=0 && *argv!=0 ){
1692 for(i=1; argv[i]; i++){
1693 if( dashdash || !ISOPT(argv[i]) ){
1694 if( n==0 ) return i;
1695 n--;
1696 }
1697 if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1698 }
1699 }
1700 return -1;
1701}
1702
1703static char emsg[] = "Command line syntax error: ";
1704
1705/*
1706** Process a flag command line argument.
1707*/
icculus9e44cf12010-02-14 17:14:22 +00001708static int handleflags(int i, FILE *err)
drh75897232000-05-29 14:26:00 +00001709{
1710 int v;
1711 int errcnt = 0;
1712 int j;
1713 for(j=0; op[j].label; j++){
drh87cf1372008-08-13 20:09:06 +00001714 if( strncmp(&argv[i][1],op[j].label,lemonStrlen(op[j].label))==0 ) break;
drh75897232000-05-29 14:26:00 +00001715 }
1716 v = argv[i][0]=='-' ? 1 : 0;
1717 if( op[j].label==0 ){
1718 if( err ){
1719 fprintf(err,"%sundefined option.\n",emsg);
1720 errline(i,1,err);
1721 }
1722 errcnt++;
1723 }else if( op[j].type==OPT_FLAG ){
1724 *((int*)op[j].arg) = v;
1725 }else if( op[j].type==OPT_FFLAG ){
icculus9e44cf12010-02-14 17:14:22 +00001726 (*(void(*)(int))(op[j].arg))(v);
drh6d08b4d2004-07-20 12:45:22 +00001727 }else if( op[j].type==OPT_FSTR ){
icculus9e44cf12010-02-14 17:14:22 +00001728 (*(void(*)(char *))(op[j].arg))(&argv[i][2]);
drh75897232000-05-29 14:26:00 +00001729 }else{
1730 if( err ){
1731 fprintf(err,"%smissing argument on switch.\n",emsg);
1732 errline(i,1,err);
1733 }
1734 errcnt++;
1735 }
1736 return errcnt;
1737}
1738
1739/*
1740** Process a command line switch which has an argument.
1741*/
icculus9e44cf12010-02-14 17:14:22 +00001742static int handleswitch(int i, FILE *err)
drh75897232000-05-29 14:26:00 +00001743{
1744 int lv = 0;
1745 double dv = 0.0;
1746 char *sv = 0, *end;
1747 char *cp;
1748 int j;
1749 int errcnt = 0;
1750 cp = strchr(argv[i],'=');
drh43617e92006-03-06 20:55:46 +00001751 assert( cp!=0 );
drh75897232000-05-29 14:26:00 +00001752 *cp = 0;
1753 for(j=0; op[j].label; j++){
1754 if( strcmp(argv[i],op[j].label)==0 ) break;
1755 }
1756 *cp = '=';
1757 if( op[j].label==0 ){
1758 if( err ){
1759 fprintf(err,"%sundefined option.\n",emsg);
1760 errline(i,0,err);
1761 }
1762 errcnt++;
1763 }else{
1764 cp++;
1765 switch( op[j].type ){
1766 case OPT_FLAG:
1767 case OPT_FFLAG:
1768 if( err ){
1769 fprintf(err,"%soption requires an argument.\n",emsg);
1770 errline(i,0,err);
1771 }
1772 errcnt++;
1773 break;
1774 case OPT_DBL:
1775 case OPT_FDBL:
1776 dv = strtod(cp,&end);
1777 if( *end ){
1778 if( err ){
1779 fprintf(err,"%sillegal character in floating-point argument.\n",emsg);
drhba99af52001-10-25 20:37:16 +00001780 errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
drh75897232000-05-29 14:26:00 +00001781 }
1782 errcnt++;
1783 }
1784 break;
1785 case OPT_INT:
1786 case OPT_FINT:
1787 lv = strtol(cp,&end,0);
1788 if( *end ){
1789 if( err ){
1790 fprintf(err,"%sillegal character in integer argument.\n",emsg);
drhba99af52001-10-25 20:37:16 +00001791 errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
drh75897232000-05-29 14:26:00 +00001792 }
1793 errcnt++;
1794 }
1795 break;
1796 case OPT_STR:
1797 case OPT_FSTR:
1798 sv = cp;
1799 break;
1800 }
1801 switch( op[j].type ){
1802 case OPT_FLAG:
1803 case OPT_FFLAG:
1804 break;
1805 case OPT_DBL:
1806 *(double*)(op[j].arg) = dv;
1807 break;
1808 case OPT_FDBL:
icculus9e44cf12010-02-14 17:14:22 +00001809 (*(void(*)(double))(op[j].arg))(dv);
drh75897232000-05-29 14:26:00 +00001810 break;
1811 case OPT_INT:
1812 *(int*)(op[j].arg) = lv;
1813 break;
1814 case OPT_FINT:
icculus9e44cf12010-02-14 17:14:22 +00001815 (*(void(*)(int))(op[j].arg))((int)lv);
drh75897232000-05-29 14:26:00 +00001816 break;
1817 case OPT_STR:
1818 *(char**)(op[j].arg) = sv;
1819 break;
1820 case OPT_FSTR:
icculus9e44cf12010-02-14 17:14:22 +00001821 (*(void(*)(char *))(op[j].arg))(sv);
drh75897232000-05-29 14:26:00 +00001822 break;
1823 }
1824 }
1825 return errcnt;
1826}
1827
icculus9e44cf12010-02-14 17:14:22 +00001828int OptInit(char **a, struct s_options *o, FILE *err)
drh75897232000-05-29 14:26:00 +00001829{
1830 int errcnt = 0;
1831 argv = a;
1832 op = o;
1833 errstream = err;
1834 if( argv && *argv && op ){
1835 int i;
1836 for(i=1; argv[i]; i++){
1837 if( argv[i][0]=='+' || argv[i][0]=='-' ){
1838 errcnt += handleflags(i,err);
1839 }else if( strchr(argv[i],'=') ){
1840 errcnt += handleswitch(i,err);
1841 }
1842 }
1843 }
1844 if( errcnt>0 ){
1845 fprintf(err,"Valid command line options for \"%s\" are:\n",*a);
drhb0c86772000-06-02 23:21:26 +00001846 OptPrint();
drh75897232000-05-29 14:26:00 +00001847 exit(1);
1848 }
1849 return 0;
1850}
1851
drhb0c86772000-06-02 23:21:26 +00001852int OptNArgs(){
drh75897232000-05-29 14:26:00 +00001853 int cnt = 0;
1854 int dashdash = 0;
1855 int i;
1856 if( argv!=0 && argv[0]!=0 ){
1857 for(i=1; argv[i]; i++){
1858 if( dashdash || !ISOPT(argv[i]) ) cnt++;
1859 if( strcmp(argv[i],"--")==0 ) dashdash = 1;
1860 }
1861 }
1862 return cnt;
1863}
1864
icculus9e44cf12010-02-14 17:14:22 +00001865char *OptArg(int n)
drh75897232000-05-29 14:26:00 +00001866{
1867 int i;
1868 i = argindex(n);
1869 return i>=0 ? argv[i] : 0;
1870}
1871
icculus9e44cf12010-02-14 17:14:22 +00001872void OptErr(int n)
drh75897232000-05-29 14:26:00 +00001873{
1874 int i;
1875 i = argindex(n);
1876 if( i>=0 ) errline(i,0,errstream);
1877}
1878
drhb0c86772000-06-02 23:21:26 +00001879void OptPrint(){
drh75897232000-05-29 14:26:00 +00001880 int i;
1881 int max, len;
1882 max = 0;
1883 for(i=0; op[i].label; i++){
drh87cf1372008-08-13 20:09:06 +00001884 len = lemonStrlen(op[i].label) + 1;
drh75897232000-05-29 14:26:00 +00001885 switch( op[i].type ){
1886 case OPT_FLAG:
1887 case OPT_FFLAG:
1888 break;
1889 case OPT_INT:
1890 case OPT_FINT:
1891 len += 9; /* length of "<integer>" */
1892 break;
1893 case OPT_DBL:
1894 case OPT_FDBL:
1895 len += 6; /* length of "<real>" */
1896 break;
1897 case OPT_STR:
1898 case OPT_FSTR:
1899 len += 8; /* length of "<string>" */
1900 break;
1901 }
1902 if( len>max ) max = len;
1903 }
1904 for(i=0; op[i].label; i++){
1905 switch( op[i].type ){
1906 case OPT_FLAG:
1907 case OPT_FFLAG:
1908 fprintf(errstream," -%-*s %s\n",max,op[i].label,op[i].message);
1909 break;
1910 case OPT_INT:
1911 case OPT_FINT:
1912 fprintf(errstream," %s=<integer>%*s %s\n",op[i].label,
drh87cf1372008-08-13 20:09:06 +00001913 (int)(max-lemonStrlen(op[i].label)-9),"",op[i].message);
drh75897232000-05-29 14:26:00 +00001914 break;
1915 case OPT_DBL:
1916 case OPT_FDBL:
1917 fprintf(errstream," %s=<real>%*s %s\n",op[i].label,
drh87cf1372008-08-13 20:09:06 +00001918 (int)(max-lemonStrlen(op[i].label)-6),"",op[i].message);
drh75897232000-05-29 14:26:00 +00001919 break;
1920 case OPT_STR:
1921 case OPT_FSTR:
1922 fprintf(errstream," %s=<string>%*s %s\n",op[i].label,
drh87cf1372008-08-13 20:09:06 +00001923 (int)(max-lemonStrlen(op[i].label)-8),"",op[i].message);
drh75897232000-05-29 14:26:00 +00001924 break;
1925 }
1926 }
1927}
1928/*********************** From the file "parse.c" ****************************/
1929/*
1930** Input file parser for the LEMON parser generator.
1931*/
1932
1933/* The state of the parser */
icculus9e44cf12010-02-14 17:14:22 +00001934enum e_state {
1935 INITIALIZE,
1936 WAITING_FOR_DECL_OR_RULE,
1937 WAITING_FOR_DECL_KEYWORD,
1938 WAITING_FOR_DECL_ARG,
1939 WAITING_FOR_PRECEDENCE_SYMBOL,
1940 WAITING_FOR_ARROW,
1941 IN_RHS,
1942 LHS_ALIAS_1,
1943 LHS_ALIAS_2,
1944 LHS_ALIAS_3,
1945 RHS_ALIAS_1,
1946 RHS_ALIAS_2,
1947 PRECEDENCE_MARK_1,
1948 PRECEDENCE_MARK_2,
1949 RESYNC_AFTER_RULE_ERROR,
1950 RESYNC_AFTER_DECL_ERROR,
1951 WAITING_FOR_DESTRUCTOR_SYMBOL,
1952 WAITING_FOR_DATATYPE_SYMBOL,
1953 WAITING_FOR_FALLBACK_ID,
icculus9e44cf12010-02-14 17:14:22 +00001954 WAITING_FOR_WILDCARD_ID
1955};
drh75897232000-05-29 14:26:00 +00001956struct pstate {
1957 char *filename; /* Name of the input file */
1958 int tokenlineno; /* Linenumber at which current token starts */
1959 int errorcnt; /* Number of errors so far */
1960 char *tokenstart; /* Text of current token */
1961 struct lemon *gp; /* Global state vector */
icculus9e44cf12010-02-14 17:14:22 +00001962 enum e_state state; /* The state of the parser */
drh0bd1f4e2002-06-06 18:54:39 +00001963 struct symbol *fallback; /* The fallback token */
drh75897232000-05-29 14:26:00 +00001964 struct symbol *lhs; /* Left-hand side of current rule */
icculus9e44cf12010-02-14 17:14:22 +00001965 const char *lhsalias; /* Alias for the LHS */
drh75897232000-05-29 14:26:00 +00001966 int nrhs; /* Number of right-hand side symbols seen */
1967 struct symbol *rhs[MAXRHS]; /* RHS symbols */
icculus9e44cf12010-02-14 17:14:22 +00001968 const char *alias[MAXRHS]; /* Aliases for each RHS symbol (or NULL) */
drh75897232000-05-29 14:26:00 +00001969 struct rule *prevrule; /* Previous rule parsed */
icculus9e44cf12010-02-14 17:14:22 +00001970 const char *declkeyword; /* Keyword of a declaration */
drh75897232000-05-29 14:26:00 +00001971 char **declargslot; /* Where the declaration argument should be put */
drha5808f32008-04-27 22:19:44 +00001972 int insertLineMacro; /* Add #line before declaration insert */
drh4dc8ef52008-07-01 17:13:57 +00001973 int *decllinenoslot; /* Where to write declaration line number */
drh75897232000-05-29 14:26:00 +00001974 enum e_assoc declassoc; /* Assign this association to decl arguments */
1975 int preccounter; /* Assign this precedence to decl arguments */
1976 struct rule *firstrule; /* Pointer to first rule in the grammar */
1977 struct rule *lastrule; /* Pointer to the most recently parsed rule */
1978};
1979
1980/* Parse a single token */
icculus9e44cf12010-02-14 17:14:22 +00001981static void parseonetoken(struct pstate *psp)
drh75897232000-05-29 14:26:00 +00001982{
icculus9e44cf12010-02-14 17:14:22 +00001983 const char *x;
drh75897232000-05-29 14:26:00 +00001984 x = Strsafe(psp->tokenstart); /* Save the token permanently */
1985#if 0
1986 printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
1987 x,psp->state);
1988#endif
1989 switch( psp->state ){
1990 case INITIALIZE:
1991 psp->prevrule = 0;
1992 psp->preccounter = 0;
1993 psp->firstrule = psp->lastrule = 0;
1994 psp->gp->nrule = 0;
1995 /* Fall thru to next case */
1996 case WAITING_FOR_DECL_OR_RULE:
1997 if( x[0]=='%' ){
1998 psp->state = WAITING_FOR_DECL_KEYWORD;
1999 }else if( islower(x[0]) ){
2000 psp->lhs = Symbol_new(x);
2001 psp->nrhs = 0;
2002 psp->lhsalias = 0;
2003 psp->state = WAITING_FOR_ARROW;
2004 }else if( x[0]=='{' ){
2005 if( psp->prevrule==0 ){
2006 ErrorMsg(psp->filename,psp->tokenlineno,
drh34ff57b2008-07-14 12:27:51 +00002007"There is no prior rule opon which to attach the code \
drh75897232000-05-29 14:26:00 +00002008fragment which begins on this line.");
2009 psp->errorcnt++;
2010 }else if( psp->prevrule->code!=0 ){
2011 ErrorMsg(psp->filename,psp->tokenlineno,
2012"Code fragment beginning on this line is not the first \
2013to follow the previous rule.");
2014 psp->errorcnt++;
2015 }else{
2016 psp->prevrule->line = psp->tokenlineno;
2017 psp->prevrule->code = &x[1];
2018 }
2019 }else if( x[0]=='[' ){
2020 psp->state = PRECEDENCE_MARK_1;
2021 }else{
2022 ErrorMsg(psp->filename,psp->tokenlineno,
2023 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
2024 x);
2025 psp->errorcnt++;
2026 }
2027 break;
2028 case PRECEDENCE_MARK_1:
2029 if( !isupper(x[0]) ){
2030 ErrorMsg(psp->filename,psp->tokenlineno,
2031 "The precedence symbol must be a terminal.");
2032 psp->errorcnt++;
2033 }else if( psp->prevrule==0 ){
2034 ErrorMsg(psp->filename,psp->tokenlineno,
2035 "There is no prior rule to assign precedence \"[%s]\".",x);
2036 psp->errorcnt++;
2037 }else if( psp->prevrule->precsym!=0 ){
2038 ErrorMsg(psp->filename,psp->tokenlineno,
2039"Precedence mark on this line is not the first \
2040to follow the previous rule.");
2041 psp->errorcnt++;
2042 }else{
2043 psp->prevrule->precsym = Symbol_new(x);
2044 }
2045 psp->state = PRECEDENCE_MARK_2;
2046 break;
2047 case PRECEDENCE_MARK_2:
2048 if( x[0]!=']' ){
2049 ErrorMsg(psp->filename,psp->tokenlineno,
2050 "Missing \"]\" on precedence mark.");
2051 psp->errorcnt++;
2052 }
2053 psp->state = WAITING_FOR_DECL_OR_RULE;
2054 break;
2055 case WAITING_FOR_ARROW:
2056 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2057 psp->state = IN_RHS;
2058 }else if( x[0]=='(' ){
2059 psp->state = LHS_ALIAS_1;
2060 }else{
2061 ErrorMsg(psp->filename,psp->tokenlineno,
2062 "Expected to see a \":\" following the LHS symbol \"%s\".",
2063 psp->lhs->name);
2064 psp->errorcnt++;
2065 psp->state = RESYNC_AFTER_RULE_ERROR;
2066 }
2067 break;
2068 case LHS_ALIAS_1:
2069 if( isalpha(x[0]) ){
2070 psp->lhsalias = x;
2071 psp->state = LHS_ALIAS_2;
2072 }else{
2073 ErrorMsg(psp->filename,psp->tokenlineno,
2074 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
2075 x,psp->lhs->name);
2076 psp->errorcnt++;
2077 psp->state = RESYNC_AFTER_RULE_ERROR;
2078 }
2079 break;
2080 case LHS_ALIAS_2:
2081 if( x[0]==')' ){
2082 psp->state = LHS_ALIAS_3;
2083 }else{
2084 ErrorMsg(psp->filename,psp->tokenlineno,
2085 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2086 psp->errorcnt++;
2087 psp->state = RESYNC_AFTER_RULE_ERROR;
2088 }
2089 break;
2090 case LHS_ALIAS_3:
2091 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
2092 psp->state = IN_RHS;
2093 }else{
2094 ErrorMsg(psp->filename,psp->tokenlineno,
2095 "Missing \"->\" following: \"%s(%s)\".",
2096 psp->lhs->name,psp->lhsalias);
2097 psp->errorcnt++;
2098 psp->state = RESYNC_AFTER_RULE_ERROR;
2099 }
2100 break;
2101 case IN_RHS:
2102 if( x[0]=='.' ){
2103 struct rule *rp;
drh9892c5d2007-12-21 00:02:11 +00002104 rp = (struct rule *)calloc( sizeof(struct rule) +
2105 sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs, 1);
drh75897232000-05-29 14:26:00 +00002106 if( rp==0 ){
2107 ErrorMsg(psp->filename,psp->tokenlineno,
2108 "Can't allocate enough memory for this rule.");
2109 psp->errorcnt++;
2110 psp->prevrule = 0;
2111 }else{
2112 int i;
2113 rp->ruleline = psp->tokenlineno;
2114 rp->rhs = (struct symbol**)&rp[1];
icculus9e44cf12010-02-14 17:14:22 +00002115 rp->rhsalias = (const char**)&(rp->rhs[psp->nrhs]);
drh75897232000-05-29 14:26:00 +00002116 for(i=0; i<psp->nrhs; i++){
2117 rp->rhs[i] = psp->rhs[i];
2118 rp->rhsalias[i] = psp->alias[i];
2119 }
2120 rp->lhs = psp->lhs;
2121 rp->lhsalias = psp->lhsalias;
2122 rp->nrhs = psp->nrhs;
2123 rp->code = 0;
2124 rp->precsym = 0;
2125 rp->index = psp->gp->nrule++;
2126 rp->nextlhs = rp->lhs->rule;
2127 rp->lhs->rule = rp;
2128 rp->next = 0;
2129 if( psp->firstrule==0 ){
2130 psp->firstrule = psp->lastrule = rp;
2131 }else{
2132 psp->lastrule->next = rp;
2133 psp->lastrule = rp;
2134 }
2135 psp->prevrule = rp;
2136 }
2137 psp->state = WAITING_FOR_DECL_OR_RULE;
2138 }else if( isalpha(x[0]) ){
2139 if( psp->nrhs>=MAXRHS ){
2140 ErrorMsg(psp->filename,psp->tokenlineno,
drhc4dd3fd2008-01-22 01:48:05 +00002141 "Too many symbols on RHS of rule beginning at \"%s\".",
drh75897232000-05-29 14:26:00 +00002142 x);
2143 psp->errorcnt++;
2144 psp->state = RESYNC_AFTER_RULE_ERROR;
2145 }else{
2146 psp->rhs[psp->nrhs] = Symbol_new(x);
2147 psp->alias[psp->nrhs] = 0;
2148 psp->nrhs++;
2149 }
drhfd405312005-11-06 04:06:59 +00002150 }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 ){
2151 struct symbol *msp = psp->rhs[psp->nrhs-1];
2152 if( msp->type!=MULTITERMINAL ){
2153 struct symbol *origsp = msp;
icculus9e44cf12010-02-14 17:14:22 +00002154 msp = (struct symbol *) calloc(1,sizeof(*msp));
drhfd405312005-11-06 04:06:59 +00002155 memset(msp, 0, sizeof(*msp));
2156 msp->type = MULTITERMINAL;
2157 msp->nsubsym = 1;
icculus9e44cf12010-02-14 17:14:22 +00002158 msp->subsym = (struct symbol **) calloc(1,sizeof(struct symbol*));
drhfd405312005-11-06 04:06:59 +00002159 msp->subsym[0] = origsp;
2160 msp->name = origsp->name;
2161 psp->rhs[psp->nrhs-1] = msp;
2162 }
2163 msp->nsubsym++;
icculus9e44cf12010-02-14 17:14:22 +00002164 msp->subsym = (struct symbol **) realloc(msp->subsym,
2165 sizeof(struct symbol*)*msp->nsubsym);
drhfd405312005-11-06 04:06:59 +00002166 msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);
2167 if( islower(x[1]) || islower(msp->subsym[0]->name[0]) ){
2168 ErrorMsg(psp->filename,psp->tokenlineno,
2169 "Cannot form a compound containing a non-terminal");
2170 psp->errorcnt++;
2171 }
drh75897232000-05-29 14:26:00 +00002172 }else if( x[0]=='(' && psp->nrhs>0 ){
2173 psp->state = RHS_ALIAS_1;
2174 }else{
2175 ErrorMsg(psp->filename,psp->tokenlineno,
2176 "Illegal character on RHS of rule: \"%s\".",x);
2177 psp->errorcnt++;
2178 psp->state = RESYNC_AFTER_RULE_ERROR;
2179 }
2180 break;
2181 case RHS_ALIAS_1:
2182 if( isalpha(x[0]) ){
2183 psp->alias[psp->nrhs-1] = x;
2184 psp->state = RHS_ALIAS_2;
2185 }else{
2186 ErrorMsg(psp->filename,psp->tokenlineno,
2187 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
2188 x,psp->rhs[psp->nrhs-1]->name);
2189 psp->errorcnt++;
2190 psp->state = RESYNC_AFTER_RULE_ERROR;
2191 }
2192 break;
2193 case RHS_ALIAS_2:
2194 if( x[0]==')' ){
2195 psp->state = IN_RHS;
2196 }else{
2197 ErrorMsg(psp->filename,psp->tokenlineno,
2198 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
2199 psp->errorcnt++;
2200 psp->state = RESYNC_AFTER_RULE_ERROR;
2201 }
2202 break;
2203 case WAITING_FOR_DECL_KEYWORD:
2204 if( isalpha(x[0]) ){
2205 psp->declkeyword = x;
2206 psp->declargslot = 0;
drh4dc8ef52008-07-01 17:13:57 +00002207 psp->decllinenoslot = 0;
drha5808f32008-04-27 22:19:44 +00002208 psp->insertLineMacro = 1;
drh75897232000-05-29 14:26:00 +00002209 psp->state = WAITING_FOR_DECL_ARG;
2210 if( strcmp(x,"name")==0 ){
2211 psp->declargslot = &(psp->gp->name);
drha5808f32008-04-27 22:19:44 +00002212 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002213 }else if( strcmp(x,"include")==0 ){
2214 psp->declargslot = &(psp->gp->include);
drh75897232000-05-29 14:26:00 +00002215 }else if( strcmp(x,"code")==0 ){
2216 psp->declargslot = &(psp->gp->extracode);
drh75897232000-05-29 14:26:00 +00002217 }else if( strcmp(x,"token_destructor")==0 ){
2218 psp->declargslot = &psp->gp->tokendest;
drh960e8c62001-04-03 16:53:21 +00002219 }else if( strcmp(x,"default_destructor")==0 ){
2220 psp->declargslot = &psp->gp->vardest;
drh75897232000-05-29 14:26:00 +00002221 }else if( strcmp(x,"token_prefix")==0 ){
2222 psp->declargslot = &psp->gp->tokenprefix;
drha5808f32008-04-27 22:19:44 +00002223 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002224 }else if( strcmp(x,"syntax_error")==0 ){
2225 psp->declargslot = &(psp->gp->error);
drh75897232000-05-29 14:26:00 +00002226 }else if( strcmp(x,"parse_accept")==0 ){
2227 psp->declargslot = &(psp->gp->accept);
drh75897232000-05-29 14:26:00 +00002228 }else if( strcmp(x,"parse_failure")==0 ){
2229 psp->declargslot = &(psp->gp->failure);
drh75897232000-05-29 14:26:00 +00002230 }else if( strcmp(x,"stack_overflow")==0 ){
2231 psp->declargslot = &(psp->gp->overflow);
drh75897232000-05-29 14:26:00 +00002232 }else if( strcmp(x,"extra_argument")==0 ){
2233 psp->declargslot = &(psp->gp->arg);
drha5808f32008-04-27 22:19:44 +00002234 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002235 }else if( strcmp(x,"token_type")==0 ){
2236 psp->declargslot = &(psp->gp->tokentype);
drha5808f32008-04-27 22:19:44 +00002237 psp->insertLineMacro = 0;
drh960e8c62001-04-03 16:53:21 +00002238 }else if( strcmp(x,"default_type")==0 ){
2239 psp->declargslot = &(psp->gp->vartype);
drha5808f32008-04-27 22:19:44 +00002240 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002241 }else if( strcmp(x,"stack_size")==0 ){
2242 psp->declargslot = &(psp->gp->stacksize);
drha5808f32008-04-27 22:19:44 +00002243 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002244 }else if( strcmp(x,"start_symbol")==0 ){
2245 psp->declargslot = &(psp->gp->start);
drha5808f32008-04-27 22:19:44 +00002246 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002247 }else if( strcmp(x,"left")==0 ){
2248 psp->preccounter++;
2249 psp->declassoc = LEFT;
2250 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2251 }else if( strcmp(x,"right")==0 ){
2252 psp->preccounter++;
2253 psp->declassoc = RIGHT;
2254 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2255 }else if( strcmp(x,"nonassoc")==0 ){
2256 psp->preccounter++;
2257 psp->declassoc = NONE;
2258 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
2259 }else if( strcmp(x,"destructor")==0 ){
2260 psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;
2261 }else if( strcmp(x,"type")==0 ){
2262 psp->state = WAITING_FOR_DATATYPE_SYMBOL;
drh0bd1f4e2002-06-06 18:54:39 +00002263 }else if( strcmp(x,"fallback")==0 ){
2264 psp->fallback = 0;
2265 psp->state = WAITING_FOR_FALLBACK_ID;
drhe09daa92006-06-10 13:29:31 +00002266 }else if( strcmp(x,"wildcard")==0 ){
2267 psp->state = WAITING_FOR_WILDCARD_ID;
drh75897232000-05-29 14:26:00 +00002268 }else{
2269 ErrorMsg(psp->filename,psp->tokenlineno,
2270 "Unknown declaration keyword: \"%%%s\".",x);
2271 psp->errorcnt++;
2272 psp->state = RESYNC_AFTER_DECL_ERROR;
2273 }
2274 }else{
2275 ErrorMsg(psp->filename,psp->tokenlineno,
2276 "Illegal declaration keyword: \"%s\".",x);
2277 psp->errorcnt++;
2278 psp->state = RESYNC_AFTER_DECL_ERROR;
2279 }
2280 break;
2281 case WAITING_FOR_DESTRUCTOR_SYMBOL:
2282 if( !isalpha(x[0]) ){
2283 ErrorMsg(psp->filename,psp->tokenlineno,
2284 "Symbol name missing after %destructor keyword");
2285 psp->errorcnt++;
2286 psp->state = RESYNC_AFTER_DECL_ERROR;
2287 }else{
2288 struct symbol *sp = Symbol_new(x);
2289 psp->declargslot = &sp->destructor;
drh4dc8ef52008-07-01 17:13:57 +00002290 psp->decllinenoslot = &sp->destLineno;
drha5808f32008-04-27 22:19:44 +00002291 psp->insertLineMacro = 1;
drh75897232000-05-29 14:26:00 +00002292 psp->state = WAITING_FOR_DECL_ARG;
2293 }
2294 break;
2295 case WAITING_FOR_DATATYPE_SYMBOL:
2296 if( !isalpha(x[0]) ){
2297 ErrorMsg(psp->filename,psp->tokenlineno,
2298 "Symbol name missing after %destructor keyword");
2299 psp->errorcnt++;
2300 psp->state = RESYNC_AFTER_DECL_ERROR;
2301 }else{
2302 struct symbol *sp = Symbol_new(x);
2303 psp->declargslot = &sp->datatype;
drha5808f32008-04-27 22:19:44 +00002304 psp->insertLineMacro = 0;
drh75897232000-05-29 14:26:00 +00002305 psp->state = WAITING_FOR_DECL_ARG;
2306 }
2307 break;
2308 case WAITING_FOR_PRECEDENCE_SYMBOL:
2309 if( x[0]=='.' ){
2310 psp->state = WAITING_FOR_DECL_OR_RULE;
2311 }else if( isupper(x[0]) ){
2312 struct symbol *sp;
2313 sp = Symbol_new(x);
2314 if( sp->prec>=0 ){
2315 ErrorMsg(psp->filename,psp->tokenlineno,
2316 "Symbol \"%s\" has already be given a precedence.",x);
2317 psp->errorcnt++;
2318 }else{
2319 sp->prec = psp->preccounter;
2320 sp->assoc = psp->declassoc;
2321 }
2322 }else{
2323 ErrorMsg(psp->filename,psp->tokenlineno,
2324 "Can't assign a precedence to \"%s\".",x);
2325 psp->errorcnt++;
2326 }
2327 break;
2328 case WAITING_FOR_DECL_ARG:
drha5808f32008-04-27 22:19:44 +00002329 if( x[0]=='{' || x[0]=='\"' || isalnum(x[0]) ){
icculus9e44cf12010-02-14 17:14:22 +00002330 const char *zOld, *zNew;
2331 char *zBuf, *z;
drha5808f32008-04-27 22:19:44 +00002332 int nOld, n, nLine, nNew, nBack;
drhb5bd49e2008-07-14 12:21:08 +00002333 int addLineMacro;
drha5808f32008-04-27 22:19:44 +00002334 char zLine[50];
2335 zNew = x;
2336 if( zNew[0]=='"' || zNew[0]=='{' ) zNew++;
drh87cf1372008-08-13 20:09:06 +00002337 nNew = lemonStrlen(zNew);
drha5808f32008-04-27 22:19:44 +00002338 if( *psp->declargslot ){
2339 zOld = *psp->declargslot;
2340 }else{
2341 zOld = "";
2342 }
drh87cf1372008-08-13 20:09:06 +00002343 nOld = lemonStrlen(zOld);
drha5808f32008-04-27 22:19:44 +00002344 n = nOld + nNew + 20;
shane58543932008-12-10 20:10:04 +00002345 addLineMacro = !psp->gp->nolinenosflag && psp->insertLineMacro &&
drhb5bd49e2008-07-14 12:21:08 +00002346 (psp->decllinenoslot==0 || psp->decllinenoslot[0]!=0);
2347 if( addLineMacro ){
drha5808f32008-04-27 22:19:44 +00002348 for(z=psp->filename, nBack=0; *z; z++){
2349 if( *z=='\\' ) nBack++;
2350 }
2351 sprintf(zLine, "#line %d ", psp->tokenlineno);
drh87cf1372008-08-13 20:09:06 +00002352 nLine = lemonStrlen(zLine);
2353 n += nLine + lemonStrlen(psp->filename) + nBack;
drha5808f32008-04-27 22:19:44 +00002354 }
icculus9e44cf12010-02-14 17:14:22 +00002355 *psp->declargslot = (char *) realloc(*psp->declargslot, n);
2356 zBuf = *psp->declargslot + nOld;
drhb5bd49e2008-07-14 12:21:08 +00002357 if( addLineMacro ){
drha5808f32008-04-27 22:19:44 +00002358 if( nOld && zBuf[-1]!='\n' ){
2359 *(zBuf++) = '\n';
2360 }
2361 memcpy(zBuf, zLine, nLine);
2362 zBuf += nLine;
2363 *(zBuf++) = '"';
2364 for(z=psp->filename; *z; z++){
2365 if( *z=='\\' ){
2366 *(zBuf++) = '\\';
2367 }
2368 *(zBuf++) = *z;
2369 }
2370 *(zBuf++) = '"';
2371 *(zBuf++) = '\n';
2372 }
drh4dc8ef52008-07-01 17:13:57 +00002373 if( psp->decllinenoslot && psp->decllinenoslot[0]==0 ){
2374 psp->decllinenoslot[0] = psp->tokenlineno;
2375 }
drha5808f32008-04-27 22:19:44 +00002376 memcpy(zBuf, zNew, nNew);
2377 zBuf += nNew;
2378 *zBuf = 0;
2379 psp->state = WAITING_FOR_DECL_OR_RULE;
drh75897232000-05-29 14:26:00 +00002380 }else{
2381 ErrorMsg(psp->filename,psp->tokenlineno,
2382 "Illegal argument to %%%s: %s",psp->declkeyword,x);
2383 psp->errorcnt++;
2384 psp->state = RESYNC_AFTER_DECL_ERROR;
2385 }
2386 break;
drh0bd1f4e2002-06-06 18:54:39 +00002387 case WAITING_FOR_FALLBACK_ID:
2388 if( x[0]=='.' ){
2389 psp->state = WAITING_FOR_DECL_OR_RULE;
2390 }else if( !isupper(x[0]) ){
2391 ErrorMsg(psp->filename, psp->tokenlineno,
2392 "%%fallback argument \"%s\" should be a token", x);
2393 psp->errorcnt++;
2394 }else{
2395 struct symbol *sp = Symbol_new(x);
2396 if( psp->fallback==0 ){
2397 psp->fallback = sp;
2398 }else if( sp->fallback ){
2399 ErrorMsg(psp->filename, psp->tokenlineno,
2400 "More than one fallback assigned to token %s", x);
2401 psp->errorcnt++;
2402 }else{
2403 sp->fallback = psp->fallback;
2404 psp->gp->has_fallback = 1;
2405 }
2406 }
2407 break;
drhe09daa92006-06-10 13:29:31 +00002408 case WAITING_FOR_WILDCARD_ID:
2409 if( x[0]=='.' ){
2410 psp->state = WAITING_FOR_DECL_OR_RULE;
2411 }else if( !isupper(x[0]) ){
2412 ErrorMsg(psp->filename, psp->tokenlineno,
2413 "%%wildcard argument \"%s\" should be a token", x);
2414 psp->errorcnt++;
2415 }else{
2416 struct symbol *sp = Symbol_new(x);
2417 if( psp->gp->wildcard==0 ){
2418 psp->gp->wildcard = sp;
2419 }else{
2420 ErrorMsg(psp->filename, psp->tokenlineno,
2421 "Extra wildcard to token: %s", x);
2422 psp->errorcnt++;
2423 }
2424 }
2425 break;
drh75897232000-05-29 14:26:00 +00002426 case RESYNC_AFTER_RULE_ERROR:
2427/* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2428** break; */
2429 case RESYNC_AFTER_DECL_ERROR:
2430 if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
2431 if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;
2432 break;
2433 }
2434}
2435
drh34ff57b2008-07-14 12:27:51 +00002436/* Run the preprocessor over the input file text. The global variables
drh6d08b4d2004-07-20 12:45:22 +00002437** azDefine[0] through azDefine[nDefine-1] contains the names of all defined
2438** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and
2439** comments them out. Text in between is also commented out as appropriate.
2440*/
danielk1977940fac92005-01-23 22:41:37 +00002441static void preprocess_input(char *z){
drh6d08b4d2004-07-20 12:45:22 +00002442 int i, j, k, n;
2443 int exclude = 0;
rse38514a92007-09-20 11:34:17 +00002444 int start = 0;
drh6d08b4d2004-07-20 12:45:22 +00002445 int lineno = 1;
rse38514a92007-09-20 11:34:17 +00002446 int start_lineno = 1;
drh6d08b4d2004-07-20 12:45:22 +00002447 for(i=0; z[i]; i++){
2448 if( z[i]=='\n' ) lineno++;
2449 if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue;
2450 if( strncmp(&z[i],"%endif",6)==0 && isspace(z[i+6]) ){
2451 if( exclude ){
2452 exclude--;
2453 if( exclude==0 ){
2454 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';
2455 }
2456 }
2457 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2458 }else if( (strncmp(&z[i],"%ifdef",6)==0 && isspace(z[i+6]))
2459 || (strncmp(&z[i],"%ifndef",7)==0 && isspace(z[i+7])) ){
2460 if( exclude ){
2461 exclude++;
2462 }else{
2463 for(j=i+7; isspace(z[j]); j++){}
2464 for(n=0; z[j+n] && !isspace(z[j+n]); n++){}
2465 exclude = 1;
2466 for(k=0; k<nDefine; k++){
drh87cf1372008-08-13 20:09:06 +00002467 if( strncmp(azDefine[k],&z[j],n)==0 && lemonStrlen(azDefine[k])==n ){
drh6d08b4d2004-07-20 12:45:22 +00002468 exclude = 0;
2469 break;
2470 }
2471 }
2472 if( z[i+3]=='n' ) exclude = !exclude;
2473 if( exclude ){
2474 start = i;
2475 start_lineno = lineno;
2476 }
2477 }
2478 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
2479 }
2480 }
2481 if( exclude ){
2482 fprintf(stderr,"unterminated %%ifdef starting on line %d\n", start_lineno);
2483 exit(1);
2484 }
2485}
2486
drh75897232000-05-29 14:26:00 +00002487/* In spite of its name, this function is really a scanner. It read
2488** in the entire input file (all at once) then tokenizes it. Each
2489** token is passed to the function "parseonetoken" which builds all
2490** the appropriate data structures in the global state vector "gp".
2491*/
icculus9e44cf12010-02-14 17:14:22 +00002492void Parse(struct lemon *gp)
drh75897232000-05-29 14:26:00 +00002493{
2494 struct pstate ps;
2495 FILE *fp;
2496 char *filebuf;
2497 int filesize;
2498 int lineno;
2499 int c;
2500 char *cp, *nextcp;
2501 int startline = 0;
2502
rse38514a92007-09-20 11:34:17 +00002503 memset(&ps, '\0', sizeof(ps));
drh75897232000-05-29 14:26:00 +00002504 ps.gp = gp;
2505 ps.filename = gp->filename;
2506 ps.errorcnt = 0;
2507 ps.state = INITIALIZE;
2508
2509 /* Begin by reading the input file */
2510 fp = fopen(ps.filename,"rb");
2511 if( fp==0 ){
2512 ErrorMsg(ps.filename,0,"Can't open this file for reading.");
2513 gp->errorcnt++;
2514 return;
2515 }
2516 fseek(fp,0,2);
2517 filesize = ftell(fp);
2518 rewind(fp);
2519 filebuf = (char *)malloc( filesize+1 );
2520 if( filebuf==0 ){
2521 ErrorMsg(ps.filename,0,"Can't allocate %d of memory to hold this file.",
2522 filesize+1);
2523 gp->errorcnt++;
2524 return;
2525 }
2526 if( fread(filebuf,1,filesize,fp)!=filesize ){
2527 ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",
2528 filesize);
2529 free(filebuf);
2530 gp->errorcnt++;
2531 return;
2532 }
2533 fclose(fp);
2534 filebuf[filesize] = 0;
2535
drh6d08b4d2004-07-20 12:45:22 +00002536 /* Make an initial pass through the file to handle %ifdef and %ifndef */
2537 preprocess_input(filebuf);
2538
drh75897232000-05-29 14:26:00 +00002539 /* Now scan the text of the input file */
2540 lineno = 1;
2541 for(cp=filebuf; (c= *cp)!=0; ){
2542 if( c=='\n' ) lineno++; /* Keep track of the line number */
2543 if( isspace(c) ){ cp++; continue; } /* Skip all white space */
2544 if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments */
2545 cp+=2;
2546 while( (c= *cp)!=0 && c!='\n' ) cp++;
2547 continue;
2548 }
2549 if( c=='/' && cp[1]=='*' ){ /* Skip C style comments */
2550 cp+=2;
2551 while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){
2552 if( c=='\n' ) lineno++;
2553 cp++;
2554 }
2555 if( c ) cp++;
2556 continue;
2557 }
2558 ps.tokenstart = cp; /* Mark the beginning of the token */
2559 ps.tokenlineno = lineno; /* Linenumber on which token begins */
2560 if( c=='\"' ){ /* String literals */
2561 cp++;
2562 while( (c= *cp)!=0 && c!='\"' ){
2563 if( c=='\n' ) lineno++;
2564 cp++;
2565 }
2566 if( c==0 ){
2567 ErrorMsg(ps.filename,startline,
2568"String starting on this line is not terminated before the end of the file.");
2569 ps.errorcnt++;
2570 nextcp = cp;
2571 }else{
2572 nextcp = cp+1;
2573 }
2574 }else if( c=='{' ){ /* A block of C code */
2575 int level;
2576 cp++;
2577 for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){
2578 if( c=='\n' ) lineno++;
2579 else if( c=='{' ) level++;
2580 else if( c=='}' ) level--;
2581 else if( c=='/' && cp[1]=='*' ){ /* Skip comments */
2582 int prevc;
2583 cp = &cp[2];
2584 prevc = 0;
2585 while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){
2586 if( c=='\n' ) lineno++;
2587 prevc = c;
2588 cp++;
2589 }
2590 }else if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments too */
2591 cp = &cp[2];
2592 while( (c= *cp)!=0 && c!='\n' ) cp++;
2593 if( c ) lineno++;
2594 }else if( c=='\'' || c=='\"' ){ /* String a character literals */
2595 int startchar, prevc;
2596 startchar = c;
2597 prevc = 0;
2598 for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){
2599 if( c=='\n' ) lineno++;
2600 if( prevc=='\\' ) prevc = 0;
2601 else prevc = c;
2602 }
2603 }
2604 }
2605 if( c==0 ){
drh960e8c62001-04-03 16:53:21 +00002606 ErrorMsg(ps.filename,ps.tokenlineno,
drh75897232000-05-29 14:26:00 +00002607"C code starting on this line is not terminated before the end of the file.");
2608 ps.errorcnt++;
2609 nextcp = cp;
2610 }else{
2611 nextcp = cp+1;
2612 }
2613 }else if( isalnum(c) ){ /* Identifiers */
2614 while( (c= *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2615 nextcp = cp;
2616 }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */
2617 cp += 3;
2618 nextcp = cp;
drhfd405312005-11-06 04:06:59 +00002619 }else if( (c=='/' || c=='|') && isalpha(cp[1]) ){
2620 cp += 2;
2621 while( (c = *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
2622 nextcp = cp;
drh75897232000-05-29 14:26:00 +00002623 }else{ /* All other (one character) operators */
2624 cp++;
2625 nextcp = cp;
2626 }
2627 c = *cp;
2628 *cp = 0; /* Null terminate the token */
2629 parseonetoken(&ps); /* Parse the token */
2630 *cp = c; /* Restore the buffer */
2631 cp = nextcp;
2632 }
2633 free(filebuf); /* Release the buffer after parsing */
2634 gp->rule = ps.firstrule;
2635 gp->errorcnt = ps.errorcnt;
2636}
2637/*************************** From the file "plink.c" *********************/
2638/*
2639** Routines processing configuration follow-set propagation links
2640** in the LEMON parser generator.
2641*/
2642static struct plink *plink_freelist = 0;
2643
2644/* Allocate a new plink */
2645struct plink *Plink_new(){
icculus9e44cf12010-02-14 17:14:22 +00002646 struct plink *newlink;
drh75897232000-05-29 14:26:00 +00002647
2648 if( plink_freelist==0 ){
2649 int i;
2650 int amt = 100;
drh9892c5d2007-12-21 00:02:11 +00002651 plink_freelist = (struct plink *)calloc( amt, sizeof(struct plink) );
drh75897232000-05-29 14:26:00 +00002652 if( plink_freelist==0 ){
2653 fprintf(stderr,
2654 "Unable to allocate memory for a new follow-set propagation link.\n");
2655 exit(1);
2656 }
2657 for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
2658 plink_freelist[amt-1].next = 0;
2659 }
icculus9e44cf12010-02-14 17:14:22 +00002660 newlink = plink_freelist;
drh75897232000-05-29 14:26:00 +00002661 plink_freelist = plink_freelist->next;
icculus9e44cf12010-02-14 17:14:22 +00002662 return newlink;
drh75897232000-05-29 14:26:00 +00002663}
2664
2665/* Add a plink to a plink list */
icculus9e44cf12010-02-14 17:14:22 +00002666void Plink_add(struct plink **plpp, struct config *cfp)
drh75897232000-05-29 14:26:00 +00002667{
icculus9e44cf12010-02-14 17:14:22 +00002668 struct plink *newlink;
2669 newlink = Plink_new();
2670 newlink->next = *plpp;
2671 *plpp = newlink;
2672 newlink->cfp = cfp;
drh75897232000-05-29 14:26:00 +00002673}
2674
2675/* Transfer every plink on the list "from" to the list "to" */
icculus9e44cf12010-02-14 17:14:22 +00002676void Plink_copy(struct plink **to, struct plink *from)
drh75897232000-05-29 14:26:00 +00002677{
2678 struct plink *nextpl;
2679 while( from ){
2680 nextpl = from->next;
2681 from->next = *to;
2682 *to = from;
2683 from = nextpl;
2684 }
2685}
2686
2687/* Delete every plink on the list */
icculus9e44cf12010-02-14 17:14:22 +00002688void Plink_delete(struct plink *plp)
drh75897232000-05-29 14:26:00 +00002689{
2690 struct plink *nextpl;
2691
2692 while( plp ){
2693 nextpl = plp->next;
2694 plp->next = plink_freelist;
2695 plink_freelist = plp;
2696 plp = nextpl;
2697 }
2698}
2699/*********************** From the file "report.c" **************************/
2700/*
2701** Procedures for generating reports and tables in the LEMON parser generator.
2702*/
2703
2704/* Generate a filename with the given suffix. Space to hold the
2705** name comes from malloc() and must be freed by the calling
2706** function.
2707*/
icculus9e44cf12010-02-14 17:14:22 +00002708PRIVATE char *file_makename(struct lemon *lemp, const char *suffix)
drh75897232000-05-29 14:26:00 +00002709{
2710 char *name;
2711 char *cp;
2712
icculus9e44cf12010-02-14 17:14:22 +00002713 name = (char*)malloc( lemonStrlen(lemp->filename) + lemonStrlen(suffix) + 5 );
drh75897232000-05-29 14:26:00 +00002714 if( name==0 ){
2715 fprintf(stderr,"Can't allocate space for a filename.\n");
2716 exit(1);
2717 }
2718 strcpy(name,lemp->filename);
2719 cp = strrchr(name,'.');
2720 if( cp ) *cp = 0;
2721 strcat(name,suffix);
2722 return name;
2723}
2724
2725/* Open a file with a name based on the name of the input file,
2726** but with a different (specified) suffix, and return a pointer
2727** to the stream */
icculus9e44cf12010-02-14 17:14:22 +00002728PRIVATE FILE *file_open(
2729 struct lemon *lemp,
2730 const char *suffix,
2731 const char *mode
2732){
drh75897232000-05-29 14:26:00 +00002733 FILE *fp;
2734
2735 if( lemp->outname ) free(lemp->outname);
2736 lemp->outname = file_makename(lemp, suffix);
2737 fp = fopen(lemp->outname,mode);
2738 if( fp==0 && *mode=='w' ){
2739 fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
2740 lemp->errorcnt++;
2741 return 0;
2742 }
icculusf5ad8242010-02-14 05:34:42 +00002743
2744 /* Add files we create to a list, so we can delete them if we fail. This
2745 ** is to keep makefiles from getting confused. We don't include .out files,
2746 ** though: this is debug information, and you don't want it deleted if there
2747 ** was an error you need to track down.
2748 */
2749 if(( *mode=='w' ) && (strcmp(suffix, ".out") != 0)){
2750 const char **ptr = (const char **)
2751 realloc(made_files, sizeof (const char **) * (made_files_count + 1));
2752 char *fname = strdup(lemp->outname);
2753 if ((ptr == NULL) || (fname == NULL)) {
2754 free(ptr);
2755 free(fname);
2756 memory_error();
2757 }
2758 made_files = ptr;
2759 made_files[made_files_count++] = fname;
2760 }
drh75897232000-05-29 14:26:00 +00002761 return fp;
2762}
2763
2764/* Duplicate the input file without comments and without actions
2765** on rules */
icculus9e44cf12010-02-14 17:14:22 +00002766void Reprint(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00002767{
2768 struct rule *rp;
2769 struct symbol *sp;
2770 int i, j, maxlen, len, ncolumns, skip;
2771 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
2772 maxlen = 10;
2773 for(i=0; i<lemp->nsymbol; i++){
2774 sp = lemp->symbols[i];
drh87cf1372008-08-13 20:09:06 +00002775 len = lemonStrlen(sp->name);
drh75897232000-05-29 14:26:00 +00002776 if( len>maxlen ) maxlen = len;
2777 }
2778 ncolumns = 76/(maxlen+5);
2779 if( ncolumns<1 ) ncolumns = 1;
2780 skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
2781 for(i=0; i<skip; i++){
2782 printf("//");
2783 for(j=i; j<lemp->nsymbol; j+=skip){
2784 sp = lemp->symbols[j];
2785 assert( sp->index==j );
2786 printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
2787 }
2788 printf("\n");
2789 }
2790 for(rp=lemp->rule; rp; rp=rp->next){
2791 printf("%s",rp->lhs->name);
drhfd405312005-11-06 04:06:59 +00002792 /* if( rp->lhsalias ) printf("(%s)",rp->lhsalias); */
drh75897232000-05-29 14:26:00 +00002793 printf(" ::=");
2794 for(i=0; i<rp->nrhs; i++){
drhfd405312005-11-06 04:06:59 +00002795 sp = rp->rhs[i];
2796 printf(" %s", sp->name);
2797 if( sp->type==MULTITERMINAL ){
2798 for(j=1; j<sp->nsubsym; j++){
2799 printf("|%s", sp->subsym[j]->name);
2800 }
2801 }
2802 /* if( rp->rhsalias[i] ) printf("(%s)",rp->rhsalias[i]); */
drh75897232000-05-29 14:26:00 +00002803 }
2804 printf(".");
2805 if( rp->precsym ) printf(" [%s]",rp->precsym->name);
drhfd405312005-11-06 04:06:59 +00002806 /* if( rp->code ) printf("\n %s",rp->code); */
drh75897232000-05-29 14:26:00 +00002807 printf("\n");
2808 }
2809}
2810
icculus9e44cf12010-02-14 17:14:22 +00002811void ConfigPrint(FILE *fp, struct config *cfp)
drh75897232000-05-29 14:26:00 +00002812{
2813 struct rule *rp;
drhfd405312005-11-06 04:06:59 +00002814 struct symbol *sp;
2815 int i, j;
drh75897232000-05-29 14:26:00 +00002816 rp = cfp->rp;
2817 fprintf(fp,"%s ::=",rp->lhs->name);
2818 for(i=0; i<=rp->nrhs; i++){
2819 if( i==cfp->dot ) fprintf(fp," *");
2820 if( i==rp->nrhs ) break;
drhfd405312005-11-06 04:06:59 +00002821 sp = rp->rhs[i];
2822 fprintf(fp," %s", sp->name);
2823 if( sp->type==MULTITERMINAL ){
2824 for(j=1; j<sp->nsubsym; j++){
2825 fprintf(fp,"|%s",sp->subsym[j]->name);
2826 }
2827 }
drh75897232000-05-29 14:26:00 +00002828 }
2829}
2830
2831/* #define TEST */
drhfd405312005-11-06 04:06:59 +00002832#if 0
drh75897232000-05-29 14:26:00 +00002833/* Print a set */
2834PRIVATE void SetPrint(out,set,lemp)
2835FILE *out;
2836char *set;
2837struct lemon *lemp;
2838{
2839 int i;
2840 char *spacer;
2841 spacer = "";
2842 fprintf(out,"%12s[","");
2843 for(i=0; i<lemp->nterminal; i++){
2844 if( SetFind(set,i) ){
2845 fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
2846 spacer = " ";
2847 }
2848 }
2849 fprintf(out,"]\n");
2850}
2851
2852/* Print a plink chain */
2853PRIVATE void PlinkPrint(out,plp,tag)
2854FILE *out;
2855struct plink *plp;
2856char *tag;
2857{
2858 while( plp ){
drhada354d2005-11-05 15:03:59 +00002859 fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->statenum);
drh75897232000-05-29 14:26:00 +00002860 ConfigPrint(out,plp->cfp);
2861 fprintf(out,"\n");
2862 plp = plp->next;
2863 }
2864}
2865#endif
2866
2867/* Print an action to the given file descriptor. Return FALSE if
2868** nothing was actually printed.
2869*/
2870int PrintAction(struct action *ap, FILE *fp, int indent){
2871 int result = 1;
2872 switch( ap->type ){
2873 case SHIFT:
drhada354d2005-11-05 15:03:59 +00002874 fprintf(fp,"%*s shift %d",indent,ap->sp->name,ap->x.stp->statenum);
drh75897232000-05-29 14:26:00 +00002875 break;
2876 case REDUCE:
2877 fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
2878 break;
2879 case ACCEPT:
2880 fprintf(fp,"%*s accept",indent,ap->sp->name);
2881 break;
2882 case ERROR:
2883 fprintf(fp,"%*s error",indent,ap->sp->name);
2884 break;
drh9892c5d2007-12-21 00:02:11 +00002885 case SRCONFLICT:
2886 case RRCONFLICT:
drh75897232000-05-29 14:26:00 +00002887 fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
2888 indent,ap->sp->name,ap->x.rp->index);
2889 break;
drh9892c5d2007-12-21 00:02:11 +00002890 case SSCONFLICT:
2891 fprintf(fp,"%*s shift %d ** Parsing conflict **",
2892 indent,ap->sp->name,ap->x.stp->statenum);
2893 break;
drh75897232000-05-29 14:26:00 +00002894 case SH_RESOLVED:
2895 case RD_RESOLVED:
2896 case NOT_USED:
2897 result = 0;
2898 break;
2899 }
2900 return result;
2901}
2902
2903/* Generate the "y.output" log file */
icculus9e44cf12010-02-14 17:14:22 +00002904void ReportOutput(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00002905{
2906 int i;
2907 struct state *stp;
2908 struct config *cfp;
2909 struct action *ap;
2910 FILE *fp;
2911
drh2aa6ca42004-09-10 00:14:04 +00002912 fp = file_open(lemp,".out","wb");
drh75897232000-05-29 14:26:00 +00002913 if( fp==0 ) return;
drh75897232000-05-29 14:26:00 +00002914 for(i=0; i<lemp->nstate; i++){
2915 stp = lemp->sorted[i];
drhada354d2005-11-05 15:03:59 +00002916 fprintf(fp,"State %d:\n",stp->statenum);
drh75897232000-05-29 14:26:00 +00002917 if( lemp->basisflag ) cfp=stp->bp;
2918 else cfp=stp->cfp;
2919 while( cfp ){
2920 char buf[20];
2921 if( cfp->dot==cfp->rp->nrhs ){
2922 sprintf(buf,"(%d)",cfp->rp->index);
2923 fprintf(fp," %5s ",buf);
2924 }else{
2925 fprintf(fp," ");
2926 }
2927 ConfigPrint(fp,cfp);
2928 fprintf(fp,"\n");
drhfd405312005-11-06 04:06:59 +00002929#if 0
drh75897232000-05-29 14:26:00 +00002930 SetPrint(fp,cfp->fws,lemp);
2931 PlinkPrint(fp,cfp->fplp,"To ");
2932 PlinkPrint(fp,cfp->bplp,"From");
2933#endif
2934 if( lemp->basisflag ) cfp=cfp->bp;
2935 else cfp=cfp->next;
2936 }
2937 fprintf(fp,"\n");
2938 for(ap=stp->ap; ap; ap=ap->next){
2939 if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
2940 }
2941 fprintf(fp,"\n");
2942 }
drhe9278182007-07-18 18:16:29 +00002943 fprintf(fp, "----------------------------------------------------\n");
2944 fprintf(fp, "Symbols:\n");
2945 for(i=0; i<lemp->nsymbol; i++){
2946 int j;
2947 struct symbol *sp;
2948
2949 sp = lemp->symbols[i];
2950 fprintf(fp, " %3d: %s", i, sp->name);
2951 if( sp->type==NONTERMINAL ){
2952 fprintf(fp, ":");
2953 if( sp->lambda ){
2954 fprintf(fp, " <lambda>");
2955 }
2956 for(j=0; j<lemp->nterminal; j++){
2957 if( sp->firstset && SetFind(sp->firstset, j) ){
2958 fprintf(fp, " %s", lemp->symbols[j]->name);
2959 }
2960 }
2961 }
2962 fprintf(fp, "\n");
2963 }
drh75897232000-05-29 14:26:00 +00002964 fclose(fp);
2965 return;
2966}
2967
2968/* Search for the file "name" which is in the same directory as
2969** the exacutable */
icculus9e44cf12010-02-14 17:14:22 +00002970PRIVATE char *pathsearch(char *argv0, char *name, int modemask)
drh75897232000-05-29 14:26:00 +00002971{
icculus9e44cf12010-02-14 17:14:22 +00002972 const char *pathlist;
2973 char *pathbufptr;
2974 char *pathbuf;
drh75897232000-05-29 14:26:00 +00002975 char *path,*cp;
2976 char c;
drh75897232000-05-29 14:26:00 +00002977
2978#ifdef __WIN32__
2979 cp = strrchr(argv0,'\\');
2980#else
2981 cp = strrchr(argv0,'/');
2982#endif
2983 if( cp ){
2984 c = *cp;
2985 *cp = 0;
drh87cf1372008-08-13 20:09:06 +00002986 path = (char *)malloc( lemonStrlen(argv0) + lemonStrlen(name) + 2 );
drh75897232000-05-29 14:26:00 +00002987 if( path ) sprintf(path,"%s/%s",argv0,name);
2988 *cp = c;
2989 }else{
drh75897232000-05-29 14:26:00 +00002990 pathlist = getenv("PATH");
2991 if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
icculus9e44cf12010-02-14 17:14:22 +00002992 pathbuf = (char *) malloc( lemonStrlen(pathlist) + 1 );
drh87cf1372008-08-13 20:09:06 +00002993 path = (char *)malloc( lemonStrlen(pathlist)+lemonStrlen(name)+2 );
icculus9e44cf12010-02-14 17:14:22 +00002994 if( (pathbuf != 0) && (path!=0) ){
2995 pathbufptr = pathbuf;
2996 strcpy(pathbuf, pathlist);
2997 while( *pathbuf ){
2998 cp = strchr(pathbuf,':');
2999 if( cp==0 ) cp = &pathbuf[lemonStrlen(pathbuf)];
drh75897232000-05-29 14:26:00 +00003000 c = *cp;
3001 *cp = 0;
icculus9e44cf12010-02-14 17:14:22 +00003002 sprintf(path,"%s/%s",pathbuf,name);
drh75897232000-05-29 14:26:00 +00003003 *cp = c;
icculus9e44cf12010-02-14 17:14:22 +00003004 if( c==0 ) pathbuf[0] = 0;
3005 else pathbuf = &cp[1];
drh75897232000-05-29 14:26:00 +00003006 if( access(path,modemask)==0 ) break;
3007 }
icculus9e44cf12010-02-14 17:14:22 +00003008 free(pathbufptr);
drh75897232000-05-29 14:26:00 +00003009 }
3010 }
3011 return path;
3012}
3013
3014/* Given an action, compute the integer value for that action
3015** which is to be put in the action table of the generated machine.
3016** Return negative if no action should be generated.
3017*/
icculus9e44cf12010-02-14 17:14:22 +00003018PRIVATE int compute_action(struct lemon *lemp, struct action *ap)
drh75897232000-05-29 14:26:00 +00003019{
3020 int act;
3021 switch( ap->type ){
drhada354d2005-11-05 15:03:59 +00003022 case SHIFT: act = ap->x.stp->statenum; break;
drh75897232000-05-29 14:26:00 +00003023 case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
3024 case ERROR: act = lemp->nstate + lemp->nrule; break;
3025 case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break;
3026 default: act = -1; break;
3027 }
3028 return act;
3029}
3030
3031#define LINESIZE 1000
3032/* The next cluster of routines are for reading the template file
3033** and writing the results to the generated parser */
3034/* The first function transfers data from "in" to "out" until
3035** a line is seen which begins with "%%". The line number is
3036** tracked.
3037**
3038** if name!=0, then any word that begin with "Parse" is changed to
3039** begin with *name instead.
3040*/
icculus9e44cf12010-02-14 17:14:22 +00003041PRIVATE void tplt_xfer(char *name, FILE *in, FILE *out, int *lineno)
drh75897232000-05-29 14:26:00 +00003042{
3043 int i, iStart;
3044 char line[LINESIZE];
3045 while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
3046 (*lineno)++;
3047 iStart = 0;
3048 if( name ){
3049 for(i=0; line[i]; i++){
3050 if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0
3051 && (i==0 || !isalpha(line[i-1]))
3052 ){
3053 if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);
3054 fprintf(out,"%s",name);
3055 i += 4;
3056 iStart = i+1;
3057 }
3058 }
3059 }
3060 fprintf(out,"%s",&line[iStart]);
3061 }
3062}
3063
3064/* The next function finds the template file and opens it, returning
3065** a pointer to the opened file. */
icculus9e44cf12010-02-14 17:14:22 +00003066PRIVATE FILE *tplt_open(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00003067{
3068 static char templatename[] = "lempar.c";
3069 char buf[1000];
3070 FILE *in;
3071 char *tpltname;
3072 char *cp;
3073
icculus3e143bd2010-02-14 00:48:49 +00003074 /* first, see if user specified a template filename on the command line. */
3075 if (user_templatename != 0) {
3076 if( access(user_templatename,004)==-1 ){
3077 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3078 user_templatename);
3079 lemp->errorcnt++;
3080 return 0;
3081 }
3082 in = fopen(user_templatename,"rb");
3083 if( in==0 ){
3084 fprintf(stderr,"Can't open the template file \"%s\".\n",user_templatename);
3085 lemp->errorcnt++;
3086 return 0;
3087 }
3088 return in;
3089 }
3090
drh75897232000-05-29 14:26:00 +00003091 cp = strrchr(lemp->filename,'.');
3092 if( cp ){
drh8b582012003-10-21 13:16:03 +00003093 sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
drh75897232000-05-29 14:26:00 +00003094 }else{
3095 sprintf(buf,"%s.lt",lemp->filename);
3096 }
3097 if( access(buf,004)==0 ){
3098 tpltname = buf;
drh960e8c62001-04-03 16:53:21 +00003099 }else if( access(templatename,004)==0 ){
3100 tpltname = templatename;
drh75897232000-05-29 14:26:00 +00003101 }else{
3102 tpltname = pathsearch(lemp->argv0,templatename,0);
3103 }
3104 if( tpltname==0 ){
3105 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
3106 templatename);
3107 lemp->errorcnt++;
3108 return 0;
3109 }
drh2aa6ca42004-09-10 00:14:04 +00003110 in = fopen(tpltname,"rb");
drh75897232000-05-29 14:26:00 +00003111 if( in==0 ){
3112 fprintf(stderr,"Can't open the template file \"%s\".\n",templatename);
3113 lemp->errorcnt++;
3114 return 0;
3115 }
3116 return in;
3117}
3118
drhaf805ca2004-09-07 11:28:25 +00003119/* Print a #line directive line to the output file. */
icculus9e44cf12010-02-14 17:14:22 +00003120PRIVATE void tplt_linedir(FILE *out, int lineno, char *filename)
drhaf805ca2004-09-07 11:28:25 +00003121{
3122 fprintf(out,"#line %d \"",lineno);
3123 while( *filename ){
3124 if( *filename == '\\' ) putc('\\',out);
3125 putc(*filename,out);
3126 filename++;
3127 }
3128 fprintf(out,"\"\n");
3129}
3130
drh75897232000-05-29 14:26:00 +00003131/* Print a string to the file and keep the linenumber up to date */
icculus9e44cf12010-02-14 17:14:22 +00003132PRIVATE void tplt_print(FILE *out, struct lemon *lemp, char *str, int *lineno)
drh75897232000-05-29 14:26:00 +00003133{
3134 if( str==0 ) return;
drh75897232000-05-29 14:26:00 +00003135 while( *str ){
drh75897232000-05-29 14:26:00 +00003136 putc(*str,out);
shane58543932008-12-10 20:10:04 +00003137 if( *str=='\n' ) (*lineno)++;
drh75897232000-05-29 14:26:00 +00003138 str++;
3139 }
drh9db55df2004-09-09 14:01:21 +00003140 if( str[-1]!='\n' ){
3141 putc('\n',out);
3142 (*lineno)++;
3143 }
shane58543932008-12-10 20:10:04 +00003144 if (!lemp->nolinenosflag) {
3145 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);
3146 }
drh75897232000-05-29 14:26:00 +00003147 return;
3148}
3149
3150/*
3151** The following routine emits code for the destructor for the
3152** symbol sp
3153*/
icculus9e44cf12010-02-14 17:14:22 +00003154void emit_destructor_code(
3155 FILE *out,
3156 struct symbol *sp,
3157 struct lemon *lemp,
3158 int *lineno
3159){
drhcc83b6e2004-04-23 23:38:42 +00003160 char *cp = 0;
drh75897232000-05-29 14:26:00 +00003161
drh75897232000-05-29 14:26:00 +00003162 if( sp->type==TERMINAL ){
3163 cp = lemp->tokendest;
3164 if( cp==0 ) return;
drha5808f32008-04-27 22:19:44 +00003165 fprintf(out,"{\n"); (*lineno)++;
drh960e8c62001-04-03 16:53:21 +00003166 }else if( sp->destructor ){
drh75897232000-05-29 14:26:00 +00003167 cp = sp->destructor;
drha5808f32008-04-27 22:19:44 +00003168 fprintf(out,"{\n"); (*lineno)++;
shane58543932008-12-10 20:10:04 +00003169 if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,sp->destLineno,lemp->filename); }
drh960e8c62001-04-03 16:53:21 +00003170 }else if( lemp->vardest ){
3171 cp = lemp->vardest;
3172 if( cp==0 ) return;
drha5808f32008-04-27 22:19:44 +00003173 fprintf(out,"{\n"); (*lineno)++;
drhcc83b6e2004-04-23 23:38:42 +00003174 }else{
3175 assert( 0 ); /* Cannot happen */
drh75897232000-05-29 14:26:00 +00003176 }
3177 for(; *cp; cp++){
3178 if( *cp=='$' && cp[1]=='$' ){
3179 fprintf(out,"(yypminor->yy%d)",sp->dtnum);
3180 cp++;
3181 continue;
3182 }
shane58543932008-12-10 20:10:04 +00003183 if( *cp=='\n' ) (*lineno)++;
drh75897232000-05-29 14:26:00 +00003184 fputc(*cp,out);
3185 }
shane58543932008-12-10 20:10:04 +00003186 fprintf(out,"\n"); (*lineno)++;
3187 if (!lemp->nolinenosflag) {
3188 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);
3189 }
3190 fprintf(out,"}\n"); (*lineno)++;
drh75897232000-05-29 14:26:00 +00003191 return;
3192}
3193
3194/*
drh960e8c62001-04-03 16:53:21 +00003195** Return TRUE (non-zero) if the given symbol has a destructor.
drh75897232000-05-29 14:26:00 +00003196*/
icculus9e44cf12010-02-14 17:14:22 +00003197int has_destructor(struct symbol *sp, struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00003198{
3199 int ret;
3200 if( sp->type==TERMINAL ){
3201 ret = lemp->tokendest!=0;
3202 }else{
drh960e8c62001-04-03 16:53:21 +00003203 ret = lemp->vardest!=0 || sp->destructor!=0;
drh75897232000-05-29 14:26:00 +00003204 }
3205 return ret;
3206}
3207
drh0bb132b2004-07-20 14:06:51 +00003208/*
3209** Append text to a dynamically allocated string. If zText is 0 then
3210** reset the string to be empty again. Always return the complete text
3211** of the string (which is overwritten with each call).
drh7ac25c72004-08-19 15:12:26 +00003212**
3213** n bytes of zText are stored. If n==0 then all of zText up to the first
3214** \000 terminator is stored. zText can contain up to two instances of
3215** %d. The values of p1 and p2 are written into the first and second
3216** %d.
3217**
3218** If n==-1, then the previous character is overwritten.
drh0bb132b2004-07-20 14:06:51 +00003219*/
icculus9e44cf12010-02-14 17:14:22 +00003220PRIVATE char *append_str(const char *zText, int n, int p1, int p2){
3221 static char empty[1] = { 0 };
drh0bb132b2004-07-20 14:06:51 +00003222 static char *z = 0;
3223 static int alloced = 0;
3224 static int used = 0;
drhaf805ca2004-09-07 11:28:25 +00003225 int c;
drh0bb132b2004-07-20 14:06:51 +00003226 char zInt[40];
drh0bb132b2004-07-20 14:06:51 +00003227 if( zText==0 ){
3228 used = 0;
3229 return z;
3230 }
drh7ac25c72004-08-19 15:12:26 +00003231 if( n<=0 ){
3232 if( n<0 ){
3233 used += n;
3234 assert( used>=0 );
3235 }
drh87cf1372008-08-13 20:09:06 +00003236 n = lemonStrlen(zText);
drh7ac25c72004-08-19 15:12:26 +00003237 }
drh0bb132b2004-07-20 14:06:51 +00003238 if( n+sizeof(zInt)*2+used >= alloced ){
3239 alloced = n + sizeof(zInt)*2 + used + 200;
icculus9e44cf12010-02-14 17:14:22 +00003240 z = (char *) realloc(z, alloced);
drh0bb132b2004-07-20 14:06:51 +00003241 }
icculus9e44cf12010-02-14 17:14:22 +00003242 if( z==0 ) return empty;
drh0bb132b2004-07-20 14:06:51 +00003243 while( n-- > 0 ){
3244 c = *(zText++);
drh50489622006-10-13 12:25:29 +00003245 if( c=='%' && n>0 && zText[0]=='d' ){
drh0bb132b2004-07-20 14:06:51 +00003246 sprintf(zInt, "%d", p1);
3247 p1 = p2;
3248 strcpy(&z[used], zInt);
drh87cf1372008-08-13 20:09:06 +00003249 used += lemonStrlen(&z[used]);
drh0bb132b2004-07-20 14:06:51 +00003250 zText++;
3251 n--;
3252 }else{
3253 z[used++] = c;
3254 }
3255 }
3256 z[used] = 0;
3257 return z;
3258}
3259
3260/*
3261** zCode is a string that is the action associated with a rule. Expand
3262** the symbols in this string so that the refer to elements of the parser
drhaf805ca2004-09-07 11:28:25 +00003263** stack.
drh0bb132b2004-07-20 14:06:51 +00003264*/
drhaf805ca2004-09-07 11:28:25 +00003265PRIVATE void translate_code(struct lemon *lemp, struct rule *rp){
drh0bb132b2004-07-20 14:06:51 +00003266 char *cp, *xp;
3267 int i;
3268 char lhsused = 0; /* True if the LHS element has been used */
3269 char used[MAXRHS]; /* True for each RHS element which is used */
3270
3271 for(i=0; i<rp->nrhs; i++) used[i] = 0;
3272 lhsused = 0;
3273
drh19c9e562007-03-29 20:13:53 +00003274 if( rp->code==0 ){
icculus9e44cf12010-02-14 17:14:22 +00003275 static char newlinestr[2] = { '\n', '\0' };
3276 rp->code = newlinestr;
drh19c9e562007-03-29 20:13:53 +00003277 rp->line = rp->ruleline;
3278 }
3279
drh0bb132b2004-07-20 14:06:51 +00003280 append_str(0,0,0,0);
icculus9e44cf12010-02-14 17:14:22 +00003281
3282 /* This const cast is wrong but harmless, if we're careful. */
3283 for(cp=(char *)rp->code; *cp; cp++){
drh0bb132b2004-07-20 14:06:51 +00003284 if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
3285 char saved;
3286 for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
3287 saved = *xp;
3288 *xp = 0;
3289 if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
drh7ac25c72004-08-19 15:12:26 +00003290 append_str("yygotominor.yy%d",0,rp->lhs->dtnum,0);
drh0bb132b2004-07-20 14:06:51 +00003291 cp = xp;
3292 lhsused = 1;
3293 }else{
3294 for(i=0; i<rp->nrhs; i++){
3295 if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
drh7ac25c72004-08-19 15:12:26 +00003296 if( cp!=rp->code && cp[-1]=='@' ){
3297 /* If the argument is of the form @X then substituted
3298 ** the token number of X, not the value of X */
3299 append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);
3300 }else{
drhfd405312005-11-06 04:06:59 +00003301 struct symbol *sp = rp->rhs[i];
3302 int dtnum;
3303 if( sp->type==MULTITERMINAL ){
3304 dtnum = sp->subsym[0]->dtnum;
3305 }else{
3306 dtnum = sp->dtnum;
3307 }
3308 append_str("yymsp[%d].minor.yy%d",0,i-rp->nrhs+1, dtnum);
drh7ac25c72004-08-19 15:12:26 +00003309 }
drh0bb132b2004-07-20 14:06:51 +00003310 cp = xp;
3311 used[i] = 1;
3312 break;
3313 }
3314 }
3315 }
3316 *xp = saved;
3317 }
3318 append_str(cp, 1, 0, 0);
3319 } /* End loop */
3320
3321 /* Check to make sure the LHS has been used */
3322 if( rp->lhsalias && !lhsused ){
3323 ErrorMsg(lemp->filename,rp->ruleline,
3324 "Label \"%s\" for \"%s(%s)\" is never used.",
3325 rp->lhsalias,rp->lhs->name,rp->lhsalias);
3326 lemp->errorcnt++;
3327 }
3328
3329 /* Generate destructor code for RHS symbols which are not used in the
3330 ** reduce code */
3331 for(i=0; i<rp->nrhs; i++){
3332 if( rp->rhsalias[i] && !used[i] ){
3333 ErrorMsg(lemp->filename,rp->ruleline,
3334 "Label %s for \"%s(%s)\" is never used.",
3335 rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
3336 lemp->errorcnt++;
3337 }else if( rp->rhsalias[i]==0 ){
3338 if( has_destructor(rp->rhs[i],lemp) ){
drh639efd02008-08-13 20:04:29 +00003339 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,
drh0bb132b2004-07-20 14:06:51 +00003340 rp->rhs[i]->index,i-rp->nrhs+1);
3341 }else{
3342 /* No destructor defined for this term */
3343 }
3344 }
3345 }
drh61e339a2007-01-16 03:09:02 +00003346 if( rp->code ){
3347 cp = append_str(0,0,0,0);
3348 rp->code = Strsafe(cp?cp:"");
3349 }
drh0bb132b2004-07-20 14:06:51 +00003350}
3351
drh75897232000-05-29 14:26:00 +00003352/*
3353** Generate code which executes when the rule "rp" is reduced. Write
3354** the code to "out". Make sure lineno stays up-to-date.
3355*/
icculus9e44cf12010-02-14 17:14:22 +00003356PRIVATE void emit_code(
3357 FILE *out,
3358 struct rule *rp,
3359 struct lemon *lemp,
3360 int *lineno
3361){
3362 const char *cp;
drh75897232000-05-29 14:26:00 +00003363
3364 /* Generate code to do the reduce action */
3365 if( rp->code ){
shane58543932008-12-10 20:10:04 +00003366 if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,rp->line,lemp->filename); }
drhaf805ca2004-09-07 11:28:25 +00003367 fprintf(out,"{%s",rp->code);
drh75897232000-05-29 14:26:00 +00003368 for(cp=rp->code; *cp; cp++){
shane58543932008-12-10 20:10:04 +00003369 if( *cp=='\n' ) (*lineno)++;
drh75897232000-05-29 14:26:00 +00003370 } /* End loop */
shane58543932008-12-10 20:10:04 +00003371 fprintf(out,"}\n"); (*lineno)++;
3372 if (!lemp->nolinenosflag) { (*lineno)++; tplt_linedir(out,*lineno,lemp->outname); }
drh75897232000-05-29 14:26:00 +00003373 } /* End if( rp->code ) */
3374
drh75897232000-05-29 14:26:00 +00003375 return;
3376}
3377
3378/*
3379** Print the definition of the union used for the parser's data stack.
3380** This union contains fields for every possible data type for tokens
3381** and nonterminals. In the process of computing and printing this
3382** union, also set the ".dtnum" field of every terminal and nonterminal
3383** symbol.
3384*/
icculus9e44cf12010-02-14 17:14:22 +00003385void print_stack_union(
3386 FILE *out, /* The output stream */
3387 struct lemon *lemp, /* The main info structure for this parser */
3388 int *plineno, /* Pointer to the line number */
3389 int mhflag /* True if generating makeheaders output */
3390){
drh75897232000-05-29 14:26:00 +00003391 int lineno = *plineno; /* The line number of the output */
3392 char **types; /* A hash table of datatypes */
3393 int arraysize; /* Size of the "types" array */
3394 int maxdtlength; /* Maximum length of any ".datatype" field. */
3395 char *stddt; /* Standardized name for a datatype */
3396 int i,j; /* Loop counters */
3397 int hash; /* For hashing the name of a type */
icculus9e44cf12010-02-14 17:14:22 +00003398 const char *name; /* Name of the parser */
drh75897232000-05-29 14:26:00 +00003399
3400 /* Allocate and initialize types[] and allocate stddt[] */
3401 arraysize = lemp->nsymbol * 2;
drh9892c5d2007-12-21 00:02:11 +00003402 types = (char**)calloc( arraysize, sizeof(char*) );
drh75897232000-05-29 14:26:00 +00003403 for(i=0; i<arraysize; i++) types[i] = 0;
3404 maxdtlength = 0;
drh960e8c62001-04-03 16:53:21 +00003405 if( lemp->vartype ){
drh87cf1372008-08-13 20:09:06 +00003406 maxdtlength = lemonStrlen(lemp->vartype);
drh960e8c62001-04-03 16:53:21 +00003407 }
drh75897232000-05-29 14:26:00 +00003408 for(i=0; i<lemp->nsymbol; i++){
3409 int len;
3410 struct symbol *sp = lemp->symbols[i];
3411 if( sp->datatype==0 ) continue;
drh87cf1372008-08-13 20:09:06 +00003412 len = lemonStrlen(sp->datatype);
drh75897232000-05-29 14:26:00 +00003413 if( len>maxdtlength ) maxdtlength = len;
3414 }
3415 stddt = (char*)malloc( maxdtlength*2 + 1 );
3416 if( types==0 || stddt==0 ){
3417 fprintf(stderr,"Out of memory.\n");
3418 exit(1);
3419 }
3420
3421 /* Build a hash table of datatypes. The ".dtnum" field of each symbol
3422 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is
drh960e8c62001-04-03 16:53:21 +00003423 ** used for terminal symbols. If there is no %default_type defined then
3424 ** 0 is also used as the .dtnum value for nonterminals which do not specify
3425 ** a datatype using the %type directive.
3426 */
drh75897232000-05-29 14:26:00 +00003427 for(i=0; i<lemp->nsymbol; i++){
3428 struct symbol *sp = lemp->symbols[i];
3429 char *cp;
3430 if( sp==lemp->errsym ){
3431 sp->dtnum = arraysize+1;
3432 continue;
3433 }
drh960e8c62001-04-03 16:53:21 +00003434 if( sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0) ){
drh75897232000-05-29 14:26:00 +00003435 sp->dtnum = 0;
3436 continue;
3437 }
3438 cp = sp->datatype;
drh960e8c62001-04-03 16:53:21 +00003439 if( cp==0 ) cp = lemp->vartype;
drh75897232000-05-29 14:26:00 +00003440 j = 0;
3441 while( isspace(*cp) ) cp++;
3442 while( *cp ) stddt[j++] = *cp++;
3443 while( j>0 && isspace(stddt[j-1]) ) j--;
3444 stddt[j] = 0;
drh02368c92009-04-05 15:18:02 +00003445 if( lemp->tokentype && strcmp(stddt, lemp->tokentype)==0 ){
drh32c4d742008-07-01 16:34:49 +00003446 sp->dtnum = 0;
3447 continue;
3448 }
drh75897232000-05-29 14:26:00 +00003449 hash = 0;
3450 for(j=0; stddt[j]; j++){
3451 hash = hash*53 + stddt[j];
3452 }
drh3b2129c2003-05-13 00:34:21 +00003453 hash = (hash & 0x7fffffff)%arraysize;
drh75897232000-05-29 14:26:00 +00003454 while( types[hash] ){
3455 if( strcmp(types[hash],stddt)==0 ){
3456 sp->dtnum = hash + 1;
3457 break;
3458 }
3459 hash++;
3460 if( hash>=arraysize ) hash = 0;
3461 }
3462 if( types[hash]==0 ){
3463 sp->dtnum = hash + 1;
drh87cf1372008-08-13 20:09:06 +00003464 types[hash] = (char*)malloc( lemonStrlen(stddt)+1 );
drh75897232000-05-29 14:26:00 +00003465 if( types[hash]==0 ){
3466 fprintf(stderr,"Out of memory.\n");
3467 exit(1);
3468 }
3469 strcpy(types[hash],stddt);
3470 }
3471 }
3472
3473 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */
3474 name = lemp->name ? lemp->name : "Parse";
3475 lineno = *plineno;
3476 if( mhflag ){ fprintf(out,"#if INTERFACE\n"); lineno++; }
3477 fprintf(out,"#define %sTOKENTYPE %s\n",name,
3478 lemp->tokentype?lemp->tokentype:"void*"); lineno++;
3479 if( mhflag ){ fprintf(out,"#endif\n"); lineno++; }
3480 fprintf(out,"typedef union {\n"); lineno++;
drh15b024c2008-12-11 02:20:43 +00003481 fprintf(out," int yyinit;\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003482 fprintf(out," %sTOKENTYPE yy0;\n",name); lineno++;
3483 for(i=0; i<arraysize; i++){
3484 if( types[i]==0 ) continue;
3485 fprintf(out," %s yy%d;\n",types[i],i+1); lineno++;
3486 free(types[i]);
3487 }
drhc4dd3fd2008-01-22 01:48:05 +00003488 if( lemp->errsym->useCnt ){
3489 fprintf(out," int yy%d;\n",lemp->errsym->dtnum); lineno++;
3490 }
drh75897232000-05-29 14:26:00 +00003491 free(stddt);
3492 free(types);
3493 fprintf(out,"} YYMINORTYPE;\n"); lineno++;
3494 *plineno = lineno;
3495}
3496
drhb29b0a52002-02-23 19:39:46 +00003497/*
3498** Return the name of a C datatype able to represent values between
drh8b582012003-10-21 13:16:03 +00003499** lwr and upr, inclusive.
drhb29b0a52002-02-23 19:39:46 +00003500*/
drh8b582012003-10-21 13:16:03 +00003501static const char *minimum_size_type(int lwr, int upr){
3502 if( lwr>=0 ){
3503 if( upr<=255 ){
3504 return "unsigned char";
3505 }else if( upr<65535 ){
3506 return "unsigned short int";
3507 }else{
3508 return "unsigned int";
3509 }
3510 }else if( lwr>=-127 && upr<=127 ){
3511 return "signed char";
3512 }else if( lwr>=-32767 && upr<32767 ){
3513 return "short";
drhb29b0a52002-02-23 19:39:46 +00003514 }else{
drh8b582012003-10-21 13:16:03 +00003515 return "int";
drhb29b0a52002-02-23 19:39:46 +00003516 }
3517}
3518
drhfdbf9282003-10-21 16:34:41 +00003519/*
3520** Each state contains a set of token transaction and a set of
3521** nonterminal transactions. Each of these sets makes an instance
3522** of the following structure. An array of these structures is used
3523** to order the creation of entries in the yy_action[] table.
3524*/
3525struct axset {
3526 struct state *stp; /* A pointer to a state */
3527 int isTkn; /* True to use tokens. False for non-terminals */
3528 int nAction; /* Number of actions */
drhe594bc32009-11-03 13:02:25 +00003529 int iOrder; /* Original order of action sets */
drhfdbf9282003-10-21 16:34:41 +00003530};
3531
3532/*
3533** Compare to axset structures for sorting purposes
3534*/
3535static int axset_compare(const void *a, const void *b){
3536 struct axset *p1 = (struct axset*)a;
3537 struct axset *p2 = (struct axset*)b;
drhe594bc32009-11-03 13:02:25 +00003538 int c;
3539 c = p2->nAction - p1->nAction;
3540 if( c==0 ){
3541 c = p2->iOrder - p1->iOrder;
3542 }
3543 assert( c!=0 || p1==p2 );
3544 return c;
drhfdbf9282003-10-21 16:34:41 +00003545}
3546
drhc4dd3fd2008-01-22 01:48:05 +00003547/*
3548** Write text on "out" that describes the rule "rp".
3549*/
3550static void writeRuleText(FILE *out, struct rule *rp){
3551 int j;
3552 fprintf(out,"%s ::=", rp->lhs->name);
3553 for(j=0; j<rp->nrhs; j++){
3554 struct symbol *sp = rp->rhs[j];
3555 fprintf(out," %s", sp->name);
3556 if( sp->type==MULTITERMINAL ){
3557 int k;
3558 for(k=1; k<sp->nsubsym; k++){
3559 fprintf(out,"|%s",sp->subsym[k]->name);
3560 }
3561 }
3562 }
3563}
3564
3565
drh75897232000-05-29 14:26:00 +00003566/* Generate C source code for the parser */
icculus9e44cf12010-02-14 17:14:22 +00003567void ReportTable(
3568 struct lemon *lemp,
3569 int mhflag /* Output in makeheaders format if true */
3570){
drh75897232000-05-29 14:26:00 +00003571 FILE *out, *in;
3572 char line[LINESIZE];
3573 int lineno;
3574 struct state *stp;
3575 struct action *ap;
3576 struct rule *rp;
drh8b582012003-10-21 13:16:03 +00003577 struct acttab *pActtab;
icculusa3191192010-02-17 05:40:34 +00003578 int i, j, n;
icculus9e44cf12010-02-14 17:14:22 +00003579 const char *name;
drh8b582012003-10-21 13:16:03 +00003580 int mnTknOfst, mxTknOfst;
3581 int mnNtOfst, mxNtOfst;
drhfdbf9282003-10-21 16:34:41 +00003582 struct axset *ax;
drh75897232000-05-29 14:26:00 +00003583
3584 in = tplt_open(lemp);
3585 if( in==0 ) return;
drh2aa6ca42004-09-10 00:14:04 +00003586 out = file_open(lemp,".c","wb");
drh75897232000-05-29 14:26:00 +00003587 if( out==0 ){
3588 fclose(in);
3589 return;
3590 }
3591 lineno = 1;
3592 tplt_xfer(lemp->name,in,out,&lineno);
3593
3594 /* Generate the include code, if any */
drha5808f32008-04-27 22:19:44 +00003595 tplt_print(out,lemp,lemp->include,&lineno);
drh75897232000-05-29 14:26:00 +00003596 if( mhflag ){
3597 char *name = file_makename(lemp, ".h");
3598 fprintf(out,"#include \"%s\"\n", name); lineno++;
3599 free(name);
3600 }
3601 tplt_xfer(lemp->name,in,out,&lineno);
3602
3603 /* Generate #defines for all tokens */
3604 if( mhflag ){
icculus9e44cf12010-02-14 17:14:22 +00003605 const char *prefix;
drh75897232000-05-29 14:26:00 +00003606 fprintf(out,"#if INTERFACE\n"); lineno++;
3607 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
3608 else prefix = "";
3609 for(i=1; i<lemp->nterminal; i++){
3610 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
3611 lineno++;
3612 }
3613 fprintf(out,"#endif\n"); lineno++;
3614 }
3615 tplt_xfer(lemp->name,in,out,&lineno);
3616
3617 /* Generate the defines */
drh75897232000-05-29 14:26:00 +00003618 fprintf(out,"#define YYCODETYPE %s\n",
drh8a415d32009-06-12 13:53:51 +00003619 minimum_size_type(0, lemp->nsymbol+1)); lineno++;
drh75897232000-05-29 14:26:00 +00003620 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++;
3621 fprintf(out,"#define YYACTIONTYPE %s\n",
drh8b582012003-10-21 13:16:03 +00003622 minimum_size_type(0, lemp->nstate+lemp->nrule+5)); lineno++;
drhe09daa92006-06-10 13:29:31 +00003623 if( lemp->wildcard ){
3624 fprintf(out,"#define YYWILDCARD %d\n",
3625 lemp->wildcard->index); lineno++;
3626 }
drh75897232000-05-29 14:26:00 +00003627 print_stack_union(out,lemp,&lineno,mhflag);
drhca44b5a2007-02-22 23:06:58 +00003628 fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003629 if( lemp->stacksize ){
drh75897232000-05-29 14:26:00 +00003630 fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize); lineno++;
3631 }else{
3632 fprintf(out,"#define YYSTACKDEPTH 100\n"); lineno++;
3633 }
drhca44b5a2007-02-22 23:06:58 +00003634 fprintf(out, "#endif\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003635 if( mhflag ){
3636 fprintf(out,"#if INTERFACE\n"); lineno++;
3637 }
3638 name = lemp->name ? lemp->name : "Parse";
3639 if( lemp->arg && lemp->arg[0] ){
3640 int i;
drh87cf1372008-08-13 20:09:06 +00003641 i = lemonStrlen(lemp->arg);
drhb1edd012000-06-02 18:52:12 +00003642 while( i>=1 && isspace(lemp->arg[i-1]) ) i--;
3643 while( i>=1 && (isalnum(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--;
drh1f245e42002-03-11 13:55:50 +00003644 fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg); lineno++;
3645 fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg); lineno++;
3646 fprintf(out,"#define %sARG_FETCH %s = yypParser->%s\n",
3647 name,lemp->arg,&lemp->arg[i]); lineno++;
3648 fprintf(out,"#define %sARG_STORE yypParser->%s = %s\n",
3649 name,&lemp->arg[i],&lemp->arg[i]); lineno++;
drh75897232000-05-29 14:26:00 +00003650 }else{
drh1f245e42002-03-11 13:55:50 +00003651 fprintf(out,"#define %sARG_SDECL\n",name); lineno++;
3652 fprintf(out,"#define %sARG_PDECL\n",name); lineno++;
3653 fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
3654 fprintf(out,"#define %sARG_STORE\n",name); lineno++;
drh75897232000-05-29 14:26:00 +00003655 }
3656 if( mhflag ){
3657 fprintf(out,"#endif\n"); lineno++;
3658 }
3659 fprintf(out,"#define YYNSTATE %d\n",lemp->nstate); lineno++;
3660 fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++;
drhc4dd3fd2008-01-22 01:48:05 +00003661 if( lemp->errsym->useCnt ){
3662 fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;
3663 fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;
3664 }
drh0bd1f4e2002-06-06 18:54:39 +00003665 if( lemp->has_fallback ){
3666 fprintf(out,"#define YYFALLBACK 1\n"); lineno++;
3667 }
drh75897232000-05-29 14:26:00 +00003668 tplt_xfer(lemp->name,in,out,&lineno);
3669
drh8b582012003-10-21 13:16:03 +00003670 /* Generate the action table and its associates:
drh75897232000-05-29 14:26:00 +00003671 **
drh8b582012003-10-21 13:16:03 +00003672 ** yy_action[] A single table containing all actions.
3673 ** yy_lookahead[] A table containing the lookahead for each entry in
3674 ** yy_action. Used to detect hash collisions.
3675 ** yy_shift_ofst[] For each state, the offset into yy_action for
3676 ** shifting terminals.
3677 ** yy_reduce_ofst[] For each state, the offset into yy_action for
3678 ** shifting non-terminals after a reduce.
3679 ** yy_default[] Default action for each state.
drh75897232000-05-29 14:26:00 +00003680 */
drh75897232000-05-29 14:26:00 +00003681
drh8b582012003-10-21 13:16:03 +00003682 /* Compute the actions on all states and count them up */
icculus9e44cf12010-02-14 17:14:22 +00003683 ax = (struct axset *) calloc(lemp->nstate*2, sizeof(ax[0]));
drhfdbf9282003-10-21 16:34:41 +00003684 if( ax==0 ){
3685 fprintf(stderr,"malloc failed\n");
3686 exit(1);
3687 }
drh75897232000-05-29 14:26:00 +00003688 for(i=0; i<lemp->nstate; i++){
drh75897232000-05-29 14:26:00 +00003689 stp = lemp->sorted[i];
drhfdbf9282003-10-21 16:34:41 +00003690 ax[i*2].stp = stp;
3691 ax[i*2].isTkn = 1;
3692 ax[i*2].nAction = stp->nTknAct;
3693 ax[i*2+1].stp = stp;
3694 ax[i*2+1].isTkn = 0;
3695 ax[i*2+1].nAction = stp->nNtAct;
drh75897232000-05-29 14:26:00 +00003696 }
drh8b582012003-10-21 13:16:03 +00003697 mxTknOfst = mnTknOfst = 0;
3698 mxNtOfst = mnNtOfst = 0;
3699
drhfdbf9282003-10-21 16:34:41 +00003700 /* Compute the action table. In order to try to keep the size of the
3701 ** action table to a minimum, the heuristic of placing the largest action
3702 ** sets first is used.
drh8b582012003-10-21 13:16:03 +00003703 */
drhe594bc32009-11-03 13:02:25 +00003704 for(i=0; i<lemp->nstate*2; i++) ax[i].iOrder = i;
drhfdbf9282003-10-21 16:34:41 +00003705 qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
drh8b582012003-10-21 13:16:03 +00003706 pActtab = acttab_alloc();
drhfdbf9282003-10-21 16:34:41 +00003707 for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
3708 stp = ax[i].stp;
3709 if( ax[i].isTkn ){
3710 for(ap=stp->ap; ap; ap=ap->next){
3711 int action;
3712 if( ap->sp->index>=lemp->nterminal ) continue;
3713 action = compute_action(lemp, ap);
3714 if( action<0 ) continue;
3715 acttab_action(pActtab, ap->sp->index, action);
drh8b582012003-10-21 13:16:03 +00003716 }
drhfdbf9282003-10-21 16:34:41 +00003717 stp->iTknOfst = acttab_insert(pActtab);
3718 if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
3719 if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
3720 }else{
3721 for(ap=stp->ap; ap; ap=ap->next){
3722 int action;
3723 if( ap->sp->index<lemp->nterminal ) continue;
3724 if( ap->sp->index==lemp->nsymbol ) continue;
3725 action = compute_action(lemp, ap);
3726 if( action<0 ) continue;
3727 acttab_action(pActtab, ap->sp->index, action);
drh8b582012003-10-21 13:16:03 +00003728 }
drhfdbf9282003-10-21 16:34:41 +00003729 stp->iNtOfst = acttab_insert(pActtab);
3730 if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
3731 if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
drh8b582012003-10-21 13:16:03 +00003732 }
3733 }
drhfdbf9282003-10-21 16:34:41 +00003734 free(ax);
drh8b582012003-10-21 13:16:03 +00003735
3736 /* Output the yy_action table */
drh8b582012003-10-21 13:16:03 +00003737 n = acttab_size(pActtab);
drhf16371d2009-11-03 19:18:31 +00003738 fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;
3739 fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
drh8b582012003-10-21 13:16:03 +00003740 for(i=j=0; i<n; i++){
3741 int action = acttab_yyaction(pActtab, i);
drhe0479212007-01-12 23:09:23 +00003742 if( action<0 ) action = lemp->nstate + lemp->nrule + 2;
drhfdbf9282003-10-21 16:34:41 +00003743 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003744 fprintf(out, " %4d,", action);
3745 if( j==9 || i==n-1 ){
3746 fprintf(out, "\n"); lineno++;
3747 j = 0;
3748 }else{
3749 j++;
3750 }
3751 }
3752 fprintf(out, "};\n"); lineno++;
3753
3754 /* Output the yy_lookahead table */
drh57196282004-10-06 15:41:16 +00003755 fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
drh8b582012003-10-21 13:16:03 +00003756 for(i=j=0; i<n; i++){
3757 int la = acttab_yylookahead(pActtab, i);
3758 if( la<0 ) la = lemp->nsymbol;
drhfdbf9282003-10-21 16:34:41 +00003759 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003760 fprintf(out, " %4d,", la);
3761 if( j==9 || i==n-1 ){
3762 fprintf(out, "\n"); lineno++;
3763 j = 0;
3764 }else{
3765 j++;
3766 }
3767 }
3768 fprintf(out, "};\n"); lineno++;
3769
3770 /* Output the yy_shift_ofst[] table */
3771 fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
drhada354d2005-11-05 15:03:59 +00003772 n = lemp->nstate;
3773 while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET ) n--;
drhf16371d2009-11-03 19:18:31 +00003774 fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;
3775 fprintf(out, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst); lineno++;
3776 fprintf(out, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst); lineno++;
drh57196282004-10-06 15:41:16 +00003777 fprintf(out, "static const %s yy_shift_ofst[] = {\n",
drh8b582012003-10-21 13:16:03 +00003778 minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
drh8b582012003-10-21 13:16:03 +00003779 for(i=j=0; i<n; i++){
3780 int ofst;
3781 stp = lemp->sorted[i];
3782 ofst = stp->iTknOfst;
3783 if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;
drhfdbf9282003-10-21 16:34:41 +00003784 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003785 fprintf(out, " %4d,", ofst);
3786 if( j==9 || i==n-1 ){
3787 fprintf(out, "\n"); lineno++;
3788 j = 0;
3789 }else{
3790 j++;
3791 }
3792 }
3793 fprintf(out, "};\n"); lineno++;
3794
3795 /* Output the yy_reduce_ofst[] table */
3796 fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
drhada354d2005-11-05 15:03:59 +00003797 n = lemp->nstate;
3798 while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET ) n--;
drhf16371d2009-11-03 19:18:31 +00003799 fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;
3800 fprintf(out, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst); lineno++;
3801 fprintf(out, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst); lineno++;
drh57196282004-10-06 15:41:16 +00003802 fprintf(out, "static const %s yy_reduce_ofst[] = {\n",
drh8b582012003-10-21 13:16:03 +00003803 minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
drh8b582012003-10-21 13:16:03 +00003804 for(i=j=0; i<n; i++){
3805 int ofst;
3806 stp = lemp->sorted[i];
3807 ofst = stp->iNtOfst;
3808 if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
drhfdbf9282003-10-21 16:34:41 +00003809 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003810 fprintf(out, " %4d,", ofst);
3811 if( j==9 || i==n-1 ){
3812 fprintf(out, "\n"); lineno++;
3813 j = 0;
3814 }else{
3815 j++;
3816 }
3817 }
3818 fprintf(out, "};\n"); lineno++;
3819
3820 /* Output the default action table */
drh57196282004-10-06 15:41:16 +00003821 fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
drh8b582012003-10-21 13:16:03 +00003822 n = lemp->nstate;
3823 for(i=j=0; i<n; i++){
3824 stp = lemp->sorted[i];
drhfdbf9282003-10-21 16:34:41 +00003825 if( j==0 ) fprintf(out," /* %5d */ ", i);
drh8b582012003-10-21 13:16:03 +00003826 fprintf(out, " %4d,", stp->iDflt);
3827 if( j==9 || i==n-1 ){
3828 fprintf(out, "\n"); lineno++;
3829 j = 0;
3830 }else{
3831 j++;
3832 }
3833 }
3834 fprintf(out, "};\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003835 tplt_xfer(lemp->name,in,out,&lineno);
3836
drh0bd1f4e2002-06-06 18:54:39 +00003837 /* Generate the table of fallback tokens.
3838 */
3839 if( lemp->has_fallback ){
drh1441f3e2009-06-12 12:50:50 +00003840 int mx = lemp->nterminal - 1;
3841 while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; }
3842 for(i=0; i<=mx; i++){
drh0bd1f4e2002-06-06 18:54:39 +00003843 struct symbol *p = lemp->symbols[i];
3844 if( p->fallback==0 ){
3845 fprintf(out, " 0, /* %10s => nothing */\n", p->name);
3846 }else{
3847 fprintf(out, " %3d, /* %10s => %s */\n", p->fallback->index,
3848 p->name, p->fallback->name);
3849 }
3850 lineno++;
3851 }
3852 }
3853 tplt_xfer(lemp->name, in, out, &lineno);
3854
3855 /* Generate a table containing the symbolic name of every symbol
3856 */
drh75897232000-05-29 14:26:00 +00003857 for(i=0; i<lemp->nsymbol; i++){
3858 sprintf(line,"\"%s\",",lemp->symbols[i]->name);
3859 fprintf(out," %-15s",line);
3860 if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; }
3861 }
3862 if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; }
3863 tplt_xfer(lemp->name,in,out,&lineno);
3864
drh0bd1f4e2002-06-06 18:54:39 +00003865 /* Generate a table containing a text string that describes every
drh34ff57b2008-07-14 12:27:51 +00003866 ** rule in the rule set of the grammar. This information is used
drh0bd1f4e2002-06-06 18:54:39 +00003867 ** when tracing REDUCE actions.
3868 */
3869 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
3870 assert( rp->index==i );
drhc4dd3fd2008-01-22 01:48:05 +00003871 fprintf(out," /* %3d */ \"", i);
3872 writeRuleText(out, rp);
drh0bd1f4e2002-06-06 18:54:39 +00003873 fprintf(out,"\",\n"); lineno++;
3874 }
3875 tplt_xfer(lemp->name,in,out,&lineno);
3876
drh75897232000-05-29 14:26:00 +00003877 /* Generate code which executes every time a symbol is popped from
3878 ** the stack while processing errors or while destroying the parser.
drh0bd1f4e2002-06-06 18:54:39 +00003879 ** (In other words, generate the %destructor actions)
3880 */
drh75897232000-05-29 14:26:00 +00003881 if( lemp->tokendest ){
drh4dc8ef52008-07-01 17:13:57 +00003882 int once = 1;
drh75897232000-05-29 14:26:00 +00003883 for(i=0; i<lemp->nsymbol; i++){
3884 struct symbol *sp = lemp->symbols[i];
3885 if( sp==0 || sp->type!=TERMINAL ) continue;
drh4dc8ef52008-07-01 17:13:57 +00003886 if( once ){
3887 fprintf(out, " /* TERMINAL Destructor */\n"); lineno++;
3888 once = 0;
3889 }
drhc53eed12009-06-12 17:46:19 +00003890 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
drh75897232000-05-29 14:26:00 +00003891 }
3892 for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
3893 if( i<lemp->nsymbol ){
3894 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
3895 fprintf(out," break;\n"); lineno++;
3896 }
3897 }
drh8d659732005-01-13 23:54:06 +00003898 if( lemp->vardest ){
3899 struct symbol *dflt_sp = 0;
drh4dc8ef52008-07-01 17:13:57 +00003900 int once = 1;
drh8d659732005-01-13 23:54:06 +00003901 for(i=0; i<lemp->nsymbol; i++){
3902 struct symbol *sp = lemp->symbols[i];
3903 if( sp==0 || sp->type==TERMINAL ||
3904 sp->index<=0 || sp->destructor!=0 ) continue;
drh4dc8ef52008-07-01 17:13:57 +00003905 if( once ){
3906 fprintf(out, " /* Default NON-TERMINAL Destructor */\n"); lineno++;
3907 once = 0;
3908 }
drhc53eed12009-06-12 17:46:19 +00003909 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
drh8d659732005-01-13 23:54:06 +00003910 dflt_sp = sp;
3911 }
3912 if( dflt_sp!=0 ){
3913 emit_destructor_code(out,dflt_sp,lemp,&lineno);
drh8d659732005-01-13 23:54:06 +00003914 }
drh4dc8ef52008-07-01 17:13:57 +00003915 fprintf(out," break;\n"); lineno++;
drh8d659732005-01-13 23:54:06 +00003916 }
drh75897232000-05-29 14:26:00 +00003917 for(i=0; i<lemp->nsymbol; i++){
3918 struct symbol *sp = lemp->symbols[i];
3919 if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
drh75013012009-06-12 15:47:34 +00003920 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;
drh0bb132b2004-07-20 14:06:51 +00003921
3922 /* Combine duplicate destructors into a single case */
3923 for(j=i+1; j<lemp->nsymbol; j++){
3924 struct symbol *sp2 = lemp->symbols[j];
3925 if( sp2 && sp2->type!=TERMINAL && sp2->destructor
3926 && sp2->dtnum==sp->dtnum
3927 && strcmp(sp->destructor,sp2->destructor)==0 ){
drhc53eed12009-06-12 17:46:19 +00003928 fprintf(out," case %d: /* %s */\n",
3929 sp2->index, sp2->name); lineno++;
drh0bb132b2004-07-20 14:06:51 +00003930 sp2->destructor = 0;
3931 }
3932 }
3933
drh75897232000-05-29 14:26:00 +00003934 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
3935 fprintf(out," break;\n"); lineno++;
3936 }
drh75897232000-05-29 14:26:00 +00003937 tplt_xfer(lemp->name,in,out,&lineno);
3938
3939 /* Generate code which executes whenever the parser stack overflows */
drha5808f32008-04-27 22:19:44 +00003940 tplt_print(out,lemp,lemp->overflow,&lineno);
drh75897232000-05-29 14:26:00 +00003941 tplt_xfer(lemp->name,in,out,&lineno);
3942
3943 /* Generate the table of rule information
3944 **
3945 ** Note: This code depends on the fact that rules are number
3946 ** sequentually beginning with 0.
3947 */
3948 for(rp=lemp->rule; rp; rp=rp->next){
3949 fprintf(out," { %d, %d },\n",rp->lhs->index,rp->nrhs); lineno++;
3950 }
3951 tplt_xfer(lemp->name,in,out,&lineno);
3952
3953 /* Generate code which execution during each REDUCE action */
3954 for(rp=lemp->rule; rp; rp=rp->next){
drh61e339a2007-01-16 03:09:02 +00003955 translate_code(lemp, rp);
drh0bb132b2004-07-20 14:06:51 +00003956 }
drhc53eed12009-06-12 17:46:19 +00003957 /* First output rules other than the default: rule */
drh0bb132b2004-07-20 14:06:51 +00003958 for(rp=lemp->rule; rp; rp=rp->next){
drhc53eed12009-06-12 17:46:19 +00003959 struct rule *rp2; /* Other rules with the same action */
drh0bb132b2004-07-20 14:06:51 +00003960 if( rp->code==0 ) continue;
drhc53eed12009-06-12 17:46:19 +00003961 if( rp->code[0]=='\n' && rp->code[1]==0 ) continue; /* Will be default: */
drhc4dd3fd2008-01-22 01:48:05 +00003962 fprintf(out," case %d: /* ", rp->index);
3963 writeRuleText(out, rp);
3964 fprintf(out, " */\n"); lineno++;
drh0bb132b2004-07-20 14:06:51 +00003965 for(rp2=rp->next; rp2; rp2=rp2->next){
3966 if( rp2->code==rp->code ){
drhc4dd3fd2008-01-22 01:48:05 +00003967 fprintf(out," case %d: /* ", rp2->index);
3968 writeRuleText(out, rp2);
drh8a415d32009-06-12 13:53:51 +00003969 fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->index); lineno++;
drh0bb132b2004-07-20 14:06:51 +00003970 rp2->code = 0;
3971 }
3972 }
drh75897232000-05-29 14:26:00 +00003973 emit_code(out,rp,lemp,&lineno);
3974 fprintf(out," break;\n"); lineno++;
drhc53eed12009-06-12 17:46:19 +00003975 rp->code = 0;
drh75897232000-05-29 14:26:00 +00003976 }
drhc53eed12009-06-12 17:46:19 +00003977 /* Finally, output the default: rule. We choose as the default: all
3978 ** empty actions. */
3979 fprintf(out," default:\n"); lineno++;
3980 for(rp=lemp->rule; rp; rp=rp->next){
3981 if( rp->code==0 ) continue;
3982 assert( rp->code[0]=='\n' && rp->code[1]==0 );
3983 fprintf(out," /* (%d) ", rp->index);
3984 writeRuleText(out, rp);
3985 fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->index); lineno++;
3986 }
3987 fprintf(out," break;\n"); lineno++;
drh75897232000-05-29 14:26:00 +00003988 tplt_xfer(lemp->name,in,out,&lineno);
3989
3990 /* Generate code which executes if a parse fails */
drha5808f32008-04-27 22:19:44 +00003991 tplt_print(out,lemp,lemp->failure,&lineno);
drh75897232000-05-29 14:26:00 +00003992 tplt_xfer(lemp->name,in,out,&lineno);
3993
3994 /* Generate code which executes when a syntax error occurs */
drha5808f32008-04-27 22:19:44 +00003995 tplt_print(out,lemp,lemp->error,&lineno);
drh75897232000-05-29 14:26:00 +00003996 tplt_xfer(lemp->name,in,out,&lineno);
3997
3998 /* Generate code which executes when the parser accepts its input */
drha5808f32008-04-27 22:19:44 +00003999 tplt_print(out,lemp,lemp->accept,&lineno);
drh75897232000-05-29 14:26:00 +00004000 tplt_xfer(lemp->name,in,out,&lineno);
4001
4002 /* Append any addition code the user desires */
drha5808f32008-04-27 22:19:44 +00004003 tplt_print(out,lemp,lemp->extracode,&lineno);
drh75897232000-05-29 14:26:00 +00004004
4005 fclose(in);
4006 fclose(out);
4007 return;
4008}
4009
4010/* Generate a header file for the parser */
icculus9e44cf12010-02-14 17:14:22 +00004011void ReportHeader(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00004012{
4013 FILE *out, *in;
icculus9e44cf12010-02-14 17:14:22 +00004014 const char *prefix;
drh75897232000-05-29 14:26:00 +00004015 char line[LINESIZE];
4016 char pattern[LINESIZE];
4017 int i;
4018
4019 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
4020 else prefix = "";
drh2aa6ca42004-09-10 00:14:04 +00004021 in = file_open(lemp,".h","rb");
drh75897232000-05-29 14:26:00 +00004022 if( in ){
4023 for(i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++){
4024 sprintf(pattern,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
4025 if( strcmp(line,pattern) ) break;
4026 }
4027 fclose(in);
4028 if( i==lemp->nterminal ){
4029 /* No change in the file. Don't rewrite it. */
4030 return;
4031 }
4032 }
drh2aa6ca42004-09-10 00:14:04 +00004033 out = file_open(lemp,".h","wb");
drh75897232000-05-29 14:26:00 +00004034 if( out ){
4035 for(i=1; i<lemp->nterminal; i++){
4036 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
4037 }
4038 fclose(out);
4039 }
4040 return;
4041}
4042
4043/* Reduce the size of the action tables, if possible, by making use
4044** of defaults.
4045**
drhb59499c2002-02-23 18:45:13 +00004046** In this version, we take the most frequent REDUCE action and make
drhe09daa92006-06-10 13:29:31 +00004047** it the default. Except, there is no default if the wildcard token
4048** is a possible look-ahead.
drh75897232000-05-29 14:26:00 +00004049*/
icculus9e44cf12010-02-14 17:14:22 +00004050void CompressTables(struct lemon *lemp)
drh75897232000-05-29 14:26:00 +00004051{
4052 struct state *stp;
drhb59499c2002-02-23 18:45:13 +00004053 struct action *ap, *ap2;
4054 struct rule *rp, *rp2, *rbest;
4055 int nbest, n;
drh75897232000-05-29 14:26:00 +00004056 int i;
drhe09daa92006-06-10 13:29:31 +00004057 int usesWildcard;
drh75897232000-05-29 14:26:00 +00004058
4059 for(i=0; i<lemp->nstate; i++){
4060 stp = lemp->sorted[i];
drhb59499c2002-02-23 18:45:13 +00004061 nbest = 0;
4062 rbest = 0;
drhe09daa92006-06-10 13:29:31 +00004063 usesWildcard = 0;
drh75897232000-05-29 14:26:00 +00004064
drhb59499c2002-02-23 18:45:13 +00004065 for(ap=stp->ap; ap; ap=ap->next){
drhe09daa92006-06-10 13:29:31 +00004066 if( ap->type==SHIFT && ap->sp==lemp->wildcard ){
4067 usesWildcard = 1;
4068 }
drhb59499c2002-02-23 18:45:13 +00004069 if( ap->type!=REDUCE ) continue;
4070 rp = ap->x.rp;
drhb4960992007-10-05 16:16:36 +00004071 if( rp->lhsStart ) continue;
drhb59499c2002-02-23 18:45:13 +00004072 if( rp==rbest ) continue;
4073 n = 1;
4074 for(ap2=ap->next; ap2; ap2=ap2->next){
4075 if( ap2->type!=REDUCE ) continue;
4076 rp2 = ap2->x.rp;
4077 if( rp2==rbest ) continue;
4078 if( rp2==rp ) n++;
4079 }
4080 if( n>nbest ){
4081 nbest = n;
4082 rbest = rp;
drh75897232000-05-29 14:26:00 +00004083 }
4084 }
drhb59499c2002-02-23 18:45:13 +00004085
4086 /* Do not make a default if the number of rules to default
drhe09daa92006-06-10 13:29:31 +00004087 ** is not at least 1 or if the wildcard token is a possible
4088 ** lookahead.
4089 */
4090 if( nbest<1 || usesWildcard ) continue;
drh75897232000-05-29 14:26:00 +00004091
drhb59499c2002-02-23 18:45:13 +00004092
4093 /* Combine matching REDUCE actions into a single default */
4094 for(ap=stp->ap; ap; ap=ap->next){
4095 if( ap->type==REDUCE && ap->x.rp==rbest ) break;
4096 }
drh75897232000-05-29 14:26:00 +00004097 assert( ap );
4098 ap->sp = Symbol_new("{default}");
4099 for(ap=ap->next; ap; ap=ap->next){
drhb59499c2002-02-23 18:45:13 +00004100 if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
drh75897232000-05-29 14:26:00 +00004101 }
4102 stp->ap = Action_sort(stp->ap);
4103 }
4104}
drhb59499c2002-02-23 18:45:13 +00004105
drhada354d2005-11-05 15:03:59 +00004106
4107/*
4108** Compare two states for sorting purposes. The smaller state is the
4109** one with the most non-terminal actions. If they have the same number
4110** of non-terminal actions, then the smaller is the one with the most
4111** token actions.
4112*/
4113static int stateResortCompare(const void *a, const void *b){
4114 const struct state *pA = *(const struct state**)a;
4115 const struct state *pB = *(const struct state**)b;
4116 int n;
4117
4118 n = pB->nNtAct - pA->nNtAct;
4119 if( n==0 ){
4120 n = pB->nTknAct - pA->nTknAct;
drhe594bc32009-11-03 13:02:25 +00004121 if( n==0 ){
4122 n = pB->statenum - pA->statenum;
4123 }
drhada354d2005-11-05 15:03:59 +00004124 }
drhe594bc32009-11-03 13:02:25 +00004125 assert( n!=0 );
drhada354d2005-11-05 15:03:59 +00004126 return n;
4127}
4128
4129
4130/*
4131** Renumber and resort states so that states with fewer choices
4132** occur at the end. Except, keep state 0 as the first state.
4133*/
icculus9e44cf12010-02-14 17:14:22 +00004134void ResortStates(struct lemon *lemp)
drhada354d2005-11-05 15:03:59 +00004135{
4136 int i;
4137 struct state *stp;
4138 struct action *ap;
4139
4140 for(i=0; i<lemp->nstate; i++){
4141 stp = lemp->sorted[i];
4142 stp->nTknAct = stp->nNtAct = 0;
4143 stp->iDflt = lemp->nstate + lemp->nrule;
4144 stp->iTknOfst = NO_OFFSET;
4145 stp->iNtOfst = NO_OFFSET;
4146 for(ap=stp->ap; ap; ap=ap->next){
4147 if( compute_action(lemp,ap)>=0 ){
4148 if( ap->sp->index<lemp->nterminal ){
4149 stp->nTknAct++;
4150 }else if( ap->sp->index<lemp->nsymbol ){
4151 stp->nNtAct++;
4152 }else{
4153 stp->iDflt = compute_action(lemp, ap);
4154 }
4155 }
4156 }
4157 }
4158 qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),
4159 stateResortCompare);
4160 for(i=0; i<lemp->nstate; i++){
4161 lemp->sorted[i]->statenum = i;
4162 }
4163}
4164
4165
drh75897232000-05-29 14:26:00 +00004166/***************** From the file "set.c" ************************************/
4167/*
4168** Set manipulation routines for the LEMON parser generator.
4169*/
4170
4171static int size = 0;
4172
4173/* Set the set size */
icculus9e44cf12010-02-14 17:14:22 +00004174void SetSize(int n)
drh75897232000-05-29 14:26:00 +00004175{
4176 size = n+1;
4177}
4178
4179/* Allocate a new set */
4180char *SetNew(){
4181 char *s;
drh9892c5d2007-12-21 00:02:11 +00004182 s = (char*)calloc( size, 1);
drh75897232000-05-29 14:26:00 +00004183 if( s==0 ){
4184 extern void memory_error();
4185 memory_error();
4186 }
drh75897232000-05-29 14:26:00 +00004187 return s;
4188}
4189
4190/* Deallocate a set */
icculus9e44cf12010-02-14 17:14:22 +00004191void SetFree(char *s)
drh75897232000-05-29 14:26:00 +00004192{
4193 free(s);
4194}
4195
4196/* Add a new element to the set. Return TRUE if the element was added
4197** and FALSE if it was already there. */
icculus9e44cf12010-02-14 17:14:22 +00004198int SetAdd(char *s, int e)
drh75897232000-05-29 14:26:00 +00004199{
4200 int rv;
drh9892c5d2007-12-21 00:02:11 +00004201 assert( e>=0 && e<size );
drh75897232000-05-29 14:26:00 +00004202 rv = s[e];
4203 s[e] = 1;
4204 return !rv;
4205}
4206
4207/* Add every element of s2 to s1. Return TRUE if s1 changes. */
icculus9e44cf12010-02-14 17:14:22 +00004208int SetUnion(char *s1, char *s2)
drh75897232000-05-29 14:26:00 +00004209{
4210 int i, progress;
4211 progress = 0;
4212 for(i=0; i<size; i++){
4213 if( s2[i]==0 ) continue;
4214 if( s1[i]==0 ){
4215 progress = 1;
4216 s1[i] = 1;
4217 }
4218 }
4219 return progress;
4220}
4221/********************** From the file "table.c" ****************************/
4222/*
4223** All code in this file has been automatically generated
4224** from a specification in the file
4225** "table.q"
4226** by the associative array code building program "aagen".
4227** Do not edit this file! Instead, edit the specification
4228** file, then rerun aagen.
4229*/
4230/*
4231** Code for processing tables in the LEMON parser generator.
4232*/
4233
icculus9e44cf12010-02-14 17:14:22 +00004234PRIVATE int strhash(const char *x)
drh75897232000-05-29 14:26:00 +00004235{
4236 int h = 0;
4237 while( *x) h = h*13 + *(x++);
4238 return h;
4239}
4240
4241/* Works like strdup, sort of. Save a string in malloced memory, but
4242** keep strings in a table so that the same string is not in more
4243** than one place.
4244*/
icculus9e44cf12010-02-14 17:14:22 +00004245const char *Strsafe(const char *y)
drh75897232000-05-29 14:26:00 +00004246{
icculus9e44cf12010-02-14 17:14:22 +00004247 const char *z;
4248 char *cpy;
drh75897232000-05-29 14:26:00 +00004249
drh916f75f2006-07-17 00:19:39 +00004250 if( y==0 ) return 0;
drh75897232000-05-29 14:26:00 +00004251 z = Strsafe_find(y);
icculus9e44cf12010-02-14 17:14:22 +00004252 if( z==0 && (cpy=(char *)malloc( lemonStrlen(y)+1 ))!=0 ){
4253 strcpy(cpy,y);
4254 z = cpy;
drh75897232000-05-29 14:26:00 +00004255 Strsafe_insert(z);
4256 }
4257 MemoryCheck(z);
4258 return z;
4259}
4260
4261/* There is one instance of the following structure for each
4262** associative array of type "x1".
4263*/
4264struct s_x1 {
4265 int size; /* The number of available slots. */
4266 /* Must be a power of 2 greater than or */
4267 /* equal to 1 */
4268 int count; /* Number of currently slots filled */
4269 struct s_x1node *tbl; /* The data stored here */
4270 struct s_x1node **ht; /* Hash table for lookups */
4271};
4272
4273/* There is one instance of this structure for every data element
4274** in an associative array of type "x1".
4275*/
4276typedef struct s_x1node {
icculus9e44cf12010-02-14 17:14:22 +00004277 const char *data; /* The data */
drh75897232000-05-29 14:26:00 +00004278 struct s_x1node *next; /* Next entry with the same hash */
4279 struct s_x1node **from; /* Previous link */
4280} x1node;
4281
4282/* There is only one instance of the array, which is the following */
4283static struct s_x1 *x1a;
4284
4285/* Allocate a new associative array */
4286void Strsafe_init(){
4287 if( x1a ) return;
4288 x1a = (struct s_x1*)malloc( sizeof(struct s_x1) );
4289 if( x1a ){
4290 x1a->size = 1024;
4291 x1a->count = 0;
4292 x1a->tbl = (x1node*)malloc(
4293 (sizeof(x1node) + sizeof(x1node*))*1024 );
4294 if( x1a->tbl==0 ){
4295 free(x1a);
4296 x1a = 0;
4297 }else{
4298 int i;
4299 x1a->ht = (x1node**)&(x1a->tbl[1024]);
4300 for(i=0; i<1024; i++) x1a->ht[i] = 0;
4301 }
4302 }
4303}
4304/* Insert a new record into the array. Return TRUE if successful.
4305** Prior data with the same key is NOT overwritten */
icculus9e44cf12010-02-14 17:14:22 +00004306int Strsafe_insert(const char *data)
drh75897232000-05-29 14:26:00 +00004307{
4308 x1node *np;
4309 int h;
4310 int ph;
4311
4312 if( x1a==0 ) return 0;
4313 ph = strhash(data);
4314 h = ph & (x1a->size-1);
4315 np = x1a->ht[h];
4316 while( np ){
4317 if( strcmp(np->data,data)==0 ){
4318 /* An existing entry with the same key is found. */
4319 /* Fail because overwrite is not allows. */
4320 return 0;
4321 }
4322 np = np->next;
4323 }
4324 if( x1a->count>=x1a->size ){
4325 /* Need to make the hash table bigger */
4326 int i,size;
4327 struct s_x1 array;
4328 array.size = size = x1a->size*2;
4329 array.count = x1a->count;
4330 array.tbl = (x1node*)malloc(
4331 (sizeof(x1node) + sizeof(x1node*))*size );
4332 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4333 array.ht = (x1node**)&(array.tbl[size]);
4334 for(i=0; i<size; i++) array.ht[i] = 0;
4335 for(i=0; i<x1a->count; i++){
4336 x1node *oldnp, *newnp;
4337 oldnp = &(x1a->tbl[i]);
4338 h = strhash(oldnp->data) & (size-1);
4339 newnp = &(array.tbl[i]);
4340 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4341 newnp->next = array.ht[h];
4342 newnp->data = oldnp->data;
4343 newnp->from = &(array.ht[h]);
4344 array.ht[h] = newnp;
4345 }
4346 free(x1a->tbl);
4347 *x1a = array;
4348 }
4349 /* Insert the new data */
4350 h = ph & (x1a->size-1);
4351 np = &(x1a->tbl[x1a->count++]);
4352 np->data = data;
4353 if( x1a->ht[h] ) x1a->ht[h]->from = &(np->next);
4354 np->next = x1a->ht[h];
4355 x1a->ht[h] = np;
4356 np->from = &(x1a->ht[h]);
4357 return 1;
4358}
4359
4360/* Return a pointer to data assigned to the given key. Return NULL
4361** if no such key. */
icculus9e44cf12010-02-14 17:14:22 +00004362const char *Strsafe_find(const char *key)
drh75897232000-05-29 14:26:00 +00004363{
4364 int h;
4365 x1node *np;
4366
4367 if( x1a==0 ) return 0;
4368 h = strhash(key) & (x1a->size-1);
4369 np = x1a->ht[h];
4370 while( np ){
4371 if( strcmp(np->data,key)==0 ) break;
4372 np = np->next;
4373 }
4374 return np ? np->data : 0;
4375}
4376
4377/* Return a pointer to the (terminal or nonterminal) symbol "x".
4378** Create a new symbol if this is the first time "x" has been seen.
4379*/
icculus9e44cf12010-02-14 17:14:22 +00004380struct symbol *Symbol_new(const char *x)
drh75897232000-05-29 14:26:00 +00004381{
4382 struct symbol *sp;
4383
4384 sp = Symbol_find(x);
4385 if( sp==0 ){
drh9892c5d2007-12-21 00:02:11 +00004386 sp = (struct symbol *)calloc(1, sizeof(struct symbol) );
drh75897232000-05-29 14:26:00 +00004387 MemoryCheck(sp);
4388 sp->name = Strsafe(x);
4389 sp->type = isupper(*x) ? TERMINAL : NONTERMINAL;
4390 sp->rule = 0;
drh0bd1f4e2002-06-06 18:54:39 +00004391 sp->fallback = 0;
drh75897232000-05-29 14:26:00 +00004392 sp->prec = -1;
4393 sp->assoc = UNK;
4394 sp->firstset = 0;
drhaa9f1122007-08-23 02:50:56 +00004395 sp->lambda = LEMON_FALSE;
drh75897232000-05-29 14:26:00 +00004396 sp->destructor = 0;
drh4dc8ef52008-07-01 17:13:57 +00004397 sp->destLineno = 0;
drh75897232000-05-29 14:26:00 +00004398 sp->datatype = 0;
drhc4dd3fd2008-01-22 01:48:05 +00004399 sp->useCnt = 0;
drh75897232000-05-29 14:26:00 +00004400 Symbol_insert(sp,sp->name);
4401 }
drhc4dd3fd2008-01-22 01:48:05 +00004402 sp->useCnt++;
drh75897232000-05-29 14:26:00 +00004403 return sp;
4404}
4405
drh60d31652004-02-22 00:08:04 +00004406/* Compare two symbols for working purposes
4407**
4408** Symbols that begin with upper case letters (terminals or tokens)
4409** must sort before symbols that begin with lower case letters
4410** (non-terminals). Other than that, the order does not matter.
4411**
4412** We find experimentally that leaving the symbols in their original
4413** order (the order they appeared in the grammar file) gives the
4414** smallest parser tables in SQLite.
4415*/
icculus9e44cf12010-02-14 17:14:22 +00004416int Symbolcmpp(const void *_a, const void *_b)
4417{
4418 const struct symbol **a = (const struct symbol **) _a;
4419 const struct symbol **b = (const struct symbol **) _b;
drh60d31652004-02-22 00:08:04 +00004420 int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
4421 int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
drhe594bc32009-11-03 13:02:25 +00004422 assert( i1!=i2 || strcmp((**a).name,(**b).name)==0 );
drh60d31652004-02-22 00:08:04 +00004423 return i1-i2;
drh75897232000-05-29 14:26:00 +00004424}
4425
4426/* There is one instance of the following structure for each
4427** associative array of type "x2".
4428*/
4429struct s_x2 {
4430 int size; /* The number of available slots. */
4431 /* Must be a power of 2 greater than or */
4432 /* equal to 1 */
4433 int count; /* Number of currently slots filled */
4434 struct s_x2node *tbl; /* The data stored here */
4435 struct s_x2node **ht; /* Hash table for lookups */
4436};
4437
4438/* There is one instance of this structure for every data element
4439** in an associative array of type "x2".
4440*/
4441typedef struct s_x2node {
icculus9e44cf12010-02-14 17:14:22 +00004442 struct symbol *data; /* The data */
4443 const char *key; /* The key */
drh75897232000-05-29 14:26:00 +00004444 struct s_x2node *next; /* Next entry with the same hash */
4445 struct s_x2node **from; /* Previous link */
4446} x2node;
4447
4448/* There is only one instance of the array, which is the following */
4449static struct s_x2 *x2a;
4450
4451/* Allocate a new associative array */
4452void Symbol_init(){
4453 if( x2a ) return;
4454 x2a = (struct s_x2*)malloc( sizeof(struct s_x2) );
4455 if( x2a ){
4456 x2a->size = 128;
4457 x2a->count = 0;
4458 x2a->tbl = (x2node*)malloc(
4459 (sizeof(x2node) + sizeof(x2node*))*128 );
4460 if( x2a->tbl==0 ){
4461 free(x2a);
4462 x2a = 0;
4463 }else{
4464 int i;
4465 x2a->ht = (x2node**)&(x2a->tbl[128]);
4466 for(i=0; i<128; i++) x2a->ht[i] = 0;
4467 }
4468 }
4469}
4470/* Insert a new record into the array. Return TRUE if successful.
4471** Prior data with the same key is NOT overwritten */
icculus9e44cf12010-02-14 17:14:22 +00004472int Symbol_insert(struct symbol *data, const char *key)
drh75897232000-05-29 14:26:00 +00004473{
4474 x2node *np;
4475 int h;
4476 int ph;
4477
4478 if( x2a==0 ) return 0;
4479 ph = strhash(key);
4480 h = ph & (x2a->size-1);
4481 np = x2a->ht[h];
4482 while( np ){
4483 if( strcmp(np->key,key)==0 ){
4484 /* An existing entry with the same key is found. */
4485 /* Fail because overwrite is not allows. */
4486 return 0;
4487 }
4488 np = np->next;
4489 }
4490 if( x2a->count>=x2a->size ){
4491 /* Need to make the hash table bigger */
4492 int i,size;
4493 struct s_x2 array;
4494 array.size = size = x2a->size*2;
4495 array.count = x2a->count;
4496 array.tbl = (x2node*)malloc(
4497 (sizeof(x2node) + sizeof(x2node*))*size );
4498 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4499 array.ht = (x2node**)&(array.tbl[size]);
4500 for(i=0; i<size; i++) array.ht[i] = 0;
4501 for(i=0; i<x2a->count; i++){
4502 x2node *oldnp, *newnp;
4503 oldnp = &(x2a->tbl[i]);
4504 h = strhash(oldnp->key) & (size-1);
4505 newnp = &(array.tbl[i]);
4506 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4507 newnp->next = array.ht[h];
4508 newnp->key = oldnp->key;
4509 newnp->data = oldnp->data;
4510 newnp->from = &(array.ht[h]);
4511 array.ht[h] = newnp;
4512 }
4513 free(x2a->tbl);
4514 *x2a = array;
4515 }
4516 /* Insert the new data */
4517 h = ph & (x2a->size-1);
4518 np = &(x2a->tbl[x2a->count++]);
4519 np->key = key;
4520 np->data = data;
4521 if( x2a->ht[h] ) x2a->ht[h]->from = &(np->next);
4522 np->next = x2a->ht[h];
4523 x2a->ht[h] = np;
4524 np->from = &(x2a->ht[h]);
4525 return 1;
4526}
4527
4528/* Return a pointer to data assigned to the given key. Return NULL
4529** if no such key. */
icculus9e44cf12010-02-14 17:14:22 +00004530struct symbol *Symbol_find(const char *key)
drh75897232000-05-29 14:26:00 +00004531{
4532 int h;
4533 x2node *np;
4534
4535 if( x2a==0 ) return 0;
4536 h = strhash(key) & (x2a->size-1);
4537 np = x2a->ht[h];
4538 while( np ){
4539 if( strcmp(np->key,key)==0 ) break;
4540 np = np->next;
4541 }
4542 return np ? np->data : 0;
4543}
4544
4545/* Return the n-th data. Return NULL if n is out of range. */
icculus9e44cf12010-02-14 17:14:22 +00004546struct symbol *Symbol_Nth(int n)
drh75897232000-05-29 14:26:00 +00004547{
4548 struct symbol *data;
4549 if( x2a && n>0 && n<=x2a->count ){
4550 data = x2a->tbl[n-1].data;
4551 }else{
4552 data = 0;
4553 }
4554 return data;
4555}
4556
4557/* Return the size of the array */
4558int Symbol_count()
4559{
4560 return x2a ? x2a->count : 0;
4561}
4562
4563/* Return an array of pointers to all data in the table.
4564** The array is obtained from malloc. Return NULL if memory allocation
4565** problems, or if the array is empty. */
4566struct symbol **Symbol_arrayof()
4567{
4568 struct symbol **array;
4569 int i,size;
4570 if( x2a==0 ) return 0;
4571 size = x2a->count;
drh9892c5d2007-12-21 00:02:11 +00004572 array = (struct symbol **)calloc(size, sizeof(struct symbol *));
drh75897232000-05-29 14:26:00 +00004573 if( array ){
4574 for(i=0; i<size; i++) array[i] = x2a->tbl[i].data;
4575 }
4576 return array;
4577}
4578
4579/* Compare two configurations */
icculus9e44cf12010-02-14 17:14:22 +00004580int Configcmp(const char *_a,const char *_b)
drh75897232000-05-29 14:26:00 +00004581{
icculus9e44cf12010-02-14 17:14:22 +00004582 const struct config *a = (struct config *) _a;
4583 const struct config *b = (struct config *) _b;
drh75897232000-05-29 14:26:00 +00004584 int x;
4585 x = a->rp->index - b->rp->index;
4586 if( x==0 ) x = a->dot - b->dot;
4587 return x;
4588}
4589
4590/* Compare two states */
icculus9e44cf12010-02-14 17:14:22 +00004591PRIVATE int statecmp(struct config *a, struct config *b)
drh75897232000-05-29 14:26:00 +00004592{
4593 int rc;
4594 for(rc=0; rc==0 && a && b; a=a->bp, b=b->bp){
4595 rc = a->rp->index - b->rp->index;
4596 if( rc==0 ) rc = a->dot - b->dot;
4597 }
4598 if( rc==0 ){
4599 if( a ) rc = 1;
4600 if( b ) rc = -1;
4601 }
4602 return rc;
4603}
4604
4605/* Hash a state */
icculus9e44cf12010-02-14 17:14:22 +00004606PRIVATE int statehash(struct config *a)
drh75897232000-05-29 14:26:00 +00004607{
4608 int h=0;
4609 while( a ){
4610 h = h*571 + a->rp->index*37 + a->dot;
4611 a = a->bp;
4612 }
4613 return h;
4614}
4615
4616/* Allocate a new state structure */
4617struct state *State_new()
4618{
icculus9e44cf12010-02-14 17:14:22 +00004619 struct state *newstate;
4620 newstate = (struct state *)calloc(1, sizeof(struct state) );
4621 MemoryCheck(newstate);
4622 return newstate;
drh75897232000-05-29 14:26:00 +00004623}
4624
4625/* There is one instance of the following structure for each
4626** associative array of type "x3".
4627*/
4628struct s_x3 {
4629 int size; /* The number of available slots. */
4630 /* Must be a power of 2 greater than or */
4631 /* equal to 1 */
4632 int count; /* Number of currently slots filled */
4633 struct s_x3node *tbl; /* The data stored here */
4634 struct s_x3node **ht; /* Hash table for lookups */
4635};
4636
4637/* There is one instance of this structure for every data element
4638** in an associative array of type "x3".
4639*/
4640typedef struct s_x3node {
4641 struct state *data; /* The data */
4642 struct config *key; /* The key */
4643 struct s_x3node *next; /* Next entry with the same hash */
4644 struct s_x3node **from; /* Previous link */
4645} x3node;
4646
4647/* There is only one instance of the array, which is the following */
4648static struct s_x3 *x3a;
4649
4650/* Allocate a new associative array */
4651void State_init(){
4652 if( x3a ) return;
4653 x3a = (struct s_x3*)malloc( sizeof(struct s_x3) );
4654 if( x3a ){
4655 x3a->size = 128;
4656 x3a->count = 0;
4657 x3a->tbl = (x3node*)malloc(
4658 (sizeof(x3node) + sizeof(x3node*))*128 );
4659 if( x3a->tbl==0 ){
4660 free(x3a);
4661 x3a = 0;
4662 }else{
4663 int i;
4664 x3a->ht = (x3node**)&(x3a->tbl[128]);
4665 for(i=0; i<128; i++) x3a->ht[i] = 0;
4666 }
4667 }
4668}
4669/* Insert a new record into the array. Return TRUE if successful.
4670** Prior data with the same key is NOT overwritten */
icculus9e44cf12010-02-14 17:14:22 +00004671int State_insert(struct state *data, struct config *key)
drh75897232000-05-29 14:26:00 +00004672{
4673 x3node *np;
4674 int h;
4675 int ph;
4676
4677 if( x3a==0 ) return 0;
4678 ph = statehash(key);
4679 h = ph & (x3a->size-1);
4680 np = x3a->ht[h];
4681 while( np ){
4682 if( statecmp(np->key,key)==0 ){
4683 /* An existing entry with the same key is found. */
4684 /* Fail because overwrite is not allows. */
4685 return 0;
4686 }
4687 np = np->next;
4688 }
4689 if( x3a->count>=x3a->size ){
4690 /* Need to make the hash table bigger */
4691 int i,size;
4692 struct s_x3 array;
4693 array.size = size = x3a->size*2;
4694 array.count = x3a->count;
4695 array.tbl = (x3node*)malloc(
4696 (sizeof(x3node) + sizeof(x3node*))*size );
4697 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4698 array.ht = (x3node**)&(array.tbl[size]);
4699 for(i=0; i<size; i++) array.ht[i] = 0;
4700 for(i=0; i<x3a->count; i++){
4701 x3node *oldnp, *newnp;
4702 oldnp = &(x3a->tbl[i]);
4703 h = statehash(oldnp->key) & (size-1);
4704 newnp = &(array.tbl[i]);
4705 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4706 newnp->next = array.ht[h];
4707 newnp->key = oldnp->key;
4708 newnp->data = oldnp->data;
4709 newnp->from = &(array.ht[h]);
4710 array.ht[h] = newnp;
4711 }
4712 free(x3a->tbl);
4713 *x3a = array;
4714 }
4715 /* Insert the new data */
4716 h = ph & (x3a->size-1);
4717 np = &(x3a->tbl[x3a->count++]);
4718 np->key = key;
4719 np->data = data;
4720 if( x3a->ht[h] ) x3a->ht[h]->from = &(np->next);
4721 np->next = x3a->ht[h];
4722 x3a->ht[h] = np;
4723 np->from = &(x3a->ht[h]);
4724 return 1;
4725}
4726
4727/* Return a pointer to data assigned to the given key. Return NULL
4728** if no such key. */
icculus9e44cf12010-02-14 17:14:22 +00004729struct state *State_find(struct config *key)
drh75897232000-05-29 14:26:00 +00004730{
4731 int h;
4732 x3node *np;
4733
4734 if( x3a==0 ) return 0;
4735 h = statehash(key) & (x3a->size-1);
4736 np = x3a->ht[h];
4737 while( np ){
4738 if( statecmp(np->key,key)==0 ) break;
4739 np = np->next;
4740 }
4741 return np ? np->data : 0;
4742}
4743
4744/* Return an array of pointers to all data in the table.
4745** The array is obtained from malloc. Return NULL if memory allocation
4746** problems, or if the array is empty. */
4747struct state **State_arrayof()
4748{
4749 struct state **array;
4750 int i,size;
4751 if( x3a==0 ) return 0;
4752 size = x3a->count;
4753 array = (struct state **)malloc( sizeof(struct state *)*size );
4754 if( array ){
4755 for(i=0; i<size; i++) array[i] = x3a->tbl[i].data;
4756 }
4757 return array;
4758}
4759
4760/* Hash a configuration */
icculus9e44cf12010-02-14 17:14:22 +00004761PRIVATE int confighash(struct config *a)
drh75897232000-05-29 14:26:00 +00004762{
4763 int h=0;
4764 h = h*571 + a->rp->index*37 + a->dot;
4765 return h;
4766}
4767
4768/* There is one instance of the following structure for each
4769** associative array of type "x4".
4770*/
4771struct s_x4 {
4772 int size; /* The number of available slots. */
4773 /* Must be a power of 2 greater than or */
4774 /* equal to 1 */
4775 int count; /* Number of currently slots filled */
4776 struct s_x4node *tbl; /* The data stored here */
4777 struct s_x4node **ht; /* Hash table for lookups */
4778};
4779
4780/* There is one instance of this structure for every data element
4781** in an associative array of type "x4".
4782*/
4783typedef struct s_x4node {
4784 struct config *data; /* The data */
4785 struct s_x4node *next; /* Next entry with the same hash */
4786 struct s_x4node **from; /* Previous link */
4787} x4node;
4788
4789/* There is only one instance of the array, which is the following */
4790static struct s_x4 *x4a;
4791
4792/* Allocate a new associative array */
4793void Configtable_init(){
4794 if( x4a ) return;
4795 x4a = (struct s_x4*)malloc( sizeof(struct s_x4) );
4796 if( x4a ){
4797 x4a->size = 64;
4798 x4a->count = 0;
4799 x4a->tbl = (x4node*)malloc(
4800 (sizeof(x4node) + sizeof(x4node*))*64 );
4801 if( x4a->tbl==0 ){
4802 free(x4a);
4803 x4a = 0;
4804 }else{
4805 int i;
4806 x4a->ht = (x4node**)&(x4a->tbl[64]);
4807 for(i=0; i<64; i++) x4a->ht[i] = 0;
4808 }
4809 }
4810}
4811/* Insert a new record into the array. Return TRUE if successful.
4812** Prior data with the same key is NOT overwritten */
icculus9e44cf12010-02-14 17:14:22 +00004813int Configtable_insert(struct config *data)
drh75897232000-05-29 14:26:00 +00004814{
4815 x4node *np;
4816 int h;
4817 int ph;
4818
4819 if( x4a==0 ) return 0;
4820 ph = confighash(data);
4821 h = ph & (x4a->size-1);
4822 np = x4a->ht[h];
4823 while( np ){
icculus9e44cf12010-02-14 17:14:22 +00004824 if( Configcmp((const char *) np->data,(const char *) data)==0 ){
drh75897232000-05-29 14:26:00 +00004825 /* An existing entry with the same key is found. */
4826 /* Fail because overwrite is not allows. */
4827 return 0;
4828 }
4829 np = np->next;
4830 }
4831 if( x4a->count>=x4a->size ){
4832 /* Need to make the hash table bigger */
4833 int i,size;
4834 struct s_x4 array;
4835 array.size = size = x4a->size*2;
4836 array.count = x4a->count;
4837 array.tbl = (x4node*)malloc(
4838 (sizeof(x4node) + sizeof(x4node*))*size );
4839 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */
4840 array.ht = (x4node**)&(array.tbl[size]);
4841 for(i=0; i<size; i++) array.ht[i] = 0;
4842 for(i=0; i<x4a->count; i++){
4843 x4node *oldnp, *newnp;
4844 oldnp = &(x4a->tbl[i]);
4845 h = confighash(oldnp->data) & (size-1);
4846 newnp = &(array.tbl[i]);
4847 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
4848 newnp->next = array.ht[h];
4849 newnp->data = oldnp->data;
4850 newnp->from = &(array.ht[h]);
4851 array.ht[h] = newnp;
4852 }
4853 free(x4a->tbl);
4854 *x4a = array;
4855 }
4856 /* Insert the new data */
4857 h = ph & (x4a->size-1);
4858 np = &(x4a->tbl[x4a->count++]);
4859 np->data = data;
4860 if( x4a->ht[h] ) x4a->ht[h]->from = &(np->next);
4861 np->next = x4a->ht[h];
4862 x4a->ht[h] = np;
4863 np->from = &(x4a->ht[h]);
4864 return 1;
4865}
4866
4867/* Return a pointer to data assigned to the given key. Return NULL
4868** if no such key. */
icculus9e44cf12010-02-14 17:14:22 +00004869struct config *Configtable_find(struct config *key)
drh75897232000-05-29 14:26:00 +00004870{
4871 int h;
4872 x4node *np;
4873
4874 if( x4a==0 ) return 0;
4875 h = confighash(key) & (x4a->size-1);
4876 np = x4a->ht[h];
4877 while( np ){
icculus9e44cf12010-02-14 17:14:22 +00004878 if( Configcmp((const char *) np->data,(const char *) key)==0 ) break;
drh75897232000-05-29 14:26:00 +00004879 np = np->next;
4880 }
4881 return np ? np->data : 0;
4882}
4883
4884/* Remove all data from the table. Pass each data to the function "f"
4885** as it is removed. ("f" may be null to avoid this step.) */
icculus9e44cf12010-02-14 17:14:22 +00004886void Configtable_clear(int(*f)(struct config *))
drh75897232000-05-29 14:26:00 +00004887{
4888 int i;
4889 if( x4a==0 || x4a->count==0 ) return;
4890 if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
4891 for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;
4892 x4a->count = 0;
4893 return;
4894}