Ich war noch ein Schüler, als ich in die Hände des Buches "Anfängerkurs C und C ++" des Verlags Dialog MEPhI fiel. Aus diesem Buch lernte ich die Grundlagen der objektorientierten Programmierung und es stellte mich vor ein Problem, das ich seit einiger Zeit nicht mehr lösen konnte. Am Ende stand eine Anwendung, die Programme auflistete, von denen eines als rekursiver Rechner bezeichnet wurde. Dies war meine erste Begegnung mit der Analyse von arithmetischen Ausdrücken unter Verwendung der rekursiven Abstiegsmethode. Ich erinnere mich noch an die langen Stunden, die damit verbracht wurden, zumindest etwas in diesem Code zu verstehen.Der Artikel richtet sich in erster Linie an diejenigen, die zum ersten Mal vor der Aufgabe stehen, Ausdrücke zu analysieren.Bevor wir also den Parser für arithmetische Ausdrücke schreiben, müssen wir die Struktur dieser Ausdrücke verstehen. Der Einfachheit halber werden wir die unäre Minusoperation und die Möglichkeit, Funktionen im Ausdruck zu verwenden, vorerst nicht berücksichtigen.Zur Beschreibung der Struktur verwenden wir die Beckus-Naur- FormenE -> T + E | T - E | T.
T -> F * T | F / t | F.
F -> N | (E)
Hier ist der vertikale Balken "|" bedeutet eine logische Operation "oder" und E, T, F, N - verschiedene Arten von Unterausdrücken, in die der ursprüngliche Ausdruck bei Verwendung dieser Sätze aufgeteilt wird. N bezeichnet in diesem Fall eine Zahl.Der erste Satz bedeutet, dass ein Ausdruck vom Typ E aus einem Ausdruck vom Typ T plus einem Ausdruck vom Typ E oder einem Ausdruck vom Typ T minus einem Ausdruck vom Typ E oder nur einem Ausdruck vom Typ T bestehen kann.Für den zweiten Satz ist alles ähnlich, aber anstatt zu addieren und zu subtrahieren, wird multipliziert und Teilung.Der dritte Satz bedeutet, dass ein Ausdruck vom Typ F entweder eine Zahl oder ein Ausdruck vom Typ E in Klammern ist.Versuchen wir, diese drei Sätze auf ein Beispiel eines arithmetischen Ausdrucks anzuwenden2 + 3 * (4 - 5) + 6 - 7
Wir wenden den ersten Satz mehrmals anE (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)
Jetzt besteht unser Ausdruck nur noch aus Unterausdrücken vom Typ T, daher wenden wir den zweiten Satz auf jeden von ihnen an.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 ist Zeit für den dritten SatzF (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
Für den Ausdruck in Klammern (4-5) haben wir rekursiv zum ersten Satz gewechselt und müssen alle Aktionen analog zu dem wiederholen, was er für den Rest des Ausdrucks war. Wenn der Ausdruck verschachtelte Klammern enthalten würde, gäbe es mehr solche rekursiven Übergänge. Ich würde empfehlen, dass Sie unabhängig versuchen, alle drei Sätze auf einen Ausdruck anzuwenden, der verschachtelte Ebenen von Klammern enthält, z. B. 2 + 2 * (3 + 4 * (5-6)), um sicherzustellen, dass sie auch für ihn funktionieren.Jetzt müssen wir nur noch die Aktionen implementieren, die von den Vorschlägen in Form von Code ausgeführt werden. Dies ist die Analyse des Ausdrucks mit der Methode des rekursiven Abstiegs. Bevor Sie jedoch mit dem Schreiben von Code beginnen, vereinfachen wir die Sätze ein wenig, indem wir die Rekursion in den ersten beiden entfernen.Wenn wir den ersten Satz endlos in sich selbst einsetzen, dann bekommen wirE -> T ± T ± T ± T ± ... ± T.
Der zweite Satz kann auf ähnliche Weise transformiert werden.T -> F * / F * / F * / * / ... * / F.
Tatsächlich bedeutet dies, dass wir hier anstelle einer Rekursion eine Schleife verwenden können. Ebenso kann eine Rekursion nicht aus dem dritten Satz ausgeschlossen werden.Wir werden den Code in Java schreiben, weil Dies ist momentan die bekannteste Programmiersprache für mich. Die letzte Bemerkung, bevor wir mit dem Schreiben des Codes beginnen - ich lasse die Aufgabe der Tokenisierung aus, d.h. Aufteilen des Ausdrucks in unteilbare signifikante Elemente (Token). Solche Token sind Zahlen, Zeichen von Rechenoperationen und Klammern. Angenommen, wir haben bereits ein Token-Array als Eingabe vom Ausdruck.String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};
Erstellen Sie die nächste Parser-Klasse, die die Methoden enthält- parse () beginnt mit dem Parsen eines Ausdrucks
- expression () zur Behandlung von Ausdrücken vom Typ E.
- term () zur Verarbeitung von Ausdrücken vom Typ T.
- Faktor () zur Verarbeitung von Ausdrücken vom Typ F und 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);
}
}
Das ist alles. Falls gewünscht, kann diesem Parser beigebracht werden, mit einem unären Minus oder Funktionen in einem Ausdruck zu arbeiten. Das erste, was zu tun ist, ist, die ursprünglichen Sätze so zu ändern, dass sie ein neues Element der Struktur des Ausdrucks berücksichtigen, und es kann weitere Vorschläge daraus geben. Sobald sie ordnungsgemäß geändert wurden, wird die Implementierung fast formal.