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