Es soll eine Anwendung entwickelt werden, mit der die Parsierung und semantische Analyse mit Hilfe von Attributgrammatiken visualisiert und erläutert werden kann. Hierbei sollen Attributgrammatiken (AGs) bzw. SDDs (Syntax-directed Definitions) eingegeben werden können und nach oder parallel zur Parsierung semantische Eigenschaften des Programms überprüft werden können. Die Aufgabe kann sowohl für die Top-Down- als auch für die Bottom-Up-Parsierung und mit unterschiedlichen AG-Auswertungsmechanismen umgesetzt werden. Eine schrittweise Auswertung umgesetzt und visuell aufbereitet werden.

Ziel dieser Arbeit ist ein Tool zur visuellen Repräsentation der letzten Stufen eines Compilers. Ausgehend von einer internen Repräsentation in Form von abstrakten Syntaxbäumen sollen einfache Methoden zur Codeerezeugung und -optimierung aufbereitet und visualisiert werden.

Der Visual Constraint Solver (VCS) ist ein Tool zur Visualisierung von Constraint-Lösungsprozessen. Er wurde im Rahmen von Abschlussarbeiten am Fachgebiet Programmiersprachen und Compilerbau entwickelt.

In der Constraint-Programmierung können sehr klar und deklarativ komplexe Such- und Optimierungsprobleme beschrieben werden. Der Lösungsprozess wird durch einen sogenannten Constraint-Solver durchgeführt und ist für den Nutzer bei großen Problemen in der Regel nur schwer nachvollziehbar. VCS unterstützt daher durch Interaktivität und Visualisierung das Verständnis des Lösungsprozesses.

Derzeit visualisiert VCS sowohl das ursprüngliche Constraint-Problem als Graphen als auch den Lösungsvorgang in Form eines Suchbaumes. Die Form des Suchbaumes ist dabei abhängig von sogenannten Variablen- und Wertauswahlheuristiken, wobei eine geschickte Wahl einer solchen Heuristik den Lösungsprozess beschleunigen kann. Mittels einer einfachen Sprache können Kriterien für interessante Suchbaumausschnitte formuliert, ausgewertet und in der Visualisierung gekennzeichnet werden.

In dieser Arbeit soll die Komponente zur Suchbaumauswertung und Visualisierung analysiert und erweitert werden. Neben der Erweiterung der Sprache zur Kriterienformulierung um Constraint-basierte
Kriterien- und Baum- bzw. Knotenmengen-Muster soll die gleichzeitige Auswertung mehrerer Suchbäume gleicher oder verschiedener CSPs ermöglicht werden sowie für deren Ergebnisse ein Verfahren zur Evaluation und zum Vergleich von Suchstrategien entwickelt und umgesetzt werden.

Knobelspiele und Logikspiele lassen sich oft sowohl als Such- als auch als Constraint-Probleme formulieren. Auch wenn es sich hierbei um Spiele handelt, lassen sich ganz ähnliche Problemstellungen in Planungs- und Optimierungsproblemen von Anwendungen der realen Welt wiederfinden und Lösungsideen und -verfahren auch oft auf reale Probleme überführen.

Im Rahmen dieser Arbeit soll das Spiel Ubongo betrachtet werden.
Es soll zunächst sowohl als Suchproblem als auch als Constraint-Problem modelliert und gelöst werden. Dabei sollen verschiedene Varianten und Implementierungen von informierten und
uninformierten Suchverfahren untersucht werden. Dabei sollen unter
anderem die folgenden Fragen behandelt werden:

1. Welche Auswirkungen haben verschiedene Suchstrategien (informierte und uninformierte) auf die benötigte Dauer für das Finden einer Lösung im Ubongo-Spiel?
2. Welche Erkenntnisse aus der Suche können genutzt werden, um die Modellierung und Suchstrategie des Constraint-Problems zu optimieren und schnellere Lösungen zu ermöglichen?
3. Inwiefern können Erkenntnisse aus dem Constraint-Modell in die Suche überführt werden?

Hieraus sollen hybride Verfahren abgeleitet und umgesetzt werden. Für die Evaluation der entwickelten hybriden Verfahren ist das Erstellen und Durchführen einer ausgiebigen Testreihe notwendig. Dafür muss ein Ubongo-Problemgenerator erstellt werden, der das Generieren erschiedener Muster erlaubt. Im Anschluss daran soll untersucht werden, ob bestimmte Muster mit bestimmten Verfahren besonders schnell gelöst werden können.

Die Arbeit soll zu einer verbesserten Modellierung und Lösung des Ubongo-Spiels als kombiniertes Such- und Constraint-Problem führen. Zudem können die gewonnenen Erkenntnisse zur Optimierung der Constraint-Modellierung beitragen.