Algorithmus für reguläre Ausdrücke

Question

Gibt es eine Möglichkeit, alle möglichen regulären Ausdrücke (die restriktivste zu am wenigsten restriktiv), die diesen Teilstring für eine bestimmte Zeichenfolge übereinstimmen würde, zu generieren?

Nehmen wir an, Sie haben einen Substring "orange" und einen String "apple banana orange grape". Wie würde ich eine Liste von Regexen erhalten, die mit "orange" übereinstimmen (ich weiß, dass es viele gibt; ich hoffe, dass es eine Bibliothek gibt, die dies für mich erledigt).

Answer 1

Das ist im Grunde dasselbe wie die Frage: "Gibt es eine Möglichkeit, bei gegebenen Laufzeitanforderungen alle möglichen Programme (die effizientesten bis zu den am wenigsten effizienten) zu generieren, die diese Anforderungen für eine bestimmte Eingabe erfüllen?" Die Antwort lautet ja gibt es eine Weg zu tun, aber die Anzahl der Ergebnisse ist unendlich und wird nur durch die Grenzen eines vernünftigen Speichers und die Beschränkungen der Sprachimplementierung begrenzt, so dass Sie Beschränkungen auferlegen müssen, was ein gültiges "Programm" für Ihre Zwecke darstellt, um es auf eine endliche Menge zu reduzieren.

Sie können sich zum Beispiel auf eine bestimmte Grammatik beschränken, die eine Teilmenge der betreffenden Sprache für reguläre Ausdrücke darstellt, und nur Regexe erzeugen, die dieser Grammatik entsprechen:

Regex       ::= StartAnchor? Anything? (Substring | Anything) Anything? EndAnchor?

StartAnchor ::= "^"

Anything    ::= ".\*"
              | "(.\*)"

Substring   ::= "orange"
              | "(orange)"

EndAnchor   ::= "$"

Nehmen Sie rekursiv alle Pfade dieser Grammatik (d. h. jeden Zweig, der durch ? y | ), um alle regulären Ausdrücke für Ihr Ziel zu erzeugen. Natürlich sagt diese Antwort absichtlich nichts darüber aus, ob dies eine gute Idee oder überhaupt notwendig ist...