src/symtab.c

   1 /* Symbol table manager for Bison,
   2    Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "quotearg.h"
  24 #include "hash.h"
  25 #include "complain.h"
  26 #include "symtab.h"
  27 #include "gram.h"
  28
  29 /*------------------------.
  30 | Distinguished symbols.  |
  31 `------------------------*/
  32
  33 symbol_t *errtoken = NULL;
  34 symbol_t *undeftoken = NULL;
  35 symbol_t *eoftoken = NULL;
  36 symbol_t *axiom = NULL;
  37 symbol_t *startsymbol = NULL;
  38 location_t startsymbol_location;
  39
  40 /*---------------------------------.
  41 | Create a new symbol, named TAG.  |
  42 `---------------------------------*/
  43
  44 static symbol_t *
  45 symbol_new (const char *tag, location_t location)
  46 {
  47   symbol_t *res = XMALLOC (symbol_t, 1);
  48
  49   res->tag = xstrdup (tag);
  50   res->type_name = NULL;
  51   res->destructor = NULL;
  52   res->location = location;
  53   res->number = NUMBER_UNDEFINED;
  54   res->prec = 0;
  55   res->assoc = right_assoc;
  56   res->user_token_number = USER_NUMBER_UNDEFINED;
  57   res->alias = NULL;
  58   res->class = unknown_sym;
  59
  60   nsyms++;
  61   return res;
  62 }
  63
  64
  65 /*-----------------------------------------------------------------.
  66 | Return the tag of this SYMBOL in a printable form.  Warning: use |
  67 | the first QUOTEARG slot: 0.                                      |
  68 `-----------------------------------------------------------------*/
  69
  70 const char *
  71 symbol_tag_get (symbol_t *symbol)
  72 {
  73   return quotearg_style (escape_quoting_style, symbol->tag);
  74 }
  75
  76
  77 /*------------------------------------------------------------.
  78 | Return the tag of this SYMBOL in a printable form.  Use the |
  79 | QUOTEARG slot number N.                                     |
  80 `------------------------------------------------------------*/
  81
  82 const char *
  83 symbol_tag_get_n (symbol_t *symbol, int n)
  84 {
  85   return quotearg_n_style (n, escape_quoting_style, symbol->tag);
  86 }
  87
  88
  89 /*-------------------------------.
  90 | Print the tag of this SYMBOL.  |
  91 `-------------------------------*/
  92
  93 void
  94 symbol_tag_print (symbol_t *symbol, FILE *out)
  95 {
  96   fputs (symbol_tag_get (symbol), out);
  97 }
  98
  99
 100 /*------------------------------------------------------------------.
 101 | Set the TYPE_NAME associated to SYMBOL.  Does nothing if passed 0 |
 102 | as TYPE_NAME.                                                     |
 103 `------------------------------------------------------------------*/
 104
 105 void
 106 symbol_type_set (symbol_t *symbol, location_t location, char *type_name)
 107 {
 108   if (type_name)
 109     {
 110       if (symbol->type_name)
 111         complain_at (location,
 112                      _("type redeclaration for %s"), symbol_tag_get (symbol));
 113       symbol->type_name = type_name;
 114     }
 115 }
 116
 117
 118 /*-------------------------------------------------------------------.
 119 | Set the DESTRUCTOR associated to SYMBOL.  Does nothing if passed 0 |
 120 | as DESTRUCTOR.                                                      |
 121 `-------------------------------------------------------------------*/
 122
 123 void
 124 symbol_destructor_set (symbol_t *symbol, location_t location, char *destructor)
 125 {
 126   if (destructor)
 127     {
 128       if (symbol->destructor)
 129         complain_at (location,
 130                      _("destructor redeclaration for %s"),
 131                      symbol_tag_get (symbol));
 132       symbol->destructor = destructor;
 133     }
 134 }
 135
 136
 137 /*------------------------------------------------------------------.
 138 | Set the PRECEDENCE associated to SYMBOL.  Does nothing if invoked |
 139 | with UNDEF_ASSOC as ASSOC.                                        |
 140 `------------------------------------------------------------------*/
 141
 142 void
 143 symbol_precedence_set (symbol_t *symbol, location_t location,
 144                        int prec, associativity assoc)
 145 {
 146   if (assoc != undef_assoc)
 147     {
 148       if (symbol->prec != 0)
 149         complain_at (location,
 150                      _("redefining precedence of %s"),
 151                      symbol_tag_get (symbol));
 152       symbol->prec = prec;
 153       symbol->assoc = assoc;
 154     }
 155
 156   /* Only terminals have a precedence. */
 157   symbol_class_set (symbol, token_sym);
 158 }
 159
 160
 161 /*-------------------------------------.
 162 | Set the CLASS associated to SYMBOL.  |
 163 `-------------------------------------*/
 164
 165 void
 166 symbol_class_set (symbol_t *symbol, symbol_class class)
 167 {
 168   if (symbol->class != unknown_sym && symbol->class != class)
 169     complain (_("symbol %s redefined"), symbol_tag_get (symbol));
 170
 171   if (class == nterm_sym && symbol->class != nterm_sym)
 172     symbol->number = nvars++;
 173   else if (class == token_sym && symbol->number == NUMBER_UNDEFINED)
 174     symbol->number = ntokens++;
 175
 176   symbol->class = class;
 177 }
 178
 179
 180 /*-------------------------------------------------.
 181 | Set the USER_TOKEN_NUMBER associated to SYMBOL.  |
 182 `-------------------------------------------------*/
 183
 184 void
 185 symbol_user_token_number_set (symbol_t *symbol, int user_token_number)
 186 {
 187   assert (symbol->class == token_sym);
 188
 189   if (symbol->user_token_number != USER_NUMBER_UNDEFINED
 190       && symbol->user_token_number != user_token_number)
 191     complain (_("redefining user token number of %s"),
 192               symbol_tag_get (symbol));
 193
 194   symbol->user_token_number = user_token_number;
 195   /* User defined EOF token? */
 196   if (user_token_number == 0)
 197     {
 198       eoftoken = symbol;
 199       eoftoken->number = 0;
 200       /* It is always mapped to 0, so it was already counted in
 201          NTOKENS.  */
 202       --ntokens;
 203     }
 204 }
 205
 206
 207 /*------------.
 208 | Free THIS.  |
 209 `------------*/
 210
 211 static void
 212 symbol_free (symbol_t *this)
 213 {
 214 #if 0
 215   /* This causes crashes because one string can appear more
 216      than once.  */
 217   XFREE (this->type_name);
 218 #endif
 219   XFREE (this->tag);
 220   XFREE (this);
 221 }
 222
 223
 224 /*-----------------------------------------------------------.
 225 | If THIS is not defined, report an error, and consider it a |
 226 | nonterminal.                                               |
 227 `-----------------------------------------------------------*/
 228
 229 static bool
 230 symbol_check_defined (symbol_t *this)
 231 {
 232   if (this->class == unknown_sym)
 233     {
 234       complain_at
 235         (this->location,
 236          _("symbol %s is used, but is not defined as a token and has no rules"),
 237          symbol_tag_get (this));
 238       this->class = nterm_sym;
 239       this->number = nvars++;
 240     }
 241
 242   return TRUE;
 243 }
 244
 245
 246 /*-------------------------------------------------------------------.
 247 | Declare the new SYMBOL.  Make it an alias of SYMVAL, and type them |
 248 | with TYPENAME.                                                     |
 249 `-------------------------------------------------------------------*/
 250
 251 void
 252 symbol_make_alias (symbol_t *symbol, symbol_t *symval)
 253 {
 254   if (symval->alias)
 255     warn (_("symbol `%s' used more than once as a literal string"),
 256           symbol_tag_get (symval));
 257   else if (symbol->alias)
 258     warn (_("symbol `%s' given more than one literal string"),
 259           symbol_tag_get (symbol));
 260   else
 261     {
 262       symval->class = token_sym;
 263       symval->user_token_number = symbol->user_token_number;
 264       symbol->user_token_number = USER_NUMBER_ALIAS;
 265       symval->alias = symbol;
 266       symbol->alias = symval;
 267       /* symbol and symval combined are only one symbol */
 268       nsyms--;
 269       ntokens--;
 270       assert (ntokens == symbol->number || ntokens == symval->number);
 271       symbol->number = symval->number =
 272         (symval->number < symbol->number) ? symval->number : symbol->number;
 273     }
 274 }
 275
 276
 277 /*---------------------------------------------------------.
 278 | Check that THIS, and its alias, have same precedence and |
 279 | associativity.                                           |
 280 `---------------------------------------------------------*/
 281
 282 static bool
 283 symbol_check_alias_consistence (symbol_t *this)
 284 {
 285   /* Check only those who _are_ the aliases. */
 286   if (this->alias && this->user_token_number == USER_NUMBER_ALIAS)
 287     {
 288       if (this->prec != this->alias->prec)
 289         {
 290           if (this->prec != 0 && this->alias->prec != 0)
 291             complain (_("conflicting precedences for %s and %s"),
 292                       symbol_tag_get (this), symbol_tag_get (this->alias));
 293           if (this->prec != 0)
 294             this->alias->prec = this->prec;
 295           else
 296             this->prec = this->alias->prec;
 297         }
 298
 299       if (this->assoc != this->alias->assoc)
 300         {
 301           /* FIXME: For some reason (probably the S/R => keep the S),
 302              the right assoc is chosen has the ``not set''.  This is
 303              not nice, fix this!  */
 304           if (this->assoc != right_assoc
 305               && this->alias->assoc != right_assoc)
 306             complain (_("conflicting associativities for %s and %s"),
 307                       symbol_tag_get (this), symbol_tag_get (this->alias));
 308           if (this->assoc != 0)
 309             this->alias->assoc = this->assoc;
 310           else
 311             this->assoc = this->alias->assoc;
 312         }
 313     }
 314   return TRUE;
 315 }
 316
 317
 318 /*-------------------------------------------------------------------.
 319 | Assign a symbol number, and write the definition of the token name |
 320 | into FDEFINES.  Put in SYMBOLS.                                    |
 321 `-------------------------------------------------------------------*/
 322
 323 static bool
 324 symbol_pack (symbol_t *this)
 325 {
 326   if (this->class == nterm_sym)
 327     {
 328       this->number += ntokens;
 329     }
 330   else if (this->alias)
 331     {
 332       /* This symbol and its alias are a single token defn.
 333          Allocate a tokno, and assign to both check agreement of
 334          prec and assoc fields and make both the same */
 335       if (this->number == NUMBER_UNDEFINED)
 336         {
 337           if (this == eoftoken || this->alias == eoftoken)
 338             this->number = this->alias->number = 0;
 339           else
 340             {
 341               assert (this->alias->number != NUMBER_UNDEFINED);
 342               this->number = this->alias->number;
 343             }
 344         }
 345       /* Do not do processing below for USER_NUMBER_ALIASs.  */
 346       if (this->user_token_number == USER_NUMBER_ALIAS)
 347         return TRUE;
 348     }
 349   else /* this->class == token_sym */
 350     {
 351       assert (this->number != NUMBER_UNDEFINED);
 352     }
 353
 354   symbols[this->number] = this;
 355   return TRUE;
 356 }
 357
 358
 359
 360
 361 /*--------------------------------------------------.
 362 | Put THIS in TOKEN_TRANSLATIONS if it is a token.  |
 363 `--------------------------------------------------*/
 364
 365 static bool
 366 symbol_translation (symbol_t *this)
 367 {
 368   /* Non-terminal? */
 369   if (this->class == token_sym
 370       && this->user_token_number != USER_NUMBER_ALIAS)
 371     {
 372       /* A token which translation has already been set? */
 373       if (token_translations[this->user_token_number] != undeftoken->number)
 374         complain (_("tokens %s and %s both assigned number %d"),
 375                   symbol_tag_get (symbols[token_translations[this->user_token_number]]),
 376                   symbol_tag_get (this), this->user_token_number);
 377
 378       token_translations[this->user_token_number] = this->number;
 379     }
 380
 381   return TRUE;
 382 }
 383
 384
 385 /*----------------------.
 386 | A symbol hash table.  |
 387 `----------------------*/
 388
 389 /* Initial capacity of symbols hash table.  */
 390 #define HT_INITIAL_CAPACITY 257
 391
 392 static struct hash_table *symbol_table = NULL;
 393
 394 static bool
 395 hash_compare_symbol_t (const symbol_t *m1, const symbol_t *m2)
 396 {
 397   return strcmp (m1->tag, m2->tag) ? FALSE : TRUE;
 398 }
 399
 400 static unsigned int
 401 hash_symbol_t (const symbol_t *m, unsigned int tablesize)
 402 {
 403   return hash_string (m->tag, tablesize);
 404 }
 405
 406
 407 /*-------------------------------.
 408 | Create the symbol hash table.  |
 409 `-------------------------------*/
 410
 411 void
 412 symbols_new (void)
 413 {
 414   symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
 415                                   NULL,
 416                                   (Hash_hasher) hash_symbol_t,
 417                                   (Hash_comparator) hash_compare_symbol_t,
 418                                   (Hash_data_freer) symbol_free);
 419 }
 420
 421
 422 /*----------------------------------------------------------------.
 423 | Find the symbol named KEY, and return it.  If it does not exist |
 424 | yet, create it.                                                 |
 425 `----------------------------------------------------------------*/
 426
 427 symbol_t *
 428 getsym (const char *key, location_t location)
 429 {
 430   symbol_t probe;
 431   symbol_t *entry;
 432
 433   (const char *) probe.tag = key;
 434   entry = hash_lookup (symbol_table, &probe);
 435
 436   if (!entry)
 437     {
 438       /* First insertion in the hash. */
 439       entry = symbol_new (key, location);
 440       hash_insert (symbol_table, entry);
 441     }
 442   return entry;
 443 }
 444
 445
 446 /*-------------------.
 447 | Free the symbols.  |
 448 `-------------------*/
 449
 450 void
 451 symbols_free (void)
 452 {
 453   hash_free (symbol_table);
 454 }
 455
 456
 457 /*---------------------------------------------------------------.
 458 | Look for undefined symbols, report an error, and consider them |
 459 | terminals.                                                     |
 460 `---------------------------------------------------------------*/
 461
 462 void
 463 symbols_do (symbol_processor processor, void *processor_data)
 464 {
 465   hash_do_for_each (symbol_table,
 466                     (Hash_processor) processor,
 467                     processor_data);
 468 }
 469
 470
 471 /*--------------------------------------------------------------.
 472 | Check that all the symbols are defined.  Report any undefined |
 473 | symbols and consider them nonterminals.                       |
 474 `--------------------------------------------------------------*/
 475
 476 void
 477 symbols_check_defined (void)
 478 {
 479   symbols_do (symbol_check_defined, NULL);
 480 }
 481
 482 /*------------------------------------------------------------------.
 483 | Set TOKEN_TRANSLATIONS.  Check that no two symbols share the same |
 484 | number.                                                           |
 485 `------------------------------------------------------------------*/
 486
 487 static void
 488 symbols_token_translations_init (void)
 489 {
 490   int num_256_available_p = TRUE;
 491   int i;
 492
 493   /* Find the highest user token number, and whether 256, the POSIX
 494      preferred user token number for the error token, is used.  */
 495   max_user_token_number = 0;
 496   for (i = 0; i < ntokens; ++i)
 497     {
 498       symbol_t *this = symbols[i];
 499       if (this->user_token_number != USER_NUMBER_UNDEFINED)
 500         {
 501           if (this->user_token_number > max_user_token_number)
 502             max_user_token_number = this->user_token_number;
 503           if (this->user_token_number == 256)
 504             num_256_available_p = FALSE;
 505         }
 506     }
 507
 508   /* If 256 is not used, assign it to error, to follow POSIX.  */
 509   if (num_256_available_p
 510       && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
 511     errtoken->user_token_number = 256;
 512
 513   /* Set the missing user numbers. */
 514   if (max_user_token_number < 256)
 515     max_user_token_number = 256;
 516
 517   for (i = 0; i < ntokens; ++i)
 518     {
 519       symbol_t *this = symbols[i];
 520       if (this->user_token_number == USER_NUMBER_UNDEFINED)
 521         this->user_token_number = ++max_user_token_number;
 522       if (this->user_token_number > max_user_token_number)
 523         max_user_token_number = this->user_token_number;
 524     }
 525
 526   token_translations = XCALLOC (symbol_number_t, max_user_token_number + 1);
 527
 528   /* Initialize all entries for literal tokens to 2, the internal
 529      token number for $undefined., which represents all invalid
 530      inputs.  */
 531   for (i = 0; i < max_user_token_number + 1; i++)
 532     token_translations[i] = undeftoken->number;
 533   symbols_do (symbol_translation, NULL);
 534 }
 535
 536
 537 /*----------------------------------------------------------------.
 538 | Assign symbol numbers, and write definition of token names into |
 539 | FDEFINES.  Set up vectors SYMBOL_TABLE, TAGS of symbols.        |
 540 `----------------------------------------------------------------*/
 541
 542 void
 543 symbols_pack (void)
 544 {
 545   symbols = XCALLOC (symbol_t *, nsyms);
 546
 547   symbols_do (symbol_check_alias_consistence, NULL);
 548   symbols_do (symbol_pack, NULL);
 549
 550   symbols_token_translations_init ();
 551
 552   if (startsymbol->class == unknown_sym)
 553     fatal_at (startsymbol_location,
 554               _("the start symbol %s is undefined"),
 555               symbol_tag_get (startsymbol));
 556   else if (startsymbol->class == token_sym)
 557     fatal_at (startsymbol_location,
 558               _("the start symbol %s is a token"),
 559               symbol_tag_get (startsymbol));
 560 }