Regulären Ausdruck

Die Übereinstimmungsergebnisse des Musters

(?<=\.)) {2,} (? = =[A-Z]) 

Mindestens zwei Plätze werden übereinstimmen, jedoch nur, wenn sie direkt nach einer Zeit (.) Und vor einem Großbuchstaben auftreten.

A regulären Ausdruck (verkürzt wie Regex oder Regexp;^[1] manchmal bezeichnet als rationaler Ausdruck^[2][3]) ist eine Sequenz von Figuren Das gibt a Suchmuster in Text. Normalerweise werden solche Muster von verwendet String-Suchalgorithmen Für "Finden" oder "finden und ersetzen" Operationen ein Saiten, oder für Eingabevalidierung. Regelmäßige Expressionstechniken werden in entwickelt in Theoretische Informatik und formelle Sprache Theorie.

Das Konzept der regulären Ausdrücke begann in den 1950er Jahren, als der amerikanische Mathematiker Stephen Cole Kleene formalisiert das Konzept von a Regelmäßige Sprache. Sie kamen mit mit Unix Textverarbeitungsdienstprogramme. Anders Syntaxe Für das Schreiben regelmäßiger Ausdrücke existiert seit den 1980er Jahren, eine ist die Posix Standard und ein anderer, weit verbreiteter, das ist das Perl Syntax.

Regelmäßige Ausdrücke werden in verwendet Suchmaschinen, in der Suche und ersetzen Sie Dialoge von Textverarbeitungen und Textredakteure, in Textverarbeitung Dienstprogramme wie sed und Awk, und in lexikalische Analyse. Die meisten allgemeine Programmiersprachen Unterstützen Sie Regex -Funktionen entweder nativ oder über Bibliotheken, einschließlich zum Beispiel Python,^[4] C,^[5] C ++,^[6] Java,^[7] und JavaScript.^[8]

Geschichte

Stephen Cole Kleene, der das Konzept einführte

Reguläre Ausdrücke stammten 1951, als Mathematiker Stephen Cole Kleene beschrieben reguläre Sprachen mit seiner mathematischen Notation genannt Regelmäßige Veranstaltungen.^[9][10] Diese entstanden Theoretische Informatikin den Unterfeldern von Automatenheorie (Berechnungsmodelle) und die Beschreibung und Klassifizierung von formelle Sprachen. Andere frühe Implementierungen von Musteranpassung umfassen die Snobol Sprache, die keine regulären Ausdrücke verwendete, sondern ihre eigenen Muster -Matching -Konstrukte.

Reguläre Ausdrücke wurden ab 1968 in zwei Verwendungen eingegeben: Muster -Matching in einem Texteditor^[11] und lexikalische Analyse in einem Compiler.^[12] Zu den ersten Erscheinungen regelmäßiger Ausdrücke in Programmform gehörte wann, wann Ken Thompson baute Kleenes Notation in den Herausgeber Qed als Mittel, um Muster in zu entsprechen Textdateien.^{[11][13][14][15]} Für die Geschwindigkeit implementierte Thompson regelmäßige Ausdrucksübereinstimmungen von Just-in-Time-Zusammenstellung (JIT) zu IBM 7094 Code auf dem Kompatibler Zeitaustauschsystem, ein wichtiges frühes Beispiel für die JIT -Zusammenstellung.^[16] Später fügte er diese Fähigkeit dem UNIX -Editor hinzu ed, was schließlich zum beliebten Suchwerkzeug führte GrepDie Verwendung regulärer Ausdrücke ("Grep" ist ein Wort, das aus dem Befehl für den regulären Ausdruck im ED -Editor abgeleitet wurde: g/re/p bedeutet "globale Suche nach regelmäßigen Ausdrucks- und Druck Matching -Zeilen").^[17] Etwa zur gleichen Zeit, als Thompson QED entwickelte, einschließlich einer Gruppe von Forschern Douglas T. Ross implementierte ein Tool, das auf regulären Ausdrücken basiert, das für die lexikalische Analyse in verwendet wird Compiler Entwurf.^[12]

Viele Variationen dieser ursprünglichen Formen regelmäßiger Ausdrücke wurden in verwendet Unix^[15] Programme bei Bell Labs in den 1970er Jahren, einschließlich vi, Lex, sed, Awk, und Exprund in anderen Programmen wie z. EMACs. Regexes wurden anschließend von einer Vielzahl von Programmen übernommen, wobei diese frühen Formen in der standardisiert sind Pox.2 Standard im Jahr 1992.

In den 1980er Jahren entstanden die komplizierteren Regexes in Perl, die ursprünglich aus einer Regex -Bibliothek abgeleitet wurde von geschrieben von Henry Spencer (1986), der später eine Umsetzung von geschrieben hat Fortgeschrittene reguläre Ausdrücke zum Tcl.^[18] Die TCL -Bibliothek ist ein Hybrid NFA/DFA Implementierung mit verbesserten Leistungsmerkmalen. Softwareprojekte, bei denen die regelmäßige Ausdrucksimplementierung von Spencer übernommen wurde PostgreSQL.^[19] Perl erweiterte später die ursprüngliche Bibliothek von Spencer, um viele neue Funktionen hinzuzufügen.^[20] Teil der Bemühungen in der Gestaltung von Raku (Früher als Perl 6 genannt) besteht darin, die Regex -Integration von Perl zu verbessern und ihren Umfang und ihre Fähigkeiten zu erhöhen, um die Definition von zu ermöglichen Ausdrucksgrammatiken analysieren.^[21] Das Ergebnis ist a Mini-Sprache genannt Raku regiert, mit denen die Raku -Grammatik definiert und Programmierern in der Sprache ein Werkzeug zur Verfügung stellt. Diese Regeln behalten bestehende Merkmale von Perl 5.x Regexes bei, erlauben aber auch Bnf-Stil -Definition von a rekursiver Abstammungsparser über Subrules.

Die Verwendung von Regexes in strukturierten Informationsstandards für Dokumenten- und Datenbankmodellierung begann in den 1960er Jahren und erweiterte in den 1980er Jahren, wenn Branchenstandards wie nach wie vor ISO SGML (Vorvorbereitet durch ANSI "GCA 101-1983") Konsolidiert. Der Kern des Kerns der Strukturspezifikationssprache Standards besteht aus Regexes. Seine Verwendung zeigt sich in der DTD Elementgruppensyntax. Vor der Verwendung regulärer Ausdrücke erlaubten viele Suchsprachen einfache Wildcards, zum Beispiel "*", um eine Abfolge von Zeichen zu entsprechen, und "?" zu einem einzigen Charakter passt. Reliquien davon können heute in der gefunden werden Glob Syntax für Dateinamen und in der Sql WIE Operator.

Ab 1997, Philip Hasel aufgetreten Pcre (Perl kompatible regelmäßige Ausdrücke), die versucht, die Regex -Funktionalität von Perl genau nachzuahmen und von vielen modernen Tools einschließlich der Verwendung verwendet wird Php und Apache HTTP Server.

Heute werden Regexes in Programmiersprachen, Textverarbeitungsprogrammen (insbesondere in der Textverarbeitung Lexer), erweiterte Textredakteure und einige andere Programme. Regex -Unterstützung ist Teil der Standardbibliothek von vielen Programmiersprachen, einschließlich Java und Pythonund ist in die Syntax anderer eingebaut, einschließlich Perl und ECMaskript. Implementierungen der Regex -Funktionalität werden oft als a bezeichnet Regex -Motorund eine Reihe von Bibliotheken stehen zur Wiederverwendung zur Verfügung. In den späten 2010er Jahren begannen mehrere Unternehmen, Hardware anzubieten. FPGA,^[22] GPU^[23] Implementierungen von Pcre kompatibel Regex -Motoren das sind schneller im Vergleich zu Zentralprozessor Implementierungen.

Muster

Der Satz Reguläre Ausdrücke, oder Regexeswird oft verwendet, um die spezifische Standard -Textsyntax für die Darstellung von Mustern für den passenden Text zu bedeuten, was sich von der nachstehend beschriebenen mathematischen Notation unterscheidet. Jedes Zeichen in einem regulären Ausdruck (dh jedes Zeichen in der Zeichenfolge, die sein Muster beschreibt) ist entweder a Metacharakter, eine besondere Bedeutung oder einen regulären Charakter, der eine wörtliche Bedeutung hat. Zum Beispiel in der Regex b., 'B' ist ein wörtlicher Charakter, der nur mit 'B' passt, während '.' ist ein Metacharakter, der zu jedem Charakter mit Ausnahme einer Newline entspricht. Daher entspricht dieser Regex, zum Beispiel "B%" oder "BX" oder "B5". Zusammen können Metacharacter und wörtliche Zeichen verwendet werden, um Text eines bestimmten Musters zu identifizieren oder eine Reihe von Instanzen davon zu verarbeiten. Musterübereinstimmungen können von einer präzisen Gleichheit bis zu einer sehr allgemeinen Ähnlichkeit variieren, wie sie von den Metacharaccern kontrolliert werden. Zum Beispiel, . ist ein sehr allgemeines Muster, [A-Z] (Übereinstimmung mit allen unteren Fallbuchstaben von 'a' bis 'z') ist weniger allgemein und b ist ein präzises Muster (übereinstimmt nur 'B'). Die Metacharacter -Syntax wurde speziell so konzipiert, dass die vorgeschriebenen Ziele in prägnanter und flexibler Weise dargestellt werden ASCII Klaviatur.

Ein sehr einfacher Fall eines regelmäßigen Ausdrucks in dieser Syntax besteht darin, ein Wort zu lokalisieren, das zwei verschiedene Wege in a Texteditorder reguläre Ausdruck Seriali [sz] e entspricht sowohl "serialise" als auch "serialize". Wildcard -Charaktere Erreichen Sie dies auch, sind aber eingeschränkter in dem, was sie Muster haben, da sie weniger Metacharacter und eine einfache Sprachbasis haben.

Der übliche Kontext von Wildcard -Charakteren ist in Kugeln Ähnliche Namen in einer Liste von Dateien, während Regexes normalerweise in Anwendungen verwendet werden, die im Allgemeinen im Muster-Match-Match-Match-Text-Zeichenfolgen stehen. Zum Beispiel die Regex ^[ \t]+|[ \t]+$ Übereinstimmt überschüssiges Weiß am Anfang oder am Ende einer Linie. Ein fortgeschrittener regulärer Ausdruck, der jeder Ziffer entspricht [+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?.

Übersetzung das Kleene Star
(s* bedeutet "Null oder mehr von s"))

A Regex -Prozessor übersetzt einen regelmäßigen Ausdruck in der obigen Syntax in eine interne Darstellung, die ausgeführt und gegen a abgestimmt werden kann Saite Darstellung des durchsuchten Textes. Ein möglicher Ansatz ist der Thompsons Baualgorithmus zu konstruieren a Nichtdeterministisches endliches Automaten (NFA), was damals ist deterministisch gemacht und das resultierende Deterministische endliche Automaten (DFA) wird in der Zieltextzeichenfolge ausgeführt, um Substrings zu erkennen, die dem regulären Ausdruck entsprechen. Das Bild zeigt das NFA -Schema N (s*) Aus dem regulären Ausdruck erhalten s*, wo s bezeichnet wiederum einen einfacheren regulären Ausdruck, der bereits gewesen ist rekursiv übersetzt in die NFA N(s).

Grundlegendes Konzept

Ein regelmäßiger Ausdruck, oft als a genannt Musteran, spezifiziert a einstellen von Strings erforderlich für einen bestimmten Zweck. Eine einfache Möglichkeit, eine endliche Reihe von Strings anzugeben, besteht darin, seine aufzulisten Elemente oder Mitglieder. Es gibt jedoch oft präzise Möglichkeiten: Zum Beispiel kann der Satz, der die drei Saiten "Hände", "Händel" und "Haendel" enthält, durch das Muster angegeben werden H (ä | ae?) Ndel; Wir sagen, dass dieses Muster Streichhölzer Jeder der drei Saiten. Es kann jedoch viele Möglichkeiten geben, einen regelmäßigen Ausdruck für denselben Satz von Zeichenfolgen zu schreiben: zum Beispiel, (Hän | han | haen) del Gibt auch den gleichen Satz von drei Zeichenfolgen in diesem Beispiel an.

Die meisten Formalismen liefern die folgenden Operationen, um regelmäßige Ausdrücke zu konstruieren.

Boolean "oder"

A vertikale Balken trennt Alternativen. Zum Beispiel, gray|grey kann "grau" oder "grau" passen.

Gruppierung

Klammern werden verwendet, um den Umfang und den Vorrang der zu definieren Betreiber (unter anderem). Zum Beispiel, Grau | grau und gr(a|e)y sind äquivalente Muster, die beide den Satz von "grau" oder "grau" beschreiben.

Quantifizierung

A Quantor Nach einem Element (wie a Zeichen, Charakter oder Gruppe) Gibt an, wie oft das vorhergehende Element wiederholt wird. Die häufigsten Quantifizierer sind die Fragezeichen ?, das Sternchen * (abgeleitet von der Kleene Star), und die Pluszeichen + (Kleene Plus).

?	Das Fragezeichen zeigt an Null oder eins Vorkommen des vorhergehenden Elements. Zum Beispiel, Farbe entspricht sowohl "Farbe" als auch "Farbe".
*	Das Sternchen zeigt an Null oder mehr Vorkommen des vorhergehenden Elements. Zum Beispiel, ABC entspricht "AC", "ABC", "ABBC", "ABBBC" und so weiter.
+	Das Pluszeichen zeigt an ein oder mehr Vorkommen des vorhergehenden Elements. Zum Beispiel, AB+c entspricht "ABC", "ABBC", "ABBBC" und so weiter, aber nicht "ac".
{n}[24]	Der vorhergehende Element ist genau übereinstimmt n mal.
{Mindest,}[24]	Der vorhergehende Gegenstand ist abgestimmt Mindest oder öfter.
{, max}[24]	Der vorhergehende Element ist bis auf Max mal.
{Minimal Maximal}[24]	Der vorhergehende Element wird zumindest übereinstimmt Mindest Zeiten, aber nicht mehr als Max mal.

Wildcard

Die Wildcard . entspricht jedem Charakter. Zum Beispiel, A.B. entspricht jeder Zeichenfolge, die ein "A" und dann jeden Charakter und dann "B" enthält; und a.*b entspricht jeder String, die ein "A" und dann das Zeichen "B" zu einem späteren Zeitpunkt enthält.

Diese Konstruktionen können kombiniert werden, um willkürlich komplexe Ausdrücke zu bilden, ähnlich wie man arithmetische Ausdrücke aus Zahlen und Operationen +, -, × und ÷ konstruieren kann.

Genauige Syntax für reguläre Ausdrücke variieren zwischen den Werkzeugen und dem Kontext; Weitere Details finden Sie in § Syntax.

Formale Sprachtheorie

Regelmäßige Ausdrücke beschreiben reguläre Sprachen in Formale Sprachtheorie. Sie haben die gleiche ausdrucksstarke Kraft wie Regelmäßige Grammatiken.

Formale Definition

Regelmäßige Ausdrücke bestehen aus Konstanten, die Sätze von Strings und Bedienungssymbole bezeichnen, die Operationen über diese Sets bezeichnen. Die folgende Definition ist Standard und findet sich in den meisten Lehrbüchern zur formalen Sprachtheorie als solche.^[25][26] Eine endliche Alphabet Σ sind die folgenden Konstanten als reguläre Ausdrücke definiert:

• (leeres Set) ∅ kennzeichnet den Satz ∅.
• (leerer String) ε den Satz, der nur die "leere" Zeichenfolge enthält, die überhaupt keine Zeichen hat.
• (wörtlicher Charakter) a In σ kennzeichnet der Satz, der nur das Zeichen enthält a.

Angesichts der regulären Ausdrücke R und S werden die folgenden Operationen über sie definiert, um regelmäßige Ausdrücke zu erzeugen:

• (Verkettung) (Rs) bezeichnet die Reihe von Zeichenfolgen, die durch Verkettung einer von R akzeptierten Zeichenfolge und einer von S akzeptierten Zeichenfolge (in dieser Reihenfolge) erhalten werden können. Sei R zum Beispiel {"ab", "c"} und S bezeichnen {"D", "EF"}. Dann, (Rs) bezeichnet {"abd", "abef", "cd", "cef"}.
• (Wechsel) (R | s) bezeichnet die Set Union von von r und S. beschriebenen Sätze, wenn R zum Beispiel {"ab", "c"} und S beschreibt, beschreibt {"ab", "d", "ef"}, Ausdruck (R | s) beschreibt {"ab", "C", "D", "EF"}.
• (Kleene Star) (R*) bezeichnet das kleinste Superset des Satzes beschrieben von R das enthält ε und ist abgeschlossen unter String -Verkettung. Dies ist der Satz aller Zeichenfolgen, die durch die Verkettung einer endlichen Zahl (einschließlich Null) von Strings aus dem von R beschriebenen Satz hergestellt werden können. Wenn R beispielsweise {"0", "1"} bezeichnet, bezeichnet R. (R*) bezeichnet die Menge aller endlichen Binäre Saiten (einschließlich der leeren Zeichenfolge). Wenn R {"ab", "c"}, bezeichnet, (R*) bezeichnet {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ...}.

Um Klammern zu vermeiden, wird angenommen, dass der Kleene -Stern die höchste Priorität, dann die Verkettung und dann die Wechsel hat. Wenn es keine Unklarheit gibt, können Klammern weggelassen werden. Zum Beispiel, (ABC kann geschrieben werden als ABC, und a | (b (c*)) kann geschrieben werden als a | bc*. Viele Lehrbücher verwenden die Symbole ∪, +oder ∨ zur Abwechslung anstelle des vertikalen Balkens.

Beispiele:

• A | B* bezeichnet {ε, "a", "b", "bb", "bbb", ...}
• (a | b)* bezeichnet die Menge aller Zeichenfolgen ohne andere Symbole als "A" und "B", einschließlich der leeren Zeichenfolge: {ε, "A", "B", "AA", "AB", "BA", "BB" , "aaa", ...}
• AB*(c | ε) bezeichnet den Satz von Strings, beginnend mit "A", dann null oder mehr "B" s und schließlich optional ein "C": {"a", "ac", "ab", "abc", "abb", "abbc ", ...}
• (0 | (1 (01*0)*1))* bezeichnet die Menge der Binärzahlen, die ein Vielfaches von 3 sind: {ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110" , "1001", "1100", "1111", "00000", ...}

Ausdruckskraft und Kompaktheit

Die formale Definition von regulären Ausdrücken ist absichtlich minimal und vermeidet die Definition ? und +- Diese können wie folgt ausgedrückt werden: a+ = aa*, und a? = (a | ε). Manchmal das ergänzen Der Bediener wird hinzugefügt, um a zu geben Verallgemeinerter regulärer Ausdruck; hier R^c entspricht allen Zeichenfolgen über σ*, die nicht übereinstimmen R. Im Prinzip ist der Komplementbetreiber überflüssig, da er keine Ausdruckskraft gewährt. Es kann jedoch einen regelmäßigen Ausdruck viel prägnanter machen - die Ausbildung eines einzelnen Komplementbetreibers kann a verursachen Doppelte Exponential Blow-up seiner Länge.^[27][28][29]

Regelmäßige Ausdrücke in diesem Sinne können die regulären Sprachen ausdrücken, genau die Klasse von Sprachen, die von akzeptiert werden, deterministische endliche Automaten. Es gibt jedoch einen signifikanten Unterschied in der Kompaktheit. Einige Klassen regulärer Sprachen können nur durch deterministische endliche Automaten beschrieben werden, deren Größe wächst exponentiell in der Größe der kürzesten äquivalenten regulären Ausdrücke. Das Standardbeispiel hier sind die SprachenL_k bestehend aus allen Saiten über dem Alphabet {a,b} Deren k^th-From-Last-Buchstaben gleicha. Einerseits beschreibt ein regulärer Ausdruck L₄ wird gegeben von$oder$.

Verallgemeinern dieses Muster auf L_k gibt den Ausdruck:$oder }. \,}$

Andererseits ist bekannt, dass jeder deterministische endliche Automaten, der die Sprache akzeptiert L_k Muss mindestens 2 haben^k Zustände. Zum Glück gibt es eine einfache Zuordnung von regulären Ausdrücken bis zum allgemeinen Nichtdeterministische endliche Automaten (NFAS), das nicht zu einer solchen Größe führt; Aus diesem Grund werden NFAs häufig als alternative Darstellungen regulärer Sprachen verwendet. NFAs sind eine einfache Variation des Typs 3 Grammatiken des Chomsky -Hierarchie.^[25]

In der entgegengesetzten Richtung gibt es viele Sprachen, die leicht von einem DFA beschrieben werden, die durch einen regulären Ausdruck nicht leicht beschrieben werden. Zum Beispiel die Bestimmung der Gültigkeit eines gegebenen ISBN Erfordert das Berechnen des Moduls der Ganzzahlbasis 11 und kann problemlos mit einem 11-Zustands-DFA implementiert werden. Ein regelmäßiger Ausdruck, der das gleiche Problem der Trennbarkeit um 11 an Antworten beantwortet, ist jedoch mindestens mehrere Megabyte in Länge.

Bei einem regelmäßigen Ausdruck, Thompsons Baualgorithmus berechnet einen äquivalenten nicht deterministischen endlichen Automaten. Eine Umwandlung in die entgegengesetzte Richtung wird durch erreicht Kleenes Algorithmus.

Schließlich ist es erwähnenswert, dass viele reale "reguläre Ausdrucks" -Motoren Merkmale implementieren, die nicht durch die regulären Ausdrücke im Sinne der formalen Sprachtheorie beschrieben werden können. Vielmehr implementieren sie Regexes. Sehen unter Für mehr dazu.

Entscheidung der Äquivalenz regulärer Ausdrücke

Wie in vielen der obigen Beispiele zu sehen ist, gibt es mehr als eine Möglichkeit, einen regelmäßigen Ausdruck zu erstellen, um die gleichen Ergebnisse zu erzielen.

Es ist möglich, eine zu schreiben Algorithmus Das entscheidet für zwei gegebene reguläre Ausdrücke, ob die beschriebenen Sprachen gleich sind; Der Algorithmus reduziert jeden Ausdruck auf a Minimale deterministische endliche Zustandsmaschineund bestimmt, ob sie sind isomorph (gleichwertig).

Algebraische Gesetze für reguläre Ausdrücke können mit einer Methode von Gischer erhalten werden, die am besten in einem Beispiel erklärt wird: um zu überprüfen, ob ((X+Y)^* und (X^* Y^*)^* bezeichnen die gleiche reguläre Sprache für alle regulären Ausdrücke X, YEs ist notwendig und ausreichend zu prüfen, ob die jeweiligen regulären Ausdrücke (a+b)^* und (a^* b^*)^* bezeichnen die gleiche Sprache über das Alphabet σ = {a,b}. Allgemeiner eine Gleichung E=F Zwischen den regelmäßigen Expressionsbegriffen mit Variablen gilt, wenn und nur wenn die Instanziierung mit unterschiedlichen Variablen durch verschiedene Symbolkonstanten ersetzt wird.^[30][31]

Jeder reguläre Ausdruck kann ausschließlich in Bezug auf die geschrieben werden Kleene Star und Gewerkschaften setzen. Dies ist ein überraschend schwieriges Problem. So einfach die regulären Ausdrücke auch sind, es gibt keine Methode, um sie systematisch in eine normale Form umzuschreiben. Der Mangel an Axiom in der Vergangenheit führte zum Problem der Sternhöhe. 1991, Dexter Kozen Axiomatisierte reguläre Ausdrücke als Kleene Algebramit Gleichung und Verwendung Hornklausel Axiome.^[32] Bereits im Jahr 1964 hatte Redko bewiesen, dass kein endlicher Satz reiner Gleichungs -Axiome die Algebra der regulären Sprachen charakterisieren kann.^[33]

Syntax

Eine Regex Muster entspricht einem Ziel Saite. Das Muster besteht aus einer Sequenz von Atome. Ein Atom ist ein einzelner Punkt innerhalb des Regex -Musters, das es mit der Zielzeichenfolge übereinstimmen versucht. Das einfachste Atom ist ein wörtliches, aber die Gruppierung von Teilen des Musters, die zu einem Atom entspricht () als Metacharacter. Metacharaccters helfen Form: Atome; Quantifizierer sagen, wie viele Atome (und ob es a ist gierig Quantor oder nicht); ein logischer oder charakter, der eine Reihe von Alternativen und einen logischen Nicht -Charakter bietet, der die Existenz eines Atoms negiert; und Backreferenzen, um sich auf frühere Atome eines vollständigen Atomemusters zu beziehen. Es wird ein Match gemacht, nicht wenn alle Atome der Saite übereinstimmen, sondern wenn alle Musteratome in der Regex übereinstimmen. Die Idee ist, ein kleines Zeichenmuster für eine große Anzahl möglicher Zeichenfolgen zu bestehen, anstatt eine große Liste aller wörtlichen Möglichkeiten zu erstellen.

Abhängig vom Regex -Prozessor gibt es etwa vierzehn Metacharacter, die ihre Charaktere haben oder nicht, die ihre haben oder nicht wörtlich Charakter Bedeutung, abhängig vom Kontext oder ob sie "entkommen" sind, d. H. Vorangegangen von einem FluchtabfolgeIn diesem Fall der Backslash \. Moderne und POSIX-erweiterte Regexes verwenden häufiger Metacharacter als ihre buchstäbliche Bedeutung, um "Backslash-Rosis" oder zu vermeiden oder zu vermeiden. Lieger Zahnstocher -Syndrom Es ist sinnvoll, eine Metacharacter in einen wörtlichen Modus zu fliehen. Aber wenn man anfängt, ist es sinnvoller, die vier Halterung Metacharacter zu haben () und {} Seien Sie in erster Linie wörtlich und "entkommen" dieser üblichen Bedeutung, um Metacharacter zu werden. Gemeinsame Standards implementieren beide. Die üblichen Metacharacer sind {} [] ()^$. |*+? und \. Die üblichen Charaktere, die Metacharacter werden, wenn sie entkommen DSWDSW und N.

Grenzwerte

Beim Eintritt in eine Regex in einer Programmiersprache können sie als üblicher Streicherliteral dargestellt werden, daher normalerweise zitiert; Dies ist beispielsweise in C, Java und Python üblich, wo die Regex betreffend ist eingetragen als "betreffend". Sie werden jedoch oft mit Schrägstrichen als geschrieben Grenzwerte, wie in /betreffend/ für die Regex betreffend. Dies entspricht ed, wo / ist der Editor -Befehl zum Suchen und ein Ausdruck /betreffend/ Kann verwendet werden, um eine Reihe von Zeilen festzulegen (entsprechen dem Muster), die mit anderen Befehlen auf beiden Seiten kombiniert werden können g/re/p wie in Grep ("Global Regex Print"), das in den meisten enthalten ist Unix-basierte Betriebssysteme wie z. Linux Verteilungen. Eine ähnliche Konvention wird in verwendet sed, wo suchen und ersetzen wird von gegeben von s/re/Ersatz/ und Muster können mit einem Komma verbunden werden, um eine Reihe von Linien wie in anzugeben /re1/,/re2/. Diese Notation ist aufgrund ihrer Verwendung in besonders bekannt Perl, wo es Teil der Syntax ist, die sich von normalen String -Literalen unterscheidet. In einigen Fällen wie SED und Perl können alternative Grenzwerte verwendet werden, um Kollision mit Inhalten zu vermeiden und zu vermeiden, dass der Trennzeichen im Inhalt vorhanden ist. Zum Beispiel in SED der Befehl s,/, x, wird a ersetzen a / mit einem Xmit Kommas als Grenzwerte.

Standards

Das IEEE Posix Standard hat drei Konformitätssätze: Bre (Grundlegende reguläre Ausdrücke),^[34] EHE (Erweiterte reguläre Ausdrücke) und Sre (Einfache reguläre Ausdrücke). Sre ist veraltet,^[35] zugunsten von BRE, wie beide bieten Rückwärtskompatibilität. Der Unterabschnitt unten abdeckt die Charakterklassen gilt sowohl für BRE als auch für ERE.

Bre und ehe zusammenarbeiten. Ehe fügt hinzu ?, +, und |und es beseitigt die Notwendigkeit, den Metacharacodern zu entkommen () und {}, welche sind erforderlich in Bre. Solange die POSIX -Standardsyntax für Regexes eingehalten wird, kann und häufig eine zusätzliche Syntax für spezifische (dennoch posix konforme) Anwendungen vorhanden sein. Obwohl POSIX.2 einige Implementierungsspezifikationen undefiniert hinterlässt, bieten BRE und ERE einen "Standard", der seitdem als Standardsyntax vieler Tools angewendet wurde, bei denen die Wahl von BRE- oder ERE -Modi normalerweise eine unterstützte Option ist. Zum Beispiel, GNU Grep hat die folgenden Optionen: "grep -e"für ehe und"grep -g"Für Bre (der Standard) und"grep -p" zum Perl Regexes.

Perl Regexes sind zu einem De -facto -Standard geworden, der eine reiche und starke Reihe von Atomausdrücken hat. Perl hat keine "grundlegenden" oder "erweiterten" Werte. Wie in posix eres, () und {} werden als Metacharacter behandelt, es sei denn, sie entkommen; Andere Metacharacter sind buchstäblich oder symbolisch, basierend auf dem Kontext. Zusätzliche Funktionen umfassen fauler Matching, Hinterreferenzen, benannte Capture -Gruppen und rekursiv Muster.

Posix grundlegend und erweitert

In dem Posix Standard, einfache reguläre Syntax (Bre) erfordert, dass die Metacharaccters () und {} bezeichnet werden \ (\) und \ {\}, während die regelmäßige Syntax erweiterte (EHE) nicht.

Beispiele:

• .bei entspricht jeder Saite mit drei Charakteren, die mit "at", einschließlich "Hut", "Katze", "Fledermaus", "4at", "#at" und "at" (beginnend mit einem Raum) enden.
• [HC] bei Matchiert "Hut" und "Katze".
• [^b] bei entspricht allen Saiten, die von übereinstimmten .bei außer "Fledermaus".
• [^hc] bei entspricht allen Saiten, die von übereinstimmten .bei Anders als "Hut" und "Katze".
• ^[hc] bei Übereinstimmung mit "Hut" und "Katze", aber erst am Anfang der Saite oder Linie.
• [HC] bei $ Übereinstimmt "Hut" und "Katze", aber nur am Ende der Saite oder Linie.
• \ [. \] entspricht jedem einzelnen Charakter, der von "[" und "]" umgeben ist, da die Klammern zum Beispiel entkommen sind: "[a]", "[b]", "[7]", "[@]", "[]] "und" [] "(Halterung der Raumklasse).
• s.* Übereinstimmung mit null oder mehr Zeichen, zum Beispiel: "S", "Saw", "Seed", "S3W96.7" und "S6#H%(>>> M n MQ".

Possix erweitert

Die Bedeutung von Metacharactern entkam mit einem Backslash wird für einige Zeichen im POSIX erweiterten regulären Ausdruck umgekehrt (EHE) Syntax. Mit dieser Syntax wird ein Backslash dazu führt, dass der Metacharakter als wörtliche Charakter behandelt wird. Also zum Beispiel, \ (\) ist jetzt () und \ {\} ist jetzt {}. Zusätzlich wird die Unterstützung für die Entfernung für \n Backreferenzen und die folgenden Metacharaccters werden hinzugefügt:

Beispiele:

• [hc]? bei Matches "at", "Hut" und "Katze".
• [hc]*bei Matchiert "at", "Hut", "Katze", "Hhat", "Chat", "Hcat", "Cchchat" und so weiter.
• [HC]+bei Matchiert "Hut", "Katze", "Hhat", "Chat", "Hcat", "Cchchat" und so weiter, aber nicht "at".
• Katze | Hund Matchiert "Katze" oder "Hund".

POSIX erweiterte reguläre Ausdrücke können häufig mit modernen Unix -Dienstprogrammen verwendet werden Befehlszeile Flagge -E.

Charakterklassen

Die Charakterklasse ist das grundlegendste Regex -Konzept nach einem wörtlichen Match. Es lässt eine kleine Reihenfolge von Zeichen zu einem größeren Satz von Zeichen übereinstimmen. Zum Beispiel, [A-Z] könnte für jeden Großbuchstaben im englischen Alphabet stehen, und \d könnte jede Ziffer bedeuten. Charakterklassen gelten für beide POSIX -Ebenen.

Bei der Angabe einer Reihe von Charakteren wie z. [a-Z] (d. H. Kleinbuchstaben a in Großbuchstaben Z), Die Gebietsschemaseinstellungen des Computers bestimmen den Inhalt durch die numerische Bestellung der Zeichenkodierung. Sie könnten Ziffern in dieser Sequenz speichern, oder die Bestellung könnte sein ABC… ZABC… Z., oder Aabbcc… ZZ. Der POSIX -Standard definiert also eine Zeichenklasse, die vom installierten Regex -Prozessor bekannt ist. Diese Definitionen befinden sich in der folgenden Tabelle:

POSIX -Charakterklassen können nur in Klammerausdrücken verwendet werden. Zum Beispiel, [[:upper:]ab] entspricht den Großbuchstaben und Kleinbuchstaben "A" und "B".

Eine zusätzliche nicht-posixe Klasse, die von einigen Tools verstanden wird, ist [:word:], was normalerweise definiert wird als [:alnum:] Plus unterstreicht. Dies spiegelt die Tatsache wider, dass in vielen Programmiersprachen dies die Zeichen sind, die in Kennungen verwendet werden können. Der Editor Vim unterscheidet weiter Wort und Wortkopf Klassen (unter Verwendung der Notation \w und \h) Da in vielen Programmiersprachen die Zeichen, die eine Kennung beginnen können \h\w* oder [[:alpha:]_][[:alnum:]_]* in POSIX Notation.

Beachten Charakterklassen werden üblicherweise als als bezeichnet als POSIX -Charakterklassen in anderen Regex -Aromen, die sie unterstützen. Mit den meisten anderen Regex -Aromen der Begriff Charakterklasse wird verwendet, um zu beschreiben, was POSIX aufruft Ausdrücke von Klammer.

Perl und Pcre

Aufgrund seiner ausdrucksstarken Kraft und seiner (relativen) Lesen haben viele andere Dienstprogramme und Programmiersprachen eine ähnliche Syntax übernommen wie Perl's - zum Beispiel, Java, JavaScript, Julia, Python, Rubin, Qt, Microsoft's .NET Framework, und XML -Schema. Einige Sprachen und Tools wie z. Schub und Php Unterstützen Sie mehrere Regex -Aromen. Perl-Derivative Regex-Implementierungen sind nicht identisch und implementieren normalerweise eine Untergruppe von Merkmalen in Perl 5.0, die 1994 veröffentlicht wurden. Perl enthält manchmal Funktionen, die ursprünglich in anderen Sprachen gefunden werden. Zum Beispiel implementiert Perl 5.10 syntaktische Erweiterungen, die ursprünglich in PCRE und Python entwickelt wurden.^[37]

Fauler Matching

In Python und einigen anderen Implementierungen (z. B. Java) sind die drei gemeinsamen Quantifizierer (*, + und ?) sind gierig Standardmäßig, weil sie so viele Zeichen wie möglich übereinstimmen.^[38] Die Regex ".+" (einschließlich der Doppelquote) auf die Zeichenfolge angewendet

"Ganymede", fuhr er fort, "ist der größte Mond im Sonnensystem."

entspricht der gesamten Linie (weil die gesamte Linie beginnt und mit einer Doppelquote endet), anstatt nur den ersten Teil zu erreichen. "Ganymede", ". Die oben genannten Quantifizierer können jedoch gemacht werden faul oder minimal oder widerwilligmit so wenigen Zeichen wie möglich durch Anhängen eines Fragezeichens: ".+?" nur übereinstimmt "Ganymede", ".^[38]

Besitzergreichung

In Java können Quantifizierer hergestellt werden besitzergreifend Indem Sie ein Plus -Schild anhängen, das die Sicherung (in einem Backtracking -Engine) deaktiviert, auch wenn dies das Gesamtspiel ermöglichen würde, um erfolgreich zu sein:^[39] Während die Regex ".*" auf die Zeichenfolge angewendet

"Ganymede", fuhr er fort, "ist der größte Mond im Sonnensystem."

entspricht der gesamten Zeile, der Regex ".*+" tut überhaupt nicht übereinstimmen, Weil .*+ verbraucht die gesamte Eingabe, einschließlich des Finales ". Daher sind Possessiv -Quantifizierer bei negierten Charakterklassen am nützlichsten, z. "[^"]*+", was passt "Ganymede", " Bei der gleichen Zeichenfolge angewendet.

Eine weitere häufige Erweiterung, die dieselbe Funktion dient, ist die Atomgruppierung, die die Backtracking für eine Klammerngruppe deaktiviert. Die typische Syntax ist (?> Gruppe). Zum Beispiel während ^(wi | w) i $ entspricht beides wi und Wii, ^(?> wi | w) i $ nur übereinstimmend Wii Weil es dem Motor verboten ist, zurückzuverfolgen, und versuchen Sie es, die Gruppe als "W" festzulegen.^[40]

Possessiv -Quantifizierer sind einfacher zu implementieren als gierige und faule Quantifizierer und in der Laufzeit in der Regel effizienter.^[39]

Muster für nicht reguläre Sprachen

Viele Funktionen in praktisch allen modernen regulären Ausdrucksbibliotheken bieten eine ausdrucksstarke Kraft, die die übersteigt reguläre Sprachen. Beispielsweise ermöglichen viele Implementierungen die Gruppierung von Subexpressionen mit Klammern und das Rückruf des Werts, den sie in demselben Ausdruck übereinstimmen ( Hinterreferenzen). Dies bedeutet, dass unter anderem ein Muster Streicher wiederholter Wörter wie "Papa" oder "Wikiwiki" übereinstimmen kann, genannt Quadrate in der formalen Sprachtheorie. Das Muster für diese Saiten ist (.+) \ 1.

Die Sprache der Quadrate ist nicht regelmäßig und es auch nicht kontextfrei, aufgrund der Lemma pumpen. Jedoch, Musteranpassung Mit einer unbegrenzten Anzahl von Backreferenzen, wie sie von zahlreichen modernen Werkzeugen unterstützt werden, ist es immer noch Kontextsensitiv.^[41] Das allgemeine Problem der Übereinstimmung einer beliebigen Anzahl von Backreferenzen ist NP-Complete, exponentiell durch die Anzahl der verwendeten BackREF -Gruppen wachsen.^[42]

Viele Tools, Bibliotheken und Motoren, die solche Konstruktionen liefern regulären Ausdruck für ihre Muster. Dies hat zu einer Nomenklatur geführt, bei der der Begriff regulärer Ausdruck unterschiedliche Bedeutungen hat Formale Sprachtheorie und Musteranpassung. Aus diesem Grund haben einige Leute den Begriff verwendet Regex, Regexp, oder einfach Muster Letzteres beschreiben. Larry Wall, Autor der Perl -Programmiersprache, schreibt in einem Aufsatz über das Design von Raku:

"Reguläre Ausdrücke" […] sind nur geringfügig mit realen regulären Ausdrücken zusammenhängen. Trotzdem ist der Begriff mit den Fähigkeiten unserer Muster -Matching -Motoren gewachsen, daher werde ich hier nicht versuchen, die sprachliche Notwendigkeit zu bekämpfen. Ich werde sie jedoch im Allgemeinen "Regexes" (oder "Regexen" nennen, wenn ich in einer angelsächsischen Stimmung bin).^[21]

Andere Merkmale, die bei der Beschreibung regulärer Sprachen nicht zu finden sind, umfassen Behauptungen. Dazu gehören die allgegenwärtigen ^ und $sowie einige anspruchsvollere Erweiterungen wie Aussehen. Sie definieren die Umgebung einer Übereinstimmung und verschütten nicht in das Match selbst, eine Funktion, die nur für den Anwendungsfall der String -Suche relevant ist. Einige von ihnen können in einer regulären Sprache simuliert werden, indem die Umgebung auch als Teil der Sprache behandelt wird.^[43]

Implementierungen und Laufzeiten

Es gibt mindestens drei verschiedene verschiedene Algorithmen Das entscheidet, ob und wie ein bestimmtes Regex mit einer Zeichenfolge übereinstimmt.

Der älteste und schnellste stützt sich auf ein Ergebnis in formaler Sprachtheorie, die es jedem erlaubt Nichtdeterministisches endliches Automaten (NFA) in a verwandelt werden Deterministische endliche Automaten (DFA). Die DFA kann explizit konstruiert und dann auf der resultierenden Eingangszeichenfolge ein Symbol jeweils ausgeführt werden. Konstruktion des DFA für einen regelmäßigen Ausdruck der Größe m hat die Zeit und den Speicherkosten von O(2^m), aber es kann auf einer Reihe von Größe ausgeführt werden n rechtzeitig O(n). Beachten Sie, dass die Größe des Ausdrucks die Größe nach Abkürzungen, wie z. B. numerische Quantifizierer, erweitert wurde.

Ein alternativer Ansatz besteht darin, die NFA direkt zu simulieren, im Wesentlichen jeden DFA -Zustand auf Bedarf zu erstellen und ihn dann beim nächsten Schritt zu verwerfen. Dies hält die DFA implizit und vermeidet die exponentiellen Baukosten, aber die Laufkosten steigen zu O(mn). Der explizite Ansatz wird der DFA -Algorithmus und der implizite Ansatz des NFA -Algorithmus bezeichnet. Das Hinzufügen von Caching zum NFA -Algorithmus wird oft als "fauler DFA" -Algorithmus oder nur als DFA -Algorithmus bezeichnet, ohne zu unterscheiden. Diese Algorithmen sind schnell, aber es ist schwierig, gruppierte Unterexpressionen, faule Quantifizierung und ähnliche Funktionen zu verwenden.^[44][45] Zu den modernen Implementierungen gehören die RE1-RE2-SREGEX-Familie basierend auf dem Cox-Code.

Der dritte Algorithmus besteht darin Backtracking. Dieser Algorithmus wird allgemein als NFA bezeichnet, diese Terminologie kann jedoch verwirrend sein. Seine Laufzeit kann exponentiell sein, was einfache Implementierungen bei der Übereinstimmung mit Ausdrücken wie ausstellen (a|aa)*b Dies enthalten sowohl Wechsel als auch unbegrenzte Quantifizierung und erzwingen den Algorithmus, eine exponentiell zunehmende Anzahl von Unterkasen zu berücksichtigen. Dieses Verhalten kann ein Sicherheitsproblem verursachen, das genannt wird Regelmäßige Ausdrucksverleugnung des Dienstes (Redos).

Obwohl Backtracking -Implementierungen im schlimmsten Fall nur eine exponentielle Garantie bieten, bieten sie eine viel größere Flexibilität und Ausdruckskraft. Beispielsweise muss jede Implementierung, die die Verwendung von Backreferenzen ermöglicht oder die verschiedenen von Perl eingeführten Erweiterungen implementiert, eine Art Backtracking enthalten. Einige Implementierungen versuchen, das Beste aus beiden Algorithmen bereitzustellen, indem er zuerst einen schnellen DFA -Algorithmus ausführt und nur dann zu einem möglicherweise langsameren Backtracking -Algorithmus zurückkehrt, wenn während des Spiels eine Rückreferenz auftritt. GNU Grep (und der zugrunde liegende Gnulib DFA) verwendet eine solche Strategie.^[46]

Sublinear -Laufzeitalgorithmen wurden mit Verwendung erreicht Boyer-Moore (BM) -Basis Algorithmen und verwandte DFA -Optimierungstechniken wie der umgekehrte Scan.^[47] GNU Grep, das eine Vielzahl von POSIX-Syntaxen und -verlängerungen unterstützt, verwendet BM für eine Vorfilterung für Firstpass und verwendet dann eine implizite DFA. Wu Agrep, was eine ungefähre Übereinstimmung implementiert, kombiniert die Präfiltrichter in die DFA in BDM (rückwärts -DAWG -Matching). Das BNDM von NR-Grep erweitert die BDM-Technik mit einer parallelen Schicht-or-Bit-Ebene.^[48]

Es gibt einige theoretische Alternativen zum Backtracking für Backreferenzen, und ihre "Exponenten" sind insofern zahmer, als sie nur mit der Anzahl der Backreferenzen zusammenhängen, eine feste Eigenschaft einiger Regexp -Sprachen wie POSIX. Eine naive Methode, die eine nicht zurückhaltende NFA für jede Rückreferenznote dupliziert, hat eine Komplexität von ${\ displayStyle {\ mathrm {o}} (n^{2k+2})}$ Zeit und ${\ displayStyle {\ mathrm {o}} (n^{2k+1})}$ Platz für einen Heuhaufen Länge N und k -Rückbeläge in der Regexp.^[49] Eine aktuelle theoretische Arbeit, die auf Speicherautomaten basiert, liefert eine engere Bindung auf "aktive" variable Knoten und eine Polynommöglichkeit für einige Backreferenced Regexps.^[50]

Unicode

In theoretischer Hinsicht kann jeder Token-Set mit regulären Ausdrücken übereinstimmen, solange es vor Definition ist. In Bezug auf historische Implementierungen wurden ursprünglich Regexes zur Verwendung geschrieben ASCII Charaktere als Token -Set, obwohl Regex -Bibliotheken zahlreiche andere unterstützt haben Zeichensätze. Viele moderne Regex -Motoren bieten zumindest einige Unterstützung für Unicode. In den meisten Fällen macht es keinen Unterschied, was der Charakter -Set ist, aber es treten einige Probleme auf, wenn sie Regexes zur Unterstützung von Unicode erweitern.

• Unterstützte Codierung. Einige Regex -Bibliotheken erwarten, an einer bestimmten Codierung statt in abstrakten Unicode -Zeichen zu arbeiten. Viele von ihnen benötigen die UTF-8 Codierung, obwohl andere erwarten könnten UTF-16, oder UTF-32. Im Gegensatz dazu sind Perl und Java bei Codings agnostisch und arbeiten stattdessen intern auf dekodierten Zeichen.
• Unterstützter Unicode -Bereich. Viele Regex -Motoren unterstützen nur die Grundlegende mehrsprachige EbeneDas heißt, die Zeichen, die mit nur 16 Bit codiert werden können. Derzeit (ab 2016^{[aktualisieren]}) Nur wenige Regex-Motoren (z. B. Perl und Java) können den vollständigen 21-Bit-Unicode-Bereich verarbeiten.
• Erweiterende ascii-orientierte Konstrukte auf Unicode. Zum Beispiel in ASCII-basierten Implementierungen die Zeichenbereiche der Form [x-y] sind wo immer gültig x und y haben Codepunkte im Bereich [0x00,0x7f] und CodePoint (x) ≤ CodePoint (y). Die natürliche Erweiterung solcher Zeichenbereiche auf Unicode würde lediglich die Anforderung ändern, dass die Endpunkte in [0x00,0x7f] auf die Anforderung liegen, dass sie in [0x0000,0x10ffff] liegen. In der Praxis ist dies jedoch oft nicht der Fall. Einige Implementierungen wie die von gaffenLassen Sie die Charakterbereiche nicht zu, um Unicode -Blöcke zu überqueren. Ein Bereich wie [0x61,0x7f] ist gültig, da beide Endpunkte in den lateinischen Basisblock fallen, ebenso wie [0x0530,0x0560], da beide Endpunkte in den armenischen Block fallen, aber ein Bereich wie [0x0061,0x0532] ist ungültig, da er enthält, da er enthält, da er enthält, da er enthält, da er enthält, da er enthält, da er enthält Mehrere Unicode -Blöcke. Andere Motoren wie die der Vim Editor, Blockcrossing zulassen, aber die Charakterwerte dürfen nicht mehr als 256 voneinander entfernt sein.^[51]
• Fall Unempfindlichkeit. Einige Fall-Insitivitätsflags betreffen nur die ASCII-Zeichen. Andere Flaggen betreffen alle Charaktere. Einige Motoren haben zwei verschiedene Flags, eine für ASCII, die andere für Unicode. Genau welche Zeichen zu den POSIX -Klassen gehören auch variiert.
• Cousins ​​von Fallunempfindlichkeit. Da ASCII eine Fallunterscheidung hat, wurde die Unempfindlichkeit der Fall bei der Suche nach Text zu einem logischen Merkmal. Unicode führte alphabetische Skripte ohne Fall ein Devanagari. Für diese, Fallempfindlichkeit ist nicht anwendbar. Für Skripte wie Chinesisch erscheint eine andere Unterscheidung logisch: zwischen traditionell und vereinfacht. In arabischen Skripten, Unempfindlichkeit gegen anfängliche, mediale, endgültige und isolierte Position kann erwünscht werden. Auf Japanisch Unempfindlichkeit zwischen Hiragana und Katakana ist manchmal nützlich.
• Normalisierung. Unicode hat Charaktere kombinieren. Wie alte Schreibmaschinen können einfache Basiszeichen (weiße Räume, Unterbrechungen, Symbole, Ziffern oder Buchstaben) von einem oder mehreren Nicht-Abstands-Symbolen (normalerweise Diakritika wie Akzentmarkierungen) folgen, um ein einzelnes druckbares Zeichen zu bilden. Unicode bietet aber auch einen begrenzten Satz vorkomponierter Zeichen, d. H. Zeichen, die bereits eine oder mehrere kombinierte Zeichen enthalten. Eine Sequenz eines Basischarakters + kombinierende Zeichen sollte mit dem identischen einzelnen vorkomponierten Charakter übereinstimmen (nur einige dieser Kombinationsequenzen können in ein einzelnes Unicode -Zeichen vorkomponiert werden, aber unendlich viele andere kombinierende Sequenzen sind in Unicode möglich und für verschiedene Sprachen benötigt Verwenden Sie ein oder mehrere kombinierte Zeichen nach einem anfänglichen Basiszeichen; diese kombinierten Sequenzen kann Geben Sie einen Basischarakter an oder kombinieren Sie Zeichen, die teilweise vorkomponiert sind, jedoch nicht unbedingt in kanonischer Reihenfolge und nicht unbedingt die kanonischen Präkonzenten verwenden). Der Prozess der Standardisierung von Sequenzen eines Basischarakters + Kombiniert Zeichen durch Zersetzung dieser kanonisch äquivalent Sequenzen, bevor sie in kanonische Reihenfolge neu ordnen (und optional neu komponieren etwas Das Kombinieren von Zeichen in das führende Basischarakter wird als Normalisierung bezeichnet.
• Neue Kontrollcodes. Unicode unter anderem eingeführt, Byte -Bestellmarken und Textrichtungsmarkierungen. Diese Codes müssen möglicherweise auf besondere Weise behandelt werden.
• Einführung von Charakterklassen für Unicode -Blöcke, Skripte und zahlreiche andere Zeicheneigenschaften. Blockeigenschaften sind viel weniger nützlich als Skripteigenschaften, da ein Block Codepunkte aus mehreren verschiedenen Skripten haben kann und ein Skript Codepunkte aus verschiedenen Blöcken haben kann.^[52] Im Perl und die java.util.regex Bibliothek, Eigenschaften des Formulars \ p {Inx} oder \ p {block = x} Passen Sie die Zeichen im Block überein X und \ P {Inx} oder \ P {block = x} stimmt mit Codepunkten in diesem Block nicht ab. Ähnlich, \ p {armenisch}, \ p {isarmenian}, oder \ p {script = armenisch} entspricht jedem Charakter im armenischen Drehbuch. Im Algemeinen, \ p {x} entspricht jedem Charakter mit beiden Binäreigenschaften X oder die allgemeine Kategorie X. Zum Beispiel, \ p {lu}, \ p {Uppercase_letter}, oder \ p {gc = lu} entspricht jedem Großbuchstaben. Binäre Eigenschaften, die sind nicht Allgemeine Kategorien umfassen \ p {White_space}, \ p {alphabetisch}, \ p {math}, und \ p {Dash}. Beispiele für nicht-binäre Eigenschaften sind \ p {bidi_class = right_to_left}, \ p {Word_break = a_letter}, und \ p {numeric_value = 10}.

Verwendet

Eine schwarze Liste auf Wikipedia Dies verwendet regelmäßige Ausdrücke, um schlechte Titel zu identifizieren

Regexes sind nützlich bei einer Vielzahl von Aufgaben von Textverarbeitungen und allgemeiner nützlich String -Verarbeitung, wo die Daten nicht textlich sein müssen. Gemeinsame Anwendungen umfassen Datenvalidierung, Datenkratzen (besonders Web -Scraping), Daten umstreiten, einfach Parsing, die Produktion von Satzstellung markieren Systeme und viele andere Aufgaben.

Während Regexes im Internet nützlich wären SuchmaschinenWenn Sie sie in der gesamten Datenbank in der gesamten Datenbank verarbeiten, können Sie abhängig von der Komplexität und dem Design des Regex übermäßige Computerressourcen konsumieren. Obwohl Systemadministratoren in vielen Fällen in REGEX-basierte Abfragen intern ausführen können, bieten die meisten Suchmaschinen der Öffentlichkeit keine Regex-Unterstützung. Bemerkenswerte Ausnahmen umfassen Google -Code -Suche und Exalead. Die Google -Code -Suche wurde jedoch im Januar 2012 geschlossen.^[53]

Beispiele

Die spezifischen Syntaxregeln variieren je nach spezifischer Implementierung. Programmiersprache, oder Bibliothek in Benutzung. Darüber hinaus kann die Funktionalität von Regex -Implementierungen zwischen variieren. Versionen.

Da Regexes ohne Beispiele schwierig zu erklären und zu verstehen können, sind interaktive Websites zum Testen von Regexes eine nützliche Ressource für das Lernen von Regexes durch Experimentieren. Dieser Abschnitt enthält eine grundlegende Beschreibung einiger Eigenschaften von Regexes im Rahmen der Illustration.

Die folgenden Konventionen werden in den Beispielen verwendet.^[54]

Metacharacacter (s) ;; Die Metacharacters -Spalte gibt die nachgewiesene Regex -Syntax an = ~ m // ;; Zeigt eine Regex an passen Betrieb in Perl = ~ s /// ;; Zeigt eine Regex an Auswechslung Betrieb in Perl

Erwähnenswert ist auch, dass diese Regexes alle perlähnliche Syntax sind. Standard Posix Regelmäßige Ausdrücke sind unterschiedlich.

Sofern nicht anders angegeben, entsprechen die folgenden Beispiele der Perl Programmiersprache, Release 5.8.8, 31. Januar 2006. Dies bedeutet, dass andere Implementierungen möglicherweise keine Unterstützung für einige Teile der hier gezeigten Syntax haben (z. B. Basic vs. Extended Regex, \ (\) vs. (), oder mangelnde \d Anstatt von Posix [:Ziffer:]).

Die in diesen Beispielen verwendeten Syntax und Konventionen stimmen auch mit der anderen Programmierumgebungen überein.^[55]

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/...../) {  drucken "$ String1 hat Länge> = 5. \ n"; } 

Hallo Welt  hat Länge> = 5. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/(h ..). (o ..)/) {  drucken "Wir haben '$ 1' und '$ 2' abgestimmt. \ N"; } 

Wir haben 'Hel' und 'O W' abgestimmt. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/l+//) {  drucken "Es gibt einen oder mehrere aufeinanderfolgende Buchstaben" L "'s in $ String1. \ N"; } 

Es gibt einen oder mehrere aufeinanderfolgende Brief "L" in Hello World. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/h.? e/) {  drucken "Es gibt ein 'H' und ein 'e' von getrennt von";  drucken "0-1 Zeichen (z. B. er hue hee). \ N"; } 

Es gibt ein 'H' und ein 'e' durch 0-1 Zeichen (z. B. er hue hee). 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/(l.+? O)/) {  drucken "Das Nicht-Greedy-Match mit 'l' gefolgt von einem oder";  drucken "Mehr Charaktere sind eher" llo "als" llo wo ". \ n"; } 

Das Nicht-Greedy-Match mit 'L', gefolgt von einem oder mehreren Charakteren, ist eher "llo" als "llo wo". 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/el*o//) {  drucken "Es gibt ein 'e', ​​gefolgt von Null zu vielen";  drucken "'l' gefolgt von 'o' (z. B. Eo, Elo, Ello, Elllo). \ n"; } 

Es gibt ein 'e', ​​gefolgt von Null bis vielen 'l', gefolgt von 'o' (z. B. Eo, Elo, Ello, Elllo). 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/l {1,2}/) {  drucken "Es gibt ein Substring mit mindestens 1";  drucken "Und höchstens 2 L's in $ String1 \ n"; } 

Es gibt ein Substring mit mindestens 1 und höchstens 2 Ls in Hello World 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/[aeiou]+/) {  drucken "$ string1 enthält ein oder mehrere Vokale. \ n"; } 

Hallo Welt  Enthält ein oder mehrere Vokale. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/(hallo | hi | pogo)/) {  drucken "$ string1 enthält mindestens einen von Hallo, Hi oder Pogo."; } 

Hallo Welt  Enthält mindestens einen von Hello, Hi oder Pogo. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/llo \ b/) {  drucken "Es gibt ein Wort, das mit 'llo' endet. \ N"; } 

Es gibt ein Wort, das mit 'llo' endet. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/\ w/) {  drucken "Es gibt mindestens einen alphanumerischen";  drucken "Zeichen in $ String1 (a-z, a-z, 0-9, _). \ n"; } 

In Hello World gibt es mindestens einen alphanumerischen Charakter  (A-Z, A-Z, 0-9, _). 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/\ w/) {  drucken "Der Raum zwischen Hallo und";  drucken "Welt ist nicht alphanumerisch. \ N"; } 

Der Raum zwischen Hallo und Welt ist nicht alphanumerisch. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/\ s.*\ s/) {  drucken "In $ String1 gibt es zwei Whitespace -Charaktere, die vielleicht";  drucken "durch andere Zeichen getrennt werden. \ n"; } 

In Hello World  Es gibt zwei Whitespace -Zeichen, die durch andere Zeichen getrennt werden können. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/\ s.*\ s/) {  drucken "In $ String1 gibt es zwei Nicht-Whitespace-Zeichen, die";  drucken "Kann durch andere Zeichen getrennt werden. \ n"; } 

In Hello World  Es gibt zwei Nicht-Whitespace-Zeichen, die durch andere Zeichen getrennt werden können. 

$ String1 = "99 Flaschen Bier an der Wand."; wenn ($ String1 = ~ m/(\ d+)/) {  drucken "$ 1 ist die erste Nummer in '$ string1' \ n"; } 

99 ist die erste Zahl in '99 Flaschen Bier an der Wand. ' 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/\ d/) {  drucken "Es gibt mindestens ein Zeichen in $ String1";  drucken "Das ist keine Ziffer. \ n"; } 

Es gibt mindestens einen Charakter in Hello World  Das ist keine Ziffer. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/^er/) {  drucken "$ String1 beginnt mit den Charakteren 'er'. \ n"; } 

Hallo Welt  beginnt mit den Charakteren 'er'. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/rld $/) {  drucken "$ string1 ist eine Zeile oder Zeichenfolge";  drucken "Das endet mit 'rld'. \ n"; } 

Hallo Welt  ist eine Zeile oder eine Zeichenfolge, die mit 'RLD' endet. 

$ String1 = "Hallo \ nworld \ n"; wenn ($ String1 = ~ m/\ ah/) {  drucken "$ string1 ist eine Zeichenfolge";  drucken "Das beginnt mit 'H'. \ n"; } 

Hallo Welt  ist eine Zeichenfolge, die mit 'H' beginnt. 

$ String1 = "Hallo \ nworld \ n"; wenn ($ String1 = ~ m/d \ n \ z/) {  drucken "$ string1 ist eine Zeichenfolge";  drucken "Das endet mit 'D \\ n'. \ n"; } 

Hallo Welt  ist eine Zeichenfolge, die mit 'D \ n' endet. 

$ String1 = "Hallo Welt \ n"; wenn ($ String1 = ~ m/[^abc]/) {  drucken "$ string1 enthält ein anderes Zeichen als";  drucken "a, b und c. \ n"; } 

Hallo Welt  enthält einen anderen Charakter als A, B und c. 

Induktion

Regelmäßige Ausdrücke können häufig auf der Grundlage einer Reihe von Beispiels erstellt ("induziert" oder "gelernt") erstellt werden. Dies ist als die bekannt Induktion regulärer Sprachen und ist Teil des allgemeinen Problems von Grammatikinduktion in Computerlerntheorie. Formell angegebene Beispiele für Zeichenfolgen in einer regulären Sprache und möglicherweise auch angegebene Beispiele für Zeichenfolgen nicht In dieser regulären Sprache ist es möglich, eine Grammatik für die Sprache zu induzieren, d. H. Einen regulären Ausdruck, der diese Sprache erzeugt. Nicht alle regulären Sprachen können auf diese Weise induziert werden (siehe Sprachidentifikation in der Grenze), aber viele können. Beispielsweise kann der Satz von Beispielen {1, 10, 100} und negativer Satz (von Counterexamples) {11, 1001, 101, 0} verwendet werden 0s).

Siehe auch

• Vergleich der regulären Expressionsmotoren
• Erweiterte Backus -Naur -Form
• Passende Wildcards
• Normale Baumgrammatik
• Thompsons Konstruktion - konvertiert einen regelmäßigen Ausdruck in ein Äquivalent Nichtdeterministisches endliches Automaton (NFA)

Anmerkungen

Verweise

Externe Links

• Medien im Zusammenhang mit Regex bei Wikimedia Commons
• Reguläre Ausdrücke bei Curlie
• ISO/IEC 9945-2: 1993 Informationstechnologie - Tragbare Betriebssystemschnittstelle (POSIX) - Teil 2: Shell und Dienstprogramme
• ISO/IEC 9945-2: 2002 Informationstechnologie - Tragbare Betriebssystemschnittstelle (POSIX) - Teil 2: Systemschnittstellen
• ISO/IEC 9945-2: 2003 Informationstechnologie - Tragbare Betriebssystemschnittstelle (POSIX) - Teil 2: Systemschnittstellen
• ISO/IEC/IEEE 9945: 2009 Informationstechnologie - Basisspezifikationen des tragbaren Betriebssystemschnittstellens (POSIX®), Ausgabe 7
• Regelmäßiger Ausdruck, IEEE STD 1003.1-2017, offene Gruppe