LR1 Items with lookahead instead of LR0 items

Replaced LR(0) with LR(1) with a lookahead in the items and a new closure
function, and a first hash table used to calculate it.

git-archimport-id: cascardo@tlscascardo--private/libgrammatic--lr1--0.1--patch-1

diff --git a/item.c b/item.c
index 9c05e06..3eb8fe3 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);
 }
 
@@ -90,7 +98,7 @@ void item_print (item_t* item)
     {
       fprintf (stdout, ".");
     }
-  fprintf (stdout, "\n");
+  fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
 }
 #endif
 
@@ -173,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)
     {
@@ -183,22 +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);
        }
     }
 }
 
-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;
@@ -211,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);
@@ -221,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;
@@ -244,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);
 }
 
 
@@ -352,7 +391,7 @@ void item_set_print_goto (gpointer key, gpointer val, gpointer data)
   gint code;
   state_t* state;
   symbol = (symbol_t*) key;
-  code = GINT_TO_POINTER (val);
+  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);
@@ -374,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;
@@ -391,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
@@ -402,7 +442,7 @@ GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
   return return_item_set;
 }
 
-void item_set_collection (Grammar* grammar, symbol_t* start)
+void item_set_collection (Grammar* grammar, GHashTable* first, symbol_t* start)
 {
   GHashTable* collection;
   GHashTable* item_set;
@@ -411,10 +451,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);
@@ -436,7 +476,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);