/* Free all memory associated with the given acttab */void acttab_free(acttab *p){  free( p->aAction );  free( p->aLookahead );  free( p );}/* Allocate a new acttab structure */acttab *acttab_alloc(void){  acttab *p = malloc( sizeof(*p) );  if( p==0 ){    fprintf(stderr,"Unable to allocate memory for a new acttab.");    exit(1);  }  memset(p, 0, sizeof(*p));  return p;}/* Add a new action to the current transaction set*/void acttab_action(acttab *p, int lookahead, int action){  if( p->nLookahead>=p->nLookaheadAlloc ){    p->nLookaheadAlloc += 25;    p->aLookahead = realloc( p->aLookahead,                             sizeof(p->aLookahead[0])*p->nLookaheadAlloc );    if( p->aLookahead==0 ){      fprintf(stderr,"malloc failed\n");      exit(1);    }  }  if( p->nLookahead==0 ){    p->mxLookahead = lookahead;    p->mnLookahead = lookahead;    p->mnAction = action;  }else{    if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;    if( p->mnLookahead>lookahead ){      p->mnLookahead = lookahead;      p->mnAction = action;    }  }  p->aLookahead[p->nLookahead].lookahead = lookahead;  p->aLookahead[p->nLookahead].action = action;  p->nLookahead++;}/*** Add the transaction set built up with prior calls to acttab_action()** into the current action table.  Then reset the transaction set back** to an empty set in preparation for a new round of acttab_action() calls.**** Return the offset into the action table of the new transaction.*/int acttab_insert(acttab *p){  int i, j, k, n;  assert( p->nLookahead>0 );  /* Make sure we have enough space to hold the expanded action table  ** in the worst case.  The worst case occurs if the transaction set  ** must be appended to the current action table  */  n = p->mxLookahead + 1;  if( p->nAction + n >= p->nActionAlloc ){    int oldAlloc = p->nActionAlloc;    p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;    p->aAction = realloc( p->aAction,                          sizeof(p->aAction[0])*p->nActionAlloc);    if( p->aAction==0 ){      fprintf(stderr,"malloc failed\n");      exit(1);    }    for(i=oldAlloc; i<p->nActionAlloc; i++){      p->aAction[i].lookahead = -1;      p->aAction[i].action = -1;    }  }  /* Scan the existing action table looking for an offset where we can  ** insert the current transaction set.  Fall out of the loop when that  ** offset is found.  In the worst case, we fall out of the loop when  ** i reaches p->nAction, which means we append the new transaction set.  **  ** i is the index in p->aAction[] where p->mnLookahead is inserted.  */  for(i=0; i<p->nAction+p->mnLookahead; i++){    if( p->aAction[i].lookahead<0 ){      for(j=0; j<p->nLookahead; j++){        k = p->aLookahead[j].lookahead - p->mnLookahead + i;        if( k<0 ) break;        if( p->aAction[k].lookahead>=0 ) break;      }      if( j<p->nLookahead ) continue;      for(j=0; j<p->nAction; j++){        if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;      }      if( j==p->nAction ){        break;  /* Fits in empty slots */      }    }else if( p->aAction[i].lookahead==p->mnLookahead ){      if( p->aAction[i].action!=p->mnAction ) continue;      for(j=0; j<p->nLookahead; j++){        k = p->aLookahead[j].lookahead - p->mnLookahead + i;        if( k<0 || k>=p->nAction ) break;        if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;        if( p->aLookahead[j].action!=p->aAction[k].action ) break;      }      if( j<p->nLookahead ) continue;      n = 0;      for(j=0; j<p->nAction; j++){        if( p->aAction[j].lookahead<0 ) continue;        if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;      }      if( n==p->nLookahead ){        break;  /* Same as a prior transaction set */      }    }  }  /* Insert transaction set at index i. */  for(j=0; j<p->nLookahead; j++){    k = p->aLookahead[j].lookahead - p->mnLookahead + i;    p->aAction[k] = p->aLookahead[j];    if( k>=p->nAction ) p->nAction = k+1;  }  p->nLookahead = 0;  /* Return the offset that is added to the lookahead in order to get the  ** index into yy_action of the action */  return i - p->mnLookahead;}/********************** From the file "assert.c" ****************************//*** A more efficient way of handling assertions.*/void myassert(file,line)char *file;int line;{  fprintf(stderr,"Assertion failed on line %d of file \"%s\"\n",line,file);  exit(1);}/********************** From the file "build.c" *****************************//*** Routines to construction the finite state machine for the LEMON** parser generator.*//* Find a precedence symbol of every rule in the grammar.** ** Those rules which have a precedence symbol coded in the input** grammar using the "[symbol]" construct will already have the** rp->precsym field filled.  Other rules take as their precedence** symbol the first RHS symbol with a defined precedence.  If there** are not RHS symbols with a defined precedence, the precedence** symbol field is left blank.*/void FindRulePrecedences(xp)struct lemon *xp;{  struct rule *rp;  for(rp=xp->rule; rp; rp=rp->next){    if( rp->precsym==0 ){      int i, j;      for(i=0; i<rp->nrhs && rp->precsym==0; i++){        struct symbol *sp = rp->rhs[i];        if( sp->type==MULTITERMINAL ){          for(j=0; j<sp->nsubsym; j++){            if( sp->subsym[j]->prec>=0 ){              rp->precsym = sp->subsym[j];              break;            }          }        }else if( sp->prec>=0 ){          rp->precsym = rp->rhs[i];	}      }    }  }  return;}/* Find all nonterminals which will generate the empty string.** Then go back and compute the first sets of every nonterminal.** The first set is the set of all terminal symbols which can begin** a string generated by that nonterminal.*/void FindFirstSets(lemp)struct lemon *lemp;{  int i, j;  struct rule *rp;  int progress;  for(i=0; i<lemp->nsymbol; i++){    lemp->symbols[i]->lambda = B_FALSE;  }  for(i=lemp->nterminal; i<lemp->nsymbol; i++){    lemp->symbols[i]->firstset = SetNew();  }  /* First compute all lambdas */  do{    progress = 0;    for(rp=lemp->rule; rp; rp=rp->next){      if( rp->lhs->lambda ) continue;      for(i=0; i<rp->nrhs; i++){         struct symbol *sp = rp->rhs[i];         if( sp->type!=TERMINAL || sp->lambda==B_FALSE ) break;      }      if( i==rp->nrhs ){        rp->lhs->lambda = B_TRUE;        progress = 1;      }    }  }while( progress );  /* Now compute all first sets */  do{    struct symbol *s1, *s2;    progress = 0;    for(rp=lemp->rule; rp; rp=rp->next){      s1 = rp->lhs;      for(i=0; i<rp->nrhs; i++){        s2 = rp->rhs[i];        if( s2->type==TERMINAL ){          progress += SetAdd(s1->firstset,s2->index);          break;        }else if( s2->type==MULTITERMINAL ){          for(j=0; j<s2->nsubsym; j++){            progress += SetAdd(s1->firstset,s2->subsym[j]->index);          }          break;	}else if( s1==s2 ){          if( s1->lambda==B_FALSE ) break;	}else{          progress += SetUnion(s1->firstset,s2->firstset);          if( s2->lambda==B_FALSE ) break;	}      }    }  }while( progress );  return;}/* Compute all LR(0) states for the grammar.  Links** are added to between some states so that the LR(1) follow sets** can be computed later.*/PRIVATE struct state *getstate(/* struct lemon * */);  /* forward reference */void FindStates(lemp)struct lemon *lemp;{  struct symbol *sp;  struct rule *rp;  Configlist_init();  /* Find the start symbol */  if( lemp->start ){    sp = Symbol_find(lemp->start);    if( sp==0 ){      ErrorMsg(lemp->filename,0,"The specified start symbol \"%s\" is not \in a nonterminal of the grammar.  \"%s\" will be used as the start \symbol instead.",lemp->start,lemp->rule->lhs->name);      lemp->errorcnt++;      sp = lemp->rule->lhs;    }  }else{    sp = lemp->rule->lhs;  }  /* Make sure the start symbol doesn't occur on the right-hand side of  ** any rule.  Report an error if it does.  (YACC would generate a new  ** start symbol in this case.) */  for(rp=lemp->rule; rp; rp=rp->next){    int i;    for(i=0; i<rp->nrhs; i++){      if( rp->rhs[i]==sp ){   /* FIX ME:  Deal with multiterminals */        ErrorMsg(lemp->filename,0,"The start symbol \"%s\" occurs on the \right-hand side of a rule. This will result in a parser which \does not work properly.",sp->name);        lemp->errorcnt++;      }    }  }  /* The basis configuration set for the first state  ** is all rules which have the start symbol as their  ** left-hand side */  for(rp=sp->rule; rp; rp=rp->nextlhs){    struct config *newcfp;    newcfp = Configlist_addbasis(rp,0);    SetAdd(newcfp->fws,0);  }  /* Compute the first state.  All other states will be  ** computed automatically during the computation of the first one.  ** The returned pointer to the first state is not used. */  (void)getstate(lemp);  return;}/* Return a pointer to a state which is described by the configuration** list which has been built from calls to Configlist_add.*/PRIVATE void buildshifts(/* struct lemon *, struct state * */); /* Forwd ref */PRIVATE struct state *getstate(lemp)struct lemon *lemp;{  struct config *cfp, *bp;  struct state *stp;  /* Extract the sorted basis of the new state.  The basis was constructed  ** by prior calls to "Configlist_addbasis()". */  Configlist_sortbasis();  bp = Configlist_basis();  /* Get a state with the same basis */  stp = State_find(bp);  if( stp ){    /* A state with the same basis already exists!  Copy all the follow-set    ** propagation links from the state under construction into the    ** preexisting state, then return a pointer to the preexisting state */    struct config *x, *y;    for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){      Plink_copy(&y->bplp,x->bplp);      Plink_delete(x->fplp);      x->fplp = x->bplp = 0;    }    cfp = Configlist_return();    Configlist_eat(cfp);  }else{    /* This really is a new state.  Construct all the details */    Configlist_closure(lemp);    /* Compute the configuration closure */    Configlist_sort();           /* Sort the configuration closure */    cfp = Configlist_return();   /* Get a pointer to the config list */    stp = State_new();           /* A new state structure */    MemoryCheck(stp);    stp->bp = bp;                /* Remember the configuration basis */    stp->cfp = cfp;              /* Remember the configuration closure */    stp->statenum = lemp->nstate++; /* Every state gets a sequence number */    stp->ap = 0;                 /* No actions, yet. */    State_insert(stp,stp->bp);   /* Add to the state table */    buildshifts(lemp,stp);       /* Recursively compute successor states */  }  return stp;}/*** Return true if two symbols are the same.*/int same_symbol(a,b)struct symbol *a;struct symbol *b;{  int i;  if( a==b ) return 1;  if( a->type!=MULTITERMINAL ) return 0;  if( b->type!=MULTITERMINAL ) return 0;  if( a->nsubsym!=b->nsubsym ) return 0;  for(i=0; i<a->nsubsym; i++){    if( a->subsym[i]!=b->subsym[i] ) return 0;  }  return 1;}/* Construct all successor states to the given state.  A "successor"** state is any state which can be reached by a shift action.*/PRIVATE void buildshifts(lemp,stp)struct lemon *lemp;struct state *stp;     /* The state from which successors are computed */{  struct config *cfp;  /* For looping thru the config closure of "stp" */  struct config *bcfp; /* For the inner loop on config closure of "stp" */  struct config *new;  /* */  struct symbol *sp;   /* Symbol following the dot in configuration "cfp" */  struct symbol *bsp;  /* Symbol following the dot in configuration "bcfp" */  struct state *newstp; /* A pointer to a successor state */  /* Each configuration becomes complete after it contibutes to a successor  ** state.  Initially, all configurations are incomplete */  for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;  /* Loop through all configurations of the state "stp" */  for(cfp=stp->cfp; cfp; cfp=cfp->next){    if( cfp->status==COMPLETE ) continue;    /* Already used by inner loop */    if( cfp->dot>=cfp->rp->nrhs ) continue;  /* Can't shift this config */    Configlist_reset();                      /* Reset the new config set */    sp = cfp->rp->rhs[cfp->dot];             /* Symbol after the dot */    /* For every configuration in the state "stp" which has the symbol "sp"    ** following its dot, add the same configuration to the basis set under    ** construction but with the dot shifted one symbol to the right. */    for(bcfp=cfp; bcfp; bcfp=bcfp->next){      if( bcfp->status==COMPLETE ) continue;    /* Already used */      if( bcfp->dot>=bcfp->rp->nrhs ) continue; /* Can't shift this one */      bsp = bcfp->rp->rhs[bcfp->dot];           /* Get symbol after dot */      if( !same_symbol(bsp,sp) ) continue;      /* Must be same as for "cfp" */      bcfp->status = COMPLETE;                  /* Mark this config as used */      new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);      Plink_add(&new->bplp,bcfp);    }    /* Get a pointer to the state described by the basis configuration set    ** constructed in the preceding loop */    newstp = getstate(lemp);    /* The state "newstp" is reached from the state "stp" by a shift action    ** on the symbol "sp" */    if( sp->type==MULTITERMINAL ){      int i;      for(i=0; i<sp->nsubsym; i++){        Action_add(&stp->ap,SHIFT,sp->subsym[i],(char*)newstp);      }    }else{      Action_add(&stp->ap,SHIFT,sp,(char *)newstp);    }  }}/*** Construct the propagation links*/void FindLinks(lemp)struct lemon *lemp;{