X-Git-Url: http://git.cascardo.info/?p=cascardo%2Fgrammar.git;a=blobdiff_plain;f=item.c;h=351dce3593d66dda2c072b9f279439f5c60cc004;hp=ef9864711582b0b7ad454c4edb6def2ee4dc0a54;hb=HEAD;hpb=b1a65b0f36eca06bcc88db6f4cecee76b78c3177 diff --git a/item.c b/item.c index ef98647..351dce3 100644 --- a/item.c +++ b/item.c @@ -1,17 +1,30 @@ +/* + * 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. + */ + + + #include #include +#include #ifdef DEBUG #include #endif -typedef struct -{ - symbol_t* left; - rule_t* right; - GList* dot; - symbol_t* lookahead; -} item_t; - item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead) { item_t* item; @@ -354,13 +367,13 @@ GHashTable* item_collection_lookup (GHashTable* collection, return symbols; } -#define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8)) +#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 %x:\n", HASH_ITEM_SET(key)); + fprintf (stdout, "Item %p:\n", HASH_ITEM_SET(key)); item_set_print (item_set); fprintf (stdout, "\n"); } @@ -369,7 +382,7 @@ void item_set_print_goto (gpointer key, gpointer val, gpointer data) { symbol_t* symbol; symbol = (symbol_t*) key; - fprintf (stdout, "GOTO (%x, %s) =\t %x\n", HASH_ITEM_SET(data), + fprintf (stdout, "GOTO (%p, %s) =\t %p\n", HASH_ITEM_SET(data), g_quark_to_string (symbol->value), HASH_ITEM_SET(val)); } @@ -392,20 +405,43 @@ GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar, GHashTable* first, GHashTable* item_set, symbol_t* symbol) { + GHashTable* symbols; GHashTable* newitem_set; GHashTable* goto_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, NULL)) { g_hash_table_destroy (newitem_set); } + */ + + /* + * 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)) { @@ -420,54 +456,101 @@ GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar, } } -void item_set_collection (grammar_t* grammar, GHashTable* first, symbol_t* start) +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); + } + } +} + +/* 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)); + + /* 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, 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, 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, first, - 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 - g_hash_table_destroy (collection); + + return collection; + }