Bau eines Interpreters

Computer: Software & Programmierung Java
#1

Hallo

Ich hätte mal eine Frage zum Bau eines Interpreters, d.h. einer Anwendung, in das der Nutzer einen (Pseudo)Code eingibt, der dann von der Anwendung interpretiert und abgearbeitet wird.

Speziell interessiert mich, wie man schnell und effizient herausfindet, welche Funktion auszuführen ist, denn dieser Vorgang wird bei einem längeren Benutzercode oder bei rekursivem Code sehr oft ausgeführt.

Ich habe dies schon einmal in einem C++ Code gelöst gesehen, dort wurde intensiv Zeiger-Hexenwerk verwendet. Wenn ich das richtig verstanden habe, legte der Programmierer ein Array der möglichen Keywords ab, zusammen mit je einem Zeiger, wo die ausprogrammierte Funktion im Speicher lag. Da das Array selbst über einen Zeiger definiert war, brauchte er also nur eine doppelte Indirektion, um zu der auszuführenden Funktion zu gelangen. Vermutlich sehr effizient, aber praktisch unlesbar.

Wie macht man das nun am Besten in Java?
Ich habe mir in meiner Naivität gedacht, dass ich die Keywords in einem Array auf Chars mappe, weil ich mit den Chars am einfachsten ein grösseres Case-Statement aufbauen kann, in dem ich dann die benötigten Funktionen aufrufe.

Aber ob das die effizienteste Art ist, das Problem zu lösen?

Gruß
Thomas

#2

Moien

Speziell interessiert mich, wie man schnell und effizient
herausfindet, welche Funktion auszuführen ist, denn dieser
Vorgang wird bei einem längeren Benutzercode oder bei
rekursivem Code sehr oft ausgeführt.

Wenn es wirklich um Performance geht und du den Interpreter selbst bauen must (es gibt Lösungen für ein paar Sprachen): benutz JIT. Die Übersetztung macht man einmal, danach läuft alles über vorgeparste Symbole.

Ich habe mir in meiner Naivität gedacht, dass ich die Keywords
in einem Array auf Chars mappe, weil ich mit den Chars am
einfachsten ein grösseres Case-Statement aufbauen kann, in dem
ich dann die benötigten Funktionen aufrufe.

Nein. Ein Weg geht über einen Suchbaum. Man baut aus allen Keywords einen Baum bei dem pro Knoten ein Char festgelegt wird. D.h. im ersten Knoten springt man entsprechend des ersten Char, im 2. entsprechend des 2. … usw. Nach maximal #-der-chars-im-Keyword ist man durch. Bei günstigen Keywords kann man früher abbrechen. Also eine Art:

public class Node{
 Node[] branch;
 Commando toExecute;

 public Node getNode(Char c){ ... }

}

wobei toExecute immer null ist, ausser in den Blättern. Das lohnt sich aber nur wenn es viele Keywords gibt. Bei sehr wenigen ist es schneller alle durch den Stringmatcher zu jagen, eine ID (integer) zu bestimmen und dann durch switch zu gehen.

Oder als Zwischending eine Hashtable.

cu

#3

Du musst das Eingegebene erst einmal parsen. Dann erhältst du eine abstrakte Repräsentation der Benutzereingabe, mit der man dann Weiteres anstellen kann. Dieser Schritt geschieht bei Compilern und Interpretern gleichermaßen. Einen solchen Parser erstellt man in der Regel nicht per Hand sondern mit speziellen Programmen, die Compiler-Compiler oder Parser-Generatoren genannt werden. Java bringt auch einen solchen mit: javacc; man kann aber auch andere solcher Parsergeneratoren für Java benutzen.