Descente récursive et analyse ascendante récursive

Question

Si j'écris mon propre analyseur personnalisé, comment puis-je savoir si j'écris un analyseur d'ascension récursif? Je suis définitivement intéressé par la complexité O (n) de l'analyse LALR (plus j'ai déjà une grammaire LALR) et je ne veux pas savoir plus tard que j'ai écrit un analyseur LL à la place. Edit: Je n'ai vu que des parseurs automatiques pilotés par des tables et un couple a généré des exemples simples d'analyseurs récursifs, dont aucun ne ressemble à distance à ce que je construisais à la main. Il est donc assez difficile d'associer le code "évident" pour traiter une règle avec un algorithme réel.

Si vous prenez le code pour une règle relativement simple, par exemple

name_or_qualified_name = identifier *('.' identifier); 

que je l'ai traduit en

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

Il n'y a rien de très gauche ou à droite à ce sujet. C'est évidemment une information utile et importante à connaître, et je ne la vois pas. Le seul fait évident ici est que c'est récursif.

Editer: Désolé, mauvais exemple. Que diriez-vous de quelque chose comme ceci:

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

Les deux LL et LALR sont O (n), ainsi ce n'est pas grave. Cependant, tous les analyseurs de descente récursifs ne sont pas tous LL. Ceux qui n'utilisent pas une forme de retour arrière – essayent une production et quand ça ne marche pas en essayer une autre jusqu'à ce que toutes les productions possibles aient été épuisées ou qu'une analyse réussie soit trouvée. Il n'est pas très difficile de remarquer que vous faites ceci :-)

Pour savoir si vous construisez un analyseur LL ou LALR – vous le savez en connaissant la méthode de construction que vous suivez.

Edité pour ajouter: Un trait distinctif entre la descente récursive et la remontée récursive est le rôle des procédures. En descente récursive, vous avez une procédure pour chaque non-terminal. En ascension récursive, vous avez une procédure pour chaque état LR. Pour avoir ce dernier, il faut à peu près construire au préalable l'automate LR (sauf si vous l'avez fait si souvent que vous pouvez le faire à la volée – mais dans ce cas vous ne poseriez pas cette question). Votre premier exemple de code ressemble à une descente récursive; mais vous ne nous avez pas dit comment le deuxième exemple de code se rapporte à votre grammaire, donc c'est difficile à dire là.