]>
Commit | Line | Data |
---|---|---|
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 | ||
35 | symbol *errtoken = NULL; | |
36 | symbol *undeftoken = NULL; | |
37 | symbol *endtoken = NULL; | |
38 | symbol *accept = NULL; | |
39 | symbol *startsymbol = NULL; | |
40 | location startsymbol_location; | |
41 | ||
42 | /*---------------------------------. | |
43 | | Create a new symbol, named TAG. | | |
44 | `---------------------------------*/ | |
45 | ||
46 | static symbol * | |
47 | symbol_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 | ||
77 | void | |
78 | symbol_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 | ||
94 | void | |
95 | symbol_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 | ||
112 | void | |
113 | symbol_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 | ||
131 | void | |
132 | symbol_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 | ||
151 | void | |
152 | symbol_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 | ||
170 | void | |
171 | symbol_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 | ||
197 | static void | |
198 | symbol_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 | ||
209 | static bool | |
210 | symbol_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 | ||
231 | void | |
232 | symbol_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 | ||
263 | static bool | |
264 | symbol_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 | ||
303 | static bool | |
304 | symbol_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 | ||
347 | static bool | |
348 | symbol_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 | ||
375 | static struct hash_table *symbol_table = NULL; | |
376 | ||
377 | static bool | |
378 | hash_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 | ||
384 | static unsigned int | |
385 | hash_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 | ||
396 | void | |
397 | symbols_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 | ||
412 | symbol * | |
413 | symbol_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 | ||
438 | symbol * | |
439 | dummy_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 | ||
459 | void | |
460 | symbols_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 | ||
472 | void | |
473 | symbols_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 | ||
486 | void | |
487 | symbols_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 | ||
497 | static void | |
498 | symbols_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 | ||
552 | void | |
553 | symbols_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 | } |