Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Nächste Überarbeitung		Vorhergehende Überarbeitung
programmieren:erweiterung:start [2015/02/06 08:52] – Externe Bearbeitung 127.0.0.1programmieren:erweiterung:start [2021/12/29 10:40] (aktuell) – Externe Bearbeitung 127.0.0.1
Zeile 1: Zeile 1:
 +====== 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! :-)
 +
  

Zuletzt angesehen:

Drucken/exportieren
QR-Code
QR-Code programmieren:erweiterung:start (erstellt für aktuelle Seite)