1 /* Symbol table manager for Bison,
2 Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
4 This file is part of Bison, the GNU Compiler Compiler.
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)
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.
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. */
28 /*------------------------.
29 | Distinguished symbols. |
30 `------------------------*/
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
;
38 /*---------------------------------.
39 | Create a new symbol, named TAG. |
40 `---------------------------------*/
43 symbol_new (const char *tag
)
45 symbol_t
*res
= XMALLOC (symbol_t
, 1);
47 res
->tag
= xstrdup (tag
);
48 res
->type_name
= NULL
;
49 res
->number
= NUMBER_UNDEFINED
;
51 res
->assoc
= right_assoc
;
52 res
->user_token_number
= USER_NUMBER_UNDEFINED
;
54 res
->class = unknown_sym
;
62 /*-----------------------------------------.
63 | Set the TYPE_NAME associated to SYMBOL. |
64 `-----------------------------------------*/
67 symbol_type_set (symbol_t
*symbol
, char *type_name
)
69 if (symbol
->type_name
)
70 complain (_("type redeclaration for %s"), symbol
->tag
);
71 symbol
->type_name
= type_name
;
75 /*------------------------------------------.
76 | Set the PRECEDENCE associated to SYMBOL. |
77 `------------------------------------------*/
80 symbol_precedence_set (symbol_t
*symbol
,
81 int prec
, associativity assoc
)
83 if (symbol
->prec
!= 0)
84 complain (_("redefining precedence of %s"), symbol
->tag
);
86 symbol
->assoc
= assoc
;
90 /*-------------------------------------.
91 | Set the CLASS associated to SYMBOL. |
92 `-------------------------------------*/
95 symbol_class_set (symbol_t
*symbol
, symbol_class
class)
97 if (symbol
->class != unknown_sym
&& symbol
->class != class)
98 complain (_("symbol %s redefined"), symbol
->tag
);
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
++;
105 symbol
->class = class;
109 /*-------------------------------------------------.
110 | Set the USER_TOKEN_NUMBER associated to SYMBOL. |
111 `-------------------------------------------------*/
114 symbol_user_token_number_set (symbol_t
*symbol
, int user_token_number
)
116 assert (symbol
->class == token_sym
);
118 if (symbol
->user_token_number
!= USER_NUMBER_UNDEFINED
119 && symbol
->user_token_number
!= user_token_number
)
120 complain (_("redefining user token number of %s"), symbol
->tag
);
122 symbol
->user_token_number
= user_token_number
;
123 /* User defined EOF token? */
124 if (user_token_number
== 0)
127 eoftoken
->number
= 0;
128 /* It is always mapped to 0, so it was already counted in
140 symbol_free (symbol_t
*this)
143 /* This causes crashes because one string can appear more
145 XFREE (this->type_name
);
152 /*-----------------------------------------------------------.
153 | If THIS is not defined, report an error, and consider it a |
155 `-----------------------------------------------------------*/
158 symbol_check_defined (symbol_t
*this)
160 if (this->class == unknown_sym
)
163 (_("symbol %s is used, but is not defined as a token and has no rules"),
165 this->class = nterm_sym
;
166 this->number
= nvars
++;
173 /*-------------------------------------------------------------------.
174 | Declare the new SYMBOL. Make it an alias of SYMVAL, and type them |
176 `-------------------------------------------------------------------*/
179 symbol_make_alias (symbol_t
*symbol
, symbol_t
*symval
, char *typename
)
182 warn (_("symbol `%s' used more than once as a literal string"),
184 else if (symbol
->alias
)
185 warn (_("symbol `%s' given more than one literal string"),
189 symval
->class = token_sym
;
190 symval
->type_name
= typename
;
191 symval
->user_token_number
= symbol
->user_token_number
;
192 symbol
->user_token_number
= USER_NUMBER_ALIAS
;
193 symval
->alias
= symbol
;
194 symbol
->alias
= symval
;
195 /* symbol and symval combined are only one symbol */
198 assert (ntokens
== symbol
->number
|| ntokens
== symval
->number
);
199 symbol
->number
= symval
->number
=
200 (symval
->number
< symbol
->number
) ? symval
->number
: symbol
->number
;
205 /*---------------------------------------------------------.
206 | Check that THIS, and its alias, have same precedence and |
208 `---------------------------------------------------------*/
211 symbol_check_alias_consistence (symbol_t
*this)
213 /* Check only those who _are_ the aliases. */
214 if (this->alias
&& this->user_token_number
== USER_NUMBER_ALIAS
)
216 if (this->prec
!= this->alias
->prec
)
218 if (this->prec
!= 0 && this->alias
->prec
!= 0)
219 complain (_("conflicting precedences for %s and %s"),
220 this->tag
, this->alias
->tag
);
222 this->alias
->prec
= this->prec
;
224 this->prec
= this->alias
->prec
;
227 if (this->assoc
!= this->alias
->assoc
)
229 if (this->assoc
!= 0 && this->alias
->assoc
!= 0)
230 complain (_("conflicting assoc values for %s and %s"),
231 this->tag
, this->alias
->tag
);
232 if (this->assoc
!= 0)
233 this->alias
->assoc
= this->assoc
;
235 this->assoc
= this->alias
->assoc
;
242 /*-------------------------------------------------------------------.
243 | Assign a symbol number, and write the definition of the token name |
244 | into FDEFINES. Put in SYMBOLS. |
245 `-------------------------------------------------------------------*/
248 symbol_pack (symbol_t
*this)
250 if (this->class == nterm_sym
)
252 this->number
+= ntokens
;
254 else if (this->alias
)
256 /* This symbol and its alias are a single token defn.
257 Allocate a tokno, and assign to both check agreement of
258 prec and assoc fields and make both the same */
259 if (this->number
== NUMBER_UNDEFINED
)
261 if (this == eoftoken
|| this->alias
== eoftoken
)
262 this->number
= this->alias
->number
= 0;
265 assert (this->alias
->number
!= NUMBER_UNDEFINED
);
266 this->number
= this->alias
->number
;
269 /* Do not do processing below for USER_NUMBER_ALIASs. */
270 if (this->user_token_number
== USER_NUMBER_ALIAS
)
273 else /* this->class == token_sym */
275 assert (this->number
!= NUMBER_UNDEFINED
);
278 symbols
[this->number
] = this;
285 /*--------------------------------------------------.
286 | Put THIS in TOKEN_TRANSLATIONS if it is a token. |
287 `--------------------------------------------------*/
290 symbol_translation (symbol_t
*this)
293 if (this->class == token_sym
294 && this->user_token_number
!= USER_NUMBER_ALIAS
)
296 /* A token which translation has already been set? */
297 if (token_translations
[this->user_token_number
] != undeftoken
->number
)
298 complain (_("tokens %s and %s both assigned number %d"),
299 symbols
[token_translations
[this->user_token_number
]]->tag
,
300 this->tag
, this->user_token_number
);
302 token_translations
[this->user_token_number
] = this->number
;
309 /*----------------------.
310 | A symbol hash table. |
311 `----------------------*/
313 /* Initial capacity of symbols hash table. */
314 #define HT_INITIAL_CAPACITY 257
316 static struct hash_table
*symbol_table
= NULL
;
319 hash_compare_symbol_t (const symbol_t
*m1
, const symbol_t
*m2
)
321 return strcmp (m1
->tag
, m2
->tag
) ? FALSE
: TRUE
;
325 hash_symbol_t (const symbol_t
*m
, unsigned int tablesize
)
327 return hash_string (m
->tag
, tablesize
);
331 /*-------------------------------.
332 | Create the symbol hash table. |
333 `-------------------------------*/
338 symbol_table
= hash_initialize (HT_INITIAL_CAPACITY
,
340 (Hash_hasher
) hash_symbol_t
,
341 (Hash_comparator
) hash_compare_symbol_t
,
342 (Hash_data_freer
) symbol_free
);
346 /*----------------------------------------------------------------.
347 | Find the symbol named KEY, and return it. If it does not exist |
349 `----------------------------------------------------------------*/
352 getsym (const char *key
)
357 (const char *) probe
.tag
= key
;
358 entry
= hash_lookup (symbol_table
, &probe
);
362 /* First insertion in the hash. */
363 entry
= symbol_new (key
);
364 hash_insert (symbol_table
, entry
);
370 /*-------------------.
371 | Free the symbols. |
372 `-------------------*/
377 hash_free (symbol_table
);
381 /*---------------------------------------------------------------.
382 | Look for undefined symbols, report an error, and consider them |
384 `---------------------------------------------------------------*/
387 symbols_do (symbol_processor processor
, void *processor_data
)
389 hash_do_for_each (symbol_table
,
390 (Hash_processor
) processor
,
395 /*--------------------------------------------------------------.
396 | Check that all the symbols are defined. Report any undefined |
397 | symbols and consider them nonterminals. |
398 `--------------------------------------------------------------*/
401 symbols_check_defined (void)
403 symbols_do (symbol_check_defined
, NULL
);
406 /*------------------------------------------------------------------.
407 | Set TOKEN_TRANSLATIONS. Check that no two symbols share the same |
409 `------------------------------------------------------------------*/
412 symbols_token_translations_init (void)
414 int num_256_available_p
= TRUE
;
417 /* Find the highest user token number, and whether 256, the POSIX
418 preferred user token number for the error token, is used. */
419 max_user_token_number
= 0;
420 for (i
= 0; i
< ntokens
; ++i
)
422 symbol_t
*this = symbols
[i
];
423 if (this->user_token_number
!= USER_NUMBER_UNDEFINED
)
425 if (this->user_token_number
> max_user_token_number
)
426 max_user_token_number
= this->user_token_number
;
427 if (this->user_token_number
== 256)
428 num_256_available_p
= FALSE
;
432 /* If 256 is not used, assign it to error, to follow POSIX. */
433 if (num_256_available_p
434 && errtoken
->user_token_number
== USER_NUMBER_UNDEFINED
)
435 errtoken
->user_token_number
= 256;
437 /* Set the missing user numbers. */
438 if (max_user_token_number
< 256)
439 max_user_token_number
= 256;
441 for (i
= 0; i
< ntokens
; ++i
)
443 symbol_t
*this = symbols
[i
];
444 if (this->user_token_number
== USER_NUMBER_UNDEFINED
)
445 this->user_token_number
= ++max_user_token_number
;
446 if (this->user_token_number
> max_user_token_number
)
447 max_user_token_number
= this->user_token_number
;
450 token_translations
= XCALLOC (symbol_number_t
, max_user_token_number
+ 1);
452 /* Initialize all entries for literal tokens to 2, the internal
453 token number for $undefined., which represents all invalid
455 for (i
= 0; i
< max_user_token_number
+ 1; i
++)
456 token_translations
[i
] = undeftoken
->number
;
457 symbols_do (symbol_translation
, NULL
);
461 /*----------------------------------------------------------------.
462 | Assign symbol numbers, and write definition of token names into |
463 | FDEFINES. Set up vectors SYMBOL_TABLE, TAGS of symbols. |
464 `----------------------------------------------------------------*/
469 symbols
= XCALLOC (symbol_t
*, nsyms
);
471 symbols_do (symbol_check_alias_consistence
, NULL
);
472 symbols_do (symbol_pack
, NULL
);
474 symbols_token_translations_init ();
476 if (startsymbol
->class == unknown_sym
)
477 fatal (_("the start symbol %s is undefined"), startsymbol
->tag
);
478 else if (startsymbol
->class == token_sym
)
479 fatal (_("the start symbol %s is a token"), startsymbol
->tag
);