Bagaimana cara merekonstruksi hutan pohon sintaksis dari vektor Earley?

Menggunakan vektor Earley sebagai pengenal cukup mudah: ketika akhir string tercapai, Anda hanya perlu memeriksa untuk produksi aksiomatik lengkap mulai dari posisi 0. Jika Anda memiliki setidaknya satu, maka string diterima.

Menggunakan vektor Earley untuk merekonstruksi pohon parsing kurang jelas. Sebenarnya, saya tidak tahu bagaimana prosedur algoritmik akan bekerja, apalagi referensi yang saya temukan tidak jelas atau super-teknis. Adakah yang bisa menjelaskannya?

Saya menggunakan terminologi dan notasi dari makalah Earley . Mungkin deskripsi yang Anda baca berbeda.

Tampaknya sering bahwa algoritma parsing CF umum pertama kali disajikan dalam bentuk pengenal, dan kemudian manajemen informasi yang diperlukan untuk benar-benar membangun pohon parse dan hutan parse semacam ditambahkan sebagai renungan. Salah satu alasannya adalah bahwa menjaga informasi yang dibutuhkan untuk membangun hutan bersama membutuhkan ruang kubik mana adalah panjang dari string input yang diuraikan, tetapi persyaratan ruang hanya kuadrat untuk pengakuan , ketika informasi ini tidak disimpan. Alasan peningkatan kompleksitas ruang ini cukup sederhana: ukuran hutan parse bisa kubik.n O ( n 2$O(n^3)$$n$$O(n^2)$

Kompleksitas waktu kasus terburuk adalah , seperti yang diketahui.$O(n^3)$

Referensi terbaik untuk algoritma Earley tentu saja adalah makalah Earley , tetapi tidak terlalu eksplisit tentang membangun hutan parse. Ini sebenarnya bisa menjadi bisnis yang berantakan, jauh lebih banyak daripada yang dibicarakan dengan cepat bagian 7 halaman 101. Memang benar, Earley tidak berbicara tentang hutan parse, atau hutan, tetapi tentang " representasi faktor dari semua pohon parsing yang mungkin ". Dan ada alasan bagus untuk itu: jika dia mencoba untuk menghasilkan hutan sesuai dengan tata bahasanya, kompleksitas ruangnya (maka waktu) yang terikat akan naik ke mana adalah ukuran yang terpanjang memerintah sisi kanan. Inilah sebabnya mengapa algoritma lain menggunakan tata bahasa dalam bentuk biner (tidak harus Chomsky Normal Form (CNF)).$O(n^{s+1})$$s$

Sebenarnya, Earley menggunakan bentuk biner secara implisit , karena itu diperlukan untuk kompleksitas waktu kubik. Ini adalah salah satu peran utama dari titik aturan di negara bagian. Tetapi bentuk biner tersirat ini menghasilkan parse dan hutan sesuai dengan tata bahasa biner, bukan dengan yang asli, yang, saya khawatirkan, merupakan sumber utama ketidakjelasan. Ini dirinci lebih lanjut di bawah ini.

Salah satu cara yang baik untuk memahami bagaimana hutan diperoleh mungkin dengan melihatnya dalam kasus yang lebih sederhana, algoritma CYK . Itu juga sering digambarkan sebagai pengenal, dan aspek parser ditambahkan di akhir. Anda dapat melihat deskripsi di wikipedia. Informasi yang dibutuhkan untuk membangun hutan adalah apa yang mereka simpan di tabel "backpointers". Backpointer pada dasarnya adalah pointer ke substring (simbol terkait) yang membentuk konstituen string sesuai dengan beberapa aturan. Mereka memberikan semua cara yang mungkin untuk mengurai substring. Ingat bahwa CYK menggunakan bentuk biner, biasanya CNF, sehingga semuanya lebih sederhana. Pengurai CYK pada dasarnya memiliki struktur pemrograman dinamis yang sama dengan Earley, tetapi jauh lebih sederhana. Jadi, memahaminya dengan baik bisa sangat membantu.

Kembali ke algoritme Earley, saya tidak percaya Anda membutuhkan vektor Earley untuk memutuskan penerimaan atau untuk membangun pohon dan hutan parse. Apa yang disebut Earley sebagai vektor dalam makalahnya hanya muncul di halaman 97, di paragraf ketiga implementasi. Ini hanya perangkat untuk mempercepat pencarian status menunjuk kembali pada posisi string tertentu k, untuk mendapatkan kompleksitas yang lebih baik. Tetapi semua informasi dalam set negara, diimplementasikan sebagai daftar negara. Namun, informasi ini tidak cukup untuk membangun hutan pohon parse, karena algoritme tidak melacak cara negara dapat memperoleh. Memang, vektor tersebut bahkan digunakan untuk secara efisien membuang suatu keadaan yang sudah ditemukan, terlepas dari bagaimana ia ditemukan.

Dalam bagian 7 artikel Earley, ia menjelaskan bahwa untuk "membuat pengenal menjadi parser", yaitu untuk dapat memulihkan pohon parse, perlu untuk melacak cara penyelesaian dilakukan.

Setiap kali kami melakukan operasi pelengkap dengan menambahkan status (mengabaikan lookahead) kita membangun sebuah pointer dari instance dalam status itu ke status yang menyebabkan kami melakukan operasi. Ini menunjukkan bahwa diuraikan sebagai . Dalam kasus D adalah ambigu akan ada satu set pointer dari itu, satu untuk setiap operasi yang melengkapi yang menyebabkan akan ditambahkan ke set negara tertentu. Setiap simbol dalam juga akan memiliki pointer dari itu (kecuali terminal), dan sebagainya, sehingga mewakili pohon derivasi untuk .D D → γ $E\rightarrow \alpha D.\beta \; g$$D$D γ E → a D . $D\rightarrow \gamma. \; f$$D$$\gamma$γ $E\rightarrow \alpha D.\beta \; g$$\gamma$$D$

Perhatikan bahwa dalam teks ini, dan adalah indeks dalam string parsing, yang menunjukkan di mana pengenalan aturan sisi kiri dimulai (seperti simbol sisi kanan telah diprediksi. Jadi adalah indeks string di mana pengakuan dari dimulai, dan berakhir pada indeks . "Ini pointer penyelesaian" adalah setara Earley dari backpoint yang dijelaskan (tidak terlalu baik di wikipedia) untuk versi parser CYK.g f D → gamma $f$$g$$f$$D\rightarrow \gamma$$g$

Dari penunjuk seperti itu (seperti yang dijelaskan dalam kutipan) kita tahu bahwa dalam contoh instance sendiri dapat dikembangkan menjadi pohon (atau hutan) yang mem-parsing string input dari indeks ke indeks , yang kita catat . Simpul tepat di bawah diberikan oleh aturan . Dengan mencari penyelesaian yang mengarah ke kita kemudian dapat menemukan petunjuk semacam itu yang memberi tahu bagaimana simbol terakhir dariE → a D . $D$$E\rightarrow \alpha D.\beta \; g$$w$$f+1$$g$$w_{f+1:g}$$D$$D\rightarrow \gamma$$D\rightarrow \gamma. \; f$$D$diperoleh, dan karenanya lebih banyak informasi tentang kemungkinan pohon parse. Juga dengan melihat penyelesaian yang mengenali simbol sebelum terakhir di set negara bagian sebelumnya, Anda menemukan bagaimana itu diperoleh, dan sebagainya.

Dengan asumsi Anda menyimpan semua pointer yang diperlukan seperti yang ditunjukkan di koran, Anda bisa mendapatkan semua representasi pohon bersama mulai dari simbol terakhir yang dikenali oleh parser, yang tentu saja merupakan simbol awal tata bahasa.

Tapi saya juga melewatkan bagian yang berantakan . Misalkan Anda memiliki aturan , yang saya pilih dengan sisi kanan lebih dari 2 simbol, dan aturan lain , untuk tata bahasa yang ambigu.$U\rightarrow XYZ$$W\rightarrow UV$

Mungkin saja parser akan menguraikan ke , ke dan keduanya dan ke . Jadi, dengan aturan , Kedua dan parse ke .$w_{f+1:g}$$X$$w_{g+1:h}$$Y$$w_{h+1:i}$$w_{h+1:j}$$Z$$U\rightarrow XYZ$$w_{f+1:i}$$w_{f+1:j}$$U$

Maka itu juga mungkin bahwa kedua dan baik parse ke . Kemudian, dengan aturan , string mengurai menjadi dengan dua cara yang berbeda, yang sesuai dengan ambiguitas tata bahasa. w j + 1 : k V W → U V w f + 1 : k$w_{i+1:k}$$w_{j+1:k}$$V$$W\rightarrow UV$$w_{f+1:k}$$W$

Tentu saja, untuk menghindari pengulangan perhitungan, algoritma Earley akan berusaha untuk membagikan sebanyak mungkin dari dua perhitungan penguraian. Apa yang akan benar-benar berbagi jelas pengakuan (dan parsing) dari dan ke dan . Tapi itu sebenarnya akan melakukan sedikit lebih banyak: itu juga akan berbagi awal dari dua parses berbeda yang mengenali dengan aturan . Maksud saya adalah bahwa negara akan ditemukan hanya satu kali (sehubungan dengan apa yang saya uraikan), dalam keadaan ditetapkan . Ini akan menjadi bagian umum dari dua parse. Tentu saja, hal-hal sementara akan menyimpang saat menguraikan w g + 1 : h X Y U U → X Y Z U → X Y . $w_{f+1:g}$$w_{g+1:h}$$X$$Y$$U$$U\rightarrow XYZ$S h Z W → U V $U\rightarrow XY.Z \; f$$S_h$$Z$ karena mereka sesuai dengan substring distict, sampai mereka menyatu lagi ketika semuanya mengurai menjadi W, ketika negara diproduksi dua kali dalam keadaan set .S $W\rightarrow UV. \; f$$S_k$

Jadi hutan pohon sintaksis bisa menjadi sangat aneh, dengan jenis pohon kembar siam yang dapat berbagi dua tepi pertama dari beberapa simpul, tetapi bukan tepi ketiga. Dengan kata lain, itu mungkin struktur yang sangat canggung. Ini mungkin menjelaskan mengapa Earley menyebutnya " representasi yang diperhitungkan dari semua pohon parse yang mungkin ", tanpa lebih spesifik.

Setiap upaya untuk memisahkan siam siam dengan pembedahan, tanpa mengubah tata bahasa akan menghasilkan peningkatan kompleksitas. Cara yang tepat untuk melakukannya adalah dengan meng-binari tata bahasa.

Saya harap ini akan membantu Anda. Biarkan aku tahu. Tapi saya bersikeras bahwa pemahaman yang baik tentang penguraian CYK dapat membantu. Ada algoritma lain, lebih sederhana dari Earley, yang dapat menguraikan semua bahasa CF secara efisien.

Anda dapat menemukan info lebih umum tentang masalah hutan parse ini dalam dua jawaban lain yang saya berikan: /cstheory/7374#18006 dan https://linguistics.stackexchange.com/questions/4619#6120 . Tetapi mereka tidak masuk ke detail spesifik dari algoritma Earley.