实现有限状态机：运行-时间错误，为什么？

Question

我知道有可用的 FSA 实现，但我很想知道出于学习目的我的错误在哪里。运行时间错误通常是在使用 >>.

从输入文件读取时

The error is 'exception thrown: exercise.exe has triggered a breakpoint'.

问过同学，他们也说不出错误。

输入：

第一行：状态数
第 2 行：# 开始状态
第3行：接受状态数
接下来的几行：#s of accept states
下一行：转换函数数
接下来几行：转换函数，形式为from to value，其中from and 到是对应状态，值是符号
下一行：我们需要检查验收的字符串数
接下来几行：字符串本身

我的代码是：

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string>
using namespace std;

ifstream I("input.txt");
ofstream O("output.txt");

struct arrow {
    int destination=-1;
    char c='x';
    arrow() {}
    arrow(char val, int to) {
        destination = to;
        c = val;
    }
};
struct node {
    int name=-1;
    bool accept=false;
    int ars=0;
    arrow* arrows=new arrow;
    node() {}
    node(bool isAccept, int whatName) {
        accept = isAccept;
        name = whatName;
    }
};
class fsa {
    int start;
    node* states=new node;
public:
    fsa(int n, int entrSt, int acceptSts) {
        this->start=entrSt;
        int* tempForAcceptStates = new int[acceptSts];
        for (int i = 0; i < acceptSts; i++) I >> tempForAcceptStates[i];
        for (int i = 0; i < n; i++) { 
            int wasNodeCreated = -1;
            for (int j = 0; j < acceptSts; j++) {
                if (tempForAcceptStates[j] == i) wasNodeCreated = i;
            }
            if (wasNodeCreated >= 0) states[i] = node(true, wasNodeCreated);
            else { states[i] = node(false, i); }
        }
        int transitions;
        I >> transitions;
        for (int i = 0; i < transitions; i++) {
            int from, to;
            char val;
            I >> from >> to >> val;
            int temp = states[from].ars;
            this->states[from].arrows[temp] = arrow(val, to);
            states[from].ars++;
        }
    }
     bool isRecognized() {
         string str;
         getline(I, str);
         bool wasSymbolFound=false;
         int currentNode = this->start;
         for (int i = 0; i < str.length(); i++) {
             int howManyArsCurrentNodeHas = states[currentNode].ars;
             for (int j = 0; j < howManyArsCurrentNodeHas; j++) {
                wasSymbolFound = false;
                 if (states[currentNode].arrows[j].c == str[i]) {
                     currentNode = states[currentNode].arrows[j].destination;
                     wasSymbolFound = true;
                }
                 if (wasSymbolFound==true) break;
             }
             if (wasSymbolFound == false) return false;
         }
         if (states[currentNode].accept==true) return true; else return false;
     }
};

void main() {
    int n, entrSt, acceptSts;
    I >> n >> entrSt >> acceptSts;
    fsa A(n, entrSt, acceptSts);
    int words;
    I >> words;
    for (int i = 0; i < words; i++) {
        if (A.isRecognized()) O << "YES\n"; else O << "NO\n";
    }
    }

示例输入：

3
0
1
0
6
0 1 a
1 0 b
0 2 b
1 2 a
2 2 a
2 2 b
3
ab
aaa
abababab

对应的期望输出：

YES
NO 
YES

Answer 1

请添加错误信息，如果我们不知道哪里出了问题，很难帮助您。

但我认为，你的问题出在fsa::states的定义上。你把它定义为new node;，它是指向堆上一个node的指针，但是你想在堆上创建一个n node的数组。稍后写入 n[i] 会尝试访问一些您尚未分配的内存，因此您会遇到访问冲突。

不要在 C++ 中使用 C 风格的动态数组 (new [])，而是使用 std::vector。

Answer 2

请记住，您的文件可能找不到，或者文件中的某些格式错误可能会导致读取错误。

不幸的是，您没有错误检查，使您面临 UB 的风险，例如您认为从文件中正确读取的变量具有随机值。例如，在我的系统上，在没有 input.txt 文件的情况下尝试您的代码会导致发生内存分配异常，因为 acceptSts 是一个巨大的随机数。

现在更详细地了解正在发生的事情，即使使用正确一致的输入文件作为示例，您的代码也注定会失败。

在 fsa 构造函数中，您使用 new node 初始化 states 成员，因此指向单个节点的指针。稍后您分配或读取索引值，例如states[i]、states[from]、states[temp]。但是你从来没有分配过一个节点数组。因此，对于每个非零索引，您都会得到 UB，这可能会导致内存损坏、程序突然中止、任何其他奇怪的行为，或者根本没有任何症状。

您可以更正此问题，例如，通过在构造函数中初始化状态，因为有限状态是已知的：

    states = new node[n];

不幸的是，您与 arrow 有同样的问题：

 states[from].arrows[temp] = arrow(val, to);

不仅 arrows 在 node 中使用指向单个箭头的指针初始化，导致与前面解释的相同的问题。使用原始分配解决这个问题更为复杂。所以我的建议是，不要使用 new 分配数组，如果允许的话，请尝试使用 vector。向量可以动态增长并且不易出错。

不相关：

使用全局 I 和 O 并在 class 方法中使用它会创建一个隐藏的耦合，这使得程序难以调试。更好的方法是将这些 fstream 对象定义为本地对象（例如 main() 的对象），并将它们作为 istream 和 ostream 引用传递给需要它们的函数。
如果你在构造函数中分配了一些指针，你也应该在析构函数中删除它，否则你可能会泄漏内存。如果你用 new[] 分配，那么 delete[]。

实现有限状态机：运行-时间错误，为什么？

Implementing finite-state machine: run-time error, why?

c++

state-machine

finite-automata