item.c

   1 #include <grammar.h>
   2
   3 typedef struct
   4 {
   5   symbol_t* left;
   6   rule_t* right;
   7   GList* dot;
   8 } item_t;
   9
  10 item_t* item_new (symbol_t* left, rule_t* right)
  11 {
  12   item_t* item;
  13   item = g_malloc (sizeof (item_t));
  14   item->left = left;
  15   item->right = right;
  16   item->dot = grammar_get_rule (right);
  17   return item;
  18 }
  19
  20 item_t* item_copy (item_t* item)
  21 {
  22   item_t* newitem;
  23   int n;
  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);
  27   return newitem;
  28 }
  29
  30 gint item_cmp (const item_t* a, const item_t* b)
  31 {
  32   int c;
  33   int na;
  34   int nb;
  35   if ((c = symbol_cmp (a->left, b->left)) != 0)
  36     return c;
  37   if ((c = rule_cmp (a->right, b->right)) != 0)
  38     return c;
  39   na = g_list_position (grammar_get_rule (a->right), a->dot);
  40   nb = g_list_position (grammar_get_rule (b->right), b->dot);
  41   if (na < nb)
  42     return -1;
  43   else if (na > nb)
  44     return 1;
  45   return 0;
  46 }
  47
  48 gboolean item_equal (gconstpointer data1, gconstpointer data2)
  49 {
  50   return (item_cmp (data1, data2) == 0);
  51 }
  52
  53 guint item_hash (gconstpointer data)
  54 {
  55   item_t* item;
  56   guint hash;
  57   item = (item_t*) data;
  58   hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
  59   return hash;
  60 }
  61
  62 void item_delete (item_t* item)
  63 {
  64   g_free (item->left);
  65   rule_delete (item->right);
  66   g_free (item);
  67 }
  68
  69 GHashTable* item_set_new ()
  70 {
  71   return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL);
  72 }
  73
  74 gboolean item_set_add (GHashTable* item_set, item_t* item)
  75 {
  76   if (!g_hash_table_lookup_extended (item_set, item, NULL, NULL))
  77     {
  78       g_hash_table_insert (item_set, item, NULL);
  79       return TRUE;
  80     }
  81   return FALSE;
  82 }
  83
  84 gboolean item_set_find (gpointer key, gpointer val, gpointer data)
  85 {
  86   return !g_hash_table_lookup_extended (data, key, NULL, NULL);
  87 }
  88
  89 gboolean item_set_equal (gconstpointer a, gconstpointer b)
  90 {
  91   if (g_hash_table_size (a) != g_hash_table_size (b))
  92     return FALSE;
  93   return (g_hash_table_find (a, item_set_find, b) == NULL);
  94 }
  95
  96 void hash_item (gpointer key, gpointer val, gpointer data)
  97 {
  98   guint* hash;
  99   hash = (guint*) data;
 100   *hash = *hash * 37 + item_hash (key);
 101 }
 102
 103 guint item_set_hash (gconstpointer a)
 104 {
 105   guint hash = 0;
 106   g_hash_table_foreach (a, hash_item, &hash);
 107   return hash;
 108 }
 109
 110 void item_set_add_each (gpointer key, gpointer val, gpointer data)
 111 {
 112   item_set_add (data, item_copy (key));
 113 }
 114
 115 GHashTable* item_set_copy (GHashTable* item_set)
 116 {
 117   GHashTable* newitem_set;
 118   newitem_set = item_set_new ();
 119   g_hash_table_foreach (item_set, item_set_add_each, newitem_set);
 120   return newitem_set;
 121 }
 122
 123 void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
 124                             item_t* item)
 125 {
 126   if (item->dot != NULL)
 127     {
 128       symbol_t* symbol;
 129       symbol = (symbol_t*) item->dot->data;
 130       if (symbol->terminal == FALSE)
 131         {
 132           GList* rules;
 133           rules = grammar_get_rules (grammar, symbol);
 134           while (rules != NULL)
 135             {
 136               rule_t* rule;
 137               item_t* newitem;
 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);
 143             }
 144         }
 145     }
 146 }
 147
 148 void put_key_on_list (gpointer key, gpointer val, gpointer data)
 149 {
 150   GList** l;
 151   l = (GList**) data;
 152   *l = g_list_prepend (*l, key);
 153 }
 154
 155 GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
 156 {
 157   int size;
 158   int last_size;
 159   GList* l;
 160   size = g_hash_table_size (item_set);
 161   do
 162     {
 163       last_size = size;
 164       l = NULL;
 165       g_hash_table_foreach (item_set, put_key_on_list, &l);
 166       while (l != NULL)
 167         {
 168           item_set_closure_step (item_set, grammar, l->data);
 169           l = g_list_next (l);
 170         }
 171       g_list_free (l);
 172       size = g_hash_table_size (item_set);
 173     } while (last_size < size);
 174   return item_set;
 175 }
 176
 177 GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
 178                            symbol_t* symbol)
 179 {
 180   GList* l;
 181   GHashTable* newitem_set;
 182   newitem_set = item_set_new ();
 183   l = NULL;
 184   g_hash_table_foreach (item_set, put_key_on_list, &l);
 185   while (l != NULL)
 186     {
 187       item_t* item;
 188       item = item_copy (l->data);
 189       if (item->dot == NULL || !symbol_equal (item->dot->data, symbol))
 190         {
 191           item_delete (item);
 192         }
 193       else
 194         {
 195           item->dot = g_list_next (item->dot);
 196           if (!item_set_add (newitem_set, item))
 197             item_delete (item);
 198         }
 199       l = g_list_next (l);
 200     }
 201   return item_set_closure (newitem_set, grammar);
 202 }
 203
 204
 205 /*
 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
 213  * it).
 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.
 228  */
 229
 230 /*
 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.
 237  */
 238
 239 typedef struct
 240 {
 241   GHashTable* symbols;
 242   gint code;
 243 } state_t;
 244
 245 state_t* state_new (gint code)
 246 {
 247   state_t* state;
 248   state = g_malloc (sizeof (state_t));
 249   state->code = code;
 250   state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 251                                           g_free, NULL);
 252   return state;
 253 }
 254
 255 void state_delete (state_t* state)
 256 {
 257   g_hash_table_destroy (state->symbols);
 258   g_free (state);
 259 }
 260
 261 GHashTable* item_collection_new ()
 262 {
 263   return g_hash_table_new_full (item_set_hash, item_set_equal,
 264                                 g_hash_table_destroy, state_delete);
 265 }
 266
 267 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
 268 {
 269   if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
 270     {
 271       state_t* state;
 272       state = state_new (g_hash_table_size (collection));
 273       g_hash_table_insert (collection, item_set, state);
 274       return TRUE;
 275     }
 276   return FALSE;
 277 }
 278
 279 state_t* item_collection_lookup (GHashTable* collection,
 280                                  GHashTable* item_set)
 281 {
 282   state_t* state;
 283   if (!g_hash_table_lookup_extended (collection, item_set,
 284                                      NULL, (gpointer*)&state))
 285     {
 286       return NULL;
 287     }
 288   return state;
 289 }
 290
 291 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
 292                                   GHashTable* item_set, symbol_t* symbol)
 293 {
 294   state_t* state;
 295   state_t* goto_state;
 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))
 301     {
 302       g_hash_table_destroy (newitem_set);
 303     }
 304   state = item_collection_lookup (collection, item_set);
 305   if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
 306     {
 307       return NULL;
 308     }
 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;
 312   else
 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;
 318 }
 319
 320 void item_set_collection (Grammar* grammar, symbol_t* start)
 321 {
 322   GHashTable* collection;
 323   GHashTable* item_set;
 324   item_t* item;
 325   rule_t* rule;
 326   GList* new_item_sets;
 327   rule = rule_new ();
 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)
 338     {
 339       GHashTable* next_item_set;
 340       GHashTable* new_item_set;
 341       GList* items;
 342       next_item_set = (GHashTable*) new_item_sets->data;
 343       items = NULL;
 344       g_hash_table_foreach (next_item_set, put_key_on_list, &items);
 345       while (items != NULL)
 346         {
 347           item_t* item;
 348           symbol_t* symbol;
 349           item = (item_t*) items->data;
 350           if (item->dot != NULL)
 351             {
 352               symbol = (symbol_t*) item->dot->data;
 353               if ((new_item_set =
 354                    item_collection_goto (collection, grammar,
 355                                          next_item_set, symbol)) != NULL)
 356               {
 357                 g_list_append (new_item_sets, new_item_set);
 358               }
 359             }
 360           items = g_list_next (items);
 361         }
 362       g_list_free (items);
 363       new_item_sets = g_list_next (new_item_sets);
 364     }
 365   g_list_free (new_item_sets);
 366 }