Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- compilerbau:lexer:start [2021/10/28 20:10] – angelegt Martin Pabst
+++ compilerbau:lexer:start [2021/12/29 11:29] (aktuell) – Externe Bearbeitung 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
 ====== Lexer ======
+<WRAP center round tip 60%>
+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]].
+</WRAP>
 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:
@@ Zeile 22: / Zeile 27: @@
 zahl[1.0] plus zahl[2.0] mal klammerAuf zahl[4.0] mal text[a1] minus zahl[3.0] klammerZu
 </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.
+===== 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>
+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;
+  	}
+}
+</code>
+===== 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() {
+		/**
+		 * 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;
+  	}
+</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() {
+    		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));
+  	}
+</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 0x;
+   }
+}
+</code java>
+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
+ */
+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>
+[[..:parser:start|Hier geht's weiter zum Parser!]]