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