/builds/wireshark/wireshark/tools/lemon/lemon.c (2024)

1/*2** This file contains all sources (including headers) to the LEMON3** LALR(1) parser generator. The sources have been combined into a4** single file to make it easy to include LEMON in the source tree5** 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#define ISSPACE(X)((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISspace) isspace((unsigned char)(X))((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISspace)17#define ISDIGIT(X)((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISdigit) isdigit((unsigned char)(X))((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISdigit)18#define ISALNUM(X)((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISalnum) isalnum((unsigned char)(X))((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISalnum)19#define ISALPHA(X)((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISalpha) isalpha((unsigned char)(X))((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISalpha)20#define ISUPPER(X)((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISupper) isupper((unsigned char)(X))((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISupper)21#define ISLOWER(X)((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISlower) islower((unsigned char)(X))((*__ctype_b_loc ())[(int) (((unsigned char)(X)))] & (unsigned
short int) _ISlower)22 23 24#ifndef __WIN32__25# if defined(_WIN32) || defined(WIN32)26# define __WIN32__27# endif28#endif29 30#ifdef __WIN32__31#ifdef __cplusplus32extern "C" {33#endif34extern int access(const char *path, int mode);35#ifdef __cplusplus36}37#endif38#else39#include <unistd.h>40#endif41 42/* #define PRIVATE static */43#define PRIVATE44 45#ifdef TEST46#define MAXRHS1000 5 /* Set low to exercise exception code */47#else48#define MAXRHS1000 100049#endif50 51extern void memory_error();52static int showPrecedenceConflict = 0;53static char *msort(char*,char**,int(*)(const char*,const char*));54 55/*56** Compilers are getting increasingly pedantic about type conversions57** as C evolves ever closer to Ada.... To work around the latest problems58** we have to define the following variant of strlen().59*/60#define lemonStrlen(X)((int)strlen(X)) ((int)strlen(X))61 62/*63** Compilers are starting to complain about the use of sprintf() and strcpy(),64** saying they are unsafe. So we define our own versions of those routines too.65**66** There are three routines here: lemon_sprintf(), lemon_vsprintf(), and67** lemon_addtext(). The first two are replacements for sprintf() and vsprintf().68** The third is a helper routine for vsnprintf() that adds texts to the end of a69** buffer, making sure the buffer is always zero-terminated.70**71** The string formatter is a minimal subset of stdlib sprintf() supporting only72** a few simply conversions:73**74** %d75** %s76** %.*s77**78*/79static void lemon_addtext(80 char *zBuf, /* The buffer to which text is added */81 int *pnUsed, /* Slots of the buffer used so far */82 const char *zIn, /* Text to add */83 int nIn, /* Bytes of text to add. -1 to use strlen() */84 int iWidth /* Field width. Negative to left justify */85){86 if( nIn<0 ) for(nIn=0; zIn[nIn]; nIn++){}87 while( iWidth>nIn ){ zBuf[(*pnUsed)++] = ' '; iWidth--; }88 if( nIn==0 ) return;89 memcpy(&zBuf[*pnUsed], zIn, nIn);90 *pnUsed += nIn;91 while( (-iWidth)>nIn ){ zBuf[(*pnUsed)++] = ' '; iWidth++; }92 zBuf[*pnUsed] = 0;93}94static int lemon_vsprintf(char *str, const char *zFormat, va_list ap){95 int i, j, k, c;96 int nUsed = 0;97 const char *z;98 char zTemp[50];99 str[0] = 0;100 for(i=j=0; (c = zFormat[i])!=0; i++){101 if( c=='%' ){102 int iWidth = 0;103 lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0);104 c = zFormat[++i];105 if( ISDIGIT(c)((*__ctype_b_loc ())[(int) (((unsigned char)(c)))] & (unsigned
short int) _ISdigit) || (c=='-' && ISDIGIT(zFormat[i+1])((*__ctype_b_loc ())[(int) (((unsigned char)(zFormat[i+1])))]
& (unsigned short int) _ISdigit)) ){106 if( c=='-' ) i++;107 while( ISDIGIT(zFormat[i])((*__ctype_b_loc ())[(int) (((unsigned char)(zFormat[i])))] &
(unsigned short int) _ISdigit) ) iWidth = iWidth*10 + zFormat[i++] - '0';108 if( c=='-' ) iWidth = -iWidth;109 c = zFormat[i];110 }111 if( c=='d' ){112 int v = va_arg(ap, int)__builtin_va_arg(ap, int);113 if( v<0 ){114 lemon_addtext(str, &nUsed, "-", 1, iWidth);115 v = -v;116 }else if( v==0 ){117 lemon_addtext(str, &nUsed, "0", 1, iWidth);118 }119 k = 0;120 while( v>0 ){121 k++;122 zTemp[sizeof(zTemp)-k] = (v%10) + '0';123 v /= 10;124 }125 lemon_addtext(str, &nUsed, &zTemp[sizeof(zTemp)-k], k, iWidth);126 }else if( c=='s' ){127 z = va_arg(ap, const char*)__builtin_va_arg(ap, const char*);128 lemon_addtext(str, &nUsed, z, -1, iWidth);129 }else if( c=='.' && memcmp(&zFormat[i], ".*s", 3)==0 ){130 i += 2;131 k = va_arg(ap, int)__builtin_va_arg(ap, int);132 z = va_arg(ap, const char*)__builtin_va_arg(ap, const char*);133 lemon_addtext(str, &nUsed, z, k, iWidth);134 }else if( c=='%' ){135 lemon_addtext(str, &nUsed, "%", 1, 0);136 }else{137 fprintf(stderrstderr, "illegal format\n");138 exit(1);139 }140 j = i+1;141 }142 }143 lemon_addtext(str, &nUsed, &zFormat[j], i-j, 0);144 return nUsed;145}146static int lemon_sprintf(char *str, const char *format, ...){147 va_list ap;148 int rc;149 va_start(ap, format)__builtin_va_start(ap, format);150 rc = lemon_vsprintf(str, format, ap);151 va_end(ap)__builtin_va_end(ap);152 return rc;153}154static void lemon_strcpy(char *dest, const char *src){155 while( (*(dest++) = *(src++))!=0 ){}156}157static void lemon_strcat(char *dest, const char *src){158 while( *dest ) dest++;159 lemon_strcpy(dest, src);160}161 162 163/* a few forward declarations... */164struct rule;165struct lemon;166struct action;167 168static struct action *Action_new(void);169static struct action *Action_sort(struct action *);170 171/********** From the file "build.h" ************************************/172void FindRulePrecedences(struct lemon*);173void FindFirstSets(struct lemon*);174void FindStates(struct lemon*);175void FindLinks(struct lemon*);176void FindFollowSets(struct lemon*);177void FindActions(struct lemon*);178 179/********* From the file "configlist.h" *********************************/180void Configlist_init(void);181struct config *Configlist_add(struct rule *, int);182struct config *Configlist_addbasis(struct rule *, int);183void Configlist_closure(struct lemon *);184void Configlist_sort(void);185void Configlist_sortbasis(void);186struct config *Configlist_return(void);187struct config *Configlist_basis(void);188void Configlist_eat(struct config *);189void Configlist_reset(void);190 191/********* From the file "error.h" ***************************************/192void ErrorMsg(const char *, int,const char *, ...);193 194/****** From the file "option.h" ******************************************/195enum option_type { OPT_FLAG=1, OPT_INT, OPT_DBL, OPT_STR,196 OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR};197struct s_options {198 enum option_type type;199 const char *label;200 char *arg;201 const char *message;202};203int OptInit(char**,struct s_options*,FILE*);204int OptNArgs(void);205char *OptArg(int);206void OptErr(int);207void OptPrint(void);208 209/******** From the file "parse.h" *****************************************/210void Parse(struct lemon *lemp);211 212/********* From the file "plink.h" ***************************************/213struct plink *Plink_new(void);214void Plink_add(struct plink **, struct config *);215void Plink_copy(struct plink **, struct plink *);216void Plink_delete(struct plink *);217 218/********** From the file "report.h" *************************************/219void Reprint(struct lemon *);220void ReportOutput(struct lemon *);221void ReportTable(struct lemon *, int, int);222void ReportHeader(struct lemon *);223void CompressTables(struct lemon *);224void ResortStates(struct lemon *);225 226/********** From the file "set.h" ****************************************/227void SetSize(int); /* All sets will be of size N */228char *SetNew(void); /* A new set for element 0..N */229void SetFree(char*); /* Deallocate a set */230int SetAdd(char*,int); /* Add element to a set */231int SetUnion(char *,char *); /* A <- A U B, thru element N */232#define SetFind(X,Y)(X[Y]) (X[Y]) /* True if Y is in set X */233 234/********** From the file "struct.h" *************************************/235/*236** Principal data structures for the LEMON parser generator.237*/238 239typedef enum {LEMON_FALSE=0, LEMON_TRUE} Boolean;240 241/* Symbols (terminals and nonterminals) of the grammar are stored242** in the following: */243enum symbol_type {244 TERMINAL,245 NONTERMINAL,246 MULTITERMINAL247};248enum e_assoc {249 LEFT,250 RIGHT,251 NONE,252 UNK253};254struct symbol {255 const char *name; /* Name of the symbol */256 int index; /* Index number for this symbol */257 enum symbol_type type; /* Symbols are all either TERMINALS or NTs */258 struct rule *rule; /* Linked list of rules of this (if an NT) */259 struct symbol *fallback; /* fallback token in case this token doesn't parse */260 int prec; /* Precedence if defined (-1 otherwise) */261 enum e_assoc assoc; /* Associativity if precedence is defined */262 char *firstset; /* First-set for all rules of this symbol */263 Boolean lambda; /* True if NT and can generate an empty string */264 int useCnt; /* Number of times used */265 char *destructor; /* Code which executes whenever this symbol is266 ** popped from the stack during error processing */267 int destLineno; /* Line number for start of destructor. Set to268 ** -1 for duplicate destructors. */269 char *datatype; /* The data type of information held by this270 ** object. Only used if type==NONTERMINAL */271 int dtnum; /* The data type number. In the parser, the value272 ** stack is a union. The .yy%d element of this273 ** union is the correct data type for this object */274 int bContent; /* True if this symbol ever carries content - if275 ** it is ever more than just syntax */276 /* The following fields are used by MULTITERMINALs only */277 int nsubsym; /* Number of constituent symbols in the MULTI */278 struct symbol **subsym; /* Array of constituent symbols */279};280 281/* Each production rule in the grammar is stored in the following282** structure. */283struct rule {284 struct symbol *lhs; /* Left-hand side of the rule */285 const char *lhsalias; /* Alias for the LHS (NULL if none) */286 int lhsStart; /* True if left-hand side is the start symbol */287 int ruleline; /* Line number for the rule */288 int nrhs; /* Number of RHS symbols */289 struct symbol **rhs; /* The RHS symbols */290 const char **rhsalias; /* An alias for each RHS symbol (NULL if none) */291 int line; /* Line number at which code begins */292 const char *code; /* The code executed when this rule is reduced */293 const char *codePrefix; /* Setup code before code[] above */294 const char *codeSuffix; /* Breakdown code after code[] above */295 struct symbol *precsym; /* Precedence symbol for this rule */296 int index; /* An index number for this rule */297 int iRule; /* Rule number as used in the generated tables */298 Boolean noCode; /* True if this rule has no associated C code */299 Boolean codeEmitted; /* True if the code has been emitted already */300 Boolean canReduce; /* True if this rule is ever reduced */301 Boolean doesReduce; /* Reduce actions occur after optimization */302 Boolean neverReduce; /* Reduce is theoretically possible, but prevented303 ** by actions or other outside implementation */304 struct rule *nextlhs; /* Next rule with the same LHS */305 struct rule *next; /* Next rule in the global list */306};307 308/* A configuration is a production rule of the grammar together with309** a mark (dot) showing how much of that rule has been processed so far.310** Configurations also contain a follow-set which is a list of terminal311** symbols which are allowed to immediately follow the end of the rule.312** Every configuration is recorded as an instance of the following: */313enum cfgstatus {314 COMPLETE,315 INCOMPLETE316};317struct config {318 struct rule *rp; /* The rule upon which the configuration is based */319 int dot; /* The parse point */320 char *fws; /* Follow-set for this configuration only */321 struct plink *fplp; /* Follow-set forward propagation links */322 struct plink *bplp; /* Follow-set backwards propagation links */323 struct state *stp; /* Pointer to state which contains this */324 enum cfgstatus status; /* used during followset and shift computations */325 struct config *next; /* Next configuration in the state */326 struct config *bp; /* The next basis configuration */327};328 329enum e_action {330 SHIFT,331 ACCEPT,332 REDUCE,333 ERROR,334 SSCONFLICT, /* A shift/shift conflict */335 SRCONFLICT, /* Was a reduce, but part of a conflict */336 RRCONFLICT, /* Was a reduce, but part of a conflict */337 SH_RESOLVED, /* Was a shift. Precedence resolved conflict */338 RD_RESOLVED, /* Was reduce. Precedence resolved conflict */339 NOT_USED, /* Deleted by compression */340 SHIFTREDUCE /* Shift first, then reduce */341};342 343/* Every shift or reduce operation is stored as one of the following */344struct action {345 struct symbol *sp; /* The look-ahead symbol */346 enum e_action type;347 union {348 struct state *stp; /* The new state, if a shift */349 struct rule *rp; /* The rule, if a reduce */350 } x;351 struct symbol *spOpt; /* SHIFTREDUCE optimization to this symbol */352 struct action *next; /* Next action for this state */353 struct action *collide; /* Next action with the same hash */354};355 356/* Each state of the generated parser's finite state machine357** is encoded as an instance of the following structure. */358struct state {359 struct config *bp; /* The basis configurations for this state */360 struct config *cfp; /* All configurations in this set */361 int statenum; /* Sequential number for this state */362 struct action *ap; /* List of actions for this state */363 int nTknAct, nNtAct; /* Number of actions on terminals and nonterminals */364 int iTknOfst, iNtOfst; /* yy_action[] offset for terminals and nonterms */365 int iDfltReduce; /* Default action is to REDUCE by this rule */366 struct rule *pDfltReduce;/* The default REDUCE rule. */367 int autoReduce; /* True if this is an auto-reduce state */368};369#define NO_OFFSET(-2147483647) (-2147483647)370 371/* A followset propagation link indicates that the contents of one372** configuration followset should be propagated to another whenever373** the first changes. */374struct plink {375 struct config *cfp; /* The configuration to which linked */376 struct plink *next; /* The next propagate link */377};378 379/* The state vector for the entire parser generator is recorded as380** follows. (LEMON uses no global variables and makes little use of381** static variables. Fields in the following structure can be thought382** of as begin global variables in the program.) */383struct lemon {384 struct state **sorted; /* Table of states sorted by state number */385 struct rule *rule; /* List of all rules */386 struct rule *startRule; /* First rule */387 int nstate; /* Number of states */388 int nxstate; /* nstate with tail degenerate states removed */389 int nrule; /* Number of rules */390 int nruleWithAction; /* Number of rules with actions */391 int nsymbol; /* Number of terminal and nonterminal symbols */392 int nterminal; /* Number of terminal symbols */393 int minShiftReduce; /* Minimum shift-reduce action value */394 int errAction; /* Error action value */395 int accAction; /* Accept action value */396 int noAction; /* No-op action value */397 int minReduce; /* Minimum reduce action */398 int maxAction; /* Maximum action value of any kind */399 struct symbol **symbols; /* Sorted array of pointers to symbols */400 int errorcnt; /* Number of errors */401 struct symbol *errsym; /* The error symbol */402 struct symbol *wildcard; /* Token that matches anything */403 char *name; /* Name of the generated parser */404 char *arg; /* Declaration of the 3rd argument to parser */405 char *ctx; /* Declaration of 2nd argument to constructor */406 char *tokentype; /* Type of terminal symbols in the parser stack */407 char *vartype; /* The default type of non-terminal symbols */408 char *start; /* Name of the start symbol for the grammar */409 char *stacksize; /* Size of the parser stack */410 char *include; /* Code to put at the start of the C file */411 char *error; /* Code to execute when an error is seen */412 char *overflow; /* Code to execute on a stack overflow */413 char *failure; /* Code to execute on parser failure */414 char *accept; /* Code to execute when the parser excepts */415 char *extracode; /* Code appended to the generated file */416 char *tokendest; /* Code to execute to destroy token data */417 char *vardest; /* Code for the default non-terminal destructor */418 char *filename; /* Name of the input file */419 char *outname; /* Name of the current output file */420 char *tokenprefix; /* A prefix added to token names in the .h file */421 int nconflict; /* Number of parsing conflicts */422 int nactiontab; /* Number of entries in the yy_action[] table */423 int nlookaheadtab; /* Number of entries in yy_lookahead[] */424 int tablesize; /* Total table size of all tables in bytes */425 int basisflag; /* Print only basis configurations */426 int printPreprocessed; /* Show preprocessor output on stdout */427 int has_fallback; /* True if any %fallback is seen in the grammar */428 int nolinenosflag; /* True if #line statements should not be printed */429 char *argv0; /* Name of the program */430};431 432#define MemoryCheck(X)if((X)==0){ extern void memory_error(); memory_error(); } if((X)==0){ \433 extern void memory_error(); \434 memory_error(); \435}436 437/**************** From the file "table.h" *********************************/438/*439** All code in this file has been automatically generated440** from a specification in the file441** "table.q"442** by the associative array code building program "aagen".443** Do not edit this file! Instead, edit the specification444** file, then rerun aagen.445*/446/*447** Code for processing tables in the LEMON parser generator.448*/449/* Routines for handling a strings */450 451const char *Strsafe(const char *);452 453void Strsafe_init(void);454int Strsafe_insert(const char *);455const char *Strsafe_find(const char *);456 457/* Routines for handling symbols of the grammar */458 459struct symbol *Symbol_new(const char *);460int Symbolcmpp(const void *, const void *);461void Symbol_init(void);462int Symbol_insert(struct symbol *, const char *);463struct symbol *Symbol_find(const char *);464struct symbol *Symbol_Nth(int);465int Symbol_count(void);466struct symbol **Symbol_arrayof(void);467 468/* Routines to manage the state table */469 470int Configcmp(const char *, const char *);471struct state *State_new(void);472void State_init(void);473int State_insert(struct state *, struct config *);474struct state *State_find(struct config *);475struct state **State_arrayof(void);476 477/* Routines used for efficiency in Configlist_add */478 479void Configtable_init(void);480int Configtable_insert(struct config *);481struct config *Configtable_find(struct config *);482void Configtable_clear(int(*)(struct config *));483 484/****************** From the file "action.c" *******************************/485/*486** Routines processing parser actions in the LEMON parser generator.487*/488 489/* Allocate a new parser action */490static struct action *Action_new(void){491 static struct action *actionfreelist = 0;492 struct action *newaction;493 494 if( actionfreelist==0 ){495 int i;496 int amt = 100;497 actionfreelist = (struct action *)calloc(amt, sizeof(struct action));498 if( actionfreelist==0 ){499 fprintf(stderrstderr,"Unable to allocate memory for a new parser action.");500 exit(1);501 }502 for(i=0; i<amt-1; i++) actionfreelist[i].next = &actionfreelist[i+1];503 actionfreelist[amt-1].next = 0;504 }505 newaction = actionfreelist;506 actionfreelist = actionfreelist->next;507 return newaction;508}509 510/* Compare two actions for sorting purposes. Return negative, zero, or511** positive if the first action is less than, equal to, or greater than512** the first513*/514static int actioncmp(515 struct action *ap1,516 struct action *ap2517){518 int rc;519 rc = ap1->sp->index - ap2->sp->index;520 if( rc==0 ){521 rc = (int)ap1->type - (int)ap2->type;522 }523 if( rc==0 && (ap1->type==REDUCE || ap1->type==SHIFTREDUCE) ){524 rc = ap1->x.rp->index - ap2->x.rp->index;525 }526 if( rc==0 ){527 rc = (int) (ap2 - ap1);528 }529 return rc;530}531 532/* Sort parser actions */533static struct action *Action_sort(534 struct action *ap535){536 ap = (struct action *)msort((char *)ap,(char **)&ap->next,537 (int(*)(const char*,const char*))actioncmp);538 return ap;539}540 541void Action_add(542 struct action **app,543 enum e_action type,544 struct symbol *sp,545 char *arg546){547 struct action *newaction;548 newaction = Action_new();549 newaction->next = *app;550 *app = newaction;551 newaction->type = type;552 newaction->sp = sp;553 newaction->spOpt = 0;554 if( type==SHIFT ){555 newaction->x.stp = (struct state *)arg;556 }else{557 newaction->x.rp = (struct rule *)arg;558 }559}560/********************** New code to implement the "acttab" module ***********/561/*562** This module implements routines use to construct the yy_action[] table.563*/564 565/*566** The state of the yy_action table under construction is an instance of567** the following structure.568**569** The yy_action table maps the pair (state_number, lookahead) into an570** action_number. The table is an array of integers pairs. The state_number571** determines an initial offset into the yy_action array. The lookahead572** value is then added to this initial offset to get an index X into the573** yy_action array. If the aAction[X].lookahead equals the value of the574** of the lookahead input, then the value of the action_number output is575** aAction[X].action. If the lookaheads do not match then the576** default action for the state_number is returned.577**578** All actions associated with a single state_number are first entered579** into aLookahead[] using multiple calls to acttab_action(). Then the580** actions for that single state_number are placed into the aAction[]581** array with a single call to acttab_insert(). The acttab_insert() call582** also resets the aLookahead[] array in preparation for the next583** state number.584*/585struct lookahead_action {586 int lookahead; /* Value of the lookahead token */587 int action; /* Action to take on the given lookahead */588};589typedef struct acttab acttab;590struct acttab {591 int nAction; /* Number of used slots in aAction[] */592 int nActionAlloc; /* Slots allocated for aAction[] */593 struct lookahead_action594 *aAction, /* The yy_action[] table under construction */595 *aLookahead; /* A single new transaction set */596 int mnLookahead; /* Minimum aLookahead[].lookahead */597 int mnAction; /* Action associated with mnLookahead */598 int mxLookahead; /* Maximum aLookahead[].lookahead */599 int nLookahead; /* Used slots in aLookahead[] */600 int nLookaheadAlloc; /* Slots allocated in aLookahead[] */601 int nterminal; /* Number of terminal symbols */602 int nsymbol; /* total number of symbols */603};604 605/* Return the number of entries in the yy_action table */606#define acttab_lookahead_size(X)((X)->nAction) ((X)->nAction)607 608/* The value for the N-th entry in yy_action */609#define acttab_yyaction(X,N)((X)->aAction[N].action) ((X)->aAction[N].action)610 611/* The value for the N-th entry in yy_lookahead */612#define acttab_yylookahead(X,N)((X)->aAction[N].lookahead) ((X)->aAction[N].lookahead)613 614/* Free all memory associated with the given acttab */615void acttab_free(acttab *p){616 free( p->aAction );617 free( p->aLookahead );618 free( p );619}620 621/* Allocate a new acttab structure */622acttab *acttab_alloc(int nsymbol, int nterminal){623 acttab *p = (acttab *) calloc( 1, sizeof(*p) );624 if( p==0 ){625 fprintf(stderrstderr,"Unable to allocate memory for a new acttab.");626 exit(1);627 }628 memset(p, 0, sizeof(*p));629 p->nsymbol = nsymbol;630 p->nterminal = nterminal;631 return p;632}633 634/* Add a new action to the current transaction set.635**636** This routine is called once for each lookahead for a particular637** state.638*/639void acttab_action(acttab *p, int lookahead, int action){640 if( p->nLookahead>=p->nLookaheadAlloc ){641 p->nLookaheadAlloc += 25;642 p->aLookahead = (struct lookahead_action *) realloc( p->aLookahead,643 sizeof(p->aLookahead[0])*p->nLookaheadAlloc );644 if( p->aLookahead==0 ){645 fprintf(stderrstderr,"malloc failed\n");646 exit(1);647 }648 }649 if( p->nLookahead==0 ){650 p->mxLookahead = lookahead;651 p->mnLookahead = lookahead;652 p->mnAction = action;653 }else{654 if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;655 if( p->mnLookahead>lookahead ){656 p->mnLookahead = lookahead;657 p->mnAction = action;658 }659 }660 p->aLookahead[p->nLookahead].lookahead = lookahead;661 p->aLookahead[p->nLookahead].action = action;662 p->nLookahead++;663}664 665/*666** Add the transaction set built up with prior calls to acttab_action()667** into the current action table. Then reset the transaction set back668** to an empty set in preparation for a new round of acttab_action() calls.669**670** Return the offset into the action table of the new transaction.671**672** If the makeItSafe parameter is true, then the offset is chosen so that673** it is impossible to overread the yy_lookaside[] table regardless of674** the lookaside token. This is done for the terminal symbols, as they675** come from external inputs and can contain syntax errors. When makeItSafe676** is false, there is more flexibility in selecting offsets, resulting in677** a smaller table. For non-terminal symbols, which are never syntax errors,678** makeItSafe can be false.679*/680int acttab_insert(acttab *p, int makeItSafe){681 int i, j, k, n, end;682 assert( p->nLookahead>0 )((void) sizeof ((p->nLookahead>0) ? 1 : 0), __extension__
({ if (p->nLookahead>0) ; else __assert_fail ("p->nLookahead>0"
, "tools/lemon/lemon.c", 682, __extension__ __PRETTY_FUNCTION__
); }));683 684 /* Make sure we have enough space to hold the expanded action table685 ** in the worst case. The worst case occurs if the transaction set686 ** must be appended to the current action table687 */688 n = p->nsymbol + 1;689 if( p->nAction + n >= p->nActionAlloc ){690 int oldAlloc = p->nActionAlloc;691 p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;692 p->aAction = (struct lookahead_action *) realloc( p->aAction,693 sizeof(p->aAction[0])*p->nActionAlloc);694 if( p->aAction==0 ){695 fprintf(stderrstderr,"malloc failed\n");696 exit(1);697 }698 for(i=oldAlloc; i<p->nActionAlloc; i++){699 p->aAction[i].lookahead = -1;700 p->aAction[i].action = -1;701 }702 }703 704 /* Scan the existing action table looking for an offset that is a705 ** duplicate of the current transaction set. Fall out of the loop706 ** if and when the duplicate is found.707 **708 ** i is the index in p->aAction[] where p->mnLookahead is inserted.709 */710 end = makeItSafe ? p->mnLookahead : 0;711 for(i=p->nAction-1; i>=end; i--){712 if( p->aAction[i].lookahead==p->mnLookahead ){713 /* All lookaheads and actions in the aLookahead[] transaction714 ** must match against the candidate aAction[i] entry. */715 if( p->aAction[i].action!=p->mnAction ) continue;716 for(j=0; j<p->nLookahead; j++){717 k = p->aLookahead[j].lookahead - p->mnLookahead + i;718 if( k<0 || k>=p->nAction ) break;719 if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;720 if( p->aLookahead[j].action!=p->aAction[k].action ) break;721 }722 if( j<p->nLookahead ) continue;723 724 /* No possible lookahead value that is not in the aLookahead[]725 ** transaction is allowed to match aAction[i] */726 n = 0;727 for(j=0; j<p->nAction; j++){728 if( p->aAction[j].lookahead<0 ) continue;729 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;730 }731 if( n==p->nLookahead ){732 break; /* An exact match is found at offset i */733 }734 }735 }736 737 /* If no existing offsets exactly match the current transaction, find an738 ** an empty offset in the aAction[] table in which we can add the739 ** aLookahead[] transaction.740 */741 if( i<end ){742 /* Look for holes in the aAction[] table that fit the current743 ** aLookahead[] transaction. Leave i set to the offset of the hole.744 ** If no holes are found, i is left at p->nAction, which means the745 ** transaction will be appended. */746 i = makeItSafe ? p->mnLookahead : 0;747 for(; i<p->nActionAlloc - p->mxLookahead; i++){748 if( p->aAction[i].lookahead<0 ){749 for(j=0; j<p->nLookahead; j++){750 k = p->aLookahead[j].lookahead - p->mnLookahead + i;751 if( k<0 ) break;752 if( p->aAction[k].lookahead>=0 ) break;753 }754 if( j<p->nLookahead ) continue;755 for(j=0; j<p->nAction; j++){756 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;757 }758 if( j==p->nAction ){759 break; /* Fits in empty slots */760 }761 }762 }763 }764 /* Insert transaction set at index i. */765#if 0766 printf("Acttab:");767 for(j=0; j<p->nLookahead; j++){768 printf(" %d", p->aLookahead[j].lookahead);769 }770 printf(" inserted at %d\n", i);771#endif772 for(j=0; j<p->nLookahead; j++){773 k = p->aLookahead[j].lookahead - p->mnLookahead + i;774 p->aAction[k] = p->aLookahead[j];775 if( k>=p->nAction ) p->nAction = k+1;776 }777 if( makeItSafe && i+p->nterminal>=p->nAction ) p->nAction = i+p->nterminal+1;778 p->nLookahead = 0;779 780 /* Return the offset that is added to the lookahead in order to get the781 ** index into yy_action of the action */782 return i - p->mnLookahead;783}784 785/*786** Return the size of the action table without the trailing syntax error787** entries.788*/789int acttab_action_size(acttab *p){790 int n = p->nAction;791 while( n>0 && p->aAction[n-1].lookahead<0 ){ n--; }792 return n;793}794 795/********************** From the file "build.c" *****************************/796/*797** Routines to construction the finite state machine for the LEMON798** parser generator.799*/800 801/* Find a precedence symbol of every rule in the grammar.802**803** Those rules which have a precedence symbol coded in the input804** grammar using the "[symbol]" construct will already have the805** rp->precsym field filled. Other rules take as their precedence806** symbol the first RHS symbol with a defined precedence. If there807** are not RHS symbols with a defined precedence, the precedence808** symbol field is left blank.809*/810void FindRulePrecedences(struct lemon *xp)811{812 struct rule *rp;813 for(rp=xp->rule; rp; rp=rp->next){814 if( rp->precsym==0 ){815 int i, j;816 for(i=0; i<rp->nrhs && rp->precsym==0; i++){817 struct symbol *sp = rp->rhs[i];818 if( sp->type==MULTITERMINAL ){819 for(j=0; j<sp->nsubsym; j++){820 if( sp->subsym[j]->prec>=0 ){821 rp->precsym = sp->subsym[j];822 break;823 }824 }825 }else if( sp->prec>=0 ){826 rp->precsym = rp->rhs[i];827 }828 }829 }830 }831 return;832}833 834/* Find all nonterminals which will generate the empty string.835** Then go back and compute the first sets of every nonterminal.836** The first set is the set of all terminal symbols which can begin837** a string generated by that nonterminal.838*/839void FindFirstSets(struct lemon *lemp)840{841 int i, j;842 struct rule *rp;843 int progress;844 845 for(i=0; i<lemp->nsymbol; i++){846 lemp->symbols[i]->lambda = LEMON_FALSE;847 }848 for(i=lemp->nterminal; i<lemp->nsymbol; i++){849 lemp->symbols[i]->firstset = SetNew();850 }851 852 /* First compute all lambdas */853 do{854 progress = 0;855 for(rp=lemp->rule; rp; rp=rp->next){856 if( rp->lhs->lambda ) continue;857 for(i=0; i<rp->nrhs; i++){858 struct symbol *sp = rp->rhs[i];859 assert( sp->type==NONTERMINAL || sp->lambda==LEMON_FALSE )((void) sizeof ((sp->type==NONTERMINAL || sp->lambda==LEMON_FALSE
) ? 1 : 0), __extension__ ({ if (sp->type==NONTERMINAL || sp
->lambda==LEMON_FALSE) ; else __assert_fail ("sp->type==NONTERMINAL || sp->lambda==LEMON_FALSE"
, "tools/lemon/lemon.c", 859, __extension__ __PRETTY_FUNCTION__
); }));860 if( sp->lambda==LEMON_FALSE ) break;861 }862 if( i==rp->nrhs ){863 rp->lhs->lambda = LEMON_TRUE;864 progress = 1;865 }866 }867 }while( progress );868 869 /* Now compute all first sets */870 do{871 struct symbol *s1, *s2;872 progress = 0;873 for(rp=lemp->rule; rp; rp=rp->next){874 s1 = rp->lhs;875 for(i=0; i<rp->nrhs; i++){876 s2 = rp->rhs[i];877 if( s2->type==TERMINAL ){878 progress += SetAdd(s1->firstset,s2->index);879 break;880 }else if( s2->type==MULTITERMINAL ){881 for(j=0; j<s2->nsubsym; j++){882 progress += SetAdd(s1->firstset,s2->subsym[j]->index);883 }884 break;885 }else if( s1==s2 ){886 if( s1->lambda==LEMON_FALSE ) break;887 }else{888 progress += SetUnion(s1->firstset,s2->firstset);889 if( s2->lambda==LEMON_FALSE ) break;890 }891 }892 }893 }while( progress );894 return;895}896 897/* Compute all LR(0) states for the grammar. Links898** are added to between some states so that the LR(1) follow sets899** can be computed later.900*/901PRIVATE struct state *getstate(struct lemon *); /* forward reference */902void FindStates(struct lemon *lemp)903{904 struct symbol *sp;905 struct rule *rp;906 907 Configlist_init();908 909 /* Find the start symbol */910 if( lemp->start ){911 sp = Symbol_find(lemp->start);912 if( sp==0 ){913 ErrorMsg(lemp->filename,0,914 "The specified start symbol \"%s\" is not "915 "in a nonterminal of the grammar. \"%s\" will be used as the start "916 "symbol instead.",lemp->start,lemp->startRule->lhs->name);917 lemp->errorcnt++;918 sp = lemp->startRule->lhs;919 }920 }else if( lemp->startRule ){921 sp = lemp->startRule->lhs;922 }else{923 ErrorMsg(lemp->filename,0,"Internal error - no start rule\n");924 exit(1);925 }926 927 /* Make sure the start symbol doesn't occur on the right-hand side of928 ** any rule. Report an error if it does. (YACC would generate a new929 ** start symbol in this case.) */930 for(rp=lemp->rule; rp; rp=rp->next){931 int i;932 for(i=0; i<rp->nrhs; i++){933 if( rp->rhs[i]==sp ){ /* FIX ME: Deal with multiterminals */934 ErrorMsg(lemp->filename,0,935 "The start symbol \"%s\" occurs on the "936 "right-hand side of a rule. This will result in a parser which "937 "does not work properly.",sp->name);938 lemp->errorcnt++;939 }940 }941 }942 943 /* The basis configuration set for the first state944 ** is all rules which have the start symbol as their945 ** left-hand side */946 for(rp=sp->rule; rp; rp=rp->nextlhs){947 struct config *newcfp;948 rp->lhsStart = 1;949 newcfp = Configlist_addbasis(rp,0);950 SetAdd(newcfp->fws,0);951 }952 953 /* Compute the first state. All other states will be954 ** computed automatically during the computation of the first one.955 ** The returned pointer to the first state is not used. */956 (void)getstate(lemp);957 return;958}959 960/* Return a pointer to a state which is described by the configuration961** list which has been built from calls to Configlist_add.962*/963PRIVATE void buildshifts(struct lemon *, struct state *); /* Forwd ref */964PRIVATE struct state *getstate(struct lemon *lemp)965{966 struct config *cfp, *bp;967 struct state *stp;968 969 /* Extract the sorted basis of the new state. The basis was constructed970 ** by prior calls to "Configlist_addbasis()". */971 Configlist_sortbasis();972 bp = Configlist_basis();973 974 /* Get a state with the same basis */975 stp = State_find(bp);976 if( stp ){977 /* A state with the same basis already exists! Copy all the follow-set978 ** propagation links from the state under construction into the979 ** preexisting state, then return a pointer to the preexisting state */980 struct config *x, *y;981 for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){982 Plink_copy(&y->bplp,x->bplp);983 Plink_delete(x->fplp);984 x->fplp = x->bplp = 0;985 }986 cfp = Configlist_return();987 Configlist_eat(cfp);988 }else{989 /* This really is a new state. Construct all the details */990 Configlist_closure(lemp); /* Compute the configuration closure */991 Configlist_sort(); /* Sort the configuration closure */992 cfp = Configlist_return(); /* Get a pointer to the config list */993 stp = State_new(); /* A new state structure */994 MemoryCheck(stp)if((stp)==0){ extern void memory_error(); memory_error(); };995 stp->bp = bp; /* Remember the configuration basis */996 stp->cfp = cfp; /* Remember the configuration closure */997 stp->statenum = lemp->nstate++; /* Every state gets a sequence number */998 stp->ap = 0; /* No actions, yet. */999 State_insert(stp,stp->bp); /* Add to the state table */1000 buildshifts(lemp,stp); /* Recursively compute successor states */1001 }1002 return stp;1003}1004 1005/*1006** Return true if two symbols are the same.1007*/1008int same_symbol(struct symbol *a, struct symbol *b)1009{1010 int i;1011 if( a==b ) return 1;1012 if( a->type!=MULTITERMINAL ) return 0;1013 if( b->type!=MULTITERMINAL ) return 0;1014 if( a->nsubsym!=b->nsubsym ) return 0;1015 for(i=0; i<a->nsubsym; i++){1016 if( a->subsym[i]!=b->subsym[i] ) return 0;1017 }1018 return 1;1019}1020 1021/* Construct all successor states to the given state. A "successor"1022** state is any state which can be reached by a shift action.1023*/1024PRIVATE void buildshifts(struct lemon *lemp, struct state *stp)1025{1026 struct config *cfp; /* For looping thru the config closure of "stp" */1027 struct config *bcfp; /* For the inner loop on config closure of "stp" */1028 struct config *newcfg; /* */1029 struct symbol *sp; /* Symbol following the dot in configuration "cfp" */1030 struct symbol *bsp; /* Symbol following the dot in configuration "bcfp" */1031 struct state *newstp; /* A pointer to a successor state */1032 1033 /* Each configuration becomes complete after it contributes to a successor1034 ** state. Initially, all configurations are incomplete */1035 for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;1036 1037 /* Loop through all configurations of the state "stp" */1038 for(cfp=stp->cfp; cfp; cfp=cfp->next){1039 if( cfp->status==COMPLETE ) continue; /* Already used by inner loop */1040 if( cfp->dot>=cfp->rp->nrhs ) continue; /* Can't shift this config */1041 Configlist_reset(); /* Reset the new config set */1042 sp = cfp->rp->rhs[cfp->dot]; /* Symbol after the dot */1043 1044 /* For every configuration in the state "stp" which has the symbol "sp"1045 ** following its dot, add the same configuration to the basis set under1046 ** construction but with the dot shifted one symbol to the right. */1047 for(bcfp=cfp; bcfp; bcfp=bcfp->next){1048 if( bcfp->status==COMPLETE ) continue; /* Already used */1049 if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */1050 bsp = bcfp->rp->rhs[bcfp->dot]; /* Get symbol after dot */1051 if( !same_symbol(bsp,sp) ) continue; /* Must be same as for "cfp" */1052 bcfp->status = COMPLETE; /* Mark this config as used */1053 newcfg = Configlist_addbasis(bcfp->rp,bcfp->dot+1);1054 Plink_add(&newcfg->bplp,bcfp);1055 }1056 1057 /* Get a pointer to the state described by the basis configuration set1058 ** constructed in the preceding loop */1059 newstp = getstate(lemp);1060 1061 /* The state "newstp" is reached from the state "stp" by a shift action1062 ** on the symbol "sp" */1063 if( sp->type==MULTITERMINAL ){1064 int i;1065 for(i=0; i<sp->nsubsym; i++){1066 Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);1067 }1068 }else{1069 Action_add(&stp->ap,SHIFT,sp,(char *)newstp);1070 }1071 }1072}1073 1074/*1075** Construct the propagation links1076*/1077void FindLinks(struct lemon *lemp)1078{1079 int i;1080 struct config *cfp, *other;1081 struct state *stp;1082 struct plink *plp;1083 1084 /* Housekeeping detail:1085 ** Add to every propagate link a pointer back to the state to1086 ** which the link is attached. */1087 for(i=0; i<lemp->nstate; i++){1088 stp = lemp->sorted[i];1089 for(cfp=stp?stp->cfp:0; cfp; cfp=cfp->next){1090 cfp->stp = stp;1091 }1092 }1093 1094 /* Convert all backlinks into forward links. Only the forward1095 ** links are used in the follow-set computation. */1096 for(i=0; i<lemp->nstate; i++){1097 stp = lemp->sorted[i];1098 for(cfp=stp?stp->cfp:0; cfp; cfp=cfp->next){1099 for(plp=cfp->bplp; plp; plp=plp->next){1100 other = plp->cfp;1101 Plink_add(&other->fplp,cfp);1102 }1103 }1104 }1105}1106 1107/* Compute all followsets.1108**1109** A followset is the set of all symbols which can come immediately1110** after a configuration.1111*/1112void FindFollowSets(struct lemon *lemp)1113{1114 int i;1115 struct config *cfp;1116 struct plink *plp;1117 int progress;1118 int change;1119 1120 for(i=0; i<lemp->nstate; i++){1121 assert( lemp->sorted[i]!=0 )((void) sizeof ((lemp->sorted[i]!=0) ? 1 : 0), __extension__
({ if (lemp->sorted[i]!=0) ; else __assert_fail ("lemp->sorted[i]!=0"
, "tools/lemon/lemon.c", 1121, __extension__ __PRETTY_FUNCTION__
); }));1122 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){1123 cfp->status = INCOMPLETE;1124 }1125 }1126 1127 do{1128 progress = 0;1129 for(i=0; i<lemp->nstate; i++){1130 assert( lemp->sorted[i]!=0 )((void) sizeof ((lemp->sorted[i]!=0) ? 1 : 0), __extension__
({ if (lemp->sorted[i]!=0) ; else __assert_fail ("lemp->sorted[i]!=0"
, "tools/lemon/lemon.c", 1130, __extension__ __PRETTY_FUNCTION__
); }));1131 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){1132 if( cfp->status==COMPLETE ) continue;1133 for(plp=cfp->fplp; plp; plp=plp->next){1134 change = SetUnion(plp->cfp->fws,cfp->fws);1135 if( change ){1136 plp->cfp->status = INCOMPLETE;1137 progress = 1;1138 }1139 }1140 cfp->status = COMPLETE;1141 }1142 }1143 }while( progress );1144}1145 1146static int resolve_conflict(struct action *,struct action *);1147 1148/* Compute the reduce actions, and resolve conflicts.1149*/1150void FindActions(struct lemon *lemp)1151{1152 int i,j;1153 struct config *cfp;1154 struct state *stp;1155 struct symbol *sp;1156 struct rule *rp;1157 1158 /* Add all of the reduce actions1159 ** A reduce action is added for each element of the followset of1160 ** a configuration which has its dot at the extreme right.1161 */1162 for(i=0; i<lemp->nstate; i++){ /* Loop over all states */1163 stp = lemp->sorted[i];1164 for(cfp=stp->cfp; cfp; cfp=cfp->next){ /* Loop over all configurations */1165 if( cfp->rp->nrhs==cfp->dot ){ /* Is dot at extreme right? */1166 for(j=0; j<lemp->nterminal; j++){1167 if( SetFind(cfp->fws,j)(cfp->fws[j]) ){1168 /* Add a reduce action to the state "stp" which will reduce by the1169 ** rule "cfp->rp" if the lookahead symbol is "lemp->symbols[j]" */1170 Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);1171 }1172 }1173 }1174 }1175 }1176 1177 /* Add the accepting token */1178 if( lemp->start ){1179 sp = Symbol_find(lemp->start);1180 if( sp==0 ){1181 if( lemp->startRule==0 ){1182 fprintf(stderrstderr, "internal error on source line %d: no start rule\n",1183 __LINE__1183);1184 exit(1);1185 }1186 sp = lemp->startRule->lhs;1187 }1188 }else{1189 sp = lemp->startRule->lhs;1190 }1191 /* Add to the first state (which is always the starting state of the1192 ** finite state machine) an action to ACCEPT if the lookahead is the1193 ** start nonterminal. */1194 Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);1195 1196 /* Resolve conflicts */1197 for(i=0; i<lemp->nstate; i++){1198 struct action *ap, *nap;1199 stp = lemp->sorted[i];1200 /* assert( stp->ap ); */1201 stp->ap = Action_sort(stp->ap);1202 for(ap=stp->ap; ap && ap->next; ap=ap->next){1203 for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){1204 /* The two actions "ap" and "nap" have the same lookahead.1205 ** Figure out which one should be used */1206 lemp->nconflict += resolve_conflict(ap,nap);1207 }1208 }1209 }1210 1211 /* Report an error for each rule that can never be reduced. */1212 for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = LEMON_FALSE;1213 for(i=0; i<lemp->nstate; i++){1214 struct action *ap;1215 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){1216 if( ap->type==REDUCE ) ap->x.rp->canReduce = LEMON_TRUE;1217 }1218 }1219 for(rp=lemp->rule; rp; rp=rp->next){1220 if( rp->canReduce ) continue;1221 ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");1222 lemp->errorcnt++;1223 }1224}1225 1226/* Resolve a conflict between the two given actions. If the1227** conflict can't be resolved, return non-zero.1228**1229** NO LONGER TRUE:1230** To resolve a conflict, first look to see if either action1231** is on an error rule. In that case, take the action which1232** is not associated with the error rule. If neither or both1233** actions are associated with an error rule, then try to1234** use precedence to resolve the conflict.1235**1236** If either action is a SHIFT, then it must be apx. This1237** function won't work if apx->type==REDUCE and apy->type==SHIFT.1238*/1239static int resolve_conflict(1240 struct action *apx,1241 struct action *apy1242){1243 struct symbol *spx, *spy;1244 int errcnt = 0;1245 assert( apx->sp==apy->sp )((void) sizeof ((apx->sp==apy->sp) ? 1 : 0), __extension__
({ if (apx->sp==apy->sp) ; else __assert_fail ("apx->sp==apy->sp"
, "tools/lemon/lemon.c", 1245, __extension__ __PRETTY_FUNCTION__
); })); /* Otherwise there would be no conflict */1246 if( apx->type==SHIFT && apy->type==SHIFT ){1247 apy->type = SSCONFLICT;1248 errcnt++;1249 }1250 if( apx->type==SHIFT && apy->type==REDUCE ){1251 spx = apx->sp;1252 spy = apy->x.rp->precsym;1253 if( spy==0 || spx->prec<0 || spy->prec<0 ){1254 /* Not enough precedence information. */1255 apy->type = SRCONFLICT;1256 errcnt++;1257 }else if( spx->prec>spy->prec ){ /* higher precedence wins */1258 apy->type = RD_RESOLVED;1259 }else if( spx->prec<spy->prec ){1260 apx->type = SH_RESOLVED;1261 }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){ /* Use operator */1262 apy->type = RD_RESOLVED; /* associativity */1263 }else if( spx->prec==spy->prec && spx->assoc==LEFT ){ /* to break tie */1264 apx->type = SH_RESOLVED;1265 }else{1266 assert( spx->prec==spy->prec && spx->assoc==NONE )((void) sizeof ((spx->prec==spy->prec && spx->
assoc==NONE) ? 1 : 0), __extension__ ({ if (spx->prec==spy
->prec && spx->assoc==NONE) ; else __assert_fail
("spx->prec==spy->prec && spx->assoc==NONE"
, "tools/lemon/lemon.c", 1266, __extension__ __PRETTY_FUNCTION__
); }));1267 apx->type = ERROR;1268 }1269 }else if( apx->type==REDUCE && apy->type==REDUCE ){1270 spx = apx->x.rp->precsym;1271 spy = apy->x.rp->precsym;1272 if( spx==0 || spy==0 || spx->prec<0 ||1273 spy->prec<0 || spx->prec==spy->prec ){1274 apy->type = RRCONFLICT;1275 errcnt++;1276 }else if( spx->prec>spy->prec ){1277 apy->type = RD_RESOLVED;1278 }else if( spx->prec<spy->prec ){1279 apx->type = RD_RESOLVED;1280 }1281 }else{1282 assert(((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1283 apx->type==SH_RESOLVED ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1284 apx->type==RD_RESOLVED ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1285 apx->type==SSCONFLICT ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1286 apx->type==SRCONFLICT ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1287 apx->type==RRCONFLICT ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1288 apy->type==SH_RESOLVED ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1289 apy->type==RD_RESOLVED ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1290 apy->type==SSCONFLICT ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1291 apy->type==SRCONFLICT ||((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1292 apy->type==RRCONFLICT((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }))1293 )((void) sizeof ((apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ? 1 : 0), __extension__
({ if (apx->type==SH_RESOLVED || apx->type==RD_RESOLVED
|| apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx
->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->
type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type
==SRCONFLICT || apy->type==RRCONFLICT) ; else __assert_fail
("apx->type==SH_RESOLVED || apx->type==RD_RESOLVED || apx->type==SSCONFLICT || apx->type==SRCONFLICT || apx->type==RRCONFLICT || apy->type==SH_RESOLVED || apy->type==RD_RESOLVED || apy->type==SSCONFLICT || apy->type==SRCONFLICT || apy->type==RRCONFLICT"
, "tools/lemon/lemon.c", 1293, __extension__ __PRETTY_FUNCTION__
); }));1294 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before1295 ** REDUCEs on the list. If we reach this point it must be because1296 ** the parser conflict had already been resolved. */1297 }1298 return errcnt;1299}1300/********************* From the file "configlist.c" *************************/1301/*1302** Routines to processing a configuration list and building a state1303** in the LEMON parser generator.1304*/1305 1306static struct config *freelist = 0; /* List of free configurations */1307static struct config *current = 0; /* Top of list of configurations */1308static struct config **currentend = 0; /* Last on list of configs */1309static struct config *basis = 0; /* Top of list of basis configs */1310static struct config **basisend = 0; /* End of list of basis configs */1311 1312/* Return a pointer to a new configuration */1313PRIVATE struct config *newconfig(void){1314 return (struct config*)calloc(1, sizeof(struct config));1315}1316 1317/* The configuration "old" is no longer used */1318PRIVATE void deleteconfig(struct config *old)1319{1320 old->next = freelist;1321 freelist = old;1322}1323 1324/* Initialized the configuration list builder */1325void Configlist_init(void){1326 current = 0;1327 currentend = &current;1328 basis = 0;1329 basisend = &basis;1330 Configtable_init();1331 return;1332}1333 1334/* Initialized the configuration list builder */1335void Configlist_reset(void){1336 current = 0;1337 currentend = &current;1338 basis = 0;1339 basisend = &basis;1340 Configtable_clear(0);1341 return;1342}1343 1344/* Add another configuration to the configuration list */1345struct config *Configlist_add(1346 struct rule *rp, /* The rule */1347 int dot /* Index into the RHS of the rule where the dot goes */1348){1349 struct config *cfp, model;1350 1351 assert( currentend!=0 )((void) sizeof ((currentend!=0) ? 1 : 0), __extension__ ({ if
(currentend!=0) ; else __assert_fail ("currentend!=0", "tools/lemon/lemon.c"
, 1351, __extension__ __PRETTY_FUNCTION__); }));1352 model.rp = rp;1353 model.dot = dot;1354 cfp = Configtable_find(&model);1355 if( cfp==0 ){1356 cfp = newconfig();1357 cfp->rp = rp;1358 cfp->dot = dot;1359 cfp->fws = SetNew();1360 cfp->stp = 0;1361 cfp->fplp = cfp->bplp = 0;1362 cfp->next = 0;1363 cfp->bp = 0;1364 *currentend = cfp;1365 currentend = &cfp->next;1366 Configtable_insert(cfp);1367 }1368 return cfp;1369}1370 1371/* Add a basis configuration to the configuration list */1372struct config *Configlist_addbasis(struct rule *rp, int dot)1373{1374 struct config *cfp, model;1375 1376 assert( basisend!=0 )((void) sizeof ((basisend!=0) ? 1 : 0), __extension__ ({ if (
basisend!=0) ; else __assert_fail ("basisend!=0", "tools/lemon/lemon.c"
, 1376, __extension__ __PRETTY_FUNCTION__); }));1377 assert( currentend!=0 )((void) sizeof ((currentend!=0) ? 1 : 0), __extension__ ({ if
(currentend!=0) ; else __assert_fail ("currentend!=0", "tools/lemon/lemon.c"
, 1377, __extension__ __PRETTY_FUNCTION__); }));1378 model.rp = rp;1379 model.dot = dot;1380 cfp = Configtable_find(&model);1381 if( cfp==0 ){1382 cfp = newconfig();1383 cfp->rp = rp;1384 cfp->dot = dot;1385 cfp->fws = SetNew();1386 cfp->stp = 0;1387 cfp->fplp = cfp->bplp = 0;1388 cfp->next = 0;1389 cfp->bp = 0;1390 *currentend = cfp;1391 currentend = &cfp->next;1392 *basisend = cfp;1393 basisend = &cfp->bp;1394 Configtable_insert(cfp);1395 }1396 return cfp;1397}1398 1399/* Compute the closure of the configuration list */1400void Configlist_closure(struct lemon *lemp)1401{1402 struct config *cfp, *newcfp;1403 struct rule *rp, *newrp;1404 struct symbol *sp, *xsp;1405 int i, dot;1406 1407 assert( currentend!=0 )((void) sizeof ((currentend!=0) ? 1 : 0), __extension__ ({ if
(currentend!=0) ; else __assert_fail ("currentend!=0", "tools/lemon/lemon.c"
, 1407, __extension__ __PRETTY_FUNCTION__); }));1408 for(cfp=current; cfp; cfp=cfp->next){1409 rp = cfp->rp;1410 dot = cfp->dot;1411 if( dot>=rp->nrhs ) continue;1412 sp = rp->rhs[dot];1413 if( sp->type==NONTERMINAL ){1414 if( sp->rule==0 && sp!=lemp->errsym ){1415 ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",1416 sp->name);1417 lemp->errorcnt++;1418 }1419 for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){1420 newcfp = Configlist_add(newrp,0);1421 for(i=dot+1; i<rp->nrhs; i++){1422 xsp = rp->rhs[i];1423 if( xsp->type==TERMINAL ){1424 SetAdd(newcfp->fws,xsp->index);1425 break;1426 }else if( xsp->type==MULTITERMINAL ){1427 int k;1428 for(k=0; k<xsp->nsubsym; k++){1429 SetAdd(newcfp->fws, xsp->subsym[k]->index);1430 }1431 break;1432 }else{1433 SetUnion(newcfp->fws,xsp->firstset);1434 if( xsp->lambda==LEMON_FALSE ) break;1435 }1436 }1437 if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);1438 }1439 }1440 }1441 return;1442}1443 1444/* Sort the configuration list */1445void Configlist_sort(void){1446 current = (struct config*)msort((char*)current,(char**)&(current->next),1447 Configcmp);1448 currentend = 0;1449 return;1450}1451 1452/* Sort the basis configuration list */1453void Configlist_sortbasis(void){1454 basis = (struct config*)msort((char*)current,(char**)&(current->bp),1455 Configcmp);1456 basisend = 0;1457 return;1458}1459 1460/* Return a pointer to the head of the configuration list and1461** reset the list */1462struct config *Configlist_return(void){1463 struct config *old;1464 old = current;1465 current = 0;1466 currentend = 0;1467 return old;1468}1469 1470/* Return a pointer to the head of the configuration list and1471** reset the list */1472struct config *Configlist_basis(void){1473 struct config *old;1474 old = basis;1475 basis = 0;1476 basisend = 0;1477 return old;1478}1479 1480/* Free all elements of the given configuration list */1481void Configlist_eat(struct config *cfp)1482{1483 struct config *nextcfp;1484 for(; cfp; cfp=nextcfp){1485 nextcfp = cfp->next;1486 assert( cfp->fplp==0 )((void) sizeof ((cfp->fplp==0) ? 1 : 0), __extension__ ({ if
(cfp->fplp==0) ; else __assert_fail ("cfp->fplp==0", "tools/lemon/lemon.c"
, 1486, __extension__ __PRETTY_FUNCTION__); }));1487 assert( cfp->bplp==0 )((void) sizeof ((cfp->bplp==0) ? 1 : 0), __extension__ ({ if
(cfp->bplp==0) ; else __assert_fail ("cfp->bplp==0", "tools/lemon/lemon.c"
, 1487, __extension__ __PRETTY_FUNCTION__); }));1488 if( cfp->fws ) SetFree(cfp->fws);1489 deleteconfig(cfp);1490 }1491 return;1492}1493/***************** From the file "error.c" *********************************/1494/*1495** Code for printing error message.1496*/1497 1498void ErrorMsg(const char *filename, int lineno, const char *format, ...){1499 va_list ap;1500 fprintf(stderrstderr, "%s:%d: ", filename, lineno);1501 va_start(ap, format)__builtin_va_start(ap, format);1502 vfprintf(stderrstderr,format,ap);1503 va_end(ap)__builtin_va_end(ap);1504 fprintf(stderrstderr, "\n");1505}1506/**************** From the file "main.c" ************************************/1507/*1508** Main program file for the LEMON parser generator.1509*/1510 1511/* Report an out-of-memory condition and abort. This function1512** is used mostly by the "MemoryCheck" macro in struct.h1513*/1514void memory_error(void){1515 fprintf(stderrstderr,"Out of memory. Aborting...\n");1516 exit(1);1517}1518 1519static int nDefine = 0; /* Number of -D options on the command line */1520static char **azDefine = 0; /* Name of the -D macros */1521 1522/* This routine is called with the argument to each -D command-line option.1523** Add the macro defined to the azDefine array.1524*/1525static void handle_D_option(char *z){1526 char **paz;1527 nDefine++;1528 azDefine = (char **) realloc(azDefine, sizeof(azDefine[0])*nDefine);1529 if( azDefine==0 ){1530 fprintf(stderrstderr,"out of memory\n");1531 exit(1);1532 }1533 paz = &azDefine[nDefine-1];1534 *paz = (char *) malloc( lemonStrlen(z)((int)strlen(z))+1 );1535 if( *paz==0 ){1536 fprintf(stderrstderr,"out of memory\n");1537 exit(1);1538 }1539 lemon_strcpy(*paz, z);1540 for(z=*paz; *z && *z!='='; z++){}1541 *z = 0;1542}1543 1544/* Rember the name of the output directory1545*/1546static char *outputDir = NULL((void*)0);1547static void handle_d_option(char *z){1548 outputDir = (char *) malloc( lemonStrlen(z)((int)strlen(z))+1 );1549 if( outputDir==0 ){1550 fprintf(stderrstderr,"out of memory\n");1551 exit(1);1552 }1553 lemon_strcpy(outputDir, z);1554}1555 1556static char *user_templatename = NULL((void*)0);1557static void handle_T_option(char *z){1558 user_templatename = (char *) malloc( lemonStrlen(z)((int)strlen(z))+1 );1559 if( user_templatename==0 ){1560 memory_error();1561 }1562 lemon_strcpy(user_templatename, z);1563}1564 1565/* Merge together to lists of rules ordered by rule.iRule */1566static struct rule *Rule_merge(struct rule *pA, struct rule *pB){1567 struct rule *pFirst = 0;1568 struct rule **ppPrev = &pFirst;1569 while( pA && pB ){1570 if( pA->iRule<pB->iRule ){1571 *ppPrev = pA;1572 ppPrev = &pA->next;1573 pA = pA->next;1574 }else{1575 *ppPrev = pB;1576 ppPrev = &pB->next;1577 pB = pB->next;1578 }1579 }1580 if( pA ){1581 *ppPrev = pA;1582 }else{1583 *ppPrev = pB;1584 }1585 return pFirst;1586}1587 1588/*1589** Sort a list of rules in order of increasing iRule value1590*/1591static struct rule *Rule_sort(struct rule *rp){1592 unsigned int i;1593 struct rule *pNext;1594 struct rule *x[32];1595 memset(x, 0, sizeof(x));1596 while( rp ){1597 pNext = rp->next;1598 rp->next = 0;1599 for(i=0; i<sizeof(x)/sizeof(x[0])-1 && x[i]; i++){1600 rp = Rule_merge(x[i], rp);1601 x[i] = 0;1602 }1603 x[i] = rp;1604 rp = pNext;1605 }1606 rp = 0;1607 for(i=0; i<sizeof(x)/sizeof(x[0]); i++){1608 rp = Rule_merge(x[i], rp);1609 }1610 return rp;1611}1612 1613/* forward reference */1614static const char *minimum_size_type(int lwr, int upr, int *pnByte);1615 1616/* Print a single line of the "Parser Stats" output1617*/1618static void stats_line(const char *zLabel, int iValue){1619 int nLabel = lemonStrlen(zLabel)((int)strlen(zLabel));1620 printf(" %s%.*s %5d\n", zLabel,1621 35-nLabel, "................................",1622 iValue);1623}1624 1625/* The main program. Parse the command line and do it... */1626int main(int argc, char **argv){1627 static int version = 0;1628 static int rpflag = 0;1629 static int basisflag = 0;1630 static int compress = 0;1631 static int quiet = 0;1632 static int statistics = 0;1633 static int mhflag = 0;1634 static int nolinenosflag = 0;1635 static int noResort = 0;1636 static int sqlFlag = 0;1637 static int printPP = 0;1638 1639 static struct s_options options[] = {1640 {OPT_FLAG, "b", (char*)&basisflag, "Print only the basis in report."},1641 {OPT_FLAG, "c", (char*)&compress, "Don't compress the action table."},1642 {OPT_FSTR, "d", (char*)&handle_d_option, "Output directory. Default '.'"},1643 {OPT_FSTR, "D", (char*)handle_D_option, "Define an %ifdef macro."},1644 {OPT_FLAG, "E", (char*)&printPP, "Print input file after preprocessing."},1645 {OPT_FSTR, "f", 0, "Ignored. (Placeholder for -f compiler options.)"},1646 {OPT_FLAG, "g", (char*)&rpflag, "Print grammar without actions."},1647 {OPT_FSTR, "I", 0, "Ignored. (Placeholder for '-I' compiler options.)"},1648 {OPT_FLAG, "m", (char*)&mhflag, "Output a makeheaders compatible file."},1649 {OPT_FLAG, "l", (char*)&nolinenosflag, "Do not print #line statements."},1650 {OPT_FSTR, "O", 0, "Ignored. (Placeholder for '-O' compiler options.)"},1651 {OPT_FLAG, "p", (char*)&showPrecedenceConflict,1652 "Show conflicts resolved by precedence rules"},1653 {OPT_FLAG, "q", (char*)&quiet, "(Quiet) Don't print the report file."},1654 {OPT_FLAG, "r", (char*)&noResort, "Do not sort or renumber states"},1655 {OPT_FLAG, "s", (char*)&statistics,1656 "Print parser stats to standard output."},1657 {OPT_FLAG, "S", (char*)&sqlFlag,1658 "Generate the *.sql file describing the parser tables."},1659 {OPT_FLAG, "x", (char*)&version, "Print the version number."},1660 {OPT_FSTR, "T", (char*)handle_T_option, "Specify a template file."},1661 {OPT_FSTR, "W", 0, "Ignored. (Placeholder for '-W' compiler options.)"},1662 {OPT_FLAG,0,0,0}1663 };1664 int i;1665 int exitcode;1666 struct lemon lem;1667 struct rule *rp;1668 1669 (void)argc;1670 OptInit(argv,options,stderrstderr);1671 if( version

0.1	'version' is 0

){1672 printf("Lemon version 1.0\n");1673 exit(0);1674 }1675 if( OptNArgs()!=1 ){1676 fprintf(stderrstderr,"Exactly one filename argument is required.\n");1677 exit(1);1678 }1679 memset(&lem, 0, sizeof(lem));1680 lem.errorcnt = 0;1681 1682 /* Initialize the machine */1683 Strsafe_init();1684 Symbol_init();1685 State_init();1686 lem.argv0 = argv[0];1687 lem.filename = OptArg(0);1688 lem.basisflag = basisflag;1689 lem.nolinenosflag = nolinenosflag;1690 lem.printPreprocessed = printPP;1691 Symbol_new("$");1692 1693 /* Parse the input file */1694 Parse(&lem);1695 if( lem.printPreprocessed || lem.errorcnt ) exit(lem.errorcnt);1696 if( lem.nrule==0 ){1697 fprintf(stderrstderr,"Empty grammar.\n");1698 exit(1);1699 }1700 lem.errsym = Symbol_find("error");1701 1702 /* Count and index the symbols of the grammar */1703 Symbol_new("{default}");1704 lem.nsymbol = Symbol_count();1705 lem.symbols = Symbol_arrayof();1706 for(i=0; i

8.1	'i' is >= field 'nsymbol'

<lem.nsymbol; i++) lem.symbols[i]->index = i;1707 qsort(lem.symbols,lem.nsymbol,sizeof(struct symbol*), Symbolcmpp);1708 for(i=0; i

9.1	'i' is >= field 'nsymbol'

<lem.nsymbol; i++) lem.symbols[i]->index = i;1709 while( lem.symbols[i-1]->type==MULTITERMINAL ){ i--; }1710 assert( strcmp(lem.symbols[i-1]->name,"{default}")==0 )((void) sizeof ((strcmp(lem.symbols[i-1]->name,"{default}"
)==0) ? 1 : 0), __extension__ ({ if (strcmp(lem.symbols[i-1]->
name,"{default}")==0) ; else __assert_fail ("strcmp(lem.symbols[i-1]->name,\"{default}\")==0"
, "tools/lemon/lemon.c", 1710, __extension__ __PRETTY_FUNCTION__
); }));1711 lem.nsymbol = i - 1;1712 for(i=1; ISUPPER(lem.symbols[i]->name[0])((*__ctype_b_loc ())[(int) (((unsigned char)(lem.symbols[i]->
name[0])))] & (unsigned short int) _ISupper); i++);1713 lem.nterminal = i;1714 1715 /* Assign sequential rule numbers. Start with 0. Put rules that have no1716 ** reduce action C-code associated with them last, so that the switch()1717 ** statement that selects reduction actions will have a smaller jump table.1718 */1719 for(i=0, rp=lem.rule; rp; rp=rp->next){1720 rp->iRule = rp->code ? i++ : -1;1721 }1722 lem.nruleWithAction = i;1723 for(rp=lem.rule; rp; rp=rp->next){1724 if( rp->iRule<0 ) rp->iRule = i++;1725 }1726 lem.startRule = lem.rule;1727 lem.rule = Rule_sort(lem.rule);1728 1729 /* Generate a reprint of the grammar, if requested on the command line */1730 if( rpflag ){1731 Reprint(&lem);1732 }else{1733 /* Initialize the size for all follow and first sets */1734 SetSize(lem.nterminal+1);1735 1736 /* Find the precedence for every production rule (that has one) */1737 FindRulePrecedences(&lem);1738 1739 /* Compute the lambda-nonterminals and the first-sets for every1740 ** nonterminal */1741 FindFirstSets(&lem);1742 1743 /* Compute all LR(0) states. Also record follow-set propagation1744 ** links so that the follow-set can be computed later */1745 lem.nstate = 0;1746 FindStates(&lem);1747 lem.sorted = State_arrayof();1748 1749 /* Tie up loose ends on the propagation links */1750 FindLinks(&lem);1751 1752 /* Compute the follow set of every reducible configuration */1753 FindFollowSets(&lem);1754 1755 /* Compute the action tables */1756 FindActions(&lem);1757 1758 /* Compress the action tables */1759 if( compress==0 ) CompressTables(&lem);1760 1761 /* Reorder and renumber the states so that states with fewer choices1762 ** occur at the end. This is an optimization that helps make the1763 ** generated parser tables smaller. */1764 if( noResort==0 ) ResortStates(&lem);1765 1766 /* Generate a report of the parser generated. (the "y.output" file) */1767 if( !quiet ) ReportOutput(&lem);1768 1769 /* Generate the source code for the parser */1770 ReportTable(&lem, mhflag, sqlFlag);1771 1772 /* Produce a header file for use by the scanner. (This step is1773 ** omitted if the "-m" option is used because makeheaders will1774 ** generate the file for us.) */1775 if( !mhflag ) ReportHeader(&lem);1776 }1777 if( statistics ){1778 printf("Parser statistics:\n");1779 stats_line("terminal symbols", lem.nterminal);1780 stats_line("non-terminal symbols", lem.nsymbol - lem.nterminal);1781 stats_line("total symbols", lem.nsymbol);1782 stats_line("rules", lem.nrule);1783 stats_line("states", lem.nxstate);1784 stats_line("conflicts", lem.nconflict);1785 stats_line("action table entries", lem.nactiontab);1786 stats_line("lookahead table entries", lem.nlookaheadtab);1787 stats_line("total table size (bytes)", lem.tablesize);1788 }1789 if( lem.nconflict > 0 ){1790 fprintf(stderrstderr,"%d parsing conflicts.\n",lem.nconflict);1791 }1792 1793 /* return 0 on success, 1 on failure. */1794 exitcode = ((lem.errorcnt > 0) || (lem.nconflict > 0)) ? 1 : 0;1795 exit(exitcode);1796 return (exitcode);1797}1798/******************** From the file "msort.c" *******************************/1799/*1800** A generic merge-sort program.1801**1802** USAGE:1803** Let "ptr" be a pointer to some structure which is at the head of1804** a null-terminated list. Then to sort the list call:1805**1806** ptr = msort(ptr,&(ptr->next),cmpfnc);1807**1808** In the above, "cmpfnc" is a pointer to a function which compares1809** two instances of the structure and returns an integer, as in1810** strcmp. The second argument is a pointer to the pointer to the1811** second element of the linked list. This address is used to compute1812** the offset to the "next" field within the structure. The offset to1813** the "next" field must be constant for all structures in the list.1814**1815** The function returns a new pointer which is the head of the list1816** after sorting.1817**1818** ALGORITHM:1819** Merge-sort.1820*/1821 1822/*1823** Return a pointer to the next structure in the linked list.1824*/1825#define NEXT(A)(*(char**)(((char*)A)+offset)) (*(char**)(((char*)A)+offset))1826 1827/*1828** Inputs:1829** a: A sorted, null-terminated linked list. (May be null).1830** b: A sorted, null-terminated linked list. (May be null).1831** cmp: A pointer to the comparison function.1832** offset: Offset in the structure to the "next" field.1833**1834** Return Value:1835** A pointer to the head of a sorted list containing the elements1836** of both a and b.1837**1838** Side effects:1839** The "next" pointers for elements in the lists a and b are1840** changed.1841*/1842static char *merge(1843 char *a,1844 char *b,1845 int (*cmp)(const char*,const char*),1846 int offset1847){1848 char *ptr, *head;1849 1850 if( a==0 ){1851 head = b;1852 }else if( b==0 ){1853 head = a;1854 }else{1855 if( (*cmp)(a,b)<=0 ){1856 ptr = a;1857 a = NEXT(a)(*(char**)(((char*)a)+offset));1858 }else{1859 ptr = b;1860 b = NEXT(b)(*(char**)(((char*)b)+offset));1861 }1862 head = ptr;1863 while( a && b ){1864 if( (*cmp)(a,b)<=0 ){1865 NEXT(ptr)(*(char**)(((char*)ptr)+offset)) = a;1866 ptr = a;1867 a = NEXT(a)(*(char**)(((char*)a)+offset));1868 }else{1869 NEXT(ptr)(*(char**)(((char*)ptr)+offset)) = b;1870 ptr = b;1871 b = NEXT(b)(*(char**)(((char*)b)+offset));1872 }1873 }1874 if( a ) NEXT(ptr)(*(char**)(((char*)ptr)+offset)) = a;1875 else NEXT(ptr)(*(char**)(((char*)ptr)+offset)) = b;1876 }1877 return head;1878}1879 1880/*1881** Inputs:1882** list: Pointer to a singly-linked list of structures.1883** next: Pointer to pointer to the second element of the list.1884** cmp: A comparison function.1885**1886** Return Value:1887** A pointer to the head of a sorted list containing the elements1888** originally in list.1889**1890** Side effects:1891** The "next" pointers for elements in list are changed.1892*/1893#define LISTSIZE30 301894static char *msort(1895 char *list,1896 char **next,1897 int (*cmp)(const char*,const char*)1898){1899 unsigned long offset;1900 char *ep;1901 char *set[LISTSIZE30];1902 int i;1903 offset = (unsigned long)((char*)next - (char*)list);1904 for(i=0; i<LISTSIZE30; i++) set[i] = 0;1905 while( list ){1906 ep = list;1907 list = NEXT(list)(*(char**)(((char*)list)+offset));1908 NEXT(ep)(*(char**)(((char*)ep)+offset)) = 0;1909 for(i=0; i<LISTSIZE30-1 && set[i]!=0; i++){1910 ep = merge(ep,set[i],cmp,offset);1911 set[i] = 0;1912 }1913 set[i] = ep;1914 }1915 ep = 0;1916 for(i=0; i<LISTSIZE30; i++) if( set[i] ) ep = merge(set[i],ep,cmp,offset);1917 return ep;1918}1919/************************ From the file "option.c" **************************/1920static char **g_argv;1921static struct s_options *op;1922static FILE *errstream;1923 1924#define ISOPT(X)((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)1925 1926/*1927** Print the command line with a carrot pointing to the k-th character1928** of the n-th field.1929*/1930static void errline(int n, int k, FILE *err)1931{1932 int spcnt, i;1933 if( g_argv[0] ){1934 fprintf(err,"%s",g_argv[0]);1935 spcnt = lemonStrlen(g_argv[0])((int)strlen(g_argv[0])) + 1;1936 }else{1937 spcnt = 0;1938 }1939 for(i=1; i<n && g_argv[i]; i++){1940 fprintf(err," %s",g_argv[i]);1941 spcnt += lemonStrlen(g_argv[i])((int)strlen(g_argv[i]))+1;1942 }1943 spcnt += k;1944 for(; g_argv[i]; i++) fprintf(err," %s",g_argv[i]);1945 if( spcnt<20 ){1946 fprintf(err,"\n%*s^-- here\n",spcnt,"");1947 }else{1948 fprintf(err,"\n%*shere --^\n",spcnt-7,"");1949 }1950}1951 1952/*1953** Return the index of the N-th non-switch argument. Return -11954** if N is out of range.1955*/1956static int argindex(int n)1957{1958 int i;1959 int dashdash = 0;1960 if( g_argv!=0 && *g_argv!=0 ){1961 for(i=1; g_argv[i]; i++){1962 if( dashdash || !ISOPT(g_argv[i])((g_argv[i])[0]=='-'||(g_argv[i])[0]=='+'||strchr((g_argv[i])
,'=')!=0) ){1963 if( n==0 ) return i;1964 n--;1965 }1966 if( strcmp(g_argv[i],"--")==0 ) dashdash = 1;1967 }1968 }1969 return -1;1970}1971 1972static char emsg[] = "Command line syntax error: ";1973 1974/*1975** Process a flag command line argument.1976*/1977static int handleflags(int i, FILE *err)1978{1979 int v;1980 int errcnt = 0;1981 int j;1982 for(j=0; op[j].label; j++){1983 if( strncmp(&g_argv[i][1],op[j].label,lemonStrlen(op[j].label)((int)strlen(op[j].label)))==0 ) break;1984 }1985 v = g_argv[i][0]=='-' ? 1 : 0;1986 if( op[j].label==0 ){1987 if( err ){1988 fprintf(err,"%sundefined option.\n",emsg);1989 errline(i,1,err);1990 }1991 errcnt++;1992 }else if( op[j].arg==0 ){1993 /* Ignore this option */1994 }else if( op[j].type==OPT_FLAG ){1995 *((int*)op[j].arg) = v;1996 }else if( op[j].type==OPT_FFLAG ){1997 (*(void(*)(int))(op[j].arg))(v);1998 }else if( op[j].type==OPT_FSTR ){1999 (*(void(*)(char *))(op[j].arg))(&g_argv[i][2]);2000 }else{2001 if( err ){2002 fprintf(err,"%smissing argument on switch.\n",emsg);2003 errline(i,1,err);2004 }2005 errcnt++;2006 }2007 return errcnt;2008}2009 2010/*2011** Process a command line switch which has an argument.2012*/2013static int handleswitch(int i, FILE *err)2014{2015 int lv = 0;2016 double dv = 0.0;2017 char *sv = 0, *end;2018 char *cp;2019 int j;2020 int errcnt = 0;2021 cp = strchr(g_argv[i],'=');2022 assert( cp!=0 )((void) sizeof ((cp!=0) ? 1 : 0), __extension__ ({ if (cp!=0)
; else __assert_fail ("cp!=0", "tools/lemon/lemon.c", 2022, __extension__
__PRETTY_FUNCTION__); }));2023 *cp = 0;2024 for(j=0; op[j].label; j++){2025 if( strcmp(g_argv[i],op[j].label)==0 ) break;2026 }2027 *cp = '=';2028 if( op[j].label==0 ){2029 if( err ){2030 fprintf(err,"%sundefined option.\n",emsg);2031 errline(i,0,err);2032 }2033 errcnt++;2034 }else{2035 cp++;2036 switch( op[j].type ){2037 case OPT_FLAG:2038 case OPT_FFLAG:2039 if( err ){2040 fprintf(err,"%soption requires an argument.\n",emsg);2041 errline(i,0,err);2042 }2043 errcnt++;2044 break;2045 case OPT_DBL:2046 case OPT_FDBL:2047 dv = strtod(cp,&end);2048 if( *end ){2049 if( err ){2050 fprintf(err,2051 "%sillegal character in floating-point argument.\n",emsg);2052 errline(i,(int)((char*)end-(char*)g_argv[i]),err);2053 }2054 errcnt++;2055 }2056 break;2057 case OPT_INT:2058 case OPT_FINT:2059 lv = strtol(cp,&end,0);2060 if( *end ){2061 if( err ){2062 fprintf(err,"%sillegal character in integer argument.\n",emsg);2063 errline(i,(int)((char*)end-(char*)g_argv[i]),err);2064 }2065 errcnt++;2066 }2067 break;2068 case OPT_STR:2069 case OPT_FSTR:2070 sv = cp;2071 break;2072 }2073 switch( op[j].type ){2074 case OPT_FLAG:2075 case OPT_FFLAG:2076 break;2077 case OPT_DBL:2078 *(double*)(op[j].arg) = dv;2079 break;2080 case OPT_FDBL:2081 (*(void(*)(double))(op[j].arg))(dv);2082 break;2083 case OPT_INT:2084 *(int*)(op[j].arg) = lv;2085 break;2086 case OPT_FINT:2087 (*(void(*)(int))(op[j].arg))((int)lv);2088 break;2089 case OPT_STR:2090 *(char**)(op[j].arg) = sv;2091 break;2092 case OPT_FSTR:2093 (*(void(*)(char *))(op[j].arg))(sv);2094 break;2095 }2096 }2097 return errcnt;2098}2099 2100int OptInit(char **a, struct s_options *o, FILE *err)2101{2102 int errcnt = 0;2103 g_argv = a;2104 op = o;2105 errstream = err;2106 if( g_argv && *g_argv && op ){2107 int i;2108 for(i=1; g_argv[i]; i++){2109 if( strcmp(g_argv[i],"--")==0 ) break;2110 if( g_argv[i][0]=='+' || g_argv[i][0]=='-' ){2111 errcnt += handleflags(i,err);2112 }else if( strchr(g_argv[i],'=') ){2113 errcnt += handleswitch(i,err);2114 }2115 }2116 }2117 if( errcnt>0 ){2118 fprintf(err,"Valid command line options for \"%s\" are:\n",*a);2119 OptPrint();2120 exit(1);2121 }2122 return 0;2123}2124 2125int OptNArgs(void){2126 int cnt = 0;2127 int dashdash = 0;2128 int i;2129 if( g_argv!=0 && g_argv[0]!=0 ){2130 for(i=1; g_argv[i]; i++){2131 if( dashdash || !ISOPT(g_argv[i])((g_argv[i])[0]=='-'||(g_argv[i])[0]=='+'||strchr((g_argv[i])
,'=')!=0) ) cnt++;2132 if( strcmp(g_argv[i],"--")==0 ) dashdash = 1;2133 }2134 }2135 return cnt;2136}2137 2138char *OptArg(int n)2139{2140 int i;2141 i = argindex(n);2142 return i>=0 ? g_argv[i] : 0;2143}2144 2145void OptErr(int n)2146{2147 int i;2148 i = argindex(n);2149 if( i>=0 ) errline(i,0,errstream);2150}2151 2152void OptPrint(void){2153 int i;2154 int max, len;2155 max = 0;2156 for(i=0; op[i].label; i++){2157 len = lemonStrlen(op[i].label)((int)strlen(op[i].label)) + 1;2158 switch( op[i].type ){2159 case OPT_FLAG:2160 case OPT_FFLAG:2161 break;2162 case OPT_INT:2163 case OPT_FINT:2164 len += 9; /* length of "<integer>" */2165 break;2166 case OPT_DBL:2167 case OPT_FDBL:2168 len += 6; /* length of "<real>" */2169 break;2170 case OPT_STR:2171 case OPT_FSTR:2172 len += 8; /* length of "<string>" */2173 break;2174 }2175 if( len>max ) max = len;2176 }2177 for(i=0; op[i].label; i++){2178 switch( op[i].type ){2179 case OPT_FLAG:2180 case OPT_FFLAG:2181 fprintf(errstream," -%-*s %s\n",max,op[i].label,op[i].message);2182 break;2183 case OPT_INT:2184 case OPT_FINT:2185 fprintf(errstream," -%s<integer>%*s %s\n",op[i].label,2186 (int)(max-lemonStrlen(op[i].label)((int)strlen(op[i].label))-9),"",op[i].message);2187 break;2188 case OPT_DBL:2189 case OPT_FDBL:2190 fprintf(errstream," -%s<real>%*s %s\n",op[i].label,2191 (int)(max-lemonStrlen(op[i].label)((int)strlen(op[i].label))-6),"",op[i].message);2192 break;2193 case OPT_STR:2194 case OPT_FSTR:2195 fprintf(errstream," -%s<string>%*s %s\n",op[i].label,2196 (int)(max-lemonStrlen(op[i].label)((int)strlen(op[i].label))-8),"",op[i].message);2197 break;2198 }2199 }2200}2201/*********************** From the file "parse.c" ****************************/2202/*2203** Input file parser for the LEMON parser generator.2204*/2205 2206/* The state of the parser */2207enum e_state {2208 INITIALIZE,2209 WAITING_FOR_DECL_OR_RULE,2210 WAITING_FOR_DECL_KEYWORD,2211 WAITING_FOR_DECL_ARG,2212 WAITING_FOR_PRECEDENCE_SYMBOL,2213 WAITING_FOR_ARROW,2214 IN_RHS,2215 LHS_ALIAS_1,2216 LHS_ALIAS_2,2217 LHS_ALIAS_3,2218 RHS_ALIAS_1,2219 RHS_ALIAS_2,2220 PRECEDENCE_MARK_1,2221 PRECEDENCE_MARK_2,2222 RESYNC_AFTER_RULE_ERROR,2223 RESYNC_AFTER_DECL_ERROR,2224 WAITING_FOR_DESTRUCTOR_SYMBOL,2225 WAITING_FOR_DATATYPE_SYMBOL,2226 WAITING_FOR_FALLBACK_ID,2227 WAITING_FOR_WILDCARD_ID,2228 WAITING_FOR_CLASS_ID,2229 WAITING_FOR_CLASS_TOKEN,2230 WAITING_FOR_TOKEN_NAME2231};2232struct pstate {2233 char *filename; /* Name of the input file */2234 int tokenlineno; /* Linenumber at which current token starts */2235 int errorcnt; /* Number of errors so far */2236 char *tokenstart; /* Text of current token */2237 struct lemon *gp; /* Global state vector */2238 enum e_state state; /* The state of the parser */2239 struct symbol *fallback; /* The fallback token */2240 struct symbol *tkclass; /* Token class symbol */2241 struct symbol *lhs; /* Left-hand side of current rule */2242 const char *lhsalias; /* Alias for the LHS */2243 int nrhs; /* Number of right-hand side symbols seen */2244 struct symbol *rhs[MAXRHS1000]; /* RHS symbols */2245 const char *alias[MAXRHS1000]; /* Aliases for each RHS symbol (or NULL) */2246 struct rule *prevrule; /* Previous rule parsed */2247 const char *declkeyword; /* Keyword of a declaration */2248 char **declargslot; /* Where the declaration argument should be put */2249 int insertLineMacro; /* Add #line before declaration insert */2250 int *decllinenoslot; /* Where to write declaration line number */2251 enum e_assoc declassoc; /* Assign this association to decl arguments */2252 int preccounter; /* Assign this precedence to decl arguments */2253 struct rule *firstrule; /* Pointer to first rule in the grammar */2254 struct rule *lastrule; /* Pointer to the most recently parsed rule */2255};2256 2257/* Parse a single token */2258static void parseonetoken(struct pstate *psp)2259{2260 const char *x;2261 x = Strsafe(psp->tokenstart); /* Save the token permanently */2262#if 02263 printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,2264 x,psp->state);2265#endif2266 switch( psp->state ){2267 case INITIALIZE:2268 psp->prevrule = 0;2269 psp->preccounter = 0;2270 psp->firstrule = psp->lastrule = 0;2271 psp->gp->nrule = 0;2272 /* fall through */2273 case WAITING_FOR_DECL_OR_RULE:2274 if( x[0]=='%' ){2275 psp->state = WAITING_FOR_DECL_KEYWORD;2276 }else if( ISLOWER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISlower) ){2277 psp->lhs = Symbol_new(x);2278 psp->nrhs = 0;2279 psp->lhsalias = 0;2280 psp->state = WAITING_FOR_ARROW;2281 }else if( x[0]=='{' ){2282 if( psp->prevrule==0 ){2283 ErrorMsg(psp->filename,psp->tokenlineno,2284 "There is no prior rule upon which to attach the code "2285 "fragment which begins on this line.");2286 psp->errorcnt++;2287 }else if( psp->prevrule->code!=0 ){2288 ErrorMsg(psp->filename,psp->tokenlineno,2289 "Code fragment beginning on this line is not the first "2290 "to follow the previous rule.");2291 psp->errorcnt++;2292 }else if( strcmp(x, "{NEVER-REDUCE")==0 ){2293 psp->prevrule->neverReduce = 1;2294 }else{2295 psp->prevrule->line = psp->tokenlineno;2296 psp->prevrule->code = &x[1];2297 psp->prevrule->noCode = 0;2298 }2299 }else if( x[0]=='[' ){2300 psp->state = PRECEDENCE_MARK_1;2301 }else{2302 ErrorMsg(psp->filename,psp->tokenlineno,2303 "Token \"%s\" should be either \"%%\" or a nonterminal name.",2304 x);2305 psp->errorcnt++;2306 }2307 break;2308 case PRECEDENCE_MARK_1:2309 if( !ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) ){2310 ErrorMsg(psp->filename,psp->tokenlineno,2311 "The precedence symbol must be a terminal.");2312 psp->errorcnt++;2313 }else if( psp->prevrule==0 ){2314 ErrorMsg(psp->filename,psp->tokenlineno,2315 "There is no prior rule to assign precedence \"[%s]\".",x);2316 psp->errorcnt++;2317 }else if( psp->prevrule->precsym!=0 ){2318 ErrorMsg(psp->filename,psp->tokenlineno,2319 "Precedence mark on this line is not the first "2320 "to follow the previous rule.");2321 psp->errorcnt++;2322 }else{2323 psp->prevrule->precsym = Symbol_new(x);2324 }2325 psp->state = PRECEDENCE_MARK_2;2326 break;2327 case PRECEDENCE_MARK_2:2328 if( x[0]!=']' ){2329 ErrorMsg(psp->filename,psp->tokenlineno,2330 "Missing \"]\" on precedence mark.");2331 psp->errorcnt++;2332 }2333 psp->state = WAITING_FOR_DECL_OR_RULE;2334 break;2335 case WAITING_FOR_ARROW:2336 if( x[0]==':' && x[1]==':' && x[2]=='=' ){2337 psp->state = IN_RHS;2338 }else if( x[0]=='(' ){2339 psp->state = LHS_ALIAS_1;2340 }else{2341 ErrorMsg(psp->filename,psp->tokenlineno,2342 "Expected to see a \":\" following the LHS symbol \"%s\".",2343 psp->lhs->name);2344 psp->errorcnt++;2345 psp->state = RESYNC_AFTER_RULE_ERROR;2346 }2347 break;2348 case LHS_ALIAS_1:2349 if( ISALPHA(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalpha) ){2350 psp->lhsalias = x;2351 psp->state = LHS_ALIAS_2;2352 }else{2353 ErrorMsg(psp->filename,psp->tokenlineno,2354 "\"%s\" is not a valid alias for the LHS \"%s\"\n",2355 x,psp->lhs->name);2356 psp->errorcnt++;2357 psp->state = RESYNC_AFTER_RULE_ERROR;2358 }2359 break;2360 case LHS_ALIAS_2:2361 if( x[0]==')' ){2362 psp->state = LHS_ALIAS_3;2363 }else{2364 ErrorMsg(psp->filename,psp->tokenlineno,2365 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);2366 psp->errorcnt++;2367 psp->state = RESYNC_AFTER_RULE_ERROR;2368 }2369 break;2370 case LHS_ALIAS_3:2371 if( x[0]==':' && x[1]==':' && x[2]=='=' ){2372 psp->state = IN_RHS;2373 }else{2374 ErrorMsg(psp->filename,psp->tokenlineno,2375 "Missing \"->\" following: \"%s(%s)\".",2376 psp->lhs->name,psp->lhsalias);2377 psp->errorcnt++;2378 psp->state = RESYNC_AFTER_RULE_ERROR;2379 }2380 break;2381 case IN_RHS:2382 if( x[0]=='.' ){2383 struct rule *rp;2384 rp = (struct rule *)calloc( sizeof(struct rule) +2385 sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs, 1);2386 if( rp==0 ){2387 ErrorMsg(psp->filename,psp->tokenlineno,2388 "Can't allocate enough memory for this rule.");2389 psp->errorcnt++;2390 psp->prevrule = 0;2391 }else{2392 int i;2393 rp->ruleline = psp->tokenlineno;2394 rp->rhs = (struct symbol**)&rp[1];2395 rp->rhsalias = (const char**)&(rp->rhs[psp->nrhs]);2396 for(i=0; i<psp->nrhs; i++){2397 rp->rhs[i] = psp->rhs[i];2398 rp->rhsalias[i] = psp->alias[i];2399 if( rp->rhsalias[i]!=0 ){ rp->rhs[i]->bContent = 1; }2400 }2401 rp->lhs = psp->lhs;2402 rp->lhsalias = psp->lhsalias;2403 rp->nrhs = psp->nrhs;2404 rp->code = 0;2405 rp->noCode = 1;2406 rp->precsym = 0;2407 rp->index = psp->gp->nrule++;2408 rp->nextlhs = rp->lhs->rule;2409 rp->lhs->rule = rp;2410 rp->next = 0;2411 if( psp->firstrule==0 ){2412 psp->firstrule = psp->lastrule = rp;2413 }else{2414 psp->lastrule->next = rp;2415 psp->lastrule = rp;2416 }2417 psp->prevrule = rp;2418 }2419 psp->state = WAITING_FOR_DECL_OR_RULE;2420 }else if( ISALPHA(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalpha) ){2421 if( psp->nrhs>=MAXRHS1000 ){2422 ErrorMsg(psp->filename,psp->tokenlineno,2423 "Too many symbols on RHS of rule beginning at \"%s\".",2424 x);2425 psp->errorcnt++;2426 psp->state = RESYNC_AFTER_RULE_ERROR;2427 }else{2428 psp->rhs[psp->nrhs] = Symbol_new(x);2429 psp->alias[psp->nrhs] = 0;2430 psp->nrhs++;2431 }2432 }else if( (x[0]=='|' || x[0]=='/') && psp->nrhs>0 && ISUPPER(x[1])((*__ctype_b_loc ())[(int) (((unsigned char)(x[1])))] & (
unsigned short int) _ISupper) ){2433 struct symbol *msp = psp->rhs[psp->nrhs-1];2434 if( msp->type!=MULTITERMINAL ){2435 struct symbol *origsp = msp;2436 msp = (struct symbol *) calloc(1,sizeof(*msp));2437 memset(msp, 0, sizeof(*msp));2438 msp->type = MULTITERMINAL;2439 msp->nsubsym = 1;2440 msp->subsym = (struct symbol **) calloc(1,sizeof(struct symbol*));2441 msp->subsym[0] = origsp;2442 msp->name = origsp->name;2443 psp->rhs[psp->nrhs-1] = msp;2444 }2445 msp->nsubsym++;2446 msp->subsym = (struct symbol **) realloc(msp->subsym,2447 sizeof(struct symbol*)*msp->nsubsym);2448 msp->subsym[msp->nsubsym-1] = Symbol_new(&x[1]);2449 if( ISLOWER(x[1])((*__ctype_b_loc ())[(int) (((unsigned char)(x[1])))] & (
unsigned short int) _ISlower) || ISLOWER(msp->subsym[0]->name[0])((*__ctype_b_loc ())[(int) (((unsigned char)(msp->subsym[0
]->name[0])))] & (unsigned short int) _ISlower) ){2450 ErrorMsg(psp->filename,psp->tokenlineno,2451 "Cannot form a compound containing a non-terminal");2452 psp->errorcnt++;2453 }2454 }else if( x[0]=='(' && psp->nrhs>0 ){2455 psp->state = RHS_ALIAS_1;2456 }else{2457 ErrorMsg(psp->filename,psp->tokenlineno,2458 "Illegal character on RHS of rule: \"%s\".",x);2459 psp->errorcnt++;2460 psp->state = RESYNC_AFTER_RULE_ERROR;2461 }2462 break;2463 case RHS_ALIAS_1:2464 if( ISALPHA(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalpha) ){2465 psp->alias[psp->nrhs-1] = x;2466 psp->state = RHS_ALIAS_2;2467 }else{2468 ErrorMsg(psp->filename,psp->tokenlineno,2469 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",2470 x,psp->rhs[psp->nrhs-1]->name);2471 psp->errorcnt++;2472 psp->state = RESYNC_AFTER_RULE_ERROR;2473 }2474 break;2475 case RHS_ALIAS_2:2476 if( x[0]==')' ){2477 psp->state = IN_RHS;2478 }else{2479 ErrorMsg(psp->filename,psp->tokenlineno,2480 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);2481 psp->errorcnt++;2482 psp->state = RESYNC_AFTER_RULE_ERROR;2483 }2484 break;2485 case WAITING_FOR_DECL_KEYWORD:2486 if( ISALPHA(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalpha) ){2487 psp->declkeyword = x;2488 psp->declargslot = 0;2489 psp->decllinenoslot = 0;2490 psp->insertLineMacro = 1;2491 psp->state = WAITING_FOR_DECL_ARG;2492 if( strcmp(x,"name")==0 ){2493 psp->declargslot = &(psp->gp->name);2494 psp->insertLineMacro = 0;2495 }else if( strcmp(x,"include")==0 ){2496 psp->declargslot = &(psp->gp->include);2497 }else if( strcmp(x,"code")==0 ){2498 psp->declargslot = &(psp->gp->extracode);2499 }else if( strcmp(x,"token_destructor")==0 ){2500 psp->declargslot = &psp->gp->tokendest;2501 }else if( strcmp(x,"default_destructor")==0 ){2502 psp->declargslot = &psp->gp->vardest;2503 }else if( strcmp(x,"token_prefix")==0 ){2504 psp->declargslot = &psp->gp->tokenprefix;2505 psp->insertLineMacro = 0;2506 }else if( strcmp(x,"syntax_error")==0 ){2507 psp->declargslot = &(psp->gp->error);2508 }else if( strcmp(x,"parse_accept")==0 ){2509 psp->declargslot = &(psp->gp->accept);2510 }else if( strcmp(x,"parse_failure")==0 ){2511 psp->declargslot = &(psp->gp->failure);2512 }else if( strcmp(x,"stack_overflow")==0 ){2513 psp->declargslot = &(psp->gp->overflow);2514 }else if( strcmp(x,"extra_argument")==0 ){2515 psp->declargslot = &(psp->gp->arg);2516 psp->insertLineMacro = 0;2517 }else if( strcmp(x,"extra_context")==0 ){2518 psp->declargslot = &(psp->gp->ctx);2519 psp->insertLineMacro = 0;2520 }else if( strcmp(x,"token_type")==0 ){2521 psp->declargslot = &(psp->gp->tokentype);2522 psp->insertLineMacro = 0;2523 }else if( strcmp(x,"default_type")==0 ){2524 psp->declargslot = &(psp->gp->vartype);2525 psp->insertLineMacro = 0;2526 }else if( strcmp(x,"stack_size")==0 ){2527 psp->declargslot = &(psp->gp->stacksize);2528 psp->insertLineMacro = 0;2529 }else if( strcmp(x,"start_symbol")==0 ){2530 psp->declargslot = &(psp->gp->start);2531 psp->insertLineMacro = 0;2532 }else if( strcmp(x,"left")==0 ){2533 psp->preccounter++;2534 psp->declassoc = LEFT;2535 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;2536 }else if( strcmp(x,"right")==0 ){2537 psp->preccounter++;2538 psp->declassoc = RIGHT;2539 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;2540 }else if( strcmp(x,"nonassoc")==0 ){2541 psp->preccounter++;2542 psp->declassoc = NONE;2543 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;2544 }else if( strcmp(x,"destructor")==0 ){2545 psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;2546 }else if( strcmp(x,"type")==0 ){2547 psp->state = WAITING_FOR_DATATYPE_SYMBOL;2548 }else if( strcmp(x,"fallback")==0 ){2549 psp->fallback = 0;2550 psp->state = WAITING_FOR_FALLBACK_ID;2551 }else if( strcmp(x,"token")==0 ){2552 psp->state = WAITING_FOR_TOKEN_NAME;2553 }else if( strcmp(x,"wildcard")==0 ){2554 psp->state = WAITING_FOR_WILDCARD_ID;2555 }else if( strcmp(x,"token_class")==0 ){2556 psp->state = WAITING_FOR_CLASS_ID;2557 }else{2558 ErrorMsg(psp->filename,psp->tokenlineno,2559 "Unknown declaration keyword: \"%%%s\".",x);2560 psp->errorcnt++;2561 psp->state = RESYNC_AFTER_DECL_ERROR;2562 }2563 }else{2564 ErrorMsg(psp->filename,psp->tokenlineno,2565 "Illegal declaration keyword: \"%s\".",x);2566 psp->errorcnt++;2567 psp->state = RESYNC_AFTER_DECL_ERROR;2568 }2569 break;2570 case WAITING_FOR_DESTRUCTOR_SYMBOL:2571 if( !ISALPHA(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalpha) ){2572 ErrorMsg(psp->filename,psp->tokenlineno,2573 "Symbol name missing after %%destructor keyword");2574 psp->errorcnt++;2575 psp->state = RESYNC_AFTER_DECL_ERROR;2576 }else{2577 struct symbol *sp = Symbol_new(x);2578 psp->declargslot = &sp->destructor;2579 psp->decllinenoslot = &sp->destLineno;2580 psp->insertLineMacro = 1;2581 psp->state = WAITING_FOR_DECL_ARG;2582 }2583 break;2584 case WAITING_FOR_DATATYPE_SYMBOL:2585 if( !ISALPHA(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalpha) ){2586 ErrorMsg(psp->filename,psp->tokenlineno,2587 "Symbol name missing after %%type keyword");2588 psp->errorcnt++;2589 psp->state = RESYNC_AFTER_DECL_ERROR;2590 }else{2591 struct symbol *sp = Symbol_find(x);2592 if((sp) && (sp->datatype)){2593 ErrorMsg(psp->filename,psp->tokenlineno,2594 "Symbol %%type \"%s\" already defined", x);2595 psp->errorcnt++;2596 psp->state = RESYNC_AFTER_DECL_ERROR;2597 }else{2598 if (!sp){2599 sp = Symbol_new(x);2600 }2601 psp->declargslot = &sp->datatype;2602 psp->insertLineMacro = 0;2603 psp->state = WAITING_FOR_DECL_ARG;2604 }2605 }2606 break;2607 case WAITING_FOR_PRECEDENCE_SYMBOL:2608 if( x[0]=='.' ){2609 psp->state = WAITING_FOR_DECL_OR_RULE;2610 }else if( ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) ){2611 struct symbol *sp;2612 sp = Symbol_new(x);2613 if( sp->prec>=0 ){2614 ErrorMsg(psp->filename,psp->tokenlineno,2615 "Symbol \"%s\" has already be given a precedence.",x);2616 psp->errorcnt++;2617 }else{2618 sp->prec = psp->preccounter;2619 sp->assoc = psp->declassoc;2620 }2621 }else{2622 ErrorMsg(psp->filename,psp->tokenlineno,2623 "Can't assign a precedence to \"%s\".",x);2624 psp->errorcnt++;2625 }2626 break;2627 case WAITING_FOR_DECL_ARG:2628 if( x[0]=='{' || x[0]=='\"' || ISALNUM(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISalnum) ){2629 const char *zOld, *zNew;2630 char *zBuf, *z;2631 int nOld, n, nLine = 0, nNew, nBack;2632 int addLineMacro;2633 char zLine[50];2634 zNew = x;2635 if( zNew[0]=='"' || zNew[0]=='{' ) zNew++;2636 nNew = lemonStrlen(zNew)((int)strlen(zNew));2637 if( *psp->declargslot ){2638 zOld = *psp->declargslot;2639 }else{2640 zOld = "";2641 }2642 nOld = lemonStrlen(zOld)((int)strlen(zOld));2643 n = nOld + nNew + 20;2644 addLineMacro = !psp->gp->nolinenosflag2645 && psp->insertLineMacro2646 && psp->tokenlineno>12647 && (psp->decllinenoslot==0 || psp->decllinenoslot[0]!=0);2648 if( addLineMacro ){2649 for(z=psp->filename, nBack=0; *z; z++){2650 if( *z=='\\' ) nBack++;2651 }2652 lemon_sprintf(zLine, "#line %d ", psp->tokenlineno);2653 nLine = lemonStrlen(zLine)((int)strlen(zLine));2654 n += nLine + lemonStrlen(psp->filename)((int)strlen(psp->filename)) + nBack;2655 }2656 *psp->declargslot = (char *) realloc(*psp->declargslot, n);2657 zBuf = *psp->declargslot + nOld;2658 if( addLineMacro ){2659 if( nOld && zBuf[-1]!='\n' ){2660 *(zBuf++) = '\n';2661 }2662 memcpy(zBuf, zLine, nLine);2663 zBuf += nLine;2664 *(zBuf++) = '"';2665 for(z=psp->filename; *z; z++){2666 if( *z=='\\' ){2667 *(zBuf++) = '\\';2668 }2669 *(zBuf++) = *z;2670 }2671 *(zBuf++) = '"';2672 *(zBuf++) = '\n';2673 }2674 if( psp->decllinenoslot && psp->decllinenoslot[0]==0 ){2675 psp->decllinenoslot[0] = psp->tokenlineno;2676 }2677 memcpy(zBuf, zNew, nNew);2678 zBuf += nNew;2679 *zBuf = 0;2680 psp->state = WAITING_FOR_DECL_OR_RULE;2681 }else{2682 ErrorMsg(psp->filename,psp->tokenlineno,2683 "Illegal argument to %%%s: %s",psp->declkeyword,x);2684 psp->errorcnt++;2685 psp->state = RESYNC_AFTER_DECL_ERROR;2686 }2687 break;2688 case WAITING_FOR_FALLBACK_ID:2689 if( x[0]=='.' ){2690 psp->state = WAITING_FOR_DECL_OR_RULE;2691 }else if( !ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) ){2692 ErrorMsg(psp->filename, psp->tokenlineno,2693 "%%fallback argument \"%s\" should be a token", x);2694 psp->errorcnt++;2695 }else{2696 struct symbol *sp = Symbol_new(x);2697 if( psp->fallback==0 ){2698 psp->fallback = sp;2699 }else if( sp->fallback ){2700 ErrorMsg(psp->filename, psp->tokenlineno,2701 "More than one fallback assigned to token %s", x);2702 psp->errorcnt++;2703 }else{2704 sp->fallback = psp->fallback;2705 psp->gp->has_fallback = 1;2706 }2707 }2708 break;2709 case WAITING_FOR_TOKEN_NAME:2710 /* Tokens do not have to be declared before use. But they can be2711 ** in order to control their assigned integer number. The number for2712 ** each token is assigned when it is first seen. So by including2713 **2714 ** %token ONE TWO THREE.2715 **2716 ** early in the grammar file, that assigns small consecutive values2717 ** to each of the tokens ONE TWO and THREE.2718 */2719 if( x[0]=='.' ){2720 psp->state = WAITING_FOR_DECL_OR_RULE;2721 }else if( !ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) ){2722 ErrorMsg(psp->filename, psp->tokenlineno,2723 "%%token argument \"%s\" should be a token", x);2724 psp->errorcnt++;2725 }else{2726 (void)Symbol_new(x);2727 }2728 break;2729 case WAITING_FOR_WILDCARD_ID:2730 if( x[0]=='.' ){2731 psp->state = WAITING_FOR_DECL_OR_RULE;2732 }else if( !ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) ){2733 ErrorMsg(psp->filename, psp->tokenlineno,2734 "%%wildcard argument \"%s\" should be a token", x);2735 psp->errorcnt++;2736 }else{2737 struct symbol *sp = Symbol_new(x);2738 if( psp->gp->wildcard==0 ){2739 psp->gp->wildcard = sp;2740 }else{2741 ErrorMsg(psp->filename, psp->tokenlineno,2742 "Extra wildcard to token: %s", x);2743 psp->errorcnt++;2744 }2745 }2746 break;2747 case WAITING_FOR_CLASS_ID:2748 if( !ISLOWER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISlower) ){2749 ErrorMsg(psp->filename, psp->tokenlineno,2750 "%%token_class must be followed by an identifier: %s", x);2751 psp->errorcnt++;2752 psp->state = RESYNC_AFTER_DECL_ERROR;2753 }else if( Symbol_find(x) ){2754 ErrorMsg(psp->filename, psp->tokenlineno,2755 "Symbol \"%s\" already used", x);2756 psp->errorcnt++;2757 psp->state = RESYNC_AFTER_DECL_ERROR;2758 }else{2759 psp->tkclass = Symbol_new(x);2760 psp->tkclass->type = MULTITERMINAL;2761 psp->state = WAITING_FOR_CLASS_TOKEN;2762 }2763 break;2764 case WAITING_FOR_CLASS_TOKEN:2765 if( x[0]=='.' ){2766 psp->state = WAITING_FOR_DECL_OR_RULE;2767 }else if( ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) || ((x[0]=='|' || x[0]=='/') && ISUPPER(x[1])((*__ctype_b_loc ())[(int) (((unsigned char)(x[1])))] & (
unsigned short int) _ISupper)) ){2768 struct symbol *msp = psp->tkclass;2769 msp->nsubsym++;2770 msp->subsym = (struct symbol **) realloc(msp->subsym,2771 sizeof(struct symbol*)*msp->nsubsym);2772 if( !ISUPPER(x[0])((*__ctype_b_loc ())[(int) (((unsigned char)(x[0])))] & (
unsigned short int) _ISupper) ) x++;2773 msp->subsym[msp->nsubsym-1] = Symbol_new(x);2774 }else{2775 ErrorMsg(psp->filename, psp->tokenlineno,2776 "%%token_class argument \"%s\" should be a token", x);2777 psp->errorcnt++;2778 psp->state = RESYNC_AFTER_DECL_ERROR;2779 }2780 break;2781 case RESYNC_AFTER_RULE_ERROR:2782/* if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;2783** break; */2784 case RESYNC_AFTER_DECL_ERROR:2785 if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;2786 if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;2787 break;2788 }2789}2790 2791/* The text in the input is part of the argument to an %ifdef or %ifndef.2792** Evaluate the text as a boolean expression. Return true or false.2793*/2794static int eval_preprocessor_boolean(char *z, int lineno){2795 int neg = 0;2796 int res = 0;2797 int okTerm = 1;2798 int i;2799 for(i=0; z[i]!=0; i++){2800 if( ISSPACE(z[i])((*__ctype_b_loc ())[(int) (((unsigned char)(z[i])))] & (
unsigned short int) _ISspace) ) continue;2801 if( z[i]=='!' ){2802 if( !okTerm ) goto pp_syntax_error;2803 neg = !neg;2804 continue;2805 }2806 if( z[i]=='|' && z[i+1]=='|' ){2807 if( okTerm ) goto pp_syntax_error;2808 if( res ) return 1;2809 i++;2810 okTerm = 1;2811 continue;2812 }2813 if( z[i]=='&' && z[i+1]=='&' ){2814 if( okTerm ) goto pp_syntax_error;2815 if( !res ) return 0;2816 i++;2817 okTerm = 1;2818 continue;2819 }2820 if( z[i]=='(' ){2821 int k;2822 int n = 1;2823 if( !okTerm ) goto pp_syntax_error;2824 for(k=i+1; z[k]; k++){2825 if( z[k]==')' ){2826 n--;2827 if( n==0 ){2828 z[k] = 0;2829 res = eval_preprocessor_boolean(&z[i+1], -1);2830 z[k] = ')';2831 if( res<0 ){2832 i = i-res;2833 goto pp_syntax_error;2834 }2835 i = k;2836 break;2837 }2838 }else if( z[k]=='(' ){2839 n++;2840 }else if( z[k]==0 ){2841 i = k;2842 goto pp_syntax_error;2843 }2844 }2845 if( neg ){2846 res = !res;2847 neg = 0;2848 }2849 okTerm = 0;2850 continue;2851 }2852 if( ISALPHA(z[i])((*__ctype_b_loc ())[(int) (((unsigned char)(z[i])))] & (
unsigned short int) _ISalpha) ){2853 int j, k, n;2854 if( !okTerm ) goto pp_syntax_error;2855 for(k=i+1; ISALNUM(z[k])((*__ctype_b_loc ())[(int) (((unsigned char)(z[k])))] & (
unsigned short int) _ISalnum) || z[k]=='_'; k++){}2856 n = k - i;2857 res = 0;2858 for(j=0; j<nDefine; j++){2859 if( strncmp(azDefine[j],&z[i],n)==0 && azDefine[j][n]==0 ){2860 res = 1;2861 break;2862 }2863 }2864 i = k-1;2865 if( neg ){2866 res = !res;2867 neg = 0;2868 }2869 okTerm = 0;2870 continue;2871 }2872 goto pp_syntax_error;2873 }2874 return res;2875 2876pp_syntax_error:2877 if( lineno>0 ){2878 fprintf(stderrstderr, "%%if syntax error on line %d.\n", lineno);2879 fprintf(stderrstderr, " %.*s <-- syntax error here\n", i+1, z);2880 exit(1);2881 }else{2882 return -(i+1);2883 }2884}2885 2886/* Run the preprocessor over the input file text. The global variables2887** azDefine[0] through azDefine[nDefine-1] contains the names of all defined2888** macros. This routine looks for "%ifdef" and "%ifndef" and "%endif" and2889** comments them out. Text in between is also commented out as appropriate.2890*/2891static void preprocess_input(char *z){2892 int i, j, k;2893 int exclude = 0;2894 int start = 0;2895 int lineno = 1;2896 int start_lineno = 1;2897 for(i=0; z[i]; i++){2898 if( z[i]=='\n' ) lineno++;2899 if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue;2900 if( strncmp(&z[i],"%endif",6)==0 && ISSPACE(z[i+6])((*__ctype_b_loc ())[(int) (((unsigned char)(z[i+6])))] &
(unsigned short int) _ISspace) ){2901 if( exclude ){2902 exclude--;2903 if( exclude==0 ){2904 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';2905 }2906 }2907 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';2908 }else if( strncmp(&z[i],"%else",5)==0 && ISSPACE(z[i+5])((*__ctype_b_loc ())[(int) (((unsigned char)(z[i+5])))] &
(unsigned short int) _ISspace) ){2909 if( exclude==1){2910 exclude = 0;2911 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';2912 }else if( exclude==0 ){2913 exclude = 1;2914 start = i;2915 start_lineno = lineno;2916 }2917 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';2918 }else if( strncmp(&z[i],"%ifdef ",7)==02919 || strncmp(&z[i],"%if ",4)==02920 || strncmp(&z[i],"%ifndef ",8)==0 ){2921 if( exclude ){2922 exclude++;2923 }else{2924 int isNot;2925 int iBool;2926 for(j=i; z[j] && !ISSPACE(z[j])((*__ctype_b_loc ())[(int) (((unsigned char)(z[j])))] & (
unsigned short int) _ISspace); j++){}2927 iBool = j;2928 isNot = (j==i+7);2929 while( z[j] && z[j]!='\n' ){ j++; }2930 k = z[j];2931 z[j] = 0;2932 exclude = eval_preprocessor_boolean(&z[iBool], lineno);2933 z[j] = k;2934 if( !isNot ) exclude = !exclude;2935 if( exclude ){2936 start = i;2937 start_lineno = lineno;2938 }2939 }2940 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';2941 }2942 }2943 if( exclude ){2944 fprintf(stderrstderr,"unterminated %%ifdef starting on line %d\n", start_lineno);2945 exit(1);2946 }2947}2948 2949/* In spite of its name, this function is really a scanner. It read2950** in the entire input file (all at once) then tokenizes it. Each2951** token is passed to the function "parseonetoken" which builds all2952** the appropriate data structures in the global state vector "gp".2953*/2954void Parse(struct lemon *gp)2955{2956 struct pstate ps;2957 FILE *fp;2958 char *filebuf;2959 unsigned int filesize;2960 int lineno;2961 int c;2962 char *cp, *nextcp;2963 int startline = 0;2964 2965 memset(&ps, '\0', sizeof(ps));2966 ps.gp = gp;2967 ps.filename = gp->filename;2968 ps.errorcnt = 0;2969 ps.state = INITIALIZE;2970 2971 /* Begin by reading the input file */2972 fp = fopen(ps.filename,"rb");2973 if( fp==0 ){2974 ErrorMsg(ps.filename,0,"Can't open this file for reading.");2975 gp->errorcnt++;2976 return;2977 }2978 fseek(fp,0,2);2979 filesize = ftell(fp);2980 rewind(fp);2981 filebuf = (char *)malloc( filesize+1 );2982 if( filesize>100000000 || filebuf==0 ){2983 ErrorMsg(ps.filename,0,"Input file too large.");2984 free(filebuf);2985 gp->errorcnt++;2986 fclose(fp);2987 return;2988 }2989 if( fread(filebuf,1,filesize,fp)!=filesize ){2990 ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",2991 filesize);2992 free(filebuf);2993 gp->errorcnt++;2994 fclose(fp);2995 return;2996 }2997 fclose(fp);2998 filebuf[filesize] = 0;2999 3000 /* Make an initial pass through the file to handle %ifdef and %ifndef */3001 preprocess_input(filebuf);3002 if( gp->printPreprocessed ){3003 printf("%s\n", filebuf);3004 return;3005 }3006 3007 /* Now scan the text of the input file */3008 lineno = 1;3009 for(cp=filebuf; (c= *cp)!=0; ){3010 if( c=='\n' ) lineno++; /* Keep track of the line number */3011 if( ISSPACE(c)((*__ctype_b_loc ())[(int) (((unsigned char)(c)))] & (unsigned
short int) _ISspace) ){ cp++; continue; } /* Skip all white space */3012 if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments */3013 cp+=2;3014 while( (c= *cp)!=0 && c!='\n' ) cp++;3015 continue;3016 }3017 if( c=='/' && cp[1]=='*' ){ /* Skip C style comments */3018 cp+=2;3019 if( (*cp)=='/' ) cp++;3020 while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){3021 if( c=='\n' ) lineno++;3022 cp++;3023 }3024 if( c ) cp++;3025 continue;3026 }3027 ps.tokenstart = cp; /* Mark the beginning of the token */3028 ps.tokenlineno = lineno; /* Linenumber on which token begins */3029 if( c=='\"' ){ /* String literals */3030 cp++;3031 while( (c= *cp)!=0 && c!='\"' ){3032 if( c=='\n' ) lineno++;3033 cp++;3034 }3035 if( c==0 ){3036 ErrorMsg(ps.filename,startline,3037 "String starting on this line is not terminated before "3038 "the end of the file.");3039 ps.errorcnt++;3040 nextcp = cp;3041 }else{3042 nextcp = cp+1;3043 }3044 }else if( c=='{' ){ /* A block of C code */3045 int level;3046 cp++;3047 for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){3048 if( c=='\n' ) lineno++;3049 else if( c=='{' ) level++;3050 else if( c=='}' ) level--;3051 else if( c=='/' && cp[1]=='*' ){ /* Skip comments */3052 int prevc;3053 cp = &cp[2];3054 prevc = 0;3055 while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){3056 if( c=='\n' ) lineno++;3057 prevc = c;3058 cp++;3059 }3060 }else if( c=='/' && cp[1]=='/' ){ /* Skip C++ style comments too */3061 cp = &cp[2];3062 while( (c= *cp)!=0 && c!='\n' ) cp++;3063 if( c ) lineno++;3064 }else if( c=='\'' || c=='\"' ){ /* String a character literals */3065 int startchar, prevc;3066 startchar = c;3067 prevc = 0;3068 for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){3069 if( c=='\n' ) lineno++;3070 if( prevc=='\\' ) prevc = 0;3071 else prevc = c;3072 }3073 }3074 }3075 if( c==0 ){3076 ErrorMsg(ps.filename,ps.tokenlineno,3077 "C code starting on this line is not terminated before "3078 "the end of the file.");3079 ps.errorcnt++;3080 nextcp = cp;3081 }else{3082 nextcp = cp+1;3083 }3084 }else if( ISALNUM(c)((*__ctype_b_loc ())[(int) (((unsigned char)(c)))] & (unsigned
short int) _ISalnum) ){ /* Identifiers */3085 while( (c= *cp)!=0 && (ISALNUM(c)((*__ctype_b_loc ())[(int) (((unsigned char)(c)))] & (unsigned
short int) _ISalnum) || c=='_') ) cp++;3086 nextcp = cp;3087 }else if( c==':' && cp[1]==':' && cp[2]=='=' ){ /* The operator "::=" */3088 cp += 3;3089 nextcp = cp;3090 }else if( (c=='/' || c=='|') && ISALPHA(cp[1])((*__ctype_b_loc ())[(int) (((unsigned char)(cp[1])))] & (
unsigned short int) _ISalpha) ){3091 cp += 2;3092 while( (c = *cp)!=0 && (ISALNUM(c)((*__ctype_b_loc ())[(int) (((unsigned char)(c)))] & (unsigned
short int) _ISalnum) || c=='_') ) cp++;3093 nextcp = cp;3094 }else{ /* All other (one character) operators */3095 cp++;3096 nextcp = cp;3097 }3098 c = *cp;3099 *cp = 0; /* Null terminate the token */3100 parseonetoken(&ps); /* Parse the token */3101 *cp = (char)c; /* Restore the buffer */3102 cp = nextcp;3103 }3104 free(filebuf); /* Release the buffer after parsing */3105 gp->rule = ps.firstrule;3106 gp->errorcnt = ps.errorcnt;3107}3108/*************************** From the file "plink.c" *********************/3109/*3110** Routines processing configuration follow-set propagation links3111** in the LEMON parser generator.3112*/3113static struct plink *plink_freelist = 0;3114 3115/* Allocate a new plink */3116struct plink *Plink_new(void){3117 struct plink *newlink;3118 3119 if( plink_freelist==0 ){3120 int i;3121 int amt = 100;3122 plink_freelist = (struct plink *)calloc( amt, sizeof(struct plink) );3123 if( plink_freelist==0 ){3124 fprintf(stderrstderr,3125 "Unable to allocate memory for a new follow-set propagation link.\n");3126 exit(1);3127 }3128 for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];3129 plink_freelist[amt-1].next = 0;3130 }3131 newlink = plink_freelist;3132 plink_freelist = plink_freelist->next;3133 return newlink;3134}3135 3136/* Add a plink to a plink list */3137void Plink_add(struct plink **plpp, struct config *cfp)3138{3139 struct plink *newlink;3140 newlink = Plink_new();3141 newlink->next = *plpp;3142 *plpp = newlink;3143 newlink->cfp = cfp;3144}3145 3146/* Transfer every plink on the list "from" to the list "to" */3147void Plink_copy(struct plink **to, struct plink *from)3148{3149 struct plink *nextpl;3150 while( from ){3151 nextpl = from->next;3152 from->next = *to;3153 *to = from;3154 from = nextpl;3155 }3156}3157 3158/* Delete every plink on the list */3159void Plink_delete(struct plink *plp)3160{3161 struct plink *nextpl;3162 3163 while( plp ){3164 nextpl = plp->next;3165 plp->next = plink_freelist;3166 plink_freelist = plp;3167 plp = nextpl;3168 }3169}3170/*********************** From the file "report.c" **************************/3171/*3172** Procedures for generating reports and tables in the LEMON parser generator.3173*/3174 3175/* Generate a filename with the given suffix. Space to hold the3176** name comes from malloc() and must be freed by the calling3177** function.3178*/3179PRIVATE char *file_makename(struct lemon *lemp, const char *suffix)3180{3181 char *name;3182 char *cp;3183 char *filename = lemp->filename;3184 int sz;3185 3186 if( outputDir ){3187 cp = strrchr(filename, '/');3188 if( cp ) filename = cp + 1;3189 }3190 sz = lemonStrlen(filename)((int)strlen(filename));3191 sz += lemonStrlen(suffix)((int)strlen(suffix));3192 if( outputDir ) sz += lemonStrlen(outputDir)((int)strlen(outputDir)) + 1;3193 sz += 5;3194 name = (char*)malloc( sz );3195 if( name==0 ){3196 fprintf(stderrstderr,"Can't allocate space for a filename.\n");3197 exit(1);3198 }3199 name[0] = 0;3200 if( outputDir ){3201 lemon_strcpy(name, outputDir);3202 lemon_strcat(name, "/");3203 }3204 lemon_strcat(name,filename);3205 cp = strrchr(name,'.');3206 if( cp ) *cp = 0;3207 lemon_strcat(name,suffix);3208 return name;3209}3210 3211/* Open a file with a name based on the name of the input file,3212** but with a different (specified) suffix, and return a pointer3213** to the stream */3214PRIVATE FILE *file_open(3215 struct lemon *lemp,3216 const char *suffix,3217 const char *mode3218){3219 FILE *fp;3220 3221 if( lemp->outname ) free(lemp->outname);3222 lemp->outname = file_makename(lemp, suffix);3223 fp = fopen(lemp->outname,mode);3224 if( fp==0 && *mode=='w' ){3225 fprintf(stderrstderr,"Can't open file \"%s\".\n",lemp->outname);3226 lemp->errorcnt++;3227 return 0;3228 }3229 return fp;3230}3231 3232/* Print the text of a rule3233*/3234void rule_print(FILE *out, struct rule *rp){3235 int i, j;3236 fprintf(out, "%s",rp->lhs->name);3237 /* if( rp->lhsalias ) fprintf(out,"(%s)",rp->lhsalias); */3238 fprintf(out," ::=");3239 for(i=0; i<rp->nrhs; i++){3240 struct symbol *sp = rp->rhs[i];3241 if( sp->type==MULTITERMINAL ){3242 fprintf(out," %s", sp->subsym[0]->name);3243 for(j=1; j<sp->nsubsym; j++){3244 fprintf(out,"|%s", sp->subsym[j]->name);3245 }3246 }else{3247 fprintf(out," %s", sp->name);3248 }3249 /* if( rp->rhsalias[i] ) fprintf(out,"(%s)",rp->rhsalias[i]); */3250 }3251}3252 3253/* Duplicate the input file without comments and without actions3254** on rules */3255void Reprint(struct lemon *lemp)3256{3257 struct rule *rp;3258 struct symbol *sp;3259 int i, j, maxlen, len, ncolumns, skip;3260 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);3261 maxlen = 10;3262 for(i=0; i<lemp->nsymbol; i++){3263 sp = lemp->symbols[i];3264 len = lemonStrlen(sp->name)((int)strlen(sp->name));3265 if( len>maxlen ) maxlen = len;3266 }3267 ncolumns = 76/(maxlen+5);3268 if( ncolumns<1 ) ncolumns = 1;3269 skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;3270 for(i=0; i<skip; i++){3271 printf("//");3272 for(j=i; j<lemp->nsymbol; j+=skip){3273 sp = lemp->symbols[j];3274 assert( sp->index==j )((void) sizeof ((sp->index==j) ? 1 : 0), __extension__ ({ if
(sp->index==j) ; else __assert_fail ("sp->index==j", "tools/lemon/lemon.c"
, 3274, __extension__ __PRETTY_FUNCTION__); }));3275 printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);3276 }3277 printf("\n");3278 }3279 for(rp=lemp->rule; rp; rp=rp->next){3280 rule_print(stdoutstdout, rp);3281 printf(".");3282 if( rp->precsym ) printf(" [%s]",rp->precsym->name);3283 /* if( rp->code ) printf("\n %s",rp->code); */3284 printf("\n");3285 }3286}3287 3288/* Print a single rule.3289*/3290void RulePrint(FILE *fp, struct rule *rp, int iCursor){3291 struct symbol *sp;3292 int i, j;3293 fprintf(fp,"%s ::=",rp->lhs->name);3294 for(i=0; i<=rp->nrhs; i++){3295 if( i==iCursor ) fprintf(fp," *");3296 if( i==rp->nrhs ) break;3297 sp = rp->rhs[i];3298 if( sp->type==MULTITERMINAL ){3299 fprintf(fp," %s", sp->subsym[0]->name);3300 for(j=1; j<sp->nsubsym; j++){3301 fprintf(fp,"|%s",sp->subsym[j]->name);3302 }3303 }else{3304 fprintf(fp," %s", sp->name);3305 }3306 }3307}3308 3309/* Print the rule for a configuration.3310*/3311void ConfigPrint(FILE *fp, struct config *cfp){3312 RulePrint(fp, cfp->rp, cfp->dot);3313}3314 3315/* #define TEST */3316#if 03317/* Print a set */3318PRIVATE void SetPrint(out,set,lemp)3319FILE *out;3320char *set;3321struct lemon *lemp;3322{3323 int i;3324 char *spacer;3325 spacer = "";3326 fprintf(out,"%12s[","");3327 for(i=0; i<lemp->nterminal; i++){3328 if( SetFind(set,i)(set[i]) ){3329 fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);3330 spacer = " ";3331 }3332 }3333 fprintf(out,"]\n");3334}3335 3336/* Print a plink chain */3337PRIVATE void PlinkPrint(out,plp,tag)3338FILE *out;3339struct plink *plp;3340char *tag;3341{3342 while( plp ){3343 fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->statenum);3344 ConfigPrint(out,plp->cfp);3345 fprintf(out,"\n");3346 plp = plp->next;3347 }3348}3349#endif3350 3351/* Print an action to the given file descriptor. Return FALSE if3352** nothing was actually printed.3353*/3354int PrintAction(3355 struct action *ap, /* The action to print */3356 FILE *fp, /* Print the action here */3357 int indent /* Indent by this amount */3358){3359 int result = 1;3360 switch( ap->type ){3361 case SHIFT: {3362 struct state *stp = ap->x.stp;3363 fprintf(fp,"%*s shift %-7d",indent,ap->sp->name,stp->statenum);3364 break;3365 }3366 case REDUCE: {3367 struct rule *rp = ap->x.rp;3368 fprintf(fp,"%*s reduce %-7d",indent,ap->sp->name,rp->iRule);3369 RulePrint(fp, rp, -1);3370 break;3371 }3372 case SHIFTREDUCE: {3373 struct rule *rp = ap->x.rp;3374 fprintf(fp,"%*s shift-reduce %-7d",indent,ap->sp->name,rp->iRule);3375 RulePrint(fp, rp, -1);3376 break;3377 }3378 case ACCEPT:3379 fprintf(fp,"%*s accept",indent,ap->sp->name);3380 break;3381 case ERROR:3382 fprintf(fp,"%*s error",indent,ap->sp->name);3383 break;3384 case SRCONFLICT:3385 case RRCONFLICT:3386 fprintf(fp,"%*s reduce %-7d ** Parsing conflict **",3387 indent,ap->sp->name,ap->x.rp->iRule);3388 break;3389 case SSCONFLICT:3390 fprintf(fp,"%*s shift %-7d ** Parsing conflict **",3391 indent,ap->sp->name,ap->x.stp->statenum);3392 break;3393 case SH_RESOLVED:3394 if( showPrecedenceConflict ){3395 fprintf(fp,"%*s shift %-7d -- dropped by precedence",3396 indent,ap->sp->name,ap->x.stp->statenum);3397 }else{3398 result = 0;3399 }3400 break;3401 case RD_RESOLVED:3402 if( showPrecedenceConflict ){3403 fprintf(fp,"%*s reduce %-7d -- dropped by precedence",3404 indent,ap->sp->name,ap->x.rp->iRule);3405 }else{3406 result = 0;3407 }3408 break;3409 case NOT_USED:3410 result = 0;3411 break;3412 }3413 if( result && ap->spOpt ){3414 fprintf(fp," /* because %s==%s */", ap->sp->name, ap->spOpt->name);3415 }3416 return result;3417}3418 3419/* Generate the "*.out" log file */3420void ReportOutput(struct lemon *lemp)3421{3422 int i, n;3423 struct state *stp;3424 struct config *cfp;3425 struct action *ap;3426 struct rule *rp;3427 FILE *fp;3428 3429 fp = file_open(lemp,".out","wb");3430 if( fp==0 ) return;3431 for(i=0; i<lemp->nxstate; i++){3432 stp = lemp->sorted[i];3433 fprintf(fp,"State %d:\n",stp->statenum);3434 if( lemp->basisflag ) cfp=stp->bp;3435 else cfp=stp->cfp;3436 while( cfp ){3437 char buf[20];3438 if( cfp->dot==cfp->rp->nrhs ){3439 lemon_sprintf(buf,"(%d)",cfp->rp->iRule);3440 fprintf(fp," %5s ",buf);3441 }else{3442 fprintf(fp," ");3443 }3444 ConfigPrint(fp,cfp);3445 fprintf(fp,"\n");3446#if 03447 SetPrint(fp,cfp->fws,lemp);3448 PlinkPrint(fp,cfp->fplp,"To ");3449 PlinkPrint(fp,cfp->bplp,"From");3450#endif3451 if( lemp->basisflag ) cfp=cfp->bp;3452 else cfp=cfp->next;3453 }3454 fprintf(fp,"\n");3455 for(ap=stp->ap; ap; ap=ap->next){3456 if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");3457 }3458 fprintf(fp,"\n");3459 }3460 fprintf(fp, "----------------------------------------------------\n");3461 fprintf(fp, "Symbols:\n");3462 fprintf(fp, "The first-set of non-terminals is shown after the name.\n\n");3463 for(i=0; i<lemp->nsymbol; i++){3464 int j;3465 struct symbol *sp;3466 3467 sp = lemp->symbols[i];3468 fprintf(fp, " %3d: %s", i, sp->name);3469 if( sp->type==NONTERMINAL ){3470 fprintf(fp, ":");3471 if( sp->lambda ){3472 fprintf(fp, " <lambda>");3473 }3474 for(j=0; j<lemp->nterminal; j++){3475 if( sp->firstset && SetFind(sp->firstset, j)(sp->firstset[j]) ){3476 fprintf(fp, " %s", lemp->symbols[j]->name);3477 }3478 }3479 }3480 if( sp->prec>=0 ) fprintf(fp," (precedence=%d)", sp->prec);3481 fprintf(fp, "\n");3482 }3483 fprintf(fp, "----------------------------------------------------\n");3484 fprintf(fp, "Syntax-only Symbols:\n");3485 fprintf(fp, "The following symbols never carry semantic content.\n\n");3486 for(i=n=0; i<lemp->nsymbol; i++){3487 int w;3488 struct symbol *sp = lemp->symbols[i];3489 if( sp->bContent ) continue;3490 w = (int)strlen(sp->name);3491 if( n>0 && n+w>75 ){3492 fprintf(fp,"\n");3493 n = 0;3494 }3495 if( n>0 ){3496 fprintf(fp, " ");3497 n++;3498 }3499 fprintf(fp, "%s", sp->name);3500 n += w;3501 }3502 if( n>0 ) fprintf(fp, "\n");3503 fprintf(fp, "----------------------------------------------------\n");3504 fprintf(fp, "Rules:\n");3505 for(rp=lemp->rule; rp; rp=rp->next){3506 fprintf(fp, "%4d: ", rp->iRule);3507 rule_print(fp, rp);3508 fprintf(fp,".");3509 if( rp->precsym ){3510 fprintf(fp," [%s precedence=%d]",3511 rp->precsym->name, rp->precsym->prec);3512 }3513 fprintf(fp,"\n");3514 }3515 fclose(fp);3516 return;3517}3518 3519/* Search for the file "name" which is in the same directory as3520** the executable */3521PRIVATE char *pathsearch(char *argv0, char *name, int modemask)3522{3523 const char *pathlist;3524 char *pathbufptr = 0;3525 char *pathbuf = 0;3526 char *path,*cp;3527 char c;3528 3529#ifdef __WIN32__3530 cp = strrchr(argv0,'\\');3531#else3532 cp = strrchr(argv0,'/');3533#endif3534 if( cp ){3535 c = *cp;3536 *cp = 0;3537 path = (char *)malloc( lemonStrlen(argv0)((int)strlen(argv0)) + lemonStrlen(name)((int)strlen(name)) + 2 );3538 if( path ) lemon_sprintf(path,"%s/%s",argv0,name);3539 *cp = c;3540 }else{3541 pathlist = getenv("PATH");3542 if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";3543 pathbuf = (char *) malloc( lemonStrlen(pathlist)((int)strlen(pathlist)) + 1 );3544 path = (char *)malloc( lemonStrlen(pathlist)((int)strlen(pathlist))+lemonStrlen(name)((int)strlen(name))+2 );3545 if( (pathbuf != 0) && (path!=0) ){3546 pathbufptr = pathbuf;3547 lemon_strcpy(pathbuf, pathlist);3548 while( *pathbuf ){3549 cp = strchr(pathbuf,':');3550 if( cp==0 ) cp = &pathbuf[lemonStrlen(pathbuf)((int)strlen(pathbuf))];3551 c = *cp;3552 *cp = 0;3553 lemon_sprintf(path,"%s/%s",pathbuf,name);3554 *cp = c;3555 if( c==0 ) pathbuf[0] = 0;3556 else pathbuf = &cp[1];3557 if( access(path,modemask)==0 ) break;3558 }3559 }3560 free(pathbufptr);3561 }3562 return path;3563}3564 3565/* Given an action, compute the integer value for that action3566** which is to be put in the action table of the generated machine.3567** Return negative if no action should be generated.3568*/3569PRIVATE int compute_action(struct lemon *lemp, struct action *ap)3570{3571 int act;3572 switch( ap->type ){3573 case SHIFT: act = ap->x.stp->statenum; break;3574 case SHIFTREDUCE: {3575 /* Since a SHIFT is inherient after a prior REDUCE, convert any3576 ** SHIFTREDUCE action with a nonterminal on the LHS into a simple3577 ** REDUCE action: */3578 if( ap->sp->index>=lemp->nterminal3579 && (lemp->errsym==0 || ap->sp->index!=lemp->errsym->index)3580 ){3581 act = lemp->minReduce + ap->x.rp->iRule;3582 }else{3583 act = lemp->minShiftReduce + ap->x.rp->iRule;3584 }3585 break;3586 }3587 case REDUCE: act = lemp->minReduce + ap->x.rp->iRule; break;3588 case ERROR: act = lemp->errAction; break;3589 case ACCEPT: act = lemp->accAction; break;3590 default: act = -1; break;3591 }3592 return act;3593}3594 3595#define LINESIZE1000 10003596/* The next cluster of routines are for reading the template file3597** and writing the results to the generated parser */3598/* The first function transfers data from "in" to "out" until3599** a line is seen which begins with "%%". The line number is3600** tracked.3601**3602** if name!=0, then any word that begin with "Parse" is changed to3603** begin with *name instead.3604*/3605PRIVATE void tplt_xfer(char *name, FILE *in, FILE *out, int *lineno)3606{3607 int i, iStart;3608 char line[LINESIZE1000];3609 while( fgets(line,LINESIZE1000,in) && (line[0]!='%' || line[1]!='%') ){3610 (*lineno)++;3611 iStart = 0;3612 if( name ){3613 for(i=0; line[i]; i++){3614 if( line[i]=='P' && strncmp(&line[i],"Parse",5)==03615 && (i==0 || !ISALPHA(line[i-1])((*__ctype_b_loc ())[(int) (((unsigned char)(line[i-1])))] &
(unsigned short int) _ISalpha))3616 ){3617 if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);3618 fprintf(out,"%s",name);3619 i += 4;3620 iStart = i+1;3621 }3622 }3623 }3624 fprintf(out,"%s",&line[iStart]);3625 }3626}3627 3628/* Skip forward past the header of the template file to the first "%%"3629*/3630PRIVATE void tplt_skip_header(FILE *in, int *lineno)3631{3632 char line[LINESIZE1000];3633 while( fgets(line,LINESIZE1000,in) && (line[0]!='%' || line[1]!='%') ){3634 (*lineno)++;3635 }3636}3637 3638/* The next function finds the template file and opens it, returning3639** a pointer to the opened file. */3640PRIVATE FILE *tplt_open(struct lemon *lemp)3641{3642 static char templatename[] = "lempar.c";3643 char buf[1000];3644 FILE *in;3645 char *tpltname;3646 char *toFree = 0;3647 char *cp;3648 3649 /* first, see if user specified a template filename on the command line. */3650 if (user_templatename != 0) {3651 if( access(user_templatename,004)==-1 ){3652 fprintf(stderrstderr,"Can't find the parser driver template file \"%s\".\n",3653 user_templatename);3654 lemp->errorcnt++;3655 return 0;3656 }3657 in = fopen(user_templatename,"rb");3658 if( in==0 ){3659 fprintf(stderrstderr,"Can't open the template file \"%s\".\n",3660 user_templatename);3661 lemp->errorcnt++;3662 return 0;3663 }3664 return in;3665 }3666 3667 cp = strrchr(lemp->filename,'.');3668 if( cp ){3669 lemon_sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);3670 }else{3671 lemon_sprintf(buf,"%s.lt",lemp->filename);3672 }3673 if( access(buf,004)==0 ){3674 tpltname = buf;3675 }else if( access(templatename,004)==0 ){3676 tpltname = templatename;3677 }else{3678 toFree = tpltname = pathsearch(lemp->argv0,templatename,0);3679 }3680 if( tpltname==0 ){3681 fprintf(stderrstderr,"Can't find the parser driver template file \"%s\".\n",3682 templatename);3683 lemp->errorcnt++;3684 return 0;3685 }3686 in = fopen(tpltname,"rb");3687 if( in==0 ){3688 fprintf(stderrstderr,"Can't open the template file \"%s\".\n",tpltname);3689 lemp->errorcnt++;3690 }3691 free(toFree);3692 return in;3693}3694 3695/* Print a #line directive line to the output file. */3696PRIVATE void tplt_linedir(FILE *out, int lineno, char *filename)3697{3698 fprintf(out,"#line %d \"",lineno);3699 while( *filename ){3700 if( *filename == '\\' ) putc('\\',out);3701 putc(*filename,out);3702 filename++;3703 }3704 fprintf(out,"\"\n");3705}3706 3707/* Print a string to the file and keep the linenumber up to date */3708PRIVATE void tplt_print(FILE *out, struct lemon *lemp, char *str, int *lineno)3709{3710 if( str==0 ) return;3711 while( *str ){3712 putc(*str,out);3713 if( *str=='\n' ) (*lineno)++;3714 str++;3715 }3716 if( str[-1]!='\n' ){3717 putc('\n',out);3718 (*lineno)++;3719 }3720 if (!lemp->nolinenosflag) {3721 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);3722 }3723 return;3724}3725 3726/*3727** The following routine emits code for the destructor for the3728** symbol sp3729*/3730void emit_destructor_code(3731 FILE *out,3732 struct symbol *sp,3733 struct lemon *lemp,3734 int *lineno3735){3736 char *cp = 0;3737 3738 if( sp->type==TERMINAL ){3739 cp = lemp->tokendest;3740 if( cp==0 ) return;3741 fprintf(out,"{\n"); (*lineno)++;3742 }else if( sp->destructor ){3743 cp = sp->destructor;3744 fprintf(out,"{\n"); (*lineno)++;3745 if( !lemp->nolinenosflag ){3746 (*lineno)++;3747 tplt_linedir(out,sp->destLineno,lemp->filename);3748 }3749 }else if( lemp->vardest ){3750 cp = lemp->vardest;3751 if( cp==0 ) return;3752 fprintf(out,"{\n"); (*lineno)++;3753 }else{3754 assert( 0 )((void) sizeof ((0) ? 1 : 0), __extension__ ({ if (0) ; else __assert_fail
("0", "tools/lemon/lemon.c", 3754, __extension__ __PRETTY_FUNCTION__
); })); /* Cannot happen */3755 }3756 for(; *cp; cp++){3757 if( *cp=='$' && cp[1]=='$' ){3758 fprintf(out,"(yypminor->yy%d)",sp->dtnum);3759 cp++;3760 continue;3761 }3762 if( *cp=='\n' ) (*lineno)++;3763 fputc(*cp,out);3764 }3765 fprintf(out,"\n"); (*lineno)++;3766 if (!lemp->nolinenosflag) {3767 (*lineno)++; tplt_linedir(out,*lineno,lemp->outname);3768 }3769 fprintf(out,"}\n"); (*lineno)++;3770 return;3771}3772 3773/*3774** Return TRUE (non-zero) if the given symbol has a destructor.3775*/3776int has_destructor(struct symbol *sp, struct lemon *lemp)3777{3778 int ret;3779 if( sp->type==TERMINAL ){3780 ret = lemp->tokendest!=0;3781 }else{3782 ret = lemp->vardest!=0 || sp->destructor!=0;3783 }3784 return ret;3785}3786 3787/*3788** Append text to a dynamically allocated string. If zText is 0 then3789** reset the string to be empty again. Always return the complete text3790** of the string (which is overwritten with each call).3791**3792** n bytes of zText are stored. If n==0 then all of zText up to the first3793** \000 terminator is stored. zText can contain up to two instances of3794** %d. The values of p1 and p2 are written into the first and second3795** %d.3796**3797** If n==-1, then the previous character is overwritten.3798*/3799PRIVATE char *append_str(const char *zText, int n, int p1, int p2){3800 static char empty[1] = { 0 };3801 static char *z = 0;3802 static int alloced = 0;3803 static int used = 0;3804 int c;3805 char zInt[40];3806 if( zText==0 ){3807 if( used==0 && z!=0 ) z[0] = 0;3808 used = 0;3809 return z;3810 }3811 if( n<=0 ){3812 if( n<0 ){3813 used += n;3814 assert( used>=0 )((void) sizeof ((used>=0) ? 1 : 0), __extension__ ({ if (used
>=0) ; else __assert_fail ("used>=0", "tools/lemon/lemon.c"
, 3814, __extension__ __PRETTY_FUNCTION__); }));3815 }3816 n = lemonStrlen(zText)((int)strlen(zText));3817 }3818 if( (int) (n+sizeof(zInt)*2+used) >= alloced ){3819 alloced = n + sizeof(zInt)*2 + used + 200;3820 z = (char *) realloc(z, alloced);3821 }3822 if( z==0 ) return empty;3823 while( n-- > 0 ){3824 c = *(zText++);3825 if( c=='%' && n>0 && zText[0]=='d' ){3826 lemon_sprintf(zInt, "%d", p1);3827 p1 = p2;3828 lemon_strcpy(&z[used], zInt);3829 used += lemonStrlen(&z[used])((int)strlen(&z[used]));3830 zText++;3831 n--;3832 }else{3833 z[used++] = (char)c;3834 }3835 }3836 z[used] = 0;3837 return z;3838}3839 3840/*3841** Write and transform the rp->code string so that symbols are expanded.3842** Populate the rp->codePrefix and rp->codeSuffix strings, as appropriate.3843**3844** Return 1 if the expanded code requires that "yylhsminor" local variable3845** to be defined.3846*/3847PRIVATE int translate_code(struct lemon *lemp, struct rule *rp){3848 char *cp, *xp;3849 int i;3850 int rc = 0; /* True if yylhsminor is used */3851 int dontUseRhs0 = 0; /* If true, use of left-most RHS label is illegal */3852 const char *zSkip = 0; /* The zOvwrt comment within rp->code, or NULL */3853 char lhsused = 0; /* True if the LHS element has been used */3854 char lhsdirect; /* True if LHS writes directly into stack */3855 char used[MAXRHS1000]; /* True for each RHS element which is used */3856 char zLhs[50]; /* Convert the LHS symbol into this string */3857 char zOvwrt[900]; /* Comment that to allow LHS to overwrite RHS */3858 3859 for(i=0; i<rp->nrhs; i++) used[i] = 0;3860 lhsused = 0;3861 3862 if( rp->code==0 ){3863 static char newlinestr[2] = { '\n', '\0' };3864 rp->code = newlinestr;3865 rp->line = rp->ruleline;3866 rp->noCode = 1;3867 }else{3868 rp->noCode = 0;3869 }3870 3871 3872 if( rp->nrhs==0 ){3873 /* If there are no RHS symbols, then writing directly to the LHS is ok */3874 lhsdirect = 1;3875 }else if( rp->rhsalias[0]==0 ){3876 /* The left-most RHS symbol has no value. LHS direct is ok. But3877 ** we have to call the destructor on the RHS symbol first. */3878 lhsdirect = 1;3879 if( has_destructor(rp->rhs[0],lemp) ){3880 append_str(0,0,0,0);3881 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,3882 rp->rhs[0]->index,1-rp->nrhs);3883 rp->codePrefix = Strsafe(append_str(0,0,0,0));3884 rp->noCode = 0;3885 }3886 }else if( rp->lhsalias==0 ){3887 /* There is no LHS value symbol. */3888 lhsdirect = 1;3889 }else if( strcmp(rp->lhsalias,rp->rhsalias[0])==0 ){3890 /* The LHS symbol and the left-most RHS symbol are the same, so3891 ** direct writing is allowed */3892 lhsdirect = 1;3893 lhsused = 1;3894 used[0] = 1;3895 if( rp->lhs->dtnum!=rp->rhs[0]->dtnum ){3896 ErrorMsg(lemp->filename,rp->ruleline,3897 "%s(%s) and %s(%s) share the same label but have "3898 "different datatypes.",3899 rp->lhs->name, rp->lhsalias, rp->rhs[0]->name, rp->rhsalias[0]);3900 lemp->errorcnt++;3901 }3902 }else{3903 lemon_sprintf(zOvwrt, "/*%s-overwrites-%s*/",3904 rp->lhsalias, rp->rhsalias[0]);3905 zSkip = strstr(rp->code, zOvwrt);3906 if( zSkip!=0 ){3907 /* The code contains a special comment that indicates that it is safe3908 ** for the LHS label to overwrite left-most RHS label. */3909 lhsdirect = 1;3910 }else{3911 lhsdirect = 0;3912 }3913 }3914 if( lhsdirect ){3915 sprintf(zLhs, "yymsp[%d].minor.yy%d",1-rp->nrhs,rp->lhs->dtnum);3916 }else{3917 rc = 1;3918 sprintf(zLhs, "yylhsminor.yy%d",rp->lhs->dtnum);3919 }3920 3921 append_str(0,0,0,0);3922 3923 /* This const cast is wrong but harmless, if we're careful. */3924 for(cp=(char *)rp->code; *cp; cp++){3925 if( cp==zSkip ){3926 append_str(zOvwrt,0,0,0);3927 cp += lemonStrlen(zOvwrt)((int)strlen(zOvwrt))-1;3928 dontUseRhs0 = 1;3929 continue;3930 }3931 if( ISALPHA(*cp)((*__ctype_b_loc ())[(int) (((unsigned char)(*cp)))] & (unsigned
short int) _ISalpha) && (cp==rp->code || (!ISALNUM(cp[-1])((*__ctype_b_loc ())[(int) (((unsigned char)(cp[-1])))] &
(unsigned short int) _ISalnum) && cp[-1]!='_')) ){3932 char saved;3933 for(xp= &cp[1]; ISALNUM(*xp)((*__ctype_b_loc ())[(int) (((unsigned char)(*xp)))] & (unsigned
short int) _ISalnum) || *xp=='_'; xp++);3934 saved = *xp;3935 *xp = 0;3936 if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){3937 append_str(zLhs,0,0,0);3938 cp = xp;3939 lhsused = 1;3940 }else{3941 for(i=0; i<rp->nrhs; i++){3942 if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){3943 if( i==0 && dontUseRhs0 ){3944 ErrorMsg(lemp->filename,rp->ruleline,3945 "Label %s used after '%s'.",3946 rp->rhsalias[0], zOvwrt);3947 lemp->errorcnt++;3948 }else if( cp!=rp->code && cp[-1]=='@' ){3949 /* If the argument is of the form @X then substituted3950 ** the token number of X, not the value of X */3951 append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);3952 }else{3953 struct symbol *sp = rp->rhs[i];3954 int dtnum;3955 if( sp->type==MULTITERMINAL ){3956 dtnum = sp->subsym[0]->dtnum;3957 }else{3958 dtnum = sp->dtnum;3959 }3960 append_str("yymsp[%d].minor.yy%d",0,i-rp->nrhs+1, dtnum);3961 }3962 cp = xp;3963 used[i] = 1;3964 break;3965 }3966 }3967 }3968 *xp = saved;3969 }3970 append_str(cp, 1, 0, 0);3971 } /* End loop */3972 3973 /* Main code generation completed */3974 cp = append_str(0,0,0,0);3975 if( cp && cp[0] ) rp->code = Strsafe(cp);3976 append_str(0,0,0,0);3977 3978 /* Check to make sure the LHS has been used */3979 if( rp->lhsalias && !lhsused ){3980 ErrorMsg(lemp->filename,rp->ruleline,3981 "Label \"%s\" for \"%s(%s)\" is never used.",3982 rp->lhsalias,rp->lhs->name,rp->lhsalias);3983 lemp->errorcnt++;3984 }3985 3986 /* Generate destructor code for RHS minor values which are not referenced.3987 ** Generate error messages for unused labels and duplicate labels.3988 */3989 for(i=0; i<rp->nrhs; i++){3990 if( rp->rhsalias[i] ){3991 if( i>0 ){3992 int j;3993 if( rp->lhsalias && strcmp(rp->lhsalias,rp->rhsalias[i])==0 ){3994 ErrorMsg(lemp->filename,rp->ruleline,3995 "%s(%s) has the same label as the LHS but is not the left-most "3996 "symbol on the RHS.",3997 rp->rhs[i]->name, rp->rhsalias[i]);3998 lemp->errorcnt++;3999 }4000 for(j=0; j<i; j++){4001 if( rp->rhsalias[j] && strcmp(rp->rhsalias[j],rp->rhsalias[i])==0 ){4002 ErrorMsg(lemp->filename,rp->ruleline,4003 "Label %s used for multiple symbols on the RHS of a rule.",4004 rp->rhsalias[i]);4005 lemp->errorcnt++;4006 break;4007 }4008 }4009 }4010 if( !used[i] ){4011 ErrorMsg(lemp->filename,rp->ruleline,4012 "Label %s for \"%s(%s)\" is never used.",4013 rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);4014 lemp->errorcnt++;4015 }4016 }else if( i>0 && has_destructor(rp->rhs[i],lemp) ){4017 append_str(" yy_destructor(yypParser,%d,&yymsp[%d].minor);\n", 0,4018 rp->rhs[i]->index,i-rp->nrhs+1);4019 }4020 }4021 4022 /* If unable to write LHS values directly into the stack, write the4023 ** saved LHS value now. */4024 if( lhsdirect==0 ){4025 append_str(" yymsp[%d].minor.yy%d = ", 0, 1-rp->nrhs, rp->lhs->dtnum);4026 append_str(zLhs, 0, 0, 0);4027 append_str(";\n", 0, 0, 0);4028 }4029 4030 /* Suffix code generation complete */4031 cp = append_str(0,0,0,0);4032 if( cp && cp[0] ){4033 rp->codeSuffix = Strsafe(cp);4034 rp->noCode = 0;4035 }4036 4037 return rc;4038}4039 4040/*4041** Generate code which executes when the rule "rp" is reduced. Write4042** the code to "out". Make sure lineno stays up-to-date.4043*/4044PRIVATE void emit_code(4045 FILE *out,4046 struct rule *rp,4047 struct lemon *lemp,4048 int *lineno4049){4050 const char *cp;4051 4052 /* Setup code prior to the #line directive */4053 if( rp->codePrefix && rp->codePrefix[0] ){4054 fprintf(out, "{%s", rp->codePrefix);4055 for(cp=rp->codePrefix; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; }4056 }4057 4058 /* Generate code to do the reduce action */4059 if( rp->code ){4060 if( !lemp->nolinenosflag ){4061 (*lineno)++;4062 tplt_linedir(out,rp->line,lemp->filename);4063 }4064 fprintf(out,"{%s",rp->code);4065 for(cp=rp->code; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; }4066 fprintf(out,"}\n"); (*lineno)++;4067 if( !lemp->nolinenosflag ){4068 (*lineno)++;4069 tplt_linedir(out,*lineno,lemp->outname);4070 }4071 }4072 4073 /* Generate breakdown code that occurs after the #line directive */4074 if( rp->codeSuffix && rp->codeSuffix[0] ){4075 fprintf(out, "%s", rp->codeSuffix);4076 for(cp=rp->codeSuffix; *cp; cp++){ if( *cp=='\n' ) (*lineno)++; }4077 }4078 4079 if( rp->codePrefix ){4080 fprintf(out, "}\n"); (*lineno)++;4081 }4082 4083 return;4084}4085 4086/*4087** Print the definition of the union used for the parser's data stack.4088** This union contains fields for every possible data type for tokens4089** and nonterminals. In the process of computing and printing this4090** union, also set the ".dtnum" field of every terminal and nonterminal4091** symbol.4092*/4093void print_stack_union(4094 FILE *out, /* The output stream */4095 struct lemon *lemp, /* The main info structure for this parser */4096 int *plineno, /* Pointer to the line number */4097 int mhflag /* True if generating makeheaders output */4098){4099 int lineno; /* The line number of the output */4100 char **types; /* A hash table of datatypes */4101 int arraysize; /* Size of the "types" array */4102 int maxdtlength; /* Maximum length of any ".datatype" field. */4103 char *stddt; /* Standardized name for a datatype */4104 int i,j; /* Loop counters */4105 unsigned hash; /* For hashing the name of a type */4106 const char *name; /* Name of the parser */4107 4108 /* Allocate and initialize types[] and allocate stddt[] */4109 arraysize = lemp->nsymbol * 2;4110 types = (char**)calloc( arraysize, sizeof(char*) );4111 if( types==0 ){4112 fprintf(stderrstderr,"Out of memory.\n");4113 exit(1);4114 }4115 for(i=0; i<arraysize; i++) types[i] = 0;4116 maxdtlength = 0;4117 if( lemp->vartype ){4118 maxdtlength = lemonStrlen(lemp->vartype)((int)strlen(lemp->vartype));4119 }4120 for(i=0; i<lemp->nsymbol; i++){4121 int len;4122 struct symbol *sp = lemp->symbols[i];4123 if( sp->datatype==0 ) continue;4124 len = lemonStrlen(sp->datatype)((int)strlen(sp->datatype));4125 if( len>maxdtlength ) maxdtlength = len;4126 }4127 stddt = (char*)malloc( maxdtlength*2 + 1 );4128 if( stddt==0 ){4129 fprintf(stderrstderr,"Out of memory.\n");4130 exit(1);4131 }4132 4133 /* Build a hash table of datatypes. The ".dtnum" field of each symbol4134 ** is filled in with the hash index plus 1. A ".dtnum" value of 0 is4135 ** used for terminal symbols. If there is no %default_type defined then4136 ** 0 is also used as the .dtnum value for nonterminals which do not specify4137 ** a datatype using the %type directive.4138 */4139 for(i=0; i<lemp->nsymbol; i++){4140 struct symbol *sp = lemp->symbols[i];4141 char *cp;4142 if( sp==lemp->errsym ){4143 sp->dtnum = arraysize+1;4144 continue;4145 }4146 if( sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0) ){4147 sp->dtnum = 0;4148 continue;4149 }4150 cp = sp->datatype;4151 if( cp==0 ) cp = lemp->vartype;4152 j = 0;4153 while( ISSPACE(*cp)((*__ctype_b_loc ())[(int) (((unsigned char)(*cp)))] & (unsigned
short int) _ISspace) ) cp++;4154 while( *cp ) stddt[j++] = *cp++;4155 while( j>0 && ISSPACE(stddt[j-1])((*__ctype_b_loc ())[(int) (((unsigned char)(stddt[j-1])))] &
(unsigned short int) _ISspace) ) j--;4156 stddt[j] = 0;4157 if( lemp->tokentype && strcmp(stddt, lemp->tokentype)==0 ){4158 sp->dtnum = 0;4159 continue;4160 }4161 hash = 0;4162 for(j=0; stddt[j]; j++){4163 hash = hash*53 + stddt[j];4164 }4165 hash = (hash & 0x7fffffff)%arraysize;4166 while( types[hash] ){4167 if( strcmp(types[hash],stddt)==0 ){4168 sp->dtnum = hash + 1;4169 break;4170 }4171 hash++;4172 if( hash>=(unsigned)arraysize ) hash = 0;4173 }4174 if( types[hash]==0 ){4175 sp->dtnum = hash + 1;4176 types[hash] = (char*)malloc( lemonStrlen(stddt)((int)strlen(stddt))+1 );4177 if( types[hash]==0 ){4178 fprintf(stderrstderr,"Out of memory.\n");4179 exit(1);4180 }4181 lemon_strcpy(types[hash],stddt);4182 }4183 }4184 4185 /* Print out the definition of YYTOKENTYPE and YYMINORTYPE */4186 name = lemp->name ? lemp->name : "Parse";4187 lineno = *plineno;4188 if( mhflag ){ fprintf(out,"#if INTERFACE\n"); lineno++; }4189 fprintf(out,"#define %sTOKENTYPE %s\n",name,4190 lemp->tokentype?lemp->tokentype:"void*"); lineno++;4191 if( mhflag ){ fprintf(out,"#endif\n"); lineno++; }4192 fprintf(out,"typedef union {\n"); lineno++;4193 fprintf(out," int yyinit;\n"); lineno++;4194 fprintf(out," %sTOKENTYPE yy0;\n",name); lineno++;4195 for(i=0; i<arraysize; i++){4196 if( types[i]==0 ) continue;4197 fprintf(out," %s yy%d;\n",types[i],i+1); lineno++;4198 free(types[i]);4199 }4200 if( lemp->errsym && lemp->errsym->useCnt ){4201 fprintf(out," int yy%d;\n",lemp->errsym->dtnum); lineno++;4202 }4203 free(stddt);4204 free(types);4205 fprintf(out,"} YYMINORTYPE;\n"); lineno++;4206 *plineno = lineno;4207}4208 4209/*4210** Return the name of a C datatype able to represent values between4211** lwr and upr, inclusive. If pnByte!=NULL then also write the sizeof4212** for that type (1, 2, or 4) into *pnByte.4213*/4214static const char *minimum_size_type(int lwr, int upr, int *pnByte){4215 const char *zType = "int";4216 int nByte = 4;4217 if( lwr>=0 ){4218 if( upr<=255 ){4219 zType = "unsigned char";4220 nByte = 1;4221 }else if( upr<65535 ){4222 zType = "unsigned short int";4223 nByte = 2;4224 }else{4225 zType = "unsigned int";4226 nByte = 4;4227 }4228 }else if( lwr>=-127 && upr<=127 ){4229 zType = "signed char";4230 nByte = 1;4231 }else if( lwr>=-32767 && upr<32767 ){4232 zType = "short";4233 nByte = 2;4234 }4235 if( pnByte ) *pnByte = nByte;4236 return zType;4237}4238 4239/*4240** Each state contains a set of token transaction and a set of4241** nonterminal transactions. Each of these sets makes an instance4242** of the following structure. An array of these structures is used4243** to order the creation of entries in the yy_action[] table.4244*/4245struct axset {4246 struct state *stp; /* A pointer to a state */4247 int isTkn; /* True to use tokens. False for non-terminals */4248 int nAction; /* Number of actions */4249 int iOrder; /* Original order of action sets */4250};4251 4252/*4253** Compare to axset structures for sorting purposes4254*/4255static int axset_compare(const void *a, const void *b){4256 struct axset *p1 = (struct axset*)a;4257 struct axset *p2 = (struct axset*)b;4258 int c;4259 c = p2->nAction - p1->nAction;4260 if( c==0 ){4261 c = p1->iOrder - p2->iOrder;4262 }4263 assert( c!=0 || p1==p2 )((void) sizeof ((c!=0 || p1==p2) ? 1 : 0), __extension__ ({ if
(c!=0 || p1==p2) ; else __assert_fail ("c!=0 || p1==p2", "tools/lemon/lemon.c"
, 4263, __extension__ __PRETTY_FUNCTION__); }));4264 return c;4265}4266 4267/*4268** Write text on "out" that describes the rule "rp".4269*/4270static void writeRuleText(FILE *out, struct rule *rp){4271 int j;4272 fprintf(out,"%s ::=", rp->lhs->name);4273 for(j=0; j<rp->nrhs; j++){4274 struct symbol *sp = rp->rhs[j];4275 if( sp->type!=MULTITERMINAL ){4276 fprintf(out," %s", sp->name);4277 }else{4278 int k;4279 fprintf(out," %s", sp->subsym[0]->name);4280 for(k=1; k<sp->nsubsym; k++){4281 fprintf(out,"|%s",sp->subsym[k]->name);4282 }4283 }4284 }4285}4286 4287 4288/* Generate C source code for the parser */4289void ReportTable(4290 struct lemon *lemp,4291 int mhflag, /* Output in makeheaders format if true */4292 int sqlFlag /* Generate the *.sql file too */4293){4294 FILE *out, *in, *sql;4295 int lineno;4296 struct state *stp;4297 struct action *ap;4298 struct rule *rp;4299 struct acttab *pActtab;4300 int i, j, n, sz;4301 int nLookAhead;4302 int szActionType; /* sizeof(YYACTIONTYPE) */4303 int szCodeType; /* sizeof(YYCODETYPE) */4304 const char *name;4305 int mnTknOfst, mxTknOfst;4306 int mnNtOfst, mxNtOfst;4307 struct axset *ax;4308 char *prefix;4309 4310 lemp->minShiftReduce = lemp->nstate;4311 lemp->errAction = lemp->minShiftReduce + lemp->nrule;4312 lemp->accAction = lemp->errAction + 1;4313 lemp->noAction = lemp->accAction + 1;4314 lemp->minReduce = lemp->noAction + 1;4315 lemp->maxAction = lemp->minReduce + lemp->nrule;4316 4317 in = tplt_open(lemp);4318 if( in==0 ) return;4319 out = file_open(lemp,".c","wb");4320 if( out==0 ){4321 fclose(in);4322 return;4323 }4324 if( sqlFlag==0 ){4325 sql = 0;4326 }else{4327 sql = file_open(lemp, ".sql", "wb");4328 if( sql==0 ){4329 fclose(in);4330 fclose(out);4331 return;4332 }4333 fprintf(sql,4334 "BEGIN;\n"4335 "CREATE TABLE symbol(\n"4336 " id INTEGER PRIMARY KEY,\n"4337 " name TEXT NOT NULL,\n"4338 " isTerminal BOOLEAN NOT NULL,\n"4339 " fallback INTEGER REFERENCES symbol"4340 " DEFERRABLE INITIALLY DEFERRED\n"4341 ");\n"4342 );4343 for(i=0; i<lemp->nsymbol; i++){4344 fprintf(sql,4345 "INSERT INTO symbol(id,name,isTerminal,fallback)"4346 "VALUES(%d,'%s',%s",4347 i, lemp->symbols[i]->name,4348 i<lemp->nterminal ? "TRUE" : "FALSE"4349 );4350 if( lemp->symbols[i]->fallback ){4351 fprintf(sql, ",%d);\n", lemp->symbols[i]->fallback->index);4352 }else{4353 fprintf(sql, ",NULL);\n");4354 }4355 }4356 fprintf(sql,4357 "CREATE TABLE rule(\n"4358 " ruleid INTEGER PRIMARY KEY,\n"4359 " lhs INTEGER REFERENCES symbol(id),\n"4360 " txt TEXT\n"4361 ");\n"4362 "CREATE TABLE rulerhs(\n"4363 " ruleid INTEGER REFERENCES rule(ruleid),\n"4364 " pos INTEGER,\n"4365 " sym INTEGER REFERENCES symbol(id)\n"4366 ");\n"4367 );4368 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){4369 assert( i==rp->iRule )((void) sizeof ((i==rp->iRule) ? 1 : 0), __extension__ ({ if
(i==rp->iRule) ; else __assert_fail ("i==rp->iRule", "tools/lemon/lemon.c"
, 4369, __extension__ __PRETTY_FUNCTION__); }));4370 fprintf(sql,4371 "INSERT INTO rule(ruleid,lhs,txt)VALUES(%d,%d,'",4372 rp->iRule, rp->lhs->index4373 );4374 writeRuleText(sql, rp);4375 fprintf(sql,"');\n");4376 for(j=0; j<rp->nrhs; j++){4377 struct symbol *sp = rp->rhs[j];4378 if( sp->type!=MULTITERMINAL ){4379 fprintf(sql,4380 "INSERT INTO rulerhs(ruleid,pos,sym)VALUES(%d,%d,%d);\n",4381 i,j,sp->index4382 );4383 }else{4384 int k;4385 for(k=0; k<sp->nsubsym; k++){4386 fprintf(sql,4387 "INSERT INTO rulerhs(ruleid,pos,sym)VALUES(%d,%d,%d);\n",4388 i,j,sp->subsym[k]->index4389 );4390 }4391 }4392 }4393 }4394 fprintf(sql, "COMMIT;\n");4395 }4396 lineno = 1;4397 4398 fprintf(out,4399 "/* This file is automatically generated by Lemon from input grammar\n"4400 "** source file \"%s\". */\n", lemp->filename); lineno += 2;4401 4402 /* The first %include directive begins with a C-language comment,4403 ** then skip over the header comment of the template file4404 */4405 if( lemp->include==0 ) lemp->include = "";4406 for(i=0; ISSPACE(lemp->include[i])((*__ctype_b_loc ())[(int) (((unsigned char)(lemp->include
[i])))] & (unsigned short int) _ISspace); i++){4407 if( lemp->include[i]=='\n' ){4408 lemp->include += i+1;4409 i = -1;4410 }4411 }4412 if( lemp->include[0]=='/' ){4413 tplt_skip_header(in,&lineno);4414 }else{4415 tplt_xfer(lemp->name,in,out,&lineno);4416 }4417 4418 /* Generate the include code, if any */4419 tplt_print(out,lemp,lemp->include,&lineno);4420 if( mhflag ){4421 char *incName = file_makename(lemp, ".h");4422 fprintf(out,"#include \"%s\"\n", incName); lineno++;4423 free(incName);4424 }4425 tplt_xfer(lemp->name,in,out,&lineno);4426 4427 /* Generate #defines for all tokens */4428 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;4429 else prefix = "";4430 if( mhflag ){4431 fprintf(out,"#if INTERFACE\n"); lineno++;4432 }else{4433 fprintf(out,"#ifndef %s%s\n", prefix, lemp->symbols[1]->name);4434 }4435 for(i=1; i<lemp->nterminal; i++){4436 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);4437 lineno++;4438 }4439 fprintf(out,"#endif\n"); lineno++;4440 tplt_xfer(lemp->name,in,out,&lineno);4441 4442 /* Generate the defines */4443 fprintf(out,"#define YYCODETYPE %s\n",4444 minimum_size_type(0, lemp->nsymbol, &szCodeType)); lineno++;4445 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol); lineno++;4446 fprintf(out,"#define YYACTIONTYPE %s\n",4447 minimum_size_type(0,lemp->maxAction,&szActionType)); lineno++;4448 if( lemp->wildcard ){4449 fprintf(out,"#define YYWILDCARD %d\n",4450 lemp->wildcard->index); lineno++;4451 }4452 print_stack_union(out,lemp,&lineno,mhflag);4453 fprintf(out, "#ifndef YYSTACKDEPTH\n"); lineno++;4454 if( lemp->stacksize ){4455 fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize); lineno++;4456 }else{4457 fprintf(out,"#define YYSTACKDEPTH 100\n"); lineno++;4458 }4459 fprintf(out, "#endif\n"); lineno++;4460 if( mhflag ){4461 fprintf(out,"#if INTERFACE\n"); lineno++;4462 }4463 name = lemp->name ? lemp->name : "Parse";4464 if( lemp->arg && lemp->arg[0] ){4465 i = lemonStrlen(lemp->arg)((int)strlen(lemp->arg));4466 while( i>=1 && ISSPACE(lemp->arg[i-1])((*__ctype_b_loc ())[(int) (((unsigned char)(lemp->arg[i-1
])))] & (unsigned short int) _ISspace) ) i--;4467 while( i>=1 && (ISALNUM(lemp->arg[i-1])((*__ctype_b_loc ())[(int) (((unsigned char)(lemp->arg[i-1
])))] & (unsigned short int) _ISalnum) || lemp->arg[i-1]=='_') ) i--;4468 fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg); lineno++;4469 fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg); lineno++;4470 fprintf(out,"#define %sARG_PARAM ,%s\n",name,&lemp->arg[i]); lineno++;4471 fprintf(out,"#define %sARG_FETCH %s=yypParser->%s;\n",4472 name,lemp->arg,&lemp->arg[i]); lineno++;4473 fprintf(out,"#define %sARG_STORE yypParser->%s=%s;\n",4474 name,&lemp->arg[i],&lemp->arg[i]); lineno++;4475 }else{4476 fprintf(out,"#define %sARG_SDECL\n",name); lineno++;4477 fprintf(out,"#define %sARG_PDECL\n",name); lineno++;4478 fprintf(out,"#define %sARG_PARAM\n",name); lineno++;4479 fprintf(out,"#define %sARG_FETCH\n",name); lineno++;4480 fprintf(out,"#define %sARG_STORE\n",name); lineno++;4481 }4482 if( lemp->ctx && lemp->ctx[0] ){4483 i = lemonStrlen(lemp->ctx)((int)strlen(lemp->ctx));4484 while( i>=1 && ISSPACE(lemp->ctx[i-1])((*__ctype_b_loc ())[(int) (((unsigned char)(lemp->ctx[i-1
])))] & (unsigned short int) _ISspace) ) i--;4485 while( i>=1 && (ISALNUM(lemp->ctx[i-1])((*__ctype_b_loc ())[(int) (((unsigned char)(lemp->ctx[i-1
])))] & (unsigned short int) _ISalnum) || lemp->ctx[i-1]=='_') ) i--;4486 fprintf(out,"#define %sCTX_SDECL %s;\n",name,lemp->ctx); lineno++;4487 fprintf(out,"#define %sCTX_PDECL ,%s\n",name,lemp->ctx); lineno++;4488 fprintf(out,"#define %sCTX_PARAM ,%s\n",name,&lemp->ctx[i]); lineno++;4489 fprintf(out,"#define %sCTX_FETCH %s=yypParser->%s;\n",4490 name,lemp->ctx,&lemp->ctx[i]); lineno++;4491 fprintf(out,"#define %sCTX_STORE yypParser->%s=%s;\n",4492 name,&lemp->ctx[i],&lemp->ctx[i]); lineno++;4493 }else{4494 fprintf(out,"#define %sCTX_SDECL\n",name); lineno++;4495 fprintf(out,"#define %sCTX_PDECL\n",name); lineno++;4496 fprintf(out,"#define %sCTX_PARAM\n",name); lineno++;4497 fprintf(out,"#define %sCTX_FETCH\n",name); lineno++;4498 fprintf(out,"#define %sCTX_STORE\n",name); lineno++;4499 }4500 if( mhflag ){4501 fprintf(out,"#endif\n"); lineno++;4502 }4503 if( lemp->errsym && lemp->errsym->useCnt ){4504 fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;4505 fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;4506 }4507 if( lemp->has_fallback ){4508 fprintf(out,"#define YYFALLBACK 1\n"); lineno++;4509 }4510 4511 /* Compute the action table, but do not output it yet. The action4512 ** table must be computed before generating the YYNSTATE macro because4513 ** we need to know how many states can be eliminated.4514 */4515 ax = (struct axset *) calloc(lemp->nxstate*2, sizeof(ax[0]));4516 if( ax==0 ){4517 fprintf(stderrstderr,"malloc failed\n");4518 exit(1);4519 }4520 for(i=0; i<lemp->nxstate; i++){4521 stp = lemp->sorted[i];4522 ax[i*2].stp = stp;4523 ax[i*2].isTkn = 1;4524 ax[i*2].nAction = stp->nTknAct;4525 ax[i*2+1].stp = stp;4526 ax[i*2+1].isTkn = 0;4527 ax[i*2+1].nAction = stp->nNtAct;4528 }4529 mxTknOfst = mnTknOfst = 0;4530 mxNtOfst = mnNtOfst = 0;4531 /* In an effort to minimize the action table size, use the heuristic4532 ** of placing the largest action sets first */4533 for(i=0; i<lemp->nxstate*2; i++) ax[i].iOrder = i;4534 qsort(ax, lemp->nxstate*2, sizeof(ax[0]), axset_compare);4535 pActtab = acttab_alloc(lemp->nsymbol, lemp->nterminal);4536 for(i=0; i<lemp->nxstate*2 && ax[i].nAction>0; i++){4537 stp = ax[i].stp;4538 if( ax[i].isTkn ){4539 for(ap=stp->ap; ap; ap=ap->next){4540 int action;4541 if( ap->sp->index>=lemp->nterminal ) continue;4542 action = compute_action(lemp, ap);4543 if( action<0 ) continue;4544 acttab_action(pActtab, ap->sp->index, action);4545 }4546 stp->iTknOfst = acttab_insert(pActtab, 1);4547 if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;4548 if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;4549 }else{4550 for(ap=stp->ap; ap; ap=ap->next){4551 int action;4552 if( ap->sp->index<lemp->nterminal ) continue;4553 if( ap->sp->index==lemp->nsymbol ) continue;4554 action = compute_action(lemp, ap);4555 if( action<0 ) continue;4556 acttab_action(pActtab, ap->sp->index, action);4557 }4558 stp->iNtOfst = acttab_insert(pActtab, 0);4559 if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;4560 if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;4561 }4562#if 0 /* Uncomment for a trace of how the yy_action[] table fills out */4563 { int jj, nn;4564 for(jj=nn=0; jj<pActtab->nAction; jj++){4565 if( pActtab->aAction[jj].action<0 ) nn++;4566 }4567 printf("%4d: State %3d %s n: %2d size: %5d freespace: %d\n",4568 i, stp->statenum, ax[i].isTkn ? "Token" : "Var ",4569 ax[i].nAction, pActtab->nAction, nn);4570 }4571#endif4572 }4573 free(ax);4574 4575 /* Mark rules that are actually used for reduce actions after all4576 ** optimizations have been applied4577 */4578 for(rp=lemp->rule; rp; rp=rp->next) rp->doesReduce = LEMON_FALSE;4579 for(i=0; i<lemp->nxstate; i++){4580 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){4581 if( ap->type==REDUCE || ap->type==SHIFTREDUCE ){4582 ap->x.rp->doesReduce = 1;4583 }4584 }4585 }4586 4587 /* Finish rendering the constants now that the action table has4588 ** been computed */4589 fprintf(out,"#define YYNSTATE %d\n",lemp->nxstate); lineno++;4590 fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++;4591 fprintf(out,"#define YYNRULE_WITH_ACTION %d\n",lemp->nruleWithAction);4592 lineno++;4593 fprintf(out,"#define YYNTOKEN %d\n",lemp->nterminal); lineno++;4594 fprintf(out,"#define YY_MAX_SHIFT %d\n",lemp->nxstate-1); lineno++;4595 i = lemp->minShiftReduce;4596 fprintf(out,"#define YY_MIN_SHIFTREDUCE %d\n",i); lineno++;4597 i += lemp->nrule;4598 fprintf(out,"#define YY_MAX_SHIFTREDUCE %d\n", i-1); lineno++;4599 fprintf(out,"#define YY_ERROR_ACTION %d\n", lemp->errAction); lineno++;4600 fprintf(out,"#define YY_ACCEPT_ACTION %d\n", lemp->accAction); lineno++;4601 fprintf(out,"#define YY_NO_ACTION %d\n", lemp->noAction); lineno++;4602 fprintf(out,"#define YY_MIN_REDUCE %d\n", lemp->minReduce); lineno++;4603 i = lemp->minReduce + lemp->nrule;4604 fprintf(out,"#define YY_MAX_REDUCE %d\n", i-1); lineno++;4605 tplt_xfer(lemp->name,in,out,&lineno);4606 4607 /* Now output the action table and its associates:4608 **4609 ** yy_action[] A single table containing all actions.4610 ** yy_lookahead[] A table containing the lookahead for each entry in4611 ** yy_action. Used to detect hash collisions.4612 ** yy_shift_ofst[] For each state, the offset into yy_action for4613 ** shifting terminals.4614 ** yy_reduce_ofst[] For each state, the offset into yy_action for4615 ** shifting non-terminals after a reduce.4616 ** yy_default[] Default action for each state.4617 */4618 4619 /* Output the yy_action table */4620 lemp->nactiontab = n = acttab_action_size(pActtab);4621 lemp->tablesize += n*szActionType;4622 fprintf(out,"#define YY_ACTTAB_COUNT (%d)\n", n); lineno++;4623 fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;4624 for(i=j=0; i<n; i++){4625 int action = acttab_yyaction(pActtab, i)((pActtab)->aAction[i].action);4626 if( action<0 ) action = lemp->noAction;4627 if( j==0 ) fprintf(out," /* %5d */ ", i);4628 fprintf(out, " %4d,", action);4629 if( j==9 || i==n-1 ){4630 fprintf(out, "\n"); lineno++;4631 j = 0;4632 }else{4633 j++;4634 }4635 }4636 fprintf(out, "};\n"); lineno++;4637 4638 /* Output the yy_lookahead table */4639 lemp->nlookaheadtab = n = acttab_lookahead_size(pActtab)((pActtab)->nAction);4640 lemp->tablesize += n*szCodeType;4641 fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;4642 for(i=j=0; i<n; i++){4643 int la = acttab_yylookahead(pActtab, i)((pActtab)->aAction[i].lookahead);4644 if( la<0 ) la = lemp->nsymbol;4645 if( j==0 ) fprintf(out," /* %5d */ ", i);4646 fprintf(out, " %4d,", la);4647 if( j==9 ){4648 fprintf(out, "\n"); lineno++;4649 j = 0;4650 }else{4651 j++;4652 }4653 }4654 /* Add extra entries to the end of the yy_lookahead[] table so that4655 ** yy_shift_ofst[]+iToken will always be a valid index into the array,4656 ** even for the largest possible value of yy_shift_ofst[] and iToken. */4657 nLookAhead = lemp->nterminal + lemp->nactiontab;4658 while( i<nLookAhead ){4659 if( j==0 ) fprintf(out," /* %5d */ ", i);4660 fprintf(out, " %4d,", lemp->nterminal);4661 if( j==9 ){4662 fprintf(out, "\n"); lineno++;4663 j = 0;4664 }else{4665 j++;4666 }4667 i++;4668 }4669 if( j>0 ){ fprintf(out, "\n"); lineno++; }4670 fprintf(out, "};\n"); lineno++;4671 4672 /* Output the yy_shift_ofst[] table */4673 n = lemp->nxstate;4674 while( n>0 && lemp->sorted[n-1]->iTknOfst==NO_OFFSET(-2147483647) ) n--;4675 fprintf(out, "#define YY_SHIFT_COUNT (%d)\n", n-1); lineno++;4676 fprintf(out, "#define YY_SHIFT_MIN (%d)\n", mnTknOfst); lineno++;4677 fprintf(out, "#define YY_SHIFT_MAX (%d)\n", mxTknOfst); lineno++;4678 fprintf(out, "static const %s yy_shift_ofst[] = {\n",4679 minimum_size_type(mnTknOfst, lemp->nterminal+lemp->nactiontab, &sz));4680 lineno++;4681 lemp->tablesize += n*sz;4682 for(i=j=0; i<n; i++){4683 int ofst;4684 stp = lemp->sorted[i];4685 ofst = stp->iTknOfst;4686 if( ofst==NO_OFFSET(-2147483647) ) ofst = lemp->nactiontab;4687 if( j==0 ) fprintf(out," /* %5d */ ", i);4688 fprintf(out, " %4d,", ofst);4689 if( j==9 || i==n-1 ){4690 fprintf(out, "\n"); lineno++;4691 j = 0;4692 }else{4693 j++;4694 }4695 }4696 fprintf(out, "};\n"); lineno++;4697 4698 /* Output the yy_reduce_ofst[] table */4699 n = lemp->nxstate;4700 while( n>0 && lemp->sorted[n-1]->iNtOfst==NO_OFFSET(-2147483647) ) n--;4701 fprintf(out, "#define YY_REDUCE_COUNT (%d)\n", n-1); lineno++;4702 fprintf(out, "#define YY_REDUCE_MIN (%d)\n", mnNtOfst); lineno++;4703 fprintf(out, "#define YY_REDUCE_MAX (%d)\n", mxNtOfst); lineno++;4704 fprintf(out, "static const %s yy_reduce_ofst[] = {\n",4705 minimum_size_type(mnNtOfst-1, mxNtOfst, &sz)); lineno++;4706 lemp->tablesize += n*sz;4707 for(i=j=0; i<n; i++){4708 int ofst;4709 stp = lemp->sorted[i];4710 ofst = stp->iNtOfst;4711 if( ofst==NO_OFFSET(-2147483647) ) ofst = mnNtOfst - 1;4712 if( j==0 ) fprintf(out," /* %5d */ ", i);4713 fprintf(out, " %4d,", ofst);4714 if( j==9 || i==n-1 ){4715 fprintf(out, "\n"); lineno++;4716 j = 0;4717 }else{4718 j++;4719 }4720 }4721 fprintf(out, "};\n"); lineno++;4722 4723 /* Output the default action table */4724 fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;4725 n = lemp->nxstate;4726 lemp->tablesize += n*szActionType;4727 for(i=j=0; i<n; i++){4728 stp = lemp->sorted[i];4729 if( j==0 ) fprintf(out," /* %5d */ ", i);4730 if( stp->iDfltReduce<0 ){4731 fprintf(out, " %4d,", lemp->errAction);4732 }else{4733 fprintf(out, " %4d,", stp->iDfltReduce + lemp->minReduce);4734 }4735 if( j==9 || i==n-1 ){4736 fprintf(out, "\n"); lineno++;4737 j = 0;4738 }else{4739 j++;4740 }4741 }4742 fprintf(out, "};\n"); lineno++;4743 tplt_xfer(lemp->name,in,out,&lineno);4744 4745 /* Generate the table of fallback tokens.4746 */4747 if( lemp->has_fallback ){4748 int mx = lemp->nterminal - 1;4749 /* 2019-08-28: Generate fallback entries for every token to avoid4750 ** having to do a range check on the index */4751 /* while( mx>0 && lemp->symbols[mx]->fallback==0 ){ mx--; } */4752 lemp->tablesize += (mx+1)*szCodeType;4753 for(i=0; i<=mx; i++){4754 struct symbol *p = lemp->symbols[i];4755 if( p->fallback==0 ){4756 fprintf(out, " 0, /* %10s => nothing */\n", p->name);4757 }else{4758 fprintf(out, " %3d, /* %10s => %s */\n", p->fallback->index,4759 p->name, p->fallback->name);4760 }4761 lineno++;4762 }4763 }4764 tplt_xfer(lemp->name, in, out, &lineno);4765 4766 /* Generate a table containing the symbolic name of every symbol4767 */4768 for(i=0; i<lemp->nsymbol; i++){4769 fprintf(out," /* %4d */ \"%s\",\n",i, lemp->symbols[i]->name); lineno++;4770 }4771 tplt_xfer(lemp->name,in,out,&lineno);4772 4773 /* Generate a table containing a text string that describes every4774 ** rule in the rule set of the grammar. This information is used4775 ** when tracing REDUCE actions.4776 */4777 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){4778 assert( rp->iRule==i )((void) sizeof ((rp->iRule==i) ? 1 : 0), __extension__ ({ if
(rp->iRule==i) ; else __assert_fail ("rp->iRule==i", "tools/lemon/lemon.c"
, 4778, __extension__ __PRETTY_FUNCTION__); }));4779 fprintf(out," /* %3d */ \"", i);4780 writeRuleText(out, rp);4781 fprintf(out,"\",\n"); lineno++;4782 }4783 tplt_xfer(lemp->name,in,out,&lineno);4784 4785 /* Generate code which executes every time a symbol is popped from4786 ** the stack while processing errors or while destroying the parser.4787 ** (In other words, generate the %destructor actions)4788 */4789 if( lemp->tokendest ){4790 int once = 1;4791 for(i=0; i<lemp->nsymbol; i++){4792 struct symbol *sp = lemp->symbols[i];4793 if( sp==0 || sp->type!=TERMINAL ) continue;4794 if( once ){4795 fprintf(out, " /* TERMINAL Destructor */\n"); lineno++;4796 once = 0;4797 }4798 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;4799 }4800 for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);4801 if( i<lemp->nsymbol ){4802 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);4803 fprintf(out," break;\n"); lineno++;4804 }4805 }4806 if( lemp->vardest ){4807 struct symbol *dflt_sp = 0;4808 int once = 1;4809 for(i=0; i<lemp->nsymbol; i++){4810 struct symbol *sp = lemp->symbols[i];4811 if( sp==0 || sp->type==TERMINAL ||4812 sp->index<=0 || sp->destructor!=0 ) continue;4813 if( once ){4814 fprintf(out, " /* Default NON-TERMINAL Destructor */\n");lineno++;4815 once = 0;4816 }4817 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;4818 dflt_sp = sp;4819 }4820 if( dflt_sp!=0 ){4821 emit_destructor_code(out,dflt_sp,lemp,&lineno);4822 }4823 fprintf(out," break;\n"); lineno++;4824 }4825 for(i=0; i<lemp->nsymbol; i++){4826 struct symbol *sp = lemp->symbols[i];4827 if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;4828 if( sp->destLineno<0 ) continue; /* Already emitted */4829 fprintf(out," case %d: /* %s */\n", sp->index, sp->name); lineno++;4830 4831 /* Combine duplicate destructors into a single case */4832 for(j=i+1; j<lemp->nsymbol; j++){4833 struct symbol *sp2 = lemp->symbols[j];4834 if( sp2 && sp2->type!=TERMINAL && sp2->destructor4835 && sp2->dtnum==sp->dtnum4836 && strcmp(sp->destructor,sp2->destructor)==0 ){4837 fprintf(out," case %d: /* %s */\n",4838 sp2->index, sp2->name); lineno++;4839 sp2->destLineno = -1; /* Avoid emitting this destructor again */4840 }4841 }4842 4843 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);4844 fprintf(out," break;\n"); lineno++;4845 }4846 tplt_xfer(lemp->name,in,out,&lineno);4847 4848 /* Generate code which executes whenever the parser stack overflows */4849 tplt_print(out,lemp,lemp->overflow,&lineno);4850 tplt_xfer(lemp->name,in,out,&lineno);4851 4852 /* Generate the tables of rule information. yyRuleInfoLhs[] and4853 ** yyRuleInfoNRhs[].4854 **4855 ** Note: This code depends on the fact that rules are number4856 ** sequentially beginning with 0.4857 */4858 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){4859 fprintf(out," %4d, /* (%d) ", rp->lhs->index, i);4860 rule_print(out, rp);4861 fprintf(out," */\n"); lineno++;4862 }4863 tplt_xfer(lemp->name,in,out,&lineno);4864 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){4865 fprintf(out," %3d, /* (%d) ", -rp->nrhs, i);4866 rule_print(out, rp);4867 fprintf(out," */\n"); lineno++;4868 }4869 tplt_xfer(lemp->name,in,out,&lineno);4870 4871 /* Generate code which execution during each REDUCE action */4872 i = 0;4873 for(rp=lemp->rule; rp; rp=rp->next){4874 i += translate_code(lemp, rp);4875 }4876 if( i ){4877 fprintf(out," YYMINORTYPE yylhsminor;\n"); lineno++;4878 }4879 /* First output rules other than the default: rule */4880 for(rp=lemp->rule; rp; rp=rp->next){4881 struct rule *rp2; /* Other rules with the same action */4882 if( rp->codeEmitted ) continue;4883 if( rp->noCode ){4884 /* No C code actions, so this will be part of the "default:" rule */4885 continue;4886 }4887 fprintf(out," case %d: /* ", rp->iRule);4888 writeRuleText(out, rp);4889 fprintf(out, " */\n"); lineno++;4890 for(rp2=rp->next; rp2; rp2=rp2->next){4891 if( rp2->code==rp->code && rp2->codePrefix==rp->codePrefix4892 && rp2->codeSuffix==rp->codeSuffix ){4893 fprintf(out," case %d: /* ", rp2->iRule);4894 writeRuleText(out, rp2);4895 fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->iRule); lineno++;4896 rp2->codeEmitted = 1;4897 }4898 }4899 emit_code(out,rp,lemp,&lineno);4900 fprintf(out," break;\n"); lineno++;4901 rp->codeEmitted = 1;4902 }4903 /* Finally, output the default: rule. We choose as the default: all4904 ** empty actions. */4905 fprintf(out," default:\n"); lineno++;4906 for(rp=lemp->rule; rp; rp=rp->next){4907 if( rp->codeEmitted ) continue;4908 assert( rp->noCode )((void) sizeof ((rp->noCode) ? 1 : 0), __extension__ ({ if
(rp->noCode) ; else __assert_fail ("rp->noCode", "tools/lemon/lemon.c"
, 4908, __extension__ __PRETTY_FUNCTION__); }));4909 fprintf(out," /* (%d) ", rp->iRule);4910 writeRuleText(out, rp);4911 if( rp->neverReduce ){4912 fprintf(out, " (NEVER REDUCES) */ assert(yyruleno!=%d);\n",4913 rp->iRule); lineno++;4914 }else if( rp->doesReduce ){4915 fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->iRule); lineno++;4916 }else{4917 fprintf(out, " (OPTIMIZED OUT) */ assert(yyruleno!=%d);\n",4918 rp->iRule); lineno++;4919 }4920 }4921 fprintf(out," break;\n"); lineno++;4922 tplt_xfer(lemp->name,in,out,&lineno);4923 4924 /* Generate code which executes if a parse fails */4925 tplt_print(out,lemp,lemp->failure,&lineno);4926 tplt_xfer(lemp->name,in,out,&lineno);4927 4928 /* Generate code which executes when a syntax error occurs */4929 tplt_print(out,lemp,lemp->error,&lineno);4930 tplt_xfer(lemp->name,in,out,&lineno);4931 4932 /* Generate code which executes when the parser accepts its input */4933 tplt_print(out,lemp,lemp->accept,&lineno);4934 tplt_xfer(lemp->name,in,out,&lineno);4935 4936 /* Append any addition code the user desires */4937 tplt_print(out,lemp,lemp->extracode,&lineno);4938 4939 acttab_free(pActtab);4940 fclose(in);4941 fclose(out);4942 if( sql ) fclose(sql);4943 return;4944}4945 4946/* Generate a header file for the parser */4947void ReportHeader(struct lemon *lemp)4948{4949 FILE *out, *in;4950 const char *prefix;4951 char line[LINESIZE1000];4952 char pattern[LINESIZE1000];4953 int i;4954 4955 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;4956 else prefix = "";4957 in = file_open(lemp,".h","rb");4958 if( in ){4959 int nextChar;4960 for(i=1; i<lemp->nterminal && fgets(line,LINESIZE1000,in); i++){4961 lemon_sprintf(pattern,"#define %s%-30s %3d\n",4962 prefix,lemp->symbols[i]->name,i);4963 if( strcmp(line,pattern) ) break;4964 }4965 nextChar = fgetc(in);4966 fclose(in);4967 if( i==lemp->nterminal && nextChar==EOF(-1) ){4968 /* No change in the file. Don't rewrite it. */4969 return;4970 }4971 }4972 out = file_open(lemp,".h","wb");4973 if( out ){4974 for(i=1; i<lemp->nterminal; i++){4975 fprintf(out,"#define %s%-30s %3d\n",prefix,lemp->symbols[i]->name,i);4976 }4977 fclose(out);4978 }4979 return;4980}4981 4982/* Reduce the size of the action tables, if possible, by making use4983** of defaults.4984**4985** In this version, we take the most frequent REDUCE action and make4986** it the default. Except, there is no default if the wildcard token4987** is a possible look-ahead.4988*/4989void CompressTables(struct lemon *lemp)4990{4991 struct state *stp;4992 struct action *ap, *ap2, *nextap;4993 struct rule *rp, *rp2, *rbest;4994 int nbest, n;4995 int i;4996 int usesWildcard;4997 4998 for(i=0; i<lemp->nstate; i++){4999 stp = lemp->sorted[i];5000 nbest = 0;5001 rbest = 0;5002 usesWildcard = 0;5003 5004 for(ap=stp->ap; ap; ap=ap->next){5005 if( ap->type==SHIFT && ap->sp==lemp->wildcard ){5006 usesWildcard = 1;5007 }5008 if( ap->type!=REDUCE ) continue;5009 rp = ap->x.rp;5010 if( rp->lhsStart ) continue;5011 if( rp==rbest ) continue;5012 n = 1;5013 for(ap2=ap->next; ap2; ap2=ap2->next){5014 if( ap2->type!=REDUCE ) continue;5015 rp2 = ap2->x.rp;5016 if( rp2==rbest ) continue;5017 if( rp2==rp ) n++;5018 }5019 if( n>nbest ){5020 nbest = n;5021 rbest = rp;5022 }5023 }5024 5025 /* Do not make a default if the number of rules to default5026 ** is not at least 1 or if the wildcard token is a possible5027 ** lookahead.5028 */5029 if( nbest<1 || usesWildcard ) continue;5030 5031 5032 /* Combine matching REDUCE actions into a single default */5033 for(ap=stp->ap; ap; ap=ap->next){5034 if( ap->type==REDUCE && ap->x.rp==rbest ) break;5035 }5036 assert( ap )((void) sizeof ((ap) ? 1 : 0), __extension__ ({ if (ap) ; else
__assert_fail ("ap", "tools/lemon/lemon.c", 5036, __extension__
__PRETTY_FUNCTION__); }));5037 ap->sp = Symbol_new("{default}");5038 for(ap=ap->next; ap; ap=ap->next){5039 if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;5040 }5041 stp->ap = Action_sort(stp->ap);5042 5043 for(ap=stp->ap; ap; ap=ap->next){5044 if( ap->type==SHIFT ) break;5045 if( ap->type==REDUCE && ap->x.rp!=rbest ) break;5046 }5047 if( ap==0 ){5048 stp->autoReduce = 1;5049 stp->pDfltReduce = rbest;5050 }5051 }5052 5053 /* Make a second pass over all states and actions. Convert5054 ** every action that is a SHIFT to an autoReduce state into5055 ** a SHIFTREDUCE action.5056 */5057 for(i=0; i<lemp->nstate; i++){5058 stp = lemp->sorted[i];5059 for(ap=stp->ap; ap; ap=ap->next){5060 struct state *pNextState;5061 if( ap->type!=SHIFT ) continue;5062 pNextState = ap->x.stp;5063 if( pNextState->autoReduce && pNextState->pDfltReduce!=0 ){5064 ap->type = SHIFTREDUCE;5065 ap->x.rp = pNextState->pDfltReduce;5066 }5067 }5068 }5069 5070 /* If a SHIFTREDUCE action specifies a rule that has a single RHS term5071 ** (meaning that the SHIFTREDUCE will land back in the state where it5072 ** started) and if there is no C-code associated with the reduce action,5073 ** then we can go ahead and convert the action to be the same as the5074 ** action for the RHS of the rule.5075 */5076 for(i=0; i<lemp->nstate; i++){5077 stp = lemp->sorted[i];5078 for(ap=stp->ap; ap; ap=nextap){5079 nextap = ap->next;5080 if( ap->type!=SHIFTREDUCE ) continue;5081 rp = ap->x.rp;5082 if( rp->noCode==0 ) continue;5083 if( rp->nrhs!=1 ) continue;5084#if 15085 /* Only apply this optimization to non-terminals. It would be OK to5086 ** apply it to terminal symbols too, but that makes the parser tables5087 ** larger. */5088 if( ap->sp->index<lemp->nterminal ) continue;5089#endif5090 /* If we reach this point, it means the optimization can be applied */5091 nextap = ap;5092 for(ap2=stp->ap; ap2 && (ap2==ap || ap2->sp!=rp->lhs); ap2=ap2->next){}5093 assert( ap2!=0 )((void) sizeof ((ap2!=0) ? 1 : 0), __extension__ ({ if (ap2!=
0) ; else __assert_fail ("ap2!=0", "tools/lemon/lemon.c", 5093
, __extension__ __PRETTY_FUNCTION__); }));5094 ap->spOpt = ap2->sp;5095 ap->type = ap2->type;5096 ap->x = ap2->x;5097 }5098 }5099}5100 5101 5102/*5103** Compare two states for sorting purposes. The smaller state is the5104** one with the most non-terminal actions. If they have the same number5105** of non-terminal actions, then the smaller is the one with the most5106** token actions.5107*/5108static int stateResortCompare(const void *a, const void *b){5109 const struct state *pA = *(const struct state**)a;5110 const struct state *pB = *(const struct state**)b;5111 int n;5112 5113 n = pB->nNtAct - pA->nNtAct;5114 if( n==0 ){5115 n = pB->nTknAct - pA->nTknAct;5116 if( n==0 ){5117 n = pB->statenum - pA->statenum;5118 }5119 }5120 assert( n!=0 )((void) sizeof ((n!=0) ? 1 : 0), __extension__ ({ if (n!=0) ;
else __assert_fail ("n!=0", "tools/lemon/lemon.c", 5120, __extension__
__PRETTY_FUNCTION__); }));5121 return n;5122}5123 5124 5125/*5126** Renumber and resort states so that states with fewer choices5127** occur at the end. Except, keep state 0 as the first state.5128*/5129void ResortStates(struct lemon *lemp)5130{5131 int i;5132 struct state *stp;5133 struct action *ap;5134 5135 for(i=0; i<lemp->nstate; i++){5136 stp = lemp->sorted[i];5137 stp->nTknAct = stp->nNtAct = 0;5138 stp->iDfltReduce = -1; /* Init dflt action to "syntax error" */5139 stp->iTknOfst = NO_OFFSET(-2147483647);5140 stp->iNtOfst = NO_OFFSET(-2147483647);5141 for(ap=stp->ap; ap; ap=ap->next){5142 int iAction = compute_action(lemp,ap);5143 if( iAction>=0 ){5144 if( ap->sp->index<lemp->nterminal ){5145 stp->nTknAct++;5146 }else if( ap->sp->index<lemp->nsymbol ){5147 stp->nNtAct++;5148 }else{5149 assert( stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp )((void) sizeof ((stp->autoReduce==0 || stp->pDfltReduce
==ap->x.rp) ? 1 : 0), __extension__ ({ if (stp->autoReduce
==0 || stp->pDfltReduce==ap->x.rp) ; else __assert_fail
("stp->autoReduce==0 || stp->pDfltReduce==ap->x.rp"
, "tools/lemon/lemon.c", 5149, __extension__ __PRETTY_FUNCTION__
); }));5150 stp->iDfltReduce = iAction;5151 }5152 }5153 }5154 }5155 qsort(&lemp->sorted[1], lemp->nstate-1, sizeof(lemp->sorted[0]),5156 stateResortCompare);5157 for(i=0; i<lemp->nstate; i++){5158 lemp->sorted[i]->statenum = i;5159 }5160 lemp->nxstate = lemp->nstate;5161 while( lemp->nxstate>1 && lemp->sorted[lemp->nxstate-1]->autoReduce ){5162 lemp->nxstate--;5163 }5164}5165 5166 5167/***************** From the file "set.c" ************************************/5168/*5169** Set manipulation routines for the LEMON parser generator.5170*/5171 5172static int size = 0;5173 5174/* Set the set size */5175void SetSize(int n)5176{5177 size = n+1;5178}5179 5180/* Allocate a new set */5181char *SetNew(void){5182 char *s;5183 s = (char*)calloc( size, 1);5184 if( s==0 ){5185 memory_error();5186 }5187 return s;5188}5189 5190/* Deallocate a set */5191void SetFree(char *s)5192{5193 free(s);5194}5195 5196/* Add a new element to the set. Return TRUE if the element was added5197** and FALSE if it was already there. */5198int SetAdd(char *s, int e)5199{5200 int rv;5201 assert( e>=0 && e<size )((void) sizeof ((e>=0 && e<size) ? 1 : 0), __extension__
({ if (e>=0 && e<size) ; else __assert_fail ("e>=0 && e<size"
, "tools/lemon/lemon.c", 5201, __extension__ __PRETTY_FUNCTION__
); }));5202 rv = s[e];5203 s[e] = 1;5204 return !rv;5205}5206 5207/* Add every element of s2 to s1. Return TRUE if s1 changes. */5208int SetUnion(char *s1, char *s2)5209{5210 int i, progress;5211 progress = 0;5212 for(i=0; i<size; i++){5213 if( s2[i]==0 ) continue;5214 if( s1[i]==0 ){5215 progress = 1;5216 s1[i] = 1;5217 }5218 }5219 return progress;5220}5221/********************** From the file "table.c" ****************************/5222/*5223** All code in this file has been automatically generated5224** from a specification in the file5225** "table.q"5226** by the associative array code building program "aagen".5227** Do not edit this file! Instead, edit the specification5228** file, then rerun aagen.5229*/5230/*5231** Code for processing tables in the LEMON parser generator.5232*/5233 5234PRIVATE unsigned strhash(const char *x)5235{5236 unsigned h = 0;5237 while( *x ) h = h*13 + *(x++);5238 return h;5239}5240 5241/* Works like strdup, sort of. Save a string in malloced memory, but5242** keep strings in a table so that the same string is not in more5243** than one place.5244*/5245const char *Strsafe(const char *y)5246{5247 const char *z;5248 char *cpy;5249 5250 if( y==0 ) return 0;5251 z = Strsafe_find(y);5252 if( z==0 && (cpy=(char *)malloc( lemonStrlen(y)((int)strlen(y))+1 ))!=0 ){5253 lemon_strcpy(cpy,y);5254 z = cpy;5255 Strsafe_insert(z);5256 }5257 MemoryCheck(z)if((z)==0){ extern void memory_error(); memory_error(); };5258 return z;5259}5260 5261/* There is one instance of the following structure for each5262** associative array of type "x1".5263*/5264struct s_x1 {5265 int size; /* The number of available slots. */5266 /* Must be a power of 2 greater than or */5267 /* equal to 1 */5268 int count; /* Number of currently slots filled */5269 struct s_x1node *tbl; /* The data stored here */5270 struct s_x1node **ht; /* Hash table for lookups */5271};5272 5273/* There is one instance of this structure for every data element5274** in an associative array of type "x1".5275*/5276typedef struct s_x1node {5277 const char *data; /* The data */5278 struct s_x1node *next; /* Next entry with the same hash */5279 struct s_x1node **from; /* Previous link */5280} x1node;5281 5282/* There is only one instance of the array, which is the following */5283static struct s_x1 *x1a;5284 5285/* Allocate a new associative array */5286void Strsafe_init(void){5287 if( x1a ) return;5288 x1a = (struct s_x1*)malloc( sizeof(struct s_x1) );5289 if( x1a ){5290 x1a->size = 1024;5291 x1a->count = 0;5292 x1a->tbl = (x1node*)calloc(1024, sizeof(x1node) + sizeof(x1node*));5293 if( x1a->tbl==0 ){5294 free(x1a);5295 x1a = 0;5296 }else{5297 int i;5298 x1a->ht = (x1node**)&(x1a->tbl[1024]);5299 for(i=0; i<1024; i++) x1a->ht[i] = 0;5300 }5301 }5302}5303/* Insert a new record into the array. Return TRUE if successful.5304** Prior data with the same key is NOT overwritten */5305int Strsafe_insert(const char *data)5306{5307 x1node *np;5308 unsigned h;5309 unsigned ph;5310 5311 if( x1a==0 ) return 0;5312 ph = strhash(data);5313 h = ph & (x1a->size-1);5314 np = x1a->ht[h];5315 while( np ){5316 if( strcmp(np->data,data)==0 ){5317 /* An existing entry with the same key is found. */5318 /* Fail because overwrite is not allows. */5319 return 0;5320 }5321 np = np->next;5322 }5323 if( x1a->count>=x1a->size ){5324 /* Need to make the hash table bigger */5325 int i,arrSize;5326 struct s_x1 array;5327 array.size = arrSize = x1a->size*2;5328 array.count = x1a->count;5329 array.tbl = (x1node*)calloc(arrSize, sizeof(x1node) + sizeof(x1node*));5330 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */5331 array.ht = (x1node**)&(array.tbl[arrSize]);5332 for(i=0; i<arrSize; i++) array.ht[i] = 0;5333 for(i=0; i<x1a->count; i++){5334 x1node *oldnp, *newnp;5335 oldnp = &(x1a->tbl[i]);5336 h = strhash(oldnp->data) & (arrSize-1);5337 newnp = &(array.tbl[i]);5338 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);5339 newnp->next = array.ht[h];5340 newnp->data = oldnp->data;5341 newnp->from = &(array.ht[h]);5342 array.ht[h] = newnp;5343 }5344 /* free(x1a->tbl); // This program was originally for 16-bit machines.5345 ** Don't worry about freeing memory on modern platforms. */5346 *x1a = array;5347 }5348 /* Insert the new data */5349 h = ph & (x1a->size-1);5350 np = &(x1a->tbl[x1a->count++]);5351 np->data = data;5352 if( x1a->ht[h] ) x1a->ht[h]->from = &(np->next);5353 np->next = x1a->ht[h];5354 x1a->ht[h] = np;5355 np->from = &(x1a->ht[h]);5356 return 1;5357}5358 5359/* Return a pointer to data assigned to the given key. Return NULL5360** if no such key. */5361const char *Strsafe_find(const char *key)5362{5363 unsigned h;5364 x1node *np;5365 5366 if( x1a==0 ) return 0;5367 h = strhash(key) & (x1a->size-1);5368 np = x1a->ht[h];5369 while( np ){5370 if( strcmp(np->data,key)==0 ) break;5371 np = np->next;5372 }5373 return np ? np->data : 0;5374}5375 5376/* Return a pointer to the (terminal or nonterminal) symbol "x".5377** Create a new symbol if this is the first time "x" has been seen.5378*/5379struct symbol *Symbol_new(const char *x)5380{5381 struct symbol *sp;5382 5383 sp = Symbol_find(x);5384 if( sp==0 ){5385 sp = (struct symbol *)calloc(1, sizeof(struct symbol) );5386 MemoryCheck(sp)if((sp)==0){ extern void memory_error(); memory_error(); };5387 sp->name = Strsafe(x);5388 sp->type = ISUPPER(*x)((*__ctype_b_loc ())[(int) (((unsigned char)(*x)))] & (unsigned
short int) _ISupper) ? TERMINAL : NONTERMINAL;5389 sp->rule = 0;5390 sp->fallback = 0;5391 sp->prec = -1;5392 sp->assoc = UNK;5393 sp->firstset = 0;5394 sp->lambda = LEMON_FALSE;5395 sp->destructor = 0;5396 sp->destLineno = 0;5397 sp->datatype = 0;5398 sp->useCnt = 0;5399 Symbol_insert(sp,sp->name);5400 }5401 sp->useCnt++;5402 return sp;5403}5404 5405/* Compare two symbols for sorting purposes. Return negative,5406** zero, or positive if a is less then, equal to, or greater5407** than b.5408**5409** Symbols that begin with upper case letters (terminals or tokens)5410** must sort before symbols that begin with lower case letters5411** (non-terminals). And MULTITERMINAL symbols (created using the5412** %token_class directive) must sort at the very end. Other than5413** that, the order does not matter.5414**5415** We find experimentally that leaving the symbols in their original5416** order (the order they appeared in the grammar file) gives the5417** smallest parser tables in SQLite.5418*/5419int Symbolcmpp(const void *_a, const void *_b)5420{5421 const struct symbol *a = *(const struct symbol **) _a;5422 const struct symbol *b = *(const struct symbol **) _b;5423 int i1 = a->type==MULTITERMINAL ? 3 : a->name[0]>'Z' ? 2 : 1;5424 int i2 = b->type==MULTITERMINAL ? 3 : b->name[0]>'Z' ? 2 : 1;5425 return i1==i2 ? a->index - b->index : i1 - i2;5426}5427 5428/* There is one instance of the following structure for each5429** associative array of type "x2".5430*/5431struct s_x2 {5432 int size; /* The number of available slots. */5433 /* Must be a power of 2 greater than or */5434 /* equal to 1 */5435 int count; /* Number of currently slots filled */5436 struct s_x2node *tbl; /* The data stored here */5437 struct s_x2node **ht; /* Hash table for lookups */5438};5439 5440/* There is one instance of this structure for every data element5441** in an associative array of type "x2".5442*/5443typedef struct s_x2node {5444 struct symbol *data; /* The data */5445 const char *key; /* The key */5446 struct s_x2node *next; /* Next entry with the same hash */5447 struct s_x2node **from; /* Previous link */5448} x2node;5449 5450/* There is only one instance of the array, which is the following */5451static struct s_x2 *x2a;5452 5453/* Allocate a new associative array */5454void Symbol_init(void){5455 if( x2a ) return;5456 x2a = (struct s_x2*)malloc( sizeof(struct s_x2) );5457 if( x2a ){5458 x2a->size = 128;5459 x2a->count = 0;5460 x2a->tbl = (x2node*)calloc(128, sizeof(x2node) + sizeof(x2node*));5461 if( x2a->tbl==0 ){5462 free(x2a);5463 x2a = 0;5464 }else{5465 int i;5466 x2a->ht = (x2node**)&(x2a->tbl[128]);5467 for(i=0; i<128; i++) x2a->ht[i] = 0;5468 }5469 }5470}5471/* Insert a new record into the array. Return TRUE if successful.5472** Prior data with the same key is NOT overwritten */5473int Symbol_insert(struct symbol *data, const char *key)5474{5475 x2node *np;5476 unsigned h;5477 unsigned ph;5478 5479 if( x2a==0 ) return 0;5480 ph = strhash(key);5481 h = ph & (x2a->size-1);5482 np = x2a->ht[h];5483 while( np ){5484 if( strcmp(np->key,key)==0 ){5485 /* An existing entry with the same key is found. */5486 /* Fail because overwrite is not allows. */5487 return 0;5488 }5489 np = np->next;5490 }5491 if( x2a->count>=x2a->size ){5492 /* Need to make the hash table bigger */5493 int i,arrSize;5494 struct s_x2 array;5495 array.size = arrSize = x2a->size*2;5496 array.count = x2a->count;5497 array.tbl = (x2node*)calloc(arrSize, sizeof(x2node) + sizeof(x2node*));5498 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */5499 array.ht = (x2node**)&(array.tbl[arrSize]);5500 for(i=0; i<arrSize; i++) array.ht[i] = 0;5501 for(i=0; i<x2a->count; i++){5502 x2node *oldnp, *newnp;5503 oldnp = &(x2a->tbl[i]);5504 h = strhash(oldnp->key) & (arrSize-1);5505 newnp = &(array.tbl[i]);5506 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);5507 newnp->next = array.ht[h];5508 newnp->key = oldnp->key;5509 newnp->data = oldnp->data;5510 newnp->from = &(array.ht[h]);5511 array.ht[h] = newnp;5512 }5513 /* free(x2a->tbl); // This program was originally written for 16-bit5514 ** machines. Don't worry about freeing this trivial amount of memory5515 ** on modern platforms. Just leak it. */5516 *x2a = array;5517 }5518 /* Insert the new data */5519 h = ph & (x2a->size-1);5520 np = &(x2a->tbl[x2a->count++]);5521 np->key = key;5522 np->data = data;5523 if( x2a->ht[h] ) x2a->ht[h]->from = &(np->next);5524 np->next = x2a->ht[h];5525 x2a->ht[h] = np;5526 np->from = &(x2a->ht[h]);5527 return 1;5528}5529 5530/* Return a pointer to data assigned to the given key. Return NULL5531** if no such key. */5532struct symbol *Symbol_find(const char *key)5533{5534 unsigned h;5535 x2node *np;5536 5537 if( x2a==0 ) return 0;5538 h = strhash(key) & (x2a->size-1);5539 np = x2a->ht[h];5540 while( np ){5541 if( strcmp(np->key,key)==0 ) break;5542 np = np->next;5543 }5544 return np ? np->data : 0;5545}5546 5547/* Return the n-th data. Return NULL if n is out of range. */5548struct symbol *Symbol_Nth(int n)5549{5550 struct symbol *data;5551 if( x2a && n>0 && n<=x2a->count ){5552 data = x2a->tbl[n-1].data;5553 }else{5554 data = 0;5555 }5556 return data;5557}5558 5559/* Return the size of the array */5560int Symbol_count()5561{5562 return x2a ? x2a->count : 0;5563}5564 5565/* Return an array of pointers to all data in the table.5566** The array is obtained from malloc. Return NULL if memory allocation5567** problems, or if the array is empty. */5568struct symbol **Symbol_arrayof()5569{5570 struct symbol **array;5571 int i,arrSize;5572 if( x2a==0 ) return 0;5573 arrSize = x2a->count;5574 array = (struct symbol **)calloc(arrSize, sizeof(struct symbol *));5575 if( array ){5576 for(i=0; i<arrSize; i++) array[i] = x2a->tbl[i].data;5577 }5578 return array;5579}5580 5581/* Compare two configurations */5582int Configcmp(const char *_a,const char *_b)5583{5584 const struct config *a = (struct config *) _a;5585 const struct config *b = (struct config *) _b;5586 int x;5587 x = a->rp->index - b->rp->index;5588 if( x==0 ) x = a->dot - b->dot;5589 return x;5590}5591 5592/* Compare two states */5593PRIVATE int statecmp(struct config *a, struct config *b)5594{5595 int rc;5596 for(rc=0; rc==0 && a && b; a=a->bp, b=b->bp){5597 rc = a->rp->index - b->rp->index;5598 if( rc==0 ) rc = a->dot - b->dot;5599 }5600 if( rc==0 ){5601 if( a ) rc = 1;5602 if( b ) rc = -1;5603 }5604 return rc;5605}5606 5607/* Hash a state */5608PRIVATE unsigned statehash(struct config *a)5609{5610 unsigned h=0;5611 while( a ){5612 h = h*571 + a->rp->index*37 + a->dot;5613 a = a->bp;5614 }5615 return h;5616}5617 5618/* Allocate a new state structure */5619struct state *State_new()5620{5621 struct state *newstate;5622 newstate = (struct state *)calloc(1, sizeof(struct state) );5623 MemoryCheck(newstate)if((newstate)==0){ extern void memory_error(); memory_error()
; };5624 return newstate;5625}5626 5627/* There is one instance of the following structure for each5628** associative array of type "x3".5629*/5630struct s_x3 {5631 int size; /* The number of available slots. */5632 /* Must be a power of 2 greater than or */5633 /* equal to 1 */5634 int count; /* Number of currently slots filled */5635 struct s_x3node *tbl; /* The data stored here */5636 struct s_x3node **ht; /* Hash table for lookups */5637};5638 5639/* There is one instance of this structure for every data element5640** in an associative array of type "x3".5641*/5642typedef struct s_x3node {5643 struct state *data; /* The data */5644 struct config *key; /* The key */5645 struct s_x3node *next; /* Next entry with the same hash */5646 struct s_x3node **from; /* Previous link */5647} x3node;5648 5649/* There is only one instance of the array, which is the following */5650static struct s_x3 *x3a;5651 5652/* Allocate a new associative array */5653void State_init(void){5654 if( x3a ) return;5655 x3a = (struct s_x3*)malloc( sizeof(struct s_x3) );5656 if( x3a ){5657 x3a->size = 128;5658 x3a->count = 0;5659 x3a->tbl = (x3node*)calloc(128, sizeof(x3node) + sizeof(x3node*));5660 if( x3a->tbl==0 ){5661 free(x3a);5662 x3a = 0;5663 }else{5664 int i;5665 x3a->ht = (x3node**)&(x3a->tbl[128]);5666 for(i=0; i<128; i++) x3a->ht[i] = 0;5667 }5668 }5669}5670/* Insert a new record into the array. Return TRUE if successful.5671** Prior data with the same key is NOT overwritten */5672int State_insert(struct state *data, struct config *key)5673{5674 x3node *np;5675 unsigned h;5676 unsigned ph;5677 5678 if( x3a==0 ) return 0;5679 ph = statehash(key);5680 h = ph & (x3a->size-1);5681 np = x3a->ht[h];5682 while( np ){5683 if( statecmp(np->key,key)==0 ){5684 /* An existing entry with the same key is found. */5685 /* Fail because overwrite is not allows. */5686 return 0;5687 }5688 np = np->next;5689 }5690 if( x3a->count>=x3a->size ){5691 /* Need to make the hash table bigger */5692 int i,arrSize;5693 struct s_x3 array;5694 array.size = arrSize = x3a->size*2;5695 array.count = x3a->count;5696 array.tbl = (x3node*)calloc(arrSize, sizeof(x3node) + sizeof(x3node*));5697 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */5698 array.ht = (x3node**)&(array.tbl[arrSize]);5699 for(i=0; i<arrSize; i++) array.ht[i] = 0;5700 for(i=0; i<x3a->count; i++){5701 x3node *oldnp, *newnp;5702 oldnp = &(x3a->tbl[i]);5703 h = statehash(oldnp->key) & (arrSize-1);5704 newnp = &(array.tbl[i]);5705 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);5706 newnp->next = array.ht[h];5707 newnp->key = oldnp->key;5708 newnp->data = oldnp->data;5709 newnp->from = &(array.ht[h]);5710 array.ht[h] = newnp;5711 }5712 free(x3a->tbl);5713 *x3a = array;5714 }5715 /* Insert the new data */5716 h = ph & (x3a->size-1);5717 np = &(x3a->tbl[x3a->count++]);5718 np->key = key;5719 np->data = data;5720 if( x3a->ht[h] ) x3a->ht[h]->from = &(np->next);5721 np->next = x3a->ht[h];5722 x3a->ht[h] = np;5723 np->from = &(x3a->ht[h]);5724 return 1;5725}5726 5727/* Return a pointer to data assigned to the given key. Return NULL5728** if no such key. */5729struct state *State_find(struct config *key)5730{5731 unsigned h;5732 x3node *np;5733 5734 if( x3a==0 ) return 0;5735 h = statehash(key) & (x3a->size-1);5736 np = x3a->ht[h];5737 while( np ){5738 if( statecmp(np->key,key)==0 ) break;5739 np = np->next;5740 }5741 return np ? np->data : 0;5742}5743 5744/* Return an array of pointers to all data in the table.5745** The array is obtained from malloc. Return NULL if memory allocation5746** problems, or if the array is empty. */5747struct state **State_arrayof(void)5748{5749 struct state **array;5750 int i,arrSize;5751 if( x3a==0 ) return 0;5752 arrSize = x3a->count;5753 array = (struct state **)calloc(arrSize, sizeof(struct state *));5754 if( array ){5755 for(i=0; i<arrSize; i++) array[i] = x3a->tbl[i].data;5756 }5757 return array;5758}5759 5760/* Hash a configuration */5761PRIVATE unsigned confighash(struct config *a)5762{5763 unsigned h=0;5764 h = h*571 + a->rp->index*37 + a->dot;5765 return h;5766}5767 5768/* There is one instance of the following structure for each5769** associative array of type "x4".5770*/5771struct s_x4 {5772 int size; /* The number of available slots. */5773 /* Must be a power of 2 greater than or */5774 /* equal to 1 */5775 int count; /* Number of currently slots filled */5776 struct s_x4node *tbl; /* The data stored here */5777 struct s_x4node **ht; /* Hash table for lookups */5778};5779 5780/* There is one instance of this structure for every data element5781** in an associative array of type "x4".5782*/5783typedef struct s_x4node {5784 struct config *data; /* The data */5785 struct s_x4node *next; /* Next entry with the same hash */5786 struct s_x4node **from; /* Previous link */5787} x4node;5788 5789/* There is only one instance of the array, which is the following */5790static struct s_x4 *x4a;5791 5792/* Allocate a new associative array */5793void Configtable_init(void){5794 if( x4a ) return;5795 x4a = (struct s_x4*)malloc( sizeof(struct s_x4) );5796 if( x4a ){5797 x4a->size = 64;5798 x4a->count = 0;5799 x4a->tbl = (x4node*)calloc(64, sizeof(x4node) + sizeof(x4node*));5800 if( x4a->tbl==0 ){5801 free(x4a);5802 x4a = 0;5803 }else{5804 int i;5805 x4a->ht = (x4node**)&(x4a->tbl[64]);5806 for(i=0; i<64; i++) x4a->ht[i] = 0;5807 }5808 }5809}5810/* Insert a new record into the array. Return TRUE if successful.5811** Prior data with the same key is NOT overwritten */5812int Configtable_insert(struct config *data)5813{5814 x4node *np;5815 unsigned h;5816 unsigned ph;5817 5818 if( x4a==0 ) return 0;5819 ph = confighash(data);5820 h = ph & (x4a->size-1);5821 np = x4a->ht[h];5822 while( np ){5823 if( Configcmp((const char *) np->data,(const char *) data)==0 ){5824 /* An existing entry with the same key is found. */5825 /* Fail because overwrite is not allows. */5826 return 0;5827 }5828 np = np->next;5829 }5830 if( x4a->count>=x4a->size ){5831 /* Need to make the hash table bigger */5832 int i,arrSize;5833 struct s_x4 array;5834 array.size = arrSize = x4a->size*2;5835 array.count = x4a->count;5836 array.tbl = (x4node*)calloc(arrSize, sizeof(x4node) + sizeof(x4node*));5837 if( array.tbl==0 ) return 0; /* Fail due to malloc failure */5838 array.ht = (x4node**)&(array.tbl[arrSize]);5839 for(i=0; i<arrSize; i++) array.ht[i] = 0;5840 for(i=0; i<x4a->count; i++){5841 x4node *oldnp, *newnp;5842 oldnp = &(x4a->tbl[i]);5843 h = confighash(oldnp->data) & (arrSize-1);5844 newnp = &(array.tbl[i]);5845 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);5846 newnp->next = array.ht[h];5847 newnp->data = oldnp->data;5848 newnp->from = &(array.ht[h]);5849 array.ht[h] = newnp;5850 }5851 /* free(x4a->tbl); // This code was originally written for 16-bit machines.5852 ** on modern machines, don't worry about freeing this trival amount of5853 ** memory. */5854 *x4a = array;5855 }5856 /* Insert the new data */5857 h = ph & (x4a->size-1);5858 np = &(x4a->tbl[x4a->count++]);5859 np->data = data;5860 if( x4a->ht[h] ) x4a->ht[h]->from = &(np->next);5861 np->next = x4a->ht[h];5862 x4a->ht[h] = np;5863 np->from = &(x4a->ht[h]);5864 return 1;5865}5866 5867/* Return a pointer to data assigned to the given key. Return NULL5868** if no such key. */5869struct config *Configtable_find(struct config *key)5870{5871 int h;5872 x4node *np;5873 5874 if( x4a==0 ) return 0;5875 h = confighash(key) & (x4a->size-1);5876 np = x4a->ht[h];5877 while( np ){5878 if( Configcmp((const char *) np->data,(const char *) key)==0 ) break;5879 np = np->next;5880 }5881 return np ? np->data : 0;5882}5883 5884/* Remove all data from the table. Pass each data to the function "f"5885** as it is removed. ("f" may be null to avoid this step.) */5886void Configtable_clear(int(*f)(struct config *))5887{5888 int i;5889 if( x4a==0 || x4a->count==0 ) return;5890 if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);5891 for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;5892 x4a->count = 0;5893 return;5894}