item.c

   1 #include <grammar.h>
   2 #include <first.h>
   3 #ifdef DEBUG
   4 #include <stdio.h>
   5 #endif
   6
   7 typedef struct
   8 {
   9   symbol_t* left;
  10   rule_t* right;
  11   GList* dot;
  12   symbol_t* lookahead;
  13 } item_t;
  14
  15 item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead)
  16 {
  17   item_t* item;
  18   item = g_malloc (sizeof (item_t));
  19   item->left = left;
  20   item->right = right;
  21   item->dot = grammar_get_rule (right);
  22   item->lookahead = lookahead;
  23   return item;
  24 }
  25
  26 item_t* item_copy (item_t* item)
  27 {
  28   item_t* newitem;
  29   int n;
  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);
  34   return newitem;
  35 }
  36
  37 gint item_cmp (const item_t* a, const item_t* b)
  38 {
  39   int c;
  40   int na;
  41   int nb;
  42   if ((c = symbol_cmp (a->left, b->left)) != 0)
  43     return c;
  44   if ((c = rule_cmp (a->right, b->right)) != 0)
  45     return c;
  46   if ((c = symbol_cmp (a->lookahead, b->lookahead)) != 0)
  47     return c;
  48   na = g_list_position (grammar_get_rule (a->right), a->dot);
  49   nb = g_list_position (grammar_get_rule (b->right), b->dot);
  50   if (na < nb)
  51     return -1;
  52   else if (na > nb)
  53     return 1;
  54   return 0;
  55 }
  56
  57 gboolean item_equal (gconstpointer data1, gconstpointer data2)
  58 {
  59   return (item_cmp (data1, data2) == 0);
  60 }
  61
  62 guint item_hash (gconstpointer data)
  63 {
  64   item_t* item;
  65   guint hash;
  66   item = (item_t*) data;
  67   hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
  68   hash = hash * 37 + symbol_hash (item->lookahead);
  69   return hash;
  70 }
  71
  72 void item_delete (item_t* item)
  73 {
  74   g_free (item->left);
  75   rule_delete (item->right);
  76   g_free (item->lookahead);
  77   g_free (item);
  78 }
  79
  80 #ifdef DEBUG
  81 void item_print (item_t* item)
  82 {
  83   GList* l;
  84   fprintf (stdout, "%s -> ", g_quark_to_string (item->left->value));
  85   l = grammar_get_rule (item->right);
  86   while (l != NULL)
  87     {
  88       symbol_t* symbol;
  89       symbol = (symbol_t*) l->data;
  90       if (l == item->dot)
  91         {
  92           fprintf (stdout, ".");
  93         }
  94       fprintf (stdout, " %s ", g_quark_to_string (symbol->value));
  95       l = g_list_next (l);
  96     }
  97   if (item->dot == NULL)
  98     {
  99       fprintf (stdout, ".");
 100     }
 101   fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
 102 }
 103 #endif
 104
 105 GHashTable* item_set_new ()
 106 {
 107   return g_hash_table_new_full (item_hash, item_equal, item_delete, NULL);
 108 }
 109
 110 gboolean item_set_add (GHashTable* item_set, item_t* item)
 111 {
 112   if (!g_hash_table_lookup_extended (item_set, item, NULL, NULL))
 113     {
 114       g_hash_table_insert (item_set, item, NULL);
 115       return TRUE;
 116     }
 117   return FALSE;
 118 }
 119
 120 static void put_key_on_list (gpointer key, gpointer val, gpointer data)
 121 {
 122   GList** l;
 123   l = (GList**) data;
 124   *l = g_list_prepend (*l, key);
 125 }
 126
 127 gboolean item_set_equal (gconstpointer a, gconstpointer b)
 128 {
 129   GList* l;
 130   gboolean equal;
 131   if (g_hash_table_size (a) != g_hash_table_size (b))
 132     return FALSE;
 133   l = NULL;
 134   g_hash_table_foreach (a, put_key_on_list, (gpointer) &l);
 135   equal = TRUE;
 136   while (l != NULL && equal == TRUE)
 137     {
 138       equal = g_hash_table_lookup_extended (b, l->data, NULL, NULL);
 139       l = g_list_next (l);
 140     }
 141   g_list_free (l);
 142   return equal;
 143 }
 144
 145 void hash_item (gpointer key, gpointer val, gpointer data)
 146 {
 147   guint* hash;
 148   hash = (guint*) data;
 149   *hash = *hash * 37 + item_hash (key);
 150 }
 151
 152 guint item_set_hash (gconstpointer a)
 153 {
 154   guint hash = 0;
 155   g_hash_table_foreach (a, hash_item, &hash);
 156   return hash;
 157 }
 158
 159 void item_set_add_each (gpointer key, gpointer val, gpointer data)
 160 {
 161   item_set_add (data, item_copy (key));
 162 }
 163
 164 GHashTable* item_set_copy (GHashTable* item_set)
 165 {
 166   GHashTable* newitem_set;
 167   newitem_set = item_set_new ();
 168   g_hash_table_foreach (item_set, item_set_add_each, newitem_set);
 169   return newitem_set;
 170 }
 171
 172 #ifdef DEBUG
 173 void item_set_print_each (gpointer key, gpointer val, gpointer data)
 174 {
 175   item_print (key);
 176 }
 177
 178 void item_set_print (GHashTable* item_set)
 179 {
 180   g_hash_table_foreach (item_set, item_set_print_each, NULL);
 181 }
 182 #endif
 183
 184 rule_t* rule_new_item (item_t* item)
 185 {
 186
 187   rule_t* rule;
 188   GList* l;
 189   rule = rule_new ();
 190   l = g_list_next (item->dot);
 191   while (l != NULL)
 192     {
 193       rule_append (rule, symbol_copy (l->data));
 194       l = g_list_next (l);
 195     }
 196   rule_append (rule, symbol_copy (item->lookahead));
 197   return rule;
 198
 199 }
 200
 201 void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
 202                             GHashTable* first, item_t* item)
 203 {
 204   if (item->dot != NULL)
 205     {
 206       symbol_t* symbol;
 207       symbol = (symbol_t*) item->dot->data;
 208       if (symbol->terminal == FALSE)
 209         {
 210           GList* rules;
 211           GList* terminals;
 212           rule_t* rule;
 213           rule = rule_new_item (item);
 214           terminals = first_rule (first, rule);
 215           rule_delete (rule);
 216           rules = grammar_get_rules (grammar, symbol);
 217           while (rules != NULL)
 218             {
 219               GList* lookahead;
 220               lookahead = terminals;
 221               while (lookahead != NULL)
 222                 {
 223                   rule_t* rule;
 224                   item_t* newitem;
 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);
 231                 }
 232               rules = g_list_next (rules);
 233             }
 234           g_list_free (terminals);
 235         }
 236     }
 237 }
 238
 239 GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar,
 240                               GHashTable* first)
 241 {
 242   int size;
 243   int last_size;
 244   GList* l;
 245   size = g_hash_table_size (item_set);
 246   do
 247     {
 248       last_size = size;
 249       l = NULL;
 250       g_hash_table_foreach (item_set, put_key_on_list, &l);
 251       while (l != NULL)
 252         {
 253           item_set_closure_step (item_set, grammar, first, l->data);
 254           l = g_list_next (l);
 255         }
 256       g_list_free (l);
 257       size = g_hash_table_size (item_set);
 258     } while (last_size < size);
 259   return item_set;
 260 }
 261
 262 GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
 263                            GHashTable* first, symbol_t* symbol)
 264 {
 265   GList* l;
 266   GHashTable* newitem_set;
 267   newitem_set = item_set_new ();
 268   l = NULL;
 269   g_hash_table_foreach (item_set, put_key_on_list, &l);
 270   while (l != NULL)
 271     {
 272       item_t* item;
 273       item = item_copy (l->data);
 274       if (item->dot == NULL || !symbol_equal (item->dot->data, symbol))
 275         {
 276           item_delete (item);
 277         }
 278       else
 279         {
 280           item->dot = g_list_next (item->dot);
 281           if (!item_set_add (newitem_set, item))
 282             item_delete (item);
 283         }
 284       l = g_list_next (l);
 285     }
 286   return item_set_closure (newitem_set, grammar, first);
 287 }
 288
 289
 290 /*
 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
 298  * it).
 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.
 313  */
 314
 315 /*
 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.
 322  */
 323
 324 GHashTable* item_collection_new ()
 325 {
 326   return g_hash_table_new_full (item_set_hash, item_set_equal,
 327                                 g_hash_table_destroy, g_hash_table_destroy);
 328 }
 329
 330 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
 331                               GHashTable** key)
 332 {
 333   if (!g_hash_table_lookup_extended (collection, item_set,
 334                                      (gpointer*)key, NULL))
 335     {
 336       GHashTable* symbols;
 337       symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 338                                        g_free, NULL);
 339       g_hash_table_insert (collection, item_set, symbols);
 340       return TRUE;
 341     }
 342   return FALSE;
 343 }
 344
 345 GHashTable* item_collection_lookup (GHashTable* collection,
 346                                     GHashTable* item_set)
 347 {
 348   GHashTable* symbols;
 349   if (!g_hash_table_lookup_extended (collection, item_set,
 350                                      NULL, (gpointer*)&symbols))
 351     {
 352       return NULL;
 353     }
 354   return symbols;
 355 }
 356
 357 #define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
 358 #ifdef DEBUG
 359 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 360 {
 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");
 366 }
 367
 368 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
 369 {
 370   symbol_t* symbol;
 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));
 374 }
 375
 376 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
 377 {
 378   GHashTable* symbols;
 379   symbols = (GHashTable*) val;
 380   g_hash_table_foreach (symbols, item_set_print_goto, key);
 381   fprintf (stdout, "\n");
 382 }
 383
 384 void item_collection_print (GHashTable* collection)
 385 {
 386   g_hash_table_foreach (collection, item_collection_print_each, NULL);
 387   g_hash_table_foreach (collection, item_collection_print_goto, NULL);
 388 }
 389 #endif
 390
 391 GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
 392                                   GHashTable* first, GHashTable* item_set,
 393                                   symbol_t* symbol)
 394 {
 395   GHashTable* symbols;
 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))
 401     {
 402       g_hash_table_destroy (newitem_set);
 403     }
 404   symbols = item_collection_lookup (collection, item_set);
 405   if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
 406     {
 407       return NULL;
 408     }
 409   goto_item_set = item_set_goto (item_set, grammar, first, symbol);
 410   if (!item_collection_add (collection, goto_item_set, &old_item_set))
 411     {
 412       g_hash_table_insert (symbols, symbol, old_item_set);
 413       g_hash_table_destroy (goto_item_set);
 414       return NULL;
 415     }
 416   else
 417     {
 418       g_hash_table_insert (symbols, symbol, goto_item_set);
 419       return goto_item_set;
 420     }
 421 }
 422
 423 void item_set_collection (grammar_t* grammar, GHashTable* first, symbol_t* start)
 424 {
 425   GHashTable* collection;
 426   GHashTable* item_set;
 427   item_t* item;
 428   rule_t* rule;
 429   GList* new_item_sets;
 430   rule = rule_new ();
 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)
 441     {
 442       GHashTable* next_item_set;
 443       GHashTable* new_item_set;
 444       GList* items;
 445       next_item_set = (GHashTable*) new_item_sets->data;
 446       items = NULL;
 447       g_hash_table_foreach (next_item_set, put_key_on_list, &items);
 448       while (items != NULL)
 449         {
 450           item_t* item;
 451           symbol_t* symbol;
 452           item = (item_t*) items->data;
 453           if (item->dot != NULL)
 454             {
 455               symbol = (symbol_t*) item->dot->data;
 456               if ((new_item_set =
 457                    item_collection_goto (collection, grammar, first,
 458                                          next_item_set, symbol)) != NULL)
 459               {
 460                 g_list_append (new_item_sets, new_item_set);
 461               }
 462             }
 463           items = g_list_next (items);
 464         }
 465       g_list_free (items);
 466       new_item_sets = g_list_next (new_item_sets);
 467     }
 468   g_list_free (new_item_sets);
 469 #ifdef DEBUG
 470   item_collection_print (collection);
 471 #endif
 472   g_hash_table_destroy (collection);
 473 }