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 :-))..

PDF zum Blatt 13

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?

Antwort »

Unsere Grammatik ist immer rechtsassoziativ, d.h. sie klammert immer implizit rechtseitig. Das ist bei Operatoren wie + und * kein Problem, denn diese sind assoziativ, – und / sind es aber nicht und während wir beim normalen Rechnen immer linksassoziativ arbeiten (das ist die Konvention, deswegen lassen wir solche Klammern normalerweise weg), macht unsere Grammatik genau das umgekehrte, was natürlich zu falschen Ergebnissen führt.

So sieht der korrekte Evaluationsbaum aus

Das ist der falsche Evaluationsbaum, wie er von unserem Parser erstellt wird..

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