15 item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead)
18 item = g_malloc (sizeof (item_t));
21 item->dot = grammar_get_rule (right);
22 item->lookahead = lookahead;
26 item_t* item_copy (item_t* item)
30 newitem = item_new (symbol_copy (item->left), rule_copy (item->right),
31 symbol_copy (item->lookahead));
32 n = g_list_position (grammar_get_rule (item->right), item->dot);
33 newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n);
37 gint item_cmp (const item_t* a, const item_t* b)
42 if ((c = symbol_cmp (a->left, b->left)) != 0)
44 if ((c = rule_cmp (a->right, b->right)) != 0)
46 if ((c = symbol_cmp (a->lookahead, b->lookahead)) != 0)
48 na = g_list_position (grammar_get_rule (a->right), a->dot);
49 nb = g_list_position (grammar_get_rule (b->right), b->dot);
57 gboolean item_equal (gconstpointer data1, gconstpointer data2)
59 return (item_cmp (data1, data2) == 0);
62 guint item_hash (gconstpointer data)
66 item = (item_t*) data;
67 hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
68 hash = hash * 37 + symbol_hash (item->lookahead);
72 void item_delete (item_t* item)
75 rule_delete (item->right);
76 g_free (item->lookahead);
81 void item_print (item_t* item)
84 fprintf (stdout, "%s -> ", g_quark_to_string (item->left->value));
85 l = grammar_get_rule (item->right);
89 symbol = (symbol_t*) l->data;
92 fprintf (stdout, ".");
94 fprintf (stdout, " %s ", g_quark_to_string (symbol->value));
97 if (item->dot == NULL)
99 fprintf (stdout, ".");
101 fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
105 GHashTable* item_set_new ()
107 return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL);
110 gboolean item_set_add (GHashTable* item_set, item_t* item)
112 if (!g_hash_table_lookup_extended (item_set, item, NULL, NULL))
114 g_hash_table_insert (item_set, item, NULL);
120 static void put_key_on_list (gpointer key, gpointer val, gpointer data)
124 *l = g_list_prepend (*l, key);
127 gboolean item_set_equal (gconstpointer a, gconstpointer b)
131 if (g_hash_table_size (a) != g_hash_table_size (b))
134 g_hash_table_foreach (a, put_key_on_list, (gpointer) &l);
136 while (l != NULL && equal == TRUE)
138 equal = g_hash_table_lookup_extended (b, l->data, NULL, NULL);
145 void hash_item (gpointer key, gpointer val, gpointer data)
148 hash = (guint*) data;
149 *hash = *hash * 37 + item_hash (key);
152 guint item_set_hash (gconstpointer a)
155 g_hash_table_foreach (a, hash_item, &hash);
159 void item_set_add_each (gpointer key, gpointer val, gpointer data)
161 item_set_add (data, item_copy (key));
164 GHashTable* item_set_copy (GHashTable* item_set)
166 GHashTable* newitem_set;
167 newitem_set = item_set_new ();
168 g_hash_table_foreach (item_set, item_set_add_each, newitem_set);
173 void item_set_print_each (gpointer key, gpointer val, gpointer data)
178 void item_set_print (GHashTable* item_set)
180 g_hash_table_foreach (item_set, item_set_print_each, NULL);
184 rule_t* rule_new_item (item_t* item)
190 l = g_list_next (item->dot);
193 rule_append (rule, symbol_copy (l->data));
196 rule_append (rule, symbol_copy (item->lookahead));
201 void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
202 GHashTable* first, item_t* item)
204 if (item->dot != NULL)
207 symbol = (symbol_t*) item->dot->data;
208 if (symbol->terminal == FALSE)
213 rule = rule_new_item (item);
214 terminals = first_rule (first, rule);
216 rules = grammar_get_rules (grammar, symbol);
217 while (rules != NULL)
220 lookahead = terminals;
221 while (lookahead != NULL)
225 rule = rule_copy (rules->data);
226 newitem = item_new (symbol_copy (symbol), rule,
227 symbol_copy (lookahead->data));
228 if (!item_set_add (item_set, newitem))
229 item_delete (newitem);
230 lookahead = g_list_next (lookahead);
232 rules = g_list_next (rules);
234 g_list_free (terminals);
239 GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar,
245 size = g_hash_table_size (item_set);
250 g_hash_table_foreach (item_set, put_key_on_list, &l);
253 item_set_closure_step (item_set, grammar, first, l->data);
257 size = g_hash_table_size (item_set);
258 } while (last_size < size);
262 GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
263 GHashTable* first, symbol_t* symbol)
266 GHashTable* newitem_set;
267 newitem_set = item_set_new ();
269 g_hash_table_foreach (item_set, put_key_on_list, &l);
273 item = item_copy (l->data);
274 if (item->dot == NULL || !symbol_equal (item->dot->data, symbol))
280 item->dot = g_list_next (item->dot);
281 if (!item_set_add (newitem_set, item))
286 return item_set_closure (newitem_set, grammar, first);
291 * This part is a little tricky. We can simply take an approach similar
292 * to the goto approach, adding a new set for every other set and grammar
293 * symbol every time we get a new set.
294 * Although a similar argument about the goto may apply (which is a very
295 * good reason to optimize it), the case for the collection is worse, since
296 * we will be building a new set for the number of sets in the collection
297 * times the number of symbol grammar. (Not building in fact, but computing
299 * Here is an approach that may work:
300 * For each *new* item set, we compute its gotos. Each goto is looked up
301 * in the collection. If it's a new item set, it's included in a list of
302 * new item sets. To compute the gotos of an item set, we should pick only
303 * the grammar symbols that appear in the items' dots. That solves the
304 * problem of getting a list of all the grammar symbols.
305 * So, there will be a list of item sets that we must iterate through. We
306 * add each new list to the hash table too, so we can look it up when we
307 * get a new one. When the list is finished, we are done and do not have to
308 * check the hash table size for each iteration.
309 * So, we need the following functions:
310 * One to check if an item set is already there and add it if it's not.
311 * One to get the symbols hash table, so we can put the computed goto
312 * there anyway. So, that's an add and a lookup.
316 * TODO: associate a number to each item set.
317 * Use a structure to the collection with a counter.
318 * Use another structure to the value in the hash table for each item set.
319 * This structure will have the symbol hash table (for the goto) and the
320 * number associated with the item set.
321 * In fact, the counter may be the hash table size.
324 GHashTable* item_collection_new ()
326 return g_hash_table_new_full (item_set_hash, item_set_equal,
327 g_hash_table_destroy, g_hash_table_destroy);
330 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
333 if (!g_hash_table_lookup_extended (collection, item_set,
334 (gpointer*)key, NULL))
337 symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
339 g_hash_table_insert (collection, item_set, symbols);
345 GHashTable* item_collection_lookup (GHashTable* collection,
346 GHashTable* item_set)
349 if (!g_hash_table_lookup_extended (collection, item_set,
350 NULL, (gpointer*)&symbols))
357 #define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
359 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
361 GHashTable* item_set;
362 item_set = (GHashTable*) key;
363 fprintf (stdout, "Item %x:\n", HASH_ITEM_SET(key));
364 item_set_print (item_set);
365 fprintf (stdout, "\n");
368 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
371 symbol = (symbol_t*) key;
372 fprintf (stdout, "GOTO (%x, %s) =\t %x\n", HASH_ITEM_SET(data),
373 g_quark_to_string (symbol->value), HASH_ITEM_SET(val));
376 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
379 symbols = (GHashTable*) val;
380 g_hash_table_foreach (symbols, item_set_print_goto, key);
381 fprintf (stdout, "\n");
384 void item_collection_print (GHashTable* collection)
386 g_hash_table_foreach (collection, item_collection_print_each, NULL);
387 g_hash_table_foreach (collection, item_collection_print_goto, NULL);
391 GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
392 GHashTable* first, GHashTable* item_set,
396 GHashTable* newitem_set;
397 GHashTable* goto_item_set;
398 GHashTable* old_item_set;
399 newitem_set = item_set_copy (item_set);
400 if (!item_collection_add (collection, newitem_set, NULL))
402 g_hash_table_destroy (newitem_set);
404 symbols = item_collection_lookup (collection, item_set);
405 if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
409 goto_item_set = item_set_goto (item_set, grammar, first, symbol);
410 if (!item_collection_add (collection, goto_item_set, &old_item_set))
412 g_hash_table_insert (symbols, symbol, old_item_set);
413 g_hash_table_destroy (goto_item_set);
418 g_hash_table_insert (symbols, symbol, goto_item_set);
419 return goto_item_set;
423 void item_set_collection (grammar_t* grammar, GHashTable* first, symbol_t* start)
425 GHashTable* collection;
426 GHashTable* item_set;
429 GList* new_item_sets;
431 rule_append (rule, symbol_copy (start));
432 item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0));
433 item_set = item_set_new ();
434 item_set_add (item_set, item);
435 item_set_closure (item_set, grammar, first);
436 collection = g_hash_table_new_full (item_set_hash, item_set_equal,
437 g_hash_table_destroy, NULL);
438 item_collection_add (collection, item_set, NULL);
439 new_item_sets = g_list_append (NULL, item_set);
440 while (new_item_sets != NULL)
442 GHashTable* next_item_set;
443 GHashTable* new_item_set;
445 next_item_set = (GHashTable*) new_item_sets->data;
447 g_hash_table_foreach (next_item_set, put_key_on_list, &items);
448 while (items != NULL)
452 item = (item_t*) items->data;
453 if (item->dot != NULL)
455 symbol = (symbol_t*) item->dot->data;
457 item_collection_goto (collection, grammar, first,
458 next_item_set, symbol)) != NULL)
460 g_list_append (new_item_sets, new_item_set);
463 items = g_list_next (items);
466 new_item_sets = g_list_next (new_item_sets);
468 g_list_free (new_item_sets);
470 item_collection_print (collection);
472 g_hash_table_destroy (collection);