item.c

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