parsing - sintactico - en qué consiste el análisis descendente con funciones recursivas

Análisis descendente recursivo: desde LL(1) hasta

Question

La siguiente gramática simple de "expresión de calculadora" (BNF) se puede analizar fácilmente con un analizador sintáctico trivial de bajada recursiva, que es predictivo LL (1):

<expr> := <term> + <term>
| <term> - <term>
| <term>
<term> := <factor> * <factor>
<factor> / <factor>
<factor>
<factor> := <number>
| <id>
| ( <expr> )
<number> := /d+
<id> := [a-zA-Z_]/w+

Porque siempre es suficiente ver el siguiente token para conocer la regla que debe elegirse. Sin embargo, supongamos que agrego la siguiente regla:

<command> := <expr>
| <id> = <expr>

Para el propósito de interactuar con la calculadora en la línea de comando, con variables, como esta:

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

¿Es cierto que no puedo usar un simple analizador predictivo de LL (1) para analizar las reglas de <command> ? Traté de escribir el analizador para ello, pero parece que necesito saber más fichas hacia adelante. ¿Es la solución para usar el seguimiento de retroceso, o puedo simplemente implementar LL (2) y siempre mirar dos tokens hacia adelante?

¿Cómo los generadores de analizador de RD manejan este problema (ANTLR, por ejemplo)?

Answer 1

El problema con

<command> := <expr>
| <id> = <expr>

es que cuando "ves" <id> no puedes decir si es el comienzo de una asignación (segunda regla) o es un " <factor> ". Solo sabrás cuándo leerás el siguiente token.

AFAIK ANTLR es LL (*) (y también es capaz de generar analizadores de paquetes de ratas si no me equivoco) por lo que probablemente manejará este grammare considerando dos tokens a la vez.

Si puede jugar con la gramática, sugeriría agregar una palabra clave para la tarea (por ej., let x = 8 ):

<command> := <expr>
| "let" <id> "=" <expr>

o use la = para significar la evaluación:

<command> := "=" <expr>
| <id> "=" <expr>

Answer 2

ANTLR 3 usa un analizador "LL (*)" en lugar de un analizador LL (k), por lo que mirará hacia adelante hasta que llegue al final de la entrada, si es necesario, sin retroceder, utilizando un autómata determinista finito especialmente optimizado ( DFA).

Answer 3

El problema es que la gramática:

<command> := <expr>
| <id> = <expr>

no es un procedimiento mutuamente recursivo. Para un analizador sintáctico decente recursivo necesitarás determinar un equivalente no recursivo.

rdentato post muestra cómo solucionarlo, suponiendo que puedes jugar con la gramática. Este powerpoint detalla el problema con más detalle y muestra cómo corregirlo: http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F%2Fxml.cs. nccu.edu.tw% 2Fcourses% 2Fcompiler% 2Fcp2006% 2Fslides% 2Flec3-Parsing% 26TopDownParsing.ppt & ei = -YLaSPrWGaPwhAK5ydCqBQ & usg = AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q & sig2 = nlYKQVfakmqy_57137XzrQ

Answer 4

Creo que hay dos formas de resolver esto con un analizador de descenso recursivo: ya sea usando (más) anticipación o retrocediendo.

Mirar hacia el futuro

command() {
if (currentToken() == id && lookaheadToken() == ''='') {
return assignment();
} else {
return expr();
}
}

Retroceder

command() {
savedLocation = scanLocation();
if (accept( id )) {
identifier = acceptedTokenValue();
if (!accept( ''='' )) {
setScanLocation( savedLocation );
return expr();
}
return new assignment( identifier, expr() );
} else {
return expr();
}
}