hi,
ich glaub zu wissen, dass man das nicht wirklich machen sollte, aber ich habe folgendes "Problem":
Ich habe eine Klasse ContextFreeGrammar, welche eine kontextfreie (Typ2 der Chomsky-Hierarchie) Grammatik G darstellt (G = (SIGMA, M, R, S))
ich speicher mir in der Klasse folgendes ab:
********************************
[HIGHLIGHT="Java"]
public class ContextFreeGrammar {
private List<String> nonTerminals;
private List<String> terminals;
private Hashtable<String,List<String>> rules;
private String startSymbol;
private char terminalMarker;
[...]
[/HIGHLIGHT]
So dass ist als Grundgerüst schon ganz brauchbar, doch ich beziehe mich im weiteren Programmverlauf auf 2 verschiedene Notationen für Typ2-Grammatiken. Zum Einen die BNF-Notation (Backus-Naur-Form), welche ich aus externen Datein einlese die der Nutzer angeben kann; und zum Zweiten die CNF (Chomsky-Normal-Form), welche ich erhalte, wenn ich die BNF mit einem Algorithmus umwandel. Die CNF wird verwendet um die BNF-Grammatiken mit einem universellen Parser zu parsen, sodass ich jede Typ2-Grammatik mit ein und dem selben Parser parsen kann (erleichtert Erweiterbarkeit für neue Grammatiken). Die CNF hat nun einige Restriktionen was die Regelmenge der Grammatik angeht.
Man kann nur Regeln folgender Form angeben:
M => Terminalsymbol
M => NichtTerminalsymbol1 NichtTerminalsymbol2
Im Gegensatz zu BNF gibt es also keine Alternativen mehr pro Nicht-Terminalsymbol. Das bedeutet das auch meine Listen-Datenstrukturen als solche überflüssig werden und ich normale Strings verwenden könnte.
Die CNF wäre also eine spezielle Notation der kontextfreien Grammatiken. Und nun dachte ich, man könnte hier mit Vererbung arbeiten und die List-Strukturen mit Strings überdecken, aber das ist wohl "dirty-style" oder?!
Da ich später über CNF parsen möchte, wäre es vielleicht effektiver nicht 1-elementige Listen zu verwenden sondern auf Strings zuzugreifen.
Also wesentlicher Unterschied: BNF = Listen von Alternative ... CNF = 1 Alternative bestehen aus 1 String (1 Terminalsymbol oder 2 nicht-Terminalsymbole in Folge).
Wie lös ich das nun am dümmsten !? Am besten gar keine Oberklasse verwenden und 2 Klassen (ContextFreeGrammarBNF und ContextFreeGrammarCNF) erstellen?
ich glaub zu wissen, dass man das nicht wirklich machen sollte, aber ich habe folgendes "Problem":
Ich habe eine Klasse ContextFreeGrammar, welche eine kontextfreie (Typ2 der Chomsky-Hierarchie) Grammatik G darstellt (G = (SIGMA, M, R, S))
ich speicher mir in der Klasse folgendes ab:
********************************
- List<String> für nicht-Terminalsymbole (M)
- Hashtable<String,Liste<String>> (also zu jedem M eine Menge von erlaubten Ableitungen/Alternative)
- Liste der Terminalsymbole, welche innerhalb der Alternativen auftreten (Elemente aus SIGMA*)
- zusätzlich noch ein Startsymbol der Grammatik, sowie ein Marker, welche die Terminalsymbole umgibt, damit ich diese von nicht-Terminalsmbolen unterscheiden kann
[HIGHLIGHT="Java"]
public class ContextFreeGrammar {
private List<String> nonTerminals;
private List<String> terminals;
private Hashtable<String,List<String>> rules;
private String startSymbol;
private char terminalMarker;
[...]
[/HIGHLIGHT]
So dass ist als Grundgerüst schon ganz brauchbar, doch ich beziehe mich im weiteren Programmverlauf auf 2 verschiedene Notationen für Typ2-Grammatiken. Zum Einen die BNF-Notation (Backus-Naur-Form), welche ich aus externen Datein einlese die der Nutzer angeben kann; und zum Zweiten die CNF (Chomsky-Normal-Form), welche ich erhalte, wenn ich die BNF mit einem Algorithmus umwandel. Die CNF wird verwendet um die BNF-Grammatiken mit einem universellen Parser zu parsen, sodass ich jede Typ2-Grammatik mit ein und dem selben Parser parsen kann (erleichtert Erweiterbarkeit für neue Grammatiken). Die CNF hat nun einige Restriktionen was die Regelmenge der Grammatik angeht.
Man kann nur Regeln folgender Form angeben:
M => Terminalsymbol
M => NichtTerminalsymbol1 NichtTerminalsymbol2
Im Gegensatz zu BNF gibt es also keine Alternativen mehr pro Nicht-Terminalsymbol. Das bedeutet das auch meine Listen-Datenstrukturen als solche überflüssig werden und ich normale Strings verwenden könnte.
Die CNF wäre also eine spezielle Notation der kontextfreien Grammatiken. Und nun dachte ich, man könnte hier mit Vererbung arbeiten und die List-Strukturen mit Strings überdecken, aber das ist wohl "dirty-style" oder?!
Da ich später über CNF parsen möchte, wäre es vielleicht effektiver nicht 1-elementige Listen zu verwenden sondern auf Strings zuzugreifen.
Also wesentlicher Unterschied: BNF = Listen von Alternative ... CNF = 1 Alternative bestehen aus 1 String (1 Terminalsymbol oder 2 nicht-Terminalsymbole in Folge).
Wie lös ich das nun am dümmsten !? Am besten gar keine Oberklasse verwenden und 2 Klassen (ContextFreeGrammarBNF und ContextFreeGrammarCNF) erstellen?
Zuletzt bearbeitet: