Mengapa tidak mungkin menggunakan regex untuk mengurai HTML / XML: penjelasan formal dalam istilah awam

Tidak ada hari di SO yang berlalu tanpa pertanyaan tentang parsing (X) HTML atau XML dengan ekspresi reguler yang diminta.

Meskipun relatif mudah untuk menghasilkan contoh yang menunjukkan regex yang tidak dapat berfungsi untuk tugas ini atau dengan kumpulan ekspresi untuk mewakili konsep, saya masih tidak dapat menemukan penjelasan formal tentang mengapa hal ini tidak mungkin dilakukan di awam. istilah.

Satu-satunya penjelasan formal yang sejauh ini dapat saya temukan di situs ini mungkin sangat akurat, tetapi juga cukup samar bagi programmer otodidak:

kekurangannya di sini adalah bahwa HTML adalah tata bahasa Chomsky Tipe 2 (tata bahasa bebas konteks) dan RegEx adalah tata bahasa Chomsky Tipe 3 (ekspresi reguler)

atau:

Ekspresi reguler hanya dapat mencocokkan bahasa biasa tetapi HTML adalah bahasa tanpa konteks.

atau:

Sebuah robot terbatas (yang merupakan struktur data yang mendasari ekspresi reguler) tidak memiliki memori selain dari keadaannya, dan jika Anda memiliki sarang yang dalam secara sewenang-wenang, Anda memerlukan robot besar yang sewenang-wenang, yang bertabrakan dengan gagasan tentang robot terbatas.

atau:

Lemma Pumping untuk bahasa biasa adalah alasan mengapa Anda tidak bisa melakukan itu.

[Agar adil: mayoritas dari penjelasan di atas tertaut ke halaman wikipedia, tetapi ini tidak lebih mudah untuk dimengerti daripada jawabannya sendiri].

Jadi pertanyaan saya adalah: dapatkah seseorang memberikan terjemahan dalam istilah awam dari penjelasan formal yang diberikan di atas tentang mengapa tidak mungkin menggunakan regex untuk parsing (X) HTML / XML?

EDIT: Setelah membaca jawaban pertama, saya pikir saya harus menjelaskan: Saya mencari "terjemahan" yang juga menjelaskan secara singkat konsep yang coba diterjemahkan: di akhir jawaban, pembaca harus memiliki gambaran kasar - misalnya - tentang apa arti "bahasa biasa" dan "tata bahasa bebas konteks" ...

Berkonsentrasi pada yang ini:

Sebuah robot terbatas (yang merupakan struktur data yang mendasari ekspresi reguler) tidak memiliki memori selain dari keadaannya, dan jika Anda memiliki sarang yang dalam secara sewenang-wenang, Anda memerlukan robot besar yang sewenang-wenang, yang bertabrakan dengan gagasan tentang robot terbatas.

The Definisi dari ekspresi reguler adalah setara dengan fakta bahwa tes apakah string cocok pola dapat dilakukan oleh robot yang terbatas (satu robot yang berbeda untuk masing-masing pola). Otomat terbatas tidak memiliki memori - tidak ada tumpukan, tidak ada tumpukan, tidak ada pita tak terbatas untuk dicoret-coret. Yang dimilikinya hanyalah sejumlah status internal yang terbatas, yang masing-masing dapat membaca unit input dari string yang diuji, dan menggunakannya untuk memutuskan status mana yang akan dipindahkan berikutnya. Sebagai kasus khusus, ini memiliki dua status penghentian: "ya, itu cocok", dan "tidak, itu tidak cocok".

HTML, di sisi lain, memiliki struktur yang dapat bertumpuk dalam-dalam. Untuk menentukan apakah sebuah file adalah HTML yang valid atau tidak, Anda perlu memeriksa apakah semua tag penutup cocok dengan tag pembuka sebelumnya. Untuk memahaminya, Anda perlu mengetahui elemen mana yang ditutup. Tanpa sarana untuk "mengingat" tag pembuka apa yang Anda lihat, tidak ada kesempatan.

Namun perlu diperhatikan bahwa sebagian besar pustaka "regex" sebenarnya mengizinkan lebih dari sekadar definisi ekspresi reguler yang ketat. Jika mereka dapat mencocokkan referensi belakang, maka mereka telah melampaui bahasa biasa. Jadi alasan mengapa Anda tidak boleh menggunakan pustaka regex pada HTML sedikit lebih rumit daripada fakta sederhana bahwa HTML tidak biasa.

Fakta bahwa HTML tidak mewakili bahasa biasa adalah red herring. Ekspresi reguler dan bahasa reguler terdengar serupa , tetapi tidak - keduanya memiliki asal yang sama, tetapi ada jarak yang mencolok antara "bahasa reguler" akademis dan kekuatan mesin pencocokan saat ini. Nyatanya, hampir semua mesin ekspresi reguler modern mendukung fitur non-reguler - contoh sederhananya adalah (.*)\1. yang menggunakan referensi ke belakang untuk mencocokkan urutan karakter yang berulang - misalnya 123123, atau bonbon. Pencocokan struktur rekursif / seimbang membuat ini semakin menyenangkan.

Wikipedia menempatkan ini dengan baik, dalam kutipan oleh Larry Wall :

'Ekspresi reguler' [...] hanya sedikit terkait dengan ekspresi reguler yang sebenarnya. Namun demikian, istilah tersebut telah berkembang dengan kemampuan mesin pencocokan pola kami, jadi saya tidak akan mencoba melawan kebutuhan linguistik di sini. Saya akan, bagaimanapun, biasanya menyebutnya "regexes" (atau "regexen", ketika saya dalam mood Anglo-Saxon).

"Ekspresi reguler hanya dapat mencocokkan bahasa biasa", seperti yang Anda lihat, tidak lebih dari kesalahan yang umum dinyatakan.

Jadi, mengapa tidak?

Alasan yang baik untuk tidak mencocokkan HTML dengan ekspresi reguler adalah "hanya karena Anda bisa bukan berarti Anda harus". Meskipun mungkin - ada alat yang lebih baik untuk pekerjaan itu . Mengingat:

• HTML yang valid lebih sulit / lebih kompleks dari yang Anda kira.
• Ada banyak jenis HTML yang "valid" - yang valid di HTML, misalnya, tidak valid di XHTML.
• Banyak dari HTML bentuk bebas yang ditemukan di internet tidak valid . Perpustakaan HTML melakukan pekerjaan yang baik untuk menangani ini juga, dan telah diuji untuk banyak kasus umum ini.

• Seringkali tidak mungkin untuk mencocokkan bagian data tanpa menguraikannya secara keseluruhan. Misalnya, Anda mungkin mencari semua judul, dan akhirnya cocok di dalam komentar atau string literal. <h1>.*?</h1>mungkin merupakan upaya berani untuk menemukan judul utama, tetapi mungkin menemukan:

  <!-- <h1>not the title!</h1> -->

  Atau bahkan:

  <script>
  var s = "Certainly <h1>not the title!</h1>";
  </script>

Poin terakhir adalah yang paling penting:

• Menggunakan parser HTML khusus lebih baik daripada regex apa pun yang dapat Anda buat. Sangat sering, XPath memungkinkan cara ekspresif yang lebih baik untuk menemukan data yang Anda butuhkan, dan menggunakan parser HTML jauh lebih mudah daripada yang disadari kebanyakan orang .

Ringkasan subjek yang bagus, dan komentar penting tentang saat mencampurkan Regex dan HTML mungkin sesuai, dapat ditemukan di blog Jeff Atwood: Parsing Html The Cthulhu Way .

Kapan lebih baik menggunakan ekspresi reguler untuk mengurai HTML?

Dalam kebanyakan kasus, lebih baik menggunakan XPath pada struktur DOM yang dapat diberikan perpustakaan kepada Anda. Namun, bertentangan dengan pendapat umum, ada beberapa kasus ketika saya sangat menyarankan menggunakan regex dan bukan parser library:

Diberikan beberapa kondisi berikut:

• Saat Anda memerlukan pembaruan satu kali untuk file HTML Anda, dan Anda tahu bahwa strukturnya konsisten.
• Jika Anda memiliki sedikit cuplikan HTML.
• Saat Anda tidak berurusan dengan file HTML, tetapi mesin template yang serupa (dalam hal ini akan sangat sulit menemukan parser).
• Ketika Anda ingin mengubah bagian dari HTML, tetapi tidak semuanya - parser, menurut pengetahuan saya, tidak dapat menjawab permintaan ini: ini akan mengurai seluruh dokumen, dan menyimpan seluruh dokumen, mengubah bagian yang tidak ingin Anda ubah.

Karena HTML dapat memiliki nesting of yang tidak terbatas <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>dan regex tidak dapat benar-benar mengatasinya karena HTML tidak dapat melacak riwayat turunan dan keluarannya.

Sebuah konstruksi sederhana yang menggambarkan kesulitan:

<body><div id="foo">Hi there!  <div id="bar">Bye!</div></div></body>

99,9% dari rutinitas ekstraksi berbasis regex umum tidak akan dapat memberi saya semua yang ada di dalam divdengan ID dengan benar foo, karena mereka tidak dapat membedakan tag penutup untuk div itu dari tag penutup untuk bardiv. Itu karena mereka tidak memiliki cara untuk mengatakan "oke, saya sekarang turun ke div kedua dari dua, jadi penutup div berikutnya yang saya lihat membawa saya keluar satu, dan yang setelah itu adalah tag penutup untuk yang pertama" . Pemrogram biasanya merespons dengan merancang regex kasus khusus untuk situasi tertentu, yang kemudian rusak segera setelah lebih banyak tag dimasukkan di dalam foodan harus dilepaskan dengan biaya yang sangat besar dalam waktu dan frustrasi. Inilah sebabnya mengapa orang menjadi marah tentang semuanya.

Bahasa reguler adalah bahasa yang dapat dicocokkan oleh mesin negara hingga.

(Memahami mesin Keadaan Hingga, mesin Push-down, dan mesin Turing pada dasarnya adalah kurikulum Kursus CS perguruan tinggi tahun keempat.)

Perhatikan mesin berikut, yang mengenali string "hi".

(Start) --Read h-->(A)--Read i-->(Succeed)
  \                  \
   \                  -- read any other value-->(Fail) 
    -- read any other value-->(Fail)

Ini adalah mesin sederhana untuk mengenali bahasa biasa; Setiap ekspresi dalam tanda kurung adalah status, dan setiap panah adalah transisi. Membangun mesin seperti ini akan memungkinkan Anda menguji string input apa pun terhadap bahasa reguler - karenanya, ekspresi reguler.

HTML mengharuskan Anda untuk mengetahui lebih dari sekadar status Anda saat ini - HTML memerlukan riwayat tentang apa yang telah Anda lihat sebelumnya, untuk mencocokkan penumpukan tag. Anda dapat melakukannya jika Anda menambahkan tumpukan ke mesin, tetapi kemudian tidak lagi "biasa". Ini disebut mesin Push-down, dan mengenali tata bahasa.

Ekspresi reguler adalah mesin dengan status diskrit terbatas (dan biasanya agak kecil).

Untuk mengurai XML, C, atau bahasa lain dengan elemen bahasa bertumpuk sembarang, Anda perlu mengingat seberapa dalam Anda. Artinya, Anda harus bisa menghitung tanda kurung / kurung / tag.

Anda tidak dapat menghitung dengan memori terbatas. Mungkin ada lebih banyak level penjepit daripada status Anda! Anda mungkin dapat mengurai subset dari bahasa Anda yang membatasi jumlah level bersarang, tetapi itu akan sangat membosankan.

Tata bahasa adalah definisi formal tentang ke mana kata-kata bisa mengalir. Misalnya, kata sifat mendahului kata benda in English grammar, tetapi kata benda mengikuti en la gramática española. Bebas konteks berarti bahwa grammer secara universal dalam semua konteks. Peka konteks berarti ada aturan tambahan dalam konteks tertentu.

Di C #, misalnya, usingberarti sesuatu yang berbeda di using System;bagian atas file, daripada using (var sw = new StringWriter (...)). Contoh yang lebih relevan adalah kode berikut di dalam kode:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

Ada alasan praktis lain untuk tidak menggunakan ekspresi reguler untuk mengurai XML dan HTML yang sama sekali tidak ada hubungannya dengan teori ilmu komputer: ekspresi reguler Anda akan menjadi sangat rumit, atau salah.

Misalnya, sangat baik menulis ekspresi reguler untuk dicocokkan

<price>10.65</price>

Tetapi jika kode Anda benar, maka:

• Ini harus mengizinkan spasi setelah nama elemen di tag awal dan akhir

• Jika dokumen berada dalam namespace, maka harus mengizinkan awalan namespace apa pun untuk digunakan

• Itu mungkin harus mengizinkan dan mengabaikan atribut tidak dikenal yang muncul di tag awal (tergantung pada semantik kosakata tertentu)

• Ini mungkin perlu mengizinkan spasi sebelum dan sesudah nilai desimal (sekali lagi, bergantung pada aturan terperinci dari kosakata XML tertentu).

• Ini tidak boleh cocok dengan sesuatu yang terlihat seperti elemen, tetapi sebenarnya ada di komentar atau bagian CDATA (ini menjadi sangat penting jika ada kemungkinan data berbahaya mencoba menipu parser Anda).

• Mungkin perlu memberikan diagnostik jika input tidak valid.

Tentu saja beberapa di antaranya tergantung pada standar kualitas yang Anda terapkan. Kami melihat banyak masalah di StackOverflow dengan orang-orang yang harus membuat XML dengan cara tertentu (misalnya, tanpa spasi di tag) karena sedang dibaca oleh aplikasi yang mengharuskannya ditulis dengan cara tertentu. Jika kode Anda memiliki umur panjang apa pun, maka penting bahwa kode tersebut harus dapat memproses XML masuk yang ditulis dengan cara apa pun yang diizinkan oleh standar XML, dan bukan hanya satu contoh dokumen masukan yang Anda gunakan untuk menguji kode Anda.

Dalam pengertian teoritis murni, ekspresi reguler tidak mungkin mengurai XML. Mereka didefinisikan dengan cara yang tidak memungkinkan mereka mengingat keadaan sebelumnya, sehingga mencegah pencocokan yang tepat dari tag arbitrer, dan mereka tidak dapat menembus kedalaman penumpukan yang sewenang-wenang, karena penumpukan perlu dibangun ke dalam ekspresi reguler.

Namun, pengurai regex modern dibuat untuk kegunaannya bagi pengembang, bukan kepatuhannya pada definisi yang tepat. Dengan demikian, kami memiliki hal-hal seperti referensi balik dan rekursi yang memanfaatkan pengetahuan dari keadaan sebelumnya. Dengan menggunakan ini, sangatlah mudah untuk membuat regex yang dapat menjelajahi, memvalidasi, atau mengurai XML.

Pertimbangkan misalnya,

(?:
    <!\-\-[\S\s]*?\-\->
    |
    <([\w\-\.]+)[^>]*?
    (?:
        \/>
        |
        >
        (?:
            [^<]
            |
            (?R)
        )*
        <\/\1>
    )
)

Ini akan menemukan tag XML atau komentar berikutnya yang dibentuk dengan benar, dan itu hanya akan menemukannya jika seluruh isinya dibentuk dengan benar. (Ekspresi ini telah diuji menggunakan Notepad ++, yang menggunakan pustaka regex Boost C ++, yang mendekati PCRE.)

Begini cara kerjanya:

1. Potongan pertama cocok dengan komentar. Ini harus didahulukan sehingga akan menangani kode yang dikomentari yang jika tidak dapat menyebabkan hang up.
2. Jika tidak cocok, itu akan mencari awal tag. Perhatikan bahwa itu menggunakan tanda kurung untuk menangkap nama.
3. Tag ini akan diakhiri dengan a />, sehingga melengkapi tag, atau diakhiri dengan a >, dalam hal ini akan dilanjutkan dengan memeriksa konten tag.
4. Ini akan terus mem-parsing hingga mencapai a <, di mana titik itu akan berulang kembali ke awal ekspresi, memungkinkannya untuk menangani komentar atau tag baru.
5. Ini akan berlanjut melalui perulangan sampai ia tiba di salah satu akhir teks atau di bagian <yang tidak dapat diurai. Gagal mencocokkan, tentu saja, akan menyebabkan proses dimulai dari awal. Jika tidak, <mungkin ini adalah awal dari tag penutup untuk iterasi ini. Menggunakan referensi belakang di dalam tag penutup <\/\1>, itu akan cocok dengan tag pembuka untuk iterasi saat ini (kedalaman). Hanya ada satu grup penangkap, jadi pertandingan ini adalah masalah sederhana. Ini membuatnya tidak tergantung pada nama tag yang digunakan, meskipun Anda dapat memodifikasi grup penangkap untuk hanya menangkap tag tertentu, jika Anda perlu.
6. Pada titik ini, ia akan menendang keluar dari rekursi saat ini, naik ke level berikutnya atau diakhiri dengan pertandingan.

Contoh ini memecahkan masalah yang berhubungan dengan spasi atau mengidentifikasi konten yang relevan melalui penggunaan kelompok karakter yang hanya meniadakan <atau >, atau dalam kasus komentar, dengan menggunakan [\S\s], yang akan cocok dengan apa pun, termasuk carriage return dan baris baru, bahkan dalam satu baris mode, terus sampai mencapai a -->. Karenanya, ia hanya memperlakukan segala sesuatu sebagai valid hingga mencapai sesuatu yang bermakna.

Untuk sebagian besar tujuan, ekspresi reguler seperti ini tidak terlalu berguna. Ini akan memvalidasi bahwa XML dibentuk dengan benar, tetapi hanya itu yang akan benar-benar dilakukan, dan itu tidak memperhitungkan properti (meskipun ini akan menjadi tambahan yang mudah). Ini hanya sesederhana ini karena mengabaikan masalah dunia nyata seperti ini, serta definisi nama tag. Menyesuaikannya dengan penggunaan nyata akan membuatnya lebih seperti binatang buas. Secara umum, parser XML yang sebenarnya akan jauh lebih unggul. Yang ini mungkin paling cocok untuk mengajarkan cara kerja rekursi.

Singkat cerita: gunakan pengurai XML untuk pekerjaan nyata, dan gunakan ini jika Anda ingin bermain-main dengan regex.

Jangan parsing XML / HTML dengan regex, gunakan pengurai XML / HTML yang tepat dan kuat xpath pertanyaan.

teori:

Menurut teori kompilasi, XML / HTML tidak dapat diurai menggunakan regex berdasarkan mesin keadaan hingga . Karena konstruksi hierarki XML / HTML, Anda perlu menggunakan robot pushdown dan memanipulasi tata bahasa LALR menggunakan alat seperti YACC .

realLife © ® ™ alat sehari-hari di a kulit :

Anda dapat menggunakan salah satu dari berikut ini:

xmllint sering diinstal secara default dengan libxml2, xpath1 (periksa pembungkus saya untuk mendapatkan keluaran yang dibatasi baris baru

xmlstarlet dapat mengedit, memilih, mengubah ... Tidak diinstal secara default, xpath1

xpath diinstal melalui modul perl XML :: XPath, xpath1

xidel xpath3

saxon-lint proyek saya sendiri, membungkus perpustakaan Java Saxon-HE @Michael Kay, xpath3

atau Anda dapat menggunakan bahasa tingkat tinggi dan libs yang tepat, saya memikirkan:

pythons lxml( from lxml import etree)

perlIni XML::LibXML, XML::XPath, XML::Twig::XPath,HTML::TreeBuilder::XPath

rubi nokogiri, periksa contoh ini

php DOMXpath, periksa contoh ini

Periksa: Menggunakan ekspresi reguler dengan tag HTML