Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- compilerbau:erweiterung:start [2021/10/28 21:12] – angelegt Martin Pabst
+++ compilerbau:erweiterung:start [2021/10/28 21:30] – [Test des Parsers] Martin Pabst
@@ Zeile 15: / Zeile 15: @@
 ===== Erweiterung der Grammatik =====
-Die [[..ebnf:start|EBNF]] dieser Sprache sieht so aus:
+Die Grammatik dieser Sprache in [[..ebnf:start|EBNF]] sieht so aus:
 <code bnf>
 Ziffer   = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
@@ Zeile 41: / Zeile 41: @@
 </code>
+===== Neue Tokentypen =====
+Für die neuen syntaktischen Elemente brauchen wir zusätzliche Tokentypen:
+<code 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
+}
+</code>
+===== Erweiterung des Lexers =====
+Damit der Lexer die Schlüsselwörter ''while'', ''print'', ''true'' und ''false'' erkennt, erweitern wir einfach die Methode ''lexText()'':
+<code java>
+	/**
+	 * 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;
+    		}
+  	}
+</code>
+Etwas trickreicher sind die neuen Zeichen. Um etwa ''<'' und ''< ='' unterscheiden zu können, muss der Lexer ein Zeichen nach vorne blicken können. Wir brauchen daher eine zusätzliche ''peek(int n)''-Methode, die ''n'' Zeichen nach vorne blickt:
+<code java>
+	/**
+	 * 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;
+    		}
+  	}
+</code>
+Damit sieht die Erkennung von ''>'', ''>='' und ''!='' so aus:
+<code java>
+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;
+</code>
+===== Test des Lexers =====
+Der Lexer lässt sich wieder mit der Klasse ''LexerTest'' testen. Den Programmtext oben zerlegt er beispielsweise in folgende Token:
+<code>
+text[a] zuweisung zahl[1.0] strichpunkt text[b] zuweisung zahl[2.0] strichpunkt whileKeyword klammerAuf text[a] kleiner zahl[10.0] klammerZu geschweifteKlammerAuf text[a] zuweisung text[a] plus zahl[1.0] strichpunkt text[b] zuweisung text[b] mal zahl[2.0] strichpunkt printKeyword klammerAuf text[b] klammerZu strichpunkt geschweifteKlammerZu
+</code>
+===== Erweiterung der Klasse Knoten =====
+Auch Anweisungen (Wiederholung, Zuweisung, Print-Anweisung) werden im Syntaxbaum als Knoten dargestellt. Dafür wird neben den Kindknoten ''rechts'' und ''links'' noch ein dritter KindKnoten ''naechsteAnweisung'' benötigt:
+<code 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;
+...
+</code>
+Die Kindknoten der Anweisungen haben für verschiedene Arten von Anweisungen verschiedene Bedeutung:
+**wiederholungs-Knoten:**
+  * links: Aussage innerhalb der Klammer
+  * rechts: erste Anweisung innerhalb des while-Blocks (d.h. innerhalb der geschweiften Klammern)
+  * naechsteAnweisung: Erste Anweisung, die der while-Anweisung folgt (d.h. erste Anweisung nach der schließenden geschweiften Klammer)
+**print-Knoten:**
+  * links: Aussage, deren wert ausgegeben werden soll
+  * rechts: ''null''
+  * naechsteAnweisung: Die Anweisung, die auf die print-Anweisung folgt.
+**Zuweisungs-Knoten:**
+  * links: text-Knoten, der den Bezeichner der Variablen enthält, der etwas zugewiesen werden soll.
+  * rechts: Aussage, deren Wert der Variablen zugewiesen werden soll.
+  * naechsteAnweisung: Die Anweisung, die auf die Zuweisung folgt.
+===== Erweiterung des Parsers =====
+Die Klasse Parser wird um Methoden zum Parsen von
+  * einer Aussage
+  * einer Wiederholung
+  * einer Zuweisung
+  * einer Print-Anweisung
+  * einer Anweisung (d.h. eine beliebige der drei vorhergehenden)
+  * einer Sequenz (d.h. einer beliebig langen Abfolge von Anweisungen)
+erweitert:
+<code java>
+public class Parser {
+...
+	/**
+	 * 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;
+  	}
+...
+}
+</code>
+Ansonsten muss nichts am Parser geändert werden.
+===== Test des Parsers =====
+Der Parser lässt sich wieder mit der Klasse ''ParserTest'' testen. Den Programmtext oben konvertiert er in folgenden Baum:
+<code>
+Eingabetext:
+a = 1;
+b = 2;
+while(a < 10){
+  a = a + 1;
+  b = b * 2;
+  print(b);
+}
+Tokens:
+text[a] zuweisung zahl[1.0] strichpunkt text[b] zuweisung zahl[2.0] strichpunkt whileKeyword klammerAuf text[a] kleiner zahl[10.0] klammerZu geschweifteKlammerAuf text[a] zuweisung text[a] plus zahl[1.0] strichpunkt text[b] zuweisung text[b] mal zahl[2.0] strichpunkt printKeyword klammerAuf text[b] klammerZu strichpunkt geschweifteKlammerZu
+Syntaxbaum (AST):
+zuweisung
+   l:text[a]
+   r:zahl[1.0]
+   n:zuweisung
+      l:text[b]
+      r:zahl[2.0]
+      n:whileKeyword
+         l:kleiner
+            l:text[a]
+            r:zahl[10.0]
+         r:zuweisung
+            l:text[a]
+            r:plus
+               l:text[a]
+               r:zahl[1.0]
+            n:zuweisung
+               l:text[b]
+               r:mal
+                  l:text[b]
+                  r:zahl[2.0]
+               n:printKeyword
+                  l:text[b]
+</code>
+Nachfolgend noch in grafischer Form. Die mit "n" bezeichneten Kanten entsprechen dem Wert des Attributs ''naechsteAnweisung'' im Knoten.
+{{ :compilerbau:erweiterung:pasted:20211028-212546.png?700 }}
+===== Erweiterung des Interpreters ======
+===== Mehrere Datentypen =====