Jak możemy dopasować ^ nb ^ n do wyrażenia regularnego Java?

_{To jest druga część serii artykułów edukacyjnych dotyczących wyrażeń regularnych. Pokazuje, jak lookaheads i zagnieżdżone odwołania mogą być użyte do dopasowania nieregularnego języka a ⁿ b ⁿ . Zagnieżdżone odwołania są po raz pierwszy wprowadzane w: W jaki sposób to wyrażenie regularne znajduje liczby trójkątne?}

Jednym z archetypów nieregularnych języków jest:

L = { aⁿ bⁿ: n > 0 }

To jest język wszystkich niepustych łańcuchów składających się z pewnej liczby a's, po których następuje taka sama liczba b' s. Przykłady ciągów w tym języku są ab, aabb, aaabbb.

Lemat o pompowaniu może wykazać, że ten język jest nieregularny . W rzeczywistości jest to archetypowy język bezkontekstowy , który może zostać wygenerowany przez gramatykę bezkontekstową S → aSb | ab .

Niemniej jednak współczesne implementacje regexów wyraźnie rozpoznają nie tylko zwykłe języki. Oznacza to, że nie są one „regularne” z definicji formalnej teorii języka. PCRE i Perl obsługują rekurencyjne wyrażenia regularne, a .NET obsługuje definicję grup równoważących. Nawet mniej „wyszukane” funkcje, np. Dopasowywanie odwołań wstecznych, oznacza, że ​​wyrażenie regularne nie jest regularne.

Ale jak potężne są te „podstawowe” funkcje? Czy możemy Lna przykład rozpoznać wyrażenia regularne w Javie? Możemy może połączyć lookarounds i odniesień zagnieżdżonych i mają wzór, który współpracuje z np String.matchespasujące ciągi jak ab, aabb, aaabbbitp?

Bibliografia

• perlfaq6: Czy mogę używać wyrażeń regularnych Perla, aby dopasować wyważony tekst?
• MSDN - Elementy języka wyrażeń regularnych - Definicje grup równoważących
• pcre.org - strona podręcznika PCRE
• regular-expressions.info - Lookarounds oraz Grouping and Backreferences
• java.util.regex.Pattern

Powiązane pytania

• Czy lookaround wpływa na to, które języki można dopasować za pomocą wyrażeń regularnych?
• NET a wzorce rekurencyjne PCRE

Nie trzeba dodawać, że TAK! Z całą pewnością możesz napisać wzorzec wyrażenia regularnego Java, aby dopasować a ⁿ b ⁿ . Używa pozytywnego wyprzedzenia dla potwierdzenia i jednego zagnieżdżonego odniesienia do „zliczania”.

Zamiast natychmiast podawać wzór, ta odpowiedź poprowadzi czytelników przez proces jego wyprowadzania. Podawane są różne wskazówki, ponieważ rozwiązanie jest powoli konstruowane. W tym aspekcie mam nadzieję, że ta odpowiedź będzie zawierała znacznie więcej niż tylko kolejny zgrabny wzorzec wyrażenia regularnego. Miejmy nadzieję, że czytelnicy nauczą się również, jak „myśleć w regex” i jak harmonijnie łączyć różne konstrukcje, aby w przyszłości mogli samodzielnie wyprowadzić więcej wzorców.

Językiem używanym do opracowania rozwiązania będzie PHP ze względu na zwięzłość. Ostatni test po sfinalizowaniu wzorca zostanie wykonany w języku Java.

Krok 1: Wypatruj asercji

Zacznijmy od prostszego problemu: chcemy dopasować a+na początku łańcucha, ale tylko wtedy, gdy zaraz po nim następuje b+. Możemy użyć ^do zakotwiczenia naszego dopasowania, a ponieważ chcemy dopasować tylko a+bezb+ znaku , możemy użyć asercji lookahead(?=…) .

Oto nasz wzór z prostą wiązką testową:

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

Dane wyjściowe to ( jak widać na ideone.com ):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

To jest dokładnie to, czego szukamy: dopasowujemy a+ , tylko jeśli znajduje się na początku ciągu i tylko wtedy, gdy bezpośrednio po nim następuje b+.

Lekcja : do tworzenia asercji można używać wzorców w obejrzeniach.

Krok 2: Przechwytywanie z wyprzedzeniem (i swobodnym - tryb odstępów)

Teraz powiedzmy, że chociaż nie chcemy, b+aby był częścią dopasowania, i tak chcemy go przechwycić do grupy 1. Ponadto, ponieważ przewidujemy bardziej skomplikowany wzorzec, użyjmy xmodyfikatora do swobodnych odstępów więc może uczynić nasze wyrażenie regularne bardziej czytelnym.

Opierając się na naszym poprzednim fragmencie kodu PHP, mamy teraz następujący wzorzec:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

Wynik to teraz ( jak widać na ideone.com ):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

Zauważ, że np. aaa|bJest wynikiem join-ing, czym każda grupa przechwyciła '|'. W tym przypadku grupa 0 (tj. Co pasował do wzorca) przechwycona aaa, a grupa 1 przechwycona b.

Lekcja : Możesz uchwycić wewnątrz widok wokół. Aby poprawić czytelność, możesz użyć wolnych odstępów.

Krok 3: refaktoryzacja wyprzedzenia do „pętli”

Zanim będziemy mogli wprowadzić nasz mechanizm liczenia, musimy dokonać jednej modyfikacji naszego wzoru. Obecnie antycypowanie znajduje się poza +„pętlą” powtórzeń. Jak dotąd jest to w porządku, ponieważ chcieliśmy tylko zapewnić, że istnieje b+śledzenie naszego a+, ale tak naprawdę chcemy ostatecznie zapewnić, że dla każdego adopasowanego elementu wewnątrz „pętli” jest odpowiadającyb .

Nie martwmy się na razie o mechanizm liczenia i po prostu zróbmy refaktoryzację w następujący sposób:

• Pierwszy Refactor a+do (?: a )+(uwaga:(?:…) to grupa non-przechwytywania)
• Następnie przesuń antycypację wewnątrz tej nieprzechwytywanej grupy
  • Zauważ, że musimy teraz „pominąć”, a*zanim będziemy mogli „zobaczyć” b+, więc odpowiednio zmodyfikuj wzór

Mamy więc teraz następujące rzeczy:

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

Dane wyjściowe są takie same jak wcześniej ( jak widać na ideone.com ), więc nie ma zmian w tym względzie. Ważną rzeczą jest to, że teraz robimy twierdzenie przy każdej iteracji w +„pętli”. Przy naszym obecnym wzorcu nie jest to konieczne, ale w następnej kolejności sprawimy, że grupa 1 będzie „liczyć” się za nas, używając samoodniesienia.

Lekcja : Możesz chwytać wewnątrz grupy, która nie jest przejmowana. Lookarounds można powtórzyć.

Krok 4: To jest krok, od którego zaczynamy liczyć

Oto, co zamierzamy zrobić: przepisujemy grupę 1 w taki sposób, że:

• Pod koniec pierwszej iteracji +, kiedy pierwszya jest dopasowana, powinna przechwycićb
• Pod koniec drugiej iteracji, kiedy inna ajest dopasowana, powinna przechwycićbb
• Pod koniec trzeciej iteracji powinien przechwycić bbb
• ...
• Pod koniec n- tej iteracji grupa 1 powinna przechwycić b ⁿ
• Jeśli nie ma ich wystarczająco dużo bdo zaliczenia do grupy 1, to twierdzenie po prostu zawodzi

Tak więc grupa 1, która jest teraz (b+), będzie musiała zostać przepisana na coś podobnego (\1 b). Oznacza to, że próbujemy „dodać” a bdo grupy 1 przechwyconej w poprzedniej iteracji.

Występuje tutaj niewielki problem polegający na tym, że w tym wzorcu brakuje „przypadku podstawowego”, tj. Przypadku, w którym można go dopasować bez odniesienia do siebie. Podstawowy przypadek jest wymagany, ponieważ grupa 1 zaczyna się „niezainicjowana”; nie przechwycił jeszcze niczego (nawet pustego łańcucha), więc próba odwołania się zawsze kończy się niepowodzeniem.

Jest wiele sposobów obejścia tego problemu, ale na razie ustawmy dopasowywanie odniesień jako opcjonalne , tj \1?. To może, ale nie musi, działać idealnie, ale zobaczmy, co to robi, a jeśli wystąpi jakiś problem, przejdziemy przez ten most, kiedy do niego dojdziemy. Ponadto dodamy więcej przypadków testowych, gdy już to zrobimy.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

Wynik to teraz ( jak widać na ideone.com ):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

Aha! Wygląda na to, że jesteśmy teraz naprawdę blisko rozwiązania! Udało nam się zmusić grupę 1 do „liczenia” za pomocą odniesienia do siebie! Ale czekaj ... coś jest nie tak z drugim i ostatnim przypadkiem testowym !! Nie ma wystarczająco dużo bi jakoś źle się liczy! W następnym kroku zbadamy, dlaczego tak się stało.

Lekcja : Jednym ze sposobów „zainicjowania” grupy odwołującej się do siebie jest uczynienie dopasowywania samoodniesień opcjonalnym.

Krok 4½: Zrozumienie, co poszło nie tak

Problem polega na tym, że skoro ustawiliśmy dopasowywanie odniesień jako opcjonalne, „licznik” może „zresetować” z powrotem do 0, gdy nie ma wystarczającej liczby wartości b. Przyjrzyjmy się dokładnie, co dzieje się w każdej iteracji naszego wzorca aaaaabbbjako dane wejściowe.

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

Aha! W naszej czwartej iteracji nadal mogliśmy dopasować \1, ale nie mogliśmy dopasować \1b! Ponieważ pozwalamy, aby dopasowywanie odniesień było opcjonalne \1?, silnik cofa się i wybrał opcję „nie, dziękuję”, która pozwala nam dopasować i przechwycić tylkob !

Zwróć jednak uwagę, że z wyjątkiem pierwszej iteracji, zawsze możesz dopasować tylko samo odniesienie \1. Jest to oczywiście oczywiste, ponieważ właśnie to uchwyciliśmy w naszej poprzedniej iteracji, aw naszej konfiguracji zawsze możemy to ponownie dopasować (np. Jeśli przechwyciliśmy bbbostatnim razem, mamy gwarancję, że nadal będzie bbb, ale może lub może nie być bbbbtym razem).

Lekcja : Uważaj na wycofywanie się. Silnik wyrażeń regularnych wykona tyle operacji cofania, ile pozwolisz, aż do dopasowania danego wzorca. Może to wpłynąć na wydajność (tj. Katastroficzne wycofywanie się ) i / lub poprawność.

Krok 5: Samoposiadanie na ratunek!

„Poprawka” powinna być teraz oczywista: połącz opcjonalne powtórzenia z kwantyfikatorem zaborczym . To znaczy, zamiast po prostu ?, użyj ?+zamiast tego (pamiętaj, że powtórzenie, które jest określone ilościowo jako zaborcze, nie cofa się, nawet jeśli taka „współpraca” może skutkować dopasowaniem ogólnego wzorca).

W warunkach bardzo nieformalne, to co ?+, ?i ??mówi:

?+

• (opcjonalnie) „Nie musi tam być”,
  • (zaborczy) "ale jeśli tam jest, musisz to wziąć i nie puścić!"

?

• (opcjonalnie) „Nie musi tam być”,
  • (chciwy) „ale jeśli tak, możesz to na razie wziąć”
    • (cofam się) „ale możesz zostać poproszony o puszczenie tego później!”

??

• (opcjonalnie) „Nie musi tam być”,
  • (niechętnie) „a nawet jeśli tak jest, nie musisz jeszcze tego brać”
    • (cofam się) „ale możesz zostać poproszony o zrobienie tego później!”

W naszej konfiguracji \1nie będzie go za pierwszym razem, ale zawsze będzie dostępny w dowolnym momencie później i zawsze chcemy to dopasować. W ten \1?+sposób osiągnęlibyśmy dokładnie to, czego chcemy.

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Teraz wynik to ( jak widać na ideone.com ):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

Voilà !!! Problem rozwiązany!!! Teraz liczymy poprawnie, dokładnie tak, jak chcemy!

Lekcja : poznaj różnicę między chciwym, niechętnym i zaborczym powtarzaniem. Opcjonalnie-zaborczy może być potężną kombinacją.

Krok 6: Ostatnie poprawki

Więc to, co teraz mamy, to wzorzec, który pasuje awielokrotnie, a dla każdego, aktóry został dopasowany, znajduje się odpowiedni bprzechwycony w grupie 1. +Kończy się, gdy nie ma więcej a, lub jeśli asercja nie powiodła się, ponieważ nie ma odpowiednika bdla an a.

Aby zakończyć pracę, wystarczy dołączyć do naszego wzoru \1 $. To jest teraz odniesienie wsteczne do dopasowanej grupy 1, po którym następuje koniec zakotwiczenia linii. Kotwica zapewnia, że ​​w ciągu nie ma żadnych dodatkowych bznaków; innymi słowy, w rzeczywistości mamy a ⁿ b ⁿ .

Oto sfinalizowany wzorzec z dodatkowymi przypadkami testowymi, w tym jeden o długości 10 000 znaków:

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Okazuje 4 mecze: ab, aabb, aaabbb, a do ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Uruchomienie w witrynie ideone.com zajmuje tylko 0,06 sekundy .

Krok 7: Test Java

Tak więc wzorzec działa w PHP, ale ostatecznym celem jest napisanie wzorca działającego w Javie.

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

Wzór działa zgodnie z oczekiwaniami ( jak widać na ideone.com ).

A teraz dochodzimy do wniosku ...

Trzeba powiedzieć, że a*antycypacja, a nawet „główna +pętla”, pozwalają na cofanie. Czytelników zachęca się do potwierdzenia, dlaczego nie stanowi to problemu pod względem poprawności i dlaczego jednocześnie sprawiłoby, że oba zaborcze również zadziałałyby (chociaż być może mieszanie obowiązkowego i nieobowiązkowego kwantyfikatora zaborczego w tym samym wzorze może prowadzić do nieporozumień).

Należy również powiedzieć, że chociaż fajnie jest, że istnieje wzorzec wyrażenia regularnego, który będzie pasował do a ⁿ b ⁿ , nie zawsze jest to „najlepsze” rozwiązanie w praktyce. Dużo lepszym rozwiązaniem jest po prostu dopasowanie^(a+)(b+)$ , a następnie porównanie długości ciągów przechwyconych przez grupy 1 i 2 w języku programowania hostującego.

W PHP może to wyglądać mniej więcej tak ( jak widać na ideone.com ):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

Celem tego artykułu NIE jest przekonanie czytelników, że regex może zrobić prawie wszystko; najwyraźniej nie może, a nawet jeśli chodzi o rzeczy, które może zrobić, należy rozważyć przynajmniej częściowe delegowanie do języka hostującego, jeśli prowadzi to do prostszego rozwiązania.

Jak wspomniano na górze, podczas gdy ten artykuł jest koniecznie oznaczony tagami [regex]dla przepełnienia stosu, być może chodzi o coś więcej. Chociaż z pewnością nauka o twierdzeniach, zagnieżdżonych odniesieniach, kwantyfikatorze zaborczym itp. Ma wartość, być może większą lekcją jest proces twórczy, za pomocą którego można spróbować rozwiązać problemy, determinację i ciężką pracę, których często wymaga, gdy jesteś poddawany różne ograniczenia, systematyczny skład z różnych części, aby zbudować działające rozwiązanie itp.

Dodatkowy materiał! Wzorzec rekurencyjny PCRE!

Ponieważ wprowadziliśmy PHP, trzeba powiedzieć, że PCRE obsługuje wzorce rekurencyjne i podprogramy. Tak więc następujący wzorzec działa dla preg_match( jak widać na ideone.com ):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

Obecnie regex Javy nie obsługuje wzorca rekurencyjnego.

Jeszcze więcej materiału bonusowego! Dopasowywanie a ⁿ b ⁿ c ⁿ !!

Tak więc widzieliśmy jak dopasować do ⁿ b ⁿ , która jest nieregularna, ale nadal bezkontekstowych, ale możemy również dopasować do ⁿ b ⁿ c ⁿ , która nie jest jeszcze wolny od kontekstu?

Odpowiedź oczywiście brzmi TAK! Zachęcamy czytelników do samodzielnego rozwiązania tego problemu, ale rozwiązanie jest podane poniżej (z implementacją w Javie na ideone.com ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $

Biorąc pod uwagę, że nie wspomniano o PCRE obsługującym wzorce rekurencyjne, chciałbym tylko wskazać najprostszy i najbardziej efektywny przykład PCRE, który opisuje dany język:

/^(a(?1)?b)$/

Jak wspomniano w pytaniu - w przypadku grupy równoważącej .NET wzorce typu a ⁿ b ⁿ c ⁿ d ⁿ … z ⁿ można łatwo dopasować jako

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

Na przykład: http://www.ideone.com/usuOE

Edytować:

Istnieje również wzorzec PCRE dla języka uogólnionego z wzorcem rekurencyjnym, ale potrzebne jest spojrzenie w przód. Nie sądzę, żeby to było bezpośrednie tłumaczenie powyższego.

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)
$

Na przykład: http://www.ideone.com/9gUwF