10 item_t* item_new (symbol_t* left, rule_t* right)
13 item = g_malloc (sizeof (item_t));
16 item->dot = grammar_get_rule (right);
20 item_t* item_copy (item_t* item)
24 newitem = item_new (symbol_copy (item->left), rule_copy (item->right));
25 n = g_list_position (grammar_get_rule (item->right), item->dot);
26 newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n);
30 gint item_cmp (const item_t* a, const item_t* b)
35 if ((c = symbol_cmp (a->left, b->left)) != 0)
37 if ((c = rule_cmp (a->right, b->right)) != 0)
39 na = g_list_position (grammar_get_rule (a->right), a->dot);
40 nb = g_list_position (grammar_get_rule (b->right), b->dot);
48 gboolean item_equal (gconstpointer data1, gconstpointer data2)
50 return (item_cmp (data1, data2) == 0);
53 guint item_hash (gconstpointer data)
57 item = (item_t*) data;
58 hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
62 void item_delete (item_t* item)
65 rule_delete (item->right);
69 GHashTable* item_set_new ()
71 return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL);
74 gboolean item_set_add (GHashTable* item_set, item_t* item)
76 if (!g_hash_table_lookup_extended (item_set, item, NULL, NULL))
78 g_hash_table_insert (item_set, item, NULL);
84 gboolean item_set_find (gpointer key, gpointer val, gpointer data)
86 return !g_hash_table_lookup_extended (data, key, NULL, NULL);
89 gboolean item_set_equal (gconstpointer a, gconstpointer b)
91 if (g_hash_table_size (a) != g_hash_table_size (b))
93 return (g_hash_table_find (a, item_set_find, b) == NULL);
96 void hash_item (gpointer key, gpointer val, gpointer data)
100 *hash = *hash * 37 + item_hash (key);
103 guint item_set_hash (gconstpointer a)
106 g_hash_table_foreach (a, hash_item, &hash);
110 void item_set_add_each (gpointer key, gpointer val, gpointer data)
112 item_set_add (data, item_copy (key));
115 GHashTable* item_set_copy (GHashTable* item_set)
117 GHashTable* newitem_set;
118 newitem_set = item_set_new ();
119 g_hash_table_foreach (item_set, item_set_add_each, newitem_set);
123 void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
126 if (item->dot != NULL)
129 symbol = (symbol_t*) item->dot->data;
130 if (symbol->terminal == FALSE)
133 rules = grammar_get_rules (grammar, symbol);
134 while (rules != NULL)
138 rule = rule_copy (rules->data);
139 newitem = item_new (symbol_copy (symbol), rule);
140 if (!item_set_add (item_set, newitem))
141 item_delete (newitem);
142 rules = g_list_next (rules);
148 void put_key_on_list (gpointer key, gpointer val, gpointer data)
152 *l = g_list_prepend (*l, key);
155 GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
160 size = g_hash_table_size (item_set);
165 g_hash_table_foreach (item_set, put_key_on_list, &l);
168 item_set_closure_step (item_set, grammar, l->data);
172 size = g_hash_table_size (item_set);
173 } while (last_size < size);
177 GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
181 GHashTable* newitem_set;
182 newitem_set = item_set_new ();
184 g_hash_table_foreach (item_set, put_key_on_list, &l);
188 item = item_copy (l->data);
189 if (item->dot == NULL || !symbol_equal (item->dot->data, symbol))
195 item->dot = g_list_next (item->dot);
196 if (!item_set_add (newitem_set, item))
201 return item_set_closure (newitem_set, grammar);
206 * This part is a little tricky. We can simply take an approach similar
207 * to the goto approach, adding a new set for every other set and grammar
208 * symbol every time we get a new set.
209 * Although a similar argument about the goto may apply (which is a very
210 * good reason to optimize it), the case for the collection is worse, since
211 * we will be building a new set for the number of sets in the collection
212 * times the number of symbol grammar. (Not building in fact, but computing
214 * Here is an approach that may work:
215 * For each *new* item set, we compute its gotos. Each goto is looked up
216 * in the collection. If it's a new item set, it's included in a list of
217 * new item sets. To compute the gotos of an item set, we should pick only
218 * the grammar symbols that appear in the items' dots. That solves the
219 * problem of getting a list of all the grammar symbols.
220 * So, there will be a list of item sets that we must iterate through. We
221 * add each new list to the hash table too, so we can look it up when we
222 * get a new one. When the list is finished, we are done and do not have to
223 * check the hash table size for each iteration.
224 * So, we need the following functions:
225 * One to check if an item set is already there and add it if it's not.
226 * One to get the symbols hash table, so we can put the computed goto
227 * there anyway. So, that's an add and a lookup.
231 * TODO: associate a number to each item set.
232 * Use a structure to the collection with a counter.
233 * Use another structure to the value in the hash table for each item set.
234 * This structure will have the symbol hash table (for the goto) and the
235 * number associated with the item set.
236 * In fact, the counter may be the hash table size.
245 state_t* state_new (gint code)
248 state = g_malloc (sizeof (state_t));
250 state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
255 void state_delete (state_t* state)
257 g_hash_table_destroy (state->symbols);
261 GHashTable* item_collection_new ()
263 return g_hash_table_new_full (item_set_hash, item_set_equal,
264 g_hash_table_destroy, state_delete);
267 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
269 if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
272 state = state_new (g_hash_table_size (collection));
273 g_hash_table_insert (collection, item_set, state);
279 state_t* item_collection_lookup (GHashTable* collection,
280 GHashTable* item_set)
283 if (!g_hash_table_lookup_extended (collection, item_set,
284 NULL, (gpointer*)&state))
291 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
292 GHashTable* item_set, symbol_t* symbol)
296 GHashTable* newitem_set;
297 GHashTable* goto_item_set;
298 GHashTable* return_item_set;
299 newitem_set = item_set_copy (item_set);
300 if (!item_collection_add (collection, newitem_set))
302 g_hash_table_destroy (newitem_set);
304 state = item_collection_lookup (collection, item_set);
305 if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
309 goto_item_set = item_set_goto (item_set, grammar, symbol);
310 if (!item_collection_add (collection, goto_item_set))
311 return_item_set = NULL;
313 return_item_set = goto_item_set;
314 goto_state = item_collection_lookup (collection, goto_item_set);
315 g_hash_table_insert (state->symbols, symbol,
316 GINT_TO_POINTER (goto_state->code));
317 return return_item_set;
320 void item_set_collection (Grammar* grammar, symbol_t* start)
322 GHashTable* collection;
323 GHashTable* item_set;
326 GList* new_item_sets;
328 rule_append (rule, symbol_copy (start));
329 item = item_new (symbol_new (FALSE, -1), rule);
330 item_set = item_set_new ();
331 item_set_add (item_set, item);
332 item_set_closure (item_set, grammar);
333 collection = g_hash_table_new_full (item_set_hash, item_set_equal,
334 g_hash_table_destroy, NULL);
335 item_collection_add (collection, item_set);
336 new_item_sets = g_list_append (NULL, item_set);
337 while (new_item_sets != NULL)
339 GHashTable* next_item_set;
340 GHashTable* new_item_set;
342 next_item_set = (GHashTable*) new_item_sets->data;
344 g_hash_table_foreach (next_item_set, put_key_on_list, &items);
345 while (items != NULL)
349 item = (item_t*) items->data;
350 if (item->dot != NULL)
352 symbol = (symbol_t*) item->dot->data;
354 item_collection_goto (collection, grammar,
355 next_item_set, symbol)) != NULL)
357 g_list_append (new_item_sets, new_item_set);
360 items = g_list_next (items);
363 new_item_sets = g_list_next (new_item_sets);
365 g_list_free (new_item_sets);