Kategori teori dan parser - referensi yang diinginkan

Karena saya tertarik pada parser (terutama dalam tata bahasa ekspresi parser), saya bertanya-tanya apakah ada beberapa pekerjaan yang memberikan perlakuan kategorikal parsing. Setiap referensi pada aplikasi teori kategori untuk parsing sangat dihargai.

Terbaik,

Salah satu aplikasi pertama teori kategori pada subjek di luar geometri aljabar adalah menguraikan! Kata kunci yang ingin Anda pandu pencarian Anda adalah "Lambek calculus" dan "tata bahasa kategori".

Dalam istilah modern, Joachim Lambek menemukan logika linier nonkomutatif untuk memodelkan struktur kalimat. Ide dasarnya adalah bahwa Anda dapat memberikan bagian dasar dari pidato sebagai memiliki jenis, dan kemudian (katakanlah) menganggap kata sifat Bahasa Inggris jenis fungsi mengambil frase nomina ke frase nomina. (misalnya, "hijau" dipandang sebagai fungsi mengambil kata benda ke kata benda, yang berarti bahwa "telur hijau" diketik dengan baik, karena "telur" adalah kata benda).

Linearitas muncul dari fakta bahwa kata sifat mengambil tepat satu frase kata benda sebagai argumen, dan nonkomutatif muncul dari fakta bahwa urutan kata dalam kalimat penting. Misalnya, argumen nomina kata sifat muncul setelah kata sifat ("telur hijau"), sedangkan frase nomina frase preposisional muncul sebelum frasa preposisi ("telur hijau dengan saus tomat"). Dalam istilah kategori, Anda menginginkan kategori monoid (non-simetris) yang ditutup di sebelah kiri dan kanan. Jadi tipe adalah jenis frase yang memiliki tipe B , ketika didahului oleh A di sebelah kiri, dan B / A adalah jenis frase yang memiliki tipe B ketika digantikan oleh A di sebelah kanan, dan tipe A ∗ B adalah jenis frase yang dibuat dengan menggabungkan sesuatu yang tipe A dengan sesuatu tipe B .$A\setminus{}B$$B$$A$$B/A$$B$$A$$A \ast B$$A$$B$

Ternyata tata bahasa Lambek setara dengan bahasa bebas konteks, meskipun tampaknya ini hasil yang cukup sulit - menunjukkan CFG adalah bagian dari tata bahasa Lambek mudah, tetapi arah lain hanya didirikan pada tahun 1991 oleh Pentus.

Latihan yang baik ^ H ^ H ^ Hpublikasi untuk pembaca (yaitu, saya belum mencobanya, tetapi saya pikir akan lebih baik untuk mencoba) adalah dengan menggunakan kalkulus Lambek untuk merumuskan ulang presentasi Valiant tentang CYK parsing melalui perkalian matriks boolean , dalam kategori ketentuan Sebagai motivasi, saya kutip dari makalah Lambek 1958 The Mathematics of Sentence Structure :

Kalkulus yang disajikan di sini identik secara formal dengan kalkulus yang dibangun oleh GD Findlay dan penulis saat ini untuk diskusi tentang pemetaan kanonik dalam aljabar linear dan multilinear.

Tampak bahwa (konteks bebas) parsing ala Parsec secara alami dinyatakan dalam kelas tipe Applicative . Pada gilirannya, kelas ini dideskripsikan dengan baik oleh apa yang disebut functor monoid lemah lemah , yang disebutkan dalam pertanyaan teori yang sangat bagus ini dan pertanyaan stackoverflow yang bagus ini .

Lebih umum, Parsec parser adalah monad , yang sangat terkenal dalam teori CS dan teori kategori sehingga saya tidak akan memberikan referensi kecuali diminta.