Mengapa menggunakan lexer / parser pada data biner begitu salah?

13

Saya sering bekerja dengan lexer / parser , sebagai lawan dari parser combinator dan melihat orang-orang yang tidak pernah mengambil kelas dalam parsing, bertanya tentang parsing data biner. Biasanya data tidak hanya biner tetapi juga peka konteks. Ini pada dasarnya menyebabkan hanya memiliki satu jenis token, token untuk byte.

Adakah yang bisa menjelaskan mengapa mem-parsing data biner dengan lexer / parser sangat salah dengan kejelasan yang cukup untuk seorang siswa CS yang tidak mengambil kelas parsing, tetapi dengan pijakan pada teori?

Guy Coder
sumber
Dugaan saya adalah bahwa lexer mungkin tidak dapat menemukan token yang lebih kecil dari byte / kata. Jika Anda membutuhkannya, Erlang memiliki dukungan yang sangat baik untuk parsing binari: user.it.uu.se/~pergu/papers/JFP_06.pdf
Dave Clarke
3
Saya tidak berpikir bahwa asumsi Anda benar. Jelas, data non-konteks-bebas menimbulkan masalah (yang sering dapat dielakkan), tetapi Anda dapat memberikan tata bahasa untuk kata-kata biner. Anda mungkin tidak akan dapat menggunakan generator parser populer, karena mereka menganggap input teks. Tapi itu masalah lain.
Raphael
@GuyCoder: Banyak contoh klasik untuk tata bahasa menggunakan alfabet biner, misalnya . S0S10S
Raphael
1
By the way: "hanya memiliki satu jenis token, token untuk byte." - tidak, itu akan membuat token byte. 28
Raphael
5
@GuyCoder: Semua data yang dihasilkan oleh program lain dapat dijelaskan oleh tata bahasa. Namun, itu mungkin bukan konteks bebas.
Raphael

Jawaban:

10

Pada prinsipnya, tidak ada yang salah.

Dalam praktek,

  • kebanyakan format data non-tekstual yang saya tahu tidak bebas konteks dan karenanya tidak cocok untuk generator parser umum. Alasan paling umum adalah bahwa mereka memiliki bidang panjang memberikan berapa kali suatu produksi harus ada.

    Jelas, memiliki bahasa yang bebas konteks tidak pernah mencegah penggunaan generator parser: kami mengurai superset bahasa dan kemudian menggunakan aturan semantik untuk menguranginya sesuai dengan yang kita inginkan. Pendekatan itu dapat digunakan untuk format non-tekstual jika hasilnya akan deterministik. Masalahnya adalah menemukan hal lain selain jumlah yang akan disinkronkan karena sebagian besar format biner memungkinkan data sewenang-wenang untuk disematkan; bidang panjang memberi tahu Anda berapa banyak.

    Anda kemudian dapat mulai memainkan trik seperti memiliki lexer yang dapat ditulis secara manual untuk mengatasinya dengan umpan balik dari pengurai (lex / yacc penanganan C menggunakan trik semacam itu untuk menangani typedef, misalnya). Tapi kemudian kita sampai pada poin kedua.

  • sebagian besar format data non-tekstual cukup sederhana (bahkan jika mereka tidak bebas konteks). Ketika jumlah yang disebutkan di atas diabaikan, bahasa teratur, LL1 paling buruk, dan karenanya cocok untuk teknik penguraian manual. Dan menangani jumlah sangat mudah untuk teknik parsing manual seperti keturunan rekursif.

Pemrogram
sumber
"Bahasa-bahasa biasa" Jika "tetapi juga konteks sensitif 'diambil untuk berarti data biner adalah tata bahasa, saya akan menjelaskan dalam jawabannya. Itu memang menjadi bagian dari masalah; orang cenderung berpikir tata bahasa atau bahasa biasa begitu Anda sebutkan parser
Guy Coder
7

Mari kita kategorikan data menjadi tiga kategori: data dapat dibaca oleh manusia (biasanya teks, bervariasi dari buku ke program), data yang dimaksudkan untuk dibaca oleh komputer dan data lainnya (parsing gambar atau suara).

Untuk kategori pertama, kita perlu mengolahnya menjadi sesuatu yang dapat digunakan komputer. Karena bahasa yang digunakan oleh manusia umumnya dapat ditangkap dengan relatif baik oleh parser, kami biasanya menggunakan parser untuk ini.

Contoh data dalam kategori ketiga adalah gambar yang dipindai dari halaman buku yang ingin Anda parsing menjadi teks. Untuk kategori ini, Anda hampir selalu membutuhkan pengetahuan yang sangat spesifik tentang input Anda, dan oleh karena itu Anda memerlukan program khusus untuk menguraikannya. Teknologi parsing standar tidak akan membuat Anda jauh di sini.

Pertanyaan Anda adalah tentang kategori kedua: jika kami memiliki data dalam biner, hampir selalu merupakan produk dari program komputer, yang ditujukan untuk program komputer lain. Ini juga berarti bahwa format data yang dipilih oleh program yang bertanggung jawab untuk pembuatannya.

Program komputer hampir selalu menghasilkan data dalam format yang memiliki struktur yang jelas. Jika kami mengurai beberapa input, kami pada dasarnya mencoba mencari tahu struktur input. Dengan data biner, struktur ini umumnya sangat sederhana dan mudah diurai oleh komputer.

Dengan kata lain, biasanya agak sia-sia untuk mengetahui struktur input yang Anda sudah tahu strukturnya. Karena parsing tidak gratis (butuh waktu dan menambah kompleksitas pada program Anda), inilah mengapa menggunakan lexers / parser pada data biner adalah 'sangat salah'.

Alex ten Brink
sumber
2
Ini adalah perspektif yang bagus, tetapi saya merasa seperti itu tidak menjawab pertanyaan.
Raphael
LANGSEC: Language-theoretic Securitymenawarkan perspektif yang menarik. Salah satu artikel berbicara tentang "mesin aneh": parser ad hoc dari format yang dikenal membentuk fasilitas penanganan input dari suatu sistem. Mereka mungkin tidak benar-benar berfungsi sebagaimana dimaksud. Karena asumsi yang salah, mesin yang rusak akan melakukan transisi keadaan yang tidak diantisipasi diberikan input yang dibuat khusus, melakukan perhitungan yang seharusnya tidak mungkin. Ini menciptakan vektor serangan. Menggunakan tata bahasa formal akan menghasilkan algoritma yang terbukti benar.
Matheus Moreira
0

Sebuah+b×(c-d)+e(+ a (* b (- c d)) e)a b c d - * + e +. Notasi matematika yang biasa memiliki redundansi lebih dari Lisp (yang membutuhkan lebih banyak tanda kurung, tetapi mendapatkan variabel arities gratis, sehingga memerlukan lebih sedikit simbol untuk mengekspresikan ekspresi menggunakan arities besar) atau RPL (yang tidak pernah membutuhkan tanda kurung). Redundansi seperti itu jarang berguna untuk komputer - dan di mana itu, yaitu ketika ada kemungkinan kesalahan dalam data, logika koreksi kesalahan biasanya disimpan terpisah dari arti fungsional data, misalnya menggunakan kode koreksi kesalahan yang berlaku untuk sewenang-wenang. urutan byte terlepas dari apa yang mereka wakili.

Format biner biasanya dirancang untuk menjadi ringkas, yang berarti beberapa fitur bahasa sederhana seperti tanda kurung seimbang yang dapat diekspresikan oleh tata bahasa bebas konteks. Lebih jauh lagi, seringkali berguna untuk representasi biner data menjadi kanonik, yaitu untuk memiliki representasi tunggal dari setiap objek. Ini mengesampingkan fitur yang kadang-kadang berlebihan seperti tanda kurung. Konsekuensi lain, kurang terpuji dari memiliki redundansi kurang adalah bahwa jika setiap input secara sintaksis benar, menghemat kesalahan pengecekan.

Faktor lain terhadap parser nontrivial untuk data biner adalah bahwa banyak format biner dirancang untuk diuraikan oleh kode tingkat rendah yang suka beroperasi dalam memori konstan dengan sedikit overhead. Ukuran tetap lebih disukai bila berlaku untuk memungkinkan pengulangan elemen secara sewenang-wenang. Format seperti TLV yang memungkinkan parser kiri ke kanan untuk mengalokasikan jumlah memori yang tepat untuk suatu objek terlebih dahulu, kemudian membaca representasi objek. Mem-parsing dari kiri ke kanan adalah keuntungan karena memungkinkan data diproses sebagaimana mestinya, tanpa buffer perantara.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Apa gunanya dua paragraf pertama? Bahkan jika Anda tidak memiliki redundansi, Anda membutuhkan parser. Juga, paragraf pertama salah: ada contoh di mana semua kata diperbolehkan tetapi Anda parse untuk mendapatkan struktur (misalnya prediksi struktur sekunder RNA).
Raphael
@ Raphael Pengurai non-sepele biasanya menyiratkan redundansi (ya, seperti yang Anda tunjukkan, ada pengecualian). Saya belum mempertimbangkan bahasa yang dirancang untuk manusia maupun komputer, ini adalah contoh yang menarik. Dua paragraf pertama membahas perbedaan khas antara format biner dan yang dapat dibaca manusia (makna khas bahwa jika Anda mencari pengecualian, Anda akan menemukannya).
Gilles 'SO- stop being evil'