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