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

10

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 .SuneSuneSuneuneSuneSune | uneune

Il semble analyser uniquement les mots de la langue .{une2n | n1}

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:SuneSuneaSuneune

   S 
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a
meribold
la source
2
Pourquoi pensez-vous qu'il ne peut pas analyser ce mot?
Yuval Filmus
@Yuval, je pense qu'il devrait l'analyser, donc je dois manquer quelque chose.
meribold
Ah, maintenant la question a plus de sens; merci pour l'édition! Si ce que vous écrivez est vrai (je n'ai pas vérifié), le générateur semble avoir un bug. (Ou ce n'est pas spécifié pour votre grammaire; je pense que cela est peu probable car la grammaire est élémentaire et sans ambiguïté.
Raphael
@Raphael, j'ai de nouveau édité la question (j'espère sans en changer le sens). Je suis en fait chargé d'expliquer pourquoi un tel analyseur ne reconnaît pas le mot aaaaaa.
meribold
Où avez-vous trouvé cet arbre. Je ne tire pas grand-chose de ce générateur d'analyseur ABNF. L'arbre que vous donnez n'a pas beaucoup de sens. Mais la chaîne aaaaaadoit analyser et ne fonctionne pas. Mais aaaaanalyse. Vous avez apparemment raison sur les pouvoirs de 2. La chose doit être mise sur écoute. il analyse uniquement aaavec S = "aa" / "a" [S] "a". Pouvez-vous retracer ce que fait l'analyseur?
babou

Réponses:

6

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 .SuneSune | uneuneuneuneuneuneuneune

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.{une2n | n1}

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.

babou
la source
1
Aie. Ouais. Je ne sais pas à quoi je pensais quand j'ai écrit cet arbre d'analyse. Je vais modifier ma question et coller la vôtre.
meribold
J'ai trouvé une autre descente récursive, un générateur d'analyseur de retour en arrière avec une démo en ligne ici et il montre le même comportement avec cette règle:S ::= 'a'<S>'a' | 'a''a'
meribold
Il n'analyse toujours pas aaaaaalors de l'utilisation S = "a" S "a" / "aa", mais vous semblez avoir raison sur les crochets.
meribold
Je ne vois pas l'intérêt d'explorer la descente récursive, l'analyseur de retour en arrière.
babou
vous avez raison S = "a" S "a" / "aa"... J'ai testé trop vite, et j'ai cliqué sur générer au lieu d'analyser.
babou
3

s1()SuneSunetrues()s2()Suneune

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()trueSSuneune

   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";
}
meribold
la source
2

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].

Sebbas
la source
J'ai enfin eu le temps de le modifier! ;)
Sebbas