Institut für Informatik

Michael Wand
David Hartmann

Sommersemester 2020 • DIGITAL

Projekt Übersicht

Letzte Änderung: 06. July 2020, 10:50 Uhr

Exkurs für Interessierte:
Grundlagen Compilerbau in 10 Minuten

Letzte Änderung: 06. July 2020, 10:50 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

Änderungshistorie:

• Formulierung angepasst: Der Baum soll abstrakt zurückgegeben werden, nicht auf der Konsole ausgegeben werden.
• Formulierung angepasst: Mit ^ ist potenzieren gemeint.

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).
Das schöne ist, dass die Definition der Sprache von der restlichen Aufgabe komplett losgelöst ist. Aus dem Grund können sie sich eine von zwei Grammatiken aussuchen:

Wählen Sie dazu eine der folgenden beiden Syntaxen aus, bevor Sie mit der Bearbeitung beginnen:

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

Anderungshistorie:

• Test von 1. zu 2. verschoben (der Gleichungstest gehört zur Evaluation, nicht zum „Unparsing“).

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()) == Expression(str).to_string()
   
   Test!
   Prüfen Sie ob Expression(Expression(str).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 GUI

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

Wählen Sie dazu eine der folgenden beiden GUIs aus, bevor Sie mit der Bearbeitung beginnen: