遞歸下降vs遞歸上升解析

Question

如果我正在編寫自己的自定義解析器，如何知道是否正在編寫遞歸上升解析器？我對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 
} 

Answer 1

LL和LALR都是O（n），所以沒關係。

但是，並非所有的遞歸下降解析器都是LL。那些不使用某種形式的回溯–嘗試一個生產，當它不工作嘗試另一種生產時，直到所有可能的生產已經耗盡或發現成功的解析。這並不是很難注意到你正在這樣做:-)

至於你如何知道你是否正在構建一個LL或LALR解析器–你知道它知道你在使用哪種構造方法。

編輯補充：遞歸下降和遞歸上升之間的一個顯着特徵是過程的作用。在遞歸下降中，你有一個針對每個非終結符的過程。在遞歸上升中，每個LR狀態都有一個過程。爲了獲得後者，你幾乎必須事先構造LR自動機（除非你經常這樣做，以至於你可以在飛行中做到這一點，但在這種情況下，你不會問這個問題）。你的第一個代碼示例看起來像遞歸下降;但是你沒有告訴我們第二個代碼示例與你的語法是如何相關的，所以很難說清楚。