Josef Lüth
Der rekursive Abstieg am Beispiel Matex erklärt.
Bei der syntaktischen Analyse werden die Token vom Parser in
einen Syntaxbaum (oder Ableitungsbaum) übertragen.
Dabei werden die Token der Reihe nach überprüft und es wird
für jedes Token ein Knoten (oder eng. Node) erstellt.
Die Knoten von Operation (wie Plus, Multiplikation…)
enthalten jeweils zwei weitere Knoten.
Zum Beispiel kann der Knoten Plus einen Knoten
Multiplikation, für den ersten Summanden
und einen Knoten Variable, für den zweiten Summanden, enthalten.
Beim Parsen werden zuerst die Plus- und Minusknoten, dann die
Multiplikations- und Divisionsknoten, dann die Potenzialrechnungsknoten und
zuletzt die Zahlen- und Variablen Knoten erstellt
![](data/image004.jpg)
Ein Syntax Baum (Beispiel:
3+x·y³)
Jeder Knoten wird einzeln in der Klasse Node gespeichert.
Der
Rekursive Abstieg
Nun wird der Rekursive Abstieg angewandt.
Ein praktisches Beispiel für den Rekursiven Abstieg ist der
„Jugend Forscht“ Wettbewerb.
Dabei ist das Ziel, einen Bundessieger (vereinfacht
dargestellt) zu ermitteln.
Damit dieser ermittelt werden kann, verlangt der
Bundeswettbewerb, dass sich jeder Landeswettbewerb für einen Sieger entscheidet.
Jeder der Landeswettbewerbe verlangt wiederum von seinen Regionalwettbewerben,
dass sich diese jeweils für einen Sieger entscheiden, dann werden die
Landessieger ermittelt.
Mit dieser Technik arbeit auch der Parser.
Hierbei sind die Knoten die Wettbewerbe, auch sie haben ein
Ergebnis zu ermitteln.
Die Knoten enthalten dafür die Methode evaluate, die das Ergebnis der
Operation, die Zahl oder die Variable zurückgibt. Für die Berechnung wird der
Evaluator aufgerufen.
Dieser Ablauf ist wie eine Kettenreaktion: Wenn man den
ersten Knoten berechnen lässt, lässt er das Ergebnis der zwei untergeordneten
Knoten berechnen und diese lassen wiederum das Ergebnis der unteren Knoten
berechnen… und so erhält man schließlich vom obersten Knoten das Ergebnis.
![](data/image005.gif)
Die Ergebnisse werden an den nächst höheren Knoten übergeben.
|