output.c

Bison语法分析器

	  n = lookaheads[state + 1];

	  for (i = n - 1; i >= m; i--)
	    {
	      rule = - LAruleno[i];
	      wordp = LA + i * tokensetsize;
	      mask = 1;

	      /* and find each token which the rule finds acceptable to come next */
	      for (j = 0; j < ntokens; j++)
		{
		  /* and record this rule as the rule to use if that token follows.  */
		  if (mask & *wordp)
		    actrow[j] = rule;

		  mask <<= 1;
		  if (mask == 0)
		    {
		      mask = 1;
		      wordp++;
		    }
		}
	    }
	}
    }

  shiftp = shift_table[state];

  /* now see which tokens are allowed for shifts in this state.
     For them, record the shift as the thing to do.  So shift is preferred to reduce.  */

  if (shiftp)
    {
      k = shiftp->nshifts;

      for (i = 0; i < k; i++)
	{
	  shift_state = shiftp->shifts[i];
	  if (! shift_state) continue;

	  symbol = accessing_symbol[shift_state];

	  if (ISVAR(symbol))
	    break;

	  actrow[symbol] = shift_state;

	  /* do not use any default reduction if there is a shift for error */

	  if (symbol == error_token_number) nodefault = 1;
	}
    }

  errp = err_table[state];

  /* See which tokens are an explicit error in this state
     (due to %nonassoc).  For them, record MINSHORT as the action.  */

  if (errp)
    {
      k = errp->nerrs;

      for (i = 0; i < k; i++)
	{
	  symbol = errp->errs[i];
	  actrow[symbol] = MINSHORT;
	}
    }

  /* now find the most common reduction and make it the default action for this state.  */

  if (nreds >= 1 && ! nodefault)
    {
      if (consistent[state])
	default_rule = redp->rules[0];
      else
	{
	  max = 0;
	  for (i = m; i < n; i++)
	    {
	      count = 0;
	      rule = - LAruleno[i];
    
	      for (j = 0; j < ntokens; j++)
		{
		  if (actrow[j] == rule)
		    count++;
		}
    
	      if (count > max)
		{
		  max = count;
		  default_rule = rule;
		}
	    }
    
	  /* actions which match the default are replaced with zero,
	     which means "use the default" */
    
	  if (max > 0)
	    {
	      for (j = 0; j < ntokens; j++)
		{
		  if (actrow[j] == default_rule)
		    actrow[j] = 0;
		}
    
	      default_rule = - default_rule;
	    }
	}
    }

  /* If have no default rule, the default is an error.
     So replace any action which says "error" with "use default".  */

  if (default_rule == 0)
    for (j = 0; j < ntokens; j++)
      {
	if (actrow[j] == MINSHORT)
	  actrow[j] = 0;
      }

  return (default_rule);
}


void
save_row (int state)
{
  register int i;
  register int count;
  register short *sp;
  register short *sp1;
  register short *sp2;

  count = 0;
  for (i = 0; i < ntokens; i++)
    {
      if (actrow[i] != 0)
	count++;
    }

  if (count == 0)
    return;

  froms[state] = sp1 = sp = NEW2(count, short);
  tos[state] = sp2 = NEW2(count, short);

  for (i = 0; i < ntokens; i++)
    {
      if (actrow[i] != 0)
	{
	  *sp1++ = i;
	  *sp2++ = actrow[i];
	}
    }

  tally[state] = count;
  width[state] = sp1[-1] - sp[0] + 1;
}



/* figure out what to do after reducing with each rule,
   depending on the saved state from before the beginning
   of parsing the data that matched this rule.

   The yydefgoto table is output now.  The detailed info
   is saved for putting into yytable later.  */

void
goto_actions (void)
{
  register int i;
  register int j;
  register int k;

  state_count = NEW2(nstates, short);

  k = default_goto(ntokens);
  fprintf(ftable, "\nstatic const short yydefgoto[] = {%6d", k);
  save_column(ntokens, k);

  j = 10;
  for (i = ntokens + 1; i < nsyms; i++)
    {
      putc(',', ftable);

      if (j >= 10)
	{
	  putc('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      k = default_goto(i);
      fprintf(ftable, "%6d", k);
      save_column(i, k);
    }

  fprintf(ftable, "\n};\n");
  FREE(state_count);
}



int
default_goto (int symbol)
{
  register int i;
  register int m;
  register int n;
  register int default_state;
  register int max;

  m = goto_map[symbol];
  n = goto_map[symbol + 1];

  if (m == n)
    return (-1);

  for (i = 0; i < nstates; i++)
    state_count[i] = 0;

  for (i = m; i < n; i++)
    state_count[to_state[i]]++;

  max = 0;
  default_state = -1;

  for (i = 0; i < nstates; i++)
    {
      if (state_count[i] > max)
	{
	  max = state_count[i];
	  default_state = i;
	}
    }

  return (default_state);
}


void
save_column (int symbol, int default_state)
{
  register int i;
  register int m;
  register int n;
  register short *sp;
  register short *sp1;
  register short *sp2;
  register int count;
  register int symno;

  m = goto_map[symbol];
  n = goto_map[symbol + 1];

  count = 0;
  for (i = m; i < n; i++)
    {
      if (to_state[i] != default_state)
	count++;
    }

  if (count == 0)
    return;

  symno = symbol - ntokens + nstates;

  froms[symno] = sp1 = sp = NEW2(count, short);
  tos[symno] = sp2 = NEW2(count, short);

  for (i = m; i < n; i++)
    {
      if (to_state[i] != default_state)
	{
	  *sp1++ = from_state[i];
	  *sp2++ = to_state[i];
	}
    }

  tally[symno] = count;
  width[symno] = sp1[-1] - sp[0] + 1;
}



/* the next few functions decide how to pack 
   the actions and gotos information into yytable. */

void
sort_actions (void)
{
  register int i;
  register int j;
  register int k;
  register int t;
  register int w;

  order = NEW2(nvectors, short);
  nentries = 0;

  for (i = 0; i < nvectors; i++)
    {
      if (tally[i] > 0)
	{
	  t = tally[i];
	  w = width[i];
	  j = nentries - 1;

	  while (j >= 0 && (width[order[j]] < w))
	    j--;

	  while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
	    j--;

	  for (k = nentries - 1; k > j; k--)
	    order[k + 1] = order[k];

	  order[j + 1] = i;
	  nentries++;
	}
    }
}


void
pack_table (void)
{
  register int i;
  register int place;
  register int state;

  base = NEW2(nvectors, short);
  pos = NEW2(nentries, short);
  table = NEW2(MAXTABLE, short);
  check = NEW2(MAXTABLE, short);

  lowzero = 0;
  high = 0;

  for (i = 0; i < nvectors; i++)
    base[i] = MINSHORT;

  for (i = 0; i < MAXTABLE; i++)
    check[i] = -1;

  for (i = 0; i < nentries; i++)
    {
      state = matching_state(i);

      if (state < 0)
	place = pack_vector(i);
      else
	place = base[state];

      pos[i] = place;
      base[order[i]] = place;
    }

  for (i = 0; i < nvectors; i++)
    {
      if (froms[i])
	FREE(froms[i]);
      if (tos[i])
	FREE(tos[i]);
    }

  FREE(froms);
  FREE(tos);
  FREE(pos);
}



int
matching_state (int vector)
{
  register int i;
  register int j;
  register int k;
  register int t;
  register int w;
  register int match;
  register int prev;

  i = order[vector];
  if (i >= nstates)
    return (-1);

  t = tally[i];
  w = width[i];

  for (prev = vector - 1; prev >= 0; prev--)
    {
      j = order[prev];
      if (width[j] != w || tally[j] != t)
	return (-1);

      match = 1;
      for (k = 0; match && k < t; k++)
	{
	  if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
	    match = 0;
	}

      if (match)
	return (j);
    }

  return (-1);
}



int
pack_vector (int vector)
{
  register int i;
  register int j;
  register int k;
  register int t;
  register int loc = 0;
  register int ok;
  register short *from;
  register short *to;

  i = order[vector];
  t = tally[i];

  if (t == 0)
    berror("pack_vector");

  from = froms[i];
  to = tos[i];

  for (j = lowzero - from[0]; j < MAXTABLE; j++)
    {
      ok = 1;

      for (k = 0; ok && k < t; k++)
	{
	  loc = j + from[k];
	  if (loc > MAXTABLE)
	    fatals(_("maximum table size (%s) exceeded"), int_to_string(MAXTABLE));

	  if (table[loc] != 0)
	    ok = 0;
	}

      for (k = 0; ok && k < vector; k++)
	{
	  if (pos[k] == j)
	    ok = 0;
	}

      if (ok)
	{
	  for (k = 0; k < t; k++)
	    {
	      loc = j + from[k];
	      table[loc] = to[k];
	      check[loc] = from[k];
	    }

	  while (table[lowzero] != 0)
	    lowzero++;

	  if (loc > high)
	    high = loc;

	  return (j);
	}
    }

  berror("pack_vector");
  return 0;	/* JF keep lint happy */
}



/* the following functions output yytable, yycheck
   and the vectors whose elements index the portion starts */

void
output_base (void)
{
  register int i;
  register int j;

  fprintf(ftable, "\nstatic const short yypact[] = {%6d", base[0]);

  j = 10;
  for (i = 1; i < nstates; i++)
    {
      putc(',', ftable);

      if (j >= 10)
	{
	  putc('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      fprintf(ftable, "%6d", base[i]);
    }

  fprintf(ftable, "\n};\n\nstatic const short yypgoto[] = {%6d", base[nstates]);

  j = 10;
  for (i = nstates + 1; i < nvectors; i++)
    {
      putc(',', ftable);

      if (j >= 10)
	{
	  putc('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      fprintf(ftable, "%6d", base[i]);
    }

  fprintf(ftable, "\n};\n");
  FREE(base);
}


void
output_table (void)
{
  register int i;
  register int j;

  fprintf(ftable, "\n\n#define\tYYLAST\t\t%d\n\n", high);
  fprintf(ftable, "\nstatic const short yytable[] = {%6d", table[0]);

  j = 10;
  for (i = 1; i <= high; i++)
    {
      putc(',', ftable);

      if (j >= 10)
	{
	  putc('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      fprintf(ftable, "%6d", table[i]);
    }

  fprintf(ftable, "\n};\n");
  FREE(table);
}


void
output_check (void)
{
  register int i;
  register int j;

  fprintf(ftable, "\nstatic const short yycheck[] = {%6d", check[0]);

  j = 10;
  for (i = 1; i <= high; i++)
    {
      putc(',', ftable);

      if (j >= 10)
	{
	  putc('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      fprintf(ftable, "%6d", check[i]);
    }

  fprintf(ftable, "\n};\n");
  FREE(check);
}



/* copy the parser code into the ftable file at the end.  */

void
output_parser (void)
{
  register int c;
#ifdef DONTDEF
  FILE *fpars;
#else
#define fpars fparser
#endif

  if (pure_parser)
    fprintf(ftable, "#define YYPURE 1\n\n");

#ifdef DONTDEF	/* JF no longer needed 'cuz open_extra_files changes the
		   currently open parser from bison.simple to bison.hairy */
  if (semantic_parser)
    fpars = fparser;
  else fpars = fparser1;
#endif

  /* Loop over lines in the standard parser file.  */

  while (1)
    {
      int write_line = 1;

      c = getc(fpars);

      /* See if the line starts with `#line.
	 If so, set write_line to 0.  */
      if (nolinesflag)
	if (c == '#') 
	  {
	    c = getc(fpars);
	    if (c == 'l')
	      {
		c = getc(fpars);
		if (c == 'i')
		  {
		    c = getc(fpars);
		    if (c == 'n')
		      {
			c = getc(fpars);
			if (c == 'e')
			  write_line = 0;
			else
			  fprintf(ftable, "#lin");
		      }
		    else
		      fprintf(ftable, "#li");
		  }
		else
		  fprintf(ftable, "#l");
	      }
	    else
	      fprintf(ftable, "#");
	  }

      /* now write out the line... */
      for (; c != '\n' && c != EOF; c = getc(fpars))
	if (write_line) {
	  if (c == '$')
	    {
	      /* `$' in the parser file indicates where to put the actions.
		 Copy them in at this point.  */
	      rewind(faction);
	      for(c=getc(faction);c!=EOF;c=getc(faction))
		putc(c,ftable);
	    }
	  else
	    putc(c, ftable);
	}
      if (c == EOF)
	break;
      putc(c, ftable);
    }
}

void
output_program (void)
{
  register int c;

  if (!nolinesflag)
    fprintf(ftable, "#line %d \"%s\"\n", lineno, infile);

  c = getc(finput);
  while (c != EOF)
    {
      putc(c, ftable);
      c = getc(finput);
    }
}


void
free_itemsets (void)
{
  register core *cp,*cptmp;

  FREE(state_table);

  for (cp = first_state; cp; cp = cptmp) {
    cptmp=cp->next;
    FREE(cp);
  }
}


void
free_shifts (void)
{
  register shifts *sp,*sptmp;/* JF derefrenced freed ptr */

  FREE(shift_table);

  for (sp = first_shift; sp; sp = sptmp) {
    sptmp=sp->next;
    FREE(sp);
  }
}


void
free_reductions (void)
{
  register reductions *rp,*rptmp;/* JF fixed freed ptr */

  FREE(reduction_table);

  for (rp = first_reduction; rp; rp = rptmp) {
    rptmp=rp->next;
    FREE(rp);
  }
}