src/symtab.c

   1 /* Symbol table manager for Bison.
   2
   3    Copyright (C) 1984, 1989, 2000-2002, 2004-2012 Free Software
   4    Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include <hash.h>
  25
  26 #include "complain.h"
  27 #include "gram.h"
  28 #include "symtab.h"
  29
  30 /*-------------------------------------------------------------------.
  31 | Symbols sorted by tag.  Allocated by the first invocation of       |
  32 | symbols_do, after which no more symbols should be created.         |
  33 `-------------------------------------------------------------------*/
  34
  35 static symbol **symbols_sorted = NULL;
  36 static symbol **semantic_types_sorted = NULL;
  37
  38 /*------------------------.
  39 | Distinguished symbols.  |
  40 `------------------------*/
  41
  42 symbol *errtoken = NULL;
  43 symbol *undeftoken = NULL;
  44 symbol *endtoken = NULL;
  45 symbol *accept = NULL;
  46 symbol *startsymbol = NULL;
  47 location startsymbol_location;
  48
  49 /*---------------------------------------.
  50 | Default %destructor's and %printer's.  |
  51 `---------------------------------------*/
  52
  53 static code_props default_tagged_code_props[CODE_PROPS_SIZE] =
  54   {
  55     CODE_PROPS_NONE_INIT,
  56     CODE_PROPS_NONE_INIT,
  57   };
  58 static code_props default_tagless_code_props[CODE_PROPS_SIZE] =
  59   {
  60     CODE_PROPS_NONE_INIT,
  61     CODE_PROPS_NONE_INIT,
  62   };
  63
  64 /*---------------------------------.
  65 | Create a new symbol, named TAG.  |
  66 `---------------------------------*/
  67
  68 static symbol *
  69 symbol_new (uniqstr tag, location loc)
  70 {
  71   symbol *res = xmalloc (sizeof *res);
  72
  73   uniqstr_assert (tag);
  74
  75   /* If the tag is not a string (starts with a double quote), check
  76      that it is valid for Yacc. */
  77   if (tag[0] != '\"' && tag[0] != '\'' && strchr (tag, '-'))
  78     yacc_at (loc, _("POSIX Yacc forbids dashes in symbol names: %s"),
  79              tag);
  80
  81   res->tag = tag;
  82   res->location = loc;
  83
  84   res->type_name = NULL;
  85   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
  86     code_props_none_init (&res->props[i]);
  87
  88   res->number = NUMBER_UNDEFINED;
  89   res->prec = 0;
  90   res->assoc = undef_assoc;
  91   res->user_token_number = USER_NUMBER_UNDEFINED;
  92
  93   res->alias = NULL;
  94   res->class = unknown_sym;
  95   res->status = undeclared;
  96
  97   if (nsyms == SYMBOL_NUMBER_MAXIMUM)
  98     fatal (_("too many symbols in input grammar (limit is %d)"),
  99            SYMBOL_NUMBER_MAXIMUM);
 100   nsyms++;
 101   return res;
 102 }
 103
 104 char const *
 105 code_props_type_string (code_props_type kind)
 106 {
 107   switch (kind)
 108     {
 109     case destructor:
 110       return "%destructor";
 111     case printer:
 112       return "%printer";
 113     }
 114   assert (0);
 115 }
 116
 117 /*----------------------------------------.
 118 | Create a new semantic type, named TAG.  |
 119 `----------------------------------------*/
 120
 121 static semantic_type *
 122 semantic_type_new (uniqstr tag, const location *loc)
 123 {
 124   semantic_type *res = xmalloc (sizeof *res);
 125
 126   uniqstr_assert (tag);
 127   res->tag = tag;
 128   if (loc)
 129     res->location = *loc;
 130   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
 131     code_props_none_init (&res->props[i]);
 132
 133   return res;
 134 }
 135
 136
 137 /*-----------------.
 138 | Print a symbol.  |
 139 `-----------------*/
 140
 141 #define SYMBOL_ATTR_PRINT(Attr)                         \
 142   if (s->Attr)                                          \
 143     fprintf (f, " %s { %s }", #Attr, s->Attr)
 144
 145 #define SYMBOL_CODE_PRINT(Attr)                                         \
 146   if (s->props[Attr].code)                                              \
 147     fprintf (f, " %s { %s }", #Attr, s->props[Attr].code)
 148
 149 void
 150 symbol_print (symbol *s, FILE *f)
 151 {
 152   if (s)
 153     {
 154       fprintf (f, "\"%s\"", s->tag);
 155       SYMBOL_ATTR_PRINT (type_name);
 156       SYMBOL_CODE_PRINT (destructor);
 157       SYMBOL_CODE_PRINT (printer);
 158     }
 159   else
 160     fprintf (f, "<NULL>");
 161 }
 162
 163 #undef SYMBOL_ATTR_PRINT
 164 #undef SYMBOL_CODE_PRINT
 165
 166
 167 /*----------------------------------.
 168 | Whether S is a valid identifier.  |
 169 `----------------------------------*/
 170
 171 static bool
 172 is_identifier (uniqstr s)
 173 {
 174   static char const alphanum[26 + 26 + 1 + 10] =
 175     "abcdefghijklmnopqrstuvwxyz"
 176     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 177     "_"
 178     "0123456789";
 179   if (!s || ! memchr (alphanum, *s, sizeof alphanum - 10))
 180     return false;
 181   for (++s; *s; ++s)
 182     if (! memchr (alphanum, *s, sizeof alphanum))
 183       return false;
 184   return true;
 185 }
 186
 187
 188 /*-----------------------------------------------.
 189 | Get the identifier associated to this symbol.  |
 190 `-----------------------------------------------*/
 191 uniqstr
 192 symbol_id_get (symbol const *sym)
 193 {
 194   aver (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS);
 195   if (sym->alias)
 196     sym = sym->alias;
 197   return is_identifier (sym->tag) ? sym->tag : 0;
 198 }
 199
 200
 201 /*------------------------------------------------------------------.
 202 | Complain that S's WHAT is redeclared at SECOND, and was first set |
 203 | at FIRST.                                                         |
 204 `------------------------------------------------------------------*/
 205
 206 static void
 207 symbol_redeclaration (symbol *s, const char *what, location first,
 208                       location second)
 209 {
 210   complain_at (second, _("%s redeclaration for %s"), what, s->tag);
 211   complain_at (first, _("previous declaration"));
 212 }
 213
 214 static void
 215 semantic_type_redeclaration (semantic_type *s, const char *what, location first,
 216                              location second)
 217 {
 218   complain_at (second, _("%s redeclaration for <%s>"), what, s->tag);
 219   complain_at (first, _("previous declaration"));
 220 }
 221
 222
 223
 224 /*-----------------------------------------------------------------.
 225 | Set the TYPE_NAME associated with SYM.  Does nothing if passed 0 |
 226 | as TYPE_NAME.                                                    |
 227 `-----------------------------------------------------------------*/
 228
 229 void
 230 symbol_type_set (symbol *sym, uniqstr type_name, location loc)
 231 {
 232   if (type_name)
 233     {
 234       if (sym->type_name)
 235         symbol_redeclaration (sym, "%type", sym->type_location, loc);
 236       uniqstr_assert (type_name);
 237       sym->type_name = type_name;
 238       sym->type_location = loc;
 239     }
 240 }
 241
 242 /*--------------------------------------------------------.
 243 | Set the DESTRUCTOR or PRINTER associated with the SYM.  |
 244 `--------------------------------------------------------*/
 245
 246 void
 247 symbol_code_props_set (symbol *sym, code_props_type kind,
 248                        code_props const *code)
 249 {
 250   if (sym->props[kind].code)
 251     symbol_redeclaration (sym, code_props_type_string (kind),
 252                           sym->props[kind].location,
 253                           code->location);
 254   sym->props[kind] = *code;
 255 }
 256
 257 /*-----------------------------------------------------.
 258 | Set the DESTRUCTOR or PRINTER associated with TYPE.  |
 259 `-----------------------------------------------------*/
 260
 261 void
 262 semantic_type_code_props_set (semantic_type *type,
 263                               code_props_type kind,
 264                               code_props const *code)
 265 {
 266   if (type->props[kind].code)
 267     semantic_type_redeclaration (type, code_props_type_string (kind),
 268                                  type->props[kind].location,
 269                                  code->location);
 270   type->props[kind] = *code;
 271 }
 272
 273 /*---------------------------------------------------.
 274 | Get the computed %destructor or %printer for SYM.  |
 275 `---------------------------------------------------*/
 276
 277 code_props const *
 278 symbol_code_props_get (symbol const *sym,
 279                        code_props_type kind)
 280 {
 281   /* Per-symbol code props.  */
 282   if (sym->props[kind].code)
 283     return &sym->props[kind];
 284
 285   /* Per-type code props.  */
 286   if (sym->type_name)
 287     {
 288       code_props const *code =
 289         &semantic_type_get (sym->type_name, NULL)->props[kind];
 290       if (code->code)
 291         return code;
 292     }
 293
 294   /* Apply default code props's only to user-defined symbols.  */
 295   if (sym->tag[0] == '$' || sym == errtoken)
 296     return &code_props_none;
 297
 298   if (sym->type_name)
 299     return &default_tagged_code_props[kind];
 300   return &default_tagless_code_props[kind];
 301 }
 302
 303 /*-----------------------------------------------------------------.
 304 | Set the PRECEDENCE associated with SYM.  Does nothing if invoked |
 305 | with UNDEF_ASSOC as ASSOC.                                       |
 306 `-----------------------------------------------------------------*/
 307
 308 void
 309 symbol_precedence_set (symbol *sym, int prec, assoc a, location loc)
 310 {
 311   if (a != undef_assoc)
 312     {
 313       if (sym->prec != 0)
 314         symbol_redeclaration (sym, assoc_to_string (a), sym->prec_location,
 315                               loc);
 316       sym->prec = prec;
 317       sym->assoc = a;
 318       sym->prec_location = loc;
 319     }
 320
 321   /* Only terminals have a precedence. */
 322   symbol_class_set (sym, token_sym, loc, false);
 323 }
 324
 325
 326 /*------------------------------------.
 327 | Set the CLASS associated with SYM.  |
 328 `------------------------------------*/
 329
 330 void
 331 symbol_class_set (symbol *sym, symbol_class class, location loc, bool declaring)
 332 {
 333   bool warned = false;
 334   if (sym->class != unknown_sym && sym->class != class)
 335     {
 336       complain_at (loc, _("symbol %s redefined"), sym->tag);
 337       // Don't report both "redefined" and "redeclared".
 338       warned = true;
 339     }
 340
 341   if (class == nterm_sym && sym->class != nterm_sym)
 342     sym->number = nvars++;
 343   else if (class == token_sym && sym->number == NUMBER_UNDEFINED)
 344     sym->number = ntokens++;
 345
 346   sym->class = class;
 347
 348   if (declaring)
 349     {
 350       if (sym->status == declared && !warned)
 351         warn_at (loc, _("symbol %s redeclared"), sym->tag);
 352       sym->status = declared;
 353     }
 354 }
 355
 356
 357 /*------------------------------------------------.
 358 | Set the USER_TOKEN_NUMBER associated with SYM.  |
 359 `------------------------------------------------*/
 360
 361 void
 362 symbol_user_token_number_set (symbol *sym, int user_token_number, location loc)
 363 {
 364   int *user_token_numberp;
 365
 366   if (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
 367     user_token_numberp = &sym->user_token_number;
 368   else
 369     user_token_numberp = &sym->alias->user_token_number;
 370   if (*user_token_numberp != USER_NUMBER_UNDEFINED
 371       && *user_token_numberp != user_token_number)
 372     complain_at (loc, _("redefining user token number of %s"), sym->tag);
 373
 374   *user_token_numberp = user_token_number;
 375   /* User defined $end token? */
 376   if (user_token_number == 0)
 377     {
 378       endtoken = sym;
 379       /* It is always mapped to 0, so it was already counted in
 380          NTOKENS.  */
 381       if (endtoken->number != NUMBER_UNDEFINED)
 382         --ntokens;
 383       endtoken->number = 0;
 384     }
 385 }
 386
 387
 388 /*----------------------------------------------------------.
 389 | If SYM is not defined, report an error, and consider it a |
 390 | nonterminal.                                              |
 391 `----------------------------------------------------------*/
 392
 393 static inline bool
 394 symbol_check_defined (symbol *sym)
 395 {
 396   if (sym->class == unknown_sym)
 397     {
 398       switch (sym->status)
 399         {
 400         case used:
 401           warn_at (sym->location,
 402                    _("symbol %s is used, but is not defined as a token"
 403                      " and has no rules"),
 404                    sym->tag);
 405           break;
 406         case undeclared:
 407         case needed:
 408           complain_at (sym->location,
 409                        _("symbol %s is used, but is not defined as a token"
 410                          " and has no rules"),
 411                        sym->tag);
 412           break;
 413         case declared:
 414           /* If declared, then sym->class != unknown_sym. */
 415           assert (0);
 416         }
 417
 418       sym->class = nterm_sym;
 419       sym->number = nvars++;
 420     }
 421
 422   for (int i = 0; i < 2; ++i)
 423     if (sym->props[i].kind == CODE_PROPS_NONE && sym->type_name)
 424       {
 425         semantic_type *sem_type = semantic_type_get (sym->type_name, NULL);
 426         if (sem_type
 427             && sem_type->props[i].kind != CODE_PROPS_NONE)
 428           sem_type->props[i].is_used = true;
 429       }
 430
 431   /* Set the semantic type status associated to the current symbol to
 432      'declared' so that we could check semantic types unnecessary uses. */
 433   if (sym->type_name)
 434     {
 435       semantic_type *sem_type = semantic_type_get (sym->type_name, NULL);
 436       if (sem_type)
 437         sem_type->status = declared;
 438     }
 439
 440   return true;
 441 }
 442
 443 static inline bool
 444 semantic_type_check_defined (semantic_type *sem_type)
 445 {
 446   if (sem_type->status == declared)
 447     {
 448       for (int i = 0; i < 2; ++i)
 449         if (sem_type->props[i].kind != CODE_PROPS_NONE
 450             && ! sem_type->props[i].is_used)
 451           warn_at (sem_type->location,
 452                    _("useless %s for type <%s>"),
 453                    code_props_type_string (i), sem_type->tag);
 454     }
 455   else
 456     warn_at (sem_type->location,
 457              _("type <%s> is used, but is not associated to any symbol"),
 458              sem_type->tag);
 459
 460   return true;
 461 }
 462
 463 static bool
 464 symbol_check_defined_processor (void *sym, void *null ATTRIBUTE_UNUSED)
 465 {
 466   return symbol_check_defined (sym);
 467 }
 468
 469 static bool
 470 semantic_type_check_defined_processor (void *sem_type,
 471                                        void *null ATTRIBUTE_UNUSED)
 472 {
 473   return semantic_type_check_defined (sem_type);
 474 }
 475
 476
 477 void
 478 symbol_make_alias (symbol *sym, symbol *str, location loc)
 479 {
 480   if (str->alias)
 481     warn_at (loc, _("symbol %s used more than once as a literal string"),
 482              str->tag);
 483   else if (sym->alias)
 484     warn_at (loc, _("symbol %s given more than one literal string"),
 485              sym->tag);
 486   else
 487     {
 488       str->class = token_sym;
 489       str->user_token_number = sym->user_token_number;
 490       sym->user_token_number = USER_NUMBER_HAS_STRING_ALIAS;
 491       str->alias = sym;
 492       sym->alias = str;
 493       str->number = sym->number;
 494       symbol_type_set (str, sym->type_name, loc);
 495     }
 496 }
 497
 498
 499 /*---------------------------------------------------------.
 500 | Check that THIS, and its alias, have same precedence and |
 501 | associativity.                                           |
 502 `---------------------------------------------------------*/
 503
 504 static inline void
 505 symbol_check_alias_consistency (symbol *this)
 506 {
 507   symbol *sym = this;
 508   symbol *str = this->alias;
 509
 510   /* Check only the symbol in the symbol-string pair.  */
 511   if (!(this->alias
 512         && this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS))
 513     return;
 514
 515   if (str->type_name != sym->type_name)
 516     {
 517       if (str->type_name)
 518         symbol_type_set (sym, str->type_name, str->type_location);
 519       else
 520         symbol_type_set (str, sym->type_name, sym->type_location);
 521     }
 522
 523
 524   for (int i = 0; i < CODE_PROPS_SIZE; ++i)
 525     if (str->props[i].code)
 526       symbol_code_props_set (sym, i, &str->props[i]);
 527     else if (sym->props[i].code)
 528       symbol_code_props_set (str, i, &sym->props[i]);
 529
 530   if (sym->prec || str->prec)
 531     {
 532       if (str->prec)
 533         symbol_precedence_set (sym, str->prec, str->assoc,
 534                                str->prec_location);
 535       else
 536         symbol_precedence_set (str, sym->prec, sym->assoc,
 537                                sym->prec_location);
 538     }
 539 }
 540
 541 static bool
 542 symbol_check_alias_consistency_processor (void *this,
 543                                           void *null ATTRIBUTE_UNUSED)
 544 {
 545   symbol_check_alias_consistency (this);
 546   return true;
 547 }
 548
 549
 550 /*-------------------------------------------------------------------.
 551 | Assign a symbol number, and write the definition of the token name |
 552 | into FDEFINES.  Put in SYMBOLS.                                    |
 553 `-------------------------------------------------------------------*/
 554
 555 static inline bool
 556 symbol_pack (symbol *this)
 557 {
 558   aver (this->number != NUMBER_UNDEFINED);
 559   if (this->class == nterm_sym)
 560     this->number += ntokens;
 561   else if (this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS)
 562     return true;
 563
 564   symbols[this->number] = this;
 565   return true;
 566 }
 567
 568 static bool
 569 symbol_pack_processor (void *this, void *null ATTRIBUTE_UNUSED)
 570 {
 571   return symbol_pack (this);
 572 }
 573
 574
 575 static void
 576 user_token_number_redeclaration (int num, symbol *first, symbol *second)
 577 {
 578   /* User token numbers are not assigned during the parsing, but in a
 579      second step, via a traversal of the symbol table sorted on tag.
 580
 581      However, error messages make more sense if we keep the first
 582      declaration first.  */
 583   if (location_cmp (first->location, second->location) > 0)
 584     {
 585       symbol* tmp = first;
 586       first = second;
 587       second = tmp;
 588     }
 589   complain_at (second->location,
 590                _("user token number %d redeclaration for %s"),
 591                num, second->tag);
 592   complain_at (first->location, _("previous declaration for %s"),
 593                first->tag);
 594 }
 595
 596 /*--------------------------------------------------.
 597 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 598 `--------------------------------------------------*/
 599
 600 static inline bool
 601 symbol_translation (symbol *this)
 602 {
 603   /* Non-terminal? */
 604   if (this->class == token_sym
 605       && this->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
 606     {
 607       /* A token which translation has already been set? */
 608       if (token_translations[this->user_token_number] != undeftoken->number)
 609         user_token_number_redeclaration
 610           (this->user_token_number,
 611            symbols[token_translations[this->user_token_number]],
 612            this);
 613
 614       token_translations[this->user_token_number] = this->number;
 615     }
 616
 617   return true;
 618 }
 619
 620 static bool
 621 symbol_translation_processor (void *this, void *null ATTRIBUTE_UNUSED)
 622 {
 623   return symbol_translation (this);
 624 }
 625
 626
 627 /*---------------------------------------.
 628 | Symbol and semantic type hash tables.  |
 629 `---------------------------------------*/
 630
 631 /* Initial capacity of symbol and semantic type hash table.  */
 632 #define HT_INITIAL_CAPACITY 257
 633
 634 static struct hash_table *symbol_table = NULL;
 635 static struct hash_table *semantic_type_table = NULL;
 636
 637 static inline bool
 638 hash_compare_symbol (const symbol *m1, const symbol *m2)
 639 {
 640   /* Since tags are unique, we can compare the pointers themselves.  */
 641   return UNIQSTR_EQ (m1->tag, m2->tag);
 642 }
 643
 644 static inline bool
 645 hash_compare_semantic_type (const semantic_type *m1, const semantic_type *m2)
 646 {
 647   /* Since names are unique, we can compare the pointers themselves.  */
 648   return UNIQSTR_EQ (m1->tag, m2->tag);
 649 }
 650
 651 static bool
 652 hash_symbol_comparator (void const *m1, void const *m2)
 653 {
 654   return hash_compare_symbol (m1, m2);
 655 }
 656
 657 static bool
 658 hash_semantic_type_comparator (void const *m1, void const *m2)
 659 {
 660   return hash_compare_semantic_type (m1, m2);
 661 }
 662
 663 static inline size_t
 664 hash_symbol (const symbol *m, size_t tablesize)
 665 {
 666   /* Since tags are unique, we can hash the pointer itself.  */
 667   return ((uintptr_t) m->tag) % tablesize;
 668 }
 669
 670 static inline size_t
 671 hash_semantic_type (const semantic_type *m, size_t tablesize)
 672 {
 673   /* Since names are unique, we can hash the pointer itself.  */
 674   return ((uintptr_t) m->tag) % tablesize;
 675 }
 676
 677 static size_t
 678 hash_symbol_hasher (void const *m, size_t tablesize)
 679 {
 680   return hash_symbol (m, tablesize);
 681 }
 682
 683 static size_t
 684 hash_semantic_type_hasher (void const *m, size_t tablesize)
 685 {
 686   return hash_semantic_type (m, tablesize);
 687 }
 688
 689 /*-------------------------------.
 690 | Create the symbol hash table.  |
 691 `-------------------------------*/
 692
 693 void
 694 symbols_new (void)
 695 {
 696   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 697                                   NULL,
 698                                   hash_symbol_hasher,
 699                                   hash_symbol_comparator,
 700                                   free);
 701   semantic_type_table = hash_initialize (HT_INITIAL_CAPACITY,
 702                                          NULL,
 703                                          hash_semantic_type_hasher,
 704                                          hash_semantic_type_comparator,
 705                                          free);
 706 }
 707
 708
 709 /*----------------------------------------------------------------.
 710 | Find the symbol named KEY, and return it.  If it does not exist |
 711 | yet, create it.                                                 |
 712 `----------------------------------------------------------------*/
 713
 714 symbol *
 715 symbol_from_uniqstr (const uniqstr key, location loc)
 716 {
 717   symbol probe;
 718   symbol *entry;
 719
 720   probe.tag = key;
 721   entry = hash_lookup (symbol_table, &probe);
 722
 723   if (!entry)
 724     {
 725       /* First insertion in the hash. */
 726       aver (!symbols_sorted);
 727       entry = symbol_new (key, loc);
 728       if (!hash_insert (symbol_table, entry))
 729         xalloc_die ();
 730     }
 731   return entry;
 732 }
 733
 734
 735 /*-----------------------------------------------------------------------.
 736 | Find the semantic type named KEY, and return it.  If it does not exist |
 737 | yet, create it.                                                        |
 738 `-----------------------------------------------------------------------*/
 739
 740 semantic_type *
 741 semantic_type_from_uniqstr (const uniqstr key, const location *loc)
 742 {
 743   semantic_type probe;
 744   semantic_type *entry;
 745
 746   probe.tag = key;
 747   entry = hash_lookup (semantic_type_table, &probe);
 748
 749   if (!entry)
 750     {
 751       /* First insertion in the hash. */
 752       entry = semantic_type_new (key, loc);
 753       if (!hash_insert (semantic_type_table, entry))
 754         xalloc_die ();
 755     }
 756   return entry;
 757 }
 758
 759
 760 /*----------------------------------------------------------------.
 761 | Find the symbol named KEY, and return it.  If it does not exist |
 762 | yet, create it.                                                 |
 763 `----------------------------------------------------------------*/
 764
 765 symbol *
 766 symbol_get (const char *key, location loc)
 767 {
 768   return symbol_from_uniqstr (uniqstr_new (key), loc);
 769 }
 770
 771
 772 /*-----------------------------------------------------------------------.
 773 | Find the semantic type named KEY, and return it.  If it does not exist |
 774 | yet, create it.                                                        |
 775 `-----------------------------------------------------------------------*/
 776
 777 semantic_type *
 778 semantic_type_get (const char *key, const location *loc)
 779 {
 780   return semantic_type_from_uniqstr (uniqstr_new (key), loc);
 781 }
 782
 783
 784 /*------------------------------------------------------------------.
 785 | Generate a dummy nonterminal, whose name cannot conflict with the |
 786 | user's names.                                                     |
 787 `------------------------------------------------------------------*/
 788
 789 symbol *
 790 dummy_symbol_get (location loc)
 791 {
 792   /* Incremented for each generated symbol.  */
 793   static int dummy_count = 0;
 794   static char buf[256];
 795
 796   symbol *sym;
 797
 798   sprintf (buf, "$@%d", ++dummy_count);
 799   sym = symbol_get (buf, loc);
 800   sym->class = nterm_sym;
 801   sym->number = nvars++;
 802   return sym;
 803 }
 804
 805 bool
 806 symbol_is_dummy (const symbol *sym)
 807 {
 808   return sym->tag[0] == '@' || (sym->tag[0] == '$' && sym->tag[1] == '@');
 809 }
 810
 811 /*-------------------.
 812 | Free the symbols.  |
 813 `-------------------*/
 814
 815 void
 816 symbols_free (void)
 817 {
 818   hash_free (symbol_table);
 819   hash_free (semantic_type_table);
 820   free (symbols);
 821   free (symbols_sorted);
 822 }
 823
 824
 825 /*---------------------------------------------------------------.
 826 | Look for undefined symbols, report an error, and consider them |
 827 | terminals.                                                     |
 828 `---------------------------------------------------------------*/
 829
 830 static int
 831 symbols_cmp (symbol const *a, symbol const *b)
 832 {
 833   return strcmp (a->tag, b->tag);
 834 }
 835
 836 static int
 837 symbols_cmp_qsort (void const *a, void const *b)
 838 {
 839   return symbols_cmp (*(symbol * const *)a, *(symbol * const *)b);
 840 }
 841
 842 static void
 843 symbols_do (Hash_processor processor, void *processor_data,
 844             struct hash_table *table, symbol **sorted)
 845 {
 846   size_t count = hash_get_n_entries (table);
 847   if (!sorted)
 848     {
 849       sorted = xnmalloc (count, sizeof *sorted);
 850       hash_get_entries (table, (void**)sorted, count);
 851       qsort (sorted, count, sizeof *sorted, symbols_cmp_qsort);
 852     }
 853   {
 854     size_t i;
 855     for (i = 0; i < count; ++i)
 856       processor (sorted[i], processor_data);
 857   }
 858 }
 859
 860 /*--------------------------------------------------------------.
 861 | Check that all the symbols are defined.  Report any undefined |
 862 | symbols and consider them nonterminals.                       |
 863 `--------------------------------------------------------------*/
 864
 865 void
 866 symbols_check_defined (void)
 867 {
 868   symbols_do (symbol_check_defined_processor, NULL,
 869               symbol_table, symbols_sorted);
 870   symbols_do (semantic_type_check_defined_processor, NULL,
 871               semantic_type_table, semantic_types_sorted);
 872 }
 873
 874 /*------------------------------------------------------------------.
 875 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 876 | number.                                                           |
 877 `------------------------------------------------------------------*/
 878
 879 static void
 880 symbols_token_translations_init (void)
 881 {
 882   bool num_256_available_p = true;
 883   int i;
 884
 885   /* Find the highest user token number, and whether 256, the POSIX
 886      preferred user token number for the error token, is used.  */
 887   max_user_token_number = 0;
 888   for (i = 0; i < ntokens; ++i)
 889     {
 890       symbol *this = symbols[i];
 891       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 892         {
 893           if (this->user_token_number > max_user_token_number)
 894             max_user_token_number = this->user_token_number;
 895           if (this->user_token_number == 256)
 896             num_256_available_p = false;
 897         }
 898     }
 899
 900   /* If 256 is not used, assign it to error, to follow POSIX.  */
 901   if (num_256_available_p
 902       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 903     errtoken->user_token_number = 256;
 904
 905   /* Set the missing user numbers. */
 906   if (max_user_token_number < 256)
 907     max_user_token_number = 256;
 908
 909   for (i = 0; i < ntokens; ++i)
 910     {
 911       symbol *this = symbols[i];
 912       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 913         this->user_token_number = ++max_user_token_number;
 914       if (this->user_token_number > max_user_token_number)
 915         max_user_token_number = this->user_token_number;
 916     }
 917
 918   token_translations = xnmalloc (max_user_token_number + 1,
 919                                  sizeof *token_translations);
 920
 921   /* Initialize all entries for literal tokens to the internal token
 922      number for $undefined, which represents all invalid inputs.  */
 923   for (i = 0; i < max_user_token_number + 1; i++)
 924     token_translations[i] = undeftoken->number;
 925   symbols_do (symbol_translation_processor, NULL,
 926               symbol_table, symbols_sorted);
 927 }
 928
 929
 930 /*----------------------------------------------------------------.
 931 | Assign symbol numbers, and write definition of token names into |
 932 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 933 `----------------------------------------------------------------*/
 934
 935 void
 936 symbols_pack (void)
 937 {
 938   symbols_do (symbol_check_alias_consistency_processor, NULL,
 939               symbol_table, symbols_sorted);
 940
 941   symbols = xcalloc (nsyms, sizeof *symbols);
 942   symbols_do (symbol_pack_processor, NULL, symbol_table, symbols_sorted);
 943
 944   /* Aliases leave empty slots in symbols, so remove them.  */
 945   {
 946     int writei;
 947     int readi;
 948     int nsyms_old = nsyms;
 949     for (writei = 0, readi = 0; readi < nsyms_old; readi += 1)
 950       {
 951         if (symbols[readi] == NULL)
 952           {
 953             nsyms -= 1;
 954             ntokens -= 1;
 955           }
 956         else
 957           {
 958             symbols[writei] = symbols[readi];
 959             symbols[writei]->number = writei;
 960             if (symbols[writei]->alias)
 961               symbols[writei]->alias->number = writei;
 962             writei += 1;
 963           }
 964       }
 965   }
 966   symbols = xnrealloc (symbols, nsyms, sizeof *symbols);
 967
 968   symbols_token_translations_init ();
 969
 970   if (startsymbol->class == unknown_sym)
 971     fatal_at (startsymbol_location,
 972               _("the start symbol %s is undefined"),
 973               startsymbol->tag);
 974   else if (startsymbol->class == token_sym)
 975     fatal_at (startsymbol_location,
 976               _("the start symbol %s is a token"),
 977               startsymbol->tag);
 978 }
 979
 980
 981 /*--------------------------------------------------.
 982 | Set default tagged/tagless %destructor/%printer.  |
 983 `--------------------------------------------------*/
 984
 985 void
 986 default_tagged_code_props_set (code_props_type kind, code_props const *code)
 987 {
 988   if (default_tagged_code_props[kind].code)
 989     {
 990       complain_at (code->location,
 991                    _("redeclaration for default tagged %s"),
 992                    code_props_type_string (kind));
 993       complain_at (default_tagged_code_props[kind].location,
 994                    _("previous declaration"));
 995     }
 996   default_tagged_code_props[kind] = *code;
 997 }
 998
 999 void
1000 default_tagless_code_props_set (code_props_type kind, code_props const *code)
1001 {
1002   if (default_tagless_code_props[kind].code)
1003     {
1004       complain_at (code->location,
1005                    _("redeclaration for default tagless %s"),
1006                    code_props_type_string (kind));
1007       complain_at (default_tagless_code_props[kind].location,
1008                    _("previous declaration"));
1009     }
1010   default_tagless_code_props[kind] = *code;
1011 }