¿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 .
Parece que solo analiza palabras del idioma .
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:a
S
/ | \
a S a
/ | \
a S a
/ \
a a
context-free
formal-grammars
compilers
parsers
meribold
fuente
fuente
aaaaaa
.aaaaaa
debe analizar y no lo hace. Peroaaaa
analiza. Aparentemente tienes razón sobre los poderes de 2. La cosa debe estar molesta. se analiza soloaa
conS = "aa" / "a" [S] "a"
. ¿Puedes rastrear lo que hace el analizador?Respuestas:
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 .S→ a Sa | a a a a a a a a
Pero el árbol de análisis tiene la siguiente forma:
o si prefiere esta presentación, con los terminales en diferentes líneas
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.{ a2norte El | n≥1}
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"
oS = "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.
fuente
S ::= 'a'<S>'a' | 'a''a'
aaaaaa
cuando se usaS = "a" S "a" / "aa"
, pero parece que tienes razón sobre los corchetes.S = "a" S "a" / "aa"
... Probé demasiado rápido e hice clic en generar en lugar de analizar.s1()
true
s()
s2()
Considere analizar la palabra
aaaaaa
nuevamente. En un momento, el árbol de análisis se verá así:s()
true
S
Sin embargo, tiendo a considerar esto un problema con mi implementación y no con el retroceso de analizadores de descenso recursivo en general.
fuente
Es una característica, no un error.
Observe de cerca cuándo y dónde ocurre el retroceso:
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].
fuente