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