Nama untuk jenis parser ini, ATAU mengapa tidak ada

Pengurai konvensional mengkonsumsi seluruh input mereka dan menghasilkan pohon pengurai tunggal. Saya mencari yang mengkonsumsi aliran kontinu dan menghasilkan hutan parse [ edit: lihat diskusi dalam komentar mengenai mengapa penggunaan istilah itu mungkin tidak konvensional ]. Perasaan saya mengatakan bahwa saya tidak bisa menjadi orang pertama yang membutuhkan (atau berpikir saya perlu) pengurai seperti itu, tetapi saya telah mencari selama berbulan-bulan tanpa hasil.

Saya menyadari bahwa saya mungkin terperangkap oleh masalah XY. Tujuan utama saya adalah mengurai aliran teks, mengabaikan sebagian besar, dan menghasilkan aliran pohon pengurai dari bagian yang dikenali.

Jadi pertanyaan saya adalah bersyarat: jika ada kelas parser dengan karakteristik ini, apa namanya? Dan jika tidak, mengapa tidak? Apa alternatifnya? Mungkin saya kehilangan beberapa cara saya dapat membuat parser konvensional melakukan apa yang saya inginkan.

Parser yang mengembalikan hasil (parsial) sebelum seluruh input telah dikonsumsi disebut Parser tambahan . Penguraian tambahan bisa sulit jika ada ambiguitas lokal dalam tata bahasa yang hanya diputuskan kemudian dalam input. Kesulitan lain adalah berpura-pura bagian-bagian dari pohon parse yang belum tercapai.

Pengurai yang mengembalikan hutan dari semua pohon parse yang mungkin - yaitu, mengembalikan pohon parse untuk setiap kemungkinan derivasi tata bahasa yang ambigu - disebut ... Saya tidak yakin apakah benda-benda ini memiliki nama. Saya tahu bahwa generator pengurai Marpa mampu melakukan ini, tetapi pengurai berbasis Earley atau GLR mana pun harus mampu melakukannya.

Namun, Anda sepertinya tidak menginginkan hal itu. Anda memiliki aliran dengan banyak dokumen tertanam, dengan sampah di antaranya:

 garbagegarbage{key:42}garbagegarbage[1,2,3]{id:0}garbage...

Anda sepertinya menginginkan parser yang melompati sampah, dan (malas) menghasilkan urutan AST untuk setiap dokumen. Ini bisa dianggap sebagai parser tambahan dalam arti yang paling umum. Tapi Anda benar-benar akan menerapkan loop seperti ini:

while stream is not empty:
  try:
    yield parse_document(stream at current position)
  except:
    advance position in stream by 1 character or token

The parse_docmentFungsi kemudian akan menjadi konvensional, non-tambahan parser. Ada sedikit kesulitan untuk memastikan bahwa Anda telah membaca cukup aliran input untuk penguraian yang sukses. Bagaimana ini dapat ditangani tergantung pada jenis parser yang Anda gunakan. Kemungkinan termasuk menumbuhkan penyangga pada kesalahan parse tertentu, atau menggunakan tokenization malas.

Token malas mungkin merupakan solusi paling elegan karena aliran input Anda. Alih-alih memiliki fase lexer menghasilkan daftar token yang tetap, parser akan dengan malas meminta token berikutnya dari panggilan balik lexer ^[1] . Lexer kemudian akan mengkonsumsi sebanyak aliran sesuai kebutuhan. Dengan cara ini, pengurai hanya bisa gagal ketika akhir sebenarnya dari aliran tercapai, atau ketika kesalahan parse nyata terjadi (yaitu kita mulai mengurai saat masih dalam sampah).

^{[1] lexer yang digerakkan oleh panggilan balik adalah ide yang bagus dalam konteks lain juga, karena ini dapat menghindari beberapa masalah dengan pencocokan token terpanjang .}

Jika Anda tahu jenis dokumen apa yang Anda cari, Anda dapat mengoptimalkan lompatan berhenti hanya di lokasi yang menjanjikan. Misalnya dokumen JSON selalu dimulai dengan karakter {atau [. Karenanya, sampah adalah string apa pun yang tidak mengandung karakter ini.

Tidak ada satu nama khusus untuk parser yang melakukan ini. Tapi saya akan menyoroti satu algoritma yang melakukan ini: parsing dengan turunannya .

Mengkonsumsi input, satu token pada satu waktu. Ini akan menghasilkan hutan parse pada akhir input. Atau, Anda juga bisa mendapatkan seluruh hutan parse saat berada di tengah parsing (parsing parsial ).

Parsing dengan turunan menangani tata bahasa bebas konteks, dan akan menghasilkan hutan parse untuk tata bahasa yang ambigu.

Benar-benar teori yang elegan, tetapi baru dalam masa pertumbuhan, dan tidak banyak digunakan. Matt Might memiliki daftar tautan ke berbagai implementasi di Scala / Racket / dll.

Teori ini lebih mudah dipelajari jika Anda mulai dengan pengenalan dengan turunan (yaitu, mulai dengan mengambil turunan dari bahasa , dengan tujuan mengenali beberapa input untuk menentukan apakah itu valid atau tidak), dan kemudian mengubah program untuk menguraikan turunan ( yaitu, ubah jadi alih-alih mengambil turunan bahasa , ia mengambil turunan parser , dan menghitung hutan parse).

Jauh dari ideal, tetapi saya telah melihatnya dilakukan lebih dari sekali: pada setiap jalur input coba diuraikan. jika gagal, pertahankan baris dan tambahkan yang berikutnya. Dalam pseudocode:

buffer = ''
for each line from input:
    buffer = buffer + line
    if can parse buffer:
        emit tree
        buffer = ''

Masalah besar adalah bahwa dalam beberapa bahasa Anda tidak dapat mengetahui apakah suatu ekspresi lengkap sebelum membaca baris berikutnya. Dalam hal ini, Anda tampaknya dapat membaca yang berikutnya, dan memeriksa apakah itu awal yang valid, atau kelanjutan yang valid ... Tetapi untuk itu Anda memerlukan sintaks bahasa yang tepat

Lebih buruk lagi, dalam bahasa-bahasa itu tidak sulit untuk membuat kasus patologis yang tidak dapat diuraikan sampai akhir file, bahkan jika itu bukan pernyataan panjang.

Pendeknya

Tampaknya solusi cepat untuk masalah Anda adalah menentukan REGEX, atau FSA (finite state automaton), yang mengenali semua kemungkinan awal dokumen (positif palsu diizinkan, yang tidak akan benar-benar sesuai dengan dokumen). Anda kemudian dapat menjalankannya dengan sangat cepat pada input Anda untuk mengidentifikasi tempat berikutnya di mana dokumen dapat dimulai dengan beberapa kesalahan. Ini dapat menyebabkan beberapa posisi yang salah untuk memulai dokumen, tetapi mereka akan dikenali oleh pengurai dan ditinggalkan.

Jadi Finite State Automaton mungkin adalah nama pengurai yang Anda cari. :)

Masalah

Selalu sulit untuk memahami masalah praktis, terutama ketika kosa kata mungkin memiliki banyak interpretasi. Kata parse forest dibuat (afaik) untuk parsing Context-Free (CF) dari kalimat-kalimat ambigu yang memiliki beberapa pohon parse. Ini dapat digeneralisasi agak untuk mengurai kisi kalimat, atau jenis tata bahasa lainnya. Karenanya semua jawaban tentang Earley, GLR, Marpa dan parser turunan (ada banyak lainnya) yang tidak relevan dalam kasus ini.

Tapi itu rupanya bukan yang Anda pikirkan. Anda ingin mengurai string unik yang merupakan urutan dokumen yang tidak ambigu, dan mendapatkan parse-tree untuk masing-masing , atau semacam representasi terstruktur, karena Anda tidak benar-benar mengatakan bagaimana sintaks dokumen Anda didefinisikan, di mana ia berdiri dari sudut pandang bahasa formal. Apa yang Anda miliki adalah algoritma dan tabel yang akan melakukan pekerjaan parsing ketika dimulai pada awal dokumen. Jadilah itu.

Masalah sebenarnya adalah aliran dokumen Anda mengandung banyak sampah yang memisahkan dokumen. Dan tampaknya kesulitan Anda untuk memindai sampah ini cukup cepat. Teknik Anda saat ini adalah mulai dari awal, dan mencoba memindai dari karakter pertama, dan lewati untuk memulai kembali di karakter berikutnya setiap kali gagal, sampai Anda mendapatkan seluruh dokumen dipindai. Kemudian Anda ulangi pernyataan dari karakter pertama setelah dokumen dipindai.

Itu juga solusi yang disarankan oleh @amon di bagian kedua dari jawabannya .

Ini mungkin bukan solusi yang sangat cepat (saya tidak punya cara untuk menguji), karena tidak mungkin kode parser dioptimalkan menjadi sangat efisien dimulai pada awal dokumen. Dalam penggunaan normal, ia melakukan ini hanya sekali, sehingga ini bukan hot spot dari sudut pandang optimasi. Karenanya, kebahagiaan Anda yang moderat dengan solusi ini tidak terlalu mengejutkan.

Jadi yang Anda butuhkan adalah algoritma yang dapat dengan cepat menemukan awal dokumen yang dimulai dengan banyak sampah. Dan Anda beruntung: algoritma seperti itu memang ada. Dan saya yakin Anda tahu itu: itu disebut mencari REGEX.

Solusi sederhana

Yang harus Anda lakukan adalah menganalisis spesifikasi dokumen Anda untuk menemukan bagaimana dokumen ini dimulai. Saya tidak bisa memberi tahu Anda dengan pasti bagaimana, karena saya tidak yakin bagaimana spesifikasi sintaksisnya diatur secara formal. Mungkin mereka semua mulai dengan beberapa kata dari daftar yang terbatas, mungkin dicampur dengan beberapa tanda baca atau angka. Itu untuk Anda periksa.

Apa yang harus Anda lakukan adalah mendefinisikan otomat keadaan terbatas (FSA), atau setara dengan kebanyakan programmer ekspresi reguler (REGEX) yang dapat mengenali beberapa karakter pertama dokumen: semakin banyak, semakin baik, tetapi tidak harus sangat besar (karena itu mungkin membutuhkan waktu dan ruang). Ini harus relatif mudah dilakukan dari spesifikasi dokumen Anda, dan mungkin dapat dilakukan secara otomatis dengan program yang membaca spesifikasi dokumen Anda.

Setelah Anda menghasilkan regexp Anda, Anda dapat menjalankannya pada aliran input Anda untuk menjadi sangat cepat ke awal dokumen pertama (atau selanjutnya) Anda sebagai berikut:

Saya berasumsi:
- docstartadalah regex yang cocok dengan awal semua dokumen
- search(regex, stream)adalah fungsi yang mencari streamsubstring yang cocok regex. Ketika kembali, aliran direduksi menjadi subfiks sufiks mulai dari awal substring pencocokan pertama, atau ke aliran kosong tidak ditemukan kecocokan.
- parse(stream)mencoba mengurai dokumen dari awal aliran (apa yang tersisa dari itu), dan mengembalikan pohon pengurai dalam format apa pun, atau gagal. Ketika kembali, aliran dikurangi ke subtream suffix-nya mulai dari posisi segera setelah akhir dokumen yang diuraikan. Ini memanggil pengecualian jika parse gagal.

forest = empty_forest
search(docstart, stream)
while stream is not empty:
  try:
    forest = forest + parse(stream)
  except
    remove first character from stream
  search(docstart, stream)

Perhatikan bahwa penghapusan karakter pertama diperlukan agar pencarian berikutnya tidak menemukan lagi kecocokan yang sama.

Tentu saja, pemendekan aliran adalah gambar. Mungkin hanya indeks di sungai.

Catatan terakhir adalah bahwa regex Anda tidak perlu terlalu akurat, asalkan itu mengenali semua awal. Jika kadang-kadang mengenali string yang tidak bisa menjadi awal dokumen (false positive), maka satu-satunya hukuman adalah biaya satu panggilan tidak berguna ke parser.

Sehingga mungkin dapat membantu menyederhanakan regex, jika berguna.

Tentang kemungkinan solusi yang lebih cepat

Solusi di atas harus bekerja dengan cukup baik dalam banyak kasus. Namun, jika Anda benar-benar memiliki banyak file sampah dan terabyte untuk diproses, mungkin ada algoritma lain yang berjalan lebih cepat.

Idenya berasal dari algoritma pencarian string Boyer-Moore . Algoritma ini dapat mencari aliran untuk string tunggal dengan sangat cepat karena menggunakan analisis struktural dari string untuk melewatkan membaca sebagian besar aliran, melompati fragmen tanpa melihatnya. Ini adalah algoritma pencarian tercepat untuk satu string.

Kesulitannya adalah bahwa adaptasinya untuk mencari regex, daripada string tunggal, tampaknya sangat halus dan mungkin tidak berfungsi juga, tergantung pada fitur regex yang Anda pertimbangkan. Yang pada gilirannya mungkin tergantung pada sintaks dokumen yang Anda parsing. Tetapi jangan terlalu mempercayai saya tentang hal ini karena saya tidak punya waktu untuk membaca dokumen-dokumen yang saya temukan dengan cermat.

Saya meninggalkan Anda dengan satu atau dua petunjuk yang saya temukan di web, termasuk satu yang kelihatannya merupakan makalah penelitian wasit , tetapi Anda harus menganggap ini sebagai lebih spekulatif, mungkin penelitian, untuk dipertimbangkan hanya jika Anda memiliki masalah kinerja yang kuat. Dan mungkin tidak ada program rak yang akan melakukannya.

Apa yang Anda gambarkan dapat digambarkan sebagai SAX vs SOM.

SAX - (Simple API for XML) adalah parser akses berurutan acara API yang dikembangkan oleh milis XML-DEV untuk dokumen XML.

SOM - (XML Schema Object Model) akses acak ke dalam representasi memori dari file XML

Ada implementasi dari kedua jenis di C #, dan Java, dan mungkin banyak lagi. Biasanya XSD atau DTD adalah opsional.

Kegembiraan SAX adalah overhead memori yang rendah, yang sangat bagus untuk file XML besar. Imbalannya adalah bahwa akses acak menggunakan SAX tidak ada atau lambat, dan lebih buruk waktu pengembangan biasanya jauh lebih besar daripada dengan SOM. Masalah yang jelas dengan SOM adalah persyaratan RAM yang berpotensi besar.

Jawaban ini tidak berlaku untuk semua platform dan semua bahasa.