lr0.c

Bison 是替代yacc的语法解析器. Bison能生成可以分析文本文件结构的程序.

/* subroutine of get_state.  create a new state for those items, if necessary.  */

core *
new_state(symbol)
int symbol;
{
  register int n;
  register core *p;
  register short *isp1;
  register short *isp2;
  register short *iend;

#ifdef	TRACE
  fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
#endif

  if (nstates >= MAXSHORT)
    toomany("states");

  isp1 = kernel_base[symbol];
  iend = kernel_end[symbol];
  n = iend - isp1;

  p = (core *) xmalloc((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  p->accessing_symbol = symbol;
  p->number = nstates;
  p->nitems = n;

  isp2 = p->items;
  while (isp1 < iend)
    *isp2++ = *isp1++;

  last_state->next = p;
  last_state = p;

  nstates++;

  return (p);
}


void
initialize_states()
{
  register core *p;
/*  register unsigned *rp1; JF unused */
/*  register unsigned *rp2; JF unused */
/*  register unsigned *rend; JF unused */

  p = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  first_state = last_state = this_state = p;
  nstates = 1;
}


void
save_shifts()
{
  register shifts *p;
  register short *sp1;
  register short *sp2;
  register short *send;

  p = (shifts *) xmalloc((unsigned) (sizeof(shifts) +
				       (nshifts - 1) * sizeof(short)));

  p->number = this_state->number;
  p->nshifts = nshifts;

  sp1 = shiftset;
  sp2 = p->shifts;
  send = shiftset + nshifts;

  while (sp1 < send)
    *sp2++ = *sp1++;

  if (last_shift)
    {
      last_shift->next = p;
      last_shift = p;
    }
  else
    {
      first_shift = p;
      last_shift = p;
    }
}



/* find which rules can be used for reduction transitions from the current state
   and make a reductions structure for the state to record their rule numbers.  */
void
save_reductions()
{
  register short *isp;
  register short *rp1;
  register short *rp2;
  register int item;
  register int count;
  register reductions *p;

  short *rend;

  /* find and count the active items that represent ends of rules */

  count = 0;
  for (isp = itemset; isp < itemsetend; isp++)
    {
      item = ritem[*isp];
      if (item < 0)
	{
	  redset[count++] = -item;
	}
    }

  /* make a reductions structure and copy the data into it.  */

  if (count)
    {
      p = (reductions *) xmalloc((unsigned) (sizeof(reductions) +
					       (count - 1) * sizeof(short)));

      p->number = this_state->number;
      p->nreds = count;

      rp1 = redset;
      rp2 = p->rules;
      rend = rp1 + count;

      while (rp1 < rend)
	*rp2++ = *rp1++;

      if (last_reduction)
	{
	  last_reduction->next = p;
	  last_reduction = p;
	}
      else
	{
	  first_reduction = p;
	  last_reduction = p;
	}
    }
}



/* Make sure that the initial state has a shift that accepts the
grammar's start symbol and goes to the next-to-final state,
which has a shift going to the final state, which has a shift
to the termination state.
Create such states and shifts if they don't happen to exist already.  */
void
augment_automaton()
{
  register int i;
  register int k;
/*  register int found; JF unused */
  register core *statep;
  register shifts *sp;
  register shifts *sp2;
  register shifts *sp1;

  sp = first_shift;

  if (sp)
    {
      if (sp->number == 0)
	{
	  k = sp->nshifts;
	  statep = first_state->next;

	  /* The states reached by shifts from first_state are numbered 1...K.
	     Look for one reached by start_symbol.  */
	  while (statep->accessing_symbol < start_symbol
		  && statep->number < k)
	    statep = statep->next;

	  if (statep->accessing_symbol == start_symbol)
	    {
	      /* We already have a next-to-final state.
		 Make sure it has a shift to what will be the final state.  */
	      k = statep->number;

	      while (sp && sp->number < k)
		{
		  sp1 = sp;
		  sp = sp->next;
		}

	      if (sp && sp->number == k)
		{
		  sp2 = (shifts *) xmalloc((unsigned) (sizeof(shifts)
							 + sp->nshifts * sizeof(short)));
		  sp2->number = k;
		  sp2->nshifts = sp->nshifts + 1;
		  sp2->shifts[0] = nstates;
		  for (i = sp->nshifts; i > 0; i--)
		    sp2->shifts[i] = sp->shifts[i - 1];

		  /* Patch sp2 into the chain of shifts in place of sp,
		     following sp1.  */
		  sp2->next = sp->next;
		  sp1->next = sp2;
		  if (sp == last_shift)
		    last_shift = sp2;
		  FREE(sp);
		}
	      else
		{
		  sp2 = NEW(shifts);
		  sp2->number = k;
		  sp2->nshifts = 1;
		  sp2->shifts[0] = nstates;

		  /* Patch sp2 into the chain of shifts between sp1 and sp.  */
		  sp2->next = sp;
		  sp1->next = sp2;
		  if (sp == 0)
		    last_shift = sp2;
		}
	    }
	  else
	    {
	      /* There is no next-to-final state as yet.  */
	      /* Add one more shift in first_shift,
		 going to the next-to-final state (yet to be made).  */
	      sp = first_shift;

	      sp2 = (shifts *) xmalloc(sizeof(shifts)
					 + sp->nshifts * sizeof(short));
	      sp2->nshifts = sp->nshifts + 1;

	      /* Stick this shift into the vector at the proper place.  */
	      statep = first_state->next;
	      for (k = 0, i = 0; i < sp->nshifts; k++, i++)
		{
		  if (statep->accessing_symbol > start_symbol && i == k)
		    sp2->shifts[k++] = nstates;
		  sp2->shifts[k] = sp->shifts[i];
		  statep = statep->next;
		}
	      if (i == k)
		sp2->shifts[k++] = nstates;

	      /* Patch sp2 into the chain of shifts
		 in place of sp, at the beginning.  */
	      sp2->next = sp->next;
	      first_shift = sp2;
	      if (last_shift == sp)
		last_shift = sp2;

	      FREE(sp);

	      /* Create the next-to-final state, with shift to
		 what will be the final state.  */
	      insert_start_shift();
	    }
	}
      else
	{
	  /* The initial state didn't even have any shifts.
	     Give it one shift, to the next-to-final state.  */
	  sp = NEW(shifts);
	  sp->nshifts = 1;
	  sp->shifts[0] = nstates;

	  /* Patch sp into the chain of shifts at the beginning.  */
	  sp->next = first_shift;
	  first_shift = sp;

	  /* Create the next-to-final state, with shift to
	     what will be the final state.  */
	  insert_start_shift();
	}
    }
  else
    {
      /* There are no shifts for any state.
	 Make one shift, from the initial state to the next-to-final state.  */

      sp = NEW(shifts);
      sp->nshifts = 1;
      sp->shifts[0] = nstates;

      /* Initialize the chain of shifts with sp.  */
      first_shift = sp;
      last_shift = sp;

      /* Create the next-to-final state, with shift to
	 what will be the final state.  */
      insert_start_shift();
    }

  /* Make the final state--the one that follows a shift from the
     next-to-final state.
     The symbol for that shift is 0 (end-of-file).  */
  statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  statep->number = nstates;
  last_state->next = statep;
  last_state = statep;

  /* Make the shift from the final state to the termination state.  */
  sp = NEW(shifts);
  sp->number = nstates++;
  sp->nshifts = 1;
  sp->shifts[0] = nstates;
  last_shift->next = sp;
  last_shift = sp;

  /* Note that the variable `final_state' refers to what we sometimes call
     the termination state.  */
  final_state = nstates;

  /* Make the termination state.  */
  statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  statep->number = nstates++;
  last_state->next = statep;
  last_state = statep;
}


/* subroutine of augment_automaton.
   Create the next-to-final state, to which a shift has already been made in
   the initial state.  */
void
insert_start_shift()
{
  register core *statep;
  register shifts *sp;

  statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  statep->number = nstates;
  statep->accessing_symbol = start_symbol;

  last_state->next = statep;
  last_state = statep;

  /* Make a shift from this state to (what will be) the final state.  */
  sp = NEW(shifts);
  sp->number = nstates++;
  sp->nshifts = 1;
  sp->shifts[0] = nstates;

  last_shift->next = sp;
  last_shift = sp;
}