it-swarm-id.com

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

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

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

83
Maniero

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 dapat menjadi lebih cepat, tetapi hanya jika Anda mengetahui hal-hal Anda - inilah mengapa kompiler yang paling banyak digunakan menggunakan pengurai turunan rekursif-tulisan tangan.

Ada satu hal yang harus Anda perhatikan dengan generator parser: kadang-kadang bisa menolak tata bahasa Anda. Untuk ikhtisar dari berbagai jenis parser dan bagaimana mereka dapat menggigit Anda, Anda mungkin ingin memulai di sini . Di Sini Anda dapat menemukan gambaran umum 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 kepada Anda.

Dalam kasus ini, menggunakan parser rekursif-keturunan yang ditulis tangan mungkin yang terbaik. Walaupun 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 tulisan tangan juga biasanya berkinerja lebih baik daripada yang dihasilkan, dengan asumsi kualitas parser 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 mengurai 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 bagus yang dapat Anda gunakan kembali'

Ini adalah jalur yang saat ini saya jalani: 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 berpikir tentang bagaimana saya ingin dapat menggunakan kode saya dan menulis kode 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 parser

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

Kecepatan tidak menjadi masalah bagi saya, saya memilih untuk mengimplementasikan parser Earley. Implementasi lanjutan dari pengurai Earley telah ditunjukkan menjadi 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 ambigu yang 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 yang 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 sewenang-wenang 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.

78
Alex ten Brink

Jika Anda belum pernah menulis parser, saya sarankan Anda melakukannya. Ini menyenangkan, dan Anda belajar bagaimana segala sesuatu bekerja, dan Anda belajar untuk menghargai upaya yang membuat parser dan lexer generator menyelamatkan Anda dari melakukan waktu berikutnya yang Anda butuhkan pengurai.

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

22
user1249

Keuntungan 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 pengurai 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 ia menggunakan YACC untuk implementasi pertama C++ (lihat Desain dan Evolusi C++ ). Dalam kasus pertama, dia berharap dia menulis parser keturunan rekursif sendiri sebagai gantinya!

14
Macneil

Opsi 3: Baik (Roll generator parser Anda sendiri)

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

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.

10
Peter Boughton

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

Ada banyak ketertarikan pada generator parser pada masa-masa awal, dimotivasi oleh sintaksis bahasa yang sangat rumit (beberapa 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).

Hari 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.

8
John R. Strohm

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, hampir 10 tahun yang lalu, jadi saya tidak ingat persisnya - 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 tergantung 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 cukup mudah [~ # ~] bnf [~ # ~] yang mudah diimplementasikan di yacc.

MENAMBAHKAN sebagai tanggapan terhadap Macneil: yacc memberikan abstraksi yang sangat kuat yang memungkinkan pemrogram berpikir dalam hal terminal, non-terminal, produksi dan hal-hal seperti itu. Juga, ketika menerapkan fungsi yylex(), 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 parsing murni dengan file yang dimuat dalam memori; jika kami memiliki masalah buffering file, ya tidak akan menjadi alat pilihan kami untuk menyelesaikannya.

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

6
azheglov

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.

3
GrandmasterB

Itu sepenuhnya tergantung pada apa yang Anda perlu uraikan. Bisakah Anda menggulung sendiri lebih cepat dari yang Anda bisa mengenai lexer? Apakah barang yang akan 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 benar-benar menyukai lemon parser , 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 merasa Anda akan kembali menggunakan salah satu yang ada, tetapi menggaruk gatal jika Anda harus :)

3
Tim Post

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. Generatornya masih sesuatu yang harus Anda lakukan, dan menurut saya itu tidak banyak. lebih mudah dari sebelumnya, tetapi kemudian membangun generator untuk DSL yang baik dan sederhana adalah salah satu bagian termudah dari latihan ini.

Membaca itu, saya akan mengatakan bahwa hari-hari penulisan parser Anda 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 masuk jauh ke dalam masalah serius yang 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 menginginkan semuanya, maka roll sendiri.

3
Gary Rowe

Keuntungan besar untuk 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.

2
philosodad

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 status dan panjang switch-cases, yang dapat meningkatkan ukuran kode sumber kecuali Anda .gitignore mereka.

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

1
Ming-Tang

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

0
JBRWilkinson