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

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

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;
}

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


person mastercooler6    schedule 11.02.2019    source источник
comment
И если мне нужен стек, зачем? Когда это уже работает для меня просто отлично.   -  person mastercooler6    schedule 11.02.2019
comment
Нет. У вас уже есть стек: стек вызовов.   -  person user207421    schedule 11.02.2019
comment
@user207421 user207421 о, понятно. Так зачем кому-то на самом деле создавать стек, как на фото?   -  person mastercooler6    schedule 11.02.2019
comment
Выдержка из книги не о рекурсивном разборе спуска. Речь идет о разборе сверху вниз и, в частности, о написании анализатора LL(1) через КПК, для которого требуется явный стек.   -  person user207421    schedule 11.02.2019


Ответы (1)


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

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

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

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

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

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

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

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

person rici    schedule 11.02.2019