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