Merge nobobject with LR1

Patches applied:

 * cascardo@tlscascardo--private/libgrammatic--lr1--0.1--base-0
   tag of cascardo@tlscascardo--private/libgrammatic--dev--0.1--patch-18

 * cascardo@tlscascardo--private/libgrammatic--lr1--0.1--patch-1
   LR1 Items with lookahead instead of LR0 items

git-archimport-id: cascardo@tlscascardo--private/libgrammatic--nogobject-lr1--0.1--patch-1

diff --combined item.c
index c089253,3eb8fe3..ef98647
--- 1/item.c
--- 2/item.c
+++ b/item.c
@@@ -1,4 -1,5 +1,5 @@@
  #include <grammar.h>
+ #include <first.h>
  #ifdef DEBUG
  #include <stdio.h>
  #endif
@@@ -8,15 -9,17 +9,17 @@@ typedef struc
    symbol_t* left;
    rule_t* right;
    GList* dot;
+   symbol_t* lookahead;
  } item_t;
  
- item_t* item_new (symbol_t* left, rule_t* right)
+ item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead)
  {
    item_t* item;
    item = g_malloc (sizeof (item_t));
    item->left = left;
    item->right = right;
    item->dot = grammar_get_rule (right);
+   item->lookahead = lookahead;
    return item;
  }
  
@@@ -24,7 -27,8 +27,8 @@@ item_t* item_copy (item_t* item
  {
    item_t* newitem;
    int n;
-   newitem = item_new (symbol_copy (item->left), rule_copy (item->right));
+   newitem = item_new (symbol_copy (item->left), rule_copy (item->right),
+                     symbol_copy (item->lookahead));
    n = g_list_position (grammar_get_rule (item->right), item->dot);
    newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n);
    return newitem;
@@@ -39,6 -43,8 +43,8 @@@ gint item_cmp (const item_t* a, const i
      return c;
    if ((c = rule_cmp (a->right, b->right)) != 0)
      return c;
+   if ((c = symbol_cmp (a->lookahead, b->lookahead)) != 0)
+     return c;
    na = g_list_position (grammar_get_rule (a->right), a->dot);
    nb = g_list_position (grammar_get_rule (b->right), b->dot);
    if (na < nb)
@@@ -59,6 -65,7 +65,7 @@@ guint item_hash (gconstpointer data
    guint hash;
    item = (item_t*) data;
    hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
+   hash = hash * 37 + symbol_hash (item->lookahead);
    return hash;
  }
  
@@@ -66,6 -73,7 +73,7 @@@ void item_delete (item_t* item
  {
    g_free (item->left);
    rule_delete (item->right);
+   g_free (item->lookahead);
    g_free (item);
  }
  
@@@ -90,7 -98,7 +98,7 @@@ void item_print (item_t* item
      {
        fprintf (stdout, ".");
      }
-   fprintf (stdout, "\n");
+   fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
  }
  #endif
  
@@@ -173,8 -181,25 +181,25 @@@ void item_set_print (GHashTable* item_s
  }
  #endif
  
 -void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
+ rule_t* rule_new_item (item_t* item)
+ {
+ 
+   rule_t* rule;
+   GList* l;
+   rule = rule_new ();
+   l = g_list_next (item->dot);
+   while (l != NULL)
+     {
+       rule_append (rule, symbol_copy (l->data));
+       l = g_list_next (l);
+     }
+   rule_append (rule, symbol_copy (item->lookahead));
+   return rule;
+ 
+ }
+ 
-                           item_t* item)
 +void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
+                           GHashTable* first, item_t* item)
  {
    if (item->dot != NULL)
      {
@@@ -183,22 -208,36 +208,36 @@@
        if (symbol->terminal == FALSE)
        {
          GList* rules;
+         GList* terminals;
+         rule_t* rule;
+         rule = rule_new_item (item);
+         terminals = first_rule (first, rule);
+         rule_delete (rule);
          rules = grammar_get_rules (grammar, symbol);
          while (rules != NULL)
            {
-             rule_t* rule;
-             item_t* newitem;
-             rule = rule_copy (rules->data);
-             newitem = item_new (symbol_copy (symbol), rule);
-             if (!item_set_add (item_set, newitem))
-               item_delete (newitem);
+             GList* lookahead;
+             lookahead = terminals;
+             while (lookahead != NULL)
+               {
+                 rule_t* rule;
+                 item_t* newitem;
+                 rule = rule_copy (rules->data);
+                 newitem = item_new (symbol_copy (symbol), rule,
+                                     symbol_copy (lookahead->data));
+                 if (!item_set_add (item_set, newitem))
+                   item_delete (newitem);
+                 lookahead = g_list_next (lookahead);
+               }
              rules = g_list_next (rules);
            }
+         g_list_free (terminals);
        }
      }
  }
  
- GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar)
 -GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar,
++GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar,
+                             GHashTable* first)
  {
    int size;
    int last_size;
@@@ -211,7 -250,7 +250,7 @@@
        g_hash_table_foreach (item_set, put_key_on_list, &l);
        while (l != NULL)
        {
-         item_set_closure_step (item_set, grammar, l->data);
+         item_set_closure_step (item_set, grammar, first, l->data);
          l = g_list_next (l);
        }
        g_list_free (l);
@@@ -220,8 -259,8 +259,8 @@@
    return item_set;
  }
  
 -GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
 +GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
-                          symbol_t* symbol)
+                          GHashTable* first, symbol_t* symbol)
  {
    GList* l;
    GHashTable* newitem_set;
@@@ -244,7 -283,7 +283,7 @@@
        }
        l = g_list_next (l);
      }
-   return item_set_closure (newitem_set, grammar);
+   return item_set_closure (newitem_set, grammar, first);
  }
  
  
@@@ -282,46 -321,66 +321,46 @@@
   * In fact, the counter may be the hash table size.
   */
  
 -typedef struct
 -{
 -  GHashTable* symbols;
 -  gint code;
 -} state_t;
 -
 -state_t* state_new (gint code)
 -{
 -  state_t* state;
 -  state = g_malloc (sizeof (state_t));
 -  state->code = code;
 -  state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 -                                        g_free, NULL);
 -  return state;
 -}
 -
 -void state_delete (state_t* state)
 -{
 -  g_hash_table_destroy (state->symbols);
 -  g_free (state);
 -}
 -
  GHashTable* item_collection_new ()
  {
    return g_hash_table_new_full (item_set_hash, item_set_equal,
 -                              g_hash_table_destroy, state_delete);
 +                              g_hash_table_destroy, g_hash_table_destroy);
  }
  
 -gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
 +gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
 +                            GHashTable** key)
  {
 -  if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
 +  if (!g_hash_table_lookup_extended (collection, item_set,
 +                                   (gpointer*)key, NULL))
      {
 -      state_t* state;
 -      state = state_new (g_hash_table_size (collection));
 -      g_hash_table_insert (collection, item_set, state);
 +      GHashTable* symbols;
 +      symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
 +                                     g_free, NULL);
 +      g_hash_table_insert (collection, item_set, symbols);
        return TRUE;
      }
    return FALSE;
  }
  
 -state_t* item_collection_lookup (GHashTable* collection,
 -                               GHashTable* item_set)
 +GHashTable* item_collection_lookup (GHashTable* collection,
 +                                  GHashTable* item_set)
  {
 -  state_t* state;
 +  GHashTable* symbols;
    if (!g_hash_table_lookup_extended (collection, item_set,
 -                                   NULL, (gpointer*)&state))
 +                                   NULL, (gpointer*)&symbols))
      {
        return NULL;
      }
 -  return state;
 +  return symbols;
  }
  
 +#define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
  #ifdef DEBUG
  void item_collection_print_each (gpointer key, gpointer val, gpointer data)
  {
    GHashTable* item_set;
 -  state_t* state;
    item_set = (GHashTable*) key;
 -  state = (state_t*) val;
 -  fprintf (stdout, "Item %d:\n", state->code);
 +  fprintf (stdout, "Item %x:\n", HASH_ITEM_SET(key));
    item_set_print (item_set);
    fprintf (stdout, "\n");
  }
@@@ -329,16 -388,20 +368,16 @@@
  void item_set_print_goto (gpointer key, gpointer val, gpointer data)
  {
    symbol_t* symbol;
 -  gint code;
 -  state_t* state;
    symbol = (symbol_t*) key;
 -  code = GPOINTER_TO_INT (val);
 -  state = (state_t*) data;
 -  fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
 -         g_quark_to_string (symbol->value), code);
 +  fprintf (stdout, "GOTO (%x, %s) =\t %x\n", HASH_ITEM_SET(data),
 +         g_quark_to_string (symbol->value), HASH_ITEM_SET(val));
  }
  
  void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
  {
 -  state_t* state;
 -  state = (state_t*) val;
 -  g_hash_table_foreach (state->symbols, item_set_print_goto, state);
 +  GHashTable* symbols;
 +  symbols = (GHashTable*) val;
 +  g_hash_table_foreach (symbols, item_set_print_goto, key);
    fprintf (stdout, "\n");
  }
  
@@@ -349,38 -412,37 +388,39 @@@ void item_collection_print (GHashTable
  }
  #endif
  
 -GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
 +GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
-                                 GHashTable* item_set, symbol_t* symbol)
+                                 GHashTable* first, GHashTable* item_set,
+                                 symbol_t* symbol)
  {
 -  state_t* state;
 -  state_t* goto_state;
 +  GHashTable* symbols;
    GHashTable* newitem_set;
    GHashTable* goto_item_set;
 -  GHashTable* return_item_set;
 +  GHashTable* old_item_set;
    newitem_set = item_set_copy (item_set);
 -  if (!item_collection_add (collection, newitem_set))
 +  if (!item_collection_add (collection, newitem_set, NULL))
      {
        g_hash_table_destroy (newitem_set);
      }
 -  state = item_collection_lookup (collection, item_set);
 -  if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
 +  symbols = item_collection_lookup (collection, item_set);
 +  if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
      {
        return NULL;
      }
-   goto_item_set = item_set_goto (item_set, grammar, symbol);
+   goto_item_set = item_set_goto (item_set, grammar, first, symbol);
 -  if (!item_collection_add (collection, goto_item_set))
 -    return_item_set = NULL;
 +  if (!item_collection_add (collection, goto_item_set, &old_item_set))
 +    {
 +      g_hash_table_insert (symbols, symbol, old_item_set);
 +      g_hash_table_destroy (goto_item_set);
 +      return NULL;
 +    }
    else
 -    return_item_set = goto_item_set;
 -  goto_state = item_collection_lookup (collection, goto_item_set);
 -  g_hash_table_insert (state->symbols, symbol,
 -                     GINT_TO_POINTER (goto_state->code));
 -  return return_item_set;
 +    {
 +      g_hash_table_insert (symbols, symbol, goto_item_set);
 +      return goto_item_set;
 +    }
  }
  
- void item_set_collection (grammar_t* grammar, symbol_t* start)
 -void item_set_collection (Grammar* grammar, GHashTable* first, symbol_t* start)
++void item_set_collection (grammar_t* grammar, GHashTable* first, symbol_t* start)
  {
    GHashTable* collection;
    GHashTable* item_set;
@@@ -389,13 -451,13 +429,13 @@@
    GList* new_item_sets;
    rule = rule_new ();
    rule_append (rule, symbol_copy (start));
-   item = item_new (symbol_new (FALSE, -1), rule);
+   item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0));
    item_set = item_set_new ();
    item_set_add (item_set, item);
-   item_set_closure (item_set, grammar);
+   item_set_closure (item_set, grammar, first);
    collection = g_hash_table_new_full (item_set_hash, item_set_equal,
                                      g_hash_table_destroy, NULL);
 -  item_collection_add (collection, item_set);
 +  item_collection_add (collection, item_set, NULL);
    new_item_sets = g_list_append (NULL, item_set);
    while (new_item_sets != NULL)
      {
@@@ -414,7 -476,7 +454,7 @@@
            {
              symbol = (symbol_t*) item->dot->data;
              if ((new_item_set =
-                  item_collection_goto (collection, grammar,
+                  item_collection_goto (collection, grammar, first,
                                         next_item_set, symbol)) != NULL)
              {
                g_list_append (new_item_sets, new_item_set);