Design: on-the-fly-Parsing + Datenstrukturen

Status
Nicht offen für weitere Antworten.

diggaa1984

Top Contributor
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 :D

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

Top Contributor
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

Top Contributor
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 :D

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 :D
 
Zuletzt bearbeitet:

diggaa1984

Top Contributor
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]
 

diggaa1984

Top Contributor
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). ;)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
S XML-Parsing / public-Member-Variablen / Design-Frage Allgemeine Java-Themen 8
J Meinung zum verwendeten Design Pattern Allgemeine Java-Themen 4
S Noch eine Design-Frage zu Setter Allgemeine Java-Themen 6
S ArrayList Design Allgemeine Java-Themen 4
S Interface Design von HookUp oder Callback Methoden für eigenes Framework Allgemeine Java-Themen 9
Kirby.exe Framework für Game Design Allgemeine Java-Themen 8
C WindowBuilder Design funktioniert nicht Allgemeine Java-Themen 0
M Diverse Design-Fragen Allgemeine Java-Themen 6
rentasad Design-Frage - Interfaces, Klassen, statische Methoden Allgemeine Java-Themen 3
M OOP Design Pattern - "extends Observable implements Observer" Allgemeine Java-Themen 0
T OOP Fehler im Design Allgemeine Java-Themen 9
perlenfischer1984 Welches Design Pattern ist geegneit. Allgemeine Java-Themen 7
perlenfischer1984 Hilfe bei Design (Pattern) Allgemeine Java-Themen 5
N Vererbung Design-Problem mit vorhandenen, von der Klasse unabhängigen Methoden Allgemeine Java-Themen 12
R Parameter Adapter - Design Allgemeine Java-Themen 1
D Bezüglich Design meines Codes Allgemeine Java-Themen 1
D OOP Design Pattern für GUI - Datenbank Anwendung Allgemeine Java-Themen 1
S Java Design Frage Allgemeine Java-Themen 10
L OOP Klassen-Design (static oder nicht?) Allgemeine Java-Themen 3
P Auf die Anzahl der Joins achten beim WS design Allgemeine Java-Themen 1
M OOP Design Frage Allgemeine Java-Themen 2
J Domain Driven Design - Modellierungsfrage Allgemeine Java-Themen 3
F Welches Design Pattern? Allgemeine Java-Themen 3
H MVC Design Allgemeine Java-Themen 9
J Swing Eigenes Button-design Allgemeine Java-Themen 2
Q Kapselung Allgemeine Design- Frage Allgemeine Java-Themen 8
Z Design um boolsche ausdrücke zu speichern & auszuwerten Allgemeine Java-Themen 3
A Sinnvolles Software Design bei Eigenschaftsänderungen von Objekten Allgemeine Java-Themen 7
C Gutes Code Design (3 Schichten Modell) Allgemeine Java-Themen 19
D Design Stations-Gitter Allgemeine Java-Themen 4
M Public Static importRunning -> Bad Design oder ok ? Allgemeine Java-Themen 5
L Software-Design: Kommunikation mit SerialPort (RXTX) Allgemeine Java-Themen 2
D [Drag&Drop] Design-Pattern-Frage Allgemeine Java-Themen 4
G Design Patterns für Programm Allgemeine Java-Themen 3
I Wie populär ist Design by Contract in Java und was haltet ihr davon? Allgemeine Java-Themen 5
Landei Design-Problem Formel-Parser Allgemeine Java-Themen 10
J Aktionen im State-Design-Modell Allgemeine Java-Themen 3
S Design Oberfläche Allgemeine Java-Themen 2
L Design-Frage: Platzierung der Save-Methode Allgemeine Java-Themen 3
G Domain Driven Design Model Allgemeine Java-Themen 14
G konkretes Domain Driven Design Aggregate Allgemeine Java-Themen 2
ruutaiokwu welches design pattern? frage an die oo-experten unter euch... Allgemeine Java-Themen 3
G Accordion Design Pattern Frage Allgemeine Java-Themen 2
hdi Hilfe beim Design (Stichwort OO, Pattern, ...) Allgemeine Java-Themen 11
B Design Problem Allgemeine Java-Themen 8
faulelotte Verständnisproblem Domain Driven Design Allgemeine Java-Themen 3
S Frage zum Design der Datenstruktur Allgemeine Java-Themen 10
D design gesucht - Angabe von zu ersetzenden substrings Allgemeine Java-Themen 2
D Design ohne Getter und Setter Allgemeine Java-Themen 8
N Welches design pattern? Allgemeine Java-Themen 8
D design client server Allgemeine Java-Themen 10
T Design-Frage Allgemeine Java-Themen 14
S JToolBar Design Allgemeine Java-Themen 3
M Bildersyncronisierung - Design Patterns? Allgemeine Java-Themen 2
T Design - Exception in Thread Allgemeine Java-Themen 3
G Composite, Design Pattern, printTree Allgemeine Java-Themen 42
N Design-Frage: persistent machen per Reflection Allgemeine Java-Themen 3
M Frage zum Design :: allgemein Allgemeine Java-Themen 6
M MVC Design Pattern - Verständniss Fragen Allgemeine Java-Themen 3
U Frage zu DB Design Allgemeine Java-Themen 3
K Design / Implementierung Allgemeine Java-Themen 5
N Checkstyle - Design for Extension Allgemeine Java-Themen 4
F Design Pattern zur Realisierung von Mehrfachvererbung? Allgemeine Java-Themen 8
E Was ist ein gutes Design fuer meine Programm? Allgemeine Java-Themen 3
F Paket und Software Design Fragen. Allgemeine Java-Themen 5
P Apple Design Allgemeine Java-Themen 5
S design frage Allgemeine Java-Themen 10
T Design-Tipp gesucht Allgemeine Java-Themen 2
M Design von Java Klassen Allgemeine Java-Themen 2
G java design von klassen und projekten Allgemeine Java-Themen 6
K Design: Klassen in Pakete aufteilen - Eure Meinung Allgemeine Java-Themen 8
S Programmierstil / design Allgemeine Java-Themen 9
S Exception design Allgemeine Java-Themen 2
m@nu Exception-Design Allgemeine Java-Themen 4
R Design-Frage Allgemeine Java-Themen 9
N Hilfe beim Design Allgemeine Java-Themen 13
D Design Pattern: Singleton Allgemeine Java-Themen 4
Torres Design-Problem mit Jakarta Struts Allgemeine Java-Themen 2
A Anwendungs-Design (Plugin-Architektur) Allgemeine Java-Themen 4
M JSON Parsing von youtube video comment replies Allgemeine Java-Themen 4
H HTML Parsing errors Allgemeine Java-Themen 9
C Parsing Java Allgemeine Java-Themen 9
D Algorithmen und Datenstrukturen in Java Allgemeine Java-Themen 40
S Algorithmen und Datenstrukturen Allgemeine Java-Themen 1
A Datenstrukturen Allgemeine Java-Themen 2
M Algorithmen und Datenstrukturen Allgemeine Java-Themen 6
A Datenstrukturen richtig anlegen/laufzeitanalyse Allgemeine Java-Themen 10
N Datenstrukturen an neue Klasse übergeben Allgemeine Java-Themen 16
M Aufgabenstellung unklar (Vorlesung Algorithmen und Datenstrukturen..) Allgemeine Java-Themen 2
D Multiple Datenstrukturen erstellen Allgemeine Java-Themen 4
D Listen / Datenstrukturen und ein blutiger Anfänger Allgemeine Java-Themen 7
J vergleich zweier datenstrukturen Allgemeine Java-Themen 6
M Effiziente Datenstrukturen Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben