src/symtab.c

   1 /* Symbol table manager for Bison,
   2    Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "hash.h"
  24 #include "complain.h"
  25 #include "symtab.h"
  26 #include "gram.h"
  27
  28 /*------------------------.
  29 | Distinguished symbols.  |
  30 `------------------------*/
  31
  32 symbol_t *errtoken = NULL;
  33 symbol_t *undeftoken = NULL;
  34 symbol_t *eoftoken = NULL;
  35 symbol_t *axiom = NULL;
  36 symbol_t *startsymbol = NULL;
  37 location_t startsymbol_location;
  38
  39 /*---------------------------------.
  40 | Create a new symbol, named TAG.  |
  41 `---------------------------------*/
  42
  43 static symbol_t *
  44 symbol_new (const char *tag)
  45 {
  46   symbol_t *res = XMALLOC (symbol_t, 1);
  47
  48   res->tag = xstrdup (tag);
  49   res->type_name = NULL;
  50   res->number = NUMBER_UNDEFINED;
  51   res->prec = 0;
  52   res->assoc = right_assoc;
  53   res->user_token_number = USER_NUMBER_UNDEFINED;
  54   res->alias = NULL;
  55   res->class = unknown_sym;
  56
  57   nsyms++;
  58   return res;
  59 }
  60
  61
  62 /*------------------------------------------------------------------.
  63 | Set the TYPE_NAME associated to SYMBOL.  Does nothing if passed 0 |
  64 | as TYPE_NAME.                                                     |
  65 `------------------------------------------------------------------*/
  66
  67 void
  68 symbol_type_set (symbol_t *symbol, char *type_name)
  69 {
  70   if (type_name)
  71     {
  72       if (symbol->type_name)
  73         complain (_("type redeclaration for %s"), symbol->tag);
  74       symbol->type_name = type_name;
  75     }
  76 }
  77
  78
  79 /*------------------------------------------------------------------.
  80 | Set the PRECEDENCE associated to SYMBOL.  Does nothing if invoked |
  81 | with UNDEF_ASSOC as ASSOC.                                        |
  82 `------------------------------------------------------------------*/
  83
  84 void
  85 symbol_precedence_set (symbol_t *symbol,
  86                        int prec, associativity assoc)
  87 {
  88   if (assoc != undef_assoc)
  89     {
  90       if (symbol->prec != 0)
  91         complain (_("redefining precedence of %s"), symbol->tag);
  92       symbol->prec = prec;
  93       symbol->assoc = assoc;
  94     }
  95
  96   /* Only terminals have a precedence. */
  97   symbol_class_set (symbol, token_sym);
  98 }
  99
 100
 101 /*-------------------------------------.
 102 | Set the CLASS associated to SYMBOL.  |
 103 `-------------------------------------*/
 104
 105 void
 106 symbol_class_set (symbol_t *symbol, symbol_class class)
 107 {
 108   if (symbol->class != unknown_sym && symbol->class != class)
 109     complain (_("symbol %s redefined"), symbol->tag);
 110
 111   if (class == nterm_sym && symbol->class != nterm_sym)
 112     symbol->number = nvars++;
 113   else if (class == token_sym && symbol->number == NUMBER_UNDEFINED)
 114     symbol->number = ntokens++;
 115
 116   symbol->class = class;
 117 }
 118
 119
 120 /*-------------------------------------------------.
 121 | Set the USER_TOKEN_NUMBER associated to SYMBOL.  |
 122 `-------------------------------------------------*/
 123
 124 void
 125 symbol_user_token_number_set (symbol_t *symbol, int user_token_number)
 126 {
 127   assert (symbol->class == token_sym);
 128
 129   if (symbol->user_token_number != USER_NUMBER_UNDEFINED
 130       && symbol->user_token_number != user_token_number)
 131     complain (_("redefining user token number of %s"), symbol->tag);
 132
 133   symbol->user_token_number = user_token_number;
 134   /* User defined EOF token? */
 135   if (user_token_number == 0)
 136     {
 137       eoftoken = symbol;
 138       eoftoken->number = 0;
 139       /* It is always mapped to 0, so it was already counted in
 140          NTOKENS.  */
 141       --ntokens;
 142     }
 143 }
 144
 145
 146 /*------------.
 147 | Free THIS.  |
 148 `------------*/
 149
 150 static void
 151 symbol_free (symbol_t *this)
 152 {
 153 #if 0
 154   /* This causes crashes because one string can appear more
 155      than once.  */
 156   XFREE (this->type_name);
 157 #endif
 158   XFREE (this->tag);
 159   XFREE (this);
 160 }
 161
 162
 163 /*-----------------------------------------------------------.
 164 | If THIS is not defined, report an error, and consider it a |
 165 | nonterminal.                                               |
 166 `-----------------------------------------------------------*/
 167
 168 static bool
 169 symbol_check_defined (symbol_t *this)
 170 {
 171   if (this->class == unknown_sym)
 172     {
 173       complain
 174         (_("symbol %s is used, but is not defined as a token and has no rules"),
 175          this->tag);
 176       this->class = nterm_sym;
 177       this->number = nvars++;
 178     }
 179
 180   return TRUE;
 181 }
 182
 183
 184 /*-------------------------------------------------------------------.
 185 | Declare the new SYMBOL.  Make it an alias of SYMVAL, and type them |
 186 | with TYPENAME.                                                     |
 187 `-------------------------------------------------------------------*/
 188
 189 void
 190 symbol_make_alias (symbol_t *symbol, symbol_t *symval)
 191 {
 192   if (symval->alias)
 193     warn (_("symbol `%s' used more than once as a literal string"),
 194           symval->tag);
 195   else if (symbol->alias)
 196     warn (_("symbol `%s' given more than one literal string"),
 197           symbol->tag);
 198   else
 199     {
 200       symval->class = token_sym;
 201       symval->user_token_number = symbol->user_token_number;
 202       symbol->user_token_number = USER_NUMBER_ALIAS;
 203       symval->alias = symbol;
 204       symbol->alias = symval;
 205       /* symbol and symval combined are only one symbol */
 206       nsyms--;
 207       ntokens--;
 208       assert (ntokens == symbol->number || ntokens == symval->number);
 209       symbol->number = symval->number =
 210         (symval->number < symbol->number) ? symval->number : symbol->number;
 211     }
 212 }
 213
 214
 215 /*---------------------------------------------------------.
 216 | Check that THIS, and its alias, have same precedence and |
 217 | associativity.                                           |
 218 `---------------------------------------------------------*/
 219
 220 static bool
 221 symbol_check_alias_consistence (symbol_t *this)
 222 {
 223   /* Check only those who _are_ the aliases. */
 224   if (this->alias && this->user_token_number == USER_NUMBER_ALIAS)
 225     {
 226       if (this->prec != this->alias->prec)
 227         {
 228           if (this->prec != 0 && this->alias->prec != 0)
 229             complain (_("conflicting precedences for %s and %s"),
 230                       this->tag, this->alias->tag);
 231           if (this->prec != 0)
 232             this->alias->prec = this->prec;
 233           else
 234             this->prec = this->alias->prec;
 235         }
 236
 237       if (this->assoc != this->alias->assoc)
 238         {
 239           /* FIXME: For some reason (probably the S/R => keep the S),
 240              the right assoc is chosen has the ``not set''.  This is
 241              not nice, fix this!  */
 242           if (this->assoc != right_assoc
 243               && this->alias->assoc != right_assoc)
 244             complain (_("conflicting associativities for %s and %s"),
 245                       this->tag, this->alias->tag);
 246           if (this->assoc != 0)
 247             this->alias->assoc = this->assoc;
 248           else
 249             this->assoc = this->alias->assoc;
 250         }
 251     }
 252   return TRUE;
 253 }
 254
 255
 256 /*-------------------------------------------------------------------.
 257 | Assign a symbol number, and write the definition of the token name |
 258 | into FDEFINES.  Put in SYMBOLS.                                    |
 259 `-------------------------------------------------------------------*/
 260
 261 static bool
 262 symbol_pack (symbol_t *this)
 263 {
 264   if (this->class == nterm_sym)
 265     {
 266       this->number += ntokens;
 267     }
 268   else if (this->alias)
 269     {
 270       /* This symbol and its alias are a single token defn.
 271          Allocate a tokno, and assign to both check agreement of
 272          prec and assoc fields and make both the same */
 273       if (this->number == NUMBER_UNDEFINED)
 274         {
 275           if (this == eoftoken || this->alias == eoftoken)
 276             this->number = this->alias->number = 0;
 277           else
 278             {
 279               assert (this->alias->number != NUMBER_UNDEFINED);
 280               this->number = this->alias->number;
 281             }
 282         }
 283       /* Do not do processing below for USER_NUMBER_ALIASs.  */
 284       if (this->user_token_number == USER_NUMBER_ALIAS)
 285         return TRUE;
 286     }
 287   else /* this->class == token_sym */
 288     {
 289       assert (this->number != NUMBER_UNDEFINED);
 290     }
 291
 292   symbols[this->number] = this;
 293   return TRUE;
 294 }
 295
 296
 297
 298
 299 /*--------------------------------------------------.
 300 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 301 `--------------------------------------------------*/
 302
 303 static bool
 304 symbol_translation (symbol_t *this)
 305 {
 306   /* Non-terminal? */
 307   if (this->class == token_sym
 308       && this->user_token_number != USER_NUMBER_ALIAS)
 309     {
 310       /* A token which translation has already been set? */
 311       if (token_translations[this->user_token_number] != undeftoken->number)
 312         complain (_("tokens %s and %s both assigned number %d"),
 313                   symbols[token_translations[this->user_token_number]]->tag,
 314                   this->tag, this->user_token_number);
 315
 316       token_translations[this->user_token_number] = this->number;
 317     }
 318
 319   return TRUE;
 320 }
 321
 322
 323 /*----------------------.
 324 | A symbol hash table.  |
 325 `----------------------*/
 326
 327 /* Initial capacity of symbols hash table.  */
 328 #define HT_INITIAL_CAPACITY 257
 329
 330 static struct hash_table *symbol_table = NULL;
 331
 332 static bool
 333 hash_compare_symbol_t (const symbol_t *m1, const symbol_t *m2)
 334 {
 335   return strcmp (m1->tag, m2->tag) ? FALSE : TRUE;
 336 }
 337
 338 static unsigned int
 339 hash_symbol_t (const symbol_t *m, unsigned int tablesize)
 340 {
 341   return hash_string (m->tag, tablesize);
 342 }
 343
 344
 345 /*-------------------------------.
 346 | Create the symbol hash table.  |
 347 `-------------------------------*/
 348
 349 void
 350 symbols_new (void)
 351 {
 352   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 353                                   NULL,
 354                                   (Hash_hasher) hash_symbol_t,
 355                                   (Hash_comparator) hash_compare_symbol_t,
 356                                   (Hash_data_freer) symbol_free);
 357 }
 358
 359
 360 /*----------------------------------------------------------------.
 361 | Find the symbol named KEY, and return it.  If it does not exist |
 362 | yet, create it.                                                 |
 363 `----------------------------------------------------------------*/
 364
 365 symbol_t *
 366 getsym (const char *key)
 367 {
 368   symbol_t probe;
 369   symbol_t *entry;
 370
 371   (const char *) probe.tag = key;
 372   entry = hash_lookup (symbol_table, &probe);
 373
 374   if (!entry)
 375     {
 376       /* First insertion in the hash. */
 377       entry = symbol_new (key);
 378       hash_insert (symbol_table, entry);
 379     }
 380   return entry;
 381 }
 382
 383
 384 /*-------------------.
 385 | Free the symbols.  |
 386 `-------------------*/
 387
 388 void
 389 symbols_free (void)
 390 {
 391   hash_free (symbol_table);
 392 }
 393
 394
 395 /*---------------------------------------------------------------.
 396 | Look for undefined symbols, report an error, and consider them |
 397 | terminals.                                                     |
 398 `---------------------------------------------------------------*/
 399
 400 void
 401 symbols_do (symbol_processor processor, void *processor_data)
 402 {
 403   hash_do_for_each (symbol_table,
 404                     (Hash_processor) processor,
 405                     processor_data);
 406 }
 407
 408
 409 /*--------------------------------------------------------------.
 410 | Check that all the symbols are defined.  Report any undefined |
 411 | symbols and consider them nonterminals.                       |
 412 `--------------------------------------------------------------*/
 413
 414 void
 415 symbols_check_defined (void)
 416 {
 417   symbols_do (symbol_check_defined, NULL);
 418 }
 419
 420 /*------------------------------------------------------------------.
 421 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 422 | number.                                                           |
 423 `------------------------------------------------------------------*/
 424
 425 static void
 426 symbols_token_translations_init (void)
 427 {
 428   int num_256_available_p = TRUE;
 429   int i;
 430
 431   /* Find the highest user token number, and whether 256, the POSIX
 432      preferred user token number for the error token, is used.  */
 433   max_user_token_number = 0;
 434   for (i = 0; i < ntokens; ++i)
 435     {
 436       symbol_t *this = symbols[i];
 437       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 438         {
 439           if (this->user_token_number > max_user_token_number)
 440             max_user_token_number = this->user_token_number;
 441           if (this->user_token_number == 256)
 442             num_256_available_p = FALSE;
 443         }
 444     }
 445
 446   /* If 256 is not used, assign it to error, to follow POSIX.  */
 447   if (num_256_available_p
 448       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 449     errtoken->user_token_number = 256;
 450
 451   /* Set the missing user numbers. */
 452   if (max_user_token_number < 256)
 453     max_user_token_number = 256;
 454
 455   for (i = 0; i < ntokens; ++i)
 456     {
 457       symbol_t *this = symbols[i];
 458       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 459         this->user_token_number = ++max_user_token_number;
 460       if (this->user_token_number > max_user_token_number)
 461         max_user_token_number = this->user_token_number;
 462     }
 463
 464   token_translations = XCALLOC (symbol_number_t, max_user_token_number + 1);
 465
 466   /* Initialize all entries for literal tokens to 2, the internal
 467      token number for $undefined., which represents all invalid
 468      inputs.  */
 469   for (i = 0; i < max_user_token_number + 1; i++)
 470     token_translations[i] = undeftoken->number;
 471   symbols_do (symbol_translation, NULL);
 472 }
 473
 474
 475 /*----------------------------------------------------------------.
 476 | Assign symbol numbers, and write definition of token names into |
 477 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 478 `----------------------------------------------------------------*/
 479
 480 void
 481 symbols_pack (void)
 482 {
 483   symbols = XCALLOC (symbol_t *, nsyms);
 484
 485   symbols_do (symbol_check_alias_consistence, NULL);
 486   symbols_do (symbol_pack, NULL);
 487
 488   symbols_token_translations_init ();
 489
 490   if (startsymbol->class == unknown_sym)
 491     fatal (_("the start symbol %s is undefined"), startsymbol->tag);
 492   else if (startsymbol->class == token_sym)
 493     fatal (_("the start symbol %s is a token"), startsymbol->tag);
 494 }