Saya menyebutkan rekursi kiri sebagai batu sandungan beberapa kali, dan inilah saatnya untuk mengetahuinya. Masalah utama adalah bahwa parser dengan keturunan rekursif kiri langsung crash karena stack overflow.
Konten Seri Parser Python PEG Pertimbangkan aturan tata bahasa hipotetis ini:
expr: expr '+' term | term
Jika kami menerapkan potongan tata bahasa ini ke metode parser rekursif kiri, kami akan mendapatkan sesuatu seperti berikut:
def expr(): if expr() and expect('+') and term(): return True if term(): return True return False
Jadi, expr() dimulai dengan panggilan ke expr() , yang dimulai dengan panggilan ke expr() , yang dimulai dengan panggilan ... Ini hanya dapat diakhiri dengan stack overflow, yang dinyatakan sebagai pengecualian RecursionError .
Solusi tradisional adalah menulis ulang tata bahasa. Di bagian sebelumnya, saya melakukan hal itu. Bahkan, aturan tata bahasa di atas dapat ditulis ulang sebagai berikut:
expr: term '+' expr | term
Namun, pada langkah membangun pohon parse, bentuknya akan berbeda. Ini dapat merusak situasi jika kita menambahkan operator '-' ke tata bahasa (karena a - (b - c) tidak sama dengan (a - b) - c ). Ini biasanya diselesaikan dengan fungsi PEG yang lebih kuat, seperti pengelompokan dan iterasi, dan kita bisa menulis ulang aturan di atas sebagai:
expr: term ('+' term)*
Sebenarnya, ini adalah bagaimana tata bahasa Python saat ini ditulis untuk pgen parser (yang memiliki masalah yang sama dengan aturan rekursif kiri).
Namun, ada masalah kecil: karena operator seperti '+' dan '-' (dengan Python) sebagian besar adalah biner, ketika kita menganalisis sesuatu seperti a + b + c , kita harus melalui hasil parsing (yang pada dasarnya daftar ['a', '+', 'b', '+', 'c'] ) untuk membuat pohon parse rekursif kiri (yang akan terlihat seperti ini [['a', '+', 'b'] , '+', 'c'] ).
Tata bahasa rekursif kiri asli sudah mengisyaratkan asosiasi yang diinginkan, jadi alangkah baiknya untuk menghasilkan parser langsung dari formulir ini. Dan kita bisa! Seorang pembaca menunjukkan trik yang bagus dengan bukti matematika yang mudah diimplementasikan. Sekarang saya akan coba jelaskan.
Mari kita lihat contoh input foo + bar + baz . Pohon parse yang ingin kita dapatkan dari ini berhubungan dengan (foo + bar) + baz . Ini membutuhkan tiga panggilan rekursif kiri ke fungsi expr() : satu sesuai dengan operator tingkat atas '+' (yaitu, yang kedua); satu lagi - ke operator internal '+' (mis. yang pertama); dan yang ketiga adalah pilihan alternatif kedua (mis., term ).
Karena saya tidak pandai menggambar diagram nyata menggunakan alat khusus, saya akan menunjukkan ini di sini menggunakan seni ASCII:
expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz'
Idenya adalah bahwa dalam fungsi expr() , kita memerlukan "oracle" yang memberitahu kita apakah akan memilih alternatif pertama (yaitu, panggilan rekursif ke expr() ) atau yang kedua (yaitu, panggilan term() panggilan). Pada panggilan pertama ke expr() oracle harus memberitahu kita untuk mengikuti alternatif pertama ( expr() ); dalam panggilan kedua (rekursif) - sama, tetapi pada panggilan ketiga harus meminta kita untuk memanggil term() . Dalam kode tersebut, akan terlihat seperti ini:
def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False
Bagaimana cara menulis ramalan seperti itu? Mari kita lihat ... Kita dapat mencoba melacak jumlah panggilan expr() rekursif kiri) expr() di tumpukan panggilan dan membandingkannya dengan jumlah operator '+' dalam ekspresi berikut. Jika tumpukan panggilan lebih dalam dari jumlah pernyataan, oracle akan mengembalikan false (memaksa kita untuk memilih term() ). Saya tidak sabar untuk mengimplementasikan ini dengan sys._getframe() , tetapi ada cara yang lebih baik: mari balikkan tumpukan panggilan!
Idenya adalah bahwa kita mulai dengan panggilan di mana oracle mengembalikan false, dan menyimpan hasilnya. Ini memberi kita urutan expr() -> term() -> 'foo' . (Seharusnya mengembalikan pohon parse untuk term awal, yaitu, 'foo' . Kode di atas hanya mengembalikan True , tetapi di bagian kedua dari rangkaian artikel saya sudah menunjukkan cara mengembalikan pohon parse sebagai gantinya.) Peramalan seperti itu mudah diterapkan, karena seharusnya kembalikan False pada panggilan pertama - tidak ada tumpukan yang memeriksa atau mengintip masa depan yang diperlukan.
Kemudian kami memanggil expr() lagi, dan kali ini oracle mengembalikan True , tetapi alih-alih panggilan rekursif kiri ke expr() kami mengganti hasil yang disimpan dari panggilan sebelumnya. Dan karena operator yang diharapkan '+' dan token yang sesuai berikutnya juga hadir, ini akan memberi kita pohon parse untuk foo + bar .
Sekali lagi kita ulangi algoritma, dan lagi semuanya ternyata: kali ini kita mendapatkan parsing tree untuk ekspresi penuh, dan itu benar-benar rekursif kiri ( (foo + bar) + baz ).
Lalu kami ulangi algoritma itu lagi. Tapi kali ini, meskipun Oracle mengembalikan True , dan hasil simpanan dari panggilan sebelumnya juga tersedia, tidak ada lagi operator '+' , dan alternatif pertama gagal. Jadi, kami mencoba opsi kedua, yang berhasil, dan hanya menemukan istilah awal ( 'foo' ). Hasil ini lebih buruk daripada yang diperoleh dari alternatif pertama, jadi pada tahap ini kami berhenti dan menyimpan analisis terpanjang (mis. (foo + bar) + baz ).
Untuk mengubahnya menjadi kode kerja, saya pertama-tama memodifikasi sedikit algoritma untuk menggabungkan panggilan oracle() dengan panggilan rekursif kiri ke expr() . Sebut saja oracle_expr() . Kode:
def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False
Selanjutnya, kita akan menulis pembungkus yang mengimplementasikan logika yang dijelaskan di atas. Ini menggunakan variabel global (jangan khawatir, saya akan menyingkirkannya nanti). Fungsi oracle_expr() akan membaca variabel global, dan wrapper akan mengendalikannya:
saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result
Kode, tentu saja, mengerikan, tetapi setidaknya itu menyampaikan esensi dari algoritma. Mari kita refactor supaya kita bisa bangga dengannya.
Pemahaman yang paling penting (yang menjadi milik saya, meskipun saya mungkin bukan yang pertama memperhatikan ini) adalah bahwa kita dapat menggunakan cache memoisasi alih-alih variabel global. Di dalamnya kita akan menyimpan hasil dari panggilan ke panggilan. Jadi kita menyingkirkan fungsi oracle_expr() , karena kita dapat menghasilkan panggilan standar ke expr() terlepas dari apakah itu dalam posisi rekursif di sebelah kiri atau di sebelah kanan.
Jadi, kita membutuhkan dekorator @memoize_left_rec terpisah, yang hanya digunakan untuk aturan rekursif kiri. Ini memanggil fungsi oracle_expr() , menarik nilai yang disimpan dari cache memoisasi, dan berisi loop yang memanggil fungsi expr() beberapa kali, sampai setiap hasil baru sebanding dengan bagian yang lebih lama dari data input daripada yang sebelumnya. Dan, tentu saja, karena setiap posisi input dan masing-masing metode parsing di-cache secara terpisah, itu tidak peduli tentang backtracking atau beberapa aturan rekursif (misalnya, dalam tata bahasa mainan yang saya gunakan, baik expr dan term dibiarkan rekursif).
Kelebihan lain dari prototipe yang saya buat di bagian ketiga adalah membuatnya mudah untuk memeriksa apakah hasil baru lebih panjang dari yang lama: metode mark() mengembalikan indeks dalam array token input, jadi kita bisa menggunakannya daripada parsed_length .
Saya menghilangkan bukti mengapa algoritma ini selalu bekerja, tidak peduli seberapa gilanya tata bahasanya. Bahkan, saya bahkan tidak membacanya. Saya melihat bahwa ini berfungsi untuk kasus-kasus sederhana, seperti expr dalam tata bahasa mainan saya, serta untuk kasus-kasus yang agak lebih rumit (misalnya, menggunakan rekursi kiri yang tersembunyi di balik elemen opsional dalam suatu alternatif, atau menggunakan rekursi bersama antara beberapa aturan). Situasi paling sulit yang dapat saya ingat dalam tata bahasa Python masih diselesaikan oleh algoritma ini, jadi saya hanya percaya pada teorema dan orang-orang yang membuktikannya.
Mari kita menulis kode pertempuran.
Pertama, generator parser harus menentukan aturan mana yang dibiarkan rekursif. Ini adalah masalah yang diselesaikan dalam teori grafik. Saya tidak akan menunjukkan algoritme di sini, dan sebenarnya saya bahkan ingin lebih menyederhanakannya. Saya berasumsi bahwa satu-satunya aturan kiri-rekursif dalam tata bahasa secara langsung kiri-rekursif, seperti expr dalam tata bahasa mainan kami. Kemudian, untuk memeriksa kekambuhan kiri, Anda hanya perlu mencari alternatif yang akan dimulai dengan nama aturan saat ini:
def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False
Sekarang kita akan mengubah generator parser sehingga untuk aturan rekursif kiri menghasilkan dekorator lain. Ingatlah bahwa di bagian ketiga, kami membungkus semua metode parser di @memoize . Sekarang kita akan membuat satu perubahan kecil di generator sehingga untuk aturan rekursif kiri kita menggunakan @memoize_left_rec , dan kemudian kita akan menerapkan sihir dalam dekorator memoize_left_rec . Sisa generator dan kode lainnya tidak perlu diubah! (Meskipun saya harus mengutak-atik kode visualisasi)
Untuk referensi, berikut adalah dekorator @memoize asli @memoize , disalin dari bagian 3. Ingat bahwa self adalah contoh Parser yang memiliki atribut memo (diinisialisasi dengan kamus kosong) dan mark() dan reset() metode yang mendapatkan dan mengatur posisi saat ini tokenizer:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
@memoize mengingat panggilan sebelumnya untuk setiap posisi dalam aliran input - untuk setiap posisi dalam array (malas) dari token input terdapat kamus memo terpisah. Empat baris pertama memoize_wrapper didedikasikan untuk mendapatkan kamus memo benar.
Dan ini adalah @memoize_left_rec . Hanya cabang else yang sedikit berbeda dari implementasi di @memoize di atas:
def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else:
Mungkin menarik bagaimana ini bekerja untuk metode expr() . Mari kita lihat bagaimana kode berikut akan dijalankan:
@memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None
Pada contoh parsing foo + bar + baz .
Setiap kali Anda memanggil fungsi expr() , panggilan itu "ketagihan" oleh dekorator yang mencari panggilan sebelumnya di posisi saat ini. Pada panggilan pertama, kita sampai ke cabang yang else , di mana kita berulang kali memanggil fungsi dihiasi expr() . Tentunya, kita akan kembali ke dekorator terlebih dahulu, tetapi kali ini sudah ada nilai dalam cache, sehingga rekursi terputus.
Apa yang terjadi selanjutnya? Nilai cache awal dihitung pada baris ini:
Ini mengarah pada fakta bahwa expr() dikembalikan tidak None , setelah yang pertama if in expr() jatuh (ketika expr: = self.expr() ). Artinya, kita beralih ke yang kedua if , yang berhasil mengenali term (dalam contoh kita, 'foo' ) dan expr mengembalikan instance Node . Dari mana kita akan kembali? Untuk while di dekorator. Kami memperbarui cache memoisasi dengan hasil baru (instance Node ), dan kemudian menjalankan iterasi berikutnya.
expr() dipanggil lagi, dan kali ini panggilan rekursif yang dicegat mengembalikan instance Node (istilah) yang di-cache, dan kemudian melanjutkan ke panggilan yang expect('+') . Semuanya beres, karena kita sekarang berada di operator '+' pertama. Setelah itu, kami mencari istilah yang juga berhasil (ditemukan 'bar' ).
Jadi sekarang expr() , yang sudah dikenali foo + bar , kembali ke while , yang melakukan tindakan yang sama: memperbarui cache memoisasi dengan hasil yang baru (lebih lama) dan memulai iterasi berikutnya.
Game ini diulangi lagi. Sekali lagi, expr() panggilan rekursif yang dicegat expr() mengambil hasil baru (kali ini foo + bar ) dari cache, dan kami berharap melihat '+' (kedua) dan term lain ( 'baz' ). Kami membuat Node mewakili (foo + bar) + baz , dan mengembalikannya ke while , yang meletakkannya di cache dan mengulanginya lagi.
Tapi sekarang kita akan pergi bersama cabang algoritma yang lain. Kami berharap dapat bertemu '+' , tetapi tidak menemukannya! Jadi, panggilan untuk expr() kembali ke alternatif kedua, dan hanya mengembalikan term . Ketika ini muncul sebelum while , ternyata hasil ini lebih pendek dari yang terakhir. Jadi itu memotong dan mengembalikan hasil yang lebih panjang ( (foo + bar) + baz ) kepada orang yang memprakarsai panggilan expr() (misalnya, panggilan statement() tidak ditampilkan di sini).
Jadi, di sinilah kisah hari ini berakhir: kami berhasil menerapkan rekursi kiri dalam pengurai PEG. Minggu depan saya berencana untuk membahas menambahkan "tindakan" ke tata bahasa, yang akan memungkinkan kita untuk menyesuaikan hasil yang dikembalikan oleh metode parser untuk alternatif ini (bukannya selalu mengembalikan instance Node ).
Jika Anda ingin bermain-main dengan kode, periksa repositori GitHub . (Saya juga menambahkan kode visualisasi untuk rekursi kiri, tapi saya tidak cukup senang dengan itu, jadi saya tidak akan memberikan tautan ke sini.)
Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0