Ist es möglich zu überprüfen, ob ein gegebener regulärer Ausdruck mit einer beliebigen Zeichenfolge übereinstimmt? Insbesondere suche ich nach einer Funktion matchesEverything($regex) , die wahr zurückgibt, wenn $regex mit einer beliebigen Zeichenfolge übereinstimmt.
Ich nehme an, dass dies äquivalent ist zu fragen: "Gibt es eine Regex r , gibt es eine Zeichenfolge, die nicht mit r übereinstimmt?" und ich denke nicht, dass dies lösbar ist, ohne Grenzen auf die Menge aller Strings zu setzen. Wenn ich beispielsweise annahm, dass die Strings niemals "blahblah" enthalten werden, dann kann ich einfach überprüfen, ob r mit "blahblah" übereinstimmt. Was aber, wenn es keine Grenzen gibt? Ich frage mich, ob dieses Problem gelöst werden kann, indem überprüft wird, ob die Regex r äquivalent zu .* ist.
Dies beantwortet Ihre Frage nicht genau, erklärt aber hoffentlich ein wenig, warum eine einfache Antwort schwer zu bekommen ist:
Erstens ist der Begriff "Regex" ein bisschen trübe, also nur um zu verdeutlichen, wir haben:
?{...} -Konstrukt sogar noch verrückter werden können, einschließlich willkürlichen Perl-Codes. Ich denke, dass dieses Problem für strenge reguläre Ausdrücke lösbar ist. Sie erstellen einfach das entsprechende DFA und durchsuchen dieses Diagramm, um festzustellen, ob ein Pfad zu einem Nicht-Akzeptieren-Zustand vorhanden ist. Aber das hilft nicht für die 'reale Welt' Regex, die in der Regel PCRE ist.
Ich glaube nicht, dass PCRE Turing-complete ist (obwohl ich es nicht weiß - siehe auch diese Frage: Sind Perl-Regexes abgeschlossen? ). Wenn es so wäre, dann denke ich, wie Jim Garrison bemerkt hat, dass dies im Grunde das Problem ist, dass es Halt gibt. Das heißt, es ist nicht einfach, sie in ein DFA umzuwandeln, was die obige Methode nutzlos macht ...
Ich habe keine Antwort auf PCREs, aber sei dir bewusst, dass die oben genannten Konstrukte (Rückreferenzen usw.) es ziemlich schwer machen würden, denke ich. Obwohl ich zögere, "unmöglich" zu sagen.
Ein echter Perl-Regex mit ?{...} ist definitiv Turing-vollständig, also gibt es Drachen, und ich glaube, du hast kein Glück.