tables.c

bison 2.0 主要可以用来做语法分析用的

  conflict_list_free = 2 * nconflict;
  conflict_list_cnt = 1;

  /* Find the rules which are reduced.  */
  if (!nondeterministic_parser)
    for (r = 0; r < nrules; ++r)
      rules[r].useful = false;

  for (i = 0; i < nstates; ++i)
    {
      rule *default_rule = action_row (states[i]);
      yydefact[i] = default_rule ? default_rule->number + 1 : 0;
      save_row (i);

      /* Now that the parser was computed, we can find which rules are
	 really reduced, and which are not because of SR or RR
	 conflicts.  */
      if (!nondeterministic_parser)
	{
	  for (j = 0; j < ntokens; ++j)
	    if (actrow[j] < 0 && actrow[j] != ACTION_NUMBER_MINIMUM)
	      rules[item_number_as_rule_number (actrow[j])].useful = true;
	  if (yydefact[i])
	    rules[yydefact[i] - 1].useful = true;
	}
    }

  free (actrow);
  free (conflrow);
}


/*------------------------------------------------------------------.
| Compute FROMS[VECTOR], TOS[VECTOR], TALLY[VECTOR], WIDTH[VECTOR], |
| i.e., the information related to non defaulted GOTO on the nterm  |
| SYM.                                                              |
|                                                                   |
| DEFAULT_STATE is the principal destination on SYM, i.e., the      |
| default GOTO destination on SYM.                                  |
`------------------------------------------------------------------*/

static void
save_column (symbol_number sym, state_number default_state)
{
  goto_number i;
  base_number *sp;
  base_number *sp1;
  base_number *sp2;
  int count;
  vector_number symno = symbol_number_to_vector_number (sym);

  goto_number begin = goto_map[sym - ntokens];
  goto_number end = goto_map[sym - ntokens + 1];

  /* Number of non default GOTO.  */
  count = 0;
  for (i = begin; i < end; i++)
    if (to_state[i] != default_state)
      count++;

  if (count == 0)
    return;

  /* Allocate room for non defaulted gotos.  */
  froms[symno] = sp = sp1 = xnmalloc (count, sizeof *sp1);
  tos[symno] = sp2 = xnmalloc (count, sizeof *sp2);

  /* Store the state numbers of the non defaulted gotos.  */
  for (i = begin; i < end; 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;
}


/*-------------------------------------------------------------.
| Return `the' most common destination GOTO on SYM (a nterm).  |
`-------------------------------------------------------------*/

static state_number
default_goto (symbol_number sym, size_t state_count[])
{
  state_number s;
  goto_number i;
  goto_number m = goto_map[sym - ntokens];
  goto_number n = goto_map[sym - ntokens + 1];
  state_number default_state = -1;
  size_t max = 0;

  if (m == n)
    return -1;

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

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

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

  return default_state;
}


/*-------------------------------------------------------------------.
| 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.                                        |
`-------------------------------------------------------------------*/

static void
goto_actions (void)
{
  symbol_number i;
  size_t *state_count = xnmalloc (nstates, sizeof *state_count);
  yydefgoto = xnmalloc (nvars, sizeof *yydefgoto);

  /* For a given nterm I, STATE_COUNT[S] is the number of times there
     is a GOTO to S on I.  */
  for (i = ntokens; i < nsyms; ++i)
    {
      state_number default_state = default_goto (i, state_count);
      save_column (i, default_state);
      yydefgoto[i - ntokens] = default_state;
    }
  free (state_count);
}


/*------------------------------------------------------------------.
| Compute ORDER, a reordering of vectors, in order to decide how to |
| pack the actions and gotos information into yytable.              |
`------------------------------------------------------------------*/

static void
sort_actions (void)
{
  int i;

  nentries = 0;

  for (i = 0; i < nvectors; i++)
    if (tally[i] > 0)
      {
	int k;
	int t = tally[i];
	int w = width[i];
	int 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++;
      }
}


/* If VECTOR is a state which actions (reflected by FROMS, TOS, TALLY
   and WIDTH of VECTOR) are common to a previous state, return this
   state number.

   In any other case, return -1.  */

static state_number
matching_state (vector_number vector)
{
  vector_number i = order[vector];
  int t;
  int w;
  int prev;

  /* If VECTOR is a nterm, return -1.  */
  if (nstates <= i)
    return -1;

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

  /* If VECTOR has GLR conflicts, return -1 */
  if (conflict_tos[i] != NULL)
    {
      int j;
      for (j = 0; j < t; j += 1)
	if (conflict_tos[i][j] != 0)
	  return -1;
    }

  for (prev = vector - 1; prev >= 0; prev--)
    {
      vector_number j = order[prev];
      int k;
      int match = 1;

      /* Given how ORDER was computed, if the WIDTH or TALLY is
	 different, there cannot be a matching state.  */
      if (width[j] != w || tally[j] != t)
	return -1;

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

      if (match)
	return j;
    }

  return -1;
}


static base_number
pack_vector (vector_number vector)
{
  vector_number i = order[vector];
  int j;
  int t = tally[i];
  int loc = 0;
  base_number *from = froms[i];
  base_number *to = tos[i];
  unsigned int *conflict_to = conflict_tos[i];

  if (!t)
    abort ();

  for (j = lowzero - from[0]; ; j++)
    {
      int k;
      bool ok = true;

      if (table_size <= j)
	abort ();

      for (k = 0; ok && k < t; k++)
	{
	  loc = j + state_number_as_int (from[k]);
	  if (table_size <= loc)
	    table_grow (loc);

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

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

      if (ok)
	{
	  for (k = 0; k < t; k++)
	    {
	      loc = j + from[k];
	      table[loc] = to[k];
	      if (nondeterministic_parser && conflict_to != NULL)
		conflict_table[loc] = conflict_to[k];
	      check[loc] = from[k];
	    }

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

	  if (loc > high)
	    high = loc;

	  if (! (BASE_MINIMUM <= j && j <= BASE_MAXIMUM))
	    abort ();
	  return j;
	}
    }
}


/*-------------------------------------------------------------.
| Remap the negative infinite in TAB from NINF to the greatest |
| possible smallest value.  Return it.                         |
|                                                              |
| In most case this allows us to use shorts instead of ints in |
| parsers.                                                     |
`-------------------------------------------------------------*/

static base_number
table_ninf_remap (base_number tab[], int size, base_number ninf)
{
  base_number res = 0;
  int i;

  for (i = 0; i < size; i++)
    if (tab[i] < res && tab[i] != ninf)
      res = tab[i];

  --res;

  for (i = 0; i < size; i++)
    if (tab[i] == ninf)
      tab[i] = res;

  return res;
}

static void
pack_table (void)
{
  int i;

  base = xnmalloc (nvectors, sizeof *base);
  pos = xnmalloc (nentries, sizeof *pos);
  table = xcalloc (table_size, sizeof *table);
  conflict_table = xcalloc (table_size, sizeof *conflict_table);
  check = xnmalloc (table_size, sizeof *check);

  lowzero = 0;
  high = 0;

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

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

  for (i = 0; i < nentries; i++)
    {
      state_number s = matching_state (i);
      base_number place;

      if (s < 0)
	/* A new set of state actions, or a nonterminal.  */
	place = pack_vector (i);
      else
	/* Action of I were already coded for S.  */
	place = base[s];

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

  /* Use the greatest possible negative infinites.  */
  base_ninf = table_ninf_remap (base, nvectors, BASE_MINIMUM);
  table_ninf = table_ninf_remap (table, high + 1, ACTION_NUMBER_MINIMUM);

  free (pos);
}



/*-----------------------------------------------------------------.
| Compute and output yydefact, yydefgoto, yypact, yypgoto, yytable |
| and yycheck.                                                     |
`-----------------------------------------------------------------*/

void
tables_generate (void)
{
  int i;

  /* This is a poor way to make sure the sizes are properly
     correlated.  In particular the signedness is not taken into
     account.  But it's not useless.  */
  verify (sizes_are_properly_correlated,
	  (sizeof nstates <= sizeof nvectors
	   && sizeof nvars <= sizeof nvectors));

  nvectors = state_number_as_int (nstates) + nvars;

  froms = xcalloc (nvectors, sizeof *froms);
  tos = xcalloc (nvectors, sizeof *tos);
  conflict_tos = xcalloc (nvectors, sizeof *conflict_tos);
  tally = xcalloc (nvectors, sizeof *tally);
  width = xnmalloc (nvectors, sizeof *width);

  token_actions ();

  goto_actions ();
  free (goto_map);
  free (from_state);
  free (to_state);

  order = xcalloc (nvectors, sizeof *order);
  sort_actions ();
  pack_table ();
  free (order);

  free (tally);
  free (width);

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

  free (froms);
  free (tos);
  free (conflict_tos);
}


/*-------------------------.
| Free the parser tables.  |
`-------------------------*/

void
tables_free (void)
{
  free (base);
  free (conflict_table);
  free (conflict_list);
  free (table);
  free (check);
  free (yydefgoto);
  free (yydefact);
}