Parser - wie würdet ihr es machen?

[dizzy]

Ich bin jetzt drauf und dran mir einen Parser für mathematische Formeln zu bauen. Leider kann ich keinen fertigen Parser nehmen, da ich nicht einfach nur 1+2 rechnen will, sondern mit komplexen Zahlen, bzw. mit Quaternionen. Die einzelnen Rechenoperationen habe ich bereits in einer Unit fertig, und die laufen. z.B.: addQ(Q1, Q2), und es gibt das Ergebnis der Addition zurück. So sind die Funktionen alle aufgebaut.

Jetzt die Frage, wie ihr am ehesten Konzeptionell daran gehen würdet!? Ich habe keinen blassen Schimmer, wie man ansetzten sollte. Baumstruktur, Listen, Rekursion etc.pp... was brauch ich, was ist sinnvoll, wie kann man es so performant wie es nur geht (wichtig!) umsetzen, dass ich einen String der Form:

Code:

z1 = z0^2 + c

so umsetzte, dass es im Programmcode etwa so ausgeführt würde:

Code:

z1 := addQ(sqrQ(z0), c);

Großes:


Bin dankbar für jede Hilfe!

Schönen Gruss,
dizzy

[Ghostwalker]

hmmmmm...also direkt kann ich dir nicht helfen.

Aber vielleicht ein paar Sachen die dir trotzdem Helfen:


a) Rekursionen vermeiden wenns um die Geschwindigkeit geht, da eine Iteration schneller abgearbeitet wird.

b) Zum Zerlegen des Ausdrucks würd ich versuchen Reguläre Ausdrücke zu verwenden. Das geht relativ einfach und schnell. Zum Glück gibts entsprechende Komponenten/Units auch für Delphi.

c) Versuch statt Abfragen/Case's Array's zu indizieren.

Bsp. Opereatoren die mit 2 Werten arbeiten

Statt

Code:

            Case Operator of
                   '+' : Add(w1,w2);
                   '-' : Sub(w1,w2);
                    :
                    :

Wie folgt:

Code:

              Type TFunktion = function(w1,w2:double):double
              var fktarr=array[ord('+')...ord('-')] of TFunktion
                    :
              //Jetzt belegen
              fktarr[ord('+')] := @add;

              //Anwenden
              fkt:= fktarr[ord('-')];
              erg:=fkt(w1,w2);

Hoffe das hilft dir zumindest etwas weiter

[dizzy]

Also das mit dem Array find ich ja schonmal obergeil
Da wär ich so schnell nicht drauf gekommen! Danke schon mal!


Aber wie klamüser ich einen String auseinander, unter Berücksichtigung von Klammersetzungen und "Potenz-vor-Punkt-vor-Strichrechung"? Und wie hinterlege ich das bestenfalls, so dass das Abrufen dann "sehr" schnell von statten gehen kann? Für jeden Rechendurchlauf den String erneut parsen wäre tödlich, da es um die Berechnung von Fraktalen geht. Ein Fraktal mit einer Auflösung von 256*256 Pixeln erfordert dann schon 65536 Rechendurchläufe. Und ich will's zudem 3D, also dann sogar Auflösung^3 Durchläufe...


Danke,
dizzy

[Robert Marquardt]

Erst mal musst du die Syntax fuer die Notation der komplexen Zahlen bekanntgeben.
Jenachdem kann der Parser schwierig bis unmoeglich werden.

Ueblicherweise zerlegt man den String erst in Token.

"z1" "=" "z0" "^" "2" "+" "c"

Darauf setzt dann der eigentliche Parser auf. Gegen Rekursionen ist nicht einzuwenden.
Ich kannte mal einen Algorithmus der Klammerausdruecke elegant verarbeitete und gegen fehlende Klammern resistent war.
Ein klassischer rekursiver Algorithmus.

[dizzy]

Also die Notation ist denkbar einfach: Komplexe Zahlen kommen in dem Ausdruck erst garnicht direkt vor. Mann soll sich nachher 5 Variable komplexe Zahlen (C1..C5) vordefinieren können, und diese werden dann als "C1" usw. in den Ausdruck geschrieben. Einziges Problemchen: Man soll die Möglichkeit haben wahlweise nur "normale" Zahlen zu benutzen, die wie komplexe behandelt werden (Imaginärteil = 0), oder aber eine vordefinierte.
Es soll also gehen:

Code:

z1 = z0^2

oder:
C1.real = 2
C1.img  = 0

z1 = z0^C1

Unter Umständen kann man die Unterstützung für normale Zahlen (bsp. 1) weglassn, und alles über die Variablen machen. Und den Algo, den du da ansprichst, *lechtz* wo, wie, wer... wie heisst denn der?

Aber ich hab noch immer keine Idee, wie es Strukturell aussehen sollte/könnte.

Danke und Gruss,
dizzy

[dizzy]

Sooooo, ich habe jetzt einen funktionierenden Parser! *froi*

Den habe ich aber auch nur mit Hilfe von hier bauen können. An dieser Stelle einen riesen Dank an Herrn Mohr für diesen einfachen, verständlichen, und ausserdem unglaublich einfach an meine Bedürfnisse anpassparen Parser! Klasse! Damit, und mit meiner Vorarbeit des Schreibens der Rechenoperationen in der Form "Ergebnis := Operation(x, y)" war es eine Sache von wenigen Minuten (grundlegendes Verstehen der Arbeitsweise des Parsers inbegriffen) es so umzubauen, das es passt. Zwar blicke ich das Teil noch nicht ganz, aber ich bin nah dran

Jetzt kommt aber das dicke ABER! Der ist bei einer ganzen Reihe von Berechnungen natürlich super-langsam, da der Formel-String jedes Mal neu geparsed wird, obwohl sich die Struktur nie ändert, sondern nur die Variableninhalte.
Ich müsste jetzt also eine Möglichkeit finden, die Informationen aus dem geparsten String so zu hinterlegen, dass sie super-performant wieder abrufbar sind.
Hat da zufällig einer einen heissen Tip parat?
Hab ja schließlich nicht meine Rechenfunktionen zum Teil mit Assembler hand-optimiert, damit mir ein Parser die ganzen Geschwindigkeitsgewinne wieder ad absurdum führt .

An der Array-Sache muss ich mal rumdoktorn, aber erst morgen (das ist ja schon in Kürze... ).
Bin aber für andere Ansätze nach wie vor absolut offen!


Habt Dank,
ein glücklicher und müder dizzy


\\die ganzen Edits: Um 4 Uhr morgens macht man Rechtschreibfehler. Sonst ist was falsch

[Robert Marquardt]

Was ein Parser macht, ist das er einen Baum des Ausdrucks erstellt.
Das ist ueberall so. Z. B. beim DOM von XML wird der Baum zugreifbar gemacht.
Behaelt man den Baum dann hat man was man braucht.
Der Baum wird abgearbeitet was dem Interpretieren eines Programmes entspricht.
Eine Variable ist ein Knoten im Baum. Der Inhalt der Variable ist ein Attribut des Knotens.

Damit habe ich kurz umrissen was an der Uni unter "kontextfreie Grammatik", bzw. "Attributgrammatik"
laeuft und zum Compilerbau gehoert.

[dizzy]

*gruks*, okay, dann sehe ich mal zu, dass ich meinem Studium vorweg-renne. Dieses Thema dürfte nämlich bald kommen

Dann mach ich mich mal dran. Danke für den Stupser!

gruss,
dizzy

[pirechner]

@ dizzy
Mich interessiert das Thema auch sehr und darum war ich sehr enttäuscht als der angegebene Link nicht funzte. Ausversehen vertippt oder macht T-online wieder die Schotten dicht?

Was sind das eigentlich immer für Bäume, da schnappt man immer wieder was drüber auf und versteht/kennt es aber nicht?

[LarsMiddendorf]

Ich verweise mal auf diesen Post:
http://www.delphipraxis.net/internal...=201967#201967

Hatte da mal ein Klasse gemacht, die den Ausdruck intern in Maschinencode umwandelt.