grammar.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
  23 struct _rule
  24 {
  25   GList* right;
  26 };
  27
  28 symbol_t* symbol_new (gboolean terminal, GQuark value)
  29 {
  30   symbol_t* symbol;
  31   symbol = g_malloc (sizeof (symbol_t));
  32   symbol->terminal = terminal;
  33   symbol->value = value;
  34   return symbol;
  35 }
  36
  37 symbol_t* symbol_copy (symbol_t* symbol)
  38 {
  39   return symbol_new (symbol->terminal, symbol->value);
  40 }
  41
  42 guint symbol_hash (gconstpointer data)
  43 {
  44   symbol_t* symbol;
  45   symbol = (symbol_t*) data;
  46   return g_direct_hash ((gpointer)symbol->value);
  47 }
  48
  49 gboolean symbol_equal (gconstpointer data1, gconstpointer data2)
  50 {
  51   symbol_t* symbol1;
  52   symbol_t* symbol2;
  53   symbol1 = (symbol_t*) data1;
  54   symbol2 = (symbol_t*) data2;
  55   return symbol1->value == symbol2->value &&
  56     symbol1->terminal == symbol2->terminal;
  57 }
  58
  59 gint symbol_cmp (symbol_t* a, symbol_t* b)
  60 {
  61   if (a->terminal == b->terminal)
  62     {
  63       if (a->value < b->value)
  64         return -1;
  65       else if (a->value > b->value)
  66         return 1;
  67       return 0;
  68     }
  69   else if (a->terminal == FALSE)
  70     {
  71       return -1;
  72     }
  73   return 1;
  74 }
  75
  76 rule_t* rule_new ()
  77 {
  78   rule_t* rule;
  79   rule = g_malloc (sizeof (rule_t));
  80   rule->right = NULL;
  81   return rule;
  82 }
  83
  84 void rule_append (rule_t* rule, symbol_t* right)
  85 {
  86   rule->right = g_list_append (rule->right, right);
  87 }
  88
  89 rule_t* rule_copy (rule_t* rule)
  90 {
  91   rule_t* new_rule;
  92   GList* r;
  93   new_rule = rule_new ();
  94   r = rule->right;
  95   while (r != NULL)
  96     {
  97       rule_append (new_rule, symbol_copy (r->data));
  98       r = g_list_next (r);
  99     }
 100   return new_rule;
 101 }
 102
 103 gint rule_cmp (rule_t* a, rule_t* b)
 104 {
 105   GList* la;
 106   GList* lb;
 107   la = grammar_get_rule (a);
 108   lb = grammar_get_rule (b);
 109   while (la != NULL && lb != NULL)
 110     {
 111       int c;
 112       if ((c = symbol_cmp (la->data, lb->data)) != 0)
 113         return c;
 114       la = g_list_next (la);
 115       lb = g_list_next (lb);
 116     }
 117   if (la == lb)
 118     return 0;
 119   else if (la == NULL)
 120     return -1;
 121   return 1;
 122 }
 123
 124 gboolean rule_equal (gconstpointer data1, gconstpointer data2)
 125 {
 126   return (rule_cmp (data1, data2) == 0);
 127 }
 128
 129 guint rule_hash (gconstpointer data)
 130 {
 131   GList* l;
 132   guint hash;
 133   l = grammar_get_rule (data);
 134   hash = 0;
 135   while (l != NULL)
 136     {
 137       hash = 37 * hash + symbol_hash (l->data);
 138       l = g_list_next (l);
 139     }
 140   return hash;
 141 }
 142
 143 symbol_t* rule_pop (rule_t* rule)
 144 {
 145   GList* r;
 146   if ((r = g_list_first (rule->right)) == NULL)
 147     return NULL;
 148   rule->right = g_list_remove_link (r, r);
 149   g_free (r->data);
 150   g_list_free (r);
 151   if (rule->right == NULL)
 152     return NULL;
 153   return rule->right->data;
 154 }
 155
 156 void rule_delete (rule_t* rule)
 157 {
 158   GList* l;
 159   for (l = g_list_first (rule->right); l != NULL; l = g_list_next (l))
 160     {
 161       g_free (l->data);
 162     }
 163   g_list_free (rule->right);
 164   g_free (rule);
 165 }
 166
 167 void rules_delete (GList** list)
 168 {
 169   GList* l;
 170   for (l = g_list_first (*list); l != NULL; l = g_list_next (l))
 171     {
 172       rule_delete (l->data);
 173     }
 174   g_list_free (*list);
 175   g_free (list);
 176 }
 177
 178 grammar_t* grammar_new ()
 179 {
 180   grammar_t* grammar;
 181   grammar = g_malloc (sizeof (grammar_t*));
 182   grammar->grammar = g_hash_table_new_full (symbol_hash, symbol_equal,
 183                                             g_free,
 184                                             (GDestroyNotify) rules_delete);
 185   return grammar;
 186 }
 187
 188 void grammar_delete (grammar_t* grammar)
 189 {
 190   g_hash_table_destroy (grammar->grammar);
 191   g_free (grammar);
 192 }
 193
 194 rule_t* grammar_rule_new (grammar_t* grammar, symbol_t* left)
 195 {
 196
 197   GList** l;
 198   rule_t* rule;
 199
 200   if (!g_hash_table_lookup_extended (grammar->grammar,
 201                                      left, NULL, (gpointer*)&l))
 202     {
 203       l = g_malloc (sizeof (GList**));
 204       *l = NULL;
 205       g_hash_table_insert (grammar->grammar, left, l);
 206     }
 207
 208   rule = rule_new ();
 209
 210   *l = g_list_append (*l, rule);
 211
 212   return rule;
 213
 214 }
 215
 216 GList* grammar_get_rules (grammar_t* grammar, symbol_t* left)
 217 {
 218   GList** l;
 219   if (!g_hash_table_lookup_extended (grammar->grammar,
 220                                      left, NULL, (gpointer*)&l))
 221     {
 222       return NULL;
 223     }
 224   return g_list_first (*l);
 225 }
 226
 227 GList* grammar_get_rule (rule_t* rule)
 228 {
 229   return rule->right;
 230 }