Analizador de descenso recursivo con retroceso para la gramática

10

¿Puede alguien aclararme por qué un analizador de descenso recursivo con retroceso que prueba las producciones y (en ese orden) no reconoce el lenguaje formado por la gramática .SunSunSununSunSun El | unun

Parece que solo analiza palabras del idioma .{a2n | n1}

Generé dicho analizador utilizando este generador de analizador ABNF con la regla de producción S = "a" S "a" / "aa"y el analizador no reconoce la palabra aaaaaa, por ejemplo.

Esperaría que use la producción hasta que la concatenación de los nodos terminales del árbol de análisis desde la izquierda comience con 7 's, y luego suba el árbol de análisis eligiendo la producción lugar hasta que el árbol se vea como esta:SaSaaSaun

   S 
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a
meribold
fuente
2
¿Por qué crees que no puede analizar esta palabra?
Yuval Filmus
@ Yuval, creo que debería analizarlo, por lo que me falta algo.
meribold
Ah, ahora la pregunta tiene más sentido; gracias por la edición! Si lo que escribe es verdadero (no lo comprobé), el generador parece tener un error. (O no está especificado para su gramática; creo que esto es poco probable ya que la gramática es elemental y no ambigua.
Rafael
@Raphael, edité la pregunta nuevamente (con suerte sin cambiar el significado). En realidad, tengo la tarea de explicar por qué un analizador no reconoce la palabra aaaaaa.
meribold
¿De dónde sacaste ese árbol? No obtengo mucho de ese generador de analizador ABNF. El árbol que das no tiene mucho sentido. Pero la cadena aaaaaadebe analizar y no lo hace. Pero aaaaanaliza. Aparentemente tienes razón sobre los poderes de 2. La cosa debe estar molesta. se analiza solo aacon S = "aa" / "a" [S] "a". ¿Puedes rastrear lo que hace el analizador?
babou

Respuestas:

6

Esta no es una gran respuesta, pero los árboles de análisis no se ajustan a los comentarios normales.

Su gramática debe analizar la cadena a a a a a a .SaSa | aaaaaaaun

Pero el árbol de análisis tiene la siguiente forma:

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

o si prefiere esta presentación, con los terminales en diferentes líneas

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

Verifiqué que el generador de analizador ABNF no parece funcionar, pero no sé cómo rastrear lo que hace.

De hecho, parece reconocer el conjunto que no es lo que define la gramática.{un2norte El | norte1}

Es un poco sorprendente tener un sitio tan elaborado alrededor de un analizador de errores, que además utiliza una técnica de análisis totalmente poco interesante.


Después de mirarlo más a fondo:

Creo que encontré una fuente del problema. Los corchetes significan opcional .

Por lo tanto, su gramática debe escribirse S = "a" S "a" / "aa" o S = "a" [S] "a". Entonces parece funcionar correctamente.

Pero el sistema aparentemente se pierde cuando se tiene el doble de la misma regla en diferentes formas. No estoy seguro por qué.

No encontré una página que explicara estos problemas sintácticos para especificar la gramática.

Todavía considero ese buggy.

babou
fuente
1
Ay. Si. No sé lo que estaba pensando cuando escribí ese árbol de análisis. Editaré mi pregunta y pegaré la tuya.
meribold
Encontré otro descenso recursivo, generador de analizador de retroceso con una demostración en línea aquí y muestra el mismo comportamiento con esta regla:S ::= 'a'<S>'a' | 'a''a'
meribold
Todavía no se analiza aaaaaacuando se usa S = "a" S "a" / "aa", pero parece que tienes razón sobre los corchetes.
meribold
No veo el punto de explorar el descenso recursivo, el analizador de retroceso.
babou
tienes razón S = "a" S "a" / "aa"... Probé demasiado rápido e hice clic en generar en lugar de analizar.
babou
3

s1()SunSuntrues()s2()Sunun

Considere analizar la palabra aaaaaanuevamente. En un momento, el árbol de análisis se verá así:

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

s()trueSSunun

   S 
 / | \
a  S  a
  / \
 a   a

Sin embargo, tiendo a considerar esto un problema con mi implementación y no con el retroceso de analizadores de descenso recursivo en general.

#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
fuente
2

Es una característica, no un error.

Observe de cerca cuándo y dónde ocurre el retroceso:

     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

El punto crucial aquí es que el analizador retrocede después de la posición, donde se encontró el último personaje coincidente. Es por eso que "salta" del árbol 11 con l = aaaaaaaa al árbol 12 con l = aaaa usando S -> aa en l [7].

Sebbas
fuente
¡Finalmente tuve tiempo de editarlo! ;)
Sebbas