Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Projekt Übersicht

Letzte Änderung: 01. February 2021, 17:11 Uhr

Exkurs für Interessierte:
Grundlagen Compilerbau in 10 Minuten

Letzte Änderung: 01. February 2021, 17:11 Uhr
keine Punkte — im Detail

Im verlinkten Exkurs gibt es einen kurzen Überblick über Grammatiken für formale Sprachen und Compilerbau.
Für die Aufgabe ist es nicht unbedingt nötig, alles durchzuarbeiten — es hilft aber dabei, die Prinzipien hinter den Aufgaben besser zu verstehen.

Aufgabe Parsing — Bäume aus Zeichenketten

Worum geht's?
Das ganze Aufgabenblatt beschäftigt sich damit, mathematische Ausdrücke zu manipulieren. Dazu müssen wir diese erstmal in den Rechner bringen.
Wie in der Vorlesung (zu Lehreinheit 8) erklärt, sind Ausdrücke eigentlich Bäume von Operatoren. Dies ist aber relativ schwierig direkt einzugeben (man bräuchte ein komplexes GUI, und die Interaktion wäre immer noch mühsam, wenn man sich nicht eine sehr raffinierte Schnittstelle überlegt). Daher ist es sinnvoll, mathematische Ausdrücke zunächst in linearisierter Form, als einfache Zeichenketten zu repräsentieren. Die Aufgaben, aus einer solchen, linearisierten Kodierung wieder einen Baum zu rekonstruieren, ist in der Informatik als „Parsing“ bekannt. Der Formalismus dahinter ist als kontextfreie Grammatiken/Sprachen bekannt: In jeden Operator im Baum kann man beliebig komplexe, zusammengesetzte Unteroperatoren einsetzen (Teilbäume).

Da es vergleichsweise schwierig ist, "normale" mathematische Ausdrücke mit Klammerung in einen Syntaxbaum zu überführen, gehen wir in dieser Aufgabe von der sogenannten "Umgekehrten Polnischen Notation" aus.

Aufgabe

Implementierung des Parsers:
Die praktische Aufgabe besteht nun darin den zuvor selbst hergeleiteten Algorithmus zu einer der oben aufgelisteten Syntaxen zu implementieren.

Anforderungen:

1. Für eine eingegebene Zeichenkette soll ein dazu passender Syntax-Baum zurückgegeben werden.
   Dazu macht es Sinn, Klassen zu definieren, mit denen die Knoten im Operatorenbaum repräsentiert werden können. Hierzu gibt es viele verschiedenen Möglichkeiten. Überlegen Sie sich selbst ein Klassendesign. Um Fehler zu vermeiden, erstellen Sie für jeden Knoten des Baums ein neues Objekt; Knoten mehrfach zu verwenden um speicher zu sparen ist nicht-trivial und verkompliziert die Aufgabe deutlich.
2. Erklären Sie Ihr Klassendesign & den Parsingablauf stichpunktartig in der README.md.
   (E.g.: Welche Rolle wird durch die jeweiligen Klassen/Programmteile beim Parsen erfüllt?)
   
   Diese Aufgabe ist nur dazu da, um den KorrektorInnen die Arbeit zu erleichtern. Im Falle, dass die Aufgabe Schwierigkeiten macht, können die KorrektorInnen besser nachvollziehen, wie Ihre Abgabe funktioniert und anteilig Teilpunkte vergeben.
3. Folgende Features soll ihr Parser erfüllen:
   • Ganze Zahlen (etwa 1, 42 oder 1337)
   • die Operatoren +, - (unär und binär), *, / und ^ (potenzieren)
   • Variablen (etwa x, y, a, b, ...)
   • Vordefinierte Funktionen sin, cos, exp und log
   • Bonus: Fließkommazahlen im Format 123.456789
4. Bonus: Fertigen Sie ein UML-Diagramm ihrer Klassenhierarchie an

// string containing the number
string Text = "456";

//number which will contain the result
int Result;

// stringstream used for the conversion constructed with the contents of 'Text' 
// ie: the stream will start containing the characters of 'Text'
istringstream convert(Text);

//give the value to 'Result' using the characters in the stream
//if that fails set 'Result' to 0
if ( !(convert >> Result) )
    Result = 0;

//'Result' now equal to 456

Aufgabe Evaluation

1. Rücktransformation (Unparsing, sozusagen):
   Implementieren Sie nun für alle involvierten Klassen die Methode to_string, die eine Repräsentative Zeichenkette für die (Teil-)Bäume und Objekte zurückgibt. Es muss dabei nicht exakt die gleiche Zeichenkette enstehen, wie die, die eingegeben wurde. Beispielsweise kann sich die neue bis auf Leerzeichen und Klammerungen unterscheiden. Was jedoch der Fall sein sollte ist, dass diese String-Repräsentation selbst wieder einlesbar ist. Insbesondere gilt dann für jede valide Zeichenkette Expression(Expression(str).to_string()).to_string() == Expression(str).to_string()
   
   Test!
   Prüfen Sie ob Expression(Expression(str).to_string()).to_string() == Expression(str).to_string()

1. Mathematische Evaluation:
   Außerdem möchten wir einen Ausdruck auswerten, wobei wir für einige Variablen konkrete Werte einsetzen wollen (Binden der Variablen). Überlegen Sie sich, wie sie dies Implementieren könnten.
   
   Mögliche Umsetzung:
   Strukturell können Sie dies ähnlich zur to_string-Funktionalität gestalten. Noch wissen die Operatorobjekte jedoch nicht, was das Operatortoken eigentlich tut. Übergeben Sie zum Beispiel der Operatordefinition zusätzlich einen Lamba-Ausdruck, der zwei Eingaben erhält und den Operator auf diese beiden anwendet.
   Die Verwendung der Evaluation könnte insgesamt wie folgt aussehen:
   
   Test!
   Werten Sie die folgenden beiden Ausdrücke aus. Definieren Sie dazu alle nötigen Operatoren und Funktionen. Es sollte (ungefähr) der gleiche Wert rauskommen (wenn nicht, stimmt irgendetwas noch nicht...). \[ \begin{aligned} \sin(x+y) = \sin(x) \cdot \cos(y) + \sin(y)\cdot\cos(x)\\ 4\cdot\cos(x)\cdot\cos(y)\cdot\cos(z) = \cos(x+y-z)+\cos(-x+y+z)+\cos(x-y+z)+\cos(x+y+z) \end{aligned} \]

Aufgabe Symbolische Ableitung

Implementieren eine Funktion deriv, die die Ableitung einer einfachen Funktion in gegebenen Variable (z.B. \(x\)) berechnet. Als Operatoren sollen Addition, Subtraktion, Multiplikation und die Funktionen \(\sin(x),\cos(x),\exp(x),\log(x)\) unterstützt werden

Hinweise:

• Bestimmen Sie die Standardableitungen zu \(\sin(x), \cos(x), \exp(x), \log(x)\).
• Implementieren Sie die Produktregel, um Ableitungen von Produkten zu bestimmen: \((f(x)\cdot g(x))' = f'(x)g(x) + f(x)g'(x)\).
• Implementieren Sie die Additivität der Ableitung, d.h. \((f(x)+g(x))' = f'(x)+g'(x)\), sowie
• die Kettenregel \(f(g(x))' = f'(g(x))\cdot g'(x)\).
• Bonus Implementieren Sie auch die Ableitung für Divisionen.

Aufgabe (Bonus) GUI

Zum Schluss brauchen wir unbedingt noch etwas hübsche Graphik (Eye Candy muß sein!).

Erstellen Sie eine GUI, bei der der User in einem Textfeld einen mathematischen Ausdruck in einer Variable (x) eingeben kann. Der eingegebene Ausdruck soll dann zusammen mit der passenden Ableitung in der GUI geplottet werden.