Java lernen durch Ausprobieren!

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen:
compilerbau:erweiterung:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.


—compilerbau:erweiterung:start [2024/08/31 12:03] (aktuell) – angelegt - 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:
 +
 +<code java>
 +a = 1;
 +b = 2;
 +while(a < 10){
 +  a = a + 1;
 +  b = b * 2;
 +  print(b);
 +}
 +</code>
 +
 +
 +===== Erweiterung der Grammatik =====
 +
 +Die Grammatik dieser Sprache in [[..ebnf:start|EBNF]] sieht so aus:
 +<code bnf>
 +Ziffer   = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
 +Buchstabe =  "A" | "B" | "C" | "D" | … | "Z" | "a" | "b" | … | "z" ;
 +Zahl = Ziffer { Ziffer | "." } ;
 +Text = Buchstabe { Buchstabe | Ziffer | "_" } ;
 +TrueFalse = "true" | "false" ;
 +Term = "(" Aussage ")" | Zahl | Text | TrueFalse | "-" Term ;
 +Produkt = Term | Term "*" Term ;
 +Quotient = Term | Term "/" Term ;
 +ProduktQuotient = Produkt | Quotient ;
 +Summe = ProduktQuotient | ProduktQuotient "+" ProduktQuotient ;
 +Differenz = ProduktQuotient | ProduktQuotient "-" ProduktQuotient ;
 +SummeDifferenz = Summe | Differenz ;
 +Vergleichsoperator = "<" | ">" | "==" | "<=" | ">=" | "!=" ;
 +Aussage = SummeDifferenz | SummeDifferenz Vergleichsoperator SummeDifferenz ;
 +
 +Zuweisung = Text "=" Aussage ";"
 +Wiederholung = "while" "(" Aussage ")" "{" Sequenz "}" ;
 +Ausgabe = "print" "(" Aussage ")" ;
 +Anweisung = Zuweisung | Wiederholung | Ausgabe ;
 +Sequenz = { Anweisung };
 +
 +Programm = Sequenz ;
 +
 +</code>
 +
 +===== Neue Tokentypen =====
 +Für die neuen syntaktischen Elemente brauchen wir zusätzliche Tokentypen:
 +
 +<code java>
 +public enum TokenType {
 +  zahl, text, plus, minus, mal, geteilt, klammerAuf, klammerZu, 
 +  geschweifteKlammerAuf, geschweifteKlammerZu,
 +  whileKeyword, printKeyword,
 +  kleiner, groesser, identisch, kleinergleich, groessergleich, ungleich,
 +  zuweisung,
 +  trueKeyword, falseKeyword,
 +  strichpunkt,
 +
 + /**
 + * Nur als Knotentyp für Knoten des Syntaxbaums:
 + */
 +  negation
 +}
 +</code>
 +
 +===== Erweiterung des Lexers =====
 +Damit der Lexer die Schlüsselwörter ''while'', ''print'', ''true'' und ''false'' erkennt, erweitern wir einfach die Methode ''lexText()'':
 +
 +<code java>
 + /**
 + * Die Methode lexText lext Variablenbezeichner und Schlüsselwörter (keywords)
 + */
 +  private void lexText() {
 +
 +    String text = "";
 +
 +    do {
 +      char c = peek();
 +      text += c;
 +      position++;
 +    } while(istBuchstabe(peek()) || istZiffer(peek()) || peek() == '_');
 +
 +    switch(text) {
 +        case "true" : 
 +          tokenListe.add(new Token(TokenType.trueKeyword));
 +          break;
 +        case "false" : 
 +          tokenListe.add(new Token(TokenType.falseKeyword));
 +          break;
 +        case "while" : 
 +          tokenListe.add(new Token(TokenType.whileKeyword));
 +          break;
 +        case "print" : 
 +          tokenListe.add(new Token(TokenType.printKeyword));
 +          break;
 +        default : 
 +          tokenListe.add(new Token(text));
 +          break;
 +    }
 +
 +  }
 +</code>
 +
 +Etwas trickreicher sind die neuen Zeichen. Um etwa ''<'' und ''< ='' unterscheiden zu können, muss der Lexer ein Zeichen nach vorne blicken können. Wir brauchen daher eine zusätzliche ''peek(int n)''-Methode, die ''n'' Zeichen nach vorne blickt:
 +
 +<code java>
 + /**
 + * peek(n) liest das Zeichen im Programmtext an (aktuelle Position + n). Die
 + * aktuelle Position (Attribut position) wird nicht verändert.
 + * 
 + * @return Das Zeichen, das n Zeichen weiter steht als die aktuelle Position
 + */
 +  private char peek(int n) {
 +    if(position + n < text.length()) {
 +      return text.charAt(position + n);
 +    } else {
 +      return(char) 0;
 +    }
 +  }
 +</code>
 +
 +Damit sieht die Erkennung von ''>'', ''>='' und ''!='' so aus:
 +
 +<code java>
 +case '>' : 
 + if(peek(1) == '=') {
 + addToken(TokenType.groessergleich);
 + position++;
 + } else {
 + addToken(TokenType.groesser);
 + }
 + break;
 +case '!' : 
 + if(peek(1) == '=') {
 + addToken(TokenType.ungleich);
 + position++;
 + } else {
 + println("Das Zeichen = wird erwartet.", Color.red);
 + System.exit(1);
 + }
 + break;
 +</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 =====
 +Auch Anweisungen (Wiederholung, Zuweisung, Print-Anweisung) werden im Syntaxbaum als Knoten dargestellt. Dafür wird neben den Kindknoten ''rechts'' und ''links'' noch ein dritter KindKnoten ''naechsteAnweisung'' benötigt:
 +
 +<code java>
 +public class Knoten {
 +
 + /**
 + * Im Token steckt der Inhalt des Knotens drin, also ein Operator, eine Zahl oder ein 
 + * Variablenbezeichner. Der Einfachheit halber verwenden wir hier die Klasse Token. 
 + */
 + private Token token; 
 +
 + /**
 + * Kindknoten linkerhand
 + */
 + private Knoten links;
 +
 + /**
 + * Kindknoten rechterhand
 + */
 + private Knoten rechts;
 +
 + /**
 + * Im Falle einer Anweisung: nächstfolgende Anweisung
 + */
 + private Knoten naechsteAnweisung;
 +
 +
 +...
 +</code>
 +
 +Die Kindknoten der Anweisungen haben für verschiedene Arten von Anweisungen verschiedene Bedeutung:
 +
 +**wiederholungs-Knoten:**
 +  * links: Aussage innerhalb der Klammer
 +  * rechts: erste Anweisung innerhalb des while-Blocks (d.h. innerhalb der geschweiften Klammern)
 +  * naechsteAnweisung: Erste Anweisung, die der while-Anweisung folgt (d.h. erste Anweisung nach der schließenden geschweiften Klammer)
 +
 +**print-Knoten:**
 +  * links: Aussage, deren wert ausgegeben werden soll
 +  * rechts: ''null''
 +  * naechsteAnweisung: Die Anweisung, die auf die print-Anweisung folgt.
 +
 +**Zuweisungs-Knoten:**
 +  * links: text-Knoten, der den Bezeichner der Variablen enthält, der etwas zugewiesen werden soll.
 +  * rechts: Aussage, deren Wert der Variablen zugewiesen werden soll.
 +  * 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! :-)
 +