Bagaimana cara kerja parsing HTML jika mereka tidak menggunakan regexp?

Saya melihat pertanyaan setiap hari yang menanyakan bagaimana mengurai atau mengekstrak sesuatu dari beberapa string HTML dan jawaban / komentar pertama selalu "Jangan gunakan RegEx untuk mem-parsing HTML, jangan sampai Anda merasa marah!" (bagian terakhir itu terkadang dihilangkan).

Ini agak membingungkan bagi saya, saya selalu berpikir bahwa secara umum, cara terbaik untuk mengurai string rumit adalah dengan menggunakan ekspresi reguler. Jadi bagaimana cara kerja parser HTML? Bukankah itu menggunakan ekspresi reguler untuk mengurai.

Satu argumen khusus untuk menggunakan ekspresi reguler adalah tidak selalu ada alternatif penguraian (seperti JavaScript, di mana DOMDocument bukan opsi yang tersedia secara universal). jQuery, misalnya, tampaknya berhasil dengan baik menggunakan regex untuk mengonversi string HTML ke simpul DOM.

Tidak yakin apakah ke CW ini atau tidak, ini adalah pertanyaan asli yang ingin saya jawab dan tidak benar-benar dimaksudkan untuk menjadi utas diskusi.

Biasanya dengan menggunakan tokeniser. Spesifikasi draf HTML5 memiliki algoritme yang luas untuk menangani "HTML dunia nyata".

Jadi bagaimana cara kerja parser HTML? Bukankah itu menggunakan ekspresi reguler untuk mengurai?

Tidak.

Jika Anda kembali ke otak Anda pada teori kursus komputasi, jika Anda mengambilnya, atau kursus kompiler, atau sesuatu yang serupa, Anda mungkin ingat bahwa ada berbagai jenis bahasa dan model komputasi. Saya tidak memenuhi syarat untuk membahas semua detailnya, tetapi saya dapat meninjau beberapa poin utama bersama Anda.

Jenis bahasa & komputasi yang paling sederhana (untuk tujuan ini) adalah bahasa biasa. Ini dapat dibuat dengan ekspresi reguler, dan dikenali dengan automata hingga. Pada dasarnya, itu berarti bahwa string "parsing" dalam bahasa ini menggunakan status, tetapi bukan memori tambahan. HTML tentu bukan bahasa biasa. Jika Anda memikirkannya, daftar tag dapat disarangkan secara dalam. Misalnya, tabel dapat berisi tabel, dan setiap tabel dapat berisi banyak tag bertingkat. Dengan ekspresi reguler, Anda mungkin dapat memilih sepasang tag, tetapi tentu saja tidak ada yang bertingkat secara sembarangan.

Bahasa sederhana klasik yang tidak teratur dicocokkan dengan benar dengan tanda kurung. Mencoba sekuat tenaga, Anda tidak akan pernah bisa membuat ekspresi reguler (atau robot terbatas) yang akan selalu berhasil. Anda membutuhkan memori untuk melacak kedalaman sarang.

Mesin negara dengan tumpukan untuk memori adalah kekuatan berikutnya dari model komputasi. Ini disebut robot push-down, dan ini mengenali bahasa yang dihasilkan oleh tata bahasa bebas konteks. Di sini, kita dapat mengenali tanda kurung yang cocok dengan benar - memang, tumpukan adalah model memori yang sempurna untuk itu.

Nah, apakah ini cukup bagus untuk HTML? Sayangnya tidak. Mungkin untuk XML super-duper yang divalidasi dengan hati-hati, sebenarnya, di mana semua tag selalu berbaris sempurna. Dalam HTML dunia nyata, Anda dapat dengan mudah menemukan cuplikan seperti <b><i>wow!</b></i>. Ini jelas tidak bersarang, jadi untuk menguraikannya dengan benar, tumpukan tidak cukup kuat.

Tingkat komputasi berikutnya adalah bahasa yang dihasilkan oleh tata bahasa umum, dan dikenali oleh mesin Turing. Ini secara umum diterima sebagai model komputasi terkuat yang pernah ada - mesin status, dengan memori tambahan, yang memorinya dapat dimodifikasi di mana saja. Inilah yang bisa dilakukan bahasa pemrograman. Ini adalah tingkat kerumitan tempat tinggal HTML.

Untuk meringkas semuanya di sini dalam satu kalimat: untuk mengurai HTML umum, Anda memerlukan bahasa pemrograman yang sebenarnya, bukan ekspresi reguler.

HTML diuraikan dengan cara yang sama seperti bahasa lain diuraikan: lexing dan parsing. Langkah lexing memecah aliran karakter individu menjadi token yang bermakna. Langkah penguraian mengumpulkan token, menggunakan status dan memori, menjadi dokumen yang koheren secara logis yang dapat ditindaklanjuti.

Ekspresi reguler hanyalah salah satu bentuk pengurai. Pengurai HTML yang jujur ​​akan jauh lebih rumit daripada yang dapat diekspresikan dalam ekspresi reguler, menggunakan penurunan rekursif , prediksi, dan beberapa teknik lain untuk menafsirkan teks dengan benar. Jika Anda benar-benar ingin masuk ke dalamnya, Anda dapat memeriksa lex & yacc dan alat serupa.

Larangan penggunaan regex untuk penguraian HTML mungkin harus ditulis dengan lebih benar sebagai: "Jangan gunakan ekspresi reguler yang naif untuk mengurai HTML ..." (jangan sampai kamu merasa marah) "... dan perlakukan hasil dengan hati-hati." Untuk tujuan spesifik tertentu, regex mungkin cukup memadai, tetapi Anda harus sangat berhati-hati untuk mengetahui batasan regex Anda dan berhati-hati sesuai dengan sumber teks yang Anda parsing (mis., Jika itu masukan pengguna, hati-hati memang).

Parsing HTML adalah transformasi teks linier menjadi struktur pohon. Ekspresi reguler umumnya tidak dapat menangani struktur pohon. Ekspresi reguler yang Anda perlukan di setiap titik untuk mendapatkan token berikutnya selalu berubah. Anda dapat menggunakan ekspresi reguler dalam parser, tetapi Anda akan membutuhkan seluruh larik ekspresi reguler untuk setiap kemungkinan status penguraian.

Jika Anda ingin mendapatkan solusi 100%: Anda perlu menulis kode kustom Anda sendiri yang mengulang-ulang HTML karakter demi karakter dan Anda perlu memiliki logika yang sangat banyak untuk menentukan apakah Anda harus menghentikan node saat ini dan memulai lanjut.

Alasannya adalah ini adalah HTML yang valid:

<ul>
<li>One
<li>Two
<li>Three
</ul>

Tapi begitu juga ini:

<ul>
<li>One</li>
<li>Two</li>
<li>Three</li>
</ul>

Jika Anda setuju dengan "solusi 90%": Maka menggunakan pengurai XML untuk memuat dokumen tidak masalah. Atau menggunakan Regex (meskipun xml lebih mudah jika Anda kemudian menguasai konten).