Beberapa tahun yang lalu, seseorang bertanya kepada saya apakah masuk akal untuk mengubah Python ke pengurai PEG (atau ke tata bahasa PEG; Saya tidak ingat persis siapa dan kapan itu). Kemudian saya memandangnya sedikit, tetapi saya tidak sampai pada kesimpulan, dan karena itu saya menjatuhkan topik ini. Saya baru-baru ini belajar lebih banyak tentang PEG (Parsing Expression Grammars, Parsing Expression Grammar), dan sekarang saya pikir ini adalah alternatif yang menarik untuk generator parser yang ditulis sendiri yang dikembangkan 30 tahun yang lalu ketika saya baru mulai bekerja dengan Python. Saya menyebutnya "pgen", dan ini mungkin merupakan bagian pertama dari kode yang saya tulis untuk Python.
Konten Seri Parser Python PEG Alasan saya saat ini tertarik pada pengurai PEG adalah karena saya agak terganggu oleh keterbatasan pgen. Ini dibangun atas implementasi LL (1) sendiri, yang memiliki sejumlah asumsi. Misalnya, saya tidak suka aturan tata bahasa yang bisa menghasilkan baris kosong, jadi saya melarangnya. Dan dengan demikian menyederhanakan algoritma untuk membuat tabel parsing. Saya juga menemukan notasi tata bahasa seperti EBNF saya sendiri, yang saya masih sangat suka.
Berikut adalah beberapa masalah dengan pgen yang mengganggu saya. "1" dalam nama LL (1) menyiratkan bahwa itu hanya menganalisis token berikutnya, dan ini membatasi kemampuan kita untuk membuat aturan tata bahasa yang baik. Misalnya, pernyataan Python dapat berupa ekspresi atau penugasan (atau sesuatu yang lain, tetapi semuanya dimulai dengan kata kunci yang disorot, seperti if atau def ). Saya ingin menggambarkan sintaks menggunakan notasi pgen. Perhatikan bahwa ini hanyalah contoh sederhana, yang merupakan himpunan bagian dari Python, seperti yang biasanya dilakukan ketika mendeskripsikan desain bahasa. Ini akan menjadi tata bahasa mainan yang akan berguna untuk demonstrasi lebih lanjut.
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
Beberapa kata tentang notasi: NAME dan NUMBER adalah token dan sudah ditentukan sebelumnya di luar tata bahasa. String kutipan dari tipe '+' atau 'if' juga merupakan token. (Mari kita tunda membicarakannya lain kali) Aturan tata bahasa dimulai dengan nama aturan, diikuti oleh : dan kemudian satu atau lebih alternatif, dipisahkan oleh | .
Masalahnya adalah bahwa jika Anda menggambarkan tata bahasa dengan cara ini, maka pgen tidak akan berfungsi. Ini disebabkan oleh kenyataan bahwa beberapa aturan ( expr dan term ) dibiarkan rekursif, dan ia tidak cukup pintar untuk menangani situasi seperti itu dengan benar. Biasanya ini diselesaikan dengan menulis ulang hanya aturan ini, meninggalkan aturan lain tidak berubah. Sebagai contoh:
expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)*
Ini mengungkapkan beberapa kemungkinan EBNF di pgen: Anda dapat membuat sarang alternatif dalam kurung dan membuat pengulangan dengan menempatkan * setelah elemen. Jadi aturan untuk ekspresi expr sini berarti "itu adalah istilah yang diikuti oleh nol atau lebih pengulangan dari urutan <istilah plus atau minus, diikuti oleh istilah>". Tata bahasa ini menggunakan bahasa yang sama dengan versi pertama, tetapi sekali lagi itu tidak mencerminkan maksud desain bahasa. Secara khusus, ini tidak menunjukkan bahwa operator terikat di sebelah kiri, dan ini penting ketika Anda mencoba untuk menghasilkan kode.
Tetapi ada masalah lain yang mengganggu dalam contoh ini (dan juga Python). Karena hanya menguraikan satu token, penganalisis tidak dapat menentukan apa yang dilihatnya - awal ekspresi atau tugas. Pada awal pemrosesan operator, parser harus memutuskan hanya token pertama, alternatif apa yang diurai. (Kenapa? Ini adalah bagaimana implementasi parsing dalam pgen bekerja) Katakanlah program kami adalah sebagai berikut:
answer = 42
Program ini diwakili oleh tiga token: NAME (dengan nilai answer ), = dan NUMBER (dengan nilai 42 ). Satu-satunya hal yang kita ketahui di awal parsing adalah token NAME pertama. Aturan yang kami coba uraikan pada tahap ini adalah statement (karakter awal tata bahasa). Tiga alternatif didefinisikan untuk itu: expr , assignment dan if_statement . Kami dapat segera mengecualikan if_statement , karena token sebelumnya bukan if . Tetapi expr dan assignment dapat dimulai dengan token NAME , dan karenanya, pgen menolak tata bahasa kami sebagai ambigu.
Ini tidak sepenuhnya benar, karena secara teknis tata bahasa itu sendiri tidak; Saya tidak dapat menemukan formulasi yang lebih akurat, jadi mari kita membahas yang ini. Dan bagaimana pgen mengatasi ini? Itu menghitung sesuatu yang disebut set PERTAMA untuk setiap aturan tata bahasa, dan jika mereka berpotongan, maka itu melempar pengecualian.
Jadi, tidak bisakah kita menyelesaikan masalah ini dengan menyediakan parser dengan buffer tampilan yang lebih besar? Sebagai contoh kita, token pratinjau kedua sudah cukup, karena dalam tata bahasa ini token penugasan kedua harus = . Tetapi dalam bahasa yang lebih realistis seperti Python, Anda mungkin memerlukan penyangga tidak terbatas, karena konten di sebelah kiri = token = dapat kompleks secara arbitrer, misalnya:
table[index + 1].name.first = 'Steven'
Dalam hal ini, Anda harus mengurai sepuluh token sebelum kita bertemu = . Tapi saya yakinkan Anda, mungkin ada ekspresi yang lebih lama. Untuk mengatasi masalah ini di pgen, kami mengubah penganalisis tata bahasa untuk menerima beberapa ekspresi yang salah, menambahkan cek tambahan di lintasan berikutnya. Ini akan melempar kesalahan SyntaxError jika tidak cocok dengan sisi kiri dan kanan. Untuk bahasa mainan kami, tulislah yang berikut ini:
statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr]
Kurung kotak menunjukkan bagian opsional. Dan kemudian pada pass berikutnya dari kompiler (katakanlah, ketika menghasilkan bytecode) kami memeriksa apakah = atau tidak, dan jika demikian, kami memeriksa bahwa sisi kiri cocok dengan sintaks target .
Ada masalah serupa untuk argumen panggilan fungsi. Kami ingin menulis sesuatu seperti ini (sekali lagi, dalam versi sintaks Python yang disederhanakan):
call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr
Tetapi algoritma penguraian, yang hanya akan mempertimbangkan token berikutnya, tidak dapat memberi tahu pengurai apakah NAME pada awal argumen adalah awal dari posarg (karena expr dapat dimulai dengan NAME ) atau awal kwarg . Sekali lagi, pengurai Python saat ini memecahkan masalah ini dengan menentukan:
arg: expr ['=' expr]
dan kemudian menyelesaikan alternatif di pass compiler berikutnya. (Kami bahkan membuat sedikit kesalahan dan mengurai foo((a) = 1) sama seperti foo(a = 1) . Ini diperbaiki hanya dengan Python 3.8)
Jadi bagaimana cara pengurai PEG mengatasi masalah ini? Menggunakan buffer cadangan yang tak terbatas! Implementasinya yang khas menggunakan apa yang disebut packrat parser, yang tidak hanya memuat seluruh program ke dalam memori sebelum menguraikannya, tetapi juga memungkinkan penganalisa untuk digulung kembali ke sejumlah token yang sewenang-wenang kembali. Meskipun istilah PEG terutama mengacu pada notasi gramatikal, parser yang dihasilkan dari tata bahasa PEG biasanya parser dengan turunan rekursif dan pengembalian tak terbatas. Packrat parser membuat ego efisien dengan mengingat aturan yang telah diuraikan untuk posisi tertentu.
Ini menyederhanakan algoritma, tetapi tentu saja ada harga: memori. Tiga puluh tahun yang lalu, saya punya alasan bagus untuk menggunakan LL (1): memori itu mahal. Dia (seperti teknologi lain seperti LALR (1), dipopulerkan oleh YACC) menggunakan mesin negara dan tumpukan untuk secara efisien membangun pohon parse.
Untungnya, komputer yang menjalankan CPython memiliki lebih banyak memori daripada 30 tahun yang lalu, dan menyimpan seluruh file dalam memori tidak lagi menjadi masalah. Sebagai contoh, file non-test terbesar di stdlib yang bisa saya temukan adalah _pydecimal.py , yang memakan waktu sekitar 223 kb. Di dunia gigabyte, ini pada dasarnya bukan apa-apa, yang membuat saya memandang parser dengan berbeda.
Tapi ada satu hal lagi di parser CPython saat ini yang mengganggu saya. Kompiler adalah hal yang kompleks, dan implementasi untuk CPython tidak terkecuali. Meskipun hasil parser pgen adalah parsing tree, parser tree tidak langsung digunakan sebagai input untuk generator bytecode: pertama-tama dikonversi ke pohon sintaksis abstrak (AST), dan baru kemudian AST ini dikompilasi menjadi bytecode. (Faktanya, ini bahkan lebih rumit di sana, tetapi untuk saat ini kami tidak akan membahas lebih rinci)
Mengapa tidak segera mengkompilasi dari pohon parse? Persis seperti itu, tetapi sekitar 15 tahun yang lalu kami menemukan bahwa kompilator terlalu rumit. Jadi kami mengisolasi AST dan fase transformasi AST dari pohon parse secara terpisah. Ketika Python berevolusi, AST tetap lebih stabil daripada parsing, yang mengurangi kemungkinan kesalahan dalam kompiler.
AST juga lebih mudah untuk bekerja dengan perpustakaan pihak ketiga yang ingin menguji kode Python. Itu dapat diperoleh dengan menggunakan modul ast populer. Ini juga memungkinkan Anda untuk membuat node dari awal dan memodifikasi yang sudah ada, serta mengkompilasi bagian menjadi bytecode. Yang terakhir memungkinkan pembuatan seluruh industri ekstensi bahasa untuk Python. (Pohon parse juga dapat diakses oleh pengguna Python melalui modul parsing, tetapi bekerja dengannya jauh lebih sulit; karena itu, ia tidak begitu populer)
Sekarang saya ingin menggabungkan hal-hal ini dan melihat apakah kita dapat membuat parser baru untuk CPython, yang menggunakan PEG dan packrat untuk membuat AST langsung selama parsing. Dengan demikian, akan mungkin untuk menghilangkan generasi pohon perantara parsing, yang dapat menghemat memori kita, bahkan meskipun menggunakan buffer tak terbatas untuk token. Saya masih dalam proses implementasi, tetapi saya sudah memiliki prototipe yang dapat mengkompilasi subset Python ke AST dengan kecepatan yang sama dengan parser CPython saat ini. Namun, ia menggunakan lebih banyak memori, dan bagi saya tampaknya memperluas subset ke dalam bahasa lengkap akan memperlambat pengurai PEG. Namun sejauh ini saya belum memikirkan optimasi, jadi saya akan terus bekerja.
Keuntungan terakhir beralih ke PEG adalah memberikan lebih banyak fleksibilitas untuk evolusi bahasa lebih lanjut. Di masa lalu, dikatakan bahwa kendala LL (1) dalam pgen membuat tata bahasa Python tetap sederhana. Ini mungkin benar, tetapi kami memiliki banyak proses lain untuk mencegah pertumbuhan bahasa yang tidak terkendali (terutama proses PEP, yang dibantu oleh persyaratan kompatibilitas mundur yang sangat ketat dan struktur manajemen baru). Jadi saya tidak khawatir tentang itu.
Saya ingin memberi tahu lebih banyak tentang PEG dan implementasi saya, tetapi akan ada di posting berikutnya setelah saya membersihkan kode.
Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0