22 Feb 09 Vorbei :-)
Das Semester ist vorbei, die letzte Übung schon vor langer Zeit gehalten und die Klausur korrigiert. Der Blog ist damit “fertig” 
Viel Erfolg weiterhin im Studium.
06 Feb 09 Blatt 13
Ich habe mal eine kleine PDF erstellt als Zusatz zu den Folien (dann muss man sich nicht so den Kopf verrenken hoffentlich :-))..
02 Feb 09 Zusatz zu Blatt 12
Zwei kleine Zusatzaufgaben um den Nutzen der Evaluationsbäume besser zu verstehen:
Zusatzaufgaben
Wir haben im Blatt 11 in der 3. Aufgabe einen RPN-Rechner kennengelernt (und auch teilweise entwickelt). Der Rechner kann eigentlich auch nicht mehr als unserer Grammatik vom Blatt 12´ und deshalb folgende Aufgabe:
Man schreibe den Quellcode vom RPN-Rechner um, damit er auch einen Evaluationsbaum ausgibt, der mit den Funktionen vom Blatt 12 ausgewertet werden kann.
Die Musterlösung für den RPN-Rechner vom Blatt 11 gibt’s hier.
Damit soll eines deutlich gemacht werden:
Durch das Verwenden eines Evaluationsbaumes werden die Operationen auf der Struktur von der Repräsentation (RPN oder normaler Ausdruck) entkoppelt.
Folgende Zusatzaufgabe bietet sich auch noch an:
Man füge folgende Methode zu IArithmetic hinzu (und implementiere sie entsprechend)´:
List<String> GetNeededVariables();
Die Funktion soll eine Liste aller Variablennamen zurückliefern, die vom Ausdruck erwartet/benutzt werden.
Fehler im Übungsblatt
Wie ich heute erfahren habe´ gibt es einen zwar relativ leicht behebaren, aber trotzdem schweren Fehler in der Aufgabenstellung der Aufgabe 1 vom Blatt 12, der offenbar niemandem bisher aufgefallen ist´:
Ausdrücke wie zB. 16 – 4 – 2 oder 16 / 4 * 2 werden falsch ausgewertet!
Man kann das selbst einmal ausprobieren und es stellt sich folgende Frage: Woran liegt das?
Das Problem kann behoben, indem man die Grammatik wie folgt abändert:
<term> ::= <factor> { [’+’ | ’-’] <factor> }*
<factor ::= <atom> { [’*’ | ’/’] <atom> }*
<atom> ::= <const> | <var> | ’(’ <term> ’)’
<const> ::= ’0’ | [’1’-’9’ {’0’-’9’}*]
<var> ::= {’a’-’z’}+
Statt bei <term> und <factor> rekursiv zu verzweigen, erlaubt man einfach beliebig viele angehängte Additionen und Subtraktionen (Tipp: While-Schleifen im Parser-Code :-))
Quizfrage: Wieso können wir nicht die Regeln links assoziativ machen, indem wir zum Beispiel <term> ändern zu:
<term> ::= <term> { [’+’ | ’-’] <factor> }
Die Änderungen gehen in ANTLR recht schnell und im Parser-Code muss man auch nur 2 Funktionen anpassen und kurz überlegen, wie herum man die Evaluationsknoten miteinander verknüpft, aber es dürfte relativ leicht zu machen sein.
Link zu einem alten aber sehr gutem Tutorial zum Compiler- und Parser-Bau
http://www.penguin.cz/~radek/book/lets_build_a_compiler/
Grüße,
Andreas
Tags: Assoziativiät, Blatt 12, Compilerbau, Parser, Zusatzaufgaben
28 Jan 09 Blatt 12 (Lexer und Parser)
Heute befasse ich mich schon einmal früher mit dem nächsten Blatt als sonst´. Das liegt einerseits daran, dass das Thema schön ist, und andererseits daran, dass es wahrscheinlich nicht möglich ist, alles sonst so in den 3 Sunden vom Praktikum unterzubringen, dass man den größt-möglichen Nutzen daraus ziehen kann.
Vorbereitung und Informationen zu den Aufgaben
Bei dem Übungsblatt geht es um das Erstellen eines Parsers und Lexers. (Am besten einmal die Aufgabenstellung überfliegen!)
Die Aufgaben benutzen BNF-Regeln, also macht es auch Sinn, diese kurz zu wiederholen, falls man sich nicht mehr so sicher fühlt.
Wie immer verweise ich auf Wikipedia (die englischen Artikel sind hier eindeutig besser) um die Begriffe zu klären:
Die einzigen Parser, die man auch ohne weitergehende Studien selber schreiben kann, sind rekursiv-absteigende Parser. Interessanterweise sind sie auch so ziemlich die einzigen Parser, deren Code leicht verständlich und wartbar ist (also insbesondere auch lesbar).
Für alle Typen gibt es sogenannte Parser Generatoren (es gibt auch Lexer Generatoren), die automatisch für einen den Quellcode eines Parsers aus vorgegebenen Regeln (BNF-Regeln meistens) erstellen.
Bekannte Beispiele sind Yacc (und Lex für den dazugehörigen Lexer Generator). Beide erstellen unlesbaren Code und um die Funktionsweise zu verstehen (bzw. um zu verstehen wie man von den Regeln auf den erstellten Code kommt) benötigt man fundiertes Wissen über Automatentheorie.
Ein für Anfänger besser geeignetes Tool (das auch Java-Code ausgibt) ist ANTLR. Zu dem Parser (der aber auch sehr mächtig ist) wurde auch ein sehr gutes Buch geschrieben (das sei hier aber nur erwähnt). Meine Beispiele benutzen später auch ANTLR.
Rekursiv-absteigende Parser
Rekursiv-absteigende Parser setzen die BNF-Regeln mehr oder weniger direkt in den Quellcode um und benutzen rekursive Aufrufe um die Regeln zu kodieren.
Wir können Exceptions benutzen um Fehler zu propagieren, doch dazu später.
Um die Struktur besser zu verstehen, möchte ich ein primitives (und nicht wirklich funktionierendes) Beispiel anführen:
Beispiel:
A ::= B | C B ::= X Y Z* C ::= A | C
Das würde wie folgt in (Pseudo-)Code umgesetzt werden (dabei besagt der Rückgabewert einer Funktion, ob die Regel gematcht werden konnte oder nicht (dies ist hilfreich bei Alternativen ;-)):
boolean ruleA() {
// A ::= B | C
return ruleB() || ruleC();
}
boolean ruleB() {
// X
if( !ruleX() )
return false;
// Y
if( !ruleY() )
return false;
// Z* (null, eines oder mehrere Zs)
while( ruleZ() )
;
return true;
}
boolean ruleC() {
// A | C
return ruleA() || ruleC();
}
Man kann folgendes feststellen:
- Diese Regeln bringen natürlich nichts, weil nie Zeichen (Fachwort: Literale) gematcht werden.
- Die Reihenfolge der Abarbeitung von Alternativen ist wichtig für die Programmausführung:
Wäre C ::= C | A und würden wir das dann auch so im Quellcode schreiben (return ruleC() || ruleA()), würde, wie man unschwer erkennt, sofort eine Endlosschleife enstehen und der Regel A würde niemals Beachtung geschenkt werden. - Die Struktur des Codes entspricht sehr stark der Struktur der Regeln – Konstrukte wie ‘mehr als eines’, etc. werden durch Schleifen kodiert, Alternativen durch “VerODERung” und Sequenzen durch “VerUNDerung”
Das ist natürlich nur ein Stück davon, wie ein Parser funktioniert (aber der wichtigste Teil, da er die Struktur beschreibt). Wir müssen jetzt “nur” noch Zeichen einlesen und “verbrauchen” können.
Lexer
In der Aufgabe (und allgemein ist es auch so) bekommen wir eine Zeichenkette und müssen aus dieser eine Struktur herausziehen.
Dazu ist es hilfreich die verschiedenen semantischen Einheiten, die man bekommt, anfangs zu klassifizieren, also zum Beispiel zu sagen: Das hier ist ein Variablenname oder das hier ist eine Zahl usw.
Dann kann man in der Grammatik bzw. im Parser direkt mit den Konzepten Zahl und Variablenname arbeiten anstatt mit irgendwelchen Zeichenregeln ala {‘a’-‘z’}+ bzw. statt mit einer Zeichenkette “x” oder “42” arbeiten zu müssen, haben wir Objekte der Typen VarToken (dessen Attribut name “x” ist) und ConstToken (dessen Attribut value 42 ist).
Der Lexer übernimmt die Aufgabe dieser Klassifierzung bzw. Zerlegung der Eingabe in ihre semantischen Einheiten:
Während ein Parser immer eine Startregel hat und von dort aus beginnt Regeln zu matchen, besteht die Aufgabe eines Lexers darin, die sogenannten Token zu bestimmen. Token sind die semantischen Einheiten, aus denen der Text besteht.
Die Aufgabe des Lexers ist also, die Zeichen einzulesen und in einem ersten Schritt zu verschiedenen Token zusammenzufassen.
Dieser Tokenstream (also Tokenstrom) wird dann vom Parser weiterverwendet (anstatt der Eingabe). In unserer Aufgabe würde der Parser nur Instanzen der Klassen VarToken, OperatorToken, etc. sehen (siehe b)) und mit diesen arbeiten.
Das heißt der Ablauf sieht folgendermaßen aus:
- Der Lexer zerlegt die Eingabe in Tokens und speichert diese in einer Liste (welche Datenstruktur bietet sich da an?
- Der Parser bekommt den Tokenstream und fängt bei der Startregel an Token zu “verbauchen”. Die Startregel verzweigt dann an ihre Unterregeln und diese machen das gleiche´.
Keine Angst, ich gehe darauf noch genauer ein.
Beispiel
Die Aufgabenstellung unterscheidet nicht zwischen Parserregeln und Lexerregeln, sondern mischt das ganze, deswegen werde ich das jetzt auch zuerst so machen.
Im Folgenden benutze ich Grafiken und Grammatiken, die mit und für ANTLR erstellt wurden (ich werde auch den Code posten, aber keine Sorge, man muss da nicht ganz durchsteigen, sondern erst reicht die Ähnlichkeit mit den BNF-Regeln aus Info1 zu sehen).
Die ANTLR-Grammatik für unsere Aufgabe sieht wie folgt aus:
grammar arithmetic;
term : factor ( ('+' | '-') term)?;
factor : atom ( ('*' | '/') factor)?;
atom : CONST | VAR | '(' term ')';
CONST : '0' | ('1'..'9' ('0'..'9')*);
VAR : ('a'..'z')+;
// eat whitespace
WS : (' '|'\n'|'\r'|'\t')+ {$channel=HIDDEN;};
Damit können wir einen Ableitungsbaum erstellen – als Beispiel: 2 * x * (y + 3):
"2 * x * (y + 3)" als Ableitungsbaum
An den Blättern stehen jeweils die Token, die gemacht wurden. “Root” ist eine Eigenart von ANTLR und wird immer noch über die Startregel gesetzt.
Ich empfehle, dass man als Übung selber auch einmal versucht den Ableitungsbaum aufzustellen (siehe Teilaufgabe a)).
Lexer, die zweite
Die Aufgabe in der b) besteht darin, sich zu überlegen, welche Attribute die verschiedenen Token haben sollen (bzw ob überhaupt).
Die verschiedenen Klassen sollen alle IToken implementieren, damit wir später Polymorphie benutzen können und auch alle Token in einer Queue<IToken> speichern können.
Wir können dann das instanceof Schlüsselwort benutzen um später festzustellen, mit was für einem Token wir es eigentlich zu tun haben
IToken token = tokenStream.poll(); if( token instanceof ConstToken ) { // ja, token ist ein ConstToken ...In der c) sollen wir dann eine Klasse Lexer schreiben, die z.B. eine statische Methode lex hat mit der Signatur:
public static Queue<IToken> lex(String expression)Diese Methode soll, wie oben schon beschrieben, die Zeichenkette expression in eine Folge von Token aufspalten und diese zurückgeben.
Parser, die zweite
Der Parser benutzt den Lexer um die Tokens zu bekommen und benutzt dann rekursive Funktionen (für jede Regel eine) um die Token zu verarbeiten.
Hätten wir zum Beispiel eine Regel:
<beispielRegel> ::= <const> <term> <const> {<var>}*dann könnte der Quellcode zum Parsen der selbigen so aussehen wie gleich im Beispiel.
Dabei ist die Methode Teil der Klasse Parser und der Tokenstream vom Typ Queue<IToken> ist in einem Attribut private Queue<IToken> tokenStream gespeichert.
Desweiteren haben wir eine Exception TokensExpectedException definiert. Der Rückgabetyp ist hier im Beispiel void, könnte aber zum Beispiel vom Typ int sein, falls wir vielleicht einen Wert durch den Ausdruck berechnen möchten.private void parseBeispielRegel() throws TokensExpectedException { if( tokenStream.peek() instanceof ConstToken ) { tokenStream.remove(); parseTerm(); if( tokenStream.peek() instanceof ConstToken ) { tokenStream.remove(); while( tokenStream.peek() instanceof VarToken ) { tokenStream.remove(); } } else { // kein 2. const gefunden throw new TokensExpectedException( "Const expected" ); } } else { // kein 1. const gefunden throw new TokensExpectedException( "Const expected" ); } }Einleitende Aufgabe zur Aufgabe 1 und 2 für’s Praktikum:
Wir schreiben zuerst einen Interpreter, also eine Parser, der gleich die Ausdrücke interpretiert und die Werte ausrechnet und als Rückgabewert der “Regel-Funktionen” zurückgibt.
Abstrakter Syntaxbaum
Auf Wikipedia findet schon einmal eine Definition: [[wikipdia:Abstract_syntax_tree#Abstract Syntax Tree]].
Ziel der Teilaufgaben d), e) und f) ist es, anstatt die Werte direkt auszuwerten, eine Baumstruktur zu benutzen um die Struktur des geparsten Textes zu speichern. Dieser kann dann getrennt (siehe Aufgabe 2) ausgewertet werden und wir brauchen ihn nur einmal zu parsen, selbst wenn wir verschiedene Operationen auf einem Ausdruck ausführen wollen – z.B. den Wert berechnen oder feststellen, welche Variablen er braucht, etc..
Was für Knotentypen kann dieser Baum haben?
In der Teilaufgabe d) sollen diese Klassen mit den entsprechenden Attributen und Methoden implementiert werden. Wir implementieren wieder ein Interface – nämlich IArithmetic – um eine Baumstruktur zu ermöglichen.
Dazu möchte ich auf Composite Pattern verweisen´, damit man versteht, welche Idee dahinter steckt.
Tree Walker
Bei der Aufgabe 2 geht es darum, einen mit dem Parser erstellten Evaluationsbaum zudurchlaufen und die Ausdrücke auszuwerten um den Wert des gesamtem Ausdruckes zu bestimmen. Dazu fügen wir eine Methode public int evaluate() zum Interface IArithmetic hinzu und implementieren sie dann für jeden Knotentyp derart, dass der Knotentyp seine Teilausdrücke auswertet und seine Operation darauf anwendet (falls er Teilausdrücke hat und ein Operator ist :D).
Dank Polymorphie und dem Composite Pattern geht das relativ schmerzlos.
Zusatzaufgabe (oder alternative Aufgabe)
Statt das Interface nachträglich zu ändern, kann man ein anderes, ebenfalls sehr mächtiges Design Pattern benutzen: das Visitor Pattern´ .
Damit können wir beliebig Operationen auf dem ganzen Baum definieren (wie das Auswerten oder Variablen bestimmen, etc.) ohne mehr als einmal das Interface und die Knotentypen anpassen zu müssen.
Das ist aber wirklich nur eine Zusatzaufgabe, falls noch Zeit bleibt.
Falls ich aber noch Zeit finde, werde ich auch noch Lösungen für alle Aufgaben in ANTLR entwickeln – es dürften nicht mehr als 100 Zeilen sein, aber mein ANTLR-Wissen ist etwas eingerostet..
Grüße,
AndreasTags: ANTLR, Blatt 12, Composite Pattern, Exceptions, Lexer, Parser, Vistor Pattern
27 Jan 09 Blatt 11 Nachbereitung
Ich möchte kuz noch einmal etwas zur Aufgabe posten, bei der es darum ging eine Queue durch 2 Stacks zu implementieren und umgekehrt einen Stack durch Queues.
Für ersteres habe ich mich vorhin hingehockt und mal ausprobiert, wie viel Stress es ist eine animierte GIF in GIMP dafür zu erstellen, die das ganze anschaulich zeigt – ich muss sagen, es ist recht viel Stress und deswegen gibt’s auch nur für die Implementierung einer Queue durch 2 Stacks eine Animation:
Implementierung eines Queues durch 2 Stacks
Die Implementierung eines Stacks durch 2 Queues erfolgt ähnlich, nur muss man bei jedem pop die Queues umschütten und das letzte Element herausziehen. Das Erstellen einer ähnlichen Skizze, wie der von mir oben, kann hilfreich sein, um sich das klar zu machen.
An sich kann man solche Aufgaben immer so lösen, dass man sich einerseits vorstellt wie das ganze nach außen hin wirken soll (das Interface also) und dann versucht die Funktionalität durch das, was man zur Verfügung hat, auszudrücken.
Soweit zum Blatt 11, wenn’s dazu noch Fragen gibt –> Email 😀
Grüße,
Andreas23 Jan 09 Blatt 11
Anbei das Eclipse-Projekt für die Aufgabe 3:
Tags: Blatt 11
10 Jan 09 Interfaces in 10 Minutes
Ich habe mich heute mal drangehockt und ein kleines Eclipse-Projekt geschrieben, das einerseits versucht Interfaces an Beispielen zu erklären (sehr banale Beispiele, die aber mit vielen Kommentaren versetzt sind), aber auch andererseits zeigt (sozusagen im Fortgeschrittenen-Teil), wie man Klassen definiert, die in For each-Schleifen benutzt werden können, also z.B.:
MeineKlasse meinObject = new MeineKlasse(); // falls die Klasse sich über integer iterieren lässt for( int i : meinObject ) { ... }Es wird als Bonus auch noch gezeigt, wie man auch noch die ersten 10 Fibonacci-Zahlen berechnen könnte 😉
Hier ist das Eclipse-Projekt: Interfaces In 10 Minutes
In der readme.txt steht die empfohlene Reihenfolge, in der man sich die Dateien anschauen sollte.
Für Feedback und Anregungen bin ich wie immer offen
Grüße,
AndreasTags: examples, foreach, interface, Java
09 Jan 09 Blatt 9
Ich habe für die Aufgabe 1 und Aufgabe 3 Eclipse-Projekte erstellt.
Hier sind sie:
Eclipse Projekt für Blatt 9 Aufgabe 1
Eclipse Projekt für Blatt 9 Aufgabe 3
Bei der Aufgabe 1 habe ich mir die Freiheit genommen auch noch gleich Testcases zu schreiben
Tags: Aufgabe 1, Aufgabe 3, Blatt 9
21 Dec 08 Kleine Zusatzaufgabe zur Landau-Notation
Ich weiß nicht, wer schon alles mit der Landau-Notation vertraut ist (und auch mit der Komplexitätstheorie von Algorithmen). Aber als kleine Zusatzaufgabe´ zur Hausaufgabe vom Blatt 6 (weil ich sie gerade korrigiere) folgendes:
Welche Laufzeiten (ala O(n), etc.) hat der Primzahltest normalerweise, wenn wir ihn so programmieren wie in der Musterlösung zur 1a)?
static boolean isPrime(int p ) { for( int k = 2 ; k * k <= p ; k++ ) { if( p % k == 0 ) { return false; } } return true; } [/sourcecode]Fleißaufgabe:
Wie sieht's mit den Laufzeiten der anderen Funktionen aus?Man kann die Lösung wahrscheinlich leicht mit Google finden, aber es an sich ganz nett da selber einmal darauf zukommen.
19 Dec 08 Blatt 8, Zusatzaufgaben
Zum Blatt 8 folgende Zusatzaufgaben:
Aufgabe 2:
j) Schreiben Sie in der Klasse TimeTable eine Methode
public int addTrainArrival( string nameOfTrain, Date arrivalTime ) { … }
welche zur gegebenen Zeit versucht ein freies Gleis für den Zug zu finden und falls dies möglich ist eine TrainConnection mit den Informationen erstellt und hinzugefügt. Die Methode gibt dies Nummer des Gleises zurück, falls ein Gleis gefunden wurde, ansonsten -1.
k) Schreiben Sie in der Klasse TimeTable eine Methode optimizeForTransitPassengers, die die TrainConnections in der TimeTable dahingehend optimiert, dass Passagiere von Zügen, die zu ähnlichen Zeiten ankommen, möglichst wenige Gleise von einem Zug zum nächsten laufen müssen, falls sie umsteigen wollen´.
Hinweis:
Es ist sinnvoll den Fahrplan um mehr TrainConnections zu erweitern – am besten mit einer For-Schleife weitere Einträge hinzufügen.
Aufgabe 3:
d) Natürlich die Potenzmenge bestimmen
Also:public staic <S> Set<Set<S>> powerSet( Set<S> s ) {…}
