前面那片文章生成的语法分析表并不是最优的，因为有些项在遇到错误输入的时候，并不是采取报错，而是执行规约，直到不能再规约的时候才报错。这是不科学的，我们需要在得到错误输入的时候立马报错，为了实现这个功能，我们需要知道某个文法符号的后面可能接的终结文法符号的集合，只有当前的输入终结文法符号处在栈顶文法符号的后缀集合中时，我们才去采取接受规约移进这三个操作，否则报错。
为了得到后缀集合，我们首先需要得到每一个文法符号的开始符号集合。为了得到这个集合，我们需要将这些符号进行拓扑排序，以保证生成体的第一个符号在生成体的头部符号处理前处理。注意这里一定不会出现环，即出现E:->T +R ,T:->E+F这种情况，至于问什么不会出现，我只是凭直觉。还需要说明的一点是，对于左递归文法，则不需要添加自己到自己的边。
在生成开始集合之后，我们再去生成直接后缀集合，即对于A:->B.C这种的产生式，我们可以直接把c的开始符号集合添加到b的后缀集合之中。这里就不需要拓扑排序了，因为我们的first集合已经完全生成了。
生成了直接后缀集合之后，我们再生成间接后缀集合，即 A:->B.这种的，b的后缀依赖于a的后缀，我们又需要去做一次拓扑排序。直觉上是没有环。。。，又是直觉。
注意拓扑排序出来的第一个项一定是开始符号，而开始符号的直接后缀已经得到了，间接后缀需要手工添加输入结束符。后面的处理就是不停的迭代。
下面是代码。
#include "decl_tackle.h"
typedef struct _first_graph_node
{
int first_symbol;//代表当前文法符号的某个产生式的第一个节点
struct* _first_graph_node next;
}first_graph_node,*pfirst_graph_node;//这里可以当作邻接表来使用
typedef struct _end_graph_node
{
int symbol_head;//代表以当前文法符号为生成式结尾符号的产生式头部符号
struct _end_graph_node* next;
}end_graph_node,pend_graph_node;//这里也是当作邻接表串联起来
int** first_graph_set;//first集
int** follow_graph_set;//follow集
pfirst_graph_node** first_graph;//这里是整个图的邻接表的开始节点
pend_graph_node** end_graph;//这里是整个图的邻接表的开始节点
int number_edge_first=;//记录开始图里面有多少条边
int number_edge_end=;//记录结束图里面有多少条边
//上面两个变量都是为了拓扑排序使用的
//注意这里是间接后缀而不是直接后缀，直接后缀的处理我们在第二遍遍历图的时候处理
//而间接后缀处理需要在直接后缀处理的基础上执行
//而直接后缀处理需要在前缀处理的基础上执行，因此我们需要三趟遍历
void add_first_edge(int index_from,int index_to)//添加一条边到前缀引用图中
{
pfirst_graph_node temp_node_add,temp_node;
if((*(*(first_graph_set+index_from)+index_to)!=))//如果这个符号还没有添加
{
temp_node=*(first_graph+index_from);
temp_node_add=malloc(sizeof(struct _first_graph_node));
temp_node_add->first_symbol=index_to;
temp_node_add->next=temp_node;
*(first_graph+index_from)=temp_node_add;//添加到邻接表
*(*(first_graph_set+index_from)+index_to)=;//标记为已经添加过了
number_edge_first++;
}
}
void add_end_edge(int index_from,int index_to)//添加一条边到后缀引用图中
{
pend_graph_node temp_node_add,temp_node;
if((*(*(end_graph_set+index_from)+index_to)!=))//如果这个符号还没有添加
{
temp_node=*(end_graph+index_from);
temp_node_add=malloc(sizeof(struct _end_graph_node));
temp_node_add->symbol_head=index_to;
temp_node_add->next=temp_node;
*(end_graph+index_from)=temp_node_add;//添加到邻接表
*(*(end_graph_set+index_from)+index_to)=;//标记为已经添加过了
number_edge_end++;
}
} void generate_graph(void)//生成first集合,利用数组来表示
//注意这个函数调用是在反转链表之后的
{
int for_i,for_j;
decl_node temp_decl_node;
int* temp_set;
phrase* temp_phrase;
pdecl_edge temp_decl_edge;
first_graph_set=malloc(sizeof(int)*(node_index+));
end_graph_set=malloc(sizeof(int)*(node_index+));
for(for_i=;for_i<node_size+;for_i++)
{
temp_set=malloc(sizeof(int)*(node_index+));
for(for_j=;for_j<node_index+;for_j++)
{
temp_set[for_j]=;
}
first_graph_set[for_i]=temp_set;
temp_set=malloc(sizeof(int)*(node_index+));
for(for_j=;for_j<node_index+;for_j++)
{
temp_set[for_j]=;
}
end_graph_set[for_i]=temp_set;
}//初始化所有的矩阵
first_graph=malloc(sizeof(struct _first_graph_node*)*(node_index+));//因为这里考虑了偏移量和结束符
end_graph=malloc(sizeof(struct _end_graph_node*)*(node_index+));//因为这里考虑了偏移量和结束符
for(for_i=;for_i<node_index+;for_i++)
{
first_graph[for_i]=NULL;
end_graph[for_i]=NULL;
}//初始化为空，省得犯以前的错误
//现在开始建立这两个图
for(for_i=;for_i<=node_index;for_i++)
{
temp_decl_node=decl_node_table[for_i];
temp_phrase=temp_decl_node->phrase_link;
while(temp_phrase!=NULL)
{
temp_edge=temp_phrase->begin_of_phrase;
if(temp_edge->node_of_dest!=for_i)//对于左递归进行忽略
{
add_first_edge(temp_edge->node_of_dest,for_i);//添加一条边到开始图中
}
while(temp_edge->next!=NULL)
{
temp_edge=temp_edge->next;//寻找到最后一个节点
}
if(temp_edge->node_of_dest!=for_i)//对于右递归进行忽略
{
add_end_edge(for_i,temp_edge->node_of_dest);//添加到后缀引用图中
}
temp_phrase=temp_phrase->next;
}//对于有产生式的文法单元，处理所有的产生式
}//所有文法单元处理完毕
}//前缀引用图和后缀引用图处理完毕 void generate_first_set(void)//对于引用图进行拓扑排序，然后按照拓扑排序来生成first集合
{
//first矩阵里面真正有意义的是那些终结文法符号所占据的位，非终结文法符号没啥意思
int number_of_edge;
int begin_stack_pointer;
int* begin_stack;
int end_stack_pointer;
int* end_stack;
int* temp_row,temp_row_add;//用来遍历矩阵的变量
pfirst_graph_node temp_node;
int* already_out_stack;//代表已经处理过了，已经出栈
int for_i,for_j;
already_out_stack=malloc(sizeof(int)*(node_index+));
for(for_i=;for_i<=node_index+;for_i++)
{
already_out_stack[for_i]=;
}//初始化
begin_stack=malloc(sizeof(int)*(node_index+));//多申请几个又不会怀孕
end_stack=malloc(sizeof(int)*(node_index+));
begin_stack_pointer=end_stack_pointer=;
number_of_edge=number_edge_first;
while(number_of_edge>)//只要还有一条边没有处理
{
for_i=;
while(first_graph[for_i]==NULL)
{
for_i++;
}//找到一个还有边存在的点
begin_stack_pointer++;
begin_stack[begin_stack_pointer]=for_i;
while(begin_stack_pointer>)//好像写的有点问题
{
temp_node=first_graph[begin_stack[begin_stack_pointer]];
if(temp_node!=NULL)//如果栈顶的点还有边
{
if(already_out_stack[temp_node->symbol_head]==)//如果这个点已经处理过了
{
first_graph[begin_stack[begin_stack_pointer]]=temp_node->next;//将这条边摘掉
number_of_edge--;
free(temp_node);
}
else//如果还没处理，那就直接入栈
{
begin_stack_pointer++;
begin_stack[begin_stack_pointer]=temp_node->symbol;
}
}
else//如果没有边，则需要考虑是不是最后一个点
{ if(begin_stack_pointer>)//如果不是栈底
{
end_stack_pointer++;
end_stack[end_stack_pointer]=begin_stack[begin_stack_pointer];//换栈
already_out_stack[begin_stack[begin_stack_pointer]]=;//表示已经处理完了
begin_stack_pointer--;
temp_node=first_graph[begin_stack[begin_stack_pointer]];
number_of_edge--;
first_graph[begin_stack[begin_stack_pointer]]=temp_node->next;//把这条边摘除
free(temp);//出栈
}
else//如果这是栈底
{
begin_stack_pointer=;//直接设置为栈空，不需要另外的措施
}
}
}//一直循环到当前节点可达的节点都被处理了
}//所有的边都处理完毕了
end_stack_pointer++;
end_stack[end_stack_pointer]=begin_stack[];//别忘了最后一个节点
already_out_stack[begin_stack[]]=;
//现在按照栈里面的顺序来处理位图
while(end_stack_pointer>)
{
temp_row=first_graph+end_stack[end_stack_pointer];
if(decl_node_table[end_stack[end_stack_pointer]].phrase_link!=NULL)//如果当前的是非终结文法符号
{
for(for_i=;for_i<=node_index;for_i++)
{
if(decl_node_table[temp_row[for_i]].phrase_link!=NULL)//如果引用的是一个非终结符，则开始合并终结符号
{
temp_row_add=first_graph+temp_row[for_i];
for(for_j=;for_j<node_index;for_j++)
{
temp_row[for_j]=temp_row[for_j]|temp_row_add[for_j];
//这里我就不去判断是不是终结文法符号了，因为我们保证了这里是一个拓扑排序
}
}
else
{
//对应终结符的时候，则不需要处理
}
}//搜索完成
end_stack_pointer--;
}
else//对于终结文法符号，在自己所在的位标注为1
{
temp_row[end_stack[end_stack_pointer]]=;
end_stack_pointer--;
}
}//堆栈中的点都处理完成
free(begin_stack);
free(end_stack);
free(already_out_stack);
//释放内存的是好孩子
}//前缀集合处理完成
//现在开始处理后缀集合
//下面这个函数来处理直接后缀
void direct_end(void)
{
int* before_row;
int* after_row;
pdecl_edge before_edge,after_edge;
phrase* current_phrase;
int for_i,for_j;
for(for_i=;for_i<node_index;for_i++)
{
current_phrase=decl_node_table[for_i].phrase_link
if(current_phrase!=NULL)//如果这里有生成式 ,则进行处理
{
before_edge=current_phrase->begin_of_phrase;
after_edge=before_edge->next;
while(after_edge!=NULL)//这个不是空的，则我们需要去处理一个直接后缀
{
before_row=follow_graph_set[before_edge->node_of_dest];
if(decl_node_table[after_edge->node_of_dest].phrase_link!=NULL)//如果不是终结文法符号
{
after_row=first_graph_set[after_edge->node_of_dest];//取出后面文法符号的first集合
for(for_j=;for_j<=node_index;for_j++)//因为是直接后缀，所以先不考虑输入终结符
{
before_row[for_j]=before_row[for_j]|after_row[for_j];//取并集
}
//并集处理完成
}
else
{
before_row[after_edge->node_of_dest]=;//将这一位置为1就行了
}
before_edge=after_edge;
after_edge=after_edge->next;
}//当前产生式处理完成
current_phrase=current_phrase->next;//处理下一个产生式
}//当前产生式头的所有产生式处理完成
}//处理下一个产生式头
//所有的产生式处理完毕
}//直接后缀处理完毕
void indirect_follow(int begin_node_index )
{
//这里又需要走一遍拓扑排序
//注意这趟处理的时候需要考虑输入终结符号
//由于开始符号可以生成任何符号，所以在拓扑排序完成之后，处于栈顶的一般是开始符号
//注意这只是一般情况下，我们并未用理论来证实这个结论，所以还是老老实实的先找到开始符号吧
//这个我们采用参数传递的方法
*(follow_graph_set[begin_node_index]+node_index+)=;//将输入结束符作为开始符号的后缀符号
//下面的内容基本就是复制前面生成first集合的代码
int number_of_edge;
int begin_stack_pointer;
int* begin_stack;
int end_stack_pointer;
int* end_stack;
int* temp_row,temp_row_add;//用来遍历矩阵的变量
pend_graph_node temp_node;//这里改变了节点类型
int* already_out_stack;//代表已经处理过了，已经出栈
int for_i,for_j;
already_out_stack=malloc(sizeof(int)*(node_index+));
for(for_i=;for_i<=node_index+;for_i++)
{
already_out_stack[for_i]=;
}//初始化
begin_stack=malloc(sizeof(int)*(node_index+));//多申请几个又不会怀孕
end_stack=malloc(sizeof(int)*(node_index+));
begin_stack_pointer=end_stack_pointer=;
number_of_edge=number_edge_end;
while(number_of_edge>)//只要还有一条边没有处理
{
for_i=;
while(first_graph[for_i]==NULL)
{
for_i++;
}//找到一个还有边存在的点
begin_stack_pointer++;
begin_stack[begin_stack_pointer]=for_i;
while(begin_stack_pointer>)//好像写的有点问题
{
temp_node=end_graph[begin_stack[begin_stack_pointer]];
if(temp_node!=NULL)//如果栈顶的点还有边
{
if(already_out_stack[temp_node->symbol_head]==)//如果这个点已经处理过了
{
end_graph[begin_stack[begin_stack_pointer]]=temp_node->next;//将这条边摘掉
number_of_edge--;
free(temp_node);
}
else//如果还没处理，那就直接入栈
{
begin_stack_pointer++;
begin_stack[begin_stack_pointer]=temp_node->symbol;
}
}
else//如果没有边，则需要考虑是不是最后一个点
{ if(begin_stack_pointer>)//如果不是栈底
{
end_stack_pointer++;
end_stack[end_stack_pointer]=begin_stack[begin_stack_pointer];//换栈
already_out_stack[begin_stack[begin_stack_pointer]]=;//表示已经处理完了
begin_stack_pointer--;
temp_node=first_graph[begin_stack[begin_stack_pointer]];
number_of_edge--;
first_graph[begin_stack[begin_stack_pointer]]=temp_node->next;//把这条边摘除
free(temp);//出栈
}
else//如果这是栈底
{
begin_stack_pointer=;//直接设置为栈空，不需要另外的措施
}
}
}//一直循环到当前节点可达的节点都被处理了
}//所有的边都处理完毕了
end_stack_pointer++;
end_stack[end_stack_pointer]=begin_stack[];//别忘了最后一个节点
already_out_stack[begin_stack[]]=;
//现在按照栈里面的顺序来处理位图
while(end_stack_pointer>)
{
temp_row=follow_graph_set+end_stack[end_stack_pointer];//
for(for_i=;for_i<=node_index;for_i++)
{
if(temp_row[for_i]==&&decl_node_table[for_i].phrase_link!=NULL)//如果这里依赖一个非终结符
{
temp_row_add=follow_graph_set+for_i;
for(for_j=;for_j<=node_index+;for_j++)//注意这里需要考虑输入终结符
{
temp_row[for_j]=temp_row[for_j]|temp_row_add[for_j];
}//合并完成
}//此符号处理完成
}//所有的处理完成
end_stack_pointer--;//堆栈减1
}//堆栈空
//现在所有的后缀信息已经处理完毕
free(begin_stack);
free(end_stack);
free(already_out_stack);
//释放内存的是好孩子
}//