Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
programmieren:schritte:lexer:start [2016/02/18 06:38] – martinprogrammieren:schritte:lexer:start [2021/12/29 10:40] (aktuell) – Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 +====== Lexer ======
  
 +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 
 +<code>
 +1 + 2 * (4 * a1 - 3)
 +</code>
 +zerlegt der Lexer also in folgende 11 Tokens:
 +<code>
 +zahl[1.0] plus zahl[2.0] mal klammerAuf zahl[4.0] mal text[a1] minus zahl[3.0] klammerZu
 +</code>
 +
 +===== 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:
 +
 +<code java>
 +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;
 +
 + }
 +
 +}
 +</code>
 +
 +===== Die Klasse TokenType =====
 +Die Klasse TokenType ist einfach eine Enum-Klasse mit den möglichen Typen:
 +
 +<code java>
 +public enum TokenType {
 + zahl, text, plus, minus, mal, geteilt, klammerAuf, klammerZu, 
 +
 + /**
 + * Nur als Knotentyp für Knoten des Syntaxbaums:
 + */
 + negation
 +}
 +</code>
 +
 +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.
 +
 +===== 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. 
 +
 +<code java>
 +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
 +
 + }
 +
 +</code>
 +
 +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.
 +
 +<code java>
 + /**
 + * 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;
 +
 + }
 +</code>
 +
 +==== Die Hilfsmethoden lexZahl() und lexText() ====
 +<code java>
 + /**
 + * 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));
 +
 + }
 +</code>
 +
 +Zum einfachen Hinzufügen eines Tokens, das weder eine Zahl noch Text darstellt, wird eine kleine Hilfsmethode definiert:
 +
 +<code java>
 + /**
 + * Fügt der tokenListe das übergebene Token hinzu
 + * 
 + * @param tokenType
 + */
 + private void addToken(TokenType tokenType) {
 + tokenListe.add(new Token(tokenType));
 +
 + }
 +</code>
 +
 +Der Zugriff auf den Programmtext geschieht immer über die Methode ''peek()'', damit weniger Fehler beim Programmieren passieren:
 +
 +<code java>
 + /**
 + * 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';
 + }
 + }
 +</code>
 +
 +Die restlichen Methoden erklären sich von selbst:
 +
 +<code java>
 + /**
 + * 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;
 +
 + }
 +</code>
 +
 +Hier geht's weiter zur Beschreibung des [[programmieren:schritte:parser:start|Parsers]].

Zuletzt angesehen:

Drucken/exportieren
QR-Code
QR-Code programmieren:schritte:lexer:start (erstellt für aktuelle Seite)