Java lernen durch Ausprobieren!

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen:
compilerbau:erweiterung:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
compilerbau:erweiterung:start [2021/10/28 21:26] – [Erweiterung der Klasse Knoten] Martin Pabstcompilerbau:erweiterung:start [2021/12/29 11:29] (aktuell) – Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 ====== Erweiterung der Sprache ====== ====== 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: 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 196: Zeile 200:
   * naechsteAnweisung: Die Anweisung, die auf die Zuweisung folgt.   * naechsteAnweisung: Die Anweisung, die auf die Zuweisung folgt.
  
 +===== Erweiterung des Parsers =====
 +Die Klasse Parser wird um Methoden zum Parsen von 
 +  * einer Aussage
 +  * einer Wiederholung
 +  * einer Zuweisung
 +  * einer Print-Anweisung
 +  * einer Anweisung (d.h. eine beliebige der drei vorhergehenden)
 +  * einer Sequenz (d.h. einer beliebig langen Abfolge von Anweisungen)
 +erweitert:
 +
 +<code java>
 +public class Parser {
 +...
 +
 + /**
 + * Parst die dem Konstruktor übergebene Liste von Tokens und gibt einen
 + * Parse-Baum (Abstract Syntax Tree) zurück.
 + * 
 + * @return Parse-Baum (Abstract Syntax Tree)
 + *             Falls die Liste der Tokens nicht der Syntax entspricht
 + */
 +  public Knoten parse() {
 +
 +    wurzel = sequenz(); 
 +
 +    return wurzel;
 +
 +  }
 +
 + /**
 + * Parst eine Reihe von Anweisungen.
 + * 
 + * @return
 + */
 +  private Knoten sequenz() {
 +
 +    Knoten knoten = null;
 +    Knoten ersteAnweisung = null;
 +
 +    do {
 +
 +      Knoten letzterKnoten = knoten;
 +
 +      knoten = anweisung();
 +
 +      if(letzterKnoten != null) {
 +
 +        letzterKnoten.setNaechsteAnweisung(knoten);
 +
 +        if(ersteAnweisung == null) {
 +
 +          ersteAnweisung = letzterKnoten;
 +
 +        }
 +      }
 +
 +    } while(knoten != null);
 +
 +    return ersteAnweisung;
 +
 +  }
 +
 + /**
 + * Parst eine Anweisung, d.h. eine Wiederholung, eine Print-Anweisung oder
 + * eine Zuweisung.
 + * 
 + * @return
 + */
 +  private Knoten anweisung() {
 +
 +    if(peek() == null) {
 +      return null;
 +    }
 + /**
 + * Eine Anweisung beginnt mit whileKeyword, printKeyword oder text:
 + */
 +    switch(peek()) {
 +        case whileKeyword : 
 +          return wiederholung();
 +        case printKeyword : 
 +          return parsePrint();
 +        case text : 
 +          return zuweisung();
 +        default : 
 +          return null;
 +    }
 +
 +  }
 +
 + /**
 + * Die Methode geht davon aus, dass das nächste Token vom Typ printKeyword
 + * ist.
 + * 
 + * @return
 + */
 +  private Knoten parsePrint() {
 +
 +    Knoten knoten = new Knoten(erwarte(TokenType.printKeyword));
 +
 +    erwarte(TokenType.klammerAuf);
 +
 +    Knoten aussage = aussage();
 +
 +    erwarte(TokenType.klammerZu);
 +
 +    erwarte(TokenType.strichpunkt);
 +
 +    knoten.setLinks(aussage);
 +
 +    return knoten;
 +
 +  }
 +
 + /**
 + * Die Methode geht davon aus, dass das nächste Token vom Typ whileKeyword
 + * ist.
 + * 
 + * @return
 + */
 +  private Knoten wiederholung() {
 +
 +    Knoten knoten = new Knoten(erwarte(TokenType.whileKeyword));
 +
 +    erwarte(TokenType.klammerAuf);
 +
 +    Knoten aussage = aussage();
 +
 +    erwarte(TokenType.klammerZu);
 +
 +    erwarte(TokenType.geschweifteKlammerAuf);
 +
 +    Knoten anweisungen = sequenz();
 +
 +    erwarte(TokenType.geschweifteKlammerZu);
 +
 +    knoten.setLinks(aussage);
 +    knoten.setRechts(anweisungen);
 +
 +    return knoten;
 +
 +  }
 +
 + /**
 + * Die Methode geht davon aus, dass das nächste Token vom Typ text ist.
 + * 
 + * @return
 + */
 +  private Knoten zuweisung() {
 +
 +    Knoten linkeSeite = new Knoten(nextToken());
 +
 +    Knoten knoten = new Knoten(erwarte(TokenType.zuweisung));
 +
 +    Knoten rechteSeite = aussage();
 +
 +    erwarte(TokenType.strichpunkt);
 +
 +    knoten.setLinks(linkeSeite);
 +    knoten.setRechts(rechteSeite);
 +
 +    return knoten;
 +
 +  }
 +
 + /**
 + * Versucht, eine Aussage im Programmtext zu parsen. Weiteres: siehe Methode
 + * SummeDifferenz.
 + * 
 + * @return Geparster Teilbaum
 + */
 +  private Knoten aussage() {
 +
 +    Knoten linkerOperand = summeDifferenz(); // Versuche, eine
 + // Summe/Differenz zu finden
 +
 +    while(peek() == TokenType.identisch || peek() == TokenType.ungleich
 +        || peek() == TokenType.kleiner || peek() == TokenType.groesser
 +        || peek() == TokenType.kleinergleich
 +        || peek() == TokenType.groessergleich) {
 +
 +      Token operator = nextToken();
 +
 +      Knoten rechterOperand = summeDifferenz();
 +
 +      Knoten neuerKnoten = new Knoten(operator, linkerOperand,
 +        rechterOperand);
 +
 +      linkerOperand = neuerKnoten;
 +
 +    }
 +
 +    return linkerOperand;
 +
 +  }
 +
 +...
 +
 +}
 +
 +</code>
 +
 +Ansonsten muss nichts am Parser geändert werden.
  
 ===== Test des Parsers ===== ===== Test des Parsers =====
Zeile 239: Zeile 445:
 Nachfolgend noch in grafischer Form. Die mit "n" bezeichneten Kanten entsprechen dem Wert des Attributs ''naechsteAnweisung'' im Knoten. 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 }} {{ :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:
 +
 +4.0
 +8.0
 +16.0
 +32.0
 +64.0
 +128.0
 +256.0
 +512.0
 +1024.0
 +
 +Termwert:
 +1.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! :-)
 +
  
compilerbau/erweiterung/start.1635449161.txt.gz · Zuletzt geändert: 2021/12/29 11:29 (Externe Bearbeitung)
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki