Salah satu proyek Java saya adalah garpu parboiled , dan tidak seperti, katakanlah, Antlr atau JavaCC, parser dihasilkan saat runtime. Tata bahasa yang dihasilkan adalah Parsing Expression Grammars, atau PEGs (Saya mendengar istilah lain untuk mereka adalah "packrat").
Sementara generasi runtime menambah kompleksitas (generasi bytecode terlibat), aspek lain berkaitan dengan teori parser itu sendiri. Sayangnya, karena saya tidak memiliki latar belakang yang kuat dalam ilmu komputer, saya tidak memiliki pengetahuan teoritis untuk memetakan kode yang ada ke konsep yang ada - dalam hal ini, parser.
Apakah ada buku referensi yang bagus tentang parser yang dapat saya beli dan baca, atau bahkan tautan di Internet, yang dapat membantu saya membangun "pemetaan" semacam itu, yang memperhitungkan pengetahuan teoretis saya yang buruk?
Jika Anda tidak keberatan dengan perbedaan bahasa, Bab 8 dari Perl Orde Tinggi adalah tentang parsing, dan khususnya membangun parser keturunan rekursif menggunakan kombinator parser. Ini dapat diakses (jika Anda tidak takut Perl) dan tersedia untuk dibaca secara gratis jika Anda suka. Ini membantu memicu minat saya pada teknik parsing beberapa tahun yang lalu.
sumber
Meskipun Teknik Parsing adalah buku yang hebat dan saya telah membaca beberapa bagian beberapa kali, ia memiliki fokus pada penguraian LR yang tidak akan menarik bagi Anda. Dalam kasus khusus Anda, Anda melihat PEG yang merupakan jenis penguraian rekursif top-down dengan pengurutan mundur berdasarkan urutan alternatif.
Saya ingin menyarankan Anda untuk melihat combinator parser, yang menggunakan strategi yang sama. Misalnya Anda dapat memeriksa makalah ini http://research.microsoft.com/pubs/65201/parsec-paper-letter.pdf yang menggunakan Haskell untuk membuat kombinator parser. Periksa bagian di
trymana mereka memasukkan backtracking (Bagian 3.4).Bagaimanapun, yang perlu Anda pelajari adalah:
sumber