2 * Copyright 2005 Thadeu Lima de Souza Cascardo
6 * Code for deterministic finite automata
8 * This code should use a similar hash table as in LR parsers.
9 * However, it will need not stack anything. Table may be fed from a
10 * grammar or a regular expression. A regular expression may be
11 * translated to a grammar and, then, to a finite automata.
36 dfa_state_t* dfa_state_new (gint state, gboolean end)
38 dfa_state_t* dfa_state;
39 dfa_state = g_malloc (sizeof (dfa_state_t));
40 dfa_state->state = state;
45 void dfa_state_delete (dfa_state_t* dfa_state)
50 gint dfa_state_hash (gconstpointer data)
52 dfa_state_t* dfa_state;
53 dfa_state = (dfa_state_t*) data;
54 return g_direct_hash (dfa_state->state);
57 gboolean dfa_state_equal (gconstpointer a, gconstpointer b)
61 dfa_a = (dfa_state_t*) a;
62 dfa_b = (dfa_state_t*) b;
63 return dfa_a->state == dfa_b->state;
66 dfa_t* dfa_new (nextcb cb, gpointer data, dfa_state_t* state)
71 parser = g_malloc (sizeof (dfa_t));
74 parser->start = state;
76 parser->table = g_hash_table_new_full (dfa_state_hash, dfa_state_equal,
77 NULL, g_hash_table_destroy);
83 void dfa_delete (dfa_t* parser)
86 g_hash_table_destroy (parser->table);
92 gboolean dfa_add (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
98 if (!g_hash_table_lookup_extended (parser->table, prev,
99 NULL, (gpointer*) &table))
101 table = g_hash_table_new_full (symbol_hash, symbol_equal,
102 g_free, dfa_state_delete);
103 g_hash_table_insert (parser->table, prev, table);
106 if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
111 g_hash_table_insert (table, symbol, next);
116 gboolean dfa_lookup (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
123 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
124 NULL, (gpointer*) &table))
129 if (!g_hash_table_lookup_extended (table, symbol,
130 NULL, (gpointer*) &n))
142 static gpointer leaf_new (gpointer data)
144 return g_node_new (data);
147 static gpointer tree_new (rule_t* rule)
149 return g_node_new (rule);
152 static gpointer tree_add (gpointer tree, gpointer data)
154 return g_node_prepend (tree, data);
157 gpointer dfa_build (dfa_t* parser)
165 symbol = g_malloc (sizeof (symbol_t));
167 state = parser->start;
173 while (dfa_lookup (parser, state, symbol, &state))
176 symbol->value = parser->cb (parser->data, NULL);
177 symbol->terminal = TRUE;