Adjust to renamings.

[bison.git] / src / symtab.c

diff --git a/src/symtab.c b/src/symtab.c
index 455e74e2310ec00727a8f68034e406d3f7fd17a9..8e384f6622f25f7d310c1d62254e5efec9693625 100644 (file)
--- a/src/symtab.c
+++ b/src/symtab.c
@@ -1,5 +1,5 @@
 /* Symbol table manager for Bison,
 /* Symbol table manager for Bison,

-   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
+   Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.

 
    This file is part of Bison, the GNU Compiler Compiler.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -20,132 +20,551 @@
 
 
 #include "system.h"
 
 
 #include "system.h"

-#include "symtab.h"
-#include "gram.h"

 
 

+#include <hash.h>
+#include <quotearg.h>

 
 

-bucket *firstsymbol;
-static bucket *lastsymbol;
-static bucket **symtab;
+#include "complain.h"
+#include "gram.h"
+#include "symtab.h"

 
 

-static int
-hash (const char *key)
-{
-  const char *cp;
-  int k;
+/*------------------------.
+| Distinguished symbols.  |
+`------------------------*/

 
 

-  cp = key;
-  k = 0;
-  while (*cp)
-    k = ((k << 1) ^ (*cp++)) & 0x3fff;
+symbol *errtoken = NULL;
+symbol *undeftoken = NULL;
+symbol *endtoken = NULL;
+symbol *accept = NULL;
+symbol *startsymbol = NULL;
+location startsymbol_location;

 
 

-  return k % TABSIZE;
-}
+/*---------------------------------.
+| Create a new symbol, named TAG.  |
+`---------------------------------*/

 
 

-/*--------------------------------------------------------------.
-| Create a new symbol, named TAG, which hash value is HASHVAL.  |
-`--------------------------------------------------------------*/
-
-static bucket *
-bucket_new (const char *tag, int hashval)
+static symbol *
+symbol_new (uniqstr tag, location loc)

 {
 {

-  bucket *res = XMALLOC (bucket, 1);
+  symbol *res = XMALLOC (symbol, 1);
+
+  uniqstr_assert (tag);
+  res->tag = tag;
+  res->location = loc;

 
 

-  res->link = symtab[hashval];
-  res->next = NULL;
-  res->tag = xstrdup (tag);

   res->type_name = NULL;
   res->type_name = NULL;

-  res->value = 0;
+  res->destructor = NULL;
+  res->printer = NULL;
+
+  res->number = NUMBER_UNDEFINED;

   res->prec = 0;
   res->prec = 0;

-  res->assoc = right_assoc;
-  res->user_token_number = SUNDEF;
+  res->assoc = undef_assoc;
+  res->user_token_number = USER_NUMBER_UNDEFINED;
+

   res->alias = NULL;
   res->class = unknown_sym;
 
   nsyms++;
   res->alias = NULL;
   res->class = unknown_sym;
 
   nsyms++;

-

   return res;
 }
 
 
   return res;
 }
 
 

+/*-----------------------------------------------------------------.
+| Set the TYPE_NAME associated with SYM.  Does nothing if passed 0 |
+| as TYPE_NAME.                                                    |
+`-----------------------------------------------------------------*/
+

 void
 void

-tabinit (void)
+symbol_type_set (symbol *sym, uniqstr type_name, location loc)

 {
 {

-  symtab = XCALLOC (bucket *, TABSIZE);
+  if (type_name)
+    {
+      if (sym->type_name)
+       complain_at (loc, _("type redeclaration for %s"), sym->tag);
+      uniqstr_assert (type_name);
+      sym->type_name = type_name;
+    }
+}

 
 

-  firstsymbol = NULL;
-  lastsymbol = NULL;
+
+/*------------------------------------------------------------------.
+| Set the DESTRUCTOR associated with SYM.  Do nothing if passed 0.  |
+`------------------------------------------------------------------*/
+
+void
+symbol_destructor_set (symbol *sym, char *destructor, location loc)
+{
+  if (destructor)
+    {
+      if (sym->destructor)
+       complain_at (loc, _("%s redeclaration for %s"),
+                    "%destructor", sym->tag);
+      sym->destructor = destructor;
+      sym->destructor_location = loc;
+    }

 }
 
 
 }
 
 

-/*----------------------------------------------------------------.
-| Find the symbol named KEY, and return it.  If it does not exist |
-| yet, create it.                                                 |
-`----------------------------------------------------------------*/
+/*---------------------------------------------------------------.
+| Set the PRINTER associated with SYM.  Do nothing if passed 0.  |
+`---------------------------------------------------------------*/

 
 

-bucket *
-getsym (const char *key)
+void
+symbol_printer_set (symbol *sym, char *printer, location loc)

 {
 {

-  int hashval;
-  bucket *bp;
-  int found;
+  if (printer)
+    {
+      if (sym->printer)
+       complain_at (loc, _("%s redeclaration for %s"),
+                    "%printer", sym->tag);
+      sym->printer = printer;
+      sym->printer_location = loc;
+    }
+}

 
 

-  hashval = hash (key);
-  bp = symtab[hashval];

 
 

-  found = 0;
-  while (bp != NULL && found == 0)
+/*-----------------------------------------------------------------.
+| Set the PRECEDENCE associated with SYM.  Does nothing if invoked |
+| with UNDEF_ASSOC as ASSOC.                                       |
+`-----------------------------------------------------------------*/
+
+void
+symbol_precedence_set (symbol *sym, int prec, assoc a, location loc)
+{
+  if (a != undef_assoc)

     {
     {

-      if (strcmp (key, bp->tag) == 0)
-       found = 1;
-      else
-       bp = bp->link;
+      if (sym->prec != 0)
+       complain_at (loc, _("redefining precedence of %s"), sym->tag);
+      sym->prec = prec;
+      sym->assoc = a;

     }
 
     }
 

-  if (found == 0)
+  /* Only terminals have a precedence. */
+  symbol_class_set (sym, token_sym, loc);
+}
+
+
+/*------------------------------------.
+| Set the CLASS associated with SYM.  |
+`------------------------------------*/
+
+void
+symbol_class_set (symbol *sym, symbol_class class, location loc)
+{
+  if (sym->class != unknown_sym && sym->class != class)
+    complain_at (loc, _("symbol %s redefined"), sym->tag);
+
+  if (class == nterm_sym && sym->class != nterm_sym)
+    sym->number = nvars++;
+  else if (class == token_sym && sym->number == NUMBER_UNDEFINED)
+    sym->number = ntokens++;
+
+  sym->class = class;
+}
+
+
+/*------------------------------------------------.
+| Set the USER_TOKEN_NUMBER associated with SYM.  |
+`------------------------------------------------*/
+
+void
+symbol_user_token_number_set (symbol *sym, int user_token_number, location loc)
+{
+  if (sym->class != token_sym)
+    abort ();
+
+  if (sym->user_token_number != USER_NUMBER_UNDEFINED
+      && sym->user_token_number != user_token_number)
+    complain_at (loc, _("redefining user token number of %s"), sym->tag);
+
+  sym->user_token_number = user_token_number;
+  /* User defined $end token? */
+  if (user_token_number == 0)
+    {
+      endtoken = sym;
+      endtoken->number = 0;
+      /* It is always mapped to 0, so it was already counted in
+        NTOKENS.  */
+      --ntokens;
+    }
+}
+
+
+/*-----------.
+| Free SYM.  |
+`-----------*/
+
+static void
+symbol_free (symbol *sym)
+{
+  free (sym);
+}
+
+
+/*----------------------------------------------------------.
+| If SYM is not defined, report an error, and consider it a |
+| nonterminal.                                              |
+`----------------------------------------------------------*/
+
+static bool
+symbol_check_defined (symbol *sym)
+{
+  if (sym->class == unknown_sym)

     {
     {

-      bp = bucket_new (key, hashval);
+      complain_at
+       (sym->location,
+        _("symbol %s is used, but is not defined as a token and has no rules"),
+        sym->tag);
+      sym->class = nterm_sym;
+      sym->number = nvars++;
+    }
+
+  return true;
+}
+

 
 

-      if (firstsymbol == NULL)
+/*------------------------------------------------------------------.
+| Declare the new symbol SYM.  Make it an alias of SYMVAL, and type |
+| them with TYPENAME.                                               |
+`------------------------------------------------------------------*/
+
+void
+symbol_make_alias (symbol *sym, symbol *symval, location loc)
+{
+  if (symval->alias)
+    warn_at (loc, _("symbol `%s' used more than once as a literal string"),
+         symval->tag);
+  else if (sym->alias)
+    warn_at (loc, _("symbol `%s' given more than one literal string"),
+         sym->tag);
+  else
+    {
+      symval->class = token_sym;
+      symval->user_token_number = sym->user_token_number;
+      sym->user_token_number = USER_NUMBER_ALIAS;
+      symval->alias = sym;
+      sym->alias = symval;
+      /* sym and symval combined are only one symbol.  */
+      nsyms--;
+      ntokens--;
+      if (ntokens != sym->number && ntokens != symval->number)
+       abort ();
+      sym->number = symval->number =
+       (symval->number < sym->number) ? symval->number : sym->number;
+    }
+}
+
+
+/*---------------------------------------------------------.
+| Check that THIS, and its alias, have same precedence and |
+| associativity.                                           |
+`---------------------------------------------------------*/
+
+static bool
+symbol_check_alias_consistence (symbol *this)
+{
+  /* Check only those who _are_ the aliases. */
+  if (this->alias && this->user_token_number == USER_NUMBER_ALIAS)
+    {
+      if (this->prec != this->alias->prec)

        {
        {

-         firstsymbol = bp;
-         lastsymbol = bp;
+         if (this->prec != 0 && this->alias->prec != 0)
+           complain_at (this->alias->location,
+                        _("conflicting precedences for %s and %s"),
+                        this->tag, this->alias->tag);
+         if (this->prec != 0)
+           this->alias->prec = this->prec;
+         else
+           this->prec = this->alias->prec;

        }
        }

-      else
+
+      if (this->assoc != this->alias->assoc)
+       {
+         if (this->assoc != undef_assoc && this->alias->assoc != undef_assoc)
+           complain_at (this->alias->location,
+                        _("conflicting associativities for %s (%s) and %s (%s)"),
+                        this->tag, assoc_to_string (this->assoc),
+                        this->alias->tag, assoc_to_string (this->alias->assoc));
+         if (this->assoc != undef_assoc)
+           this->alias->assoc = this->assoc;
+         else
+           this->assoc = this->alias->assoc;
+       }
+    }
+  return true;
+}
+
+
+/*-------------------------------------------------------------------.
+| Assign a symbol number, and write the definition of the token name |
+| into FDEFINES.  Put in SYMBOLS.                                    |
+`-------------------------------------------------------------------*/
+
+static bool
+symbol_pack (symbol *this)
+{
+  if (this->class == nterm_sym)
+    {
+      this->number += ntokens;
+    }
+  else if (this->alias)
+    {
+      /* This symbol and its alias are a single token defn.
+        Allocate a tokno, and assign to both check agreement of
+        prec and assoc fields and make both the same */
+      if (this->number == NUMBER_UNDEFINED)

        {
        {

-         lastsymbol->next = bp;
-         lastsymbol = bp;
+         if (this == endtoken || this->alias == endtoken)
+           this->number = this->alias->number = 0;
+         else
+           {
+             if (this->alias->number == NUMBER_UNDEFINED)
+               abort ();
+             this->number = this->alias->number;
+           }

        }
        }

+      /* Do not do processing below for USER_NUMBER_ALIASes.  */
+      if (this->user_token_number == USER_NUMBER_ALIAS)
+       return true;
+    }
+  else /* this->class == token_sym */
+    {
+      if (this->number == NUMBER_UNDEFINED)
+       abort ();
+    }
+
+  symbols[this->number] = this;
+  return true;
+}
+
+
+
+
+/*--------------------------------------------------.
+| Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
+`--------------------------------------------------*/

 
 

-      symtab[hashval] = bp;
+static bool
+symbol_translation (symbol *this)
+{
+  /* Non-terminal? */
+  if (this->class == token_sym
+      && this->user_token_number != USER_NUMBER_ALIAS)
+    {
+      /* A token which translation has already been set? */
+      if (token_translations[this->user_token_number] != undeftoken->number)
+       complain_at (this->location,
+                    _("tokens %s and %s both assigned number %d"),
+                    symbols[token_translations[this->user_token_number]]->tag,
+                    this->tag, this->user_token_number);
+
+      token_translations[this->user_token_number] = this->number;

     }
 
     }
 

-  return bp;
+  return true;
+}
+
+
+/*----------------------.
+| A symbol hash table.  |
+`----------------------*/
+
+/* Initial capacity of symbols hash table.  */
+#define HT_INITIAL_CAPACITY 257
+
+static struct hash_table *symbol_table = NULL;
+
+static bool
+hash_compare_symbol (const symbol *m1, const symbol *m2)
+{
+  /* Since tags are unique, we can compare the pointers themselves.  */
+  return UNIQSTR_EQ (m1->tag, m2->tag);
+}
+
+static unsigned int
+hash_symbol (const symbol *m, unsigned int tablesize)
+{
+  /* Since tags are unique, we can hash the pointer itself.  */
+  return ((size_t) m->tag) % tablesize;

 }
 
 
 }
 
 

+/*-------------------------------.
+| Create the symbol hash table.  |
+`-------------------------------*/
+

 void
 void

-free_symtab (void)
+symbols_new (void)
+{
+  symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
+                                 NULL,
+                                 (Hash_hasher) hash_symbol,
+                                 (Hash_comparator) hash_compare_symbol,
+                                 (Hash_data_freer) symbol_free);
+}
+
+
+/*----------------------------------------------------------------.
+| Find the symbol named KEY, and return it.  If it does not exist |
+| yet, create it.                                                 |
+`----------------------------------------------------------------*/
+
+symbol *
+symbol_get (const char *key, location loc)

 {
 {

+  symbol probe;
+  symbol *entry;
+
+  /* Keep the symbol in a printable form.  */
+  key = uniqstr_new (quotearg_style (escape_quoting_style, key));
+  *(char const **) &probe.tag = key;
+  entry = hash_lookup (symbol_table, &probe);
+
+  if (!entry)
+    {
+      /* First insertion in the hash. */
+      entry = symbol_new (key, loc);
+      hash_insert (symbol_table, entry);
+    }
+  return entry;
+}
+
+
+/*------------------------------------------------------------------.
+| Generate a dummy nonterminal, whose name cannot conflict with the |
+| user's names.                                                     |
+`------------------------------------------------------------------*/
+
+symbol *
+dummy_symbol_get (location loc)
+{
+  /* Incremented for each generated symbol.  */
+  static int dummy_count = 0;
+  static char buf[256];
+
+  symbol *sym;
+
+  sprintf (buf, "@%d", ++dummy_count);
+  sym = symbol_get (buf, loc);
+  sym->class = nterm_sym;
+  sym->number = nvars++;
+  return sym;
+}
+
+
+/*-------------------.
+| Free the symbols.  |
+`-------------------*/
+
+void
+symbols_free (void)
+{
+  hash_free (symbol_table);
+  free (symbols);
+}
+
+
+/*---------------------------------------------------------------.
+| Look for undefined symbols, report an error, and consider them |
+| terminals.                                                     |
+`---------------------------------------------------------------*/
+
+void
+symbols_do (symbol_processor processor, void *processor_data)
+{
+  hash_do_for_each (symbol_table,
+                   (Hash_processor) processor,
+                   processor_data);
+}
+
+
+/*--------------------------------------------------------------.
+| Check that all the symbols are defined.  Report any undefined |
+| symbols and consider them nonterminals.                       |
+`--------------------------------------------------------------*/
+
+void
+symbols_check_defined (void)
+{
+  symbols_do (symbol_check_defined, NULL);
+}
+
+/*------------------------------------------------------------------.
+| Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
+| number.                                                           |
+`------------------------------------------------------------------*/
+
+static void
+symbols_token_translations_init (void)
+{
+  bool num_256_available_p = true;

   int i;
   int i;

-  bucket *bp, *bptmp;          /* JF don't use ptr after free */

 
 

-  for (i = 0; i < TABSIZE; i++)
+  /* Find the highest user token number, and whether 256, the POSIX
+     preferred user token number for the error token, is used.  */
+  max_user_token_number = 0;
+  for (i = 0; i < ntokens; ++i)

     {
     {

-      bp = symtab[i];
-      while (bp)
+      symbol *this = symbols[i];
+      if (this->user_token_number != USER_NUMBER_UNDEFINED)

        {
        {

-         bptmp = bp->link;
-#if 0
-         /* This causes crashes because one string can appear more
-            than once.  */
-         if (bp->type_name)
-           XFREE (bp->type_name);
-#endif
-         XFREE (bp->tag);
-         XFREE (bp);
-         bp = bptmp;
+         if (this->user_token_number > max_user_token_number)
+           max_user_token_number = this->user_token_number;
+         if (this->user_token_number == 256)
+           num_256_available_p = false;

        }
     }
        }
     }

-  XFREE (symtab);
+
+  /* If 256 is not used, assign it to error, to follow POSIX.  */
+  if (num_256_available_p
+      && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
+    errtoken->user_token_number = 256;
+
+  /* Set the missing user numbers. */
+  if (max_user_token_number < 256)
+    max_user_token_number = 256;
+
+  for (i = 0; i < ntokens; ++i)
+    {
+      symbol *this = symbols[i];
+      if (this->user_token_number == USER_NUMBER_UNDEFINED)
+       this->user_token_number = ++max_user_token_number;
+      if (this->user_token_number > max_user_token_number)
+       max_user_token_number = this->user_token_number;
+    }
+
+  token_translations = XCALLOC (symbol_number, max_user_token_number + 1);
+
+  /* Initialize all entries for literal tokens to 2, the internal
+     token number for $undefined, which represents all invalid inputs.
+     */
+  for (i = 0; i < max_user_token_number + 1; i++)
+    token_translations[i] = undeftoken->number;
+  symbols_do (symbol_translation, NULL);
+}
+
+
+/*----------------------------------------------------------------.
+| Assign symbol numbers, and write definition of token names into |
+| FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
+`----------------------------------------------------------------*/
+
+void
+symbols_pack (void)
+{
+  symbols = XCALLOC (symbol *, nsyms);
+
+  symbols_do (symbol_check_alias_consistence, NULL);
+  symbols_do (symbol_pack, NULL);
+
+  symbols_token_translations_init ();
+
+  if (startsymbol->class == unknown_sym)
+    fatal_at (startsymbol_location,
+             _("the start symbol %s is undefined"),
+             startsymbol->tag);
+  else if (startsymbol->class == token_sym)
+    fatal_at (startsymbol_location,
+             _("the start symbol %s is a token"),
+             startsymbol->tag);

 }
 }