====== Lexer ======
Im folgenden findest Du die Beschreibung des Lexers. Den [[.test:start|fertigen Lexer zusammen mit einem direkt im Browser ausführbaren Testprogramm findest Du hier]].
Der Lexer liest den Programmtext Zeichen für Zeichen und fasst diese zu kleinsten syntaktischen Einheiten, sogenannten Tokens, zusammen. Unsere Beispielsprache besteht aus folgenden 8 Tokens:
* +
* -
* *
* /
* (
* )
* Zahlen (die aus Ziffern und Dezimalpunkten bestehen), z.B. ''1.278''
* Variablenbezeichnern, die mit einem Buchstaben des (englischen!) Alphabets beginnen und danach aus Buchstaben, Ziffern oder einem Unterstrich bestehen.
Die Tokens können im Programmtext unmittelbar hintereinander stehen, sie können aber auch durch Leerzeichen oder Zeilenumbrüche ('whitespace') voneinander getrennt sein. Whitespace wird vom Lexer einfach überlesen.
Den Programmtext
1 + 2 * (4 * a1 - 3)
zerlegt der Lexer also in folgende 11 Tokens:
zahl[1.0] plus zahl[2.0] mal klammerAuf zahl[4.0] mal text[a1] minus zahl[3.0] klammerZu
===== Die Klasse TokenType =====
Die Klasse TokenType ist einfach eine Enum-Klasse mit den möglichen Typen:
public enum TokenType {
zahl, text, plus, minus, mal, geteilt, klammerAuf, klammerZu,
/**
* Nur als Knotentyp für Knoten des Syntaxbaums:
*/
negation
}
Da wir die TokenTypen der Einfachheit halber auch als Typen der Knoten des vom Parser generierten Syntaxbaums verwenden, gibt es einen zusätzlichen Typ ''negation''. Dazu später mehr.
===== Die Klasse Token =====
Damit der Parser die Tokens nachher weiterverarbeiten kann, muss zu jedem Token sein Typ (Zahl, plus, text, ...) sowie - im Falle von Zahlen und Variablen - auch die konkrete Zahl bzw. die konkrete Variable gespeichert werden. Ein Token wird daher als Objekt der Klasse ''Token'' abgebildet:
public class Token {
private TokenType tokenType; // Art des Tokens (z.B. zahl, klammerAuf usw.)
private double zahl; // Wird nur belegt, wenn tokenType == zahl
private String text; // Wird nur belegt, falls tokenType == bezeichner
public Token(double zahl) {
this.zahl = zahl;
tokenType = TokenType.zahl;
}
public Token(String text) {
this.text = text;
tokenType = TokenType.text;
}
public Token(TokenType tokenType) {
this.tokenType = tokenType;
}
public TokenType getTokenType() {
return tokenType;
}
public double getZahl() {
return zahl;
}
public String getText() {
return text;
}
/**
* Die toString()-Methode dient nur Debuggingzwecken
*/
@Override
public String toString() {
String s = "" + tokenType;
switch(tokenType) {
case zahl :
s += "[" + zahl + "]";
break;
case text :
s += "[" + text + "]";
break;
default :
break;
}
return s;
}
}
===== Funktionsweise des Lexers =====
Die Klasse Lexer bekommt im Konstruktor den Programmtext übergeben und speichert ihn im Attribut ''text''. Darauf kann nachfolgend die Methode ''peek()'' zugreifen, um den Programmtext Zeichen für Zeichen auszulesen.
public class Lexer {
/**
* Die Zeichenkette wird von links nach rechts abgearbeitet. Hier ist
* gespeichert, das wievielte Zeichen gerade angesehen wird:
*/
private int position;
/**
* Liste zur Speicherung der ermittelten Tokens
*/
private ArrayList tokenListe;
/**
* Wir speichern den Programmtext in einem Attribut der Klasse, damit er
* nachher nicht von Methode zu Methode weitergereicht werden muss.
*/
private String text;
/**
*
* @param text
* Programmtext, der in Tokens zerlegt werden soll
*/
public Lexer(String text) {
this.text = text;
position = 0; // Wir beginnen mit dem Zeichen ganz links
tokenListe = new ArrayList(); // Liste zur Aufnahme der gelesenen Tokens instanzieren
}
Die Methode ''lex()'' liest den Programmtext nun Zeichen für Zeichen und zerlegt ihn in Tokens. Zum lexen von Zahlen oder Text (erstmal: Variablenbezeichnern; später: auch Schlüsselwörter) greift sie auf die Hilfsmethoden ''lexZahl()'' und ''lexText'' zurück.
/**
* Zerlegt den Programmtext, der dem Konstruktor übergeben wurde
*
* @return Liste mit Tokens
* @throws Exception
* Eine Exception wird ausgelöst, wenn der Programmtext Passagen
* enthält, aus denen keine Token gebildet werden können.
*/
public ArrayList lex() {
/**
* Wiederholung, die den Programmtext von links nach rechts abarbeitet:
*/
while(position < text.length()) {
/**
* peek() liest das nächste Zeichen im Programmtext, erhöht die
* Variable position aber nicht. Ruft man peek() mehrmals
* hintereinander auf, liefert es also immer dasselbe Zeichen.
*/
char c = peek();
if(istZiffer(c)) {
lexZahl();
} else if(istBuchstabe(c)) {
lexText();
} else {
switch(c) {
case '+' :
addToken(TokenType.plus);
break;
case '-' :
addToken(TokenType.minus);
break;
case '*' :
addToken(TokenType.mal);
break;
case '/' :
addToken(TokenType.geteilt);
break;
case '(' :
addToken(TokenType.klammerAuf);
break;
case ')' :
addToken(TokenType.klammerZu);
break;
case ' ' :
case '\n' :
case '\r' :
// Leerzeichen werden einfach überlesen
break;
default :
println("Fehler: Der Lexer kann mit dem Zeichen '" + c
+ "' an Position " + position + " nichts anfangen.");
System.exit(0);
}
position++; // Das von peek() oben gelesene Zeichen ist
// verarbeitet, also jetzt das nächste holen.
}
}
return tokenListe;
}
===== Die Hilfsmethoden lexZahl() und lexText() =====
/**
* Die Methode lexText 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 Variablennamen zusammen.
*/
private void lexText() {
String variablenBezeichner = "";
do {
char c = peek();
variablenBezeichner += c;
position++;
} while(Character.isLetter(peek()) || Character.isDigit(peek()) || peek() == '_');
tokenListe.add(new Token(variablenBezeichner));
}
/**
* Die Methode lexZahl liest eine Zahl
*/
private void lexZahl() {
String zahlAlsString = "";
do {
char c = peek();
zahlAlsString += c;
position++;
} while(Character.isDigit(peek()) || peek() == '.');
/**
* Hier machen wir es uns leicht und lassen Java den String in eine Zahl
* konvertieren. Die Methode parseDouble ist für sich genommen natürlich
* auch ein Lexer.
*/
double zahl = Double.parseDouble(zahlAlsString);
tokenListe.add(new Token(zahl));
}
Zum einfachen Hinzufügen eines Tokens, das weder eine Zahl noch Text darstellt, wird eine kleine Hilfsmethode definiert:
/**
* Fügt der tokenListe das übergebene Token hinzu
*
* @param tokenType
*/
private void addToken(TokenType tokenType) {
tokenListe.add(new Token(tokenType));
}
Der Zugriff auf den Programmtext geschieht immer über die Methode peek(), damit weniger Fehler beim Programmieren passieren:
/**
* peek() liest das nächste Zeichen im Programmtext, erhöht die Variable
* position aber nicht. Ruft man peek() mehrmals hintereinander auf, liefert
* es also immer dasselbe Zeichen.
*
* @return nächstes Zeichen im Programmtext
*/
private char peek() {
if(position < text.length()) {
return text.charAt(position);
} else {
return 0x;
}
}
Die restlichen Methoden erklären sich von selbst:
/**
* Vorsicht: Die übergebene Liste ist nur dann gefüllt, wenn zuvor die
* Methode lex aufgerufen wurde.
*
* @return Liste mit den Tokens, in die der Lexer den Programmtext zerlegt
* hat.
*/
public ArrayList getTokenListe() {
return tokenListe;
}
/**
* Nur zu Debuggingzwecken
*/
public String toString() {
String s = "";
for(Token token : tokenListe) {
s += token.toString() + " ";
}
if(!s.isEmpty()) {
s = s.substring(0, s.length() - 1);
}
return s;
}
[[..:parser:start|Hier geht's weiter zum Parser!]]