Item collection building returns the collection

[cascardo/grammar.git] / item.c

diff --git a/item.c b/item.c
index fd017e2..c4c5373 100644 (file)
--- a/item.c
+++ b/item.c
@@ -1,4 +1,5 @@
 #include <grammar.h>
+#include <first.h>
 #ifdef DEBUG
 #include <stdio.h>
 #endif
@@ -8,15 +9,17 @@ 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)
+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;
 }
 
@@ -24,7 +27,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;
@@ -39,6 +43,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)
@@ -59,6 +65,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;
 }
 
@@ -66,6 +73,7 @@ void item_delete (item_t* item)
 {
   g_free (item->left);
   rule_delete (item->right);
+  g_free (item->lookahead);
   g_free (item);
 }
 
@@ -74,7 +82,7 @@ void item_print (item_t* item)
 {
   GList* l;
   fprintf (stdout, "%s -> ", g_quark_to_string (item->left->value));
-  l = grammar_rule_get (item->right);
+  l = grammar_get_rule (item->right);
   while (l != NULL)
     {
       symbol_t* symbol;
@@ -84,12 +92,13 @@ void item_print (item_t* item)
          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");
+  fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
 }
 #endif
 
@@ -108,16 +117,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)
@@ -159,8 +181,25 @@ void item_set_print (GHashTable* item_set)
 }
 #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* grammar,
-                           item_t* item)
+                           GHashTable* first, item_t* item)
 {
   if (item->dot != NULL)
     {
@@ -169,29 +208,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* grammar,
+                             GHashTable* first)
 {
   int size;
   int last_size;
@@ -204,7 +250,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);
@@ -214,7 +260,7 @@ GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
 }
 
 GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
-                          symbol_t* symbol)
+                          GHashTable* first, symbol_t* symbol)
 {
   GList* l;
   GHashTable* newitem_set;
@@ -237,7 +283,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);
 }
 
 
@@ -344,8 +390,8 @@ void item_set_print_goto (gpointer key, gpointer val, gpointer data)
   symbol_t* symbol;
   gint code;
   state_t* state;
-  symbol = (symbol_t*) symbol;
-  code = GINT_TO_POINTER (val);
+  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);
@@ -367,7 +413,8 @@ void item_collection_print (GHashTable* collection)
 #endif
 
 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
-                                 GHashTable* item_set, symbol_t* symbol)
+                                 GHashTable* first, GHashTable* item_set,
+                                 symbol_t* symbol)
 {
   state_t* state;
   state_t* goto_state;
@@ -384,7 +431,7 @@ GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
     {
       return NULL;
     }
-  goto_item_set = item_set_goto (item_set, grammar, symbol);
+  goto_item_set = item_set_goto (item_set, grammar, first, symbol);
   if (!item_collection_add (collection, goto_item_set))
     return_item_set = NULL;
   else
@@ -395,7 +442,8 @@ GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
   return return_item_set;
 }
 
-void item_set_collection (Grammar* grammar, symbol_t* start)
+GHashTable* item_set_collection (Grammar* grammar, GHashTable* first,
+                                symbol_t* start)
 {
   GHashTable* collection;
   GHashTable* item_set;
@@ -404,10 +452,10 @@ void item_set_collection (Grammar* grammar, symbol_t* start)
   GList* new_item_sets;
   rule = rule_new ();
   rule_append (rule, symbol_copy (start));
-  item = item_new (symbol_new (FALSE, -1), rule);
+  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);
   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
                                      g_hash_table_destroy, NULL);
   item_collection_add (collection, item_set);
@@ -429,7 +477,7 @@ void item_set_collection (Grammar* grammar, symbol_t* start)
            {
              symbol = (symbol_t*) item->dot->data;
              if ((new_item_set =
-                  item_collection_goto (collection, grammar,
+                  item_collection_goto (collection, grammar, first,
                                         next_item_set, symbol)) != NULL)
              {
                g_list_append (new_item_sets, new_item_set);
@@ -444,5 +492,5 @@ void item_set_collection (Grammar* grammar, symbol_t* start)
 #ifdef DEBUG
   item_collection_print (collection);
 #endif
-  g_hash_table_destroy (collection);
+  return collection;
 }