Hi Leute^^

Mich überkam mal wieder die Lust, was neues zu programmieren, das auch nicht zu einfach ist.
Und so bin ich drauf gekommen, mir nen Mathe-Parser zu basteln.

Ich hab auch schon gegoogelt und bin auf verschiedene Anstöße gekommen:
Iterative Parser, rekursive Parser, UPN-Parser, Parser mit Stack usw.
Hab mir auch schon diverse PDFs und andere Seite angeschaut, abe rda war irgendwie nix weiter interessantes dabei, das nicht irgendwie Parser-Generatoren o.Ä. verwendet hätte

Aber jetzt meine Frage: Wie würdet ihr das angehen?
Ich hab sowas noch nie gemacht, von daher bin ich praktisch auf eure Hilfe angewiesen

Mir kommts erstmal überhaupt nicht auf Geschwindigkeit an, sondern darauf, dass er erstmal das wesentliche beherrscht: +-*/ (inklusive Punkt-vor-Strich-Regeln) und Klammersetzung, nach dem Motto "FIRST make it work, THEN make it fast"

Ich hoff mal, ihr könnt mir bei dem Thema helfen

Erste Anlaufstelle: die FORENSUCHE. Einfach mal nach PARSER suchen - gibt es einige hier im Forum.

AXMD

Die Forensuche hab ich schon oft verwendet, hat auch oftmals geholfen bei diversen anderen Problemen.
Allerdings fand ich eigentlich nur fertige Units für Parser.
Ich wollte aber mal wissen, wie man/wie ihr sowas angeht/angehen würdet

Wohl eher gar nicht; schon die String-Zerlegung zu programmieren, wäre mir persönlich viel zu aufwändig!

Das wichtigste ist, die Struktur zu erkennen - wo sind Operatoren, wo Variablen/Zahlen. Dann die Struktur nach Operatoren-Wertigkeit sortiert in einem Baum einbauen. Und dann (wenn sich der Baum fehlerfrei aufbauen lies) den Baum lösen.

Das alles selber zu machen, wäre "Eulen nach Athen tragen", oder "das Rad neu erfinden", oder ... - na, du verstehst: Wozu sich wochenlang den Kopf zerbrechen, das andere über Monate hinweg schon perfektioniert haben?

In den JEDI-Bibliotheken müsste bereits was enthalten sein:

sourceforge.net/projects/jcl + sourceforge.net/projects/jvcl

Öhm, Danke LigH
Aber das war eine der Antworten, die ich eher nicht hören wollte

Ich weiß, dass es vermutlich viel Arbeit sein wird
Ich brauch den Parser ja auch nicht für ein Projekt, ich will das einfach nur ma gemacht haben
Stichwort Lerneffekt

Trotzdem danke, wenn ich mal nen Schnellen brauch, dann schau ich in die JCL

Das hab ich mir eines Tages auch gesagt und dabei ist die Unit tyParser.pas rausgekommen.

Eine Erklärung zur verwendeten Methode findest du hier.

Jedoch basiert die neuste Version von tyParser auf anderen (aber ähnlichen) Prinzipien.
Die Unit tyParser enthält übrigens auch einen Compiler, welcher einen Stringausdruck in eine direkt ausführbare Funktion umwandelt.

Das ganze wurde gänzlich von Hand geschrieben.

PS: Im DF hat es übrigens auch noch eine Handvoll andere Parsers. Die kannst du dir ja auch mal anschauen

So, mein Tipp: regular Expressions. Ein parsen mit Hilfe von Pos(), Copy, Delete() waere hier wohl glatter Selbstmord. Allerdings habe ich im Moment keine RegExp-Unit fuer Delphi (Infos gibts hier) installiert, also gibt es nur Pseudo- oder php-Code. Da ich dir keinen fertigen Code geben will () gibts Pseudo-Code. Erstens die Grundlagen:

1. Der Parser akzeptiert Variablen, die auch mehr als ein Zeichen lang sein koennen. Die Variablen duerfen aber ausschliesslich aus Kleinbuchstaben (a-z) bestehen.
   
2. Als Operationszeichen kennt der Parser die Grundrechenarten (+, -, *, /) sowie die Potenz (^)
   
3. Geklammerte Ausdruecke sind erlaubt, solange die Klammern geschlossen werden
   
4. Ausser diesen Zeichen duerfen natuerlich noch Zahlen sowie Spaces zur Formatierung verwendet werden.
   
5. Sollte was anderes auftreten, bricht der Parser einfach ab.

Hier noch die Referenz zu den einzelnen php-Funktionen die ich verwendet habe, ich denke dass es diese auch in den RegExp-Libs fuer Delphi gibt: preg_match_all(), preg_match(), preg_replace() und preg_split().

Bevor es losgeht, noch eine Kleinigkeit: ich erklaere hier nicht lange die Feinheiten der Regular Expressions. Diese duerft ihr selbst rausfinden

So, der Parser besteht aus drei Funktionen. Die beiden ersten sind relativ einfach:

• parse_expression() erwartet als Parameter den String mit der Expression, sowie ein Array mit den Variablen-Deklarationen. In php geht dies ja z.B. so: $ar['foo'] = 3. Da dies in Delphi nicht geht, musst du dir anders helfen, z.B. mit der Komponente fuer String-Indizierte Arrays. Was macht die Funktion? Einfach: mit einer Regular Expression werden alle Zeichen-Kombinationen rausgesucht, und durch den entsprechenden Array-Wert ersetzt. Die Regexp sieht dann so aus: #\b([a-z]+)\b#is. Diese Regexp findet eine mind. 1 Zeichen lange Folge der Buchstaben a-z, die von Wortgrenzen umgeben sind. Das wird in preg_match_all reingefuettert, zusammen mit der Expression. Dort gibts als Rueckgabewert ja die Anzahl Matches, also ersetzen wir alle gefundenen Elemente mit deren Wert. Ist kein Wert vorhanden, so nehmen wir einfach 0. In anderen Worten (php):
  
  markieren

  Quelltext
     

  1: 2: 3: 4: 5: 6:

  $varcount = preg_match_all('#\b([a-z]+)\b#is', $expr, $matches, PREG_SET_ORDER); for ($i = 0; $i < $varcount; $i++) {   $varname = $matches[$i][1];   $expr = preg_replace('#\b'. $varname .'\b#is', (isset($vars[$varname]) ? $vars[$varname] : 0), $expr); }

  
  Die Funktion gibt einen Integer zurueck, naemlich den Rueckgabewert von do_parsing(), welche spaeter noch deklariert wird.
  
• eval_expression(): Diese Funktion erwartet ein array mit 3 Elementen, wobei das erste und letzte Element eine Zahl, das zweite Element ein beliebiges Operationszeichen sein koennen. Zuerst werden diese Bedingungen geprueft. Der erste Teil kann in Delphi wahrs. entfallen, dieser ist nur da, weil php nicht typesafe ist. Nach der Pruefung ob es sich ueberhaupt um ein Array der Laenge 3 handelt, testen wir die einzelnen Teile, dies geschieht mit preg_match. Element 1 und 3 muessen Zahlen sein (Regexp: #\d+(\.\d+)?#), Element 2 eines der vorher festgelegten Op-Zeichen (RegExp: #(\+|\-|\*|\/|\^)#). Sobald das erledigt ist, fuehren wir einfach die gewuenschte Operation aus, welche anhand von Element 2 bestimmt werden kann. Das Ergebnis geben wir zurueck. Und da dies ein einfacher Code ist (case-of), gibts hier keinen Codeschnipsel
  
• do_parsing() schlussendlich ist das, worauf es ankommt. Diese Funktion erwartet nur einen String mit dem Rechenausdruck, in dem die Variablen bereits durch Zahlen ersetzt wurden. Jetzt gehts richtig los: zuerst werden Klammern aufgeloest. Also wiedermal preg_match_all, diesmal mit dieser regexp: #\((.*)\)#is. Anschliessend fuettern wir unseren ersten Match (also das was in der Klammer steht) wieder in do_parsing, und ersetzen den Ausdruck inkl. Klammern mit dem Rueckgabewert von do_parsing. Hier der Code:
  
  markieren

  Quelltext
     

  1: 2: 3: 4: 5:

  $matchcount = preg_match_all('#\((.*)\)#is', $expr, $matches, PREG_SET_ORDER); for ($i = 0; $i < $matchcount; $i++) {   $expr = str_replace($matches[$i][0], do_parsing($matches[$i][1]), $expr); }

  
  Aus diesem Rechenausdruck: 2+4*(52-4) wird also 2+4*48. Wie es dazu kommt, sehen wir gleich.
  
  Jetzt versehen wir jedes Einzelelement des Rechenausdrucks (also Op-Zeichen sowie Zahlen [nicht Ziffern]) mit einem Leerzeichen, vorne und hinten. Warum sehn wir gleich. Die Regexp sieht hier ein bisschen verwirrend aus, ist sie aber nicht: #(\+|\-|\*|\/|\^|\d+(\.\d+)?)#is. Hier der entsprechende php-Code:
  
  markieren

  Quelltext
     

  1:	$expr = preg_replace('#(\+|\-|\*|\/|\^|\d+(\.\d+)?)#is', ' \\1 ', $expr);

  
  
  Anschliessend ersetzen wir alle mehrfach hintereinander vorkommenden Leerzeichen mit einem einzigen:
  
  markieren

  Quelltext
     

  1:	$expr = preg_replace('# {2,}#', ' ', trim($expr));

  
  Das {2,} bedeutet in diesem Fall "mind. 2 mal". Das trim() schneidet dabei alle "aussenstehenden" Leerzeichen ab.
  Nun sieht unser Rechenausdruck von vorhin schon so aus (der Klammmernausdruck wird der Einfachheit halber direkt ausgewertet, aber nur in der Erklaerung ): 2 + 4 * 48
  
  Jetzt kommt der richtig lustige Teil:
  Wir spalten unseren Rechenausdruck in einzelne Teile, und zwar immer am Leerzeichen. Dieses teilt ja jeden einzelnen Ausdruck. Dazu wird preg_split() mit folgender regexp verwendet: # #. Die einzelnen Teile landen alle in einem Array, welches also folgende Zeichen enthaelt:
  
  markieren

  Quelltext
     

  1: 2: 3: 4: 5:

  2 + 4 * 48

  
  
  Anschliessend prueffen wir folgende Bedingungen:
  
  • Das erste und letzte Zeichen muessen Integers sein. Das Pruefen auf Integer mittels preg hatten wir ja schon
    
  • Die Anzahl der Elemente ist ungerade. Der Grund ist einfach: jedes Rechenzeichen muss von 2 Zahlen umgeben sein, sonst haben wir einen ungueltigen Ausdruck.
  
  Trifft eine der beiden Bedingungen nicht zu, gehts raus. Anschliessend kommt ein kleiner "Speedhack" (und Bugfix *g*): wenn nur ein Element im Array ist, geben wir diesen Wert gleich zurueck. Sonst wuerde diese Rechnung einen Fehler ergeben, da im naechsten Schritt mind. 3 Elemente da sein muessen: 2+(4)
  
  Anschliessend initialisieren wir unsere Rueckgabevariable (ich nenne sie Value) mit dem ersten Array-Element, warum wird gleich rauskommen. Im naechsten Schritt laufen wir mit einer Schleife, welche bei 1 beginnt, natuerlich innerhalb der Array-Grenzen bleiben muss, und in jedem Schritt um 2 erhoeht wird, ueber das Array mit den einzelnen Elementen. So sprechen wir Elemente mit ungeradem Index an, was in unserem Fall die Op-Zeichen sind. Nun pruefen wir auf die folgenden Bediungungen:
  
  • Das aktuelle Rechenzeichen ist *, / oder ^
    
  • Das aktuelle Rechenzeichen ist + oder -, aber es gibt kein weiteres Rechenzeichen mehr
    
  • Das aktuelle Rechenzeichen ist + oder -, ebenso wie das folgende
  
  In diesem Fall weisen wir value den Rueckgabewert von eval_expression zu, welche mit folgenden Parametern aufgerufen wird: value, dem aktuellen Rechenzeichen, und der naechsten Zahl, also dem naechsten Array-Element.
  
  Die Faelle die ich oben geprueft habe, sind nur gueltig, wenn die Punkt-vor-Strich-Regel nicht gilt. Falls wir aber ein + oder / haben, und das naechste Rechenzeichen ein *, / oder ^ ist, so wird es etwas komplizierter. In diesem Fall werten wir erstmal den naechsten Ausdruck aus. Eine temp-Variable bekommt also den Wert von eval_expression() mit den folgenden Parametern zugewiesen: Die naechste Zahl, das naechste Op-Zeichen, die uebernaechste Zahl. Anschliessend weisen wir value das Ergebnis von eval_expression mit folgenden Parametern zu: value, das aktuelle Op-Zeichen, und dem Wert unserer Temp-Variable. Anschliessend inkrementieren wir die Laufvariable um 2 (zusaetzlich zu den 2, die in jedem Durchlauf addiert werden, damit die naechste Operation, welche ja soeben bereits durchgefuehrt wurde, uebersprungen wird. Tja...und sobald die Schleife zu Ende ist, gibt die Funktion den Wert von value zurueck, und gut is.

So, und nachdem das jetzt viel Theorie war, gibts erstmal Praxis. Gegeben sei folgender Ausdruck: 2+  a*(b^4 -2)- 6/3
a ist in dem Fall 5, b ist 2.
Man beachte die mehrfachen Leerzeichen, die ich reingebaut habe.

• Aufruf von parse_expression('2+  a*(b^4 -2)- 6/3', vararray);
  Jetzt werden alle Variablen ersetzt, der Ausdruck sieht also so aus: 2+  5*(2^4 -2)- 6/3
  
• Jetzt sind wir in do_parsing('2+  5*(2^4 -2)- 6/3'). Wir pruefen auf Klammern und finden (2^4 -2)
  
  • Rekursiver Aufruf von do_parsing('2^4 -2') (Klammern werden nicht mituebergeben).
    
  • Wir finden keine Klammern, weiter im Programm.
    
  • Wir fuegen vor und hinter jedem Element ein Leerzeichen ein, der Ausdruck sieht nun so aus:  2  ^  4   -  2
    
  • Mehrfache Leerzeichen werden rausgeworfen: 2 ^ 4 - 2
    
  • Der String wird gespalten, wir haben ein Array mit folgenden Elementen:
    markieren

    Quelltext
       

    1: 2: 3: 4: 5:

    2 ^ 4 - 2

    
    
  • Unsere Pruefungen passen, das Array ist laenger als 1 Element, also parsen wir das Ding durch. Unsere Laufvariable ist i, in matches stehn die einzelnen Teile drin.
    
  • Value wird auf 2 gesetzt.
    
    • i ist 1, das Zeichen an der Stelle ist ^, also werten wir den Ausdruck aus: eval_expression(2, ^, 4). In Value steht jetzt 16.
      
    • Das naechste Zeichen ist -. Nachdem es nachher kein Op-Zeichen mehr gibt, koennen wir wiederum gleich auswerten: eval_expression(16, -, 2). Value ist nun 14, die Schleife ist zuende.
    
    
  • Wir geben den Wert von Value zurueck: 14.
  
  
• Der Rueckgabewert vom Klammernausdruck wird statt dem Ausdruck selbst eingesetzt, also sieht der gesamte Ausdruck jezt so aus: 2+  5*14- 6/3
  
• Das Spiel geht weiter, diesmal ein kleines bisschen Schneller: nach der Leerzeichenspielerei sieht der Ausdruck so aus: 2 + 5 * 14 - 6 / 3
  
• Wieder splitten wir, und erhalten folgendes array:
  markieren

  Quelltext
     

  1: 2: 3: 4: 5: 6: 7: 8: 9:

  2 + 5 * 14 - 6 / 3

  
  
• Also, pruefen...ok. Array ist laenger als 1 Element, also Laufvariable auf 1, value auf das erste Element (2).
  
  • Wir finden ein +, stellen aber fest, dass das folgende Zeichen ein * ist. Also werten wir erstmal den Ausdruck aus: eval_expression(5, *, 14). Den Rueckgabewert (70) schreiben wir in tempvalue.
    
  • Anschliessend koennen wir den folgenden Ausdruck ausfuehren: eval_expression(2, +, 70). Das Ergebnis (72) kommt in Value, und wir inkrementieren i um 2.
    
  • Value ist nun 72, i ist 5 (Standard-Inkrementierung plus die 2 von vorhin). Was finden wir? Ein -, aber wieder gilt Punkt vor Strich. Also wie vorhin erstmal eval_expression(6, /, 3) ausfuehren, und das Ergebnis (2) dann weiterverwenden: eval_expression(72, -, 2). Das Ergebnis (70) kommt in value, und wieder inkrementieren wir i um 2.
    
  • i ist nun groesser als die Anzahl Elemente im Array, also brechen wir ab.
  
  
• Wir geben den Wert von Value (70) zurueck.
  
• parse_expression() bekommt den Wert, gibt ihn zurueck, und fertig ist die Rechnung: 2+  a*(b^4 -2)-6/3 = 70

So, ich hab dir (Benutzername) doch gesagt, vor 3 gibts kein Ergebnis. Allerdings ist eine gute Stunde fuers Tippen des Beitrags draufgegangen. Deshalb: danke fuers Lesen. Ich hoffe ihr versteht meine Ausfuehrungen wenigstens ein bisschen, und bei Fragen: nur her damit. Und wer einen Blick auf den Code (php) werfen will, kann sich per PN an mich wenden, und vielleicht habe ich morgen (oder eher heute) Lust, das ganze noch in Delphi zu schreiben

Greetz
alcaeus

Edit: Regexps fuer Reelle Zahlen angepasst

So, und nachdem dieses lange Posting so schoen war, gibts heute Abend noch eins. Ich hab soeben das Delphi-Beispiel fertiggestellt, hab aber im Moment keine Lust, es zu erklaeren. Das kommt heute um 2 Uhr nachts

Greetz
alcaeus

Auf jeden Fall schonmal Danke
Aber heut nacht um 2 is schon seit etwa 10 Stunden vorbei

In einem alten Turbo-Pascal Buch (so alt ist es auch noch nicht) haben sie einen Parser so programmiert, das die Funktion im Hauptprogramm eingegeben wird, die dann in einen Quelltext integriert wird, der kompiliert wird. Dieser überschreibt eine Dummy-Methode im Hauptprogramm. Nun kannn das Hauptprogramm die eingegebene Funktion nutzen, als hätte sie schon beim kompilieren im Quelltext gestanden.

P.S.:Wozu einen Mathe-Parser programmieren, wenn man schon einen im Kompiler eingebauten hat?

P.P.S.: eventuell geht das mit dem ersetzen der Dummy-Funktion nicht mehr unter Delphi. Dann müsste man die Ausgabe des Ergebnisses im dynamisch generierten Programm vornehemen.

jakobwenzel hat folgendes geschrieben:

In einem alten Turbo-Pascal Buch (so alt ist es auch noch nicht) haben sie einen Parser so programmiert, das die Funktion im Hauptprogramm eingegeben wird, die dann in einen Quelltext integriert wird, der kompiliert wird. Dieser überschreibt eine Dummy-Methode im Hauptprogramm. Nun kannn das Hauptprogramm die eingegebene Funktion nutzen, als hätte sie schon beim kompilieren im Quelltext gestanden. P.S.:Wozu einen Mathe-Parser programmieren, wenn man schon einen im Kompiler eingebauten hat? P.P.S.: eventuell geht das mit dem ersetzen der Dummy-Funktion nicht mehr unter Delphi. Dann müsste man die Ausgabe des Ergebnisses im dynamisch generierten Programm vornehemen.

Mich würde interessieren, wie der Quelltext dazu aussieht. Könntest du den uU mal posten?

AXMD

Die .bgi und .chr Dateien sind für den Grafikmodus. Funktion.exe/.pas ist das Hauptprogramm, hilfprg.exe/.pas das Hilfsprogramm. Das Programm braucht den Borland Pascal-Compiler TPC.exe im gleichen Verzeichnis. Da ich nicht weiß ob das Programm inzwischen Freeware ist, habe ich es weggelassen. Das Programm hat den Runtime-Error 200 Bug auf PC mit >150 MHZ Prozesor. (Hat ja inzwischen fast jeder so einen) Deshalb braucht man das Programm "PC-Bremse" (www.lrz-muenchen.de/...klein/downloads.html, 3. Programm von oben) benutzen. Ich musste bei meinem Rechner auf 75% gehen (1.5 GHZ).

Mist, Datei vergessen... Hier ist sie...

Moderiert von raziel: 32 mal entfernt.

jakobwenzel hat folgendes geschrieben:

Das Programm hat den Runtime-Error 200 Bug auf PC mit >150 MHZ Prozesor. (Hat ja inzwischen fast jeder so einen) Deshalb braucht man das Programm "PC-Bremse" (www.lrz-muenchen.de/...klein/downloads.html, 3. Programm von oben) benutzen. Ich musste bei meinem Rechner auf 75% gehen (1.5 GHZ).

gibt auch einen patch für kompilierte programme: CTBPPAT, ausserdem ein update für die crt.tpu, damit neue progs den fehler nicht mehr haben

Ich glaube, so einen Patch habe ich schon drauf, das Programm habe ich dann wohl auf meinem alten PC (150 MHZ) kompiliert.

jakobwenzel hat folgendes geschrieben:

Ich glaube, so einen Patch habe ich schon drauf, das Programm habe ich dann wohl auf meinem alten PC (150 MHZ) kompiliert.

der patch ctbppat patcht fertigt kompilierte programme. dadurch funktionieren diese auf jedem system einwandfrei.
der fix patcht gleich die verantwortlichen dateien in der TP installation, so dass der fehler in neu kompilierten .exe'n gar nicht drin ist.

Ich meinte das Update für die crt.tpu

Ich habs mal jetzt nicht runtergeladen, aber ich hab auch schonmal Überlegungen angestellt, dass man kompilietren Code "einfach" austauscht.
Aber das scheint mir nicht sehr sauber zu sein

Das Hilfsprogramm kopiert den Maschinencode der Funktion in einen der "unteren" Speicherbereiche, die, zumindest unter DOS (bzw. "Das 16-Bit Teilsystem" unter XP) jedes Programm auslesen kann. Das Hauptprogramm überschreibt seine Dummy-Funktion nur im Speicher mit dem neuen Code, der dann anstatt der Dummy-Funktion aufgerufen wird. Die Dummy-Funktion muss halt länger als die richtige Funktion sein, sonst werden andere Funktionen überschrieben.

Wahrscheinlich funktioniert ein Teil dessen, was unter DOS so wunderbar geht, unter Windows mit Delphi nicht mehr.

Der Vorschlag mit Regular Expressions ist nett, würde ich persönlich aber nicht empfehlen.

Normalerweise besteht ein Parser aus einer Komponente, die den Text in "Atome" (oder Tokens) zerlegt (Lexer) und einer Komponente, die die Tokens dann auswertet. (In meinem Parser ist das ganze zwar nicht so klar getrennt aber egal)

Der "Suchen und Ersetzen"-Ansatz ist meiner Meinung nach langsam, kompliziert (deswegen fehleranfällig) und nicht universell einsetzbar (man denke an Fälle wie: "1 - (-1) + 2e-1" (wobei 2e-1 = 0.2)).
Ausserdem sollte man meiner Meinung nach nicht am Ausdruck selbst arbeiten. Der Parser sollte sich den String anschauen und den genau so interpretieren, wie er da steht. Im Idealfall sollte sich der Parser einen Baum generieren, welcher er dann noch optimieren kann. Aus diesem Baum ist es dann relativ einfach möglich, einen Bytecode oder direkt Maschinencode zu generieren. Das beschleunigt die Auswertung ganz entscheidend.

Last but not least: Man sollte sich bei Parsern zuerst eine Grammatik definieren (z.B. in EBNF). Spätestens wenn du kompliziertere Sachen drin hast sind alle anderen Ansätze unmöglich zu implementieren. Mit EBNF kannst du ganze Programmiersprachen (Delphi, Java, etc.) definieren. Mit Regular Expressions kommst du da nicht sehr weit... Ausserdem würde ich bezweifeln, dass du es mit RegExp schaffst, eine halbwegs sinnvolle Fehlermeldung zu generieren, wenn was schief läuft.