Analyseur de descente récursif avec retour en arrière pour la grammaire

Quelqu'un peut-il m'éclairer pourquoi un analyseur de descente récursive avec retour arrière qui essaie les productions et (dans cet ordre) ne reconnaît pas le langage formé par la grammaire .$S \rightarrow aSa$$S \rightarrow aa$$S \rightarrow aSa\ |\ aa$

Il semble analyser uniquement les mots de la langue .$\{a^{2^n}\ |\ n \ge 1 \}$

J'ai généré un tel analyseur à l'aide de ce générateur d' analyseur ABNF avec la règle de production S = "a" S "a" / "aa"et l'analyseur ne reconnaît pas le mot aaaaaa, par exemple.

Je m'attendrais à ce qu'il utilise la production jusqu'à ce que la concaténation des nœuds terminaux de l'arbre d'analyse à partir de la gauche commence par 7 , puis monte dans l'arbre d'analyse en choisissant la production place jusqu'à ce que l'arbre ressemble ce:$S \rightarrow aSa$a$S \rightarrow aa$

   S 
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a

Ce n'est pas vraiment une réponse, mais les arbres d'analyse ne correspondent pas aux commentaires normaux.

Votre grammaire doit analyser la chaîne .$S \rightarrow aSa\ |\ aa$$aaaaaa$

Mais l'arbre d'analyse a la forme suivante:

      S 
     /|\
    / S \
   / /|\ \
  / / S \ \
 / / / \ \ \
a a a   a a a

ou si vous préférez cette présentation, avec les terminaux sur des lignes différentes

     S 
   / | \
  a  S  a
   / | \
  a  S  a
    / \
   a   a

J'ai vérifié que le générateur d'analyseur ABNF ne semble pas fonctionner, mais je ne sais pas comment tracer ce qu'il fait.

Il semble en effet recongniser l'ensemble qui n'est pas ce que la grammaire définit.$\{a^{2^n}\ |\ n \ge 1 \}$

Il est un peu surprenant d'avoir un site aussi élaboré autour d'un analyseur de buggy, qui utilise en outre une technique d'analyse totalement inintéressante.

Après un nouvel examen:

Je pense avoir trouvé une source du problème. Les crochets signifient facultatif .

Donc, votre grammaire doit être écrite soit S = "a" S "a" / "aa" ou S = "a" [S] "a". Ensuite, cela semble fonctionner correctement.

Mais le système est apparemment perdu lorsqu'il a deux fois la même règle sous différentes formes. Je ne suis pas sûr pourquoi.

Je n'ai pas trouvé de page expliquant ces problèmes syntaxiques pour spécifier la grammaire.

Je considère toujours ce buggy.

s1()$S \rightarrow aSa$trues()s2()$S \rightarrow aa$

Pensez à analyser à aaaaaanouveau le mot . À un moment donné, l'arbre d'analyse ressemblera à ceci:

   S 
 / | \
a  S  a
 / | \
a  S  a    <--
 / | \
a  S  a
  / \
 a   a

s()trueS$S \rightarrow aa$

   S 
 / | \
a  S  a
  / \
 a   a

J'ai tendance à considérer cela comme un problème avec ma mise en œuvre et non avec le retour en arrière des analyseurs de descente récursifs en général, cependant.

#include <iostream>

char* next;    
bool term(char token) {
    if (*next != '\0')
        return *next++ == token;
    else
        return false;
}

bool s();    
bool s1() {
    return term('a') && s() && term('a');
}    
bool s2() {
    return term('a') && term('a');
}    
bool s() {
    auto save = next;
    return s1() or (next = save, s2());
}    

int main(int argc, char* argv[]) {
    next = "aaaaaa";
    if (s() && *next == '\0') {
        std::cout << "match";
    }
    else
        std::cout << "no match";
}

C'est une fonctionnalité pas un bug

Examinez de près quand et où le retour en arrière se produit:

     1.           2.          3.          4.          5.          6.          7.          8.          9.          10.         11.         12.

     S            S           S           S           S           S           S           S           S           S           S           S      
   / | \        / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
  a  S  a      a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
               a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                            / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
                           a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                                        / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
                                       a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                    / | \       / | \       / | \       / | \       / | \       /   \
                                                   a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                                / | \       / | \       / | \       /   \   
                                                               a  S  a     a  S  a     a  S  a     a     a
                                                                            / | \       /   \
                                                                           a  S  a     a     a



w[] = 'aaaaaa'  //input
l[] = ''        //current tree leafs


 1. tree:   The parser starts with the start symbol S and tries first alternative S->aSa:       Result: w[0]  = l[0]     w = aaaaaa    l = aSa
 |          -- S->aSa works                                                                         | |     | | 
 6. tree:   The parser matches a after a:                                                       Result: w[6]  = l[6]     w = aaaaaa    l = aaaaaaSaaaaaa
 7. tree:   The parser tries S->aSa again but there is no match!                                Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaSaaaaaaa 
 8. tree:   The parser tries S->aa but there is still no match!                                 Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaaaa
 9. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaa
10. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaa
11. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaa
12. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaa

Le point crucial ici est que l'analyseur revient en arrière après la position où le dernier caractère correspondant a été trouvé. C'est pourquoi il "saute" de l'arbre 11 avec l = aaaaaaaa au 12ème arbre avec l = aaaa en utilisant S -> aa à l [7].