Kann ich den Satz von First CHARs bestimmen, die mit dem Regex -Muster übereinstimmen?

Question

Ich möchte in der Lage sein, die Menge aller Zeichen zu berechnen, die als die übereinstimmen können Erste Zeichen in einer Zeichenfolge durch eine bestimmte Instanz von java.util.regex.Pattern. In Anbetracht des DFA -Äquivalents zu einem bestimmten regulären Ausdruck möchte ich die Menge aller ausgehenden Übergänge vom Startzustand.

Ein Beispiel:

Pattern p = Pattern.compile("[abc]def|daniel|chris|\\s+");
Set<Character> first = getFirstSet(p);

Der Satz first sollte die folgenden Elemente enthalten:

{ 'a', 'b', 'c', 'd', ' ', '\n', '\r', '\t' }

Irgendwelche Ideen? Ich bin mir bewusst, dass ich die DFA selbst konstruieren und die relevanten Zustände auf diese Weise bestimmen kann, aber ich möchte diese Art von Ärger vermeiden (lesen Sie: Es ist mir nicht so viel wert). Beachten Sie, dass meine Host -Sprache tatsächlich Scala ist, daher habe ich Zugang zu all den Kern -Scala -Bibliotheken (für das, was es wert ist).

Answer 1

Ich denke, Sie könnten den regulären Ausdruck analysieren und eine rekursive Funktion definieren, die auf dem analysierten regulären Ausdruck in einem links nach rechts arbeitet und eine solche Reihe von ersten aufbaut.

Einige Dinge sind einfach:

• Sequenz: First (r1r2) = First (R1) + (if '' in First (R1) First (R2) Ansonsten leere Menge)
• Wechsel: First (R1 | R2) = First (R1) + First (R2)
• Iteration: First (r*) = First (r) + '' '
• Zeichen: First (c) = c
• Zeichenklassen: First ([c1-cn]) = set (c1, c2, ..., cn) ...

Erweitern Sie dies auf alle Primitiven und Spezialflaggen, die Ihr regulärer Ausdrucksdialekt kennt, und Sie können loslegen.

Answer 2

Sie könnten es rekursiv lösen ...

• Streifen der Klammern und rufen Sie rekursiv auf.
• Toplevel -Alternativen aufgeteilt und für jeden Teil rekursiv anrufen.
• Wenn es keine Alternativen gibt,
  • Ausgeben alle Symbole von links bis zum ersten nicht optionalen Symbol.
  • Wenn es Charachter -Gruppen gibt, geben Sie alle Symbole aus.

Es gibt wahrscheinlich viele Fehler in dieser Idee, aber das würde ich versuchen. Sie müssen Behauptung, Gruppennamen und tausend andere Dinge ausziehen. Und wenn Sie eine umgekehrte Zeichenklasse wie [^0-9] finden, müssen Sie viele Zeichen ausgeben.

Ich gehe also davon aus, dass es wirklich ein komplexes Problem ist.