Kapan harus menggunakan Parser Combinator? Kapan menggunakan Generator Parser?

Saya telah terjun ke dunia parser baru-baru ini, ingin membuat bahasa pemrograman saya sendiri.

Namun, saya menemukan bahwa ada dua pendekatan penulisan parser yang agak berbeda: Parser Generators dan Parser Combinators.

Menariknya, saya tidak dapat menemukan sumber daya yang menjelaskan dalam kasus apa pendekatan mana yang lebih baik; Sebaliknya, banyak sumber daya (dan orang) aku bertanya tentang subjek tidak tahu dari pendekatan lain, hanya menjelaskan mereka pendekatan sebagai yang pendekatan dan tidak menyebutkan lain sama sekali:

• The book Naga terkenal masuk ke lexing / scanning dan menyebutkan (f) lex, tetapi tidak menyebutkan Parser combinators sama sekali.
• Pola Implementasi Bahasa sangat bergantung pada ANTLR Parser Generator yang dibangun di Jawa, dan tidak menyebutkan Parser Combinator sama sekali.
• Tutorial Pengantar Parsec tentang Parsec, yang merupakan Parser Combinator di Haskell, tidak menyebutkan Parser Generator sama sekali.
• Boost :: spirit , C ++ Parser Combinator yang paling terkenal, sama sekali tidak menyebut Parser Generator.
• Posting blog penjelasan yang luar biasa yang Anda Bisa Kumpulkan Parser Combinators tidak menyebutkan Parser Generator sama sekali.

Gambaran Sederhana:

Generator Parser

Generator Parser mengambil file yang ditulis dalam DSL yang merupakan dialek dari bentuk Extended Backus-Naur , dan mengubahnya menjadi kode sumber yang kemudian dapat (ketika dikompilasi) menjadi pengurai untuk bahasa input yang dijelaskan dalam DSL ini.

Ini berarti bahwa proses kompilasi dilakukan dalam dua langkah terpisah. Menariknya, Parser Generator sendiri juga kompiler (dan banyak dari mereka memang hosting sendiri ).

Parser Combinator

Parser Combinator menjelaskan fungsi sederhana yang disebut parser yang semuanya mengambil input sebagai parameter, dan mencoba untuk memetik karakter pertama dari input ini jika cocok. Mereka mengembalikan tuple (result, rest_of_input), di mana resultmungkin kosong (misalnya nilatau Nothing) jika parser tidak dapat mengurai apa pun dari input ini. Contoh akan menjadi digitpengurai. Parser lain tentu saja dapat mengambil Parser sebagai argumen pertama (argumen terakhir masih tetap menjadi string input) untuk menggabungkan mereka: misalnya many1upaya untuk mencocokkan Parser lain sebanyak mungkin (tetapi setidaknya sekali, atau itu sendiri gagal).

Anda sekarang tentu saja dapat menggabungkan (menulis) digitdan many1, untuk membuat parser baru, katakanlah integer.

Juga, choiceparser tingkat yang lebih tinggi dapat ditulis yang mengambil daftar parser, mencoba masing-masing secara bergantian.

Dengan cara ini, lexers / parser yang sangat kompleks dapat dibangun. Dalam bahasa yang mendukung overloading operator, ini juga sangat mirip dengan EBNF, meskipun masih ditulis secara langsung dalam bahasa target (dan Anda dapat menggunakan semua fitur dari bahasa target yang Anda inginkan).

Perbedaan Sederhana

Bahasa:

• Parser Generator ditulis dalam kombinasi EBNF-ish DSL dan kode yang harus dihasilkan pernyataan ini ketika cocok.
• Parser Combinators ditulis dalam bahasa target secara langsung.

Lexing / Parsing:

• Parser Generator memiliki perbedaan yang sangat berbeda antara 'lexer' (yang membagi string menjadi token yang mungkin ditandai untuk menunjukkan nilai seperti apa yang kita hadapi) dan 'parser' (yang mengambil daftar output token dari lexer dan upaya untuk menggabungkan mereka, membentuk Pohon Sintaks Abstrak).
• Parser Combinators tidak memiliki / membutuhkan perbedaan ini; biasanya, parser sederhana melakukan pekerjaan 'lexer' dan parser tingkat lebih tinggi memanggil yang lebih sederhana untuk memutuskan jenis AST-node yang akan dibuat.

Pertanyaan

Namun, bahkan mengingat perbedaan-perbedaan ini (dan ini adalah daftar perbedaan mungkin jauh dari lengkap!), Saya tidak dapat membuat pilihan berpendidikan kapan harus menggunakan yang mana. Saya gagal melihat apa implikasi / konsekuensi dari perbedaan-perbedaan ini.

Properti masalah apa yang mengindikasikan bahwa masalah sebaiknya diselesaikan dengan menggunakan Parser Generator? Apa masalah properti akan menunjukkan bahwa masalah akan lebih baik diselesaikan menggunakan Parser Combinator?

Saya telah melakukan banyak penelitian beberapa hari terakhir ini, untuk lebih memahami mengapa ada teknologi terpisah ini, dan apa kekuatan dan kelemahannya.

Beberapa jawaban yang sudah ada mengisyaratkan beberapa perbedaan mereka, tetapi mereka tidak memberikan gambaran yang lengkap, dan tampaknya agak berpendapat, itulah sebabnya jawaban ini ditulis.

Eksposisi ini panjang, tetapi penting. tahan dengan saya (Atau jika Anda tidak sabar, gulir ke ujung untuk melihat diagram alur).

Untuk memahami perbedaan antara Parser Combinators dan Parser Generator, orang pertama-tama perlu memahami perbedaan antara berbagai jenis penguraian yang ada.

Parsing

Parsing adalah proses menganalisis serangkaian simbol sesuai dengan tata bahasa formal. (Dalam Ilmu Komputasi,) parsing digunakan untuk dapat membuat komputer memahami teks yang ditulis dalam bahasa, biasanya membuat pohon parse yang mewakili teks tertulis, menyimpan makna dari bagian tulisan yang berbeda di setiap simpul pohon. Pohon parse ini kemudian dapat digunakan untuk berbagai tujuan yang berbeda, seperti menerjemahkannya ke bahasa lain (digunakan dalam banyak kompiler), menafsirkan instruksi tertulis secara langsung dalam beberapa cara (SQL, HTML), yang memungkinkan alat-alat seperti Linters melakukan pekerjaan mereka , dll. Kadang-kadang, pohon parse tidak secara eksplisitdihasilkan, melainkan tindakan yang harus dilakukan pada setiap jenis node di pohon dijalankan secara langsung. Ini meningkatkan efisiensi, tetapi di bawah air masih terdapat pohon parse implisit.

Parsing adalah masalah yang sulit secara komputasi. Sudah ada lebih dari lima puluh tahun penelitian tentang masalah ini, tetapi masih banyak yang harus dipelajari.

Secara kasar, ada empat algoritma umum untuk membiarkan komputer mem-parsing input:

• Penguraian LL. (Bebas konteks, parsing top-down.)
• Penguraian LR. (Bebas konteks, penguraian dari bawah ke atas.)
• PEG + Penguraian paket.
• Parsing Earley.

Perhatikan bahwa jenis parsing ini sangat umum, deskripsi teoretis. Ada beberapa cara untuk mengimplementasikan masing-masing algoritma ini pada mesin fisik, dengan pengorbanan yang berbeda.

LL dan LR hanya dapat melihat tata bahasa bebas konteks (yaitu; konteks di sekitar token yang ditulis tidak penting untuk memahami bagaimana mereka digunakan).

Parsing PEG / Packrat dan Earley parsing digunakan jauh lebih sedikit: Earley-parsing bagus karena dapat menangani lebih banyak tata bahasa (termasuk yang tidak harus bebas dari Konteks) tetapi kurang efisien (seperti yang diklaim oleh naga) buku (bagian 4.1.1); Saya tidak yakin apakah klaim ini masih akurat). Parsing Expression Grammar + Packrat-parsing adalah metode yang relatif efisien dan juga dapat menangani lebih banyak tata bahasa daripada LL dan LR, tetapi menyembunyikan ambigueties, karena akan dengan cepat disentuh di bawah.

LL (Kiri-ke-kanan, Derivasi paling kiri)

Ini mungkin cara paling alami untuk berpikir tentang parsing. Idenya adalah untuk melihat token berikutnya dalam string input dan kemudian memutuskan yang mana dari beberapa kemungkinan panggilan rekursif yang harus diambil untuk menghasilkan struktur pohon.

Pohon ini dibangun 'top-down', yang berarti bahwa kita mulai pada akar pohon, dan melakukan perjalanan aturan tata bahasa dengan cara yang sama seperti kita melakukan perjalanan melalui string input. Itu juga dapat dilihat sebagai membangun 'postfix' yang setara untuk aliran token 'infix' yang sedang dibaca.

Parser yang melakukan parsing LL-style dapat ditulis agar terlihat sangat mirip dengan tata bahasa asli yang ditentukan. Ini membuatnya relatif mudah untuk dipahami, didebug dan ditingkatkan. Combinator Parser Klasik tidak lebih dari 'potongan lego' yang dapat disatukan untuk membangun parser gaya LL.

LR (Kiri-ke-kanan, Derivasi Kanan)

Penguraian LR berjalan dengan cara lain, bottom-up: Pada setiap langkah, elemen teratas pada stack dibandingkan dengan daftar tata bahasa, untuk melihat apakah mereka dapat direduksi menjadi aturan level yang lebih tinggi dalam tata bahasa. Jika tidak, token berikutnya dari aliran input menggeser ed dan ditempatkan di atas tumpukan.

Suatu program benar jika pada akhirnya kita berakhir dengan satu node pada stack yang mewakili aturan awal dari tata bahasa kita.

Lihat kedepan

Dalam salah satu dari kedua sistem ini, kadang-kadang perlu untuk mengintip lebih banyak token dari input sebelum dapat memutuskan pilihan mana yang akan dibuat. Ini adalah (0), (1), (k)atau (*)-syntax Anda lihat setelah nama dua algoritma umum ini, seperti LR(1) atau LL(k). kbiasanya singkatan dari 'sebanyak kebutuhan tata bahasa Anda', sementara *biasanya singkatan dari 'parser ini melakukan backtracking', yang lebih kuat / mudah diimplementasikan, tetapi memiliki memori dan penggunaan waktu yang jauh lebih tinggi daripada parser yang hanya dapat terus mengurai secara linear.

Perhatikan bahwa parser gaya LR sudah memiliki banyak token di tumpukan ketika mereka mungkin memutuskan untuk 'melihat ke depan', sehingga mereka sudah memiliki lebih banyak informasi untuk dikirim. Ini berarti bahwa mereka sering membutuhkan lebih sedikit 'lookahead' daripada parser gaya LL untuk tata bahasa yang sama.

LL vs. LR: Ambiguety

Saat membaca dua deskripsi di atas, orang mungkin bertanya-tanya mengapa parsing gaya-LR ada, karena parsing gaya-LL tampaknya jauh lebih alami.

Namun, parsing gaya LL memiliki masalah: Rekursi Kiri .

Sangat wajar untuk menulis tata bahasa seperti:

expr ::= expr '+' expr | term term ::= integer | float

Tapi, parser LL-style akan terjebak dalam loop rekursif tak terbatas ketika mengurai tata bahasa ini: Ketika mencoba kemungkinan paling kiri dari expraturan, itu berulang ke aturan ini lagi tanpa mengkonsumsi input apa pun.

Ada beberapa cara untuk mengatasi masalah ini. Yang paling sederhana adalah menulis ulang tata bahasa Anda sehingga jenis rekursi ini tidak terjadi lagi:

expr ::= term expr_rest expr_rest ::= '+' expr | ϵ term ::= integer | float (Di sini, ϵ singkatan dari 'string kosong')

Tata bahasa ini sekarang adalah rekursif yang tepat. Perhatikan bahwa ini segera jauh lebih sulit untuk dibaca.

Dalam praktiknya, rekursi kiri mungkin terjadi secara tidak langsung dengan banyak langkah lain di antaranya. Ini membuatnya menjadi masalah yang sulit untuk diwaspadai. Tetapi mencoba menyelesaikannya membuat tata bahasa Anda lebih sulit untuk dibaca.

Seperti yang dinyatakan Bagian 2.5 dari Buku Naga:

Kami tampaknya memiliki konflik: di satu sisi kami membutuhkan tata bahasa yang memfasilitasi terjemahan, di sisi lain kami membutuhkan tata bahasa yang sangat berbeda yang memfasilitasi penguraian. Solusinya adalah mulai dengan tata bahasa untuk terjemahan yang mudah dan dengan hati-hati mengubahnya untuk memudahkan penguraian. Dengan menghilangkan rekursi kiri kita bisa mendapatkan tata bahasa yang cocok untuk digunakan dalam penerjemah rekursif-keturunan prediktif.

Parser gaya LR tidak memiliki masalah rekursi kiri ini, karena mereka membangun pohon dari bawah ke atas. Namun , terjemahan mental dari tata bahasa seperti di atas ke parser LR-style (yang sering diimplementasikan sebagai Finite-State Automaton )
sangat sulit (dan rawan kesalahan) untuk dilakukan, karena sering ada ratusan atau ribuan negara + transisi negara untuk dipertimbangkan. Inilah sebabnya mengapa pengurai gaya LR biasanya dihasilkan oleh Parser Generator, yang juga dikenal sebagai 'kompiler kompiler'.

Bagaimana mengatasi Ketidakjelasan

Kami melihat dua metode untuk menyelesaikan ambigueties Rekursi Kiri di atas: 1) menulis ulang sintaks 2) menggunakan parser LR.

Tetapi ada beberapa jenis ambiguitas lain yang lebih sulit untuk dipecahkan: Bagaimana jika dua aturan yang berbeda berlaku secara bersamaan?

Beberapa contoh umum adalah:

• ekspresi aritmatika.
• yang lain menggantung

Pengurai gaya LL dan LR memiliki masalah dengan ini. Masalah dengan parsing ekspresi aritmatika dapat diselesaikan dengan memperkenalkan prioritas operator. Dengan cara yang sama, masalah lain seperti Dangling Else dapat diselesaikan, dengan memilih satu perilaku yang diutamakan dan bertahan dengannya. (Dalam C / C ++, misalnya, menggantung lain selalu milik terdekat 'jika').

'Solusi' lain untuk ini adalah dengan menggunakan Parser Expression Grammar (PEG): Ini mirip dengan tata bahasa BNF yang digunakan di atas, tetapi dalam kasus ambiguitas, selalu 'pilih yang pertama'. Tentu saja, ini tidak benar-benar 'menyelesaikan' masalah, tetapi menyembunyikan bahwa ambiguitas benar-benar ada: Pengguna akhir mungkin tidak tahu pilihan yang dibuat parser, dan ini mungkin mengarah pada hasil yang tidak terduga.

Lebih banyak informasi yang jauh lebih mendalam daripada posting ini, termasuk mengapa secara umum tidak mungkin untuk mengetahui apakah tata bahasa Anda tidak memiliki ambiguitas dan implikasi dari hal ini adalah artikel blog indah LL dan LR dalam konteks: Mengapa parsing alat itu sulit . Saya sangat merekomendasikannya; itu sangat membantu saya untuk memahami semua hal yang saya bicarakan saat ini.

50 tahun penelitian

Namun hidup terus berjalan. Ternyata parser gaya LR 'normal' diimplementasikan sebagai otomat keadaan terbatas sering membutuhkan ribuan status + transisi, yang merupakan masalah dalam ukuran program. Jadi, varian seperti Simple LR (SLR) dan LALR (Look-ahead LR) ditulis yang menggabungkan teknik-teknik lain untuk membuat automaton lebih kecil, mengurangi disk dan jejak memori dari program parser.

Juga, cara lain untuk menyelesaikan ambiguitas yang tercantum di atas adalah dengan menggunakan teknik umum di mana, dalam kasus ambiguitas, kedua kemungkinan disimpan dan diurai: Salah satu mungkin gagal untuk menguraikan garis (dalam hal ini kemungkinan lain adalah 'benar' satu), serta mengembalikan keduanya (dan dengan cara ini menunjukkan bahwa ada ambiguitas) dalam kasus mereka berdua benar.

Menariknya, setelah algoritma Generalized LR dijelaskan, ternyata pendekatan yang sama dapat digunakan untuk mengimplementasikan parser Generalized LL , yang juga sama cepatnya ($ O (n ^ 3) $ kompleksitas waktu untuk tata bahasa ambigu, $ O (n) $ untuk tata bahasa yang sama sekali tidak ambigu, meskipun dengan lebih banyak pembukuan daripada parser LR sederhana (LA), yang berarti faktor konstan yang lebih tinggi) tetapi sekali lagi memungkinkan parser ditulis dalam gaya turunan berulang (atas-bawah) yang jauh lebih alami untuk menulis dan men-debug.

Parser Combinators, Parser Generator

Jadi, dengan paparan panjang ini, kita sekarang sampai pada inti pertanyaan:

Apa perbedaan Combinators Parser dan Generator Parser, dan kapan satu harus digunakan di atas yang lain?

Mereka adalah jenis binatang yang sangat berbeda:

Parser Combinators dibuat karena orang menulis parser top-down dan menyadari bahwa banyak dari ini memiliki banyak kesamaan .

Parser Generator dibuat karena orang mencari untuk membuat parser yang tidak memiliki masalah yang dimiliki parser gaya LL (yaitu parser gaya LR), yang terbukti sangat sulit dilakukan dengan tangan. Yang umum termasuk Yacc / Bison, yang mengimplementasikan (LA) LR).

Menariknya, saat ini lanskap agak kacau:

• Dimungkinkan untuk menulis Parser Combinators yang bekerja dengan algoritma GLL , menyelesaikan masalah ambiguitas yang dimiliki parser LL-style klasik, sambil juga dapat dibaca / dimengerti seperti semua jenis parsing top-down.

• Parser Generator juga dapat ditulis untuk parser gaya-LL. ANTLR melakukan hal itu, dan menggunakan heuristik lain (Adaptive LL (*)) untuk menyelesaikan ambiguitas yang dimiliki oleh parser gaya LL klasik.

Secara umum, membuat generator parser LR dan dan men-debug output dari generator parser LR gaya (LA) yang berjalan pada tata bahasa Anda itu sulit, karena terjemahan tata bahasa asli Anda ke bentuk LR 'dalam-luar'. Di sisi lain, alat-alat seperti Yacc / Bison telah bertahun-tahun dari optimisations, dan melihat banyak digunakan di alam liar, yang berarti bahwa banyak orang sekarang menganggap itu sebagai yang cara untuk melakukan parsing dan skeptis terhadap pendekatan baru.

Yang mana yang harus Anda gunakan, tergantung pada seberapa keras tata bahasa Anda, dan seberapa cepat pengurai harus. Bergantung pada tata bahasa, salah satu teknik ini (/ implementasi dari teknik yang berbeda) mungkin lebih cepat, memiliki tapak memori yang lebih kecil, memiliki tapak cakram yang lebih kecil, atau lebih dapat diperluas atau lebih mudah untuk di-debug daripada yang lainnya. Mileage Anda Mungkin Bervariasi .

Catatan samping: Mengenai masalah Analisis Leksikal.

Analisis Leksikal dapat digunakan baik untuk Parser Combinators dan Parser Generators. Idenya adalah untuk memiliki parser 'bodoh' yang sangat mudah diimplementasikan (dan karena itu cepat) yang melakukan pass pertama atas kode sumber Anda, menghapus misalnya mengulangi spasi putih, komentar, dll, dan mungkin 'tokenizing' dalam sangat cara kasar berbagai elemen yang membentuk bahasa Anda.

Keuntungan utama adalah bahwa langkah pertama ini membuat pengurai nyata jauh lebih sederhana (dan karena itu mungkin lebih cepat). Kerugian utama adalah Anda memiliki langkah penerjemahan terpisah, dan mis. Pelaporan kesalahan dengan nomor baris dan kolom menjadi lebih sulit karena penghapusan spasi putih.

Lexer pada akhirnya adalah 'hanya' pengurai lain dan dapat diimplementasikan menggunakan salah satu teknik di atas. Karena kesederhanaannya, seringkali teknik lain digunakan selain parser utama, dan misalnya ada tambahan 'generator lexer'.

Tl; Dr:

Berikut adalah bagan alur yang berlaku untuk sebagian besar kasus:

Untuk input yang dijamin bebas dari kesalahan sintaksis, atau jika lulus / gagal secara keseluruhan pada kebenaran sintaksis tidak apa-apa, kombinator parser jauh lebih mudah untuk digunakan, terutama dalam bahasa pemrograman fungsional. Ini adalah situasi seperti teka-teki pemrograman, membaca file data, dll.

Fitur yang membuat Anda ingin menambahkan kompleksitas generator parser adalah pesan kesalahan. Anda ingin pesan kesalahan yang mengarahkan pengguna ke garis dan kolom, dan mudah-mudahan juga bisa dimengerti oleh manusia. Dibutuhkan banyak kode untuk melakukannya dengan benar, dan generator parser yang lebih baik seperti antlr dapat membantu Anda.

Namun, pembuatan otomatis hanya bisa membuat Anda sejauh ini, dan sebagian besar kompiler open source komersial dan berumur panjang akhirnya secara manual menulis parser mereka. Saya kira jika Anda merasa nyaman melakukan ini, Anda tidak akan mengajukan pertanyaan ini, jadi saya sarankan pergi dengan generator parser.

Sam Harwell, salah satu pemelihara parser generator ANTLR, baru-baru ini menulis :

Saya menemukan [kombinator] tidak memenuhi kebutuhan saya:

1. ANTLR memberi saya alat untuk mengelola hal-hal seperti ambiguitas. Selama pengembangan ada alat yang bisa menunjukkan hasil parse ambigu sehingga saya bisa menghilangkan ambiguitas dalam tata bahasa. Saat runtime saya dapat memanfaatkan ambiguitas yang dihasilkan dari input yang tidak lengkap dalam IDE untuk menghasilkan hasil yang lebih akurat dalam fitur seperti penyelesaian kode.
2. Dalam praktiknya saya telah menemukan bahwa kombinator parser tidak cocok untuk memenuhi tujuan kinerja saya. Sebagian dari ini kembali
3. Saat hasil parse digunakan untuk fitur seperti garis besar, penyelesaian kode, dan indentasi pintar, mudah untuk perubahan tata bahasa yang halus untuk memengaruhi keakuratan hasil tersebut. ANTLR menyediakan alat yang dapat mengubah ketidakcocokan ini menjadi kesalahan kompilasi, bahkan dalam kasus di mana tipe akan dikompilasi. Saya dapat dengan percaya diri membuat prototipe fitur bahasa baru yang memengaruhi tata bahasa dengan mengetahui bahwa semua kode tambahan yang membentuk IDE akan memberikan pengalaman lengkap untuk fitur baru sejak awal. Garpu ANTLR 4 saya (yang menjadi dasar target C #) adalah satu-satunya alat yang saya ketahui yang bahkan berupaya menyediakan fitur ini.

Pada dasarnya, parser combinator adalah mainan yang asyik untuk dimainkan, tetapi mereka tidak cocok untuk melakukan pekerjaan serius.

Seperti yang disebutkan Karl, generator parser cenderung memiliki pelaporan kesalahan yang lebih baik. Tambahan:

• mereka cenderung lebih cepat, karena kode yang dihasilkan dapat dikhususkan untuk sintaks dan menghasilkan tabel lompatan untuk lookahead.
• mereka cenderung memiliki perkakas yang lebih baik, untuk mengidentifikasi sintaksis yang ambigu, menghapus rekursi kiri, mengisi cabang kesalahan, dll.
• mereka cenderung menangani definisi rekursif dengan lebih baik.
• mereka cenderung lebih kuat, karena generator telah bekerja lebih lama dan melakukan lebih banyak boilerplate untuk Anda, mengurangi kemungkinan Anda mengacaukannya.

Di sisi lain, kombinator memiliki kelebihan sendiri:

• mereka ada dalam kode, jadi jika sintaks Anda bervariasi pada saat runtime, Anda dapat lebih mudah bermutasi.
• mereka cenderung lebih mudah untuk diikat dan dikonsumsi (output generator parser cenderung sangat generik dan canggung untuk digunakan).
• mereka ada dalam kode, jadi cenderung sedikit lebih mudah untuk di-debug ketika tata bahasa Anda tidak melakukan apa yang Anda harapkan.
• mereka cenderung memiliki kurva belajar yang lebih dangkal karena mereka bekerja seperti kode lainnya. Generator Parser cenderung memiliki kebiasaan sendiri untuk belajar membuat barang berfungsi.