src/symtab.c

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