programmieren:schritte:lexer:start

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== 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:
Suche

Navigation

Drucken/exportieren

Werkzeuge

QR-Code
