src/symtab.c

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