dfa.c

   1 /*
   2  * Copyright 2005 Thadeu Lima de Souza Cascardo
   3  *
   4  * libgrammatic
   5  *
   6  * Code for deterministic finite automata
   7  *
   8  * This code should use a similar hash table as in LR parsers.
   9  * However, it will need not stack anything. Table may be fed from a
  10  * grammar or a regular expression. A regular expression may be
  11  * translated to a grammar and, then, to a finite automata.
  12  *
  13  */
  14
  15 #include <grammar.h>
  16 #include <stdlib.h>
  17 #include <dfa.h>
  18 #ifdef DEBUG
  19 #include <stdio.h>
  20 #endif
  21
  22 struct _dfa_t
  23 {
  24   nextcb cb;
  25   gpointer data;
  26   GHashTable* table;
  27   dfa_state_t* start;
  28 };
  29
  30 typedef struct
  31 {
  32   gint state;
  33   gboolean end;
  34 } _dfa_state_t;
  35
  36 dfa_state_t* dfa_state_new (gint state, gboolean end)
  37 {
  38   dfa_state_t* dfa_state;
  39   dfa_state = g_malloc (sizeof (dfa_state_t));
  40   dfa_state->state = state;
  41   dfa_state->end = end;
  42   return dfa_state;
  43 }
  44
  45 void dfa_state_delete (dfa_state_t* dfa_state)
  46 {
  47   g_free (dfa_state);
  48 }
  49
  50 gint dfa_state_hash (gconstpointer data)
  51 {
  52   dfa_state_t* dfa_state;
  53   dfa_state = (dfa_state_t*) data;
  54   return g_direct_hash (dfa_state->state);
  55 }
  56
  57 gboolean dfa_state_equal (gconstpointer a, gconstpointer b)
  58 {
  59   dfa_state_t* dfa_a;
  60   dfa_state_t* dfa_b;
  61   dfa_a = (dfa_state_t*) a;
  62   dfa_b = (dfa_state_t*) b;
  63   return dfa_a->state == dfa_b->state;
  64 }
  65
  66 dfa_t* dfa_new (nextcb cb, gpointer data, dfa_state_t* state)
  67 {
  68
  69   dfa_t* parser;
  70
  71   parser = g_malloc (sizeof (dfa_t));
  72   parser->cb = cb;
  73   parser->data = data;
  74   parser->start = state;
  75
  76   parser->table = g_hash_table_new_full (dfa_state_hash, dfa_state_equal,
  77                                          NULL, g_hash_table_destroy);
  78
  79   return parser;
  80
  81 }
  82
  83 void dfa_delete (dfa_t* parser)
  84 {
  85
  86   g_hash_table_destroy (parser->table);
  87
  88   g_free (parser);
  89
  90 }
  91
  92 gboolean dfa_add (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
  93                   dfa_state_t* next)
  94 {
  95
  96   GHashTable* table;
  97
  98   if (!g_hash_table_lookup_extended (parser->table, prev,
  99                                      NULL, (gpointer*) &table))
 100     {
 101       table = g_hash_table_new_full (symbol_hash, symbol_equal,
 102                                      g_free, dfa_state_delete);
 103       g_hash_table_insert (parser->table, prev, table);
 104     }
 105
 106   if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
 107     {
 108       return FALSE;
 109     }
 110
 111   g_hash_table_insert (table, symbol, next);
 112   return TRUE;
 113
 114 }
 115
 116 gboolean dfa_lookup (dfa_t* parser, dfa_state_t* prev, symbol_t* symbol,
 117                      dfa_state_t** next)
 118 {
 119
 120   GHashTable* table;
 121   dfa_state_t* n;
 122
 123   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 124                                      NULL, (gpointer*) &table))
 125     {
 126       return FALSE;
 127     }
 128
 129   if (!g_hash_table_lookup_extended (table, symbol,
 130                                      NULL, (gpointer*) &n))
 131     {
 132       return FALSE;
 133     }
 134
 135   if (next)
 136     *next = n;
 137
 138   return TRUE;
 139
 140 }
 141
 142 static gpointer leaf_new (gpointer data)
 143 {
 144   return g_node_new (data);
 145 }
 146
 147 static gpointer tree_new (rule_t* rule)
 148 {
 149   return g_node_new (rule);
 150 }
 151
 152 static gpointer tree_add (gpointer tree, gpointer data)
 153 {
 154   return g_node_prepend (tree, data);
 155 }
 156
 157 gpointer dfa_build (dfa_t* parser)
 158 {
 159
 160   dfa_state_t* state;
 161   dfa_state_t* last;
 162   dfa_state_t* next;
 163   symbol_t* symbol;
 164
 165   symbol = g_malloc (sizeof (symbol_t));
 166
 167   state = parser->start;
 168   last = NULL;
 169
 170   if (state->end)
 171     last = state;
 172
 173   while (dfa_lookup (parser, state, symbol, &state))
 174     {
 175
 176       symbol->value = parser->cb (parser->data, NULL);
 177       symbol->terminal = TRUE;
 178
 179       if (state->end)
 180         last = state;
 181
 182     }
 183
 184   return last;
 185
 186 }