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

Hier der Quelltext zum Download.

Die EBNF dieser Sprache 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,
 
	/**
	 * 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 lexVariable geht davon aus, dass das nächste zu verarbeitende
	 * Zeichen ein Buchstabe ist. Solange weitere Buchstaben oder Ziffern
	 * kommen, liest sie sie und setzt sie zu einem Text zusammen.
	 */
	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 {
						throw new Exception("Das Zeichen = wird erwartet.");
					}
					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:

	/**
	 * Parst die dem Konstruktor übergebene Liste von Tokens und gibt einen
	 * Parse-Baum (Abstract Syntax Tree) zurück.
	 * 
	 * @return Parse-Baum (Abstract Syntax Tree)
	 * @throws Exception
	 *             Falls die Liste der Tokens nicht der Syntax entspricht
	 */
	public Knoten parse() throws Exception {
 
		wurzel = sequenz(); 
 
		return wurzel;
 
	}
 
	/**
	 * Parst eine Reihe von Anweisungen.
	 * 
	 * @return
	 * @throws Exception
	 */
	private Knoten sequenz() throws Exception {
 
		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
	 * @throws Exception
	 */
	private Knoten anweisung() throws Exception {
 
		if(peek() == null){
			return null;
		}
		/**
		 * Eine Anweisung beginnt mit whileKeyword, printKeyword oder text:
		 */
		switch (peek()) {
		case whileKeyword:
			return wiederholung();
		case printKeyword:
			return print();
		case text:
			return zuweisung();
		default:
			return null;
		}
 
	}
 
	/**
	 * Die Methode geht davon aus, dass das nächste Token vom Typ printKeyword
	 * ist.
	 * 
	 * @return
	 * @throws Exception
	 */
	private Knoten print() throws Exception {
 
		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
	 * @throws Exception
	 */
	private Knoten wiederholung() throws Exception {
 
		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
	 * @throws Exception
	 */
	private Knoten zuweisung() throws Exception {
 
		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
	 * @throws Exception
	 */
	private Knoten aussage() throws Exception {
 
		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.
Die einfachste (aber nicht: beste) Lösung besteht darin, den Rückgabewert der Methode interpretiere auf Object zu ändern und bei jeder Berechnung anhand des Operators zu entscheiden, ob die Operanden auf Double oder Boolean gecastet werden müssen. Schwierig wird es bei den Vergleichsoperatoren '==' und '!=', da sie sowohl mit Booleschen als auch mit numerischen Operanden Sinn machen.

Der erste Änderungsschritt besteht darin, die HashMap zur Speicherung der Variablenbelegungen so zu ändern, dass sie als Variablenwerte beliebige Objekte (also insbes. Double-Objekte und Boolean-Objekte) akzeptiert:

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

Die Methode interpretiere gibt jetzt Objekte der Klasse Object zurück (d.h. Double oder Boolean oder null). 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.

	/**
	 * Berechnet - ausgehend vom übergebenen Knoten - den Wert des Terms, der
	 * durch den Knoten und den darunterhängenden Teilbaum gegeben ist.
	 * 
	 * @param knoten
	 *            Wurzel des Teilbaums, dessen Termwert berechnet werden soll
	 * @return Wert des Terms
	 * @throws Exception
	 */
	public Object interpretiere(Knoten knoten) throws Exception {

		if (knoten != null) {

			switch (knoten.getToken().getTokenType()) {

Bei der Berechnung der Rückgabewerte müssen die Termwerte des linken und rechten Operanden jeweils passend interpretiert („gecastet“) werden. Für den Operator plus sieht das beispielsweise so aus:

			case plus:
				return (Double) interpretiere(knoten.getLinks())
						+ (Double) interpretiere(knoten.getRechts());

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 der Klasse des linken Operanden entschieden, wie gecastet wird:

			case ungleich:

				Object linkerWert1 = interpretiere(knoten.getLinks());

				if (linkerWert1.getClass() == Double.class) {
					return (Double) interpretiere(knoten.getLinks()) != (Double) interpretiere(knoten
							.getRechts());
				} else {
					return (Boolean) interpretiere(knoten.getLinks()) != (Boolean) interpretiere(knoten
							.getRechts());
				}

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

			case zuweisung:
				String variablenbezeichner1 = knoten.getLinks().getToken()
						.getText();

				Object 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
				 */
				System.out.println(interpretiere(knoten.getLinks()));

				/**
				 * 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();
 
			System.out.println("\nAusgabe des Programms:\n");			
 
			Object wert = i.interpretiere(p.getWurzel());
 
			System.out
					.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!