+#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;
+
+}