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

Erweiterung der Grammatik

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 ;

Neue Tokentypen

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
}

Erweiterung des Lexers

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;

Test des Lexers

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

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:

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.

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:

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.

Test des Parsers

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.