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