Parsing ist die englische Bez für "grammatisch Zerlegen" oder "analysieren".

Der Begriff spielt gerade in der Informatik eine entscheidene Rolle im Bereich

der "Gramatiken" und den daraus syntetisierten Sprachen.

Z.B. zählen auch Kompiler zu Parsern, die über Grammatiken erzeugte Sprach-Syntax

prüfen und entschlüsseln können.

Ein Math-Parser hat nun im Speziellen die "Analysierung" eines mathematischen

Ausdrucks als Aufgabe.

(Die Berechnung des Ausdrucks soll zunächst einmal nicht in die Betrachtung

mit hineinfallen - obwohl sie doch das eigentliche Ziel darstellt.)

Als Beispiel für mathematische Ausdrücke könnte man z.B. :

3 Plus 4

5 Minus 6

zehn geteilt duch 8

fünf hoch 3 und das Ergebnis plus eins

(5+3)/2

Sicherlich werden Sie nun überrascht sein, hatten Sie doch eigentlich nur mit dem

letzen Beispiel gerechnet... dennoch können all diese Beispiele mathematische Ausdrücke

darstellen.

Hier fällt einem jedoch ins Auge, was ide erste Überlegung sein sollte, wenn man einen

Parser entwirft:

Zunächsteinmal müssen wir uns über die Grammatik einige werden, die unserem Math-Parser

zugrunde gelegt werden soll.

Natürlich entscheiden wir uns für eine Grammatik, aus welcher wohl das letzte Beispiel

entstanden sein könnte, da sie uns am geläufigsten ist und am wenigsten zu Fehliunter-

pretationen von den späteren Benutzern unseres Parser führt.

Jedoch müssen wir auch hier einige Besonderheiten gleich festhalten.

Da es sich bei unserem Expression-String um eine Zeichenkette handelt, müssen wir wohl oder

über auf Bruchstriche verzichten. Auch können wir nicht wie gewohnt die Exponenten 

schreiben.

Dafür hat die folgene Schreibweise eingebürgert:

        y                        ___
x^y = X       oder    x^(1/2) = V x |  (Wurzel aus x)

Somit können wir durch entsprechende Klammerung sowie durch Anwendung von Potenz-

regeln, jeden ''herkömmlichen'' mathematischen Ausdruck ein eine äquivaltene Zeichenkette

(im folgenden Expression genannt) umformen. Die Äquivalenz ist zur Zeit noch eine

rein gedankliche Wunschvorstellung, die es erst gilt in unserem Parser umzusetzen.

Nun haben wir uns also gedanklich oder evtl auch schon skizzenhaft auf

dem Papier eine Vorstellung von unserer Grammatik gemacht, die wir verwenden möchten.

Der nächste Schritt ist, sich über die Einzelheiten der Grammatik im Klaren zu werden.

Hierbei könnte man gemäß der BNF-Notation genaue Ausführungen über Nonterminale

und Terminale machen.

Ich möchte jedoch aus Gründen der Einfachkeit nicht weiter auf diese eingehen und

eine andere Gliederung vornehmen, die natürlich nur für unseren Math-Parser zutrifft:

Im Prinzip gibt es 4 grobe "Bausteine" für unseren Parser: (Sie werden sehen, daß

es später eine vielzahl untergeordneter Bausteine geben wird, die es dann heißt

zu verifizieren bzw zu evaluieren.)

- allgemeine Zahlen/Konstanten/Variablen

- Rechenoperatoren

- Bindungsoperatoren

- Funktionen

Auch wenn nicht ganz normgerecht, halte ich diese Aufteilung für sehr zweckmäßig.

In unserer Parser(klasse) wollen wir die folgenden Bausteine im Speziellen betrachten:

- Dezimalzahlen, Konstante pi und e, Variable x

- +, -, *, /, ^

- )(

- sin, cos und tan

Nun wird er ernst!

Prinzipiell werden wir das Parsing über einen Binärbaum implementieren, bei dem

jeder Knoten ein Operator oder eine Funktion ist und jedes Blatt eine Dezimalzahl

eine Konstante oder eine Variable darstellt.

Der Binärbaum wird über eine rekursive Funktion implementiert, die je nach

Bindungsstärke des Operators, dein bindungsscgwächsten zuerst in einen Knoten schreibt

und die übrigen Terme links und rechts des Operators in die untergeordneten Zweige

verteilt und mit ihnen genau so forgeht, bis letztendlich eine Zahl eine Konstante

oder eine Variable im Blatt übrigbleibt.

Elementar ist nun also eine Funktion, die entscheidet, welcher Operator

der bindungsschwächste ist. Dafür müssen wir eine Funktion implementieren,

die die Operatoren sowie Klammerebene berücksichtigt und uns z.B. 

aus der Expression:

(3+4)*5

folgende Rückgabewerte liefert:

bindungsschwäschster Operator = ''*''

restlinks = ''3+4''

restrechts = ''5''

Nun sehen Sie an diesem einfachen Beispiel, daß der Baumursprung (Root)

den Operator ''*'' als Wert zugewiesen bekommt.

Für die anderen beiden Werte sehen wir schon, daß wir eine neue Funktion

benötigen:

Gesucht ist eine Funktion die uns aus dem Wert des Blattes oder Knotens

bestimmt ob es sich um ein Blatt oder um einen Knoten handelt. 

Beispiel :

bool IstBlatt(String Input)

{

 if (Input.LowerCase() == "pi") return true;

 ...

 try {

   double z = Input.ToDouble();

   String VGLInput = z;

   if (VGLInput == Input) return true;

 }

 catch (Exception &exception) {}

 return false;

}

Diese Funktion überprüft nun anhand eines generierten Vergleichstrings,

ob, Input eine Zahl ist oder nicht.

Außerdem müssen wir hier schon berücksichtigen, daß wir für Funktionen,

Konstanten und Variablen ein true zurückgeben.

Diese Funktion würde im Beispiel ''3+4'' ein false zurückgeben

und uns signalisieren, daß wir nun mit dem Wert ''3+4'' als linken Unterbaum

genauso zu verfahren haben wie bei der gesamten Expression.

Der linke Unterbaum besteht jedoch (unsere Funktion IstBlatt(''5'') liefert

uns true zurück) nur aus einem Blatt mit dem Wert ''5''.

Die Rekursive Funktion wird jedoch erst ''3+4'' überprüfen und

nun wieder einen bindungsschwächsten Operator (nämlich +) herausfiltern

sowie restlinks = 3 und restrechts = 4.

Damit erhalten wir folgenden Binärbaum:

                      (*)

                     /   \

                   (+)   (5)

                  /   \

                (3)   (4)

Wenn diese Baum steht, ist das Parsing abgeschlossen und man kann sich an die Berechnung 

machen.

Auch diese wird wieder über eine rekursive Funktion implementiert,

die bis zur ersten Zahl/Variable/Konstanen (also einem Blatt) vorgeht

und dieses als Wert zurückgibt.

Da sie rekursiv implementiert wurde, prüft die aufrufende Instanz immer,

ob die aufgerufene ein Blatt zurückliefert.

Ist dies der Fall, wird die entsprechende mathematische Operation

ausgeführt, ansonsten wird in der aufgerufenen Instanz weiter verzweigt, bis ein

Blatt gefunden wurde.

In unserem Beispiel würde z.B. zuerst die 3+4 = 7 berechnet, die 7 würde wiederum

als Rückgabeweit der rekursiven Funktion dienen und auf der Ebene mit dem Operator

* mit der 5 verknüpft werden. Das Ergebnis wäre 35. Dieses lieg logischerweise

als String vor, da wir unsere Expressions nur als String übergeben konnten und

muß noch in eine Zahl umgewandelt werden.

Wichtig ist, daß die Rekursion in der gleichen reihenfolge (erst links, dann rechts)

durchgeführt wird.

Ein Tip für die Trigonometrischen Funktionen:

Impelmentieren Sie zunächst eine Filterfunktion, die einen Expressionstring der Form

4+sin(3*(x+1))

in die Form

4+s#(3*(6+1)) bringt.

Damit haben Sie die Möglichekeit die Funktion (die ja nicht wie ein Operator zwei

Parameter benötigt, in einen operator # umzuwandeln, der dann s#18 berechnet.

Bei der Berechnung können Sie dann  wieder auf sin(18) zurückgehen und das Ergebnis

als String zurückgeben.

Ich hoffe Ihnen hat die kleine Ausführung über den Bau eines Math-Parsers geholfen.

Ich wünsche Ihnen nun viel Erfolg bei Ihrer eigenen Impementation!

Christian Motika

copyright (c) 2001