ich dies tun würde, indem die minimalen Deterministic Finite Automaton für die Sprache zu konstruieren.Wenn Sie mit einer Regex beginnen, kann dies automatisch von Thompson's Construction gefolgt von Subset Construction und Minimierung erfolgen. Siehe zum Beispiel this description.
Let P = { < START, [""] > } be a set of pairs <State, list of strings>
for n = 0, 1, ... Max
Let P' = {} be a new set
while P is not empty
Remove the pair <s, L> from P
For each transition s -- c --> t in alpha order of c
if t is an accepting state,
output l + c for each string l in L
put <t, L + c> in P' (** i.e. append c to each string in L)
end
Set P = P'
end
Beachten Sie, dass der Schritt markiert ** Bedürfnisse wahr sein Set Insertion, als Duplikate leicht nach oben zuschneiden können:
Mit einem DFA in der Hand, können Sie so etwas wie dieser Algorithmus verwenden.
Dies ist ein Kernalgorithmus. P kann mit der Ausgabelänge exponentiell wachsen, aber dies ist nur der Preis für die Verfolgung aller Möglichkeiten für eine zukünftige Ausgabezeichenfolge. Die von Ihnen erwähnten Einschränkungen für Auftrag, Größe und Platz können Sie sicherstellen, indem Sie die sortierte Reihenfolge in den Listen L beibehalten und die Suche abbrechen, wenn Ressourcenlimits erreicht werden.
bearbeiten
ist hier ein Spielzeug Java-Beispiel, wo ich hart, um die DFA für einfache binäre Gleitkomma-Literale mit optionalen Minuszeichen codiert haben. Dies verwendet ein etwas anderes Schema als der Pseudocode, um eine strikte sortierte Reihenfolge der Ausgabe zu erhalten und Zeichenbereiche zu berücksichtigen.
import java.util.Comparator;
import java.util.TreeSet;
public class Test{
public static class DFA {
public static class Transition {
final int to;
final char lo, hi; // Character range.
public Transition(int to, char lo, char hi) {
this.to = to;
this.lo = lo;
this.hi = hi;
}
public Transition(int to, char ch) {
this(to, ch, ch);
}
}
// transitions[i] is a vector of transitions from state i.
final Transition [] [] transitions;
// accepting[i] is true iff state i is accepting
final boolean [] accepting;
// Make a fresh immutable DFA.
public DFA(Transition [] [] transitions, boolean [] accepting) {
this.transitions = transitions;
this.accepting = accepting;
}
// A pair is a DFA state number and the input string read to get there.
private static class Pair {
final int at;
final String s;
Pair(int at, String s) {
this.at = at;
this.s = s;
}
}
// Compare pairs ignoring `at` states, since
// they are equal iff the strings are equal.
private Comparator<Pair> emitOrder = new Comparator<Pair>() {
@Override
public int compare(Pair a, Pair b) {
return a.s.compareTo(b.s);
}
};
// Emit all strings accepted by the DFA of given max length.
// Output is in sorted order.
void emit(int maxLength) {
TreeSet<Pair> pairs = new TreeSet<Pair>(emitOrder);
pairs.add(new Pair(0, ""));
for (int len = 0; len <= maxLength; ++len) {
TreeSet<Pair> newPairs = new TreeSet<Pair>(emitOrder);
while (!pairs.isEmpty()) {
Pair pair = pairs.pollFirst();
for (Transition x : transitions[pair.at]) {
for (char ch = x.lo; ch <= x.hi; ch++) {
String s = pair.s + ch;
if (newPairs.add(new Pair(x.to, s)) && accepting[x.to]) {
System.out.println(s);
}
}
}
}
pairs = newPairs;
}
}
}
// Emit with a little DFA for floating point numbers.
public void run() {
DFA.Transition [] [] transitions = {
{ // From 0
new DFA.Transition(1, '-'),
new DFA.Transition(2, '.'),
new DFA.Transition(3, '0', '1'),
},
{ // From 1
new DFA.Transition(2, '.'),
new DFA.Transition(3, '0', '1'),
},
{ // From 2
new DFA.Transition(4, '0', '1'),
},
{ // From 3
new DFA.Transition(3, '0', '1'),
new DFA.Transition(4, '.'),
},
{ // From 4
new DFA.Transition(4, '0', '1'),
}
};
boolean [] accepting = { false, false, false, true, true };
new DFA(transitions, accepting).emit(4);
}
public static void main (String [] args) {
new Test().run();
}
}
Da ich mit Delphi nicht vertraut bin, kann ich nur von einem allgemeinen Standpunkt aus sprechen. Der beste Weg, dies zu tun, wäre meines Erachtens, eine Regex in ein Diagramm zu zerlegen, das ihre äquivalente Zustandsmaschine darstellt (wikipedia sollte in der Lage sein, dort in die richtige Richtung zu weisen). Von dort können Wörter erzeugt werden, indem eine Tiefen-zuerst-Traversierung des Graphen durchgeführt wird (wobei berücksichtigt wird, dass es sehr wahrscheinlich zyklisch ist). Der Nachteil ist, dass wir keine Sprachen nutzen können, die in Regex-Unterstützung integriert sind. – jpm
+1: Sehr interessant. Es ist ein wirklich generativer Ansatz, der meinem hochgradig uneffizienten Generator/Tester Weg widerspricht. Meiner Meinung nach gibt es überhaupt keinen Nachteil: Die eingebaute Regex-Unterstützung dient der Bewertung und das führt mich in die Irre, eine Lösung zu finden. Sie können erwägen, Ihren Kommentar als Antwort zu migrieren, ich finde es akzeptabel. Vielen Dank. – menjaraz
Dies scheint eine dumme Möglichkeit zu sein, reguläre Ausdrücke zu verwenden. Ich denke, dass ein vereinfachtes Generator-Ausdruckssystem, das ein Generator-Objekt erzeugt, das einigen Regex-Features (die '[AZ] .'' und' [AZ] * '(bis zu einer festen Grenze) unterstützen, allein ähnlich wäre –