Análisis de descenso recursivo - desde LL (1) hacia arriba

Question

La siguiente & "; calculadora expresión &"; la gramática (BNF) se puede analizar fácilmente con un analizador trivial de descenso recursivo, que es LL predictivo (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 próximo token para saber la regla que se debe elegir. Sin embargo, supongamos que agrego la siguiente regla:

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

Con el fin 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 analizador predictivo LL (1) simple para analizar las reglas <command>? Traté de escribir el analizador para ello, pero parece que necesito saber más fichas hacia adelante. ¿Es la solución usar el rastreo hacia atrás, o puedo implementar LL (2) y siempre mirar dos tokens hacia adelante?

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

Answer 1

El problema con

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

es que cuando " vea " <id> no se puede saber si es el comienzo de una asignación (segunda regla) o si es " <factor> " ;. Solo sabrá cuándo leerá el próximo token.

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

Si puede jugar con la gramática, le sugiero que agregue una palabra clave para la tarea (por ejemplo, let x = 8):

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

o use = para indicar evaluación:

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

Answer 2

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

Lookahead

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

Retroceso

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

Answer 3

El problema es que la gramática:

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

no es un procedimiento recursivo mutuo. Para un analizador recursivo decente, deberá determinar un equivalente no recursivo.

rdentato post muestra cómo solucionar esto, suponiendo que pueda jugar con la gramática. Este powerpoint explica el problema con un poco más de detalle y muestra cómo corregirlo:

ANTLR 3 usa un " LL (*) " analizador 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 finito determinístico especialmente optimizado (DFA).

Answer 4

Answer 5

Answer 6

Answer 7

Answer 8