+static bool
+symbol_translation_processor (void *this, void *null ATTRIBUTE_UNUSED)
+{
+ return symbol_translation (this);
+}
+
+
+/*---------------------------------------.
+| Symbol and semantic type hash tables. |
+`---------------------------------------*/
+
+/* Initial capacity of symbol and semantic type hash table. */
+#define HT_INITIAL_CAPACITY 257
+
+static struct hash_table *symbol_table = NULL;
+static struct hash_table *semantic_type_table = NULL;
+
+static inline bool
+hash_compare_symbol (const symbol *m1, const symbol *m2)
+{
+ /* Since tags are unique, we can compare the pointers themselves. */
+ return UNIQSTR_EQ (m1->tag, m2->tag);
+}
+
+static inline bool
+hash_compare_semantic_type (const semantic_type *m1, const semantic_type *m2)
+{
+ /* Since names are unique, we can compare the pointers themselves. */
+ return UNIQSTR_EQ (m1->tag, m2->tag);
+}
+
+static bool
+hash_symbol_comparator (void const *m1, void const *m2)
+{
+ return hash_compare_symbol (m1, m2);
+}
+
+static bool
+hash_semantic_type_comparator (void const *m1, void const *m2)
+{
+ return hash_compare_semantic_type (m1, m2);
+}
+
+static inline size_t
+hash_symbol (const symbol *m, size_t tablesize)
+{
+ /* Since tags are unique, we can hash the pointer itself. */
+ return ((uintptr_t) m->tag) % tablesize;
+}
+
+static inline size_t
+hash_semantic_type (const semantic_type *m, size_t tablesize)
+{
+ /* Since names are unique, we can hash the pointer itself. */
+ return ((uintptr_t) m->tag) % tablesize;
+}
+
+static size_t
+hash_symbol_hasher (void const *m, size_t tablesize)
+{
+ return hash_symbol (m, tablesize);
+}
+
+static size_t
+hash_semantic_type_hasher (void const *m, size_t tablesize)
+{
+ return hash_semantic_type (m, tablesize);
+}
+
+/*-------------------------------.
+| Create the symbol hash table. |
+`-------------------------------*/
+
+void
+symbols_new (void)
+{
+ symbol_table = hash_initialize (HT_INITIAL_CAPACITY,
+ NULL,
+ hash_symbol_hasher,
+ hash_symbol_comparator,
+ free);
+ semantic_type_table = hash_initialize (HT_INITIAL_CAPACITY,
+ NULL,
+ hash_semantic_type_hasher,
+ hash_semantic_type_comparator,
+ free);
+}
+
+
+/*----------------------------------------------------------------.
+| Find the symbol named KEY, and return it. If it does not exist |
+| yet, create it. |
+`----------------------------------------------------------------*/
+
+symbol *
+symbol_from_uniqstr (const uniqstr key, location loc)
+{
+ symbol probe;
+ symbol *entry;
+
+ probe.tag = key;
+ entry = hash_lookup (symbol_table, &probe);
+
+ if (!entry)
+ {
+ /* First insertion in the hash. */
+ aver (!symbols_sorted);
+ entry = symbol_new (key, loc);
+ if (!hash_insert (symbol_table, entry))
+ xalloc_die ();
+ }
+ return entry;
+}
+
+
+/*-----------------------------------------------------------------------.
+| Find the semantic type named KEY, and return it. If it does not exist |
+| yet, create it. |
+`-----------------------------------------------------------------------*/
+
+semantic_type *
+semantic_type_from_uniqstr (const uniqstr key, const location *loc)
+{
+ semantic_type probe;
+ semantic_type *entry;
+
+ probe.tag = key;
+ entry = hash_lookup (semantic_type_table, &probe);
+
+ if (!entry)
+ {
+ /* First insertion in the hash. */
+ entry = semantic_type_new (key, loc);
+ if (!hash_insert (semantic_type_table, entry))
+ xalloc_die ();
+ }
+ return entry;
+}
+
+
+/*----------------------------------------------------------------.
+| Find the symbol named KEY, and return it. If it does not exist |
+| yet, create it. |
+`----------------------------------------------------------------*/
+
+symbol *
+symbol_get (const char *key, location loc)
+{
+ return symbol_from_uniqstr (uniqstr_new (key), loc);
+}
+
+
+/*-----------------------------------------------------------------------.
+| Find the semantic type named KEY, and return it. If it does not exist |
+| yet, create it. |
+`-----------------------------------------------------------------------*/
+
+semantic_type *
+semantic_type_get (const char *key, const location *loc)
+{
+ return semantic_type_from_uniqstr (uniqstr_new (key), loc);
+}
+
+
+/*------------------------------------------------------------------.
+| Generate a dummy nonterminal, whose name cannot conflict with the |
+| user's names. |
+`------------------------------------------------------------------*/
+
+symbol *
+dummy_symbol_get (location loc)
+{
+ /* Incremented for each generated symbol. */
+ static int dummy_count = 0;
+ static char buf[256];
+
+ symbol *sym;
+
+ sprintf (buf, "$@%d", ++dummy_count);
+ sym = symbol_get (buf, loc);
+ sym->class = nterm_sym;
+ sym->number = nvars++;
+ return sym;
+}
+
+bool
+symbol_is_dummy (const symbol *sym)
+{
+ return sym->tag[0] == '@' || (sym->tag[0] == '$' && sym->tag[1] == '@');
+}
+
+/*-------------------.
+| Free the symbols. |
+`-------------------*/
+
+void
+symbols_free (void)
+{
+ hash_free (symbol_table);
+ hash_free (semantic_type_table);
+ free (symbols);
+ free (symbols_sorted);
+ free (semantic_types_sorted);
+}
+
+
+/*---------------------------------------------------------------.
+| Look for undefined symbols, report an error, and consider them |
+| terminals. |
+`---------------------------------------------------------------*/
+
+static int
+symbols_cmp (symbol const *a, symbol const *b)
+{
+ return strcmp (a->tag, b->tag);
+}
+
+static int
+symbols_cmp_qsort (void const *a, void const *b)
+{
+ return symbols_cmp (*(symbol * const *)a, *(symbol * const *)b);
+}
+
+static void
+symbols_do (Hash_processor processor, void *processor_data,
+ struct hash_table *table, symbol ***sorted)
+{
+ size_t count = hash_get_n_entries (table);
+ if (!*sorted)
+ {
+ *sorted = xnmalloc (count, sizeof **sorted);
+ hash_get_entries (table, (void**)*sorted, count);
+ qsort (*sorted, count, sizeof **sorted, symbols_cmp_qsort);
+ }
+ {
+ size_t i;
+ for (i = 0; i < count; ++i)
+ processor ((*sorted)[i], processor_data);
+ }
+}
+
+/*--------------------------------------------------------------.
+| Check that all the symbols are defined. Report any undefined |
+| symbols and consider them nonterminals. |
+`--------------------------------------------------------------*/
+
+void
+symbols_check_defined (void)
+{
+ symbols_do (symbol_check_defined_processor, NULL,
+ symbol_table, &symbols_sorted);
+ symbols_do (semantic_type_check_defined_processor, NULL,
+ semantic_type_table, &semantic_types_sorted);
+}
+
+/*------------------------------------------------------------------.
+| Set TOKEN_TRANSLATIONS. Check that no two symbols share the same |
+| number. |
+`------------------------------------------------------------------*/
+
+static void
+symbols_token_translations_init (void)
+{
+ bool num_256_available_p = true;
+ int i;
+
+ /* Find the highest user token number, and whether 256, the POSIX
+ preferred user token number for the error token, is used. */
+ max_user_token_number = 0;
+ for (i = 0; i < ntokens; ++i)
+ {
+ symbol *this = symbols[i];
+ if (this->user_token_number != USER_NUMBER_UNDEFINED)
+ {
+ if (this->user_token_number > max_user_token_number)
+ max_user_token_number = this->user_token_number;
+ if (this->user_token_number == 256)
+ num_256_available_p = false;
+ }
+ }
+
+ /* If 256 is not used, assign it to error, to follow POSIX. */
+ if (num_256_available_p
+ && errtoken->user_token_number == USER_NUMBER_UNDEFINED)
+ errtoken->user_token_number = 256;
+
+ /* Set the missing user numbers. */
+ if (max_user_token_number < 256)
+ max_user_token_number = 256;
+
+ for (i = 0; i < ntokens; ++i)
+ {
+ symbol *this = symbols[i];
+ if (this->user_token_number == USER_NUMBER_UNDEFINED)
+ this->user_token_number = ++max_user_token_number;
+ if (this->user_token_number > max_user_token_number)
+ max_user_token_number = this->user_token_number;
+ }
+
+ token_translations = xnmalloc (max_user_token_number + 1,
+ sizeof *token_translations);
+
+ /* Initialize all entries for literal tokens to the internal token
+ number for $undefined, which represents all invalid inputs. */
+ for (i = 0; i < max_user_token_number + 1; i++)
+ token_translations[i] = undeftoken->number;
+ symbols_do (symbol_translation_processor, NULL,
+ symbol_table, &symbols_sorted);
+}
+
+
+/*----------------------------------------------------------------.
+| Assign symbol numbers, and write definition of token names into |
+| FDEFINES. Set up vectors SYMBOL_TABLE, TAGS of symbols. |
+`----------------------------------------------------------------*/
+
+void
+symbols_pack (void)
+{
+ symbols_do (symbol_check_alias_consistency_processor, NULL,
+ symbol_table, &symbols_sorted);
+
+ symbols = xcalloc (nsyms, sizeof *symbols);
+ symbols_do (symbol_pack_processor, NULL, symbol_table, &symbols_sorted);
+
+ /* Aliases leave empty slots in symbols, so remove them. */
+ {
+ int writei;
+ int readi;
+ int nsyms_old = nsyms;
+ for (writei = 0, readi = 0; readi < nsyms_old; readi += 1)
+ {
+ if (symbols[readi] == NULL)
+ {
+ nsyms -= 1;
+ ntokens -= 1;
+ }
+ else
+ {
+ symbols[writei] = symbols[readi];
+ symbols[writei]->number = writei;
+ if (symbols[writei]->alias)
+ symbols[writei]->alias->number = writei;
+ writei += 1;
+ }
+ }
+ }
+ symbols = xnrealloc (symbols, nsyms, sizeof *symbols);
+
+ symbols_token_translations_init ();
+
+ if (startsymbol->class == unknown_sym)
+ complain (&startsymbol_location, fatal,
+ _("the start symbol %s is undefined"),
+ startsymbol->tag);
+ else if (startsymbol->class == token_sym)
+ complain (&startsymbol_location, fatal,
+ _("the start symbol %s is a token"),
+ startsymbol->tag);
+}
+
+/*---------------------------------.
+| Initialize relation graph nodes. |
+`---------------------------------*/
+
+static void
+init_prec_nodes (void)
+{
+ int i;
+ prec_nodes = xcalloc (nsyms, sizeof *prec_nodes);
+ for (i = 0; i < nsyms; ++i)
+ {
+ prec_nodes[i] = xmalloc (sizeof *prec_nodes[i]);
+ symgraph *s = prec_nodes[i];
+ s->id = i;
+ s->succ = 0;
+ s->pred = 0;
+ }
+}
+
+/*----------------.
+| Create a link. |
+`----------------*/
+
+static symgraphlink *
+symgraphlink_new (graphid id, symgraphlink *next)
+{
+ symgraphlink *l = xmalloc (sizeof *l);
+ l->id = id;
+ l->next = next;
+ return l;
+}
+
+
+/*------------------------------------------------------------------.
+| Register the second symbol of the precedence relation, and return |
+| whether this relation is new. Use only in register_precedence. |
+`------------------------------------------------------------------*/
+
+static bool
+register_precedence_second_symbol (symgraphlink **first, graphid sym)
+{
+ if (!*first || sym < (*first)->id)
+ *first = symgraphlink_new (sym, *first);
+ else
+ {
+ symgraphlink *slist = *first;
+
+ while (slist->next && slist->next->id <= sym)
+ slist = slist->next;
+
+ if (slist->id == sym)
+ /* Relation already present. */
+ return false;
+
+ slist->next = symgraphlink_new (sym, slist->next);
+ }
+ return true;
+}
+
+/*------------------------------------------------------------------.
+| Register a new relation between symbols as used. The first symbol |
+| has a greater precedence than the second one. |
+`------------------------------------------------------------------*/
+
+void
+register_precedence (graphid first, graphid snd)
+{
+ if (!prec_nodes)
+ init_prec_nodes ();
+ register_precedence_second_symbol (&(prec_nodes[first]->succ), snd);
+ register_precedence_second_symbol (&(prec_nodes[snd]->pred), first);
+}
+
+
+/*---------------------------------------.
+| Deep clear a linked / adjacency list). |
+`---------------------------------------*/
+
+static void
+linkedlist_free (symgraphlink *node)
+{
+ if (node)
+ {
+ while (node->next)
+ {
+ symgraphlink *tmp = node->next;
+ free (node);
+ node = tmp;
+ }
+ free (node);
+ }
+}
+
+/*----------------------------------------------.
+| Clear and destroy association tracking table. |
+`----------------------------------------------*/
+
+static void
+assoc_free (void)
+{
+ int i;
+ for (i = 0; i < nsyms; ++i)
+ {
+ linkedlist_free (prec_nodes[i]->pred);
+ linkedlist_free (prec_nodes[i]->succ);
+ free (prec_nodes[i]);
+ }
+ free (prec_nodes);
+}
+
+/*---------------------------------------.
+| Initialize association tracking table. |
+`---------------------------------------*/
+
+static void
+init_assoc (void)
+{
+ graphid i;
+ used_assoc = xcalloc(nsyms, sizeof(*used_assoc));
+ for (i = 0; i < nsyms; ++i)
+ used_assoc[i] = false;
+}
+
+/*------------------------------------------------------------------.
+| Test if the associativity for the symbols is defined and useless. |
+`------------------------------------------------------------------*/
+
+static inline bool
+is_assoc_useless (symbol *s)
+{
+ return s
+ && s->assoc != undef_assoc
+ && s->assoc != precedence_assoc
+ && !used_assoc[s->number];
+}
+
+/*-------------------------------.
+| Register a used associativity. |
+`-------------------------------*/
+
+void
+register_assoc (graphid i, graphid j)
+{
+ if (!used_assoc)
+ init_assoc ();
+ used_assoc[i] = true;
+ used_assoc[j] = true;
+}
+
+/*--------------------------------------------------.
+| Print a warning for unused precedence relations. |
+`--------------------------------------------------*/
projects / bison.git / blobdiff