登 录
贴一个字符串匹配算法实现：
因为这是嵌入式设备上提炼的一个简单需求，没有考虑周全，有以下缺点：
#ifndef _DFA_H_<br /> #define _DHA_H_</p> <p>#define MAX_STATE 128<br /> #define EMPTY_INPUT '/0'</p> <p>/*<br /> * pattern string:<br /> * regular expression meta characters : '?', '+', '*', '[', ']', '^', '(', ')', '.'<br /> * character set: a subset of ascii character set - { ?+*^[](). }<br /> */</p> <p>// list head has no state inside<br /> struct state_set {<br /> int state;<br /> struct state_set *next;<br /> };</p> <p>struct dfa_transform {<br /> char input;<br /> int state;<br /> struct dfa_transform *next;<br /> };</p> <p>struct dfa_transform_entry {<br /> int ntrans;<br /> int state;<br /> struct dfa_transform *transform;<br /> };</p> <p>struct dfa {<br /> int nstates;<br /> int start;<br /> struct state_set *terminals;<br /> struct dfa_transform_entry *trans_table;<br /> // char *alpha_set;<br /> char *matched_str;<br /> };</p> <p>struct dfa *dfa_create(const char *pattern);<br /> void dfa_release(struct dfa *d);</p> <p>void dfa_set_alpha(const char *alpha);<br /> int dfa_match(const struct dfa *d, const char *string);</p> <p>#endif<br />
#include <stdlib.h><br /> #include <stdio.h><br /> #include <string.h></p> <p>#include "dfa.h"</p> <p>static char *alpha_set = "012345678";</p> <p>static int is_alpha(const char *alpha_set, char c)<br /> {<br /> int i;<br /> for (i = 0; i != strlen(alpha_set); i++)<br /> if (alpha_set[i] == c)<br /> return 1;<br /> return 0;<br /> }</p> <p>static void free_set(struct state_set *set)<br /> {<br /> if (!set)<br /> return;</p> <p> if (set->next)<br /> free_set(set->next);</p> <p> free(set);<br /> };</p> <p>static void free_transform(struct dfa_transform *t)<br /> {<br /> if (!t)<br /> return;</p> <p> if (t->next)<br /> free_transform(t->next);</p> <p> free(t);<br /> }</p> <p>static void free_dfa(struct dfa *dfa)<br /> {<br /> int i;</p> <p> if (!dfa)<br /> return;</p> <p> free_set(dfa->terminals);</p> <p> for (i = 0; i != dfa->nstates; i++)<br /> free_transform(dfa->trans_table[i].transform);</p> <p> if (dfa->trans_table)<br /> free(dfa->trans_table);<br /> };</p> <p>static void dfa_dump(const struct dfa *d)<br /> {<br /> struct state_set *set_iter = d->terminals->next;<br /> struct dfa_transform *trans_iter;<br /> int state = 0;<br /> printf("/n/nnfa (maybe dfa):/n/n");<br /> printf("/tnstates:/t/t%d/n", d->nstates);<br /> printf("/tstart:/t/t/t%d/n", d->start);<br /> printf("/tterminal states:/t{");<br /> for (; set_iter; set_iter = set_iter->next)<br /> printf("%d, ", set_iter->state);<br /> printf("}/n");<br /> printf("/talpha set:/t/t/"%s/"/n", alpha_set);<br /> printf("/n/ttransfer table:/n/n/tstate/ttransforms(input -> state)/n");</p> <p> for (; state != d->nstates; state++) {<br /> printf("/t%d/t", state);<br /> for (trans_iter = d->trans_table[state].transform; trans_iter; trans_iter = trans_iter->next)<br /> printf("(%c -> %d), ", trans_iter->input, trans_iter->state);<br /> printf("/n");<br /> }<br /> }</p> <p>static int in_set(const struct state_set *set, int state)<br /> {<br /> struct state_set *iter = set->next;<br /> for (; iter && iter->state != state; iter = iter->next);<br /> if (iter)<br /> return 1;<br /> return 0;<br /> }</p> <p>static void set_add_state(struct state_set *set, int state)<br /> {<br /> struct state_set *new_elem;</p> <p> if (set && in_set(set, state))<br /> return;</p> <p> new_elem = malloc(sizeof(struct state_set));<br /> new_elem->state = state;<br /> new_elem->next = set->next;<br /> set->next = new_elem;<br /> }</p> <p>static int same_set(const struct state_set *s1, const struct state_set *s2)<br /> {<br /> const struct state_set *itl, *itr;</p> <p> if (!s1->next && s2->next || !s2->next && s1->next)<br /> return 0;<br /> for (itl = s1->next; itl; itl = itl->next) {<br /> for (itr = s2->next; itr; itr = itr->next)<br /> if (itl->state == itr->state)<br /> break;<br /> if (!itr)<br /> return 0;<br /> }</p> <p> for (itl = s2->next; itl; itl = itl->next) {<br /> for (itr = s1->next; itr; itr = itr->next)<br /> if (itl->state == itr->state)<br /> break;<br /> if (!itr)<br /> return 0;<br /> }</p> <p> return 1;<br /> }</p> <p>static struct dfa *dfa_init(struct dfa *d)<br /> {<br /> d->start = d->nstates = 0;<br /> d->terminals = malloc(sizeof(struct state_set));<br /> d->terminals->next = 0;<br /> d->trans_table = 0;<br /> d->matched_str = 0;<br /> }</p> <p>static struct dfa *create_dfa_str(const char *pattern);</p> <p>static struct dfa *create_dfa_n_str(const char * const*patterns, int npatterns);</p> <p>static int transfer(const struct dfa *dfa, int state, char input)<br /> {<br /> if (state >= dfa->nstates)<br /> return -1;<br /> struct dfa_transform *trans_iter = (dfa->trans_table[state]).transform;<br /> for (; trans_iter && trans_iter->input != input; trans_iter = trans_iter->next);<br /> if (trans_iter)<br /> return trans_iter->state;<br /> return -1;<br /> }</p> <p>static int insert_transform(struct dfa *d, int state, char input, int next_state)<br /> {<br /> struct dfa_transform *new_trans;<br /> struct dfa_transform_entry *entry = &(d->trans_table[state]);</p> <p> new_trans = malloc(sizeof(struct dfa_transform));<br /> new_trans->input = input;<br /> new_trans->state = next_state;<br /> new_trans->next = 0;</p> <p> new_trans->next = entry->transform;<br /> entry->transform = new_trans;<br /> entry->ntrans++;</p> <p> return 0;<br /> }</p> <p>static struct state_set *set_transfer(const struct dfa *dfa, const struct state_set *set, char input)<br /> {<br /> struct dfa_transform *trans_iter;<br /> struct state_set *ret_set = 0;<br /> const struct state_set *set_iter;<br /> int state;</p> <p> if (!set || (set && !set->next))<br /> return 0;</p> <p> for (set_iter = set->next; set_iter; set_iter = set_iter->next) {<br /> state = set_iter->state;<br /> trans_iter = (dfa->trans_table[state].transform);<br /> for (; trans_iter; trans_iter = trans_iter->next) {<br /> if (trans_iter->input == input) {<br /> if (!ret_set) {<br /> ret_set = malloc(sizeof(struct state_set));<br /> ret_set->next = 0;<br /> }<br /> set_add_state(ret_set, trans_iter->state);<br /> }<br /> }<br /> }</p> <p> printf("set_transfer {");<br /> for (set_iter = set->next; set_iter; set_iter = set_iter->next)<br /> printf("%d, ", set_iter->state);<br /> printf("}: (/'%c/' -> {", input);<br /> if (ret_set)<br /> for (set_iter = ret_set->next; set_iter; set_iter = set_iter->next)<br /> printf("%d, ", set_iter->state);<br /> printf("}/n");<br /> return ret_set;<br /> }</p> <p>static struct state_set *e_closure(const struct dfa *nfa, const struct state_set *set)<br /> {<br /> struct dfa_transform *trans_iter;<br /> struct state_set *e_set, *set_iter;<br /> char *state_tag_map = malloc(nfa->nstates);<br /> int *state_queue = malloc(nfa->nstates * 4);<br /> int tail = 0, head = 0, qsize = nfa->nstates, s, i;<br /> for (i = 0; i != nfa->nstates; i++)<br /> state_tag_map[i] = 0;</p> <p> e_set = malloc(sizeof(struct state_set));<br /> e_set->next = 0;<br /> for (set_iter = set->next; set_iter; set_iter = set_iter->next)<br /> state_queue[head++] = set_iter->state;</p> <p> while (tail != head) {<br /> s = state_queue[tail++];<br /> if (tail == qsize)<br /> tail = 0;<br /> if (state_tag_map[s] == 1)<br /> continue;<br /> state_tag_map[s] = 1;<br /> set_add_state(e_set, s);<br /> for (trans_iter = nfa->trans_table[s].transform; trans_iter; trans_iter = trans_iter->next) {<br /> if (trans_iter->input == EMPTY_INPUT) {<br /> for (i = tail; i % qsize!= head; i++)<br /> if (trans_iter->state == state_queue[i % qsize])<br /> break;<br /> if (i % qsize != head || state_tag_map[trans_iter->state] == 1)<br /> continue;</p> <p> // add state to queue<br /> if ( (head + 1) % qsize == tail)<br /> printf("big warnning: queue overflow!/n");<br /> state_queue[head] = trans_iter->state;<br /> head = (head + 1) % qsize;<br /> }<br /> }<br /> }</p> <p> // dump<br /> printf("empty closure of {");<br /> for (set_iter = set->next; set_iter; set_iter = set_iter->next)<br /> printf("%d, ", set_iter->state);<br /> printf("} is {");<br /> for (set_iter = e_set->next; set_iter; set_iter = set_iter->next)<br /> printf("%d, ", set_iter->state);<br /> printf("}/n");</p> <p> return e_set;<br /> }</p> <p>static struct dfa *nfa_to_dfa(const struct dfa *nfa)<br /> {<br /> struct set_transfer {<br /> struct state_set *set;<br /> struct state_set *next_set;<br /> struct set_transfer *next;<br /> int dfa_state;<br /> char input;<br /> } *set_transfer_table[128], *set_trans_iter ;<br /> struct state_set *state_set_queue[128];<br /> int tail = 0, head = 0, nsets = 0, i, j;<br /> struct state_set *s0, *set_iter1, *set_iter2, *new_set;<br /> struct dfa *ret_dfa;</p> <p> s0 = malloc(sizeof(struct state_set));<br /> s0->next = 0;<br /> set_add_state(s0, nfa->start);<br /> state_set_queue[(head++) % 128] = e_closure(nfa, s0);<br /> free_set(s0);</p> <p> while (tail != head) {<br /> set_iter1 = state_set_queue[(tail++) % 128];<br /> // dump<br /> printf("dfa state %d : state set: {", nsets);<br /> for (set_iter2 = set_iter1->next; set_iter2; set_iter2 = set_iter2->next)<br /> printf("%d, ", set_iter2->state);<br /> printf("}/n");</p> <p> set_transfer_table[nsets] = malloc(sizeof(struct set_transfer));<br /> set_transfer_table[nsets]->set = set_iter1;<br /> set_transfer_table[nsets]->next = 0;<br /> set_transfer_table[nsets]->dfa_state = nsets;<br /> nsets++;<br /> set_trans_iter = set_transfer_table[nsets - 1];<br /> for (i = 0; i != strlen(alpha_set); i++) {<br /> new_set = set_transfer(nfa, set_iter1, alpha_set[i]);<br /> if (new_set) {<br /> set_iter2 = e_closure(nfa, new_set);<br /> free_set(new_set);<br /> for (j = 0; j != nsets; j++)<br /> if (same_set(set_transfer_table[j]->set, set_iter2))<br /> break;<br /> if (j == nsets) {<br /> for (j = tail; j % 128 != head; j++)<br /> if (same_set(state_set_queue[j], set_iter2))<br /> break;<br /> if (j % 128 != head) {<br /> free_set(set_iter2);<br /> set_iter2 = state_set_queue[j];<br /> printf("{");<br /> for (new_set = set_iter2->next; new_set; new_set = new_set->next)<br /> printf("%d, ", new_set->state);<br /> printf("} in set_queue/n");<br /> } else { // add to queue<br /> if ((head + 1) % 128 == tail)<br /> printf("big warnning: queue overflow!/n");<br /> state_set_queue[head] = set_iter2;<br /> head = (head + 1) % 128;<br /> }<br /> } else {<br /> printf("{");<br /> for (new_set = set_iter2->next; new_set; new_set = new_set->next)<br /> printf("%d, ", new_set->state);<br /> printf("} in set_transfer_table/n");</p> <p> free_set(set_iter2);<br /> set_iter2 = set_transfer_table[j]->set;<br /> }</p> <p> // insert set_transfer (set_transfer_table[nsets - 1].set, alpha_set[i], set_iter2)<br /> printf("dfa transfer insert : {");<br /> for (new_set = set_iter1->next; new_set; new_set= new_set->next)<br /> printf("%d, ", new_set->state);<br /> printf("} :/t/t/t(%c -> {", alpha_set[i]);<br /> for (new_set = set_iter2->next; new_set; new_set= new_set->next)<br /> printf("%d, ", new_set->state);<br /> printf("}/n");</p> <p> set_trans_iter->next = malloc(sizeof(struct set_transfer));<br /> set_trans_iter->next->input = alpha_set[i];<br /> set_trans_iter->next->next_set = set_iter2;<br /> set_trans_iter->next ->next = 0;<br /> set_trans_iter = set_trans_iter->next;<br /> }<br /> }<br /> }</p> <p> // construct dfa from set_transfer_table<br /> ret_dfa = malloc(sizeof(struct dfa));<br /> dfa_init(ret_dfa);<br /> ret_dfa->nstates = nsets;<br /> ret_dfa->trans_table = malloc(sizeof(struct dfa_transform_entry) * nsets);<br /> memset(ret_dfa->trans_table, 0, sizeof(struct dfa_transform_entry) * nsets);<br /> for (i = 0; i != nsets; i++) {<br /> ret_dfa->trans_table[i].state = i;<br /> if (in_set(set_transfer_table[i]->set, nfa->nstates - 1))<br /> set_add_state(ret_dfa->terminals, set_transfer_table[i]->dfa_state);<br /> for (set_trans_iter = set_transfer_table[i]->next;<br /> set_trans_iter; set_trans_iter = set_trans_iter->next) {<br /> for (j = 0; j != nsets; j++)<br /> if (set_transfer_table[j]->set == set_trans_iter->next_set)<br /> break;<br /> insert_transform(ret_dfa, set_transfer_table[i]->dfa_state, set_trans_iter->input, j);<br /> printf("set transfer to dfa: transfer(%d: /'%c/'->%d)/n"<br /> , set_transfer_table[i]->dfa_state, set_trans_iter->input, j);<br /> }<br /> }</p> <p> // memeory release,<br /> // to be continue...<br /> return ret_dfa;</p> <p>}</p> <p>static struct dfa *merge_dfa(const struct dfa *dfa_l, const struct dfa *dfa_r)<br /> {<br /> // return dfa_left + dfa_right<br /> // to be continue...<br /> }</p> <p>/*<br /> * pattern string:<br /> * meta characters : { '?', '+', '*', '[', ']', '^', '(', ')', '.' }<br /> * character set: { 0, 1, 2, 3, 4, 5, 6 } represents keys on panel<br /> *<br /> * string to nfa details:<br /> * . : for all character in alpha-set, insert a transform<br /> *<br /> * a : back_state = front_state;<br /> * front_state++,<br /> *<br /> * [ab...] : back_state = front_state;<br /> * parall a|b|..., front_state++;<br /> *<br /> * (pattern) : (, push back_state,<br /> * ), pop to get back_state<br /> *<br /> * '*' : new state sn;<br /> * t(front_state, e) = { sn, back_state };<br /> * t(back_state, e) = sn<br /> * update back_state and front_state to sn<br /> *<br /> * '+' : new state sn;<br /> * t(front_state, e) = { sn, back_state };<br /> * update back_state to sn<br /> *<br /> * '?' : new state sn;<br /> * t(back_state, e) = t(front_state, e) = sn;<br /> * update back_state to sn<br /> *<br /> * '/0': add front_state to terminal SET<br /> * if stack.empty, algorithm terminaled, otherwise error<br /> * EOS : KEY_OK<br /> */<br /> struct dfa *dfa_create(const char *pattern)<br /> {<br /> printf("/ncreate dfa for pattern: /"%s/"/n", pattern);<br /> struct dfa *tmp_nfa, *ret_dfa;<br /> char *parall_inputs;<br /> int par_stack[5], top = 0;<br /> int back_state = 0, front_state = 0, new_state;<br /> int is_complement, i = 0, j;<br /> tmp_nfa = malloc(sizeof(struct dfa));<br /> dfa_init(tmp_nfa);<br /> tmp_nfa->trans_table = malloc(sizeof(struct dfa_transform_entry) * MAX_STATE);<br /> memset(tmp_nfa->trans_table, 0, sizeof(struct dfa_transform_entry) * MAX_STATE);<br /> while (pattern[i]) {<br /> if (is_alpha(alpha_set, pattern[i])) {<br /> back_state = front_state;<br /> front_state++;<br /> insert_transform(tmp_nfa, back_state, pattern[i], front_state);<br /> } else if (pattern[i] == '.') {<br /> back_state = front_state;<br /> front_state++;<br /> for (j = 0; j != strlen(alpha_set); j++)<br /> insert_transform(tmp_nfa, back_state, pattern[j], front_state);<br /> } else if (pattern[i] == '[') {<br /> back_state = front_state;<br /> front_state++;<br /> if (pattern[i+1] == '^') {<br /> i++;<br /> // ... unimplement<br /> } else {<br /> while (pattern[++i] != ']')<br /> insert_transform(tmp_nfa, back_state, pattern[i], front_state);<br /> }<br /> } else if (pattern[i] == '(') {<br /> back_state = front_state;<br /> par_stack[top++] = back_state;<br /> } else if (pattern[i] == ')') {<br /> back_state = par_stack[--top];<br /> } else if (pattern[i] == '*') {<br /> insert_transform(tmp_nfa, front_state, EMPTY_INPUT, front_state + 1);<br /> insert_transform(tmp_nfa, front_state, EMPTY_INPUT, back_state);<br /> insert_transform(tmp_nfa, back_state, EMPTY_INPUT, front_state + 1);<br /> front_state++;<br /> } else if (pattern[i] == '+') {<br /> insert_transform(tmp_nfa, front_state, EMPTY_INPUT, back_state);<br /> insert_transform(tmp_nfa, front_state, EMPTY_INPUT, front_state + 1);<br /> front_state++;<br /> } else if (pattern[i] == '?') {<br /> insert_transform(tmp_nfa, front_state, EMPTY_INPUT, front_state + 1);<br /> insert_transform(tmp_nfa, back_state, EMPTY_INPUT, front_state + 1);<br /> front_state++;<br /> } else {<br /> printf("bad pattern/n");<br /> return 0;<br /> }<br /> tmp_nfa->nstates = front_state + 1;<br /> i++;<br /> }</p> <p> dfa_dump(tmp_nfa);</p> <p> ret_dfa = nfa_to_dfa(tmp_nfa);<br /> free_dfa(tmp_nfa);</p> <p> return ret_dfa;<br /> }</p> <p>void dfa_release(struct dfa *d)<br /> {<br /> free_dfa(d);<br /> }</p> <p>int dfa_match(const struct dfa *d, const char *str)<br /> {<br /> if (!d || d->nstates <= 0) // ?? == 0<br /> return 0;<br /> int i = 0, state = d->start;<br /> for (; i != strlen(str); i++) {<br /> state = transfer(d, state, str[i]);<br /> if (state == -1)<br /> return 0;<br /> }</p> <p> return in_set(d->terminals, state);<br /> }</p> <p>int main(int argc, char **argv)<br /> {<br /> // struct dfa *d = dfa_create("3(1*(0?1[013]+)*(2012)?(23)+)*310[31]2*3*");<br /> char pattern[] = "1*23[243]+";<br /> char str[200];<br /> struct dfa *d = dfa_create(pattern);<br /> dfa_dump(d);<br /> while (1) {<br /> printf(" >");<br /> scanf("%199s", &str);<br /> if (dfa_match(d, str))<br /> printf("/"%s/" match /%s//n", str, pattern);<br /> else<br /> printf("/"%s/" unmatch /%s//n", str, pattern);<br /> }<br /> return 0;<br /> }<br />
抱歉!评论已关闭.