Formelinterpreter, Programmierbarer Tabellenrechner

[Dipl Phys Ernst Winter]

Interpreter für anwenderdefinierte Funktionen
Die Unit Formel exportiert:

Delphi-Quellcode:

type
  TPar = array[0..9] of extended;
function FWert(FStr: string; const P: TPar): extended;     // Formelinterpreter

Verwendung:
Der Anwender übergibt dem Programm eine Formel als Text mit einer Reihe von Parametern vom Typ extended. Mit dem Interpreter berechnet das Programm Werte dieser Funktion.

Die Formel ist wie ein arithmetischer Ausdruck in Objekt-Pascal zu schreiben. In der Formel sind als Operanden zugelassen:
- Die Variable x
- Die Parameter a, b, c, d, w
- u für cos(w), v für sin(w)
- x^n als Potenz von x mit ganzzahligen Exponenten n=0..9.
- Zahlenkonstanten (Dezimalzahlen, Gleitkommazahlen )
- Die Konstante PI = 3.14159265358979
- Geklammerte Ausdrücke: '( Ausdruck )'
- Standardfunktionen mit einem Ausdruck w als Argument
-- ABSw)
-- INT(w)
-- FRAC(w)
-- SQR(w)
-- SQRT(w)
-- EXP(w)
-- LN(w)
-- SIN(w)
-- COS(w)
-- ARCTAN(w)

Zwischen zwei Operanden muß ein Operator stehen:
'*', '/' Multiplikation, Division mit Vorrang vor Addition und Subtraktion ausgeführt.
'+', '-' Addition, Subtraktion

Ein '+' oder '-' kann als monadischer Operator vor einem Ausdruck stehen.

Zwischen Operanden und Operatoren können Leerzeichen stehen.
Kommentare nach einem ';'

Fehlermeldungen:
'Doppelter Operator',
'Fehlender Operator',
'Fehlende Klammer',
'Überzählige Klammer',
'Fehler in Konstante',
'Fehlender Exponent',
'Illegale Funktionsbezeichnung',
'Illegale Variablenbezeichnung',
'Fehlendes Funktionsargument',
'Exponent von x^n keine Ziffer',
'Fehlender Operand',
'Syntaxfehler'.
Laufzeitfehler
'Division durch 0'
'SQRT mit negativem Argument'
'Ln mit negativem Argument'

Der Interpreter ist ein Musterbeispiel für die Leistungsfähigkeit rekursiver Programmierung. Er verwendet Rekursive Aufrufe zur Berechnung geklammerter Ausdrücke und der in Klammern stehenden Argumente von Funktionen.

Programmierbarer Tabellenrechner
Ich zeige die Anwendung des Interpreters am Beispiel eines programmierbaren Tabellenrechners.

Der programmierbare Tabellenrechner gibt nach Vereinbarung der Abszisseneinteilung, Formel und Parameter eine Tabelle mit Funktionswerten der analytischen Funktionen zu den äquidistanten Abszissen aus.


[edit=Matze]Tippefehler im Titel korrigiert ("Tabellenrwchner"), damit das Thema über die Suche leichter gefunden wird. MfG, Matze[/edit]

[Dust Signs]

Guten Morgen, Herr Winter!

Ich hätte einige Anregungen zu Ihrem Formelinterpreter. Über die Geschwindigkeit kann ich mir an dieser Stelle kein Urteil bilden - vielleicht hat ja irgendjemand hier Zeit, um einen Geschwindigkeitsvergleich mit Dax' Parser anzustellen. Zu Ihrem Parser:
* Hat es einen besonderen Grund, dass nur Ziffern als Exponenten erlaubt sind? Selbstverständlich lässt sich x^x in exp(x*ln(x)) umschreiben, doch wäre x^x eine weit kürzere Schreibweise - und da der Potenzoperator ja ohnehin vorhanden ist könnte er doch erweitert werden
* Mir scheint als würden die Negation und die Subtraktion (unär und binär) bezüglich ihrer Priorität nicht unterschieden werden, was bei Ausdrücken wie 1/-x oder 1--x zu einem Syntaxfehler führt ("doppelter Operator"). Da das durch entsprechende Klammersetzung umgangen werden kann ist das allerdings kein Problem - es ließe sich vermutlich ohenhin darüber streiten, ob die Ausdrücke überhaupt syntaktisch korrekt sind (ebenso wie -x^-x). Meiner Meinung nach sind sie das, aber ich weiß nicht, wie streng die dem Parser zugrunde liegende Grammatik definiert ist und ob sie derartige Ausdrücke überhaupt erlaubt (e scheint so, als wäre das nicht der Fall)
* Die Euler'sche Zahl als Konstante wäre noch praktisch - so muss man nicht immer exp(1) schreiben, wenn man sie benötigt

Das Programm gefällt mir ansonsten sehr gut

Dust Signs

[mschaefer]

Lasst doch den HAM-Parser mal dagegen laufen. Beide Programme sind gut, da bricht sich ehedem keiner einen Zacken aus der Krone.
Vom Programmcode her gefällt mir die Unit gut, da sie dokumentiert ist. Das ist nicht selbverständlich. Also eine runde Sache !

Grüße // Martin

[himitsu]

OK, der Code hier ist zumindestens recht kurz und übersichtlich,
aber bei der Einrückung könnte man noch etwas aufräumen.

PS: bezüglich Geschwindigkeit:

Delphi-Quellcode:

until Pos(Zei,'0123456789')=0;
// entspricht
until not (Zei in ['0'..'9']);
// und enthält keine Char-To-String-Umwandlungen sowie kein großen String-Vergleich

und auch wenn du in der Formel alles kurz halten willst ... die Funktions- und Variablennamen könnte man dennoch etwas länger und aussagekräftiger gestalten (diese werden dann eh vom Compiler rauskompiliert)

[gammatester]

Hier mal eine konstruktive Kritik (bzw. Fehlerreport/Frage). Beim Progtabrechner liefert y=x^2^3 dieselben Ergebnisse wie y=x^2 ohne Hinweise auf Fehler oder so. Eigentlich wollte ich nur testen ob x^2^3 als (x^2)^3 oder als x^(2^3) geparst wird.

Ich glaube, die Implementation kommt mit x^y^z ohne Klammern nicht klar, liefert aber keinen Fehler.
Gammatester

[sirius]

Geschwindigkeit ist ja nicht alles. Hauptsache ein Algorithmus ist nicht unnötig zu langsam. Das ist hier nicht der Fall. Natürlich kann dieser Parser nicht mit HAM (soweit ich es von der Beschreibung kenne, getestet habe ich es nicht) mithalten. Wie Dax schon sagte, HAM produziert nach dem einmaligen Parsen direkt Bytecode bzw (ich nenne ihn) Opcode. Da dauert zwar das Parsen ein wenig länger, aber wenn man die Formel mehrmals verwendet macht sich da ein enormer Geschwindigkeitsunterschied bemerkbar. Durch den Bytecode steht die Formel nach dem Parsen nun einmal so im Programm, als hätte man die Formel direkt in Delphi vorm Compilieren eingetragen. Da kann kein anders gearteter Parser mithalten.

Ich habe mal kurz ein Vergleichsprogramm geschrieben. Allerdings ohne HAM sondern mit meinem eigenen Parser, der auch Opcode erstellt und mit diesem Parser hier ohne OpCode. Ich nenne meinen mal kurzerhand OpCode-Parser und den anderen TTR-Parser. Den von Herrn Winter nenne ich Formel-Parser (weil die Unit so heißt).
Meiner soll allerdings nicht in die CodeLib sondern ist hier nur zum Vergleich.

Bedienung:
Links ist das Bedienfeld. Dort kann man oben die Formel eingeben .Ich habe mal nur die Abhängigkeit von x als Laufvariable eingebracht. Darunter kommt dann das Intervall von wo bis wo und in welchen Schritten die y Werte berechnet werden sollen.
Dann kommen drei Pushbutton, welche den jeweiligen Parser starten (OpCode=>Meiner ; Formel=>H. Winter; TTR->aus verlinktem Tutorial)
Darunter sind zwei Radiobuttons. Da kann man auswählen, ob die Funktion im gegebenen Intervall gezeichnet werden soll oder nur eine Zeitmessung der Funktionsberechnung im gegebenen Intervall mit n Wiederholungen erfolgen soll. Die Wiederholungen sind nur dafür da, um die Streuung zu verringern. Die Zeitangabe im gelben Feld wird immer für den gesamten Vorgang angegeben. Das Zeichnen ist eigentlich nur zur Kontrolle, ob der Parser auch richtig rechnet.

Hier sieht man, dass mein Parser ab 5 Werten besser wird als der hier vorgestellte. Also wenn man die gleiche Formel für 5 verschiedene x verwendet liegt der OpCode vorn.
Das ist auch das, was Dax erwähnte.
Ansonsten kann ja jeder mal selber nachsehen. Der TTR liegt immer deutlich hinten. Das ist allerdings noch eine Frage des Funktionenumfangs.
------------------------------------------------------------- Soweit dazu. ..

Deswegen ist der hier vorgestellte Code nicht unbedingt schlecht. "GoTo-s" sind allerdings doch etwas veraltet. Naja, und die Einschränkungen bezüglich Exponentialrechnung sind auch eher ungewöhnlich. Ich weis jetzt nicht, was noch so fehlt.

[Dipl Phys Ernst Winter]

Dust Signs schreibt

Zitat:

Mir scheint als würden die Negation und die Subtraktion (unär und binär) bezüglich ihrer Priorität nicht unterschieden werden, was bei Ausdrücken wie 1/-x oder 1--x zu einem Syntaxfehler führt ("doppelter Operator").

In den Ausdrücken wie 1/-x oder 1--x ist das Vorzeichen von x wie ein Operator eingefügt, das führt natürlich zu einem Syntaxfehler. Richtig ist x mir einem negativen Wert zu belegen.

[Dipl Phys Ernst Winter]

Vielen Dank an Gammatester!

An y=x^2^3 habe ich nicht gedacht.

Es stimmt: Die Implementation kommt mit x^2^3 ohne Klammern nicht klar.

^n mit n 0..9 muß wie ein Operator behandelt werden, damit fehlt bei x^2^3 eine Fehlermeldung.

Nochmals vielen Dank, ich habe die Fehlermeldung 'Fehlender Operand' für aufeinanderfolgende Potenzierungen eingefügt.

[Jakob Ullmann]

Warum nicht lieber den "Bug" fixen?

Zitat:

^n mit n 0..9 muß wie ein Operator behandelt werden, damit fehlt bei x^2^3 eine Fehlermeldung.

Wie meinst du das? Das ^ ist doch genau wie +, -, *, / ein Operator und kann auch entsprechend behandelt werden.

[Dust Signs]

Zwei Anmerkungen hätte ich noch:

* 0^0 ist nicht 1, sondern undefiniert
* 2^(-1) ist nicht erlaubt. Die Fehlermeldung macht zwar insofern Sinn, als dass - keine Ziffer, aber -1 sehr wohl eine Zahl ist. Oder übersehe ich hier etwas?
* -1^2 ist nach meiner Interpretation 1, da das unäre Minus eine höhere Priorität hat als der Potenzoperator, d.h. der Ausdruck äquivalent zu (-1)^2 sein müsste anstatt zu -(1^2)

Dust Signs

[Mithrandir]

Zitat von Dust Signs:

* -1^2 ist nach meiner Interpretation 1, da das unäre Minus eine höhere Priorität hat als der Potenzoperator, d.h. der Ausdruck äquivalent zu (-1)^2 sein müsste anstatt zu -(1^2)

Da ist mein Taschenrechner (und ich btw auch) anderer Meinung. -1² ist -1.