/* Generate the nondeterministic finite state machine for bison,   Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.This file is part of Bison, the GNU Compiler Compiler.Bison is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2, or (at your option)any later version.Bison is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with Bison; see the file COPYING.  If not, write tothe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  *//* See comments in state.h for the data structures that represent it.   The entry point is generate_states.  */#include <stdio.h>#include "system.h"#include "machine.h"#include "new.h"#include "gram.h"#include "state.h"extern char *nullable;extern short *itemset;extern short *itemsetend;int nstates;int final_state;core *first_state;shifts *first_shift;reductions *first_reduction;int get_state();core *new_state();void new_itemsets();void append_states();void initialize_states();void save_shifts();void save_reductions();void augment_automaton();void insert_start_shift();extern void initialize_closure();extern void closure();extern void finalize_closure();extern void toomany();static core *this_state;static core *last_state;static shifts *last_shift;static reductions *last_reduction;static int nshifts;static short *shift_symbol;static short *redset;static short *shiftset;static short **kernel_base;static short **kernel_end;static short *kernel_items;/* hash table for states, to recognize equivalent ones.  */#define	STATE_TABLE_SIZE	1009static core **state_table;voidallocate_itemsets(){  register short *itemp;  register int symbol;  register int i;  register int count;  register short *symbol_count;  count = 0;  symbol_count = NEW2(nsyms, short);  itemp = ritem;  symbol = *itemp++;  while (symbol)    {      if (symbol > 0)	{	  count++;	  symbol_count[symbol]++;	}      symbol = *itemp++;    }  /* see comments before new_itemsets.  All the vectors of items     live inside kernel_items.  The number of active items after     some symbol cannot be more than the number of times that symbol     appears as an item, which is symbol_count[symbol].     We allocate that much space for each symbol.  */  kernel_base = NEW2(nsyms, short *);  kernel_items = NEW2(count, short);  count = 0;  for (i = 0; i < nsyms; i++)    {      kernel_base[i] = kernel_items + count;      count += symbol_count[i];    }  shift_symbol = symbol_count;  kernel_end = NEW2(nsyms, short *);}voidallocate_storage(){  allocate_itemsets();  shiftset = NEW2(nsyms, short);  redset = NEW2(nrules + 1, short);  state_table = NEW2(STATE_TABLE_SIZE, core *);}voidfree_storage(){  FREE(shift_symbol);  FREE(redset);  FREE(shiftset);  FREE(kernel_base);  FREE(kernel_end);  FREE(kernel_items);  FREE(state_table);}/* compute the nondeterministic finite state machine (see state.h for details)from the grammar.  */voidgenerate_states(){  allocate_storage();  initialize_closure(nitems);  initialize_states();  while (this_state)    {      /* Set up ruleset and itemset for the transitions out of this state.         ruleset gets a 1 bit for each rule that could reduce now.	 itemset gets a vector of all the items that could be accepted next.  */      closure(this_state->items, this_state->nitems);      /* record the reductions allowed out of this state */      save_reductions();      /* find the itemsets of the states that shifts can reach */      new_itemsets();      /* find or create the core structures for those states */      append_states();      /* create the shifts structures for the shifts to those states,         now that the state numbers transitioning to are known */      if (nshifts > 0)        save_shifts();      /* states are queued when they are created; process them all */      this_state = this_state->next;    }  /* discard various storage */  finalize_closure();  free_storage();  /* set up initial and final states as parser wants them */  augment_automaton();}/* Find which symbols can be shifted in the current state,   and for each one record which items would be active after that shift.   Uses the contents of itemset.   shift_symbol is set to a vector of the symbols that can be shifted.   For each symbol in the grammar, kernel_base[symbol] points to   a vector of item numbers activated if that symbol is shifted,   and kernel_end[symbol] points after the end of that vector.  */voidnew_itemsets(){  register int i;  register int shiftcount;  register short *isp;  register short *ksp;  register int symbol;#ifdef	TRACE  fprintf(stderr, "Entering new_itemsets\n");#endif  for (i = 0; i < nsyms; i++)    kernel_end[i] = NULL;  shiftcount = 0;  isp = itemset;  while (isp < itemsetend)    {      i = *isp++;      symbol = ritem[i];      if (symbol > 0)	{          ksp = kernel_end[symbol];          if (!ksp)	    {	      shift_symbol[shiftcount++] = symbol;	      ksp = kernel_base[symbol];	    }          *ksp++ = i + 1;          kernel_end[symbol] = ksp;	}    }  nshifts = shiftcount;}/* Use the information computed by new_itemsets to find the state numbers   reached by each shift transition from the current state.   shiftset is set up as a vector of state numbers of those states.  */voidappend_states(){  register int i;  register int j;  register int symbol;#ifdef	TRACE  fprintf(stderr, "Entering append_states\n");#endif  /* first sort shift_symbol into increasing order */  for (i = 1; i < nshifts; i++)    {      symbol = shift_symbol[i];      j = i;      while (j > 0 && shift_symbol[j - 1] > symbol)	{	  shift_symbol[j] = shift_symbol[j - 1];	  j--;	}      shift_symbol[j] = symbol;    }  for (i = 0; i < nshifts; i++)    {      symbol = shift_symbol[i];      shiftset[i] = get_state(symbol);    }}/* find the state number for the state we would get to(from the current state) by shifting symbol.Create a new state if no equivalent one exists already.Used by append_states  */intget_state(symbol)int symbol;{  register int key;  register short *isp1;  register short *isp2;  register short *iend;  register core *sp;  register int found;  int n;#ifdef	TRACE  fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);#endif  isp1 = kernel_base[symbol];  iend = kernel_end[symbol];  n = iend - isp1;  /* add up the target state's active item numbers to get a hash key */  key = 0;  while (isp1 < iend)    key += *isp1++;  key = key % STATE_TABLE_SIZE;  sp = state_table[key];  if (sp)    {      found = 0;      while (!found)	{	  if (sp->nitems == n)	    {	      found = 1;	      isp1 = kernel_base[symbol];	      isp2 = sp->items;	      while (found && isp1 < iend)		{		  if (*isp1++ != *isp2++)		    found = 0;		}	    }	  if (!found)	    {	      if (sp->link)		{		  sp = sp->link;		}	      else   /* bucket exhausted and no match */		{		  sp = sp->link = new_state(symbol);		  found = 1;		}	    }	}    }  else      /* bucket is empty */    {      state_table[key] = sp = new_state(symbol);    }  return (sp->number);}