这个程序是找到一个NFA所有状态的epsilon闭包。我已经使用堆栈来完成此操作。当我使用 gcc 编译它并运行它 Windows 10(命令提示符(时，该程序给出了正确的输出。但是当我使用相同的编译器编译并在 Linux 中运行它时，它会导致分段错误。为此，我已经使用了任何动态内存分配。
我尝试使用 gdb 进行调试，但找不到问题。在显示转换矩阵时检测到 printf(""( 之后的分割错误。 如果有人能找到故障，那将非常有帮助。提前谢谢。
输入是从文件：nfa.txt读取的。
//states
q0 q1 q2
//input_symbols
0 1
//start_state
q0
//final_state
q2
//transitions of the form : intial_state input final_state
q0 0 q0
q0 e q1
q1 1 q1
q1 e q2
q2 2 q2
输出如下：
232 表示零转换 (Φ(，-1 表示ε。
States:
q0
q1
q2
Transitions read
232 0 1 2 -1
0 0 232 232 1
1 232 1 232 2
2 232 232 2 232
e-closure(0) : 0 1 2
e-closure(1) : 1 2
e-closure(2) : 2
请耐心等待，因为这是一个相当长的程序。
#include <stdio.h>
#include <string.h> //REMEMBER ME WHILE I'M GONE
#include <errno.h>
#include <stdlib.h>
FILE *file;
int numberOfStates = 0;
int flag = 0;
int states[20];
int j = 0;
int i = 0;
int k = 0;
char a[20];
int transitions[4][5];
int visited[10];
int MAXSIZE = 8;
int stack[8];
int top = -1;
int isempty()
{
if(top == -1)
return 1;
else
return 0;
}
int isfull()
{
if(top == MAXSIZE)
return 1;
else
return 0;
}
int pop()
{
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
}
else
printf("Could not retrieve data, Stack is empty.n");
}
int push(int data) {
if(!isfull()) {
top = top + 1;
stack[top] = data;
}
else
printf("Could not insert data, Stack is full.n");
}
int IsVisited(int edge)
{
for(int i = 0; i < 10; i++)
if(visited[edge] == 1)
return 1;
return 0;
}
void epsilon_closure(int state)
{
int e_closure[10];
for(int i = 0; i < 10; i++ )
{ e_closure[i] = -1;
visited[i] = 0;
}
push(state);
visited[state] = 1;
while(top != -1)
{
int u = pop();
j = 1;
while(j < 5)
{
//if there is an epsilon transition from the state 'u' to 'v'
if(transitions[j][0] == u && transitions[j][4] != 232) //ASCII of Φ = 232
{
if(! IsVisited(transitions[j][4]))
{
visited[transitions[j][4]] = 1;
push(transitions[j][4]);
}
}
j++;
}
}
j = 0;
for(int edge = 0; edge < 10; edge++)
{
if(visited[edge] == 1)
e_closure[j++] = edge;
}
printf("e-closure(%d) : ",state);
for (i = 0; e_closure[i] != -1; ++i)
printf("%d ", e_closure[i]);
printf("n");
}
int main()
{
file = fopen("nfa.txt","r");
if (file == NULL) {
perror("fopen");
return -1;
}
//Reading the states
while(!feof(file))
{
fscanf(file,"%s",a);
if(strcmp("//states",a) == 0)
flag = 1;
else if(strcmp("//input_symbols",a) == 0)
break;
if (flag == 1 && a[0] != '/')
{
states[i++] = a[1] - '0';
}
numberOfStates = i;
}
//Display the states of the e-NFA
printf("nStates : n");
for(i = 0; i < numberOfStates; i++ )
{
printf("q%dn",states[i]);
}
i = 1;
flag = 0;
//Reading the transition table
for(int i = 0; i < 4; i++){
for(int j = 0; j < 5; j++)
{
transitions[i][j] = 232;
}
}
while(!feof(file))
{
fgets(a,100,file);
if(a[0] == '/')
{
flag = 1;
}
if(flag == 1 && a[0] != '/')
{
j = 0;
//found a way to store the transition table in a matrix
if(a[3] == 'e')
transitions[(a[1] - '0') + 1][4] = a[6] - '0';
else
transitions[(a[1] - '0') + 1][(a[3] - '0') + 1] = a[6] - '0';
if(a[3] != 'e')
transitions[0][a[3] - '0' + 1] = a[3] - '0'; //input
else
transitions[0][4] = -1; // epsilon input
transitions[(a[1] - '0') + 1][0] = a[1] - '0'; //initial state
}
}
printf("nTransitions readn");
for(int i = 0; i < 4; i++){
for(int j = 0; j < 5; j++)
{
printf("%dt",transitions[i][j]);
}
printf("n"); //detected segmentation fault here
}
//Calling e-closure for all the states
for(k = 0; k < numberOfStates; k++)
{
epsilon_closure(states[k]);
}
return 0;
}
这里有一个错误：
int push(int data) {
if(!isfull()) {
top = top + 1;
stack[top] = data;
}
else
printf("Could not insert data, Stack is full.n");
}
如果top == MAXSIZE-1，isfull()将返回 false，则top递增以MAXSIZE并stack[MAXSIZE]分配超出界限的内容并调用 UB。没有检查完整的源代码，我可以想象分配后递增top是正确的，或者您必须更改isfull()以返回 true 如果top >= MAXSIZE-1