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       assert (sym->status != declared);
 387       complain_at (sym->location,
 388                    sym->status == needed ? complaint : Wother,
 389                    _("symbol %s is used, but is not defined as a token"
 390                      " and has no rules"),
 391                    sym->tag);
 392       sym->class = nterm_sym;
 393       sym->number = nvars++;
 394     }
 395
 396   for (int i = 0; i < 2; ++i)
 397     symbol_code_props_get (sym, i)->is_used = true;
 398
 399   /* Set the semantic type status associated to the current symbol to
 400      'declared' so that we could check semantic types unnecessary uses. */
 401   if (sym->type_name)
 402     {
 403       semantic_type *sem_type = semantic_type_get (sym->type_name, NULL);
 404       if (sem_type)
 405         sem_type->status = declared;
 406     }
 407
 408   return true;
 409 }
 410
 411 static inline bool
 412 semantic_type_check_defined (semantic_type *sem_type)
 413 {
 414   // <*> and <> do not have to be "declared".
 415   if (sem_type->status == declared
 416       || !*sem_type->tag
 417       || STREQ(sem_type->tag, "*"))
 418     {
 419       for (int i = 0; i < 2; ++i)
 420         if (sem_type->props[i].kind != CODE_PROPS_NONE
 421             && ! sem_type->props[i].is_used)
 422           complain_at (sem_type->location, Wother,
 423                        _("useless %s for type <%s>"),
 424                        code_props_type_string (i), sem_type->tag);
 425     }
 426   else
 427     complain_at (sem_type->location, Wother,
 428                  _("type <%s> is used, but is not associated to any symbol"),
 429                  sem_type->tag);
 430
 431   return true;
 432 }
 433
 434 static bool
 435 symbol_check_defined_processor (void *sym, void *null ATTRIBUTE_UNUSED)
 436 {
 437   return symbol_check_defined (sym);
 438 }
 439
 440 static bool
 441 semantic_type_check_defined_processor (void *sem_type,
 442                                        void *null ATTRIBUTE_UNUSED)
 443 {
 444   return semantic_type_check_defined (sem_type);
 445 }
 446
 447
 448 void
 449 symbol_make_alias (symbol *sym, symbol *str, location loc)
 450 {
 451   if (str->alias)
 452     complain_at (loc, Wother,
 453               _("symbol %s used more than once as a literal string"), str->tag);
 454   else if (sym->alias)
 455     complain_at (loc, Wother,
 456               _("symbol %s given more than one literal string"), sym->tag);
 457   else
 458     {
 459       str->class = token_sym;
 460       str->user_token_number = sym->user_token_number;
 461       sym->user_token_number = USER_NUMBER_HAS_STRING_ALIAS;
 462       str->alias = sym;
 463       sym->alias = str;
 464       str->number = sym->number;
 465       symbol_type_set (str, sym->type_name, loc);
 466     }
 467 }
 468
 469
 470 /*---------------------------------------------------------.
 471 | Check that THIS, and its alias, have same precedence and |
 472 | associativity.                                           |
 473 `---------------------------------------------------------*/
 474
 475 static inline void
 476 symbol_check_alias_consistency (symbol *this)
 477 {
 478   symbol *sym = this;
 479   symbol *str = this->alias;
 480
 481   /* Check only the symbol in the symbol-string pair.  */
 482   if (!(this->alias
 483         && this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS))
 484     return;
 485
 486   if (str->type_name != sym->type_name)
 487     {
 488       if (str->type_name)
 489         symbol_type_set (sym, str->type_name, str->type_location);
 490       else
 491         symbol_type_set (str, sym->type_name, sym->type_location);
 492     }
 493
 494
 495   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
 496     if (str->props[i].code)
 497       symbol_code_props_set (sym, i, &str->props[i]);
 498     else if (sym->props[i].code)
 499       symbol_code_props_set (str, i, &sym->props[i]);
 500
 501   if (sym->prec || str->prec)
 502     {
 503       if (str->prec)
 504         symbol_precedence_set (sym, str->prec, str->assoc,
 505                                str->prec_location);
 506       else
 507         symbol_precedence_set (str, sym->prec, sym->assoc,
 508                                sym->prec_location);
 509     }
 510 }
 511
 512 static bool
 513 symbol_check_alias_consistency_processor (void *this,
 514                                           void *null ATTRIBUTE_UNUSED)
 515 {
 516   symbol_check_alias_consistency (this);
 517   return true;
 518 }
 519
 520
 521 /*-------------------------------------------------------------------.
 522 | Assign a symbol number, and write the definition of the token name |
 523 | into FDEFINES.  Put in SYMBOLS.                                    |
 524 `-------------------------------------------------------------------*/
 525
 526 static inline bool
 527 symbol_pack (symbol *this)
 528 {
 529   aver (this->number != NUMBER_UNDEFINED);
 530   if (this->class == nterm_sym)
 531     this->number += ntokens;
 532   else if (this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS)
 533     return true;
 534
 535   symbols[this->number] = this;
 536   return true;
 537 }
 538
 539 static bool
 540 symbol_pack_processor (void *this, void *null ATTRIBUTE_UNUSED)
 541 {
 542   return symbol_pack (this);
 543 }
 544
 545
 546 static void
 547 user_token_number_redeclaration (int num, symbol *first, symbol *second)
 548 {
 549   /* User token numbers are not assigned during the parsing, but in a
 550      second step, via a traversal of the symbol table sorted on tag.
 551
 552      However, error messages make more sense if we keep the first
 553      declaration first.  */
 554   if (location_cmp (first->location, second->location) > 0)
 555     {
 556       symbol* tmp = first;
 557       first = second;
 558       second = tmp;
 559     }
 560   complain_at (second->location, complaint,
 561                _("user token number %d redeclaration for %s"),
 562                num, second->tag);
 563   complain_at (first->location, complaint, _("previous declaration for %s"),
 564                first->tag);
 565 }
 566
 567 /*--------------------------------------------------.
 568 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 569 `--------------------------------------------------*/
 570
 571 static inline bool
 572 symbol_translation (symbol *this)
 573 {
 574   /* Non-terminal? */
 575   if (this->class == token_sym
 576       && this->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
 577     {
 578       /* A token which translation has already been set? */
 579       if (token_translations[this->user_token_number] != undeftoken->number)
 580         user_token_number_redeclaration
 581           (this->user_token_number,
 582            symbols[token_translations[this->user_token_number]],
 583            this);
 584
 585       token_translations[this->user_token_number] = this->number;
 586     }
 587
 588   return true;
 589 }
 590
 591 static bool
 592 symbol_translation_processor (void *this, void *null ATTRIBUTE_UNUSED)
 593 {
 594   return symbol_translation (this);
 595 }
 596
 597
 598 /*---------------------------------------.
 599 | Symbol and semantic type hash tables.  |
 600 `---------------------------------------*/
 601
 602 /* Initial capacity of symbol and semantic type hash table.  */
 603 #define HT_INITIAL_CAPACITY 257
 604
 605 static struct hash_table *symbol_table = NULL;
 606 static struct hash_table *semantic_type_table = NULL;
 607
 608 static inline bool
 609 hash_compare_symbol (const symbol *m1, const symbol *m2)
 610 {
 611   /* Since tags are unique, we can compare the pointers themselves.  */
 612   return UNIQSTR_EQ (m1->tag, m2->tag);
 613 }
 614
 615 static inline bool
 616 hash_compare_semantic_type (const semantic_type *m1, const semantic_type *m2)
 617 {
 618   /* Since names are unique, we can compare the pointers themselves.  */
 619   return UNIQSTR_EQ (m1->tag, m2->tag);
 620 }
 621
 622 static bool
 623 hash_symbol_comparator (void const *m1, void const *m2)
 624 {
 625   return hash_compare_symbol (m1, m2);
 626 }
 627
 628 static bool
 629 hash_semantic_type_comparator (void const *m1, void const *m2)
 630 {
 631   return hash_compare_semantic_type (m1, m2);
 632 }
 633
 634 static inline size_t
 635 hash_symbol (const symbol *m, size_t tablesize)
 636 {
 637   /* Since tags are unique, we can hash the pointer itself.  */
 638   return ((uintptr_t) m->tag) % tablesize;
 639 }
 640
 641 static inline size_t
 642 hash_semantic_type (const semantic_type *m, size_t tablesize)
 643 {
 644   /* Since names are unique, we can hash the pointer itself.  */
 645   return ((uintptr_t) m->tag) % tablesize;
 646 }
 647
 648 static size_t
 649 hash_symbol_hasher (void const *m, size_t tablesize)
 650 {
 651   return hash_symbol (m, tablesize);
 652 }
 653
 654 static size_t
 655 hash_semantic_type_hasher (void const *m, size_t tablesize)
 656 {
 657   return hash_semantic_type (m, tablesize);
 658 }
 659
 660 /*-------------------------------.
 661 | Create the symbol hash table.  |
 662 `-------------------------------*/
 663
 664 void
 665 symbols_new (void)
 666 {
 667   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 668                                   NULL,
 669                                   hash_symbol_hasher,
 670                                   hash_symbol_comparator,
 671                                   free);
 672   semantic_type_table = hash_initialize (HT_INITIAL_CAPACITY,
 673                                          NULL,
 674                                          hash_semantic_type_hasher,
 675                                          hash_semantic_type_comparator,
 676                                          free);
 677 }
 678
 679
 680 /*----------------------------------------------------------------.
 681 | Find the symbol named KEY, and return it.  If it does not exist |
 682 | yet, create it.                                                 |
 683 `----------------------------------------------------------------*/
 684
 685 symbol *
 686 symbol_from_uniqstr (const uniqstr key, location loc)
 687 {
 688   symbol probe;
 689   symbol *entry;
 690
 691   probe.tag = key;
 692   entry = hash_lookup (symbol_table, &probe);
 693
 694   if (!entry)
 695     {
 696       /* First insertion in the hash. */
 697       aver (!symbols_sorted);
 698       entry = symbol_new (key, loc);
 699       if (!hash_insert (symbol_table, entry))
 700         xalloc_die ();
 701     }
 702   return entry;
 703 }
 704
 705
 706 /*-----------------------------------------------------------------------.
 707 | Find the semantic type named KEY, and return it.  If it does not exist |
 708 | yet, create it.                                                        |
 709 `-----------------------------------------------------------------------*/
 710
 711 semantic_type *
 712 semantic_type_from_uniqstr (const uniqstr key, const location *loc)
 713 {
 714   semantic_type probe;
 715   semantic_type *entry;
 716
 717   probe.tag = key;
 718   entry = hash_lookup (semantic_type_table, &probe);
 719
 720   if (!entry)
 721     {
 722       /* First insertion in the hash. */
 723       entry = semantic_type_new (key, loc);
 724       if (!hash_insert (semantic_type_table, entry))
 725         xalloc_die ();
 726     }
 727   return entry;
 728 }
 729
 730
 731 /*----------------------------------------------------------------.
 732 | Find the symbol named KEY, and return it.  If it does not exist |
 733 | yet, create it.                                                 |
 734 `----------------------------------------------------------------*/
 735
 736 symbol *
 737 symbol_get (const char *key, location loc)
 738 {
 739   return symbol_from_uniqstr (uniqstr_new (key), loc);
 740 }
 741
 742
 743 /*-----------------------------------------------------------------------.
 744 | Find the semantic type named KEY, and return it.  If it does not exist |
 745 | yet, create it.                                                        |
 746 `-----------------------------------------------------------------------*/
 747
 748 semantic_type *
 749 semantic_type_get (const char *key, const location *loc)
 750 {
 751   return semantic_type_from_uniqstr (uniqstr_new (key), loc);
 752 }
 753
 754
 755 /*------------------------------------------------------------------.
 756 | Generate a dummy nonterminal, whose name cannot conflict with the |
 757 | user's names.                                                     |
 758 `------------------------------------------------------------------*/
 759
 760 symbol *
 761 dummy_symbol_get (location loc)
 762 {
 763   /* Incremented for each generated symbol.  */
 764   static int dummy_count = 0;
 765   static char buf[256];
 766
 767   symbol *sym;
 768
 769   sprintf (buf, "$@%d", ++dummy_count);
 770   sym = symbol_get (buf, loc);
 771   sym->class = nterm_sym;
 772   sym->number = nvars++;
 773   return sym;
 774 }
 775
 776 bool
 777 symbol_is_dummy (const symbol *sym)
 778 {
 779   return sym->tag[0] == '@' || (sym->tag[0] == '$' && sym->tag[1] == '@');
 780 }
 781
 782 /*-------------------.
 783 | Free the symbols.  |
 784 `-------------------*/
 785
 786 void
 787 symbols_free (void)
 788 {
 789   hash_free (symbol_table);
 790   hash_free (semantic_type_table);
 791   free (symbols);
 792   free (symbols_sorted);
 793 }
 794
 795
 796 /*---------------------------------------------------------------.
 797 | Look for undefined symbols, report an error, and consider them |
 798 | terminals.                                                     |
 799 `---------------------------------------------------------------*/
 800
 801 static int
 802 symbols_cmp (symbol const *a, symbol const *b)
 803 {
 804   return strcmp (a->tag, b->tag);
 805 }
 806
 807 static int
 808 symbols_cmp_qsort (void const *a, void const *b)
 809 {
 810   return symbols_cmp (*(symbol * const *)a, *(symbol * const *)b);
 811 }
 812
 813 static void
 814 symbols_do (Hash_processor processor, void *processor_data,
 815             struct hash_table *table, symbol **sorted)
 816 {
 817   size_t count = hash_get_n_entries (table);
 818   if (!sorted)
 819     {
 820       sorted = xnmalloc (count, sizeof *sorted);
 821       hash_get_entries (table, (void**)sorted, count);
 822       qsort (sorted, count, sizeof *sorted, symbols_cmp_qsort);
 823     }
 824   {
 825     size_t i;
 826     for (i = 0; i < count; ++i)
 827       processor (sorted[i], processor_data);
 828   }
 829 }
 830
 831 /*--------------------------------------------------------------.
 832 | Check that all the symbols are defined.  Report any undefined |
 833 | symbols and consider them nonterminals.                       |
 834 `--------------------------------------------------------------*/
 835
 836 void
 837 symbols_check_defined (void)
 838 {
 839   symbols_do (symbol_check_defined_processor, NULL,
 840               symbol_table, symbols_sorted);
 841   symbols_do (semantic_type_check_defined_processor, NULL,
 842               semantic_type_table, semantic_types_sorted);
 843 }
 844
 845 /*------------------------------------------------------------------.
 846 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 847 | number.                                                           |
 848 `------------------------------------------------------------------*/
 849
 850 static void
 851 symbols_token_translations_init (void)
 852 {
 853   bool num_256_available_p = true;
 854   int i;
 855
 856   /* Find the highest user token number, and whether 256, the POSIX
 857      preferred user token number for the error token, is used.  */
 858   max_user_token_number = 0;
 859   for (i = 0; i < ntokens; ++i)
 860     {
 861       symbol *this = symbols[i];
 862       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 863         {
 864           if (this->user_token_number > max_user_token_number)
 865             max_user_token_number = this->user_token_number;
 866           if (this->user_token_number == 256)
 867             num_256_available_p = false;
 868         }
 869     }
 870
 871   /* If 256 is not used, assign it to error, to follow POSIX.  */
 872   if (num_256_available_p
 873       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 874     errtoken->user_token_number = 256;
 875
 876   /* Set the missing user numbers. */
 877   if (max_user_token_number < 256)
 878     max_user_token_number = 256;
 879
 880   for (i = 0; i < ntokens; ++i)
 881     {
 882       symbol *this = symbols[i];
 883       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 884         this->user_token_number = ++max_user_token_number;
 885       if (this->user_token_number > max_user_token_number)
 886         max_user_token_number = this->user_token_number;
 887     }
 888
 889   token_translations = xnmalloc (max_user_token_number + 1,
 890                                  sizeof *token_translations);
 891
 892   /* Initialize all entries for literal tokens to the internal token
 893      number for $undefined, which represents all invalid inputs.  */
 894   for (i = 0; i < max_user_token_number + 1; i++)
 895     token_translations[i] = undeftoken->number;
 896   symbols_do (symbol_translation_processor, NULL,
 897               symbol_table, symbols_sorted);
 898 }
 899
 900
 901 /*----------------------------------------------------------------.
 902 | Assign symbol numbers, and write definition of token names into |
 903 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 904 `----------------------------------------------------------------*/
 905
 906 void
 907 symbols_pack (void)
 908 {
 909   symbols_do (symbol_check_alias_consistency_processor, NULL,
 910               symbol_table, symbols_sorted);
 911
 912   symbols = xcalloc (nsyms, sizeof *symbols);
 913   symbols_do (symbol_pack_processor, NULL, symbol_table, symbols_sorted);
 914
 915   /* Aliases leave empty slots in symbols, so remove them.  */
 916   {
 917     int writei;
 918     int readi;
 919     int nsyms_old = nsyms;
 920     for (writei = 0, readi = 0; readi < nsyms_old; readi += 1)
 921       {
 922         if (symbols[readi] == NULL)
 923           {
 924             nsyms -= 1;
 925             ntokens -= 1;
 926           }
 927         else
 928           {
 929             symbols[writei] = symbols[readi];
 930             symbols[writei]->number = writei;
 931             if (symbols[writei]->alias)
 932               symbols[writei]->alias->number = writei;
 933             writei += 1;
 934           }
 935       }
 936   }
 937   symbols = xnrealloc (symbols, nsyms, sizeof *symbols);
 938
 939   symbols_token_translations_init ();
 940
 941   if (startsymbol->class == unknown_sym)
 942     complain_at (startsymbol_location, fatal,
 943                  _("the start symbol %s is undefined"),
 944                  startsymbol->tag);
 945   else if (startsymbol->class == token_sym)
 946     complain_at (startsymbol_location, fatal,
 947                  _("the start symbol %s is a token"),
 948                  startsymbol->tag);
 949 }