src/symtab.c

   1 /* Symbol table manager for Bison.
   2
   3    Copyright (C) 1984, 1989, 2000-2002, 2004-2012 Free Software
   4    Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program 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 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include <hash.h>
  25
  26 #include "complain.h"
  27 #include "gram.h"
  28 #include "symtab.h"
  29
  30 /*-------------------------------------------------------------------.
  31 | Symbols sorted by tag.  Allocated by the first invocation of       |
  32 | symbols_do, after which no more symbols should be created.         |
  33 `-------------------------------------------------------------------*/
  34
  35 static symbol **symbols_sorted = NULL;
  36 static symbol **semantic_types_sorted = NULL;
  37
  38 /*------------------------.
  39 | Distinguished symbols.  |
  40 `------------------------*/
  41
  42 symbol *errtoken = NULL;
  43 symbol *undeftoken = NULL;
  44 symbol *endtoken = NULL;
  45 symbol *accept = NULL;
  46 symbol *startsymbol = NULL;
  47 location startsymbol_location;
  48
  49 /*---------------------------------------.
  50 | Default %destructor's and %printer's.  |
  51 `---------------------------------------*/
  52
  53 static code_props default_tagged_code_props[CODE_PROPS_SIZE] =
  54   {
  55     CODE_PROPS_NONE_INIT,
  56     CODE_PROPS_NONE_INIT,
  57   };
  58 static code_props default_tagless_code_props[CODE_PROPS_SIZE] =
  59   {
  60     CODE_PROPS_NONE_INIT,
  61     CODE_PROPS_NONE_INIT,
  62   };
  63
  64 /*---------------------------------.
  65 | Create a new symbol, named TAG.  |
  66 `---------------------------------*/
  67
  68 static symbol *
  69 symbol_new (uniqstr tag, location loc)
  70 {
  71   symbol *res = xmalloc (sizeof *res);
  72
  73   uniqstr_assert (tag);
  74
  75   /* If the tag is not a string (starts with a double quote), check
  76      that it is valid for Yacc. */
  77   if (tag[0] != '\"' && tag[0] != '\'' && strchr (tag, '-'))
  78     yacc_at (loc, _("POSIX Yacc forbids dashes in symbol names: %s"),
  79              tag);
  80
  81   res->tag = tag;
  82   res->location = loc;
  83
  84   res->type_name = NULL;
  85   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
  86     code_props_none_init (&res->props[i]);
  87
  88   res->number = NUMBER_UNDEFINED;
  89   res->prec = 0;
  90   res->assoc = undef_assoc;
  91   res->user_token_number = USER_NUMBER_UNDEFINED;
  92
  93   res->alias = NULL;
  94   res->class = unknown_sym;
  95   res->status = undeclared;
  96
  97   if (nsyms == SYMBOL_NUMBER_MAXIMUM)
  98     fatal (_("too many symbols in input grammar (limit is %d)"),
  99            SYMBOL_NUMBER_MAXIMUM);
 100   nsyms++;
 101   return res;
 102 }
 103
 104 char const *
 105 code_props_type_string (code_props_type kind)
 106 {
 107   switch (kind)
 108     {
 109     case destructor:
 110       return "%destructor";
 111     case printer:
 112       return "%printer";
 113     }
 114   assert (0);
 115 }
 116
 117 /*----------------------------------------.
 118 | Create a new semantic type, named TAG.  |
 119 `----------------------------------------*/
 120
 121 static semantic_type *
 122 semantic_type_new (uniqstr tag, const location *loc)
 123 {
 124   semantic_type *res = xmalloc (sizeof *res);
 125
 126   uniqstr_assert (tag);
 127   res->tag = tag;
 128   if (loc)
 129     res->location = *loc;
 130   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
 131     code_props_none_init (&res->props[i]);
 132
 133   return res;
 134 }
 135
 136
 137 /*-----------------.
 138 | Print a symbol.  |
 139 `-----------------*/
 140
 141 #define SYMBOL_ATTR_PRINT(Attr)                         \
 142   if (s->Attr)                                          \
 143     fprintf (f, " %s { %s }", #Attr, s->Attr)
 144
 145 #define SYMBOL_CODE_PRINT(Attr)                                         \
 146   if (s->props[Attr].code)                                              \
 147     fprintf (f, " %s { %s }", #Attr, s->props[Attr].code)
 148
 149 void
 150 symbol_print (symbol *s, FILE *f)
 151 {
 152   if (s)
 153     {
 154       fprintf (f, "\"%s\"", s->tag);
 155       SYMBOL_ATTR_PRINT (type_name);
 156       SYMBOL_CODE_PRINT (destructor);
 157       SYMBOL_CODE_PRINT (printer);
 158     }
 159   else
 160     fprintf (f, "<NULL>");
 161 }
 162
 163 #undef SYMBOL_ATTR_PRINT
 164 #undef SYMBOL_CODE_PRINT
 165
 166
 167 /*----------------------------------.
 168 | Whether S is a valid identifier.  |
 169 `----------------------------------*/
 170
 171 static bool
 172 is_identifier (uniqstr s)
 173 {
 174   static char const alphanum[26 + 26 + 1 + 10] =
 175     "abcdefghijklmnopqrstuvwxyz"
 176     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 177     "_"
 178     "0123456789";
 179   if (!s || ! memchr (alphanum, *s, sizeof alphanum - 10))
 180     return false;
 181   for (++s; *s; ++s)
 182     if (! memchr (alphanum, *s, sizeof alphanum))
 183       return false;
 184   return true;
 185 }
 186
 187
 188 /*-----------------------------------------------.
 189 | Get the identifier associated to this symbol.  |
 190 `-----------------------------------------------*/
 191 uniqstr
 192 symbol_id_get (symbol const *sym)
 193 {
 194   aver (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS);
 195   if (sym->alias)
 196     sym = sym->alias;
 197   return is_identifier (sym->tag) ? sym->tag : 0;
 198 }
 199
 200
 201 /*------------------------------------------------------------------.
 202 | Complain that S's WHAT is redeclared at SECOND, and was first set |
 203 | at FIRST.                                                         |
 204 `------------------------------------------------------------------*/
 205
 206 static void
 207 symbol_redeclaration (symbol *s, const char *what, location first,
 208                       location second)
 209 {
 210   complain_at (second, _("%s redeclaration for %s"), what, s->tag);
 211   complain_at (first, _("previous declaration"));
 212 }
 213
 214 static void
 215 semantic_type_redeclaration (semantic_type *s, const char *what, location first,
 216                              location second)
 217 {
 218   complain_at (second, _("%s redeclaration for <%s>"), what, s->tag);
 219   complain_at (first, _("previous declaration"));
 220 }
 221
 222
 223
 224 /*-----------------------------------------------------------------.
 225 | Set the TYPE_NAME associated with SYM.  Does nothing if passed 0 |
 226 | as TYPE_NAME.                                                    |
 227 `-----------------------------------------------------------------*/
 228
 229 void
 230 symbol_type_set (symbol *sym, uniqstr type_name, location loc)
 231 {
 232   if (type_name)
 233     {
 234       if (sym->type_name)
 235         symbol_redeclaration (sym, "%type", sym->type_location, loc);
 236       uniqstr_assert (type_name);
 237       sym->type_name = type_name;
 238       sym->type_location = loc;
 239     }
 240 }
 241
 242 /*--------------------------------------------------------.
 243 | Set the DESTRUCTOR or PRINTER associated with the SYM.  |
 244 `--------------------------------------------------------*/
 245
 246 void
 247 symbol_code_props_set (symbol *sym, code_props_type kind,
 248                        code_props const *code)
 249 {
 250   if (sym->props[kind].code)
 251     symbol_redeclaration (sym, code_props_type_string (kind),
 252                           sym->props[kind].location,
 253                           code->location);
 254   sym->props[kind] = *code;
 255 }
 256
 257 /*-----------------------------------------------------.
 258 | Set the DESTRUCTOR or PRINTER associated with TYPE.  |
 259 `-----------------------------------------------------*/
 260
 261 void
 262 semantic_type_code_props_set (semantic_type *type,
 263                               code_props_type kind,
 264                               code_props const *code)
 265 {
 266   if (type->props[kind].code)
 267     semantic_type_redeclaration (type, code_props_type_string (kind),
 268                                  type->props[kind].location,
 269                                  code->location);
 270   type->props[kind] = *code;
 271 }
 272
 273 /*---------------------------------------------------.
 274 | Get the computed %destructor or %printer for SYM.  |
 275 `---------------------------------------------------*/
 276
 277 code_props const *
 278 symbol_code_props_get (symbol const *sym,
 279                        code_props_type kind)
 280 {
 281   /* Per-symbol code props.  */
 282   if (sym->props[kind].code)
 283     return &sym->props[kind];
 284
 285   /* Per-type code props.  */
 286   if (sym->type_name)
 287     {
 288       code_props const *code =
 289         &semantic_type_get (sym->type_name, NULL)->props[kind];
 290       if (code->code)
 291         return code;
 292     }
 293
 294   /* Apply default code props's only to user-defined symbols.  */
 295   if (sym->tag[0] == '$' || sym == errtoken)
 296     return &code_props_none;
 297
 298   if (sym->type_name)
 299     return &default_tagged_code_props[kind];
 300   return &default_tagless_code_props[kind];
 301 }
 302
 303 /*-----------------------------------------------------------------.
 304 | Set the PRECEDENCE associated with SYM.  Does nothing if invoked |
 305 | with UNDEF_ASSOC as ASSOC.                                       |
 306 `-----------------------------------------------------------------*/
 307
 308 void
 309 symbol_precedence_set (symbol *sym, int prec, assoc a, location loc)
 310 {
 311   if (a != undef_assoc)
 312     {
 313       if (sym->prec != 0)
 314         symbol_redeclaration (sym, assoc_to_string (a), sym->prec_location,
 315                               loc);
 316       sym->prec = prec;
 317       sym->assoc = a;
 318       sym->prec_location = loc;
 319     }
 320
 321   /* Only terminals have a precedence. */
 322   symbol_class_set (sym, token_sym, loc, false);
 323 }
 324
 325
 326 /*------------------------------------.
 327 | Set the CLASS associated with SYM.  |
 328 `------------------------------------*/
 329
 330 void
 331 symbol_class_set (symbol *sym, symbol_class class, location loc, bool declaring)
 332 {
 333   bool warned = false;
 334   if (sym->class != unknown_sym && sym->class != class)
 335     {
 336       complain_at (loc, _("symbol %s redefined"), sym->tag);
 337       // Don't report both "redefined" and "redeclared".
 338       warned = true;
 339     }
 340
 341   if (class == nterm_sym && sym->class != nterm_sym)
 342     sym->number = nvars++;
 343   else if (class == token_sym && sym->number == NUMBER_UNDEFINED)
 344     sym->number = ntokens++;
 345
 346   sym->class = class;
 347
 348   if (declaring)
 349     {
 350       if (sym->status == declared && !warned)
 351         warn_at (loc, _("symbol %s redeclared"), sym->tag);
 352       sym->status = declared;
 353     }
 354 }
 355
 356
 357 /*------------------------------------------------.
 358 | Set the USER_TOKEN_NUMBER associated with SYM.  |
 359 `------------------------------------------------*/
 360
 361 void
 362 symbol_user_token_number_set (symbol *sym, int user_token_number, location loc)
 363 {
 364   int *user_token_numberp;
 365
 366   if (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
 367     user_token_numberp = &sym->user_token_number;
 368   else
 369     user_token_numberp = &sym->alias->user_token_number;
 370   if (*user_token_numberp != USER_NUMBER_UNDEFINED
 371       && *user_token_numberp != user_token_number)
 372     complain_at (loc, _("redefining user token number of %s"), sym->tag);
 373
 374   *user_token_numberp = user_token_number;
 375   /* User defined $end token? */
 376   if (user_token_number == 0)
 377     {
 378       endtoken = sym;
 379       /* It is always mapped to 0, so it was already counted in
 380          NTOKENS.  */
 381       if (endtoken->number != NUMBER_UNDEFINED)
 382         --ntokens;
 383       endtoken->number = 0;
 384     }
 385 }
 386
 387
 388 /*----------------------------------------------------------.
 389 | If SYM is not defined, report an error, and consider it a |
 390 | nonterminal.                                              |
 391 `----------------------------------------------------------*/
 392
 393 static inline bool
 394 symbol_check_defined (symbol *sym)
 395 {
 396   if (sym->class == unknown_sym)
 397     {
 398       switch (sym->status)
 399         {
 400         case used:
 401           warn_at (sym->location,
 402                    _("symbol %s is used, but is not defined as a token"
 403                      " and has no rules"),
 404                    sym->tag);
 405           break;
 406         case undeclared:
 407         case needed:
 408           complain_at (sym->location,
 409                        _("symbol %s is used, but is not defined as a token"
 410                          " and has no rules"),
 411                        sym->tag);
 412           break;
 413         case declared:
 414           /* If declared, then sym->class != unknown_sym. */
 415           assert (0);
 416         }
 417
 418       sym->class = nterm_sym;
 419       sym->number = nvars++;
 420     }
 421
 422   /* Set the semantic type status associated to the current symbol to
 423      'declared' so that we could check semantic types unnecessary uses. */
 424   if (sym->type_name)
 425     {
 426       semantic_type *sem_type = semantic_type_get (sym->type_name, NULL);
 427       if (sem_type)
 428         sem_type->status = declared;
 429     }
 430
 431   return true;
 432 }
 433
 434 static inline bool
 435 semantic_type_check_defined (semantic_type *sem_type)
 436 {
 437   if (sem_type->status != declared)
 438     warn_at (sem_type->location,
 439              _("type <%s> is used, but is not associated to any symbol"),
 440              sem_type->tag);
 441
 442   return true;
 443 }
 444
 445 static bool
 446 symbol_check_defined_processor (void *sym, void *null ATTRIBUTE_UNUSED)
 447 {
 448   return symbol_check_defined (sym);
 449 }
 450
 451 static bool
 452 semantic_type_check_defined_processor (void *sem_type,
 453                                        void *null ATTRIBUTE_UNUSED)
 454 {
 455   return semantic_type_check_defined (sem_type);
 456 }
 457
 458
 459 void
 460 symbol_make_alias (symbol *sym, symbol *str, location loc)
 461 {
 462   if (str->alias)
 463     warn_at (loc, _("symbol %s used more than once as a literal string"),
 464              str->tag);
 465   else if (sym->alias)
 466     warn_at (loc, _("symbol %s given more than one literal string"),
 467              sym->tag);
 468   else
 469     {
 470       str->class = token_sym;
 471       str->user_token_number = sym->user_token_number;
 472       sym->user_token_number = USER_NUMBER_HAS_STRING_ALIAS;
 473       str->alias = sym;
 474       sym->alias = str;
 475       str->number = sym->number;
 476       symbol_type_set (str, sym->type_name, loc);
 477     }
 478 }
 479
 480
 481 /*---------------------------------------------------------.
 482 | Check that THIS, and its alias, have same precedence and |
 483 | associativity.                                           |
 484 `---------------------------------------------------------*/
 485
 486 static inline void
 487 symbol_check_alias_consistency (symbol *this)
 488 {
 489   symbol *sym = this;
 490   symbol *str = this->alias;
 491
 492   /* Check only the symbol in the symbol-string pair.  */
 493   if (!(this->alias
 494         && this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS))
 495     return;
 496
 497   if (str->type_name != sym->type_name)
 498     {
 499       if (str->type_name)
 500         symbol_type_set (sym, str->type_name, str->type_location);
 501       else
 502         symbol_type_set (str, sym->type_name, sym->type_location);
 503     }
 504
 505
 506   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
 507     if (str->props[i].code)
 508       symbol_code_props_set (sym, i, &str->props[i]);
 509     else if (sym->props[i].code)
 510       symbol_code_props_set (str, i, &sym->props[i]);
 511
 512   if (sym->prec || str->prec)
 513     {
 514       if (str->prec)
 515         symbol_precedence_set (sym, str->prec, str->assoc,
 516                                str->prec_location);
 517       else
 518         symbol_precedence_set (str, sym->prec, sym->assoc,
 519                                sym->prec_location);
 520     }
 521 }
 522
 523 static bool
 524 symbol_check_alias_consistency_processor (void *this,
 525                                           void *null ATTRIBUTE_UNUSED)
 526 {
 527   symbol_check_alias_consistency (this);
 528   return true;
 529 }
 530
 531
 532 /*-------------------------------------------------------------------.
 533 | Assign a symbol number, and write the definition of the token name |
 534 | into FDEFINES.  Put in SYMBOLS.                                    |
 535 `-------------------------------------------------------------------*/
 536
 537 static inline bool
 538 symbol_pack (symbol *this)
 539 {
 540   aver (this->number != NUMBER_UNDEFINED);
 541   if (this->class == nterm_sym)
 542     this->number += ntokens;
 543   else if (this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS)
 544     return true;
 545
 546   symbols[this->number] = this;
 547   return true;
 548 }
 549
 550 static bool
 551 symbol_pack_processor (void *this, void *null ATTRIBUTE_UNUSED)
 552 {
 553   return symbol_pack (this);
 554 }
 555
 556
 557 static void
 558 user_token_number_redeclaration (int num, symbol *first, symbol *second)
 559 {
 560   /* User token numbers are not assigned during the parsing, but in a
 561      second step, via a traversal of the symbol table sorted on tag.
 562
 563      However, error messages make more sense if we keep the first
 564      declaration first.  */
 565   if (location_cmp (first->location, second->location) > 0)
 566     {
 567       symbol* tmp = first;
 568       first = second;
 569       second = tmp;
 570     }
 571   complain_at (second->location,
 572                _("user token number %d redeclaration for %s"),
 573                num, second->tag);
 574   complain_at (first->location, _("previous declaration for %s"),
 575                first->tag);
 576 }
 577
 578 /*--------------------------------------------------.
 579 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 580 `--------------------------------------------------*/
 581
 582 static inline bool
 583 symbol_translation (symbol *this)
 584 {
 585   /* Non-terminal? */
 586   if (this->class == token_sym
 587       && this->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
 588     {
 589       /* A token which translation has already been set? */
 590       if (token_translations[this->user_token_number] != undeftoken->number)
 591         user_token_number_redeclaration
 592           (this->user_token_number,
 593            symbols[token_translations[this->user_token_number]],
 594            this);
 595
 596       token_translations[this->user_token_number] = this->number;
 597     }
 598
 599   return true;
 600 }
 601
 602 static bool
 603 symbol_translation_processor (void *this, void *null ATTRIBUTE_UNUSED)
 604 {
 605   return symbol_translation (this);
 606 }
 607
 608
 609 /*---------------------------------------.
 610 | Symbol and semantic type hash tables.  |
 611 `---------------------------------------*/
 612
 613 /* Initial capacity of symbol and semantic type hash table.  */
 614 #define HT_INITIAL_CAPACITY 257
 615
 616 static struct hash_table *symbol_table = NULL;
 617 static struct hash_table *semantic_type_table = NULL;
 618
 619 static inline bool
 620 hash_compare_symbol (const symbol *m1, const symbol *m2)
 621 {
 622   /* Since tags are unique, we can compare the pointers themselves.  */
 623   return UNIQSTR_EQ (m1->tag, m2->tag);
 624 }
 625
 626 static inline bool
 627 hash_compare_semantic_type (const semantic_type *m1, const semantic_type *m2)
 628 {
 629   /* Since names are unique, we can compare the pointers themselves.  */
 630   return UNIQSTR_EQ (m1->tag, m2->tag);
 631 }
 632
 633 static bool
 634 hash_symbol_comparator (void const *m1, void const *m2)
 635 {
 636   return hash_compare_symbol (m1, m2);
 637 }
 638
 639 static bool
 640 hash_semantic_type_comparator (void const *m1, void const *m2)
 641 {
 642   return hash_compare_semantic_type (m1, m2);
 643 }
 644
 645 static inline size_t
 646 hash_symbol (const symbol *m, size_t tablesize)
 647 {
 648   /* Since tags are unique, we can hash the pointer itself.  */
 649   return ((uintptr_t) m->tag) % tablesize;
 650 }
 651
 652 static inline size_t
 653 hash_semantic_type (const semantic_type *m, size_t tablesize)
 654 {
 655   /* Since names are unique, we can hash the pointer itself.  */
 656   return ((uintptr_t) m->tag) % tablesize;
 657 }
 658
 659 static size_t
 660 hash_symbol_hasher (void const *m, size_t tablesize)
 661 {
 662   return hash_symbol (m, tablesize);
 663 }
 664
 665 static size_t
 666 hash_semantic_type_hasher (void const *m, size_t tablesize)
 667 {
 668   return hash_semantic_type (m, tablesize);
 669 }
 670
 671 /*-------------------------------.
 672 | Create the symbol hash table.  |
 673 `-------------------------------*/
 674
 675 void
 676 symbols_new (void)
 677 {
 678   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 679                                   NULL,
 680                                   hash_symbol_hasher,
 681                                   hash_symbol_comparator,
 682                                   free);
 683   semantic_type_table = hash_initialize (HT_INITIAL_CAPACITY,
 684                                          NULL,
 685                                          hash_semantic_type_hasher,
 686                                          hash_semantic_type_comparator,
 687                                          free);
 688 }
 689
 690
 691 /*----------------------------------------------------------------.
 692 | Find the symbol named KEY, and return it.  If it does not exist |
 693 | yet, create it.                                                 |
 694 `----------------------------------------------------------------*/
 695
 696 symbol *
 697 symbol_from_uniqstr (const uniqstr key, location loc)
 698 {
 699   symbol probe;
 700   symbol *entry;
 701
 702   probe.tag = key;
 703   entry = hash_lookup (symbol_table, &probe);
 704
 705   if (!entry)
 706     {
 707       /* First insertion in the hash. */
 708       aver (!symbols_sorted);
 709       entry = symbol_new (key, loc);
 710       if (!hash_insert (symbol_table, entry))
 711         xalloc_die ();
 712     }
 713   return entry;
 714 }
 715
 716
 717 /*-----------------------------------------------------------------------.
 718 | Find the semantic type named KEY, and return it.  If it does not exist |
 719 | yet, create it.                                                        |
 720 `-----------------------------------------------------------------------*/
 721
 722 semantic_type *
 723 semantic_type_from_uniqstr (const uniqstr key, const location *loc)
 724 {
 725   semantic_type probe;
 726   semantic_type *entry;
 727
 728   probe.tag = key;
 729   entry = hash_lookup (semantic_type_table, &probe);
 730
 731   if (!entry)
 732     {
 733       /* First insertion in the hash. */
 734       entry = semantic_type_new (key, loc);
 735       if (!hash_insert (semantic_type_table, entry))
 736         xalloc_die ();
 737     }
 738   return entry;
 739 }
 740
 741
 742 /*----------------------------------------------------------------.
 743 | Find the symbol named KEY, and return it.  If it does not exist |
 744 | yet, create it.                                                 |
 745 `----------------------------------------------------------------*/
 746
 747 symbol *
 748 symbol_get (const char *key, location loc)
 749 {
 750   return symbol_from_uniqstr (uniqstr_new (key), loc);
 751 }
 752
 753
 754 /*-----------------------------------------------------------------------.
 755 | Find the semantic type named KEY, and return it.  If it does not exist |
 756 | yet, create it.                                                        |
 757 `-----------------------------------------------------------------------*/
 758
 759 semantic_type *
 760 semantic_type_get (const char *key, const location *loc)
 761 {
 762   return semantic_type_from_uniqstr (uniqstr_new (key), loc);
 763 }
 764
 765
 766 /*------------------------------------------------------------------.
 767 | Generate a dummy nonterminal, whose name cannot conflict with the |
 768 | user's names.                                                     |
 769 `------------------------------------------------------------------*/
 770
 771 symbol *
 772 dummy_symbol_get (location loc)
 773 {
 774   /* Incremented for each generated symbol.  */
 775   static int dummy_count = 0;
 776   static char buf[256];
 777
 778   symbol *sym;
 779
 780   sprintf (buf, "$@%d", ++dummy_count);
 781   sym = symbol_get (buf, loc);
 782   sym->class = nterm_sym;
 783   sym->number = nvars++;
 784   return sym;
 785 }
 786
 787 bool
 788 symbol_is_dummy (const symbol *sym)
 789 {
 790   return sym->tag[0] == '@' || (sym->tag[0] == '$' && sym->tag[1] == '@');
 791 }
 792
 793 /*-------------------.
 794 | Free the symbols.  |
 795 `-------------------*/
 796
 797 void
 798 symbols_free (void)
 799 {
 800   hash_free (symbol_table);
 801   hash_free (semantic_type_table);
 802   free (symbols);
 803   free (symbols_sorted);
 804 }
 805
 806
 807 /*---------------------------------------------------------------.
 808 | Look for undefined symbols, report an error, and consider them |
 809 | terminals.                                                     |
 810 `---------------------------------------------------------------*/
 811
 812 static int
 813 symbols_cmp (symbol const *a, symbol const *b)
 814 {
 815   return strcmp (a->tag, b->tag);
 816 }
 817
 818 static int
 819 symbols_cmp_qsort (void const *a, void const *b)
 820 {
 821   return symbols_cmp (*(symbol * const *)a, *(symbol * const *)b);
 822 }
 823
 824 static void
 825 symbols_do (Hash_processor processor, void *processor_data,
 826             struct hash_table *table, symbol **sorted)
 827 {
 828   size_t count = hash_get_n_entries (table);
 829   if (!sorted)
 830     {
 831       sorted = xnmalloc (count, sizeof *sorted);
 832       hash_get_entries (table, (void**)sorted, count);
 833       qsort (sorted, count, sizeof *sorted, symbols_cmp_qsort);
 834     }
 835   {
 836     size_t i;
 837     for (i = 0; i < count; ++i)
 838       processor (sorted[i], processor_data);
 839   }
 840 }
 841
 842 /*--------------------------------------------------------------.
 843 | Check that all the symbols are defined.  Report any undefined |
 844 | symbols and consider them nonterminals.                       |
 845 `--------------------------------------------------------------*/
 846
 847 void
 848 symbols_check_defined (void)
 849 {
 850   symbols_do (symbol_check_defined_processor, NULL,
 851               symbol_table, symbols_sorted);
 852   symbols_do (semantic_type_check_defined_processor, NULL,
 853               semantic_type_table, semantic_types_sorted);
 854 }
 855
 856 /*------------------------------------------------------------------.
 857 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 858 | number.                                                           |
 859 `------------------------------------------------------------------*/
 860
 861 static void
 862 symbols_token_translations_init (void)
 863 {
 864   bool num_256_available_p = true;
 865   int i;
 866
 867   /* Find the highest user token number, and whether 256, the POSIX
 868      preferred user token number for the error token, is used.  */
 869   max_user_token_number = 0;
 870   for (i = 0; i < ntokens; ++i)
 871     {
 872       symbol *this = symbols[i];
 873       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 874         {
 875           if (this->user_token_number > max_user_token_number)
 876             max_user_token_number = this->user_token_number;
 877           if (this->user_token_number == 256)
 878             num_256_available_p = false;
 879         }
 880     }
 881
 882   /* If 256 is not used, assign it to error, to follow POSIX.  */
 883   if (num_256_available_p
 884       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 885     errtoken->user_token_number = 256;
 886
 887   /* Set the missing user numbers. */
 888   if (max_user_token_number < 256)
 889     max_user_token_number = 256;
 890
 891   for (i = 0; i < ntokens; ++i)
 892     {
 893       symbol *this = symbols[i];
 894       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 895         this->user_token_number = ++max_user_token_number;
 896       if (this->user_token_number > max_user_token_number)
 897         max_user_token_number = this->user_token_number;
 898     }
 899
 900   token_translations = xnmalloc (max_user_token_number + 1,
 901                                  sizeof *token_translations);
 902
 903   /* Initialize all entries for literal tokens to the internal token
 904      number for $undefined, which represents all invalid inputs.  */
 905   for (i = 0; i < max_user_token_number + 1; i++)
 906     token_translations[i] = undeftoken->number;
 907   symbols_do (symbol_translation_processor, NULL,
 908               symbol_table, symbols_sorted);
 909 }
 910
 911
 912 /*----------------------------------------------------------------.
 913 | Assign symbol numbers, and write definition of token names into |
 914 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 915 `----------------------------------------------------------------*/
 916
 917 void
 918 symbols_pack (void)
 919 {
 920   symbols_do (symbol_check_alias_consistency_processor, NULL,
 921               symbol_table, symbols_sorted);
 922
 923   symbols = xcalloc (nsyms, sizeof *symbols);
 924   symbols_do (symbol_pack_processor, NULL, symbol_table, symbols_sorted);
 925
 926   /* Aliases leave empty slots in symbols, so remove them.  */
 927   {
 928     int writei;
 929     int readi;
 930     int nsyms_old = nsyms;
 931     for (writei = 0, readi = 0; readi < nsyms_old; readi += 1)
 932       {
 933         if (symbols[readi] == NULL)
 934           {
 935             nsyms -= 1;
 936             ntokens -= 1;
 937           }
 938         else
 939           {
 940             symbols[writei] = symbols[readi];
 941             symbols[writei]->number = writei;
 942             if (symbols[writei]->alias)
 943               symbols[writei]->alias->number = writei;
 944             writei += 1;
 945           }
 946       }
 947   }
 948   symbols = xnrealloc (symbols, nsyms, sizeof *symbols);
 949
 950   symbols_token_translations_init ();
 951
 952   if (startsymbol->class == unknown_sym)
 953     fatal_at (startsymbol_location,
 954               _("the start symbol %s is undefined"),
 955               startsymbol->tag);
 956   else if (startsymbol->class == token_sym)
 957     fatal_at (startsymbol_location,
 958               _("the start symbol %s is a token"),
 959               startsymbol->tag);
 960 }
 961
 962
 963 /*--------------------------------------------------.
 964 | Set default tagged/tagless %destructor/%printer.  |
 965 `--------------------------------------------------*/
 966
 967 void
 968 default_tagged_code_props_set (code_props_type kind, code_props const *code)
 969 {
 970   if (default_tagged_code_props[kind].code)
 971     {
 972       complain_at (code->location,
 973                    _("redeclaration for default tagged %s"),
 974                    code_props_type_string (kind));
 975       complain_at (default_tagged_code_props[kind].location,
 976                    _("previous declaration"));
 977     }
 978   default_tagged_code_props[kind] = *code;
 979 }
 980
 981 void
 982 default_tagless_code_props_set (code_props_type kind, code_props const *code)
 983 {
 984   if (default_tagless_code_props[kind].code)
 985     {
 986       complain_at (code->location,
 987                    _("redeclaration for default tagless %s"),
 988                    code_props_type_string (kind));
 989       complain_at (default_tagless_code_props[kind].location,
 990                    _("previous declaration"));
 991     }
 992   default_tagless_code_props[kind] = *code;
 993 }
 994