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