item.c

   1 #include <grammar.h>
   2 #ifdef DEBUG
   3 #include <stdio.h>
   4 #endif
   5
   6 typedef struct
   7 {
   8   symbol_t* left;
   9   rule_t* right;
  10   GList* dot;
  11 } item_t;
  12
  13 item_t* item_new (symbol_t* left, rule_t* right)
  14 {
  15   item_t* item;
  16   item = g_malloc (sizeof (item_t));
  17   item->left = left;
  18   item->right = right;
  19   item->dot = grammar_get_rule (right);
  20   return item;
  21 }
  22
  23 item_t* item_copy (item_t* item)
  24 {
  25   item_t* newitem;
  26   int n;
  27   newitem = item_new (symbol_copy (item->left), rule_copy (item->right));
  28   n = g_list_position (grammar_get_rule (item->right), item->dot);
  29   newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n);
  30   return newitem;
  31 }
  32
  33 gint item_cmp (const item_t* a, const item_t* b)
  34 {
  35   int c;
  36   int na;
  37   int nb;
  38   if ((c = symbol_cmp (a->left, b->left)) != 0)
  39     return c;
  40   if ((c = rule_cmp (a->right, b->right)) != 0)
  41     return c;
  42   na = g_list_position (grammar_get_rule (a->right), a->dot);
  43   nb = g_list_position (grammar_get_rule (b->right), b->dot);
  44   if (na < nb)
  45     return -1;
  46   else if (na > nb)
  47     return 1;
  48   return 0;
  49 }
  50
  51 gboolean item_equal (gconstpointer data1, gconstpointer data2)
  52 {
  53   return (item_cmp (data1, data2) == 0);
  54 }
  55
  56 guint item_hash (gconstpointer data)
  57 {
  58   item_t* item;
  59   guint hash;
  60   item = (item_t*) data;
  61   hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
  62   return hash;
  63 }
  64
  65 void item_delete (item_t* item)
  66 {
  67   g_free (item->left);
  68   rule_delete (item->right);
  69   g_free (item);
  70 }
  71
  72 #ifdef DEBUG
  73 void item_print (item_t* item)
  74 {
  75   GList* l;
  76   fprintf (stdout, "%s -> ", g_quark_to_string (item->left->value));
  77   l = grammar_get_rule (item->right);
  78   while (l != NULL)
  79     {
  80       symbol_t* symbol;
  81       symbol = (symbol_t*) l->data;
  82       if (l == item->dot)
  83         {
  84           fprintf (stdout, ".");
  85         }
  86       fprintf (stdout, " %s ", g_quark_to_string (symbol->value));
  87       l = g_list_next (l);
  88     }
  89   if (item->dot == NULL)
  90     {
  91       fprintf (stdout, ".");
  92     }
  93   fprintf (stdout, "\n");
  94 }
  95 #endif
  96
  97 GHashTable* item_set_new ()
  98 {
  99   return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL);
 100 }
 101
 102 gboolean item_set_add (GHashTable* item_set, item_t* item)
 103 {
 104   if (!g_hash_table_lookup_extended (item_set, item, NULL, NULL))
 105     {
 106       g_hash_table_insert (item_set, item, NULL);
 107       return TRUE;
 108     }
 109   return FALSE;
 110 }
 111
 112 static void put_key_on_list (gpointer key, gpointer val, gpointer data)
 113 {
 114   GList** l;
 115   l = (GList**) data;
 116   *l = g_list_prepend (*l, key);
 117 }
 118
 119 gboolean item_set_equal (gconstpointer a, gconstpointer b)
 120 {
 121   GList* l;
 122   gboolean equal;
 123   if (g_hash_table_size (a) != g_hash_table_size (b))
 124     return FALSE;
 125   l = NULL;
 126   g_hash_table_foreach (a, put_key_on_list, (gpointer) &l);
 127   equal = TRUE;
 128   while (l != NULL && equal == TRUE)
 129     {
 130       equal = g_hash_table_lookup_extended (b, l->data, NULL, NULL);
 131       l = g_list_next (l);
 132     }
 133   g_list_free (l);
 134   return equal;
 135 }
 136
 137 void hash_item (gpointer key, gpointer val, gpointer data)
 138 {
 139   guint* hash;
 140   hash = (guint*) data;
 141   *hash = *hash * 37 + item_hash (key);
 142 }
 143
 144 guint item_set_hash (gconstpointer a)
 145 {
 146   guint hash = 0;
 147   g_hash_table_foreach (a, hash_item, &hash);
 148   return hash;
 149 }
 150
 151 void item_set_add_each (gpointer key, gpointer val, gpointer data)
 152 {
 153   item_set_add (data, item_copy (key));
 154 }
 155
 156 GHashTable* item_set_copy (GHashTable* item_set)
 157 {
 158   GHashTable* newitem_set;
 159   newitem_set = item_set_new ();
 160   g_hash_table_foreach (item_set, item_set_add_each, newitem_set);
 161   return newitem_set;
 162 }
 163
 164 #ifdef DEBUG
 165 void item_set_print_each (gpointer key, gpointer val, gpointer data)
 166 {
 167   item_print (key);
 168 }
 169
 170 void item_set_print (GHashTable* item_set)
 171 {
 172   g_hash_table_foreach (item_set, item_set_print_each, NULL);
 173 }
 174 #endif
 175
 176 void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
 177                             item_t* item)
 178 {
 179   if (item->dot != NULL)
 180     {
 181       symbol_t* symbol;
 182       symbol = (symbol_t*) item->dot->data;
 183       if (symbol->terminal == FALSE)
 184         {
 185           GList* rules;
 186           rules = grammar_get_rules (grammar, symbol);
 187           while (rules != NULL)
 188             {
 189               rule_t* rule;
 190               item_t* newitem;
 191               rule = rule_copy (rules->data);
 192               newitem = item_new (symbol_copy (symbol), rule);
 193               if (!item_set_add (item_set, newitem))
 194                 item_delete (newitem);
 195               rules = g_list_next (rules);
 196             }
 197         }
 198     }
 199 }
 200
 201 GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar)
 202 {
 203   int size;
 204   int last_size;
 205   GList* l;
 206   size = g_hash_table_size (item_set);
 207   do
 208     {
 209       last_size = size;
 210       l = NULL;
 211       g_hash_table_foreach (item_set, put_key_on_list, &l);
 212       while (l != NULL)
 213         {
 214           item_set_closure_step (item_set, grammar, l->data);
 215           l = g_list_next (l);
 216         }
 217       g_list_free (l);
 218       size = g_hash_table_size (item_set);
 219     } while (last_size < size);
 220   return item_set;
 221 }
 222
 223 GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
 224                            symbol_t* symbol)
 225 {
 226   GList* l;
 227   GHashTable* newitem_set;
 228   newitem_set = item_set_new ();
 229   l = NULL;
 230   g_hash_table_foreach (item_set, put_key_on_list, &l);
 231   while (l != NULL)
 232     {
 233       item_t* item;
 234       item = item_copy (l->data);
 235       if (item->dot == NULL || !symbol_equal (item->dot->data, symbol))
 236         {
 237           item_delete (item);
 238         }
 239       else
 240         {
 241           item->dot = g_list_next (item->dot);
 242           if (!item_set_add (newitem_set, item))
 243             item_delete (item);
 244         }
 245       l = g_list_next (l);
 246     }
 247   return item_set_closure (newitem_set, grammar);
 248 }
 249
 250
 251 /*
 252  * This part is a little tricky. We can simply take an approach similar
 253  * to the goto approach, adding a new set for every other set and grammar
 254  * symbol every time we get a new set.
 255  * Although a similar argument about the goto may apply (which is a very
 256  * good reason to optimize it), the case for the collection is worse, since
 257  * we will be building a new set for the number of sets in the collection
 258  * times the number of symbol grammar. (Not building in fact, but computing
 259  * it).
 260  * Here is an approach that may work:
 261  * For each *new* item set, we compute its gotos. Each goto is looked up
 262  * in the collection. If it's a new item set, it's included in a list of
 263  * new item sets. To compute the gotos of an item set, we should pick only
 264  * the grammar symbols that appear in the items' dots. That solves the
 265  * problem of getting a list of all the grammar symbols.
 266  * So, there will be a list of item sets that we must iterate through. We
 267  * add each new list to the hash table too, so we can look it up when we
 268  * get a new one. When the list is finished, we are done and do not have to
 269  * check the hash table size for each iteration.
 270  * So, we need the following functions:
 271  * One to check if an item set is already there and add it if it's not.
 272  * One to get the symbols hash table, so we can put the computed goto
 273  * there anyway. So, that's an add and a lookup.
 274  */
 275
 276 /*
 277  * TODO: associate a number to each item set.
 278  * Use a structure to the collection with a counter.
 279  * Use another structure to the value in the hash table for each item set.
 280  * This structure will have the symbol hash table (for the goto) and the
 281  * number associated with the item set.
 282  * In fact, the counter may be the hash table size.
 283  */
 284
 285 GHashTable* item_collection_new ()
 286 {
 287   return g_hash_table_new_full (item_set_hash, item_set_equal,
 288                                 g_hash_table_destroy, g_hash_table_destroy);
 289 }
 290
 291 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
 292                               GHashTable** key)
 293 {
 294   if (!g_hash_table_lookup_extended (collection, item_set,
 295                                      (gpointer*)key, NULL))
 296     {
 297       GHashTable* symbols;
 298       symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 299                                        g_free, NULL);
 300       g_hash_table_insert (collection, item_set, symbols);
 301       return TRUE;
 302     }
 303   return FALSE;
 304 }
 305
 306 GHashTable* item_collection_lookup (GHashTable* collection,
 307                                     GHashTable* item_set)
 308 {
 309   GHashTable* symbols;
 310   if (!g_hash_table_lookup_extended (collection, item_set,
 311                                      NULL, (gpointer*)&symbols))
 312     {
 313       return NULL;
 314     }
 315   return symbols;
 316 }
 317
 318 #define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
 319 #ifdef DEBUG
 320 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 321 {
 322   GHashTable* item_set;
 323   item_set = (GHashTable*) key;
 324   fprintf (stdout, "Item %x:\n", HASH_ITEM_SET(key));
 325   item_set_print (item_set);
 326   fprintf (stdout, "\n");
 327 }
 328
 329 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
 330 {
 331   symbol_t* symbol;
 332   symbol = (symbol_t*) key;
 333   fprintf (stdout, "GOTO (%x, %s) =\t %x\n", HASH_ITEM_SET(data),
 334            g_quark_to_string (symbol->value), HASH_ITEM_SET(val));
 335 }
 336
 337 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
 338 {
 339   GHashTable* symbols;
 340   symbols = (GHashTable*) val;
 341   g_hash_table_foreach (symbols, item_set_print_goto, key);
 342   fprintf (stdout, "\n");
 343 }
 344
 345 void item_collection_print (GHashTable* collection)
 346 {
 347   g_hash_table_foreach (collection, item_collection_print_each, NULL);
 348   g_hash_table_foreach (collection, item_collection_print_goto, NULL);
 349 }
 350 #endif
 351
 352 GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
 353                                   GHashTable* item_set, symbol_t* symbol)
 354 {
 355   GHashTable* symbols;
 356   GHashTable* newitem_set;
 357   GHashTable* goto_item_set;
 358   GHashTable* old_item_set;
 359   newitem_set = item_set_copy (item_set);
 360   if (!item_collection_add (collection, newitem_set, NULL))
 361     {
 362       g_hash_table_destroy (newitem_set);
 363     }
 364   symbols = item_collection_lookup (collection, item_set);
 365   if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
 366     {
 367       return NULL;
 368     }
 369   goto_item_set = item_set_goto (item_set, grammar, symbol);
 370   if (!item_collection_add (collection, goto_item_set, &old_item_set))
 371     {
 372       g_hash_table_insert (symbols, symbol, old_item_set);
 373       g_hash_table_destroy (goto_item_set);
 374       return NULL;
 375     }
 376   else
 377     {
 378       g_hash_table_insert (symbols, symbol, goto_item_set);
 379       return goto_item_set;
 380     }
 381 }
 382
 383 void item_set_collection (grammar_t* grammar, symbol_t* start)
 384 {
 385   GHashTable* collection;
 386   GHashTable* item_set;
 387   item_t* item;
 388   rule_t* rule;
 389   GList* new_item_sets;
 390   rule = rule_new ();
 391   rule_append (rule, symbol_copy (start));
 392   item = item_new (symbol_new (FALSE, -1), rule);
 393   item_set = item_set_new ();
 394   item_set_add (item_set, item);
 395   item_set_closure (item_set, grammar);
 396   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
 397                                       g_hash_table_destroy, NULL);
 398   item_collection_add (collection, item_set, NULL);
 399   new_item_sets = g_list_append (NULL, item_set);
 400   while (new_item_sets != NULL)
 401     {
 402       GHashTable* next_item_set;
 403       GHashTable* new_item_set;
 404       GList* items;
 405       next_item_set = (GHashTable*) new_item_sets->data;
 406       items = NULL;
 407       g_hash_table_foreach (next_item_set, put_key_on_list, &items);
 408       while (items != NULL)
 409         {
 410           item_t* item;
 411           symbol_t* symbol;
 412           item = (item_t*) items->data;
 413           if (item->dot != NULL)
 414             {
 415               symbol = (symbol_t*) item->dot->data;
 416               if ((new_item_set =
 417                    item_collection_goto (collection, grammar,
 418                                          next_item_set, symbol)) != NULL)
 419               {
 420                 g_list_append (new_item_sets, new_item_set);
 421               }
 422             }
 423           items = g_list_next (items);
 424         }
 425       g_list_free (items);
 426       new_item_sets = g_list_next (new_item_sets);
 427     }
 428   g_list_free (new_item_sets);
 429 #ifdef DEBUG
 430   item_collection_print (collection);
 431 #endif
 432   g_hash_table_destroy (collection);
 433 }