src/symtab.c

   1 /* Symbol table manager for Bison.
   2
   3    Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004, 2005 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., 51 Franklin Street, Fifth Floor,
  21    Boston, MA 02110-1301, 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 = xmalloc (sizeof *res);
  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   if (nsyms == SYMBOL_NUMBER_MAXIMUM)
  70     fatal (_("too many symbols in input grammar (limit is %d)"),
  71            SYMBOL_NUMBER_MAXIMUM);
  72   nsyms++;
  73   return res;
  74 }
  75
  76
  77 /*-----------------.
  78 | Print a symbol.  |
  79 `-----------------*/
  80
  81 #define SYMBOL_ATTR_PRINT(Attr)                         \
  82   if (s->Attr)                                          \
  83     fprintf (f, " %s { %s }", #Attr, s->Attr)
  84
  85 void
  86 symbol_print (symbol *s, FILE *f)
  87 {
  88   fprintf (f, "\"%s\"", s->tag);
  89   SYMBOL_ATTR_PRINT (type_name);
  90   SYMBOL_ATTR_PRINT (destructor);
  91   SYMBOL_ATTR_PRINT (printer);
  92 }
  93
  94 #undef SYMBOL_ATTR_PRINT
  95
  96 /*------------------------------------------------------------------.
  97 | Complain that S's WHAT is redeclared at SECOND, and was first set |
  98 | at FIRST.                                                         |
  99 `------------------------------------------------------------------*/
 100
 101 static void
 102 redeclaration (symbol* s, const char *what, location first, location second)
 103 {
 104   complain_at (second, _("%s redeclaration for %s"), what, s->tag);
 105   complain_at (first, _("first declaration"));
 106 }
 107
 108
 109 /*-----------------------------------------------------------------.
 110 | Set the TYPE_NAME associated with SYM.  Does nothing if passed 0 |
 111 | as TYPE_NAME.                                                    |
 112 `-----------------------------------------------------------------*/
 113
 114 void
 115 symbol_type_set (symbol *sym, uniqstr type_name, location loc)
 116 {
 117   if (type_name)
 118     {
 119       if (sym->type_name)
 120         redeclaration (sym, "%type", sym->type_location, loc);
 121       uniqstr_assert (type_name);
 122       sym->type_name = type_name;
 123       sym->type_location = loc;
 124     }
 125 }
 126
 127
 128 /*------------------------------------------------------------------.
 129 | Set the DESTRUCTOR associated with SYM.  Do nothing if passed 0.  |
 130 `------------------------------------------------------------------*/
 131
 132 void
 133 symbol_destructor_set (symbol *sym, const char *destructor, location loc)
 134 {
 135   if (destructor)
 136     {
 137       if (sym->destructor)
 138         redeclaration (sym, "%destructor", sym->destructor_location, loc);
 139       sym->destructor = destructor;
 140       sym->destructor_location = loc;
 141     }
 142 }
 143
 144
 145 /*---------------------------------------------------------------.
 146 | Set the PRINTER associated with SYM.  Do nothing if passed 0.  |
 147 `---------------------------------------------------------------*/
 148
 149 void
 150 symbol_printer_set (symbol *sym, const char *printer, location loc)
 151 {
 152   if (printer)
 153     {
 154       if (sym->printer)
 155         redeclaration (sym, "%printer", sym->destructor_location, loc);
 156       sym->printer = printer;
 157       sym->printer_location = loc;
 158     }
 159 }
 160
 161
 162 /*-----------------------------------------------------------------.
 163 | Set the PRECEDENCE associated with SYM.  Does nothing if invoked |
 164 | with UNDEF_ASSOC as ASSOC.                                       |
 165 `-----------------------------------------------------------------*/
 166
 167 void
 168 symbol_precedence_set (symbol *sym, int prec, assoc a, location loc)
 169 {
 170   if (a != undef_assoc)
 171     {
 172       if (sym->prec != 0)
 173         redeclaration (sym, assoc_to_string (a), sym->prec_location, loc);
 174       sym->prec = prec;
 175       sym->assoc = a;
 176       sym->prec_location = loc;
 177     }
 178
 179   /* Only terminals have a precedence. */
 180   symbol_class_set (sym, token_sym, loc);
 181 }
 182
 183
 184 /*------------------------------------.
 185 | Set the CLASS associated with SYM.  |
 186 `------------------------------------*/
 187
 188 void
 189 symbol_class_set (symbol *sym, symbol_class class, location loc)
 190 {
 191   if (sym->class != unknown_sym && sym->class != class)
 192     complain_at (loc, _("symbol %s redefined"), sym->tag);
 193
 194   if (class == nterm_sym && sym->class != nterm_sym)
 195     sym->number = nvars++;
 196   else if (class == token_sym && sym->number == NUMBER_UNDEFINED)
 197     sym->number = ntokens++;
 198
 199   sym->class = class;
 200 }
 201
 202
 203 /*------------------------------------------------.
 204 | Set the USER_TOKEN_NUMBER associated with SYM.  |
 205 `------------------------------------------------*/
 206
 207 void
 208 symbol_user_token_number_set (symbol *sym, int user_token_number, location loc)
 209 {
 210   if (sym->class != token_sym)
 211     abort ();
 212
 213   if (sym->user_token_number != USER_NUMBER_UNDEFINED
 214       && sym->user_token_number != user_token_number)
 215     complain_at (loc, _("redefining user token number of %s"), sym->tag);
 216
 217   sym->user_token_number = user_token_number;
 218   /* User defined $end token? */
 219   if (user_token_number == 0)
 220     {
 221       endtoken = sym;
 222       endtoken->number = 0;
 223       /* It is always mapped to 0, so it was already counted in
 224          NTOKENS.  */
 225       --ntokens;
 226     }
 227 }
 228
 229
 230 /*----------------------------------------------------------.
 231 | If SYM is not defined, report an error, and consider it a |
 232 | nonterminal.                                              |
 233 `----------------------------------------------------------*/
 234
 235 static inline bool
 236 symbol_check_defined (symbol *sym)
 237 {
 238   if (sym->class == unknown_sym)
 239     {
 240       complain_at
 241         (sym->location,
 242          _("symbol %s is used, but is not defined as a token and has no rules"),
 243          sym->tag);
 244       sym->class = nterm_sym;
 245       sym->number = nvars++;
 246     }
 247
 248   return true;
 249 }
 250
 251 static bool
 252 symbol_check_defined_processor (void *sym, void *null ATTRIBUTE_UNUSED)
 253 {
 254   return symbol_check_defined (sym);
 255 }
 256
 257
 258 /*------------------------------------------------------------------.
 259 | Declare the new symbol SYM.  Make it an alias of SYMVAL, and type |
 260 | SYMVAL with SYM's type.                                           |
 261 `------------------------------------------------------------------*/
 262
 263 void
 264 symbol_make_alias (symbol *sym, symbol *symval, location loc)
 265 {
 266   if (symval->alias)
 267     warn_at (loc, _("symbol `%s' used more than once as a literal string"),
 268              symval->tag);
 269   else if (sym->alias)
 270     warn_at (loc, _("symbol `%s' given more than one literal string"),
 271              sym->tag);
 272   else
 273     {
 274       symval->class = token_sym;
 275       symval->user_token_number = sym->user_token_number;
 276       sym->user_token_number = USER_NUMBER_ALIAS;
 277       symval->alias = sym;
 278       sym->alias = symval;
 279       /* sym and symval combined are only one symbol.  */
 280       nsyms--;
 281       ntokens--;
 282       if (ntokens != sym->number && ntokens != symval->number)
 283         abort ();
 284       sym->number = symval->number =
 285         (symval->number < sym->number) ? symval->number : sym->number;
 286       symbol_type_set (symval, sym->type_name, loc);
 287     }
 288 }
 289
 290
 291 /*---------------------------------------------------------.
 292 | Check that THIS, and its alias, have same precedence and |
 293 | associativity.                                           |
 294 `---------------------------------------------------------*/
 295
 296 static inline void
 297 symbol_check_alias_consistency (symbol *this)
 298 {
 299   symbol *alias = this;
 300   symbol *orig  = this->alias;
 301
 302   /* Check only those that _are_ the aliases.  */
 303   if (!(this->alias && this->user_token_number == USER_NUMBER_ALIAS))
 304     return;
 305
 306   if (orig->type_name != alias->type_name)
 307     {
 308       if (orig->type_name)
 309         symbol_type_set (alias, orig->type_name, orig->type_location);
 310       else
 311         symbol_type_set (orig, alias->type_name, alias->type_location);
 312     }
 313
 314
 315   if (orig->destructor || alias->destructor)
 316     {
 317       if (orig->destructor)
 318         symbol_destructor_set (alias, orig->destructor,
 319                                orig->destructor_location);
 320       else
 321         symbol_destructor_set (orig, alias->destructor,
 322                                alias->destructor_location);
 323     }
 324
 325   if (orig->printer || alias->printer)
 326     {
 327       if (orig->printer)
 328         symbol_printer_set (alias, orig->printer, orig->printer_location);
 329       else
 330         symbol_printer_set (orig, alias->printer, alias->printer_location);
 331     }
 332
 333   if (alias->prec || orig->prec)
 334     {
 335       if (orig->prec)
 336         symbol_precedence_set (alias, orig->prec, orig->assoc,
 337                                orig->prec_location);
 338       else
 339         symbol_precedence_set (orig, alias->prec, alias->assoc,
 340                                alias->prec_location);
 341     }
 342 }
 343
 344 static bool
 345 symbol_check_alias_consistency_processor (void *this,
 346                                           void *null ATTRIBUTE_UNUSED)
 347 {
 348   symbol_check_alias_consistency (this);
 349   return true;
 350 }
 351
 352
 353 /*-------------------------------------------------------------------.
 354 | Assign a symbol number, and write the definition of the token name |
 355 | into FDEFINES.  Put in SYMBOLS.                                    |
 356 `-------------------------------------------------------------------*/
 357
 358 static inline bool
 359 symbol_pack (symbol *this)
 360 {
 361   if (this->class == nterm_sym)
 362     {
 363       this->number += ntokens;
 364     }
 365   else if (this->alias)
 366     {
 367       /* This symbol and its alias are a single token defn.
 368          Allocate a tokno, and assign to both check agreement of
 369          prec and assoc fields and make both the same */
 370       if (this->number == NUMBER_UNDEFINED)
 371         {
 372           if (this == endtoken || this->alias == endtoken)
 373             this->number = this->alias->number = 0;
 374           else
 375             {
 376               if (this->alias->number == NUMBER_UNDEFINED)
 377                 abort ();
 378               this->number = this->alias->number;
 379             }
 380         }
 381       /* Do not do processing below for USER_NUMBER_ALIASes.  */
 382       if (this->user_token_number == USER_NUMBER_ALIAS)
 383         return true;
 384     }
 385   else /* this->class == token_sym */
 386     {
 387       if (this->number == NUMBER_UNDEFINED)
 388         abort ();
 389     }
 390
 391   symbols[this->number] = this;
 392   return true;
 393 }
 394
 395 static bool
 396 symbol_pack_processor (void *this, void *null ATTRIBUTE_UNUSED)
 397 {
 398   return symbol_pack (this);
 399 }
 400
 401
 402
 403
 404 /*--------------------------------------------------.
 405 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 406 `--------------------------------------------------*/
 407
 408 static inline bool
 409 symbol_translation (symbol *this)
 410 {
 411   /* Non-terminal? */
 412   if (this->class == token_sym
 413       && this->user_token_number != USER_NUMBER_ALIAS)
 414     {
 415       /* A token which translation has already been set? */
 416       if (token_translations[this->user_token_number] != undeftoken->number)
 417         complain_at (this->location,
 418                      _("tokens %s and %s both assigned number %d"),
 419                      symbols[token_translations[this->user_token_number]]->tag,
 420                      this->tag, this->user_token_number);
 421
 422       token_translations[this->user_token_number] = this->number;
 423     }
 424
 425   return true;
 426 }
 427
 428 static bool
 429 symbol_translation_processor (void *this, void *null ATTRIBUTE_UNUSED)
 430 {
 431   return symbol_translation (this);
 432 }
 433
 434
 435 /*----------------------.
 436 | A symbol hash table.  |
 437 `----------------------*/
 438
 439 /* Initial capacity of symbols hash table.  */
 440 #define HT_INITIAL_CAPACITY 257
 441
 442 static struct hash_table *symbol_table = NULL;
 443
 444 static inline bool
 445 hash_compare_symbol (const symbol *m1, const symbol *m2)
 446 {
 447   /* Since tags are unique, we can compare the pointers themselves.  */
 448   return UNIQSTR_EQ (m1->tag, m2->tag);
 449 }
 450
 451 static bool
 452 hash_symbol_comparator (void const *m1, void const *m2)
 453 {
 454   return hash_compare_symbol (m1, m2);
 455 }
 456
 457 static inline size_t
 458 hash_symbol (const symbol *m, size_t tablesize)
 459 {
 460   /* Since tags are unique, we can hash the pointer itself.  */
 461   return ((uintptr_t) m->tag) % tablesize;
 462 }
 463
 464 static size_t
 465 hash_symbol_hasher (void const *m, size_t tablesize)
 466 {
 467   return hash_symbol (m, tablesize);
 468 }
 469
 470
 471 /*-------------------------------.
 472 | Create the symbol hash table.  |
 473 `-------------------------------*/
 474
 475 void
 476 symbols_new (void)
 477 {
 478   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 479                                   NULL,
 480                                   hash_symbol_hasher,
 481                                   hash_symbol_comparator,
 482                                   free);
 483 }
 484
 485
 486 /*----------------------------------------------------------------.
 487 | Find the symbol named KEY, and return it.  If it does not exist |
 488 | yet, create it.                                                 |
 489 `----------------------------------------------------------------*/
 490
 491 symbol *
 492 symbol_get (const char *key, location loc)
 493 {
 494   symbol probe;
 495   symbol *entry;
 496
 497   key = uniqstr_new (key);
 498   probe.tag = key;
 499   entry = hash_lookup (symbol_table, &probe);
 500
 501   if (!entry)
 502     {
 503       /* First insertion in the hash. */
 504       entry = symbol_new (key, loc);
 505       hash_insert (symbol_table, entry);
 506     }
 507   return entry;
 508 }
 509
 510
 511 /*------------------------------------------------------------------.
 512 | Generate a dummy nonterminal, whose name cannot conflict with the |
 513 | user's names.                                                     |
 514 `------------------------------------------------------------------*/
 515
 516 symbol *
 517 dummy_symbol_get (location loc)
 518 {
 519   /* Incremented for each generated symbol.  */
 520   static int dummy_count = 0;
 521   static char buf[256];
 522
 523   symbol *sym;
 524
 525   sprintf (buf, "@%d", ++dummy_count);
 526   sym = symbol_get (buf, loc);
 527   sym->class = nterm_sym;
 528   sym->number = nvars++;
 529   return sym;
 530 }
 531
 532
 533 /*-------------------.
 534 | Free the symbols.  |
 535 `-------------------*/
 536
 537 void
 538 symbols_free (void)
 539 {
 540   hash_free (symbol_table);
 541   free (symbols);
 542 }
 543
 544
 545 /*---------------------------------------------------------------.
 546 | Look for undefined symbols, report an error, and consider them |
 547 | terminals.                                                     |
 548 `---------------------------------------------------------------*/
 549
 550 static void
 551 symbols_do (Hash_processor processor, void *processor_data)
 552 {
 553   hash_do_for_each (symbol_table, processor, processor_data);
 554 }
 555
 556
 557 /*--------------------------------------------------------------.
 558 | Check that all the symbols are defined.  Report any undefined |
 559 | symbols and consider them nonterminals.                       |
 560 `--------------------------------------------------------------*/
 561
 562 void
 563 symbols_check_defined (void)
 564 {
 565   symbols_do (symbol_check_defined_processor, NULL);
 566 }
 567
 568 /*------------------------------------------------------------------.
 569 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 570 | number.                                                           |
 571 `------------------------------------------------------------------*/
 572
 573 static void
 574 symbols_token_translations_init (void)
 575 {
 576   bool num_256_available_p = true;
 577   int i;
 578
 579   /* Find the highest user token number, and whether 256, the POSIX
 580      preferred user token number for the error token, is used.  */
 581   max_user_token_number = 0;
 582   for (i = 0; i < ntokens; ++i)
 583     {
 584       symbol *this = symbols[i];
 585       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 586         {
 587           if (this->user_token_number > max_user_token_number)
 588             max_user_token_number = this->user_token_number;
 589           if (this->user_token_number == 256)
 590             num_256_available_p = false;
 591         }
 592     }
 593
 594   /* If 256 is not used, assign it to error, to follow POSIX.  */
 595   if (num_256_available_p
 596       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 597     errtoken->user_token_number = 256;
 598
 599   /* Set the missing user numbers. */
 600   if (max_user_token_number < 256)
 601     max_user_token_number = 256;
 602
 603   for (i = 0; i < ntokens; ++i)
 604     {
 605       symbol *this = symbols[i];
 606       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 607         this->user_token_number = ++max_user_token_number;
 608       if (this->user_token_number > max_user_token_number)
 609         max_user_token_number = this->user_token_number;
 610     }
 611
 612   token_translations = xnmalloc (max_user_token_number + 1,
 613                                  sizeof *token_translations);
 614
 615   /* Initialize all entries for literal tokens to 2, the internal
 616      token number for $undefined, which represents all invalid inputs.
 617      */
 618   for (i = 0; i < max_user_token_number + 1; i++)
 619     token_translations[i] = undeftoken->number;
 620   symbols_do (symbol_translation_processor, NULL);
 621 }
 622
 623
 624 /*----------------------------------------------------------------.
 625 | Assign symbol numbers, and write definition of token names into |
 626 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 627 `----------------------------------------------------------------*/
 628
 629 void
 630 symbols_pack (void)
 631 {
 632   symbols = xcalloc (nsyms, sizeof *symbols);
 633
 634   symbols_do (symbol_check_alias_consistency_processor, NULL);
 635   symbols_do (symbol_pack_processor, NULL);
 636
 637   symbols_token_translations_init ();
 638
 639   if (startsymbol->class == unknown_sym)
 640     fatal_at (startsymbol_location,
 641               _("the start symbol %s is undefined"),
 642               startsymbol->tag);
 643   else if (startsymbol->class == token_sym)
 644     fatal_at (startsymbol_location,
 645               _("the start symbol %s is a token"),
 646               startsymbol->tag);
 647 }