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:
1.278Die 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
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:
package lexer; 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.variable; } 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 variable: s += "[" + text + "]"; break; default: break; } return s; } }
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 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<Token> 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<Token>(); // 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<Token> lex() throws Exception { /** * 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: throw new Exception("Der Lexer kann mit dem Zeichen '" + c + "' an Position " + position + " nichts anfangen."); } position++; // Das von peek() oben gelesene Zeichen ist // verarbeitet, also jetzt das nächste holen. } } return tokenListe; }
/** * 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() { StringBuilder variablenBezeichner = new StringBuilder(); do { char c = peek(); variablenBezeichner.append(c); position++; } while (Character.isLetter(peek()) || Character.isDigit(peek()) || peek() == '_'); tokenListe.add(new Token(variablenBezeichner.toString())); } /** * Die Methode lexZahl liest eine Zahl */ private void lexZahl() throws NumberFormatException { 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 '\u0000'; } }
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<Token> getTokenListe() { return tokenListe; } /** * Nur zu Debuggingzwecken */ @Override public String toString() { String s = ""; for (Token token : tokenListe) { s += token.toString() + " "; } if (!s.isEmpty()) { s = s.substring(0, s.length() - 1); } return s; }
Hier geht's weiter zur Beschreibung des Parsers.