Gibt es einen regulären Ausdruck, um einen gültigen regulären Ausdruck zu erkennen?

Question

Ist es möglich, einen gültigen regulären Ausdruck mit einem anderen regulären Ausdruck zu erkennen? Wenn ja, geben Sie bitte unten einen Beispielcode an.

Answer 1

/
^                                             # start of string
(                                             # first group start
  (?:
    (?:[^?+*{}()[\]\\|]+                      # literals and ^, $
     | \\.                                    # escaped characters
     | \[ (?: \^?\\. | \^[^\\] | [^\\^] )     # character classes
          (?: [^\]\\]+ | \\. )* \]
     | \( (?:\?[:=!]|\?<[=!]|\?>)? (?1)?? \)  # parenthesis, with recursive content
     | \(\? (?:R|[+-]?\d+) \)                 # recursive matching
     )
    (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )?   # quantifiers
  | \|                                        # alternative
  )*                                          # repeat content
)                                             # end first group
$                                             # end of string
/

Dies ist ein rekursiver Regex, der von vielen Regex-Engines nicht unterstützt wird. PCRE-basierte Engines sollten sie unterstützen.

Ohne Leerzeichen und Kommentare:

/^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*)$/

---

.NET unterstützt keine direkte Rekursion. (Die (?1) y (?R) Konstrukte). Die Rekursion müsste auf die Zählung ausgeglichener Gruppen umgestellt werden:

^                                         # start of string
(?:
  (?: [^?+*{}()[\]\\|]+                   # literals and ^, $
   | \\.                                  # escaped characters
   | \[ (?: \^?\\. | \^[^\\] | [^\\^] )   # character classes
        (?: [^\]\\]+ | \\. )* \]
   | \( (?:\?[:=!]
         | \?<[=!]
         | \?>
         | \?<[^\W\d]\w*>
         | \?'[^\W\d]\w*'
         )?                               # opening of group
     (?<N>)                               #   increment counter
   | \)                                   # closing of group
     (?<-N>)                              #   decrement counter
   )
  (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )? # quantifiers
| \|                                      # alternative
)*                                        # repeat content
$                                         # end of string
(?(N)(?!))                                # fail if counter is non-zero.

Verdichtet:

^(?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>|\?<[^\W\d]\w*>|\?'[^\W\d]\w*')?(?<N>)|\)(?<-N>))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*$(?(N)(?!))

Aus den Kommentaren:

Werden dadurch Ersetzungen und Übersetzungen validiert?

Es wird nur der Regex-Teil von Ersetzungen und Übersetzungen überprüft. s/<this part>/.../

Es ist theoretisch nicht möglich, alle gültigen Regex-Grammatiken mit einem Regex abzugleichen.

Es ist möglich, wenn die Regex-Engine Rekursion unterstützt, wie z.B. PCRE, aber das kann man nicht mehr wirklich reguläre Ausdrücke nennen.

Ein "rekursiver regulärer Ausdruck" ist in der Tat kein regulärer Ausdruck. Aber dies ist eine oft akzeptierte Erweiterung der Regex-Maschinen... Ironischerweise passt dieser erweiterte Regex nicht zu erweiterten Regexen.

"In der Theorie sind Theorie und Praxis dasselbe. In der Praxis sind sie es nicht." Fast jeder, der sich mit regulären Ausdrücken auskennt, weiß, dass reguläre Ausdrücke keine Rekursion unterstützen. Aber PCRE und die meisten anderen Implementierungen unterstützen viel mehr als nur einfache reguläre Ausdrücke.

mit diesem mit Shell-Skript in der grep-Befehl, zeigt es mir einige Fehler. grep: Ungültiger Inhalt von {} . Ich entwickle ein Skript, das eine Codebasis durchsucht, um alle Dateien zu finden, die reguläre Ausdrücke enthalten

Dieses Muster nutzt eine Erweiterung namens rekursive reguläre Ausdrücke. Dies wird von der POSIX-Variante von regex nicht unterstützt. Sie können es mit dem Schalter -P versuchen, um die PCRE-Regex-Variante zu aktivieren.

Regex selbst "ist keine reguläre Sprache und kann daher nicht durch reguläre Ausdrücke geparst werden...".

Dies gilt auch für klassische reguläre Ausdrücke. Einige moderne Implementierungen erlauben Rekursion, was sie zu einer kontextfreien Sprache macht, obwohl sie für diese Aufgabe etwas langatmig ist.

Ich sehe, wo Sie übereinstimmen []()/\ . und andere spezielle Regex-Zeichen. Wo sind nicht-spezifische Zeichen erlaubt? Es scheint so, als würde dies mit ^(?:[\.]+)$ , aber nicht ^abcdefg$ . Das ist eine gültige Regex.

[^?+*{}()[\]\\|] passt auf jedes einzelne Zeichen, das nicht Teil eines der anderen Konstrukte ist. Dies schließt sowohl literal ( a - z ), und bestimmte Sonderzeichen ( ^ , $ , . ).

Answer 2

Unwahrscheinlich.

Bewerten Sie es in einer try..catch oder was immer Ihre Sprache vorsieht.

Answer 3

Nein, wenn Sie streng genommen von regulären Ausdrücken sprechen und nicht einige Implementierungen regulärer Ausdrücke einbeziehen, die eigentlich kontextfreie Grammatiken sind.

Es gibt eine Einschränkung bei regulären Ausdrücken, die es unmöglich macht, einen Regex zu schreiben, der auf alle und nur auf Regexe passt. Sie können nicht auf Implementierungen wie geschweifte Klammern passen, die gepaart sind. Regexe verwenden viele solcher Konstrukte, z.B. [] als Beispiel. Wann immer es eine [ muss es einen passenden ] was für eine Regex einfach genug ist "\[.*\]" .

Bei Regexen ist dies nicht möglich, da sie verschachtelt werden können. Wie kann man eine Regex schreiben, die auf verschachtelte Klammern passt? Die Antwort ist, dass man das ohne eine unendlich lange Regex nicht kann. Man kann eine beliebige Anzahl von verschachtelten Klammern mit roher Gewalt abgleichen, aber man kann niemals einen beliebig langen Satz von verschachtelten Klammern abgleichen.

Diese Fähigkeit wird oft als Zählen bezeichnet, da die Tiefe der Verschachtelung gezählt wird. Eine Regex hat per Definition nicht die Fähigkeit, zu zählen.

---

Ich schrieb schließlich " Einschränkungen bei regulären Ausdrücken " darüber.

Answer 4

Gute Frage.

Echte reguläre Sprachen können nicht über beliebig tief verschachtelte wohlgeformte Klammern entscheiden. Wenn Ihr Alphabet enthält '(' y ')' ist es das Ziel, zu entscheiden, ob eine Zeichenkette aus diesen wohlgeformten übereinstimmenden Klammern besteht. Da dies eine notwendige Voraussetzung für reguläre Ausdrücke ist, lautet die Antwort nein.

Wenn man jedoch die Anforderungen lockert und eine Rekursion hinzufügt, kann man es wahrscheinlich tun. Der Grund dafür ist, dass die Rekursion als Stapel fungieren kann, mit dem Sie die aktuelle Verschachtelungstiefe "zählen" können, indem Sie auf diesen Stapel schieben.

Russ Cox schrieb " Der Abgleich regulärer Ausdrücke kann einfach und schnell sein ", das eine wunderbare Abhandlung über die Implementierung von Regex-Engines ist.

Answer 5

Nein, wenn Sie standardmäßige reguläre Ausdrücke verwenden.

Der Grund dafür ist, dass Sie nicht die Schleifensatz für reguläre Sprachen. Das Pump-Lemma besagt, dass eine Zeichenkette, die zur Sprache "L" gehört, regulär ist, wenn es eine Zahl "N" gibt, so dass nach der Aufteilung der Zeichenkette in drei Teilzeichenfolgen x , y , z , so dass |x|>=1 && |xy|<=N können Sie wiederholen y so oft Sie wollen, und die gesamte Zeichenkette gehört immer noch zu L .

Eine Folge des Pump-Lemmas ist, dass es keine regulären Zeichenketten der Form a^Nb^Mc^N , d. h. zwei Teilstrings gleicher Länge, die durch einen weiteren String getrennt sind. Wie auch immer Sie solche Zeichenketten in x , y y z können Sie nicht "pumpen". y ohne eine Zeichenkette mit einer anderen Anzahl von "a" und "c" zu erhalten und somit die ursprüngliche Sprache zu verlassen. Das ist zum Beispiel der Fall bei Klammern in regulären Ausdrücken.