Added DFA code

Deterministic Finite Automata code. It parses regular grammars using a
simple table and no stack. Table should be generated from a grammar or a
regular expression.

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

diff --git a/dfa.c b/dfa.c
new file mode 100644 (file)
index 0000000..9e7776f
--- /dev/null
+++ b/dfa.c
@@ -0,0 +1,186 @@
+/*
+ * Copyright 2005 Thadeu Lima de Souza Cascardo
+ *
+ * libgrammatic
+ *
+ * Code for deterministic finite automata
+ *
+ * This code should use a similar hash table as in LR parsers.
+ * However, it will need not stack anything. Table may be fed from a
+ * grammar or a regular expression. A regular expression may be
+ * translated to a grammar and, then, to a finite automata.
+ *
+ */
+
+#include <grammar.h>
+#include <stdlib.h>
+#include <dfa.h>
+#ifdef DEBUG
+#include <stdio.h>
+#endif
+
+struct _dfa_t
+{
+  nextcb cb;
+  gpointer data;
+  GHashTable* table;
+  dfa_state_t* start;
+};
+
+typedef struct
+{
+  gint state;
+  gboolean end;
+} _dfa_state_t;
+
+dfa_state_t* dfa_state_new (gint state, gboolean end)
+{
+  dfa_state_t* dfa_state;
+  dfa_state = g_malloc (sizeof (dfa_state_t));
+  dfa_state->state = state;
+  dfa_state->end = end;
+  return dfa_state;
+}
+
+void dfa_state_delete (dfa_state_t* dfa_state)
+{
+  g_free (dfa_state);
+}
+
+gint dfa_state_hash (gconstpointer data)
+{
+  dfa_state_t* dfa_state;
+  dfa_state = (dfa_state_t*) data;
+  return g_direct_hash (dfa_state->state);
+}
+
+gboolean dfa_state_equal (gconstpointer a, gconstpointer b)
+{
+  dfa_state_t* dfa_a;
+  dfa_state_t* dfa_b;
+  dfa_a = (dfa_state_t*) a;
+  dfa_b = (dfa_state_t*) b;
+  return dfa_a->state == dfa_b->state;
+}
+
+dfa_t* dfa_new (nextcb cb, gpointer data, dfa_state_t* state)
+{
+
+  dfa_t* parser;
+
+  parser = g_malloc (sizeof (dfa_t));
+  parser->cb = cb;
+  parser->data = data;
+  parser->start = state;
+
+  parser->table = g_hash_table_new_full (dfa_state_hash, dfa_state_equal,
+                                        NULL, g_hash_table_destroy);
+
+  return parser;
+
+}
+
+void dfa_delete (dfa_t* parser)
+{
+
+  g_hash_table_destroy (parser->table);
+
+  g_free (parser);
+
+}
+
+gboolean dfa_add (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
+                 dfa_state_t* next)
+{
+
+  GHashTable* table;
+
+  if (!g_hash_table_lookup_extended (parser->table, prev,
+                                    NULL, (gpointer*) &table))
+    {
+      table = g_hash_table_new_full (symbol_hash, symbol_equal,
+                                    g_free, dfa_state_delete);
+      g_hash_table_insert (parser->table, prev, table);
+    }
+
+  if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
+    {
+      return FALSE;
+    }
+
+  g_hash_table_insert (table, symbol, next);
+  return TRUE;
+
+}
+
+gboolean dfa_lookup (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
+                    dfa_state_t** next)
+{
+
+  GHashTable* table;
+  dfa_state_t* n;
+
+  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*) &n))
+    {
+      return FALSE;
+    }
+
+  if (next)
+    *next = n;
+
+  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 dfa_build (dfa_t* parser)
+{
+
+  dfa_state_t* state;
+  dfa_state_t* last;
+  dfa_state_t* next;
+  symbol_t* symbol;
+
+  symbol = g_malloc (sizeof (symbol_t));
+
+  state = parser->start;
+  last = NULL;
+
+  if (state->end)
+    last = state;
+
+  while (dfa_lookup (parser, state, symbol, &state))
+    {
+
+      symbol->value = parser->cb (parser->data, NULL);
+      symbol->terminal = TRUE;
+
+      if (state->end)
+       last = state;
+
+    }
+
+  return last;
+
+}

diff --git a/dfa.h b/dfa.h
new file mode 100644 (file)
index 0000000..0bb38c2
--- /dev/null
+++ b/dfa.h
@@ -0,0 +1,16 @@
+#ifndef DFA_H
+#define DFA_H
+
+#include <grammar.h>
+
+typedef struct _dfa_state_t dfa_state_t;
+typedef struct _dfa_t dfa_t;
+
+dfa_state_t* dfa_state_new (gint, gboolean);
+void dfa_state_delete (dfa_state_t*);
+dfa_t* dfa_new (nextcb, gpointer);
+void dfa_delete (dfa_t*);
+gboolean dfa_add (dfa_t*, dfa_state_t*, symbol_t*, dfa_state_t*);
+gpointer dfa_build (dfa_t*);
+
+#endif