compilerbau:start
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen RevisionVorhergehende ÜberarbeitungNächste Überarbeitung | Vorhergehende ÜberarbeitungNächste ÜberarbeitungBeide Seiten der Revision | ||
compilerbau:start [2021/10/28 20:08] – Martin Pabst | compilerbau:start [2021/11/09 10:17] – [Compilerbau (Einführung)] Martin Pabst | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Compilerbau (Einführung) ====== | ====== Compilerbau (Einführung) ====== | ||
+ | <WRAP center round tip 80%> | ||
+ | Wenn Du Dich für Compilerbau interessierst, | ||
+ | </ | ||
+ | |||
Ein Schüler (Lukas) bat um eine Erklärung, wie ein Compiler (z.B. [[https:// | Ein Schüler (Lukas) bat um eine Erklärung, wie ein Compiler (z.B. [[https:// | ||
Zeile 12: | Zeile 16: | ||
* [[.parser: | * [[.parser: | ||
* [[.interpreter: | * [[.interpreter: | ||
- | * [[.verwendung: | ||
* [[.ebnf: | * [[.ebnf: | ||
* [[.erweiterung: | * [[.erweiterung: | ||
* [[.aufgaben: | * [[.aufgaben: | ||
+ | |||
+ | |||
+ | ====== Fertiges Programm zum Ausprobieren ====== | ||
+ | Der Compiler unten bekommt ein kleines Testprogramm übergeben. Er verarbeitet es in drei Schritten: | ||
+ | - Der Lexer zerlegt das Programm in einzelne Tokens. | ||
+ | - Der Parser bekommt die Tokenliste und baut daraus den AST (abstract syntax tree) auf. | ||
+ | - Der Interpreter führ das Testprogramm aus, indem er den AST geeignet traversiert. | ||
+ | |||
+ | Hier das Testprogramm: | ||
+ | <code java> | ||
+ | a = 1; | ||
+ | b = 2; | ||
+ | while(a < 10) { | ||
+ | a = a + 1; | ||
+ | b = b * 2; | ||
+ | print(b); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | < | ||
+ | <div class=" | ||
+ | |||
+ | <script type=" | ||
+ | /** | ||
+ | * Der Text wird hier Stringkonstante definiert. Er könnte ebenso | ||
+ | * gut gerade vom Benutzer eingegeben worden sein. Wichtig ist: Der | ||
+ | * Java-Compiler compiliert hier nichts. Es wird alles durch Lexer, | ||
+ | * Parser und Interpreter erledigt. | ||
+ | */ | ||
+ | String text = | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | |||
+ | println(" | ||
+ | |||
+ | /** | ||
+ | * Zerlegung des Programmtextes in Tokens: | ||
+ | */ | ||
+ | Lexer l = new Lexer(text); | ||
+ | l.lex(); | ||
+ | println(" | ||
+ | |||
+ | /** | ||
+ | * Bauen des Abstract Syntax Tree: | ||
+ | */ | ||
+ | Parser p = new Parser(l.getTokenListe()); | ||
+ | |||
+ | p.parse(); | ||
+ | |||
+ | println(" | ||
+ | |||
+ | /** | ||
+ | * Ausführung des Programms | ||
+ | */ | ||
+ | |||
+ | Interpreter i = new Interpreter(); | ||
+ | |||
+ | println(" | ||
+ | |||
+ | Wert wert = i.interpretiere(p.getWurzel()); | ||
+ | |||
+ | println(" | ||
+ | </ | ||
+ | |||
+ | <script type=" | ||
+ | public class Interpreter { | ||
+ | |||
+ | /** | ||
+ | * Speichert Zuordnungen von Variablenbezeichnern zu Werten: | ||
+ | */ | ||
+ | private HashMap< | ||
+ | |||
+ | /** | ||
+ | * Belegt die Variable mit Bezeichner bezeichner mit dem Wert wert. | ||
+ | * | ||
+ | * @param bezeichner | ||
+ | * Bezeichner der Variablen | ||
+ | * @param wert | ||
+ | * Wert der Variablen | ||
+ | */ | ||
+ | public void belegeVariable(String bezeichner, Wert wert) { | ||
+ | variablenbelegung.put(bezeichner, | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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 Wert interpretiere(Knoten knoten) { | ||
+ | |||
+ | if(knoten != null) { | ||
+ | |||
+ | switch(knoten.getToken().getTokenType()) { | ||
+ | |||
+ | | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert + | ||
+ | | ||
+ | |||
+ | | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert - | ||
+ | | ||
+ | |||
+ | | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert * | ||
+ | | ||
+ | |||
+ | | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert / | ||
+ | | ||
+ | |||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert < | ||
+ | | ||
+ | |||
+ | case groesser : | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert > | ||
+ | | ||
+ | |||
+ | case kleinergleich : | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert <= | ||
+ | | ||
+ | |||
+ | case groessergleich : | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert >= | ||
+ | | ||
+ | |||
+ | case identisch : | ||
+ | |||
+ | Wert linkerWert = interpretiere(knoten.getLinks()); | ||
+ | |||
+ | if(linkerWert.typ == Typ.doubleTyp) { | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert == | ||
+ | interpretiere(knoten.getRechts()).doubleWert); | ||
+ | } else { | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).booleanWert == | ||
+ | interpretiere(knoten.getRechts()).booleanWert); | ||
+ | } | ||
+ | |||
+ | case ungleich : | ||
+ | |||
+ | Wert linkerWert1 = interpretiere(knoten.getLinks()); | ||
+ | |||
+ | if(linkerWert1.typ == Typ.doubleTyp) { | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).doubleWert != | ||
+ | interpretiere(knoten.getRechts()).doubleWert); | ||
+ | } else { | ||
+ | | ||
+ | interpretiere(knoten.getLinks()).booleanWert != | ||
+ | interpretiere(knoten.getRechts()).booleanWert); | ||
+ | } | ||
+ | |||
+ | case trueKeyword : | ||
+ | |||
+ | return new Wert(true); | ||
+ | |||
+ | case falseKeyword : | ||
+ | |||
+ | return new Wert(false); | ||
+ | |||
+ | case text : | ||
+ | |||
+ | String variablenbezeichner = knoten.getToken().getText(); | ||
+ | |||
+ | Wert wert = variablenbelegung.get(variablenbezeichner); | ||
+ | |||
+ | if(wert == null) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | return wert; | ||
+ | |||
+ | case zahl : | ||
+ | return new Wert(knoten.getToken().getZahl()); | ||
+ | |||
+ | 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 : | ||
+ | String variablenbezeichner1 = knoten.getLinks().getToken() | ||
+ | .getText(); | ||
+ | |||
+ | Wert wert1 = interpretiere(knoten.getRechts()); | ||
+ | |||
+ | /** | ||
+ | * Neuen Wert der Variable speichern: | ||
+ | */ | ||
+ | variablenbelegung.put(variablenbezeichner1, | ||
+ | |||
+ | /** | ||
+ | * 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 | ||
+ | */ | ||
+ | println(interpretiere(knoten.getLinks()), | ||
+ | |||
+ | /** | ||
+ | * Führe die Anweisungen aus, die nach der Print-Anweisung kommen: | ||
+ | */ | ||
+ | interpretiere(knoten.getNaechsteAnweisung()); | ||
+ | |||
+ | return null; | ||
+ | |||
+ | default : | ||
+ | return null; // sollte nie vorkommen | ||
+ | } | ||
+ | |||
+ | } else { | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Nur zu Debuggingzwecken | ||
+ | * | ||
+ | * @return String, der alle Variablen zusammen mit ihrer Belegung in der | ||
+ | * Form variablenbezeichner = wert enthält. | ||
+ | */ | ||
+ | | ||
+ | |||
+ | | ||
+ | } | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | |||
+ | <script type=" | ||
+ | public class Parser { | ||
+ | |||
+ | /** | ||
+ | * Liste, die vom Lexer kommt | ||
+ | */ | ||
+ | private ArrayList< | ||
+ | |||
+ | /** | ||
+ | * 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< | ||
+ | |||
+ | 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 = 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; | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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 " | ||
+ | * Baum zusammen. | ||
+ | * | ||
+ | * Folgt ein weiteres Plus oder Minus, wird der Baum als erster Operand | ||
+ | * einer weiteren Summe/ | ||
+ | * 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(); | ||
+ | // | ||
+ | // | ||
+ | |||
+ | while(peek() == TokenType.plus || peek() == TokenType.minus) { | ||
+ | |||
+ | Token operator = nextToken(); | ||
+ | |||
+ | Knoten rechterOperand = produktQuotient(); | ||
+ | |||
+ | Knoten neuerKnoten = new Knoten(operator, | ||
+ | | ||
+ | |||
+ | linkerOperand = neuerKnoten; | ||
+ | |||
+ | } | ||
+ | |||
+ | return linkerOperand; | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Wie PlusMinus, jedoch für Mal und geteilt. Als erster bzw. zweiter | ||
+ | * Operand wird nach einem einfachen Term (Klammerterm, | ||
+ | * 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 = neuerKnoten; | ||
+ | |||
+ | } | ||
+ | |||
+ | return linkerOperand; | ||
+ | |||
+ | } | ||
+ | |||
+ | private Knoten einfacherTerm() { | ||
+ | |||
+ | if(peek() == null) { | ||
+ | println(" | ||
+ | | ||
+ | } | ||
+ | |||
+ | switch(peek()) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | // | ||
+ | // | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | // | ||
+ | // Term danach | ||
+ | | ||
+ | | ||
+ | | ||
+ | System.exit(1); | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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 Token erwarte(TokenType tokenType) { | ||
+ | |||
+ | if(peek() == null) { | ||
+ | println(" | ||
+ | + tokenType, Color.red); | ||
+ | | ||
+ | } | ||
+ | |||
+ | if(peek() != tokenType) { | ||
+ | println(" | ||
+ | | ||
+ | } | ||
+ | |||
+ | return nextToken(); | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Nur zu Debuggingzwecken | ||
+ | */ | ||
+ | public String toString() { | ||
+ | |||
+ | return toString(wurzel, | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Traversiert vom übergebenen Knoten ausgehend den Teilbaum in pre-order | ||
+ | * Reihenfolge, | ||
+ | * 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 kante) { | ||
+ | |||
+ | String s = ""; | ||
+ | |||
+ | s += einruecken + kante; | ||
+ | s += knoten.getToken().toString() + " | ||
+ | |||
+ | if(knoten.getLinks() != null) { | ||
+ | | ||
+ | s += toString(knoten.getLinks(), | ||
+ | } | ||
+ | |||
+ | if(knoten.getRechts() != null) { | ||
+ | s += toString(knoten.getRechts(), | ||
+ | } | ||
+ | |||
+ | if(knoten.getNaechsteAnweisung() != null) { | ||
+ | s += toString(knoten.getNaechsteAnweisung(), | ||
+ | } | ||
+ | |||
+ | return s; | ||
+ | |||
+ | } | ||
+ | |||
+ | public Knoten getWurzel() { | ||
+ | return wurzel; | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | <script type=" | ||
+ | public class Lexer { | ||
+ | |||
+ | /** | ||
+ | * Die Zeichenkette wird von links nach rechts abgearbeitet. Hier ist | ||
+ | * gespeichert, | ||
+ | */ | ||
+ | private int position; | ||
+ | |||
+ | /** | ||
+ | * Liste zur Speicherung der ermittelten Tokens | ||
+ | */ | ||
+ | private ArrayList< | ||
+ | |||
+ | /** | ||
+ | * Wir speichern den Programmtext in einem Attribut der Klasse, damit er | ||
+ | * nachher nicht von Methode zu Methode weitergereicht werden muss. | ||
+ | */ | ||
+ | private String text; | ||
+ | |||
+ | /** | ||
+ | * | ||
+ | * @param text | ||
+ | * Programmtext, | ||
+ | */ | ||
+ | public Lexer(String text) { | ||
+ | |||
+ | this.text = text; | ||
+ | |||
+ | position = 0; // Wir beginnen mit dem Zeichen ganz links | ||
+ | |||
+ | tokenListe = new ArrayList< | ||
+ | // | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Zerlegt den Programmtext, | ||
+ | * | ||
+ | * @return Liste mit Tokens | ||
+ | * @throws Exception | ||
+ | * Eine Exception wird ausgelöst, wenn der Programmtext Passagen | ||
+ | * | ||
+ | */ | ||
+ | public ArrayList< | ||
+ | |||
+ | /** | ||
+ | * Wiederholung, | ||
+ | */ | ||
+ | while(position < text.length()) { | ||
+ | |||
+ | /** | ||
+ | * peek() liest das nächste Zeichen im Programmtext, | ||
+ | * Variable position aber nicht. Ruft man peek() mehrmals | ||
+ | * hintereinander auf, liefert es also immer dasselbe Zeichen. | ||
+ | */ | ||
+ | char c = peek(); | ||
+ | |||
+ | if(istZiffer(c)) { | ||
+ | lexZahl(); | ||
+ | } else if(istBuchstabe(c)) { | ||
+ | lexText(); | ||
+ | } else { | ||
+ | switch(c) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | | ||
+ | | ||
+ | | ||
+ | // Leerzeichen werden einfach überlesen | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | System.exit(1); | ||
+ | } | ||
+ | |||
+ | position++; | ||
+ | // verarbeitet, | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | return tokenListe; | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Die Methode lexZahl liest eine Zahl | ||
+ | */ | ||
+ | private void lexZahl() { | ||
+ | |||
+ | String zahlAlsString = ""; | ||
+ | |||
+ | do { | ||
+ | char c = peek(); | ||
+ | zahlAlsString += c; | ||
+ | position++; | ||
+ | } while(istZiffer(peek()) || peek() == ' | ||
+ | |||
+ | /** | ||
+ | * Hier machen wir es uns leicht und lassen Java den String in eine Zahl | ||
+ | * konvertieren. Die Methode parseDouble ist für sich genommen natürlich | ||
+ | * auch ein Lexer. | ||
+ | */ | ||
+ | double zahl = Double.parseDouble(zahlAlsString); | ||
+ | |||
+ | tokenListe.add(new Token(zahl)); | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Fügt der tokenListe das übergebene Token hinzu | ||
+ | * | ||
+ | * @param tokenType | ||
+ | */ | ||
+ | private void addToken(TokenType tokenType) { | ||
+ | tokenListe.add(new Token(tokenType)); | ||
+ | |||
+ | } | ||
+ | |||
+ | /** | ||
+ | * peek() liest das nächste Zeichen im Programmtext, | ||
+ | * position aber nicht. Ruft man peek() mehrmals hintereinander auf, liefert | ||
+ | * es also immer dasselbe Zeichen. | ||
+ | * | ||
+ | * @return nächstes Zeichen im Programmtext | ||
+ | */ | ||
+ | private char peek() { | ||
+ | if(position < text.length()) { | ||
+ | return text.charAt(position); | ||
+ | } else { | ||
+ | return(char) 0; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * 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; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * | ||
+ | * @param c | ||
+ | * beliebiges zeichen | ||
+ | * @return true, falls c eine Ziffer ist | ||
+ | */ | ||
+ | private boolean istZiffer(char c) { | ||
+ | return c >= ' | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * | ||
+ | * @param c | ||
+ | * beliebiges Zeichen | ||
+ | * @return true, falls c ein Buchstabe ist | ||
+ | */ | ||
+ | private boolean istBuchstabe(char c) { | ||
+ | return c >= ' | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Vorsicht: Die übergebene Liste ist nur dann gefüllt, wenn zuvor die | ||
+ | * Methode lex aufgerufen wurde. | ||
+ | * | ||
+ | * @return Liste mit den Tokens, in die der Lexer den Programmtext zerlegt | ||
+ | * hat. | ||
+ | */ | ||
+ | public ArrayList< | ||
+ | return tokenListe; | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Nur zu Debuggingzwecken | ||
+ | */ | ||
+ | public String toString() { | ||
+ | |||
+ | String s = ""; | ||
+ | |||
+ | for(Token token : tokenListe) { | ||
+ | s += token.toString() + " "; | ||
+ | } | ||
+ | |||
+ | if(!s.isEmpty()) { | ||
+ | s = s.substring(0, | ||
+ | } | ||
+ | |||
+ | return s; | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | <script type=" | ||
+ | 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; | ||
+ | |||
+ | public Knoten(Token token) { | ||
+ | this.token = token; | ||
+ | } | ||
+ | |||
+ | public Knoten(Token token, Knoten linkerOperand, | ||
+ | this.token = token; | ||
+ | this.links = linkerOperand; | ||
+ | this.rechts = rechterOperand; | ||
+ | } | ||
+ | |||
+ | public Knoten getLinks() { | ||
+ | return links; | ||
+ | } | ||
+ | |||
+ | public void setLinks(Knoten links) { | ||
+ | this.links = links; | ||
+ | } | ||
+ | |||
+ | public Knoten getRechts() { | ||
+ | return rechts; | ||
+ | } | ||
+ | |||
+ | public void setRechts(Knoten rechts) { | ||
+ | this.rechts = rechts; | ||
+ | } | ||
+ | |||
+ | public Token getToken() { | ||
+ | return token; | ||
+ | } | ||
+ | |||
+ | public Knoten getNaechsteAnweisung() { | ||
+ | return naechsteAnweisung; | ||
+ | } | ||
+ | |||
+ | public void setNaechsteAnweisung(Knoten naechsteAnweisung) { | ||
+ | this.naechsteAnweisung = naechsteAnweisung; | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | } | ||
+ | </ | ||
+ | |||
+ | <script type=" | ||
+ | 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 | ||
+ | } | ||
+ | |||
+ | public class Token { | ||
+ | |||
+ | private TokenType tokenType; // Art des Tokens (z.B. zahl, klammerAuf usw.) | ||
+ | private double zahl; // Wird nur belegt, wenn tokenType == zahl | ||
+ | private String text; // Wird nur belegt, falls tokenType == bezeichner | ||
+ | |||
+ | public Token(double zahl){ | ||
+ | this.zahl = zahl; | ||
+ | tokenType = TokenType.zahl; | ||
+ | } | ||
+ | |||
+ | public Token(String text){ | ||
+ | this.text = text; | ||
+ | tokenType = TokenType.text; | ||
+ | } | ||
+ | |||
+ | public Token(TokenType tokenType){ | ||
+ | this.tokenType = tokenType; | ||
+ | } | ||
+ | |||
+ | public TokenType getTokenType() { | ||
+ | return tokenType; | ||
+ | } | ||
+ | |||
+ | public double getZahl() { | ||
+ | return zahl; | ||
+ | } | ||
+ | |||
+ | public String getText() { | ||
+ | return text; | ||
+ | } | ||
+ | |||
+ | /** | ||
+ | * Die toString()-Methode dient nur Debuggingzwecken | ||
+ | */ | ||
+ | public String toString() { | ||
+ | |||
+ | String s = "" | ||
+ | |||
+ | switch (tokenType) { | ||
+ | case zahl: | ||
+ | s += " | ||
+ | break; | ||
+ | case text: | ||
+ | s += " | ||
+ | break; | ||
+ | default: | ||
+ | break; | ||
+ | } | ||
+ | |||
+ | return s; | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | </ | ||
+ | |||
+ | <script type=" | ||
+ | /** | ||
+ | * 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 { | ||
+ | | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | </ | ||
compilerbau/start.txt · Zuletzt geändert: 2022/05/19 08:10 von Martin Pabst