Kontextfreie Grammatik in Java definieren

Miratek

Grünschnabel
Hallo,

ich habe die Aufgabenstellung, dass ich als Eingabe einen (bis zu 30 stelligen) String habe, der dann überprüft werden soll, ob er in der Grammatik vorkommt. Die Grammatik ist definiert durch z.B. A->aB usw.
Wie kann ich das in Java umsetzen?

Vielen Dank schon mal für Antworten!
 

sheel

I love Asm
Hi

a) Die Grammatik als Graph aufzeichnen: Einen Startknoten, eine Reihe anderer Knoten (ein paar davon sind gültige Endknoten), und zwischen welchen Knoten kann man (ein. oder beidseitig) herumspringen wenn man keine/folgende... Buchstaben dabei "verbraucht".

b) Das genau so in Java-Objekte umsetzen. Eine Klasse Knoten, die zwei boolean Start/End hat (die meisten Knoten haben vermutlich beides false, aber manche eben nicht). Und eine Klasse für Übergange (Außer dass man kein Ü in Variablennamen verwenden sollte), von welchem zu welchem Knoten, braucht man Buchstaben dafür ja/nein, und welche (ArrayList von char oder so). Davon genug Objekte im Programm natürlich auch anlegen und mit Daten füllen, idealerweise in eine Knoten-ArrayList und eine Übergang-ArrayList.
(Falls es auch Übergänge mit "von-bis", zB. A-Z gibt, muss es eben keine Arrayliste von einzelnen chars werden, sondern eine von jeweils zwei chars, Anfang und Ende des Bereichs)

Um ein Wort auf Gültigkeit zu überprüfen, beginnt man theoretisch am Startknoten,, nimmt den ersten Buchstaben, und geht am passenden Übergang zum nächsten Knoten. Beim aktuellen Knoten mit dem nächsten Buchstaben wiederholen, usw., bis das Wort aufgebraucht ist. Wenn man irgendwo steckt, weil es für den aktuellen Buchstaben im aktuellen Knoten keinen Übergang gibt, wird das Wort nicht akzeptiert. Wenn man am Ende bei einem Knoten ist, der nicht als Endknoten markiert ist, auch nicht akzeptiert.

Die Implementierung hängt davon ab, ob die Graphen sicher immer deterministisch sind oder nicht (nicht deterministisch = es kann vorkommen, dass man sich bei Knoten soundso und Buchstabe soundso zwischen mehreren möglichen Übergängen aussuchen kann)

c1) Deterministisch (einfacher):
Ziemlich gleich zur theoretischen Beschreibung. Eine Variable aktueller Knoten (entweder das Knotenobjekt selber oder der Index in der ArrayListe), und eine Variable für die Position im Wort machen.
Dann in einer Schleife: Zuerst alle Übergänge durchsuchen, welcher vom aktuellen Knoten ausgeht und den aktuellen Buchstaben akzeptiert. Falls nichts gefunden, nicht akzeptiert. Sonst, den Zielknoten zum neuen aktuellen Knoten machen, und die Buchstabenposition um 1 erhöhen.
Am Schluss noch prüfen ob der aktuelle Knoten die Endmarkierung hat, sonst auch nicht akzeptieren.

c2) Nichtdeterministisch:
Sobald man zur ersten Gabelung kommt hat man praktisch mehrere aktuelle Knoten weiterzuverfolgen. Man könnte das schön mit Rekursion lösen, dabei gibts aber ein Stackoverflow-Risiko. Ohne Rekursion:
Nicht einen aktuellen Knoten und Buchstabenpositition haben, sondern eine ArrayList davon (am Anfang nur ein Eintrag, Startknoten und 0 eben). In einer Schleife immer alle Einträge durchgehen, jeweils aus der Arraylist rausnehmen, wie die Einzelvariante oben behandeln, und ein/mehrere Zielknoten samt neuer Position wieder einfügen. Wenn man steckt, einfach nichts einfügen.
Sollte die Liste je leer werden, nicht akzeptieren.
Wenn man bei einem der verfolgten Pfade am Wortende ankommt und das kein Endknoten ist, auch nicht wieder in die Liste einfügen weil eben ungültig.
 

Miratek

Grünschnabel
Danke für deine Antwort.
Ich verstehe aber größtenteils nur Bahnhof, denn das Thema der Rekursion ist mir komplett neu.
Wie schreibe ich die zwei Beispiele dann in Java:
A -> aB
B -> aC
C -> A
 

sheel

I love Asm
Wie geschrieben ist die Rekursion "nicht" nötig, wurde nur nebenbei erwähnt.

Welche "zwei" Beispiele? Ich seh nur eins.
Jedenfalls, den kompletten Code werde ich nicht liefern. Fang mit Teil a einmal selber an...
 

Miratek

Grünschnabel
drei Beispiele* meinte ich

Java:
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String x = scanner.nextLine(); //Dies ist der bis zu 30-stellige String der Eingabe.
System.out.println(??.contains(x));
}

Der String besteht nur aus den Buchstaben {a, b}. Jetzt soll ich überprüfen, ob der eingegebene String in der Grammatik vorkommt, die vorgegeben ist.
Also z.B.
A -> aB
B -> aC
C -> A
Doch nun weiß ich nicht, wie ich diese definieren soll.
 

sheel

I love Asm
Nochmal, die drei Zeilen gehören zusammen. Das ist ein Beispiel
(in der hier nicht so hilfreichen Generatorschreibweise)

Außerdem fehlt dir ein Terminierer, das einzige gültige Wort für deine Beispielgrammatik ist eine unendlich lange Folge von a's. Da man keine unendlich vielen Buchstaben im Computer speichern kann ... einfach ausgeben, dass nichts akzeptiert wird?

...

Verstanden hast du Grammatiken anscheinend nicht mal annähernd ... implementieren wird so schwer.

Wenn ich dazu komm, schreib ich in der Nacht etwas mehr Erklärungen, aber eine Frage zuerst:
Soll das Programm dann mit beliebigen Grammatiken funktionieren (wenn die G. im Quelltext geändert wird, oder evt. kann das Programm ja die Grammatik sogar auch einlesen), oder gibt es vom Lehrer ein paar Beispiele und spezielle Lösungen für die sind ok?
 

Miratek

Grünschnabel
Grammatiken selbst habe ich schon verstanden, aber nicht in Verbindung mit Java.
Es ist eine Grammatik vorgegeben und nur mit dieser soll es funktionieren.

Danke für deine Antworten - ich versuche mich selbst nochmal daran.. :)
 

sheel

I love Asm
Ok, da es nur diese eine Grammatik werden soll, ist alles gerade viel einfacher geworden:
(Ich nehme an, der Generator startet mit einem "A")

In Regexschreibweise wäre deine Grammatik (aa|ab)*b
Also am Schluss eines gültigen Worts gibt es sicher ein einzelnes b, und davor beliebig viele aa und/oder ab beliebig vermischt. Gültige Wörter sind zB. b, aaaaaaaab (aa aa aa aa b), ababababb, aaabaab usw.

Beim eingegebenen Wort anfangs einfach prüfen ob es nicht leer ist (if, String.length...) und mit b endet (if, ==, 'b' ...). Wenn nein, falsch. Wenn ja, das b mit substring entfernen und weitermachen. ... Dann eben immer entweder aa oder ab abzwicken, und falls was anderes da steht nicht akzeptieren.