4 Komplexe Terme
Haben Sie eigentlich schon bemerkt, dass unsere Implementierung der Potenzen in bestimmten Situationen zu falschen Ergebnissen führt? Falls nicht, dann starten Sie doch einmal die letzte Version Ihres "TermInterpreters" und berechnen Sie die folgenden Ausdrücke: 2^3, -2^3, 2^4, -2^4, 3^-2, -3^-2, 2^-3 und -2^-3. Wenn Sie großzügigerweise von der etwas schlampigen Schreibweise absehen, die wir hier bemühen müssen, weil unser Programm noch keine Klammern kennt - welche Terme werden richtig berechnet, welche falsch?
Sofern Sie die Potenzen genau so implementiert haben wie es im Lösungsvorschlag gemacht wurde, dann dürfte Ihr Programm Schwierigkeiten haben bei negativen Potenzen mit geraden Exponenten. Dies liegt daran, dass z.B. "-3^2" als "(-3)^2" interpretiert wird, aber den mathematischen Konventionen nach eigentlich "-(3^2)" bedeutet (wegen "Hoch vor Punkt vor Strich"). Dass im Falle von ungeraden Exponenten die Ergebnisse richtig sind, ist nicht unser Verdienst, sondern eher ein Zufall.
Es nützt uns also gar nichts, dass unser Interpreter schon negative Zahlen erkennen kann - spätestens bei den Potenzen brauchen die Vorzeichen eine Sonderbehandlung, weil Vorzeichen vor Potenzen sich eben auf die ganze Potenz beziehen und nicht nur auf die Basis. Um diese Schwierigkeiten zu beheben, führen wir nun als Bauteile von Potenzen die "vorzeichenbehafteten Faktoren" ein, kurz "V-Faktoren" genannt, welche die Aufrufe von "Zahl" in unserer bisherigen Definition von "Potenz" ersetzen sollen. Wir werden den Begriff des V-Faktors später noch erheblich erweitern, aber zunächst wollen wir uns darauf beschränken, V-Faktoren als Zahlen zu betrachten, die (möglicherweise) ein Vorzeichen haben. Man erhält dann für diese neue Situation die folgenden Syntaxdiagramme:
Analog zum bisher schon einige Male praktizierten Vorgehen werden wir also nun eine Funktion VFaktor implementieren, und diese dann von der neuen Version der Funktion Potenz aus zweimal aufrufen. Bisher hatte jede unserer Parser-Funktionen eine Deklaration der Form
function FNAME(var s: String; var res: Double): Boolean;
Dies genügt nun für die Funktion VFaktor nicht mehr. Damit die Berechnung des Wertes einer Potenz erfolgreich sein kann, muss die Funktion Potenz "erfahren", ob in dem Quellstring vor der Basis ein Minuszeichen stand oder nicht. Um die Rückgabe dieser Information zu ermöglichen, statten wir die Funktion VFaktor mit einem weiteren Variablen-Parameter aus:
function VFaktor(var s: String; var res: Double; var HasMinus: Boolean): Boolean;
In der Variablen res soll aber nach wie vor der tatsächliche Wert des erkannten V-Faktors zurückgegeben werden, und nicht etwa nur sein Betrag. Dies wird bei späteren Erweiterungen nochmals wichtig werden.
Aufgaben:
-
Zahlen mit Vorzeichen
Kopieren Sie Ihr TermTester-Projekt in ein neues Verzeichnis. Bauen Sie dann die oben beschriebene Funktion VFaktor in die Unit TermInterpreter ein. Ändern Sie die Funktion Potenz nun so ab, dass sie statt Zahl nun VFaktor aufruft und zudem den Wert der Potenz unter Berücksichtigung der Vorzeichen korrekt berechnet.
Testen Sie das Programm aus, speziell mit den oben angegebenen Beispiel-Potenzen!
Nun wollen wir den Begriff des V-Faktors noch etwas verallgemeinern. Was kann außer Zahlen noch als Basis oder Exponent einer Potenz auftreten? Nun, Terme enthalten neben Zahlen ja üblicherweise auch Variablen, Funktionsterme also zumindest mal ein "x", möglicherweise aber auch noch Konstantenbezeichner wie "e" oder "pi". Überall dort, wo eine Zahl steht, kann auch eine Variable oder eine Konstante stehen. Wir können also unser Syntax-Diagramm für V-Faktoren zum Beispiel so erweitern:
Wenn nun die Variable "x" erkannt werden soll, dann muss bei der Interpretation des Termstrings jedes "x" durch den aktuellen Zahlenwert der Variablen x ersetzt werden. Damit dies überhaupt möglich ist, müssen wir die öffentliche Hauptfunktion unserer Unit, nämlich "Termwert", umdeklarieren: sie muss nun einen zusätzlichen Parameter erhalten, in dem der gewünschte Wert für das Funktionsargument übergeben wird. Beim Aufruf von "Termwert" sollte dann dieser Wert in eine interne Variable der TermInterpreter-Unit kopiert werden. Eine solche Variable (z.B. "arg_x" vom Typ Double) kann vorteilhaft direkt am Anfang des "implementation"-Teils unserer Unit deklariert werden, so dass sie für alle unit-internen Prozeduren verfügbar ist, von außen aber nicht gesehen werden kann. Die Konstanten "e" und "pi" können ebenfalls unit-intern deklariert werden, müssen aber nur einmal zu Programmbeginn mit entsprechenden festen Werten initialisiert werden. Nach diesen Vorbereitungen sollte die Erstellung einer Parser-Funktion VarConst zur Erkennung und Berechnung der aufgeführten Variablen x und der Konstanten e und pi kein unüberwindbares Hindernis für Sie sein!
Aufgaben:
-
Terme mit Variablen
Kopieren Sie Ihr TermTester-Projekt in ein neues Verzeichnis. Bauen Sie dann die oben beschriebene Funktion VarConst in die Unit TermInterpreter ein. Ändern Sie die Funktion TermWert nun so ab, dass sie wie bisher zunächst Zahl aufruft; wenn aber diese Funktion nichts erkannt hat, dann soll auch noch VarConst aufgerufen werden.
Testen Sie das Programm aus, ob es die Berechnung Funktionstermen mit Variablen und Konstanten nun komplett beherrscht!
Inzwischen kann unser Interpreter schon eine ganze Menge. Klammern jedoch kennt er noch nicht. Und es ist kein Zufall, dass wir dieses Problem erst jetzt angehen, denn an dieser Stelle nimmt unserer Projekt eine unerwartete Wendung hin zum Thema "Rekursion"! Und dies wird uns ein zusätzliches Problem bescheren, für dessen Lösung wir eine bisher noch nie verwendete Programmiertechnik einsetzen müssen.
Gehen wir die Sache mal ganz naiv an: ein Term kann Klammern enthalten, das sind Term-Teile, die mit "(" anfangen und mit ")" aufhören. (Vorsichtigerweise wollen wir uns zunächst einmal auf nur eine Sorte von Klammern beschränken.) Und wo in unserem Term können solche Klammerterme vorkommen? Überall dort, wo Zahlen oder Variablen oder Konstanten stehen könnten - womit wir unseren Klammerterm schon als eine weitere Variante der in der Funktion VFaktor aufgelisteten Term-Bausteine erkannt haben.
Und was kann nun alles in einer solchen Klammer drinstehen? Na, eben wieder ein Term! Und da wir schon vor langer Zeit gelernt haben, dass jeder Term eine Summe ist, könnten wir den Klammerterm also folgendermaßen in unsere Term-Sprache einbauen:
Das sieht zunächst ganz harmlos aus. Die oben schon angedrohte Rekursion wird erst erkennbar, wenn man sich klar macht, dass ein Term eine Klammer enthalten kann, die dann wieder einen Term enthalten kann, der dann wieder eine Klammer enthalten kann, die dann wieder einen Term enthält....
Analog zum bisherigen Vorgehen rufen wir in der Funktion Klammerterm nun nach der Erkennung der öffnenden Klammer einfach die Funktion Summe auf. Damit das geht, müssen wir Summe in unserem Quelltext vor der Funktion Klammerterm aufführen - der Delphi-Compiler kann nur Dinge verarbeiten, die er schon kennt! Damit dies funktioniert, müssen wir aber eine ganze Reihe von weiteren Funktionen nach vorne verlagern, nämlich Produkt, Potenz, VFaktor, VarConst, Klammerterm... hoppla!
Hier stolpern wir über ein klassisches "Henne-Ei-Problem": um Klammerterm implementieren zu können, brauchen wir zuvor Summe, aber um Summe implementieren zu können, brauchen wir zuvor Klammerterm! Diese Systemverklemmung kann z.B. dadurch behoben werden, dass man die Deklaration (d.h. die Definition) der Funktion Summe von deren eigentlicher Implementierung trennt. Man nennt dies eine "Forward-Deklaration":
function summe(var s: String; res: Double): Boolean; forward; { Deklaration }
{ hier kommen beliebig viele andere Prozeduren und Funktionen, z.B. auch: }
function Klammerterm(var s: String; res: Double): Boolean;
begin
{ Öffnende Klammer erkennen }
IF Summe(s, res) then begin {***}
{ Schließende Klammer erkennen }
Result := True;
end
else
{....}
end;
function summe; { Implementierung }
begin
{ Hier folgt die eigentlich Implementierung der Funktion Summe! }
end;
Um den Quelltext an der Stelle {***} übersetzen zu können, muss der Compiler nur wissen, wie die Funktion Summe aufgerufen wird, nicht jedoch, was sie im Detail tut! Genau diese Information wird durch die vorangestellte "Forward"-Deklaration geliefert. Bei der später folgenden eigentlichen Implementierung der Funktion Summe ist es dann nicht mehr nötig, die Parameterliste nochmals anzugeben; die kennt der Compiler ja schon! (Wenn man sie trotzdem hinschreiben will, muss sie natürlich punktgenau mit der in der obigen Forward-Deklaration übereinstimmen.)
Es gibt noch andere Methoden, dieses "Henne-Ei-Problem" zu lösen: man kann die Funktion Klammerterm auch als lokale Funktion innerhalb der Funktion Summe aufführen. Allerdings erhält man dann notwendigerweise eine ganze Serie ineinandergeschachtelter Funktionen (Klammerterm in VFaktor in Potenz in Produkt in Summe), was den Quelltext nicht gerade übersichtlicher macht. Die explizite Forward-Deklaration hat den Vorteil, dass man den Quelltext nur minimal verändern muss, und zwar eben gerade dort, wo das eigentliche Problem auftaucht.
Aufgaben:
-
Terme mit Klammern
Kopieren Sie Ihr TermTester-Projekt in ein neues Verzeichnis. Bauen Sie dann eine dem obigen Syntax-Diagramm entsprechende Funktion Klammerterm in die Unit TermInterpreter ein. Ändern Sie die Funktion VFaktor nun so ab, dass sie zusätzlich noch Klammerterm aufruft, sofern das notwendig ist, und ergänzen Sie die Forward-Deklaration von Summe.
Testen Sie das Programm aus, ob es nun beliebig komplexe Klammerterme mit Zahlen, Variablen und Konstanten korrekt berechnet!
Nun fehlen eigentlich nur noch die wichtigsten Standard-Funktionen, und dann wäre unser Term-Interpreter komplett. Also an die Arbeit! Wir können von unserer Vorarbeit bei den Klammertermen profitieren: kommt in einem Term eine Funktion vor, dann steht da stets ein Funktionsname, dem ein Klammerterm folgt! Mögliche Funktionsnamen sind z.B. "sqrt", "sin", "log" usw. Man erhält also das folgende Syntaxdiagramm:
Wir müssen also eigentlich nur noch die Erkennung der Funktionsnamen implementieren.
Aufgaben:
-
Funktionaler Abschluss!
Kopieren Sie Ihr TermInterpreter-Projekt in ein neues Verzeichnis. Implementieren Sie dann die Funktion Funktion(!), die die Erkennung der verschiedenen Standardfunktionen realisiert. Benutzen Sie zur Berechnung des Funktionsargumentes die schon vorhandene Funktion Klammerterm!
Testen Sie dann den neuen TermInterpreter mit Termen, die nun auch die Standardfunktionen enthalten.
Wenn Sie auch diesen letzten Schritt erfolgreich hinter sich gebracht haben, ist es Zeit, sich stolz zurückzulehnen und mit Wohlgefallen auf das vollbrachte Werk zu blicken: Sie haben nun einen Term-Interpreter gebaut, der alle für den üblichen Mathematikunterricht relevanten Terme "verstehen" kann, wobei man die Anführungszeichen eigentlich schon weglassen könnte!
Selbst wenn sich bei folgenden Anwendungen herausstellen sollte, dass diese Aussage noch nicht ganz zutrifft, dann kann Ihr Term-Interpreter zumindest leicht erweitert werden. Solche Modifikationen werden aber niemals die Struktur des Term-Interpreter-Programms betreffen, sondern immer nur den Charakter von Ergänzungen im Detail haben: der Term-Interpreter ist der Syntax mathematischer Terme gewachsen, auch wenn er möglicherweise noch nicht die ganze Semantik der Termsprache beherrscht, (d.h.: er versteht die "Grammmatik" der Termsprache, auch wenn er vielleicht noch nicht alle benötigten "Vokabeln" kennt).
