====== Erweiterung der Sprache ======
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]].
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:start|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.
{{ :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:
/**
* 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 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.
===== Test des Interpreters =====
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! :-)