Mengapa menggunakan lexer / parser pada data biner begitu salah?

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?

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.

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'.

$a + b \times (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.