c++ - 为什么要实现有限状态机 : run-time error,？

Question

我知道有可用的 FSA 实现，但我很想知道出于学习目的我的错误在哪里。运行时错误通常发生在使用 >> 从输入文件读取时。

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

我问过我的同学，但他们也无法确定错误。

输入:

• 第一行:状态数

• 第二行:开始状态#

• 第三行:接受状态数

• 接下来的几行:接受状态的数量

• 下一行:转换函数的数量

• 接下来几行:转换函数，形式为从到值，其中from和to是相应的状态，< em>值是一个符号

• 下一行:我们需要检查是否接受的字符串数量

• 接下来的几行:字符串本身

我的代码是:

#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

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

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

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

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

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

    states = new node[n];

不幸的是，您对 arrow 也有同样的问题:

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

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

不相关:

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