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 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* 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* 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* 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 typedef struct
 286 {
 287   GHashTable* symbols;
 288   gint code;
 289 } state_t;
 290
 291 state_t* state_new (gint code)
 292 {
 293   state_t* state;
 294   state = g_malloc (sizeof (state_t));
 295   state->code = code;
 296   state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 297                                           g_free, NULL);
 298   return state;
 299 }
 300
 301 void state_delete (state_t* state)
 302 {
 303   g_hash_table_destroy (state->symbols);
 304   g_free (state);
 305 }
 306
 307 GHashTable* item_collection_new ()
 308 {
 309   return g_hash_table_new_full (item_set_hash, item_set_equal,
 310                                 g_hash_table_destroy, state_delete);
 311 }
 312
 313 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
 314 {
 315   if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
 316     {
 317       state_t* state;
 318       state = state_new (g_hash_table_size (collection));
 319       g_hash_table_insert (collection, item_set, state);
 320       return TRUE;
 321     }
 322   return FALSE;
 323 }
 324
 325 state_t* item_collection_lookup (GHashTable* collection,
 326                                  GHashTable* item_set)
 327 {
 328   state_t* state;
 329   if (!g_hash_table_lookup_extended (collection, item_set,
 330                                      NULL, (gpointer*)&state))
 331     {
 332       return NULL;
 333     }
 334   return state;
 335 }
 336
 337 #ifdef DEBUG
 338 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 339 {
 340   GHashTable* item_set;
 341   state_t* state;
 342   item_set = (GHashTable*) key;
 343   state = (state_t*) val;
 344   fprintf (stdout, "Item %d:\n", state->code);
 345   item_set_print (item_set);
 346   fprintf (stdout, "\n");
 347 }
 348
 349 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
 350 {
 351   symbol_t* symbol;
 352   gint code;
 353   state_t* state;
 354   symbol = (symbol_t*) key;
 355   code = GINT_TO_POINTER (val);
 356   state = (state_t*) data;
 357   fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
 358            g_quark_to_string (symbol->value), code);
 359 }
 360
 361 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
 362 {
 363   state_t* state;
 364   state = (state_t*) val;
 365   g_hash_table_foreach (state->symbols, item_set_print_goto, state);
 366   fprintf (stdout, "\n");
 367 }
 368
 369 void item_collection_print (GHashTable* collection)
 370 {
 371   g_hash_table_foreach (collection, item_collection_print_each, NULL);
 372   g_hash_table_foreach (collection, item_collection_print_goto, NULL);
 373 }
 374 #endif
 375
 376 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
 377                                   GHashTable* item_set, symbol_t* symbol)
 378 {
 379   state_t* state;
 380   state_t* goto_state;
 381   GHashTable* newitem_set;
 382   GHashTable* goto_item_set;
 383   GHashTable* return_item_set;
 384   newitem_set = item_set_copy (item_set);
 385   if (!item_collection_add (collection, newitem_set))
 386     {
 387       g_hash_table_destroy (newitem_set);
 388     }
 389   state = item_collection_lookup (collection, item_set);
 390   if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
 391     {
 392       return NULL;
 393     }
 394   goto_item_set = item_set_goto (item_set, grammar, symbol);
 395   if (!item_collection_add (collection, goto_item_set))
 396     return_item_set = NULL;
 397   else
 398     return_item_set = goto_item_set;
 399   goto_state = item_collection_lookup (collection, goto_item_set);
 400   g_hash_table_insert (state->symbols, symbol,
 401                        GINT_TO_POINTER (goto_state->code));
 402   return return_item_set;
 403 }
 404
 405 void item_set_collection (Grammar* grammar, symbol_t* start)
 406 {
 407   GHashTable* collection;
 408   GHashTable* item_set;
 409   item_t* item;
 410   rule_t* rule;
 411   GList* new_item_sets;
 412   rule = rule_new ();
 413   rule_append (rule, symbol_copy (start));
 414   item = item_new (symbol_new (FALSE, -1), rule);
 415   item_set = item_set_new ();
 416   item_set_add (item_set, item);
 417   item_set_closure (item_set, grammar);
 418   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
 419                                       g_hash_table_destroy, NULL);
 420   item_collection_add (collection, item_set);
 421   new_item_sets = g_list_append (NULL, item_set);
 422   while (new_item_sets != NULL)
 423     {
 424       GHashTable* next_item_set;
 425       GHashTable* new_item_set;
 426       GList* items;
 427       next_item_set = (GHashTable*) new_item_sets->data;
 428       items = NULL;
 429       g_hash_table_foreach (next_item_set, put_key_on_list, &items);
 430       while (items != NULL)
 431         {
 432           item_t* item;
 433           symbol_t* symbol;
 434           item = (item_t*) items->data;
 435           if (item->dot != NULL)
 436             {
 437               symbol = (symbol_t*) item->dot->data;
 438               if ((new_item_set =
 439                    item_collection_goto (collection, grammar,
 440                                          next_item_set, symbol)) != NULL)
 441               {
 442                 g_list_append (new_item_sets, new_item_set);
 443               }
 444             }
 445           items = g_list_next (items);
 446         }
 447       g_list_free (items);
 448       new_item_sets = g_list_next (new_item_sets);
 449     }
 450   g_list_free (new_item_sets);
 451 #ifdef DEBUG
 452   item_collection_print (collection);
 453 #endif
 454   g_hash_table_destroy (collection);
 455 }