如何使用此评估(BFS)避免堆栈溢出

Question

我已经构造了一个NFA，我正在运行这个方法来评估机器，看看一个表达式是否有效。这适用于小的正则表达式，但是当我的正则表达式的大小以及NFA的大小变得太大时，这个搜索会向我抛出一个堆栈溢出。我很确定这是因为我已经实现了一个BFS，正在使用递归，并且可能没有很好地处理我的基本案例。

这个方法接受一个表达式和一个节点（从NFA的起始节点开始）。首先，它检查表达式的长度是否为零，如果我在接受节点（节点上的布尔值）中，然后返回true。如果表达式长度为零，但当前节点不是accept节点，则返回false。

如果这两个都不求值，那么我将得到当前节点可以使用“e”（epsilon）转换到达的所有节点的列表，并求值它们。

如果没有“E”节点，那么我从输入表达式中删除第一个字符，生成表达式的一个缩短的子字符串（删除表达式的前部），然后使用删除的字符和缩减的表达式查找该节点可以到达的节点列表。

如果这两个都不命中，则返回false

一个基本的正则表达式是(ab)*A，一个求值表达式的例子是aaaa，它在每一次求值时都被简化，AAAA->AAA->AA->A->

    private boolean evaluate(autoNode node, String expression)
{

    if(expression.length()==0 && node.getAccept())
    {
        return true;
    }
    else if(expression.length()==0 && !node.getAccept())
    {
        return false;
    }

    String evalExp = expression.charAt(0)+""; //The first character in the expression
    String redExp = expression.substring(1, expression.length()); 

    //for each epsilon transition, evaluate it
    if(node.getTransSet().contains("e"))
    {
        //if this node has an "e" transition then...
        ArrayList<autoNode> EpsilonTransMap = node.getPathMap("e");
        //The above ArrayList is a list of all the nodes that this node can reach
        //using the "e" / epsilon transition
        for(autoNode nodes : EpsilonTransMap)
        {               
            if(evaluate(nodes, expression))
            {
                return true;
            }
        }
    }
    //for each transition on that key evaluate it
    if(node.getTransSet().contains(evalExp))
    {
        //if this node has a transition from the front of the expression then...
        ArrayList<autoNode> TransitionKeyMap = node.getPathMap(evalExp);
        //The above ArrayList is a list of all the nodes that this node can reach
        //on a transition equal to the "key" removed from the front of the expression String
        for(autoNode nodes : TransitionKeyMap)
        {
            if(evaluate(nodes, redExp))
            {
                return true;
            }
        }
    }

    return false;
}

我意识到我可能因为使用bfs搜索而不是DFS而导致了自己的问题。我想知道是否有人可以帮助我修复这一点，并避免堆栈溢出，使太多的事情同时进行。因为虽然(ab)*A可以很好地评估...

((aa)+(bb)+(cc)+)(ba)(ca)

创建一个相当大的NFA，在计算“a”时导致堆栈溢出

任何不会导致我完全放弃这个方法的东西都是很好的，也是很感激的。

Answer 1

其实这里没有DFS或BFS，但这并不重要。我想不能使用带有字母“e”的正则表达式也不重要。

重要的是，每当到达epsilon转换的循环时，就会出现堆栈溢出。例如：

evalue(n1,“AA”）找到从n1到n2的epsilon转换，并递归：

求值(n2，“aa”）发现从n2到n1的epsilon跃迁并递归：

评估(n1，“AA”）。如此循环，直到堆栈溢出。

你有很多方法可以解决这个问题...但是，即使您修复了它，这仍然是一个相当糟糕的评估NFA的算法--它可能会在状态数上花费指数级的时间！

编辑--所以，下面是使用伪代码进行NFA评估的正确方法：

boolean evaluate(Node nfa, String str)
{
    Set<Node> fromStates = new Set();
    fromStates.add(nfa);
    closeEpsilons(fromStates);

    for (char chr in str)
    {
        if (fromStates.size()==0)
            return false;

        //find all the states we can get to from
        //fromStates via chr

        Set<Node> toStates = new Set();
        for (Node fromState in fromStates)
        {
            //OP's code would say .getPathMap(chr) here
            for(Node toState in fromState.getTransitionTargets(chr))
            {
                if (!toStates.contains(toState))
                    toStates.add(toState);
            }
        }
        closeEpsilons(toStates);

        //process the rest of the string with the state set we just found
        fromStates = toStates;
    }

    //string is done.  see if anything accepts
    for(Node state in fromStates)
    {
        if (state.accepts())
        {
            return true;
        }
    }
    return false;
}

//expand a state set with all states is reaches via epsilons
void closeEpsilons(Set<Node> states)
{
    Queue<Node> processQueue = new Queue();
    processQueue.addAll(states);

    while(!processQueue.isEmpty())
    {
        Node fromState = processQueue.removeFirst();

        //OP's code would say "getPathMap("e") here
        for(Node toState in fromState.getEpsilonTargets())
        {
            if (!states.contains(toState))
            {
                //found a new state
                states.add(toState);
                //we'll have to search it for epsilons
                processQueue.add(toState);
            }
        }
    }
}