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 (&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 (NULL, 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   unsigned i = 0;
 197   complain_indent (&second, complaint, &i,
 198                    _("%s redeclaration for %s"), what, s->tag);
 199   i += SUB_INDENT;
 200   complain_indent (&first, complaint, &i,
 201                    _("previous declaration"));
 202 }
 203
 204 static void
 205 semantic_type_redeclaration (semantic_type *s, const char *what, location first,
 206                              location second)
 207 {
 208   unsigned i = 0;
 209   complain_indent (&second, complaint, &i,
 210                    _("%s redeclaration for <%s>"), what, s->tag);
 211   i += SUB_INDENT;
 212   complain_indent (&first, complaint, &i,
 213                    _("previous declaration"));
 214 }
 215
 216
 217
 218 /*-----------------------------------------------------------------.
 219 | Set the TYPE_NAME associated with SYM.  Does nothing if passed 0 |
 220 | as TYPE_NAME.                                                    |
 221 `-----------------------------------------------------------------*/
 222
 223 void
 224 symbol_type_set (symbol *sym, uniqstr type_name, location loc)
 225 {
 226   if (type_name)
 227     {
 228       if (sym->type_name)
 229         symbol_redeclaration (sym, "%type", sym->type_location, loc);
 230       uniqstr_assert (type_name);
 231       sym->type_name = type_name;
 232       sym->type_location = loc;
 233     }
 234 }
 235
 236 /*--------------------------------------------------------.
 237 | Set the DESTRUCTOR or PRINTER associated with the SYM.  |
 238 `--------------------------------------------------------*/
 239
 240 void
 241 symbol_code_props_set (symbol *sym, code_props_type kind,
 242                        code_props const *code)
 243 {
 244   if (sym->props[kind].code)
 245     symbol_redeclaration (sym, code_props_type_string (kind),
 246                           sym->props[kind].location,
 247                           code->location);
 248   sym->props[kind] = *code;
 249 }
 250
 251 /*-----------------------------------------------------.
 252 | Set the DESTRUCTOR or PRINTER associated with TYPE.  |
 253 `-----------------------------------------------------*/
 254
 255 void
 256 semantic_type_code_props_set (semantic_type *type,
 257                               code_props_type kind,
 258                               code_props const *code)
 259 {
 260   if (type->props[kind].code)
 261     semantic_type_redeclaration (type, code_props_type_string (kind),
 262                                  type->props[kind].location,
 263                                  code->location);
 264   type->props[kind] = *code;
 265 }
 266
 267 /*---------------------------------------------------.
 268 | Get the computed %destructor or %printer for SYM.  |
 269 `---------------------------------------------------*/
 270
 271 code_props *
 272 symbol_code_props_get (symbol *sym, code_props_type kind)
 273 {
 274   /* Per-symbol code props.  */
 275   if (sym->props[kind].code)
 276     return &sym->props[kind];
 277
 278   /* Per-type code props.  */
 279   if (sym->type_name)
 280     {
 281       code_props *code =
 282         &semantic_type_get (sym->type_name, NULL)->props[kind];
 283       if (code->code)
 284         return code;
 285     }
 286
 287   /* Apply default code props's only to user-defined symbols.  */
 288   if (sym->tag[0] != '$' && sym != errtoken)
 289     {
 290       code_props *code =
 291         &semantic_type_get (sym->type_name ? "*" : "", NULL)->props[kind];
 292       if (code->code)
 293         return code;
 294     }
 295   return &code_props_none;
 296 }
 297
 298 /*-----------------------------------------------------------------.
 299 | Set the PRECEDENCE associated with SYM.  Does nothing if invoked |
 300 | with UNDEF_ASSOC as ASSOC.                                       |
 301 `-----------------------------------------------------------------*/
 302
 303 void
 304 symbol_precedence_set (symbol *sym, int prec, assoc a, location loc)
 305 {
 306   if (a != undef_assoc)
 307     {
 308       if (sym->prec != 0)
 309         symbol_redeclaration (sym, assoc_to_string (a), sym->prec_location,
 310                               loc);
 311       sym->prec = prec;
 312       sym->assoc = a;
 313       sym->prec_location = loc;
 314     }
 315
 316   /* Only terminals have a precedence. */
 317   symbol_class_set (sym, token_sym, loc, false);
 318 }
 319
 320
 321 /*------------------------------------.
 322 | Set the CLASS associated with SYM.  |
 323 `------------------------------------*/
 324
 325 void
 326 symbol_class_set (symbol *sym, symbol_class class, location loc, bool declaring)
 327 {
 328   bool warned = false;
 329   if (sym->class != unknown_sym && sym->class != class)
 330     {
 331       complain (&loc, complaint, _("symbol %s redefined"), sym->tag);
 332       // Don't report both "redefined" and "redeclared".
 333       warned = true;
 334     }
 335
 336   if (class == nterm_sym && sym->class != nterm_sym)
 337     sym->number = nvars++;
 338   else if (class == token_sym && sym->number == NUMBER_UNDEFINED)
 339     sym->number = ntokens++;
 340
 341   sym->class = class;
 342
 343   if (declaring)
 344     {
 345       if (sym->status == declared && !warned)
 346         complain (&loc, Wother, _("symbol %s redeclared"), sym->tag);
 347       sym->status = declared;
 348     }
 349 }
 350
 351
 352 /*------------------------------------------------.
 353 | Set the USER_TOKEN_NUMBER associated with SYM.  |
 354 `------------------------------------------------*/
 355
 356 void
 357 symbol_user_token_number_set (symbol *sym, int user_token_number, location loc)
 358 {
 359   int *user_token_numberp;
 360
 361   if (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
 362     user_token_numberp = &sym->user_token_number;
 363   else
 364     user_token_numberp = &sym->alias->user_token_number;
 365   if (*user_token_numberp != USER_NUMBER_UNDEFINED
 366       && *user_token_numberp != user_token_number)
 367     complain (&loc, complaint, _("redefining user token number of %s"),
 368               sym->tag);
 369
 370   *user_token_numberp = user_token_number;
 371   /* User defined $end token? */
 372   if (user_token_number == 0)
 373     {
 374       endtoken = sym;
 375       /* It is always mapped to 0, so it was already counted in
 376          NTOKENS.  */
 377       if (endtoken->number != NUMBER_UNDEFINED)
 378         --ntokens;
 379       endtoken->number = 0;
 380     }
 381 }
 382
 383
 384 /*----------------------------------------------------------.
 385 | If SYM is not defined, report an error, and consider it a |
 386 | nonterminal.                                              |
 387 `----------------------------------------------------------*/
 388
 389 static inline bool
 390 symbol_check_defined (symbol *sym)
 391 {
 392   if (sym->class == unknown_sym)
 393     {
 394       assert (sym->status != declared);
 395       complain (&sym->location,
 396                 sym->status == needed ? complaint : Wother,
 397                 _("symbol %s is used, but is not defined as a token"
 398                   " and has no rules"),
 399                   sym->tag);
 400       sym->class = nterm_sym;
 401       sym->number = nvars++;
 402     }
 403
 404   for (int i = 0; i < 2; ++i)
 405     symbol_code_props_get (sym, i)->is_used = true;
 406
 407   /* Set the semantic type status associated to the current symbol to
 408      'declared' so that we could check semantic types unnecessary uses. */
 409   if (sym->type_name)
 410     {
 411       semantic_type *sem_type = semantic_type_get (sym->type_name, NULL);
 412       if (sem_type)
 413         sem_type->status = declared;
 414     }
 415
 416   return true;
 417 }
 418
 419 static inline bool
 420 semantic_type_check_defined (semantic_type *sem_type)
 421 {
 422   // <*> and <> do not have to be "declared".
 423   if (sem_type->status == declared
 424       || !*sem_type->tag
 425       || STREQ(sem_type->tag, "*"))
 426     {
 427       for (int i = 0; i < 2; ++i)
 428         if (sem_type->props[i].kind != CODE_PROPS_NONE
 429             && ! sem_type->props[i].is_used)
 430           complain (&sem_type->location, Wother,
 431                     _("useless %s for type <%s>"),
 432                     code_props_type_string (i), sem_type->tag);
 433     }
 434   else
 435     complain (&sem_type->location, Wother,
 436               _("type <%s> is used, but is not associated to any symbol"),
 437               sem_type->tag);
 438
 439   return true;
 440 }
 441
 442 static bool
 443 symbol_check_defined_processor (void *sym, void *null ATTRIBUTE_UNUSED)
 444 {
 445   return symbol_check_defined (sym);
 446 }
 447
 448 static bool
 449 semantic_type_check_defined_processor (void *sem_type,
 450                                        void *null ATTRIBUTE_UNUSED)
 451 {
 452   return semantic_type_check_defined (sem_type);
 453 }
 454
 455
 456 void
 457 symbol_make_alias (symbol *sym, symbol *str, location loc)
 458 {
 459   if (str->alias)
 460     complain (&loc, Wother,
 461               _("symbol %s used more than once as a literal string"), str->tag);
 462   else if (sym->alias)
 463     complain (&loc, Wother,
 464               _("symbol %s given more than one literal string"), sym->tag);
 465   else
 466     {
 467       str->class = token_sym;
 468       str->user_token_number = sym->user_token_number;
 469       sym->user_token_number = USER_NUMBER_HAS_STRING_ALIAS;
 470       str->alias = sym;
 471       sym->alias = str;
 472       str->number = sym->number;
 473       symbol_type_set (str, sym->type_name, loc);
 474     }
 475 }
 476
 477
 478 /*---------------------------------------------------------.
 479 | Check that THIS, and its alias, have same precedence and |
 480 | associativity.                                           |
 481 `---------------------------------------------------------*/
 482
 483 static inline void
 484 symbol_check_alias_consistency (symbol *this)
 485 {
 486   symbol *sym = this;
 487   symbol *str = this->alias;
 488
 489   /* Check only the symbol in the symbol-string pair.  */
 490   if (!(this->alias
 491         && this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS))
 492     return;
 493
 494   if (str->type_name != sym->type_name)
 495     {
 496       if (str->type_name)
 497         symbol_type_set (sym, str->type_name, str->type_location);
 498       else
 499         symbol_type_set (str, sym->type_name, sym->type_location);
 500     }
 501
 502
 503   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
 504     if (str->props[i].code)
 505       symbol_code_props_set (sym, i, &str->props[i]);
 506     else if (sym->props[i].code)
 507       symbol_code_props_set (str, i, &sym->props[i]);
 508
 509   if (sym->prec || str->prec)
 510     {
 511       if (str->prec)
 512         symbol_precedence_set (sym, str->prec, str->assoc,
 513                                str->prec_location);
 514       else
 515         symbol_precedence_set (str, sym->prec, sym->assoc,
 516                                sym->prec_location);
 517     }
 518 }
 519
 520 static bool
 521 symbol_check_alias_consistency_processor (void *this,
 522                                           void *null ATTRIBUTE_UNUSED)
 523 {
 524   symbol_check_alias_consistency (this);
 525   return true;
 526 }
 527
 528
 529 /*-------------------------------------------------------------------.
 530 | Assign a symbol number, and write the definition of the token name |
 531 | into FDEFINES.  Put in SYMBOLS.                                    |
 532 `-------------------------------------------------------------------*/
 533
 534 static inline bool
 535 symbol_pack (symbol *this)
 536 {
 537   aver (this->number != NUMBER_UNDEFINED);
 538   if (this->class == nterm_sym)
 539     this->number += ntokens;
 540   else if (this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS)
 541     return true;
 542
 543   symbols[this->number] = this;
 544   return true;
 545 }
 546
 547 static bool
 548 symbol_pack_processor (void *this, void *null ATTRIBUTE_UNUSED)
 549 {
 550   return symbol_pack (this);
 551 }
 552
 553
 554 static void
 555 user_token_number_redeclaration (int num, symbol *first, symbol *second)
 556 {
 557   unsigned i = 0;
 558   /* User token numbers are not assigned during the parsing, but in a
 559      second step, via a traversal of the symbol table sorted on tag.
 560
 561      However, error messages make more sense if we keep the first
 562      declaration first.  */
 563   if (location_cmp (first->location, second->location) > 0)
 564     {
 565       symbol* tmp = first;
 566       first = second;
 567       second = tmp;
 568     }
 569   complain_indent (&second->location, complaint, &i,
 570                    _("user token number %d redeclaration for %s"),
 571                    num, second->tag);
 572   i += SUB_INDENT;
 573   complain_indent (&first->location, complaint, &i,
 574                    _("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   free (semantic_types_sorted);
 805 }
 806
 807
 808 /*---------------------------------------------------------------.
 809 | Look for undefined symbols, report an error, and consider them |
 810 | terminals.                                                     |
 811 `---------------------------------------------------------------*/
 812
 813 static int
 814 symbols_cmp (symbol const *a, symbol const *b)
 815 {
 816   return strcmp (a->tag, b->tag);
 817 }
 818
 819 static int
 820 symbols_cmp_qsort (void const *a, void const *b)
 821 {
 822   return symbols_cmp (*(symbol * const *)a, *(symbol * const *)b);
 823 }
 824
 825 static void
 826 symbols_do (Hash_processor processor, void *processor_data,
 827             struct hash_table *table, symbol ***sorted)
 828 {
 829   size_t count = hash_get_n_entries (table);
 830   if (!*sorted)
 831     {
 832       *sorted = xnmalloc (count, sizeof **sorted);
 833       hash_get_entries (table, (void**)*sorted, count);
 834       qsort (*sorted, count, sizeof **sorted, symbols_cmp_qsort);
 835     }
 836   {
 837     size_t i;
 838     for (i = 0; i < count; ++i)
 839       processor ((*sorted)[i], processor_data);
 840   }
 841 }
 842
 843 /*--------------------------------------------------------------.
 844 | Check that all the symbols are defined.  Report any undefined |
 845 | symbols and consider them nonterminals.                       |
 846 `--------------------------------------------------------------*/
 847
 848 void
 849 symbols_check_defined (void)
 850 {
 851   symbols_do (symbol_check_defined_processor, NULL,
 852               symbol_table, &symbols_sorted);
 853   symbols_do (semantic_type_check_defined_processor, NULL,
 854               semantic_type_table, &semantic_types_sorted);
 855 }
 856
 857 /*------------------------------------------------------------------.
 858 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 859 | number.                                                           |
 860 `------------------------------------------------------------------*/
 861
 862 static void
 863 symbols_token_translations_init (void)
 864 {
 865   bool num_256_available_p = true;
 866   int i;
 867
 868   /* Find the highest user token number, and whether 256, the POSIX
 869      preferred user token number for the error token, is used.  */
 870   max_user_token_number = 0;
 871   for (i = 0; i < ntokens; ++i)
 872     {
 873       symbol *this = symbols[i];
 874       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 875         {
 876           if (this->user_token_number > max_user_token_number)
 877             max_user_token_number = this->user_token_number;
 878           if (this->user_token_number == 256)
 879             num_256_available_p = false;
 880         }
 881     }
 882
 883   /* If 256 is not used, assign it to error, to follow POSIX.  */
 884   if (num_256_available_p
 885       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 886     errtoken->user_token_number = 256;
 887
 888   /* Set the missing user numbers. */
 889   if (max_user_token_number < 256)
 890     max_user_token_number = 256;
 891
 892   for (i = 0; i < ntokens; ++i)
 893     {
 894       symbol *this = symbols[i];
 895       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 896         this->user_token_number = ++max_user_token_number;
 897       if (this->user_token_number > max_user_token_number)
 898         max_user_token_number = this->user_token_number;
 899     }
 900
 901   token_translations = xnmalloc (max_user_token_number + 1,
 902                                  sizeof *token_translations);
 903
 904   /* Initialize all entries for literal tokens to the internal token
 905      number for $undefined, which represents all invalid inputs.  */
 906   for (i = 0; i < max_user_token_number + 1; i++)
 907     token_translations[i] = undeftoken->number;
 908   symbols_do (symbol_translation_processor, NULL,
 909               symbol_table, &symbols_sorted);
 910 }
 911
 912
 913 /*----------------------------------------------------------------.
 914 | Assign symbol numbers, and write definition of token names into |
 915 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 916 `----------------------------------------------------------------*/
 917
 918 void
 919 symbols_pack (void)
 920 {
 921   symbols_do (symbol_check_alias_consistency_processor, NULL,
 922               symbol_table, &symbols_sorted);
 923
 924   symbols = xcalloc (nsyms, sizeof *symbols);
 925   symbols_do (symbol_pack_processor, NULL, symbol_table, &symbols_sorted);
 926
 927   /* Aliases leave empty slots in symbols, so remove them.  */
 928   {
 929     int writei;
 930     int readi;
 931     int nsyms_old = nsyms;
 932     for (writei = 0, readi = 0; readi < nsyms_old; readi += 1)
 933       {
 934         if (symbols[readi] == NULL)
 935           {
 936             nsyms -= 1;
 937             ntokens -= 1;
 938           }
 939         else
 940           {
 941             symbols[writei] = symbols[readi];
 942             symbols[writei]->number = writei;
 943             if (symbols[writei]->alias)
 944               symbols[writei]->alias->number = writei;
 945             writei += 1;
 946           }
 947       }
 948   }
 949   symbols = xnrealloc (symbols, nsyms, sizeof *symbols);
 950
 951   symbols_token_translations_init ();
 952
 953   if (startsymbol->class == unknown_sym)
 954     complain (&startsymbol_location, fatal,
 955               _("the start symbol %s is undefined"),
 956               startsymbol->tag);
 957   else if (startsymbol->class == token_sym)
 958     complain (&startsymbol_location, fatal,
 959               _("the start symbol %s is a token"),
 960               startsymbol->tag);
 961 }