grammar.c

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