[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Eliot-dev] Changes to eliot/dic/automaton.c [antoine-1]
From: |
eliot-dev |
Subject: |
[Eliot-dev] Changes to eliot/dic/automaton.c [antoine-1] |
Date: |
Sun, 23 Oct 2005 16:58:24 -0400 |
Index: eliot/dic/automaton.c
diff -u eliot/dic/automaton.c:1.9.2.2 eliot/dic/automaton.c:1.9.2.3
--- eliot/dic/automaton.c:1.9.2.2 Sun Oct 23 18:38:18 2005
+++ eliot/dic/automaton.c Sun Oct 23 20:58:19 2005
@@ -17,8 +17,6 @@
/* along with this program; if not, write to the Free Software */
/* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
-/* $Id: automaton.c,v 1.9.2.2 2005/10/23 18:38:18 afrab Exp $ */
-
/**
* \file automaton.c
* \brief (Non)Deterministic Finite Automaton for Regexp
@@ -56,7 +54,7 @@
/* ************************************************** *
exported functions for static automata
* ************************************************** */
-
+
automaton automaton_build (int init_state, int *ptl, int *PS, struct
search_RegE_list_t *list);
void automaton_delete (automaton a);
int automaton_get_nstate (automaton a);
@@ -64,7 +62,7 @@
int automaton_get_accept (automaton a, int state);
int automaton_get_next_state (automaton a, int start, char l);
void automaton_dump (automaton a, char* filename);
-
+
/* ************************************************** *
static functions for dynamic automata
@@ -116,7 +114,7 @@
exported functions for static automata
* ************************************************** */
-automaton
+automaton
automaton_build(int init_state, int *ptl, int *PS, struct search_RegE_list_t
*list)
{
Automaton nfa,dfa;
@@ -139,7 +137,7 @@
return final;
}
-void
+void
automaton_delete(automaton a)
{
int i;
@@ -174,7 +172,7 @@
return a->trans[state][(int)l];
}
-void
+void
automaton_dump(automaton a, char* filename)
{
int i,l;
@@ -235,8 +233,8 @@
static Automaton
s_automaton_create()
-{
- Automaton a;
+{
+ Automaton a;
a = (Automaton)malloc(sizeof(struct Automaton_t));
a->nstates = 0;
a->init_state = NULL;
@@ -287,9 +285,9 @@
return s;
}
-static void
+static void
s_automaton_add_state(Automaton a, astate s)
-{
+{
a->nstates ++;
alist_add(a->states,(void*)s);
DMSG(printf("** state %s added to
automaton\n",s_automaton_id_to_str(s->id)));
@@ -308,7 +306,7 @@
//DMSG(printf("** get state %s ok\n",s_automaton_id_to_str(s->id)));
return s;
}
- }
+ }
return NULL;
}
@@ -344,7 +342,7 @@
DMSG(printf("** current state =
%s\n",s_automaton_id_to_str(current_state->id)));
memset(used_letter,0,sizeof(used_letter));
/* 3: \foreach l in \sigma | l \neq # */
- for(p=1; p < maxpos; p++)
+ for(p=1; p < maxpos; p++)
{
int current_letter = ptl[p];
if (used_letter[current_letter] == 0)
@@ -353,7 +351,7 @@
int pos, ens = 0;
for(pos = 1; pos <= maxpos; pos++)
{
- if (ptl[pos] == current_letter &&
+ if (ptl[pos] == current_letter &&
(int)alist_elt_get_value(alist_get_first(current_state->id)) & (1 << (pos - 1)))
ens |= PS[pos];
}
@@ -369,7 +367,7 @@
current_state->next[current_letter] = temp_state;
alist_add(L,temp_state);
}
- else
+ else
{
alist_delete(temp_id);
current_state->next[current_letter] = temp_state;
@@ -417,7 +415,7 @@
if ((z = y->next[letter]) != NULL) /* \delta (y,z) = l
*/
{
- r = s_automaton_successor(z->id,RE_EPSILON,nfa, list);
+ r = s_automaton_successor(z->id,RE_EPSILON,nfa, list);
alist_insert(Ry,r);
alist_delete(r);
alist_insert(Ry,z->id); /* Ry = Ry \cup
succ(z) */
@@ -426,7 +424,7 @@
/* \epsilon transition from start node */
if ((z = y->next[RE_EPSILON]) != NULL) /* \delta (y,z) =
\epsilon */
{
- r = s_automaton_successor(z->id,letter,nfa, list);
+ r = s_automaton_successor(z->id,letter,nfa, list);
alist_insert(Ry,r); /* Ry = Ry \cup
succ(z) */
alist_delete(r);
}
@@ -443,7 +441,7 @@
DMSG(printf("is in "));
DMSG(regexp_print_letter(stdout,i));
- r = s_automaton_successor(z->id,RE_EPSILON,nfa, list);
+ r = s_automaton_successor(z->id,RE_EPSILON,nfa, list);
alist_insert(Ry,r);
alist_delete(r);
alist_insert(Ry,z->id);
@@ -477,14 +475,14 @@
DMSG(printf("%s ",s_automaton_id_to_str(ns->id)));
if (ns->accept && alist_is_in(s->id,idx))
{
- DMSG(printf("(ok) "));
+ DMSG(printf("(ok) "));
s->accept = 1;
}
}
DMSG(printf("\n"));
}
-static Automaton
+static Automaton
s_automaton_NFA_to_DFA(Automaton nfa, struct search_RegE_list_t *list)
{
Automaton dfa = NULL;
@@ -514,7 +512,7 @@
if (! alist_is_empty(temp_id))
{
-
+
DMSG(printf("*** successor of %s for
",s_automaton_id_to_str(current_state->id)));
DMSG(regexp_print_letter(stdout,letter));
DMSG(printf(" = %s\n", s_automaton_id_to_str(temp_id)));
@@ -522,7 +520,7 @@
temp_state = s_automaton_get_state(dfa,temp_id);
// DMSG(printf("*** automaton get state -%s-
ok\n",s_automaton_id_to_str(temp_id)));
-
+
if (temp_state == NULL)
{
temp_state = s_automaton_state_create(temp_id);
@@ -540,7 +538,7 @@
{
alist_delete(temp_id);
}
- }
+ }
}
for(ptr = alist_get_first(dfa->states) ; ptr ; ptr =
alist_get_next(dfa->states,ptr))
@@ -548,7 +546,7 @@
astate s = (astate)alist_elt_get_value(ptr);
s_automaton_node_set_accept(s,nfa);
}
-
+
alist_delete(L);
return dfa;
}
@@ -557,11 +555,11 @@
* ************************************************** *
* ************************************************** */
-static automaton
+static automaton
s_automaton_finalize(Automaton a)
{
int i,l;
- automaton fa = NULL;
+ automaton fa = NULL;
alist_elt ptr;
astate s;
@@ -593,9 +591,9 @@
s = (astate)alist_elt_get_value(ptr);
i = s->id_static;
- if (s == a->init_state)
+ if (s == a->init_state)
fa->init = i;
- if (s->accept == 1)
+ if (s->accept == 1)
fa->accept[i] = 1;
for(l=0; l < MAX_TRANSITION_LETTERS; l++)
@@ -611,7 +609,7 @@
* ************************************************** *
* ************************************************** */
-static void
+static void
s_automaton_print_nodes(FILE* f, Automaton a)
{
char * sid;
@@ -635,7 +633,7 @@
fprintf(f,"\n");
}
-static void
+static void
s_automaton_print_edges(FILE* f, Automaton a)
{
int letter;
@@ -660,7 +658,7 @@
}
}
-static void
+static void
s_automaton_dump(Automaton a, char* filename)
{
FILE* f;