Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- compilerbau:parser:start [2021/10/28 20:43] – angelegt Martin Pabst
+++ compilerbau:parser:start [2021/12/29 11:29] (aktuell) – Externe Bearbeitung 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
 ====== Parser ======
+<WRAP center round tip 60%>
+Im folgenden findest Du die Beschreibung des Parsers. Den [[.test:start|fertigen Parser zusammen mit einem direkt im Browser ausführbaren Testprogramm findest Du hier]].
+</WRAP>
 Der Parser analysiert die Liste der Tokens anhand einer gegebenen Syntax und erstellt eine Baumstruktur ("Abstract Syntax Tree"), die die Bedeutung ("Semantik") des Programmtextes wiedergibt. Die Syntax unserer einfachen Beispielsprache entspricht der einfacher mathematischer Terme:
@@ Zeile 72: / Zeile 75: @@
 }
 </code>
+Will man auf einen Baum im Programm zugreifen, so reicht es, seine Wurzel in einem Attribut zu speichern. Durch sukzessiven Aufruf von getRechts() und getLinks() bekommt man jeden beliebigen Knoten unterhalb.
+===== Die Klasse Parser =====
+Es gibt verschiedene Arten, einen Parser zu programmieren. Die einfachste, "von Hand" machbare Art ist ein [[http://en.wikipedia.org/wiki/Recursive_descent_parser|recursive descent parser]]. Um die Idee dahinter zu begreifen, geht man im konkreten Beispiel von folgender Deutung der Syntax aus:
+  * Eine Summe besteht aus
+    * einem Produkt/Quotienten (=linker Summand), einem Pluszeichen und einem weiteren Produkt/Quotienten (rechter Summand) oder
+    * **ausschließlich** aus einem Produkt/Quotienten
+  * Ein Produkt besteht aus
+    * einem "einfachen Term" (=linker Faktor), einem Malzeichen und einem weiteren "einfachen Term" (rechter Faktor) oder
+    * **ausschließlich** aus einem "einfachen Term".
+  * Analog mit Differenz bzw. Quotient
+  * Ein "einfacher Term" besteht aus
+    * einer öffnenden Klammer, einer Summe(bzw. Differenz) und einer schließenden Klammer oder
+    * einem Minuszeichen gefolgt von einem "einfachen Term" oder
+    * einer Variablen oder
+    * einer Zahl.
+**Bem.:** In dieser Beschreibung steckt implizit schon drin, dass "Punkt vor Strich" gilt. \\
+Obiger Beschreibung folgend ruft die Methode ''summeDifferenz()'' zunächst die Methode ''produktQuotient()'' auf, um den ersten Summanden (bzw. Minuend) zu ermitteln. Folgt danach ein + oder ein -, so handelt es sich um eine "echte" Summe/Differenz und es wird anschließend nochmals ''produktQuotient'' aufgerufen, um den zweiten Summanden (bzw. den Subtrahenden) zu parsen. Folgt weder ein + noch ein Minus, so besteht die komplette Summe nur aus einem Produkt. \\
+Falls eine echte Summe vorliegt, kann diese natürlich wiederum der erste Summand einer weiteren Summe sein (''1 + 2'' ist der erste Summand von ''1 + 2 + 3''. Daher wird in ersterem Fall am Ende überprüft, ob nochmals ein + oder - vorliegt und ggf. das ganze wiederholt. \\ \\
+Die Methode ''produktQuotient()'' ist ganz analog zu ''summeDifferenz()'' programmiert. Sie sucht als ersten Summanden einen einfachen Term, ... \\  \\
+Insgesamt erkennt man am Vorgehen die Namensgebung: Durch rekursive Aufrufe ("recursive") parst man die Tokenliste und erzeugt absteigend ("descent") den Parse-Baum (Abstract Syntax Tree). \\ \\
+Die Einzelheiten der Programmierung kann man am besten am kommentierten Sourcecode ersehen.
+===== Sourcecode =====
+<code 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 = summeDifferenz(); // Versuche, eine Summe oder Differenz zu finden
+    		return wurzel;
+  	}
+	/**
+	 * 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");
+         System.exit(0);
+    		}
+    		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.");
+            System.exit(0);
+    		}
+  	}
+	/**
+	 * 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 void erwarte(TokenType tokenType) {
+    		if(peek() == null) {
+      			println(
+       					"Parserfehler: unerwartetes Ende. Erwartet wird: "
+        							+ tokenType);
+         System.exit(0);
+    		}
+    		if(peek() != tokenType) {
+      			println("Parserfehler: Erwartet wird: " + tokenType);
+         System.exit(0);
+    		}
+    		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 sb = "";
+      sb += einruecken;
+      sb += knoten.getToken().toString() + "\n";
+      if(knoten.getLinks() != null) {
+         sb += toString(knoten.getLinks(), einruecken + "   ");
+      }
+      if(knoten.getRechts() != null) {
+         sb += toString(knoten.getRechts(), einruecken + "   ");
+      }
+      return sb;
+  	}
+  	public Knoten getWurzel() {
+    		return wurzel;
+  	}
+}
+</code>
+[[..interpreter:start|Hier geht's weiter zur Beschreibung des Interpreters!]]