Haruskah saya menggunakan generator parser atau haruskah saya menggulir kode lexer dan parser kustom saya sendiri?

Apa kelebihan dan kekurangan spesifik dari setiap cara untuk mengerjakan tata bahasa bahasa pemrograman?

Mengapa / Kapan saya harus menggulung sendiri? Mengapa / Kapan saya harus menggunakan generator?

Ada tiga opsi sebenarnya, ketiganya lebih disukai dalam situasi yang berbeda.

Opsi 1: generator parser, atau 'Anda perlu menguraikan beberapa bahasa dan Anda hanya ingin membuatnya berfungsi, sial'

Katakanlah, Anda diminta membuat parser untuk beberapa format data kuno SEKARANG. Atau Anda perlu pengurai Anda untuk menjadi cepat. Atau Anda perlu parser agar mudah dirawat.

Dalam kasus ini, Anda mungkin lebih baik menggunakan generator parser. Anda tidak perlu mengutak-atik detail, Anda tidak harus mendapatkan banyak kode rumit untuk bekerja dengan baik, Anda hanya menulis tata bahasa input akan mematuhi, menulis beberapa kode penanganan dan presto: pengurai instan.

Keuntungannya jelas:

• Ini (biasanya) cukup mudah untuk menulis spesifikasi, khususnya jika format input tidak terlalu aneh (opsi 2 akan lebih baik jika itu).
• Anda berakhir dengan sebuah karya yang sangat mudah dipelihara yang mudah dipahami: definisi tata bahasa biasanya mengalir jauh lebih alami daripada kode.
• Parser yang dihasilkan oleh generator Parser yang baik biasanya jauh lebih cepat daripada kode tulisan tangan. Kode tulisan tangan bisa lebih cepat, tetapi hanya jika Anda mengetahui hal-hal Anda - inilah mengapa kompiler yang paling banyak digunakan menggunakan parser rekursif-keturunan yang ditulis tangan.

Ada satu hal yang harus Anda perhatikan dengan generator parser: kadang-kadang bisa menolak tata bahasa Anda. Untuk ikhtisar tentang berbagai jenis parser dan bagaimana mereka dapat menggigit Anda, Anda mungkin ingin memulai di sini . Di sini Anda dapat menemukan ikhtisar dari banyak implementasi dan jenis tata bahasa yang mereka terima.

Opsi 2: parser yang ditulis tangan, atau 'Anda ingin membuat parser Anda sendiri, dan Anda ingin menjadi user-friendly'

Generator Parser bagus, tetapi mereka tidak ramah (pengguna akhir, bukan Anda) ramah. Anda biasanya tidak dapat memberikan pesan kesalahan yang baik, Anda juga tidak bisa memberikan pemulihan kesalahan. Mungkin bahasa Anda sangat aneh dan parser menolak tata bahasa Anda atau Anda membutuhkan lebih banyak kontrol daripada yang diberikan generator.

Dalam kasus ini, menggunakan parser rekursif-keturunan yang ditulis tangan mungkin yang terbaik. Meskipun melakukannya dengan benar mungkin rumit, Anda memiliki kontrol penuh atas parser Anda sehingga Anda dapat melakukan semua jenis hal-hal baik yang tidak dapat Anda lakukan dengan generator parser, seperti pesan kesalahan dan bahkan pemulihan kesalahan (coba hapus semua titik koma dari file C # : kompiler C # akan mengeluh, tetapi akan mendeteksi sebagian besar kesalahan lainnya terlepas dari keberadaan titik koma).

Parser yang ditulis tangan juga biasanya berkinerja lebih baik daripada yang dihasilkan, dengan asumsi kualitas pengurai cukup tinggi. Di sisi lain, jika Anda tidak berhasil menulis parser yang bagus - biasanya karena (kombinasi) kurangnya pengalaman, pengetahuan atau desain - maka kinerja biasanya lebih lambat. Untuk lexers, yang terjadi adalah sebaliknya: lexers yang dihasilkan secara umum menggunakan pencarian tabel, membuatnya lebih cepat daripada (kebanyakan) tulisan tangan.

Dari segi pendidikan, menulis parser Anda sendiri akan mengajarkan Anda lebih banyak daripada menggunakan generator. Anda harus menulis lebih banyak dan lebih rumit lagi kode, ditambah Anda harus memahami persis bagaimana Anda menguraikan bahasa. Di sisi lain, jika Anda ingin belajar cara membuat bahasa Anda sendiri (jadi, dapatkan pengalaman di desain bahasa), baik opsi 1 atau opsi 3 lebih disukai: jika Anda mengembangkan bahasa, itu mungkin akan banyak berubah, dan opsi 1 dan 3 memberi Anda waktu yang lebih mudah dengan itu.

Opsi 3: generator parser tulisan tangan, atau 'Anda sedang mencoba belajar banyak dari proyek ini dan Anda tidak keberatan berakhir dengan sepotong kode yang bagus yang dapat Anda gunakan kembali'

Ini adalah jalur yang saya jalani saat ini: Anda menulis generator parser Anda sendiri . Meskipun sangat tidak trivial, melakukan hal ini mungkin akan paling mengajari Anda.

Untuk memberi Anda gambaran tentang melakukan proyek seperti ini, saya akan memberi tahu Anda tentang kemajuan saya sendiri.

Generator lexer

Saya membuat generator lexer saya sendiri terlebih dahulu. Saya biasanya mendesain perangkat lunak dimulai dengan bagaimana kode akan digunakan, jadi saya memikirkan bagaimana saya ingin dapat menggunakan kode saya dan menulis potongan kode ini (ini dalam C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Pasangan input-token string dikonversi menjadi struktur rekursif yang sesuai yang menggambarkan ekspresi reguler yang diwakilinya menggunakan gagasan tumpukan aritmatika. Ini kemudian dikonversi menjadi NFA (otomat hingga terbatas nondeterministic), yang pada gilirannya dikonversi menjadi DFA (otomat hingga finin deterministik). Anda kemudian dapat mencocokkan string dengan DFA.

Dengan cara ini, Anda mendapatkan ide bagus bagaimana tepatnya lexers bekerja. Selain itu, jika Anda melakukannya dengan cara yang benar, hasil dari generator lexer Anda dapat kira-kira secepat implementasi profesional. Anda juga tidak kehilangan ekspresif apa pun dibandingkan dengan opsi 2, dan tidak banyak ekspresif dibandingkan dengan opsi 1.

Saya menerapkan generator lexer saya di lebih dari 1600 baris kode. Kode ini membuat pekerjaan di atas, tetapi masih menghasilkan lexer dengan cepat setiap kali Anda memulai program: Saya akan menambahkan kode untuk menulisnya ke disk di beberapa titik.

Jika Anda ingin tahu cara menulis lexer Anda sendiri, ini adalah tempat yang baik untuk memulai.

Generator pengurai

Anda kemudian menulis generator parser Anda. Saya merujuk ke sini lagi untuk tinjauan umum tentang berbagai jenis parser - sebagai aturan praktis, semakin banyak mereka dapat mengurai, semakin lambat mereka.

Kecepatan tidak menjadi masalah bagi saya, saya memilih untuk mengimplementasikan parser Earley. Implementasi lanjutan dari pengurai Earley telah terbukti sekitar dua kali lebih lambat dari jenis pengurai lainnya.

Sebagai imbalan untuk hit kecepatan itu, Anda mendapatkan kemampuan untuk menguraikan segala jenis tata bahasa, bahkan yang ambigu. Ini berarti Anda tidak perlu khawatir tentang apakah parser Anda memiliki rekursi kiri di dalamnya, atau apa konflik pengurangan-shift itu. Anda juga dapat mendefinisikan tata bahasa dengan lebih mudah menggunakan tata bahasa ambigu jika tidak masalah pohon parse mana yang dihasilkan, seperti itu tidak masalah apakah Anda mengurai 1 + 2 + 3 sebagai (1 + 2) +3 atau sebagai 1 + (2 + 3).

Ini adalah tampilan kode menggunakan generator parser saya:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Perhatikan bahwa IntWrapper hanyalah sebuah Int32, kecuali bahwa C # mengharuskannya untuk menjadi kelas, maka saya harus memperkenalkan kelas pembungkus)

Saya harap Anda melihat bahwa kode di atas sangat kuat: tata bahasa apa pun yang dapat Anda buat dapat diuraikan. Anda dapat menambahkan bit kode sembarang dalam tata bahasa yang mampu melakukan banyak tugas. Jika Anda berhasil menjalankan semua ini, Anda dapat menggunakan kembali kode yang dihasilkan untuk melakukan banyak tugas dengan sangat mudah: Bayangkan saja membangun juru bahasa command-line menggunakan potongan kode ini.

Jika Anda belum pernah menulis parser, saya sarankan Anda melakukannya. Ini menyenangkan, dan Anda belajar bagaimana segala sesuatunya bekerja, dan Anda belajar menghargai upaya yang dilakukan oleh generator parser dan lexer yang tidak membuat Anda melakukan hal lain kali saat Anda membutuhkan parser.

Saya juga menyarankan Anda mencoba membaca http://compilers.iecc.com/crenshaw/ karena memiliki sikap yang sangat membumi terhadap cara melakukannya.

Keuntungan dari menulis parser keturunan rekursif Anda sendiri adalah bahwa Anda dapat menghasilkan pesan kesalahan berkualitas tinggi pada kesalahan sintaks. Menggunakan generator parser, Anda dapat membuat produksi kesalahan dan menambahkan pesan kesalahan khusus pada titik-titik tertentu, tetapi generator parser tidak cocok dengan kekuatan memiliki kontrol penuh atas parsing.

Keuntungan lain dari menulis sendiri adalah lebih mudah untuk menguraikan representasi yang lebih sederhana yang tidak memiliki korespondensi satu lawan satu dengan tata bahasa Anda.

Jika tata bahasa Anda sudah diperbaiki, dan pesan kesalahan penting, pertimbangkan untuk menggulirkan sendiri, atau setidaknya menggunakan generator parser yang memberi Anda pesan kesalahan yang Anda butuhkan. Jika tata bahasa Anda terus berubah, Anda sebaiknya mempertimbangkan menggunakan generator parser.

Bjarne Stroustrup berbicara tentang bagaimana dia menggunakan YACC untuk implementasi pertama C ++ (lihat Desain dan Evolusi C ++ ). Dalam kasus pertama, dia berharap dia menulis parser keturunan rekursif sendiri sebagai gantinya!

Opsi 3: Baik (Gulung generator parser Anda sendiri)

Hanya karena ada alasan untuk tidak menggunakan ANTLR , bison , Coco / R , Grammatica , JavaCC , Lemon , setengah matang , SableCC , Quex , dll - itu tidak berarti Anda harus langsung menggulung parser sendiri + lexer.

Identifikasi mengapa semua alat ini tidak cukup baik - mengapa mereka tidak membiarkan Anda mencapai tujuan Anda?

Kecuali Anda yakin bahwa keanehan dalam tata bahasa yang Anda hadapi adalah unik, Anda tidak boleh hanya membuat parser + lexer khusus untuk itu. Alih-alih, buat alat yang akan menciptakan apa yang Anda inginkan, tetapi juga dapat digunakan untuk memenuhi kebutuhan di masa mendatang, lalu lepaskan sebagai Perangkat Lunak Bebas untuk mencegah orang lain mengalami masalah yang sama dengan Anda.

Memutar parser Anda sendiri memaksa Anda untuk berpikir langsung tentang kompleksitas bahasa Anda. Jika bahasanya sulit diurai, mungkin akan sulit dimengerti.

Ada banyak minat pada generator parser pada masa-masa awal, dimotivasi oleh sintaksis bahasa yang sangat rumit (beberapa orang akan mengatakan "tersiksa"). JOVIAL adalah contoh yang sangat buruk: dibutuhkan dua simbol lookahead, pada saat yang lain membutuhkan paling banyak satu simbol. Hal ini membuat menghasilkan parser untuk kompiler JOVIAL lebih sulit dari yang diharapkan (seperti General Dynamics / Fort Worth Division belajar dengan cara yang sulit ketika mereka membeli kompiler JOVIAL untuk program F-16).

Saat ini, keturunan rekursif secara universal adalah metode yang disukai, karena lebih mudah bagi penulis kompiler. Compiler keturunan rekursif sangat menghargai desain bahasa yang sederhana dan bersih, karena jauh lebih mudah untuk menulis parser keturunan rekursif untuk bahasa yang sederhana dan bersih daripada yang berbelit-belit dan berantakan.

Akhirnya: Sudahkah Anda mempertimbangkan untuk menggunakan bahasa Anda di LISP, dan membiarkan penerjemah LISP melakukan hal yang berat untuk Anda? AutoCAD melakukan itu, dan menemukan itu membuat hidup mereka jauh lebih mudah. Ada beberapa penerjemah LISP yang ringan di luar sana, beberapa di antaranya dapat disematkan.

Saya pernah menulis parser untuk aplikasi komersial dan saya menggunakan yacc . Ada prototipe yang bersaing di mana pengembang menulis semuanya dengan tangan di C ++ dan itu bekerja sekitar lima kali lebih lambat.

Adapun lexer untuk parser ini, saya menulisnya sepenuhnya dengan tangan. Butuh - maaf, itu hampir 10 tahun yang lalu, jadi saya tidak ingat persis - sekitar 1000 baris dalam C .

Alasan mengapa saya menulis lexer dengan tangan adalah tata bahasa input parser. Itu adalah persyaratan, sesuatu yang harus dipatuhi oleh implementasi parser saya, bukan sesuatu yang saya rancang. (Tentu saja saya akan mendesainnya secara berbeda. Dan lebih baik!) Tata bahasanya sangat bergantung pada konteks dan bahkan tergantung pada semantik di beberapa tempat. Sebagai contoh, titik koma bisa menjadi bagian dari token di satu tempat, tetapi pemisah di tempat yang berbeda - berdasarkan interpretasi semantik dari beberapa elemen yang diuraikan sebelumnya. Jadi, saya "mengubur" dependensi semantik seperti itu dalam lexer yang ditulis tangan dan membuat saya dengan BNF yang cukup mudah yang mudah diimplementasikan di yacc.

TAMBAH dalam menanggapi Macneil : yacc menyediakan abstraksi yang sangat kuat yang memungkinkan programmer berpikir dalam hal terminal, non-terminal, produksi dan hal-hal seperti itu. Juga, ketika mengimplementasikan yylex()fungsi, itu membantu saya untuk fokus mengembalikan token saat ini dan tidak khawatir tentang apa yang sebelum atau sesudahnya. Programer C ++ bekerja pada level karakter, tanpa manfaat dari abstraksi seperti itu dan akhirnya menciptakan algoritma yang lebih rumit dan kurang efisien. Kami menyimpulkan bahwa kecepatan yang lebih lambat tidak ada hubungannya dengan C ++ itu sendiri atau perpustakaan. Kami mengukur kecepatan penguraian murni dengan file yang dimuat dalam memori; jika kami memiliki masalah buffering file, ya tidak akan menjadi alat pilihan kami untuk menyelesaikannya.

JUGA INGIN MENAMBAH : ini bukan resep untuk menulis parser secara umum, hanya sebuah contoh bagaimana itu bekerja dalam satu situasi tertentu.

Itu sepenuhnya tergantung pada apa yang Anda perlu uraikan. Bisakah Anda menggulung sendiri lebih cepat dari yang Anda bisa mengenai lexer? Apakah barang yang diuraikan cukup statis sehingga Anda tidak akan menyesali keputusan nanti? Apakah Anda menemukan implementasi yang ada terlalu rumit? Jika demikian, bersenang-senanglah menggulung sendiri, tetapi hanya jika Anda tidak merunduk kurva belajar.

Akhir-akhir ini, saya sangat menyukai pengurai lemon , yang bisa dibilang paling sederhana dan termudah yang pernah saya gunakan. Demi mempermudah perawatan, saya hanya menggunakannya untuk sebagian besar kebutuhan. SQLite menggunakannya serta beberapa proyek penting lainnya.

Tapi, saya sama sekali tidak tertarik pada lexers, di luar mereka tidak menghalangi saya ketika saya perlu menggunakannya (karenanya, lemon). Anda mungkin, dan jika demikian, mengapa tidak membuatnya? Saya punya perasaan Anda akan kembali menggunakan yang ada, tetapi menggaruk gatal jika Anda harus :)

Itu tergantung pada apa tujuan Anda.

Apakah Anda mencoba mempelajari cara kerja parser / kompiler? Kemudian tulis sendiri dari awal. Itulah satu-satunya cara Anda benar-benar akan belajar menghargai semua seluk beluk apa yang mereka lakukan. Saya telah menulis satu beberapa bulan terakhir, dan itu merupakan pengalaman yang menarik dan berharga, terutama 'ah, jadi itu sebabnya bahasa X melakukan ini ...' saat-saat.

Apakah Anda perlu menyatukan sesuatu dengan cepat untuk aplikasi pada tenggat waktu? Maka mungkin menggunakan alat parser.

Apakah Anda memerlukan sesuatu yang ingin Anda kembangkan selama 10, 20, bahkan 30 tahun ke depan? Tulis sendiri, dan luangkan waktu Anda. Itu akan sangat berharga.

Sudahkah Anda mempertimbangkan pendekatan meja kerja bahasa Martin Fowlers ? Mengutip dari artikel

Perubahan paling jelas yang dibuat oleh sebuah meja kerja bahasa untuk persamaan adalah kemudahan menciptakan DSL eksternal. Anda tidak lagi harus menulis parser. Anda harus mendefinisikan sintaksis abstrak - tetapi itu sebenarnya langkah pemodelan data yang cukup mudah. Selain itu DSL Anda mendapatkan IDE yang kuat - meskipun Anda harus meluangkan waktu untuk mendefinisikan editor itu. Generator masih merupakan sesuatu yang harus Anda lakukan, dan saya rasa itu tidak jauh lebih mudah dari sebelumnya. Tetapi kemudian membangun generator untuk DSL yang baik dan sederhana adalah salah satu bagian yang paling mudah dari latihan ini.

Membaca itu, saya akan mengatakan bahwa hari-hari penulisan parser Anda sendiri sudah berakhir dan lebih baik menggunakan salah satu perpustakaan yang tersedia. Setelah Anda menguasai perpustakaan maka semua DSL yang Anda buat di masa depan akan mendapat manfaat dari pengetahuan itu. Selain itu, orang lain tidak perlu mempelajari pendekatan Anda untuk parsing.

Edit untuk mencakup komentar (dan pertanyaan yang direvisi)

Keuntungan menggulung sendiri

1. Anda akan memiliki pengurai dan mendapatkan semua pengalaman indah berpikir melalui serangkaian masalah yang rumit
2. Anda mungkin menemukan sesuatu yang istimewa yang tidak dipikirkan orang lain (tidak mungkin tetapi Anda terlihat seperti orang yang pintar)
3. Ini akan membuat Anda sibuk dengan masalah yang menarik

Jadi singkatnya, Anda harus menggulung sendiri ketika Anda ingin benar-benar menyusup jauh ke dalam perut masalah yang sangat sulit yang Anda rasakan sangat termotivasi untuk dikuasai.

Keuntungan menggunakan perpustakaan orang lain

1. Anda akan menghindari menciptakan kembali roda (masalah umum dalam pemrograman Anda akan setuju)
2. Anda dapat fokus pada hasil akhir (Anda mengkilap bahasa baru) dan tidak terlalu khawatir tentang bagaimana itu diuraikan dll
3. Anda akan melihat bahasa Anda beraksi jauh lebih cepat (tetapi pahala Anda akan berkurang karena tidak semuanya Anda)

Karena itu, jika Anda ingin hasil akhir yang cepat, gunakan perpustakaan orang lain.

Secara keseluruhan, ini bermuara pada pilihan seberapa banyak Anda ingin memiliki masalah, dan dengan demikian solusinya. Jika Anda ingin semuanya, maka roll sendiri.

Keuntungan besar menulis sendiri adalah Anda akan tahu cara menulis sendiri. Keuntungan besar menggunakan alat seperti yacc adalah Anda akan tahu cara menggunakan alat ini. Saya penggemar puncak pohon untuk eksplorasi awal.

Mengapa tidak memotong generator parser open-source dan membuatnya sendiri? Jika Anda tidak menggunakan generator parser, kode Anda akan sangat sulit dipertahankan, jika Anda membuat perubahan besar pada sintaksis bahasa Anda.

Dalam parser saya, saya menggunakan ekspresi reguler (maksud saya, gaya Perl) untuk tokenize, dan menggunakan beberapa fungsi kenyamanan untuk meningkatkan keterbacaan kode. Namun, kode yang dihasilkan parser bisa lebih cepat dengan membuat tabel negara dan panjang switch- cases, yang dapat meningkatkan ukuran kode sumber kecuali Anda .gitignore.

Berikut adalah dua contoh parser yang ditulis khusus:

https://github.com/SHiNKiROU/DesignScript - dialek BASIC, karena saya terlalu malas untuk menulis lookaheads dalam notasi array, saya mengorbankan kualitas pesan kesalahan https://github.com/SHiNKiROU/ExprParser - Kalkulator rumus. Perhatikan trik pemrograman aneh

"Haruskah saya menggunakan 'roda' yang telah dicoba dan diuji ini atau menciptakannya kembali?"