--- /dev/null
+/*
+ * 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;
+
+}