From: Thadeu Lima de Souza Cascardo Date: Sun, 23 Oct 2005 23:40:44 +0000 (+0000) Subject: Update with lr1 branch X-Git-Tag: cascardo@tlscascardo--private,libgrammatic--regular--0.1--base-0~8 X-Git-Url: http://git.cascardo.eti.br/?p=cascardo%2Fgrammar.git;a=commitdiff_plain;h=3e5e98ceab44fdf624ed07653bc46216d0921ee5;hp=-c Update with lr1 branch Patches applied: * cascardo@tlscascardo--private/libgrammatic--lr1--0.1--patch-5 Added header to item collection building git-archimport-id: cascardo@tlscascardo--private/libgrammatic--nogobject-lr1--0.1--patch-4 --- 3e5e98ceab44fdf624ed07653bc46216d0921ee5 diff --combined item.c index eef188d,dea4adb..f1f61ce --- a/item.c +++ b/item.c @@@ -1,17 -1,10 +1,10 @@@ #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; @@@ -198,7 -191,7 +191,7 @@@ rule_t* rule_new_item (item_t* item } -void item_set_closure_step (GHashTable* item_set, Grammar* grammar, +void item_set_closure_step (GHashTable* item_set, grammar_t* grammar, GHashTable* first, item_t* item) { if (item->dot != NULL) @@@ -236,7 -229,7 +229,7 @@@ } } -GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar, +GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar, GHashTable* first) { int size; @@@ -259,7 -252,7 +252,7 @@@ return item_set; } -GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar, +GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar, GHashTable* first, symbol_t* symbol) { GList* l; @@@ -321,46 -314,66 +314,46 @@@ * 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) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8)) #ifdef DEBUG void item_collection_print_each (gpointer key, gpointer val, gpointer data) { GHashTable* item_set; - state_t* state; item_set = (GHashTable*) key; - state = (state_t*) val; - fprintf (stdout, "Item %d:\n", state->code); + fprintf (stdout, "Item %x:\n", HASH_ITEM_SET(key)); item_set_print (item_set); fprintf (stdout, "\n"); } @@@ -368,16 -381,20 +361,16 @@@ void item_set_print_goto (gpointer key, gpointer val, gpointer data) { symbol_t* symbol; - gint code; - state_t* state; symbol = (symbol_t*) key; - code = GPOINTER_TO_INT (val); - state = (state_t*) data; - fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code, - g_quark_to_string (symbol->value), code); + fprintf (stdout, "GOTO (%x, %s) =\t %x\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) { - state_t* state; - state = (state_t*) val; - g_hash_table_foreach (state->symbols, item_set_print_goto, state); + GHashTable* symbols; + symbols = (GHashTable*) val; + g_hash_table_foreach (symbols, item_set_print_goto, key); fprintf (stdout, "\n"); } @@@ -388,39 -405,37 +381,39 @@@ void item_collection_print (GHashTable } #endif -GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar, +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; 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)) + symbols = item_collection_lookup (collection, item_set); + if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL)) { return NULL; } goto_item_set = item_set_goto (item_set, grammar, first, symbol); - if (!item_collection_add (collection, goto_item_set)) - return_item_set = NULL; + 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; + } 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; + } } -GHashTable* item_set_collection (Grammar* grammar, GHashTable* first, +GHashTable* item_set_collection (grammar_t* grammar, GHashTable* first, symbol_t* start) { GHashTable* collection; @@@ -436,7 -451,7 +429,7 @@@ item_set_closure (item_set, grammar, first); 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) {