X-Git-Url: http://git.cascardo.info/?p=cascardo%2Fgrammar.git;a=blobdiff_plain;f=item.c;h=c089253eb199342da251173244a7122f8c997c56;hp=5a41dca569a653848ea7f294bf8eff550e7ac673;hb=58c67aca3f0c6090ae9fba5d872d041d514c6b8f;hpb=3a6785fdd5c2b67ba5c79d29ece8ff83e14eba3c

diff --git a/item.c b/item.c
index 5a41dca..c089253 100644
--- a/item.c
+++ b/item.c
@@ -1,4 +1,7 @@
 #include <grammar.h>
+#ifdef DEBUG
+#include <stdio.h>
+#endif
 
 typedef struct
 {
@@ -66,6 +69,31 @@ void item_delete (item_t* item)
   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, "\n");
+}
+#endif
+
 GHashTable* item_set_new ()
 {
   return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL);
@@ -81,16 +109,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,7 +161,19 @@ GHashTable* item_set_copy (GHashTable* item_set)
   return newitem_set;
 }
 
-void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
+#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
+
+void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
 			    item_t* item)
 {
   if (item->dot != NULL)
@@ -145,14 +198,7 @@ void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
     }
 }
 
-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)
 {
   int size;
   int last_size;
@@ -174,7 +220,7 @@ GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
   return item_set;
 }
 
-GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
+GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
 			   symbol_t* symbol)
 {
   GList* l;
@@ -236,88 +282,105 @@ 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) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
+#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));
+  item_set_print (item_set);
+  fprintf (stdout, "\n");
 }
 
-GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
+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),
+	   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_t* grammar,
 				  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, 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;
+    }
 }
 
-void item_set_collection (Grammar* grammar, symbol_t* start)
+void item_set_collection (grammar_t* grammar, symbol_t* start)
 {
   GHashTable* collection;
   GHashTable* item_set;
@@ -332,7 +395,7 @@ void item_set_collection (Grammar* grammar, symbol_t* start)
   item_set_closure (item_set, grammar);
   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)
     {
@@ -363,4 +426,8 @@ void item_set_collection (Grammar* grammar, symbol_t* start)
       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);
 }