Todavía era un niño de escuela cuando caí en manos del libro "Curso para principiantes C y C ++" de la editorial Dialog MEPhI. Fue de este libro que aprendí sobre los conceptos básicos de la programación orientada a objetos, y también me planteó un problema que no pude resolver por bastante tiempo. Al final, había una aplicación que enumeraba programas, uno de los cuales se llamaba calculadora recursiva. Este fue mi primer encuentro con el análisis de expresiones aritméticas utilizando el método de descenso recursivo. Todavía recuerdo esas largas horas que pasé intentando al menos entender algo en este código.El artículo está destinado principalmente a aquellos que se enfrentan a la tarea de analizar expresiones por primera vez.Y así, antes de escribir el analizador de expresiones aritméticas, necesitamos entender la estructura de estas mismas expresiones. Por simplicidad, no consideraremos la operación unaria menos y la posibilidad de usar funciones en la expresión por ahora.Para describir la estructura, utilizamos las formas de Beckus-Naur.E -> T + E | T - E | T
T -> F * T | F / t | F
F -> N | (MI)
Aquí está la barra vertical "|" significa una operación lógica "o", y E, T, F, N - varios tipos de subexpresiones en las que la expresión original se dividirá al usar estas oraciones. N en este caso denota un número.La primera oración significa que una expresión de tipo E puede consistir en una expresión de tipo T más una expresión de tipo E, o una expresión de tipo T menos una expresión de tipo E o simplemente una expresión de tipo T.Para la segunda oración, todo es similar, pero en lugar de sumar y restar habrá multiplicación y división.La tercera oración significa que una expresión de tipo F es un número o una expresión de tipo E entre paréntesis.Intentemos aplicar estas tres oraciones a un ejemplo de una expresión aritmética.2 + 3 * (4 - 5) + 6 - 7
Aplicamos la primera oración varias vecesE (2 + 3 * (4-5) + 6-7) ->
T (2) + E (3 * (4-5) + 6-7) ->
T (2) + T (3 * (4-5)) + E (6-7) ->
T (2) + T (3 * (4-5)) + T (6) - T (7)
Ahora nuestra expresión consiste solo en subexpresiones de tipo T, por lo que aplicamos la segunda oración a cada una de ellas.T (2) -> F (2)
T (3 * (4-5)) -> F (3) * T ((4-5)) -> F (3) * F ((4-5))
T (6) -> F (6)
T (7) -> F (7)
Es hora de la tercera oración.F (2) -> N (2) -> 2
F (3) -> N (3) -> 3
F ((4-5)) -> E (4-5)
F (6) -> N (6) -> 6
F (7) -> N (7) -> 7
Para la expresión entre paréntesis (4-5), pasamos recursivamente a la primera oración y tendremos que repetir todas las acciones por analogía con lo que fue para el resto de la expresión. Si la expresión contuviera paréntesis anidados, habría más transiciones recursivas. Le recomendaría que intente de forma independiente aplicar las tres oraciones a una expresión que contenga niveles anidados de corchetes, por ejemplo 2 + 2 * (3 + 4 * (5-6)), para asegurarse de que también funcionen para ella.Ahora solo tenemos que implementar las acciones que llevan a cabo las propuestas en forma de código. Este será el análisis de la expresión usando el método de descenso recursivo, pero antes de comenzar a escribir código, simplifiquemos un poco las oraciones eliminando la recursividad en las dos primeras.Si sustituimos sin cesar la primera oración en sí misma, entonces obtenemosE -> T ± T ± T ± T ± ... ± T
La segunda oración se puede transformar de manera similar.T -> F * / F * / F * / * / ... * / F
De hecho, esto significa que en lugar de recurrencia, podemos usar un bucle aquí. Del mismo modo, la recursión no puede excluirse de la tercera oración.Escribiremos el código en Java, porque Este es el lenguaje de programación más familiar para mí en este momento. El último comentario antes de comenzar a escribir el código: dejo de lado la tarea de tokenización, es decir dividiendo la expresión en elementos significativos indivisibles (tokens). Tales tokens son números, signos de operaciones aritméticas y corchetes. Supongamos que ya tenemos una matriz de tokens como entrada de la expresión.String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};
Cree la próxima clase de analizador que contendrá los métodos- parse () comienza a analizar una expresión
- expresión () para manejar expresiones de tipo E
- term () para procesar expresiones de tipo T
- factor () para procesar expresiones de tipo F y N
public class RecursiveDescentParser {
private final String[] tokens;
private int pos = 0;
public RecursiveDescentParser(String[] tokens) {
this.tokens = tokens;
}
public Double parse() {
Double result = expression();
if (pos != tokens.length) {
throw new IllegalStateException("Error in expression at " + tokens[pos]));
}
return result;
}
private Double expression() {
Double first = term();
while (pos < tokens.length) {
String operator = tokens[pos];
if (!operator.equals("+") && !operator.equals("-")) {
break;
} else {
pos++;
}
Double second = term();
if (operator.equals("+")) {
first += second;
} else {
first -= second;
}
}
return first;
}
private Double term() {
Double first = factor();
while (pos < tokens.length) {
String operator = tokens[pos];
if (!operator.equals("*") && !operator.equals("/")) {
break;
} else {
pos++;
}
Double second = factor();
if (operator.equals("*")) {
first *= second;
} else {
first /= second;
}
}
return first;
}
private Double factor() {
String next = tokens[pos];
Double result;
if (next.equals("(")) {
pos++;
result = expression();
String closingBracket;
if (pos < tokens.length) {
closingBracket = tokens[pos];
} else {
throw new IllegalStateException("Unexpected end of expression");
}
if (pos < tokens.length && closingBracket.equals(")")) {
pos++;
return result;
}
throw new IllegalStateException("')' expected but " + closingBracket);
}
pos++;
return Double.parseDouble(next);
}
}
Eso es todo. Si lo desea, se puede enseñar a este analizador a trabajar con un signo o menos unario en una expresión. Lo primero que debe hacer es cambiar las oraciones originales para que tengan en cuenta un nuevo elemento de la estructura de la expresión, y puede haber más propuestas a partir de esto. Una vez que se modifican adecuadamente, la implementación se vuelve casi formal.