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++] - ''; 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, "", 1, iWidth); 109 } 110 k = 0; 111 while( v>0 ){ 112 k++; 113 zTemp[sizeof(zTemp)-k] = (v%10) + ''; 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 } 5041
This page was automatically generated by LXR 0.3.1. • OpenWrt