Inhalt
|
Inhalt |
Praktikum objektorientiertes Programmieren: CNF
|
 Spezifikation |
Benutzung
 |
Die Konvertierung einer Grammatik in Chomsky-Normalform kann die Anzahl ihrer Nichtterminale quadrieren. (vgl. [2, Übung 4.13]) Deshalb ist es sinnvoll, keine starken Einschränkungen bei der Struktur der Meta- und auch der Alphabetzeichen vorzunehmen. Prinzipiell können hier beliebige Datentypen verwendet werden, für die die Gleichheit definiert ist, wir beschränken uns dann doch und zwar auf Zeichenketten. Das ermöglicht Metazeichen wie [AB] oder A2.
Die Definition einer Grammatik und auch sämtliche Algorithmen sind mengenorientiert. Es werden Mengen betrachtet, ihre Durchschnitte oder Vereinigungen, die Frage tritt auf, ob ein bestimmtes Element in einer Menge enthalten ist... Darauf aufgebaut finden sich dann Mengen von bestimmten Objekten (z.B. Tupel bei der Regelmenge), Zusammenfassungen von Mengen zu Grammatiken und anschliessend verschiedene Typen von Grammatiken. Das legt eine Klassenstruktur nahe, die genau diesen Aufbau nachvollzieht.
Als Grundlage für jede Art von Listen von Objekten benutzen wir die Klasse java.util.Vector. Daraus abgeleitet wird die Klasse OList, die neben komfortablen Routinen zum Hinzufügen und Entfernen von Elementen und ganzen Listen von Elementen bereits die (vor allem für Mengen interessanten) Operationen filter, foldl, hull, map, union, intersect, minus, power, sort, init, tail und subst bereitstellt. Daraus abgeleitet wird dann die Klasse Set zur Repräsentation von Mengen und damit sind die Spezialisierungen Alphabet und Rules zu realisieren.
Zu beachten ist hierbei noch, dass es in java nicht möglich ist, Funktionen als Variablen zu verwenden. Um aber z.B. eine Liste zu filtern, wird eine Funktion benötigt, die den einzelnen Listenelementen Wahrheitswerte zuordnet. Wir realisieren das durch Definition von Function-Interfaces, die Klassen beschreiben, die die benötigten Methoden zur Verfügung stellen, also etwa eine filternde Methode.
Schliesslich werden die verschiedenen Grammatiken modelliert, wobei jede einzelne Grammatik nur den jeweiligen Algorithmus beinhaltet, der zur Erzeugung ihres speziellen Typs notwendig ist und die Beziehungen zwischen ihnen durch Vererbung abgebildet werden.
Weitere Details und Informationen zu den Klassen, die für das Userinterface und die Darstellung des Ablaufs der Algorithmen benötigt werden, finden sich in der javadoc-generierten Dokumentation und in der UML-Darstellung in Abbildung 2.
|
Spezifikation |
Benutzung
|
|
Inhalt |
Praktikum objektorientiertes Programmieren: CNF
|
