From: Thadeu Lima de Souza Cascardo <cascardo@dcc.ufmg.br>
Date: Thu, 10 Nov 2005 20:09:55 +0000 (+0000)
Subject: Generates LR(1) table from Items
X-Git-Url: http://git.cascardo.info/?p=cascardo%2Fgrammar.git;a=commitdiff_plain;h=b854111c3da17fbba15ae05157bf681b6265be97

Generates LR(1) table from Items

Generates LR(1) parser table from computing LR(1) items.


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

diff --git a/lr1_gen.c b/lr1_gen.c
new file mode 100644
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;
+
+}