X-Git-Url: http://git.cascardo.info/?p=cascardo%2Fgrammar.git;a=blobdiff_plain;f=item.c;h=351dce3593d66dda2c072b9f279439f5c60cc004;hp=5a41dca569a653848ea7f294bf8eff550e7ac673;hb=1c9564234c5dac0c4742b47c41dc3ff8fdd02d77;hpb=3a6785fdd5c2b67ba5c79d29ece8ff83e14eba3c diff --git a/item.c b/item.c index 5a41dca..351dce3 100644 --- a/item.c +++ b/item.c @@ -1,19 +1,38 @@ -#include +/* + * Copyright (C) 2005 Thadeu Lima de Souza Cascardo + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ -typedef struct -{ - symbol_t* left; - rule_t* right; - GList* dot; -} item_t; -item_t* item_new (symbol_t* left, rule_t* right) + +#include +#include +#include +#ifdef DEBUG +#include +#endif + +item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead) { item_t* item; item = g_malloc (sizeof (item_t)); item->left = left; item->right = right; item->dot = grammar_get_rule (right); + item->lookahead = lookahead; return item; } @@ -21,7 +40,8 @@ item_t* item_copy (item_t* item) { item_t* newitem; int n; - newitem = item_new (symbol_copy (item->left), rule_copy (item->right)); + newitem = item_new (symbol_copy (item->left), rule_copy (item->right), + symbol_copy (item->lookahead)); n = g_list_position (grammar_get_rule (item->right), item->dot); newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n); return newitem; @@ -36,6 +56,8 @@ gint item_cmp (const item_t* a, const item_t* b) return c; if ((c = rule_cmp (a->right, b->right)) != 0) return c; + if ((c = symbol_cmp (a->lookahead, b->lookahead)) != 0) + return c; na = g_list_position (grammar_get_rule (a->right), a->dot); nb = g_list_position (grammar_get_rule (b->right), b->dot); if (na < nb) @@ -56,6 +78,7 @@ guint item_hash (gconstpointer data) guint hash; item = (item_t*) data; hash = rule_hash (item->right) * 37 + symbol_hash (item->left); + hash = hash * 37 + symbol_hash (item->lookahead); return hash; } @@ -63,9 +86,35 @@ void item_delete (item_t* item) { g_free (item->left); rule_delete (item->right); + g_free (item->lookahead); g_free (item); } +#ifdef DEBUG +void item_print (item_t* item) +{ + GList* l; + fprintf (stdout, "%s -> ", g_quark_to_string (item->left->value)); + l = grammar_get_rule (item->right); + while (l != NULL) + { + symbol_t* symbol; + symbol = (symbol_t*) l->data; + if (l == item->dot) + { + fprintf (stdout, "."); + } + fprintf (stdout, " %s ", g_quark_to_string (symbol->value)); + l = g_list_next (l); + } + if (item->dot == NULL) + { + fprintf (stdout, "."); + } + fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value)); +} +#endif + GHashTable* item_set_new () { return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL); @@ -81,16 +130,29 @@ gboolean item_set_add (GHashTable* item_set, item_t* item) return FALSE; } -gboolean item_set_find (gpointer key, gpointer val, gpointer data) +static void put_key_on_list (gpointer key, gpointer val, gpointer data) { - return !g_hash_table_lookup_extended (data, key, NULL, NULL); + GList** l; + l = (GList**) data; + *l = g_list_prepend (*l, key); } gboolean item_set_equal (gconstpointer a, gconstpointer b) { + GList* l; + gboolean equal; if (g_hash_table_size (a) != g_hash_table_size (b)) return FALSE; - return (g_hash_table_find (a, item_set_find, b) == NULL); + l = NULL; + g_hash_table_foreach (a, put_key_on_list, (gpointer) &l); + equal = TRUE; + while (l != NULL && equal == TRUE) + { + equal = g_hash_table_lookup_extended (b, l->data, NULL, NULL); + l = g_list_next (l); + } + g_list_free (l); + return equal; } void hash_item (gpointer key, gpointer val, gpointer data) @@ -120,8 +182,37 @@ GHashTable* item_set_copy (GHashTable* item_set) return newitem_set; } -void item_set_closure_step (GHashTable* item_set, Grammar* grammar, - item_t* item) +#ifdef DEBUG +void item_set_print_each (gpointer key, gpointer val, gpointer data) +{ + item_print (key); +} + +void item_set_print (GHashTable* item_set) +{ + g_hash_table_foreach (item_set, item_set_print_each, NULL); +} +#endif + +rule_t* rule_new_item (item_t* item) +{ + + rule_t* rule; + GList* l; + rule = rule_new (); + l = g_list_next (item->dot); + while (l != NULL) + { + rule_append (rule, symbol_copy (l->data)); + l = g_list_next (l); + } + rule_append (rule, symbol_copy (item->lookahead)); + return rule; + +} + +void item_set_closure_step (GHashTable* item_set, grammar_t* grammar, + GHashTable* first, item_t* item) { if (item->dot != NULL) { @@ -130,29 +221,36 @@ void item_set_closure_step (GHashTable* item_set, Grammar* grammar, if (symbol->terminal == FALSE) { GList* rules; + GList* terminals; + rule_t* rule; + rule = rule_new_item (item); + terminals = first_rule (first, rule); + rule_delete (rule); rules = grammar_get_rules (grammar, symbol); while (rules != NULL) { - rule_t* rule; - item_t* newitem; - rule = rule_copy (rules->data); - newitem = item_new (symbol_copy (symbol), rule); - if (!item_set_add (item_set, newitem)) - item_delete (newitem); + GList* lookahead; + lookahead = terminals; + while (lookahead != NULL) + { + rule_t* rule; + item_t* newitem; + rule = rule_copy (rules->data); + newitem = item_new (symbol_copy (symbol), rule, + symbol_copy (lookahead->data)); + if (!item_set_add (item_set, newitem)) + item_delete (newitem); + lookahead = g_list_next (lookahead); + } rules = g_list_next (rules); } + g_list_free (terminals); } } } -void put_key_on_list (gpointer key, gpointer val, gpointer data) -{ - GList** l; - l = (GList**) data; - *l = g_list_prepend (*l, key); -} - -GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar) +GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar, + GHashTable* first) { int size; int last_size; @@ -165,7 +263,7 @@ GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar) g_hash_table_foreach (item_set, put_key_on_list, &l); while (l != NULL) { - item_set_closure_step (item_set, grammar, l->data); + item_set_closure_step (item_set, grammar, first, l->data); l = g_list_next (l); } g_list_free (l); @@ -174,8 +272,8 @@ GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar) return item_set; } -GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar, - symbol_t* symbol) +GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar, + GHashTable* first, symbol_t* symbol) { GList* l; GHashTable* newitem_set; @@ -198,7 +296,7 @@ GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar, } l = g_list_next (l); } - return item_set_closure (newitem_set, grammar); + return item_set_closure (newitem_set, grammar, first); } @@ -236,131 +334,223 @@ GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar, * In fact, the counter may be the hash table size. */ -typedef struct -{ - GHashTable* symbols; - gint code; -} state_t; - -state_t* state_new (gint code) -{ - state_t* state; - state = g_malloc (sizeof (state_t)); - state->code = code; - state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal, - g_free, NULL); - return state; -} - -void state_delete (state_t* state) -{ - g_hash_table_destroy (state->symbols); - g_free (state); -} - GHashTable* item_collection_new () { return g_hash_table_new_full (item_set_hash, item_set_equal, - g_hash_table_destroy, state_delete); + g_hash_table_destroy, g_hash_table_destroy); } -gboolean item_collection_add (GHashTable* collection, GHashTable* item_set) +gboolean item_collection_add (GHashTable* collection, GHashTable* item_set, + GHashTable** key) { - if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL)) + if (!g_hash_table_lookup_extended (collection, item_set, + (gpointer*)key, NULL)) { - state_t* state; - state = state_new (g_hash_table_size (collection)); - g_hash_table_insert (collection, item_set, state); + GHashTable* symbols; + symbols = g_hash_table_new_full (symbol_hash, symbol_equal, + g_free, NULL); + g_hash_table_insert (collection, item_set, symbols); return TRUE; } return FALSE; } -state_t* item_collection_lookup (GHashTable* collection, - GHashTable* item_set) +GHashTable* item_collection_lookup (GHashTable* collection, + GHashTable* item_set) { - state_t* state; + GHashTable* symbols; if (!g_hash_table_lookup_extended (collection, item_set, - NULL, (gpointer*)&state)) + NULL, (gpointer*)&symbols)) { return NULL; } - return state; + return symbols; +} + +#define HASH_ITEM_SET(item_set) (item_set) +#ifdef DEBUG +void item_collection_print_each (gpointer key, gpointer val, gpointer data) +{ + GHashTable* item_set; + item_set = (GHashTable*) key; + fprintf (stdout, "Item %p:\n", HASH_ITEM_SET(key)); + item_set_print (item_set); + fprintf (stdout, "\n"); +} + +void item_set_print_goto (gpointer key, gpointer val, gpointer data) +{ + symbol_t* symbol; + symbol = (symbol_t*) key; + fprintf (stdout, "GOTO (%p, %s) =\t %p\n", HASH_ITEM_SET(data), + g_quark_to_string (symbol->value), HASH_ITEM_SET(val)); +} + +void item_collection_print_goto (gpointer key, gpointer val, gpointer data) +{ + GHashTable* symbols; + symbols = (GHashTable*) val; + g_hash_table_foreach (symbols, item_set_print_goto, key); + fprintf (stdout, "\n"); +} + +void item_collection_print (GHashTable* collection) +{ + g_hash_table_foreach (collection, item_collection_print_each, NULL); + g_hash_table_foreach (collection, item_collection_print_goto, NULL); } +#endif -GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar, - GHashTable* item_set, symbol_t* symbol) +GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar, + GHashTable* first, GHashTable* item_set, + symbol_t* symbol) { - state_t* state; - state_t* goto_state; + + GHashTable* symbols; GHashTable* newitem_set; GHashTable* goto_item_set; - GHashTable* return_item_set; + GHashTable* old_item_set; + + /* + * Is it a new item set? Why should we insert a copy of it? Do we + * destroy the original later? + * + * TODO: Check why this code was once here. WTF! Caused some damn + * bug. + */ + /* newitem_set = item_set_copy (item_set); - if (!item_collection_add (collection, newitem_set)) + if (!item_collection_add (collection, newitem_set, NULL)) { g_hash_table_destroy (newitem_set); } - state = item_collection_lookup (collection, item_set); - if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL)) + */ + + /* + * Is there a computed goto from this item set with this symbol + * already? + */ + symbols = item_collection_lookup (collection, item_set); + if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL)) + { + return NULL; + } + + /* + * If the computed goto already exists in the table, retrieve it and + * add the entry in the table pointing to it instead of the newly + * computed item set. Destroy the new copy. We don't need it. Only + * return the computed goto if it's a new item set. + */ + goto_item_set = item_set_goto (item_set, grammar, first, symbol); + if (!item_collection_add (collection, goto_item_set, &old_item_set)) { + g_hash_table_insert (symbols, symbol, old_item_set); + g_hash_table_destroy (goto_item_set); return NULL; } - goto_item_set = item_set_goto (item_set, grammar, symbol); - if (!item_collection_add (collection, goto_item_set)) - return_item_set = NULL; else - return_item_set = goto_item_set; - goto_state = item_collection_lookup (collection, goto_item_set); - g_hash_table_insert (state->symbols, symbol, - GINT_TO_POINTER (goto_state->code)); - return return_item_set; + { + g_hash_table_insert (symbols, symbol, goto_item_set); + return goto_item_set; + } +} + +void get_symbol_at_dot (gpointer key, gpointer val, gpointer data) +{ + item_t* item; + GHashTable* symbols; + symbol_t* symbol; + item = (item_t*) key; + symbols = (GHashTable*) data; + if (item->dot != NULL) + { + symbol = item->dot->data; + if (!g_hash_table_lookup_extended (symbols, symbol, NULL, NULL)) + { + g_hash_table_insert (symbols, symbol, NULL); + } + } } -void item_set_collection (Grammar* grammar, symbol_t* start) +/* Get the symbols at the dot in this item set */ +GList* item_set_symbols_at_dot (GHashTable* item_set) { + GHashTable* symbols; + GList* symbols_list; + symbols_list = NULL; + symbols = g_hash_table_new_full (symbol_hash, symbol_equal, + NULL, NULL); + g_hash_table_foreach (item_set, get_symbol_at_dot, symbols); + g_hash_table_foreach (symbols, put_key_on_list, &symbols_list); + g_hash_table_destroy (symbols); + return symbols_list; +} + +GHashTable* item_set_collection (grammar_t* grammar, GHashTable* first, + symbol_t* start) +{ + GHashTable* collection; GHashTable* item_set; item_t* item; rule_t* rule; GList* new_item_sets; + + /* Augmented grammar has start symbol S' -> S */ rule = rule_new (); rule_append (rule, symbol_copy (start)); - item = item_new (symbol_new (FALSE, -1), rule); + + /* First item set is the closure of the item set with S' -> . S , $ */ + item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0)); item_set = item_set_new (); item_set_add (item_set, item); - item_set_closure (item_set, grammar); + item_set_closure (item_set, grammar, first); + + /* Insert first item set in the collection of item sets and start working */ collection = g_hash_table_new_full (item_set_hash, item_set_equal, g_hash_table_destroy, NULL); - item_collection_add (collection, item_set); + item_collection_add (collection, item_set, NULL); + new_item_sets = g_list_append (NULL, item_set); + while (new_item_sets != NULL) { GHashTable* next_item_set; GHashTable* new_item_set; - GList* items; + GList* symbols; + /* + * For each item, compute the goto for the symbol at its + * dot. Should be done only for each symbol at a dot in the + * whole item set. Only new item sets are put in the new item + * sets list. Check item_collection_goto. + * + * TODO: Only do this for each symbol at a dot in the item set. + */ next_item_set = (GHashTable*) new_item_sets->data; - items = NULL; - g_hash_table_foreach (next_item_set, put_key_on_list, &items); - while (items != NULL) + symbols = item_set_symbols_at_dot (next_item_set); + while (symbols != NULL) { - item_t* item; symbol_t* symbol; - item = (item_t*) items->data; - if (item->dot != NULL) + symbol = (symbol_t*) symbols->data; + if ((new_item_set = + item_collection_goto (collection, grammar, first, + next_item_set, symbol)) != NULL) { - symbol = (symbol_t*) item->dot->data; - if ((new_item_set = - item_collection_goto (collection, grammar, - next_item_set, symbol)) != NULL) - { - g_list_append (new_item_sets, new_item_set); - } + g_list_append (new_item_sets, new_item_set); } - items = g_list_next (items); + symbols = g_list_next (symbols); } - g_list_free (items); + g_list_free (symbols); new_item_sets = g_list_next (new_item_sets); } + g_list_free (new_item_sets); + +#ifdef DEBUG + item_collection_print (collection); +#endif + + return collection; + }