Рекурсивный спуск против рекурсивного разбора - PullRequest
Новая
       21

Рекурсивный спуск против рекурсивного разбора

0 голосов
/ 13 ноября 2011

Если я пишу свой собственный парсер, как я могу узнать, пишу ли я рекурсивный синтаксический анализатор восхождения?Я определенно заинтересован в сложности O (n) синтаксического анализа LALR (плюс у меня уже есть грамматика LALR) и не хочу позже узнать, что я написал вместо этого анализатор LL.

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

Если вы берете код для относительно простого правила, например 

name_or_qualified_name = identifier *('.' identifier);

который я перевел на 

std::vector<std::wstring> RecursiveParseNameOrQualifiedName(Iterator& begin, Iterator end) {
    std::vector<std::wstring> retval;
    retval.push_back(begin->Codepoints);
    CheckedIncrement(begin, end); // The only place that can legitimately expect end of input is namespace contents.
    while(begin->type == Wide::Lexer::TokenType::Dot) {
        CheckedIncrement(begin, end);
        if (begin->type != Wide::Lexer::TokenType::Identifier)
            Wide::ParserExceptionBuilder(*begin) << L"Expected 'identifier' after '.'";
        retval.push_back(begin->Codepoints);
    }
    return retval;
}

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

Редактировать: Извините, плохой пример.Как насчет такого: 

void RecursiveParseUsing(Iterator& begin, Iterator end, Wide::Parser::NamespaceAST* current_namespace) {
    auto new_using = std::unique_ptr<Wide::Parser::UsingAST>( new Wide::Parser::UsingAST() );
    // expect "begin" to point to a using
    CheckedIncrement(begin, end);
    // Must be an identifier, at least
    if (begin->type != Wide::Lexer::TokenType::Identifier)
        Wide::ParserExceptionBuilder(*begin) << L"Expected 'identifier' after 'using'";
    CheckedIncrement(begin, end);
    switch(begin->type) {
    case Wide::Lexer::TokenType::Dot: {
        begin--; // back to identifier
        new_using->original_name = RecursiveParseNameOrQualifiedName(begin, end);
        current_namespace->unnamed_contents.push_back(std::move(new_using));
        break; }
    case Wide::Lexer::TokenType::Equals: {
        begin--; // back to Identifier
        new_using->new_name = begin->Codepoints;
        begin++; // Back to equals
        begin++; // The token ahead of equals- should be "identifier"
        new_using->original_name = RecursiveParseNameOrQualifiedName(begin, end); // The only valid next production
        // this should be left at the one past the name
        current_namespace->contents[new_using->new_name] = std::move(new_using);
        break; }
    case Wide::Lexer::TokenType::Semicolon: {
        begin--; // Identifier
        new_using->original_name.push_back(begin->Codepoints);
        begin++; // Semicolon
        current_namespace->unnamed_contents.push_back(std::move(new_using));
        break; }
    default:
        Wide::ParserExceptionBuilder(*begin) << L"Expected '.', '=' or ';' after 'identifier' when parsing 'using'.";
    }
    if (begin->type != Wide::Lexer::TokenType::Semicolon)
        Wide::ParserExceptionBuilder(*begin) << L"Expected ';' after 'identifier'";
    CheckedIncrement(begin, end); // One-past-the-end
}

1 Ответ

3 голосов
/ 13 ноября 2011

И LL, и LALR имеют значение O (n), поэтому это не имеет значения.

Однако не все парсеры рекурсивного спуска являются LL.Те, которые не используют какую-либо форму возврата - пробуют одно производство, а когда оно не работает, пробуют другое, пока все возможные производства не будут исчерпаны или не будет найден успешный анализ.Нетрудно заметить, что вы делаете это: -)

Относительно того, как вы знаете, создаете ли вы парсер LL или LALR - вы узнаете это, зная, какой метод построения вы используете.

Отредактировано, чтобы добавить: Одной из отличительных особенностей рекурсивного спуска и рекурсивного подъема является роль процедур.При рекурсивном спуске у вас есть процедура для каждого нетерминала.В рекурсивном восхождении у вас есть процедура для каждого состояния LR.Чтобы получить последнее, вам в значительной степени нужно заранее создать автомат LR (если вы не делали это так часто, что вы можете сделать это на лету - но в этом случае вы не будете задавать этот вопрос).Ваш первый пример кода выглядит как рекурсивный спуск;но вы не сказали нам, как второй пример кода относится к вашей грамматике, поэтому там трудно сказать.

...