Design: on-the-fly-Parsing + Datenstrukturen

[diggaa1984]

hallo,

nachdem ich heut den ganzen tag damit verbracht hab per schreibtischtest herauszufinden ob ein gegebener Algorithmus für meine Datenstrukturen brauchbar ist, bin ich zum Entschluss gekommen ... ja isser 😀

So nun stellt sich mir die Frage wie ich die Datenstrukturen des Parse-Vorgangs selbst gestalte. Ich habe einen String der Länge n, welche ich parsen muss. Der String hat in der Regel weit weniger als 100 Zeichen (theoretisch aber nicht begrenzt).

Dazu brauche ich eine n x n - Matrix, welche IMMER wenn ich parse neu gebildet werden muss (der String verändert sich ja schliesslich unvorhersehbar .. cut/paste etc.). Was feststeht, es ist eine obere Dreiecksmatrix.

So, was habe ich in der Matrix an den einzelnen Positionen anzugeben: Eine Menge (kann leer sein) von Strings, welche eine bestimmte Bedingung erfüllen. Wenn ich am Anfang des Parsens 1x komplett über den String renne, ist die Matrix mit allen Infos gefüllt.

Nun muss ich das ganze parsen im Sinne von, gugg wie welche Matrix-Einträge miteinander verknüpft sind (CYK-Algorithmus).

Fragen: Welche Datenstruktur bietet sich an damit ich nich son Overhead habe beim erstellen der Matrix (komplettes überschreiben bei neuem Parsen).

Wichtig: Parsen soll on-the-fly gestaltet werden, sprich wie in Eclipse nach Eingabe eines Zeichens kommt in der Regel, sollte was nicht passen gleich der rote Balken etc.
So in der Art würde ich das gerne umsetzen, hier stellt sich dann auch die Frage wie ich das in Verbindung mit Swing am besten umsetzen kann.

 

[Wildcard]

Wichtig: Parsen soll on-the-fly gestaltet werden, sprich wie in Eclipse nach Eingabe eines Zeichens kommt in der Regel, sollte was nicht passen gleich der rote Balken etc.

Hmm, du möchtest also eine Art Editor für eine Domain Specific Language?
Ich kann dir da xText ans Herz legen (ist allerdings für Eclipse). Du gibst eine ANTLR artige Grammatik für deine DSL an und daraus wird dir ein Datenmodell (EMF) generiert und ein Eclipse Editor inklusive autocomplete, on-thy-fly validierung, Outline, und was man sonst so braucht (Lexer, Parser und Linker natürlich auch).
Da steckt insgesamt sehr viel dahinter, daher würde ich versuchen zu vermeiden das Rad neu zu erfinden. Schon das einfache Problem, das du nicht für jeden Tastenanschlag neu Parsen willst und insbesondere nicht komplett parsen willst, ist in der Praxis nicht ganz trivial zu implementieren. Dafür brauchst du einen Reconciler, der inkrementelle Änderungen an das Document übermittelt usw.
Schau dir das Projekt mal an, funktioniert echt fantastisch, obwohl es noch im incubation status ist.

 

[diggaa1984]

hm also die grammatiken und das parsen sollte soweit stehen .. also ich muss BNF-grammatiken parsen, mittels CYK-algo kann ich da universell jede korrekt angegebene BNF-Grammatik (was ich auch schon selbst erkennen kann) parsen. Durch laden einer neuen BNF-Grammatik aus einer Textdatei bemerke ich dann ob die Notation da drin den Programmanforderungen entspricht. Wenn nich, gibts ne dezente Information mit Fehler in der Grammatik und weiter gehts, zum nächsten Versuch 😀

ich hatte grad die idee, die "GUI" als Listener an den Parser zu hänge ... in der GUI merke ich mir dann, ob ich schon den Parse-Auftrag in die Queue geschoben habe. Zumindest erhoffe ich mir davon das nicht nach jedem Tastendruck son Auftrag losgeht, obwohl natürlich viel Zeit vergeht aus PC-Sicht. Wenn das Framework meint ich lass mal den Parse-Thread ran, dann wird geparsed.

Eventuell kann ich direkt wenn der Parser losläuft den String aus der GUI abfragen, sodass ich zwischenzeitliche Eingabe noch mitbekomme.
Wenn geparst wurde, gibts n Listener Event mit eventuellen Informationen zum Parse-Ergebnis. Und ich kann nach Änderungen am Dokument erneut den Auftrag losschicken.
Schliesslich weiss ich ja nicht, ob nur noch 1 Zeichen kommt, oder n ganzer Schwung

Schon das einfache Problem, das du nicht für jeden Tastenanschlag neu Parsen willst und insbesondere nicht komplett parsen willst

naja ich sag mal der String ist da jeweils nicht soooo lang, aber ja ich wollte nich unbedingt prozedural nach jeder winzigen Änderung am Document parsen 😀

 

[diggaa1984]

ich glaub ich liste mal was ich für zugriffe brauch: 😉

[HIGHLIGHT="Java"]
/* key = NonTerminalsymbol ... value = Liste mit Ableitungen
*
* Bsp: M = A | B | 'foo'
*
* key = "M"
* values = ArrayList<String>({"A","B","foo"})
*/
Hashtable<String,List<String>> regelmenge;

//Die Matrix mit schneller Zugriffsmöglichkeit für Zelle und wiederum für deren Listinhalte


//algo:
for i=1 .. n
//vergleich ob eine Regel existiert die aktuellen substring ableiten kann
//zugriff also auf alle Values der Hashtable => ergibt initiale Matrix

for j=2 .. n
for i=j-1 .. 1
for k=i .. j-1
//für jede Regel der Form: X = Y Z (also 2 nicht-terminalsymbole vorhanden)
//=> zugriff also auf alle Values der Hashtable

//wenn Matrix(i,k) && Matrix(k+1,j)
//neuer Matrixeintrag
[/HIGHLIGHT]

 

[Wildcard]

Jo, ok. Für eine einzige Zeile spielt es nicht wirklich eine Rolle, da hast du recht.

 

[diggaa1984]

werd mal sehen wies aussieht, wenn ich die Matrix nur resize, wenn der String länger ist als inne Matrix passt. Die bisher erstellten Listen in der Matrix sollen wiederverwendet werden (bei neuem String eben mal alles auf n*n - Fläche clearen, bzw alles oberhalb der diagonalen .. Rest bleibt). 😉