如何避免使用此評估（BFS）的堆棧溢出

Question

我有我構建的NFA，並且正在運行此方法來評估計算機以查看錶達式是否有效。這適用於小的正則表達式，但是當我的正則表達式的大小以及因此我的NFA的大小變得太大時，此搜索會引發堆棧溢出。我相當肯定這是因爲我已經實現了一個BFS，我正在使用遞歸，並且可能沒有很好地處理我的基礎案例。

該方法採用表達式和節點（從NFA的開始節點開始）。首先檢查表達式的長度是否爲零，如果我處於接受節點（節點上的布爾值），則返回true。 如果表達式長度爲零，但當前節點不是接受節點，則返回false。

如果這些都沒有評估，那麼我得到當前節點可以使用「e」（ε）轉換到達的所有節點的列表，並對它們進行評估。

如果沒有「e」節點，那麼我從輸入表達式中移除第一個字符，縮小表達式的子串（移除表達式的前面），然後查找該節點的節點列表可以使用刪除的字符和減少的表達式。

如果沒有這些命中，然後我返回false

一個基本的正則表達式（A | B）*一個 和評價表述的一個例子是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引起我自己的問題。我想知道是否有人可以幫助我解決這個問題，並避免因一次發生太多事情而導致堆棧溢出。因爲儘管（A | B）*一個可以評估就好了......

（（AA）+ |（BB）+ |（CC）+）（BA）（CA）

創建相當大的NFA，在評估時會導致堆棧溢出： 「a」

任何不會導致我完全廢棄該方法的方法將非常有用。

Answer 1

那麼，你實際上沒有DFS 或 BFS在這裏，但這並不重要。我想這不是重要的，你不能使用帶有字母「e」的正則表達式。

重要的是，只要您達到epsilon轉換週期，就會發生堆棧溢出。例如：

評估（N1， 「AA」）發現的ε過渡由n1到n2，和遞歸：其中認爲從N2到n1和遞歸的ε過渡

評估（N2， 「AA」） ：

評估（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); 
      } 
     } 
    } 
}