msgbartop
Gruppe F1
msgbarbottom

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: , , , ,