Bagaimana kita bisa mencocokkan ^ nb ^ n dengan Java regex?

_{Ini adalah bagian kedua dari seri artikel regex pendidikan. Ini menunjukkan bagaimana lookahead dan referensi bersarang dapat digunakan untuk mencocokkan bahasa non-reguler a ⁿ b ⁿ . Referensi bertingkat pertama kali diperkenalkan dalam: Bagaimana ekspresi reguler ini menemukan bilangan segitiga?}

Salah satu pola dasar bahasa non- reguler adalah:

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

Ini adalah bahasa dari semua string yang tidak kosong yang terdiri dari beberapa bilangan yang adiikuti dengan bilangan yang sama b. Contoh string dalam bahasa ini ab, aabb, aaabbb.

Bahasa ini dapat diperlihatkan tidak teratur oleh lemma pemompaan . Ini sebenarnya adalah bahasa tanpa konteks pola dasar , yang dapat dihasilkan oleh tata bahasa bebas konteks S → aSb | ab .

Meskipun demikian, implementasi ekspresi reguler modern dengan jelas mengenali lebih dari sekadar bahasa biasa. Artinya, mereka tidak "biasa" menurut definisi teori bahasa formal. PCRE dan Perl mendukung regex rekursif, dan .NET mendukung definisi grup penyeimbang. Bahkan fitur yang kurang "mewah", misalnya pencocokan referensi latar, berarti ekspresi reguler tidak teratur.

Tapi seberapa kuatkah fitur "dasar" ini? Bisakah kita mengenali Ldengan regex Java, misalnya? Bisakah kita mungkin menggabungkan lookarounds dan referensi bersarang dan memiliki pola yang bekerja dengan misalnya String.matchesuntuk mencocokkan string seperti ab, aabb, aaabbb, dll?

Referensi

• perlfaq6: Dapatkah saya menggunakan ekspresi reguler Perl untuk mencocokkan teks seimbang?
• MSDN - Elemen Bahasa Ekspresi Reguler - Menyeimbangkan Definisi Grup
• pcre.org - halaman manual PCRE
• regular-expressions.info - Lookarounds dan Grouping and Backreferences
• java.util.regex.Pattern

Pertanyaan terkait

• Apakah lookaround memengaruhi bahasa mana yang bisa dicocokkan dengan ekspresi reguler?
• Grup Penyeimbang Regex .NET vs Pola Rekursif PCRE

Jawabannya adalah, tidak perlu dikatakan, YA! Anda pasti bisa menulis pola regex Java agar cocok dengan ⁿ b ⁿ . Ini menggunakan lookahead positif untuk pernyataan, dan satu referensi bertingkat untuk "menghitung".

Daripada segera memberikan polanya, jawaban ini akan memandu pembaca melalui proses pembuatannya . Berbagai petunjuk diberikan saat solusi dibangun perlahan. Dalam aspek ini, semoga jawaban ini berisi lebih dari sekadar pola regex rapi lainnya. Semoga pembaca juga akan belajar bagaimana "berpikir dalam ekspresi reguler", dan bagaimana menempatkan berbagai konstruksi secara harmonis, sehingga mereka dapat memperoleh lebih banyak pola mereka sendiri di masa depan.

Bahasa yang digunakan untuk mengembangkan solusi adalah PHP karena ringkasnya. Tes terakhir setelah pola diselesaikan akan dilakukan di Java.

Langkah 1: Cari pernyataan

Mari kita mulai dengan masalah yang lebih sederhana: kita ingin mencocokkan a+di awal string, tetapi hanya jika diikuti segera oleh b+. Kita bisa menggunakan ^untuk melabuhkan kecocokan kita, dan karena kita hanya ingin mencocokkan a+tanpa b+, kita bisa menggunakan pernyataan lookahead(?=…) .

Inilah pola kami dengan test harness sederhana:

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);

Outputnya adalah ( seperti yang terlihat di ideone.com ):

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

Ini persis dengan keluaran yang kita inginkan: kita cocok a+, hanya jika itu di awal string, dan hanya jika segera diikuti oleh b+.

Pelajaran : Anda dapat menggunakan pola dalam pencarian untuk membuat pernyataan.

Langkah 2: Menangkap dalam tampilan (dan mode spasi bebas)

Sekarang katakanlah meskipun kami tidak ingin b+menjadi bagian dari pertandingan, kami tetap ingin menangkapnya ke dalam grup 1. Selain itu, karena kami mengantisipasi pola yang lebih rumit, mari gunakan xpengubah untuk spasi bebas jadi kami dapat membuat ekspresi reguler kami lebih mudah dibaca.

Membangun dari potongan PHP kami sebelumnya, kami sekarang memiliki pola berikut:

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

Outputnya sekarang ( seperti yang terlihat di ideone.com ):

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

Perhatikan bahwa eg aaa|badalah hasil dari join-ing yang ditangkap oleh setiap kelompok '|'. Dalam kasus ini, kelompok 0 (yaitu pola yang cocok) ditangkap aaa, dan kelompok 1 ditangkap b.

Pelajaran : Anda dapat menjepret di dalam sebuah pemandangan. Anda dapat menggunakan spasi bebas untuk meningkatkan keterbacaan.

Langkah 3: Memfaktorkan kembali lookahead ke dalam "loop"

Sebelum kita dapat memperkenalkan mekanisme penghitungan kita, kita perlu melakukan satu modifikasi pada pola kita. Saat ini, lookahead berada di luar +pengulangan "loop". Sejauh ini baik-baik saja karena kami hanya ingin menegaskan bahwa ada yang b+mengikuti kami a+, tetapi yang benar - benar ingin kami lakukan pada akhirnya adalah menegaskan bahwa untuk setiap ayang kami cocokkan di dalam "loop", ada yang sesuai bdengannya.

Untuk saat ini jangan khawatir tentang mekanisme penghitungan dan lakukan saja refactoring sebagai berikut:

• Refactor pertama a+ke (?: a )+(perhatikan bahwa (?:…)non-capturing group)
• Kemudian pindahkan lookahead ke dalam grup non-capturing ini
  • Perhatikan bahwa sekarang kita harus "melewati" a*sebelum kita dapat "melihat" b+, jadi ubah pola yang sesuai

Jadi sekarang kami memiliki yang berikut:

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

Outputnya sama seperti sebelumnya ( seperti yang terlihat di ideone.com ), jadi tidak ada perubahan dalam hal itu. Yang penting adalah bahwa sekarang kita membuat pernyataan di setiap iterasi dari +"lingkaran". Dengan pola kita saat ini, ini tidak perlu, tetapi selanjutnya kita akan membuat grup 1 "menghitung" untuk kita menggunakan referensi sendiri.

Pelajaran : Anda bisa menangkap di dalam grup non-penangkap. Pengamatan bisa diulang.

Langkah 4: Ini adalah langkah di mana kita mulai menghitung

Inilah yang akan kami lakukan: kami akan menulis ulang grup 1 sedemikian rupa:

• Di akhir iterasi pertama +, saat yang pertamaa cocok, itu harus menangkapb
• Di akhir iterasi kedua, ketika yang lain acocok, itu harus menangkapbb
• Di akhir iterasi ketiga, itu harus menangkap bbb
• ...
• Pada akhir iterasi ke- n , grup 1 harus menangkap b ⁿ
• Jika tidak cukup buntuk dimasukkan ke dalam grup 1 maka pernyataan gagal

Jadi grup 1, yang sekarang (b+), harus ditulis ulang menjadi seperti (\1 b). Artinya, kami mencoba untuk "menambahkan" a bke grup 1 apa yang ditangkap di iterasi sebelumnya.

Ada sedikit masalah di sini karena pola ini kehilangan "kasus dasar", yaitu kasus di mana ia dapat cocok tanpa referensi sendiri. Kasus dasar diperlukan karena grup 1 memulai "tidak diinisialisasi"; itu belum menangkap apa pun (bahkan string kosong), jadi upaya referensi sendiri akan selalu gagal.

Ada banyak cara untuk mengatasi ini, tetapi untuk saat ini mari kita buat pencocokan referensi mandiri opsional , yaitu \1?. Ini mungkin atau mungkin tidak bekerja dengan sempurna, tetapi mari kita lihat apa fungsinya, dan jika ada masalah maka kita akan menyeberangi jembatan itu ketika kita sampai di sana. Juga, kami akan menambahkan beberapa kasus uji lagi saat kami melakukannya.

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

Outputnya sekarang ( seperti yang terlihat di 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....

A-ha! Sepertinya kita sudah sangat dekat dengan solusinya sekarang! Kami berhasil membuat grup 1 "menghitung" menggunakan referensi sendiri! Tapi tunggu ... ada yang salah dengan test case kedua dan terakhir !! Tidak cukup bs, dan entah bagaimana itu dihitung salah! Kami akan memeriksa mengapa ini terjadi di langkah berikutnya.

Pelajaran : Satu cara untuk "menginisialisasi" grup referensi mandiri adalah dengan membuat pencocokan referensi mandiri opsional.

Langkah 4½: Memahami apa yang salah

Masalahnya adalah karena kita membuat pencocokan referensi mandiri opsional, "penghitung" dapat "mengatur ulang" kembali ke 0 bila jumlahnya tidak mencukupi b. Mari kita teliti apa yang terjadi pada setiap iterasi pola kita dengan aaaaabbbsebagai masukan.

 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

A-ha! Pada iterasi ke-4 kami, kami masih bisa menyamai \1, tetapi kami tidak bisa mencocokkan \1b! Karena kami mengizinkan pencocokan referensi mandiri menjadi opsional dengan \1?, mesin melakukan backtrack dan mengambil opsi "tidak, terima kasih", yang kemudian memungkinkan kami untuk mencocokkan dan menangkap hanyab !

Perhatikan, bagaimanapun, bahwa kecuali pada iterasi pertama, Anda selalu dapat mencocokkan hanya referensi sendiri \1. Ini jelas, tentu saja, karena itulah yang baru saja kami tangkap pada iterasi kami sebelumnya, dan dalam pengaturan kami, kami selalu dapat mencocokkannya lagi (misalnya jika kami menangkapnya bbbterakhir kali, kami dijamin masih akan ada bbb, tetapi mungkin ada atau mungkin tidak bbbbkali ini).

Pelajaran : Waspadai mundur. Mesin regex akan melakukan pelacakan mundur sebanyak yang Anda izinkan hingga pola yang diberikan cocok. Hal ini dapat memengaruhi kinerja (mis. Lacak balik bencana ) dan / atau kebenaran.

Langkah 5: Milik diri untuk menyelamatkan!

"Perbaikan" sekarang seharusnya sudah jelas: gabungkan pengulangan opsional dengan pembilang posesif . Artinya, alih-alih hanya ?, gunakan ?+sebagai gantinya (ingat bahwa pengulangan yang dikuantifikasi sebagai posesif tidak mundur, bahkan jika "kerja sama" semacam itu dapat menghasilkan kecocokan dari pola keseluruhan).

Dalam istilah yang sangat informal, inilah yang ?+, ?dan ??katakan:

?+

• (opsional) "Tidak harus ada di sana,"
  • (posesif) "tetapi jika ada, Anda harus mengambilnya dan tidak melepaskannya!"

?

• (opsional) "Tidak harus ada di sana,"
  • (serakah) "tetapi jika itu Anda bisa menerimanya untuk saat ini,"
    • (mundur) "tetapi Anda mungkin diminta untuk melepaskannya nanti!"

??

• (opsional) "Tidak harus ada di sana,"
  • (enggan) "dan bahkan jika itu Anda tidak harus mengambilnya dulu,"
    • (mundur) "tetapi Anda mungkin diminta untuk mengambilnya nanti!"

Dalam pengaturan kami, \1tidak akan ada untuk pertama kalinya, tetapi akan selalu ada kapan saja setelah itu, dan kami selalu ingin mencocokkannya. Dengan demikian, \1?+akan mencapai apa yang kita inginkan.

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

Sekarang hasilnya adalah ( seperti yang terlihat di 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à !!! Masalah terpecahkan !!! Kami sekarang menghitung dengan benar, persis seperti yang kami inginkan!

Pelajaran : Pelajari perbedaan antara pengulangan serakah, enggan, dan posesif. Opsional-posesif bisa menjadi kombinasi yang kuat.

Langkah 6: Sentuhan akhir

Jadi apa yang kita miliki sekarang adalah pola yang cocok aberulang kali, dan untuk setiap ayang cocok, ada yang sesuai bditangkap di grup 1. +Berhenti ketika tidak ada lagi a, atau jika pernyataan gagal karena tidak ada yang sesuai buntuk sebuah a.

Untuk menyelesaikan pekerjaan, kita hanya perlu menambahkan pola kita \1 $. Ini sekarang menjadi referensi kembali ke grup 1 yang cocok, diikuti oleh akhir jangkar baris. Jangkar memastikan bahwa tidak ada tambahan apapun bdalam string; dengan kata lain, bahwa sebenarnya kita memiliki a ⁿ b ⁿ .

Inilah pola akhir, dengan kasus uji tambahan, termasuk satu yang memiliki 10.000 karakter:

$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

Ia menemukan 4 pertandingan: ab, aabb, aaabbb, dan sebuah ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Hanya perlu 0,06 detik untuk berjalan di ideone.com .

Langkah 7: Tes Java

Jadi polanya berfungsi di PHP, tetapi tujuan akhirnya adalah menulis pola yang berfungsi di Java.

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);
}

Polanya bekerja seperti yang diharapkan ( seperti yang terlihat di ideone.com ).

Dan sekarang kita sampai pada kesimpulan ...

Perlu dikatakan bahwa a*in the lookahead, dan memang "main +loop", keduanya mengizinkan backtracking. Pembaca didorong untuk mengkonfirmasi mengapa ini bukan masalah dalam hal kebenaran, dan mengapa pada saat yang sama membuat keduanya posesif juga akan berhasil (meskipun mungkin mencampur pembilang posesif wajib dan tidak wajib dalam pola yang sama dapat menyebabkan kesalahan persepsi).

Juga harus dikatakan bahwa meskipun rapi bahwa ada pola regex yang akan cocok dengan a ⁿ b ⁿ , ini tidak selalu merupakan solusi "terbaik" dalam praktiknya. Solusi yang jauh lebih baik adalah mencocokkan ^(a+)(b+)$, dan kemudian membandingkan panjang string yang ditangkap oleh grup 1 dan 2 dalam bahasa pemrograman hosting.

Di PHP, mungkin terlihat seperti ini ( seperti yang terlihat di ideone.com ):

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

Tujuan artikel ini BUKAN untuk meyakinkan pembaca bahwa regex dapat melakukan hampir semua hal; jelas tidak bisa, dan bahkan untuk hal-hal yang bisa dilakukannya, setidaknya sebagian delegasi ke bahasa hosting harus dipertimbangkan jika mengarah ke solusi yang lebih sederhana.

Seperti disebutkan di atas, sementara artikel ini selalu diberi tag [regex]untuk stackoverflow, mungkin lebih dari itu. Meskipun tentunya ada nilai dalam mempelajari pernyataan, referensi bersarang, pembilang posesif, dll, mungkin pelajaran yang lebih besar di sini adalah proses kreatif yang digunakan seseorang untuk mencoba memecahkan masalah, tekad, dan kerja keras yang sering dibutuhkan saat Anda dihadapkan. berbagai kendala, komposisi sistematis dari berbagai bagian untuk membangun solusi kerja, dll.

Materi bonus! Pola rekursif PCRE!

Karena kami memang memunculkan PHP, perlu dikatakan bahwa PCRE mendukung pola rekursif dan subrutin. Jadi, pola berikut berfungsi untuk preg_match( seperti yang terlihat di ideone.com ):

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

Saat ini regex Java tidak mendukung pola rekursif.

Lebih banyak materi bonus! Mencocokkan a ⁿ b ⁿ c ⁿ !!

Jadi kita telah melihat bagaimana mencocokkan a ⁿ b ⁿ yang tidak beraturan, tetapi masih bebas konteks, tetapi dapatkah kita juga mencocokkan a ⁿ b ⁿ c ⁿ , yang bahkan tidak bebas konteks?

Jawabannya tentu saja YA! Pembaca didorong untuk mencoba menyelesaikan ini sendiri, tetapi solusinya disediakan di bawah ini (dengan implementasi di Java di ideone.com ).

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

Mengingat tidak disebutkannya PCRE yang mendukung pola rekursif, saya hanya ingin menunjukkan contoh PCRE yang paling sederhana dan paling efisien yang menjelaskan bahasa yang dimaksud:

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

Seperti yang disebutkan dalam pertanyaan - dengan grup penyeimbang .NET, pola tipe a ⁿ b ⁿ c ⁿ d ⁿ … z ⁿ dapat dicocokkan dengan mudah seperti

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

Misalnya: http://www.ideone.com/usuOE

Edit:

Ada juga pola PCRE untuk bahasa umum dengan pola rekursif, tetapi diperlukan tampilan yang mirip. Saya tidak berpikir ini adalah terjemahan langsung dari yang di atas.

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

Misalnya: http://www.ideone.com/9gUwF