Minggu ini kita membuat generator parser "independen", yaitu, akan menghasilkan parser sendiri.
Konten Seri Parser Python PEG Jadi, kita sudah memiliki generator parser, yang sebagian adalah parser tata bahasa. Kita bisa menyebutnya meta-parser. Meta-parser bekerja mirip dengan yang dihasilkan: GrammarParser mewarisi dari Parser dan menggunakan mekanisme yang sama mark() / reset() / hope() . Namun, di sana semuanya ditulis dengan tangan. Tapi benarkah itu?
Saat mendesain kompiler, biasanya kompiler ditulis dalam bahasa yang dikompilasi. Saya ingat dengan cinta bahwa kompiler Pascal yang saya gunakan ketika saya pertama kali belajar memprogram ditulis dalam Pascal itu sendiri, GCC ditulis dalam C, dan kompiler Rust ditulis dalam Rust.
Bagaimana cara melakukannya? Pada awalnya, terapkan kompiler untuk subset atau versi bahasa sebelumnya dalam bahasa lain. (Biarkan saya mengingatkan Anda bahwa kompiler Pascal asli ditulis dalam FORTRAN!) Kemudian kompiler baru ditulis dalam bahasa target dan dikompilasi menggunakan kompilasi bootstrap yang diimplementasikan di awal. Segera setelah kompiler baru mulai bekerja dengan cukup baik, kompiler bootstrap dihapus, dan setiap versi bahasa atau kompiler berikutnya dibatasi untuk apa yang dapat dikompilasi menggunakan versi kompilator sebelumnya.
Mari kita lakukan untuk parser meta kita. Kami akan menulis tata bahasa untuk tata bahasa (meta-grammar) dan kemudian menghasilkan meta-parser baru dari ini. Untungnya, saya merencanakan langkah ini dari awal, jadi itu akan sangat sederhana. Tindakan yang kami tambahkan dalam episode sebelumnya adalah komponen penting karena kami tidak perlu mengubah generator, jadi kami perlu membuat struktur data yang kompatibel.
Berikut ini adalah versi sederhana dari metagram tanpa tindakan:
start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING
Saya akan menunjukkan cara menambahkan tindakan dari bawah ke atas. Ingat dari Bagian 3 bahwa ada objek Rule yang memiliki name dan alts . Awalnya, alts hanyalah daftar daftar garis (daftar eksternal untuk alternatif dan daftar internal untuk setiap elemen alternatif), tetapi untuk mengimplementasikan tindakan, saya mengubahnya sehingga alternatif diwakili oleh objek Alt dengan items dan atribut action . Elemen masih direpresentasikan sebagai string sederhana. Untuk item kami dapatkan:
item: NAME { name.string } | STRING { string.string }
Ini memerlukan sedikit penjelasan: ketika penganalisa memproses token, ia mengembalikan objek TokenInfo yang memiliki type , string dan atribut lainnya. Kami tidak ingin generator menangani objek TokenInfo , jadi tindakan di sini mengekstrak string dari token. Perhatikan bahwa untuk semua token huruf besar, seperti NAME , parser yang dihasilkan menggunakan versi string (di sini name ) sebagai nama variabel.
Berikutnya adalah items yang harus mengembalikan daftar string:
items: item items { [item] + items } | item { [item] }
Di sini saya menggunakan aturan rekursif kanan, jadi kami tidak bergantung pada pemrosesan rekursi kiri yang ditambahkan di Bagian 5. (Mengapa tidak? Selalu baik untuk menjaga hal-hal sesederhana mungkin, dan tata bahasa ini tidak akan banyak mendapat manfaat dari perubahan dalam rekursi kiri) Perhatikan bahwa satu item terdaftar, tetapi items rekursif tidak, karena sudah daftar.
Aturan alt untuk membuat objek Alt :
alt: items { Alt(items) }
Saya akan menghilangkan tindakan untuk rules dan start , karena mereka didefinisikan dengan cara ini.
Namun, ada dua pertanyaan terbuka. Pertama, bagaimana cara menemukan definisi kelas Rule dan Alt ? Untuk melakukan ini, kita perlu menambahkan beberapa pernyataan import ke kode yang dihasilkan. Cara paling sederhana adalah dengan mengedarkan flag ke generator, yang mengatakan "ini adalah meta-grammar", dan biarkan generator memasukkan import tambahan di awal program yang dihasilkan. Tetapi sekarang setelah kita memiliki tindakan, banyak parser lain juga ingin menyesuaikan impor mereka, jadi mengapa tidak melihat apakah kita dapat menerapkan pendekatan yang lebih umum.
Ada banyak cara untuk mengimplementasikannya. Mekanisme sederhana dan umum adalah menambahkan bagian "definisi variabel" di bagian atas tata bahasa dan memungkinkan generator untuk menggunakan variabel-variabel ini untuk mengontrol berbagai aspek dari kode yang dihasilkan. Saya memutuskan untuk menggunakan simbol @ untuk mulai mendefinisikan variabel, diikuti oleh nama variabel ( NAME ) dan nilai ( STRING ). Sebagai contoh, kita dapat meletakkan blok kode berikut di bagian atas meta-grammar:
@subheader "from grammar import Rule, Alt"
Generator parser akan mencetak nilai variabel subheader setelah impor standar, yang ditambahkan secara default (misalnya, untuk mengimpor memoize ). Jika Anda ingin beberapa elemen import , Anda dapat menggunakan string dengan tanda kutip tiga, misalnya,
@subheader """ from token import OP from grammar import Rule, Alt """
Ini mudah ditambahkan ke meta-grammar: kita akan memecah aturan start menjadi yang berikut:
start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE
(Saya tidak ingat mengapa saya menyebutnya "meta", tapi saya memilih nama ini ketika saya menulis kode, dan saya akan menaatinya. :-)
Kita harus menambahkan ini ke metaparser bootstrap. Sekarang tata bahasa bukan hanya daftar aturan, mari kita tambahkan objek tata bahasa dengan metas dan atribut rules . Kami dapat mengatur tindakan berikut:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) }
(Perhatikan bahwa meta mengembalikan tuple; dan juga menggunakan eval() untuk memproses kutipan string.)
Saya tidak menyebutkan implementasi tindakan dalam aturan untuk alt ! Alasannya adalah mereka agak berantakan. Tetapi tidak masuk akal untuk menunda lebih jauh, jadi di sini:
alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Kotoran dalam definisi ini disebabkan oleh keinginan saya untuk membuat kode Python sewenang-wenang valid antara kurung aksi keriting, termasuk bersarang di kurung kurawal lain. Untuk tujuan ini, kami menggunakan token OP khusus, yang dihasilkan tokenizer kami untuk semua tanda baca yang dikenali oleh Python (mengembalikan satu token dengan tipe OP untuk operator multi-karakter, seperti <= atau ** ). Satu-satunya token lain yang dapat terjadi dalam ekspresi Python adalah nama, angka, dan string. Dengan demikian, kode antara kawat gigi luar aksi, tampaknya, dapat diekspresikan melalui pengulangan NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP .
Sayangnya, ini tidak akan berhasil karena OP juga cocok dengan kurung kurawal, dan karena penganalisa PEG selalu serakah, ini akan menangkap braket penutup, dan kita tidak akan pernah melihat akhir aksinya. Oleh karena itu, kami menambahkan sedikit penyesuaian, memungkinkan tindakan untuk melempar kesalahan pilihan alternatif, mengembalikan Tidak ada. Saya tidak tahu apakah ini merupakan kejadian standar pada parser PEG lainnya - saya membuat ini di tempat ketika saya harus menyelesaikan masalah mengenali tanda kurung penutup (bahkan tanpa pasangan bersarang). Ini tampaknya bekerja dengan baik, dan saya pikir itu cocok dengan filosofi keseluruhan analisis PEG. Ini dapat dianggap sebagai bentuk pandangan jauh ke depan yang khusus (yang akan saya bahas di bawah).
Dengan menggunakan hack kecil ini, kita bisa membuat perbandingan pada kejatuhan OP pada kurung kurawal. Maka perbandingan stuff dan action akan dimungkinkan.
Dengan hal-hal ini, meta-grammar dapat diurai oleh bootstrap metaparser, dan generator dapat mengubahnya menjadi meta-parser baru yang dapat menganalisis sendiri. Dan, yang penting, meta-parser baru masih dapat menguraikan meta-grammar yang sama. Jika kita mengkompilasi meta-grammar dengan meta-compiler baru, hasilnya sama: ini membuktikan bahwa meta-parser yang dihasilkan bekerja dengan benar.
Inilah tata bahasa meta tindakan lengkap. Dia dapat menganalisis dirinya sendiri, karena dia tahu cara menggabungkan garis panjang:
@subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string }
Sekarang kami memiliki tata bahasa yang berfungsi, kami hampir siap untuk melakukan beberapa perbaikan.
Tetapi pertama-tama Anda perlu berpikir sedikit: garis kosong! Ternyata modul tokenize stdlib membuat token tambahan untuk melacak tokenize baris yang tidak signifikan (token NL ) dan komentar (token COMMENT ). Alih-alih memasukkan mereka dalam tata bahasa (saya mencobanya, tidak ada banyak kesenangan!), Ada sepotong kode yang sangat sederhana yang bisa kita tambahkan ke kelas tokenizer kita untuk memfilternya. Inilah metode peek_token disempurnakan:
def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos]
Ini sepenuhnya menghapus token NL dan COMMENT , jadi kita tidak perlu lagi khawatir tentang mereka dalam tata bahasa.
Akhirnya, mari kita lakukan peningkatan pada tata bahasa meta! Semuanya murni kosmetik: Saya tidak suka kalau dipaksa menulis semua alternatif dalam satu baris. Tata bahasa meta yang saya tunjukkan di atas sebenarnya tidak menguraikan sendiri karena hal-hal seperti:
start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
Ini disebabkan oleh fakta bahwa tokenizer membuat token NEWLINE di akhir baris pertama, dan pada saat ini meta-parser akan menganggap ini sebagai akhir dari aturan. Selain itu, NEWLINE ini akan diikuti oleh token INDENT , karena baris berikutnya indentasi. Sampai awal aturan berikutnya, token DEDENT juga akan hadir.
Inilah cara mengatasinya. Untuk memahami perilaku modul tokenize , kita dapat melihat urutan token yang dihasilkan untuk blok indentasi dengan menjalankan modul tokenize sebagai skrip dan memberikannya beberapa teks:
$ python -m tokenize foo bar baz dah dum ^D
Kita melihat bahwa ini menghasilkan urutan token berikut (saya sedikit menyederhanakan keluaran dari kode di atas):
NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE
Dengan demikian, sekelompok string yang dipilih ditunjukkan oleh DEDENT dan DEDENT . Sekarang kita dapat menulis ulang aturan meta-grammar untuk rule sebagai berikut:
rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts }
(Saya memecah tindakan menjadi garis sehingga mereka membaca secara normal dalam kolom teks yang sempit. Ini dimungkinkan karena tokenizer mengabaikan pemisah garis di dalam kurung kurawal yang sesuai.)
Keindahan dari hal ini adalah kita bahkan tidak perlu mengubah generator: struktur data yang dibuat oleh tata bahasa yang ditingkatkan ini sama dengan sebelumnya. Perhatikan juga opsi ketiga untuk rule : ini memungkinkan kita untuk menulis:
start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) }
bahwa beberapa mungkin merasa lebih bersih daripada versi yang saya tunjukkan sebelumnya. Kedua bentuk itu mudah diselesaikan, jadi kami tidak perlu berdebat tentang gaya.
Dalam posting berikutnya, saya akan menunjukkan bagaimana saya mengimplementasikan berbagai fungsi PEG, seperti elemen opsional, pengulangan, dan tooltips. (Sejujurnya, saya berencana untuk membicarakannya di artikel ini, tetapi sudah terlalu besar. Jadi saya akan membaginya menjadi dua bagian.)
Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0