2 * Copyright (C) 2005 Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 * Copyright 2005 Thadeu Lima de Souza Cascardo
26 * Code for deterministic finite automata
28 * This code should use a similar hash table as in LR parsers.
29 * However, it will need not stack anything. Table may be fed from a
30 * grammar or a regular expression. A regular expression may be
31 * translated to a grammar and, then, to a finite automata.
56 dfa_state_t* dfa_state_new (gint state, gboolean end)
58 dfa_state_t* dfa_state;
59 dfa_state = g_malloc (sizeof (dfa_state_t));
60 dfa_state->state = state;
65 void dfa_state_delete (dfa_state_t* dfa_state)
70 gint dfa_state_hash (gconstpointer data)
72 dfa_state_t* dfa_state;
73 dfa_state = (dfa_state_t*) data;
74 return g_direct_hash (dfa_state->state);
77 gboolean dfa_state_equal (gconstpointer a, gconstpointer b)
81 dfa_a = (dfa_state_t*) a;
82 dfa_b = (dfa_state_t*) b;
83 return dfa_a->state == dfa_b->state;
86 dfa_t* dfa_new (nextcb cb, gpointer data, dfa_state_t* state)
91 parser = g_malloc (sizeof (dfa_t));
94 parser->start = state;
96 parser->table = g_hash_table_new_full (dfa_state_hash, dfa_state_equal,
97 NULL, g_hash_table_destroy);
103 void dfa_delete (dfa_t* parser)
106 g_hash_table_destroy (parser->table);
112 gboolean dfa_add (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
118 if (!g_hash_table_lookup_extended (parser->table, prev,
119 NULL, (gpointer*) &table))
121 table = g_hash_table_new_full (symbol_hash, symbol_equal,
122 g_free, dfa_state_delete);
123 g_hash_table_insert (parser->table, prev, table);
126 if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
131 g_hash_table_insert (table, symbol, next);
136 gboolean dfa_lookup (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
143 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
144 NULL, (gpointer*) &table))
149 if (!g_hash_table_lookup_extended (table, symbol,
150 NULL, (gpointer*) &n))
162 static gpointer leaf_new (gpointer data)
164 return g_node_new (data);
167 static gpointer tree_new (rule_t* rule)
169 return g_node_new (rule);
172 static gpointer tree_add (gpointer tree, gpointer data)
174 return g_node_prepend (tree, data);
177 gpointer dfa_build (dfa_t* parser)
185 symbol = g_malloc (sizeof (symbol_t));
187 state = parser->start;
193 while (dfa_lookup (parser, state, symbol, &state))
196 symbol->value = parser->cb (parser->data, NULL);
197 symbol->terminal = TRUE;