src/symtab.c

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