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