lr1_gen.c

   1 /*
   2  *  Copyright (C) 2005  Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
   3  *
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 2 of the License, or
   7  *  (at your option) any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License along
  15  *  with this program; if not, write to the Free Software Foundation, Inc.,
  16  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  17  */
  18
  19
  20
  21 #include <grammar.h>
  22 #include <item.h>
  23 #include <lr1.h>
  24 #include <first.h>
  25 #include <scanner.h>
  26 #ifdef DEBUG
  27 #include <stdio.h>
  28 #endif
  29
  30 static void put_key_val_on_list (gpointer key, gpointer val, gpointer data)
  31 {
  32   GList** l;
  33   l = (GList**) data;
  34   *l = g_list_prepend (*l, val);
  35   *l = g_list_prepend (*l, key);
  36 }
  37
  38 static void put_key_on_list (gpointer key, gpointer val, gpointer data)
  39 {
  40   GList** l;
  41   l = (GList**) data;
  42   *l = g_list_prepend (*l, key);
  43 }
  44
  45 void lr1_gen_add (gpointer key, gpointer val, gpointer data)
  46 {
  47
  48   GList* l;
  49   transition_t* transition;
  50
  51
  52   l = NULL;
  53   g_hash_table_foreach (key, put_key_on_list, (gpointer) &l);
  54
  55   while (l != NULL)
  56     {
  57       item_t* item;
  58       item = (item_t*) l->data;
  59
  60       if (item->left->value == -1 && item->left->terminal == FALSE)
  61         {
  62           if (item->dot == NULL)
  63             {
  64 #ifdef DEBUG
  65               printf ("ACCEPT: %p\n", key);
  66 #endif
  67               transition = transition_accept_new ();
  68               lr1_add (data, key, symbol_new (TRUE, 0), transition);
  69             }
  70           else
  71             {
  72 #ifdef DEBUG
  73               printf ("START: %p\n", key);
  74 #endif
  75               lr1_push (data, key, NULL);
  76             }
  77         }
  78       else if (item->dot == NULL)
  79         {
  80 #ifdef DEBUG
  81           printf ("REDUCE: %p, %s\n", key,
  82                   g_quark_to_string (item->lookahead->value));
  83 #endif
  84           transition = transition_reduce_new (item->left, item->right);
  85           lr1_add (data, key, item->lookahead, transition);
  86         }
  87
  88       l = g_list_next (l);
  89
  90     }
  91
  92   g_list_free (l);
  93
  94
  95   l = NULL;
  96   g_hash_table_foreach (val, put_key_val_on_list, (gpointer) &l);
  97
  98   while (l != NULL)
  99     {
 100
 101       symbol_t* symbol;
 102       symbol = (symbol_t*) l->data;
 103       l = g_list_next (l);
 104
 105 #ifdef DEBUG
 106       printf ("SHIFT: %p, %s, %p\n", key,
 107               g_quark_to_string (symbol->value), l->data);
 108 #endif
 109       transition = transition_shift_new (l->data);
 110       lr1_add (data, key, symbol, transition);
 111
 112       l = g_list_next (l);
 113
 114     }
 115
 116   g_list_free (l);
 117
 118 }
 119
 120 lr1_t* lr1_gen (grammar_t* grammar, symbol_t* start, nextcb cb, gpointer data)
 121 {
 122
 123   GHashTable* first;
 124   GHashTable* collection;
 125   lr1_t* lr1;
 126
 127   lr1 = lr1_new (cb, data);
 128
 129   first = grammar_first (grammar);
 130 #ifdef DEBUG
 131   first_print (first);
 132 #endif
 133
 134   collection = item_set_collection (grammar, first, start);
 135
 136   g_hash_table_foreach (collection, lr1_gen_add, lr1);
 137
 138   return lr1;
 139
 140 }