Home » Tutorials » Sonstiges » Funktionsinterpreter

Funktionsinterpreter

Interpreter Nr. 1

Nun beginnen wir mit der eigentlichen Arbeit an unserem Interpreter.
Die Idee ist also wie folgt:

  • Wir zerlegen den Eingabestring in die einzelnen Symbole.
  • Wir gehen die Eingabesymbole von links nach rechts durch und unterscheiden dabei drei Fälle:
  • Es handelt sich um eine Zahl. Dann landet diese umgehend auf dem Stack.
  • Es handelt sich um das Symbol ‚x‘. Dann landet der Wert von x direkt auf dem Stack.
  • Es handelt sich um einen Operator. Je nach dem, um was für einen Operator es sich handelt, holen wir einen oder zwei Operanden vom Stack, wenden den Operator darauf an und bringen das Ergebnis wieder auf den Stack.
  • Wenn wir alle Symbole abgearbeitet haben, brauchen wir nur noch das letzte Objekt auf dem Stack zurück zu liefern.

Wir benötigen also zunächst eine Methode, welche den Eingabestring auftrennt. Als Trennungszeichen wird hier das Leerzeichen verwendet.

procedure SplitString(res: TStringList; str: String; seperator: Char);
var
  Pos: Integer;
begin
  repeat
    Pos := AnsiPos(seperator, str);
    if Pos <> 0 then
    begin
      res.Add(Copy(str, 0, Pos - 1));
      str := Copy(str, Pos + 1, Length(str));
    end
    else
      res.Add(str);
  until (Pos = 0);
end;

Die eigentliche Prozedur zum Interpretieren der (mathematischen) Funktion ist nun die Umsetzung der oben beschriebenen Regeln. Lediglich die eigentlichen Zuweisungen sind durch den Umweg über TNumber etwas ungewohnt. Zudem müssen wir daran denken, die nicht mehr benötigten Instanzen jedes mal wieder frei zu geben, da ansonsten unnötig viel Speicher reserviert wird.

function interpret(const func: String; x: Extended): Extended;
var
  splittedFunction: TStringList;
  i: Integer;
  Stack: TStack;
  isNumber: Boolean;
  val: Extended;
  a, b: TNumber;
begin
  // Splitte den String in die einzelnen Symbole
  splittedFunction := TStringList.Create();
  SplitString(splittedFunction, func, ' ');
  // Stack bereit machen
  Stack := TStack.Create();
  // Jedes Symbol abarbeiten
  for i := 0 to splittedFunction.Count - 1 do
  begin
    // 1. Fall: Es handelt sich um das x.
    if splittedFunction[i] = 'x' then
    begin
      // Bring das x auf den Stack
      stack.Push(TNumber.Create(x));
    end
    else
    begin
      // 2. Fall: Handelt es sich um eine Zahl?
      isNumber := TryStrToFloat(splittedFunction[i], val);
      if isNumber then
      begin
        // Bring die Zahl auf den Stack
        stack.Push(TNumber.Create(val));
      end
      // Es handelt sich um einen Operator. Finde nun raus, welcher das ist
      else if splittedFunction[i] = '+' then
      begin
        a := stack.Pop();
        b := Stack.Pop();
        a.setNumber(a.getNumber() + b.getNumber());
        b.Free();
        stack.Push(a);
      end
      else if splittedFunction[i] = '-' then
      begin
        a := stack.Pop();
        b := Stack.Pop();
        a.setNumber(b.getNumber() - a.getNumber());
        b.Free();
        stack.Push(a);
      end
      else if splittedFunction[i] = '*' then
      begin
        a := stack.Pop();
        b := Stack.Pop();
        a.setNumber(a.getNumber() * b.getNumber());
        b.Free();
        stack.Push(a);
      end
      else if splittedFunction[i] = 'sqrt' then
      begin
        a := stack.Pop();
        a.setNumber(sqrt(a.getNumber()));
        stack.Push(a);
      end;
    end;
  end;
  // Liefere das Ergebnis zurück
  a := stack.pop();
  result := a.getNumber();
  // Gebe noch alle Ressourcen frei
  splittedFunction.Free();
  a.Free();
end;

Etwas ist jetzt auffällig. In dem Ausschnitt

if splitted_function[i] = '-' then
begin
  a := stack.Pop();
  b := Stack.Pop();
  a.setNumber(b.getNumber() - a.getNumber());
  stack.Push(a);
end;

werden die Operanden vertauscht. Die Frage nach dem Warum kann man sich damit erklären, dass der Stack die Werte genau verkehrt herum bereitliegen hat. In der UPN wird der Ausdruck 5 – 2 etwa zu 5 2 -. Damit landet zunächst die 5 und dann erst die 2 auf dem Stack. Werden diese nun der Reihenfolge nach abgerufen, so erhalten wir zunächst die 2 und dann die 5. Um dies zu korrigieren, müssen wir also bei sämtlichen Verknüpfungen, die nicht kommutativ sind, die Operanden vertauschen.

Wir sind soweit fertig und haben damit einen einfachen Funktionsinterpreter geschrieben. Da etwa bei der Berechnung von 200.000 Werten der Funktion f: x -> (x^2 + 2)^(1/2) viele Schritte unnötigerweise mehrfach ausgeführt werden, werden wir uns im nächsten Abschnitt anschauen, wie wir derartige Berechnungen noch beschleunigen können.