为了加速转换的处理，我压缩了符号表。具体算法参考任何一本与编译或者自动机相关的书籍。
这里的核心问题是处理传递性闭包，transitive closure,这个我目前采取的是最简单的warshall算法，虽然是4次的复杂度，但是由于我构建nfa的时候并没有采取标准的方法，使得nfa的节点减少很多。ps，上上篇所说的re转nfa，我这里有一个修改，就是对于or转换，不再增加节点，而是只增加两条空转换边。
相关代码如下
#include "nfa_process.h"
//首先在原来的nfa节点中，把最后的那个正则的开始节点可达的那些节点提取出来，相当于又一次的拷贝
p_edge_list nfa_to_dfa[];//这个当作新的nfa图
int nfa_min_node_number=;//注意nfa_min_node_number使用的时候是从1开始的，他的值表示已经使用到了多少
#define BYTE_MASK 0x80
typedef struct _dfa_edge
{
struct _dfa_edge* next;
char label;
int dest_dfa_index;
}dfa_edge,*pdfa_edge;
typedef struct _dfa_node
{
pdfa_edge begin;
int dfa_hash_number;
}dfa_node,*pdfa_node;
dfa_node current_dfa_table[];//由于dfa的数量很大，所以开一个400的数组
int dfa_node_number=;//dfa_node_number作为一个全局变量，用来标号使用
int current_dfa_node=;//这个用来表示处理到了那一个dfa节点了
typedef struct _dfa_hash
{
int in_use;
char* name;
int dfa_node_pointer;
}dfa_hash;
dfa_hash dfa_hash_table[];//400的理由同上，这里刚好397是一个质数
void ntd_add_edge(int ntd_node_begin,int ntd_node_end,char label)//在压缩过的 nfa中加边
{
p_edge_list temp_pnode=malloc(sizeof(struct _graph_edge_list));
temp_pnode->label_of_edge=label;
temp_pnode->destination_number=ntd_node_end;
temp_pnode->next_edge=nfa_to_dfa[ntd_node_begin];
nfa_to_dfa[ntd_node_begin]=temp_pnode;
}
int dfa_into_hash(char* input_name,int dfa_node_index,int byte_of_bitmap)//这里是hash插入函数
{
int for_i;
unsigned int result;
int counter;
char* hash_name;
result=;
for(for_i=;for_i<byte_of_bitmap;for_i++)
{
result+=(unsigned int) input_name[for_i];
}
result=result%;
counter=;
while(counter<)
{
if(dfa_hash_table[result].in_use==)
{
dfa_hash_table[result].dfa_node_pointer=dfa_node_index;
dfa_hash_table[result].in_use=;
hash_name=malloc(sizeof(char)*(byte_of_bitmap+));
strcpy(hash_name,input_name);
dfa_hash_table[result].name=hash_name;
return result;
}
result=(result+)%;
counter++;
}
return -;
}
int search_dfa_hash(char* input_name)//对于一个名字寻找是否已经在表中
{
int for_i;
unsigned int result;
int counter;
int byte_of_bitmap=strlen(input_name);
result=;
for(for_i=;for_i<byte_of_bitmap;for_i++)
{
result+=(unsigned int) input_name[for_i];
}
result=result%;
counter=;
while(counter<)
{
if(dfa_hash_table[result].in_use==)
{
return -;
}
else
{
if(!strcmp(dfa_hash_table[result].name,input_name))
{
return result;
}
else
{
result=(result+)%;
counter++;
}
}
}
return -;
} int hamming_distance(int input)//用来得到一个4字节的int里面二进制存在1的个数
{
int temp=(unsigned)input;
temp=(temp&0x55555555)+((temp>>)&0x55555555);
temp=(temp&0x33333333)+((temp>>)&0x33333333);
temp=(temp&0x0f0f0f0f)+((temp>>)&0x0f0f0f0f);
temp=(temp&0x00ff00ff)+((temp>>)&0x00ff00ff);
temp=(temp&0x0000ffff)+((temp>>)&0x0000ffff);
return temp;
}
int length_of_char_set(void)//计算字符表中的字符的种类
{
int result=;
result+=hamming_distance(alpha_table.char_one);
result+=hamming_distance(alpha_table.char_two);
result+=hamming_distance(alpha_table.char_three);
result+=hamming_distance(alpha_table.char_four);
return result;
} minimize_char_set(char* mini_set)//压缩字母表
{
int for_i;
unsigned int another_mask;
int mini_set_counter;
mini_set_counter=for_i=;
for(for_i=;for_i<;for_i++)
{
if(for_i!=)//对于空转换字符我们不予理睬
{
another_mask=MASK>>for_i;
if(alpha_table.char_one&another_mask)
{ mini_set[mini_set_counter++]=for_i;
}
}
}
for(for_i=;for_i<;for_i++)
{
another_mask=MASK>>(for_i%);
if(alpha_table.char_two&another_mask)
{
mini_set[mini_set_counter++]=for_i;
}
}
for(for_i=;for_i<;for_i++)
{
another_mask=MASK>>(for_i%);
if(alpha_table.char_three&another_mask)
{
mini_set[mini_set_counter++]=for_i;
}
}
for(for_i=;for_i<;for_i++)
{
another_mask=MASK>>(for_i%);
if(alpha_table.char_four&another_mask)
{
mini_set[mini_set_counter++]=for_i;
}
}
} void set_dfa_bit(char* begin,int index)//在转换节点中设置第index位，这里是从1开始数的，所以要注意
{
char* temp;
index=index-;
temp=begin+index/;
index=index%;
*temp=(unsigned char)(*temp)|(BYTE_MASK>>index);
}
int extract_nfa(void)//这里是压缩nfa，实质上与前面那个nfa复制函数是一样的
//返回开始节点的索引，为了nfa转dfa用
{
int nfa_begin_number;
int nfa_end_number; int copy_destination;
int offset;
int original_token;
char copy_label;
p_edge_list pcopy;
original_token=token_node_number-;
nfa_begin_number=token_node[original_token].bottom;
nfa_end_number=token_node[original_token].top;
offset=nfa_min_node_number-nfa_begin_number+;//因为这样要考虑下一个节点
for(nfa_begin_number;nfa_begin_number<=nfa_end_number;nfa_begin_number++)//开始复制图
{
pcopy=nfa_node[nfa_begin_number];
nfa_min_node_number++;
nfa_node[nfa_min_node_number]=NULL;
while(pcopy!=NULL)
{
copy_label=pcopy->label_of_edge;
copy_destination=pcopy->destination_number+offset;
ntd_add_edge(nfa_min_node_number,copy_destination,copy_label);
pcopy=pcopy->next_edge;
}
}
return token_node[original_token].begin+offset;
}
void tackle_dfa_label(char* output,int dfa_current,char input_label,int node_size)//处理边转换
{
char* current_nfa_set;
int for_i;
int dfa_hash_index;
p_edge_list temp_edge;//这里处理的还是nfa的边
char temp_label=input_label;
dfa_hash_index=current_dfa_table[dfa_current].dfa_hash_number;
current_nfa_set=dfa_hash_table[dfa_hash_index].name;
for(for_i=;for_i<node_size;for_i++)//对于这个位图中的每一位进行遍历
{
if((BYTE_MASK>>(for_i%))&(current_nfa_set[for_i/]))//如果这个位有效
{
temp_edge=nfa_to_dfa[for_i+];//注意这里要加1，因为 nfa_to_table的索引是从1开始的
while(temp_edge!=NULL)
{
if(temp_edge->label_of_edge==temp_label)
{
set_dfa_bit(output,temp_edge->destination_number);//注意这里不需要减1
}
temp_edge=temp_edge->next_edge;
}
}
}
} int is_label_null(char* input_name,int name_size_inbyte)//判断一个label是否为空
{
int result;
int for_i;
result=;
for(for_i=;for_i<name_size_inbyte;for_i++)
{
result+=(unsigned char)(input_name[for_i]);
}
if(result==)
{
return ;
}
else
{
return ;
}
}
void extend_dfa_label(char* input_name,int node_size,int* result_null_access)//这里对结果进行空扩展
{
char* extend_temp;
int for_i,for_j;
int size_in_byte;
unsigned char current_mask;
int for_k;
size_in_byte=(node_size+)/;
for_j=;
extend_temp=malloc(sizeof(char)*(size_in_byte));//临时的位图
for(for_i=;for_i<size_in_byte;for_i++)
{
extend_temp[for_i]=;
}
while(for_j<node_size)
{
current_mask=BYTE_MASK>>(for_j%);
if(input_name[for_j/]¤t_mask)
{
for(for_k=;for_k<node_size;for_k++)
{
if(result_null_access[for_j*node_size+for_k])
{
set_dfa_bit(extend_temp,for_k+);//for_k处在for_k+1位那里
}
}
}
for_j++;
}
for(for_k=;for_k<size_in_byte;for_k++)//然后把结果复制回去
{
input_name[for_k]=extend_temp[for_k];
}
free(extend_temp);
} void null_transition(int index_of_begin)//这里是nfa转dfa的主函数
{
int nfa_begin=index_of_begin;//获得起始节点
int node_size=nfa_min_node_number;
int for_i,for_k,for_m;
int for_j;
//现在需要求传递性闭包，目前为了省事采取四次方的算法，虽然可以做点优化，但是是以空间复杂度为代价的
//由于是四次方的算法，所以我们需要尽量减少节点的数目，幸运的是，我自己定义的转换规则几乎很少去增加节点
//这样将大大的有利于效率
//计算传递性闭包，我采用warshall算法，直接开一个n*n的矩阵
int* origin_null_access=malloc(sizeof(int)*node_size*node_size);
int* result_null_access=malloc(sizeof(int)*node_size*node_size);
int node_size_byte=(node_size+)/;
int alpha_size;
char* mini_alpha_set;
int search_result;
char label;
pdfa_edge temp_dfa_edge;
char* begin_nfa_set=malloc(sizeof(char)*(node_size_byte+));
char* temp_nfa_set=malloc(sizeof(char)*(node_size_byte+));
for(for_i=;for_i<node_size*node_size;for_i++)
{
origin_null_access[for_i]=;
result_null_access[for_i]=;
}
for(for_i=;for_i<=node_size_byte;for_i++)//malloc注意一定要自己去初始化值，否则默认为0xcd操
{
begin_nfa_set[for_i]=;
temp_nfa_set[for_i]=;
}
for(for_i=;for_i<=node_size;for_i++)//初始化矩阵
//注意矩阵下标是从0开始的，而节点下标是从1开始的，引用的时候要小心
{
p_edge_list temp;
temp=nfa_to_dfa[for_i];
origin_null_access[(for_i-)*node_size+for_i-]=;//由于自己对自己总是可达的
result_null_access[(for_i-)*node_size+for_i-]=;//同上
while(temp!=NULL)
{
if(temp->label_of_edge==(char))
{
origin_null_access[(for_i-)*node_size+temp->destination_number-]=;
result_null_access[(for_i-)*node_size+temp->destination_number-]=;
}
temp=temp->next_edge;
}
}
//初始化基础的可达矩阵
for(for_i=;for_i<node_size;for_i++)//这里之所以迭代node_size-1次，因为最长简单路径不超过node_size-1条边。
{
for(for_j=;for_j<node_size;for_j++)
{
for(for_k=;for_k<node_size;for_k++)
{
int temp=;
for(for_m=;for_m<node_size;for_m++)
{
temp+=result_null_access[for_j*node_size+for_m]*origin_null_access[for_m*node_size+for_k];
}
if(temp>)
{
result_null_access[for_j*node_size+for_k]=;//可联通
}
else
{
result_null_access[for_j*node_size+for_k]=;//不可联通
}
}
}
}
//至此邻接矩阵已经构建完成，现在我们把它变成邻接位图
node_size_byte=(node_size+)/;
//现在来处理字符集，注意，这里不包括空转换字符
alpha_size=length_of_char_set();
mini_alpha_set=malloc(sizeof(char)*alpha_size);
for(for_i=;for_i<alpha_size;for_i++)
{
mini_alpha_set[for_i]=;
}
minimize_char_set(mini_alpha_set);
//这里用位图来表示每个点的在某一个字符上的转换集合
//加上一个\0，是为了使他变成字符串，这样就好比较了
//方便了hash和二叉树的插入和寻找
for(for_i=;for_i<node_size;for_i++)
{
if(result_null_access[(nfa_begin-)*node_size+for_i]==)//我擦，这里忘了减少1了
{
set_dfa_bit(begin_nfa_set,for_i+);
}
}
dfa_node_number++;
current_dfa_table[dfa_node_number].begin=NULL;
current_dfa_table[dfa_node_number].dfa_hash_number=dfa_into_hash(begin_nfa_set,dfa_node_number,node_size_byte+);
current_dfa_node=;
while(current_dfa_node<dfa_node_number)
{
current_dfa_node++; for(for_j=;for_j<alpha_size;for_j++)
{
for(for_i=;for_i<=node_size_byte;for_i++)
{
temp_nfa_set[for_i]='\0';
}//清空上次的结果
label=mini_alpha_set[for_j];//设定转换条件
tackle_dfa_label(temp_nfa_set,current_dfa_node,label,node_size);//进行边转换
extend_dfa_label(temp_nfa_set,node_size,result_null_access);//进行空扩展
if(!is_label_null(temp_nfa_set,node_size_byte))//如果在这个字符上有转换
{
search_result=search_dfa_hash(temp_nfa_set);
if(search_result==-)//如果为新的状态，则为之建立一个新的节点
{
dfa_node_number++;
current_dfa_table[dfa_node_number].begin=NULL;
current_dfa_table[dfa_node_number].dfa_hash_number=dfa_into_hash(temp_nfa_set,dfa_node_number,node_size_byte+);
temp_dfa_edge=malloc(sizeof(struct _dfa_edge));//建立一条新的边
temp_dfa_edge->next=current_dfa_table[current_dfa_node].begin;
temp_dfa_edge->label=mini_alpha_set[for_j];
temp_dfa_edge->dest_dfa_index=dfa_node_number;
printf("add an node %d\n",dfa_node_number);
printf("add an edge from %d to %d with label %c\n",current_dfa_node,dfa_node_number,mini_alpha_set[for_j]);
}
else//如果已经存在这个状态
{
temp_dfa_edge=malloc(sizeof(struct _dfa_edge));
temp_dfa_edge->next=current_dfa_table[current_dfa_node].begin;
temp_dfa_edge->label=mini_alpha_set[for_j];
temp_dfa_edge->dest_dfa_index=dfa_hash_table[search_result].dfa_node_pointer;
printf("add an edge from %d to %d with label %c\n",current_dfa_node,temp_dfa_edge->dest_dfa_index,mini_alpha_set[for_j]);
}
current_dfa_table[current_dfa_node].begin=temp_dfa_edge;//修改邻接表
}//对于单字符处理完毕
}//对于所有的字符都处理完毕了
}//对于当前节点处理完毕，但是可能还有其他节点，继续迭代。
}//他妈的 nfa转dfa全都处理完毕
void show_dfa_table(void)//输出邻接表
{
int for_i;
pdfa_edge temp_dfa_edge;
for(for_i=;for_i<=dfa_node_number;for_i++)
{
temp_dfa_edge=current_dfa_table[for_i].begin;
while(temp_dfa_edge!=NULL)
{
printf("there is an dfa edge from %d to %d with label %c\n",for_i,temp_dfa_edge->dest_dfa_index,temp_dfa_edge->label);
temp_dfa_edge=temp_dfa_edge->next;
}
}
}