[Quiz #18] ComFreek (Java)

[ComFreek]

Knapp 24 Stunden später abgegeben, aber hier ist es:
Anhang anzeigen Quiz18.7z

Musste feststellen, dass es doch noch ein paar Bugs gibt Habe da wohl zu lange herumgespielt, einen eigenen Regex-Matcher zu schreiben (der ja gar nicht gefordert war).

Parser - zeitlich nicht ganz hinbekommen. Man kann sich abends nur schwer für Regex-Grammatiken begeistern. Habe dann auch nach einem Regex-Parser gesucht, auch einen in Java gefunden; doch es stellte sich heraus, dass es nur ein Lexer (Tokenizer) war.

 

[sheel]

Schön, noch was zu sehen

Ihr habt alle so viele Klassen

 

[ComFreek]

Ich weiß ja nicht wo du deine Magic Methods reinsteckst.

Edit: Ich blicke gerade duch deinen Code. Bei dir scheint ja alles auf der der FA zu basieren. Charset.java ist aber echt "krass" Wozu brauchst du denn die Zahlen?

 

[sheel]

Eine Kurzkurzfassung der Klassen:
Main ist eben main, Ein-/Ausgabe etc.

Range ist eine Datenstruktur vergleichbar zu einer math. Menge aus ints
(also unsortiert, keine Doppelten). Mit dem Unterschied,
dass drin immer Von-Bis-Paare gespeichert werden.
Also statt {1,2,3,4,6,7,8} wäre es vom Prinzip {1-4,6-8}
Wenn man 5 dazutut ergibt es eben {1-8}.
Auch in der Klasse sind ein paar Mengenoperationen wie Konjunktion/Disjunktion...
Verwendet für mehrere verschiedene Zwecke.

FA (finite automaton, endlicher Automat) ist, wie du sagst, das Hauptding (neben Parser).
Als Datenstruktur recht uninteressant, =Liste von Nodes.
Jeder Node hat dann außer einer eindeutigen Nummer noch eine Liste von Verbindungen (Path).
Das wär auch ziemlich alles von Node und Path.
Weiters in FA sind paar Algorithmen mit Hilfsfunktionen:
deterministisch machen und überflüssige Knoten wegkürzen, als Vorarbeit für das Wichtigste:
Mehrere FAs=Regexps zusammenführen zu einem
(der genau das akzeptiert, was alle Ausgangsdinger akzeptieren)

Klasse Revregex hat den Parser mit einigen Hilfsfunktionen, und,
ziemlich kurz dagegen, die Wortgenerierung aus einem vorhandenen fertigen Automaten.

Und Charset: Irgendwann ist mir eingefallen,
dass "gültiges Unicodezeichen" als (UTF32-artige) Zeichennummer
nicht einfach etwas zwichen 0 und Millionen ist.
Es gibt so viel Sonderdinge und Definitionslücken drin...
deshalb das große Array, das sind die gültigen Nummern
wieder als Von-Bis Paare (jeweils zwei aufeinanderfolgende int gehören zusammen)
Und wenn das schon da war hab ich das selbe System auch für den Rest (Ascii etc.) gemacht.
(9 ist Tab. Zeilenwechsel sind absichtlich nicht dabei,
damit pro generiertem Wort nur eine Zeile verbraucht wird)

So, so viel zu meiner Lösung in deinem Thread

 

[alxy]

Mh, ich kann leider kein Java.

Aber meine Implementierung seiht etwas anders aus. Meine "CharacterClass"es enthalten jeweils alle möglichen ASCII Zeichen (werden in nem array gespeichert). Für negative Klassen erstelle ich zuerst eine CharacterClass mit allen zeichen und entferne dann die, die es eben nicht sein dürfen.

Was bei meiner Implementierung echt beschissen gelöst ist, ist das mit den And- und OrExpressions, dass gefällt mir überhaupt nicht. Ich glaube das ist das was sheel gemacht hat schöner (habe was mit node, etc gelesen). Man könnte eine Art baumstruktur machen, wobei AND verknüpfungen immer eine struktur tiefer gehen, und OR verknüpfungen auf selber ebene einen neuen "Ast" anlegen.

Ich habe mich wie comfreek übrigens auch zuerstmal auf das abstrahieren des ausdrucks in einen objecttree konzentriert. Werde aber vielleicht nochmal darann weiterarbeiten, da mir jede nacht irgendwie neue gute ideen kommen

 

[sheel]

So eine Art Baumstruktur (naja, eher Graph allgemein) ist es ja auch.
Schreib gleich ein bisschen (oder mehr) dazu, kommt dann hier rein.

edit:
Vorstellen kann man sich so einen "FA" zB. so:
http://blog.markshead.com/wp-content/uploads/2011/02/non-deterministic-finite-state-machine.png
Um es gleich vorweg zu nehmen: Der passt zum Regexp
ab*c|ac*d
oder, das Selbe,
a(b*c|c*d)

Die Buchstaben in den Knoten sind eig. unwichtig, sind nur zur Unterscheidung
(Zahlen gehen genau so gut).
Am Bild zwar nicht wirklich gekennzeichnet, aber angenommen, s ist Start und t ist Ende.

Der Normalfall "püfen, ob ein Wort zum Regexp passt" ist bei dieser Form die Frage,
ob es einen Weg von Start zu Ende gibt, bei dem die Buchstaben
der abgefahrenen Pfade genau das Prüfwort ergeben.
(Es kann auch mehrere mögliche Enden geben.
Und ein Pfad zwischen zwei Knoten kann auch mehrere mögliche Buchstaben haben,
oder anders gesagt es kann mehrere Pfade mit verschiedenen Buchstaben
zwischen den selben Knoten geben)

Regex-Strukturen wie * und | kann man damit gut abbilden
Ein Oder wäre die Verzweigung im Knoten s, ein * die Schleifen in q und r
( der Bogen kann sich natürlich auch über mehrere Knoten ziehen, für (...)* )
sachen wie a+ kann man umformen zu aa* usw.
Optionales wie a? kann man durch eine Verzweigung machen,
bei der eine Seite zu a geht und die andere Seite
ein buchstabenloser (aber existierender) Pfad ist
(der beim Wortprüfen eben keinen Buchstaben ausmacht.
Gibts am Bild nicht, ist aber erlaubt)

Wortgenerierung läuft dann ca. so ab:

Man beginnt beim Start als aktueller Knoten und einem leeren Wort(speicher)
Solange der aktuelle Knoten kein Endknoten ist
{
    Nimm zufällig einen der verfügbaren Pfade
    Füg den dazugehörenden Buchstaben (falls vorhanden) zum Wort dazu
    und nimm den Zielknoten als aktuellen
}

Einfach zufällig durchlaufen.

Mein Parser zerlegt die Regexp eben in Knoten und Pfade
und behandelt * etc. wie oben beschrieben als Schleifen usw.
Wenn alle eingegeben Regexp so behandelt wurden
gibts ein paar Algorithmen (alle in Klasse FA),
die zusammen am Ende einen einizgen Automat ergeben, der genau die Worte erlaubt,
die eben von allen Quellautomaten erlaubt werden.

Als Datenstruktur ist es (wie schon gesagt) ein Haufen Knoten,
wobei jeder Pfade hat, die ihren Gegenüber-Knoten
und ihre mögliche Buchstaben wissen.
(die Buchstaben sind das Hauptgebiet für die Rangeklasse,
damit auch etwas wie "alle Unicodezeichen" speichersparend als Von-Bis abgespeichert wird)


PS: Lasst doch nicht mich allein schreiben,
eure Vorgehensweisen sind auch interessant

 

[ComFreek]

Meine Vorgehensweise:

Ein RegexToken ist bei mir jedes mögliche "Ding" in einem Regex. Zum Beispiel gibt es einen OrBranch, TokenGroup oder auch eine NegativeTokenGroup.
Meine Datenstruktur ist ein Baum (praktisch AST), sprich OrBranch kann zwei Tokens als Kinder besitzen.
Auf höchster Ebene ist es eine Liste.

Bsp:

[abc]+(hello){1,3}

Wird zerlegt in:

Root
|
|-- VariableCountSequence (min. 1, max. -1 (unendlich))
|    |
|    |-- TokenGroup
|         |
|         |-- TextSequence "a"
|         |-- TextSequence "b"
|         |-- TextSequence "c"
|
|-- VariableCountSequence (min. 1, max. 3)
     |
     |-- TextSequence "hello"

Die Struktur eignet sich relativ einfach zum Matchen von Regexen.
Das Problem tritt dann allerdings beim Lösen auf!

Ich fügte noch ein Interface (neben RegexToken) namens "SolvableRegexToken" hinzu.
Jedes Token, das diese implementiert, muss eine Methode definieren, welche für einen Parameter n genau so viele Lösungen (wenn möglich) generiert und als Liste zurückgibt.

(Theoretisches) Beispiel für obigen Regex mit n = 3:

[[a, b, c], [hello, hellohello, hellohello]]

(Die eckigen Klammern sollen Listen darstellen)

Man kann nun jeweils ein Element einer Liste mit einem anderen Element einer anderen der Reihe nach kombinieren.


Wenn man so will, sind bei mir AND-Verknüpfungen eine einfache Ebene (Liste in meiner Implementierung).

@sheel:

Du generiertst also solche FA und legst sie dann bei mehreren RegExps einfach übereinander (ja, stark vereinfacht). Finde ich sehr elegant! ;-)
​

 

[sheel]

@sheel:

Du generiertst also solche FA und legst sie dann bei mehreren RegExps einfach übereinander (ja, stark vereinfacht).
​

So ists.

Direkt nach dem Parsen ist die Struktur vom Prinzip her auch ähnlich geordnet so wie bei dir im
Codeblock, nur dass zB. die drei Textsequenzen nicht Kinder von einem Oberelement,
sondern hintereinander gekettet sind (Also erstes kennt zweites, zweites drittes...)
(später kommt dann dank der Algo-Verarbeitung alles durcheinander)
Typen wie die (unendliche) VariableCountSequence werden eben durch schleifenartige Verbindungen gemacht etc. Der Nachteil ist eben, wie ich bei meiner Abgabe geschrieben hab,
dass genaue Wiederholungszählung dadurch nicht möglich ist. x{2,4} ist xxx?x?

Der eigentliche Grund für den Ansatz war ja, dass mir
a) auf die Schnelle nicht in den Kopf wollte, wie ich Regex in zB. deiner Struktur einfach
(und trotzdem in jedem Fall korrekt) vereinige
b) und ich für die Automatenstruktur noch Uniunterlagen hatte,
die die verwendeten Algos samt Beweisen beinhalten

(Zu meiner Verteidigung: Das Zeug kann man auch im Netz finden,
nicht nur in umständlichen Texten versteckt, sondern sogar bei Stackoverflow etc.)
(und ich mein generell natürlich nur theortische Beschreibungen, kein Code oÄ.)