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 "quotearg.h"
  24 #include "hash.h"
  25 #include "complain.h"
  26 #include "symtab.h"
  27 #include "gram.h"
  28
  29 /*------------------------.
  30 | Distinguished symbols.  |
  31 `------------------------*/
  32
  33 symbol_t *errtoken = NULL;
  34 symbol_t *undeftoken = NULL;
  35 symbol_t *endtoken = NULL;
  36 symbol_t *accept = NULL;
  37 symbol_t *startsymbol = NULL;
  38 location_t startsymbol_location;
  39
  40 /*---------------------------------.
  41 | Create a new symbol, named TAG.  |
  42 `---------------------------------*/
  43
  44 static symbol_t *
  45 symbol_new (struniq_t tag, location_t location)
  46 {
  47   symbol_t *res = XMALLOC (symbol_t, 1);
  48
  49   struniq_assert (tag);
  50   res->tag = tag;
  51   res->location = location;
  52
  53   res->type_name = NULL;
  54   res->destructor = NULL;
  55   res->printer = NULL;
  56
  57   res->number = NUMBER_UNDEFINED;
  58   res->prec = 0;
  59   res->assoc = undef_assoc;
  60   res->user_token_number = USER_NUMBER_UNDEFINED;
  61
  62   res->alias = NULL;
  63   res->class = unknown_sym;
  64
  65   nsyms++;
  66   return res;
  67 }
  68
  69
  70 /*------------------------------------------------------------------.
  71 | Set the TYPE_NAME associated to SYMBOL.  Does nothing if passed 0 |
  72 | as TYPE_NAME.                                                     |
  73 `------------------------------------------------------------------*/
  74
  75 void
  76 symbol_type_set (symbol_t *symbol, struniq_t type_name, location_t location)
  77 {
  78   if (type_name)
  79     {
  80       if (symbol->type_name)
  81         complain_at (location,
  82                      _("type redeclaration for %s"), symbol->tag);
  83       struniq_assert (type_name);
  84       symbol->type_name = type_name;
  85     }
  86 }
  87
  88
  89 /*-------------------------------------------------------------------.
  90 | Set the DESTRUCTOR associated to SYMBOL.  Do nothing if passed 0.  |
  91 `-------------------------------------------------------------------*/
  92
  93 void
  94 symbol_destructor_set (symbol_t *symbol, char *destructor, location_t location)
  95 {
  96   if (destructor)
  97     {
  98       if (symbol->destructor)
  99         complain_at (location,
 100                      _("%s redeclaration for %s"),
 101                      "%destructor", symbol->tag);
 102       symbol->destructor = destructor;
 103       symbol->destructor_location = location;
 104     }
 105 }
 106
 107
 108 /*----------------------------------------------------------------.
 109 | Set the PRINTER associated to SYMBOL.  Do nothing if passed 0.  |
 110 `----------------------------------------------------------------*/
 111
 112 void
 113 symbol_printer_set (symbol_t *symbol, char *printer, location_t location)
 114 {
 115   if (printer)
 116     {
 117       if (symbol->printer)
 118         complain_at (location,
 119                      _("%s redeclaration for %s"),
 120                      "%printer", symbol->tag);
 121       symbol->printer = printer;
 122       symbol->printer_location = location;
 123     }
 124 }
 125
 126
 127 /*------------------------------------------------------------------.
 128 | Set the PRECEDENCE associated to SYMBOL.  Does nothing if invoked |
 129 | with UNDEF_ASSOC as ASSOC.                                        |
 130 `------------------------------------------------------------------*/
 131
 132 void
 133 symbol_precedence_set (symbol_t *symbol,
 134                        int prec, assoc_t assoc, location_t location)
 135 {
 136   if (assoc != undef_assoc)
 137     {
 138       if (symbol->prec != 0)
 139         complain_at (location,
 140                      _("redefining precedence of %s"),
 141                      symbol->tag);
 142       symbol->prec = prec;
 143       symbol->assoc = assoc;
 144     }
 145
 146   /* Only terminals have a precedence. */
 147   symbol_class_set (symbol, token_sym, location);
 148 }
 149
 150
 151 /*-------------------------------------.
 152 | Set the CLASS associated to SYMBOL.  |
 153 `-------------------------------------*/
 154
 155 void
 156 symbol_class_set (symbol_t *symbol, symbol_class class, location_t location)
 157 {
 158   if (symbol->class != unknown_sym && symbol->class != class)
 159     complain_at (location, _("symbol %s redefined"), symbol->tag);
 160
 161   if (class == nterm_sym && symbol->class != nterm_sym)
 162     symbol->number = nvars++;
 163   else if (class == token_sym && symbol->number == NUMBER_UNDEFINED)
 164     symbol->number = ntokens++;
 165
 166   symbol->class = class;
 167 }
 168
 169
 170 /*-------------------------------------------------.
 171 | Set the USER_TOKEN_NUMBER associated to SYMBOL.  |
 172 `-------------------------------------------------*/
 173
 174 void
 175 symbol_user_token_number_set (symbol_t *symbol,
 176                               int user_token_number, location_t location)
 177 {
 178   if (symbol->class != token_sym)
 179     abort ();
 180
 181   if (symbol->user_token_number != USER_NUMBER_UNDEFINED
 182       && symbol->user_token_number != user_token_number)
 183     complain_at (location, _("redefining user token number of %s"),
 184                  symbol->tag);
 185
 186   symbol->user_token_number = user_token_number;
 187   /* User defined $end token? */
 188   if (user_token_number == 0)
 189     {
 190       endtoken = symbol;
 191       endtoken->number = 0;
 192       /* It is always mapped to 0, so it was already counted in
 193          NTOKENS.  */
 194       --ntokens;
 195     }
 196 }
 197
 198
 199 /*------------.
 200 | Free THIS.  |
 201 `------------*/
 202
 203 static void
 204 symbol_free (symbol_t *this)
 205 {
 206   free (this);
 207 }
 208
 209
 210 /*-----------------------------------------------------------.
 211 | If THIS is not defined, report an error, and consider it a |
 212 | nonterminal.                                               |
 213 `-----------------------------------------------------------*/
 214
 215 static bool
 216 symbol_check_defined (symbol_t *this)
 217 {
 218   if (this->class == unknown_sym)
 219     {
 220       complain_at
 221         (this->location,
 222          _("symbol %s is used, but is not defined as a token and has no rules"),
 223          this->tag);
 224       this->class = nterm_sym;
 225       this->number = nvars++;
 226     }
 227
 228   return true;
 229 }
 230
 231
 232 /*-------------------------------------------------------------------.
 233 | Declare the new SYMBOL.  Make it an alias of SYMVAL, and type them |
 234 | with TYPENAME.                                                     |
 235 `-------------------------------------------------------------------*/
 236
 237 void
 238 symbol_make_alias (symbol_t *symbol, symbol_t *symval, location_t loc)
 239 {
 240   if (symval->alias)
 241     warn_at (loc, _("symbol `%s' used more than once as a literal string"),
 242           symval->tag);
 243   else if (symbol->alias)
 244     warn_at (loc, _("symbol `%s' given more than one literal string"),
 245           symbol->tag);
 246   else
 247     {
 248       symval->class = token_sym;
 249       symval->user_token_number = symbol->user_token_number;
 250       symbol->user_token_number = USER_NUMBER_ALIAS;
 251       symval->alias = symbol;
 252       symbol->alias = symval;
 253       /* symbol and symval combined are only one symbol */
 254       nsyms--;
 255       ntokens--;
 256       if (ntokens != symbol->number && ntokens != symval->number)
 257         abort ();
 258       symbol->number = symval->number =
 259         (symval->number < symbol->number) ? symval->number : symbol->number;
 260     }
 261 }
 262
 263
 264 /*---------------------------------------------------------.
 265 | Check that THIS, and its alias, have same precedence and |
 266 | associativity.                                           |
 267 `---------------------------------------------------------*/
 268
 269 static bool
 270 symbol_check_alias_consistence (symbol_t *this)
 271 {
 272   /* Check only those who _are_ the aliases. */
 273   if (this->alias && this->user_token_number == USER_NUMBER_ALIAS)
 274     {
 275       if (this->prec != this->alias->prec)
 276         {
 277           if (this->prec != 0 && this->alias->prec != 0)
 278             complain_at (this->alias->location,
 279                          _("conflicting precedences for %s and %s"),
 280                          this->tag, this->alias->tag);
 281           if (this->prec != 0)
 282             this->alias->prec = this->prec;
 283           else
 284             this->prec = this->alias->prec;
 285         }
 286
 287       if (this->assoc != this->alias->assoc)
 288         {
 289           if (this->assoc != undef_assoc && this->alias->assoc != undef_assoc)
 290             complain_at (this->alias->location,
 291                          _("conflicting associativities for %s (%s) and %s (%s)"),
 292                          this->tag, assoc_to_string (this->assoc),
 293                          this->alias->tag, assoc_to_string (this->alias->assoc));
 294           if (this->assoc != undef_assoc)
 295             this->alias->assoc = this->assoc;
 296           else
 297             this->assoc = this->alias->assoc;
 298         }
 299     }
 300   return true;
 301 }
 302
 303
 304 /*-------------------------------------------------------------------.
 305 | Assign a symbol number, and write the definition of the token name |
 306 | into FDEFINES.  Put in SYMBOLS.                                    |
 307 `-------------------------------------------------------------------*/
 308
 309 static bool
 310 symbol_pack (symbol_t *this)
 311 {
 312   if (this->class == nterm_sym)
 313     {
 314       this->number += ntokens;
 315     }
 316   else if (this->alias)
 317     {
 318       /* This symbol and its alias are a single token defn.
 319          Allocate a tokno, and assign to both check agreement of
 320          prec and assoc fields and make both the same */
 321       if (this->number == NUMBER_UNDEFINED)
 322         {
 323           if (this == endtoken || this->alias == endtoken)
 324             this->number = this->alias->number = 0;
 325           else
 326             {
 327               if (this->alias->number == NUMBER_UNDEFINED)
 328                 abort ();
 329               this->number = this->alias->number;
 330             }
 331         }
 332       /* Do not do processing below for USER_NUMBER_ALIASes.  */
 333       if (this->user_token_number == USER_NUMBER_ALIAS)
 334         return true;
 335     }
 336   else /* this->class == token_sym */
 337     {
 338       if (this->number == NUMBER_UNDEFINED)
 339         abort ();
 340     }
 341
 342   symbols[this->number] = this;
 343   return true;
 344 }
 345
 346
 347
 348
 349 /*--------------------------------------------------.
 350 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 351 `--------------------------------------------------*/
 352
 353 static bool
 354 symbol_translation (symbol_t *this)
 355 {
 356   /* Non-terminal? */
 357   if (this->class == token_sym
 358       && this->user_token_number != USER_NUMBER_ALIAS)
 359     {
 360       /* A token which translation has already been set? */
 361       if (token_translations[this->user_token_number] != undeftoken->number)
 362         complain_at (this->location,
 363                      _("tokens %s and %s both assigned number %d"),
 364                      symbols[token_translations[this->user_token_number]]->tag,
 365                      this->tag, this->user_token_number);
 366
 367       token_translations[this->user_token_number] = this->number;
 368     }
 369
 370   return true;
 371 }
 372
 373
 374 /*----------------------.
 375 | A symbol hash table.  |
 376 `----------------------*/
 377
 378 /* Initial capacity of symbols hash table.  */
 379 #define HT_INITIAL_CAPACITY 257
 380
 381 static struct hash_table *symbol_table = NULL;
 382
 383 static bool
 384 hash_compare_symbol (const symbol_t *m1, const symbol_t *m2)
 385 {
 386   /* Since tags are unique, we can compare the pointers themselves.  */
 387   return STRUNIQ_EQ (m1->tag, m2->tag);
 388 }
 389
 390 static unsigned int
 391 hash_symbol (const symbol_t *m, unsigned int tablesize)
 392 {
 393   /* Since tags are unique, we can hash the pointer itself.  */
 394   return ((size_t) m->tag) % tablesize;
 395 }
 396
 397
 398 /*-------------------------------.
 399 | Create the symbol hash table.  |
 400 `-------------------------------*/
 401
 402 void
 403 symbols_new (void)
 404 {
 405   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 406                                   NULL,
 407                                   (Hash_hasher) hash_symbol,
 408                                   (Hash_comparator) hash_compare_symbol,
 409                                   (Hash_data_freer) symbol_free);
 410 }
 411
 412
 413 /*----------------------------------------------------------------.
 414 | Find the symbol named KEY, and return it.  If it does not exist |
 415 | yet, create it.                                                 |
 416 `----------------------------------------------------------------*/
 417
 418 symbol_t *
 419 symbol_get (const char *key, location_t location)
 420 {
 421   symbol_t probe;
 422   symbol_t *entry;
 423
 424   /* Keep the symbol in a printable form.  */
 425   key = struniq_new (quotearg_style (escape_quoting_style, key));
 426   *(char const **) &probe.tag = key;
 427   entry = hash_lookup (symbol_table, &probe);
 428
 429   if (!entry)
 430     {
 431       /* First insertion in the hash. */
 432       entry = symbol_new (key, location);
 433       hash_insert (symbol_table, entry);
 434     }
 435   return entry;
 436 }
 437
 438
 439 /*------------------------------------------------------------------.
 440 | Generate a dummy nonterminal, whose name cannot conflict with the |
 441 | user's names.                                                     |
 442 `------------------------------------------------------------------*/
 443
 444 symbol_t *
 445 dummy_symbol_get (location_t location)
 446 {
 447   /* Incremented for each generated symbol.  */
 448   static int dummy_count = 0;
 449   static char buf[256];
 450
 451   symbol_t *sym;
 452
 453   sprintf (buf, "@%d", ++dummy_count);
 454   sym = symbol_get (buf, location);
 455   sym->class = nterm_sym;
 456   sym->number = nvars++;
 457   return sym;
 458 }
 459
 460
 461 /*-------------------.
 462 | Free the symbols.  |
 463 `-------------------*/
 464
 465 void
 466 symbols_free (void)
 467 {
 468   hash_free (symbol_table);
 469   free (symbols);
 470 }
 471
 472
 473 /*---------------------------------------------------------------.
 474 | Look for undefined symbols, report an error, and consider them |
 475 | terminals.                                                     |
 476 `---------------------------------------------------------------*/
 477
 478 void
 479 symbols_do (symbol_processor processor, void *processor_data)
 480 {
 481   hash_do_for_each (symbol_table,
 482                     (Hash_processor) processor,
 483                     processor_data);
 484 }
 485
 486
 487 /*--------------------------------------------------------------.
 488 | Check that all the symbols are defined.  Report any undefined |
 489 | symbols and consider them nonterminals.                       |
 490 `--------------------------------------------------------------*/
 491
 492 void
 493 symbols_check_defined (void)
 494 {
 495   symbols_do (symbol_check_defined, NULL);
 496 }
 497
 498 /*------------------------------------------------------------------.
 499 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 500 | number.                                                           |
 501 `------------------------------------------------------------------*/
 502
 503 static void
 504 symbols_token_translations_init (void)
 505 {
 506   bool num_256_available_p = true;
 507   int i;
 508
 509   /* Find the highest user token number, and whether 256, the POSIX
 510      preferred user token number for the error token, is used.  */
 511   max_user_token_number = 0;
 512   for (i = 0; i < ntokens; ++i)
 513     {
 514       symbol_t *this = symbols[i];
 515       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 516         {
 517           if (this->user_token_number > max_user_token_number)
 518             max_user_token_number = this->user_token_number;
 519           if (this->user_token_number == 256)
 520             num_256_available_p = false;
 521         }
 522     }
 523
 524   /* If 256 is not used, assign it to error, to follow POSIX.  */
 525   if (num_256_available_p
 526       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 527     errtoken->user_token_number = 256;
 528
 529   /* Set the missing user numbers. */
 530   if (max_user_token_number < 256)
 531     max_user_token_number = 256;
 532
 533   for (i = 0; i < ntokens; ++i)
 534     {
 535       symbol_t *this = symbols[i];
 536       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 537         this->user_token_number = ++max_user_token_number;
 538       if (this->user_token_number > max_user_token_number)
 539         max_user_token_number = this->user_token_number;
 540     }
 541
 542   token_translations = XCALLOC (symbol_number_t, max_user_token_number + 1);
 543
 544   /* Initialize all entries for literal tokens to 2, the internal
 545      token number for $undefined, which represents all invalid inputs.
 546      */
 547   for (i = 0; i < max_user_token_number + 1; i++)
 548     token_translations[i] = undeftoken->number;
 549   symbols_do (symbol_translation, NULL);
 550 }
 551
 552
 553 /*----------------------------------------------------------------.
 554 | Assign symbol numbers, and write definition of token names into |
 555 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 556 `----------------------------------------------------------------*/
 557
 558 void
 559 symbols_pack (void)
 560 {
 561   symbols = XCALLOC (symbol_t *, nsyms);
 562
 563   symbols_do (symbol_check_alias_consistence, NULL);
 564   symbols_do (symbol_pack, NULL);
 565
 566   symbols_token_translations_init ();
 567
 568   if (startsymbol->class == unknown_sym)
 569     fatal_at (startsymbol_location,
 570               _("the start symbol %s is undefined"),
 571               startsymbol->tag);
 572   else if (startsymbol->class == token_sym)
 573     fatal_at (startsymbol_location,
 574               _("the start symbol %s is a token"),
 575               startsymbol->tag);
 576 }