www.pudn.com > bison.zip > nullable.c

/* Part of the bison parser generator, 
   Copyright (C) 1984, 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 modify 
it under the terms of the GNU General Public License as published by 
the 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 of 
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
GNU General Public License for more details. 
 
You should have received a copy of the GNU General Public License 
along with Bison; see the file COPYING.  If not, write to 
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */ 
 
 
/* set up nullable, a vector saying which nonterminals can expand into the null string. 
   nullable[i - ntokens] is nonzero if symbol i can do so.  */ 
 
#include  
#include "system.h" 
#include "types.h" 
#include "gram.h" 
#include "new.h" 
 
 
char *nullable; 
 
 
void 
set_nullable() 
{ 
  register short *r; 
  register short *s1; 
  register short *s2; 
  register int ruleno; 
  register int symbol; 
  register shorts *p; 
 
  short *squeue; 
  short *rcount; 
  shorts **rsets; 
  shorts *relts; 
  char any_tokens; 
  short *r1; 
 
#ifdef	TRACE 
  fprintf(stderr, "Entering set_nullable"); 
#endif 
 
  nullable = NEW2(nvars, char) - ntokens; 
 
  squeue = NEW2(nvars, short); 
  s1 = s2 = squeue; 
 
  rcount = NEW2(nrules + 1, short); 
  rsets = NEW2(nvars, shorts *) - ntokens; 
  /* This is said to be more elements than we actually use. 
     Supposedly nitems - nrules is enough. 
     But why take the risk?  */ 
  relts = NEW2(nitems + nvars + 1, shorts); 
  p = relts; 
 
  r = ritem; 
  while (*r) 
    { 
      if (*r < 0) 
	{ 
	  symbol = rlhs[-(*r++)]; 
	  if (symbol >= 0 && !nullable[symbol]) 
	    { 
	      nullable[symbol] = 1; 
	      *s2++ = symbol; 
	    } 
	} 
      else 
	{ 
	  r1 = r; 
	  any_tokens = 0; 
	  for (symbol = *r++; symbol > 0; symbol = *r++) 
	    { 
	      if (ISTOKEN(symbol)) 
		any_tokens = 1; 
	    } 
 
	  if (!any_tokens) 
	    { 
	      ruleno = -symbol; 
	      r = r1; 
	      for (symbol = *r++; symbol > 0; symbol = *r++) 
		{ 
		  rcount[ruleno]++; 
		  p->next = rsets[symbol]; 
		  p->value = ruleno; 
		  rsets[symbol] = p; 
		  p++; 
		} 
	    } 
	} 
    } 
 
  while (s1 < s2) 
    { 
      p = rsets[*s1++]; 
      while (p) 
	{ 
	  ruleno = p->value; 
	  p = p->next; 
	  if (--rcount[ruleno] == 0) 
	    { 
	      symbol = rlhs[ruleno]; 
	      if (symbol >= 0 && !nullable[symbol]) 
		{ 
		  nullable[symbol] = 1; 
		  *s2++ = symbol; 
		} 
	    } 
	} 
    } 
 
  FREE(squeue); 
  FREE(rcount); 
  FREE(rsets + ntokens); 
  FREE(relts); 
} 
 
 
void 
free_nullable() 
{ 
  FREE(nullable + ntokens); 
}