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   assert (symbol->class == token_sym);
 179
 180   if (symbol->user_token_number != USER_NUMBER_UNDEFINED
 181       && symbol->user_token_number != user_token_number)
 182     complain_at (location, _("redefining user token number of %s"),
 183                  symbol->tag);
 184
 185   symbol->user_token_number = user_token_number;
 186   /* User defined $end token? */
 187   if (user_token_number == 0)
 188     {
 189       endtoken = symbol;
 190       endtoken->number = 0;
 191       /* It is always mapped to 0, so it was already counted in
 192          NTOKENS.  */
 193       --ntokens;
 194     }
 195 }
 196
 197
 198 /*------------.
 199 | Free THIS.  |
 200 `------------*/
 201
 202 static void
 203 symbol_free (symbol_t *this)
 204 {
 205   free (this);
 206 }
 207
 208
 209 /*-----------------------------------------------------------.
 210 | If THIS is not defined, report an error, and consider it a |
 211 | nonterminal.                                               |
 212 `-----------------------------------------------------------*/
 213
 214 static bool
 215 symbol_check_defined (symbol_t *this)
 216 {
 217   if (this->class == unknown_sym)
 218     {
 219       complain_at
 220         (this->location,
 221          _("symbol %s is used, but is not defined as a token and has no rules"),
 222          this->tag);
 223       this->class = nterm_sym;
 224       this->number = nvars++;
 225     }
 226
 227   return true;
 228 }
 229
 230
 231 /*-------------------------------------------------------------------.
 232 | Declare the new SYMBOL.  Make it an alias of SYMVAL, and type them |
 233 | with TYPENAME.                                                     |
 234 `-------------------------------------------------------------------*/
 235
 236 void
 237 symbol_make_alias (symbol_t *symbol, symbol_t *symval, location_t loc)
 238 {
 239   if (symval->alias)
 240     warn_at (loc, _("symbol `%s' used more than once as a literal string"),
 241           symval->tag);
 242   else if (symbol->alias)
 243     warn_at (loc, _("symbol `%s' given more than one literal string"),
 244           symbol->tag);
 245   else
 246     {
 247       symval->class = token_sym;
 248       symval->user_token_number = symbol->user_token_number;
 249       symbol->user_token_number = USER_NUMBER_ALIAS;
 250       symval->alias = symbol;
 251       symbol->alias = symval;
 252       /* symbol and symval combined are only one symbol */
 253       nsyms--;
 254       ntokens--;
 255       assert (ntokens == symbol->number || ntokens == symval->number);
 256       symbol->number = symval->number =
 257         (symval->number < symbol->number) ? symval->number : symbol->number;
 258     }
 259 }
 260
 261
 262 /*---------------------------------------------------------.
 263 | Check that THIS, and its alias, have same precedence and |
 264 | associativity.                                           |
 265 `---------------------------------------------------------*/
 266
 267 static bool
 268 symbol_check_alias_consistence (symbol_t *this)
 269 {
 270   /* Check only those who _are_ the aliases. */
 271   if (this->alias && this->user_token_number == USER_NUMBER_ALIAS)
 272     {
 273       if (this->prec != this->alias->prec)
 274         {
 275           if (this->prec != 0 && this->alias->prec != 0)
 276             complain_at (this->alias->location,
 277                          _("conflicting precedences for %s and %s"),
 278                          this->tag, this->alias->tag);
 279           if (this->prec != 0)
 280             this->alias->prec = this->prec;
 281           else
 282             this->prec = this->alias->prec;
 283         }
 284
 285       if (this->assoc != this->alias->assoc)
 286         {
 287           if (this->assoc != undef_assoc && this->alias->assoc != undef_assoc)
 288             complain_at (this->alias->location,
 289                          _("conflicting associativities for %s (%s) and %s (%s)"),
 290                          this->tag, assoc_to_string (this->assoc),
 291                          this->alias->tag, assoc_to_string (this->alias->assoc));
 292           if (this->assoc != undef_assoc)
 293             this->alias->assoc = this->assoc;
 294           else
 295             this->assoc = this->alias->assoc;
 296         }
 297     }
 298   return true;
 299 }
 300
 301
 302 /*-------------------------------------------------------------------.
 303 | Assign a symbol number, and write the definition of the token name |
 304 | into FDEFINES.  Put in SYMBOLS.                                    |
 305 `-------------------------------------------------------------------*/
 306
 307 static bool
 308 symbol_pack (symbol_t *this)
 309 {
 310   if (this->class == nterm_sym)
 311     {
 312       this->number += ntokens;
 313     }
 314   else if (this->alias)
 315     {
 316       /* This symbol and its alias are a single token defn.
 317          Allocate a tokno, and assign to both check agreement of
 318          prec and assoc fields and make both the same */
 319       if (this->number == NUMBER_UNDEFINED)
 320         {
 321           if (this == endtoken || this->alias == endtoken)
 322             this->number = this->alias->number = 0;
 323           else
 324             {
 325               assert (this->alias->number != NUMBER_UNDEFINED);
 326               this->number = this->alias->number;
 327             }
 328         }
 329       /* Do not do processing below for USER_NUMBER_ALIASes.  */
 330       if (this->user_token_number == USER_NUMBER_ALIAS)
 331         return true;
 332     }
 333   else /* this->class == token_sym */
 334     {
 335       assert (this->number != NUMBER_UNDEFINED);
 336     }
 337
 338   symbols[this->number] = this;
 339   return true;
 340 }
 341
 342
 343
 344
 345 /*--------------------------------------------------.
 346 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 347 `--------------------------------------------------*/
 348
 349 static bool
 350 symbol_translation (symbol_t *this)
 351 {
 352   /* Non-terminal? */
 353   if (this->class == token_sym
 354       && this->user_token_number != USER_NUMBER_ALIAS)
 355     {
 356       /* A token which translation has already been set? */
 357       if (token_translations[this->user_token_number] != undeftoken->number)
 358         complain_at (this->location,
 359                      _("tokens %s and %s both assigned number %d"),
 360                      symbols[token_translations[this->user_token_number]]->tag,
 361                      this->tag, this->user_token_number);
 362
 363       token_translations[this->user_token_number] = this->number;
 364     }
 365
 366   return true;
 367 }
 368
 369
 370 /*----------------------.
 371 | A symbol hash table.  |
 372 `----------------------*/
 373
 374 /* Initial capacity of symbols hash table.  */
 375 #define HT_INITIAL_CAPACITY 257
 376
 377 static struct hash_table *symbol_table = NULL;
 378
 379 static bool
 380 hash_compare_symbol (const symbol_t *m1, const symbol_t *m2)
 381 {
 382   /* Since tags are unique, we can compare the pointers themselves.  */
 383   return STRUNIQ_EQ (m1->tag, m2->tag);
 384 }
 385
 386 static unsigned int
 387 hash_symbol (const symbol_t *m, unsigned int tablesize)
 388 {
 389   /* Since tags are unique, we can hash the pointer itself.  */
 390   return ((size_t) m->tag) % tablesize;
 391 }
 392
 393
 394 /*-------------------------------.
 395 | Create the symbol hash table.  |
 396 `-------------------------------*/
 397
 398 void
 399 symbols_new (void)
 400 {
 401   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 402                                   NULL,
 403                                   (Hash_hasher) hash_symbol,
 404                                   (Hash_comparator) hash_compare_symbol,
 405                                   (Hash_data_freer) symbol_free);
 406 }
 407
 408
 409 /*----------------------------------------------------------------.
 410 | Find the symbol named KEY, and return it.  If it does not exist |
 411 | yet, create it.                                                 |
 412 `----------------------------------------------------------------*/
 413
 414 symbol_t *
 415 symbol_get (const char *key, location_t location)
 416 {
 417   symbol_t probe;
 418   symbol_t *entry;
 419
 420   /* Keep the symbol in a printable form.  */
 421   key = struniq_new (quotearg_style (escape_quoting_style, key));
 422   *(char const **) &probe.tag = key;
 423   entry = hash_lookup (symbol_table, &probe);
 424
 425   if (!entry)
 426     {
 427       /* First insertion in the hash. */
 428       entry = symbol_new (key, location);
 429       hash_insert (symbol_table, entry);
 430     }
 431   return entry;
 432 }
 433
 434
 435 /*------------------------------------------------------------------.
 436 | Generate a dummy nonterminal, whose name cannot conflict with the |
 437 | user's names.                                                     |
 438 `------------------------------------------------------------------*/
 439
 440 symbol_t *
 441 dummy_symbol_get (location_t location)
 442 {
 443   /* Incremented for each generated symbol.  */
 444   static int dummy_count = 0;
 445   static char buf[256];
 446
 447   symbol_t *sym;
 448
 449   sprintf (buf, "@%d", ++dummy_count);
 450   sym = symbol_get (buf, location);
 451   sym->class = nterm_sym;
 452   sym->number = nvars++;
 453   return sym;
 454 }
 455
 456
 457 /*-------------------.
 458 | Free the symbols.  |
 459 `-------------------*/
 460
 461 void
 462 symbols_free (void)
 463 {
 464   hash_free (symbol_table);
 465   free (symbols);
 466 }
 467
 468
 469 /*---------------------------------------------------------------.
 470 | Look for undefined symbols, report an error, and consider them |
 471 | terminals.                                                     |
 472 `---------------------------------------------------------------*/
 473
 474 void
 475 symbols_do (symbol_processor processor, void *processor_data)
 476 {
 477   hash_do_for_each (symbol_table,
 478                     (Hash_processor) processor,
 479                     processor_data);
 480 }
 481
 482
 483 /*--------------------------------------------------------------.
 484 | Check that all the symbols are defined.  Report any undefined |
 485 | symbols and consider them nonterminals.                       |
 486 `--------------------------------------------------------------*/
 487
 488 void
 489 symbols_check_defined (void)
 490 {
 491   symbols_do (symbol_check_defined, NULL);
 492 }
 493
 494 /*------------------------------------------------------------------.
 495 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 496 | number.                                                           |
 497 `------------------------------------------------------------------*/
 498
 499 static void
 500 symbols_token_translations_init (void)
 501 {
 502   bool num_256_available_p = true;
 503   int i;
 504
 505   /* Find the highest user token number, and whether 256, the POSIX
 506      preferred user token number for the error token, is used.  */
 507   max_user_token_number = 0;
 508   for (i = 0; i < ntokens; ++i)
 509     {
 510       symbol_t *this = symbols[i];
 511       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 512         {
 513           if (this->user_token_number > max_user_token_number)
 514             max_user_token_number = this->user_token_number;
 515           if (this->user_token_number == 256)
 516             num_256_available_p = false;
 517         }
 518     }
 519
 520   /* If 256 is not used, assign it to error, to follow POSIX.  */
 521   if (num_256_available_p
 522       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 523     errtoken->user_token_number = 256;
 524
 525   /* Set the missing user numbers. */
 526   if (max_user_token_number < 256)
 527     max_user_token_number = 256;
 528
 529   for (i = 0; i < ntokens; ++i)
 530     {
 531       symbol_t *this = symbols[i];
 532       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 533         this->user_token_number = ++max_user_token_number;
 534       if (this->user_token_number > max_user_token_number)
 535         max_user_token_number = this->user_token_number;
 536     }
 537
 538   token_translations = XCALLOC (symbol_number_t, max_user_token_number + 1);
 539
 540   /* Initialize all entries for literal tokens to 2, the internal
 541      token number for $undefined, which represents all invalid inputs.
 542      */
 543   for (i = 0; i < max_user_token_number + 1; i++)
 544     token_translations[i] = undeftoken->number;
 545   symbols_do (symbol_translation, NULL);
 546 }
 547
 548
 549 /*----------------------------------------------------------------.
 550 | Assign symbol numbers, and write definition of token names into |
 551 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 552 `----------------------------------------------------------------*/
 553
 554 void
 555 symbols_pack (void)
 556 {
 557   symbols = XCALLOC (symbol_t *, nsyms);
 558
 559   symbols_do (symbol_check_alias_consistence, NULL);
 560   symbols_do (symbol_pack, NULL);
 561
 562   symbols_token_translations_init ();
 563
 564   if (startsymbol->class == unknown_sym)
 565     fatal_at (startsymbol_location,
 566               _("the start symbol %s is undefined"),
 567               startsymbol->tag);
 568   else if (startsymbol->class == token_sym)
 569     fatal_at (startsymbol_location,
 570               _("the start symbol %s is a token"),
 571               startsymbol->tag);
 572 }