Klassendesign für einen Pascal Interpreter

[dvdlly]

Ich versuche einen Interpreter für eine Untermenge von Pascal zu schreiben und stehe vor einer Design Entscheidung - bisher habe ich einen Lexer und einen Parser geschrieben. Der Parser erzeugt den abstrakten Syntaxbaum (AST) und nun fehlt noch der tatsächliche Interpreter, der den Baum "auswertet". Das Problem ist: die verschiedenen Kinder im AST bedürfen unterschiedlicher Auswertungen. So habe ich z.B. eine Klasse BinOp, wo der rechte und linke Kindsknoten gemäß der binären operation verknüpft werden (nebenbei muss auch geprüft werden, von was für einem typ die beiden Kindsknoten sind). Im folgenden habe ich ein paar der Klassen angehängt um hoffentlich die Probleme zu verdeutlichen.

[CODE lang="java" title="BinOp Klasse"]package com.Parser;
import com.Lexer.Token;
import com.Visitor.*;

public class BinaryOp extends AST {
public AST left;
public AST right;
public Token operation;

public BinaryOp(AST left, AST right, Token op) {
this.left = left;
this.right = right;
operation = op;
}

@Override
public AST visit(Visitor visitor) {
// add something smart here.
return null;
}

@Override
public void print(){
left.print();
System.out.println("Binary operation of type : " + operation.type);
right.print();
}

@Override
public Object gettype() {
return operation.type;
}
}
[/CODE]
[CODE lang="java" title="AST Klasse"]package com.Parser;

import com.Visitor.Visitor;

public abstract class AST {
abstract AST visit(Visitor visitor);
abstract void print();
abstract Object gettype();
}[/CODE]

 

[httpdigest]

Ich versuche einen Interpreter für eine Untermenge von Pascal zu schreiben und stehe vor einer Design Entscheidung - bisher habe ich einen Lexer und einen Parser geschrieben. Der Parser erzeugt den abstrakten Syntaxbaum (AST) und nun fehlt noch der tatsächliche Interpreter, der den Baum "auswertet". Das Problem ist: die verschiedenen Kinder im AST bedürfen unterschiedlicher Auswertungen. So habe ich z.B. eine Klasse BinOp, wo der rechte und linke Kindsknoten gemäß der binären operation verknüpft werden (nebenbei muss auch geprüft werden, von was für einem typ die beiden Kindsknoten sind). Im folgenden habe ich ein paar der Klassen angehängt um hoffentlich die Probleme zu verdeutlichen.

Ja, okay. Und was ist jetzt deine ganz konkrete Frage bzw. dein ganz konkretes Problem? Ich lese hier erstmal nur eine Problembeschreibung, aber keinen Ansatz, wo du genau ein Problem hast/siehst.
Unterschiedliche Klassen für unterschiedliche Arten von AST-Knoten zu haben und verschiedene Visitor, die unterschiedliche Aufgaben haben (semantische Analyse, Auswertung, "Code Lowering" - für Compiler) ist ziemlich Standard.

 

[httpdigest]

Es hängt aber von deinem Parser ab, wie deine AST-Klassenstruktur genau aussieht.
Wenn du z.B. eine allgemeine AST-Library verwendest (z.B. jjtree von javacc oder die von ANTLR), dann hast du nur ganz allgemeine untypisierte Node-Klassen im AST und kannst nicht mit double-dispatch darüber "visiten".
Wenn du aber einen Parser hast, der typisierte AST-Klassen instanziiert, dann habe ich schon mal Parser geschrieben, die in etwa folgende Klassenstruktur hatten:

public interface Visitable {
  void accept(Visitor v);
}
public interface Visitor {
  void visitBinOpExpression(BinOpExpression e);
  ...
}
public class InterpretVisitor {
  public void visitBinOpExpression(BinOpExpression e) {
    // visit operands and perform operation
  }
  ...
}
public abstract class Node implements Visitable {}
public abstract class StatementNode extends Node {}
public abstract class ExpressionNode extends Node {
  public abstract Type type();
}
public class BinOpExpressionNode extends ExpressionNode {
  public final ExpressionNode leftOperand;
  public final ExpressionNode rightOperand;
  public final OperationKind operation;
  public void accept(Visitor v) {
    v.visitBinOpExpression(this);
  }
}

Du hast also Statements und Expressions (Expressions haben einen statischen Typ).
Zusätzlich kommen noch Declarations und CompilationUnits.

Hier lohnt es sich übrigens sehr! sich den Code von GraalVM anzugucken. Das sind sehr klar strukturierte AST-Knoten-Klassen: https://github.com/oracle/graal/tre...compiler.nodes/src/org/graalvm/compiler/nodes

 

[dvdlly]

Danke für deine Antwort.
Mein Problem liegt darin visitBinOp zu implementieren - eigentlich müsste die methode doch einen Rückgabetyp haben, es kann sich ja z.B. um die Zuweisung einer Variable zu dem Wert einer binären Operation handeln. Aber der Rückgabetyp der binären Operation kann in meinem Falle sowohl Integer als auch Double sein.

 

[httpdigest]

Der Visitor kann direkt Rückgabewerte bei seinen Methoden haben, muss es aber nicht. Wenn dein Interpreter/Visitor selbst eine Stack-Maschine implementiert, kannst du auch einfach einen java.util.Stack als Instanzvariable für das (rekursive) Auswerten von Ausdrücken verwenden und die visit...Op() Methoden poppen und pushen dann von/auf diesen Stack.
Wenn du dann z.B. ein "AssignmentStatement"-Node besuchst, hat dieses Assignment ja eine Expression als rechte Seite und eine Variable als linke Seite. Die Expression lässt du dann wieder von diesem Visitor berechnen und der erwartete Wert ist dann der oberste Wert auf dem Stack.
Um die eigentlichen Typen der Operationen zu ermitteln (mit Coalescing/Widening/etc.) brauchst du erstmal vermutlich eine semantische Analyse, also z.B. durch eine weitere Visitor-Implementierung, die Typen von Ausdrücken berechnet.
Dein Interpreter/Evaluierungs-Visitor nutzt dann diese Typinformationen. Die Typen selbst kannst du z.B. als Feld an eine abstrakte ExpressionNode-Klasse hängen.

 

[dvdlly]

Gibt es keine Möglichkeit, die visitBinOp Methode ohne semantische Analyse zu implementieren?

 

[httpdigest]

Doch. Du wertest einfach beide Argumente (rekursiv) durch deinen Visitor aus und prüfst dann mit instanceof (oder ähnlichen Laufzeittests), welche Typen die tatsächlichen Werte haben. Und abhängig davon führst du die entsprechende Typerweiterung (int zu float, wenn der andere Operand auch ein float ist, etc.) aus und berechnest das Ergebnis.
Da deine Visitor (bzw. der java.util.Stack, den du evtl. für die Werte verwendest) ja _alle möglichen_ validen Pascal-Programme bzw. Ausdrücke unterstützen müssen, musst du natürlich einen Java-Typ zur Repräsentation aller möglichen Pascal-Werte verwenden. Also z.B. einfach java.lang.Object. Wenn dein Visitor dann ein Pascal-Int-Literal auswertet, könntest du das z.B. durch einen java.lang.Integer repräsentieren. Einen Pascal-float durch java.lang.Float, etc.
Typ-Checks ist ja auch nur einer der Aspekte von semantischer Analyse, um zu prüfen, ob ein Pascal-Programm auch valide ist. Ein anderer wäre z.B. dass keine nicht-deklarierten Variablen in Ausdrücken referenziert werden.
Das findest du ansonsten aber nur heraus, wenn du den Ausdruck wirklich zur Laufzeit auswertest. (also in etwa wie bei JavaScript).