Нужно ли использовать стек для реализации парсера рекурсивного спуска?

Question

Я запустил свой парсер рекурсивного спуска, и пока он работает просто отлично.Возвращает «ПРИНЯТЬ» или «ОТКАЗ» после анализа ввода.Но я вижу в Интернете и в другом учебнике, что они используют «КПК для анализа сверху вниз».Итак, я просто хочу получить подтверждение, что это просто ДРУГОЙ способ кодирования синтаксического анализатора, а не ПУТЬ.Мой парсер выглядит так:

public class Parser {

private int n = 0;
private Tokens token = Main.TokenList.get(n);

public Parser() {
        Boolean bool = parse_Program();
        if (bool){
            System.out.println("ACCEPT");
        }else System.out.println("REJECT");

}

Boolean parse_Program(){
    if (!parse_DeclarationList()){
         return false;
    }
    return true;
}

private boolean parse_DeclarationList() {
    if (!parse_Declaration()){
        return false;
    }
    if(!parse_DeclarationListPrime()){
          return false;
    }
    return true;
}

private boolean parse_DeclarationListPrime() {
        if (token.getContents().equals("int") || token.getContents().equals("void") || token.getContents().equals("float")) {
            if (!parse_Declaration()) {
                return false;
            }else return true;
        }else if (token.getContents().equals("$")){
            return true;
        }

    return false;
}


private boolean parse_Declaration() {
    if (!parse_TypeSpecifier()){
        return false;
    }
    if (token.getType().equals("ID")){
        Accept();
    }else return false;

    if (!parse_DDD()){
        return false;
    }
    return true;
}

private boolean parse_DDD() {
    if (token.getContents().equals("(")){
        Accept();
        if(!parse_params()){
            return false;
        }
        if (token.getContents().equals(")")){
            Accept();
            if (!parse_compoundStmt()){
                return false;
            }else return true;
        }
    }else if (token.getContents().equals(";") || token.getContents().equals("[")){
        if (!parse_varDeclarationPrime()){
            return false;
        }else return true;
    }
    return false;
}

private boolean parse_compoundStmt() {
    if (token.getContents().equals("{")){
        Accept();
        if (!parse_localDeclarations()){
            return false;
        }
        if (token.getContents().equals("}")){
            Accept();
            return true;
        }
    }
    return false;
}

private boolean parse_localDeclarations() {
    if (!parse_localDeclarationsPrime()){
        return false;
    }else return true;
}

private boolean parse_localDeclarationsPrime() {
    if (!parse_varDeclaration()){
        return false;
    }
    return true;
}

private boolean parse_params() {
   if (token.getContents().equals("int") || token.getContents().equals("void") || token.getContents().equals("float")) {
        if (getNextToken().getContents().equals(")") && token.getContents().equals("void")) {
            Accept();
            return true;
        } else {
            if (!parse_paramList()) {
                return false;
            } else return true;
        }
    }
    return false;
}

private Tokens getNextToken() {
    Tokens nextToken = Main.TokenList.get(n+1);
    return nextToken;
}

private boolean parse_paramList() {
    if (!parse_param()){
        return false;
    }
    if (!parse_paramListPrime()){
        return false;
    }
    return true;
}

private boolean parse_paramListPrime() {
    if (token.getContents().equals(",")){
        Accept();
        if (!parse_param()){
            return false;
        }
        if (!parse_paramListPrime()){
            return false;
        }
        return true;
    }else if (token.getContents().equals(")")){
        return true;
    }
    return false;
}


private boolean parse_param() {
    if (token.getContents().equals("int") || token.getContents().equals("void") || token.getContents().equals("float")){
        Accept();
        if (token.getType().equals("ID")){
            Accept();
            if (!parse_paramPrime()){
                return false;
            }else return true;
        }
    }
    return false;
}

private boolean parse_paramPrime() {
    if (token.getContents().equals("[")){
        Accept();
        if (token.getContents().equals("]")){
            Accept();
            return true;
        }
    }else if (token.getContents().equals(")")){
        return true;
    }
    return false;
}

private boolean parse_varDeclaration() {
    if (!parse_TypeSpecifier()){
        return false;
    }
    if (token.getType().equals("ID")){
        Accept();
    }else
        return false;
    if (!parse_varDeclarationPrime()){
        return false;
    }
    return true;
}

private boolean parse_varDeclarationPrime() {
    if (token.getContents().equals(";")){
        Accept();
        return true;
    }else if (token.getContents().equals("[")){
        Accept();
        if (token.getType().equals("NUM")){
            Accept();
            if (token.getContents().equals("]")){
                Accept();
                if (token.getContents().equals(";")){
                    Accept();
                    return true;
                }
            }
        }
    }
    return false;
}

private void Accept() {
    try {
        if ((n + 1) <= Main.TokenList.size() - 1) {
            token = Main.TokenList.get(++n);
        } else {
            token.setContents("$");
        }
    }catch (Exception e){

    }
}

private boolean parse_TypeSpecifier() {
    if (token.getContents().equals("int") || token.getContents().equals("float") || token.getContents().equals("void")){
        Accept();
        return true;
    }
    return false;
}

Это из учебника:

Answer 1

Разбор сверху вниз требует некоторого стека синтаксического анализатора.Смысл разбора рекурсивного спуска заключается в использовании стека вызовов в качестве стека синтаксического анализатора.Поэтому вы должны рассматривать алгоритм в вашем учебнике как альтернативу рекурсивному спуску.

Рекурсивное спуск является популярным решением для синтаксического анализа, но оно может быть проблематичным в языке, подобном C (или C ++), который не обнаруживаетпереполнение стека (или не надежно обнаруживает его).В этом случае вы, вероятно, захотите использовать выделенный стек анализатора для производственного анализатора, особенно если:

• вы запускаете анализатор в многопоточном приложении (чтобы стеки были небольшими);

• все, что вы анализируете, должно иметь глубокое вложение (возможно, это дендритная структура данных);

• вы анализируете непроверенный ввод, и выбеспокоятся о том, что злоумышленники предоставляют слишком вложенные данные;

• вы недостаточно усердно работали, чтобы минимизировать размер стекового фрейма, возможно, из-за аллергии на динамическое распределение памяти.

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

В качестве альтернативы, вы можете использовать генератор синтаксических анализаторов, который создает парсеры сконтролируемый размер стека.