#include <grammar.h>
+#include <first.h>
+#include <item.h>
#ifdef DEBUG
#include <stdio.h>
#endif
-typedef struct
-{
- symbol_t* left;
- rule_t* right;
- GList* dot;
-} item_t;
-
-item_t* item_new (symbol_t* left, rule_t* right)
+item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead)
{
item_t* item;
item = g_malloc (sizeof (item_t));
item->left = left;
item->right = right;
item->dot = grammar_get_rule (right);
+ item->lookahead = lookahead;
return item;
}
{
item_t* newitem;
int n;
- newitem = item_new (symbol_copy (item->left), rule_copy (item->right));
+ newitem = item_new (symbol_copy (item->left), rule_copy (item->right),
+ symbol_copy (item->lookahead));
n = g_list_position (grammar_get_rule (item->right), item->dot);
newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n);
return newitem;
return c;
if ((c = rule_cmp (a->right, b->right)) != 0)
return c;
+ if ((c = symbol_cmp (a->lookahead, b->lookahead)) != 0)
+ return c;
na = g_list_position (grammar_get_rule (a->right), a->dot);
nb = g_list_position (grammar_get_rule (b->right), b->dot);
if (na < nb)
guint hash;
item = (item_t*) data;
hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
+ hash = hash * 37 + symbol_hash (item->lookahead);
return hash;
}
{
g_free (item->left);
rule_delete (item->right);
+ g_free (item->lookahead);
g_free (item);
}
{
fprintf (stdout, ".");
}
- fprintf (stdout, "\n");
+ fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
}
#endif
}
#endif
-void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
- item_t* item)
+rule_t* rule_new_item (item_t* item)
+{
+
+ rule_t* rule;
+ GList* l;
+ rule = rule_new ();
+ l = g_list_next (item->dot);
+ while (l != NULL)
+ {
+ rule_append (rule, symbol_copy (l->data));
+ l = g_list_next (l);
+ }
+ rule_append (rule, symbol_copy (item->lookahead));
+ return rule;
+
+}
+
+void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
+ GHashTable* first, item_t* item)
{
if (item->dot != NULL)
{
if (symbol->terminal == FALSE)
{
GList* rules;
+ GList* terminals;
+ rule_t* rule;
+ rule = rule_new_item (item);
+ terminals = first_rule (first, rule);
+ rule_delete (rule);
rules = grammar_get_rules (grammar, symbol);
while (rules != NULL)
{
- rule_t* rule;
- item_t* newitem;
- rule = rule_copy (rules->data);
- newitem = item_new (symbol_copy (symbol), rule);
- if (!item_set_add (item_set, newitem))
- item_delete (newitem);
+ GList* lookahead;
+ lookahead = terminals;
+ while (lookahead != NULL)
+ {
+ rule_t* rule;
+ item_t* newitem;
+ rule = rule_copy (rules->data);
+ newitem = item_new (symbol_copy (symbol), rule,
+ symbol_copy (lookahead->data));
+ if (!item_set_add (item_set, newitem))
+ item_delete (newitem);
+ lookahead = g_list_next (lookahead);
+ }
rules = g_list_next (rules);
}
+ g_list_free (terminals);
}
}
}
-GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
+GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar,
+ GHashTable* first)
{
int size;
int last_size;
g_hash_table_foreach (item_set, put_key_on_list, &l);
while (l != NULL)
{
- item_set_closure_step (item_set, grammar, l->data);
+ item_set_closure_step (item_set, grammar, first, l->data);
l = g_list_next (l);
}
g_list_free (l);
return item_set;
}
-GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
- symbol_t* symbol)
+GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
+ GHashTable* first, symbol_t* symbol)
{
GList* l;
GHashTable* newitem_set;
}
l = g_list_next (l);
}
- return item_set_closure (newitem_set, grammar);
+ return item_set_closure (newitem_set, grammar, first);
}
* In fact, the counter may be the hash table size.
*/
-typedef struct
-{
- GHashTable* symbols;
- gint code;
-} state_t;
-
-state_t* state_new (gint code)
-{
- state_t* state;
- state = g_malloc (sizeof (state_t));
- state->code = code;
- state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
- g_free, NULL);
- return state;
-}
-
-void state_delete (state_t* state)
-{
- g_hash_table_destroy (state->symbols);
- g_free (state);
-}
-
GHashTable* item_collection_new ()
{
return g_hash_table_new_full (item_set_hash, item_set_equal,
- g_hash_table_destroy, state_delete);
+ g_hash_table_destroy, g_hash_table_destroy);
}
-gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
+gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
+ GHashTable** key)
{
- if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
+ if (!g_hash_table_lookup_extended (collection, item_set,
+ (gpointer*)key, NULL))
{
- state_t* state;
- state = state_new (g_hash_table_size (collection));
- g_hash_table_insert (collection, item_set, state);
+ GHashTable* symbols;
+ symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
+ g_free, NULL);
+ g_hash_table_insert (collection, item_set, symbols);
return TRUE;
}
return FALSE;
}
-state_t* item_collection_lookup (GHashTable* collection,
- GHashTable* item_set)
+GHashTable* item_collection_lookup (GHashTable* collection,
+ GHashTable* item_set)
{
- state_t* state;
+ GHashTable* symbols;
if (!g_hash_table_lookup_extended (collection, item_set,
- NULL, (gpointer*)&state))
+ NULL, (gpointer*)&symbols))
{
return NULL;
}
- return state;
+ return symbols;
}
+#define HASH_ITEM_SET(item_set) (item_set)
#ifdef DEBUG
void item_collection_print_each (gpointer key, gpointer val, gpointer data)
{
GHashTable* item_set;
- state_t* state;
item_set = (GHashTable*) key;
- state = (state_t*) val;
- fprintf (stdout, "Item %d:\n", state->code);
+ fprintf (stdout, "Item %p:\n", HASH_ITEM_SET(key));
item_set_print (item_set);
fprintf (stdout, "\n");
}
void item_set_print_goto (gpointer key, gpointer val, gpointer data)
{
symbol_t* symbol;
- gint code;
- state_t* state;
symbol = (symbol_t*) key;
- code = GINT_TO_POINTER (val);
- state = (state_t*) data;
- fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
- g_quark_to_string (symbol->value), code);
+ fprintf (stdout, "GOTO (%p, %s) =\t %p\n", HASH_ITEM_SET(data),
+ g_quark_to_string (symbol->value), HASH_ITEM_SET(val));
}
void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
{
- state_t* state;
- state = (state_t*) val;
- g_hash_table_foreach (state->symbols, item_set_print_goto, state);
+ GHashTable* symbols;
+ symbols = (GHashTable*) val;
+ g_hash_table_foreach (symbols, item_set_print_goto, key);
fprintf (stdout, "\n");
}
}
#endif
-GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
- GHashTable* item_set, symbol_t* symbol)
+GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
+ GHashTable* first, GHashTable* item_set,
+ symbol_t* symbol)
{
- state_t* state;
- state_t* goto_state;
+
+ GHashTable* symbols;
GHashTable* newitem_set;
GHashTable* goto_item_set;
- GHashTable* return_item_set;
+ GHashTable* old_item_set;
+
+ /*
+ * Is it a new item set? Why should we insert a copy of it? Do we
+ * destroy the original later?
+ *
+ * TODO: Check why this code was once here. WTF! Caused some damn
+ * bug.
+ */
+ /*
newitem_set = item_set_copy (item_set);
- if (!item_collection_add (collection, newitem_set))
+ if (!item_collection_add (collection, newitem_set, NULL))
{
g_hash_table_destroy (newitem_set);
}
- state = item_collection_lookup (collection, item_set);
- if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
+ */
+
+ /*
+ * Is there a computed goto from this item set with this symbol
+ * already?
+ */
+ symbols = item_collection_lookup (collection, item_set);
+ if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
{
return NULL;
}
- goto_item_set = item_set_goto (item_set, grammar, symbol);
- if (!item_collection_add (collection, goto_item_set))
- return_item_set = NULL;
+
+ /*
+ * If the computed goto already exists in the table, retrieve it and
+ * add the entry in the table pointing to it instead of the newly
+ * computed item set. Destroy the new copy. We don't need it. Only
+ * return the computed goto if it's a new item set.
+ */
+ goto_item_set = item_set_goto (item_set, grammar, first, symbol);
+ if (!item_collection_add (collection, goto_item_set, &old_item_set))
+ {
+ g_hash_table_insert (symbols, symbol, old_item_set);
+ g_hash_table_destroy (goto_item_set);
+ return NULL;
+ }
else
- return_item_set = goto_item_set;
- goto_state = item_collection_lookup (collection, goto_item_set);
- g_hash_table_insert (state->symbols, symbol,
- GINT_TO_POINTER (goto_state->code));
- return return_item_set;
+ {
+ g_hash_table_insert (symbols, symbol, goto_item_set);
+ return goto_item_set;
+ }
+}
+
+void get_symbol_at_dot (gpointer key, gpointer val, gpointer data)
+{
+ item_t* item;
+ GHashTable* symbols;
+ symbol_t* symbol;
+ item = (item_t*) key;
+ symbols = (GHashTable*) data;
+ if (item->dot != NULL)
+ {
+ symbol = item->dot->data;
+ if (!g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
+ {
+ g_hash_table_insert (symbols, symbol, NULL);
+ }
+ }
+}
+
+/* Get the symbols at the dot in this item set */
+GList* item_set_symbols_at_dot (GHashTable* item_set)
+{
+ GHashTable* symbols;
+ GList* symbols_list;
+ symbols_list = NULL;
+ symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
+ NULL, NULL);
+ g_hash_table_foreach (item_set, get_symbol_at_dot, symbols);
+ g_hash_table_foreach (symbols, put_key_on_list, &symbols_list);
+ g_hash_table_destroy (symbols);
+ return symbols_list;
}
-void item_set_collection (Grammar* grammar, symbol_t* start)
+GHashTable* item_set_collection (grammar_t* grammar, GHashTable* first,
+ symbol_t* start)
{
+
GHashTable* collection;
GHashTable* item_set;
item_t* item;
rule_t* rule;
GList* new_item_sets;
+
+ /* Augmented grammar has start symbol S' -> S */
rule = rule_new ();
rule_append (rule, symbol_copy (start));
- item = item_new (symbol_new (FALSE, -1), rule);
+
+ /* First item set is the closure of the item set with S' -> . S , $ */
+ item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0));
item_set = item_set_new ();
item_set_add (item_set, item);
- item_set_closure (item_set, grammar);
+ item_set_closure (item_set, grammar, first);
+
+ /* Insert first item set in the collection of item sets and start working */
collection = g_hash_table_new_full (item_set_hash, item_set_equal,
g_hash_table_destroy, NULL);
- item_collection_add (collection, item_set);
+ item_collection_add (collection, item_set, NULL);
+
new_item_sets = g_list_append (NULL, item_set);
+
while (new_item_sets != NULL)
{
GHashTable* next_item_set;
GHashTable* new_item_set;
- GList* items;
+ GList* symbols;
+ /*
+ * For each item, compute the goto for the symbol at its
+ * dot. Should be done only for each symbol at a dot in the
+ * whole item set. Only new item sets are put in the new item
+ * sets list. Check item_collection_goto.
+ *
+ * TODO: Only do this for each symbol at a dot in the item set.
+ */
next_item_set = (GHashTable*) new_item_sets->data;
- items = NULL;
- g_hash_table_foreach (next_item_set, put_key_on_list, &items);
- while (items != NULL)
+ symbols = item_set_symbols_at_dot (next_item_set);
+ while (symbols != NULL)
{
- item_t* item;
symbol_t* symbol;
- item = (item_t*) items->data;
- if (item->dot != NULL)
+ symbol = (symbol_t*) symbols->data;
+ if ((new_item_set =
+ item_collection_goto (collection, grammar, first,
+ next_item_set, symbol)) != NULL)
{
- symbol = (symbol_t*) item->dot->data;
- if ((new_item_set =
- item_collection_goto (collection, grammar,
- next_item_set, symbol)) != NULL)
- {
- g_list_append (new_item_sets, new_item_set);
- }
+ g_list_append (new_item_sets, new_item_set);
}
- items = g_list_next (items);
+ symbols = g_list_next (symbols);
}
- g_list_free (items);
+ g_list_free (symbols);
new_item_sets = g_list_next (new_item_sets);
}
+
g_list_free (new_item_sets);
+
#ifdef DEBUG
item_collection_print (collection);
#endif
- g_hash_table_destroy (collection);
+
+ return collection;
+
}