Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- compilerbau:erweiterung:start [2021/10/28 21:29] – [Erweiterung der Klasse Knoten] Martin Pabst
+++ compilerbau:erweiterung:start [2021/12/29 11:29] (aktuell) – Externe Bearbeitung 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
 ====== Erweiterung der Sprache ======
+<WRAP center round tip 60%>
+Im folgenden zeige ich Dir, wie Du die Sprache, die unser Lexer/Parser/Interpreter versteht, zu einer kleinen Programmiersprache erweitern kannst. \\ \\ Das [[.test:start|gesamte Programm in ausführbarer Form findest Du hier]].
+</WRAP>
 Bisher kennt unsere Programmiersprache nur Terme (expressions), keine Anweisungen (statements). Wir wollen sie daher erweitern, so dass beispielsweise folgendes Programm kompiliert und ausgeführt werden kann:
@@ Zeile 441: / Zeile 445: @@
 Nachfolgend noch in grafischer Form. Die mit "n" bezeichneten Kanten entsprechen dem Wert des Attributs ''naechsteAnweisung'' im Knoten.
 {{ :compilerbau:erweiterung:pasted:20211028-212546.png?700 }}
+===== Erweiterung des Interpreters ======
+===== Mehrere Datentypen =====
+Die größte Herausforderung bei der Erweiterung des Interpreters ist, dass Term- und Variablenwerte jetzt zwei verschiedene Datentypen haben können. Der Term ''10 + 4'' etwa hat den Datentyp ''double'', der Term ''10 > 2'' hat den Datentyp ''boolean''. Unsere Programmiersprache ist [[http://en.wikipedia.org/wiki/Strong_and_weak_typing| weakly typed]]. Das hat die Konsequenz, dass der Datentyp von Variablen erst zur Laufzeit (also im Interpreter) offenbar wird. Entsprechend muss sich dieser darum kümmern. \\ \\
+Zum Speichern der Werte verwenden wir eine Klasse ''Wert'', die sowohl einen ''double''- als auch einen ''boolean''-Wert enthalten kann und in der insbesondere gespeichert ist, welchen der beiden Datentypen sie gerade enthält:
+<code java>
+/**
+ * Datentyp des gespeicherten Wertes
+ */
+enum Typ {
+   doubleTyp, booleanTyp
+}
+/**
+ * Ein Objekt der Klasse Wert kann einen boolean- oder double-Wert speichern.
+ * Der aktuell gespeicherte Datentyp ist im Attribut Typ hinterlegt.
+ */
+class Wert {
+   Typ typ;
+   double doubleWert;
+   boolean booleanWert;
+   public Wert(double d) {
+      this.doubleWert = d;
+      this.typ = Typ.doubleTyp;
+   }
+   public Wert(boolean b) {
+      this.booleanWert = b;
+      this.typ = Typ.booleanTyp;
+   }
+   public String toString() {
+      if(typ == Typ.doubleTyp) {
+         return doubleWert;
+      } else {
+         return booleanWert;
+      }
+   }
+}
+</code>
+Der erste Änderungsschritt besteht darin, die ''HashMap'' zur Speicherung der Variablenbelegungen so zu ändern, dass sie als Variablenwerte ''Wert''-Objekte akzeptiert:
+<code java>
+public class Interpreter {
+	/**
+	 * Speichert Zuordnungen von Variablenbezeichnern zu Werten:
+	 */
+  	private HashMap<String, Wert> variablenbelegung = new HashMap<>();
+</code>
+Die Methode ''interpretiere'' gibt jetzt Objekte der Klasse ''Wert'' zurück. Am Anfang der Methode wird jetzt sichergestellt, dass ''knoten != null'' ist, da im Falle einer Sequenz nach dem Ausführen der letzten Anweisung die Methode ''interpretiere'' mit dem Wert des Attributs ''naechsterKnoten'' dieser Anweisung aufgerufen wird, und da steckt dann ''null'' drin. Die ''switch''-Verzweigung als zentraler Bestandteil der Methode ''interpretiere'' bleibt.
+<code java>
+  	public Wert interpretiere(Knoten knoten) {
+    		if(knoten != null) {
+      			switch(knoten.getToken().getTokenType()) {
+...
+</code>
+Die Berechnung des Rückgabewertes sieht für den Operator ''plus'' etwa so aus:
+<code java>
+case plus :
+   return new Wert(
+      interpretiere(knoten.getLinks()).doubleWert +
+      interpretiere(knoten.getRechts()).doubleWert);
+</code>
+Für die anderen Operatoren sieht das entsprechend aus. Trickreich wird es nur bei den Vergleichsoperatoren ''=='' und ''!='', da sie sowohl mit numerischen als auch mit booleschen Operanden Sinn machen. Hier wird anhand des Attributes ''typ'' des Wert-Objekts unterschieden:
+<code java>
+case ungleich :
+	Wert linkerWert1 = interpretiere(knoten.getLinks());
+	if(linkerWert1.typ == Typ.doubleTyp) {
+		return new Wert(
+		interpretiere(knoten.getLinks()).doubleWert !=
+		interpretiere(knoten.getRechts()).doubleWert);
+	} else {
+		return new Wert(
+		interpretiere(knoten.getLinks()).booleanWert !=
+		interpretiere(knoten.getRechts()).booleanWert);
+	}
+</code>
+Die Knoten, die einer Wiederholung, Zuweisung oder Print-Anweisung entsprechen, werden vom nachfolgenden Code interpretiert:
+<code java>
+case whileKeyword :
+   /**
+    * Im linken Knoten hat der Parser die Bedingung (also den Term
+    * innerhalb von "(...)") abgelegt:
+    */
+	while(interpretiere(knoten.getLinks()).booleanWert) {
+   /**
+    * Der rechte Knoten zeigt auf die erste Anweisung innerhalb
+    * der Wiederholung. Die Methode interpretiere führt auch
+    * gleich die nachfolgenden Anweisungen aus.
+    */
+          interpretiere(knoten.getRechts());
+        }
+   /**
+    * führe die Anweisungen aus, die auf die Wiederholung folgen,
+    * also nach der "}"
+    */
+	interpretiere(knoten.getNaechsteAnweisung());
+	return null;
+case zuweisung :
+   String variablenbezeichner1 = knoten.getLinks().getToken().getText();
+   Wert wert1 = interpretiere(knoten.getRechts());
+   /**
+    * Neuen Wert der Variable speichern:
+    */
+   variablenbelegung.put(variablenbezeichner1, wert1);
+   /**
+    * Führe die Anweisungen aus, die nach der Zuweisung kommen:
+    */
+   interpretiere(knoten.getNaechsteAnweisung());
+   return wert1;
+case printKeyword :
+   /**
+    * Im linken Knoten steckt der Term, dessen Wert ausgegeben werden soll
+    */
+   println(interpretiere(knoten.getLinks()), Color.lightblue);
+   /**
+    * Führe die Anweisungen aus, die nach der Print-Anweisung kommen:
+    */
+   interpretiere(knoten.getNaechsteAnweisung());
+   return null;
+</code>
+Dadurch, dass am Ende jeder Anweisung mittels ''interpretiere(knoten.getNaechsteAnweisung());'' gleich die nächstfolgende Anweisung ausgeführt wird, wird sichergestellt, dass das ganze Programm abgearbeitet wird.
+===== Test des Interpreters =====
+Der Lexer lässt sich mit der Klasse ''InterpreterTest'' testen. Hier die Codestelle, die das Programm ausführt:
+<code java>
+/**
+ * Ausführung des Programms
+ */
+Interpreter i = new Interpreter();
+println("\nAusgabe des Programms:\n");
+Wert wert = i.interpretiere(p.getWurzel());
+println("\nTermwert:\n" + wert);
+</code>
+Innerhalb der Ausgabe sieht man auch die Ausgabe des interpretierten Programms:
+<code>
+Eingabetext:
+a = 1;
+b = 2;
+while(a < 10){
+  a = a + 1;
+  b = b * 2;
+  print(b);
+}
+Bem.: An dieser Stelle gibt der Interpreter auch die Tokenliste und den Syntaxbaum aus. Sie sind weiter oben auf dieser Seite unter "Test des Parsers" zu sehen.
+Ausgabe des Programms:
+.0
+.0
+.0
+.0
+.0
+.0
+.0
+.0
+.0
+Termwert:
+.0
+</code>
+**Kleine Denkaufgabe:** Woher kommt am Ende der Termwert ''1.0''? \\
+Bei der Implementierung des Compilers wurden viele Kompromisse eingegangen, um den Code einfachstmöglich zu halten:
+  * Die Fehlermeldungen könnten ausführlicher sein
+  * Die Performance des Lexers kann verbessert werden
+  * Starke Typisierung wäre wünschenswert
+  * Die Typen der Knoten des Syntaxbaums sollten von den Typen der Tokens unterschieden werden
+  * ...
+**Aber:** Er läuft! :-)