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* 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* 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* 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 typedef struct
 318 {
 319   GHashTable* symbols;
 320   gint code;
 321 } state_t;
 322
 323 state_t* state_new (gint code)
 324 {
 325   state_t* state;
 326   state = g_malloc (sizeof (state_t));
 327   state->code = code;
 328   state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 329                                           g_free, NULL);
 330   return state;
 331 }
 332
 333 void state_delete (state_t* state)
 334 {
 335   g_hash_table_destroy (state->symbols);
 336   g_free (state);
 337 }
 338
 339 GHashTable* item_collection_new ()
 340 {
 341   return g_hash_table_new_full (item_set_hash, item_set_equal,
 342                                 g_hash_table_destroy, state_delete);
 343 }
 344
 345 gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
 346 {
 347   if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
 348     {
 349       state_t* state;
 350       state = state_new (g_hash_table_size (collection));
 351       g_hash_table_insert (collection, item_set, state);
 352       return TRUE;
 353     }
 354   return FALSE;
 355 }
 356
 357 state_t* item_collection_lookup (GHashTable* collection,
 358                                  GHashTable* item_set)
 359 {
 360   state_t* state;
 361   if (!g_hash_table_lookup_extended (collection, item_set,
 362                                      NULL, (gpointer*)&state))
 363     {
 364       return NULL;
 365     }
 366   return state;
 367 }
 368
 369 #ifdef DEBUG
 370 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 371 {
 372   GHashTable* item_set;
 373   state_t* state;
 374   item_set = (GHashTable*) key;
 375   state = (state_t*) val;
 376   fprintf (stdout, "Item %d:\n", state->code);
 377   item_set_print (item_set);
 378   fprintf (stdout, "\n");
 379 }
 380
 381 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
 382 {
 383   symbol_t* symbol;
 384   gint code;
 385   state_t* state;
 386   symbol = (symbol_t*) key;
 387   code = GPOINTER_TO_INT (val);
 388   state = (state_t*) data;
 389   fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
 390            g_quark_to_string (symbol->value), code);
 391 }
 392
 393 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
 394 {
 395   state_t* state;
 396   state = (state_t*) val;
 397   g_hash_table_foreach (state->symbols, item_set_print_goto, state);
 398   fprintf (stdout, "\n");
 399 }
 400
 401 void item_collection_print (GHashTable* collection)
 402 {
 403   g_hash_table_foreach (collection, item_collection_print_each, NULL);
 404   g_hash_table_foreach (collection, item_collection_print_goto, NULL);
 405 }
 406 #endif
 407
 408 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
 409                                   GHashTable* first, GHashTable* item_set,
 410                                   symbol_t* symbol)
 411 {
 412   state_t* state;
 413   state_t* goto_state;
 414   GHashTable* newitem_set;
 415   GHashTable* goto_item_set;
 416   GHashTable* return_item_set;
 417   newitem_set = item_set_copy (item_set);
 418   if (!item_collection_add (collection, newitem_set))
 419     {
 420       g_hash_table_destroy (newitem_set);
 421     }
 422   state = item_collection_lookup (collection, item_set);
 423   if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
 424     {
 425       return NULL;
 426     }
 427   goto_item_set = item_set_goto (item_set, grammar, first, symbol);
 428   if (!item_collection_add (collection, goto_item_set))
 429     return_item_set = NULL;
 430   else
 431     return_item_set = goto_item_set;
 432   goto_state = item_collection_lookup (collection, goto_item_set);
 433   g_hash_table_insert (state->symbols, symbol,
 434                        GINT_TO_POINTER (goto_state->code));
 435   return return_item_set;
 436 }
 437
 438 GHashTable* item_set_collection (Grammar* grammar, GHashTable* first,
 439                                  symbol_t* start)
 440 {
 441   GHashTable* collection;
 442   GHashTable* item_set;
 443   item_t* item;
 444   rule_t* rule;
 445   GList* new_item_sets;
 446   rule = rule_new ();
 447   rule_append (rule, symbol_copy (start));
 448   item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0));
 449   item_set = item_set_new ();
 450   item_set_add (item_set, item);
 451   item_set_closure (item_set, grammar, first);
 452   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
 453                                       g_hash_table_destroy, NULL);
 454   item_collection_add (collection, item_set);
 455   new_item_sets = g_list_append (NULL, item_set);
 456   while (new_item_sets != NULL)
 457     {
 458       GHashTable* next_item_set;
 459       GHashTable* new_item_set;
 460       GList* items;
 461       next_item_set = (GHashTable*) new_item_sets->data;
 462       items = NULL;
 463       g_hash_table_foreach (next_item_set, put_key_on_list, &items);
 464       while (items != NULL)
 465         {
 466           item_t* item;
 467           symbol_t* symbol;
 468           item = (item_t*) items->data;
 469           if (item->dot != NULL)
 470             {
 471               symbol = (symbol_t*) item->dot->data;
 472               if ((new_item_set =
 473                    item_collection_goto (collection, grammar, first,
 474                                          next_item_set, symbol)) != NULL)
 475               {
 476                 g_list_append (new_item_sets, new_item_set);
 477               }
 478             }
 479           items = g_list_next (items);
 480         }
 481       g_list_free (items);
 482       new_item_sets = g_list_next (new_item_sets);
 483     }
 484   g_list_free (new_item_sets);
 485 #ifdef DEBUG
 486   item_collection_print (collection);
 487 #endif
 488   return collection;
 489 }