src/symtab.c

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