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.
reference-request
formal-grammars
recursion
parsers
left-recursion
usuario71015
fuente
fuente
Respuestas:
Es solo un analizador LL (1) implementado con descenso recursivo.
Comienza con:
aplique la eliminación de recursión izquierda para obtener una gramática LL (1):
escribe las funciones correspondientes:
eliminar la recursividad de la cola:
en línea:
y solo tiene que agregar el procesamiento semántico para obtener su función.
fuente
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.
fuente