¿Nombre correcto para un analizador de descenso recursivo que usa bucles para manejar la recursividad izquierda?

8

Esta gramática se deja recursiva:

Expression  ::= AdditionExpression

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

MultiplicationExpression    ::=
    Term
        | MultiplicationExpression '*' Term
        | MultiplicationExpression '/' Term

Term    ::=
    Number
        | '(' AdditionExpression ')'

Number  ::=
    [+-]?[0-9]+(\.[0-9]+)?

Entonces, en teoría, el descenso recursivo no funcionará. Pero al explotar las propiedades de la gramática de que cada regla recursiva a la izquierda corresponde a un nivel de precedencia específico, y esa anticipación de una sola ficha es suficiente para elegir la producción correcta, las reglas recursivas a la izquierda se pueden analizar individualmente con bucles while.

Por ejemplo, para analizar el AdditionExpression no terminal, este pseudocódigo es suficiente:

function parse_addition_expression() {
    num = parse_multiplication_expression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            num += parse_multiplication_expression()
        else if (current_token == MINUS)
            num -= parse_multiplication_expression()
        else {
            unget_token()
            return num
        }
    }
    return num
}

¿Cuál es el nombre correcto para este tipo de analizador? Este artículo informativo solo se refiere a él como la "Solución clásica": https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Debe haber un nombre propio para este tipo de analizador.

usuario71015
fuente
Para mí no es un tipo de analizador, es solo la aplicación de la eliminación de recursión izquierda combinada con un analizador de descenso recursivo. Vea esta pregunta para una técnica para eliminar la recursividad izquierda.
Programador
Creo que podrías estar en lo correcto. Se parece a un equivalente en tiempo de ejecución del algoritmo de eliminación de recursión izquierda.
user71015
1
No utilice el cuadro de 'respuesta' para publicar comentarios u otros comentarios. Si crea una cuenta , conservará el acceso y podrá aceptar la respuesta que más le ayudó. Si ingresó un correo electrónico y perdió el acceso, puede recuperar el acceso . Si no ingresó una dirección de correo electrónico y no tiene acceso al navegador / cookies que utilizó para publicar la pregunta, probablemente no tenga suerte. Nadie más puede aceptar la respuesta por usted, ni siquiera los moderadores.
DW

Respuestas:

11

Es solo un analizador LL (1) implementado con descenso recursivo.

Comienza con:

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

aplique la eliminación de recursión izquierda para obtener una gramática LL (1):

AdditionExpression  ::= 
    MultiplicationExpression AdditionExpressionTail

AdditionExpressionTail ::=
        | '+' MultiplicationExpression AdditionExpressionTail
        | '-' MultiplicationExpression AdditionExpressionTail

escribe las funciones correspondientes:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    parse_AdditionExpressionTail()
}

function parse_AdditionExpressionTail() {
    if (has_token()) {
        get_token()
        if (current_token == PLUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else if (current_token == MINUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else {
            unget_token()
        }
    }
}

eliminar la recursividad de la cola:

function parse_AdditionExpressionTail() {
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

en línea:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

y solo tiene que agregar el procesamiento semántico para obtener su función.

Un programador
fuente
6

Desea analizar el análisis LL ( )k . El artículo de Wikipedia es en su mayoría inútil, pero es básicamente un descenso recursivo con símbolos anticipados.k

También hay LL ( ) que permite la búsqueda anticipada ilimitada.

Consulte aquí para obtener una descripción completa de la potencia de esta clase de analizadores.

Rafael
fuente
1
No veo cómo se relaciona esto. El código no usa más de un símbolo de anticipación.
Programador
@AProgrammer Entonces es un analizador LL (1), o muy relacionado.
Raphael
Es un analizador LL (1). Expandí mi comentario en una respuesta.
Programador
2
@AProgrammer No veo cómo se necesitaba una segunda respuesta. LL (1) es LL (k) para k = 1 (¿no es obvio?). Pero bueno.
Raphael