-1

如果我正在编写自己的自定义解析器，我怎么知道我是否正在编写递归上升解析器？我绝对对 LALR 解析的 O(n) 复杂性感兴趣（而且我已经有一个 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
}
4

1 回答 1

3

LL 和 LALR 都是 O(n)，所以没关系。

但是，并非所有递归下降解析器都是 LL。那些不使用某种形式的回溯——尝试一个产品，当它不起作用时尝试另一个，直到所有可能的产品都用尽或找到成功的解析。注意到你正在这样做并不难:-)

至于你如何知道你是在构造一个 LL 还是 LALR 解析器——你可以通过知道你正在遵循哪种构造方法来知道它。

编辑添加：递归下降和递归上升之间的一个显着特征是过程的作用。在递归下降中，每个非终结符都有一个过程。在递归上升中，每个 LR 状态都有一个过程。为了获得后者，您几乎必须事先构建 LR 自动机（除非您经常这样做，以至于您可以即时执行此操作——但在这种情况下，您不会问这个问题）。您的第一个代码示例看起来像递归下降；但是您没有告诉我们第二个代码示例与您的语法有何关系，因此很难说清楚。

于 2011-11-13T14:55:29.440 回答