Pabst-Software

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Erweiterung der Sprache ======
Bisher kennt unsere Programmiersprache nur Terme (expressions), keine Anweisungen (statements). Wir wollen sie daher erweitern, so dass beispielsweise folgendes Programm kompiliert und ausgeführt werden kann:

<code java>
a = 1;
b = 2;
while(a < 10){
  a = a + 1;
  b = b * 2;
  print(b);
}
</code>

===== Quelltext =====
Hier der {{:programmieren:erweiterung:extendedparser.zip|Quelltext zum Download.}}
===== Erweiterung der Grammatik =====

Die [[programmieren:ebnf:start|EBNF]] dieser Sprache sieht so aus:
<code bnf>
Ziffer   = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
Buchstabe =  "A" | "B" | "C" | "D" | … | "Z" | "a" | "b" | … | "z" ;
Zahl = Ziffer { Ziffer | "." } ;
Text = Buchstabe { Buchstabe | Ziffer | "_" } ;
TrueFalse = "true" | "false" ;
Term = "(" Aussage ")" | Zahl | Text | TrueFalse | "-" Term ;
Produkt = Term | Term "*" Term ;
Quotient = Term | Term "/" Term ;
ProduktQuotient = Produkt | Quotient ;
Summe = ProduktQuotient | ProduktQuotient "+" ProduktQuotient ;
Differenz = ProduktQuotient | ProduktQuotient "-" ProduktQuotient ;
SummeDifferenz = Summe | Differenz ;
Vergleichsoperator = "<" | ">" | "==" | "<=" | ">=" | "!=" ;
Aussage = SummeDifferenz | SummeDifferenz Vergleichsoperator SummeDifferenz ;

Zuweisung = Text "=" Aussage ";"
Wiederholung = "while" "(" Aussage ")" "{" Sequenz "}" ;
Ausgabe = "print" "(" Aussage ")" ;
Anweisung = Zuweisung | Wiederholung | Ausgabe ;
Sequenz = { Anweisung };

Programm = Sequenz ;

</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,
	
	/**
	 * 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 lexVariable 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 Text zusammen.
	 */
	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 {
						throw new Exception("Das Zeichen = wird erwartet.");
					}
					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>
	/**
	 * Parst die dem Konstruktor übergebene Liste von Tokens und gibt einen
	 * Parse-Baum (Abstract Syntax Tree) zurück.
	 * 
	 * @return Parse-Baum (Abstract Syntax Tree)
	 * @throws Exception
	 *             Falls die Liste der Tokens nicht der Syntax entspricht
	 */
	public Knoten parse() throws Exception {

		wurzel = sequenz(); 

		return wurzel;

	}

	/**
	 * Parst eine Reihe von Anweisungen.
	 * 
	 * @return
	 * @throws Exception
	 */
	private Knoten sequenz() throws Exception {
		
		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
	 * @throws Exception
	 */
	private Knoten anweisung() throws Exception {

		if(peek() == null){
			return null;
		}
		/**
		 * Eine Anweisung beginnt mit whileKeyword, printKeyword oder text:
		 */
		switch (peek()) {
		case whileKeyword:
			return wiederholung();
		case printKeyword:
			return print();
		case text:
			return zuweisung();
		default:
			return null;
		}

	}

	/**
	 * Die Methode geht davon aus, dass das nächste Token vom Typ printKeyword
	 * ist.
	 * 
	 * @return
	 * @throws Exception
	 */
	private Knoten print() throws Exception {

		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
	 * @throws Exception
	 */
	private Knoten wiederholung() throws Exception {

		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
	 * @throws Exception
	 */
	private Knoten zuweisung() throws Exception {

		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
	 * @throws Exception
	 */
	private Knoten aussage() throws Exception {

		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.
{{ :programmieren:erweiterung:ast_einfaches_programm.png | AST des einfachen Beispielprogramms}}

===== Erweiterung des Interpreters =====

===== Mehrere Datentypen =====
Die größte Herausforderung bei der Erweiterung des Interpreters ist, dass Term- und Variablenwerte jetzt zwei verschiedene Datentypen haben können. Der Term ''10 + 4'' etwa hat den Datentyp ''Double'', der Term ''10 > 2'' hat den Datentyp Boolean. Unsere Programmiersprache ist [[http://en.wikipedia.org/wiki/Strong_and_weak_typing| weakly typed]]. Das hat die Konsequenz, dass der Datentyp von Variablen erst zur Laufzeit (also im Interpreter) offenbar wird. Entsprechend muss sich dieser darum kümmern. \\
Die einfachste (aber nicht: beste) Lösung besteht darin, den Rückgabewert der Methode ''interpretiere'' auf ''Object'' zu ändern und bei jeder Berechnung anhand des Operators zu entscheiden, ob die Operanden auf ''Double'' oder ''Boolean'' [[http://en.wikipedia.org/wiki/Type_conversion|gecastet]] werden müssen. Schwierig wird es bei den Vergleichsoperatoren '==' und '!=', da sie sowohl mit Booleschen als auch mit numerischen Operanden Sinn machen. \\

Der erste Änderungsschritt besteht darin, die ''HashMap'' zur Speicherung der Variablenbelegungen so zu ändern, dass sie als Variablenwerte beliebige Objekte (also insbes. ''Double-Objekte'' und ''Boolean-Objekte'') akzeptiert:

<code java>
public class Interpreter {

	/**
	 * Speichert Zuordnungen von Variablenbezeichnern zu Werten:
	 */
	private HashMap<String, Object> variablenbelegung = new HashMap<>();
</code>

Die Methode ''interpretiere'' gibt jetzt Objekte der Klasse ''Object'' zurück (d.h. ''Double'' oder ''Boolean'' oder null). Am Anfang der Methode wird jetzt sichergestellt, dass ''knoten != null'' ist, da im Falle einer Sequenz nach dem Ausführen der letzten Anweisung die Methode ''interpretiere'' mit dem Wert des Attributs ''naechsterKnoten'' dieser Anweisung aufgerufen wird, und da steckt dann ''null'' drin. Die ''switch''-Verzweigung als zentraler Bestandteil der Methode ''interpretiere'' bleibt.

<code>
	/**
	 * 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 Object interpretiere(Knoten knoten) throws Exception {

		if (knoten != null) {

			switch (knoten.getToken().getTokenType()) {
</code>

Bei der Berechnung der Rückgabewerte müssen die Termwerte des linken und rechten Operanden jeweils passend interpretiert ("gecastet") werden. Für den Operator ''plus'' sieht das beispielsweise so aus:

<code java>
			case plus:
				return (Double) interpretiere(knoten.getLinks())
						+ (Double) interpretiere(knoten.getRechts());
</code>

Für die anderen Operatoren sieht das entsprechend aus. Trickreich wird es nur bei den Vergleichsoperatoren ''=='' und ''!='', da sie sowohl mit numerischen als auch mit booleschen Operanden Sinn machen. Hier wird anhand der Klasse des linken Operanden entschieden, wie gecastet wird:

<code>
			case ungleich:

				Object linkerWert1 = interpretiere(knoten.getLinks());

				if (linkerWert1.getClass() == Double.class) {
					return (Double) interpretiere(knoten.getLinks()) != (Double) interpretiere(knoten
							.getRechts());
				} else {
					return (Boolean) interpretiere(knoten.getLinks()) != (Boolean) interpretiere(knoten
							.getRechts());
				}
</code>

Die Knoten, die einer Wiederholung, Zuweisung oder Print-Anweisung entsprechen, werden vom nachfolgenden Code interpretiert:

<code>
			case zuweisung:
				String variablenbezeichner1 = knoten.getLinks().getToken()
						.getText();

				Object 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
				 */
				System.out.println(interpretiere(knoten.getLinks()));

				/**
				 * Führe die Anweisungen aus, die nach der Print-Anweisung kommen:
				 */
				interpretiere(knoten.getNaechsteAnweisung());

				return null;
</code>

Dadurch, dass am Ende jeder Anweisung mittels ''interpretiere(knoten.getNaechsteAnweisung());'' gleich die nächstfolgende Anweisung ausgeführt wird, wird sichergestellt, dass das ganze Programm abgearbeitet wird.

===== Test des Interpreters =====
Der Lexer lässt sich mit der Klasse ''InterpreterTest'' testen. Hier die Codestelle, die das Programm ausführt:

<code java>
			/**
			 * Ausführung des Programms
			 */

			Interpreter i = new Interpreter();

			System.out.println("\nAusgabe des Programms:\n");			
			
			Object wert = i.interpretiere(p.getWurzel());
			
			System.out
					.println("\nTermwert:\n" + wert);
</code>

Innerhalb der Ausgabe sieht man auch die Ausgabe des interpretierten Programms:

<code>
Eingabetext:
a = 1;
b = 2;
while(a < 10){
  a = a + 1;
  b = b * 2;
  print(b);
}

Bem.: An dieser Stelle gibt der Interpreter auch die Tokenliste und den Syntaxbaum aus. Sie sind weiter oben auf dieser Seite unter "Test des Parsers" zu sehen.

Ausgabe des Programms:

4.0
8.0
16.0
32.0
64.0
128.0
256.0
512.0
1024.0

Termwert:
1.0
</code>

**Kleine Denkaufgabe:** Woher kommt am Ende der Termwert ''1.0''? \\ 

Bei der Implementierung des Compilers wurden viele Kompromisse eingegangen, um den Code einfachstmöglich zu halten:

  * Die Fehlermeldungen könnten ausführlicher sein
  * Die Performance des Lexers kann verbessert werden
  * Starke Typisierung wäre wünschenswert
  * Die Typen der Knoten des Syntaxbaums sollten von den Typen der Tokens unterschieden werden
  * ...

**Aber:** Er läuft! :-)