Verschmelzen Sie mehrere Regexe zu einem einzigen

Question

Ich habe mehrere Regexes (eigentlich mehrere tausend), und ich muss überprüfen, ob eine Zeichenfolge mit einem dieser Regexe übereinstimmt. Es ist nicht sehr effizient, also möchte ich alle diese Regexes als eine einzige Regex zusammenführen.

Zum Beispiel, wenn ein diese Regexes haben:

• 'foo * bar'
• 'foo * zip'
• ZAP * bar '

Ich möchte Erhalte etwas wie 'foo * (bar | zip) | zap * bar'.

Gibt es einen Algorithmus, eine Bibliothek oder ein Werkzeug, um dies zu tun?

Answer 1

Sie können einfach die Regexes verketten mit oder (|) (und Anker für den Anfang/Ende der Zeichenfolge).

Die meisten guten Regex-Bibliotheken optimieren ihre Automaten mit endlichem Zustand, nachdem sie sie aus Ihrer Regex erstellt haben. PCRE macht das zum Beispiel.

Dieser Schritt kümmert sich normalerweise um Ihr Optimierungsproblem, dh. Sie wenden die meisten Transformationen an, die Sie "von Hand" machen müssten.

Answer 2

Ich kann mir nicht vorstellen, auch wenn es möglich wäre, dass die resultierende Regex effizienter wäre.

Answer 3

Ich bezweifle es sehr, mit der Begründung, dass ein solches Werkzeug sehr komplex sein müsste, um mit all den verschiedenen Möglichkeiten, wie eine Regex kombiniert werden könnte, umzugehen.

Wenn die Regexes, die Sie haben, relativ einfach sind, wie in Ihren Beispielen, haben Sie vielleicht etwas Glück, wenn Sie Ihre eigenen schreiben.

Answer 4

In der Theorie ist eine Regex ein (nichtdeterministischer) endlicher Automat; somit können sie zusammengeführt und minimiert werden. Sie können einen Blick auf this als Ausgangspunkt nehmen.

Beachten Sie jedoch, dass dies möglicherweise nicht die richtige Antwort ist. Warum müssen Sie mit mehreren tausend regulären Ausdrücken umgehen? Ich kann die Wartehase der Hölle nur so ergründen. Vielleicht solltest du darüber nachdenken, einen Parser und eine Grammatik zu schreiben - das ist sehr einfach (und Grammatiken sind sowieso mächtiger als reguläre Ausdrücke).