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 gboolean item_set_find (gpointer key, gpointer val, gpointer data)
 113 {
 114   return !g_hash_table_lookup_extended (data, key, NULL, NULL);
 115 }
 116
 117 gboolean item_set_equal (gconstpointer a, gconstpointer b)
 118 {
 119   if (g_hash_table_size (a) != g_hash_table_size (b))
 120     return FALSE;
 121   return (g_hash_table_find (a, item_set_find, b) == NULL);
 122 }
 123
 124 void hash_item (gpointer key, gpointer val, gpointer data)
 125 {
 126   guint* hash;
 127   hash = (guint*) data;
 128   *hash = *hash * 37 + item_hash (key);
 129 }
 130
 131 guint item_set_hash (gconstpointer a)
 132 {
 133   guint hash = 0;
 134   g_hash_table_foreach (a, hash_item, &hash);
 135   return hash;
 136 }
 137
 138 void item_set_add_each (gpointer key, gpointer val, gpointer data)
 139 {
 140   item_set_add (data, item_copy (key));
 141 }
 142
 143 GHashTable* item_set_copy (GHashTable* item_set)
 144 {
 145   GHashTable* newitem_set;
 146   newitem_set = item_set_new ();
 147   g_hash_table_foreach (item_set, item_set_add_each, newitem_set);
 148   return newitem_set;
 149 }
 150
 151 #ifdef DEBUG
 152 void item_set_print_each (gpointer key, gpointer val, gpointer data)
 153 {
 154   item_print (key);
 155 }
 156
 157 void item_set_print (GHashTable* item_set)
 158 {
 159   g_hash_table_foreach (item_set, item_set_print_each, NULL);
 160 }
 161 #endif
 162
 163 void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
 164                             item_t* item)
 165 {
 166   if (item->dot != NULL)
 167     {
 168       symbol_t* symbol;
 169       symbol = (symbol_t*) item->dot->data;
 170       if (symbol->terminal == FALSE)
 171         {
 172           GList* rules;
 173           rules = grammar_get_rules (grammar, symbol);
 174           while (rules != NULL)
 175             {
 176               rule_t* rule;
 177               item_t* newitem;
 178               rule = rule_copy (rules->data);
 179               newitem = item_new (symbol_copy (symbol), rule);
 180               if (!item_set_add (item_set, newitem))
 181                 item_delete (newitem);
 182               rules = g_list_next (rules);
 183             }
 184         }
 185     }
 186 }
 187
 188 void put_key_on_list (gpointer key, gpointer val, gpointer data)
 189 {
 190   GList** l;
 191   l = (GList**) data;
 192   *l = g_list_prepend (*l, key);
 193 }
 194
 195 GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
 196 {
 197   int size;
 198   int last_size;
 199   GList* l;
 200   size = g_hash_table_size (item_set);
 201   do
 202     {
 203       last_size = size;
 204       l = NULL;
 205       g_hash_table_foreach (item_set, put_key_on_list, &l);
 206       while (l != NULL)
 207         {
 208           item_set_closure_step (item_set, grammar, l->data);
 209           l = g_list_next (l);
 210         }
 211       g_list_free (l);
 212       size = g_hash_table_size (item_set);
 213     } while (last_size < size);
 214   return item_set;
 215 }
 216
 217 GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
 218                            symbol_t* symbol)
 219 {
 220   GList* l;
 221   GHashTable* newitem_set;
 222   newitem_set = item_set_new ();
 223   l = NULL;
 224   g_hash_table_foreach (item_set, put_key_on_list, &l);
 225   while (l != NULL)
 226     {
 227       item_t* item;
 228       item = item_copy (l->data);
 229       if (item->dot == NULL || !symbol_equal (item->dot->data, symbol))
 230         {
 231           item_delete (item);
 232         }
 233       else
 234         {
 235           item->dot = g_list_next (item->dot);
 236           if (!item_set_add (newitem_set, item))
 237             item_delete (item);
 238         }
 239       l = g_list_next (l);
 240     }
 241   return item_set_closure (newitem_set, grammar);
 242 }
 243
 244
 245 /*
 246  * This part is a little tricky. We can simply take an approach similar
 247  * to the goto approach, adding a new set for every other set and grammar
 248  * symbol every time we get a new set.
 249  * Although a similar argument about the goto may apply (which is a very
 250  * good reason to optimize it), the case for the collection is worse, since
 251  * we will be building a new set for the number of sets in the collection
 252  * times the number of symbol grammar. (Not building in fact, but computing
 253  * it).
 254  * Here is an approach that may work:
 255  * For each *new* item set, we compute its gotos. Each goto is looked up
 256  * in the collection. If it's a new item set, it's included in a list of
 257  * new item sets. To compute the gotos of an item set, we should pick only
 258  * the grammar symbols that appear in the items' dots. That solves the
 259  * problem of getting a list of all the grammar symbols.
 260  * So, there will be a list of item sets that we must iterate through. We
 261  * add each new list to the hash table too, so we can look it up when we
 262  * get a new one. When the list is finished, we are done and do not have to
 263  * check the hash table size for each iteration.
 264  * So, we need the following functions:
 265  * One to check if an item set is already there and add it if it's not.
 266  * One to get the symbols hash table, so we can put the computed goto
 267  * there anyway. So, that's an add and a lookup.
 268  */
 269
 270 /*
 271  * TODO: associate a number to each item set.
 272  * Use a structure to the collection with a counter.
 273  * Use another structure to the value in the hash table for each item set.
 274  * This structure will have the symbol hash table (for the goto) and the
 275  * number associated with the item set.
 276  * In fact, the counter may be the hash table size.
 277  */
 278
 279 typedef struct
 280 {
 281   GHashTable* symbols;
 282   gint code;
 283 } state_t;
 284
 285 state_t* state_new (gint code)
 286 {
 287   state_t* state;
 288   state = g_malloc (sizeof (state_t));
 289   state->code = code;
 290   state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 291                                           g_free, NULL);
 292   return state;
 293 }
 294
 295 void state_delete (state_t* state)
 296 {
 297   g_hash_table_destroy (state->symbols);
 298   g_free (state);
 299 }
 300
 301 GHashTable* item_collection_new ()
 302 {
 303   return g_hash_table_new_full (item_set_hash, item_set_equal,
 304                                 g_hash_table_destroy, state_delete);
 305 }
 306
 307 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
 308 {
 309   if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
 310     {
 311       state_t* state;
 312       state = state_new (g_hash_table_size (collection));
 313       g_hash_table_insert (collection, item_set, state);
 314       return TRUE;
 315     }
 316   return FALSE;
 317 }
 318
 319 state_t* item_collection_lookup (GHashTable* collection,
 320                                  GHashTable* item_set)
 321 {
 322   state_t* state;
 323   if (!g_hash_table_lookup_extended (collection, item_set,
 324                                      NULL, (gpointer*)&state))
 325     {
 326       return NULL;
 327     }
 328   return state;
 329 }
 330
 331 #ifdef DEBUG
 332 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 333 {
 334   GHashTable* item_set;
 335   state_t* state;
 336   item_set = (GHashTable*) key;
 337   state = (state_t*) val;
 338   fprintf (stdout, "Item %d:\n", state->code);
 339   item_set_print (item_set);
 340   fprintf (stdout, "\n");
 341 }
 342
 343 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
 344 {
 345   symbol_t* symbol;
 346   gint code;
 347   state_t* state;
 348   symbol = (symbol_t*) key;
 349   code = GINT_TO_POINTER (val);
 350   state = (state_t*) data;
 351   fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
 352            g_quark_to_string (symbol->value), code);
 353 }
 354
 355 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
 356 {
 357   state_t* state;
 358   state = (state_t*) val;
 359   g_hash_table_foreach (state->symbols, item_set_print_goto, state);
 360   fprintf (stdout, "\n");
 361 }
 362
 363 void item_collection_print (GHashTable* collection)
 364 {
 365   g_hash_table_foreach (collection, item_collection_print_each, NULL);
 366   g_hash_table_foreach (collection, item_collection_print_goto, NULL);
 367 }
 368 #endif
 369
 370 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
 371                                   GHashTable* item_set, symbol_t* symbol)
 372 {
 373   state_t* state;
 374   state_t* goto_state;
 375   GHashTable* newitem_set;
 376   GHashTable* goto_item_set;
 377   GHashTable* return_item_set;
 378   newitem_set = item_set_copy (item_set);
 379   if (!item_collection_add (collection, newitem_set))
 380     {
 381       g_hash_table_destroy (newitem_set);
 382     }
 383   state = item_collection_lookup (collection, item_set);
 384   if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
 385     {
 386       return NULL;
 387     }
 388   goto_item_set = item_set_goto (item_set, grammar, symbol);
 389   if (!item_collection_add (collection, goto_item_set))
 390     return_item_set = NULL;
 391   else
 392     return_item_set = goto_item_set;
 393   goto_state = item_collection_lookup (collection, goto_item_set);
 394   g_hash_table_insert (state->symbols, symbol,
 395                        GINT_TO_POINTER (goto_state->code));
 396   return return_item_set;
 397 }
 398
 399 void item_set_collection (Grammar* grammar, symbol_t* start)
 400 {
 401   GHashTable* collection;
 402   GHashTable* item_set;
 403   item_t* item;
 404   rule_t* rule;
 405   GList* new_item_sets;
 406   rule = rule_new ();
 407   rule_append (rule, symbol_copy (start));
 408   item = item_new (symbol_new (FALSE, -1), rule);
 409   item_set = item_set_new ();
 410   item_set_add (item_set, item);
 411   item_set_closure (item_set, grammar);
 412   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
 413                                       g_hash_table_destroy, NULL);
 414   item_collection_add (collection, item_set);
 415   new_item_sets = g_list_append (NULL, item_set);
 416   while (new_item_sets != NULL)
 417     {
 418       GHashTable* next_item_set;
 419       GHashTable* new_item_set;
 420       GList* items;
 421       next_item_set = (GHashTable*) new_item_sets->data;
 422       items = NULL;
 423       g_hash_table_foreach (next_item_set, put_key_on_list, &items);
 424       while (items != NULL)
 425         {
 426           item_t* item;
 427           symbol_t* symbol;
 428           item = (item_t*) items->data;
 429           if (item->dot != NULL)
 430             {
 431               symbol = (symbol_t*) item->dot->data;
 432               if ((new_item_set =
 433                    item_collection_goto (collection, grammar,
 434                                          next_item_set, symbol)) != NULL)
 435               {
 436                 g_list_append (new_item_sets, new_item_set);
 437               }
 438             }
 439           items = g_list_next (items);
 440         }
 441       g_list_free (items);
 442       new_item_sets = g_list_next (new_item_sets);
 443     }
 444   g_list_free (new_item_sets);
 445 #ifdef DEBUG
 446   item_collection_print (collection);
 447 #endif
 448   g_hash_table_destroy (collection);
 449 }