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