Analizador de descenso recursivo

En informática, un analizador descendente recursivo es una especie de analizador de arriba hacia abajo creado a partir de un conjunto de procedimientos mutuamente recursivos (o un equivalente no recursivo) donde cada uno de estos procedimientos implementa uno de los no terminales de la gramática. Así, la estructura del programa resultante refleja fielmente la de la gramática que reconoce.

Un analizador predictivo es un analizador descendente recursivo que no requiere retroceso. El análisis predictivo solo es posible para la clase de gramáticas LL(k), que son las gramáticas libres de contexto para las que existe algún número entero positivo k que permite que un analizador descendente recursivo decida qué producción usar por examinando solo los siguientes tokens de entrada k. Las gramáticas LL(k) por lo tanto excluyen todas las gramáticas ambiguas, así como todas las gramáticas que contienen recursividad por la izquierda. Cualquier gramática libre de contexto se puede transformar en una gramática equivalente que no tenga recursividad por la izquierda, pero la eliminación de la recursividad por la izquierda no siempre produce una gramática LL(k). Un analizador predictivo se ejecuta en tiempo lineal.

El descenso recursivo con retroceso es una técnica que determina qué producción usar probando cada producción por turno. El descenso recursivo con retroceso no se limita a las gramáticas LL(k), pero no se garantiza que termine a menos que la gramática sea LL(k). Incluso cuando terminan, los analizadores que usan descenso recursivo con retroceso pueden requerir un tiempo exponencial.

Aunque los analizadores predictivos se utilizan ampliamente y se eligen con frecuencia si se escribe un analizador a mano, los programadores suelen preferir utilizar un analizador basado en tablas producido por un generador de analizadores, ya sea para un LL(k) o utilizando un analizador alternativo, como LALR o LR. Este es particularmente el caso si una gramática no está en forma LL (k), ya que se trata de transformar la gramática a LL para que sea adecuada para el análisis predictivo. Los analizadores predictivos también se pueden generar automáticamente, utilizando herramientas como ANTLR.

Los analizadores predictivos se pueden representar usando diagramas de transición para cada símbolo no terminal donde los bordes entre los estados inicial y final están etiquetados por los símbolos (terminales y no terminales) del lado derecho de la regla de producción.

Ejemplo de analizador

La siguiente gramática similar a EBNF (para el lenguaje de programación PL/0 de Niklaus Wirth, de Algorithms + Data Structures = Programs) está en formato LL(1):

 programa = bloque ". . bloque = ["Contesta" ident "=" Número {}" ident "=" Número} ";] ["var" ident {}" ident} ";] {}"procedimiento" ident "; bloque ";} declaración . declaración = ident ":=" expresión Silencio "llamar" ident Silencio "Principio" declaración {}"; declaración } "final" Silencio "si" condición "entonces" declaración Silencio "mientras" condición "do" declaración . condición = "odd" expresión Silencio expresión ()"="Silencio"#Silencio"Seguido"Silencio"Seguido"Silencio"No"Silencio"No") expresión . expresión = ["+"Silencio"-] mandato ["+"Silencio"-) mandato} . mandato = factor ["*Silencio"/") factor} . factor = ident Silencio Número Silencio "( expresión ")" .

Los terminales se expresan entre comillas. Cada no terminal está definido por una regla en la gramática, excepto ident y number, que se supone que están definidos implícitamente.

Implementación C

Lo que sigue es una implementación de un analizador de descenso recursivo para el lenguaje anterior en C. El analizador lee el código fuente y sale con un mensaje de error si el código no se analiza, y sale en silencio si el código se analiza correctamente.

Observe cuán fielmente el analizador predictivo a continuación refleja la gramática anterior. Hay un procedimiento para cada no terminal en la gramática. El análisis desciende de arriba hacia abajo hasta que se procesa el no terminal final. El fragmento de programa depende de una variable global, sym, que contiene el símbolo actual de la entrada, y la función nextsym, que actualiza sym cuando llamó.

Las implementaciones de las funciones nextsym y error se omiten por simplicidad.

typedef enum {ident, number, lparen, rparen, times, slash, plus,
    minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
    endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
    varsym, procsym, period, oddsym} Symbol;

Symbol sym;
void nextsym(void);
void error(const char msg[]);

int accept(Symbol s) {
    if (sym == s) {
        nextsym();
        return 1;
    }
    return 0;
}

int expect(Symbol s) {
    if (accept(s))
        return 1;
    error("expect: unexpected symbol");
    return 0;
}

void factor(void) {
    if (accept(ident)) {
        ;
    } else if (accept(number)) {
        ;
    } else if (accept(lparen)) {
        expression();
        expect(rparen);
    } else {
        error("factor: syntax error");
        nextsym();
    }
}

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        nextsym();
        factor();
    }
}

void expression(void) {
    if (sym == plus || sym == minus)
        nextsym();
    term();
    while (sym == plus || sym == minus) {
        nextsym();
        term();
    }
}

void condition(void) {
    if (accept(oddsym)) {
        expression();
    } else {
        expression();
        if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
            nextsym();
            expression();
        } else {
            error("condition: invalid operator");
            nextsym();
        }
    }
}

void statement(void) {
    if (accept(ident)) {
        expect(becomes);
        expression();
    } else if (accept(callsym)) {
        expect(ident);
    } else if (accept(beginsym)) {
        do {
            statement();
        } while (accept(semicolon));
        expect(endsym);
    } else if (accept(ifsym)) {
        condition();
        expect(thensym);
        statement();
    } else if (accept(whilesym)) {
        condition();
        expect(dosym);
        statement();
    } else {
        error("statement: syntax error");
        nextsym();
    }
}

void block(void) {
    if (accept(constsym)) {
        do {
            expect(ident);
            expect(eql);
            expect(number);
        } while (accept(comma));
        expect(semicolon);
    }
    if (accept(varsym)) {
        do {
            expect(ident);
        } while (accept(comma));
        expect(semicolon);
    }
    while (accept(procsym)) {
        expect(ident);
        expect(semicolon);
        block();
        expect(semicolon);
    }
    statement();
}

void program(void) {
    nextsym();
    block();
    expect(period);
}

Ejemplos

Algunos generadores de analizadores descendentes recursivos:

• TMG – un compilador de principios utilizado en los años 1960 y principios de 1970
• JavaCC
• Coco/R
• ANTLR
• Marco de parser espírita – un marco de generador de parser de ascendencia recidiva C++ que no requiere paso precompilado
• parboiled (Java) – una biblioteca PEG de descendencia recurrente para Java