]> git.saurik.com Git - bison.git/blob - src/symtab.c
grammar: warn about unused precedence for symbols
[bison.git] / src / symtab.c
1 /* Symbol table manager for Bison.
2
3 Copyright (C) 1984, 1989, 2000-2002, 2004-2013 Free Software
4 Foundation, Inc.
5
6 This file is part of Bison, the GNU Compiler Compiler.
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20
21 #include <config.h>
22 #include "system.h"
23
24 #include <hash.h>
25
26 #include "complain.h"
27 #include "gram.h"
28 #include "symtab.h"
29
30 /*-------------------------------------------------------------------.
31 | Symbols sorted by tag. Allocated by the first invocation of |
32 | symbols_do, after which no more symbols should be created. |
33 `-------------------------------------------------------------------*/
34
35 static symbol **symbols_sorted = NULL;
36 static symbol **semantic_types_sorted = NULL;
37
38 /*------------------------.
39 | Distinguished symbols. |
40 `------------------------*/
41
42 symbol *errtoken = NULL;
43 symbol *undeftoken = NULL;
44 symbol *endtoken = NULL;
45 symbol *accept = NULL;
46 symbol *startsymbol = NULL;
47 location startsymbol_location;
48
49 /*---------------------------.
50 | Precedence relation graph. |
51 `---------------------------*/
52
53 static symgraph **prec_nodes;
54
55 /*---------------------------------.
56 | Create a new symbol, named TAG. |
57 `---------------------------------*/
58
59 static symbol *
60 symbol_new (uniqstr tag, location loc)
61 {
62 symbol *res = xmalloc (sizeof *res);
63 uniqstr_assert (tag);
64
65 /* If the tag is not a string (starts with a double quote), check
66 that it is valid for Yacc. */
67 if (tag[0] != '\"' && tag[0] != '\'' && strchr (tag, '-'))
68 complain (&loc, Wyacc,
69 _("POSIX Yacc forbids dashes in symbol names: %s"), tag);
70
71 res->tag = tag;
72 res->location = loc;
73
74 res->type_name = NULL;
75 {
76 int i;
77 for (i = 0; i < CODE_PROPS_SIZE; ++i)
78 code_props_none_init (&res->props[i]);
79 }
80
81 res->number = NUMBER_UNDEFINED;
82 res->prec = 0;
83 res->assoc = undef_assoc;
84 res->user_token_number = USER_NUMBER_UNDEFINED;
85
86 res->alias = NULL;
87 res->class = unknown_sym;
88 res->status = undeclared;
89
90 if (nsyms == SYMBOL_NUMBER_MAXIMUM)
91 complain (NULL, fatal, _("too many symbols in input grammar (limit is %d)"),
92 SYMBOL_NUMBER_MAXIMUM);
93 nsyms++;
94 return res;
95 }
96
97 char const *
98 code_props_type_string (code_props_type kind)
99 {
100 switch (kind)
101 {
102 case destructor:
103 return "%destructor";
104 case printer:
105 return "%printer";
106 }
107 assert (0);
108 }
109
110 /*----------------------------------------.
111 | Create a new semantic type, named TAG. |
112 `----------------------------------------*/
113
114 static semantic_type *
115 semantic_type_new (uniqstr tag, const location *loc)
116 {
117 semantic_type *res = xmalloc (sizeof *res);
118
119 uniqstr_assert (tag);
120 res->tag = tag;
121 res->location = loc ? *loc : empty_location;
122 res->status = undeclared;
123 {
124 int i;
125 for (i = 0; i < CODE_PROPS_SIZE; ++i)
126 code_props_none_init (&res->props[i]);
127 }
128
129 return res;
130 }
131
132
133 /*-----------------.
134 | Print a symbol. |
135 `-----------------*/
136
137 #define SYMBOL_ATTR_PRINT(Attr) \
138 if (s->Attr) \
139 fprintf (f, " %s { %s }", #Attr, s->Attr)
140
141 #define SYMBOL_CODE_PRINT(Attr) \
142 if (s->props[Attr].code) \
143 fprintf (f, " %s { %s }", #Attr, s->props[Attr].code)
144
145 void
146 symbol_print (symbol const *s, FILE *f)
147 {
148 if (s)
149 {
150 fprintf (f, "\"%s\"", s->tag);
151 SYMBOL_ATTR_PRINT (type_name);
152 SYMBOL_CODE_PRINT (destructor);
153 SYMBOL_CODE_PRINT (printer);
154 }
155 else
156 fprintf (f, "<NULL>");
157 }
158
159 #undef SYMBOL_ATTR_PRINT
160 #undef SYMBOL_CODE_PRINT
161
162
163 /*----------------------------------.
164 | Whether S is a valid identifier. |
165 `----------------------------------*/
166
167 static bool
168 is_identifier (uniqstr s)
169 {
170 static char const alphanum[26 + 26 + 1 + 10] =
171 "abcdefghijklmnopqrstuvwxyz"
172 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
173 "_"
174 "0123456789";
175 if (!s || ! memchr (alphanum, *s, sizeof alphanum - 10))
176 return false;
177 for (++s; *s; ++s)
178 if (! memchr (alphanum, *s, sizeof alphanum))
179 return false;
180 return true;
181 }
182
183
184 /*-----------------------------------------------.
185 | Get the identifier associated to this symbol. |
186 `-----------------------------------------------*/
187 uniqstr
188 symbol_id_get (symbol const *sym)
189 {
190 aver (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS);
191 if (sym->alias)
192 sym = sym->alias;
193 return is_identifier (sym->tag) ? sym->tag : 0;
194 }
195
196
197 /*------------------------------------------------------------------.
198 | Complain that S's WHAT is redeclared at SECOND, and was first set |
199 | at FIRST. |
200 `------------------------------------------------------------------*/
201
202 static void
203 symbol_redeclaration (symbol *s, const char *what, location first,
204 location second)
205 {
206 unsigned i = 0;
207 complain_indent (&second, complaint, &i,
208 _("%s redeclaration for %s"), what, s->tag);
209 i += SUB_INDENT;
210 complain_indent (&first, complaint, &i,
211 _("previous declaration"));
212 }
213
214 static void
215 semantic_type_redeclaration (semantic_type *s, const char *what, location first,
216 location second)
217 {
218 unsigned i = 0;
219 complain_indent (&second, complaint, &i,
220 _("%s redeclaration for <%s>"), what, s->tag);
221 i += SUB_INDENT;
222 complain_indent (&first, complaint, &i,
223 _("previous declaration"));
224 }
225
226
227
228 /*-----------------------------------------------------------------.
229 | Set the TYPE_NAME associated with SYM. Does nothing if passed 0 |
230 | as TYPE_NAME. |
231 `-----------------------------------------------------------------*/
232
233 void
234 symbol_type_set (symbol *sym, uniqstr type_name, location loc)
235 {
236 if (type_name)
237 {
238 if (sym->type_name)
239 symbol_redeclaration (sym, "%type", sym->type_location, loc);
240 uniqstr_assert (type_name);
241 sym->type_name = type_name;
242 sym->type_location = loc;
243 }
244 }
245
246 /*--------------------------------------------------------.
247 | Set the DESTRUCTOR or PRINTER associated with the SYM. |
248 `--------------------------------------------------------*/
249
250 void
251 symbol_code_props_set (symbol *sym, code_props_type kind,
252 code_props const *code)
253 {
254 if (sym->props[kind].code)
255 symbol_redeclaration (sym, code_props_type_string (kind),
256 sym->props[kind].location,
257 code->location);
258 sym->props[kind] = *code;
259 }
260
261 /*-----------------------------------------------------.
262 | Set the DESTRUCTOR or PRINTER associated with TYPE. |
263 `-----------------------------------------------------*/
264
265 void
266 semantic_type_code_props_set (semantic_type *type,
267 code_props_type kind,
268 code_props const *code)
269 {
270 if (type->props[kind].code)
271 semantic_type_redeclaration (type, code_props_type_string (kind),
272 type->props[kind].location,
273 code->location);
274 type->props[kind] = *code;
275 }
276
277 /*---------------------------------------------------.
278 | Get the computed %destructor or %printer for SYM. |
279 `---------------------------------------------------*/
280
281 code_props *
282 symbol_code_props_get (symbol *sym, code_props_type kind)
283 {
284 /* Per-symbol code props. */
285 if (sym->props[kind].code)
286 return &sym->props[kind];
287
288 /* Per-type code props. */
289 if (sym->type_name)
290 {
291 code_props *code =
292 &semantic_type_get (sym->type_name, NULL)->props[kind];
293 if (code->code)
294 return code;
295 }
296
297 /* Apply default code props's only to user-defined symbols. */
298 if (sym->tag[0] != '$' && sym != errtoken)
299 {
300 code_props *code =
301 &semantic_type_get (sym->type_name ? "*" : "", NULL)->props[kind];
302 if (code->code)
303 return code;
304 }
305 return &code_props_none;
306 }
307
308 /*-----------------------------------------------------------------.
309 | Set the PRECEDENCE associated with SYM. Does nothing if invoked |
310 | with UNDEF_ASSOC as ASSOC. |
311 `-----------------------------------------------------------------*/
312
313 void
314 symbol_precedence_set (symbol *sym, int prec, assoc a, location loc)
315 {
316 if (a != undef_assoc)
317 {
318 if (sym->prec != 0)
319 symbol_redeclaration (sym, assoc_to_string (a), sym->prec_location,
320 loc);
321 sym->prec = prec;
322 sym->assoc = a;
323 sym->prec_location = loc;
324 }
325
326 /* Only terminals have a precedence. */
327 symbol_class_set (sym, token_sym, loc, false);
328 }
329
330
331 /*------------------------------------.
332 | Set the CLASS associated with SYM. |
333 `------------------------------------*/
334
335 void
336 symbol_class_set (symbol *sym, symbol_class class, location loc, bool declaring)
337 {
338 bool warned = false;
339 if (sym->class != unknown_sym && sym->class != class)
340 {
341 complain (&loc, complaint, _("symbol %s redefined"), sym->tag);
342 /* Don't report both "redefined" and "redeclared". */
343 warned = true;
344 }
345
346 if (class == nterm_sym && sym->class != nterm_sym)
347 sym->number = nvars++;
348 else if (class == token_sym && sym->number == NUMBER_UNDEFINED)
349 sym->number = ntokens++;
350
351 sym->class = class;
352
353 if (declaring)
354 {
355 if (sym->status == declared && !warned)
356 complain (&loc, Wother, _("symbol %s redeclared"), sym->tag);
357 sym->status = declared;
358 }
359 }
360
361
362 /*------------------------------------------------.
363 | Set the USER_TOKEN_NUMBER associated with SYM. |
364 `------------------------------------------------*/
365
366 void
367 symbol_user_token_number_set (symbol *sym, int user_token_number, location loc)
368 {
369 int *user_token_numberp;
370
371 if (sym->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
372 user_token_numberp = &sym->user_token_number;
373 else
374 user_token_numberp = &sym->alias->user_token_number;
375 if (*user_token_numberp != USER_NUMBER_UNDEFINED
376 && *user_token_numberp != user_token_number)
377 complain (&loc, complaint, _("redefining user token number of %s"),
378 sym->tag);
379
380 *user_token_numberp = user_token_number;
381 /* User defined $end token? */
382 if (user_token_number == 0)
383 {
384 endtoken = sym;
385 /* It is always mapped to 0, so it was already counted in
386 NTOKENS. */
387 if (endtoken->number != NUMBER_UNDEFINED)
388 --ntokens;
389 endtoken->number = 0;
390 }
391 }
392
393
394 /*----------------------------------------------------------.
395 | If SYM is not defined, report an error, and consider it a |
396 | nonterminal. |
397 `----------------------------------------------------------*/
398
399 static inline bool
400 symbol_check_defined (symbol *sym)
401 {
402 if (sym->class == unknown_sym)
403 {
404 assert (sym->status != declared);
405 complain (&sym->location,
406 sym->status == needed ? complaint : Wother,
407 _("symbol %s is used, but is not defined as a token"
408 " and has no rules"),
409 sym->tag);
410 sym->class = nterm_sym;
411 sym->number = nvars++;
412 }
413
414 {
415 int i;
416 for (i = 0; i < 2; ++i)
417 symbol_code_props_get (sym, i)->is_used = true;
418 }
419
420 /* Set the semantic type status associated to the current symbol to
421 'declared' so that we could check semantic types unnecessary uses. */
422 if (sym->type_name)
423 {
424 semantic_type *sem_type = semantic_type_get (sym->type_name, NULL);
425 if (sem_type)
426 sem_type->status = declared;
427 }
428
429 return true;
430 }
431
432 static inline bool
433 semantic_type_check_defined (semantic_type *sem_type)
434 {
435 /* <*> and <> do not have to be "declared". */
436 if (sem_type->status == declared
437 || !*sem_type->tag
438 || STREQ(sem_type->tag, "*"))
439 {
440 int i;
441 for (i = 0; i < 2; ++i)
442 if (sem_type->props[i].kind != CODE_PROPS_NONE
443 && ! sem_type->props[i].is_used)
444 complain (&sem_type->location, Wother,
445 _("useless %s for type <%s>"),
446 code_props_type_string (i), sem_type->tag);
447 }
448 else
449 complain (&sem_type->location, Wother,
450 _("type <%s> is used, but is not associated to any symbol"),
451 sem_type->tag);
452
453 return true;
454 }
455
456 static bool
457 symbol_check_defined_processor (void *sym, void *null ATTRIBUTE_UNUSED)
458 {
459 return symbol_check_defined (sym);
460 }
461
462 static bool
463 semantic_type_check_defined_processor (void *sem_type,
464 void *null ATTRIBUTE_UNUSED)
465 {
466 return semantic_type_check_defined (sem_type);
467 }
468
469
470 void
471 symbol_make_alias (symbol *sym, symbol *str, location loc)
472 {
473 if (str->alias)
474 complain (&loc, Wother,
475 _("symbol %s used more than once as a literal string"), str->tag);
476 else if (sym->alias)
477 complain (&loc, Wother,
478 _("symbol %s given more than one literal string"), sym->tag);
479 else
480 {
481 str->class = token_sym;
482 str->user_token_number = sym->user_token_number;
483 sym->user_token_number = USER_NUMBER_HAS_STRING_ALIAS;
484 str->alias = sym;
485 sym->alias = str;
486 str->number = sym->number;
487 symbol_type_set (str, sym->type_name, loc);
488 }
489 }
490
491
492 /*---------------------------------------------------------.
493 | Check that THIS, and its alias, have same precedence and |
494 | associativity. |
495 `---------------------------------------------------------*/
496
497 static inline void
498 symbol_check_alias_consistency (symbol *this)
499 {
500 symbol *sym = this;
501 symbol *str = this->alias;
502
503 /* Check only the symbol in the symbol-string pair. */
504 if (!(this->alias
505 && this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS))
506 return;
507
508 if (str->type_name != sym->type_name)
509 {
510 if (str->type_name)
511 symbol_type_set (sym, str->type_name, str->type_location);
512 else
513 symbol_type_set (str, sym->type_name, sym->type_location);
514 }
515
516
517 {
518 int i;
519 for (i = 0; i < CODE_PROPS_SIZE; ++i)
520 if (str->props[i].code)
521 symbol_code_props_set (sym, i, &str->props[i]);
522 else if (sym->props[i].code)
523 symbol_code_props_set (str, i, &sym->props[i]);
524 }
525
526 if (sym->prec || str->prec)
527 {
528 if (str->prec)
529 symbol_precedence_set (sym, str->prec, str->assoc,
530 str->prec_location);
531 else
532 symbol_precedence_set (str, sym->prec, sym->assoc,
533 sym->prec_location);
534 }
535 }
536
537 static bool
538 symbol_check_alias_consistency_processor (void *this,
539 void *null ATTRIBUTE_UNUSED)
540 {
541 symbol_check_alias_consistency (this);
542 return true;
543 }
544
545
546 /*-------------------------------------------------------------------.
547 | Assign a symbol number, and write the definition of the token name |
548 | into FDEFINES. Put in SYMBOLS. |
549 `-------------------------------------------------------------------*/
550
551 static inline bool
552 symbol_pack (symbol *this)
553 {
554 aver (this->number != NUMBER_UNDEFINED);
555 if (this->class == nterm_sym)
556 this->number += ntokens;
557 else if (this->user_token_number == USER_NUMBER_HAS_STRING_ALIAS)
558 return true;
559
560 symbols[this->number] = this;
561 return true;
562 }
563
564 static bool
565 symbol_pack_processor (void *this, void *null ATTRIBUTE_UNUSED)
566 {
567 return symbol_pack (this);
568 }
569
570
571 static void
572 user_token_number_redeclaration (int num, symbol *first, symbol *second)
573 {
574 unsigned i = 0;
575 /* User token numbers are not assigned during the parsing, but in a
576 second step, via a traversal of the symbol table sorted on tag.
577
578 However, error messages make more sense if we keep the first
579 declaration first. */
580 if (location_cmp (first->location, second->location) > 0)
581 {
582 symbol* tmp = first;
583 first = second;
584 second = tmp;
585 }
586 complain_indent (&second->location, complaint, &i,
587 _("user token number %d redeclaration for %s"),
588 num, second->tag);
589 i += SUB_INDENT;
590 complain_indent (&first->location, complaint, &i,
591 _("previous declaration for %s"),
592 first->tag);
593 }
594
595 /*--------------------------------------------------.
596 | Put THIS in TOKEN_TRANSLATIONS if it is a token. |
597 `--------------------------------------------------*/
598
599 static inline bool
600 symbol_translation (symbol *this)
601 {
602 /* Non-terminal? */
603 if (this->class == token_sym
604 && this->user_token_number != USER_NUMBER_HAS_STRING_ALIAS)
605 {
606 /* A token which translation has already been set? */
607 if (token_translations[this->user_token_number] != undeftoken->number)
608 user_token_number_redeclaration
609 (this->user_token_number,
610 symbols[token_translations[this->user_token_number]],
611 this);
612
613 token_translations[this->user_token_number] = this->number;
614 }
615
616 return true;
617 }
618
619 static bool
620 symbol_translation_processor (void *this, void *null ATTRIBUTE_UNUSED)
621 {
622 return symbol_translation (this);
623 }
624
625
626 /*---------------------------------------.
627 | Symbol and semantic type hash tables. |
628 `---------------------------------------*/
629
630 /* Initial capacity of symbol and semantic type hash table. */
631 #define HT_INITIAL_CAPACITY 257
632
633 static struct hash_table *symbol_table = NULL;
634 static struct hash_table *semantic_type_table = NULL;
635
636 static inline bool
637 hash_compare_symbol (const symbol *m1, const symbol *m2)
638 {
639 /* Since tags are unique, we can compare the pointers themselves. */
640 return UNIQSTR_EQ (m1->tag, m2->tag);
641 }
642
643 static inline bool
644 hash_compare_semantic_type (const semantic_type *m1, const semantic_type *m2)
645 {
646 /* Since names are unique, we can compare the pointers themselves. */
647 return UNIQSTR_EQ (m1->tag, m2->tag);
648 }
649
650 static bool
651 hash_symbol_comparator (void const *m1, void const *m2)
652 {
653 return hash_compare_symbol (m1, m2);
654 }
655
656 static bool
657 hash_semantic_type_comparator (void const *m1, void const *m2)
658 {
659 return hash_compare_semantic_type (m1, m2);
660 }
661
662 static inline size_t
663 hash_symbol (const symbol *m, size_t tablesize)
664 {
665 /* Since tags are unique, we can hash the pointer itself. */
666 return ((uintptr_t) m->tag) % tablesize;
667 }
668
669 static inline size_t
670 hash_semantic_type (const semantic_type *m, size_t tablesize)
671 {
672 /* Since names are unique, we can hash the pointer itself. */
673 return ((uintptr_t) m->tag) % tablesize;
674 }
675
676 static size_t
677 hash_symbol_hasher (void const *m, size_t tablesize)
678 {
679 return hash_symbol (m, tablesize);
680 }
681
682 static size_t
683 hash_semantic_type_hasher (void const *m, size_t tablesize)
684 {
685 return hash_semantic_type (m, tablesize);
686 }
687
688 /*-------------------------------.
689 | Create the symbol hash table. |
690 `-------------------------------*/
691
692 void
693 symbols_new (void)
694 {
695 symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
696 NULL,
697 hash_symbol_hasher,
698 hash_symbol_comparator,
699 free);
700 semantic_type_table = hash_initialize (HT_INITIAL_CAPACITY,
701 NULL,
702 hash_semantic_type_hasher,
703 hash_semantic_type_comparator,
704 free);
705 }
706
707
708 /*----------------------------------------------------------------.
709 | Find the symbol named KEY, and return it. If it does not exist |
710 | yet, create it. |
711 `----------------------------------------------------------------*/
712
713 symbol *
714 symbol_from_uniqstr (const uniqstr key, location loc)
715 {
716 symbol probe;
717 symbol *entry;
718
719 probe.tag = key;
720 entry = hash_lookup (symbol_table, &probe);
721
722 if (!entry)
723 {
724 /* First insertion in the hash. */
725 aver (!symbols_sorted);
726 entry = symbol_new (key, loc);
727 if (!hash_insert (symbol_table, entry))
728 xalloc_die ();
729 }
730 return entry;
731 }
732
733
734 /*-----------------------------------------------------------------------.
735 | Find the semantic type named KEY, and return it. If it does not exist |
736 | yet, create it. |
737 `-----------------------------------------------------------------------*/
738
739 semantic_type *
740 semantic_type_from_uniqstr (const uniqstr key, const location *loc)
741 {
742 semantic_type probe;
743 semantic_type *entry;
744
745 probe.tag = key;
746 entry = hash_lookup (semantic_type_table, &probe);
747
748 if (!entry)
749 {
750 /* First insertion in the hash. */
751 entry = semantic_type_new (key, loc);
752 if (!hash_insert (semantic_type_table, entry))
753 xalloc_die ();
754 }
755 return entry;
756 }
757
758
759 /*----------------------------------------------------------------.
760 | Find the symbol named KEY, and return it. If it does not exist |
761 | yet, create it. |
762 `----------------------------------------------------------------*/
763
764 symbol *
765 symbol_get (const char *key, location loc)
766 {
767 return symbol_from_uniqstr (uniqstr_new (key), loc);
768 }
769
770
771 /*-----------------------------------------------------------------------.
772 | Find the semantic type named KEY, and return it. If it does not exist |
773 | yet, create it. |
774 `-----------------------------------------------------------------------*/
775
776 semantic_type *
777 semantic_type_get (const char *key, const location *loc)
778 {
779 return semantic_type_from_uniqstr (uniqstr_new (key), loc);
780 }
781
782
783 /*------------------------------------------------------------------.
784 | Generate a dummy nonterminal, whose name cannot conflict with the |
785 | user's names. |
786 `------------------------------------------------------------------*/
787
788 symbol *
789 dummy_symbol_get (location loc)
790 {
791 /* Incremented for each generated symbol. */
792 static int dummy_count = 0;
793 static char buf[256];
794
795 symbol *sym;
796
797 sprintf (buf, "$@%d", ++dummy_count);
798 sym = symbol_get (buf, loc);
799 sym->class = nterm_sym;
800 sym->number = nvars++;
801 return sym;
802 }
803
804 bool
805 symbol_is_dummy (const symbol *sym)
806 {
807 return sym->tag[0] == '@' || (sym->tag[0] == '$' && sym->tag[1] == '@');
808 }
809
810 /*-------------------.
811 | Free the symbols. |
812 `-------------------*/
813
814 void
815 symbols_free (void)
816 {
817 hash_free (symbol_table);
818 hash_free (semantic_type_table);
819 free (symbols);
820 free (symbols_sorted);
821 free (semantic_types_sorted);
822 }
823
824
825 /*---------------------------------------------------------------.
826 | Look for undefined symbols, report an error, and consider them |
827 | terminals. |
828 `---------------------------------------------------------------*/
829
830 static int
831 symbols_cmp (symbol const *a, symbol const *b)
832 {
833 return strcmp (a->tag, b->tag);
834 }
835
836 static int
837 symbols_cmp_qsort (void const *a, void const *b)
838 {
839 return symbols_cmp (*(symbol * const *)a, *(symbol * const *)b);
840 }
841
842 static void
843 symbols_do (Hash_processor processor, void *processor_data,
844 struct hash_table *table, symbol ***sorted)
845 {
846 size_t count = hash_get_n_entries (table);
847 if (!*sorted)
848 {
849 *sorted = xnmalloc (count, sizeof **sorted);
850 hash_get_entries (table, (void**)*sorted, count);
851 qsort (*sorted, count, sizeof **sorted, symbols_cmp_qsort);
852 }
853 {
854 size_t i;
855 for (i = 0; i < count; ++i)
856 processor ((*sorted)[i], processor_data);
857 }
858 }
859
860 /*--------------------------------------------------------------.
861 | Check that all the symbols are defined. Report any undefined |
862 | symbols and consider them nonterminals. |
863 `--------------------------------------------------------------*/
864
865 void
866 symbols_check_defined (void)
867 {
868 symbols_do (symbol_check_defined_processor, NULL,
869 symbol_table, &symbols_sorted);
870 symbols_do (semantic_type_check_defined_processor, NULL,
871 semantic_type_table, &semantic_types_sorted);
872 }
873
874 /*------------------------------------------------------------------.
875 | Set TOKEN_TRANSLATIONS. Check that no two symbols share the same |
876 | number. |
877 `------------------------------------------------------------------*/
878
879 static void
880 symbols_token_translations_init (void)
881 {
882 bool num_256_available_p = true;
883 int i;
884
885 /* Find the highest user token number, and whether 256, the POSIX
886 preferred user token number for the error token, is used. */
887 max_user_token_number = 0;
888 for (i = 0; i < ntokens; ++i)
889 {
890 symbol *this = symbols[i];
891 if (this->user_token_number != USER_NUMBER_UNDEFINED)
892 {
893 if (this->user_token_number > max_user_token_number)
894 max_user_token_number = this->user_token_number;
895 if (this->user_token_number == 256)
896 num_256_available_p = false;
897 }
898 }
899
900 /* If 256 is not used, assign it to error, to follow POSIX. */
901 if (num_256_available_p
902 && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
903 errtoken->user_token_number = 256;
904
905 /* Set the missing user numbers. */
906 if (max_user_token_number < 256)
907 max_user_token_number = 256;
908
909 for (i = 0; i < ntokens; ++i)
910 {
911 symbol *this = symbols[i];
912 if (this->user_token_number == USER_NUMBER_UNDEFINED)
913 this->user_token_number = ++max_user_token_number;
914 if (this->user_token_number > max_user_token_number)
915 max_user_token_number = this->user_token_number;
916 }
917
918 token_translations = xnmalloc (max_user_token_number + 1,
919 sizeof *token_translations);
920
921 /* Initialize all entries for literal tokens to the internal token
922 number for $undefined, which represents all invalid inputs. */
923 for (i = 0; i < max_user_token_number + 1; i++)
924 token_translations[i] = undeftoken->number;
925 symbols_do (symbol_translation_processor, NULL,
926 symbol_table, &symbols_sorted);
927 }
928
929
930 /*----------------------------------------------------------------.
931 | Assign symbol numbers, and write definition of token names into |
932 | FDEFINES. Set up vectors SYMBOL_TABLE, TAGS of symbols. |
933 `----------------------------------------------------------------*/
934
935 void
936 symbols_pack (void)
937 {
938 symbols_do (symbol_check_alias_consistency_processor, NULL,
939 symbol_table, &symbols_sorted);
940
941 symbols = xcalloc (nsyms, sizeof *symbols);
942 symbols_do (symbol_pack_processor, NULL, symbol_table, &symbols_sorted);
943
944 /* Aliases leave empty slots in symbols, so remove them. */
945 {
946 int writei;
947 int readi;
948 int nsyms_old = nsyms;
949 for (writei = 0, readi = 0; readi < nsyms_old; readi += 1)
950 {
951 if (symbols[readi] == NULL)
952 {
953 nsyms -= 1;
954 ntokens -= 1;
955 }
956 else
957 {
958 symbols[writei] = symbols[readi];
959 symbols[writei]->number = writei;
960 if (symbols[writei]->alias)
961 symbols[writei]->alias->number = writei;
962 writei += 1;
963 }
964 }
965 }
966 symbols = xnrealloc (symbols, nsyms, sizeof *symbols);
967
968 symbols_token_translations_init ();
969
970 if (startsymbol->class == unknown_sym)
971 complain (&startsymbol_location, fatal,
972 _("the start symbol %s is undefined"),
973 startsymbol->tag);
974 else if (startsymbol->class == token_sym)
975 complain (&startsymbol_location, fatal,
976 _("the start symbol %s is a token"),
977 startsymbol->tag);
978 }
979
980 /*---------------------------------.
981 | Initialize relation graph nodes. |
982 `---------------------------------*/
983
984 static void
985 init_prec_nodes (void)
986 {
987 int i;
988 prec_nodes = xcalloc (nsyms, sizeof *prec_nodes);
989 for (i = 0; i < nsyms; ++i)
990 {
991 prec_nodes[i] = xmalloc (sizeof *prec_nodes[i]);
992 symgraph *s = prec_nodes[i];
993 s->id = i;
994 s->succ = 0;
995 s->pred = 0;
996 }
997 }
998
999 /*----------------.
1000 | Create a link. |
1001 `----------------*/
1002
1003 static symgraphlink *
1004 symgraphlink_new (graphid id, symgraphlink *next)
1005 {
1006 symgraphlink *l = xmalloc (sizeof *l);
1007 l->id = id;
1008 l->next = next;
1009 return l;
1010 }
1011
1012
1013 /*------------------------------------------------------------------.
1014 | Register the second symbol of the precedence relation, and return |
1015 | whether this relation is new. Use only in register_precedence. |
1016 `------------------------------------------------------------------*/
1017
1018 static bool
1019 register_precedence_second_symbol (symgraphlink **first, graphid sym)
1020 {
1021 if (!*first || sym < (*first)->id)
1022 *first = symgraphlink_new (sym, *first);
1023 else
1024 {
1025 symgraphlink *slist = *first;
1026
1027 while (slist->next && slist->next->id <= sym)
1028 slist = slist->next;
1029
1030 if (slist->id == sym)
1031 /* Relation already present. */
1032 return false;
1033
1034 slist->next = symgraphlink_new (sym, slist->next);
1035 }
1036 return true;
1037 }
1038
1039 /*------------------------------------------------------------------.
1040 | Register a new relation between symbols as used. The first symbol |
1041 | has a greater precedence than the second one. |
1042 `------------------------------------------------------------------*/
1043
1044 void
1045 register_precedence (graphid first, graphid snd)
1046 {
1047 if (!prec_nodes)
1048 init_prec_nodes ();
1049 register_precedence_second_symbol (&(prec_nodes[first]->succ), snd);
1050 register_precedence_second_symbol (&(prec_nodes[snd]->pred), first);
1051 }
1052
1053
1054 /*--------------------------------------------------.
1055 | Print a warning for unused precedence relations. |
1056 `--------------------------------------------------*/
1057
1058 void
1059 print_precedence_warnings (void)
1060 {
1061 int i;
1062 if (!prec_nodes)
1063 init_prec_nodes ();
1064 for (i = 0; i < nsyms; ++i)
1065 {
1066 symbol *s = symbols[i];
1067 if (s
1068 && s->prec != 0
1069 && !prec_nodes[i]->pred
1070 && !prec_nodes[i]->succ
1071 && s->assoc == precedence_assoc)
1072 complain (&s->location, Wother,
1073 _("useless precedence for %s"), s->tag);
1074 }
1075 }