StackoverflowException, возникающее при попытке проанализировать глубоко вложенные группы в регулярных выражениях

Question

Я пытаюсь написать синтаксический анализатор для регулярных выражений, который, я уверен, может справиться почти со всем, что ему брошено (например, он может правильно проанализировать это чудовище регулярного выражения: http://www.ex -parrot.com /~pdw/Mail-RFC822-Address.html без проблем.). Тем не менее, когда мой синтаксический анализатор генерирует исключение StackoverflowException, он имеет дело с чем-то вроде следующего (обратите внимание, что я знаю, что это конкретное регулярное выражение ничего не делает, но это самый простой пример) как я могу переписать свой код для удаления рекурсии?:

public static String generateOverflowingRegex()
{
    StringBuilder sb = new StringBuilder();
    IntStream.range(0, 1000).forEach(i -> sb.append("("));
    sb.append("[a-z]+");
    IntStream.range(0, 1000).forEach(i -> sb.append(")"));
    return sb.toString();
}

Я исследовал рекурсивный прыжок на батуте, однако считаю, что это подходит только для хвостовой рекурсии, которая не применима ни к одному из моих рекурсивных методов. Я также думал о преобразовании в стек в куче, однако то, как я думаю о проблеме, приводит к тому, что читаемость кода не существует.

Ниже приведен фрагмент полного кода, #tryParse () является основной точкой входа.

с точки зрения развертывания #setupParseState () в try parse, это довольно просто, но это становится намного сложнее при вводе #doParse (), так как он вызывает методы, такие как #isOr (), который вызывает #setupParseState () .

    public State tryParse(String pattern) throws InterruptedException
    {
        State state = new State();
        state.setSource(pattern);
        setupParseState("or", state);
        return state;
    }

    protected boolean setupParseState(String typeToCheck, State state) throws InterruptedException
    {
        //init new parse state
        state.openNode(typeToCheck);
        state.getCurrentNode().setStartIndex(state.getIndex());
        if (doParse(typeToCheck, state))
        {
            state.getCurrentNode().setEndIndex(state.getIndex());
            //set current node as complete set parent node as current node and return to parent state.
            state.closeNode();
            return true;
        }
        //parsing failed so drop current state and return to previous state
        state.discardNode();
        return false;
    }

    protected boolean doParse(String name, State state) throws InterruptedException
    {
        int tempIndex = state.getIndex();
        boolean sucess = false;
        switch (name)
        {
            case "or":
                if (isOr(state))
                {
                    sucess = true;
                    break;
                }
                break;
            case "sequence":
                if (iSequence(state))
                {
                    sucess = true;
                    break;
                }
                break;
            case "term":
                if (isTerm(state))
                {
                    sucess = true;
                    break;
                }
                break;
        }
        if (!sucess)
        {
            state.index = tempIndex;
        }
        return sucess;
    }

    protected boolean isOr(State state) throws InterruptedException
    {
        state.setNodeValue("OR: match either of the following");
        while (true)
        {
            if (!setupParseState("sequence", state))
            {
                return false;
            }
            Character temp = state.getCurrentState();
            if (temp != null && temp.charValue() == '|') state.advanceState();
            else break;
        }
        return true;
    }

    protected boolean iSequence(State state) throws InterruptedException
    {
        state.setNodeValue("Sequence: match all of the following in order");
        boolean isEmpty = true;
        while (true)
        {
            if (!setupParseState("term", state)) break;
            isEmpty = false;
        }
        if (!isEmpty)
        {
            return true;
        }
        if (state.getCurrentState() == null || state.getCurrentState().charValue() == '|' || state.getCurrentState().charValue() == ')')
        {
            state.setNodeValue("Empty");
            return true;
        }
        return false;
    }

    protected boolean isTerm(State state) throws InterruptedException
    {
        if (setupParseState("assertion", state))
        {
            return true;
        }
        if (setupParseState("quantatom", state))
        {
            return true;
        }
        return false;
    }