src/symtab.c

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