Menerapkan fitur PEG yang tersisa

Setelah saya mengumpulkan semua bagian dari generator parser PEG bersama di posting sebelumnya, saya siap untuk menunjukkan bagaimana menerapkan beberapa hal menarik lainnya.

Kami akan mempertimbangkan fitur PEG berikut:

• Item bernama: NAME=item (nama dapat digunakan dalam aksi)
• Lihat-lihat: &item (positif) dan !item (negatif)
• Mengelompokkan item dalam tanda kurung: ( item item ... )
• Item opsional: [item item ...] dan item?
• Duplikat item: item* (nol atau lebih) dan item+ (satu atau lebih)

Argumen Bernama

Mari kita mulai dengan elemen bernama. Ini nyaman ketika kita memiliki beberapa dari mereka dalam satu alternatif untuk aturan yang sama, misalnya:

 expr: term '+' term 

Kita bisa merujuk ke term kedua dengan menambahkan angka 1 ke nama variabel, sehingga dalam tindakan ternyata seperti ini:

 expr: term '+' term { term + term1 } 

Tetapi tidak semua orang menyukainya, dan secara pribadi, saya lebih suka menulis sesuatu seperti ini:

 expr: left=term '+' right=term { left + right } 

Ini mudah didukung dalam tata bahasa meta dengan mengubah aturan untuk item sebagai berikut:

 item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } atom: | NAME { name.string } | STRING { string.string } 

(Di mana atom hanyalah item lama)

Ini mengharuskan kami untuk menambahkan definisi kelas NamedItem ke grammar.py . Ini adalah salah satu kelas data yang saya sebutkan sebelumnya - juga memiliki atribut name dan item .

Kita juga perlu membuat perubahan kecil pada generator kode, yang akan saya tinggalkan sebagai latihan untuk pembaca (atau Anda dapat melihat ke repositori saya :-). Kode yang dihasilkan sekarang akan menetapkan hasil pencocokan setiap elemen ke variabel dengan nama yang ditentukan, dan bukan dengan nama yang diperoleh dari nama aturan elemen. Ini juga akan berfungsi untuk elemen yang token (salah satu dari bentuk NAME atau string literal seperti ':=' ).

Lihat ke depan

Diikuti oleh lookahead. Anda mungkin menemukan konsep ini dalam ekspresi reguler. Selama pencarian maju, alternatif yang diuraikan dapat segera ditolak atau diterima, tanpa menggeser pointer tokenizer.

Bahkan, lookahead dapat digunakan sebagai cara yang lebih elegan untuk menghilangkan kebingungan dengan pengecualian parser, yang saya tulis di artikel sebelumnya. Alih-alih mengizinkan tindakan untuk menolak alternatif yang sudah diterima dengan mengembalikan Tidak Ada, kita dapat menambahkan instruksi sebelum OP untuk mengecualikan "}" . Aturan lama tampak seperti ini:

  | OP { None if op.string in ("{", "}") else op.string } 

Versi baru terlihat seperti ini:

  | !"}" OP { op.string } 

Ini mentransfer braket keriting yang memproses dari aksi ke tata bahasa, di mana tempatnya. Kita tidak perlu memeriksa "{" , karena itu sesuai dengan alternatif sebelumnya (pada kenyataannya, ini juga berlaku untuk versi lama, tapi saya lupa tentang hal itu :-).

Kami menambahkan tata bahasa untuk lookaheads ke aturan untuk item sebagai berikut:

 item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } | "&" atom { Lookahead(atom, True) } | "!" atom { Lookahead(atom, False) } 

Sekali lagi, kita perlu menambahkan dataclass Lookahead ke grammar.py (dan mengimpornya ke @subheader !) Dan memodifikasi generator sedikit dengan menambahkan metode pembantu berikut:

  def lookahead(self, positive, func, *args): mark = self.mark() ok = func(*args) is not None self.reset(mark) return ok == positive 

Dalam kasus kami, kode yang dihasilkan untuk alternatif ini terlihat seperti ini:

  if (True and self.lookahead(False, self.expect, "}") and (op := self.expect(OP)) ): return op . string 

Seperti yang dapat Anda lihat dari fragmen tata bahasa di atas, lookahead tidak bisa mendapatkan nama yang tepat. Ini mudah untuk diperbaiki, tetapi saya masih tidak tahu seberapa berguna itu. Selain itu, untuk prakiraan negatif, nilainya akan selalu None .

Pengelompokan dalam kurung

Sekarang mari kita implementasikan grup dengan tanda kurung. Tempat terbaik untuk menambahkannya ke metagram adalah aturan untuk atom :

 atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } 

Dua alternatif pertama tidak berubah. Tindakan untuk alternatif baru menggunakan peretasan (yang implementasinya tetap tidak dapat dijelaskan), yang memungkinkan meta-parser untuk menambahkan aturan baru ke tata bahasa dengan cepat. Fungsi helper ini (didefinisikan dalam meta-parser) mengembalikan nama objek aturan baru. Ini akan terdiri dari awalan tetap diikuti oleh angka, yang membuatnya unik, misalnya, _synthetic_rule_1 .

Anda mungkin bertanya apa yang terjadi jika aturan sintetis akhirnya dibatalkan. Saya tidak tahu bagaimana cara menghindari ini, tetapi seharusnya tidak ada masalah - dalam kasus terburuk akan ada aturan yang tidak digunakan dalam tata bahasa. Dan berkat memoisasi, tindakan yang sama tidak akan pernah dieksekusi dua kali untuk posisi input yang sama, jadi ini bukan masalah juga (tetapi bahkan jika itu masalahnya, dalam kasus terburuk kita akan memiliki aturan mati).

Menggunakan alts di dalam tanda kurung berarti kita dapat mendefinisikan bar vertikal sebagai pembatas dalam grup. Misalnya, bahwa solusi tindakan baru kami tidak akan secara kebetulan cocok dengan { , kami dapat mengubah negasi menjadi ini:

  | !("{" | "}") OP { op.string } 

Selain itu, grup juga dapat memuat aksi! Ini tidak akan membantu dalam menyelesaikan masalah dengan tindakan, tetapi dalam situasi lain mungkin bermanfaat. Dan karena kita dalam hal apa pun menghasilkan aturan sintetik, itu tidak memerlukan pekerjaan tambahan untuk mengimplementasikannya (kecuali untuk implementasi synthetic_rule :-).

Item opsional

Seperti pada pgen lama, saya menggunakan tanda kurung siku untuk menunjukkan sekelompok token opsional. Di sinilah ternyata bermanfaat. Misalnya, aturan tata bahasa yang menjelaskan Python for loop dapat menggunakannya untuk menunjukkan bahwa ekstensi yang else bisa ada. Dan lagi kita dapat memperluas tata bahasa untuk atom sebagai berikut:

 atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } 

Di sini Maybe adalah kelas data lain, dengan atribut item tunggal. Kami memodifikasi pembuat kode sehingga hasil dari fungsi sintetis tidak gagal jika nilai ini None . Untuk melakukan ini, Anda dapat menambahkan or True dalam implementasi. Misalnya, untuk [term] :

 if (True and ((term := self.term()) or True) ): return term 

Item duplikat

Beralih ke pengulangan adalah fungsi PEG lain yang bermanfaat (notasi dipinjam dari ekspresi reguler dan juga digunakan dalam pgen). Ada dua bentuk: menambahkan * ke atom berarti "nol atau lebih pengulangan", sementara menambahkan + berarti "satu atau lebih pengulangan". Untuk alasan lain, saya harus menulis ulang aturan tata bahasa untuk item dan atom , menambahkan aturan perantara, yang saya sebut molecule :

 item: | NAME '=' molecule { NamedItem(name.string, molecule) } | "&" atom { Lookahead(atom) } | "!" atom { Lookahead(atom, False) } | molecule { molecule } molecule: | atom "?" { Maybe(atom) } | atom "*" { Loop(atom, False) } | atom "+" { Loop(atom, True) } | atom { atom } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } atom: | NAME { name.string } | STRING {string.string } | "(" alts ")" { self.synthetic_rule(alts) } 

Perhatikan bahwa ini memperkenalkan sintaks alternatif untuk elemen opsional ( atom? ). Itu tidak memerlukan upaya implementasi tambahan, karena ini hanyalah cara lain untuk membuat simpul Maybe .

Refactoring aturan ini diperlukan karena saya tidak ingin membuat situasi tertentu valid:

• pengulangan opsional (karena ini hanya pengulangan nol atau lebih);
• pengulangan (internal akan menangkap semua pertandingan, karena PEG selalu menggunakan algoritma serakah)
• nilai opsional yang diulangi (yang akan mengganggu analisis jika elemen opsional tidak cocok).

Namun, ini masih bukan solusi ideal, karena Anda dapat menulis sesuatu seperti (foo?)* . Penting untuk menambahkan tanda centang pada situasi ini di generator parser, tapi saya akan melakukan ini di luar artikel.

Kelas data Loop memiliki dua atribut: item dan nonempty . Kode yang dihasilkan akan menggunakan metode helper parser loop() . Ini sangat mirip dengan metode lookahead() yang ditunjukkan sebelumnya:

  def loop(self, nonempty, func, *args): mark = self.mark() nodes = [] while node := func(*args) is not None: nodes.append(node) if len(nodes) >= nonempty: return nodes self.reset(mark) return None 

Jika nonempty False (dalam arti tata bahasa adalah * ), maka ini tidak akan menyebabkan kesalahan. Tidak ada entri yang ditemukan, dan daftar kosong akan dikembalikan. Untuk mewujudkannya, kami mengimplementasikan parser generator sehingga is not None ditambahkan. Pemeriksaan yang lebih lunak dari pos sebelumnya akan mengembalikan False jika daftar kosong.

Itu saja untuk hari ini! Saya akan membahas "cut" ( ~ ) operator yang hadir di TatSu, tetapi sejauh ini saya belum memiliki kesempatan untuk menghadapinya. Saya bahkan belum siap untuk membahasnya - dokumentasi TatSu hanya memberikan contoh sederhana yang sedikit menarik minat saya. Saya tidak menemukannya di generator PEG-parser lain, jadi, mungkin, fitur ini hanya TatSu. Mungkin suatu hari nanti saya akan menceritakan tentang dia. (Sementara itu, saya menerapkannya untuk berjaga-jaga, Anda tidak pernah tahu. :-)

Saya pikir artikel selanjutnya adalah tentang pengalaman saya menulis tata bahasa PEG yang dapat menganalisis tata bahasa Python. Saya akan memberi tahu Anda bagaimana sprint pengembang kernel Python terjadi, yang berada di London minggu ini dengan dukungan logistik dari Bloomberg dan dukungan keuangan dari PSF dan beberapa perusahaan lain (misalnya, Dropbox membayar saya hotel dan penerbangan). Terima kasih khusus kepada Emily Morhouse dan Pablo Galindo Salgado, yang banyak membantu dalam mengimplementasikan alat dan tes. Selanjutnya, kita akan menulis tes kinerja, dan kemudian kita akan menambahkan tindakan ke tata bahasa ini sehingga dapat membuat pohon AST yang dapat dikompilasi oleh kompiler kode byte CPython. Ada banyak hal yang lebih menarik di depan!

Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0