8 Strings, STL-Container und Operatoren

 

 

 

 

1 Klasse für Chomsky-Normalform-Grammatiken

 

Schreiben Sie eine Grammatik-Klasse für Chomsky-Normalform(CNF)-Grammatiken (und ggfs. weitere, von ihr benötigte Klassen).

Eine CNF-Grammatik hat nur Regeln, die den Schablonen (1) oder (2) entsprechen.

(1) N -> N N
(2) N -> t
(N steht für Nicht-Terminal, t steht für terminal.)

Nehmen Sie als Startsymbol grundsätzlich "S" an.
Definieren Sie sinnvolle, öffentliche Elementfunktionen:

• Hinzufügen einer Regel
• Finden einer Regel für ein gegebenes Terminal / Nicht-Terminal
• Ausgabe der kompletten Grammatik in einer gut lesbaren Darstellung auf die Konsole (cout).
• den Operator +, der zwei Grammatiken nimmt und eine dritte ausgibt. Diese sollte die Vereinigungsmenge der enthaltenen Terminale / Nichtterminale / Regeln haben.

Hinweise: Welche Elemente hat eine Grammatik grundsätzlich?
Entscheiden Sie, wie Symbole (Terminale / Nichtterminale) in Ihrer Grammatik repräsentiert werden. Sie können einfach "string"-Objekte in den Regeln verwenden. Besser aber wäre es, eine Liste (Vektor) mit den Terminalen / Nichtterminalen als Klassenelement zu speichern und in den Regeln nur einen Index zu verwenden. Zum Beispiel:
Liste der Nichtterminale:

0. S
1. NP
2. VP
3. N
4. V
5. Det

Eine Grammatikregel wird dann nur noch gespeichert in Form der Indizes:
"S -> NP VP" zum Beispiel wird intern notiert als "0 -> 1 2".

Wie repräsentiert man Regeln am Besten? Eine Regel ist schließlich auch nur ein Objekt.

Nutzen Sie, wo sinnvoll, die Container-Klassen der STL. Sie können 'map' und 'vector' verwenden. 'set' stellt eine größere Schwierigkeit dar, da Sie vorher eine Ordnungsfunktion für die Parameter-Klasse definieren müssten.
Denken Sie an die Unterteilung in Header-Files (.h) und Implementierungs-Dateien (.cpp). Erstellen Sie zunächst alle benötigten Klassendeklarationen (.h-Dateien). Erst, wenn die Struktur des Projekts klar ist, beginnen Sie mit der Implementierung.

 

 

2 Beispielanwendung

Demonstrieren Sie, dass Ihre Klasse funktioniert. Schreiben Sie dazu ein Programm (also eine main()-Funktion), das die folgende Grammatik anlegt.

S -> NP VP
NP -> Det N
VP -> V NP
VP -> V E

Det -> the
Det -> a
NP -> pedro
N -> girl
N -> boxer
N -> donkey
V -> loves
V -> beats

Zeigen Sie anhand jeweils mindestens einem Beispiel, dass die anderen öffentlichen Methoden der Grammatik funktionieren. Zeigen Sie die Verknüpfung zweier Grammatiken mit dem +-Operator.


Reichen Sie die Grammatik-Klasse sowie das Beispielprogramm in Quelltextform (.h- und .cpp-Dateien).

Abgabetermin: Montag, 2. Juli, 13.00 Uhr.