Erweiterung der Sprache

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:

a = 1;
b = 2;
while(a < 10){
  a = a + 1;
  b = b * 2;
  print(b);
}

Die Grammatik dieser Sprache in EBNF sieht so aus:

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 ;

Für die neuen syntaktischen Elemente brauchen wir zusätzliche Tokentypen:

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
}

Damit der Lexer die Schlüsselwörter while, print, true und false erkennt, erweitern wir einfach die Methode lexText():

	/**
	 * 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;
    		}
 
  	}

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:

	/**
	 * 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;
    		}
  	}

Damit sieht die Erkennung von >, >= und != so aus:

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;

Der Lexer lässt sich wieder mit der Klasse LexerTest testen. Den Programmtext oben zerlegt er beispielsweise in folgende Token:

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

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:

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;
 
 
...

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.

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:

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;
 
  	}
 
...
 
}

Ansonsten muss nichts am Parser geändert werden.

Der Parser lässt sich wieder mit der Klasse ParserTest testen. Den Programmtext oben konvertiert er in folgenden Baum:

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]

Nachfolgend noch in grafischer Form. Die mit „n“ bezeichneten Kanten entsprechen dem Wert des Attributs naechsteAnweisung im Knoten.

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 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:

/**
 * 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;
      }
   }
}

Der erste Änderungsschritt besteht darin, die HashMap zur Speicherung der Variablenbelegungen so zu ändern, dass sie als Variablenwerte Wert-Objekte akzeptiert:

public class Interpreter {
 
	/**
	 * Speichert Zuordnungen von Variablenbezeichnern zu Werten:
	 */
  	private HashMap<String, Wert> variablenbelegung = new HashMap<>();

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.

  	public Wert interpretiere(Knoten knoten) {
 
    		if(knoten != null) {
 
      			switch(knoten.getToken().getTokenType()) {
...

Die Berechnung des Rückgabewertes sieht für den Operator plus etwa so aus:

case plus : 
   return new Wert(
      interpretiere(knoten.getLinks()).doubleWert + 
      interpretiere(knoten.getRechts()).doubleWert);

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:

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);
	}

Die Knoten, die einer Wiederholung, Zuweisung oder Print-Anweisung entsprechen, werden vom nachfolgenden Code interpretiert:

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;

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.

Der Lexer lässt sich mit der Klasse InterpreterTest testen. Hier die Codestelle, die das Programm ausführt:

/**
 * Ausführung des Programms
 */
 
Interpreter i = new Interpreter();
 
println("\nAusgabe des Programms:\n");	
 
Wert wert = i.interpretiere(p.getWurzel());
 
println("\nTermwert:\n" + wert);

Innerhalb der Ausgabe sieht man auch die Ausgabe des interpretierten Programms:

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

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!