Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- compilerbau:start [2021/10/28 20:07] – angelegt Martin Pabst
+++ compilerbau:start [2022/05/19 08:10] (aktuell) – [Fertiges Programm zum Ausprobieren] Martin Pabst
@@ Zeile 1: / Zeile 1: @@
 ====== Compilerbau (Einführung) ======
-Ein Schüler (Lukas) bat um eine Erklärung, wie ein Compiler (z.B. [[programme:eos:start|EOS]] oder die [[https://www.online-ide.de|Online-IDE]]) programmiert wird. Leider pflegen alle Artikel, die ich dazu im Internet finde, einen recht theoretischen Zugang zum Thema. Daher möchte ich die Sache im Folgenden so erklären, wie ich sie (damals als Schüler in der 12. Jahrgangsstufe) an einem einfachen, in Pascal geschriebenen Compiler gelernt habe. \\
+<WRAP center round tip 80%>
+Wenn Du Dich für Compilerbau interessierst, solltest Du unbedingt das Buch [[https://craftinginterpreters.com/|"Crafting Interpreters"]] von Robert Nystrom lesen. Es ist sehr kurzweilig und äußerst anschaulich geschrieben. Für alle, die sich das Buch nicht leisten können, hat der Autor es [[https://craftinginterpreters.com/contents.html|hier kostenlos in Html-Form]] veröffentlicht.
+</WRAP>
+Ein Schüler von mir (Lukas) fragte mich, wie ein Compiler (z.B. [[https://www.pabst-software.de/doku.php?id=programme:eos:start|EOS]] oder die [[https://www.online-ide.de|Online-IDE]]) programmiert wird. Leider pflegen alle Artikel, die ich dazu im Internet finde, einen recht theoretischen Zugang zum Thema. Daher möchte ich die Sache im Folgenden so erklären, wie ich sie (damals als Schüler in der 12. Jahrgangsstufe) an einem einfachen, in Pascal geschriebenen Compiler gelernt habe. \\
+<WRAP center round info 80%>
+Ein **Compiler** ist ein Computerprogramm, das einen in einer Programmiersprache verfassten Programmtext einliest und in eine andere Programmiersprache umwandelt oder direkt ausführt. Er arbeitet üblicherweise in drei Schritten, die nacheinander ausgeführt werden:
+  - **Lexer**: Der Lexer zerlegt den Programmtext in die kleinsten syntaktisch sinnvollen Einheiten ("Tokens").
+  - **Parser**: Der Parser analysiert die Liste der Tokens und erstellt daraus eine strukturelle Repräsentation des Programms, üblicherweise einen Baum ("Syntaxbaum" oder "abstract syntax tree" oder kurz: AST)
+  - **Interpreter/Codegenerator**: Ein Interpreter kann das als AST übergebene Programm direkt ausführen. Ein Codegenerator kann es in eine andere Programmiersprache (z.B. Maschinensprache) umwandeln.
+</WRAP>
-Ein Compiler ist ein Computerprogramm, das einen in einer Programmiersprache verfassten Programmtext einliest und in eine andere Programmiersprache umwandelt oder direkt ausführt. Er arbeitet üblicherweise in drei Schritten, die nacheinander ausgeführt werden:
-  - Lexer: Der Lexer zerlegt den Programmtext in die kleinsten syntaktisch sinnvollen Einheiten ("Tokens").
-  - Parser: Der Parser analysiert die Liste der Tokens und erstellt daraus eine strukturelle Repräsentation des Programms, üblicherweise einen Baum ("Syntaxbaum" oder "abstract syntax tree" oder kurz: AST)
-  - Interpreter/Codegenerator: Ein Interpreter kann das als AST übergebene Programm direkt ausführen. Ein Codegenerator kann es in eine andere Programmiersprache (z.B. Maschinensprache) umwandeln.
 Im Folgenden wird die Funktionsweise eines Compilers vorgestellt, der mathematische Terme (z.B. ''2 * (3 + a) - b'' ) mit gegebenen Variablenbelegungen zur Laufzeit auswerten kann. In einem zweiten Schritt wird dieser Compiler zu einer einfachen Programmiersprache [[.erweiterung:start|erweitert]], die Wiederholungen, Zuweisungen und eine einfach Print-Anweisung enthält.
+====== Inhalt dieses Tutorials ======
   * [[.lexer:start|a) Lexer]] \\
   * [[.parser:start|b) Parser]] \\
   * [[.interpreter:start|c) Interpreter]] \\
-  * [[.verwendung:start|d) Ausprobieren von Lexer, Parser und Interpreter!]] \\
   * [[.ebnf:start|e) Beschreibung der Grammatik mittels EBNF]] \\
   * [[.erweiterung:start|f) Erweiterung der Sprache]] \\
   * [[.aufgaben:start|g) Aufgaben]] \\
+====== Fertiges Programm zum Ausprobieren ======
+Ihr wollt sicher sehen, was der Compiler kann, der im Rahmen dieses Tutorials erstellt wird, daher hier gleich ein Blick auf das fertige Programm. \\ \\
+Unser Compiler unten bekommt ein kleines Testprogramm übergeben. Er verarbeitet es in drei Schritten:
+  - Der Lexer zerlegt das Programm in einzelne Tokens.
+  - Der Parser bekommt die Tokenliste und baut daraus den AST (abstract syntax tree) auf.
+  - Der Interpreter führ das Testprogramm aus, indem er den AST geeignet traversiert.
+Hier das Testprogramm, das unser Compiler übersetzen wird.:
+<code java>
+a = 1;
+b = 2;
+while(a < 10) {
+  a = a + 1;
+  b = b * 2;
+  print(b);
+}
+</code>
+<WRAP center round tip 80%>
+Schreibe weitere Testprogramme mit der oben angegebenen Syntax, füge sie unten ein und lasse sie vom Compiler übersetzen und ausführen!
+</WRAP>
+<HTML>
+<div class="java-online" style="height: 80vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'ErweiterungTest', 'speed': 'max'}">
+<script type="text/plain" title="Testprogramm.java">
+/**
+ * Der Text wird hier Stringkonstante definiert. Er könnte ebenso
+ * gut gerade vom Benutzer eingegeben worden sein. Wichtig ist: Der
+ * Java-Compiler compiliert hier nichts. Es wird alles durch unseren
+ * selbstprogrammierten Compiler (Lexer, Parser und Interpreter)
+ * übersetzt und ausgeführt.
+ */
+String text = """
+a = 1;
+b = 2;
+while(a < 10) {
+  a = a + 1;
+  b = b * 2;
+  print(b);
+}
+""";
+println("Eingabetext:\n" + text);
+/**
+ * Zerlegung des Programmtextes in Tokens:
+ */
+Lexer l = new Lexer(text);
+l.lex();
+println("\nTokens:\n" + l.toString());
+/**
+ * Bauen des Abstract Syntax Tree:
+ */
+Parser p = new Parser(l.getTokenListe());
+p.parse();
+println("\nSyntaxbaum (abstract syntax tree):\n" + p.toString());
+/**
+ * Ausführung des Programms
+ */
+Interpreter i = new Interpreter();
+println("\nAusgabe des Programms:\n");
+Wert wert = i.interpretiere(p.getWurzel());
+println("\nTermwert:\n" + wert);
+</script>
+<script type="text/plain" title="Interpreter.java">
+public class Interpreter {
+	/**
+	 * Speichert Zuordnungen von Variablenbezeichnern zu Werten:
+	 */
+  	private HashMap<String, Wert> variablenbelegung = new HashMap<>();
+	/**
+	 * Belegt die Variable mit Bezeichner bezeichner mit dem Wert wert.
+	 *
+	 * @param bezeichner
+	 *            Bezeichner der Variablen
+	 * @param wert
+	 *            Wert der Variablen
+	 */
+  	public void belegeVariable(String bezeichner, Wert wert) {
+    		variablenbelegung.put(bezeichner, wert);
+  	}
+	/**
+	 * Berechnet - ausgehend vom übergebenen Knoten - den Wert des Terms, der
+	 * durch den Knoten und den darunterhängenden Teilbaum gegeben ist.
+	 *
+	 * @param knoten
+	 *            Wurzel des Teilbaums, dessen Termwert berechnet werden soll
+	 * @return Wert des Terms
+	 * @throws Exception
+	 */
+  	public Wert interpretiere(Knoten knoten) {
+    		if(knoten != null) {
+      			switch(knoten.getToken().getTokenType()) {
+         			case plus :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert +
+               						interpretiere(knoten.getRechts()).doubleWert);
+         			case minus :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert -
+               						interpretiere(knoten.getRechts()).doubleWert);
+         			case mal :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert *
+               						interpretiere(knoten.getRechts()).doubleWert);
+         			case geteilt :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert /
+               						interpretiere(knoten.getRechts()).doubleWert);
+         			case negation :
+           				return new Wert(- interpretiere(knoten.getLinks()).doubleWert);
+         			case kleiner :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert <
+         								interpretiere(knoten.getRechts()).doubleWert);
+            			case groesser :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert >
+         								interpretiere(knoten.getRechts()).doubleWert);
+            			case kleinergleich :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert <=
+         								interpretiere(knoten.getRechts()).doubleWert);
+            			case groessergleich :
+           				return new Wert(
+          								interpretiere(knoten.getLinks()).doubleWert >=
+         								interpretiere(knoten.getRechts()).doubleWert);
+            			case identisch :
+              				Wert linkerWert = interpretiere(knoten.getLinks());
+              				if(linkerWert.typ == Typ.doubleTyp) {
+           						return new Wert(
+									interpretiere(knoten.getLinks()).doubleWert ==
+									interpretiere(knoten.getRechts()).doubleWert);
+              				} else {
+           						return new Wert(
+									interpretiere(knoten.getLinks()).booleanWert ==
+									interpretiere(knoten.getRechts()).booleanWert);
+              				}
+            			case ungleich :
+              				Wert linkerWert1 = interpretiere(knoten.getLinks());
+              				if(linkerWert1.typ == Typ.doubleTyp) {
+           						return new Wert(
+									interpretiere(knoten.getLinks()).doubleWert !=
+									interpretiere(knoten.getRechts()).doubleWert);
+              				} else {
+           						return new Wert(
+									interpretiere(knoten.getLinks()).booleanWert !=
+									interpretiere(knoten.getRechts()).booleanWert);
+              				}
+            			case trueKeyword :
+              				return new Wert(true);
+            			case falseKeyword :
+              				return new Wert(false);
+            			case text :
+              				String variablenbezeichner = knoten.getToken().getText();
+              				Wert wert = variablenbelegung.get(variablenbezeichner);
+              				if(wert == null) {
+                 				println("Die Belegung der Variable "
+                 							+ variablenbezeichner + " ist nicht bekannt.", Color.red);
+             								System.exit(1);
+              				}
+              				return wert;
+            			case zahl :
+              				return new Wert(knoten.getToken().getZahl());
+            			case whileKeyword :
+				/**
+				 * Im linken Knoten hat der Parser die Bedingung (also den Term
+				 * innerhalb von "(...)") abgelegt:
+				 */
+              				while(interpretiere(knoten.getLinks()).booleanWert) {
+					/**
+					 * Der rechte Knoten zeigt auf die erste Anweisung innerhalb
+					 * der Wiederholung. Die Methode interpretiere führt auch
+					 * gleich die nachfolgenden Anweisungen aus.
+					 */
+                					interpretiere(knoten.getRechts());
+              				}
+				/**
+				 * führe die Anweisungen aus, die auf die Wiederholung folgen,
+				 * also nach der "}"
+				 */
+              				interpretiere(knoten.getNaechsteAnweisung());
+              				return null;
+            			case zuweisung :
+              				String variablenbezeichner1 = knoten.getLinks().getToken()
+            						.getText();
+              				Wert wert1 = interpretiere(knoten.getRechts());
+				/**
+				 * Neuen Wert der Variable speichern:
+				 */
+              				variablenbelegung.put(variablenbezeichner1, wert1);
+				/**
+				 * Führe die Anweisungen aus, die nach der Zuweisung kommen:
+				 */
+              				interpretiere(knoten.getNaechsteAnweisung());
+              				return wert1;
+            			case printKeyword :
+				/**
+				 * Im linken Knoten steckt der Term, dessen Wert ausgegeben werden soll
+				 */
+								println(interpretiere(knoten.getLinks()), Color.lightblue);
+				/**
+				 * Führe die Anweisungen aus, die nach der Print-Anweisung kommen:
+				 */
+              				interpretiere(knoten.getNaechsteAnweisung());
+              				return null;
+            			default :
+              				return null; // sollte nie vorkommen
+         			}
+       		} else {
+         			return null;
+       		}
+     	}
+	/**
+	 * Nur zu Debuggingzwecken
+	 *
+	 * @return String, der alle Variablen zusammen mit ihrer Belegung in der
+	 *         Form variablenbezeichner = wert enthält.
+	 */
+     	public String getBelegungAlsString() {
+       		return variablenbelegung.toString();
+     	}
+   }
+</script>
+<script type="text/plain" title="Parser.java">
+public class Parser {
+	/**
+	 * Liste, die vom Lexer kommt
+	 */
+  	private ArrayList<Token> tokenListe;
+	/**
+	 * Zur Speicherung des Parse-Baums (Abstract Syntax Tree) reicht es, die
+	 * Wurzel zu speichern. Über sie bekommt man jeden beliebigen Knoten
+	 * darunter.
+	 */
+  	private Knoten wurzel;
+	/**
+	 * Nummer des Tokens, das gerade analysiert wird (von 0 beginnend)
+	 */
+  	private int position;
+	/**
+	 *
+	 * @param tokenListe
+	 *            Liste von Tokens, die geparst werden soll
+	 */
+  	public Parser(ArrayList<Token> tokenListe) {
+    		this.tokenListe = tokenListe;
+    		position = 0;
+  	}
+	/**
+	 * Parst die dem Konstruktor übergebene Liste von Tokens und gibt einen
+	 * Parse-Baum (Abstract Syntax Tree) zurück.
+	 *
+	 * @return Parse-Baum (Abstract Syntax Tree)
+	 *             Falls die Liste der Tokens nicht der Syntax entspricht
+	 */
+  	public Knoten parse() {
+    		wurzel = sequenz();
+    		return wurzel;
+  	}
+	/**
+	 * Parst eine Reihe von Anweisungen.
+	 *
+	 * @return
+	 */
+  	private Knoten sequenz() {
+    		Knoten knoten = null;
+    		Knoten ersteAnweisung = null;
+    		do {
+      			Knoten letzterKnoten = knoten;
+      			knoten = anweisung();
+      			if(letzterKnoten != null) {
+        				letzterKnoten.setNaechsteAnweisung(knoten);
+        				if(ersteAnweisung == null) {
+          					ersteAnweisung = letzterKnoten;
+        				}
+      			}
+    		} while(knoten != null);
+    		return ersteAnweisung;
+  	}
+	/**
+	 * Parst eine Anweisung, d.h. eine Wiederholung, eine Print-Anweisung oder
+	 * eine Zuweisung.
+	 *
+	 * @return
+	 */
+  	private Knoten anweisung() {
+    		if(peek() == null) {
+      			return null;
+    		}
+		/**
+		 * Eine Anweisung beginnt mit whileKeyword, printKeyword oder text:
+		 */
+    		switch(peek()) {
+       		case whileKeyword :
+         			return wiederholung();
+       		case printKeyword :
+         			return parsePrint();
+       		case text :
+         			return zuweisung();
+       		default :
+         			return null;
+    		}
+  	}
+	/**
+	 * Die Methode geht davon aus, dass das nächste Token vom Typ printKeyword
+	 * ist.
+	 *
+	 * @return
+	 */
+  	private Knoten parsePrint() {
+    		Knoten knoten = new Knoten(erwarte(TokenType.printKeyword));
+    		erwarte(TokenType.klammerAuf);
+    		Knoten aussage = aussage();
+    		erwarte(TokenType.klammerZu);
+    		erwarte(TokenType.strichpunkt);
+    		knoten.setLinks(aussage);
+    		return knoten;
+  	}
+	/**
+	 * Die Methode geht davon aus, dass das nächste Token vom Typ whileKeyword
+	 * ist.
+	 *
+	 * @return
+	 */
+  	private Knoten wiederholung() {
+    		Knoten knoten = new Knoten(erwarte(TokenType.whileKeyword));
+    		erwarte(TokenType.klammerAuf);
+    		Knoten aussage = aussage();
+    		erwarte(TokenType.klammerZu);
+    		erwarte(TokenType.geschweifteKlammerAuf);
+    		Knoten anweisungen = sequenz();
+    		erwarte(TokenType.geschweifteKlammerZu);
+    		knoten.setLinks(aussage);
+    		knoten.setRechts(anweisungen);
+    		return knoten;
+  	}
+	/**
+	 * Die Methode geht davon aus, dass das nächste Token vom Typ text ist.
+	 *
+	 * @return
+	 */
+  	private Knoten zuweisung() {
+    		Knoten linkeSeite = new Knoten(nextToken());
+    		Knoten knoten = new Knoten(erwarte(TokenType.zuweisung));
+    		Knoten rechteSeite = aussage();
+    		erwarte(TokenType.strichpunkt);
+    		knoten.setLinks(linkeSeite);
+    		knoten.setRechts(rechteSeite);
+    		return knoten;
+  	}
+	/**
+	 * Versucht, eine Aussage im Programmtext zu parsen. Weiteres: siehe Methode
+	 * SummeDifferenz.
+	 *
+	 * @return Geparster Teilbaum
+	 */
+  	private Knoten aussage() {
+    		Knoten linkerOperand = summeDifferenz(); // Versuche, eine
+													// Summe/Differenz zu finden
+    		while(peek() == TokenType.identisch || peek() == TokenType.ungleich
+        				|| peek() == TokenType.kleiner || peek() == TokenType.groesser
+        				|| peek() == TokenType.kleinergleich
+        				|| peek() == TokenType.groessergleich) {
+      			Token operator = nextToken();
+      			Knoten rechterOperand = summeDifferenz();
+      			Knoten neuerKnoten = new Knoten(operator, linkerOperand,
+       					rechterOperand);
+      			linkerOperand = neuerKnoten;
+    		}
+    		return linkerOperand;
+  	}
+	/**
+	 * Versucht, eine Summe oder Differenz zu parsen. Parst zunächst den ersten
+	 * Operanden (unter der Annahme, dass es eine Multiplikation oder Division
+	 * ist) und sieht dann nach, ob ein Pluszeichen oder ein Minuszeichen kommt.
+	 * Falls "ja", parst es den zweiten Operanden und fügt alle drei zu einem
+	 * Baum zusammen.
+	 *
+	 * Folgt ein weiteres Plus oder Minus, wird der Baum als erster Operand
+	 * einer weiteren Summe/Differenz gedeuet und nach dem zweiten Operanden
+	 * dazu gesucht usw.
+	 *
+	 * Folgt kein weiteres Plus oder Minus, so endet die Methode und der
+	 * aktuelle Baum wird zurückgegeben.
+	 *
+	 * @return Geparster Teilbaum
+	 */
+  	private Knoten summeDifferenz() {
+    		Knoten linkerOperand = produktQuotient(); // Versuche, eine
+													// Multiplikation
+													// oder Division zu finden
+    		while(peek() == TokenType.plus || peek() == TokenType.minus) {
+      			Token operator = nextToken();
+      			Knoten rechterOperand = produktQuotient();
+      			Knoten neuerKnoten = new Knoten(operator, linkerOperand,
+       					rechterOperand);
+      			linkerOperand = neuerKnoten;
+    		}
+    		return linkerOperand;
+  	}
+	/**
+	 * Wie PlusMinus, jedoch für Mal und geteilt. Als erster bzw. zweiter
+	 * Operand wird nach einem einfachen Term (Klammerterm, Zahl, Variable oder
+	 * Negation) gesucht.
+	 *
+	 * @return
+	 */
+  	private Knoten produktQuotient() {
+    		Knoten linkerOperand = einfacherTerm();
+    		while(peek() == TokenType.mal || peek() == TokenType.geteilt) {
+      			Token operator = nextToken();
+      			Knoten rechterOperand = einfacherTerm();
+      			Knoten neuerKnoten = new Knoten(operator, linkerOperand,
+       					rechterOperand);
+      			linkerOperand = neuerKnoten;
+    		}
+    		return linkerOperand;
+  	}
+  	private Knoten einfacherTerm() {
+    		if(peek() == null) {
+      			println("Parserfehler: unerwartetes Ende", Color.red);
+         System.exit(1);
+    		}
+    		switch(peek()) {
+       		case klammerAuf : // Klammerterm
+         			nextToken();
+         			Knoten knoten = summeDifferenz(); // In der Klammer kann sich wieder
+												// eine
+												// Summe/Differenz befinden...
+         			erwarte(TokenType.klammerZu); // Überliest die schließende Klammer
+         			return knoten;
+       		case text :
+         			return new Knoten(nextToken());
+       		case zahl :
+         			return new Knoten(nextToken());
+       		case minus :
+         			Knoten knoten1 = new Knoten(new Token(TokenType.negation));
+         			nextToken(); // überliest das Minuszeichen
+         			knoten1.setLinks(einfacherTerm()); // die Negation wirkt auf den
+												// einfachen
+			// Term danach
+         			return knoten1;
+       		default :
+         			println("Das Token " + peek() + " ist fehl am Platz.", Color.red);
+            System.exit(1);
+    		}
+  	}
+	/**
+	 * Gibt das nächste Token aus der Tokenliste zurück, erhöht aber nicht die
+	 * Leseposition
+	 *
+	 * @return
+	 */
+  	public TokenType peek() {
+    		if(position < tokenListe.size()) {
+      			return tokenListe.get(position).getTokenType();
+    		}
+    		return null;
+  	}
+	/**
+	 * Gibt das nächste Token aus der Tokenliste zurück und erhöht(!) die
+	 * Leseposition
+	 *
+	 * @return
+	 */
+  	public Token nextToken() {
+    		if(position < tokenListe.size()) {
+      			Token token = tokenListe.get(position);
+      			position++;
+      			return token;
+    		}
+    		return null;
+  	}
+	/**
+	 * Wirft eine Exception, wenn das nächste Token in der Tokenliste nicht dem
+	 * übergebenen Typ entspricht.
+	 *
+	 * @param tokenType
+	 */
+  	public Token erwarte(TokenType tokenType) {
+    		if(peek() == null) {
+      			println("Parserfehler: unerwartetes Ende. Erwartet wird: "
+        							+ tokenType, Color.red);
+         System.exit(1);
+    		}
+    		if(peek() != tokenType) {
+      			println("Parserfehler: Erwartet wird: " + tokenType, Color.red);
+         System.exit(1);
+    		}
+    		return nextToken();
+  	}
+	/**
+	 * Nur zu Debuggingzwecken
+	 */
+  	public String toString() {
+      return toString(wurzel, "", "");
+  	}
+	/**
+	 * Traversiert vom übergebenen Knoten ausgehend den Teilbaum in pre-order
+	 * Reihenfolge, d.h. zuerst wird der Konten selbst besucht, dann der
+	 * komplette linke Teilbaum, der dranhängt, dann der komplette rechte
+	 * Teilbaum, der dranhängt.
+	 *
+	 * @param knoten
+	 * @param einruecken
+	 * @param sb
+	 */
+  	private String toString(Knoten knoten, String einruecken, String kante) {
+      String s = "";
+      s += einruecken + kante;
+      s += knoten.getToken().toString() + "\n";
+      if(knoten.getLinks() != null) {
+            s += toString(knoten.getLinks(), einruecken + "   ", "l:");
+      }
+      if(knoten.getRechts() != null) {
+            s += toString(knoten.getRechts(), einruecken + "   ", "r:");
+      }
+      if(knoten.getNaechsteAnweisung() != null) {
+            s += toString(knoten.getNaechsteAnweisung(), einruecken + "   ", "n:");
+      }
+      return s;
+  	}
+  	public Knoten getWurzel() {
+    		return wurzel;
+  	}
+}
+</script>
+<script type="text/plain" title="Lexer.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
+  	}
+	/**
+	 * 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 '{' :
+             					addToken(TokenType.geschweifteKlammerAuf);
+             					break;
+           				case '}' :
+             					addToken(TokenType.geschweifteKlammerZu);
+             					break;
+           				case ';' :
+             					addToken(TokenType.strichpunkt);
+             					break;
+           				case '<' :
+             					if(peek(1) == '=') {
+               						addToken(TokenType.kleinergleich);
+               						position++;
+             					} else {
+               						addToken(TokenType.kleiner);
+             					}
+             					break;
+           				case '>' :
+             					if(peek(1) == '=') {
+               						addToken(TokenType.groessergleich);
+               						position++;
+             					} else {
+               						addToken(TokenType.groesser);
+             					}
+             					break;
+           				case '!' :
+             					if(peek(1) == '=') {
+               						addToken(TokenType.ungleich);
+               						position++;
+             					} else {
+               						println("Das Zeichen = wird erwartet.", Color.red);
+                                 System.exit(1);
+             					}
+             					break;
+           				case '=' :
+             					if(peek(1) == '=') {
+               						addToken(TokenType.identisch);
+               						position++;
+             					} else {
+               						addToken(TokenType.zuweisung);
+             					}
+             					break;
+           				case ' ' :
+           				case '\n' :
+           				case '\r' :
+					// Leerzeichen werden einfach überlesen
+             					break;
+           				default :
+             					println("Der Lexer kann mit dem Zeichen '" + c
+                 							+ "' an Position " + position + " nichts anfangen.", Color.red);
+                  System.exit(1);
+        				}
+        				position++; // Das von peek() oben gelesene Zeichen ist
+							// verarbeitet, also jetzt das nächste holen.
+      			}
+    		}
+    		return tokenListe;
+  	}
+	/**
+	 * Die Methode lexText lext Variablenbezeichner und Schlüsselwörter (keywords)
+	 */
+  	private void lexText() {
+    		String text = "";
+    		do {
+      			char c = peek();
+      			text += c;
+      			position++;
+    		} while(istBuchstabe(peek()) || istZiffer(peek()) || peek() == '_');
+    		switch(text) {
+       		case "true" :
+         			tokenListe.add(new Token(TokenType.trueKeyword));
+         			break;
+       		case "false" :
+         			tokenListe.add(new Token(TokenType.falseKeyword));
+         			break;
+       		case "while" :
+         			tokenListe.add(new Token(TokenType.whileKeyword));
+         			break;
+       		case "print" :
+         			tokenListe.add(new Token(TokenType.printKeyword));
+         			break;
+       		default :
+         			tokenListe.add(new Token(text));
+         			break;
+    		}
+  	}
+	/**
+	 * Die Methode lexZahl liest eine Zahl
+	 */
+  	private void lexZahl() {
+    		String zahlAlsString = "";
+    		do {
+      			char c = peek();
+      			zahlAlsString += c;
+      			position++;
+    		} while(istZiffer(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));
+  	}
+	/**
+	 * Fügt der tokenListe das übergebene Token hinzu
+	 *
+	 * @param tokenType
+	 */
+  	private void addToken(TokenType tokenType) {
+    		tokenListe.add(new Token(tokenType));
+  	}
+	/**
+	 * 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(char) 0;
+    		}
+  	}
+	/**
+	 * peek(n) liest das Zeichen im Programmtext an (aktuelle Position + n). Die
+	 * aktuelle Position (Attribut position) wird nicht verändert.
+	 *
+	 * @return Das Zeichen, das n Zeichen weiter steht als die aktuelle Position
+	 */
+  	private char peek(int n) {
+    		if(position + n < text.length()) {
+      			return text.charAt(position + n);
+    		} else {
+      			return(char) 0;
+    		}
+  	}
+	/**
+	 *
+	 * @param c
+	 *            beliebiges zeichen
+	 * @return true, falls c eine Ziffer ist
+	 */
+  	private boolean istZiffer(char c) {
+    		return c >= '0' && c <= '9';
+  	}
+	/**
+	 *
+	 * @param c
+	 *            beliebiges Zeichen
+	 * @return true, falls c ein Buchstabe ist
+	 */
+  	private boolean istBuchstabe(char c) {
+    		return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
+  	}
+	/**
+	 * 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;
+  	}
+}
+</script>
+<script type="text/plain" title="Knoten.java">
+public class Knoten {
+	/**
+	 * Im Token steckt der Inhalt des Knotens drin, also ein Operator, eine Zahl oder ein
+	 * Variablenbezeichner. Der Einfachheit halber verwenden wir hier die Klasse Token.
+	 */
+	private Token token;
+	/**
+	 * Kindknoten linkerhand
+	 */
+	private Knoten links;
+	/**
+	 * Kindknoten rechterhand
+	 */
+	private Knoten rechts;
+	/**
+	 * Im Falle einer Anweisung: nächstfolgende Anweisung
+	 */
+	private Knoten naechsteAnweisung;
+	public Knoten(Token token) {
+		this.token = token;
+	}
+	public Knoten(Token token, Knoten linkerOperand, Knoten rechterOperand) {
+		this.token = token;
+		this.links = linkerOperand;
+		this.rechts = rechterOperand;
+	}
+	public Knoten getLinks() {
+		return links;
+	}
+	public void setLinks(Knoten links) {
+		this.links = links;
+	}
+	public Knoten getRechts() {
+		return rechts;
+	}
+	public void setRechts(Knoten rechts) {
+		this.rechts = rechts;
+	}
+	public Token getToken() {
+		return token;
+	}
+	public Knoten getNaechsteAnweisung() {
+		return naechsteAnweisung;
+	}
+	public void setNaechsteAnweisung(Knoten naechsteAnweisung) {
+		this.naechsteAnweisung = naechsteAnweisung;
+	}
+}
+</script>
+<script type="text/plain" title="Token, TokenType.java">
+public enum TokenType {
+  	zahl, text, plus, minus, mal, geteilt, klammerAuf, klammerZu,
+  	geschweifteKlammerAuf, geschweifteKlammerZu,
+  	whileKeyword, printKeyword,
+  	kleiner, groesser, identisch, kleinergleich, groessergleich, ungleich,
+  	zuweisung,
+  	trueKeyword, falseKeyword,
+  	strichpunkt,
+	/**
+	 * Nur als Knotentyp für Knoten des Syntaxbaums:
+	 */
+  	negation
+}
+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
+	 */
+	public String toString() {
+		String s = "" + tokenType;
+		switch (tokenType) {
+		case zahl:
+			s += "[" + zahl + "]";
+			break;
+		case text:
+			s += "[" + text + "]";
+			break;
+		default:
+			break;
+		}
+		return s;
+	}
+}
+</script>
+<script type="text/plain" title="Wert.java">
+/**
+ * Datentyp des gespeicherten Wertes
+ */
+enum Typ {
+   doubleTyp, booleanTyp
+}
+/**
+ * Ein Objekt der Klasse Wert kann einen boolean- oder double-Wert speichern.
+ * Der aktuell gespeicherte Datentyp ist im Attribut Typ hinterlegt.
+ */
+class Wert {
+   Typ typ;
+   double doubleWert;
+   boolean booleanWert;
+   public Wert(double d) {
+      this.doubleWert = d;
+      this.typ = Typ.doubleTyp;
+   }
+   public Wert(boolean b) {
+      this.booleanWert = b;
+      this.typ = Typ.booleanTyp;
+   }
+   public String toString() {
+      if(typ == Typ.doubleTyp) {
+         return doubleWert;
+      } else {
+         return booleanWert;
+      }
+   }
+}
+</script>
+</div>
+</HTML>