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:23] – [Erweiterung des Lexers] 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 139: Zeile 143:
  break;  break;
 </code> </code>
 +
 +
 +===== Test des Lexers =====
 +Der Lexer lässt sich wieder mit der Klasse ''LexerTest'' testen. Den Programmtext oben zerlegt er beispielsweise in folgende Token:
 +<code>
 +text[a] zuweisung zahl[1.0] strichpunkt text[b] zuweisung zahl[2.0] strichpunkt whileKeyword klammerAuf text[a] kleiner zahl[10.0] klammerZu geschweifteKlammerAuf text[a] zuweisung text[a] plus zahl[1.0] strichpunkt text[b] zuweisung text[b] mal zahl[2.0] strichpunkt printKeyword klammerAuf text[b] klammerZu strichpunkt geschweifteKlammerZu
 +</code>
 +
  
 ===== Erweiterung der Klasse Knoten ===== ===== Erweiterung der Klasse Knoten =====
Zeile 188: 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 =====
 +Der Parser lässt sich wieder mit der Klasse ''ParserTest'' testen. Den Programmtext oben konvertiert er in folgenden Baum:
 +<code>
 +Eingabetext:
 +a = 1;
 +b = 2;
 +while(a < 10){
 +  a = a + 1;
 +  b = b * 2;
 +  print(b);
 +}
 +
 +Tokens:
 +text[a] zuweisung zahl[1.0] strichpunkt text[b] zuweisung zahl[2.0] strichpunkt whileKeyword klammerAuf text[a] kleiner zahl[10.0] klammerZu geschweifteKlammerAuf text[a] zuweisung text[a] plus zahl[1.0] strichpunkt text[b] zuweisung text[b] mal zahl[2.0] strichpunkt printKeyword klammerAuf text[b] klammerZu strichpunkt geschweifteKlammerZu
 +
 +Syntaxbaum (AST):
 +zuweisung
 +   l:text[a]
 +   r:zahl[1.0]
 +   n:zuweisung
 +      l:text[b]
 +      r:zahl[2.0]
 +      n:whileKeyword
 +         l:kleiner
 +            l:text[a]
 +            r:zahl[10.0]
 +         r:zuweisung
 +            l:text[a]
 +            r:plus
 +               l:text[a]
 +               r:zahl[1.0]
 +            n:zuweisung
 +               l:text[b]
 +               r:mal
 +                  l:text[b]
 +                  r:zahl[2.0]
 +               n:printKeyword
 +                  l:text[b]
 +</code>
 +
 +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:
 +
 +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.1635449017.txt.gz · Zuletzt geändert: 2021/12/29 11:29 (Externe Bearbeitung)
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki