Generates LR(1) table from Items

[cascardo/grammar.git] / lr1_gen.c

diff --git a/lr1_gen.c b/lr1_gen.c
new file mode 100644 (file)
index 0000000..3ff7cbf
--- /dev/null
+++ b/lr1_gen.c
@@ -0,0 +1,114 @@
+#include <grammar.h>
+#include <item.h>
+#include <lr1.h>
+#include <first.h>
+#include <scanner.h>
+#ifdef DEBUG
+#include <stdio.h>
+#endif
+
+static void put_key_val_on_list (gpointer key, gpointer val, gpointer data)
+{
+  GList** l;
+  l = (GList**) data;
+  *l = g_list_prepend (*l, val);
+  *l = g_list_prepend (*l, key);
+}
+
+static void put_key_on_list (gpointer key, gpointer val, gpointer data)
+{
+  GList** l;
+  l = (GList**) data;
+  *l = g_list_prepend (*l, key);
+}
+
+void lr1_gen_add (gpointer key, gpointer val, gpointer data)
+{
+
+  GList* l;
+  transition_t* transition;
+
+
+  l = NULL;
+  g_hash_table_foreach (key, put_key_on_list, (gpointer) &l);
+
+  while (l != NULL)
+    {
+      item_t* item;
+      item = (item_t*) l->data;
+
+      if (item->left->value == -1 && item->left->terminal == FALSE)
+       {
+         if (item->dot == NULL)
+           {
+#ifdef DEBUG
+             printf ("ACCEPT: %x\n", key);
+#endif
+             transition = transition_accept_new ();
+             lr1_add (data, key, symbol_new (TRUE, 0), transition);
+           }
+         else
+           {
+             lr1_push (data, key, NULL);
+           }
+       }
+      else if (item->dot == NULL)
+       {
+#ifdef DEBUG
+         printf ("REDUCE: %x, %s\n", key,
+                 g_quark_to_string (item->lookahead->value));
+#endif
+         transition = transition_reduce_new (item->left, item->right);
+         lr1_add (data, key, item->lookahead, transition);
+       }
+
+      l = g_list_next (l);
+
+    }
+
+  g_list_free (l);
+
+
+  l = NULL;
+  g_hash_table_foreach (val, put_key_val_on_list, (gpointer) &l);
+
+  while (l != NULL)
+    {
+
+      symbol_t* symbol;
+      symbol = (symbol_t*) l->data;
+      l = g_list_next (l);
+
+#ifdef DEBUG
+      printf ("SHIFT: %x, %s, %x\n", key,
+             g_quark_to_string (symbol->value), l->data);
+#endif
+      transition = transition_shift_new (l->data);
+      lr1_add (data, key, symbol, transition);
+
+      l = g_list_next (l);
+
+    }
+
+  g_list_free (l);
+
+}
+
+lr1_t* lr1_gen (grammar_t* grammar, symbol_t* start, nextcb cb, gpointer data)
+{
+
+  GHashTable* first;
+  GHashTable* collection;
+  lr1_t* lr1;
+
+  lr1 = lr1_new (cb, data);
+
+  first = grammar_first (grammar);
+
+  collection = item_set_collection (grammar, first, start);
+
+  g_hash_table_foreach (collection, lr1_gen_add, lr1);
+
+  return lr1;
+
+}