J'étais encore un écolier quand je suis tombé entre les mains du livre "Débutant Cours C et C ++" de la maison d'édition Dialog MEPhI. C'est à partir de ce livre que j'ai appris les bases de la programmation orientée objet, et cela m'a aussi posé un problème que je n'ai pas pu résoudre pendant un certain temps. À la fin, il y avait une application répertoriant les programmes, dont l'un était appelé une calculatrice récursive. Ce fut ma première rencontre avec l'analyse d'expressions arithmétiques en utilisant la méthode de descente récursive. Je me souviens encore de ces longues heures passées à essayer de comprendre au moins quelque chose dans ce code.L'article est principalement destiné à ceux qui sont confrontés à la tâche d'analyser des expressions pour la première fois.Et donc, avant d'écrire l'analyseur d'expressions arithmétiques, nous devons comprendre la structure de ces expressions mêmes. Pour simplifier, nous ne considérerons pas l'opération unaire moins et la possibilité d'utiliser des fonctions dans l'expression pour l'instant.Pour décrire la structure, nous utilisons les formes Beckus-NaurE -> T + E | T - E | T
T -> F * T | F / t | F
F -> N | (E)
Voici la barre verticale "|" signifie une opération logique "ou", et E, T, F, N - différents types de sous-expressions dans lesquelles l'expression originale sera divisée lors de l'utilisation de ces phrases. N dans ce cas désigne un nombre.La première phrase signifie qu'une expression de type E peut consister en une expression de type T plus une expression de type E, ou une expression de type T moins une expression de type E ou simplement une expression de type T.Pourla deuxième phrase, tout est similaire, mais au lieu d'ajouter et de soustraire il y aura multiplication et division.La troisième phrase signifie qu'une expression de type F est soit un nombre soit une expression de type E entre crochets.Essayons d'appliquer ces trois phrases à un exemple d'expression arithmétique2 + 3 * (4 - 5) + 6 - 7
Nous appliquons la première phrase plusieurs foisE (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)
Maintenant, notre expression se compose uniquement de sous-expressions de type T, nous appliquons donc la deuxième phrase à chacun d'eux.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)
Il est temps pour la troisième phraseF (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
Pour l'expression entre crochets (4-5), nous sommes récursivement passés à la première phrase et nous devrons répéter toutes les actions par analogie avec ce que c'était pour le reste de l'expression. Si l'expression contenait des crochets imbriqués, il y aurait plus de telles transitions récursives. Je vous recommande d'essayer indépendamment d'appliquer les trois phrases à une expression qui contiendrait des niveaux imbriqués de crochets, par exemple 2 + 2 * (3 + 4 * (5-6)), pour vous assurer qu'ils fonctionnent également pour cela.Il ne nous reste plus qu'à mettre en œuvre les actions menées par les propositions sous forme de code. Ce sera l'analyse de l'expression à l'aide de la méthode de descente récursive, mais avant de commencer à écrire du code, simplifions un peu les phrases en nous débarrassant de la récursivité dans les deux premières d'entre elles.Si nous substituons sans cesse la première phrase en elle-même, alors nous obtenonsE -> T ± T ± T ± T ± ... ± T
La deuxième phrase peut être transformée de manière similaire.T -> F * / F * / F * / * / ... * / F
En fait, cela signifie qu'au lieu de la récursivité, nous pouvons utiliser une boucle ici. De même, la récursivité ne peut être exclue de la troisième phrase.Nous allons écrire le code en Java, car C'est le langage de programmation le plus familier pour moi en ce moment. La dernière remarque avant de commencer à écrire le code - je laisse de côté la tâche de tokenisation, c'est-à-dire fractionner l'expression en éléments significatifs indivisibles (jetons). Ces jetons sont des nombres, des signes d'opérations arithmétiques et des parenthèses. Supposons que nous ayons déjà un tableau de jetons en entrée de l'expression.String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};
Créez la prochaine classe d'analyseur qui contiendra les méthodes- parse () démarre l'analyse d'une expression
- expression () pour gérer les expressions de type E
- term () pour traiter les expressions de type T
- factor () pour le traitement des expressions de type F et 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);
}
}
C'est tout. Si vous le souhaitez, cet analyseur peut apprendre à travailler avec un moins unaire ou à fonctionner dans une expression. La première chose à faire est de modifier les phrases originales afin qu'elles prennent en compte un nouvel élément de la structure de l'expression, et il pourrait y avoir plus de propositions à partir de cela. Une fois qu'ils sont correctement modifiés, la mise en œuvre devient presque formelle.