Wyrażenie regularne - Regular expression

Wyniki dopasowania wzorca
(?<=\.) {2,}(?=[A-Z])
Dopasowywane są co najmniej dwie spacje, ale tylko wtedy, gdy występują bezpośrednio po kropce (.) i przed wielką literą.
Stephen Cole Kleene , który wprowadził tę koncepcję
Czarna lista w Wikipedii, która używa wyrażeń regularnych do identyfikowania złych tytułów

Wyrażenie regularne (skracane jako regex lub regexp , nazywane także racjonalnego wypowiedzi ) jest ciągiem znaków , który określa wyszukiwania wzorca . Zazwyczaj takie wzorce są używane przez algorytmy wyszukiwania ciągów do operacji „znajdź” lub „znajdź i zamień” na ciągach lub do walidacji danych wejściowych. Jest to technika opracowana w informatyce teoretycznej i teorii języka formalnego .

Koncepcja wyrażeń regularnych rozpoczęła się w latach 50. XX wieku, kiedy amerykański matematyk Stephen Cole Kleene sformalizował opis języka regularnego . Weszły do ​​powszechnego użytku z narzędziami do przetwarzania tekstu w systemie Unix . Od lat 80. istniały różne składnie do pisania wyrażeń regularnych, jedna to standard POSIX, a druga, szeroko stosowana, to składnia Perla .

Wyrażenia regularne są używane w wyszukiwarkach , wyszukiwaniu i zastępowaniu okien dialogowych w edytorach tekstu i edytorach tekstu , w narzędziach do przetwarzania tekstu , takich jak sed i AWK oraz w analizie leksykalnej . Wiele języków programowania zapewnia funkcje wyrażeń regularnych wbudowane lub za pośrednictwem bibliotek , ponieważ ma to zastosowanie w wielu sytuacjach.

Historia

Wyrażenia regularne powstały w 1951 roku, kiedy matematyk Stephen Cole Kleene opisał języki regularne używając notacji matematycznej zwanej zdarzeniami regularnymi . Powstały one w informatyce teoretycznej , w poddziedzinach teorii automatów (modele obliczeniowe) oraz opisie i klasyfikacji języków formalnych . Inne wczesne implementacje dopasowywania wzorców obejmują język SNOBOL , który nie używa wyrażeń regularnych, ale zamiast tego własne konstrukcje dopasowywania wzorców.

Wyrażenia regularne weszły do ​​powszechnego użytku od 1968 roku w dwóch zastosowaniach: dopasowywanie wzorców w edytorze tekstu i analiza leksykalna w kompilatorze. Jednym z pierwszych pojawień się wyrażeń regularnych w formie programu był fakt, że Ken Thompson wbudował notację Kleene do edytora QED jako sposób dopasowywania wzorców w plikach tekstowych . Aby przyspieszyć, firma Thompson zaimplementowała dopasowywanie wyrażeń regularnych przez kompilację just -in-time (JIT) do kodu IBM 7094 w zgodnym systemie podziału czasu , co jest ważnym wczesnym przykładem kompilacji JIT. Później dodał tę funkcję do edytora uniksowego ed , co ostatecznie doprowadziło do tego, że popularne narzędzie wyszukiwania grep używa wyrażeń regularnych („grep” to słowo pochodzące z polecenia wyszukiwania wyrażeń regularnych w edytorze ed: co oznacza „Globalne wyszukiwanie dla linii wyrażenia regularnego i dopasowania do druku”). Mniej więcej w tym samym czasie, gdy Thompson opracował QED, grupa badaczy, w tym Douglas T. Ross, wdrożyła narzędzie oparte na wyrażeniach regularnych, które jest używane do analizy leksykalnej w projektowaniu kompilatorów . g/re/p

Wiele odmian tych oryginalnych form wyrażeń regularnych było używanych w programach uniksowych w Bell Labs w latach 70., w tym vi , lex , sed , AWK i expr , a także w innych programach, takich jak Emacs . Regexes zostały następnie przyjęte przez szeroką gamę programów, przy czym te wczesne formy zostały ujednolicone w standardzie POSIX.2 w 1992 roku.

W latach 80. w Perlu pojawiły się bardziej skomplikowane wyrażenia regularne, które pierwotnie wywodziły się z biblioteki wyrażeń regularnych napisanej przez Henry'ego Spencera (1986), który później napisał implementację Zaawansowanych Wyrażeń Regularnych dla Tcl . Biblioteka Tcl to hybrydowa implementacja NFA / DFA o ulepszonej charakterystyce wydajności. Projekty oprogramowania, które przyjęły implementację wyrażeń regularnych Tcl Spencera, obejmują PostgreSQL . Perl później rozszerzył oryginalną bibliotekę Spencera, aby dodać wiele nowych funkcji. Częścią wysiłku w projektowaniu Raku (dawniej Perl 6) jest poprawa integracji wyrażeń regularnych Perla oraz zwiększenie ich zakresu i możliwości, aby umożliwić definicję parsowania gramatyki wyrażeń . Rezultatem jest mini-język o nazwie Raku rules , który służy do definiowania gramatyki Raku, a także stanowi narzędzie dla programistów w tym języku. Reguły te zachowują istniejące cechy wyrażeń regularnych Perla 5.x, ale także pozwalają na definicję rekurencyjnego parsera zstępującego w stylu BNF za pomocą reguł podrzędnych.

Stosowanie wyrażeń regularnych w ustrukturyzowanych standardach informacji do modelowania dokumentów i baz danych rozpoczęło się w latach 60. XX wieku i rozszerzyło się w latach 80., kiedy skonsolidowano standardy branżowe, takie jak ISO SGML (poprzedzone przez ANSI „GCA 101-1983”). Jądro standardów języka specyfikacji struktury składa się z wyrażeń regularnych. Jego użycie jest widoczne w składni grupy elementów DTD .

Począwszy od 1997, Philip Hazel opracował PCRE (Perl Compatible Regular Expressions), który stara się naśladować funkcjonalność wyrażeń regularnych Perla i jest używany przez wiele nowoczesnych narzędzi, w tym PHP i Apache HTTP Server .

Obecnie wyrażenia regularne są szeroko obsługiwane w językach programowania, programach do przetwarzania tekstu (w szczególności lexers ), zaawansowanych edytorach tekstu i niektórych innych programach. Obsługa Regex jest częścią standardowej biblioteki wielu języków programowania, w tym Java i Python , i jest wbudowana w składnię innych, w tym Perl i ECMAScript . Implementacje funkcjonalności regex są często nazywane silnikiem regex , a wiele bibliotek jest dostępnych do ponownego wykorzystania. Pod koniec 2010 roku kilka firm zaczęło oferować implementacje sprzętowe, FPGA , GPU silników regex kompatybilnych z PCRE , które są szybsze w porównaniu do implementacji CPU .

Wzory

Fraza wyrażenia regularne lub regexes jest często używana w celu oznaczenia określonej, standardowej składni tekstowej do przedstawiania wzorców dopasowywania tekstu, w odróżnieniu od notacji matematycznej opisanej poniżej. Każdy znak w wyrażeniu regularnym (czyli każdy znak w ciągu opisującym jego wzorzec) jest albo metaznakiem o znaczeniu specjalnym, albo znakiem regularnym o znaczeniu dosłownym. Na przykład w regexie b.„b” to znak dosłowny, który pasuje tylko do „b”, a „.” to metaznak, który pasuje do każdego znaku z wyjątkiem nowej linii. Dlatego to wyrażenie regularne pasuje na przykład do „b%”, „bx” lub „b5”. Łącznie metaznaki i znaki dosłowne mogą służyć do identyfikowania tekstu danego wzorca lub przetwarzania wielu jego wystąpień. Dopasowania wzorców mogą się różnić od dokładnej równości do bardzo ogólnego podobieństwa, kontrolowanego przez metaznaki. Na przykład .jest bardzo ogólnym wzorcem [a-z](dopasuj wszystkie małe litery od „a” do „z”) jest mniej ogólny i bjest precyzyjnym wzorcem (dopasowuje tylko „b”). Składnia metaznaków została zaprojektowana specjalnie do przedstawiania wyznaczonych celów w zwięzły i elastyczny sposób, aby kierować automatyzacją przetwarzania tekstu różnych danych wejściowych w formie łatwej do wpisania przy użyciu standardowej klawiatury ASCII .

Bardzo prostym przypadkiem wyrażenia regularnego w tej składni jest zlokalizowanie słowa pisanego na dwa różne sposoby w edytorze tekstu , wyrażenie regularne seriali[sz]epasuje zarówno do "serializacji" i "serializacji". Znaki wieloznaczne również to osiągają, ale są bardziej ograniczone pod względem wzorców, ponieważ mają mniej metaznaków i prostą bazę językową.

Typowym kontekstem symboli wieloznacznych jest umieszczanie podobnych nazw na liście plików, podczas gdy wyrażenia regularne są zwykle używane w aplikacjach, które ogólnie dopasowują ciągi tekstowe do wzorca. Na przykład wyrażenie regularne dopasowuje nadmiar białych znaków na początku lub na końcu wiersza. Zaawansowanym wyrażeniem regularnym pasującym do dowolnej liczby jest . ^[ \t]+|[ \t]+$[+-]?(\d+(\.\d+)?|\.\d+)([eE][+-]?\d+)?

Tłumaczenia na gwiazdę Kleene
( s * oznacza „zero lub więcej s ”)

Procesor regex przekłada regularny ekspresję powyższych parametrów do wewnętrznej reprezentacji, które mogą być wykonane i dopasowane na sznurkiem reprezentujący istota tekst przeszukiwane. Możliwa jest także algorytmu konstrukcji Thompsona skonstruować niedeterministycznych skończonego automatu (NFA), który jest następnie deterministyczny, a wynikowy deterministyczny automat skończony (DFA) jest uruchamiany na docelowym ciągu tekstowym w celu rozpoznania podciągów pasujących do wyrażenia regularnego. Rysunek przedstawia schemat NAS uzyskany z wyrażenia regularnego , gdzie s oznacza z kolei prostsze wyrażenie regularne, które zostało już rekurencyjnie przetłumaczone na N ( s ) NAS . N(s*)s*

Podstawowe koncepcje

Wyrażenie regularne, często nazywane wzorcem , określa zestaw ciągów znaków wymaganych do określonego celu. Prostym sposobem określenia skończonego zestawu łańcuchów jest wymienienie jego elementów lub elementów. Jednak często istnieją bardziej zwięzłe sposoby: na przykład zestaw zawierający trzy ciągi „Handel”, „Händel” i „Haendel” można określić za pomocą wzorca H(ä|ae?)ndel; mówimy, że ten wzór pasuje do każdego z trzech ciągów. W większości formalizmów , jeśli istnieje co najmniej jedno wyrażenie regularne, które pasuje do określonego zestawu, to istnieje nieskończona liczba innych wyrażeń regularnych, które również do niego pasują — specyfikacja nie jest unikalna. Większość formalizmów zapewnia następujące operacje do konstruowania wyrażeń regularnych.

Boole'owskie „lub”
Pionowy pasek oddziela alternatywy. Na przykład można dopasować „szary” lub „szary”.gray|grey
Grupowanie
Nawiasy służą do określenia zakresu i pierwszeństwa operatorów (między innymi). Na przykład gray|greyi są równoważnymi wzorami, które opisują zestaw "szary" lub "szary".gr(a|e)y
Ujęcie ilościowe
Kwantyfikator po tokena (takie jak znak) lub grupa określa jak często, że poprzedzający element jest dozwolone wystąpić. Najczęstszymi kwantyfikatorami są znak zapytania ? , gwiazdka * (pochodząca z gwiazdy Kleene ) i znak plus + ( Kleene plus ).
? Znak zapytania wskazuje zero lub jedno wystąpienie poprzedniego elementu. Na przykład colou?rdopasowuje zarówno „kolor”, jak i „kolor”.
* Gwiazdka wskazuje zero lub więcej wystąpień poprzedniego elementu. Na przykład ab*cpasuje do „ac”, „abc”, „abbc”, „abbbc” itd.
+ Znak plus wskazuje co najmniej jedno wystąpienie poprzedniego elementu. Na przykład ab+cpasuje do „abc”, „abbc”, „abbbc” itd., ale nie do „ac”.
{n} Poprzedni element jest dopasowywany dokładnie n razy.
{min,} Poprzedni element jest dopasowywany min lub więcej razy.
{,max} Poprzedni element jest dopasowywany maksymalnie razy.
{min,max} Poprzedni element jest dopasowany co najmniej min razy, ale nie więcej niż max razy.
Dzika karta

Symbol wieloznaczny .pasuje do dowolnego znaku. Na przykład a.bdopasowuje dowolny ciąg, który zawiera „a”, następnie dowolny inny znak, a następnie „b”, a.*bdopasowuje dowolny ciąg zawierający „a”, a następnie znak „b” w pewnym późniejszym momencie.

Konstrukcje te można łączyć, tworząc dowolnie złożone wyrażenia, podobnie jak można konstruować wyrażenia arytmetyczne z liczb i operacji +, −, × i ÷. Na przykład H(ae?|ä)ndeli oba są prawidłowymi wzorcami, które pasują do tych samych ciągów, co we wcześniejszym przykładzie, . H(a|ae|ä)ndelH(ä|ae?)ndel

Dokładna składnia wyrażeń regularnych różni się w zależności od narzędzi i kontekstu; więcej szczegółów podano w § Składnia .

Formalna teoria języka

Wyrażenia regularne opisują języki regularne w teorii języka formalnego . Mają taką samą siłę wyrazu jak zwykłe gramatyki .

Formalna definicja

Wyrażenia regularne składają się ze stałych, które oznaczają zestawy ciągów i symboli operatorów, które oznaczają operacje na tych zestawach. Poniższa definicja jest standardowa i jako taka znajduje się w większości podręczników teorii języka formalnego. Mając skończony alfabet Σ, następujące stałe są definiowane jako wyrażenia regularne:

  • ( zestaw pusty ) ∅ oznaczający zestaw ∅.
  • ( pusty ciąg ) ε oznaczający zestaw zawierający tylko „pusty” ciąg, który nie zawiera żadnych znaków.
  • ( znak dosłowny ) aw Σ oznaczający zbiór zawierający tylko znak a .

Biorąc pod uwagę wyrażenia regularne R i S, następujące operacje na nich są zdefiniowane w celu utworzenia wyrażeń regularnych:

  • ( konkatenacja ) (RS)oznacza zbiór łańcuchów, które można uzyskać, łącząc łańcuch zaakceptowany przez R i łańcuch zaakceptowany przez S (w tej kolejności). Na przykład niech R oznacza {"ab", "c"}, a S oznacza {"d", "ef"}. Następnie (RS)oznacza {"abd", "abef", "cd", "cef"}.
  • ( alternacja ) (R|S)oznacza sumę zbiorów opisanych przez R i S. Na przykład, jeśli R opisuje {"ab", "c"}, a S opisuje {"ab", "d", "ef"}, wyrażenie (R|S)opisuje { "Alfabet"}.
  • ( Gwiazda Kleene ) (R*)oznacza najmniejszy nadzbiór zbioru opisanego przez R, który zawiera ε i jest zamknięty w ramach konkatenacji łańcuchów. Jest to zbiór wszystkich łańcuchów, które można utworzyć przez połączenie dowolnej skończonej liczby (włącznie z zerem) łańcuchów ze zbioru opisanego przez R. Na przykład, jeśli R oznacza {"0", "1"}, (R*)oznacza zbiór wszystkich skończone ciągi binarne (w tym ciąg pusty). Jeśli R oznacza {"ab", "c"}, (R*)oznacza {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", . ..}.

Aby uniknąć nawiasów, zakłada się, że gwiazda Kleene ma najwyższy priorytet, następnie konkatenację, a następnie alternację. Jeśli nie ma niejasności, nawiasy można pominąć. Na przykład (ab)cmoże być zapisany jako abc, i a|(b(c*))może być zapisany jako a|bc*. Wiele podręczników używa symboli ∪, + lub ∨ zamiast pionowej kreski.

Przykłady:

  • a|b* oznacza {ε, "a", "b", "bb", "bbb", ...}
  • (a|b)* oznacza zbiór wszystkich ciągów bez symboli innych niż „a” i „b”, w tym pusty ciąg: {ε, „a”, „b”, „aa”, „ab”, „ba”, „bb” , "aaa", ...}
  • ab*(c|ε) oznacza zestaw ciągów zaczynających się od "a", następnie zero lub więcej "b" i na końcu opcjonalnie "c": {"a", "ac", "ab", "abc", "abb", "abbc ", ...}
  • (0|(1(01*0)*1))* oznacza zbiór liczb binarnych będących wielokrotnościami 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110" , "1001", "1100", "1111", "00000", ... }

Ekspresyjna moc i kompaktowość

Formalna definicja wyrażeń regularnych jest celowo minimalna i unika się definiowania ?oraz — +można je wyrazić w następujący sposób: a+= aa*i a?= (a|ε). Czasami dodawany jest operator dopełnienia , aby uzyskać uogólnione wyrażenie regularne ; tutaj R c dopasowuje wszystkie łańcuchy powyżej Σ*, które nie pasują do R . W zasadzie operator dopełnienia jest zbędny, ponieważ nie daje żadnej większej mocy wyrazu. Może jednak sprawić, że wyrażenie regularne będzie bardziej zwięzłe — wyeliminowanie pojedynczego operatora dopełnienia może spowodować podwójne wykładnicze powiększenie jego długości.

Wyrażenia regularne w tym sensie mogą wyrażać języki regularne, dokładnie taką klasę języków akceptowaną przez deterministyczne automaty skończone . Istnieje jednak znacząca różnica w zwartości. Niektóre klasy języków regularnych mogą być opisane tylko przez deterministyczne automaty skończone, których rozmiar rośnie wykładniczo wraz z rozmiarem najkrótszego równoważnego wyrażenia regularnego. Standardowym przykładem są tutaj języki L k składające się ze wszystkich łańcuchów w alfabecie { a , b } , których k- ta -od-ostatnia litera jest równa  a . Z jednej strony wyrażenie regularne opisujące L 4 jest dane przez .

Uogólnienie tego wzoru na L k daje wyrażenie:

Z drugiej strony, wiadomo, że każdy deterministyczny automat skończony przyjmując język L k musi mieć co najmniej 2 tys stany. Na szczęście istnieje proste mapowanie z wyrażeń regularnych do bardziej ogólnych niedeterministycznych automatów skończonych (NFA), które nie prowadzą do takiego powiększenia; z tego powodu NFA są często używane jako alternatywne reprezentacje języków regularnych. NFAs są odmianą prosty typu, 3 gramatyk z hierarchii Chomsky'ego .

W przeciwnym kierunku istnieje wiele języków, które można łatwo opisać za pomocą DFA, których nie da się łatwo opisać wyrażeniem regularnym. Na przykład określenie ważności danego numeru ISBN wymaga obliczenia modułu liczby całkowitej o podstawie 11 i może być łatwo zaimplementowane za pomocą 11-stanowego DFA. Jednak wyrażenie regularne odpowiadające na ten sam problem podzielności przez 11 ma długość co najmniej wielu megabajtów.

Mając wyrażenie regularne, algorytm konstrukcji Thompsona oblicza równoważny niedeterministyczny automat skończony. Konwersję w przeciwnym kierunku osiąga algorytm Kleene'a .

Na koniec warto zauważyć, że wiele rzeczywistych silników „wyrażeń regularnych” implementuje funkcje, których nie można opisać za pomocą wyrażeń regularnych w sensie teorii języka formalnego; raczej implementują wyrażenia regularne . Więcej informacji na ten temat znajdziesz poniżej .

Decydowanie o równoważności wyrażeń regularnych

Jak widać w wielu powyższych przykładach, istnieje więcej niż jeden sposób skonstruowania wyrażenia regularnego, aby osiągnąć te same wyniki.

Można napisać algorytm, który dla dwóch danych wyrażeń regularnych rozstrzyga, czy opisane języki są równe; algorytm redukuje każde wyrażenie do minimalnej deterministycznej maszyny stanów skończonych i określa, czy są one izomorficzne (równoważne).

Prawa algebraiczne dla wyrażeń regularnych można uzyskać za pomocą metody Gischera, którą najlepiej wyjaśniono na przykładzie: Aby sprawdzić, czy ( X + Y ) * i ( X * Y * ) * oznaczają ten sam język regularny, dla wszystkich wyrażeń regularnych X , Y , konieczne i wystarczające jest sprawdzenie, czy poszczególne wyrażenia regularne ( a + b ) * i ( a * b * ) * oznaczają ten sam język nad alfabetem Σ={ a , b }. Mówiąc bardziej ogólnie, równanie E = F między wyrażeniami regularnymi ze zmiennymi zachodzi wtedy i tylko wtedy, gdy jego wystąpienie z różnymi zmiennymi zastąpionymi różnymi stałymi symboli jest słuszne.

Redundancja może być wyeliminowana przez użycie Kleene star and set union w celu znalezienia interesującego podzbioru wyrażeń regularnych, który nadal jest w pełni ekspresyjny, ale być może ich użycie może zostać ograniczone. To zaskakująco trudny problem. Tak proste, jak wyrażenia regularne, nie ma metody systematycznego przepisywania ich do jakiejś normalnej postaci. Brak aksjomatu w przeszłości doprowadził do problemu z wysokością gwiazdy . W 1991 roku Dexter Kozen dokonał aksjomatyzacji wyrażeń regularnych jako algebry Kleene'a , używając aksjomatów równania i klauzuli Horna . Już w 1964 Redko udowodnił, że żaden skończony zbiór czysto równań aksjomatów nie może scharakteryzować algebry języków regularnych.

Składnia

Wzorzec wyrażenia regularnego pasuje do ciągu docelowego . Wzór składa się z sekwencji atomów . Atom to pojedynczy punkt we wzorcu wyrażenia regularnego, który próbuje dopasować do docelowego ciągu. Najprostszym atomem jest literał, ale grupowanie części wzorca w celu dopasowania do atomu będzie wymagało użycia ( )metaznaków. Metaznaki pomagają tworzyć: atomy ; kwantyfikatory mówiące, ile atomów (i czy jest to kwantyfikator zachłanny, czy nie); logiczny znak OR, który oferuje zestaw alternatyw, oraz logiczny znak NIE, który neguje istnienie atomu; i odniesienia wsteczne, aby odnieść się do poprzednich atomów kompletnego wzorca atomów. Dopasowanie jest dokonywane nie wtedy, gdy wszystkie atomy łańcucha są dopasowane, ale gdy wszystkie atomy wzorca w wyrażeniu regularnym pasują. Pomysł polega na tym, aby mały wzorzec znaków oznaczał dużą liczbę możliwych ciągów, zamiast kompilowania dużej listy wszystkich dosłownych możliwości.

W zależności od procesora wyrażeń regularnych istnieje około czternastu metaznaków, znaków, które mogą lub nie mogą mieć swoje dosłowne znaczenie, w zależności od kontekstu lub tego, czy są one "zapisane", tj. poprzedzone sekwencją specjalną , w tym przypadku ukośnikiem odwrotnym \. Rozszerzone wyrażenia regularne nowoczesne i POSIX używają metaznaków częściej niż ich dosłowne znaczenie, więc aby uniknąć „odwrotnego ukośnika” lub syndromu pochylonej wykałaczki , sensowne jest uciekanie metaznaków do trybu dosłownego; ale wychodząc na zewnątrz, to ma większy sens mieć cztery Bracketing metaznaki ( )i { }być przede wszystkim dosłowny i „Escape” to zwykłe znaczenie stania metaznakami. Wspólne standardy wdrażają oba. Zwykłe metaznaki to {}[]()^$.|*+?i \. Zwykłe znaki, które stają się metaznakami po ucieczce, to dswDSWi N.

Ograniczniki

Wprowadzając wyrażenie regularne w języku programowania, mogą one być reprezentowane jako zwykły literał łańcuchowy, stąd zwykle cytowane; jest to powszechne na przykład w C, Javie i Pythonie, gdzie wyrażenie regularne rejest wprowadzane jako "re". Jednak często są one pisane z ukośnikami jako ogranicznikami , jak w /re/przypadku wyrażenia regularnego re. Pochodzi z ed , gdzie /jest poleceniem edytora do wyszukiwania, a wyrażenie /re/może być użyte do określenia zakresu linii (pasujących do wzorca), które można łączyć z innymi poleceniami po obu stronach, najbardziej znanym g/re/pjak w grep ("global regex print"), który jest zawarty w większości systemów operacyjnych opartych na systemie Unix , takich jak dystrybucje Linuksa . Podobna konwencja stosowana jest w sed , gdzie wyszukiwanie i zamiana jest podane przez , s/re/replacement/a wzorce można łączyć przecinkami w celu określenia zakresu linii, jak w /re1/,/re2/. Ta notacja jest szczególnie dobrze znana ze względu na jej użycie w Perl , gdzie stanowi część składni odrębnej od normalnych literałów łańcuchowych. W niektórych przypadkach, takich jak sed i Perl, można użyć alternatywnych ograniczników, aby uniknąć kolizji z zawartością i uniknąć konieczności unikania występowania znaku ogranicznika w zawartości. Na przykład, w sed polecenie s,/,X,zastąpi /ze związkiem X, stosując jako ograniczniki przecinkami.

Normy

Standard IEEE POSIX ma trzy zestawy zgodności: BRE (podstawowe wyrażenia regularne), ERE (rozszerzone wyrażenia regularne) i SRE (proste wyrażenia regularne). SRE jest przestarzały na rzecz BRE, ponieważ oba zapewniają kompatybilność wsteczną . Poniższy podrozdział dotyczący klas znaków dotyczy zarówno BRE, jak i ERE.

BRE i ERE współpracują. ERE dodaje ?, +, i |, i usuwa konieczność zmiany znaczenia metaznaków ( )i { }, które są wymagane w BRE. Ponadto, o ile przestrzegana jest standardowa składnia POSIX dla wyrażeń regularnych, może istnieć i często jest dodatkowa składnia do obsługi określonych (jednak zgodnych z POSIX) aplikacji. Chociaż POSIX.2 pozostawia pewne szczegóły implementacji niezdefiniowane, BRE i ERE zapewniają "standard", który został przyjęty jako domyślna składnia wielu narzędzi, gdzie wybór trybów BRE lub ERE jest zwykle obsługiwaną opcją. Na przykład, GNU grep ma następujące opcje: " grep -E" dla ERE i " grep -G" dla BRE (domyślnie) i " grep -P" dla wyrażeń regularnych Perla .

Wyrażenia regularne Perla stały się de facto standardem, posiadającym bogaty i potężny zestaw wyrażeń atomowych. Perl nie ma poziomów „podstawowych” ani „rozszerzonych”. Tak jak w POSIX ERE, ( )i { }są traktowane jako metaznaki, chyba że są zmienione; wiadomo, że inne metaznaki są dosłowne lub symboliczne, oparte wyłącznie na kontekście. Dodatkowe funkcje obejmują dopasowywanie z opóźnieniem , odwołania wsteczne , nazwane grupy przechwytywania i wzorce rekurencyjne .

POSIX podstawowy i rozszerzony

W standardzie POSIX podstawowa regularna składnia ( BRE ) wymaga, aby metaznaki ( ) i { }były oznaczone \(\)i \{\}, podczas gdy rozszerzona regularna składnia ( ERE ) nie.

Metaznak Opis
^ Dopasowuje pozycję początkową w ciągu. W narzędziach opartych na liniach dopasowuje pozycję początkową dowolnej linii.
. Dopasowuje dowolny pojedynczy znak (wiele aplikacji wyklucza znaki nowej linii , a dokładnie to, które znaki są uważane za nowe linie, zależy od smaku, kodowania znaków i platformy, ale można bezpiecznie założyć, że dołączony jest znak nowego wiersza). W wyrażeniach nawiasów klamrowych POSIX znak kropki pasuje do kropki literału. Na przykład a.cpasuje do „abc” itp., ale [a.c]pasuje tylko do „a”, „.” lub „c”.
[ ] Wyrażenie w nawiasie. Dopasowuje pojedynczy znak zawarty w nawiasach. Na przykład [abc]pasuje do „a”, „b” lub „c”. [a-z]określa zakres, który pasuje do dowolnej małej litery od „a” do „z”. Te formy mogą być mieszane: [abcx-z]pasuje do „a”, „b”, „c”, „x”, „y” lub „z”, podobnie jak [a-cx-z].

-Znak jest traktowany jako dosłowny charakter jeśli jest to ostatni lub pierwszy (po ^, jeśli jest obecny) znak w nawiasach: [abc-], [-abc]. Pamiętaj, że znaki ucieczki odwrotnym ukośnikiem są niedozwolone. ]Postać może być zawarte w wyrażeniu wspornika jeśli jest to pierwszy (po ^) znak: []abc].

[^ ] Dopasowuje pojedynczy znak, który nie jest zawarty w nawiasach. Na przykład [^abc]dopasowuje dowolny znak inny niż „a”, „b” lub „c”. [^a-z]dopasowuje dowolny pojedynczy znak, który nie jest małą literą od „a” do „z”. Podobnie można mieszać dosłowne znaki i zakresy.
$ Dopasowuje końcową pozycję ciągu lub pozycję tuż przed kończącym ciąg znakiem nowej linii. W narzędziach opartych na liniach dopasowuje pozycję końcową dowolnej linii.
( ) Definiuje zaznaczone podwyrażenie. Ciąg dopasowany w nawiasach można później przywołać (patrz następny wpis, ). Zaznaczone podwyrażenie jest również nazywane blokiem lub grupą przechwytywania. Tryb BRE wymaga . \n\( \)
\n Dopasowuje to, co pasowało n- te oznaczone podwyrażenie, gdzie n jest cyfrą od 1 do 9. Ta konstrukcja jest niejasno zdefiniowana w standardzie POSIX.2. Niektóre narzędzia umożliwiają odwoływanie się do więcej niż dziewięciu grup przechwytywania. Znany również jako odwołanie wsteczne.
* Dopasowuje poprzedni element zero lub więcej razy. Na przykład ab*cpasuje do „ac”, „abc”, „abbbc” itd. [xyz]*pasuje do „”, „x”, „y”, „z”, „zx”, „zyx”, „xyzzy” itd. (ab)*pasuje do „”, „ab”, „abab”, „ababab” i tak dalej.
{m,n} Dopasowuje poprzedni element co najmniej mi nie więcej niż n razy. Na przykład a{3,5}dopasowuje tylko „aaa”, „aaaa” i „aaaaa”. Nie występuje to w kilku starszych wystąpieniach wyrażeń regularnych. Tryb BRE wymaga\{m,n\} .

Przykłady:

  • .at dopasowuje dowolny trzyznakowy ciąg kończący się na "at", w tym "kapelusz", "kot" i "nietoperz".
  • [hc]at pasuje do "kapelusz" i "kot".
  • [^b]atdopasowuje wszystkie pasujące łańcuchy z .atwyjątkiem „bat”.
  • [^hc]atdopasowuje wszystkie ciągi dopasowane przez .atinne niż „kapelusz” i „kot”.
  • ^[hc]at pasuje do "kapelusz" i "kot", ale tylko na początku ciągu lub linii.
  • [hc]at$ pasuje do "kapelusz" i "kot", ale tylko na końcu ciągu lub linii.
  • \[.\] pasuje do dowolnego pojedynczego znaku otoczonego „[” i „]”, ponieważ nawiasy są pominięte, na przykład: „[a]” i „[b]”.
  • s.* dopasowuje s, po którym następuje zero lub więcej znaków, na przykład: „s” i „saw” i „seed”.

Rozszerzenie POSIX

Znaczenie metaznakami uciekł z backslash jest odwrócony do niektórych znaków w rozszerzonych wyrażeń regularnych POSIX ( ERE składni). W tej składni ukośnik odwrotny powoduje, że metaznak jest traktowany jako znak dosłowny. Na przykład \( \)jest teraz ( )i \{ \}jest teraz { }. Ponadto usunięto obsługę odwołań wstecznych i dodano następujące metaznaki: \n

Metaznak Opis
? Dopasowuje poprzedni element zero lub jeden raz. Na przykład ab?cdopasowuje tylko „ac” lub „abc”.
+ Dopasowuje poprzedni element raz lub więcej razy. Na przykład ab+cpasuje do „abc”, „abbc”, „abbbc” itd., ale nie do „ac”.
| Operator wyboru (znany również jako alternation lub set union) pasuje do wyrażenia przed operatorem lub wyrażenia po operatorze. Na przykład abc|defdopasowuje „abc” lub „def”.

Przykłady:

  • [hc]?at pasuje do "at", "kapelusz" i "kot".
  • [hc]*at pasuje do „at”, „hat”, „cat”, „hhat”, „chat”, „hcat”, „cchchat” i tak dalej.
  • [hc]+at pasuje do „hat”, „cat”, „hhat”, „chat”, „hcat”, „cchchat” itd., ale nie do „at”.
  • cat|dog pasuje do „kot” lub „pies”.

Rozszerzone wyrażenia regularne POSIX mogą być często używane z nowoczesnymi narzędziami uniksowymi, dołączając flagę wiersza poleceń -E .

Klasy postaci

Klasa znaków jest najbardziej podstawowym pojęciem wyrażeń regularnych po dosłownym dopasowaniu. Sprawia, że ​​jedna mała sekwencja znaków pasuje do większego zestawu znaków. Na przykład może oznaczać dowolną wielką literę alfabetu angielskiego i może oznaczać dowolną cyfrę. Klasy znaków dotyczą obu poziomów POSIX. [A-Z]\d

Podczas określania zakresu znaków, na przykład (np. od małych do wielkich ), ustawienia regionalne komputera określają zawartość na podstawie kolejności numerycznej kodowania znaków. Mogą przechowywać cyfry w tej kolejności lub kolejność może być abc…zABC…Z lub aAbBcC…zZ . Tak więc standard POSIX definiuje klasę znaków, która będzie znana przez zainstalowany procesor wyrażeń regularnych. Definicje te znajdują się w poniższej tabeli: [a-Z]aZ

POSIX Niestandardowe Perl/Tcl Krzepkość Jawa ASCII Opis
[:ascii:] \p{ASCII} [\x00-\x7F] Znaki ASCII
[:alnum:] \p{Alnum} [A-Za-z0-9] Znaki alfanumeryczne
[:word:] \w \w \w [A-Za-z0-9_] Znaki alfanumeryczne plus „_”
\W \W \W [^A-Za-z0-9_] Znaki niebędące słowami
[:alpha:] \a \p{Alpha} [A-Za-z] Znaki alfabetyczne
[:blank:] \s \p{Blank} [ \t] Spacja i tabulator
\b \< \> \b (?<=\W)(?=\w)|(?<=\w)(?=\W) Granice słów
\B (?<=\W)(?=\W)|(?<=\w)(?=\w) Granice niebędące słowami
[:cntrl:] \p{Cntrl} [\x00-\x1F\x7F] Postacie kontrolne
[:digit:] \d \d \p{Digit} lub \d [0-9] Cyfry
\D \D \D [^0-9] Niecyfry
[:graph:] \p{Graph} [\x21-\x7E] Widoczne postacie
[:lower:] \l \p{Lower} [a-z] Małe litery
[:print:] \p \p{Print} [\x20-\x7E] Widoczne znaki i znak spacji
[:punct:] \p{Punct} [][!"#$%&'()*+,./:;<=>?@\^_`{|}~-] Znaki interpunkcyjne
[:space:] \s \_s \p{Space} lub \s [ \t\r\n\v\f] Białe znaki
\S \S \S [^ \t\r\n\v\f] Znaki inne niż białe znaki
[:upper:] \u \p{Upper} [A-Z] Wielkie litery
[:xdigit:] \x \p{XDigit} [A-Fa-f0-9] Cyfry szesnastkowe

Klasy znaków POSIX mogą być używane tylko w wyrażeniach nawiasów. Na przykład dopasowuje wielkie litery i małe litery „a” i „b”. [[:upper:]ab]

Dodatkową klasą nie POSIX rozumianą przez niektóre narzędzia jest , który jest zwykle definiowany jako plus podkreślenie. Odzwierciedla to fakt, że w wielu językach programowania są to znaki, które mogą być używane w identyfikatorach. Edytor Vim dodatkowo rozróżnia klasy word i word-head (za pomocą notacji i ), ponieważ w wielu językach programowania znaki, które mogą rozpoczynać identyfikator, nie są takie same, jak te, które mogą występować w innych pozycjach: liczby są generalnie wykluczone, więc identyfikator wyglądałby jak lub w notacji POSIX. [:word:][:alnum:]\w\h\h\w*[[:alpha:]_][[:alnum:]_]*

Zauważ, że to, co standardy POSIX nazywają klasami znaków, są powszechnie określane jako klasy znaków POSIX w innych odmianach wyrażeń regularnych, które je obsługują. W większości innych odmian wyrażeń regularnych termin klasa znaków jest używany do opisania tego, co POSIX nazywa wyrażeniami nawiasów .

Perl i PCRE

Ze względu na jego siłę wyrazu i (względną) łatwość czytania, wiele innych narzędzi i języków programowania przyjęło składnię podobną do składni Perla — na przykład Java , JavaScript , Julia , Python , Ruby , Qt , Microsoft .NET Framework i XML Schemat . Niektóre języki i narzędzia, takie jak Boost i PHP, obsługują wiele smaków wyrażeń regularnych. Implementacje wyrażeń regularnych pochodnych Perla nie są identyczne i zwykle implementują podzbiór funkcji znalezionych w Perlu 5.0, wydanym w 1994 roku. Perl czasami zawiera funkcje pierwotnie znalezione w innych językach. Na przykład Perl 5.10 implementuje rozszerzenia składniowe pierwotnie opracowane w PCRE i Pythonie.

Leniwe dopasowanie

W Pythonie oraz niektórych innych implementacjach (np Java), trzy (wspólne kwantyfikatory *, +i ?) są chciwi domyślnie, ponieważ odpowiadają one za wiele znaków jak to możliwe. Wyrażenie regularne ".+"(w tym podwójne cudzysłowy) zastosowane do łańcucha

"Ganymede," he continued, "is the largest moon in the Solar System."

dopasowuje cały wiersz (ponieważ cały wiersz zaczyna się i kończy podwójnym cudzysłowem), zamiast dopasowywać tylko pierwszą część, "Ganymede,". Powyższe kwantyfikatory można jednak uczynić leniwymi lub minimalnymi lub niechętnymi , dopasowując jak najmniej znaków, dodając znak zapytania: ".+?"tylko pasuje "Ganymede,".

Jednak w niektórych okolicznościach całe zdanie może być dopasowane. Operator znaku zapytania nie zmienia znaczenia operatora kropki, więc nadal może pasować do podwójnych cudzysłowów w danych wejściowych. Wzorzec taki jak ".*?" EOFnadal będzie pasował do całego wejścia, jeśli jest to łańcuch:

"Ganymede," he continued, "is the largest moon in the Solar System." EOF

Aby zapewnić, że podwójne cudzysłowy nie będą częścią dopasowania, należy zastąpić kropkę (np "[^"]*". ). Spowoduje to dopasowanie cytowanej części tekstu bez dodatkowych cudzysłowów. (Usuwając możliwość dopasowania stałego przyrostka, tj. ", zmieniło to również dopasowanie leniwe w dopasowanie zachłanne, więc ?nie jest już potrzebne.)

Dopasowanie zaborcze

W Javie kwantyfikatory można uczynić zaborczymi przez dodanie znaku plus, który wyłącza wycofywanie się (w silniku z wycofywaniem), nawet jeśli pozwoliłoby to na powodzenie ogólnego dopasowania: Podczas gdy wyrażenie regularne ".*"zastosowane do łańcucha

"Ganymede," he continued, "is the largest moon in the Solar System."

pasuje do całej linii, regex ".*+"ma nie pasuje w ogóle , ponieważ .*+zużywa cały wkład, w tym finale ". Tak więc kwantyfikatory dzierżawcze są najbardziej przydatne w przypadku zanegowanych klas znaków, np. "[^"]*+", który pasuje "Ganymede,"po zastosowaniu do tego samego łańcucha.

Innym powszechnym rozszerzeniem spełniającym tę samą funkcję jest grupowanie atomowe, które wyłącza cofanie się dla grupy w nawiasach. Typowa składnia to (?>group) . Na przykład, podczas gdy ^(wi|w)i$ pasuje zarówno do wi, jak i wii , ^(?>wi|w)i$ pasuje tylko do wii, ponieważ silnik nie może się cofać i spróbuj ustawić grupę jako "w".

Kwantyfikatory dzierżawcze są łatwiejsze do zaimplementowania niż kwantyfikatory zachłanne i leniwe i zazwyczaj są bardziej wydajne w czasie wykonywania.

Wzorce dla języków nieregularnych

Wiele funkcji, które można znaleźć w praktycznie wszystkich nowoczesnych bibliotekach wyrażeń regularnych, zapewnia ekspresyjną moc przewyższającą języki regularne . Na przykład wiele implementacji umożliwia grupowanie podwyrażeń w nawiasach i przywoływanie wartości, które pasują w tym samym wyrażeniu ( referencje wsteczne ). Oznacza to, między innymi, że wzorzec może pasować do ciągów powtarzających się słów, takich jak „tata” lub „WikiWiki”, zwanychkwadratamiw teorii języka formalnego. Wzorzec dla tych ciągów to(.+)\1.

Język kwadratów nie jest ani regularny, ani bezkontekstowy ze względu na lemat o pompowaniu . Jednak dopasowywanie wzorców z nieograniczoną liczbą odwołań wstecznych, obsługiwane przez wiele nowoczesnych narzędzi, jest nadal zależne od kontekstu . Ogólny problem dopasowania dowolnej liczby odwołań wstecznych jest NP-zupełny , rosnący wykładniczo wraz z liczbą użytych grup odwołań wstecznych.

Jednak wiele narzędzi, bibliotek i silników, które udostępniają takie konstrukcje, nadal używa terminu wyrażenie regularne dla swoich wzorców. Doprowadziło to do nomenklatury, w której termin wyrażenie regularne ma różne znaczenia w teorii języka formalnego i dopasowywaniu wzorców. Z tego powodu niektórzy ludzie zaczęli używać terminu regex , regexp , lub po prostu wzorca, aby opisać to drugie. Larry Wall , autor języka programowania Perl, pisze w eseju o projekcie Raku :

„Wyrażenia regularne” […] są tylko marginalnie związane z rzeczywistymi wyrażeniami regularnymi. Niemniej jednak termin ten urósł wraz z możliwościami naszych silników dopasowywania wzorców, więc nie zamierzam tutaj walczyć z językową koniecznością. Będę jednak generalnie nazywał je „regexes” (lub „regexen”, gdy jestem w nastroju anglosaskim).

Twierdzenie Spojrzeć za siebie Patrz przed siebie
Pozytywny (? <= wzór ) (? = wzór )
Negatywny (? <! wzór ) (? ! wzór )
Asercje wsteczne i wyprzedzające
w wyrażeniach regularnych Perla

Inne cechy, których nie można znaleźć w opisie języków regularnych, obejmują asercje. Należą do nich wszechobecne ^ i $ , a także niektóre bardziej wyrafinowane rozszerzenia, takie jak lookaround. Definiują otoczenie dopasowania i nie przenikają do samego dopasowania, co jest istotne tylko w przypadku użycia wyszukiwania ciągów. Niektóre z nich można symulować w zwykłym języku, traktując również otoczenie jako część języka.

Wdrożenia i czasy pracy

Istnieją co najmniej trzy różne algorytmy decydujące o tym, czy i jak dane wyrażenie regularne pasuje do ciągu.

Najstarszy i najszybszy opiera się na wyniku teorii języka formalnego, który pozwala na przekształcenie każdego niedeterministycznego automatu skończonego (NFA) w deterministyczny automat skończony (DFA). DFA można skonstruować jawnie, a następnie uruchomić na wynikowym ciągu wejściowym po jednym symbolu na raz. Konstruowanie DFA dla wyrażenia regularnego o rozmiarze m ma czas i koszt pamięci równy O (2 m ), ale można go uruchomić na łańcuchu o rozmiarze n w czasie O ( n ). Zauważ, że rozmiar wyrażenia to rozmiar po rozwinięciu skrótów, takich jak kwantyfikatory liczbowe.

Alternatywnym podejściem jest bezpośrednie symulowanie NAS, zasadniczo budowanie każdego stanu DFA na żądanie, a następnie odrzucanie go w następnym kroku. Dzięki temu DFA pozostaje niejawny i unika się wykładniczego kosztu budowy, ale koszt eksploatacji wzrasta do O ( mn ). Podejście jawne nazywa się algorytmem DFA, a podejście niejawne algorytmem NFA. Dodanie buforowania do algorytmu NFA jest często nazywane „leniwym algorytmem DFA” lub po prostu algorytmem DFA bez rozróżniania. Algorytmy te są szybkie, ale używanie ich do przywoływania zgrupowanych podwyrażeń, leniwej kwantyfikacji i podobnych funkcji jest trudne. Nowoczesne implementacje obejmują rodzinę re1-re2-sregex opartą na kodzie Coxa.

Trzeci algorytm polega na dopasowaniu wzorca do ciągu wejściowego przez wycofywanie . Ten algorytm jest powszechnie nazywany NFA, ale ta terminologia może być myląca. Jego czas działania może być wykładniczy, co wykazują proste implementacje podczas dopasowywania takich wyrażeń, które zawierają zarówno naprzemienną, jak i nieograniczoną kwantyfikację i zmuszają algorytm do rozważenia wykładniczo rosnącej liczby podprzypadków. To zachowanie może powodować problem z zabezpieczeniami o nazwie Odmowa usługi wyrażeń regularnych (ReDoS). (a|aa)*b

Chociaż implementacje z nawracaniem dają gwarancję wykładniczą tylko w najgorszym przypadku, zapewniają znacznie większą elastyczność i moc ekspresji. Na przykład każda implementacja, która pozwala na użycie odwołań wstecznych lub implementuje różne rozszerzenia wprowadzone przez Perla, musi zawierać jakiś rodzaj śledzenia wstecznego. Niektóre implementacje starają się zapewnić to, co najlepsze z obu algorytmów, najpierw uruchamiając szybki algorytm DFA, i powracają do potencjalnie wolniejszego algorytmu śledzenia wstecznego tylko wtedy, gdy podczas dopasowania zostanie napotkane odwołanie wsteczne. GNU grep (i bazowy DFA gnulib) używa takiej strategii.

Podliniowe algorytmy uruchomieniowe zostały osiągnięte przy użyciu algorytmów opartych na Boyer-Moore (BM) i powiązanych technik optymalizacji DFA, takich jak skanowanie wsteczne. GNU grep, który obsługuje szeroką gamę składni i rozszerzeń POSIX, używa BM do wstępnego filtrowania w pierwszym przebiegu, a następnie używa niejawnego DFA. Wu agrep , który implementuje przybliżone dopasowanie, łączy wstępne filtrowanie z DFA w BDM (dopasowanie wsteczne DAWG). BNDM NR-grep rozszerza technikę BDM o równoległość Shift-Or na poziomie bitowym.

Istnieje kilka teoretycznych alternatyw dla wycofywania się dla odwołań wstecznych, a ich „wykładniki” są poskromione, ponieważ są związane tylko z liczbą odwołań wstecznych, stałą właściwością niektórych języków regexp, takich jak POSIX. Jedna naiwna metoda, która duplikuje NFA bez śledzenia wstecznego dla każdej notatki o odwołaniu wstecznym, ma złożoność czasu i przestrzeni dla stogu siana o długości n i k odwołań wstecznych w RegExp. Bardzo niedawna praca teoretyczna oparta na automatach pamięciowych daje ściślejsze ograniczenie w oparciu o używane „aktywne” zmienne węzły oraz możliwość wielomianu dla niektórych wyrażeń regularnych, do których odwołuje się wstecz.

Unicode

W kategoriach teoretycznych każdy zestaw tokenów może być dopasowany za pomocą wyrażeń regularnych, o ile jest to wstępnie zdefiniowane. Jeśli chodzi o historyczne implementacje, wyrażenia regularne zostały pierwotnie napisane tak, aby używały znaków ASCII jako zestawu tokenów, chociaż biblioteki wyrażeń regularnych obsługują wiele innych zestawów znaków . Wiele nowoczesnych silników regex oferuje przynajmniej część wsparcia dla Unicode . Pod wieloma względami nie ma znaczenia, jaki jest zestaw znaków, ale podczas rozszerzania wyrażeń regularnych w celu obsługi Unicode pojawiają się pewne problemy.

  • Obsługiwane kodowanie . Niektóre biblioteki regex oczekują, że będą działać na określonym kodowaniu zamiast na abstrakcyjnych znakach Unicode. Wiele z nich wymaga kodowania UTF-8 , podczas gdy inne mogą oczekiwać UTF-16 lub UTF-32 . W przeciwieństwie do tego, Perl i Java są agnostyczne w zakresie kodowania, zamiast tego operują wewnętrznie na zdekodowanych znakach.
  • Obsługiwany zakres Unicode . Wiele silników regex obsługuje tylko podstawową płaszczyznę wielojęzyczną , czyli znaki, które można zakodować za pomocą tylko 16 bitów. Obecnie (od 2016 r.) tylko kilka silników regex (np. Perl i Java) może obsłużyć pełny 21-bitowy zakres Unicode.
  • Rozszerzanie konstrukcji zorientowanych na ASCII do Unicode . Na przykład w implementacjach opartych na ASCII zakresy znaków formularza [x-y]są prawidłowe, gdy x i y mają punkty kodowe z zakresu [0x00,0x7F] i codepoint( x ) ≤ codepoint( y ). Naturalne rozszerzenie takich zakresów znaków do Unicode po prostu zmieniłoby wymaganie, że punkty końcowe leżą w [0x00,0x7F] na wymaganie, że leżą w [0x0000,0x10FFFF]. Jednak w praktyce często tak nie jest. Niektóre implementacje, takie jak gawk , nie pozwalają zakresom znaków na przecinanie bloków Unicode. Zakres taki jak [0x61,0x7F] jest prawidłowy, ponieważ oba punkty końcowe należą do bloku Łaciny podstawowej, podobnie jak [0x0530,0x0560], ponieważ oba punkty końcowe należą do bloku ormiańskiego, ale zakres taki jak [0x0061,0x0532] jest nieprawidłowy, ponieważ obejmuje wiele bloków Unicode. Inne silniki, takie jak edytor Vima , pozwalają na przechodzenie bloków, ale wartości znaków nie mogą być od siebie oddalone o więcej niż 256.
  • Niewrażliwość na wielkość liter . Niektóre flagi niewrażliwości na wielkość liter mają wpływ tylko na znaki ASCII. Inne flagi wpływają na wszystkie postacie. Niektóre silniki mają dwie różne flagi, jedną dla ASCII, drugą dla Unicode. Dokładne znaki należące do klas POSIX również się różnią.
  • Kuzyni niewrażliwości na wielkość liter . Ponieważ ASCII ma rozróżnienie wielkości liter, niewrażliwość na wielkość liter stała się logiczną cechą wyszukiwania tekstu. Unicode wprowadził alfabetyczne skrypty bez wielkości liter, takie jak Devanagari . W tym przypadku rozróżnianie wielkości liter nie ma zastosowania. W przypadku skryptów takich jak chiński logiczne wydaje się inne rozróżnienie: między tradycyjnym a uproszczonym. W pismach arabskich może być pożądana niewrażliwość na pozycję początkową, środkową, końcową i izolowaną . W języku japońskim czasami przydatna jest niewrażliwość między hiraganą a katakaną .
  • Normalizacja . Unicode ma łączenie znaków . Podobnie jak w starych maszynach do pisania, po zwykłych znakach podstawowych (spacjach, interpunkcjach, symbolach, cyfrach lub literach) może występować jeden lub więcej symboli bez odstępów (zwykle znaki diakrytyczne, takie jak znaki akcentu modyfikujące litery), aby utworzyć pojedynczy drukowalny znak; ale Unicode zapewnia również ograniczony zestaw prekomponowanych znaków, tj. znaków, które zawierają już jeden lub więcej znaków łączących. Sekwencja znaku podstawowego + znaków łączących powinna być dopasowana do identycznego pojedynczego złożonego znaku (tylko niektóre z tych łączących sekwencji mogą być wstępnie złożone w pojedynczy znak Unicode, ale nieskończenie wiele innych łączących sekwencji jest możliwych w Unicode i jest potrzebnych dla różnych języków , przy użyciu jednego lub więcej znaków łączących po początkowym znaku podstawowym; te sekwencje łączące mogą obejmować znak podstawowy lub łączące znaki częściowo prekomponowane, ale niekoniecznie w kolejności kanonicznej i niekoniecznie przy użyciu prekompozycji kanonicznych). Proces standaryzacji sekwencji znaku podstawowego + łączenia znaków przez dekompozycję tych kanonicznie równoważnych sekwencji, przed zmianą ich kolejności w kolejności kanonicznej (i opcjonalnie rekompozycji niektórych znaków łączących do wiodącego znaku podstawowego) nazywa się normalizacją.
  • Nowe kody kontrolne . Unicode wprowadził między innymi znaczniki kolejności bajtów i znaczniki kierunku tekstu. Być może trzeba będzie postępować z tymi kodeksami w specjalny sposób.
  • Wprowadzenie klas znaków dla bloków Unicode, skryptów i wielu innych właściwości znaków . Właściwości bloku są znacznie mniej przydatne niż właściwości skryptu, ponieważ blok może mieć punkty kodowe z kilku różnych skryptów, a skrypt może mieć punkty kodowe z kilku różnych bloków. W Perl i java.util.regexbiblioteki, właściwości formularza \p{InX}lub \p{Block=X}znaków meczu w bloku X i \P{InX}czy \P{Block=X}punkty dopasowania kodu nie w tym bloku. Podobnie, \p{Armenian}, \p{IsArmenian}lub \p{Script=Armenian}pasuje do dowolnego znaku w alfabecie ormiańskim. Ogólnie \p{X}dopasowuje dowolny znak z właściwością binarną X lub ogólną kategorią X . Na przykład \p{Lu}, \p{Uppercase_Letter}albo \p{GC=Lu}dopasowuje dowolny wielką literą. Właściwości binarne, które są nie ogólne kategorie obejmują \p{White_Space}, \p{Alphabetic}, \p{Math}, i \p{Dash}. Przykładami właściwości niebinarnych są \p{Bidi_Class=Right_to_Left}, \p{Word_Break=A_Letter}, i \p{Numeric_Value=10}.

Zastosowania

Regexes są przydatne w wielu różnych zadaniach związanych z przetwarzaniem tekstu, a bardziej ogólnie w przetwarzaniu ciągów , gdzie dane nie muszą być tekstowe. Typowe aplikacje obejmują sprawdzanie poprawności danych , dane zgrzebłowych (zwłaszcza zgarniania WWW ), dane spory , prosty analizowania , produkcja podświetlanie składni systemów i wielu innych zadań.

Chociaż wyrażenia regularne byłyby przydatne w wyszukiwarkach internetowych , przetwarzanie ich w całej bazie danych może zużywać nadmierne zasoby komputera w zależności od złożoności i projektu wyrażenia regularnego. Chociaż w wielu przypadkach administratorzy systemu mogą wewnętrznie uruchamiać zapytania oparte na wyrażeniach regularnych, większość wyszukiwarek nie oferuje publicznie obsługi wyrażenia regularnego. Godne uwagi wyjątki obejmują Google Code Search i Exalead . Jednak Google Code Search został zamknięty w styczniu 2012 roku.

Przykłady

Konkretne reguły składni różnią się w zależności od konkretnej implementacji, języka programowania lub używanej biblioteki . Dodatkowo funkcjonalność implementacji wyrażeń regularnych może się różnić w zależności od wersji .

Ponieważ wyrażenia regularne mogą być trudne zarówno do wyjaśnienia, jak i zrozumienia bez przykładów, interaktywne strony internetowe do testowania wyrażeń regularnych są przydatnym źródłem do nauki wyrażeń regularnych poprzez eksperymentowanie. Ta sekcja zawiera podstawowy opis niektórych właściwości wyrażeń regularnych za pomocą ilustracji.

W przykładach zastosowano następujące konwencje.

metacharacter(s) ;; the metacharacters column specifies the regex syntax being demonstrated
=~ m//           ;; indicates a regex match operation in Perl
=~ s///          ;; indicates a regex substitution operation in Perl

Warto również zauważyć, że wszystkie te wyrażenia regularne mają składnię podobną do Perla. Standardowe wyrażenia regularne POSIX są inne.

O ile nie wskazano inaczej, poniższe przykłady są zgodne z językiem programowania Perl , wydanie 5.8.8, 31 stycznia 2006. Oznacza to, że inne implementacje mogą nie obsługiwać niektórych części pokazanej tutaj składni (np. podstawowe vs. rozszerzone regex, \( \)vs. ()lub brak \dzamiast POSIX [:digit:] ).

Składnia i konwencje użyte w tych przykładach pokrywają się również z innymi środowiskami programistycznymi.

Metaznaki Opis Przykład
. Normalnie dopasowuje dowolny znak z wyjątkiem nowej linii.
W nawiasach kwadratowych kropka jest dosłowna.
$string1 = "Hello World\n";
if ($string1 =~ m/...../) {
  print "$string1 has length >= 5.\n";
}

Wyjście:

Hello World
 has length >= 5.
( ) Grupuje serię elementów szyku w jeden element.
Kiedy dopasujesz wzorzec w nawiasach, możesz później użyć dowolnego z $1, $2, ..., aby odwołać się do poprzednio dopasowanego wzorca.
$string1 = "Hello World\n";
if ($string1 =~ m/(H..).(o..)/) {
  print "We matched '$1' and '$2'.\n";
}

Wyjście:

We matched 'Hel' and 'o W'.
+ Dopasowuje poprzedni element wzorca raz lub więcej razy.
$string1 = "Hello World\n";
if ($string1 =~ m/l+/) {
  print "There are one or more consecutive letter \"l\"'s in $string1.\n";
}

Wyjście:

There are one or more consecutive letter "l"'s in Hello World.
? Dopasowuje poprzedni element wzorca zero lub jeden raz.
$string1 = "Hello World\n";
if ($string1 =~ m/H.?e/) {
  print "There is an 'H' and a 'e' separated by ";
  print "0-1 characters (e.g., He Hue Hee).\n";
}

Wyjście:

There is an 'H' and a 'e' separated by 0-1 characters (e.g., He Hue Hee).
? Modyfikuje *, +, ?lub {M,N}„d regex, który przychodzi przed dopasować tak kilka razy, jak to możliwe.
$string1 = "Hello World\n";
if ($string1 =~ m/(l.+?o)/) {
  print "The non-greedy match with 'l' followed by one or ";
  print "more characters is 'llo' rather than 'llo Wo'.\n";
}

Wyjście:

The non-greedy match with 'l' followed by one or more characters is 'llo' rather than 'llo Wo'.
* Dopasowuje poprzedni element wzoru zero lub więcej razy.
$string1 = "Hello World\n";
if ($string1 =~ m/el*o/) {
  print "There is an 'e' followed by zero to many ";
  print "'l' followed by 'o' (e.g., eo, elo, ello, elllo).\n";
}

Wyjście:

There is an 'e' followed by zero to many 'l' followed by 'o' (e.g., eo, elo, ello, elllo).
{M,N} Oznacza minimalną liczbę dopasowań M i maksymalną liczbę N.
N można pominąć, a M może wynosić 0: {M}pasuje "dokładnie" M razy; {M,}pasuje „co najmniej” M razy; {0,N}pasuje „co najwyżej” N razy.
x* y+ z?jest zatem równoważne x{0,} y{1,} z{0,1}.
$string1 = "Hello World\n";
if ($string1 =~ m/l{1,2}/) {
  print "There exists a substring with at least 1 ";
  print "and at most 2 l's in $string1\n";
}

Wyjście:

There exists a substring with at least 1 and at most 2 l's in Hello World
[…] Oznacza zestaw możliwych dopasowań znaków.
$string1 = "Hello World\n";
if ($string1 =~ m/[aeiou]+/) {
  print "$string1 contains one or more vowels.\n";
}

Wyjście:

Hello World
 contains one or more vowels.
| Oddziela alternatywne możliwości.
$string1 = "Hello World\n";
if ($string1 =~ m/(Hello|Hi|Pogo)/) {
  print "$string1 contains at least one of Hello, Hi, or Pogo.";
}

Wyjście:

Hello World
 contains at least one of Hello, Hi, or Pogo.
\b Dopasowuje granicę o zerowej szerokości między znakiem klasy słowa (patrz dalej) a znakiem niebędącym znakiem klasy słowa lub krawędzią; taki sam jak

(^\w|\w$|\W\w|\w\W).

$string1 = "Hello World\n";
if ($string1 =~ m/llo\b/) {
  print "There is a word that ends with 'llo'.\n";
}

Wyjście:

There is a word that ends with 'llo'.
\w Dopasowuje znak alfanumeryczny, w tym „_”;
tak samo jak [A-Za-z0-9_]w ASCII i
[\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]

w Unicode, gdzie Alphabeticwłaściwość zawiera więcej niż litery łacińskie, a Decimal_Numberwłaściwość zawiera więcej niż cyfry arabskie.

$string1 = "Hello World\n";
if ($string1 =~ m/\w/) {
  print "There is at least one alphanumeric ";
  print "character in $string1 (A-Z, a-z, 0-9, _).\n";
}

Wyjście:

There is at least one alphanumeric character in Hello World
 (A-Z, a-z, 0-9, _).
\W Dopasowuje non charakter -alphanumeric, z wyjątkiem "_";
tak samo jak [^A-Za-z0-9_]w ASCII i
[^\p{Alphabetic}\p{GC=Mark}\p{GC=Decimal_Number}\p{GC=Connector_Punctuation}]

w Unicode.

$string1 = "Hello World\n";
if ($string1 =~ m/\W/) {
  print "The space between Hello and ";
  print "World is not alphanumeric.\n";
}

Wyjście:

The space between Hello and World is not alphanumeric.
\s Dopasowuje znak odstępu,
który w ASCII to tabulator, wysuw wiersza, wysuw strony, powrót karetki i spacja;
w Unicode dopasowuje również spacje bez przerw, następny wiersz i spacje o zmiennej szerokości (między innymi).
$string1 = "Hello World\n";
if ($string1 =~ m/\s.*\s/) {
  print "In $string1 there are TWO whitespace characters, which may";
  print " be separated by other characters.\n";
}

Wyjście:

In Hello World
 there are TWO whitespace characters, which may be separated by other characters.
\S Dopasowuje wszystko poza białymi znakami.
$string1 = "Hello World\n";
if ($string1 =~ m/\S.*\S/) {
  print "In $string1 there are TWO non-whitespace characters, which";
  print " may be separated by other characters.\n";
}

Wyjście:

In Hello World
 there are TWO non-whitespace characters, which may be separated by other characters.
\d Dopasowuje cyfrę;
tak samo jak [0-9]w ASCII;
w Unicode, tak samo jak właściwość \p{Digit}lub \p{GC=Decimal_Number}, która sama w sobie jest taka sama jak \p{Numeric_Type=Decimal}właściwość.
$string1 = "99 bottles of beer on the wall.";
if ($string1 =~ m/(\d+)/) {
  print "$1 is the first number in '$string1'\n";
}

Wyjście:

99 is the first number in '99 bottles of beer on the wall.'
\D Dopasowuje niecyfrę;
tak samo jak [^0-9]w ASCII lub \P{Digit}w Unicode.
$string1 = "Hello World\n";
if ($string1 =~ m/\D/) {
  print "There is at least one character in $string1";
  print " that is not a digit.\n";
}

Wyjście:

There is at least one character in Hello World
 that is not a digit.
^ Dopasowuje początek wiersza lub ciągu.
$string1 = "Hello World\n";
if ($string1 =~ m/^He/) {
  print "$string1 starts with the characters 'He'.\n";
}

Wyjście:

Hello World
 starts with the characters 'He'.
$ Dopasowuje koniec wiersza lub ciągu.
$string1 = "Hello World\n";
if ($string1 =~ m/rld$/) {
  print "$string1 is a line or string ";
  print "that ends with 'rld'.\n";
}

Wyjście:

Hello World
 is a line or string that ends with 'rld'.
\A Dopasowuje początek ciągu (ale nie wiersz wewnętrzny).
$string1 = "Hello\nWorld\n";
if ($string1 =~ m/\AH/) {
  print "$string1 is a string ";
  print "that starts with 'H'.\n";
}

Wyjście:

Hello
World
 is a string that starts with 'H'.
\z Dopasowuje koniec ciągu (ale nie wiersz wewnętrzny).
$string1 = "Hello\nWorld\n";
if ($string1 =~ m/d\n\z/) {
  print "$string1 is a string ";
  print "that ends with 'd\\n'.\n";
}

Wyjście:

Hello
World
 is a string that ends with 'd\n'.
[^…] Dopasowuje wszystkie znaki z wyjątkiem tych w nawiasach.
$string1 = "Hello World\n";
if ($string1 =~ m/[^abc]/) {
 print "$string1 contains a character other than ";
 print "a, b, and c.\n";
}

Wyjście:

Hello World
 contains a character other than a, b, and c.

Wprowadzenie

Wyrażenia regularne można często tworzyć ("indukowane" lub "nauczone") na podstawie zestawu przykładowych ciągów. Jest to znane jako indukcja języków regularnych i jest częścią ogólnego problemu indukcji gramatyki w teorii uczenia się komputerowego . Formalnie, biorąc pod uwagę przykłady ciągów w języku regularnym, a być może także przykłady ciągów nie w tym języku regularnym, możliwe jest wywołanie gramatyki dla tego języka, tj. wyrażenia regularnego, które generuje ten język. Nie wszystkie języki regularne można indukować w ten sposób (patrz identyfikacja języka w granicy ), ale wiele z nich może. Na przykład zbiór przykładów {1, 10, 100} i zbiór ujemny (kontrprzykładów) {11, 1001, 101, 0} może być użyty do wywołania wyrażenia regularnego 1⋅0* (1, po którym następuje zero lub więcej 0s).

Zobacz też

Uwagi

Bibliografia

Zewnętrzne linki