compilerbau:erweiterung:start
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | compilerbau:erweiterung:start [2024/08/31 12:03] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Erweiterung der Sprache ====== | ||
+ | <WRAP center round tip 60%> | ||
+ | Im folgenden zeige ich Dir, wie Du die Sprache, die unser Lexer/ | ||
+ | </ | ||
+ | |||
+ | Bisher kennt unsere Programmiersprache nur Terme (expressions), | ||
+ | |||
+ | <code java> | ||
+ | a = 1; | ||
+ | b = 2; | ||
+ | while(a < 10){ | ||
+ | a = a + 1; | ||
+ | b = b * 2; | ||
+ | print(b); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | ===== Erweiterung der Grammatik ===== | ||
+ | |||
+ | Die Grammatik dieser Sprache in [[..ebnf: | ||
+ | <code bnf> | ||
+ | Ziffer | ||
+ | Buchstabe = " | ||
+ | Zahl = Ziffer { Ziffer | " | ||
+ | Text = Buchstabe { Buchstabe | Ziffer | " | ||
+ | TrueFalse = " | ||
+ | Term = " | ||
+ | Produkt = Term | Term " | ||
+ | Quotient = Term | Term "/" | ||
+ | ProduktQuotient = Produkt | Quotient ; | ||
+ | Summe = ProduktQuotient | ProduktQuotient " | ||
+ | Differenz = ProduktQuotient | ProduktQuotient " | ||
+ | SummeDifferenz = Summe | Differenz ; | ||
+ | Vergleichsoperator = "<" | ||
+ | Aussage = SummeDifferenz | SummeDifferenz Vergleichsoperator SummeDifferenz ; | ||
+ | |||
+ | Zuweisung = Text " | ||
+ | Wiederholung = " | ||
+ | Ausgabe = " | ||
+ | Anweisung = Zuweisung | Wiederholung | Ausgabe ; | ||
+ | Sequenz = { Anweisung }; | ||
+ | |||
+ | Programm = Sequenz ; | ||
+ | |||
+ | </ | ||
+ | |||
+ | ===== 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, | ||
+ | whileKeyword, | ||
+ | kleiner, groesser, identisch, kleinergleich, | ||
+ | zuweisung, | ||
+ | trueKeyword, | ||
+ | strichpunkt, | ||
+ | |||
+ | /** | ||
+ | * Nur als Knotentyp für Knoten des Syntaxbaums: | ||
+ | */ | ||
+ | negation | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Erweiterung des Lexers ===== | ||
+ | Damit der Lexer die Schlüsselwörter '' | ||
+ | |||
+ | <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) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | |||
+ | Etwas trickreicher sind die neuen Zeichen. Um etwa ''<'' | ||
+ | |||
+ | <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; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Damit sieht die Erkennung von ''>'', | ||
+ | |||
+ | <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(" | ||
+ | System.exit(1); | ||
+ | } | ||
+ | break; | ||
+ | </ | ||
+ | |||
+ | |||
+ | ===== Test des Lexers ===== | ||
+ | Der Lexer lässt sich wieder mit der Klasse '' | ||
+ | < | ||
+ | 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 | ||
+ | </ | ||
+ | |||
+ | |||
+ | ===== Erweiterung der Klasse Knoten ===== | ||
+ | Auch Anweisungen (Wiederholung, | ||
+ | |||
+ | <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; | ||
+ | |||
+ | |||
+ | ... | ||
+ | </ | ||
+ | |||
+ | 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: | ||
+ | |||
+ | **print-Knoten: | ||
+ | * links: Aussage, deren wert ausgegeben werden soll | ||
+ | * rechts: '' | ||
+ | * naechsteAnweisung: | ||
+ | |||
+ | **Zuweisungs-Knoten: | ||
+ | * links: text-Knoten, | ||
+ | * rechts: Aussage, deren Wert der Variablen zugewiesen werden soll. | ||
+ | * naechsteAnweisung: | ||
+ | |||
+ | ===== 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 Zuweisung. | ||
+ | * | ||
+ | * @return | ||
+ | */ | ||
+ | private Knoten anweisung() { | ||
+ | |||
+ | if(peek() == null) { | ||
+ | return null; | ||
+ | } | ||
+ | /** | ||
+ | * Eine Anweisung beginnt mit whileKeyword, | ||
+ | */ | ||
+ | switch(peek()) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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(); | ||
+ | // | ||
+ | |||
+ | 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 = neuerKnoten; | ||
+ | |||
+ | } | ||
+ | |||
+ | return linkerOperand; | ||
+ | |||
+ | } | ||
+ | |||
+ | ... | ||
+ | |||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | Ansonsten muss nichts am Parser geändert werden. | ||
+ | |||
+ | ===== Test des Parsers ===== | ||
+ | Der Parser lässt sich wieder mit der Klasse '' | ||
+ | < | ||
+ | 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[b] | ||
+ | r:zahl[2.0] | ||
+ | n: | ||
+ | | ||
+ | l:text[a] | ||
+ | r: | ||
+ | | ||
+ | l:text[a] | ||
+ | r:plus | ||
+ | | ||
+ | | ||
+ | n:zuweisung | ||
+ | | ||
+ | r:mal | ||
+ | l:text[b] | ||
+ | r:zahl[2.0] | ||
+ | | ||
+ | l:text[b] | ||
+ | </ | ||
+ | |||
+ | Nachfolgend noch in grafischer Form. Die mit " | ||
+ | {{ : | ||
+ | |||
+ | ===== 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 '' | ||
+ | Zum Speichern der Werte verwenden wir eine Klasse '' | ||
+ | <code java> | ||
+ | /** | ||
+ | * Datentyp des gespeicherten Wertes | ||
+ | */ | ||
+ | enum Typ { | ||
+ | | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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; | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | this.doubleWert = d; | ||
+ | this.typ = Typ.doubleTyp; | ||
+ | } | ||
+ | |||
+ | | ||
+ | this.booleanWert = b; | ||
+ | this.typ = Typ.booleanTyp; | ||
+ | } | ||
+ | |||
+ | | ||
+ | if(typ == Typ.doubleTyp) { | ||
+ | | ||
+ | } else { | ||
+ | | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Der erste Änderungsschritt besteht darin, die '' | ||
+ | |||
+ | <code java> | ||
+ | public class Interpreter { | ||
+ | |||
+ | /** | ||
+ | * Speichert Zuordnungen von Variablenbezeichnern zu Werten: | ||
+ | */ | ||
+ | private HashMap< | ||
+ | </ | ||
+ | |||
+ | Die Methode '' | ||
+ | |||
+ | <code java> | ||
+ | public Wert interpretiere(Knoten knoten) { | ||
+ | |||
+ | if(knoten != null) { | ||
+ | |||
+ | switch(knoten.getToken().getTokenType()) { | ||
+ | ... | ||
+ | </ | ||
+ | |||
+ | Die Berechnung des Rückgabewertes sieht für den Operator '' | ||
+ | <code java> | ||
+ | case plus : | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert + | ||
+ | interpretiere(knoten.getRechts()).doubleWert); | ||
+ | </ | ||
+ | |||
+ | Für die anderen Operatoren sieht das entsprechend aus. Trickreich wird es nur bei den Vergleichsoperatoren '' | ||
+ | |||
+ | <code java> | ||
+ | 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); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Die Knoten, die einer Wiederholung, | ||
+ | |||
+ | <code java> | ||
+ | case whileKeyword : | ||
+ | /** | ||
+ | * Im linken Knoten hat der Parser die Bedingung (also den Term | ||
+ | * innerhalb von " | ||
+ | */ | ||
+ | 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 : | ||
+ | | ||
+ | |||
+ | Wert wert1 = interpretiere(knoten.getRechts()); | ||
+ | |||
+ | /** | ||
+ | * Neuen Wert der Variable speichern: | ||
+ | */ | ||
+ | | ||
+ | |||
+ | /** | ||
+ | * Führe die Anweisungen aus, die nach der Zuweisung kommen: | ||
+ | */ | ||
+ | | ||
+ | |||
+ | | ||
+ | |||
+ | case printKeyword : | ||
+ | |||
+ | /** | ||
+ | * Im linken Knoten steckt der Term, dessen Wert ausgegeben werden soll | ||
+ | */ | ||
+ | | ||
+ | |||
+ | /** | ||
+ | * Führe die Anweisungen aus, die nach der Print-Anweisung kommen: | ||
+ | */ | ||
+ | | ||
+ | |||
+ | | ||
+ | </ | ||
+ | |||
+ | Dadurch, dass am Ende jeder Anweisung mittels '' | ||
+ | |||
+ | ===== Test des Interpreters ===== | ||
+ | Der Lexer lässt sich mit der Klasse '' | ||
+ | |||
+ | <code java> | ||
+ | /** | ||
+ | * Ausführung des Programms | ||
+ | */ | ||
+ | |||
+ | Interpreter i = new Interpreter(); | ||
+ | |||
+ | println(" | ||
+ | |||
+ | Wert wert = i.interpretiere(p.getWurzel()); | ||
+ | |||
+ | println(" | ||
+ | </ | ||
+ | |||
+ | Innerhalb der Ausgabe sieht man auch die Ausgabe des interpretierten Programms: | ||
+ | |||
+ | < | ||
+ | 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" | ||
+ | |||
+ | Ausgabe des Programms: | ||
+ | |||
+ | 4.0 | ||
+ | 8.0 | ||
+ | 16.0 | ||
+ | 32.0 | ||
+ | 64.0 | ||
+ | 128.0 | ||
+ | 256.0 | ||
+ | 512.0 | ||
+ | 1024.0 | ||
+ | |||
+ | Termwert: | ||
+ | 1.0 | ||
+ | </ | ||
+ | |||
+ | **Kleine Denkaufgabe: | ||
+ | |||
+ | Bei der Implementierung des Compilers wurden viele Kompromisse eingegangen, | ||
+ | |||
+ | * 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! :-) | ||
+ | |||