Added LR1 Parsing Algorithm

LR(1) parsing algorithm is added to the library.

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

diff --git a/lr1.c b/lr1.c
new file mode 100644 (file)
index 0000000..d7f2d98
--- /dev/null
+++ b/lr1.c
@@ -0,0 +1,265 @@
+#include <grammar.h>
+#include <stdlib.h>
+
+enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
+
+struct _transition_t
+{
+  gint action;
+  gint state;
+  symbol_t* left;
+  rule_t* right;
+};
+
+struct _lr1_t
+{
+  nextcb cb;
+  gpointer data;
+  GHashTable* table;
+  GList* stack;
+};
+
+typedef struct
+{
+  gint state;
+  gpointer attrib;
+} state_t;
+
+transition_t* transition_shift_new (gint state)
+{
+  transition_t* transition;
+  transition = g_malloc (sizeof (transition_t));
+  transition->action = PARSER_SHIFT;
+  transition->state = state;
+  transition->left = NULL;
+  transition->right = NULL;
+  return transition;
+}
+
+transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
+{
+  transition_t* transition;
+  transition = g_malloc (sizeof (transition_t));
+  transition->action = PARSER_REDUCE;
+  transition->state = 0;
+  transition->left = left;
+  transition->right = right;
+  return transition;
+}
+
+transition_t* transition_accept_new ()
+{
+  transition_t* transition;
+  transition = g_malloc (sizeof (transition_t));
+  transition->action = PARSER_ACCEPT;
+  transition->state = 0;
+  transition->left = NULL;
+  transition->right = NULL;
+  return transition;
+}
+
+void transition_delete (transition_t* transition)
+{
+  if (transition->left != NULL)
+    g_free (transition->left);
+  if (transition->right != NULL)
+    rule_delete (transition->right);
+  g_free (transition);
+}
+
+static void lr1_push (lr1_t* parser, gint st, gpointer attrib)
+{
+  state_t* state;
+  state = g_malloc (sizeof (state_t));
+  state->state = st;
+  state->attrib = attrib;
+  parser->stack = g_list_prepend (parser->stack, state);
+}
+
+static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
+{
+
+  GList* l;
+  state_t* state;
+  if ((l = g_list_first (parser->stack)) == NULL)
+    return FALSE;
+  parser->stack = g_list_remove_link (l, l);
+  state = (state_t*) l->data;
+  if (attrib)
+    *attrib = state->attrib;
+  g_free (state);
+  g_list_free (l);
+  return TRUE;
+
+}
+
+lr1_t* lr1_new (nextcb cb, gpointer data)
+{
+
+  lr1_t* parser;
+
+  parser = g_malloc (sizeof (lr1_t));
+  parser->cb = cb;
+  parser->data = data;
+
+  parser->stack = NULL;
+  lr1_push (parser, 0, NULL);
+  parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
+                                        NULL, g_hash_table_destroy);
+
+  return parser;
+
+}
+
+void lr1_delete (lr1_t* parser)
+{
+
+  GList* l;
+
+  for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
+    {
+      g_free (l->data);
+    }
+
+  g_list_free (parser->stack);
+
+  g_hash_table_destroy (parser->table);
+
+  g_free (parser);
+
+}
+
+gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
+                 transition_t* transition)
+{
+
+  GHashTable* table;
+
+  if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
+                                    NULL, (gpointer*) &table))
+    {
+      table = g_hash_table_new_full (symbol_hash, symbol_equal,
+                                    g_free, transition_delete);
+      g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
+    }
+
+  if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
+    {
+      return FALSE;
+    }
+
+  g_hash_table_insert (table, symbol, transition);
+  return TRUE;
+
+}
+
+gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
+                    transition_t** transition)
+{
+
+  GHashTable* table;
+  transition_t* trans;
+
+  if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
+                                    NULL, (gpointer*) &table))
+    {
+      return FALSE;
+    }
+
+  if (!g_hash_table_lookup_extended (table, symbol,
+                                    NULL, (gpointer*) &trans))
+    {
+      return FALSE;
+    }
+
+  if (transition)
+    *transition = trans;
+
+  return TRUE;
+
+}
+
+static gpointer leaf_new (gpointer data)
+{
+  return g_node_new (data);
+}
+
+static gpointer tree_new (rule_t* rule)
+{
+  return g_node_new (rule);
+}
+
+static gpointer tree_add (gpointer tree, gpointer data)
+{
+  return g_node_prepend (tree, data);
+}
+
+gpointer lr1_build (lr1_t* parser)
+{
+
+  state_t* state;
+  symbol_t* symbol;
+  transition_t* transition;
+  gpointer attrib;
+  GList* l;
+
+  symbol = g_malloc (sizeof (symbol_t));
+
+  symbol->value = parser->cb (parser->data, &attrib);
+  symbol->terminal = TRUE;
+
+  while (1)
+    {
+
+      l = g_list_first (parser->stack);
+      state = (state_t*) l->data;
+      if (!lr1_lookup (parser, state->state, symbol, &transition))
+       return NULL;
+
+      if (transition->action == PARSER_SHIFT)
+       {
+         gint st;
+         lr1_push (parser, transition->state, leaf_new (attrib));
+         symbol->value = parser->cb (parser->data, &attrib);
+         symbol->terminal = TRUE;
+       }
+
+      else if (transition->action == PARSER_REDUCE)
+       {
+
+         state_t* state;
+         transition_t* trans;
+         GList* l;
+         gpointer attrib;
+
+         attrib = tree_new (symbol_copy (transition->left));
+
+         for (l = grammar_get_rule (transition->right);
+              l != NULL;
+              l = g_list_previous (l))
+           {
+             gpointer attr;
+             if (!lr1_pop (parser, &attr))
+               return NULL;
+             tree_add (attrib, attr);
+           }
+
+         l = g_list_first (parser->stack);
+         state = (state_t*) l->data;
+         lr1_lookup (parser, state->state, transition->left, &trans);
+         lr1_push (parser, trans->state, attrib);
+
+       }
+
+      else if (transition->action == PARSER_ACCEPT)
+       {
+         l = g_list_first (parser->stack);
+         state = (state_t*) l->data;
+         return state->attrib;
+       }
+
+    }
+
+  return NULL;
+
+}

diff --git a/lr1.h b/lr1.h
new file mode 100644 (file)
index 0000000..89de8ce
--- /dev/null
+++ b/lr1.h
@@ -0,0 +1,18 @@
+#ifndef LR1_H
+#define LR1_H
+
+#include <grammar.h>
+
+typedef struct _transition_t transition_t;
+typedef struct _lr1_t lr1_t;
+
+transition_t* transition_shift_new (gint);
+transition_t* transition_reduce_new (symbol_t*, rule_t*);
+transition_t* transition_accept_new ();
+void transition_delete (transition_t*);
+lr1_t* lr1_new (nextcb, gpointer);
+void lr1_delete (lr1_t*);
+void lr1_add (lr1_t*, gint, symbol_t*, transition_t*);
+gpointer lr1_build (lr1_t*);
+
+#endif