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
Leave a Comment
You must be logged in to post a comment.
