2 Ein Interpreter für Zahlen
Üblicherweise gibt ein Computer-Benutzer über die Tastatur nur Texte ein. Selbst wenn der Text Ziffern enthält, werden diese zunächst noch nicht als Zahlen erkannt, sondern (genau wie jeder andere Text auch) als Folge von ASCII-Nummern in einer Zeichenkette abgelegt. Soll nun in einem Programm tatsächlich eine Zahl eingegeben werden, dann muss die eingegebene Zeichenkette interpretiert werden, d.h.: das Programm muss feststellen, was diese Zeichenkette bedeutet. Einen Algorithmus, der so etwas leistet, nennt man einen Interpreter. Ein Interpreter ist also eine Maschine, die als Eingabe eine Zeichenkette entgegen nimmt, diese auf ihre Bedeutung hin untersucht und das Ergebnis der Untersuchung in einer geeigneten Datenstruktur zurückgibt.
Damit der Inhalt einer Zeichenkette einem Interpreter seinen Sinn enthüllen kann, muss dieser die Zeichenkette "verstehen". Das ist dann besonders einfach, wenn die Zeichenkette den Bedeutungsinhalt in einer Form enthält, die durch die Syntaxregeln einer entsprechenden formalen Sprache festgelegt ist. Wenn die zu interpretierenden Zeichenketten also "Sätze" einer formalen Sprache sind, dann braucht man einen Interpreter, der diese formale Sprache "versteht".
Wir wollen uns in diesem Kapitel mit der Interpretation von Zahlen beschäftigen. Wenn wir bisher einen Text, der eine Ziffernfolge enthält, in eine Zahl umwandeln wollten, dann haben wir uns stets entsprechender Standardfunktionen von Delphi bedient, wie StrToInt() oder StrToFloat() usw. In diesen Funktionen sind entsprechende Interpreter-Algorithmen implementiert. Jetzt wollen wir aber darauf verzichten, diese Funktionen zu verwenden, sondern untersuchen, nach welchen Konstruktionsprinzipien sie gebaut sind und wie sie arbeiten. Dazu werden wir selbst einen Interpreter für Zahlen implementieren, eine Maschine also, die die formale Sprache versteht, in der wir Zahlen ausdrücken. Dass es eine solche formale Sprache gibt, wird sich zeigen, wenn wir darüber nachdenken, wie eine Zeichenkette beschaffen sein muss, damit wir sie als Zahl interpretieren (können). Die Syntax-Diagramme dieser formalen Sprache werden uns dann helfen, unser Wissen über den Aufbau von "Zahlstrings" an den Interpreter weiter zu geben.
Wenn wir das geschafft haben, können wir die Fähigkeiten des Interpreters erweitern; das Fernziel ist, einen Interpreter für beliebige mathematische Terme zu bauen. Das lohnt sich, denn für diese Aufgabe bietet Delphi keine passende Standardfunktion an! Gesucht ist also eine Funktion, der in einer Zeichenkette die Textdarstellung eines mathematischen Terms übergeben wird und die dann den Wert dieses Terms errechnet und zurückgibt. Eine solche Funktion könnte z.B. so deklariert werden:
function TermWert(s: String): Double;
Wir wollen diese Funktion in einer eigenen neuen Unit namens "TermInterpreter" unterbringen. Die Schnittstelle dieser Unit sollte möglichst sparsam gestaltet werden. Daher gibt es neben der Funktion TermWert nur noch ein paar öffentliche Variablen, die der Diagnose im Fehlerfall dienen. Die Unit kann also z.B. so aussehen:
unit TermInterpreter;
interface
var LastErrorMsg : String;
LastErrorPos : Integer;
Okay : Boolean;
function TermWert(s: String): Double;
implementation
{ Interne Scannerfunktionen für logische Term-Bestandteile }
function N_Zahl(var s: String; var res: Double): Boolean;
begin
{ kommt später }
end;
{ Öffentliche Funktion }
function TermWert(s: String): Double;
var r : Double;
ils : Integer;
begin
LastErrorMsg := '';
LastErrorPos := 0;
ils := Length(s);
If N_Zahl(s, r) then begin
Result := r;
Okay := True;
end
else begin
Result := 0;
Okay := False;
LastErrorPos := ils - Length(s);
LastErrorMsg := LastErrorMsg + ' {Rest : ' + s + ' }';
end;
end;
end.
Die Vorteile eines solchen Vorgehens sind zum einen, dass wir uns gleich am Anfang eine Testumgebung einrichten können, die wir dann nur noch an wenigen Stellen der Entwicklung des eigentlichen Term-Interpreters ändern müssen. Wir können uns also auf die wesentlichen Teile unserer Arbeit konzentieren. Andererseits liegt am Ende der Entwicklung mit der Unit "TermInterpreter" ein abgeschlossenes Softwareprodukt mit wohldefinierter Schnittstelle vor, das in allen weiteren Projekten eingesetzt werden kann, in denen ein Term-Interpreter gebraucht wird.
Es ist allerdings noch ein weiter Weg bis dahin. Fangen wir also gleich mit dem ersten Schritt an: in der obigen Unit wird schon die Funktion "N_Zahl" deklariert, die aus dem übergebenen String s eine natürliche Zahl erkennen soll. Diese Funktion ist die erste einer langen Reihe von "Parser-Funktionen" (von engl. "to parse": grammatisch zergliedern), die wir programmieren werden. Es hat sich bewährt, alle Parser-Funktionen als boolsche Funktionen zu implementieren, die genau dann TRUE liefern, wenn der übergebene String s den Regeln entsprach, die der Parser überprüft. Daneben sollte der Parser alle erkannten Zeichen aus dem String s löschen und den numerischen Wert des erkannten Term(teils) im Parameter res zurück geben. Damit diese Ergebnisse auch wirklich im aufrufenden Programm ankommen, müssen für s und res natürlich Variablenparameter verwendet werden. In den beiden folgenden Abschnitten werden entsprechende Parser-Funktionen für die Erkennung von natürlichen Zahlen und Fließkomma-Zahlen konstruiert.
Die einfachsten Zahlen sind die natürlichen Zahlen. Sie bestehen aus einer endlichen Folge von Ziffern. Eine Ziffer ist eines der Terminalsymbole aus der Menge {'0', '1', '2', '3',...., '8', '9'}. Eine natürliche Zahl muss mindestens eine Ziffer enthalten. All dies wird durch die folgenden beiden Syntaxdiagramme ausgedrückt:
Beachten Sie, dass mit diesem Syntax-Diagramm auch die Null ("0") zur natürlichen Zahl avanciert - im Gegensatz zur sonst üblichen mathematischen Praxis. Außerdem sind in größeren Zahlen durchaus auch führende Nullen erlaubt: nach den obigen Regeln ist z.B. "007" eine gültige natürliche Zahl. Selbst "000" ist zugelassen und bedeutet "Null"; die leere Zeichenkette "" ist allerdings kein gültiges Zahlwort! Insgesamt ist die Menge der gültigen Zahlwörter zwar etwas größer als üblich, aber dafür ist unser Syntax-Diagramm schön einfach, ohne jedoch sinnlose Bildungen zuzulassen!
Wenn wir nun einen String s haben, der die Textdarstellung einer natürlichen Zahl n (im Dezimalsystem) enthält, dann ist also eine Funktion gesucht, die
- den String s von vorne nach hinten Zeichen für Zeichen "abtastet",
- dabei prüft, ob das jeweils untersuchte Zeichen eine gültige Ziffer ist,
- gegebenenfalls den numerischen Wert der Zahl n aus diesen Ziffern berechnet und
- die erkannten Zeichen aus dem String s löscht.
Eine Funktion, die dies leistet, könnte z.B. so aussehen:
function N_Zahl(var s: String; var res: Double): Boolean;
var c : Char;
begin
If Length(s) > 0 then
c := s[1]
else
c := #0;
If c in ['0'..'9'] then begin { Es wird eine Ziffer erwartet.... }
Result := True;
res := 0;
Repeat { Solange Ziffern da sind, werden sie }
Delete(s, 1, 1);
{#} res := 10 * res + (Ord(c) - Ord('0')); { ... ausgewertet. }
If Length(s) > 0 then
c := s[1] { Nächstes Zeichen holen }
else
c := #0;
until not (c in ['0'..'9']); { bis keine Ziffer mehr gefunden wird }
end
else begin { Falls keine Ziffer da ist: Fehler! }
Result := False;
LastErrorMsg := 'Ziffer erwartet!'; { Fehlermeldung absetzen }
end;
end;
Die eigentliche Zahlerkennung, also die Berechnung eines numerischen Wertes aus einem Zeichen, findet in der mit {#} markierten Zeile statt: Ord(c) liefert die ASCII-Nummer des Zeichens c, und da die Ziffern 0..9 die (dezimalen) ASCII-Nummern 48..57 haben, ergibt Ord(c) - Ord('0') tatsächlich den numerischen Wert der Ziffer in c.
Aufgaben:
-
Wir erkennen natürliche Zahlen...
Machen Sie sich klar, wie die Verwaltung der Stellenwerte geschieht, indem Sie einen Aufruf der Funktion N_Zahl mit s = '4308' mit einer Lauftabelle "von Hand" durchspielen!
-
...und der Rechner kann's auch!
Nun wollen wir dem Rechner beibringen, wie er natürliche Zahlen aus einem String erkennen kann:
- Stellen Sie die Testumgebung für die folgende Term-Interpreter-Entwicklung her: ein Programm mit einem (Edit-) Eingabefeld für den Termstring, einem Knopf, einem (FloatEdit-) Ausgabefeld für den (numerischen!) Termwert und einem (Edit-) Ausgabefeld für eventuelle Fehlermeldungen. Speichern Sie das Projekt in einem neuen Verzeichnis unter dem Namen "TermTester.dpr".
- Fügen Sie Ihrem Projekt eine neue (nicht-visuelle) Unit "TermInterpreter" hinzu. Stellen Sie sicher, dass diese Unit in der Uses-Liste der "Unit1" Ihres Formulars aufgeführt wird - nur dann können Sie die TermInterpreter-Funktionen auch wirklich nutzen! Bauen Sie die obigen Codefragmente in die Unit "Terminterpreter" ein.
- Ergänzen Sie Ihr Hauptprogramm durch eine Klickprozedur für den Knopf, die den im Eingabefeld stehenden String zusammen mit einer lokalen Ergebnisvariablen an die Funktion "TermWert" übergibt und das Ergebnis des Umwandlungsversuchs in die entsprechenden Ausgabefelder schreibt.
- Testen Sie das Programm mit verschiedenen zulässigen und unzulässigen Eingaben! Machen Sie sich klar, warum die Eingabe "z123" eine Fehlermeldung produziert, "12z3" jedoch nicht - und dass das so richtig ist!
- Einem aufmerksamen Kritiker könnte am obigen Entwurf der Funktion N_Zahl auffallen, dass da zwei mal derselbe Code vorkommt, nämlich beim Holen des nächsten Zeichens. Diese Aufgabe lässt sich natürlich vorteilhaft in einer eigenen unit-internen Funktion "GetFirstChar" erledigen - ein klassischer Fall von "outsourcing" ;-)
Implementieren Sie GetFirstChar(s: String) und benutzen Sie im Folgenden stets diese Funktion, um das erste Zeichen aus dem zu untersuchenden String auszulesen!
Wie ist nun eine Fließkomma-Zahl aufgebaut? Schauen wir uns ein paar Beispiele in wissenschaftlicher Notation an:
1,234; -3,14156; -5; +3,5; 1e9; 1.25e-8
Der erste Unterschied zu den natürlichen Zahlen kann schon vor der ersten Ziffer auftreten: Fließkomma-Zahlen können ein Vorzeichen haben. Allerdings müssen sie kein Vorzeichen haben! Ähnlich liegen die Dinge bei der Zutat, die den Fließkomma-Zahlen den Namen gab, nämlich dem Komma: es kann ein Komma vorkommen, aber es muss nicht! Wenn allerdings ein Komma vorhanden ist, dann muss ihm unbedingt mindestens eine Ziffer folgen. Um die Diskussion gleich vollständig über die Bühne zu bringen: ein weiterer optionaler Teil ist der Exponent: wenn ein 'e' folgt, dann muss danach eine (eventuell vorzeichenbehaftete) ganze Zahl kommen. Das folgende Syntax-Diagramm stellt diese Situation übersichtlich dar:
Dieses Syntax-Diagramm macht schon Gebrauch von dem Nichtterminal-Symbol "Natürliche Zahl", das im vorigen Syntax-Diagramm definiert wurde - genau wie das Syntax-Diagramm für "Natürliche Zahl" dort schon Gebrauch machte vom Nichtterminal-Symbol "Ziffer". Man erhält so eine Menge von Diagrammen, die voneinander logisch abhängig sind, und trotzdem bleiben die Verhältnisse überschaubar.
Wie wird nun ein solch kompliziertes Syntax-Diagramm in einer Parser-Funktion implementiert? Am einfachsten läuft man durch das Syntax-Diagramm auf zulässigen Wegen und beachtet dabei die folgenden Transformations-Regeln:
geht der Weg über ein Terminal-Symbol, dann muss dieses Symbol im String stehen;
geht der Weg über ein Nichtterminal-Symbol, dann wird die zu diesem Symbol gehörende Parser-Funktion aufgerufen;
an jeder Verzweigung muss man die verschiedenen Möglichkeiten in entsprechenden Ästen einer Entscheidung implementieren.
|
Das folgende Code-Fragment setzt nur einen Teil des obigen Syntax-Diagramms um, denn es wird zunächst auf die Erkennung eines Exponenten verzichtet:
function Zahl(var s: String; var res: Double): Boolean;
var IsMinus : Boolean;
c : Char;
d : Double;
begin
IsMinus := False; { Normalerweise erwarten wir was Positives! }
c := GetFirstChar(s);
If c in ['+', '-'] then begin { Optionales Vorzeichen testen }
Delete(s, 1, 1);
IsMinus := c = '-'; { Gegebenenfalls auf Minus umschalten }
end;
If N_Zahl(s, res) then begin { Vorkomma-Anteil holen }
Result := True; { => Erfolg ! }
c := GetFirstChar(s);
If c in ['.', ','] then begin { Nachkommastellen vorhanden ? }
Delete(s, 1, 1); { Dezimaltrenner löschen }
c := GetFirstChar(s);
If c in ['0'..'9'] then begin { Ziffern einlesen }
d := 0.1; { Stellenwert initialisieren }
Repeat
Delete(s, 1, 1);
res := res + d * (Ord(c) - Ord('0')); { Wert berechnen }
d := d / 10; { Stellenwert für nächste Stelle }
c := GetFirstChar(s); { Nächste Ziffer holen ... }
until not (c in ['0'..'9']); { ...bis keine mehr da sind }
end
else begin
Result := False;
LastErrorMsg := 'Nachkommastellen erwartet!';
end;
end;
{ Hier fehlt noch die Exponenten-Erkennung ! }
If IsMinus then res := -res; { Erst hier über das VZ entscheiden !!! }
end
else
Result := False; { LastErrorMsg wird schon von N_Zahl gesetzt. }
end;
Wie Sie sehen, wird hier für den Vorkomma-Anteil lediglich N_Zahl aufgerufen. Für den Nachkomma-Anteil ist jedoch eine eigene Verarbeitung der einzelnen Ziffern implementiert, weil hier bei einem Aufruf von N_Zahl eventuelle führende Nullen verloren gehen würden: 13,2 und 13,002 wären nicht unterscheidbar!
Aufgaben:
-
Wir erkennen Fließkomma-Zahlen...
Machen Sie sich klar, wie die Verwaltung der Stellenwerte des Nachkomma-Anteils geschieht, indem Sie einen Aufruf der obigen Funktion Zahl mit s = '4,380' und s = '4,038' mit einer Lauftabelle "von Hand" durchspielen!
-
...und der Rechner kann's auch!
Natürlich soll nun auch wieder der Rechner lernen, wie er Fließkomma-Zahlen aus einem String erkennen kann:
- Stellen Sie eine Kopie Ihres "TermTester"-Projekts in einem neuen Verzeichnis her, damit Sie die alte Version behalten. Falls bei der zukünftigen schwierigen Entwicklung mal was schief geht, können Sie dann immer wieder zu diesem alten Entwicklungsstand zurückkehren, um einen neuen Versuch zu wagen. (Sie wissen hoffentlich, dass Sie beim Kopieren eines Projektes nur die DPR-, PAS- und DFM-Dateien kopieren dürfen! Den faulen Ignoranten, die einfach wieder den ganzen Verzeichnisinhalt kopieren, möge der Monitor explodieren!)
- Ergänzen Sie Ihre Unit "TermInterpreter" um die oben beschriebene Funktion Zahl. Damit Sie beim Kompilieren keinen Fehler bekommen, darf diese Funktion im "implementation"-Teil der Unit erst nach der Funktion N_Zahl stehen! Rufen Sie dann in der Funktion TermWert statt N_Zahl nun Zahl auf!
- Ergänzen Sie die Funktion Zahl durch eine Erkennung für den Exponenten-Teil der Fließkomma-Zahlen! Fügen Sie diesen Teil an der vorgesehenen Stelle ein.
Bei der Berechnung des Zahlwertes werden Sie 10z bilden wollen, aber Delphi hat zunächst keine Standardfunktion dafür parat. Binden Sie die Standard-Unit "Math" ein und benutzen Sie die dann verfügbare Funktion power(b, e), die Ihnen den Wert von be liefert.
- Testen Sie das Programm mit verschiedenen zulässigen und unzulässigen Eingaben! Machen Sie sich klar, warum die Eingaben "1,e23" und "-e3" eine Fehlermeldung produzieren, "1,2-e3" und "1,2+3" jedoch nicht - und dass das so richtig ist!
