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